ESE 5291 Special Topics in Information Science & Learning: Foundations of Graph Signal Processing and Graph Machine Learning
Course Overview
This course introduces the mathematical, statistical, and algorithmic foundations of Graph Signal Processing (GSP) and Graph Machine Learning (GML), with emphasis on systems, signal processing, and learning from graph-structured data. The course bridges graph theory, random graph models, and modern graph neural networks. The course connects spectral graph theory, random graph models, and signal processing on graphs with the latest advances on graph machine learning. Students will engage with current research in graph-based learning through paper readings, student presentations, and a semester-long project.
Course Objectives
- Develop operator-theoretic understanding of graph Laplacians and spectral graph filters.
- Analyze graph neural networks from signal processing and dynamical systems perspectives.
- Evaluate stability and generalization of graph learning models.
- Apply graph ML techniques to networked and distributed engineering systems.
- Critically assess contemporary research literature in graph signal processing and graph machine learning.
Prerequisites
Linear algebra (spectral theory), probability theory, optimization, signals and systems, and prior exposure to machine learning. Programming experience in Python/PyTorch required.
Readings
- Ortega, Antonio, et al. “Graph signal processing: Overview, challenges, and applications.” Proceedings of the IEEE 106.5 (2018): 808-828.
- Sandryhaila, Aliaksei, and José MF Moura. “Discrete signal processing on graphs.” IEEE Transactions on Signal Processing 61.7 (2013): 1644-1656.
- Hamilton, William L. “Graph representation learning.” Morgan & Claypool Publishers, 2020.
- Albert-László Barabási, Network Science
Weekly Schedule
| Week | Topics | Slides |
|---|---|---|
| 1 | Intro to GSP; graph diffusion processes; graph Laplacian and graph Fourier transform, comparison with classical DSP. | Lecture 1 Lecture 2 |
| 2 | Graph Convolutions and Properties: locality, shift and permutation invariance, stability of spectral filters, perturbation analysis; explicitly link these properties of filters to the core principle of Graph Neural Networks (GNNs). | Lecture 3 Lecture 4 |
| 3 | Graph Filter Design and Diffusion Processes: heat kernels, polynomial filters, distributed implementation, types of graph learning problems; preview of GNNs: design of polynomial filters and their direct relationship to early spectral GNNs (e.g., ChebNet). | Lecture 5 |
| 4 | Random Graph Models and Structure-Based Inference: stochastic block models, random geometric graphs; spectral Clustering as a foundational technique for Community Detection and data partitioning on graphs, emphasizing the connection between graph theory and real-world inference tasks. | |
| 5 | In-depth study of Message Passing GNNs, GCN, ChebNet, GraphSAGE (can all be seen as graph convolutional networks): expressivity and Weisfeiler-Lehman test. | |
| 6 | Oversmoothing and oversquashing of GNNs: dynamical systems view of GNN layers, Dirichlet energy, effective resistance, receptive field growth and Jacobian sensitivity analysis. | |
| 7 | Graph Limit Analysis with Graphons: graphons, graphon convolution and graphon neural networks, focusing on non-asymptotic convergence and size-transferability; study the critical problem of training models on small, random graphs and proving their reliable deployment on large-scale graphs. | |
| 8 | Graph Limit Analysis with Manifolds: manifolds and the Laplace-Beltrami operator, spectral convergence, and manifold neural networks; examine stability and performance guarantees when transferring models between discrete graph data and continuous geometric spaces (manifolds). | |
| 9 | Graph Attention Networks and Graph Transformers: attention as adaptive filtering, positional encodings for transformers. | |
| 10 | Graph Generative Models: graph variational autoencoders (GVAEs), introduction to diffusion models and flow matching with extensions on generating graph models. | |
| 11 | Graph Learning from Signals: Laplacian learning (inferring graph topology from smooth signals), geometric graph constructions (building graphs like k-NN from high-dimensional data), robust graph signal recovery (reconstructing signals from noisy/partial data). | |
| 12 | Dynamic Graph Learning: representations of dynamic graphs, temporal graph learning models, evaluation tasks and metrics. | |
| 13 | Graph Machine Learning in Practice: drug discovery and molecular property prediction in biomedical data analysis, interatomic potential learning in material science, brain connectome analysis in neuroscience. | |
| 14 | ||
| 15 |