Graph Neural Networks

This is an introductory course on Graph Neural Networks. Many systems in nature and in human-made settings are complex, with each part interacting with the whole. Networks provide a fundamental way to model such systems. By studying local properties of a network, one can infer information about the entire system, reflecting local-to-global phenomena that appear across modern mathematics. Students will develop the ability to work with network and graph data and use mathematical abstractions to formulate questions about datasets whose structure is not immediately apparent.

Module 1 motivates graphs and highlights their prevalence in both natural and human-made physical systems. It also introduces classical graph invariants and problems. Module 2 focuses on the spectrum of adjacency and Laplacian matrices and their relationship to information in networks. Module 3 covers node embeddings and the neural message passing framework, which is central to Graph Neural Networks. It also discusses attention mechanisms and the role of spectral methods in this context.

The course starts with an introduction to graphs and their properties. Natural examples will be seen which are not obvious to be networks. Notions of equivariance and invariance with respect to the permutation group will be introduced via matrices. We will then discuss the matrices associated to a graph. The spectrum of these matrices will be introduced and will see how it relates to the information in a network. The message passing framework will be introduced and the usual GNN architectures will be shown to fir this paradigm. Finally, the role of the spectrum in the message passing neural network will be clarified.

By the end of this course, each student will have had the opportunity to:

• Understand the need for abstract machinery of graphs.
• Analyse datasets and apply graph neural networks.
• Synthesize the interconnection between different concepts and use them in projects.

By the end of this course, each student will have had the opportunity to:

• Identify situations where graphical abstraction is relevant. | Knowledge Outcome  
• Explore and summarize various characteristics of network data. | Comprehend Outcome 
• Carry out classical experiments to interpret graph data.| Apply Outcome 
• Visualize social/ biological networks and find a problem. | Analyse Outcome 
• Experiment with various GNNs and decide a course of action. | Evaluate Outcome  
• Produce a viable algorithm to improve existing architectures. | Synthesize Outcome 

• Networks, Crowds and Markets, Easley and Kleinberg.
• Graph Representation Learning, Hamilton.
• Hands-On Graph Neural Networks Using Python, Labonne.

• Spectral Graph Theory, Chung.
• Networks, Newman.

Articles (Non-exhaustive)

• DeepWalk: Online Learning of Social Representations by B. Perozzi et. al.
• Neural Message Passing for Quantum Chemistry, Gilmer et. al.
• Kipf & Welling (2017)  Semi-supervised Classification with GCNs
• Xu et al. (2019)  How Powerful Are Graph Neural Networks?
• Alon & Yahav (2021)  On the Bottleneck of GNNs and Its Practical Implications