Breaking Symmetry Bottlenecks in GNN Readouts
This addresses a fundamental limitation in GNN expressivity for graph learning tasks, offering a novel solution to improve model performance.
The paper identified a previously unrecognized expressivity bottleneck in GNNs at the readout stage, where linear permutation-invariant readouts erase symmetry-aware information, and introduced projector-based invariant readouts that improve performance, enabling separation of WL-hard graph pairs and boosting benchmarks.
Graph neural networks (GNNs) are widely used for learning on structured data, yet their ability to distinguish non-isomorphic graphs is fundamentally limited. These limitations are usually attributed to message passing; in this work we show that an independent bottleneck arises at the readout stage. Using finite-dimensional representation theory, we prove that all linear permutation-invariant readouts, including sum and mean pooling, factor through the Reynolds (group-averaging) operator and therefore project node embeddings onto the fixed subspace of the permutation action, erasing all non-trivial symmetry-aware components regardless of encoder expressivity. This yields both a new expressivity barrier and an interpretable characterization of what global pooling preserves or destroys. To overcome this collapse, we introduce projector-based invariant readouts that decompose node representations into symmetry-aware channels and summarize them with nonlinear invariant statistics, preserving permutation invariance while retaining information provably invisible to averaging. Empirically, swapping only the readout enables fixed encoders to separate WL-hard graph pairs and improves performance across multiple benchmarks, demonstrating that readout design is a decisive and under-appreciated factor in GNN expressivity.