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.
- Edges (E): relationships — bonds, friendships, citations, roads.
- Features on nodes and/or edges: atom type, age, year, speed limit.
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:
Each node’s new representation = function(its current representation, representations of its neighbours)
After k iterations, node v’s embedding captures information from all nodes up to k hops away (its k-hop neighbourhood).
This is beautiful because:
- Nearby nodes influence each other (just like in the real world).
- The same aggregation function works on graphs of any size.
- 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 B=[0,1] and C=[1,1]. After one GCN-style layer (mean aggregation + identity weights), A’s new representation is the mean of A, B, C: ([1,0]+[0,1]+[1,1])/3 = [0.67, 0.67]. After a second layer, A’s representation will also absorb B’s and C’s updated neighbours — capturing the 2-hop neighbourhood.
Animated Information Flow
Three Task Levels
GNNs can produce predictions at three granularities:
| Level | What you predict | Example |
|---|---|---|
| Node | Label for each node | Is this user a bot? |
| Edge | Label or score for each edge | Will A befriend B? |
| Graph | Label for the whole graph | Is this molecule toxic? |
For node tasks: use the node embeddings directly. For graph tasks: readout (pooling) the node embeddings into a single graph vector.
The Landscape of GNN Architectures
| Model | Year | Key idea |
|---|---|---|
| GCN | 2016 | Spectral convolution → normalised averaging |
| GAT | 2018 | Attention weights on edges |
| GraphSAGE | 2017 | Inductive learning via neighbourhood sampling |
| GIN | 2019 | Most expressive aggregator (sum + MLP) |
| Sheaf NN | 2022+ | Section-space diffusion, generalises GCN |
✅ Key Takeaways
- Graphs model relational data: atoms, users, papers, intersections — any entities with relationships.
- GNNs learn by iterative neighbourhood aggregation: after k layers, each node knows about its k-hop neighbourhood.
- The same model works on graphs of any size and any node ordering — it's permutation invariant/equivariant.
- Supports node-, edge-, and graph-level predictions via readout pooling.
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.