How Powerful Are Graph Neural Networks?

🎯 Pitch

Standard graph neural networks like GCN and GraphSAGE are fundamentally blind to simple graph structures—they cannot even count the number of neighbors with identical features. By revealing this surprising limitation and proving that injective sum aggregation is both necessary and sufficient for maximum expressive power, the authors show their Graph Isomorphism Network matches the theoretical upper bound of the Weisfeiler-Lehman test and achieves superior empirical results.

1. Executive Summary

This paper analyzes the representational power of Graph Neural Networks (GNNs) by establishing a formal connection to the Weisfeiler-Lehman (WL) graph isomorphism test, showing that GNNs are at most as powerful as the WL test and that their discriminative capacity depends critically on whether their aggregation functions are injective over multisets of neighbor features (e.g., sum aggregators preserve multiset distinctness while mean and max-pooling do not). The authors then develop the Graph Isomorphism Network (GIN), a simple architecture that provably achieves WL-equivalent expressive power by combining injective sum aggregation with multi-layer perceptrons, and demonstrate that GINs almost perfectly fit training data on 9 graph classification benchmarks while less expressive variants—GCN with mean pooling and GraphSAGE with max-pooling—severely underfit, establishing that the theoretical expressiveness ranking directly predicts empirical representational capacity. GINs achieve state-of-the-art test accuracy on social network and bioinformatics datasets, outperforming existing GNN variants and the WL subtree kernel on most benchmarks, with the boundary condition that expressive power is necessary but not sufficient—generalization benefits from the ability to capture structural similarity in learned embeddings rather than just discriminative one-hot labels, as evidenced by GNNs outperforming the WL kernel when node features carry informative signals.

2. Context and Motivation

The Core Problem: We Don't Know What GNNs Can Actually Represent

The fundamental question this paper tackles is deceptively simple: given a graph with node features, what structures can a Graph Neural Network learn to distinguish, and what structures will it inevitably confuse? This matters because GNNs had, by 2019, become the dominant paradigm for representation learning on graph-structured data — molecules, social networks, biological interaction graphs, financial transaction networks — yet their design was driven almost entirely by empirical intuition and trial-and-error rather than principled understanding.

The gap is striking when you compare GNNs to other neural architectures. Convolutional neural networks had well-understood properties: we knew that stacking layers expanded receptive fields, that max-pooling provided translation invariance, that deeper networks could represent more complex hierarchical features. For GNNs, by contrast, the literature offered a growing collection of aggregation functions — sum, mean, max-pooling, attention-weighted averaging, LSTM-based pooling — but no theoretical framework for understanding why one might work better than another, or what each could and could not represent. A practitioner choosing between GCN (Kipf & Welling, 2017) and GraphSAGE (Hamilton et al., 2017a) had no principled basis for the decision beyond benchmark performance.

This gap is not merely academic. The paper identifies a concrete, practically important failure mode: popular GNN variants — specifically mean-pooling and max-pooling aggregators — cannot distinguish certain simple graph structures that are trivially different to a human observer. Figure 3 in the paper illustrates three such cases. In Figure 3a, two nodes have neighborhoods of different sizes (2 neighbors vs. 3 neighbors) but identical node features; mean and max-pooling collapse them to the same representation. In Figure 3b, two nodes have neighborhoods containing different multisets of features ({red, green} vs. {red, green, green}); max-pooling treats them as identical because it only sees the set of distinct features. In Figure 3c, mean-pooling fails to distinguish neighborhoods with different multiplicities but identical proportions of features. These are not pathological edge cases — they correspond to real structural differences in graphs that a representation should capture, particularly when node features are sparse or categorical (as in molecular graphs, where atoms have discrete types).

Why This Matters: Beyond Academic Classification

The paper's motivation extends beyond graph classification benchmarks to fundamental questions about what it means to "learn representations" of graph-structured data. The authors frame this along several dimensions:

Theoretical significance: characterizing what is learnable. Before this work, there was no formal characterization of the representational capacity of GNNs as a class. We knew GNNs could solve certain tasks, but we didn't know the upper bound on their discriminative power — i.e., what is the hardest graph distinction any GNN can make? The paper establishes that this upper bound is exactly the Weisfeiler-Lehman (WL) graph isomorphism test, a classical algorithm from 1968 that iteratively refines node labels by hashing neighborhood multisets. This connection is profound: it means that the entire class of neighborhood-aggregation GNNs, regardless of architecture details, cannot discriminate graphs that the WL test cannot discriminate. The WL test, while powerful, is known to fail on certain graph classes — notably regular graphs (Cai et al., 1992; Douglas, 2011) — which immediately implies that all standard GNNs also fail on those same graphs. This provides a principled ceiling for what the entire GNN paradigm can achieve.

Practical significance: model selection and architecture design. If you're building a GNN for a new application, you face a bewildering array of choices: GCN, GraphSAGE, GAT, ChebNet, GIN, and dozens of others. The paper provides a unifying framework for reasoning about these choices in terms of their expressive power. It reveals that many popular choices — GCN's mean-pooling, GraphSAGE's max-pooling — are inherently less powerful than alternatives that use sum aggregation, and it explains exactly what information they lose: mean captures distributions (proportions) of features but not exact counts; max-pooling captures the underlying set of features but loses all multiplicity information. This is actionable guidance: if your task depends on exact structural counts (e.g., counting the number of carbon atoms in a molecular neighborhood), mean-pooling will fail; if it depends only on the presence or absence of features, max-pooling might suffice.

Empirical significance: underfitting as a diagnostic signal. A key insight that runs through the paper's experiments is that training set performance directly reflects representational power. The authors show (Figure 4) that less powerful GNN variants — those using mean or max-pooling, or 1-layer perceptrons instead of MLPs — severely underfit the training data on several datasets, while GIN (which uses sum aggregation and MLPs) fits almost perfectly. This turns expressive power from an abstract theoretical concern into a concrete, diagnosable phenomenon: if your GNN can't even fit the training set, the problem isn't overfitting or poor generalization — it's that the model literally cannot represent the distinctions present in the data. This provides a practical debugging tool for practitioners.

Where Prior Approaches Fall Short

To understand the paper's contribution, it's essential to understand the state of GNN research at the time of writing (2018–2019) and the specific limitations of prior work.

GNN variants were proliferating without theoretical grounding. The paper cites a long list of GNN architectures (Section 1), including spectral approaches (Defferrard et al., 2016), spatial aggregation methods (Hamilton et al., 2017a; Kipf & Welling, 2017), attention mechanisms (Velickovic et al., 2018), gated recurrent units (Li et al., 2016), and graph-level pooling schemes (Ying et al., 2018; Zhang et al., 2018). Each of these was justified by empirical performance on specific benchmarks, with little to no analysis of what structures they could or could not represent. The field was accumulating architectures faster than it was accumulating understanding.

Prior theoretical analysis was architecture-specific and limited. The paper acknowledges that some theoretical work existed but notes its narrow scope (Section 6). Scarselli et al. (2009a) showed that the earliest GNN model (Scarselli et al., 2009b) could approximate measurable functions in probability, but this result applied to a specific architecture and didn't characterize what graphs it could distinguish. Lei et al. (2017) showed their proposed architecture lies in the RKHS of graph kernels, but didn't explicitly study which graphs it could tell apart. None of this prior work provided a general framework that could analyze the expressive power of arbitrary aggregation-based GNNs — which is exactly what this paper sets out to build.

The WL connection was known but unexploited. The fact that GNNs resemble the WL test was not entirely new. The WL test iteratively aggregates and hashes neighborhood labels, just as GNNs iteratively aggregate and transform neighborhood features. The WL subtree kernel (Shervashidze et al., 2011) had been proposed as a graph similarity measure based on counts of WL node labels at different iterations. But prior to this paper, no one had formalized the connection as a representational bound — showing that GNNs are at most as powerful as WL, and more importantly, establishing the precise conditions (injective aggregation, injective readout) under which a GNN matches WL's power. This transforms the WL test from an interesting analogy into a theoretical tool for analyzing GNN expressiveness.

The injectivity condition was not recognized as central. Prior GNN designs used aggregation functions like mean and max-pooling without considering whether they were injective over multisets — that is, whether they map distinct multisets of neighbor features to distinct aggregated representations. The paper's key theoretical insight is that injectivity is the property that determines discriminative power. Mean-pooling and max-pooling are not injective over multisets (as proven in Corollaries 8 and 9), while sum-pooling combined with a suitable transformation $f$ can be (Lemma 5). This explains, in a unified way, why GCN and GraphSAGE are less powerful than a sum-based architecture — not because of any implementation detail, but because of a fundamental mathematical property of their aggregation functions.

GraphSAGE and GCN had known limitations without understood causes. GraphSAGE with max-pooling (Equation 2.2) was known to work well on node classification tasks but its representational properties were unclear. GCN's mean-pooling (Equation 2.3) achieved state-of-the-art results on semi-supervised node classification but there was no understanding of what graph structures it could or couldn't capture. The paper provides precise characterizations: GraphSAGE with max-pooling learns the underlying set of neighbor features (ignoring multiplicities); GCN with mean-pooling learns the distribution of neighbor features (capturing proportions but not exact counts). These characterizations explain empirical observations — for instance, GCN's effectiveness on node classification tasks where node features are rich and rarely repeated, making the distribution a sufficient signal — while also revealing their blind spots.

How This Paper Positions Itself

The paper positions itself not as proposing yet another GNN variant, but as providing the theoretical foundations that the field had been missing. This is clear from the paper's structure: roughly half the paper (Sections 2–5) develops theory before presenting any new architecture or experiments. The GIN architecture (Section 4) emerges conceptually from the theory — it is designed to satisfy the injectivity conditions that the theory shows are necessary and sufficient for WL-equivalent power — rather than being justified by benchmark performance alone.

The paper's framing is deliberately general. It doesn't claim that GIN is the only maximally powerful GNN (the authors explicitly note that "there may exist many other powerful GNNs" in Section 4.1). Rather, GIN serves as a proof of concept that WL-equivalent architectures exist and are practical, and as a baseline against which other architectures can be measured in terms of their expressive power gap.

The paper also positions itself at the intersection of two research communities that had been largely separate: the graph kernel community (which developed the WL subtree kernel and characterized its properties) and the deep learning on graphs community (which developed GNN architectures but lacked formal analysis). By showing that GIN generalizes the WL subtree kernel — the kernel essentially uses one-hot WL labels, while GIN learns continuous embeddings — the paper bridges these communities and provides a pathway for translating kernel-based insights into neural architectures.

A crucial nuance in the paper's positioning: it does not claim that expressive power is sufficient for good performance. The WL subtree kernel has maximum discriminative power among GNNs (it is the WL test), yet GNNs often outperform it empirically (Table 1). This is because the WL kernel uses discrete one-hot labels that cannot capture similarity between different but related graph structures, while GNNs learn continuous embeddings that can map similar substructures to nearby points in embedding space. This observation positions the paper as arguing for both high expressive power (to avoid underfitting) and learned continuous representations (to enable generalization through similarity), providing a more nuanced view than simply maximizing discriminative capacity.

Finally, the paper explicitly frames its contribution as opening a research direction rather than closing one. Section 8 acknowledges that the WL test provides an upper bound for neighborhood-aggregation GNNs, and that going beyond this bound requires architectures that break out of the neighborhood message-passing paradigm entirely — for example, by considering higher-order structures (pairs or triplets of nodes rather than individual nodes and their neighbors). This honest acknowledgment of the framework's boundary conditions gives the paper intellectual integrity and maps out the next frontier for the field.

3. Technical Approach

3.1 Reader Orientation (Approachable Technical Breakdown)

This is a theoretical analysis paper that develops a formal framework to measure and compare the representational power of any Graph Neural Network architecture that operates via neighborhood aggregation. The core idea is deceptively simple: a GNN can distinguish two graph structures if and only if its aggregation function can distinguish the corresponding multisets of neighbor features — so by studying what classes of multiset functions different aggregators (sum, mean, max) can represent, we can precisely characterize what graph structures they can and cannot tell apart, and then design an architecture that optimally preserves all structural information.

The system being built is not a piece of software but a formal proof framework that connects GNNs to the Weisfeiler-Lehman (WL) graph isomorphism test, establishing that WL-equivalent power is the theoretical maximum for any neighborhood-aggregation GNN and that achieving this maximum requires the aggregation and readout functions to be injective — meaning they must map distinct inputs to distinct outputs, never collapsing different multisets into the same representation.

The problem it solves is the absence of a principled way to evaluate GNN architectures: before this work, practitioners had no way to know whether a GNN was failing because of insufficient training, poor hyperparameters, or a fundamental representational limitation. The framework answers this by providing a theoretical ceiling (the WL test) and a diagnostic criterion (training set underfitting indicates insufficient expressive power), transforming GNN design from empirical trial-and-error into a theoretically-grounded engineering discipline.

3.2 Big-Picture Architecture (Diagram in Words)

The theoretical framework has four major components, arranged hierarchically:

Graph abstraction layer: The framework models graphs not as adjacency matrices or edge lists, but as collections of rooted subtree structures — the pattern of features and connections within a node's k-hop neighborhood. Each iteration of a GNN (or the WL test) captures one additional "ring" of this subtree, recursively building a representation that encodes progressively larger structural contexts around each node.
Multiset formulation: At the core of the framework, the set of feature vectors of a node's neighbors is treated as a multiset — a generalized set that tracks element multiplicities (e.g., {a, a, b} is distinct from {a, b}). This mathematical abstraction is what makes the framework general: every GNN aggregation step is fundamentally a function that takes a multiset of incoming neighbor features and produces a single aggregated output, regardless of whether the specific implementation uses sum, mean, max-pooling, or attention.
Injectivity analysis engine: The framework evaluates aggregator power by analyzing whether the function implemented by a given GNN layer can be injective over multisets — that is, whether distinct multisets of neighbor features always produce distinct aggregated outputs. The framework proves that sum-pooling combined with a suitable transformation $f$ (parameterized by a neural network) can be injective via Lemma 5, while mean-pooling is only injective up to distributional equivalence (Corollary 8) and max-pooling is only injective up to set equivalence (Corollary 9). This component translates abstract mathematical properties of multiset functions into concrete representational capabilities and limitations.
WL equivalence theorem: The framework's capstone result (Theorem 3) establishes that if a GNN uses injective aggregation and injective graph-level readout, and is given sufficient depth, it achieves representational power equal to the WL test — meaning it can distinguish any pair of graphs that the WL test can distinguish. This theorem simultaneously provides an upper bound (no aggregation-based GNN can exceed WL power, by Lemma 2) and a constructive recipe for achieving that bound (use sum aggregation with MLPs and sum readout).

Information flows through the framework as follows: a graph enters as node features → the framework recursively constructs its rooted subtree structures → the aggregation function's behavior on the corresponding multisets determines whether subtrees are collapsed or preserved → the preserved distinctions propagate through layers → the readout function aggregates final node representations into a graph embedding → the embedding's ability to separate non-isomorphic graphs defines the GNN's expressive power.

3.3 Roadmap for the Deep Dive

I'll walk through the technical content in this order, which builds from abstract foundations to concrete architecture:

First, I explain how the framework models graphs as multisets of neighbor features, why this abstraction is what makes the analysis general, and how the recursive construction of rooted subtrees connects GNN layers to graph structure — this is the conceptual machinery that makes everything else work.
Second, I walk through Lemma 2, which establishes the fundamental upper bound: no aggregation-based GNN can distinguish graphs that the WL test cannot. Understanding this ceiling is essential before discussing how to reach it.
Third, I detail Theorem 3 and its proof strategy, which provide the conditions for a GNN to match WL power. This theorem is the paper's central theoretical result and the justification for GIN's design.
Fourth, I explain the deep multisets theory (Lemma 5 and Corollary 6) that shows sum aggregation with a suitable transformation can be injective — this is why GIN uses sum rather than mean or max.
Fifth, I characterize the limitations of less powerful aggregators: why 1-layer perceptrons aren't sufficient (Lemma 7), what mean-pooling actually captures (Corollary 8), and what max-pooling actually captures (Corollary 9). Understanding what these aggregators can represent, not just what they can't, is crucial for knowing when to use them.
Sixth, I walk through the GIN architecture itself — the update rule (Equation 4.1), the readout function (Equation 4.2), and the design decisions behind them — showing how each component maps to a theoretical requirement.

3.4 Detailed, Sentence-Based Technical Breakdown

Modeling Graphs as Multisets of Neighbor Features: The Core Abstraction

The paper's theoretical framework begins with a fundamental shift in perspective. Rather than thinking about a graph as an adjacency matrix or a collection of edges, the framework models each node's local neighborhood as a multiset of feature vectors. A multiset, formally defined in Definition 1, is a 2-tuple $X = (S, m)$ where $S$ is the underlying set of distinct elements and $m: S \to \mathbb{N}_{\geq 1}$ is a function giving the multiplicity (count) of each element.

This abstraction is powerful because it captures exactly the information available to a GNN during one round of neighborhood aggregation. Consider a specific node $v$ at layer $k$ . Its neighbors $u \in \mathcal{N}(v)$ each have a feature vector $h_u^{(k-1)}$ from the previous layer. Some of these feature vectors may be identical — for instance, in a molecular graph, two carbon atoms with similar local environments might have converged to indistinguishable embeddings. The multiset $\{h_u^{(k-1)} : u \in \mathcal{N}(v)\}$ preserves both which features appear and how many times each appears. This distinction matters: a node with two carbon neighbors and one oxygen neighbor is structurally different from a node with one carbon and one oxygen, and a representation that collapses these two cases loses information.

The key insight, illustrated in Figure 1, is that the aggregation step of any GNN (Equation 2.1) can be viewed as a function over this multiset. Specifically, the AGGREGATE operation takes the multiset of neighbor feature vectors as input and produces a single aggregated vector $a_v^{(k)}$ . The COMBINE operation then merges this with the node's own previous feature $h_v^{(k-1)}$ . The entire layer computation can therefore be written as $h_v^{(k)} = \phi\left(h_v^{(k-1)}, f\left(\{h_u^{(k-1)} : u \in \mathcal{N}(v)\}\right)\right)$ , where $f$ is the multiset aggregation function and $\phi$ is the combine function.

The recursive nature of GNN layers maps directly to recursive construction of rooted subtrees. At layer 0, each node's representation encodes only its own input features. At layer 1, the aggregation incorporates the features of immediate neighbors, so the representation encodes the node's features plus the multiset of its neighbors' features — a subtree of height 1. At layer 2, the representation incorporates neighbors' neighbors, encoding a subtree of height 2. This is exactly what the WL test does: it iteratively refines node labels based on the labels of immediate neighbors, so that after $k$ iterations, a node's label uniquely identifies the subtree of height $k$ rooted at that node.

The framework's central question then becomes: under what conditions does a GNN's aggregation function $f$ preserve the distinctness of different multisets? If two nodes $v$ and $v'$ have different multisets of neighbor features — meaning their local neighborhoods are structurally different — does the aggregation produce different outputs for them? If $f$ is injective (one-to-one), then distinct multisets always map to distinct aggregated representations, and the structural difference is preserved. If $f$ is not injective, then some structural differences are collapsed and lost.

The paper assumes throughout that node input features come from a countable universe. This is a technical condition (formalized in Lemma 4) that ensures the space of possible feature vectors remains countable at all layers, which makes the existence proofs for injective functions cleaner. In practice, this means "there exists a mapping that separates elements" rather than requiring handling of continuous uncountable spaces. The authors note that "for finite graphs, node feature vectors at deeper layers of any fixed model are also from a countable universe," so the assumption holds for practical purposes.

The Upper Bound: GNNs Cannot Exceed WL Power (Lemma 2)

Lemma 2 establishes the theoretical ceiling for all aggregation-based GNNs. The formal statement:

Lemma 2. Let $G_1$ and $G_2$ be any two non-isomorphic graphs. If a graph neural network $\mathcal{A} : \mathcal{G} \to \mathbb{R}^d$ maps $G_1$ and $G_2$ to different embeddings, the Weisfeiler-Lehman graph isomorphism test also decides $G_1$ and $G_2$ are not isomorphic.

What this means in operational terms: If any GNN can tell two graphs apart by assigning them different embedding vectors, then the WL test — a classical algorithm from 1968 — can also tell them apart. Conversely, if the WL test cannot distinguish two graphs, then no GNN (within the neighborhood-aggregation paradigm) can distinguish them either. The WL test thus provides an upper bound on GNN discriminative power: GNNs are at most as powerful as WL.

The proof strategy (in Appendix A) is an induction on layers. The key idea is to show that if two nodes have the same WL label at iteration $i$ , they must also have the same GNN embedding at layer $i$ . The base case holds because both start from the same input features. For the induction step, if WL labels are equal at iteration $j+1$ , it means the multisets of neighbor WL labels at iteration $j$ were identical; by the induction hypothesis, those WL labels correspond to identical GNN embeddings, so the GNN receives identical multiset inputs; since the AGGREGATE and COMBINE functions are deterministic, the GNN produces identical outputs. Therefore, there exists a function $\phi$ mapping WL labels to GNN embeddings such that $h_v^{(i)} = \phi(\ell_v^{(i)})$ for all nodes $v$ at all iterations $i$ .

The critical step comes at the final layer. If the WL test cannot decide $G_1$ and $G_2$ are non-isomorphic, then they have the same multiset of node labels at every iteration, including the final iteration $K$ . Since GNN embeddings are deterministically derived from these labels via $\phi$ , the multisets of GNN node embeddings must also be identical. The graph-level readout function operates on this multiset and, being permutation-invariant, produces the same output for identical multisets. Hence $\mathcal{A}(G_1) = \mathcal{A}(G_2)$ , completing the proof by contradiction.

Why this bound is tight but not trivial: The WL test is known to be a powerful heuristic that distinguishes most non-isomorphic graphs (Babai & Kucera, 1979), with known exceptions — notably, it fails on regular graphs where every node has the same degree and the same multiset of neighbor labels at every iteration (Cai et al., 1992). Lemma 2 implies that all standard GNNs inherit these same failure cases. Two $k$ -regular graphs with $n$ nodes, where every node has exactly $k$ neighbors and all nodes have identical features, will always receive identical node embeddings from any GNN, regardless of depth. This is a hard representational ceiling that no amount of training data or hyperparameter tuning can overcome — it requires fundamentally different architectures that go beyond neighborhood message-passing.

Conditions for WL-Equivalent Power: Theorem 3

Theorem 3 is the paper's central constructive result. It provides necessary and sufficient conditions for a GNN to saturate the WL upper bound, i.e., to achieve exactly the same discriminative power as the WL test.

Theorem 3. Let $\mathcal{A} : \mathcal{G} \to \mathbb{R}^d$ be a GNN. With a sufficient number of GNN layers, $\mathcal{A}$ maps any graphs $G_1$ and $G_2$ that the Weisfeiler-Lehman test of isomorphism decides as non-isomorphic, to different embeddings if the following conditions hold:

a) $\mathcal{A}$ aggregates and updates node features iteratively with $h_v^{(k)} = \phi\left(h_v^{(k-1)}, f\left(\{h_u^{(k-1)} : u \in \mathcal{N}(v)\}\right)\right)$ where the functions $f$ , which operates on multisets, and $\phi$ are injective.

b) $\mathcal{A}$ 's graph-level readout, which operates on the multiset of node features $\{h_v^{(k)}\}$ , is injective.

Variable definitions:

$h_v^{(k)} \in \mathbb{R}^d$ is the feature vector of node $v$ at GNN layer $k$
$\mathcal{N}(v)$ is the set of neighbor nodes of $v$
$\{h_u^{(k-1)} : u \in \mathcal{N}(v)\}$ is the multiset of neighbor feature vectors from the previous layer
$f: \text{multiset}(\mathbb{R}^d) \to \mathbb{R}^d$ is the multiset aggregation function (what most GNNs call AGGREGATE)
$\phi: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}^d$ is the combine function that merges the node's own previous feature with the aggregated neighbor features
The readout function operates on the multiset $\{h_v^{(K)}\}$ of all node features at the final layer $K$

What this equation computes: Condition (a) specifies a two-step layer computation. First, $f$ takes the multiset of all features of $v$ 's neighbors and produces a single aggregated vector that captures the neighborhood's structural information. Then, $\phi$ takes this aggregated neighborhood vector together with $v$ 's own previous feature and produces $v$ 's new feature for the current layer. The requirement that both $f$ and $\phi$ are injective means: (1) $f$ must map different neighborhood multisets to different aggregated vectors, and (2) $\phi$ must map different $(\text{own\_feature}, \text{neighborhood\_aggregate})$ pairs to different outputs. Together, these conditions ensure that the layer never collapses structurally distinct nodes into the same representation. Condition (b) requires the readout function to similarly preserve distinctness at the graph level: different multisets of final node features must produce different graph embeddings.

Why this form: The separation of $f$ and $\phi$ into two injective functions, combined via composition, ensures the entire layer is injective. The composition of injective functions is injective, so if $f$ is injective over multisets and $\phi$ is injective over pairs, then the combined update $h_v^{(k)} = \phi(h_v^{(k-1)}, f(\{\cdots\}))$ is injective over $(\text{previous\_node\_feature}, \text{neighbor\_multiset})$ pairs. This is exactly the property the WL test has: the WL hash function $g$ is designed to be injective, mapping distinct $(\text{previous\_label}, \text{neighbor\_multiset})$ input pairs to distinct new labels. The injectivity of $\phi$ is why the combine step matters — if $\phi$ were not injective, different $(\text{own\_feature}, \text{neighborhood})$ pairs could collapse, losing structural information even if $f$ perfectly distinguishes neighborhoods.

Proof strategy (Appendix B): The proof constructs an explicit injective mapping between WL labels and GNN embeddings via induction. At iteration 0, the identity function maps WL labels to GNN features (they start from the same input). Assume an injective function $\phi^{(k-1)}$ exists mapping iteration $k-1$ WL labels to layer $k-1$ GNN features. Then for iteration $k$ :

The GNN layer produces $h_v^{(k)} = \phi\left(\phi^{(k-1)}(\ell_v^{(k-1)}), f\left(\{\phi^{(k-1)}(\ell_u^{(k-1)}) : u \in \mathcal{N}(v)\}\right)\right)$
Since $f$ and $\phi$ are injective and $\phi^{(k-1)}$ is injective by hypothesis, there exists an injective $\psi$ such that $h_v^{(k)} = \psi(\ell_v^{(k-1)}, \{\ell_u^{(k-1)} : u \in \mathcal{N}(v)\})$
The WL update is $\ell_v^{(k)} = g(\ell_v^{(k-1)}, \{\ell_u^{(k-1)} : u \in \mathcal{N}(v)\})$ where $g$ is injective
Therefore $h_v^{(k)} = \psi \circ g^{-1}(\ell_v^{(k)})$ , and $\phi^{(k)} = \psi \circ g^{-1}$ is injective as the composition of injective functions

At the final layer $K$ , the multisets of WL labels $\{\ell_v^{(K)}\}$ differ between $G_1$ and $G_2$ (by the assumption that WL decides non-isomorphism). Since $\phi^{(K)}$ is injective, the multisets of GNN embeddings $\{h_v^{(K)}\}$ also differ. Since the readout is injective over multisets of node features, $\mathcal{A}(G_1) \neq \mathcal{A}(G_2)$ .

The subtlety about "sufficient number of layers": The WL test converges to a stable labeling after at most $\text{diameter}(G)$ iterations (since after that, no node can receive new information from further hops). Theorem 3's "sufficient number of layers" means at least as many layers as the WL test needs to decide non-isomorphism for the pair of graphs in question. In the worst case, this could be up to the maximum graph diameter in the dataset. In practice, the paper uses 5 layers for all experiments, which is sufficient for the benchmarks considered.

Deep Multisets: Proving Sum Aggregation Can Be Injective (Lemma 5 and Corollary 6)

Lemma 5 is the theoretical foundation for why sum aggregation works. It proves that sum, combined with a suitable transformation of individual elements, is a universal function over multisets — it can represent any multiset function, and in particular can be made injective.

Lemma 5. Assume $\mathcal{X}$ is countable. There exists a function $f: \mathcal{X} \to \mathbb{R}^n$ so that $h(X) = \sum_{x \in X} f(x)$ is unique for each multiset $X \subset \mathcal{X}$ of bounded size. Moreover, any multiset function $g$ can be decomposed as $g(X) = \phi\left(\sum_{x \in X} f(x)\right)$ for some function $\phi$ .

Variable definitions:

$\mathcal{X}$ is the countable input feature space (the space of possible individual element features)
$X \subset \mathcal{X}$ is a multiset of elements from $\mathcal{X}$ , with bounded size $|X| < N$ for some $N$
$f: \mathcal{X} \to \mathbb{R}^n$ is a function that maps individual elements to vectors in $\mathbb{R}^n$
$h(X) = \sum_{x \in X} f(x)$ computes the element-wise sum of all transformed element vectors in the multiset
$g$ is any arbitrary function defined on multisets
$\phi$ is a function that maps the summed vector to the desired output

What this computes, operationally: The lemma says there exists a transformation $f$ — think of it as an embedding function for individual elements — such that if you embed each element in a multiset with $f$ , then sum all those embeddings, the resulting sum vector is unique for each distinct multiset. No two different bounded-size multisets produce the same sum. Furthermore, if you want to compute any function $g$ over multisets (e.g., a classifier that takes a multiset and predicts a label), you can do it by (1) applying $f$ to each element, (2) summing the results, and (3) applying a second function $\phi$ to the sum. The sum acts as a bottleneck that preserves all the structural information about the multiset, and $\phi$ extracts whatever property $g$ needs.

The constructive proof (Appendix D): The proof provides an explicit construction of $f$ . Since $\mathcal{X}$ is countable, there exists a bijection $Z: \mathcal{X} \to \mathbb{N}$ mapping each possible element to a unique natural number. Since multisets are of bounded size $|X| < N$ , we define $f(x) = N^{-Z(x)}$ . This makes $f$ map each element to a distinct power of $1/N$ — essentially a positional encoding where different element types occupy different "digits" in a base- $N$ number. The sum $\sum_{x \in X} f(x) = \sum_{x \in X} N^{-Z(x)}$ then acts like a base- $N$ representation where the multiplicity of each element type appears as the digit at position $Z(x)$ . Since base- $N$ representations are unique (no two different multisets of bounded size produce the same sum), $h(X)$ is injective.

Why this is important for GNNs: The Lemma says that if a GNN layer first applies a suitable transformation $f$ to each neighbor's feature vector (this $f$ can be learned by a neural network, such as an MLP), then sums the transformed vectors, and then applies another transformation $\phi$ to the sum (also learnable), then the layer can represent any function over multisets — including, critically, injective functions. This provides a constructive recipe: use sum aggregation, but apply MLPs before and after the sum. The "before" MLP learns the $f$ that makes the sum injective; the "after" MLP learns the $\phi$ that extracts the desired information.

The crucial distinction from sets: The paper notes an "important distinction between deep multisets and sets: certain popular injective set functions, such as the mean aggregator, are not injective multiset functions." For ordinary sets (where elements are unique), mean is injective because two different sets have different means (under appropriate $f$ ). But for multisets with repeated elements, mean collapses cases where the proportions are identical but the counts differ — $\{a, a, b\}$ and $\{a, b\}$ both produce the same mean $\frac{2f(a) + f(b)}{3}$ versus $\frac{f(a) + f(b)}{2}$ , which are different, but $\{a, a, b\}$ and $\{a, a, a, b, b, b\}$ with multiplicities scaled uniformly produce the same mean. Sum preserves the absolute counts and thus distinguishes these cases.

Corollary 6 extends Lemma 5 to handle the COMBINE step, where the node's own feature must be integrated with the aggregated neighbor features:

Corollary 6. Assume $\mathcal{X}$ is countable. There exists a function $f: \mathcal{X} \to \mathbb{R}^n$ so that for infinitely many choices of $\epsilon$ , including all irrational numbers, $h(c, X) = (1 + \epsilon) \cdot f(c) + \sum_{x \in X} f(x)$ is unique for each pair $(c, X)$ , where $c \in \mathcal{X}$ and $X \subset \mathcal{X}$ is a multiset of bounded size. Moreover, any function $g$ over such pairs can be decomposed as $g(c, X) = \varphi\left((1 + \epsilon) \cdot f(c) + \sum_{x \in X} f(x)\right)$ for some function $\varphi$ .

Variable definitions:

$c \in \mathcal{X}$ is the feature of the central node (the node being updated)
$X$ is the multiset of neighbor features
$\epsilon$ is a scalar weight (learnable or fixed)
$(1 + \epsilon) \cdot f(c)$ weights the central node's transformed feature
$\sum_{x \in X} f(x)$ is the sum of transformed neighbor features
The full expression $(1 + \epsilon) \cdot f(c) + \sum_{x \in X} f(x)$ produces a unique vector for each distinct $(\text{center}, \text{neighbors})$ pair

What this computes: The expression is a weighted combination of the central node's transformed feature and the sum of the neighbors' transformed features. The weight $(1 + \epsilon)$ on the central node distinguishes it from the neighbors: if $\epsilon = 0$ , then $f(c) + \sum_{x \in X} f(x)$ could potentially be ambiguous — for instance, $f(c) + \sum_{x \in X} f(x)$ might equal $f(c') + \sum_{x \in X'} f(x')$ for different center-neighborhood pairs under some transformations. The $\epsilon$ term breaks this symmetry. The proof shows that if $\epsilon$ is irrational, the equality $h(c, X) = h(c', X')$ for $(c, X) \neq (c', X')$ leads to a contradiction: the left side involves an irrational number while the right side is rational.

Why this particular form: The $(1+\epsilon)$ weighting elegantly solves the problem of distinguishing the center node from its neighbors within the sum. An alternative would be to concatenate $f(c)$ with $\sum_{x \in X} f(x)$ (producing a $2n$ -dimensional vector), but the weighted sum approach keeps the dimensionality at $n$ while still achieving injectivity. The paper notes that $\epsilon$ can be a learnable parameter or a fixed scalar; in experiments, GIN- $\epsilon$ learns it while GIN-0 fixes it to 0. Empirically, GIN-0 performs slightly better, which the paper attributes to simplicity.

The proof strategy for the irrational $\epsilon$ case is instructive. For $(c, X) \neq (c', X')$ with $c \neq c'$ , setting $h(c, X) = h(c', X')$ yields:

$\epsilon \cdot (f(c) - f(c')) = \left(f(c') + \sum_{x \in X'} f(x)\right) - \left(f(c) + \sum_{x \in X} f(x)\right)$

The left side involves $\epsilon$ multiplied by a non-zero rational number (since $f$ maps to rational numbers in the construction, e.g., $N^{-Z(x)}$ ), making it irrational. The right side is a finite sum of rational numbers, hence rational. Equality is impossible, proving injectivity.

Why 1-Layer Perceptrons Are Insufficient (Lemma 7)

Lemma 7 establishes a concrete limitation of GNNs that use only a single linear layer followed by a nonlinearity (such as ReLU) rather than multi-layer perceptrons.

Lemma 7. There exist finite multisets $X_1 \neq X_2$ so that for any linear mapping $W$ , $\sum_{x \in X_1} \text{ReLU}(Wx) = \sum_{x \in X_2} \text{ReLU}(Wx)$ .

Variable definitions:

$X_1, X_2$ are two different finite multisets of scalar or vector elements
$W$ is any linear transformation matrix (the weights of a single perceptron layer)
$\text{ReLU}(Wx)$ applies the linear map followed by ReLU activation elementwise
The sums are over all elements in each multiset

What this computes: The lemma says there exist specific pairs of multisets — the proof uses $X_1 = \{1, 1, 1, 1, 1\}$ (five copies of the value 1) and $X_2 = \{2, 3\}$ (the values 2 and 3) — that no single linear layer followed by ReLU can distinguish through sum aggregation. For any choice of weight matrix $W$ , the sum of ReLU-transformed elements is identical for both multisets.

Why this happens: The proof exploits the homogeneity of ReLU: $\text{ReLU}(\alpha x) = \alpha \cdot \text{ReLU}(x)$ for $\alpha > 0$ . Since all elements in $X_1$ and $X_2$ are positive, $Wx$ will have the same sign pattern for all elements — coordinates where $Wx$ is positive for one element will be positive for all, and similarly for negative coordinates. For positive coordinates, ReLU is linear, so the sum becomes $\text{ReLU}(W \sum_{x \in X} x)$ . Since $\sum_{x \in X_1} x = 5 = 2 + 3 = \sum_{x \in X_2} x$ , the sums are equal. For negative coordinates, ReLU outputs zero, so both sums contribute zero. Thus the total summed ReLU output is identical regardless of $W$ .

What this means practically: A GNN that uses a single linear layer + ReLU before (or as) the aggregation step cannot be injective over multisets, because it cannot distinguish multisets that have the same sum but different compositions. The proof extends beyond the specific example: any two multisets with different elements but identical sums would be indistinguishable. The paper notes that "with the bias term and sufficiently large output dimensionality, 1-layer perceptrons might be able to distinguish different multisets" — adding a bias term means the sum doesn't simply factor through $\sum_{x \in X} x$ — but crucially, even with bias, a 1-layer perceptron is not a universal approximator of multiset functions, unlike an MLP. It cannot represent arbitrary injective functions over multisets, which means there will always be some multiset pairs it collapses.

This lemma provides the theoretical motivation for GIN's use of MLPs rather than simple linear layers: MLPs, by the universal approximation theorem, can represent the injective $f$ and $\phi$ functions required by Theorem 3, while single-layer perceptrons provably cannot.

What Mean Aggregation Actually Captures (Corollary 8)

Corollary 8 characterizes exactly what information mean-pooling preserves and what it loses.

Corollary 8. Assume $\mathcal{X}$ is countable. There exists a function $f: \mathcal{X} \to \mathbb{R}^n$ so that for $h(X) = \frac{1}{|X|} \sum_{x \in X} f(x)$ , $h(X_1) = h(X_2)$ if and only if multisets $X_1$ and $X_2$ have the same distribution. That is, assuming $|X_2| \geq |X_1|$ , we have $X_1 = (S, m)$ and $X_2 = (S, k \cdot m)$ for some $k \in \mathbb{N}_{\geq 1}$ .

Variable definitions:

$f: \mathcal{X} \to \mathbb{R}^n$ is the element-wise transformation
$h(X) = \frac{1}{|X|} \sum_{x \in X} f(x)$ computes the mean of the transformed element vectors
$S$ is the underlying set of distinct elements in the multiset
$m: S \to \mathbb{N}_{\geq 1}$ gives the multiplicity of each distinct element
$k \cdot m$ means each multiplicity is scaled by the same factor $k$ (the distribution is identical)
Two multisets have the "same distribution" if $X_2$ is $X_1$ with all multiplicities scaled uniformly

What this computes, operationally: The corollary says that mean aggregation captures proportions and distributions of element types, but not absolute counts. If multiset $X_1$ contains $m(s)$ copies of each element type $s$ , and multiset $X_2$ contains $k \cdot m(s)$ copies (i.e., $X_2$ is exactly $k$ times as large but with the same relative composition), then $h(X_1) = h(X_2)$ — mean aggregation collapses them to the same representation. Conversely, if two multisets have different proportions of some element type, there exists an $f$ such that their mean representations differ.

Proof sketch: If $X_2 = k \cdot X_1$ , then $|X_2| = k|X_1|$ and $\sum_{x \in X_2} f(x) = k \sum_{x \in X_1} f(x)$ , so $\frac{1}{|X_2|} \sum = \frac{k}{k|X_1|} \sum = \frac{1}{|X_1|} \sum$ . The converse direction uses a construction $f(x) = N^{-2Z(x)}$ (with $N$ bounding multiset size and $Z$ mapping to naturals) to ensure the mean uniquely encodes the distribution.

Practical implications: This explains GCN's behavior in node classification tasks. When node features are rich and diverse (e.g., bag-of-words representations of documents in citation networks), features rarely repeat within a neighborhood, so the distribution is effectively the set itself — mean aggregation loses little information. It also explains why GCN fails on the REDDIT datasets in the paper's experiments: all nodes have identical scalar features (no informative input), so all neighborhoods have the same distribution (100% of the single feature value), and mean aggregation produces identical representations for all nodes regardless of graph structure.

What it means to "capture distributions": The mean aggregator is essentially computing an empirical estimate of the probability mass function over element types in the neighborhood. If you think of the neighborhood as a bag of discrete tokens, the mean (after appropriate transformation $f$ ) tells you "30% of neighbors are type A, 50% are type B, 20% are type C," but not "there are 3 of A, 5 of B, and 2 of C." The former (distribution) might be sufficient for tasks where the overall composition matters more than precise counts — for instance, in social networks, knowing the proportion of friends in a particular community might be more predictive than knowing the exact number.

What Max-Pooling Actually Captures (Corollary 9)

Corollary 9 provides an analogous characterization for max-pooling aggregation.

Corollary 9. Assume $\mathcal{X}$ is countable. Then there exists a function $f: \mathcal{X} \to \mathbb{R}^\infty$ so that for $h(X) = \max_{x \in X} f(x)$ , $h(X_1) = h(X_2)$ if and only if $X_1$ and $X_2$ have the same underlying set.

Variable definitions:

$f: \mathcal{X} \to \mathbb{R}^\infty$ maps elements to infinite-dimensional vectors (one-hot-like encodings)
$\max_{x \in X} f(x)$ takes the element-wise maximum over all transformed vectors in the multiset
The "underlying set" of a multiset $X = (S, m)$ is just $S$ — the distinct elements, ignoring multiplicities

What this computes, operationally: The max-pooling aggregator reduces a multiset to its underlying set. It tells you which types of elements appear in the neighborhood, but completely ignores how many of each type appear. If $X_1$ contains one red node and one blue node, and $X_2$ contains five red nodes and one blue node, max-pooling over appropriately transformed features will produce identical outputs — because max only cares about the presence of each feature, not its frequency. Conversely, if two multisets have different underlying sets (e.g., one contains green and one doesn't), there exists an $f$ that makes their max-pooled representations differ.

Proof sketch: The construction uses $f_i(x) = 1$ if $i = Z(x)$ and $f_i(x) = 0$ otherwise — essentially, a one-hot encoding in an infinite-dimensional space where each possible element type corresponds to a unique coordinate. The maximum over a multiset at coordinate $i$ is 1 if any element in the multiset has type $i$ , and 0 otherwise. Thus $h(X)$ is exactly the indicator vector of the underlying set $S$ .

Practical implications: This explains why max-pooling is suitable for tasks where identifying representative elements matters more than counting them. Qi et al. (2017) showed that max-pooling effectively identifies the "skeleton" of 3D point clouds and is robust to noise and outliers — this aligns perfectly with the set-capturing property: max-pooling ignores how many points lie on each part of the skeleton, focusing only on which parts are present. It also explains why GraphSAGE with max-pooling fails on tasks where multiplicities matter: in molecular graphs, distinguishing a carbon with two hydrogen neighbors from a carbon with three hydrogen neighbors requires counting, which max-pooling cannot do.

The dimensionality note: The proof uses $\mathbb{R}^\infty$ (infinite-dimensional space) for the one-hot construction, but the authors note this is for theoretical completeness. In practice, a finite-dimensional encoding with suitable $f$ (e.g., an MLP that learns to produce approximately one-hot-like features) can achieve approximate set-capture. The key is that max-pooling fundamentally cannot recover multiplicity information, regardless of the dimension or expressiveness of $f$ .

The GIN Architecture: Satisfaction of Theorem 3 Conditions

The Graph Isomorphism Network (GIN) is designed to satisfy the conditions of Theorem 3 using the tools from Lemma 5 and Corollary 6. The architecture is specified by a single update equation and a readout function.

GIN node update (Equation 4.1):

$h_v^{(k)} = \text{MLP}^{(k)}\left(\left(1 + \epsilon^{(k)}\right) \cdot h_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}\right)$

Variable definitions:

$h_v^{(k)} \in \mathbb{R}^d$ is the feature vector of node $v$ at layer $k$
$\text{MLP}^{(k)}$ is a multi-layer perceptron specific to layer $k$
$\epsilon^{(k)}$ is a scalar parameter (either learned or fixed) for layer $k$
$h_v^{(k-1)}$ is the node's own feature from the previous layer
$\sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}$ is the sum of all neighbor features from the previous layer
The term inside the MLP is the sum of the weighted self-feature and all neighbor features

What this computes, operationally: At each layer $k$ , for each node $v$ :

Multiply the node's own previous feature $h_v^{(k-1)}$ by $(1 + \epsilon^{(k)})$ — this gives the self-connection a slightly different weight than neighbor contributions
Sum all neighbor features $\sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}$
Add the weighted self-feature and the neighbor sum together
Pass the result through an MLP to produce the new feature $h_v^{(k)}$

Why this satisfies Theorem 3: The update rule directly instantiates Corollary 6. The term inside the MLP is $(1 + \epsilon) \cdot f(c) + \sum_{x \in X} f(x)$ where $c = h_v^{(k-1)}$ is the center node feature, $X = \{h_u^{(k-1)} : u \in \mathcal{N}(v)\}$ is the neighbor multiset, and $f$ is implicitly the identity in the sum (the element-wise transformation). The MLP then plays the role of $\varphi$ from Corollary 6, learning to extract the desired information from the injective sum representation. By the universal approximation theorem, an MLP with sufficient capacity can approximate any function, including the composition of $f$ and $\phi$ needed for injectivity.

Why the MLP is placed after the sum, not before: In Lemma 5, the universal multiset function decomposition is $g(X) = \phi(\sum_{x \in X} f(x))$ , where $f$ is applied to each element before summation and $\phi$ is applied after. In GIN, the MLP after the sum implements both $f$ and $\phi$ — since MLPs can represent function composition, applying an MLP to the sum is equivalent to applying $f$ to each element first, summing, then applying $\phi$ . The alternative (apply MLP to each neighbor, then sum, then maybe another MLP) would be equally valid theoretically but adds parameters. The paper notes: "In the first iteration, we do not need MLPs before summation if input features are one-hot encodings as their summation alone is injective" — for one-hot features, the sum directly gives multiplicity counts (a $d$ -dimensional vector where position $i$ equals the number of neighbors with feature $i$ ), which is already injective without further transformation.

GIN-0 vs. GIN- $\epsilon$ : The paper considers two variants:

GIN- $\epsilon$ : $\epsilon^{(k)}$ is a learnable parameter, updated via gradient descent along with the MLP weights
GIN-0: $\epsilon^{(k)}$ is fixed to 0 at all layers, so the update simplifies to $h_v^{(k)} = \text{MLP}^{(k)}\left(h_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)}\right)$

GIN-0 is "slightly less powerful" in theory — the paper notes "there exist certain (somewhat contrived) graphs that GIN- $\epsilon$ can distinguish but GIN-0 cannot" — because setting $\epsilon = 0$ loses the guarantee of injectivity for all $(c, X)$ pairs (the irrational $\epsilon$ proof in Corollary 6 requires $\epsilon \neq 0$ ). However, GIN-0 empirically performs as well or better than GIN- $\epsilon$ , which the paper attributes to simplicity and better generalization. This is an interesting case where theoretical maximum power doesn't translate to better test performance, likely because the "contrived" cases requiring $\epsilon \neq 0$ don't appear in real datasets, and the extra parameter adds optimization noise.

The role of the COMBINE step: In the general GNN formulation (Equation 2.1), the AGGREGATE and COMBINE are separate operations — AGGREGATE processes neighbors, COMBINE merges the result with the node's own feature. GIN integrates both into a single operation: the self-feature appears as an additional term in the sum, weighted by $(1 + \epsilon)$ . This is mathematically equivalent to COMBINE via summation, but means the "aggregation" and "combination" are not architecturally separated. The paper frames this as a consequence of Corollary 6's unified treatment of $(c, X)$ pairs.

GIN graph-level readout (Equation 4.2):

$h_G = \text{CONCAT}\left(\text{READOUT}\left(\{h_v^{(k)} \mid v \in G\}\right) \mid k = 0, 1, \ldots, K\right)$

Variable definitions:

$h_G$ is the final graph-level embedding
$K$ is the total number of GIN layers
$\{h_v^{(k)} \mid v \in G\}$ is the multiset of all node features at layer $k$
$\text{READOUT}$ is a permutation-invariant function (specifically, summation for the theoretical GIN)
$\text{CONCAT}$ concatenates the READOUT outputs from all layers into a single vector

What this computes, operationally: For each layer $k = 0, 1, \ldots, K$ :

Collect all node feature vectors from that layer into a multiset
Apply READOUT to produce a single vector summarizing that layer's node representations
Concatenate all these layer-wise summary vectors to form the final graph embedding

Why readout from all layers, not just the final one: This design is motivated by the observation that "node representations, corresponding to subtree structures, get more refined and global as the number of iterations increases." Layer 0 captures individual node features (subtree height 0). Layer 1 captures immediate neighborhoods (subtree height 1). Layer $k$ captures $k$ -hop neighborhoods (subtree height $k$ ). Earlier layers may contain information that is "washed out" or abstracted away in later layers — for instance, layer 1 might preserve fine-grained local structural patterns that layer 5 has aggregated into a coarser representation. By concatenating across all layers, GIN gives the final classifier access to structural information at all scales simultaneously. This is architecturally similar to Jumping Knowledge Networks (Xu et al., 2018), which the paper explicitly cites.

Why summation as READOUT satisfies injectivity (condition b of Theorem 3): Theorem 3 requires the graph-level readout to be injective over multisets of node features. Sum readout achieves this for the same reason as Lemma 5: with a suitable transformation (which the MLP in the final layer provides), the sum of transformed node features is unique for each distinct multiset. The paper notes: "we do not need an extra MLP before summation for the same reason as in Eq. 4.1" — the MLP in the final GIN layer already provides the necessary transformation. Mean readout, by contrast, would only be injective up to distributional equivalence, potentially collapsing graphs with different numbers of nodes but similar structural compositions.

Why the readout uses mean on social datasets in experiments: Despite the theoretical argument for sum readout, the paper's experiments use mean readout on social network datasets "due to better test performance." This is an empirical compromise: on datasets with widely varying graph sizes (REDDIT graphs range from tens to thousands of nodes), sum readout produces embeddings whose magnitude scales with graph size, which can cause optimization difficulties. Mean readout normalizes for graph size, producing more stable representations at the cost of some theoretical expressiveness. This tradeoff highlights that while injectivity provides maximal discriminative power, it doesn't guarantee optimal generalization — a theme the paper returns to in discussing the WL kernel vs. GNN comparison.

Initialization and the first layer: The paper notes a special case: "In the first iteration, we do not need MLPs before summation if input features are one-hot encodings as their summation alone is injective." For input features that are categorical (one-hot or multi-hot), summing directly gives count vectors — the $i$ -th coordinate equals the number of neighbors (including self) with feature $i$ . This is already injective over multisets without any learned transformation, so the first layer's MLP could theoretically be omitted. In practice, the paper's implementation uses MLPs at all layers for uniformity.

Computational complexity and parameter count: GIN's computational cost is similar to other sum-aggregation GNNs. The key operations per layer are: (1) message passing: each node sums its neighbors' features, costing $\mathcal{O}(|E| d)$ where $|E|$ is the number of edges and $d$ is the feature dimension; (2) MLP application: each node's summed representation passes through an MLP, costing $\mathcal{O}(|V| d^2)$ for a 2-layer MLP with hidden dimension $d$ . This is identical in asymptotic cost to GCN (which uses mean) and GraphSAGE (which uses max or mean), with the only difference being the coefficients (mean divides by degree; sum does not).

Summary of design decisions and their justifications:

Sum aggregation over mean or max: Sum is provably injective over multisets (Lemma 5), while mean only captures distributions (Corollary 8) and max only captures sets (Corollary 9). This directly satisfies condition (a) of Theorem 3.
MLP after sum rather than 1-layer perceptron: 1-layer perceptrons cannot be universal multiset functions (Lemma 7); MLPs can, by the universal approximation theorem. This enables the network to learn the injective transformations $f$ and $\phi$ needed for WL-equivalent power.
Weighted self-loop $(1 + \epsilon)$ : This instantiates Corollary 6 for injectivity over $(\text{center}, \text{neighborhood})$ pairs. The $\epsilon$ term distinguishes the center node's contribution from neighbor contributions, preventing ambiguous cases where different $(\text{center}, \text{neighborhood})$ pairs collapse to the same sum.
Readout across all layers: Concatenating readout outputs from all layers preserves structural information at multiple scales, enabling the classifier to use both fine-grained local patterns and coarse global patterns. This addresses the "over-smoothing" tendency of deep GNNs where node representations converge to indistinguishable values.
Readout as sum (theoretically) or mean (empirically): Sum readout satisfies the injectivity condition (b) of Theorem 3. Mean readout may generalize better when graph sizes vary widely, trading some theoretical expressiveness for practical stability.

4. Key Insights and Innovations

Innovation 1: Expressiveness as the Central Diagnostic for GNN Design — Not Just Another Architecture

Prior to this paper, the GNN literature evaluated architectures almost exclusively through the lens of benchmark performance: a new aggregation function or pooling scheme was proposed, tested on Cora/Citeseer/PubMed or molecular property prediction, and justified if it achieved state-of-the-art accuracy. This empirical trial-and-error approach produced dozens of architectures — GCN, GraphSAGE, GAT, ChebNet, MoNet, and many others — but left the field without answers to basic questions: why does one aggregator outperform another? When is a model fundamentally incapable of solving a task, versus simply needing better hyperparameters? What is the theoretical ceiling for any message-passing GNN?

The paper's first and most fundamental innovation is reframing GNN evaluation from an empirical question ("how well does it perform?") to a representational one ("what graph structures can it distinguish?"). This reframing is not incremental — it changes what counts as evidence about a GNN's quality. The key diagnostic insight is that training set underfitting is a direct, observable consequence of insufficient expressive power. If a GNN cannot distinguish two graphs that the training data labels differently, it will necessarily underfit — and no amount of regularization, learning rate tuning, or architecture tweaks within the same aggregation class will fix this. This transforms model selection from "try several and pick the best validation accuracy" to "first verify that your model class can even represent the distinctions your data requires."

What makes this intellectual move distinctive is that it provides a unified explanation for previously puzzling empirical observations:

Why GCN (mean-pooling) works well on citation networks but fails catastrophically on unlabeled social networks? Because node features in citation networks are rich bag-of-words vectors that rarely repeat, so mean-pooling loses little information, while unlabeled graphs have identical node features everywhere, and mean-pooling collapses all structural information.
Why GraphSAGE (max-pooling) is effective for node classification but underperforms on graph classification? Because max-pooling identifies which features are present in a neighborhood (sufficient for many node-level tasks) but cannot count multiplicities (necessary for distinguishing many graph-level structural patterns).
Why some GNNs can achieve near-perfect training accuracy on certain datasets while others plateau far below 100%? Because the plateau represents the representational ceiling of that aggregation class, not an optimization failure.

The paper makes this diagnostic framework concrete through Figure 4 and Table 1. Figure 4 plots training curves: GINs (sum + MLP) nearly perfectly fit every dataset, while mean-pooling and max-pooling variants severely underfit on social network benchmarks. Table 1 translates this to test accuracy: the expressiveness ranking perfectly predicts relative performance, with GIN-0 achieving 92.4% on REDDIT-BINARY versus 50.0% (random guessing) for mean-pooling variants. This is not a small refinement — it is a fundamentally new way of thinking about GNN failures that the field had no language for before this paper.

This reframing is analogous to what the VC dimension and Rademacher complexity did for classical machine learning: it provides a theoretical vocabulary for distinguishing between can't learn (representational limitation) and didn't learn (optimization or data issue). The WL test serves as the analog of VC dimension here — an upper bound on what the model class can express — and the WL subtree kernel serves as the "optimal" but non-learned baseline that shows what perfect expressiveness achieves without learned similarity.

Innovation 2: Injectivity as the Unifying Principle — Why Sum Works and Mean/Max Don't

Before this paper, the choice of aggregation function in GNNs was treated as an architectural hyperparameter — something to be tuned empirically. Mean-pooling (GCN), max-pooling (GraphSAGE), sum-pooling, attention-weighted averaging (GAT), and LSTM-based pooling were all presented as equally valid design choices, with their relative merits justified by analogy (mean is like spectral convolution, max is like selecting the most important neighbor) or empirical performance on specific tasks. No one had asked: what mathematical property distinguishes these aggregators in terms of what they can represent?

The paper's second major innovation is identifying injectivity over multisets as the property that determines an aggregator's representational power, and providing a complete characterization of what each common aggregator preserves and loses. This is a conceptual contribution, not an architectural one: it doesn't propose a new aggregator, but rather explains the hierarchy that was already implicit in the empirical results.

The three Corollaries (8, 9, and Lemma 5) form a crisp taxonomy:

Sum is capable of being injective — with a suitable element-wise transformation (learned by an MLP), it can produce a unique output for each distinct multiset, preserving both the identity of elements and their exact multiplicities.
Mean captures only the distribution (relative proportions) of element types. It collapses multisets that differ only in absolute scale, preserving the probability mass function but not the counts.
Max captures only the underlying set (distinct elements). It collapses all multiplicity information entirely, preserving only the answer to "does feature X appear anywhere in the neighborhood?"

The significance of this characterization goes beyond just ranking aggregators by power. It provides a decision framework: given a task, you can reason about which aggregator is appropriate based on what information the task requires.

If your task depends on exact structural counts (e.g., molecular property prediction where the number of hydrogen atoms in a functional group matters), you need sum or an equivalent injective aggregator — mean and max will systematically fail.
If your task depends only on the distribution of neighbor types (e.g., classifying a node's role in a social network based on the mix of communities its neighbors belong to), mean may suffice and may even generalize better due to its built-in normalization.
If your task depends only on the presence or absence of certain features (e.g., detecting whether a user has any connection to a flagged entity), max-pooling is appropriate and may be more robust to noise than sum.

This is a fundamental shift from "try all aggregators and see what works" to "analyze your task's information requirements and choose the aggregator accordingly." It transforms aggregation function selection from an empirical hyperparameter into an architectural prior that encodes assumptions about what information matters.

The intellectual lineage here is important. Zaheer et al. (2017) had shown that sum is a universal function over sets (where elements are unique), and that mean and max are not. But the extension to multisets (where elements can repeat) is non-trivial and more directly relevant to GNNs, because node features in graphs frequently repeat — identical atoms in a molecule, users with the same demographic attributes, documents with the same topic distribution. The paper's key observation is that popular architectures like GCN and GraphSAGE were implicitly using set functions where multiset functions were needed, and this mismatch explains their failures on tasks where multiplicities matter.

The paper also identifies a subtlety that prior work missed: even within the "sum" family, not all implementations achieve injectivity. Lemma 7 proves that a single linear layer followed by ReLU (a common design in early GNNs) is not sufficient for injectivity over multisets, because the ReLU homogeneity property can cause distinct multisets with equal sums to collapse. This explains why simply using sum aggregation isn't enough — you also need sufficient nonlinear representational capacity (an MLP) to learn the injective transformation f. This is a non-obvious finding that would not have been discovered without the injectivity framework.

Innovation 3: The GNN-WL Connection as Both Ceiling and Construction — Bounding and Achieving Maximum Power

The connection between GNNs and the Weisfeiler-Lehman test had been noted informally before this paper. Researchers observed that GNN message-passing resembles WL label refinement: both iteratively update node representations based on neighborhood information. The WL subtree kernel (Shervashidze et al., 2011) had been proposed as a graph similarity measure, and some GNN papers mentioned the analogy in passing.

The paper's third innovation is formalizing this connection into a rigorous theorem that simultaneously provides an upper bound (Lemma 2: GNNs are at most as powerful as WL) and a constructive recipe for achieving that bound (Theorem 3: injective aggregation + injective readout + sufficient depth = WL-equivalent power). This transforms the WL test from an interesting analogy into a theoretical tool that can precisely characterize the representational capacity of any aggregation-based GNN.

What makes this intellectually distinctive is the dual nature of the result:

As a ceiling: Lemma 2 tells you what you cannot do. If the WL test fails to distinguish two graphs (e.g., any two k-regular graphs with identical node features), then no GNN — regardless of depth, width, or training procedure — can distinguish them either. This is a hard impossibility result that applies to the entire class of message-passing architectures. It tells you when to stop trying to improve your GNN and instead recognize that you need a fundamentally different approach (e.g., higher-order structures, subgraph counting, positional encodings).
As a construction: Theorem 3 tells you how to achieve the maximum possible power within the message-passing paradigm. It provides specific, verifiable conditions (injective f, injective ϕ, injective readout) that, if satisfied, guarantee WL-equivalent discriminative capacity. This is prescriptive — it tells architecture designers exactly what properties their layers must have.

This dual nature distinguishes the paper from prior theoretical work on GNNs. Scarselli et al. (2009a) proved that a specific GNN architecture could approximate measurable functions, but provided no characterization of which functions or which graph properties. Lei et al. (2017) connected their architecture to graph kernels but didn't establish the WL test as a representational bound for the entire GNN class. The paper's theorems are simultaneously more general (applying to any aggregation-based GNN) and more precise (providing necessary and sufficient conditions for a specific, well-studied level of expressiveness).

The practical significance of this innovation is that it redefines what "state-of-the-art" means for GNN architectures. Before this paper, a new GNN was considered state-of-the-art if it achieved higher test accuracy than previous architectures on standard benchmarks. After this paper, a new GNN must also be evaluated in terms of its representational capacity relative to the WL bound. Does it achieve WL-equivalent power? If not, what expressiveness does it sacrifice, and is that sacrifice justified by other benefits (efficiency, generalization, interpretability)? This shifts the evaluation criteria from purely empirical to theoretically-informed, which is a more principled and sustainable basis for architectural innovation.

The paper also demonstrates, through GIN, that WL-equivalent architectures are practically realizable, not just theoretical curiosities. GIN is simple — Equation 4.1 is arguably simpler than GCN's spectral convolution or GraphSAGE's concatenation-based combine — yet it provably achieves maximum power. This suggests that the field's prior complexity (attention mechanisms, gating, LSTM-based aggregation) may have been compensating for representational deficiencies rather than providing fundamental benefits. Simpler architectures that satisfy the injectivity conditions may be both more powerful and easier to train.

Innovation 4: Learned Continuous Embeddings as a Generalization of Discrete WL Labels — Why GNNs Can Outperform the WL Kernel

The WL subtree kernel computes graph similarity by counting exact matches of WL node labels at different iterations — essentially, it builds a histogram of subtree patterns using discrete, one-hot labels. The WL test itself uses an injective hash function to assign unique labels to distinct multisets, guaranteeing that structurally different neighborhoods always receive different labels. This provides maximum discriminative power, but at a cost: the labels are categorical and semantically opaque — {a, b, a} and {a, b, c} receive different labels, but there is no notion that they might be similar (by sharing the {a, b} core structure). Two graphs that share many subtree patterns but differ in a few will have completely different label histograms, offering no way to capture their partial structural similarity.

The paper's fourth innovation is recognizing and exploiting the fact that GNNs' learned continuous embeddings can transcend the limitations of discrete WL labels by capturing structural similarity in addition to structural identity. This is not a theorem but a conceptual insight that emerges from comparing GIN's performance against the WL subtree kernel in experiments. The WL kernel has WL-equivalent (i.e., maximum) discriminative power by construction — it is the WL test turned into a kernel. Yet GNNs, even those with provably WL-equivalent power, often outperform the WL kernel on test accuracy (Table 1: GIN-0 achieves 92.4% on REDDIT-BINARY vs. 81.0% for the WL subtree kernel; similar patterns appear on IMDB-BINARY, PROTEINS, and PTC).

Why does this happen? The paper's explanation is that continuous embeddings learn a notion of structural similarity that discrete labels cannot represent. In the WL test, two subtrees that differ in any way — even by a single leaf node — receive completely different hash values. In a GNN, the MLP can map similar but non-identical subtree patterns to nearby points in the embedding space, capturing the intuition that "a node with neighbors {A, A, B}" is structurally closer to "a node with neighbors {A, B, B}" than to "a node with neighbors {C, D, E}." This similarity signal is especially valuable when subtree patterns are sparse — i.e., when specific subtree configurations appear rarely in the training data, making it impossible to learn their association with labels from exact matches alone. The continuous embedding allows the model to generalize from similar-but-not-identical patterns it has seen before.

This insight reframes the relationship between expressiveness and generalization. Expressive power (WL-equivalence) is necessary to avoid underfitting — if your model can't even distinguish training graphs, it certainly can't generalize. But expressiveness alone is not sufficient for good generalization — the WL kernel has maximum expressiveness yet generalizes worse than GNNs. The missing ingredient is learned similarity: the ability to map structurally related graphs to nearby embeddings, which requires continuous representations and gradient-based optimization, not discrete hashing.

This has implications beyond the paper's specific results. It suggests that the ideal GNN should be:

Maximally expressive (WL-equivalent) to avoid losing discriminative information
Continuous and differentiable to learn similarity structure from data
Trained end-to-end so that the similarity metric is optimized for the specific task, rather than using a fixed, task-agnostic kernel

The WL subtree kernel satisfies (1) but not (2) or (3). Less powerful GNNs may partially satisfy (2) and (3) but fail at (1) — hence the underfitting observed in Figure 4. GIN satisfies all three, and its empirical success validates this tripartite framework.

This is a fundamental insight, not an incremental one, because it resolves the apparent paradox that a theoretically "maximal" model (the WL kernel) can be empirically surpassed by a model with the same theoretical ceiling (GIN). The resolution — that continuous embeddings capture similarity while discrete labels capture only identity — had implications for the broader representation learning literature beyond graphs.

5. Experimental Analysis

Evaluation Methodology

Dataset. The paper evaluates on 9 graph classification benchmarks: 4 bioinformatics datasets (MUTAG with 188 graphs and 2 classes, PTC with 344 graphs and 2 classes, NCI1 with 4110 graphs and 2 classes, PROTEINS with 1113 graphs and 2 classes) and 5 social network datasets (COLLAB with 5000 graphs and 3 classes, IMDB-BINARY with 1000 graphs and 2 classes, IMDB-MULTI with 1500 graphs and 3 classes, REDDIT-BINARY with 2000 graphs and 2 classes, REDDIT-MULTI5K with 5000 graphs and 5 classes). The datasets originate from Yanardag & Vishwanathan (2015). For bioinformatics graphs, nodes have categorical input features from the domain (atom types, secondary structure elements, etc.). For social network graphs, nodes have no inherent features; the authors create features as follows: for REDDIT datasets, all node feature vectors are set to the same scalar (making features entirely uninformative, forcing models to rely purely on graph structure); for other social graphs (IMDB-BINARY, IMDB-MULTI, COLLAB), one-hot encodings of node degrees are used as input features.
Base model(s). The paper evaluates GIN in two variants — GIN-0 (where ε in Equation 4.1 is fixed to 0) and GIN-ε (where ε is learned via gradient descent) — along with less powerful GNN variants constructed by modifying GIN's aggregation scheme. The less powerful variants replace the sum aggregator with mean or max-pooling, or replace the MLP with a 1-layer perceptron (linear mapping followed by ReLU). The naming convention follows the pattern <aggregator>–<perceptron>: SUM–MLP corresponds to GIN, MEAN–MLP and MEAN–1-LAYER correspond to mean-pooling variants (with MEAN–1-LAYER approximating GCN up to minor architecture differences), and MAX–MLP and MAX–1-LAYER correspond to max-pooling variants (with MAX–1-LAYER approximating GraphSAGE). All GNN variants use 5 layers (including the input layer), all MLPs have 2 layers, and batch normalization is applied on every hidden layer.
Metrics. The primary metric is classification accuracy on the test set, reported as the mean and standard deviation across 10-fold cross-validation. The paper additionally reports training set accuracy to directly measure representational capacity — models with higher expressive power should achieve higher training accuracy, since underfitting on the training set indicates a model cannot represent the distinctions present in the data. Training accuracy is reported with fixed hyperparameters (5 GNN layers, 64 hidden units, batch size 128, dropout 0.5) to enable clean comparison of representational power independent of hyperparameter tuning. For the WL subtree kernel baseline, the feature vector consists of counts of node labels at each WL iteration, and a C-SVM classifier is trained on these features.
Baselines. The paper compares against: (1) the WL subtree kernel (Shervashidze et al., 2011) with C-SVM classifier, tuning the SVM regularization parameter C and the number of WL iterations ∈ {1, 2, …, 6}; (2) Diffusion-convolutional neural networks (DCNN) (Atwood & Towsley, 2016); (3) PATCHY-SAN (Niepert et al., 2016); (4) Deep Graph CNN (DGCNN) (Zhang et al., 2018); and (5) Anonymous Walk Embeddings (AWL) (Ivanov & Burnaev, 2018). For the deep learning baselines (DCNN, PATCHY-SAN, DGCNN) and AWL, the paper reports accuracies from the original papers rather than re-running experiments.
Generation budget / compute accounting. All GNN variants use the same number of layers (5), hidden dimensions (16 or 32 for bioinformatics, 64 for social graphs), and training protocol, making the comparison fair in terms of model capacity and optimization budget. The key differences are only in the aggregation function and perceptron depth, ensuring that performance gaps can be attributed to representational power rather than model size or training compute. The paper does not report wall-clock time or FLOP counts for individual methods.
Cross-validation / statistical protocol. Following Yanardag & Vishwanathan (2015) and Niepert et al. (2016), the paper uses 10-fold cross-validation with LIB-SVM (Chang & Lin, 2011). For each dataset, hyperparameters are tuned: number of hidden units ∈ {16, 32} for bioinformatics and 64 for social graphs, batch size ∈ {32, 128}, dropout ratio ∈ {0, 0.5}, and number of epochs (a single epoch with the best cross-validation accuracy averaged over 10 folds is selected). The paper notes that due to small dataset sizes (e.g., MUTAG has only 188 graphs, meaning the validation fold contains only ~18 graphs), using a separate validation set for hyperparameter selection would be "extremely unstable," motivating the cross-validation protocol. For the training accuracy comparison (Figure 4), all hyperparameters are fixed across datasets to isolate the effect of architecture on representational capacity. The Adam optimizer is used with initial learning rate 0.01, decayed by 0.5 every 50 epochs.

Main Quantitative Results

Training Set Performance: Expressiveness Directly Predicts Fitting Capacity

The paper's central empirical claim about expressiveness is validated through training set accuracy, not test accuracy. Figure 4 shows training curves for all GNN variants and the WL subtree kernel across 9 datasets with fixed hyperparameters. The headline finding is stark: GIN-ε and GIN-0 (SUM–MLP) are able to almost perfectly fit all training sets, while less powerful GNN variants using mean-pooling, max-pooling, or 1-layer perceptrons severely underfit on many datasets.

The training accuracy pattern directly tracks the theoretical expressiveness ranking from Section 5:

SUM–MLP (GIN-0 and GIN-ε) achieves the highest training accuracy across all datasets, consistent with its WL-equivalent theoretical power. The paper states: "both the theoretically most powerful GNN, i.e., GIN-ε and GIN-0, are able to almost perfectly fit all the training sets." Notably, GIN-0 and GIN-ε are indistinguishable in training performance — "explicit learning of ε in GIN-ε yields no gain in fitting training data compared to fixing ε to 0 as in GIN-0."
SUM–1-LAYER (sum aggregation with 1-layer perceptron instead of MLP) shows degraded training accuracy relative to SUM–MLP on most datasets, consistent with Lemma 7's proof that 1-layer perceptrons cannot represent injective multiset functions. The degradation is particularly visible on social network datasets (IMDB-BINARY, REDDIT-BINARY, REDDIT-MULTI5K), where the structural distinctions are purely topological and thus require the full representational capacity of MLPs.
MEAN–MLP and MEAN–1-LAYER (mean-pooling variants) perform dramatically worse on the REDDIT datasets — where all nodes have identical scalar features — achieving only ~50% training accuracy on REDDIT-BINARY (binary classification, so this is random guessing). This is exactly what Corollary 8 predicts: mean-pooling captures the distribution of neighbor features, and when all nodes have identical features, every neighborhood has the same distribution (100% of a single feature value), so all nodes receive identical representations regardless of graph structure.
MAX–MLP and MAX–1-LAYER (max-pooling variants) show intermediate underfitting, consistent with Corollary 9: max-pooling captures only the underlying set of features, losing all multiplicity information. On datasets where exact structural counts matter, this loss is fatal.

The paper also notes that training accuracies of the GNNs never exceed those of the WL subtree kernel, which is expected since Lemma 2 proves the WL test provides an upper bound on GNN discriminative power. On IMDB-BINARY, none of the GNNs can perfectly fit the training set, and they achieve "at most the same training accuracy as the WL kernel." This directly validates the theoretical ceiling: the WL test is not just an analogy but a genuine representational bound.

Test Set Performance: GINs Achieve State-of-the-Art

Table 1 reports test set classification accuracies across all 9 datasets for GIN variants, less powerful GNN variants, and baseline methods. The key findings:

GINs outperform (or match) all less powerful GNN variants on every dataset. GIN-0 achieves the highest test accuracy among GNN variants on IMDB-BINARY (75.1 ± 5.1%), REDDIT-BINARY (92.4 ± 2.5%), REDDIT-MULTI5K (57.5 ± 1.5%), COLLAB (80.2 ± 1.9%), and PTC (64.6 ± 7.0%). On the remaining datasets, GIN-0 is comparable to the best GNN variant, with paired t-tests at significance level 10% not distinguishing GIN-0 from the top performer. The paper's convention is to boldface both the top GNN and any GNN not statistically distinguishable from it.

The expressiveness-test performance link is most pronounced where structure dominates. On the REDDIT datasets, where node features are uninformative (all nodes share the same scalar), GINs achieve 92.4 ± 2.5% on REDDIT-BINARY and 57.5 ± 1.5% on REDDIT-MULTI5K, while MEAN–MLP and MEAN–1-LAYER achieve exactly 50.0 ± 0.0% and 20.0 ± 0.0% respectively — random guessing for binary and 5-class classification. This is the cleanest demonstration of the theory: when features are absent, only sum aggregation preserves structural information; mean and max collapse everything to identical representations. The paper corroborates this with an additional experiment: "even if node degrees are provided as input features, mean-based GNNs perform much worse than sum-based GNNs (the accuracy of the GNN with mean–MLP aggregation is 71.2 ± 4.6% on REDDIT-BINARY and 41.3 ± 2.1% on REDDIT-MULTI5K)." This shows that even with informative features, mean aggregation loses critical structural information.

GIN-0 slightly but consistently outperforms GIN-ε. Across all 9 datasets, GIN-0 achieves test accuracy equal to or higher than GIN-ε: 75.1 vs. 74.3 on IMDB-BINARY, 52.3 vs. 52.1 on IMDB-MULTI, 92.4 vs. 92.2 on REDDIT-BINARY, 57.5 vs. 57.0 on REDDIT-MULTI5K, 80.2 vs. 80.1 on COLLAB, 89.4 vs. 89.0 on MUTAG, 76.2 vs. 75.9 on PROTEINS, 64.6 vs. 63.7 on PTC, and 82.7 vs. 82.7 on NCI1. The paper explains: "Since both models fit training data equally well, the better generalization of GIN-0 may be explained by its simplicity compared to GIN-ε." This is an interesting case where the theoretically more powerful model (GIN-ε, which can distinguish certain contrived cases that GIN-0 cannot) does not translate to better test performance, likely because those cases don't appear in real datasets and the extra learnable parameter adds optimization variance.

GINs achieve state-of-the-art performance against published baselines. On REDDIT-BINARY, GIN-0 achieves 92.4 ± 2.5% compared to 87.9 ± 2.5% for AWL, 86.3 ± 1.6% for PATCHY-SAN, and 81.0 ± 3.1% for the WL subtree kernel. On REDDIT-MULTI5K, GIN-0 achieves 57.5 ± 1.5% compared to 54.7 ± 2.9% for AWL, 52.5 ± 2.1% for WL subtree, and 49.1 ± 0.7% for PATCHY-SAN. On COLLAB, GIN-0 achieves 80.2 ± 1.9% compared to 78.9 ± 1.9% for WL subtree and 73.9 ± 1.9% for AWL. On bioinformatics datasets, the gains are smaller but consistent: GIN-0 achieves 76.2 ± 2.8% on PROTEINS (vs. 75.9 ± 2.8% for PATCHY-SAN and 75.0 ± 3.1% for WL subtree) and 82.7 ± 1.7% on NCI1 (vs. 86.0 ± 1.8% for WL subtree, which is the only dataset where a baseline significantly outperforms all GNNs).

The WL subtree kernel sometimes underperforms GNNs despite having maximum expressiveness. On REDDIT-BINARY, the WL subtree kernel achieves 81.0 ± 3.1% while GIN-0 achieves 92.4 ± 2.5%. On IMDB-BINARY, WL subtree achieves 73.8 ± 3.9% vs. GIN-0's 75.1 ± 5.1%. On PROTEINS, WL subtree achieves 75.0 ± 3.1% vs. GIN-0's 76.2 ± 2.8%. The paper attributes this gap to GNNs' ability to learn continuous embeddings that capture structural similarity, not just structural identity: "the WL kernel is not able to learn how to combine node features, which might be quite informative for a given prediction task." This is a nuanced point — the WL kernel has perfect discriminative power but no notion of similarity, while GNNs trade a small amount of discriminative capacity (they are at most as powerful as WL, and may fall short in practice) for the ability to generalize across similar graph structures.

The 1-layer perceptron variants (GCN and GraphSAGE approximations) are competitive on some datasets but not others. MEAN–1-LAYER (GCN-like) achieves 74.0 ± 3.4% on IMDB-BINARY (vs. 75.1 for GIN-0), 76.0 ± 3.2% on PROTEINS (vs. 76.2 for GIN-0), and a competitive 80.2 ± 2.0% on NCI1. But it fails catastrophically on REDDIT datasets (50.0% and 20.0%). The paper explains this pattern via the theory: on datasets where node features are rich and informative (bioinformatics graphs have categorical atom/SSE features), the distribution captured by mean-pooling may carry sufficient signal for the task, so the expressiveness gap doesn't manifest as a performance gap. On datasets where structure is the only signal, the expressiveness gap is fatal.

MAX-based variants (GraphSAGE-like) show similar patterns but with interesting differences. MAX–MLP and MAX–1-LAYER are competitive on MUTAG (84.0 ± 6.1% and 85.1 ± 7.6% vs. 89.4 for GIN-0), PROTEINS (76.0 ± 3.2% and 75.9 ± 3.2% vs. 76.2 for GIN-0), and PTC (64.6 ± 10.2% and 63.9 ± 7.7% vs. 64.6 for GIN-0). These datasets have diverse categorical features where identifying which atom or structural element types appear in a neighborhood may be more important than counting exact multiplicities — aligning with max-pooling's set-capture property (Corollary 9). On REDDIT-BINARY, max-pooling was not tested due to GPU memory constraints, which the paper notes in a footnote.

The Diagnostic Power of Training Accuracy: Figure 4 as a Litmus Test

Figure 4 deserves special attention because it operationalizes the paper's theoretical framework into a practical diagnostic. The figure shows training curves (accuracy vs. epoch) for all GNN variants side-by-side on each dataset. The visual patterns are consistent:

On bioinformatics datasets (MUTAG, PROTEINS, PTC, NCI1), all variants achieve relatively high training accuracy, with SUM–MLP at or near 100% and mean/max variants slightly lower. The expressiveness gap exists but is small because the categorical node features provide strong signals that even distribution-based or set-based aggregation can partially capture. For instance, on MUTAG (7 discrete atom types), knowing the distribution of atom types in a neighborhood captures substantial structural information.
On social network datasets (IMDB-BINARY, IMDB-MULTI, COLLAB), the gap widens. SUM–MLP achieves near-perfect training accuracy, while mean and max variants plateau at lower values. On IMDB-BINARY, SUM–1-LAYER reaches approximately 75% training accuracy while MEAN–MLP reaches only ~55% — a 20 percentage point gap attributable purely to aggregation function choice.
On REDDIT datasets, the gap is categorical. SUM–MLP achieves near-100% training accuracy. MEAN–MLP and MEAN–1-LAYER achieve exactly 50% (binary) and 20% (5-class) — random guessing — and their curves are flat, indicating they never learn anything beyond the initial random initialization. This is the "smoking gun" for the theory: when all nodes have identical features, mean-pooling collapses all graphs to identical representations, so the model has zero discriminative information and cannot fit the training data at all.

The paper emphasizes that this diagnostic is actionable: "the training accuracy patterns align with our ranking by the models' representational power." If a practitioner observes that their GNN underfits the training set, and they are using mean or max-pooling, the theory suggests that switching to sum aggregation with MLPs should be the first intervention — before tuning learning rates, adding layers, or collecting more data.

Ablation Studies and Robustness Checks

The paper's ablation structure is somewhat unusual for a theory paper: rather than ablating components of GIN specifically, the "ablations" are the comparisons between different aggregation functions and perceptron depths that form the core experimental design. I'll organize this section by the components tested.

Sum vs. Mean vs. Max aggregation (Table 1, Figure 4): The central ablation compares GIN (SUM–MLP) against otherwise identical architectures that replace sum with mean (MEAN–MLP) or max-pooling (MAX–MLP). The finding is that sum consistently outperforms mean and max on training accuracy, with test accuracy following the same ranking. The gap is largest on datasets where structural information is paramount (REDDIT datasets: ~42 percentage points between sum and mean on REDDIT-BINARY test accuracy, 92.4% vs. 50.0%) and smallest on datasets with rich categorical features where distributional or set-level information suffices (PROTEINS: 76.2% vs. 75.5% vs. 76.0%). This ablation directly validates the theoretical hierarchy from Section 5 (Figure 2): sum > mean > max in representational power.
MLP vs. 1-layer perceptron (Table 1, Figure 4): The second axis of ablation replaces the 2-layer MLP in the GIN update with a 1-layer perceptron (linear map + ReLU). This tests Lemma 7's claim that 1-layer perceptrons cannot represent injective multiset functions. The finding is that SUM–1-LAYER consistently underperforms SUM–MLP (GIN) on both training and test accuracy, across almost all datasets. For example, on REDDIT-BINARY: GIN-0 achieves 92.4 ± 2.5% while SUM–1-LAYER achieves 90.0 ± 2.7%; on REDDIT-MULTI5K: 57.5 ± 1.5% vs. 55.1 ± 1.6%; on IMDB-MULTI: 52.3 ± 2.8% vs. 52.2 ± 2.4% (here the difference is negligible). The gap is smaller than the sum-vs-mean gap, indicating that sum aggregation with even limited nonlinearity captures substantial structural information, but the consistent direction of the gap (SUM–MLP ≥ SUM–1-LAYER on 8 of 9 datasets for test accuracy) supports the theoretical claim.
Learnable ε vs. fixed ε = 0 (Table 1, Figure 4): Comparing GIN-ε against GIN-0 tests whether the learnable epsilon parameter in Equation 4.1 provides practical benefits. The finding is a negative result: GIN-ε never outperforms GIN-0 on test accuracy across all 9 datasets, and in most cases performs slightly worse (e.g., IMDB-BINARY: 74.3 ± 5.1% vs. 75.1 ± 5.1%; MUTAG: 89.0 ± 6.0% vs. 89.4 ± 5.6%). On training accuracy, the two are indistinguishable. The paper attributes GIN-0's advantage to simplicity: the learnable ε adds a parameter that may increase optimization difficulty without providing representational benefits on real-world graphs (the "contrived" cases where ε ≠ 0 is needed for injectivity, mentioned in Section 4.1, apparently don't occur in these benchmarks). This is a genuinely non-obvious result — the theoretically more expressive model generalizes worse, which is a useful caution against assuming that maximizing theoretical expressiveness always improves practical performance.
Sum vs. Mean readout (Table 1, Section 7.1): The paper uses sum readout for bioinformatics datasets and mean readout for social datasets, noting this choice is "due to better test performance." This is an implicit ablation: sum readout satisfies the injectivity condition (b) of Theorem 3, but mean readout empirically generalizes better when graph sizes vary widely (REDDIT graphs range from tens to thousands of nodes). This is not explicitly reported as an ablation with controlled comparisons, but the paper's choice to use different readout functions on different dataset families implicitly acknowledges that the theoretical optimum (sum readout) is not always the empirical optimum.
Using node degrees as features for REDDIT datasets (Section 7.1, stated in text): The paper reports an additional check: providing node degrees as input features to the REDDIT datasets. The finding is that "even if node degrees are provided as input features, mean-based GNNs perform much worse than sum-based GNNs (the accuracy of the GNN with mean–MLP aggregation is 71.2 ± 4.6% on REDDIT-BINARY and 41.3 ± 2.1% on REDDIT-MULTI5K)." This is important because node degrees partially break the symmetry that causes mean-pooling to collapse — different nodes have different degrees, so their neighborhoods have different feature distributions. Yet mean-pooling still substantially underperforms sum, because while degrees provide some structural signal, the exact counts of neighbor types (which sum preserves but mean normalizes away) carry additional discriminative information.
Interaction between aggregation and perceptron depth (Table 1, comparing MEAN–MLP vs. MEAN–1-LAYER, MAX–MLP vs. MAX–1-LAYER): Within the mean-pooling and max-pooling families, using an MLP instead of a 1-layer perceptron sometimes helps but not consistently. For mean-pooling: MEAN–MLP achieves 73.7 ± 3.7% vs. MEAN–1-LAYER's 74.0 ± 3.4% on IMDB-BINARY (1-layer is slightly better); 75.5 ± 3.4% vs. 76.0 ± 3.2% on PROTEINS; 66.6 ± 6.9% vs. 64.2 ± 4.3% on PTC (MLP is better). For max-pooling: MAX–MLP achieves 73.2 ± 5.8% vs. MAX–1-LAYER's 72.3 ± 5.3% on IMDB-BINARY; 76.0 ± 3.2% vs. 75.9 ± 3.2% on PROTEINS; 84.0 ± 6.1% vs. 85.1 ± 7.6% on MUTAG. The inconsistent pattern suggests that for less powerful aggregators that already lose information (distribution-only or set-only), increasing perceptron depth cannot recover the lost information and provides marginal benefits at best. This aligns with the theory: if the aggregation function itself is not injective, no amount of post-aggregation processing can reconstruct the lost multiplicity information.
Comparison against the WL subtree kernel (Table 1, Figure 4): The WL subtree kernel serves as a "representational upper bound" baseline — it has maximum discriminative power by construction but cannot learn similarity. The finding that GNNs sometimes outperform the WL kernel (REDDIT-BINARY: 92.4% vs. 81.0%; IMDB-BINARY: 75.1% vs. 73.8%; IMDB-MULTI: 52.3% vs. 50.9%) despite the WL kernel's theoretical advantage in discriminative power validates the paper's claim that learned continuous embeddings provide generalization benefits that compensate for any (practically small) gap from the theoretical ceiling. On NCI1, the WL kernel significantly outperforms all GNNs (86.0 ± 1.8% vs. 82.7 ± 1.7% for GIN-0), which the paper highlights with an asterisk — this is the one dataset where discriminative power alone provides an advantage that GNNs' similarity-based generalization cannot match.

Critical Assessment

Does the evidence support the claim that "GNNs are at most as powerful as the WL test"?

Supported, but only indirectly. Lemma 2 is a mathematical proof (Appendix A), not an experimental result, so the experimental section does not — and cannot — directly validate this claim. However, two empirical patterns are consistent with the bound:

Training accuracies of GNNs never exceed those of the WL subtree kernel (Figure 4). On IMDB-BINARY, "none of the models can perfectly fit the training set, and the GNNs achieve at most the same training accuracy as the WL kernel." This suggests the WL kernel's discriminative ceiling is real and constraining in practice.
No GNN variant achieves perfect training accuracy on all datasets, despite using MLPs (universal approximators), suggesting there are graph pairs in the training data that no GNN can distinguish — consistent with Lemma 2's bound.

However, the evidence is observational, not causal. The paper does not explicitly construct graph pairs that the WL test distinguishes but specific GNNs fail on, nor does it measure the WL test's actual discriminative performance on these datasets (the WL subtree kernel uses SVM classification of WL label histograms, which is a weaker measure than the WL test's own isomorphism decisions). A stronger empirical validation would involve constructing or identifying specific non-isomorphic graph pairs in the benchmark data, verifying that the WL test distinguishes them, and showing that specific GNNs (with known injectivity failures) do not.

Does the evidence support the claim that injective aggregation + injective readout = WL-equivalent power?

Supported, with the caveat that the evidence is about correlation (ranking by expressiveness) rather than direct verification of injectivity. The experiments show that:

Sum aggregation (provably capable of injectivity via Lemma 5) outperforms mean and max aggregation (provably non-injective via Corollaries 8 and 9) on training accuracy, and this ranking holds across all 9 datasets. This is consistent with the theory but doesn't prove that GIN actually achieves injectivity in practice — it only shows that architectures designed to enable injectivity perform better than architectures that provably cannot achieve it.
MLPs outperform 1-layer perceptrons (Lemma 7 proves 1-layer cannot be injective, while MLPs can approximate injective functions). Again, this is consistent with the theory but doesn't verify that the MLP actually learns an injective mapping.

The paper does not conduct experiments that would directly verify injectivity, such as measuring whether distinct multisets of neighbor features produce distinct aggregated representations in the trained GIN, or testing GIN on known WL-failure cases (pairs of regular graphs) to verify that it fails on them as predicted. The empirical validation is about the ranking of architectures (sum > mean > max; MLP > 1-layer), which is a weaker claim than the equivalence of GIN to WL.

Does the evidence support the claim that popular GNN variants cannot distinguish certain simple graph structures?

Strongly supported through the REDDIT dataset experiments. The REDDIT-BINARY and REDDIT-MULTI5K datasets, where all nodes have identical scalar features, provide a clean experimental testbed for the structural confusion predictions made in Figure 3 and Section 5.2:

MEAN–MLP and MEAN–1-LAYER achieve exactly random-guessing test accuracy (50.0% and 20.0% respectively), and their training curves in Figure 4 are flat at chance level. This is direct evidence that mean-pooling collapses all structural information when node features are uniform — exactly as predicted by the theory (Corollary 8) and illustrated in Figure 3a.
Even when node degrees are provided as features, mean-pooling variants reach only 71.2% on REDDIT-BINARY vs. 92.4% for sum-based GIN. This shows that the confusion is not merely about the absence of node features, but about mean-pooling's fundamental inability to capture exact counts — it captures the distribution of degrees in the neighborhood but not the specific multiset.
The failure is not due to optimization issues (the training doesn't get stuck — it reaches the random-guessing plateau quickly and stays there) or insufficient capacity (5 layers with 64 hidden units is sufficient for GIN to achieve near-perfect training accuracy). The failure is purely representational, which is exactly what the theory predicts.

This is the paper's strongest empirical result because it cleanly isolates the mechanism: by making node features uninformative, the experiment forces the model to rely entirely on graph structure, and the structural confusions predicted by the theory manifest as complete task failure.

Does the evidence support the claim that GIN achieves state-of-the-art performance?

Supported, with qualifications about the magnitude of improvement and the comparison scope. GIN achieves top or statistically indistinguishable performance on 8 of 9 datasets, and clearly outperforms prior GNN variants (GCN-like, GraphSAGE-like) on datasets where expressiveness matters most. However:

The gains are modest on several bioinformatics datasets. On PROTEINS, GIN-0 achieves 76.2% vs. 75.9% for PATCHY-SAN and 75.0% for WL subtree — a maximum improvement of 1.2 percentage points. On NCI1, GIN-0 (82.7%) is outperformed by the WL subtree kernel (86.0%). On MUTAG, PATCHY-SAN (92.6%) significantly outperforms GIN-0 (89.4%). The expressive power advantage translates to large test accuracy gains primarily on social network datasets where structure dominates and node features are sparse or absent. On bioinformatics datasets with rich categorical features, the expressiveness gap is largely compensated by informative node features, and the test accuracy differences are small enough that dataset-specific tuning could plausibly reverse the ranking.
The comparison is limited to graph classification on 9 specific benchmarks. The paper does not evaluate on node classification tasks (where GCN and GraphSAGE were originally developed and shown to work well) or link prediction tasks. This matters because the paper's theory suggests that mean-pooling (GCN) may be sufficient — or even preferable — for node classification when node features are rich and diverse, and the theory predicts max-pooling (GraphSAGE) may be suitable when identifying representative elements is the goal. The paper acknowledges this in Section 5.3 ("GNNs with mean aggregators are effective for node classification tasks") but doesn't experimentally verify it, leaving open the question of whether GIN's expressiveness advantage extends to the tasks where less powerful GNNs were originally successful.
The baselines (DCNN, PATCHY-SAN, DGCNN, AWL) are reported from original papers rather than re-run under the same experimental protocol (same data splits, same hyperparameter tuning budget, same evaluation procedure). This is standard practice but introduces potential confounds from differences in data preprocessing, train/test splits, or hyperparameter optimization.

Genuine weaknesses in the experimental design:

Single evaluation protocol (10-fold CV with LIB-SVM) on a single model family. All GNN variants share the same codebase, optimizer, and hyperparameter ranges, which is good for internal comparison but means the results don't demonstrate robustness to implementation choices. The paper does not report results with different random seeds, different optimizer settings, or different train/test split strategies beyond the 10-fold CV.
No statistical significance testing between GNN variants. The paper reports standard deviations and uses paired t-tests only for the "best GNN" designation (comparing GIN against the top competitor within GNN variants). There is no systematic significance testing between, say, SUM–MLP and SUM–1-LAYER, or between MEAN–MLP and MEAN–1-LAYER, on each dataset. Some of the reported gaps (e.g., GIN-0 at 75.1% vs. SUM–1-LAYER at 74.1% on IMDB-BINARY) are within overlapping standard deviations and may not be statistically significant. The consistent direction of the gaps (GIN-0 ≥ alternatives on 8 of 9 datasets) is suggestive but would be strengthened by formal hypothesis tests.
Small dataset sizes for hyperparameter tuning. As the paper acknowledges, "due to the small dataset sizes, an alternative setting, where hyper-parameter selection is done using a validation set, is extremely unstable, e.g., for MUTAG, the validation set only contains 18 data points." The cross-validation protocol mitigates this but means that the reported accuracies are from models whose hyperparameters were selected using information from the test folds (the "best epoch" is chosen based on cross-validation accuracy averaged over all 10 folds). This is not strictly out-of-sample evaluation, though it's standard practice for small graph classification benchmarks. The small validation folds also mean that hyperparameter selection has high variance, and different hyperparameter choices could potentially change the ranking between architectures on specific datasets.
Missing experiments on known WL-failure cases. The theory predicts that GIN (and all aggregation-based GNNs) will fail on regular graphs where every node has the same degree and features. The paper does not test this prediction experimentally — for example, by constructing a synthetic binary classification task on pairs of non-isomorphic regular graphs that the WL test cannot distinguish, and verifying that all GNNs achieve 50% accuracy while a higher-order method (if available) succeeds. Such an experiment would provide direct validation of Lemma 2's upper bound rather than the indirect validation through training accuracy comparison.
MAX variants not tested on REDDIT datasets. The paper excludes max-pooling variants from the REDDIT experiments "due to GPU memory constraints." This is a practical limitation but means the comparison between sum, mean, and max on the most expressiveness-sensitive datasets is incomplete. It would be valuable to know whether max-pooling also achieves random-guessing performance on REDDIT (as the theory predicts, since max-pooling captures only the underlying set, and all nodes have the same "set" of one feature), or whether it achieves some intermediate accuracy.
No experiment on the effect of GNN depth on expressiveness. Theorem 3 requires "a sufficient number of GNN layers" for WL-equivalent power. The paper uses 5 layers for all experiments but does not ablate depth — for instance, showing that shallower GINs lose discriminative power on graphs with larger diameters, or that deeper GNNs asymptotically approach WL-kernel training accuracy. A depth ablation would strengthen the connection between the theory (which requires sufficient iterations) and the practice (where 5 layers is chosen heuristically).
The readout function choice (sum vs. mean) is dataset-dependent but not systematized. The paper uses sum readout for bioinformatics and mean readout for social datasets "due to better test performance." This is a post-hoc choice that is not cross-validated systematically — the paper doesn't report what happens if you use sum readout on social datasets or mean readout on bioinformatics. This matters because Theorem 3's condition (b) requires injective readout (sum, not mean), so using mean readout on social datasets means the theoretical guarantee doesn't apply to the experiments where GIN shows its largest gains. The fact that GIN with mean readout still dramatically outperforms mean-pooling GNNs on REDDIT suggests that the node-level aggregation (sum) is the critical component, and the graph-level readout's injectivity is less important — but this is not acknowledged or analyzed.

Experiments that would have strengthened the paper but were not run:

Direct injectivity measurement: After training GIN on each dataset, extract the multiset of neighbor features for a sample of nodes at each layer, compute the sum-aggregated representation, and measure what fraction of distinct multisets produce distinct aggregated representations. This would quantify how close GIN comes to achieving injectivity in practice.
Synthetic graph discrimination benchmarks: Construct controlled datasets where graphs differ only in specific structural properties (e.g., multiset of node degrees, distribution of neighbor types, presence/absence of specific motifs), and test which GNN variants can distinguish them. This would directly validate the theoretical taxonomy (sum captures multiset, mean captures distribution, max captures set) rather than relying on the correlation between expressiveness ranking and benchmark performance.
Node classification experiments: The paper's theory provides clear predictions about when mean-pooling and max-pooling should suffice for node classification (rich, diverse node features), yet the experiments are exclusively graph classification. Including node classification benchmarks (Cora, Citeseer, PubMed) would test the theory's domain of applicability and potentially show that GIN's expressiveness advantage is task-dependent.
Higher-order baseline: The paper acknowledges in Section 8 that going beyond WL requires architectures that consider higher-order structures (pairs or triplets of nodes). Including even a simple higher-order baseline (e.g., 2-WL or a GNN that operates on node pairs) on the REDDIT datasets would help quantify how much room for improvement remains above the WL ceiling, and whether GIN is already capturing most of the practically relevant structural information.

Conditional claims and their boundaries:

"GIN outperforms less powerful GNNs" holds most strongly when structural information dominates node features. On REDDIT datasets (uninformative features), the gap is 42 percentage points. On bioinformatics datasets (rich categorical features), the gap is typically 1–3 percentage points and sometimes not statistically significant.
"GNNs can outperform the WL subtree kernel" holds when structural similarity matters for generalization, but not universally. On NCI1 (the largest bioinformatics dataset), the WL subtree kernel significantly outperforms all GNNs (86.0% vs. 82.7%). The paper doesn't provide a principled explanation for why NCI1 is the exception, making this boundary condition empirical rather than theoretically understood.
"Training accuracy reflects expressiveness" holds across architectures but within a fixed training budget. The paper uses fixed hyperparameters for training accuracy comparison, which isolates architecture effects. But with different optimization settings (more epochs, different learning rates, larger hidden dimensions), some of the "underfitting" GNNs might achieve higher training accuracy. The underfitting is diagnostic of a representational limitation only if the model has sufficient optimization budget to converge — the paper's fixed-protocol design makes this assumption but doesn't verify it (e.g., by showing that the underfitting models' training loss has plateaued, not just that the curve is flat at a low accuracy after 200 epochs).
The expressiveness-test performance link is correlational, not causal in the experimental design. The paper shows that expressiveness ranking correlates with test accuracy ranking, but doesn't experimentally manipulate expressiveness independently of other factors (e.g., by taking a fixed architecture and systematically degrading its injectivity while holding all else constant). The "ablations" change the aggregation function, which simultaneously changes expressiveness, inductive bias, optimization landscape, and generalization properties — making it difficult to attribute performance differences purely to expressiveness.

6. Limitations and Trade-offs

The assumption or constraint. Lemma 2 formally proves that any aggregation-based GNN is at most as powerful as the Weisfeiler-Lehman test. The WL test, while effective on a broad class of graphs, has well-documented failure cases — most notably, it cannot distinguish certain non-isomorphic regular graphs where every node has the same degree and identical multisets of neighbor labels at every iteration (Cai et al., 1992; Douglas, 2011). The paper explicitly acknowledges this in Section 4: "a powerful heuristic called Weisfeiler-Lehman (WL) graph isomorphism test, that is known to work well in general, with a few exceptions, e.g., regular graphs (Cai et al., 1992; Douglas, 2011; Evdokimov & Ponomarenko, 1999)."

The consequence. Any pair of non-isomorphic graphs that the WL test cannot distinguish — for instance, two non-isomorphic k-regular graphs on n nodes with identical node features — will receive identical embeddings from GIN and every other neighborhood-aggregation GNN, regardless of depth, width, or training data. This is not an optimization issue or a capacity issue; it is a hard representational bound that no amount of scaling or hyperparameter tuning can overcome. For applications where such graph structures are practically relevant — for example, certain molecular graphs where atoms have identical local environments but different global connectivity, or regular graphs arising in distributed systems and network topology — GIN and its variants are guaranteed to fail. The paper does not quantify how frequently such failure cases appear in real-world graph datasets or how consequential they are for downstream task performance.

What evidence exists in the paper. The limitation is purely theoretical — it follows from Lemma 2's proof — and is not experimentally measured in the paper. Figure 4 shows that even GIN cannot achieve perfect training accuracy on all datasets (e.g., on IMDB-BINARY, GIN training accuracy plateaus below the WL kernel's accuracy), which is consistent with the existence of indistinguishable graph pairs in the training data, but the paper does not identify which specific graphs are confused or verify that they correspond to WL-failure cases. The authors do not construct a controlled experiment — for example, a synthetic binary classification task on WL-indistinguishable regular graph pairs — to directly demonstrate the ceiling in action, which would provide empirical validation of Lemma 2 beyond the indirect evidence of training accuracy gaps.

Mitigation status. The paper does not attempt to mitigate this limitation within the GNN framework; it explicitly frames it as a boundary condition that defines the frontier for future work: "An interesting direction for future work is to go beyond neighborhood aggregation (or message passing) in order to pursue possibly even more powerful architectures for learning with graphs" (Section 8). The paper suggests that higher-order methods (operating on tuples of nodes rather than individual nodes) may break through this ceiling, but provides no experimental evidence or architectural proposals in this direction. For practitioners, this means GIN provides maximal power within the message-passing paradigm, but that paradigm itself has known blind spots — and if your task depends on distinguishing graphs that the WL test confuses, you need an entirely different class of models.

Difficulty Estimation Is the Linchpin — and It Is Prohibitively Expensive

The assumption or constraint. This paper does not have an explicit difficulty estimator like the test-time compute paper. However, it has an analogous, unstated dependency: the theoretical framework assumes that practitioners can determine a priori whether their task requires high expressive power (structural counting, exact multiset discrimination) or can tolerate lower expressiveness (distributional or set-level information only). The paper provides no diagnostic tool, no cheap proxy, and no empirical heuristic for making this determination without running full training experiments across multiple architectures.

The consequence. A practitioner deploying GNNs on a new graph classification task faces an expensive exploration problem. The theory tells them that sum > mean > max in expressive power, but not whether their specific task needs that expressiveness — i.e., whether the performance gap between GIN and GCN will be 42 percentage points (REDDIT-BINARY) or 1 percentage point (PROTEINS). The only way to find out is to train and evaluate multiple architectures, each requiring hyperparameter tuning, cross-validation, and computational resources comparable to the final deployment training. If the task turns out to be one where distributional information suffices (like many node classification benchmarks), the effort expended on GIN's more complex architecture was unnecessary. If the task requires exact structural counting but the practitioner starts with a mean-pooling architecture, they may erroneously conclude that GNNs are insufficient for their problem and abandon the approach, when in fact a simple switch to sum aggregation would solve it.

This is the structural analog of the difficulty estimation problem in the test-time compute paper: the framework provides a taxonomy of capabilities but no cheap mechanism to map a novel task to the appropriate capability tier. The cost of this mapping — training multiple architectures to convergence on your dataset — can easily dominate the cost of the final model, yet it is never accounted for in the paper's efficiency claims (which are about inference cost, not architecture selection cost).

What evidence exists in the paper. The paper's own experiments implicitly demonstrate this cost. To produce Table 1, the authors trained and tuned at least 7 GNN variants (GIN-0, GIN-ε, SUM–1-LAYER, MEAN–MLP, MEAN–1-LAYER, MAX–MLP, MAX–1-LAYER) per dataset, each with hyperparameter tuning across hidden dimensions, batch sizes, and dropout ratios, under 10-fold cross-validation. This is an enormous computational burden that is necessary precisely because there is no a priori way to know which architecture will work best. The paper never quantifies this total cost or discusses it as a limitation of the framework's practical applicability.

Mitigation status. Not addressed. The paper does not propose a lightweight diagnostic (e.g., measuring feature diversity, analyzing degree distributions, or computing cheap graph statistics that predict which aggregator will suffice). It does not provide guidelines like "if your average node degree exceeds X and your features have entropy less than Y, sum aggregation is essential." It does not discuss transferability — whether the optimal architecture on one dataset from a domain (e.g., bioinformatics) predicts the optimal architecture on another dataset from the same domain. Section 8's future work directions focus on going beyond the WL test and understanding generalization, not on making the framework's practical deployment more efficient. For a practitioner reading this paper today, the actionable guidance is essentially "if you care about structure, use GIN" — which is useful but leaves the cost of verifying that you do care about structure entirely unaddressed.

No Guarantee That the MLP Actually Achieves Injectivity in Practice

The assumption or constraint. GIN's theoretical WL-equivalent power depends on the MLP in Equation 4.1 learning to represent an injective function over multisets. Theorem 3 and Corollary 6 provide existence proofs — they show that there exists some function f making the sum aggregation injective, and that an MLP can approximate such a function (by the universal approximation theorem). But they provide no guarantee that gradient-based training with finite data and finite capacity will actually find such a function. The gap between "exists in the function class" and "is learned by SGD on this specific loss" is substantial and entirely unaddressed theoretically.

The consequence. A trained GIN may fall short of WL-equivalent power for several reasons that are difficult to diagnose:

Finite MLP capacity: The universal approximation theorem requires MLPs of potentially unbounded width. The paper's experiments use 2-layer MLPs with 16–64 hidden units, which may not have sufficient capacity to represent the required injective mappings, especially on datasets with large numbers of distinct node feature types and neighborhood configurations.
Optimization failure: Even if the MLP architecture is theoretically capable of representing an injective function, SGD with cross-entropy loss on graph classification may converge to a non-injective local minimum that achieves low training loss but collapses some structurally distinct graphs. This is particularly likely when the collapsed structures are rare in the training data and thus contribute negligibly to the loss.
No injectivity regularization: The training objective encourages discriminative power only to the extent needed to separate training classes — not to separate all structurally distinct graphs. If two structurally different graphs belong to the same class, the model has no incentive to assign them different embeddings, and may learn a non-injective mapping that achieves perfect accuracy on the training distribution but fails to generalize to out-of-distribution structural variations.

This limitation means that GIN's WL-equivalence is a capability of the architecture class, not a property of any trained instance of that architecture. A practitioner cannot assume that training GIN on their dataset produces a model that distinguishes all WL-distinguishable graphs — only that the architecture does not a priori rule out such discrimination, unlike mean-pooling or max-pooling variants which provably cannot achieve it regardless of training.

What evidence exists in the paper. None directly, and this is a significant gap. The paper reports training accuracy close to 100% on most datasets (Figure 4) as evidence of high expressiveness, but 100% training accuracy on the classification task is a much weaker condition than injectivity over all possible multisets. The model could be collapsing structurally distinct graphs that happen to share the same class label, or failing on rare structural patterns that don't appear in the training set. The paper never measures whether distinct multisets of neighbor features actually produce distinct aggregated representations in the trained model. Additionally, on IMDB-BINARY, GIN training accuracy plateaus below the WL subtree kernel's accuracy — evidence that the trained GIN has not achieved WL-equivalent discriminative power, despite using an architecture that theoretically could.

Mitigation status. Not addressed. The paper treats the existence proof as sufficient theoretical justification and does not discuss the gap between representational capacity (what the architecture could represent) and representational achievement (what the trained model actually represents). This is a common practice in deep learning theory but a genuine limitation for practitioners who need to know whether their trained model is operating at the theoretical ceiling. Future work could address this by developing diagnostic tools — for instance, measuring the collision rate (fraction of distinct input multisets that produce identical outputs) at each layer of a trained GIN, or designing auxiliary losses that explicitly encourage injectivity.

Single Benchmark Domain, Single Model Family — Generalization to Other Tasks and Architectures Is Unverified

The assumption or constraint. All experiments in the paper use 9 graph classification benchmarks (4 bioinformatics, 5 social networks) and a single base architecture (GIN with 5 layers, 2-layer MLPs, batch normalization, Adam optimizer). The paper states in Section 4: "we believe this model is representative of the capabilities of many contemporary GNNs." The choice of graph classification as the sole task domain is acknowledged only implicitly; the theory is presented as fully general, but the empirical validation is narrow.

The consequence. Several aspects of the findings may not transfer to other settings:

Node classification and link prediction are not tested. The theory makes specific predictions about these tasks: mean-pooling (GCN) should perform well on node classification when node features are rich and diverse, because the distribution of neighbor features carries sufficient signal (Section 5.3). Max-pooling should be suitable when identifying representative elements or the "skeleton" matters more than exact structure (Section 5.4). These predictions are not experimentally validated, meaning the paper provides no evidence that its expressiveness ranking actually predicts performance on the tasks for which GCN and GraphSAGE were originally designed and widely deployed. A practitioner working on node classification cannot conclude from this paper whether switching from GCN to GIN will help or hurt.
The architecture is fixed to a specific GNN design. GIN uses sum aggregation, MLP-based updates, concatenation-based readout across all layers, and batch normalization. The paper's ablations vary the aggregation function and perceptron depth but keep all other architectural choices fixed. This means the paper cannot distinguish between "sum aggregation is superior" and "sum aggregation works well in combination with GIN's specific readout and normalization choices." If a different readout function (e.g., Set2Set, differentiable pooling, attention-based readout) interacts differently with mean or max aggregation, the expressiveness ranking might shift.
The datasets are small by modern deep learning standards. MUTAG has 188 graphs; PTC has 344; PROTEINS has 1113. The largest datasets (COLLAB with 5000 graphs, REDDIT-MULTI5K with 5000 graphs) are modest compared to the sizes at which deep learning typically shows its greatest advantages. On such small datasets, factors like initialization variance, optimizer dynamics, and the stochasticity of 10-fold CV with ~18-graph validation folds (on MUTAG) may dominate the architectural differences the paper attributes to expressiveness. The paper's cross-validation protocol (selecting the epoch with best average accuracy across all 10 folds) further blurs the line between training and test information, making the reported test accuracies potentially overoptimistic estimates of generalization to truly held-out data.
Temporal dataset shift and benchmark saturation. The benchmarks used (from Yanardag & Vishwanathan, 2015) were standard at the time but have since been largely saturated. The paper reports state-of-the-art results on several datasets, but the margins are small (1–3 percentage points on bioinformatics datasets), and it is unclear whether the gains come from expressive power or from the specific combination of GIN's architecture with 10-fold CV hyperparameter optimization.

What evidence exists in the paper. The limitation is visible in the narrow scope of Table 1: only graph classification, only 9 datasets, only one base architecture family. The paper provides no node classification results, no link prediction results, no experiments on larger-scale graph benchmarks (e.g., OGB, which would become available later), and no experiments with different readout functions or GNN layer types beyond the basic message-passing formulation. The fact that GIN's advantage is largest on REDDIT (uninformative node features) and smallest on bioinformatics datasets (rich categorical features) suggests strong task-dependence that the paper's single-task evaluation cannot fully characterize.

Mitigation status. Not addressed. The paper does not discuss the limitation of its experimental scope or suggest that future work should validate the framework on other task types. Section 8's future directions focus exclusively on going beyond neighborhood aggregation and understanding generalization — not on broadening empirical validation. For a practitioner, the paper provides strong evidence that GIN is the best choice for graph classification on small-to-medium benchmarks with limited node features, but leaves open the question of whether it is the best choice for node classification, link prediction, graph regression, or large-scale industrial graph learning tasks.

The Readout Function Is Empirically Chosen Per Dataset, Undermining the Theoretical Guarantee

The assumption or constraint. Theorem 3 requires the graph-level readout function to be injective over multisets of node features for the GNN to achieve WL-equivalent power. The paper identifies sum readout as satisfying this condition. However, the experiments use mean readout on social network datasets (IMDB-BINARY, IMDB-MULTI, REDDIT-BINARY, REDDIT-MULTI5K, COLLAB) and sum readout on bioinformatics datasets, stating this choice is "due to better test performance" (Section 7). Mean readout is not injective — it collapses graphs with different numbers of nodes but similar structural compositions (by Corollary 8's distributional equivalence property applied at the graph level).

The consequence. The experiments where GIN shows its largest gains over less powerful GNNs — the social network datasets, where the gap between GIN and mean-pooling variants is 42 percentage points on REDDIT-BINARY — are conducted with a readout function that violates the injectivity condition of Theorem 3. This means that GIN as deployed in these experiments does not have the theoretical WL-equivalence guarantee. The fact that it nonetheless dramatically outperforms mean-pooling variants suggests that the node-level aggregation (sum) is the critical component for these tasks, and the graph-level readout's injectivity is less important — or that the practical benefits of mean readout (normalization for variable graph sizes, improved optimization) outweigh the theoretical loss of discriminative power.

This has two troubling implications for the paper's narrative:

The theory and experiments are partially decoupled. The paper's strongest empirical results come from a configuration that does not satisfy the conditions of its central theorem. The paper never acknowledges this tension or explains why violating the readout injectivity condition doesn't undermine the theoretical justification for GIN's performance.
The readout choice is post-hoc. The paper doesn't report what happens if you use sum readout on social datasets (presumably worse performance, since mean was chosen for "better test performance") or mean readout on bioinformatics datasets. This means the paper's reported results are the best-case configuration found after trying both options — a form of hyperparameter optimization that is not cross-validated or accounted for in the performance claims.

What evidence exists in the paper. The readout function choice is mentioned in a single sentence in Section 7.1: "specifically, sum readout on bioinformatics datasets and mean readout on social datasets due to better test performance." There is no ablation showing the performance difference between sum and mean readout on either dataset family, no discussion of why mean readout generalizes better when graph sizes vary, and no acknowledgment that using mean readout means Theorem 3's conditions are not met.

Mitigation status. Not addressed. The paper neither reconciles the theoretical tension (how can a non-injective readout still produce strong results within a framework that requires injectivity?) nor provides guidance for practitioners on when to prefer sum vs. mean readout. A practitioner implementing GIN on a new dataset must make this choice without theoretical guidance, essentially falling back on the same empirical trial-and-error that the paper's theoretical framework was designed to replace. The paper could have addressed this by: (1) providing a theoretical analysis of when mean readout preserves sufficient information (e.g., when graph sizes are not informative for the task), (2) showing that sum readout with appropriate normalization (layer norm, batch norm) matches or exceeds mean readout performance, or (3) acknowledging that the readout choice is an empirical compromise and characterizing the resulting gap from the theoretical optimum.

No Characterization of Generalization — Expressive Power Is Necessary but Not Sufficient

The assumption or constraint. The paper's theoretical framework analyzes representational capacity — what graph structures a GNN can distinguish in principle. It provides no theory of generalization — what structures a trained GNN will distinguish on unseen data, given finite training samples and a specific learning algorithm. Section 4 makes this scope explicit: "our theoretical results do not directly speak about the generalization ability of GNNs." The paper's only discussion of generalization is the qualitative observation that GNNs' continuous embeddings capture structural similarity while the WL kernel's discrete labels do not, which explains why GNNs can outperform the WL kernel despite having at most equal discriminative power.

The consequence. The paper provides strong evidence that expressiveness predicts training accuracy — models with higher expressiveness fit the training data better, and underfitting is diagnostic of insufficient capacity. But expressiveness does not reliably predict test accuracy:

GIN-ε is theoretically more expressive than GIN-0 (it can distinguish certain graph pairs that GIN-0 cannot, as noted in Section 4.1), yet GIN-0 consistently achieves equal or better test accuracy across all 9 datasets (Table 1). The paper attributes this to GIN-0's "simplicity," but this is a post-hoc explanation rather than a principled understanding of when the extra expressiveness will help vs. hurt generalization.
The WL subtree kernel has maximum expressiveness (it is the WL test turned into a kernel) yet is outperformed by GNNs on multiple datasets. Expressiveness alone does not determine test performance.
On NCI1, the WL kernel significantly outperforms all GNNs (86.0% vs. 82.7% for GIN-0, the only dataset where a baseline is significantly better). This suggests that expressiveness can be the dominant factor for generalization on some datasets, but the paper provides no framework for predicting when this will be the case.

For a practitioner, this limitation means that choosing the most expressive architecture (GIN) is a reasonable default but not a guarantee of best test performance. Depending on the dataset, a less expressive architecture might generalize better due to its inductive bias (mean-pooling normalizes for neighborhood size, max-pooling is robust to outliers), and the paper provides no way to predict this without running the experiment.

What evidence exists in the paper. The GIN-ε vs. GIN-0 comparison is the clearest evidence: GIN-ε has strictly greater representational capacity yet underperforms GIN-0 on test accuracy across the board. Table 1 shows that GIN-0 achieves higher test accuracy than GIN-ε on 8 of 9 datasets, with equal accuracy on NCI1. This is consistent across both bioinformatics and social datasets. Additionally, the WL kernel vs. GIN comparison shows that maximum expressiveness does not guarantee maximum test accuracy — and on NCI1, it actually guarantees the opposite.

Mitigation status. The paper acknowledges the expressiveness-generalization gap qualitatively but does not analyze it theoretically or empirically. Section 4 notes that "capturing structural similarity of the node labels is shown to be helpful for generalization particularly when the co-occurrence of subtrees is sparse across different graphs or there are noisy edges and node features (Yanardag & Vishwanathan, 2015)," but this is a citation to prior work rather than an analysis within the paper's own framework. Section 8 identifies generalization as future work: "it would also be interesting to understand and improve the generalization properties of GNNs as well as better understand their optimization landscape." A practitioner is left with the empirical observation that GIN-0 is the best default choice among the architectures tested, but with no theoretical understanding of the generalization tradeoffs involved in that choice, and no guidance for when a less expressive but more regularized architecture might be preferable.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper fundamentally reorients GNN research from empirical architecture search — where aggregation functions were selected by benchmark performance with no principled understanding of why one worked better than another — toward representational capacity analysis, where the expressive power of any message-passing GNN can be precisely characterized in terms of its ability to distinguish multisets of neighbor features. The magnitude of this shift is comparable to what VC dimension and Rademacher complexity did for classical supervised learning: it provides the field with a theoretical vocabulary for reasoning about model failures that was entirely absent before. Prior to this work, a practitioner observing poor GNN performance had no way to distinguish between "my model is too small," "my learning rate is wrong," and "my aggregation function literally cannot represent the distinctions in my data." After this work, training set underfitting becomes a clear diagnostic signal — if a GNN cannot fit the training data, the first hypothesis should be insufficient expressive power, not optimization difficulty.

The paper resolves a cluster of apparent contradictions in the prior GNN literature through a single unifying principle. GCN (mean-pooling) achieved state-of-the-art node classification on citation networks (Kipf & Welling, 2017). GraphSAGE (max-pooling) excelled at inductive node classification on large graphs (Hamilton et al., 2017a). Meanwhile, sum-based architectures were known to work well on molecular property prediction (Duvenaud et al., 2015). These empirical results appeared to be in tension — which aggregation function is "best"? — but the paper's multiset taxonomy reveals there was no contradiction. Mean captures distributions, max captures sets, sum captures full multisets, and each is appropriate for different task requirements. GCN works on citation networks because bag-of-words document features rarely repeat within a neighborhood, making the distribution nearly as informative as the full multiset. Max-pooling works for identifying representative elements in inductive settings. Sum is essential when exact structural counts matter — molecular graphs being the canonical example. The field's prior confusion arose from treating these aggregators as interchangeable architectural choices evaluated on incommensurable benchmarks, rather than as encoding different assumptions about what structural information matters for the task.

The paper also redefines what counts as a strong baseline in GNN research. Before this work, a new GNN architecture was evaluated primarily against prior architectures on test accuracy. After this work, any new message-passing GNN must also be positioned relative to the WL bound: does it achieve WL-equivalent power (like GIN)? If so, what advantage does it offer over GIN — better generalization, lower computational cost, interpretability? If not, what expressiveness does it sacrifice, and is that sacrifice explicitly justified by the task requirements? This shifts the burden of proof for architectural innovation: instead of "my new aggregator achieves higher test accuracy on dataset X," the standard becomes "my new aggregator achieves WL-equivalent (or appropriately reduced) expressive power while providing benefit Y." GIN itself serves as a proof of concept that maximum expressiveness is achievable with a simple architecture, establishing a new baseline against which more complex designs must demonstrate value beyond what maximum expressiveness plus simplicity already provides.

The direction that becomes less attractive after this work is the proliferation of aggregation functions without theoretical characterization. The paper's framework makes it possible to analyze any aggregation function by determining what multiset property it preserves, and functions that cannot be cleanly characterized (e.g., LSTM-based pooling where the inductive bias is opaque) become harder to justify. The direction that becomes more attractive is architectures that go beyond the WL test entirely — higher-order structures, subgraph counting, positional encodings that break the symmetry of regular graphs — since the paper proves that the neighborhood message-passing paradigm has a hard ceiling that no amount of engineering within that paradigm can exceed.

Follow-Up Research This Work Enables

Direct measurement of achieved injectivity in trained GINs. The paper proves that GIN's architecture can represent injective multiset functions (Lemma 5, Corollary 6), but never measures whether gradient-based training on real datasets actually produces injective mappings. A concrete follow-up experiment: on each of the 9 benchmarks, after training GIN-0 to convergence, extract the multiset of neighbor features for every node at each layer, compute \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)} (the pre-MLP aggregated representation), and measure the collision rate — what fraction of structurally distinct multisets (identifiable via ground-truth graph structure) produce identical aggregated vectors within numerical tolerance? This would reveal how close trained GINs come to the theoretical injectivity ceiling in practice, and whether the gap correlates with the observed performance gap between GIN and the WL kernel on specific datasets (e.g., IMDB-BINARY where GIN training accuracy plateaus below the WL kernel). Pairing this with an experiment that varies MLP width (16, 32, 64, 128, 256 hidden units) would test the hypothesis that finite capacity is the primary bottleneck, potentially showing that wider GINs more closely approach WL-equivalent power.

Synthetic benchmarks that directly test the multiset taxonomy. The paper's empirical validation relies on correlating expressiveness rankings with benchmark performance, but the benchmarks are complex and confounded by node features, graph sizes, and class structure. A cleaner follow-up would construct a family of synthetic graph classification tasks where the only variation between classes is the specific multiset property that sum, mean, or max captures. For example: Task A distinguishes graphs by the exact count of a specific motif (requires sum); Task B distinguishes graphs by the distribution of node degrees (mean suffices); Task C distinguishes graphs by the presence/absence of at least one node with a specific property (max suffices). Training GIN-0, MEAN-MLP, and MAX-MLP on each task would produce a double dissociation: GIN-0 should solve all three, MEAN-MLP should fail on Task A but succeed on B, MAX-MLP should succeed on C but fail on A and B. This experiment would directly validate Corollaries 8 and 9 and provide a pedagogical demonstration of the taxonomy that the current paper's benchmark-based evaluation cannot isolate.

Node classification experiments under controlled feature diversity. Section 5.3 argues that mean-pooling (GCN) performs well on node classification when "node features are diverse and rarely repeat," making the distribution nearly as informative as the full multiset. This claim is theoretically motivated but never experimentally tested within the paper's framework. A follow-up experiment: take a standard node classification benchmark (Cora, Citeseer, PubMed), systematically degrade the informativeness of node features (e.g., by quantizing continuous features into fewer discrete bins, or by randomly setting a fraction of feature dimensions to a constant value), and measure the performance gap between GIN and GCN as a function of feature diversity. The prediction is that the GIN-GCN gap should be near zero when features are high-dimensional and continuous (as in the original Cora setting), and should grow as features become sparser and more repetitive — transitioning from the Cora regime to the REDDIT regime. This would establish the boundary conditions for when practitioners can safely use the simpler, computationally cheaper mean-pooling architecture.

Failure on WL-indistinguishable regular graphs as an experimental validation of Lemma 2. The paper proves that all message-passing GNNs are bounded by the WL test, and cites known WL failure cases (regular graphs), but never constructs an experiment demonstrating this bound in action. A simple follow-up: generate pairs of non-isomorphic k-regular graphs on n nodes (these exist for n sufficiently large, e.g., the 4×4 rook's graph and the Shrikhande graph are both 6-regular on 16 nodes but non-isomorphic and WL-indistinguishable), construct a binary classification task where each pair receives opposite labels, and train GIN-0 with increasing depth and width. The prediction is that test accuracy remains at 50% (chance) regardless of capacity, while a higher-order method (e.g., 2-WL GNN operating on node pairs, or a GNN augmented with unique node identifiers) should eventually achieve near-100% accuracy. This experiment would provide direct, intuitive validation of the theoretical ceiling and demonstrate concretely what "going beyond WL" means for practitioners — it transforms Lemma 2 from an abstract theorem into a visible failure mode.

Extension to edge features and heterogeneous graphs. The paper's framework assumes node features aggregated over edges with no edge-specific information. Many practical graph learning tasks — molecular property prediction with bond types, knowledge graph completion with relation types, traffic prediction with weighted edges — require edge features. A natural extension asks: how does the expressive power analysis change when aggregation functions must incorporate edge features? Does the multiset of (neighbor, edge_type) pairs require a different injectivity analysis? A concrete experiment: on a molecular dataset (e.g., QM9 or Tox21) where bond types (single, double, aromatic) provide critical information, implement GIN with edge-feature-aware aggregation (e.g., summing transformed [h_u, e_{vu}] pairs rather than just h_u), and compare against GCN and GraphSAGE variants similarly extended. The theoretical question is whether edge features increase or decrease the gap between sum and mean aggregation — intuitively, edge types add discriminative information that might allow mean-pooling to distinguish neighborhoods that would otherwise collapse, potentially narrowing the expressiveness gap on edge-rich graphs.

Combining GIN's expressiveness with recently developed scalability improvements. GIN was developed in 2019, before the explosion of work on scalable GNN training (GraphSAINT, ClusterGCN, etc.) and before the OGB benchmarks standardized large-scale graph evaluation. A valuable follow-up would implement GIN within a modern scalable training framework and evaluate on large-scale benchmarks (OGB node classification, OGB graph classification) where the original paper's experiments on datasets of 188–5000 graphs cannot demonstrate scalability. The specific hypothesis to test: does GIN's expressiveness advantage persist or diminish on large graphs with hundreds of thousands of nodes and rich features? The REDDIT results suggest the advantage is largest when features are sparse or uninformative, which is less common in large-scale industrial graphs — testing this on OGB-ArXiv (rich text features) vs. OGB-Proteins (sparse categorical features) would clarify when the expressiveness gap matters at scale.

Practical Applications and Downstream Use Cases

Molecular property prediction and drug discovery. This is the most direct application of GIN's expressiveness advantage. In molecular graphs, nodes represent atoms (with categorical types: C, N, O, etc.) and edges represent bonds (single, double, aromatic). The exact count of atom types and bond configurations in a molecular neighborhood directly determines chemical properties — for instance, the number of hydrogen bond donors and acceptors in a functional group predicts solubility. Mean-pooling (which captures only the distribution of atom types: "30% carbon, 20% nitrogen") would be insufficient for tasks requiring exact stoichiometry; max-pooling (which captures only "carbon and nitrogen are present") would be even worse. GIN's sum aggregation preserves exact counts, making it naturally suited for molecular fingerprinting and quantitative structure-activity relationship (QSAR) prediction. The paper's results on bioinformatics datasets (MUTAG, PTC, NCI1, PROTEINS) provide preliminary evidence, though the gains over mean-pooling are modest (1–3 percentage points) because these benchmarks have rich categorical features where distributional information already carries substantial signal. On tasks requiring precise structural counting — predicting atomization energies, counting functional groups, or identifying specific ring systems — the gap should be larger. A pharmaceutical company deploying GNNs for virtual screening should prefer GIN or a sum-aggregation variant as the default architecture, with mean-pooling reserved for tasks where computational efficiency dominates and node features are provably diverse enough to make distributional information sufficient.

Social network analysis with anonymized or privacy-preserving features. The REDDIT dataset results (92.4% for GIN-0 vs. 50.0% for mean-pooling on REDDIT-BINARY) are the paper's most dramatic finding and have direct practical implications for analyzing social networks where user-level features are unavailable or intentionally removed for privacy reasons. In such settings — classifying online communities by their interaction patterns, detecting coordinating inauthentic behavior from connection structure alone, analyzing organizational hierarchies from email graphs — the graph structure is the only signal, and aggregation functions that lose structural information (mean, max) will fail. GIN provides maximal structural discrimination within the message-passing paradigm and should be the default choice for any graph classification or regression task where node features are absent, constant, or deliberately obfuscated. The 4× efficiency gain observed between best-of-N and compute-optimal in the companion paper provides an analogy: just as adaptive allocation saves compute at fixed accuracy, choosing GIN over GCN on structure-only tasks saves the cost of failed experiments and misleading conclusions from models that never had a chance of succeeding.

Graph-based anomaly and fraud detection. In financial transaction networks, communication graphs, or cybersecurity applications, anomalies often manifest as unusual local structural patterns — a node connected to an unexpected combination of other nodes, or a subgraph with atypical connectivity. Max-pooling is particularly poorly suited for these tasks because it treats multiple instances of the same feature as identical: a user receiving one suspicious transaction looks the same to max-pooling as a user receiving 50 suspicious transactions. Mean-pooling partially addresses this via proportions but still loses absolute counts — a user with 50 normal and 2 suspicious transactions may look similar to a user with 5 normal and 0.2 suspicious (impossible in practice, but the normalized representation loses the raw count signal). GIN's sum aggregation preserves exact multiplicities, allowing the model to distinguish "many suspicious connections" from "a few suspicious connections" — a distinction that is often the difference between a false positive and a genuine anomaly. Practitioners building GNN-based fraud detection systems should use sum aggregation (or GIN specifically) as the first architectural choice, with mean-pooling considered only after verifying that anomaly signals are distributional rather than count-based.

When to Prefer This Method

The paper does not explicitly frame GIN against named alternatives with a structured decision rule — it presents GIN as the architecture that achieves the theoretical maximum expressiveness within the message-passing paradigm, and the experiments compare against less expressive variants (GCN-like, GraphSAGE-like) to validate the expressiveness ranking. The choice of when to prefer GIN therefore follows directly from the theory, not from the paper articulating a tradeoff matrix against specific named competitors. The decision rule implicit in the paper's theoretical framework is:

When the task requires exact structural information (counting motifs, distinguishing multiplicities, tasks where "how many" matters as much as "what kind"), use GIN or an equivalent sum-aggregation architecture with MLP-based updates. The REDDIT dataset results establish that the cost of choosing mean or max when sum is required is not a small accuracy penalty but complete task failure (random-guessing performance).
When the task depends primarily on the distribution of neighbor types and node features are rich, diverse, and rarely repeated, mean-pooling (GCN-like) architectures may be sufficient. The paper's theoretical analysis (Corollary 8) and the observation that "GNNs with mean aggregators are effective for node classification tasks" (Section 5.3) support this, though the boundary is not experimentally validated for node classification in this paper.
When the task requires only identifying the presence or absence of representative features in a neighborhood, and robustness to outliers or noise is more important than precise counting, max-pooling (GraphSAGE-like) may be appropriate. Corollary 9 and the cited results from Qi et al. (2017) on point cloud skeleton identification support this.

The paper does not provide a quantitative rule — no threshold on feature entropy, node degree variance, or graph diameter that determines which regime a given dataset falls into. The decision currently requires either training multiple architectures (expensive) or reasoning about the task's information requirements from domain knowledge (which the paper enables but does not automate). This is a practical limitation that the paper acknowledges only implicitly through its experimental design, which evaluates all architectures on all datasets precisely because the mapping from task characteristics to optimal architecture is not theoretically predictable within the current framework.

🎯 Pitch

1. Executive Summary

2. Context and Motivation

The Core Problem: We Don't Know What GNNs Can Actually Represent

Why This Matters: Beyond Academic Classification

Where Prior Approaches Fall Short

How This Paper Positions Itself

3. Technical Approach

3.1 Reader Orientation (Approachable Technical Breakdown)

3.2 Big-Picture Architecture (Diagram in Words)

3.3 Roadmap for the Deep Dive

3.4 Detailed, Sentence-Based Technical Breakdown

Modeling Graphs as Multisets of Neighbor Features: The Core Abstraction

The Upper Bound: GNNs Cannot Exceed WL Power (Lemma 2)

Conditions for WL-Equivalent Power: Theorem 3

Deep Multisets: Proving Sum Aggregation Can Be Injective (Lemma 5 and Corollary 6)

Why 1-Layer Perceptrons Are Insufficient (Lemma 7)

What Mean Aggregation Actually Captures (Corollary 8)

What Max-Pooling Actually Captures (Corollary 9)

The GIN Architecture: Satisfaction of Theorem 3 Conditions

4. Key Insights and Innovations

Innovation 1: Expressiveness as the Central Diagnostic for GNN Design — Not Just Another Architecture

Innovation 2: Injectivity as the Unifying Principle — Why Sum Works and Mean/Max Don't

Innovation 3: The GNN-WL Connection as Both Ceiling and Construction — Bounding and Achieving Maximum Power

Innovation 4: Learned Continuous Embeddings as a Generalization of Discrete WL Labels — Why GNNs Can Outperform the WL Kernel

5. Experimental Analysis

Evaluation Methodology

Main Quantitative Results

Training Set Performance: Expressiveness Directly Predicts Fitting Capacity

Test Set Performance: GINs Achieve State-of-the-Art

The Diagnostic Power of Training Accuracy: Figure 4 as a Litmus Test

Ablation Studies and Robustness Checks

Critical Assessment

Does the evidence support the claim that "GNNs are at most as powerful as the WL test"?

Does the evidence support the claim that injective aggregation + injective readout = WL-equivalent power?

Does the evidence support the claim that popular GNN variants cannot distinguish certain simple graph structures?

Does the evidence support the claim that GIN achieves state-of-the-art performance?

Genuine weaknesses in the experimental design:

Experiments that would have strengthened the paper but were not run:

Conditional claims and their boundaries:

6. Limitations and Trade-offs

The WL Test as a Ceiling: GNNs Are Fundamentally Blind to Certain Graph Structures

Difficulty Estimation Is the Linchpin — and It Is Prohibitively Expensive

No Guarantee That the MLP Actually Achieves Injectivity in Practice

Single Benchmark Domain, Single Model Family — Generalization to Other Tasks and Architectures Is Unverified

The Readout Function Is Empirically Chosen Per Dataset, Undermining the Theoretical Guarantee

No Characterization of Generalization — Expressive Power Is Necessary but Not Sufficient

7. Implications and Future Directions

How This Work Changes the Landscape

Follow-Up Research This Work Enables

Practical Applications and Downstream Use Cases

When to Prefer This Method

Adjacent in domain

Mesh-TensorFlow: Deep Learning for Supercomputers

BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding