# Graph Isomorphism Network (GIN)

> GIN (Xu, Hu, Leskovec, Jegelka, ICLR 2019) updates h_v ← MLP((1+ε)h_v + Σ h_u); sum aggregation is injective on multisets, so GIN is as powerful as the 1-WL test, the upper bound for message-passing GNNs.

Source: https://www.mlfoundry.in/learn/graph-isomorphism-network-gin  
Section: Deep Learning › Graph Neural Networks (GNNs)  
Level: advanced · 8 min read · updated 2026-10-21

**Graph Isomorphism Network (GIN):** is a message-passing GNN whose layer sums the neighbour features, adds $(1+\varepsilon)$ times the node's own feature and passes the result through an MLP. Xu, Hu, Leskovec and Jegelka introduced it in "How Powerful are Graph Neural Networks?" (ICLR 2019). The paper proved that no message-passing GNN can distinguish more graphs than the 1-dimensional Weisfeiler–Lehman (1-WL) test, and that GIN reaches this bound. Morris et al. ("Weisfeiler and Leman Go Neural", AAAI 2019) proved the same upper bound independently.

The task GIN was built for is **Graph classification**: map a whole graph, of any size and node order, to a label. Two graphs that are isomorphic must get the same output, so the model must be permutation invariant. Ideally it should also give different outputs to graphs that are not isomorphic. Before GNNs, the strongest tools here were graph kernels, in particular the WL subtree kernel (Shervashidze et al., 2011). It counts the colours produced by 1-WL refinement.

**Graph Convolutional Network (GCN)** and **GraphSAGE** were designed for node classification, and their aggregators were chosen on empirical grounds. The GIN paper asks a sharper question: which aggregators lose information about the neighbourhood? Its answer is that mean and max do, and sum does not.

## The 1-WL test as the yardstick

1-WL colour refinement gives every node a colour (its label, or one shared colour if there are none). Each round then replaces a node's colour by a hash of its own colour and the **multiset** of its neighbours' colours:

$$
c^{(k)}(v)=\operatorname{HASH}\Big(c^{(k-1)}(v),\ \{\!\{\,c^{(k-1)}(u)\;:\;u\in\mathcal N(v)\,\}\!\}\Big)
$$

- $\{\!\{\cdot\}\!\}$: a multiset: repeated colours are counted
- $\operatorname{HASH}$: an injective map from (colour, multiset) pairs to new colours, shared by both graphs

Two graphs whose colour histograms differ after some round are certainly not isomorphic. Equal histograms prove nothing: a 6-cycle and two disjoint triangles are both 2-regular, so every node keeps the same colour forever. A GNN layer has exactly the WL form, with an aggregator in place of the multiset and a learned update in place of HASH. The paper shows that a GNN that separates two graphs implies that 1-WL separates them too (Lemma 2). If the aggregation, the update and the readout are all **injective**, the GNN separates every pair that 1-WL separates (Theorem 3).

## The GIN layer

Sums over a countable feature space can be made injective. For a multiset $X$ of bounded size there is a function $f$ for which $\sum_{x\in X}f(x)$ is unique for each $X$ (Lemma 5). Corollary 6 extends this to the pair (node, neighbourhood): $(1+\varepsilon)f(c)+\sum_{x\in X}f(x)$ is unique for infinitely many $\varepsilon$, including every irrational one. An MLP can approximate the required $f$ and the next layer's map (universal approximation), which gives the update:

$$
h_v^{(k)}=\operatorname{MLP}^{(k)}\Big(\big(1+\varepsilon^{(k)}\big)\,h_v^{(k-1)}+\sum_{u\in\mathcal N(v)}h_u^{(k-1)}\Big)
$$

- $h_v^{(0)}$: input node features (one-hot atom type, one-hot degree, …)
- $\varepsilon^{(k)}$: learned scalar (GIN-$\varepsilon$) or fixed at 0 (GIN-0)
- $\operatorname{MLP}^{(k)}$: two layers with batch norm in the paper; a single linear layer plus ReLU is provably weaker

Node embeddings from early layers describe small rooted subtrees, which may generalise better; late layers describe deep subtrees. GIN therefore reads out **every** layer and concatenates the results:

$$
h_G=\operatorname{CONCAT}\Big(\ \sum_{v\in G}h_v^{(k)}\ \Big|\ k=0,1,\dots,K\Big)
$$

- $\sum_{v\in G}$: sum readout, injective on multisets for the same reason as the sum aggregator
- $K$: number of GIN layers; the paper used 5 layers including the input layer, so $K=4$

> Figure: One GIN layer at node v (feature A = [1, 0]) with neighbours B, B and A. The sum aggregate [1, 2] keeps the count of each type; with ε = 0 the MLP input is [1, 0] + [1, 2] = [2, 2]. A mean would give [0.33, 0.67] (only proportions) and a max [1, 1] (only which types occur). Right: the graph vector concatenates sum readouts of layers k = 0 to 4 and feeds a linear classifier.

## Why mean and max fall short

The mean of the neighbour features records the **distribution** of the neighbourhood: the neighbours $\{A,B\}$ and $\{A,A,B,B\}$ give the same mean. The max records only the **set** of distinct features, so $\{A,B\}$ and $\{A,B,B\}$ match as well. With identical input features (as in many social graphs), mean and max see the same value at every node and every layer. They cannot even detect node degrees. GCN's normalised aggregation behaves like a weighted mean, and GraphSAGE's pooling aggregator is a max. Both are therefore strictly weaker than 1-WL on some pairs. Their loss is not always harmful: a mean is a sensible statistic when the size of the neighbourhood is noise.

> Figure: Exact colour refinement under each aggregator's view (sum = multiset, which is 1-WL; mean = proportions; max = set), plus a real GNN with seeded random weights. Default pair: the path B–A–B–A–B against a spider. Every A sees only B and every B only A, so mean and max report "same" at every k and the GNN gap is 0.000. Sum differs from k = 1, with gap 0.080. On "two A-trees", mean separates the graphs from k = 1 (gap 0.607) but max never does. On "C6 vs 2 triangles" every aggregator says "same": this is the 1-WL limit.

## Worked example: C4 against the star K1,3

Both graphs have 4 nodes and all input features equal to 1. Update h ← h_v + AGG(h_u) with an identity MLP (ε = 0); readout with the same aggregator

| Aggregator | C4 after layer 1 | Star after layer 1 | Readout, layer 1 | Readout, layer 2 |
| --- | --- | --- | --- | --- |
| sum | [3, 3, 3, 3] | [4, 2, 2, 2] (centre first) | 12 vs 10 | 36 vs 28 |
| mean | [2, 2, 2, 2] | [2, 2, 2, 2] | 2 vs 2 | 4 vs 4 |
| max | [2, 2, 2, 2] | [2, 2, 2, 2] | 2 vs 2 | 4 vs 4 |

Sum turns the degrees (2, 2, 2, 2 against 3, 1, 1, 1) into different values after one layer. Mean and max of identical neighbours return the neighbour value itself, so both graphs stay constant at every layer. Graph size can sometimes leak in through a sum readout, but here both graphs have 4 nodes, so nothing does.

**Setup and results in the paper (GIN-0, 10-fold cross-validation accuracy)**

- **Architecture:** 5 GNN layers including the input layer; every MLP has 2 layers, batch norm on each hidden layer; Adam, learning rate 0.01 halved every 50 epochs
- **Tuned:** hidden units 16 or 32 (bioinformatics) and 64 (social); batch size 32 or 128; dropout 0 or 0.5 after the dense layer; number of epochs
- **Input features:** node labels for bioinformatics graphs; one-hot degrees for the social graphs, and identical features on the REDDIT graphs
- **MUTAG:** 89.4 ± 5.6%
- **PROTEINS:** 76.2 ± 2.8%
- **IMDB-BINARY:** 75.1 ± 5.1%
- **REDDIT-BINARY:** 92.4 ± 2.5%
- **Training fit:** GIN-0 and GIN-ε fit almost all training graphs; the mean and max variants and the 1-layer-perceptron variants underfit markedly

> **Read the protocol before comparing numbers:** The accuracies above are means over the 10 validation folds, with the number of epochs chosen by the best fold-averaged accuracy, so there is no separate test set. Errica et al. (ICLR 2020) re-ran GIN and others with nested model selection and found smaller gaps, sometimes in favour of a structure-agnostic baseline. See **Graph classification**.

```python
import numpy as np

def wl_test(A1, A2, iters=3):
    """1-WL on two graphs with one shared colour table; True if the histograms ever differ."""
    cols = [[0] * len(A1), [0] * len(A2)]          # no node features: one initial colour
    table = {}
    for _ in range(iters):
        cols = [[table.setdefault((c[v], tuple(sorted(c[u] for u in np.flatnonzero(A[v])))), len(table))
                 for v in range(len(A))] for A, c in zip((A1, A2), cols)]
        if sorted(cols[0]) != sorted(cols[1]):
            return True
    return False

def gin_embed(A, X, layers, eps=0.0):
    """GIN forward pass: h <- MLP((1+eps) h + A h); graph vector = concat of sum readouts."""
    H, reads = X, [X.sum(0)]
    for W1, W2 in layers:
        Z = (1 + eps) * H + A @ H                       # sum aggregation keeps neighbour counts
        H = np.maximum(0, np.maximum(0, Z @ W1) @ W2)   # 2-layer MLP (batch norm omitted)
        reads.append(H.sum(0))
    return np.concatenate(reads)

def cycle(n):
    return np.roll(np.eye(n), 1, 1) + np.roll(np.eye(n), -1, 1)

C6, two_C3 = cycle(6), np.kron(np.eye(2), cycle(3))   # 6-cycle vs two disjoint triangles
C4, star = cycle(4), np.zeros((4, 4))
star[0, 1:] = star[1:, 0] = 1

rng = np.random.default_rng(0)
layers = [(rng.normal(size=(d, 16)), rng.normal(size=(16, 16)) / 4) for d in (1, 16, 16)]
for name, G1, G2 in [("C6 vs 2xC3", C6, two_C3), ("C4 vs star", C4, star)]:
    h1 = gin_embed(G1, np.ones((len(G1), 1)), layers)
    h2 = gin_embed(G2, np.ones((len(G2), 1)), layers)
    print(f"{name}: 1-WL distinguishes={wl_test(G1, G2)}, GIN gap={np.linalg.norm(h1 - h2):.3f}")
# C6 vs 2xC3: 1-WL distinguishes=False, GIN gap=0.000
# C4 vs star: 1-WL distinguishes=True, GIN gap=157.216
```

1-WL with a shared colour table and a GIN-0 forward pass with random weights (numpy, runs as is; the printed values are the actual output)

In PyTorch Geometric the layer is `GINConv(nn, eps=0.0, train_eps=False)`, where `nn` is the MLP; `train_eps=True` gives GIN-ε. `GINEConv` adds edge features to each message before the sum and is the usual choice for molecules (see **Molecular property prediction**).

## Beyond 1-WL

1-WL fails on all regular graphs with the same size and degree. It cannot count triangles, and it cannot tell a 6-cycle from two triangles. This limits every message-passing GNN, including GIN, **Graph Attention Network (GAT)** and **Message Passing Neural Networks (MPNN)**. Ways past the limit: higher-order GNNs that pass messages between $k$-tuples of nodes (Morris et al., following the $k$-WL hierarchy), at $O(n^k)$ cost; node features that break symmetry, such as random features, identifiers or Laplacian eigenvectors (see **Graph transformers**); and subgraph GNNs that run a GNN on many marked or edited copies of the graph.

> **Expressive is not the same as accurate:** Injectivity guarantees that different graphs *can* get different embeddings. It does not guarantee that the network learns a useful embedding from a few hundred graphs, or that it generalises. On small datasets a mean readout or a simpler GCN often matches GIN. GIN's clearest advantage in the paper is training accuracy. Its test-accuracy gains are largest on social graphs with no informative node features, where mean-based GNNs see little of the structure.

**Question:** All nodes have the same feature. Which aggregator lets a GNN tell the star K1,3 from the 4-cycle C4?

- A. Mean
- B. Max
- C. Sum
- D. None of them: 1-WL cannot separate them

**Answer:** C. Sum — With equal features, the mean or max of any neighbourhood equals that feature, so all nodes look alike in both graphs. Sum returns the degree times the feature: 2 everywhere in C4, against 3, 1, 1, 1 in the star. 1-WL separates them after one round.

**Question:** Why does GIN add (1 + ε) h_v instead of putting v into the neighbour sum?

- A. To make the layer faster
- B. So that the node's own feature and its neighbours' features combine injectively, as (c, X) pairs in Corollary 6
- C. To normalise by the degree
- D. It is required for permutation invariance

**Answer:** B. So that the node's own feature and its neighbours' features combine injectively, as (c, X) pairs in Corollary 6 — With $\varepsilon=0$ and $v$ added to the neighbour sum, the node is just one more element of the multiset. Swapping the centre's feature with a neighbour's would then give the same sum. The weight $1+\varepsilon$, with $\varepsilon$ irrational in the proof, keeps the centre distinguishable. In practice GIN-0 performed as well as or slightly better than GIN-ε.

**Key points**

- A message-passing GNN can separate at most the graph pairs that the 1-WL colour-refinement test separates.
- GIN reaches the bound: $h_v\leftarrow\mathrm{MLP}((1+\varepsilon)h_v+\sum_{u}h_u)$, plus a sum readout over every layer, concatenated.
- Sum keeps the multiset of neighbour features, mean keeps only its proportions, and max keeps only its set. GCN-style and max-pool aggregators are therefore weaker.
- MLPs (not single linear layers) are needed to approximate the injective functions; GIN-0 with ε = 0 works as well in practice.
- 1-WL, and so GIN, cannot separate regular graphs of the same size and degree (C6 vs two triangles) or count triangles. Higher-order, positional or subgraph methods go further.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
