Does your graph learning task really require more expressive GNNs ?

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.