Conclusion

Chapter 1: The Core Ideas

Everything in graph ML reduces to a small set of ideas. If you understand these deeply, you can derive the rest. Here they are, one by one.

1. Message Passing: The Universal Primitive

At every layer l, each node v aggregates messages from its neighbors N(v), then updates its own representation:

The choice of AGG (sum, mean, max, attention-weighted) and UPD (MLP, GRU) defines the GNN variant. Sum = GIN (most expressive). Mean = GCN (normalizes by degree). Attention-weighted = GAT (learnable importance). The framework unifies hundreds of papers.

2. The WL Hierarchy: Expressiveness Has a Ceiling

The Weisfeiler-Lehman graph isomorphism test is the theoretical ceiling for message-passing GNNs. Two graphs that fool the 1-WL test (assign the same color sequence) are indistinguishable by any message-passing GNN, no matter how deep or wide. Regular graphs of the same size fool 1-WL. Going beyond requires higher-order WL (k-WL) or structural encodings.

3. Positional Encoding: Breaking Symmetry

Without positional encoding, all nodes in a symmetric graph get the same embedding. There's no way to distinguish node 3 from node 7 in a regular graph — they look identical to the GNN. Positional encodings break this symmetry by giving each node a unique structural signature: random walk landing probabilities, Laplacian eigenvectors, or distance to anchor nodes.

4. Graph-Level Pooling: From Nodes to Graphs

Many tasks need a graph-level representation (predict if this molecule is toxic). Graph pooling aggregates node representations into a single graph vector. Simple: sum/mean all node embeddings. Better: hierarchical pooling (DiffPool, MinCutPool) that mimics the hierarchical structure of real graphs.

Chapter 2: The Application Landscape

Graph ML is not one field solving one problem — it's a general framework that has been successfully applied across six major domains. Each domain has different graph types, different tasks, and different engineering challenges.

Chapter 3: What Changed (2017 → 2025)

The field of graph ML has changed completely in eight years. Not just incremental improvement — a fundamental shift in what's possible and how we think about the problem.

2017: The Beginning

Kipf and Welling publish GCN (December 2016/published 2017). It's a 2-layer network on the Cora citation graph, 1433 node features, 7 classes, 2708 nodes. Training takes seconds. The key insight: spectral graph convolution can be approximated by simple first-order neighborhood aggregation. This creates the field.

The Scaling Inflection (2019-2022)

OGB (Open Graph Benchmark) launches in 2020 — standard large-scale benchmarks. ogbn-products (2.4M nodes), ogbn-papers100M (111M nodes). Suddenly the question isn't "does it work on Cora?" but "does it work at web scale?" Mini-batch training, neighbor sampling (GraphSAGE), cluster-GCN, SIGN emerge to handle the scale challenge.

The Foundation Model Era (2023-2025)

The most dramatic shift: graph foundation models. Instead of training a separate GNN for each task and graph, can we train one massive model that transfers across graphs? This mirrors what GPT-3 did for text: one model, many tasks, zero-shot generalization.

Chapter 4: Open Problems

The most important thing a good course can give you is not just what we know, but what we don't know. Here are the four hardest open problems in graph ML — problems where a PhD thesis could make a real contribution.

Open Problem 1: Scalability to Billion-Node Graphs

The web-scale graph (Facebook social graph: 3B nodes, 300B edges) is too large for any current full-batch GNN. Even mini-batch methods with neighbor sampling struggle: sampling 2-hop neighborhoods for batch size 1000 might touch millions of nodes. Current workarounds (GraphSAGE, cluster-GCN, SIGN) all introduce approximation errors. A principled approach to exact inference on billion-node graphs doesn't exist yet.

Open Problem 2: Expressiveness Beyond 1-WL Without Cubic Cost

We know 1-WL GNNs can't distinguish certain graph pairs (regular graphs, triangles vs. 4-cycles). Higher-order WL (2-WL, 3-WL) is strictly more expressive but costs O(n²) or O(n³) per layer — unusable at scale. Is there a way to get k-WL expressiveness with O(n) cost? Some recent work (subgraph GNNs, DS-WL) takes steps toward this, but there's no clean answer yet.

Open Problem 3: Dynamic Graphs

Real graphs change over time. Twitter's follow graph changes every second. A protein interaction network changes during cell differentiation. Current GNNs are static: they're trained on a snapshot and can't efficiently update when edges/nodes appear or disappear. Temporal GNNs (TGAT, TGN) exist but are expensive. Efficient streaming graph learning remains open.

Open Problem 4: Interpretability

When a GNN predicts that a molecule is toxic, which structural patterns caused that prediction? GNNExplainer, PGExplainer, and similar methods attempt to find important subgraphs, but their fidelity is limited: the "explanation" doesn't always faithfully reflect the model's actual computation. For high-stakes domains (drug safety, credit scoring), this is a blocker for deployment.

Chapter 5: The Research Frontier

Three convergences are defining the next five years of graph ML research. Each combines graph learning with a currently dominant paradigm from the broader AI field.

Frontier 1: Graph + LLM

As covered in Lecture 16: LLMs give rich semantic understanding of node text; GNNs give structural reasoning. The question for 2025-2027: can we build a unified architecture that processes both modalities without treating them as separate? Graph Tokens approaches (mapping graph substructures to special tokens in the LLM's vocabulary) are the leading direction. If successful, this could enable LLMs to "think in graphs" natively.

Frontier 2: Graph + Diffusion

As covered in Lecture 18: diffusion models for graph generation are achieving state-of-the-art on molecular benchmarks. The open question: can these scale to protein-level graphs (thousands of nodes), and can the diffusion process be conditioned on arbitrary molecular properties rather than just property scores? Structure-based drug design (conditioning on 3D protein pocket geometry) is the target application.

Frontier 3: Graph + RL

As covered in Lecture 17: RL for agent optimization on knowledge graphs. Beyond this: using graphs as the world model in RL. The environment's causal structure (which variables affect which other variables) is a graph. An agent that can learn and exploit this causal graph will be dramatically more sample-efficient than one that doesn't.

Chapter 6: Practical Advice

You've learned the theory. Now, how do you actually use it? When you sit down with a new graph ML problem, which method do you reach for? Here's the decision procedure that experienced practitioners use.

Step 1: What is your task?

Step 2: What is your graph?

Step 3: The PyG Ecosystem

PyTorch Geometric (PyG) is the standard library. It implements 100+ GNN layers, all major datasets, and handles the data loading/batching complexity of graphs. Start with torch_geometric.nn.GCNConv or SAGEConv, compose layers, add a linear head, train with standard PyTorch. For large-scale graphs: DGL (Deep Graph Library) has better distributed training support.

PyG: minimal GNN classifier
import torch
from torch_geometric.nn import GCNConv, global_mean_pool
import torch.nn.functional as F

class SimpleGNN(torch.nn.Module):
    def __init__(self, in_dim, hidden, out_dim):
        super().__init__()
        self.conv1 = GCNConv(in_dim, hidden)
        self.conv2 = GCNConv(hidden, hidden)
        self.head  = torch.nn.Linear(hidden, out_dim)

    def forward(self, x, edge_index, batch):
        x = F.relu(self.conv1(x, edge_index))   # Layer 1: aggregate
        x = F.relu(self.conv2(x, edge_index))   # Layer 2: aggregate
        x = global_mean_pool(x, batch)          # Graph pooling
        return self.head(x)                      # Classification head

# That's a complete graph classifier. ~15 lines of real PyG code.
# Swap GCNConv → GINConv for max expressiveness.
# Swap GCNConv → GATConv for attention aggregation.

Chapter 7: Connections — All 19 Lectures

Here is the complete map of CS224W. Every lecture, in order, with its core contribution and the one key paper to read if you want to go deeper.

Recommended Reading (Beyond the Course)

• Graph Representation Learning (William Hamilton, 2020) — Free book. Covers the first 10 lectures in textbook depth. cs.mcgill.ca
• Benchmarking Graph Neural Networks (Dwivedi et al., 2020) — If you want to know which GNN actually works best on which tasks. ICLR 2022.
• A Gentle Introduction to Graph Neural Networks (Sanchez-Lengeling et al., Distill 2021) — Best visual explanation of message passing. distill.pub
• PyTorch Geometric Documentation — The practical companion to this course. Every method covered here has a PyG implementation. pytorch-geometric.readthedocs.io

"The structure of a graph encodes what matters about its domain. To ignore structure is to throw away the most important information. To reason over structure is to understand the domain itself."

— Jure Leskovec