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, extensions to methods incorporating multi-way relationships among data (e.g., hypergraphs, simplicial complexes) will be discussed. Exercises on real-world data will be carried out using Python and/or Matlab. 

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 2: Deep Learning on Graphs

• Design of graph convolutional neural networks 

• Pooling on graphs 

• Graph attention mechanisms 

• Applications to graph and node classification problems

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.