CS 886: Graph Neural Networks

Logistics

• Instructor: Kimon Fountoulakis
• Seminar Time: Tu/Th 1pm to 2:20pm
• Office hours: Monday 1pm to 2pm.

Overview

Learning from multi-modal datasets is currently one of the most prominent topics in artificial intelligence. The reason behind this trend is that many applications, such as recommendation systems and fraud detection, require the combination of different types of data. In addition, it is often the case that data exhibit relations that need to be captured for downstream applications. In this course, we are interested in multi-modal data that combine a graph—i.e., a set of nodes and edges—with attributes for each node and/or edge. The attributes of the nodes and edges capture information about the nodes and edges themselves, while the edges between the nodes capture relations among them. Capturing relations is particularly helpful for applications where we are trying to make predictions for nodes given neighborhood data.

One of the most prominent and principled ways of handling such multi-modal data for downstream tasks such as node classification is graph neural networks. Graph neural network models can mix hand-crafted or automatically learned attributes of the nodes while taking into account relational information among the nodes. Therefore, the output vector representation of the graph neural network contains global and local information about the nodes. This contrasts with neural networks that only learn from the attributes of entities.

This seminar-based course will cover seminal work in the space of graph neural networks. Below I provide the topics and architectures which we will study during the course.

Topics

1. Generalization performance of graph neural networks
2. Expressive power of graph neural networks
3. Large language models and graphs
4. Neural algorithmic reasoning
5. Generative graph neural networks
6. Self-supervised learning in graphs
7. Oversmoothing
8. Scalability

Architectures:

1. Spectral and spatial convolutional graph neural networks
2. Graph attention networks
3. Invariant and equivariant graph neural networks
4. General message passing graph neural networks
5. Higher-order graph neural networks
6. Graph neural networks for heterogeneous graphs

We will focus on both practical and theoretical aspects of machine learning on graphs. Practical aspects include, scalability and performance on real data. Examples of theoretical questions include: what does convolution do to the input data? Does convolution improve generalization compared to not using a graph? How do multiple convolutions change the data and how do they affect generalization?

Course structure: The seminar is based on weekly student presentations, discussions, a midterm and a final project.

(Tentative) Schedule

The schedule below is subject to change:

Week	Date	Topic	Readings	Slides
1	1/7	Introduction, problems and applications (Kimon lecturing)	- Geometric Deep Learning (Chapter 1) - Geometric foundations of Deep Learning - Towards Geometric Deep Learning I: On the Shoulders of Giants - Towards Geometric Deep Learning II: The Perceptron Affair - Towards Geometric Deep Learning III: First Geometric Architectures - A Gentle Introduction to Graph Neural Networks - Intro to graph neural networks (ML Tech Talks) - Foundations of Graph Neural Networks	Slides
1	1/9	Spatial graph convolution and its theoretical performance on simple random data (Kimon lecturing)	- Semi-Supervised Classification with Graph Convolutional Networks - Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization - Code for reproducing the experiments - Effects of Graph Convolutions in Multi-layer Networks - Code for reproducing the experiments - Theory of Graph Neural Networks: Representation and Learning - PyTorch code for GCN - Example code	Slides, Slides
2	1/14	Graph Attention Network, Graph Attention Retrospective, and Optimality of Message Passing (Kimon lecturing)	- Graph Attention Networks - PyTorch Code - Graph Attention Retrospective - Code for reproducing the experiments - Video lecture - Theory of Graph Neural Networks: Representation and Learning - Optimality of Message-Passing Architectures for Sparse Graphs	Slides, Slides
2	1/16	A popular spectral graph convolution model, message passing, symmetries and reasoning (Kimon lecturing)	- Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering - What Can Neural Networks Reason About?	Slides, Slides
3	1/21	Expressive power, Part 1	- The Expressive Power of Graph Neural Networks (Chapter 5.3) - The Expressive Power of Graph Neural Networks (Chapter 5.4, up to 5.4.2.3), included)	Slides
3	1/23	Expressive power, Part 2	- The Expressive Power of Graph Neural Networks (Chapter 5.4.2.4, up to 5.4.3.2), included) - What graph neural networks cannot learn: depth vs width	Slides, Slides
4	1/28	Higher-order graph neural networks	- k-hop Graph Neural Networks - Multi-Hop Attention Graph Neural Network	Slides, Slides
4	1/30	Higher-order graph neural networks and their expressive power	- Provably Powerful Graph Networks - How Powerful are K-hop Message Passing Graph Neural Networks	Slides, Slides
5	2/4	Invariant and Equivariant Graph Neural Networks, Part 1	- An Introduction To Invariant Graph Networks, Part 1 and An Introduction To Invariant Graph Networks, Part 2 - Invariant and Equivariant Graph Networks	Slides, Slides
5	2/6	Invariant and Equivariant Graph Neural Networks, Part 2	- Building powerful and equivariant graph neural networks with structural message-passing - Universal Invariant and Equivariant Graph Neural Networks	Slides, Slides
6	2/11	GNNs for heterogeneous graphs	- Modeling Relational Data with Graph Convolutional Networks - MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding	Slides, Slides
6	2/13	Oversmoothing Part 1	- DeepGCNs: Can GCNs Go as Deep as CNNs? - Simple and Deep Graph Convolutional Networks	Slides, Slides
7	2/18	Reading Week
7	2/20	Reading Week
8	2/25	Oversmoothing Part 2	- Not too little, not too much: a theoretical analysis of graph (over)smoothing - Analysis of Corrected Graph Convolutions	Slides, Slides
8	2/27	Scalable GNNs, Part 1	- Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks - SIGN: Scalable Inception Graph Neural Networks	Slides, Slides
9	3/4	Scalable GNNs, Part 2	- GraphSAINT: Graph Sampling Based Inductive Learning Method - Training Graph Neural Networks with 1000 Layers	Slides, Slides
9	3/6	Self-supervised learning in graphs	- Graph Self-Supervised Learning: A Survey	Slides
10	3/11	Link prediction	- Link Prediction Based on Graph Neural Networks - Line Graph Neural Networks for Link Prediction	Slides, Slides
10	3/13	GNNs for combinatorial optimization, Part 1	- Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs - Simulation of Graph Algorithms with Looped Transformers	Slides
11	3/18	GNNs for combinatorial optimization, Part 2	- Attention, Learn to Solve Routing Problems! - Exact Combinatorial Optimization with Graph Convolutional Neural Networks	Slides, Slides
11	3/20	GNNs + LLMs, Part 1	- Talk like a Graph: Encoding Graphs for Large Language Models - Can Language Models Solve Graph Problems in Natural Language?	Slides, Slides
12	3/25	GNNs + LLMs, Part 2	- Graph Neural Prompting with Large Language Models - G-Retriever: Retrieval-Augmented Generation for Textual Graph Understanding and Question Answering	Slides, Slides
12	3/27	Algorithmic Reasoning, Part 1	- Neural Algorithmic Reasoning and A Generalist Neural Algorithmic Learner - Deep Equilibrium Algorithmic Reasoning	Slides, Slides
13	4/1	Algorithmic Reasoning, Part 2	- Pointer Graph Networks - Relational Attention: Generalizing Transformers for Graph-Structured Tasks
13	4/3	GNNs + LLMs, Part 3	- A Survey of Large Language Models for Graphs

Readings

• Geometric Deep Learning, Michael M. Bronstein, Joan Bruna, Taco Cohen, Petar Veličković, 2021
• Theory of Graph Neural Networks: Representation and Learning, Stefanie Jegelka, 2022
• Graph Representation Learning Book, William L. Hamilton, 2020
• Graph Neural Networks, Lingfei Wu, Peng Cui, Jian Pei, Liang Zhao, (2022)

Other courses online related to machine learning on graphs

• Machine Learning with Graphs, Jure Leskovec, Stanford
• Graph Representation Learning, William L. Hamilton, McGill
• Introduction to Graph Neural Networks, Xavier Bresson, Nanyang Techinical University and NYU
• Recent Developments in Graph Network Architectures, Xavier Bresson, Nanyang Techinical University
• Benchmarking GNNs, Xavier Bresson, Nanyang Techinical University
• Foundations of Graph Neural Networks, Petar Veličković, DeepMind
• Geometric Deep Learning Course
• Machine Learning for the Working Mathematician: Geometric Deep Learning, Geordie Williamson, The University of Syndney
• Advanced lectures on community detection, Laurent Massoulie, INRIA Paris

Online reading seminars

• LoGaG: Learning on Graphs and Geometry Reading Group

Code

• PyTorch Geometric
• Deep Graph Library

Competitions

• Open Graph Benchmark
• CLRS Algorithmic Reasoning Benchmark
• The CLRS-Text Algorithmic Reasoning Language Benchmark

Datasets

• PyTorch Geometric Datasets
• Open Graph Benchmark
• HyperGraphs
• TUDatasets
• Non Homophily Benchmarks
• Graph Learning Benchmarks
• Hetionet
• Heterogeneous graph benchmarks
• Long Range Graph Benchmark
• IGB-Datasets

Workload Breakdown

• Class Participation: 15%
• Midterm Project: 20%
• Presentations: 25%
• Final Project: 40%

Midterm Project

This is a 3-page paper, along with (if relevant) the source code of your project, including instructions on how to run it. You may use your midterm project as a foundation for your final project, which will be 6 pages. Please see the next section below for details.

Options for the midterm project:

• Option A (Empirical evaluation): Pick a problem that interests you. Implement and experiment with several graph neural network methods to tackle this problem.
• Option B (Method design): Identify a problem for which there are no satisfying approaches. Develop a new graph neural network architecture to tackle this problem. Analyze theoretically and/or empirically the performance of your technique.
• Option C (Theoretical analysis): Identify a problem or a graph neural network architecture for which theoretical performance (e.g., complexity, performance on random data, expressivity) is not well understood. Analyze the properties of this problem or technique.

Information about the project template and the source code is given below.

• Project Paper: The project papers will be 3 pages. You can have extra pages for the references and the appendix. They will be written in the two-column ICML format, using the ICML template which you can find in the corresponding website.
• Project Source Code: Please put your source code into github and include a link in your project writeup. On the github page, please document exactly how to run your source code.

Final Project

There is one main deliverable of your project, a 6-page paper and (if relevant) the source code of your project with instructions to run your code. Note that you are allowed to use the midterm project (3 pages) as a foundation for this project.

Options for the final project:

• Option A (Empirical evaluation): Pick a problem that interests you. Implement and experiment with several graph neural network methods to tackle this problem.
• Option B (Method design): Identify a problem for which there are no satisfying approaches. Develop a new graph neural network architecture to tackle this problem. Analyze theoretically and/or empirically the performance of your technique.
• Option C (Theoretical analysis): Identify a problem or a graph neural network architecture for which theoretical performance (e.g., complexity, performance on random data, expressivity) is not well understood. Analyze the properties of this problem or technique.

Information about the project template and the source code is given below.

• Project Paper: The project papers will be 6 pages. You can have extra pages for the references and the appendix. They will be written in the two-column ICML format, using the ICML template which you can find in the corresponding website.
• Project Source Code: Please put your source code into github and include a link in your project writeup. On the github page, please document exactly how to run your source code.

Publish Your Project

Although not required for the course, keep in mind that I am more than happy to help you publish your final project. For example, in CS886 2024, Robert Wang published his final project at NeurIPS 2024.

Presentations

Each student will be doing 2 presentations (estimated number, based on previous years) in the term. Each presentation will be about 40 to 50 minutes long plus questions. Here are the important points summarizing what you have to do for your presentations.

• You must present with slides. The content in your slides should be your own but you can use others' materials, e.g., figures from the paper we are reading, when necessary and by crediting your source on your slide.
• Please have a separate slide, or set of slides, for each of the 4 questions below:
  • What is the problem?
  • Why is it important?
  • Why don't previous methods work on that problem?
  • What is the solution to the problem the authors propose?
  • What interesting research questions does the paper raise?
• It is very helpful to demonstrate the ideas in the paper through examples. So try to have examples in your presentation.

University of Waterloo Academic Integrity Policy

The University of Waterloo Senate Undergraduate Council has also approved the following message outlining University of Waterloo policy on academic integrity and associated policies.

Academic Integrity

In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. Check the Office of Academic Integrity's website for more information. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in, and our, of the classroom.

Grievance

A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 - Student Petitions and Grievances, Section 4. When in doubt please be certain to contact the department's administrative assistant who will provide further assistance.

Discipline

A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about “rules” for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. For information on categories of offenses and types of penalties, students should refer to Policy 71-Student Discipline. For typical penalties check Guidelines for the Assessment of Penalties.

Avoiding Academic Offenses

Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy.

Appeals

A decision made or a penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72 - Student Appeals.

Note for students with disabilities

The AccessAbility Services Office (AAS), located in Needles Hall, Room 1401, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with the AAS at the beginning of each academic term.