用双随机矩阵替代传统图卷积中的拉普拉斯矩阵,提升多跳邻近与局部中心性建模。
Beyond the Laplacian: Doubly Stochastic Matrices for Graph Neural Networks

- 提出基于修正拉普拉斯逆的双随机矩阵,编码连续多跳邻近关系。
- 通过截断尼曼级数实现 $O(K|E|)$ 复杂度,避免 $O(n^3)$ 精确求逆。
- 引入残差质量补偿机制,严格恢复行随机性,适用于异质图与图注意力模型。
图神经网络通常依赖标准拉普拉斯矩阵或邻接矩阵进行结构消息传递。本文将传统拉普拉斯矩阵替换为由修正拉普拉斯逆导出的双随机图矩阵(DSM),以自然地编码连续多跳邻近性和严格的局部中心性。为克服精确矩阵求逆带来的 $O(n^3)$ 不可处理复杂度,首先采用截断尼曼级数可扩展地近似 DSM,构成所提 DsmNet 基础。此外,由于代数截断导致概率质量泄漏,引入 DsmNet-compensate:该变体具备数学严谨的残差质量补偿机制,解析地将截断尾部质量重新注入自环,严格恢复行随机性与结构主导性。理论与实证分析表明,解耦架构在 $O(K|E|)$ 时间内高效运行,并通过控制狄利克雷能量衰减有效缓解过平滑问题,在同质基准上提供稳健验证。最后,建立 DSM 在异质拓扑上的理论边界,并证明其作为图变换器的连续结构编码的通用性。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) conventionally rely on standard Laplacian or adjacency matrices for structural message passing. In this work, we substitute the traditional Laplacian with a Doubly Stochastic graph Matrix (DSM), derived from the inverse of the modified Laplacian, to naturally encode continuous multi-hop proximity and strict local centrality. To overcome the intractable $O(n^3)$ complexity of exact matrix inversion, we first utilize a truncated Neumann series to scalably approximate the DSM, which serves as the foundation for our proposed DsmNet. Furthermore, because algebraic truncation inherently causes probability mass leakage, we introduce DsmNet-compensate. This variant features a mathematically rigorous Residual Mass Compensation mechanism that analytically re-injects the truncated tail mass into self-loops, strictly restoring row-stochasticity and structural dominance. Extensive theoretical and empirical analyses demonstrate that our decoupled architectures operate efficiently in $O(K|E|)$ time and effectively mitigate over-smoothing by bounding Dirichlet energy decay, providing robust empirical validation on homophilic benchmarks. Finally, we establish the theoretical boundaries of the DSM on heterophilic topologies and demonstrate its versatility as a continuous structural encoding for Graph Transformers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。