Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

GIN: Graph Isomorphism Network, The Most Expressive GNN

5 minute read

Published:

TL;DR: GIN (Xu et al., 2019) is provably as expressive as the 1-dimensional Weisfeiler-Leman (1-WL) graph isomorphism test, the theoretical ceiling for message-passing GNNs. The key: aggregate with sum (not mean or max) and apply an MLP after each layer. GCN and GraphSAGE are strictly less expressive.
A graph, the rooted subtree that two WL iterations induce, and the multiset a GNN aggregates
Two WL iterations unroll each node into a rooted subtree; a GNN layer aggregates the same structure as a multiset of neighbour features. The correspondence is why an MPNN is at most as powerful as 1-WL (Xu et al., 2019, Figure 1).

Why Expressiveness Matters

Two different graphs that a GNN represents identically are indistinguishable by that model, it can’t learn to predict different outputs for them. The more graphs a GNN can distinguish, the more powerful it is.

A concrete failure of mean aggregation:

Graph 1: 4 neighbours, all type A v A A A A mean(A,A,A,A) = A ✓ sum(A,A,A,A) = 4A ✓ Graph 2: 2 neighbours, all type A v A A mean(A,A) = A ← SAME as Graph 1! sum(A,A) = 2A ← DIFFERENT ✓
Figure 1: Mean aggregation cannot distinguish a node with 4 identical neighbours from one with 2 identical neighbours, both produce the same mean, \(h_A\). Sum aggregation separates them, because \(4 h_A \ne 2 h_A\) whenever \(h_A \ne 0\).
Why Sum and Not Mean? Consider two nodes, \(v_1\) whose neighbour features form the multiset \(\{\!\{h_A, h_A, h_A, h_A\}\!\}\) and \(v_2\) with \(\{\!\{h_A, h_A\}\!\}\). Mean aggregation returns \(h_A\) for both. Sum returns \(4h_A\) versus \(2h_A\), different. The neighbourhood size, and more generally how many nodes of each type there are, is structural information: mean throws it away, sum preserves it. This seemingly small difference is the key to GIN's theoretical advantage.

The Weisfeiler-Leman Test

The 1-WL test (also called colour refinement) is a classical algorithm for distinguishing graphs. Write \(c^{(k)}_v\) for the colour of node \(v\) at round \(k\), starting from \(c^{(0)}_v\) = the node’s label. Each round it applies

\[ c^{(k)}_v = \operatorname{HASH}\Big( c^{(k-1)}_v, \; \big\{\!\!\big\{ c^{(k-1)}_u : u \in \mathcal{N}(v) \big\}\!\!\big\} \Big) \]

where \(\{\!\{\cdot\}\!\}\) denotes a multiset (a set that keeps repetitions) and \(\operatorname{HASH}\) is injective. The algorithm terminates when the partition of nodes into colours stops changing. If two graphs end with different colour histograms they are certainly not isomorphic; if the histograms match, the test is inconclusive, 1-WL is a one-sided test, and it famously fails on pairs of regular graphs such as a 6-cycle versus two disjoint triangles.

Compare that update with the MPNN loop: a GNN is running exactly this algorithm with learned functions in place of \(\operatorname{HASH}\). Xu et al. (2019) proved:

Theorem (Xu et al., 2019): Any message-passing GNN, any model of the neighbourhood-aggregation form, is at most as powerful as the 1-WL test at distinguishing non-isomorphic graphs. And there exist message-passing GNNs that reach that bound; GIN is one of them.

For a GNN to match 1-WL, its aggregation must be an injective multiset function: different multisets of neighbour features must produce different outputs, exactly as \(\operatorname{HASH}\) does. The enabling lemma is:

\[ \text{For a countable feature space } \mathcal{X}, \; \exists f : \mathcal{X} \to \mathbb{R}^{n} \text{ such that } X \mapsto \sum_{x \in X} f(x) \text{ is injective over multisets } X \subset \mathcal{X} \text{ of bounded size.} \]

In other words sum aggregation can be made injective, mean and max cannot:

  • Mean cannot distinguish multisets with the same distribution of elements but different sizes: \(\operatorname{mean}(\{\!\{A, A, A, A\}\!\}) = \operatorname{mean}(\{\!\{A, A\}\!\})\) (see the figure above).
  • Max only sees the set of distinct elements, so it is blind to every multiplicity: \(\max(\{\!\{A, A, B\}\!\}) = \max(\{\!\{A, B\}\!\})\).
  • Sum preserves both the size of the multiset and its contents.

The GIN Layer

\[ h_v^{(k)} = \operatorname{MLP}^{(k)}\Big( \big(1 + \epsilon^{(k)}\big) \cdot h_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)} \Big) \]

Two components:

  • \(\epsilon^{(k)} \in \mathbb{R}\), a scalar, either learned by gradient descent or fixed at \(0\) (the variant the paper calls GIN-0). It weights the centre node’s own representation separately from the neighbour sum, so that the pair \(\big(h_v, \{\!\{h_u\}\!\}\big)\) is recoverable, the analogue of the first argument of \(\operatorname{HASH}\).
  • \(\operatorname{MLP}^{(k)}\), a multi-layer perceptron applied after summing. This is what realises the injective \(f\) (and the outer function composed with it) from the lemma above. It is crucial: a single linear layer, as in GCN, cannot represent the required injective mappings, whereas an MLP with at least one hidden layer is a universal approximator.

Comparison

ModelAggregatorUpdate1-WL power
GCNDegree-normalised sum (mean-like)Linear + ReLU\(<\) 1-WL
GATAttention-weighted sumLinear + ReLU\(<\) 1-WL
GraphSAGEMean or max-poolLinear + ReLU\(<\) 1-WL
GINSumMLP\(=\) 1-WL

GIN is the only architecture in this list that reaches the 1-WL bound. Note this is a statement about worst-case distinguishing power, not about accuracy: a less expressive model can still win on a given dataset.

GIN for Graph Classification

For graph-level tasks, GIN uses a readout that concatenates the sum-pooled representations from all layers, not just the final one:

\[ h_G = \Big\Vert_{k=0}^{K} \; \sum_{v \in V} h_v^{(k)} \]

where \(\Vert\) is concatenation over the layer index \(k\) and \(V\) is the node set. Sum pooling is used here for the same reason as inside the layer, it is the injective choice. Using representations from all layers captures both fine-grained (early layers) and coarse (late layers) structural information.

✅ Key Takeaways

  • Message-passing GNNs are bounded in expressiveness by the 1-dimensional Weisfeiler-Leman test; two graphs 1-WL cannot separate, no MPNN can separate.
  • GIN reaches that bound using sum aggregation + an MLP update, because sum is the aggregator that can be made injective over multisets.
  • Mean and max aggregation are provably less expressive, mean loses the multiset size, max loses all multiplicities.
  • The \(\epsilon^{(k)}\) parameter lets GIN weight the centre node differently from the sum over its neighbours.
  • 1-WL is itself only a one-sided test, so matching it is a ceiling, not a guarantee of distinguishing every pair of non-isomorphic graphs.

You May Also Enjoy

The Standard Library Modules Worth Knowing Before You pip install

8 minute read

Published:

Python ships with a counter, a queue, a memoiser, a CLI parser, a test framework’s smaller cousin, and a JSON-safe date library already installed, most of what people reach for a package to solve is one import away.

Files and Context Managers: Why with Is Not Optional

9 minute read

Published:

A file object that falls out of scope without with does get closed eventually, but ‘eventually’ means whenever the garbage collector gets around to it, which is not a promise any program handling more than a handful of files can live with.

Errors and Exceptions: EAFP, the Hierarchy, and Reading a Traceback

9 minute read

Published:

Exceptions in Python are not exceptional. They are a normal control-flow mechanism that the language leans on so heavily that the idiomatic style is to try the operation and handle the failure, rather than check first, which is faster, shorter, and free of race conditions.