Efficient Curvature-aware Graph Network

• URL: http://arxiv.org/abs/2511.01443v1
• Date: Mon, 03 Nov 2025 10:51:58 GMT
• Title: Efficient Curvature-aware Graph Network
• Authors: Chaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li,
• Abstract summary: We propose a novel graph curvature measure--Effective Resistance Curvature--which quantifies the ease of message passing along graph edges.<n>We prove the low computational complexity of effective resistance curvature and establish its substitutability for Ollivier-Ricci curvature.
• Score: 8.665262442928217
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Dynamic Graph Structure Learning via Resistance Curvature Flow [8.07689343442439]
  Geometric Representation Learning aims to approximate the non-Euclidean topology of high-dimensional data through discrete graph structures.<n>Traditional static graph construction methods based on Euclidean distance often fail to capture the intrinsic curvature characteristics of the data manifold.<n>This paper proposes a novel geometric evolution framework: Resistance Curvature Flow (RCF)
  arXiv  Detail & Related papers  (2026-01-13T02:23:32Z)
• Curvature Learning for Generalization of Hyperbolic Neural Networks [51.888534247573894]
  Hyperbolic neural networks (HNNs) have demonstrated notable efficacy in representing real-world data with hierarchical structures.<n>Inappropriate curvatures may cause HNNs to converge to suboptimal parameters, degrading overall performance.<n>We propose a sharpness-aware curvature learning method to smooth the loss landscape, thereby improving the generalization of HNNs.
  arXiv  Detail & Related papers  (2025-08-24T07:14:30Z)
• Depth-Adaptive Graph Neural Networks via Learnable Bakry-'Emery Curvature [7.2716257100195385]
  Graph Neural Networks (GNNs) have demonstrated strong representation learning capabilities for graph-based tasks.<n>Recent advances on GNNs leverage geometric properties, such as curvature, to enhance its representation capabilities.<n>We propose integrating Bakry-'Emery curvature, which captures both structural and task-driven aspects of information propagation.
  arXiv  Detail & Related papers  (2025-03-03T00:48:41Z)
• Accelerated Evaluation of Ollivier-Ricci Curvature Lower Bounds: Bridging Theory and Computation [0.0]
  Curvature serves as a potent and descriptive invariant, with its efficacy validated both theoretically and practically within graph theory. We employ a definition of generalized Ricci curvature proposed by Ollivier, which Lin and Yau later adapted to graph theory, known as Ollivier-Ricci curvature (ORC) ORC measures curvature using the Wasserstein distance, thereby integrating geometric concepts with probability theory and optimal transport.
  arXiv  Detail & Related papers  (2024-05-22T02:44:46Z)
• Revealing Decurve Flows for Generalized Graph Propagation [108.80758541147418]
  This study addresses the limitations of the traditional analysis of message-passing, central to graph learning, by defining em textbfgeneralized propagation with directed and weighted graphs. We include a preliminary exploration of learned propagation patterns in datasets, a first in the field.
  arXiv  Detail & Related papers  (2024-02-13T14:13:17Z)
• DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing [72.70197960100677]
  Graph Structure Learning (GSL) plays an important role in boosting Graph Neural Networks (GNNs) with a refined graph. GSL solutions usually focus on structure refinement with task-specific supervision (i.e., node classification) or overlook the inherent weakness of GNNs themselves. We propose to study self-supervised graph structure-feature co-refinement for effectively alleviating the issue of over-squashing in typical GNNs.
  arXiv  Detail & Related papers  (2024-01-23T14:06:08Z)
• Mitigating Over-Smoothing and Over-Squashing using Augmentations of Forman-Ricci Curvature [1.1126342180866644]
  We propose a rewiring technique based on Augmented Forman-Ricci curvature (AFRC), a scalable curvature notation. We prove that AFRC effectively characterizes over-smoothing and over-squashing effects in message-passing GNNs.
  arXiv  Detail & Related papers  (2023-09-17T21:43:18Z)
• Graph Condensation for Inductive Node Representation Learning [59.76374128436873]
  We propose mapping-aware graph condensation (MCond) MCond integrates new nodes into the synthetic graph for inductive representation learning. On the Reddit dataset, MCond achieves up to 121.5x inference speedup and 55.9x reduction in storage requirements.
  arXiv  Detail & Related papers  (2023-07-29T12:11:14Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network [72.16255675586089]
  We propose an Adaptive Curvature Exploration Hyperbolic Graph NeuralNetwork named ACE-HGNN to adaptively learn the optimal curvature according to the input graph and downstream tasks. Experiments on multiple real-world graph datasets demonstrate a significant and consistent performance improvement in model quality with competitive performance and good generalization ability.
  arXiv  Detail & Related papers  (2021-10-15T07:18:57Z)
• Curvature Graph Neural Network [8.477559786537919]
  We introduce discrete graph curvature (the Ricci curvature) to quantify the strength of structural connection of pairwise nodes. We propose Curvature Graph Neural Network (CGNN), which effectively improves the adaptive locality ability of GNNs. The experimental results on synthetic datasets show that CGNN effectively exploits the topology structure information.
  arXiv  Detail & Related papers  (2021-06-30T00:56:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.