Source
Xu et al. (2019), LIT-580. Read as NOTE-319.
The account
A message-passing layer maps each node’s own state and the multiset of its neighbors’ states to a new state. If two nodes get the same 1-WL color after k rounds, no k-layer GNN can tell them apart, because each layer sees no more than a WL refinement does. The bound is achieved when every step is injective. Sum with an MLP is (Lemma 5, Corollary 6). Mean is not: two neighborhoods with the same feature proportions collide. Max is not either: the multiplicities vanish.
The bound and the injectivity argument are LIT-580’s, which also put them to a test: training accuracy ranks sum–MLP above sum with one layer above the mean and max variants (Figure 4), and on REDDIT-BINARY and MULTI-5K with no node features GIN-0 reaches 92.4 and 57.5 while the mean variants sit at chance, 50.0 and 20.0.
What it explains
- Why sum–MLP GNNs fit training sets that mean and max variants underfit
- Why mean-aggregation GNNs are at chance on featureless Reddit graphs, where every neighborhood has the same proportions
- Why adding node degree as a feature partly rescues mean aggregation
Where it stops
- Distinguishability, not generalization. With informative features, aggregator choice matters little in the paper’s own tables
- 1-WL is itself limited. It cannot count cycles or tell some regular graphs apart. Positional encodings and higher-order GNNs address that, outside this account