Graph Signal Processing and Learning

Objectives

The goal of this course is to make students able to represent information distributed over a graph, and to perform analysis, processing, and learning from data collected over, e.g., technological, biological, or information networks. The course will introduce fundamental tools from algebraic graph theory and graph signal processing, which will be used to perform several graph machine learning tasks such as graph filtering, sampling and recovery, spectral clustering, topology inference from data, and graph neural networks. Finally, it is shown how to formulate and solve distributed machine learning problems, suitable for big data applications, where optimization and data processing must be necessarily performed over multiple agents. 

Prerequisite: basic knowledge of calculus, linear algebra, and digital signal processing.

Final Exam: Oral exam and/or computer project.

Lessons: 12 hours, corresponding to 2 CFU

Dates: The course will be held in the "Aula DIET 09" of the DIET Dept., according to the following schedule:

• 08-07-24 ,  10.00 - 13.00 

• 09-07-24 ,  10.00 - 13.00

• 10-07-24,   14.00 - 17.00

• 11-07-24,   10.00 - 13.00  

Contents

Part 1: Graphs

• Algebraic graph theory

• Graph Partitioning, spectral clustering

• Random Graph Models: Erdos-Renyi, small-world, scale-free, random geometric graphs

Part 2: Graph Signal Processing

• Graph Signals

• Basics of graph signal processing: Graph Fourier Transform, graph filters

• Sampling and recovery of graph signals, sampling strategies

• Diffusion processes, Convolutional Graph Filters, design of filters

Part 3: Deep Learning on Graphs

• Design of graph convolutional neural networks 

• Pooling on graphs 

• Graph attention mechanisms 

• Applications to graph and node classification problems

Part 4:  Distributed Optimization and Learning

• Distributed consensus optimization

• Federated learning

Textbooks and resources:

[1]  Slides and codes 

[2] M.E.J. Newman, Networks: An Introduction, Oxford, UK: Oxford University Press. 

[3] Ortega, A., Frossard, P., Kovačević, J., Moura, J. M., & Vandergheynst, P. (2018). Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5), 808-828.

[4]  P. Di Lorenzo, S. Barbarossa, and P. Banelli, Sampling and Recovery of Graph Signals, Cooperative and Graph Signal Processing, P. Djuric and C. Richard Eds., Elsevier, 2018. 

[5] Isufi, E., Gama, F., Shuman, D. I., & Segarra, S. (2022). Graph filters for signal processing and machine learning on graphs. arXiv preprint arXiv:2211.08854, 2022. 

[6] Ruiz, L., Gama, F., & Ribeiro, A. (2021). Graph neural networks: Architectures, stability, and transferability. Proceedings of the IEEE, 109(5), 660-682.

[7] Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007). Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE, 95(1), 215-233. 

[8] Li, T., Sahu, A. K., Talwalkar, A., & Smith, V. (2020). Federated learning: Challenges, methods, and future directions. IEEE signal processing magazine, 37(3), 50-60. 

[9]  S. Boyd et al., Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Foundations and Trends in Machine Learning, 3(1):1–122, 2011.