Definition
Graph Isomorphism Network (GIN) is a message-passing GNN whose layer sums the neighbour features, adds 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:
- a multiset: repeated colours are counted
- 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 of bounded size there is a function for which is unique for each (Lemma 5). Corollary 6 extends this to the pair (node, neighbourhood): is unique for infinitely many , including every irrational one. An MLP can approximate the required and the next layer's map (universal approximation), which gives the update:
- input node features (one-hot atom type, one-hot degree, …)
- learned scalar (GIN-) or fixed at 0 (GIN-0)
- 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:
- sum readout, injective on multisets for the same reason as the sum aggregator
- number of GIN layers; the paper used 5 layers including the input layer, so
Why mean and max fall short
The mean of the neighbour features records the distribution of the neighbourhood: the neighbours and give the same mean. The max records only the set of distinct features, so and 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.
Worked example: C4 against the star K1,3
| 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
1import numpy as np23def wl_test(A1, A2, iters=3):4 """1-WL on two graphs with one shared colour table; True if the histograms ever differ."""5 cols = [[0] * len(A1), [0] * len(A2)] # no node features: one initial colour6 table = {}7 for _ in range(iters):8 cols = [[table.setdefault((c[v], tuple(sorted(c[u] for u in np.flatnonzero(A[v])))), len(table))9 for v in range(len(A))] for A, c in zip((A1, A2), cols)]10 if sorted(cols[0]) != sorted(cols[1]):11 return True12 return False1314def gin_embed(A, X, layers, eps=0.0):15 """GIN forward pass: h <- MLP((1+eps) h + A h); graph vector = concat of sum readouts."""16 H, reads = X, [X.sum(0)]17 for W1, W2 in layers:18 Z = (1 + eps) * H + A @ H # sum aggregation keeps neighbour counts19 H = np.maximum(0, np.maximum(0, Z @ W1) @ W2) # 2-layer MLP (batch norm omitted)20 reads.append(H.sum(0))21 return np.concatenate(reads)2223def cycle(n):24 return np.roll(np.eye(n), 1, 1) + np.roll(np.eye(n), -1, 1)2526C6, two_C3 = cycle(6), np.kron(np.eye(2), cycle(3)) # 6-cycle vs two disjoint triangles27C4, star = cycle(4), np.zeros((4, 4))28star[0, 1:] = star[1:, 0] = 12930rng = np.random.default_rng(0)31layers = [(rng.normal(size=(d, 16)), rng.normal(size=(16, 16)) / 4) for d in (1, 16, 16)]32for name, G1, G2 in [("C6 vs 2xC3", C6, two_C3), ("C4 vs star", C4, star)]:33 h1 = gin_embed(G1, np.ones((len(G1), 1)), layers)34 h2 = gin_embed(G2, np.ones((len(G2), 1)), layers)35 print(f"{name}: 1-WL distinguishes={wl_test(G1, G2)}, GIN gap={np.linalg.norm(h1 - h2):.3f}")36# C6 vs 2xC3: 1-WL distinguishes=False, GIN gap=0.00037# C4 vs star: 1-WL distinguishes=True, GIN gap=157.216In 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 -tuples of nodes (Morris et al., following the -WL hierarchy), at 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.
Check yourself
All nodes have the same feature. Which aggregator lets a GNN tell the star K1,3 from the 4-cycle C4?
Check yourself
Why does GIN add (1 + ε) h_v instead of putting v into the neighbour sum?
Remember
- ✓A message-passing GNN can separate at most the graph pairs that the 1-WL colour-refinement test separates.
- ✓GIN reaches the bound: , 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.