Graph Neural Networks: Learning on Graphs
Published:
Series note: This Graph Neural Networks track is organised as short, self-contained 3-5 minute posts. The fundamentals are aligned with the presentation in William L. Hamilton’s Graph Representation Learning, which is the main background reference for the basic graph concepts used throughout the series.
Graphs Are Everywhere
A graph \(G = (V, E)\) consists of:
- Nodes \(V\): entities — atoms, people, papers, intersections. We write \(N = \lvert V \rvert\).
- Edges \(E\): relationships — bonds, friendships, citations, roads, collected in an adjacency matrix \(A\).
- Features on nodes and/or edges: atom type, age, year, speed limit. Node features are stacked into \(X \in \mathbb{R}^{N \times d}\).
Real-world data that’s naturally a graph:
- Molecules: atoms = nodes, bonds = edges. Predicting drug toxicity or binding affinity.
- Social networks: users = nodes, follows/friends = edges. Recommendation, fraud detection.
- Knowledge graphs: entities = nodes, relations = edges. Question answering, link prediction.
- Citation networks: papers = nodes, citations = edges. Classifying papers by topic.
- Road networks: intersections = nodes, roads = edges. Route planning, traffic prediction.
Why Not Just Use Standard Neural Networks?
A standard MLP takes a fixed-size vector as input. Graphs have:
- Variable size — different graphs have different numbers of nodes and edges.
- No canonical ordering — there’s no “first” node; permuting nodes shouldn’t change predictions.
- Relational structure — the patterns live in the connections, not just the individual features.
GNNs are designed to respect all three of these properties.
The Core Idea: Aggregate from Neighbours
Every GNN follows the same fundamental principle, called message passing. Writing \(h_v^{(k)}\) for the representation of node \(v\) after \(k\) rounds and \(\mathcal{N}(v)\) for its neighbourhood:
In words: each node’s new representation is a learned function of its own current representation together with a permutation-invariant summary of its neighbours’ representations. After \(k\) iterations, \(h_v^{(k)}\) captures information from all nodes up to \(k\) hops away — its \(k\)-hop neighbourhood.
This is elegant because:
- Nearby nodes influence each other (just like in the real world).
- The same aggregation function works on graphs of any size, since it is defined per node.
- The function is learned from data, so it adapts to the task.
Concrete numerical example. Suppose node \(A\) has feature vector \([1, 0]\) and its two neighbours are \(B = [0,1]\) and \(C = [1,1]\). Under one GCN-style layer with mean aggregation over \(\{A\} \cup \mathcal{N}(A)\) and identity weights:
After a second layer, \(h_A^{(2)}\) also absorbs the updated representations of \(B\) and \(C\) — which already summarise their neighbours — so \(A\) ends up seeing its 2-hop neighbourhood.
Animated Information Flow
Three Task Levels
GNNs can produce predictions at three granularities:
| Level | What you predict | Output built from | Example |
|---|---|---|---|
| Node | Label for each node | \(h_v^{(K)}\) | Is this user a bot? |
| Edge | Label or score for each pair | \(f(h_u^{(K)}, h_v^{(K)})\) | Will A befriend B? |
| Graph | Label for the whole graph | \(h_G = \mathrm{READOUT}(\{h_v^{(K)}\})\) | Is this molecule toxic? |
For node tasks, use the node embeddings directly. For edge tasks, score a pair of embeddings. For graph tasks, readout (pool) all node embeddings into a single graph vector first.
A second, orthogonal distinction is whether the graph you are evaluated on was visible during training. In the transductive setting there is one fixed graph and only test labels are withheld; in the inductive setting the model must embed nodes or graphs it has never seen, so it has to generalise the aggregation function rather than memorise per-node vectors.
The Landscape of GNN Architectures
| Model | Venue | Key idea |
|---|---|---|
| GCN | ICLR 2017 | Spectral convolution simplified to degree-normalised averaging |
| GraphSAGE | NeurIPS 2017 | Inductive learning via neighbourhood sampling |
| GAT | ICLR 2018 | Learned attention weights over neighbours |
| GIN | ICLR 2019 | Sum aggregation + MLP; as expressive as the 1-WL test |
| Sheaf NN | NeurIPS 2022 | Diffusion over a sheaf’s section space, generalising GCN |
✅ Key Takeaways
- Graphs model relational data: atoms, users, papers, intersections — any entities with relationships.
- GNNs learn by iterative neighbourhood aggregation: after \(k\) layers, \(h_v^{(k)}\) summarises the \(k\)-hop neighbourhood of \(v\).
- The same model works on graphs of any size and any node ordering — node-level outputs are permutation equivariant, graph-level outputs permutation invariant.
- Supports node-, edge-, and graph-level predictions from the same backbone; only the output head changes, with readout pooling for graph-level tasks.
- Evaluation splits into transductive (one fixed graph, labels withheld) and inductive (unseen nodes or graphs at test time).
References
- Hamilton, W. L. (2020). Graph Representation Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning.
- Bronstein, M. M., Bruna, J., Cohen, T., & Veličković, P. (2021). Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv preprint.