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.