Efficient Curvature-aware Graph Network

Chaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li · 2025

Read Efficient Curvature-aware Graph Network by Chaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01443.txt.

Introduction

Chaoqun Fei and colleagues give graph neural networks a cheaper sense of edge bending. The curvature of a graph's edges tells a network how information can flow, and the classic Ollivier-Ricci version is meaningful but far too expensive to compute on large graphs.

Their stand-in, effective resistance curvature, measures how easily messages pass along an edge using the electrical resistance between its endpoints instead of an optimal transport distance. They prove the new measure's low computing cost and that it can stand in for the Ollivier-Ricci version. Across diverse graph learning tasks, networks using effective resistance curvature matched the results of the classical measure while sharply cutting the computing overhead, making geometric priors usable at scale.

Catalog record

CREATORChaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-01443

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Curvature-aware Graph Network Thanks: C.Q. Fei and T.L. Zhou are with the School of Artificial Intelligence, South China Normal University, Foshan 528225, China (e-mail: [email protected]; [email protected]) Thanks: T.Y. Hao is with the School of Computer Science, South China Normal Univerisity, Guangzhou 510631, China (e-mail: [email protected]) Thanks: Y.Y. Li is with the State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China (e-mail: [email protected]) (Corresponding author: Yangyang Li.) Chaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li 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. I Introduction Graph Neural Networks (GNNs) are a class of deep learning models specifically designed to process graph-structured data [ 2 ] . Unlike traditional neural networks, GNNs are capable of effectively capturing the relationships between nodes and the global structural information of the graph [ 3 ] . Through a message-passing mechanism, GNNs allow each node to aggregate information from its neighbors, gradually updating its own representation [ 1 ] . This aggregation process can be iterated multiple times, enabling the network to learn deeper, more abstract features [ 4 ] [ 1 ] . Due to their flexibility and powerful representational capabilities, GNNs have become an important research direction in machine learning and data mining. Key tasks include node classification [ 7 ] , edge classification [ 6 ] [ 8 ] , and graph classification. Additionally, GNNs can be employed for graph generation [ 9 ] , creating new graph structures; graph regression, predicting numerical attributes of graphs or nodes; and graph embedding [ 10 ] , which maps graph data to a lower-dimensional space for more efficient analysis. These capabilities make GNNs highly applicable in diverse domains, including social networks [ 18 ] , recommendation systems, biological network analysis, and knowledge graphs. However, similar to other deep learning models, Graph Neural Networks (GNNs) face significant challenges in terms of interpretability. Due to their ”black-box” nature, understanding and explaining the decision-making process of GNNs has become a key area of research. First, the complexity of the message-passing mechanism represents a major obstacle. The representation at each layer is influenced by many neighboring nodes, making it difficult to intuitively grasp the model’s reasoning, such as the occurrence of ”Over-smoothing” [ 11 ] and ”Over-squashing” phenomena [ 12 ] . Second, the non-Euclidean structure of graph introduces additional complexity. Graphs intricate non-grid structures and the complex interactions between topology and node features challenge traditional interpretation methods [ 5 ] . To address these challenges, researchers have focused on analyzing the influence of neighboring nodes on the final representation. For example, Graph Attention Networks (GATs) [ 13 ] provide interpretability by using attention weights to highlight the interactions between nodes. By analyzing attention scores across different edges, it becomes possible to identify which edges most significantly impact the final prediction. However, since the attention matrix is learned during model optimization, it provides only a limited degree of interpretability. For more general GNN models, efforts have also been made to incorporate the non-Euclidean geometric structure of the graph, quantify relationships between nodes and their local neighbors, and track the evolution of the learning process [ 5 ] . These approaches offer new insights into the decision-making process of GNNs and have accelerated the development of interpretable graph neural networks. Currently, Ollivier-Ricci curvature [ 19 ] , as a type of discrete non-Euclidean graph structure, is widely applied in graph representation learning [ 14 ] . Rooted in the concept of abstract Ricci curvature, it reflects the geometric and topological properties of graphs. Researchers have used Ollivier-Ricci graph curvature to study the ”Over-smoothing” and ”Over-squashing” phenomena in GNNs [ 26 ] . They found that positive curvature on graph edges is related to the ”Over-smoothing” phenomenon, while negative curvature is associated with ”Over-squashing” [ 27 ] [ 28 ] . In geometry, the edge curvature of a graph can be interpreted as the degree of variation in the way nodes are connected, quantifying changes in the adjacency matrix of the graph, such as the addition or removal of edges, or changes in edge weights. Ollivier-Ricci curvature primarily measures edge variation by considering the Wasserstein distance between nodes and their probability distributions. Based on Wasserstein distance, it assesses the relative positions and similarities between nodes, reflecting the geometric characteristics of the graph. Locally, Ollivier-Ricci curvature can serve as an indicator of whether the region is ”flat.” Positive curvature suggests an outward bulge, reflecting stronger inter-node connections and revealing cluster-like structures, which can contribute to ”over-smoothing” in GNNs. In contrast, negative curvature indicates an inward concavity, pointing to weaker connections between nodes and highlighting bottleneck structures, thereby helping to explain the phenomenon of ”over-squashing”. Although Ollivier-Ricci curvature has shown many advantages in graph analysis and representation learning, it also faces several challenges that limit its application in the field of graph representation learning: 1. High computational cost: The computation of Ollivier-Ricci curvature depends on evaluating the probability distributions of nodes and Wasserstein distance, which can lead to significant computational costs, especially in large-scale graphs. This issue becomes more pronounced when dealing with complex graphs. 2. Increased model complexity: Incorporating Ollivier-Ricci curvature into models like Graph Neural Networks (GNNs) can considerably increase model complexity, which may affect both the interpretability and debug ability of the model. To address this challenge, we introduce a novel and efficient graph curvature concept- Effective Resistance Curvature - for Graph Neural Network [ 29 ] . This method models the graph as an electrical circuit, where resistance reflects the ease or difficulty of current flow, thereby quantifying the connectivity between edges. We demonstrate that the proposed resistance curvature not only captures the geometric structure of edges in a manner consistent with Ollivier-Ricci curvature, but also significantly reduces computational complexity, making it particularly suitable for large-scale graph applications. From the perspective of message passing in Graph Neural Network, we analogize information to electric current, likening the propagation of messages across the graph to the flow of current in a circuit. In high-curvature regions, nodes are more densely interconnected, analogous to a network with multiple parallel pathways that exhibit lower effective resistance, thereby facilitating the smooth flow of current—or information. In contrast, low-curvature regions correspond to higher effective resistance, which impedes current flow. This electrical model provides an alternative yet equivalent representation of

Read the complete text