How Powerful Are Graph Neural Networks?

Graph neural networks follow a simple recipe called neighborhood aggregation (also known as message passing). At each layer, every node collects feature vectors from its neighbors, combines them with some aggregation function (sum, mean, or max), and then transforms the result. After k layers, each node's representation captures the structure of its k-hop neighborhood.

But here is the crucial question: can the GNN tell two different graphs apart? If two graphs produce the same node embeddings, the GNN treats them as identical — even if they have completely different structures. The power of a GNN is its ability to map different graphs to different embeddings. A more powerful GNN can distinguish a larger family of non-isomorphic graphs.

This notion of power has a classical counterpart in graph theory: the Weisfeiler-Lehman (WL) graph isomorphism test, a procedure that iteratively refines node colors based on neighbor colors. Two graphs that the WL test cannot distinguish are called WL-equivalent. The key insight of this paper: the neighborhood aggregation in GNNs is structurally identical to the WL test's color refinement. Therefore, a GNN can be at most as powerful as the WL test — and the question becomes: which GNNs actually reach this ceiling?

The 1-dimensional Weisfeiler-Lehman test works as follows. Every node starts with an initial color (its label or degree). At each iteration, the test collects the multiset of colors from each node's neighbors, hashes the combination of the node's own color and the neighbor multiset into a new color, and assigns it. After enough iterations, if two graphs have different sets of node colors, they are declared non-isomorphic.

Now compare this with a generic GNN layer. Each node collects features from its neighbors (AGGREGATE), combines them with its own features (COMBINE), and passes the result through a nonlinearity. The parallel is exact: both processes recursively refine node representations based on local neighborhoods. The WL test uses a hash function (injective by construction); the GNN uses a learned neural function that may or may not be injective.

The paper formalizes this: Theorem 1 states that if the GNN's aggregation function is injective — i.e., it never maps two different multisets to the same output — then the GNN is exactly as powerful as the WL test. If the aggregation is not injective, the GNN is strictly weaker.

The paper examines three aggregation functions and ranks them by how much multiset information they preserve.

Sum captures the full multiset. Given a multiset like 3, sum produces 7. A different multiset 4 produces 7 too — but with the right neural network transformation applied before summation, sum can be made injective. Sum preserves both the identity and the multiplicity of each element.

Mean captures the proportion (distribution) of elements but loses the count. The multisets 2 and 2 both have mean 4/3 — mean cannot tell them apart. Mean is blind to the size of the neighborhood: a node with 3 neighbors averaging feature value 5 and a node with 300 neighbors averaging feature value 5 look identical.

Max captures only the presence of distinct elements but loses multiplicity entirely. The multisets 3 and 3 are indistinguishable under max because max(3, …) = 3 regardless of duplicates. Max is blind to how many times each feature appears.

The hierarchy is clear: sum > mean > max in discriminative power. GCN uses mean; the max-pooling variant of GraphSAGE uses max. Neither can reach the WL ceiling.

Now that we know what makes a GNN maximally powerful — injective aggregation over multisets — the question is: how do we build one? The paper shows that sum aggregation followed by a multi-layer perceptron (MLP) is sufficient.

The intuition: the Universal Approximation Theorem tells us that an MLP can approximate any continuous function. The paper extends this to multisets: given a countable input space, there exists a function f such that f composed with sum is injective over all multisets of bounded size. An MLP can learn this f. Therefore: MLP ∘ sum is an injective multiset function — exactly what we need.

The full GIN update rule combines the node's own features with the sum of neighbor features, weighted by a learnable parameter ε, and passes everything through an MLP. The ε parameter allows the network to learn how much to weigh the center node versus its neighbors — an important degree of freedom that ensures the combined function is also injective.

For graph classification, we need a single vector representing the entire graph, not just individual nodes. A naive approach is to read out only from the final layer, but this loses information: early layers capture local structure (edges, triangles), while later layers capture global patterns. Discarding early representations is like reading only the conclusion of a book.

GIN uses a concatenation readout that reads from every layer. At each layer k, it sums all node features in the graph to get a graph-level vector, then concatenates the vectors from all layers. This preserves structural information at every scale — from immediate neighbors to the full graph diameter.

The authors validate their theory on 9 graph classification benchmarks spanning bioinformatics (MUTAG, PTC, PROTEINS, NCI1) and social networks (COLLAB, IMDB-BINARY, IMDB-MULTI, REDDIT-BINARY, REDDIT-MULTI-5K).

Two key findings emerge. First, training accuracy confirms expressivity: GIN achieves near-perfect training accuracy on all datasets, while GCN and GraphSAGE variants often severely underfit. This directly validates the theory — a more expressive model can fit more complex structural patterns in the training data.

Second, test accuracy correlates with theory: GIN-0 (with ε fixed at 0) and GIN (with learned ε) consistently outperform or match the less expressive GNN variants. On social network datasets where graph structure (rather than node features) is the primary signal, the advantage of sum aggregation is particularly pronounced.

The paper establishes a clear hierarchy of GNN variants by discriminative power:

At the top sits GIN (and the WL test), which can distinguish any pair of non-isomorphic graphs that differ in their multiset of subtree patterns. In the middle, mean-based GNNs (like GCN) capture the distribution of features but lose count information. At the bottom, max-based GNNs capture only the set of distinct features, losing both count and distribution.

This hierarchy has a geometric interpretation. Think of node neighborhoods as bags of colored marbles. Sum-based GNNs record the exact inventory: "3 red, 2 blue, 1 green." Mean-based GNNs record the proportions: "50% red, 33% blue, 17% green" — identical for bags of 6 and 60. Max-based GNNs record only which colors are present: "red, blue, green" — identical for any bag containing those colors.

GIN reaches the 1-WL ceiling, but the 1-WL test itself has limitations. It cannot distinguish certain regular graphs (like two non-isomorphic 3-regular graphs on 8 nodes) or count substructures like triangles and cycles. Recognizing these limitations opened a rich research frontier.

Higher-order WL tests (k-WL) operate on k-tuples of nodes instead of individual nodes, giving strictly more discriminative power. Architectures like k-IGN and Graphormer go beyond the 1-WL ceiling by incorporating global positional encodings, higher-order interactions, or attention mechanisms that implicitly capture more structural information.

The GIN paper's lasting contribution is not GIN itself — it is the framework. By connecting GNNs to the WL hierarchy, it gave the community a shared language for reasoning about expressivity, turning architecture design from art into science.