PAPERS-07-007 · Paper — Graph Isomorphism Network (GIN)

The paper

The Graph Isomorphism Network (GIN) paper, titled “How Powerful are Graph Neural Networks?” by Xu, Hu, Leskovec, and Jegelka, appeared in 2019 at ICLR. It is considered a landmark because it rigorously analyzed GNN expressive power and introduced a provably maximally expressive architecture.

Before this paper

Before GIN, graph neural networks performed well in practice but researchers did not know how powerful they truly were at distinguishing different graph structures. The field lacked a theoretical grounding for the limits of message‑passing GNNs. Consequently, it was unclear whether existing designs could capture all structural nuances needed for tasks like graph classification. This uncertainty created a wall for systematic improvement.

The key idea

The key insight of the paper is to treat GNNs as a form of the Weisfeiler‑Lehman (WL) graph isomorphism test and to show that a GNN can be as powerful as the WL test if its neighbor aggregation function is injective. By ensuring injectivity, the network can uniquely encode the multiset of neighbor features, enabling it to distinguish any graphs that the WL test can separate. This theoretical link guides the design of a maximally expressive GNN.

How it works

GIN works by first aggregating each node’s neighbor features with a simple sum, which preserves the full multiset information. The summed vector is then passed through a multilayer perceptron (MLP) that acts as a learnable, injective transformation. This process is repeated for several layers, allowing information to propagate across the graph. The sum‑plus‑MLP combination guarantees that the aggregation is injective, meeting the condition for WL‑level expressiveness. Finally, a readout function pools node embeddings to produce a graph‑level representation for classification.

See it — how powerful can a GNN be

flowchart LR
  A["Neighbor features"] --> B["SUM (not mean/max)"]
  B --> C["MLP"]
  C --> D["As powerful as<br/>the WL test"]

What they showed

The authors demonstrated that GIN achieves state‑of‑the‑art performance on standard graph‑classification benchmarks, matching the theoretical expressive power they proved. Their experiments showed that using the sum aggregator and MLP outperformed mean or max aggregators, confirming the importance of injectivity.

What it changed

GIN gave the community a principled understanding of the expressive limits of GNNs and showed how to design networks that reach those limits. It shifted research from empirical trial‑and‑error toward theory‑driven architecture design. As a result, GIN quickly became a strong baseline and inspired many follow‑up works that build on its expressive framework. Next: Message Passing Neural Networks (MPNN).

The one-line takeaway

Sum aggregation with an injective MLP makes a GNN as powerful as the Weisfeiler‑Lehman test.

Read it / meet it

Reading the original ICLR paper will reveal the elegant theory and simple architecture behind GIN. Today, you’ll find GIN used as a standard baseline in graph‑classification libraries and benchmarks, reflecting its lasting impact.