通过群论构造新特征空间,解决图神经网络长程信息压缩问题。
Schreier-Coset Graph Propagation
- 用Schreier-陪集嵌入增强节点特征,不改变图结构
- 在标准数据集上性能媲美或超越扩增图基线
- 适合处理分层模块化图,低延迟低内存
图神经网络(GNN)在图结构数据上学习具有理论优势,但常受过挤压问题限制,即远距离节点信息被压缩到固定大小向量中。现有方法如图重连和抗瓶颈架构(如凯莱图与扩增图)虽缓解此问题,却带来可扩展性瓶颈。特别是基于SL(2,Z_n)的凯莱图虽具强理论性质,但节点数呈立方增长O(n³),导致内存开销高。本文提出施雷尔-陪集图传播(SCGP),一种群论增强方法,通过施雷尔-陪集嵌入丰富节点特征,不改变输入图拓扑。SCGP将无瓶颈连接模式嵌入紧凑特征空间,提升长程消息传递能力,同时保持计算效率。实验证明,SCGP在标准节点与图分类基准上表现媲美或优于扩增图与重连式GNN基线。尤其在处理分层与模块化图结构时,展现更低推理延迟、更好可扩展性与低内存占用,适用于实时及资源受限场景。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) offer a principled framework for learning over graph-structured data, yet their expressive capacity is often hindered by over-squashing, wherein information from distant nodes is compressed into fixed-size vectors. Existing solutions, including graph rewiring and bottleneck-resistant architectures such as Cayley and expander graphs, avoid this problem but introduce scalability bottlenecks. In particular, the Cayley graphs constructed over $SL(2,\mathbb{Z}_n)$ exhibit strong theoretical properties, yet suffer from cubic node growth $O(n^3)$, leading to high memory usage. To address this, this work introduces Schrier-Coset Graph Propagation (SCGP), a group-theoretic augmentation method that enriches node features through Schreier-coset embeddings without altering the input graph topology. SCGP embeds bottleneck-free connectivity patterns into a compact feature space, improving long-range message passing while maintaining computational efficiency. Empirical evaluations across standard node and graph classification benchmarks demonstrate that SCGP achieves performance comparable to, or exceeding, expander graph and rewired GNN baselines. Furthermore, SCGP exhibits particular advantages in processing hierarchical and modular graph structures, offering reduced inference latency, improved scalability, and a low memory footprint, making it suitable for real-time and resource-constrained applications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。