破解图神经网络读出层对称性瓶颈,提升图区分能力
Breaking Symmetry Bottlenecks in GNN Readouts
- 用群论证明线性读出必投影到对称不变子空间
- 新读出方法保留非平凡对称信息,可区分传统方法无法区分的图
- 仅替换读出层即显著提升模型性能,适合图学习研究者
图神经网络广泛用于结构化数据学习,但其区分非同构图的能力存在根本局限。本文揭示:这一限制不仅源于消息传递机制,更来自读出阶段的独立瓶颈。基于有限维表示理论,我们证明所有线性排列不变读出(如求和、平均池化)均通过Reynolds算子(群平均),将节点嵌入投影至置换作用的不动子空间,无论编码器多强,都会抹除所有非平凡的对称感知成分。这揭示了新的表达能力瓶颈,并给出了全局池化所保留或破坏内容的可解释刻画。为克服该坍塌,我们提出基于投影的不变读出,将节点表示分解为对称感知通道,以非线性不变统计量汇总,保持置换不变性的同时保留传统平均无法捕捉的信息。实验表明,仅更换读出层,固定编码器即可分离WL难解图对,并在多个基准上提升性能,证明读出设计是决定图神经网络表达力的关键且被低估的因素。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。