Graph neural networks
Molecules, citation networks and social networks have no natural order and no fixed shape. Graph neural networks pass messages along edges — and the constraints that make that work also limit what they can see.
55 min
After this lesson you can
- Represent a graph with an adjacency matrix and a feature matrix, and name node-, edge- and graph-level tasks
- State permutation invariance and equivariance with a permutation matrix, and explain why a plain MLP on the adjacency matrix violates them
- Write one round of message passing, and derive the GCN's normalised propagation rule from Kipf's two fixes
- Explain GAT's attention coefficients and how they differ from GCN's fixed weights
- Prove that repeated GCN propagation collapses features onto one direction (over-smoothing), and say how residual connections resist it
- State precisely what Xu et al. proved about GNNs and the Weisfeiler–Lehman test, and find two graphs no such GNN can tell apart
In this lesson
- The data: nodes, edges and features
- The inductive bias: order must not matter
- The architecture: passing messages
- GCN: the simplest rule that works
- GAT: let the edges have opinions
- Over-smoothing: why GNNs are shallow
- Expressivity: what message passing cannot see
- How GNNs are evaluated
- Open problems
This lesson is part of Descent Pro
Descent Pro unlocks every lesson on the route, from base camp to the summit. Every plan starts with a free trial.