提出高效图曲率方法，计算速度远超传统方法。
Efficient Curvature-aware Graph Network
- 用有效电阻替代最优传输距离，降低计算开销。
- 在多个任务上性能媲美经典曲率，计算时间显著缩短。
- 适合大规模图神经网络应用，兼顾效率与几何表达能力。
图曲率为图神经网络提供几何先验，提升对复杂图结构的建模能力，尤其增强结构感知、鲁棒性与理论可解释性。现有方法中，Ollivier-Ricci曲率因强几何可解释性被广泛研究，能有效刻画节点间的局部几何分布，但其计算复杂度极高，难以应用于大规模图数据集。为此，本文提出一种新型图曲率度量——有效电阻曲率（Effective Resistance Curvature），通过节点对之间的有效电阻来衡量消息传递的难易程度，而非使用最优传输距离。该方法在保持相近几何表达能力的同时，显著提升计算效率。理论上，我们证明了有效电阻曲率具有低计算复杂度，并建立了其对Ollivier-Ricci曲率的可替代性。大量实验表明，该方法在多种GNN任务中表现接近经典曲率，同时大幅降低计算开销。
原文摘要 · Abstract (English)
Graph curvature provides geometric priors for Graph Neural Networks (GNNs), enhancing their ability to model complex graph structures, particularly in terms of structural awareness, robustness, and theoretical interpretability. Among existing methods, Ollivier-Ricci curvature has been extensively studied due to its strong geometric interpretability, effectively characterizing the local geometric distribution between nodes. However, its prohibitively high computational complexity limits its applicability to large-scale graph datasets. To address this challenge, we propose a novel graph curvature measure--Effective Resistance Curvature--which quantifies the ease of message passing along graph edges using the effective resistance between node pairs, instead of the optimal transport distance. This method significantly outperforms Ollivier-Ricci curvature in computational efficiency while preserving comparable geometric expressiveness. Theoretically, we prove the low computational complexity of effective resistance curvature and establish its substitutability for Ollivier-Ricci curvature. Furthermore, extensive experiments on diverse GNN tasks demonstrate that our method achieves competitive performance with Ollivier-Ricci curvature while drastically reducing computational overhead.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。