研究如何重连图结构来缓解GNN的过平滑与过挤压问题。
On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks
- 用谱间隙和导通率定义图优化目标，分别对抗过平滑与过挤压。
- 证明两种优化问题均为NP-hard，决策版本为NP-complete。
- 为图重连的近似算法提供理论依据，适合做GNN结构优化的研究者。
图神经网络（GNN）在深度架构下面临两大挑战：过平滑（节点表示趋于相同）和过挤压（远距离信息无法通过瓶颈传播）。两者均与图结构密切相关，由此引发一个问题：能否通过优化图拓扑来缓解这些问题？本文从理论上研究此类图结构优化的计算复杂性。将过平滑与过挤压的缓解分别建模为基于谱间隙和导通率的图优化问题。通过从最小二分划问题归约，证明了精确优化任一问题均为NP-hard，且其决策版本为NP-complete。结果为图重连在GNN优化中的根本限制提供了理论基础，支持实践中采用近似算法与启发式方法。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) face two fundamental challenges when scaled to deep architectures: oversmoothing, where node representations converge to indistinguishable vectors, and oversquashing, where information from distant nodes fails to propagate through bottlenecks. Both phenomena are intimately tied to the underlying graph structure, raising a natural question: can we optimize the graph topology to mitigate these issues? This paper provides a theoretical investigation of the computational complexity of such graph structure optimization. We formulate oversmoothing and oversquashing mitigation as graph optimization problems based on spectral gap and conductance, respectively. We prove that exact optimization for either problem is NP-hard through reductions from Minimum Bisection, establishing NP-completeness of the decision versions. Our results provide theoretical foundations for understanding the fundamental limits of graph rewiring for GNN optimization and justify the use of approximation algorithms and heuristic methods in practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。