Breaking Symmetry Bottlenecks in GNN Readouts

• URL: http://arxiv.org/abs/2602.05950v1
• Date: Thu, 05 Feb 2026 18:08:13 GMT
• Title: Breaking Symmetry Bottlenecks in GNN Readouts
• Authors: Mouad Talhi, Arne Wolf, Anthea Monod,
• Abstract summary: Graph neural networks (GNNs) are widely used for learning on structured data, yet their ability to distinguish non-isomorphic graphs is fundamentally limited.<n>We show that an independent bottleneck arises at the readout stage.<n>We introduce projector-based invariant readouts that decompose node representations into symmetry-aware channels.
• Score: 0.764671395172401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Generalizing GNNs with Tokenized Mixture of Experts [75.8310720413187]
  We show that improving stability requires reducing reliance on shift-sensitive features, leaving an irreducible worst-case generalization floor.<n>We propose STEM-GNN, a pretrain-then-finetune framework with a mixture-of-experts encoder for diverse computation paths.<n>Across nine node, link, and graph benchmarks, STEM-GNN achieves a stronger three-way balance, improving robustness to degree/homophily shifts and to feature/edge corruptions while remaining competitive on clean graphs.
  arXiv  Detail & Related papers  (2026-02-09T22:48:30Z)
• Variational Bayesian Flow Network for Graph Generation [54.94088904387278]
  We propose Variational Bayesian Flow Network (VBFN) for graph generation.<n>VBFN performs variational lifting to a tractable joint Gaussian variational belief family governed by structured precisions.<n>On synthetic and molecular graph datasets, VBFN improves fidelity and diversity, and surpasses baseline methods.
  arXiv  Detail & Related papers  (2026-01-30T03:59:38Z)
• Resolving Node Identifiability in Graph Neural Processes via Laplacian Spectral Encodings [9.343292907600913]
  We provide theory for a Laplacian positional encoding that is invariant to eigenvector sign flips and to basis rotations within eigenspaces.<n>We prove that this encoding yields node identifiability from a constant number of observations and establish a sample-complexity separation from architectures constrained by the Weisfeiler-Lehman test.
  arXiv  Detail & Related papers  (2025-11-24T12:20:36Z)
• Learning Efficient Positional Encodings with Graph Neural Networks [109.8653020407373]
  We introduce PEARL, a novel framework of learnable PEs for graphs.<n>PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power.<n>Our analysis demonstrates that PEARL approximates equivariant functions of eigenvectors with linear complexity, while rigorously establishing its stability and high expressive power.
  arXiv  Detail & Related papers  (2025-02-03T07:28:53Z)
• Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectors [29.055130767451036]
  We propose a novel method exploiting Laplacian eigenvectors to generate stable and globally expressive graph representations. Our method deals with numerically close eigenvalues in a smooth fashion, ensuring its better robustness against perturbations.
  arXiv  Detail & Related papers  (2024-10-13T06:02:25Z)
• Parseval Convolution Operators and Neural Networks [16.78532039510369]
  We first identify the Parseval convolution operators as the class of energy-preserving filterbanks. We then present a constructive approach for the design/specification of such filterbanks via the chaining of elementary Parseval modules. We demonstrate the usage of those tools with the design of a CNN-based algorithm for the iterative reconstruction of biomedical images.
  arXiv  Detail & Related papers  (2024-08-19T13:31:16Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters [12.709930975472698]
  We consider the graph functional shifts as the symmetry group: the unitary operators that commute with the graph shift operator.<n>We propose nonlinear spectral filters (NLSFs) that are fully equivariant to graph functional shifts.<n>We demonstrate the superior performance of NLSFs over existing spectral GNNs in node and graph classification benchmarks.
  arXiv  Detail & Related papers  (2024-06-03T12:07:01Z)
• Neural Tangent Kernels Motivate Graph Neural Networks with Cross-Covariance Graphs [94.44374472696272]
  We investigate NTKs and alignment in the context of graph neural networks (GNNs) Our results establish the theoretical guarantees on the optimality of the alignment for a two-layer GNN. These guarantees are characterized by the graph shift operator being a function of the cross-covariance between the input and the output data.
  arXiv  Detail & Related papers  (2023-10-16T19:54:21Z)
• GRAFENNE: Learning on Graphs with Heterogeneous and Dynamic Feature Sets [19.71442902979904]
  Graph neural networks (GNNs) are built on the assumption of a static set of features characterizing each node in a graph. In this work, we address limitations through a novel GNN framework called GRAFENNE. We prove that GRAFENNE is at least as expressive as any of the existing message-passing GNNs in terms of Weisfeiler-Leman tests.
  arXiv  Detail & Related papers  (2023-06-06T07:00:24Z)
• Frame Averaging for Invariant and Equivariant Network Design [50.87023773850824]
  We introduce Frame Averaging (FA), a framework for adapting known (backbone) architectures to become invariant or equivariant to new symmetry types. We show that FA-based models have maximal expressive power in a broad setting. We propose a new class of universal Graph Neural Networks (GNNs), universal Euclidean motion invariant point cloud networks, and Euclidean motion invariant Message Passing (MP) GNNs.
  arXiv  Detail & Related papers  (2021-10-07T11:05:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.