acceptodds
Under review as a conference paper at ICLR 2027

Does your graph learning task really require more expressive GNNs ?

Abstract

Whether a Message Passing Neural Network (MPNN) is expressive enough for a given graph learning task is typically answered post hoc, by comparing model performance on a held-out set. We argue that this question should instead be an- swered a priori, as a property of the dataset. We formalize three dataset-level conditions: refinability, 1-WL separation within the dataset, and amenability. We show that each condition gives theoretical guarantees on the performance of MPNNs, but that 1-WL separation, the property that collision counts measure, de- pends on the whole dataset, can break with one new graph, and says nothing about nodes. We prove that amenability is the right notion: on an amenable family, a GIN with enough message-passing layers universally approximates any continu- ous permutation-invariant target, at both graph and node level, the guarantee holds on train and test together, and the fraction of non-amenable graphs bounds the loss of any MPNN. Amenability is a per-graph property, testable in quasi-linear time, and our implementation checks millions of graphs in minutes. Empirically, we find that more than 99% of molecular graphs and more than 98% of their k-hop neighborhoods are amenable, and that a 1-WL approximation of random-walk positional encodings gives the same gain as the encodings themselves, suggest- ing that MPNNs are expressive enough for typical molecular property prediction tasks.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Expressivity, Datasets, WL-1

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_4hwtOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper builds on results by Arvind et al. (2015) and proposes to use amenability for measuring for how much expressivity is needed on a graph dataset. If all graphs in a specific dataset are amenable, sufficiently expressive MPNNs can distinguish all non-isomorphic graphs within that dataset (and also distinguish them from non-isomorphic graphs outside of the dataset) in theory. It is shown that in three molecule datasets almost all graphs are amenable. And that a 1-WL approximation of random walk encodings gives the same gain as the encodings themselves, suggesting that the gain comes from the inductive bias.

Critical strengths

The paper is well written and easy to follow for the most parts.

Critical weaknesses

The contribution of the paper is very limited. For most parts it is also not clear what the contribution is: The paper mainly builds on [Arvind et al., 2015], where amenability and the running time for testing amenability are already established, yet the paper claims this as their contribution.

While the paper itself is well written, I find the structure strange, it is not motivated why Sections 3.2 and Section 4 are part of the paper, especially since Section 4 seems to contain only results from Arvind et al., 2015. There is also a justification paragraph at the end of many sections which could be integrated into the text more naturally.

Questions for authors

Q1: Can you state for the contributions of your paper how they differ from [Arvind et al., 2015]?

Q2: Even if not all graphs in a dataset are amenable, it could be that no confusers are present in the dataset, and thus MPNNs can distinguish all graphs (and in practice this is often the case [Zopf, 2022]). Therefore, looking just at "can 1-WL distinguish all graphs in the dataset", we can determine that accuracy gains only come from modeling choices and not from expressivity gains. If we, however, look at amenability, could we not be misled to think that more expressivity is needed for that dataset (as not all graphs in the dataset are amenable), while it is not, making it actually harder to attribute accuracy gains?

1 comment
Reviewer_4hwtOpenReview ↗

Response to Rebuttal

I thank the reviewers for their answers. However, they do not address my concerns regarding novelty and presentation of the contributions beyond from Arvind et al.:

In the paper, the algorithm is present as in a way that makes it seem like a new contribution. Although the authors mention that the algorithm was proposed by Arvind et al., I do not think this sufficiently distinguishes their contributions from the existing results. If the algorithm and its theoretical properties are already established in Arvind et al. (2015), I do not see why they need to be presented as a contribution of the paper and even listed in the contribution section.

Also, my second question is not answered. Consider a dataset, in which 1-WL can distinguish all graphs (in both train and test set), while not all graphs in the dataset are amenable. Looking only at amenability, could we not incorrectly conclude that a method performs better because it is more expressive? I agree that only looking at collisions in the training set is also problematic, but my above concern is different from this problem.

Based on your answer, another question came to my mind: Are there actually real-world examples of confusers in test set? The existence of possible confusers does not necessarily imply that they will likely occur in the underlying data distribution. I think this important, since amenability is motivated as a measure for guiding design choices.

Having read also the concerns of the other reviewers, I will keep my score.

Reviewer_evwrOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes amenability as a dataset-level diagnostic for asking whether graph learning really needs expressivity beyond 1-WL. It links this property to approximation guarantees and prediction risk, audits several molecular datasets, and compares true RWPE with RWPE predicted by an MPNN.

Critical strengths
  1. Clear conceptual distinctions. The paper separates node-orbit separability, within-dataset graph separability, and single-graph identifiability, clarifying the scope of expressivity claims.

  2. Large-scale data audit. Statistics on about millions of molecular graphs and many local neighborhoods provide useful material on data structure and model capability.

  3. Supplementary encoding comparison. Replacing true RWPE with MPNN-predicted RWPE adds a useful angle to existing encoding ablations, though mechanistic claims need tighter controls.

Critical weaknesses
  1. The attributed-graph certification claim does not look sound as stated. Section 4.3 applies structural checks after attributed CR, but two edge-colored K6K_6 graphs with red edges C6C_6 vs. 2K32K_3 and blue elsewhere are indistinguishable by attributed CR yet both pass the uncolored checks. The authors should clarify whether the implementation handles this case differently and re-check the molecular statistics if needed.

  2. Some theoretical extensions are wrong or not qualified carefully enough. Remark 3 assumes concatenated node-orbit representations distinguish tuple orbits, but in amenable C4C_4 all node embeddings coincide while adjacent and opposite pairs lie in different tuple orbits. The uniform approximation claims for arbitrary D⊆GnD\subseteq\mathcal G_n also need additional domain assumptions.

  3. The incremental contribution and practical conclusions need stronger support. Zopf (2022) and Luo et al. (2025) already cover much of the 1-WL-bottleneck and RWPE-ablation ground, and the learned-RWPE experiment adds capacity, pretraining, and only one benchmark. Amenability rates alone also do not quantify task-specific loss or establish efficient learning and generalization.

Questions for authors
  1. How does the implementation actually handle edge attributes? Would it certify the two edge-colored K6K_6 graphs above as amenable, and would any necessary correction change the reported statistics?

  2. How would you revise Remark 3 given the C4C_4 tuple-orbit counterexample? What additional assumptions are needed for the uniform approximation claims in Theorems 4 and 6?

  3. Beyond existing collision analyses and positional-encoding ablations, what task-level predictive value does amenability really provide? Could capacity- and training-budget-matched experiments sharpen the interpretation of the learned-RWPE results?

1 comment
Reviewer_evwrOpenReview ↗

Response to the Rebuttal

Thanks for the response. Table 3b does help. Comparing true vs. learned RWPE under the same downstream model is a fair point, and freezing the predictor addresses the capacity concern. The separate pretraining still needs to count toward the total budget, though.

But my two technical objections still haven't been answered.

First one, the attributed test. Take the two edge-coloured K6K_6 graphs I described, constant node features. Red edges form C6C_6 in one, two disjoint triangles in the other. Blue elsewhere. Every vertex has two red and three blue neighbours, so attributed CR gives identical fingerprints. The graphs aren't isomorphic as edge-coloured graphs. But the uncoloured checks in Section 4.3 see a single complete cell and accept both. That contradicts the soundness claim as stated. Does the implementation handle edge types differently? If so, how? And would fixing it change the 99.4% figure? Reviewer 4i5b's W4/Q4 raises the same underlying issue.

Second one, Remark 3. In C4C_4 with constant features, all vertices get the same MPNN embedding. But an adjacent pair and an opposite pair are in different tuple orbits. Concatenating node embeddings can't distinguish them. So the extension to arbitrary tuples doesn't follow. The uniform approximation claims in Theorems 4 and 6 also need their domain assumptions clarified. Compact feature spaces alone don't justify arbitrary DD.

On the response arguments. I accept the budget-matched table, so capacity is settled. Corollary 3 doesn't help, though. It only speaks about amenable graphs, and whether these graphs are amenable is exactly what the attributed test is supposed to certify. If the test is unsound, 99.4% isn't evidence of amenability, and Corollary 3 applies to nothing. ZINC-12k doesn't settle it either. N2-GNN beats GIN+ there, so it doesn't show there's no gain to explain.

I agree the guarantees are about approximation, not optimisation or sample complexity, and that this scope should be explicit. But for now, the unanswered certification and theory issues are enough for me to keep my score unchanged.

Reviewer_4i5bOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper argues that whether an MPNN is expressive enough for a task should be decided a priori, as a property of the dataset. It compares refinability, color refinement separation and amenability, argues that amenability is the right condition since it is checked per graph and bounds the loss of any MPNN, and gives a quasi-linear test for it.

Critical strengths

S1: Bringing amenability from the graph isomorphism literature to graph learning is a principled choice.

S2: Distilling RWPE into an MPNN is a simple and interesting way to probe whether an encoding adds information beyond color refinement.

S3: The test is fast enough to run on very large datasets and their local neighborhoods, which makes reporting it next to a benchmark practical.

Critical weaknesses

W1: It is unclear how the diagnostic would affect model selection in practice. The experiments show that encodings still help even on amenable data, so a high amenable fraction does not necessarily tell us which model to use.

W2: The paper argues that gains from more expressive models on molecular benchmarks are not due to expressivity. However, the experiments only test one positional encoding on one dataset. Higher-order and subgraph architectures, which partly motivate the paper, are left for future work.

W3: The title and framework discuss graph learning in general, including both graph-level and node-level tasks. However, the evaluation is limited to graph-level molecular benchmarks, where color refinement is already known to separate almost all graphs.

W4: The characterization used holds for unattributed graphs, yet every experiment uses node and edge features, and the claim that the adapted test remains sound is stated without proof, although all reported amenable fractions depend on it.

W5: Section 2 presents definitions in informal paragraphs rather than formal statements. Some notation is used before being introduced, or is never defined. The abstract also uses terms without explaining them. Overall, I found the paper difficult to read in places.

Questions for authors

Q1: Can the authors give a concrete case where the amenable fraction of a dataset changes the choice of architecture?

Q2: Can the authors apply the same protocol to one subgraph or higher-order GNN, for instance by distilling its node features into an MPNN, and show whether the gain is retained?

Q3: Can you report the amenable fraction on non-molecular graph benchmarks where more expressive models report large gains over MPNNs?

Q4: Can you provide a proof that the adapted test remains sound with node and edge features, including how edge types enter the cell graph?

Comments on the paper

3 comments

We thank the three reviewers for their careful reading and their detailed questions. We are glad that they found several strong points in the paper:

  • The approach. Bringing amenability from the graph isomorphism literature to graph learning is "a principled choice", and the paper makes "clear conceptual distinctions" between node-orbit separability, separability inside the dataset and identifiability of a single graph, which clarify "the scope of expressivity claims".
  • The test at scale. The test is "fast enough to run on very large datasets and their local neighborhoods, which makes reporting it next to a benchmark practical", and our statistics on millions of molecular graphs "provide useful material on data structure and model capability".
  • The RWPE experiment. Distilling RWPE into an MPNN is "a simple and interesting way to probe whether an encoding adds information beyond color refinement", and it "adds a useful angle to existing encoding ablations".
  • The writing. The paper is "clear and easy to follow".

Below, we answer the three questions that several reviewers raised: what our contribution is beyond Arvind et al. (2015), what the amenable fraction tells a practitioner, and the scope of our experiments.

1 - Contribution (Reviewer 4hwt Q1, Reviewer evwr)

Yes, our work builds on the graph isomorphism results of Arvind et al. (2015) and Kiefer et al. (2015). The paper states this in the contributions (line 066), and again where amenability is introduced (line 167), at the start of Section 4 (line 247), for the characterization (Theorem 3, line 288) and for the running time (line 303). Amenability, its characterization and the quasi-linear test are their results. Arvind et al. study graph isomorphism, and they do not consider learning, datasets or MPNNs. Our contributions are the following.

  1. Dataset-level conditions for MPNN expressivity. We define three conditions on a dataset: refinability (P1), separation inside the dataset (P2) and amenability (P3). We compare them (Proposition 1, Remark 2). P2, the property that collision counts measure, depends on the whole dataset, one new graph can break it, and it says nothing about nodes. P3 has none of these problems.
  2. Guarantees for learning on amenable data. On an amenable family, a GIN with enough layers approximates any continuous permutation-invariant target, at graph level and at node level (Theorem 4). The guarantee holds on train and test together (Proposition 1). We also give the corresponding result under P2 (Theorem 6).
  3. A bound on the loss of any MPNN. The CR-class risk decomposition (Theorem 2) and its corollary show that the fraction of non-amenable graphs bounds the loss of any MPNN. With Corollary 3, on an amenable graph, no encoding carries information that color refinement does not already have.
  4. A test for datasets, not single graphs. We use the test on attributed graphs and on the rooted kk-hop ball of every node, which gives a measure at node level. Our open-source implementation checks millions of graphs, and the 656656 million kk-hop balls of three datasets.
  5. The first measurement of amenability on real data. 99.4%99.4\% of the molecules of ZINC-250k, AQSOL and PCQM4Mv2 are amenable, and more than 98%98\% of their kk-hop balls. On AQSOL, 94.6%94.6\% of the training molecules are amenable but only 71.8%71.8\% of the test molecules, so the test finds a shift between the splits before any training.
  6. A test of why RWPE helps. An MPNN learns RWPE from the graph alone (R2>0.99R^2 > 0.99), and these learned encodings give the same gain as the true RWPE. So on amenable data, the gain of RWPE comes from inductive bias and not from expressivity.

Zopf. Zopf counts collisions of CR fingerprints, which tests P2. We discuss this at line 236 and in Finding 2 (line 375). On our three datasets, CR separates every pair of molecules, so a collision count reports no problem. But about 21,00021{,}000 molecules are not amenable: each one has a confuser outside the dataset, and a new molecule from the same source can break P2. Zopf also gives no guarantee on the loss, on test data or on nodes. Items 1 to 3 above give these guarantees.

Luo et al. They show that classic MPNNs with good training choices match or beat graph transformers on graph-level tasks. This is why we use their GINE setup in our RWPE experiment. Their ablation shows that the encoding (RWSE) is one of the largest gains on ZINC: without it, the MAE of GIN+ goes from 0.0650.065 to 0.1230.123. But they do not explain this gain, and they leave the question open: "A deeper theoretical understanding is needed to elucidate the role of each architectural component within GNN+ [...], particularly regarding the model's expressiveness". Our work answers this question for RWPE on molecules: the gain does not come from expressivity, because 99.4%99.4\% of the molecules are amenable and an MPNN learns the encoding from the graph alone.

2 - What the amenable fraction tells a practitioner (Reviewer 4i5b W1/Q1, Reviewer evwr Q3, Reviewer 4hwt Q2)

What the test answers. The amenable fraction answers one question: can expressivity be what limits an MPNN on this data? It does not tell which inductive bias is best, and the paper does not claim that. The RWPE result (Finding 5, line 431) is an example of the test doing its job. The usual explanation of the gain of RWPE is that RWPE are more expressive than 1-WL. On amenable graphs, the test rules this explanation out, and the experiment confirms it: an MPNN learns RWPE from the graph alone, and the learned encodings give the same gain. So the gain comes from inductive bias.

Cases where the fraction changes a choice (Reviewer 4i5b Q1).

  • Whether to use a more expressive model. With p=99.4%p = 99.4\%, Corollary 1 bounds the loss floor of any MPNN by 0.6%0.6\% of the largest conditional variance of the target on a non-amenable CR class. A higher-order or subgraph model costs much more and can recover only this part. On these datasets, the better choice is an MPNN with a good inductive bias.
  • The opposite case. In CSL and EXP, every graph has a confuser by construction (all CSL graphs are 44-regular on 4141 nodes, and EXP is built from pairs that 1-WL cannot distinguish), so p=0p = 0. There, a more expressive model is justified, and these are the benchmarks where such models win.
  • Depth. Separating the graphs takes k2(D)=5k_2(\mathcal{D}) = 5 to 77 iterations, but separating the nodes takes tCR(D)=11t_{\mathrm{CR}}(\mathcal{D}) = 11 to 1212 (Finding 3, line 396). The depth of the MPNN should follow tCRt_{\mathrm{CR}}.

Task-specific loss (Reviewer evwr). Our claims are about approximation, that is, what an MPNN can represent. We make no claim about optimization or sample complexity. Expressivity is a question of approximation, and the field uses it as such to motivate more expressive architectures. Within this scope, we do bound the loss with amenability. Corollary 1 shows that the minimum loss of any MPNN on a task is at most (1−p)(1-p) times the largest variance of the target on a non-amenable CR class, where pp is the amenable fraction. So on amenable graphs, the lack of expressivity causes no loss, for any task.

Can amenability mislead? (Reviewer 4hwt Q2). We think the risk goes the other way. "No collision in the dataset" says nothing about unseen graphs: each non-amenable graph has a confuser outside the dataset, and a new graph from the same source can be one (Proposition 1, lines 159-160). Take a dataset with no collisions but a low amenable fraction. A collision count says that 1-WL is enough, so we choose an MPNN. But the low amenable fraction tells us that new graphs will bring confusers, and the MPNN will fail on them. Here, the collision count gives a false sense of safety, and amenability shows the real risk. This is critical for Machine Learning, as we do not have access to the test set and risk "overfitting" our architecture choice if we just look at collisions on the train set.

3 - Scope of the experiments (Reviewer 4i5b W2/W3/Q2/Q3, Reviewer evwr)

The theory covers every architecture; RWPE shows it in practice (Reviewer 4i5b W2/Q2). Our claim about higher-order and subgraph GNNs does not come from the RWPE experiment. It comes from a theorem that holds for every architecture. For any graph-level target, Corollary 3 shows that on an amenable graph, the CR fingerprint already holds all the information about the target. So on the 99.4%99.4\% of amenable molecules, no encoding and no architecture can add information about the target, whatever mechanism it uses to go beyond 1-WL. We do not need to test each architecture to know this. The RWPE experiment tests what the theorem cannot show: whether an MPNN learns such an encoding in practice. It does (R2>0.99R^2 > 0.99), and the learned encoding gives the same gain as the true one. We chose RWPE because it is one of the most widely used encodings on molecular tasks, and it is the encoding used in the tuned MPNNs of Luo et al. (2025).

We do not think that distilling a subgraph or higher-order GNN is necessary, because on molecular benchmarks there is almost no gain to explain: a well-tuned 1-WL model performs as well as these architectures. The table below gives the MAE on ZINC-12k, where models usually have at most 500500k parameters. The 1-WL result is the tuned GIN+ of Luo et al. (2025, Table 2), and the other results are collected by Feng et al. (NeurIPS 2023, Table 5).

ModelExpressivityZINC-12k MAE
GIN+1-WL0.065±0.0040.065 \pm 0.004
SSWL+subgraph0.070±0.0050.070 \pm 0.005
KC-SetGNNhigher-order0.075±0.0030.075 \pm 0.003
PPGN3-WL0.079±0.0050.079 \pm 0.005
CINhigher-order0.079±0.0060.079 \pm 0.006
SUNsubgraph0.083±0.0030.083 \pm 0.003
I$^2$-GNNsubgraph0.083±0.0010.083 \pm 0.001
GNN-AKsubgraph0.093±0.0020.093 \pm 0.002
ESANsubgraph0.097±0.0060.097 \pm 0.006
N$^2$-GNNhigher-order0.059±0.0020.059 \pm 0.002

All higher-order and subgraph models are worse than GIN+, except N$^2$-GNN, which is better by 0.0060.006. For comparison, the RWSE encoding alone improves GIN+ by 0.0580.058 (from 0.1230.123 to 0.0650.065, Luo et al., Table 5), ten times more.

Node level is tested on 656M neighborhoods; molecules are a case study (Reviewer 4i5b W3/Q3). The evaluation is not only graph-level: we test the rooted kk-hop ball of every atom, 656656 million balls in total, and more than 98%98\% of them are amenable (Finding 4). CR separates almost all molecules (P2), but amenability is a stronger property, and 21,00021{,}000 molecules fail it (Finding 2).

For Q3: the benchmarks where more expressive models report large gains over MPNNs are synthetic, such as CSL, EXP and BREC. They are built from graphs that 1-WL cannot distinguish, so every graph has a confuser and the amenable fraction is 0%0\%. Amenability correctly predicts that these benchmarks need more expressivity, and that molecular benchmarks do not.

Same model, same budget: the predictor is frozen (Reviewer evwr). The experiments of Table 3b are already matched in capacity and training budget. The three rows train the same GINE, with 475475k parameters, for the same 500,000500{,}000 steps with the same hyperparameters, over 44 seeds (Appendix C.2, line 820). Only the input encoding changes: none, the true RWPE, or the learned RWPE. The RWPE predictor is frozen, so it adds no trainable parameters. It is a fixed function of the graph structure, like the algorithm that computes RWPE, and its pretraining uses only the structure, never the target. The comparison that supports our claim is between the true RWPE (0.050±0.0040.050 \pm 0.004) and the learned RWPE (0.051±0.0040.051 \pm 0.004): the same model, with two fixed encodings, gives the same result.

ZINC-250k is large and represents drug-like molecules well (Reviewer evwr). We agree that the RWPE experiment uses one dataset. But ZINC-250k has 250,000250{,}000 drug-like molecules, and it covers the usual topology of these molecules well: rings, chains and their combinations. Our structural statistics support this: ZINC-250k and PCQM4Mv2, which has 3.43.4 million molecules, give almost the same amenable fraction (99.38%99.38\% and 99.47%99.47\%) and almost the same tCRt_{\mathrm{CR}} (1111 and 1212, Table 1). RWPE is also mainly used on molecular tasks, and ZINC is its standard benchmark (Dwivedi et al., 2022). Finally, the general claim comes from the theory (Corollary 3), not from this experiment alone.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.