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
Grading
- Discussion participation: 10%
- Homework assignments: 40%
- Research Paper Presentation: 20%
- Course Project (proposal 5%, midterm report 5%, final paper 10% + presentation 10%): 30%
Weekly Schedule
| Week | Topics | Deliverables |
|---|---|---|
| 1 | Intro to GSP; graph diffusion processes; graph Laplacian and graph Fourier transform, comparison with classical DSP. | |
| 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). | HW 1 out |
| 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). | |
| 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. | HW1 due, HW2 out |
| 5 | In-depth study of Message Passing GNNs, GCN, ChebNet, GraphSAGE (can all be seen as graph convolutional networks): expressivity and Weisfeiler-Lehman test. | Project proposal due |
| 6 | Oversmoothing and oversquashing of GNNs: dynamical systems view of GNN layers, Dirichlet energy, effective resistance, receptive field growth and Jacobian sensitivity analysis. | HW 2 due, HW 3 out |
| 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). | HW 3 due, HW 4 out |
| 9 | Graph Attention Networks and Graph Transformers: attention as adaptive filtering, positional encodings for transformers. | Project midterm report due |
| 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). | HW 4 due, HW 5 out |
| 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. | HW 5 due |
| 14 | Project presentation | |
| 15 | Final project report due |
Paper Presentation Requirement
Each student (or pair) selects a recent top-tier conference or journal paper. Deliverables include technical summary, methodological critique, reproducibility analysis (code execution as a bonus), and future research directions. Presentation length: 30 minutes.
Paper list will be provided. Students can also suggest papers that are relevant.
Course Project Options and Requirements
Topic Options:
Option A – Theory-Oriented:
Examples: Stability bounds and spectral analysis of graph machine learning models, size-transferability under graph limits.
Option B – Systems/Experimental:
Examples: GML for distributed sensor networks, dynamic multi-agent coordination with GML, transfer learning across different graph domains.
Option C – Hybrid Theory + Systems (Encouraged for PhD students):
Combine mathematical analysis with empirical validation.
Requirements:
Project proposal (2-3 pages): Single column NeurIPS conference style format. Define the problem and present a feasible plan, including problem statement, related works and background, proposed approach, experiment plan and expected contributions.
Project midterm report (4-6 pages): Show substantial progress and refine the direction, including preliminary results and analysis with revised plan for final project.
Project final report (6-10 pages): Present the full project as a mini conference paper, with introduction, related work, problem formulation, method or theory, experiments and analysis, conclusion and discussion.
Final project presentation: 12-15 mins presentation with 3-5 mins Q&A.
ESE-Relevant Application Areas
- Wireless sensor networks and distributed inference
- Networked control systems
- Medical data analysis
- Multi-agent systems and swarm robotics
- Molecular and material structure analysis