Theory of GNNs — How Expressive Are They?

Slide 3 recalls where we are: the full GNN training pipeline from Lecture 5 (dataset split → input graph → GNN → node embeddings → prediction head → predictions, compared with labels by the loss function and the evaluation metrics). PyG provides the core modules for this pipeline, and GraphGym implements the full pipeline to help with GNN design.

Slide 4 reminds us of the variety of graphs: social networks, economic networks, citation networks, molecules. Slide 5: why is deep learning on graphs hard? Graphs are complex: they have a complex topological structure with no spatial locality like grids (images) or sequences (text), and there is no fixed node ordering or reference point.

Slide 6 poses the questions of this lecture. Many GNN models have been proposed (GCN, GAT, GraphSAGE, the whole design space of Lecture 4).

• What is the expressive power of these models — their ability to distinguish different graph structures?
• How do we design a maximally expressive GNN model?

Slide 7: a classical test of expressivity is graph isomorphism — given a pair of graphs, can we tell whether they are isomorphic (the same graph up to renaming the nodes)? The figure shows two drawings of 5-node graphs that look alike. Status of the problem: it is open: no polynomial-time algorithm is known, and it has not been proven NP-complete.

Slide 8 asks a simpler question that is the real focus: given a pair of nodes with different neighbourhood structures, is there a GNN that can always tell them apart? The figure shows a 5-node graph (edges 1–2, 1–5, 2–5, 5–4, 4–3) and, below it, the computation tree of each of its 5 nodes; the trees have different shapes.

Why "expressive power" matters: if a model maps two different structures to the same embedding, no prediction head can ever give them different labels. Expressiveness is an upper bound on what training can achieve, not a guarantee that training reaches it.

Slide 9 fixes the class of models: message-passing GNNs. One layer has two steps:

The figure: three coloured neighbour dots at the bottom send messages up into a box, which aggregates them into the node above.

Slide 10: different GNN models use different neural networks in the box. The figure shows the input graph with target node A and A's 2-layer computation tree; every aggregation box is marked with a question mark.

• Slide 11, GCN (mean-pool) [Kipf and Welling, ICLR 2017]: element-wise mean pooling + Linear + ReLU non-linearity.
• Slide 12, GraphSAGE (max-pool) [Hamilton et al., NeurIPS 2017]: MLP + element-wise max pooling.

The whole lecture is about one question: which choice of box loses the least information?

Slide 13 sets a convention: we use node colours to represent node features. Same colour = same feature. In the running example all nodes share the same feature (all yellow), so the only thing that can separate nodes is the structure. Key question: how well can a GNN distinguish different graph structures?

The running graph has 5 nodes and edges 1–2, 1–5, 2–5, 5–4, 4–3. Degrees: node 1: 2, node 2: 2, node 3: 1, node 4: 2, node 5: 3. We look at local neighbourhood structures around each node:

• Slide 14: nodes 1 and 5 have different neighbourhood structures, because they have different degrees (2 vs 3).
• Slide 15: nodes 1 and 4 both have degree 2. But they still have different neighbourhood structures, because their neighbours have different degrees: node 1 has neighbours of degrees 2 and 3; node 4 has neighbours of degrees 1 and 3.
• Slide 16: nodes 1 and 2 have the same neighbourhood structure, because they are symmetric within the graph (swapping 1 and 2 maps the graph to itself). Node 1 has neighbours of degrees 2 and 3; so does node 2. Even going one step deeper, to 2nd-hop neighbours, both see the same degrees (node 4, of degree 2).

Slide 17: key question — can GNN node embeddings distinguish different nodes' local neighbourhood structures? If so, when? If not, when will a GNN fail? To answer, we need to understand how a GNN captures local neighbourhood structure. The key concept is the computational graph.

Slide 18: in each layer, a GNN aggregates neighbouring node embeddings. So a GNN generates node embeddings through a computational graph defined by the neighbourhood. Example: node 1's computational graph for a 2-layer GNN. The root is 1; its children are its neighbours 2 and 5; the children of 2 are 1 and 5, and the children of 5 are 1, 2 and 4.

Slide 19 draws the computational graphs of nodes 1 and 2 side by side. Node 2's tree: root 2; children 1 and 5; under 1: 2 and 5; under 5: 1, 2, 4. Apart from the labels, the two trees have the same shape.

Slide 20: but a GNN only sees node features, not IDs. Erase the labels and both trees become identical trees of yellow dots. Slide 21: so a GNN will generate the same embedding for nodes 1 and 2, because (a) the computational graphs are the same and (b) the node features (colours) are identical. A GNN does not care about node IDs; it just aggregates the feature vectors of different nodes. The GNN will not be able to distinguish nodes 1 and 2.

Slide 22: in general, different local neighbourhoods define different computational graphs. The figure lists the 2-layer trees of all 5 nodes; e.g. node 3's tree is 3 → 4 → {3, 5}, a thin chain at the top, while node 5's tree starts with three branches.

Slide 23: computational graphs are identical to rooted subtree structures around each node — the structures you get by recursively unfolding neighbouring nodes from the root.

Slide 24: a GNN's node embeddings capture rooted subtree structures. The most expressive GNN maps different rooted subtrees to different node embeddings. In the figure, the embedding row above the trees uses colours: nodes 1 and 2 (same tree) get the same colour; nodes 3, 4, 5 each get their own colour.

So the right question is not "can the GNN tell nodes apart?" but "can it tell trees apart?". Nodes 1 and 2 are a case where no GNN of this kind can separate them — and, since they are truly symmetric, it also should not.

Slide 25 recalls a definition. A function \(f:X\to Y\) is injective if it maps different elements to different outputs. Intuition: \(f\) retains all the information about its input (you could in principle invert it). The figure maps elements 1, 2, 3 of \(X\) to three different elements of \(Y=\{A,B,C,D\}\).

Slide 26: the most expressive GNN should map subtrees to node embeddings in \(\mathbb{R}^d\) injectively.

Slide 27, key observation: subtrees of the same depth can be recursively characterised from the leaves to the root. Compare node 1 and node 4 with uniform input features. Node 1's root has 2 neighbours, which in turn have 2 and 3 neighbours: the description is (2 neighbours, 3 neighbours) under a 2-neighbour root. Node 4's root also has 2 neighbours, but they have 1 and 3 neighbours: (1 neighbour, 3 neighbours). The two descriptions differ, so the trees differ.

Slide 28: if each step of the GNN's aggregation can fully retain the neighbouring information, then the generated node embeddings can distinguish different rooted subtrees. The figure frames each level of the two trees: if level 1 keeps "2 neighbours" vs "1 neighbour, 3 neighbours" apart, and level 2 keeps the resulting multisets apart, the roots end up different.

Slide 29: in other words, the most expressive GNN uses an injective neighbour aggregation function at each step — it maps different neighbour multisets to different embeddings.

Slide 30 summarises: to generate a node embedding, a GNN uses a computational graph that is a subtree rooted at the node. A GNN can fully distinguish different subtree structures if every step of its neighbour aggregation is injective.

Why "every step"? The argument is an induction on depth. If depth-\(k\) embeddings already separate depth-\(k\) subtrees, and the aggregation is injective, then two depth-\((k+1)\) subtrees with different multisets of children get different embeddings. One non-injective step anywhere can merge two different trees, and nothing later can split them again.

Slide 32, key observation: the expressive power of a GNN is characterised by that of its neighbour aggregation function. A more expressive aggregation gives a more expressive GNN; an injective aggregation gives the most expressive GNN. Next: analyse the aggregation functions theoretically.

Slide 33: neighbour aggregation can be abstracted as a function over a multiset — a set with repeating elements. The figure shows a node with two yellow children as equivalent to the multiset {yellow, yellow}; other multiset examples: {yellow, blue} and {yellow, yellow, blue}. Same colour = same features.

Slide 34: we analyse two popular aggregators. GCN (mean-pool) uses element-wise mean pooling over neighbour features, \(\mathrm{Mean}(\{x_u\}_{u\in N(v)})\). GraphSAGE (max-pool) uses element-wise max pooling, \(\mathrm{Max}(\{x_u\}_{u\in N(v)})\).

GCN (slide 35): element-wise mean, then a linear function and ReLU, \(\max(0,x)\). Theorem [Xu et al., ICLR 2019]: GCN's aggregation function cannot distinguish different multisets with the same colour proportion. Failure case: {yellow, blue} vs {yellow, yellow, blue, blue}. Why? Slide 36: assume, for simplicity, node features (colours) are one-hot: yellow \(=(1,0)^\top\), blue \(=(0,1)^\top\); this is enough to show how GCN fails. Slide 37: the element-wise mean of \((1,0),(0,1)\) is \((0.5,0.5)\), and the mean of \((1,0),(1,0),(0,1),(0,1)\) is also \((0.5,0.5)\). After Linear + ReLU: the same outputs. Mean sees the distribution of colours, not the counts.

GraphSAGE (slide 38): apply an MLP, then take an element-wise max. Theorem [Xu et al., ICLR 2019]: GraphSAGE's aggregation cannot distinguish different multisets with the same set of distinct colours. Failure case: {yellow, blue}, {yellow, yellow, blue, blue} and {yellow, blue, blue}. Why? Slide 39: for simplicity, assume the MLP outputs a one-hot encoding (yellow → \((1,0)\), blue → \((0,1)\)). The element-wise max of any multiset that contains both colours is \((1,1)\). The same outputs. Max sees only the set of colours present.

Slide 40, summary so far:

• The expressive power of GNNs can be characterised by that of the neighbour aggregation function.
• Neighbour aggregation is a function over multisets (sets with repeating elements).
• GCN's and GraphSAGE's aggregation functions fail to distinguish some basic multisets, hence they are not injective.
• Therefore GCN and GraphSAGE are not maximally powerful GNNs.

Slide 41, our goal: design the maximally powerful GNN in the class of message-passing GNNs. This is achieved by designing an injective neighbour aggregation function over multisets. We design a neural network that can model such a function.

Theorem (slide 42) [Xu et al., ICLR 2019]: any injective multiset function can be expressed as

where \(S\) is the multiset, \(f\) is some non-linear function applied to each element, the sum runs over the multiset, and \(\Phi\) is another non-linear function. The figure: the multiset {yellow, blue, blue} becomes \(\Phi(f(\text{yellow})+f(\text{blue})+f(\text{blue}))\).

Proof intuition (slide 43): let \(f\) produce one-hot encodings of colours. Then the sum of the one-hot encodings retains all the information about the input multiset — it is the vector of counts. Example: \((1,0)+(0,1)+(0,1)=(1,2)\): one yellow, two blue. Different multisets give different count vectors, and \(\Phi\) can then map these injectively wherever we want.

How do we model \(\Phi\) and \(f\)? Slide 44: with a multi-layer perceptron (MLP). Universal Approximation Theorem [Hornik et al., 1989]: a 1-hidden-layer MLP with a sufficiently large hidden dimension and an appropriate non-linearity \(\sigma(\cdot)\) (including ReLU and sigmoid) can approximate any continuous function to arbitrary accuracy. The figure: input → \(\mathbf{W}_1\) → \(\sigma\) → \(\mathbf{W}_2\) → output.

Slide 45: we have arrived at a neural network that can model any injective multiset function:

In practice, an MLP hidden dimension of 100 to 500 is sufficient.

Slide 46: the Graph Isomorphism Network (GIN) [Xu et al., ICLR 2019] applies an MLP, an element-wise sum, then another MLP. Theorem: GIN's neighbour aggregation function is injective. No failure cases! GIN is the most expressive GNN in the class of message-passing GNNs introduced so far.

Slide 47 discusses the power of pooling with the figure from the GIN paper. Top: three pairs of small neighbourhoods (colours = feature values) where (a) mean and max both fail, (b) max fails, and (c) mean and max both fail. Bottom: a ranking by discriminative power on an input multiset — sum captures the full multiset, mean captures the distribution (proportions), max captures only the underlying set: sum > mean > max.

A subtlety: the theorem is about countable feature spaces (e.g. one-hot or discrete features). With arbitrary real-valued features, sum can also collide (e.g. \(\{1,3\}\) and \(\{2,2\}\) have the same sum), which is exactly why \(f\) is applied before summing.

Slide 48: so far we described GIN's neighbour aggregation. Now we describe the full GIN model by relating it to the WL graph kernel (a traditional way to obtain graph-level features, from Lecture 2). We will see that GIN is a "neural network" version of the WL kernel. Slide 49 repeats the graph isomorphism problem from slide 7: a classical expressivity test; open problem (no polynomial-time algorithm known, not proven NP-complete).

Colour refinement (slide 50). Given a graph \(G\) with node set \(V\):

1. Assign an initial colour \(c^{(0)}(v)\) to each node \(v\).
2. Iteratively refine node colours by \[ c^{(k+1)}(v)=\mathrm{HASH}\Big(c^{(k)}(v),\ \big\{c^{(k)}(u)\big\}_{u\in N(v)}\Big), \] where HASH maps different inputs to different colours.
3. After \(K\) steps of colour refinement, \(c^{(K)}(v)\) summarises the structure of the \(K\)-hop neighbourhood.

Worked example on two graphs (slides 51–53). Both graphs have 6 nodes.

• Slide 51: assign initial colour 1 to all nodes. Then each node collects its own colour and the multiset of its neighbours' colours, written as "own colour, neighbour colours": for example a node of degree 2 gets "1,11", a node of degree 4 gets "1,1111".
• Slide 52: injectively HASH the aggregated colours, using the hash table 1,1 → 2; 1,11 → 3; 1,111 → 4; 1,1111 → 5. After this step the colour of each node is just its degree class; the next rounds repeat the process with the new colours.
• Slide 53: the process continues until a stable colouring is reached (no colour class splits any more). Two graphs are considered isomorphic if they have the same set of colours. In the example the final colour multisets differ (the figure shows different colour labels such as 8, 10, 11 in the two graphs), so the two graphs are not isomorphic: \(\neq\).

Slide 54: GIN uses a neural network to model the injective HASH function \(c^{(k+1)}(v)=\mathrm{HASH}(c^{(k)}(v),\{c^{(k)}(u)\}_{u\in N(v)})\). Specifically, we model an injective function over the tuple (root node features \(c^{(k)}(v)\), neighbouring node colours \(\{c^{(k)}(u)\}_{u\in N(v)}\)).

Theorem (slide 55) [Xu et al., ICLR 2019]: any injective function over the tuple \(\big(c^{(k)}(v),\{c^{(k)}(u)\}_{u\in N(v)}\big)\) can be modelled as

where \(\epsilon\) is a learnable scalar. The \((1+\epsilon)\) factor lets the network tell the root apart from its neighbours: without it, a root of colour A with neighbours {B} would give the same sum as a root of colour B with neighbours {A}.

Slide 56: if the input feature \(c^{(0)}(v)\) is one-hot, direct summation is already injective (example: \((1,0)+(0,1)+(0,1)=(1,2)\)). Then we only need \(\Phi\) to ensure injectivity:

This MLP can provide "one-hot" input features for the next layer, so the argument repeats layer after layer.

GIN's node embedding updates (slide 57). Given a graph \(G\) with node set \(V\): assign an initial vector \(c^{(0)}(v)\) to each node; iteratively update node vectors by \(c^{(k+1)}(v)=\mathrm{GINConv}\big(\{c^{(k)}(v),\{c^{(k)}(u)\}_{u\in N(v)}\}\big)\), where GINConv is a differentiable colour HASH function that maps different inputs to different embeddings. After \(K\) GIN iterations, \(c^{(K)}(v)\) summarises the structure of the \(K\)-hop neighbourhood — exactly like WL.

Slide 58 compares them in a table. WL graph kernel: update target = node colours (one-hot); update function = HASH. GIN: update target = node embeddings (low-dimensional vectors); update function = GINConv. Advantages of GIN over the WL kernel:

• Node embeddings are low-dimensional; hence they can capture the fine-grained similarity of different nodes (WL colours are either equal or different; there is no "almost the same").
• The parameters of the update function can be learned for the downstream tasks.

Slide 59, expressive power of GIN: because of this relation, GIN and the WL kernel have exactly the same expressive power. If two graphs can be distinguished by GIN, they can also be distinguished by the WL kernel, and vice versa. How powerful is this? The WL kernel has been shown, both theoretically and empirically, to distinguish most real-world graphs [Cai et al. 1992]. (Citation note: the slide credits Cai, Fürer & Immerman 1992, but that paper is the negative result, that no fixed \(k\)-WL identifies all graphs. The positive "almost all graphs" result is Babai, Erdős & Selkow 1980, with Babai & Kučera 1979 for a linear-time canonical labelling.) Hence GIN is also powerful enough to distinguish most real graphs!

Precisely, the result has two halves: no message-passing GNN can be more powerful than 1-WL (any GNN's embedding is a function of the WL colour), and GIN, with injective layers, reaches 1-WL.

Slide 60, the bad news: the WL kernel cannot distinguish some basic graph structures. The figure shows two 10-node graphs: two pentagons joined by an edge, and two hexagons sharing an edge. Every node has degree 2 or 3 in both, the degree patterns match, and colour refinement never separates them. Also, the WL kernel cannot count important substructures, such as cycles and cliques.

Why do these matter?

• Cycles (slide 61): the bonds between atoms in chemical compounds form cycles. The hexagon is the most common polygon in organic compounds and yields stable materials. The figure shows three drug molecules (Doxorubicin, Camptothecin, Etoposide), each full of rings.
• Cliques and quasi-cliques (slide 62): fraudster detection in e-commerce networks (an adjacency matrix where a dense block of fraudsters and "camouflage" edges to honest users stands out; Hooi et al. 2016), detection of protein complexes in protein–protein interaction networks (Vlasic et al. 2017), and graph compression (Dhulipala et al. 2017).

Slide 63: can the expressive power of GNNs be improved? There are basic graph structures the existing GNN framework cannot distinguish, such as differences in cycles: in the figure, \(v_1\) in graph A lies on a 3-cycle and \(v_2\) in graph B on a 4-cycle, yet their computational graphs are the same binary tree. GNNs' expressive power can be improved to resolve this [You et al. AAAI 2021; Li et al. NeurIPS 2020; Kanatsoulis et al. ICLR 2024] — the topic of Lecture 7.

Slide 64, summary of the lecture:

• We designed a neural network that can model an injective multiset function.
• Using it for neighbour aggregation gives GIN, the most expressive GNN model (among message-passing GNNs).
• The key is element-wise sum pooling instead of mean or max pooling.
• GIN is closely related to the WL graph kernel.
• Both GIN and the WL kernel can distinguish most real graphs.