Graph Neural Networks
Message passing, expressive power and the WL test, over-smoothing, over-squashing and sampling at scale.
7concepts
74flashcards
53minutes of reading
- 01 Expressive Power and the WL Test The exact ceiling on what a message-passing network can distinguish, why the aggregation function determines whether that ceiling is reached, and the graphs it provably cannot tell apart.
- 02 Graph Attention Networks and Graph Transformers How attention replaces fixed neighbour weights in GAT, why the original GAT can only compute a static ranking of neighbours, and how graph transformers attend globally while injecting structure through positional and structural encodings.
- 03 Heterogeneous and Temporal Graphs Why real graphs have typed nodes and edges that a homogeneous model averages together, how relation-specific message passing preserves the distinction, and what adding time requires.
- 04 Link Prediction and Negative Sampling Why predicting edges is not ordinary classification, how negative sampling choices determine what the model learns, and the evaluation leakage that makes published numbers hard to trust.
- 05 Over-Smoothing and Over-Squashing The two distinct reasons deep graph networks fail, why they pull in opposite directions, and the interventions that address each.
- 06 Sampling and Scaling to Large Graphs Why full-batch training does not scale past a certain graph size, the neighbourhood explosion that makes naive mini-batching worse, and the three sampling strategies that resolve it.
- 07 Spectral Graph Convolutions Defining convolution on a graph through the eigenvectors of its Laplacian, how Chebyshev polynomials make the filter local and cheap, and how the familiar GCN layer falls out as a first-order approximation with a renormalisation trick.