CS Paper Radar

A comparative exploration of Steinerberger curvature and resistance curvature in model and real-world complex networks

Madhumita Mondal, Priyank Vasu, Areejit Samal, Jürgen Jost

cs.SI ·submitted 2026-11-17 18:46 UTC · v1

Abstract

Discrete curvature extends the concept of curvature from continuous spaces to discrete structures such as graphs and networks. It provides a mathematical framework for characterising local and global network geometry, that offers insights into structural properties such as connectivity and clustering. In this study, we investigate Steinerberger curvature (SBC) and resistance curvature (RC) and examine their relationships with established graph curvature measures, namely Forman-Ricci, Augmented Forman-Ricci, and Ollivier-Ricci curvatures, a notion of scalar sectional curvature, as well as conventional vertex-based measures. A systematic comparative analysis is conducted across various synthetic network models and real-world networks, focusing on curvature distributions, correlations with structural measures, and the identification of structurally important vertices through network disintegration experiments based on global efficiency. Our results show that SBC generally exhibits weaker correlations with other measures. On the other hand, RC is strongly positively correlated with established discrete Ricci curvature measures, whereas it is predominantly negatively correlated with conventional vertex-based measures like degree and centrality-based measures. Furthermore, RC achieves a reduction in communication efficiency comparable to or faster than established Ricci curvature measures. These findings suggest that SBC captures structural characteristics that are largely distinct from those reflected by other measures, while RC exhibits distinct structural associations and shows significant potential for identifying vertices critical to network connectivity.

Comment
40 pages, 5 main figures, 3 supplementary figures, 1 main table, 17 supplementary tables

Closest papers

Nearest neighbours by meaning across the whole index.

Ollivier's Ricci Curvature on Complex-weighted Graphs

cs.SI math.MGphysics.soc-ph ·2026-08-10 ·Yu Tian, Eleanor Wiesler, Melanie Weber
similarity 0.67
Abstract · 32 pages, 11 figures

Understanding the geometry of complex networks is critical for effective modeling and analysis across domains. While discrete notions of Ricci curvature have emerged as powerful tools for characterizing both local and global network structure, existing formulations are largely confined to undirected networks with real-valued weights. This limits the use of curvature-based analysis of directional and complex-weighted relations that arise naturally in many applications, from social and biological systems to quantum and signal-processing networks. In this work, we introduce a principled extension of Ollivier's Ricci curvature to complex-weighted graphs, which encompasses directed graphs as a special case. We establish fundamental theoretical properties of this new notion, including relations to the magnetic Laplacian and combinatorial upper and lower bounds that relate curvature to cycle structure in local neighborhoods. We further develop computational methods for curvature estimation and demonstrate their utility in community detection on directed networks.

0.10

When Does Discrete Ricci Curvature Help? An Edge-Level Analysis of Curvature-Enhanced GCNs for PPI Prediction

cs.LG ·2026-11-16 ·Clara Joswig, Elham Gholamzadeh, Ghazal Mostofi, Nico Scherf
published similarity 0.61
Abstract · 15 pages, 6 figures, 9 tables. Accepted at the NeurIPS 2026 Workshop on Geometric Distributional Deep Learning

Curvature-enhanced graph convolutional networks (CGCN) incorporate Ollivier-Ricci curvature (ORC), grounded in optimal transport theory, into message passing, motivated by the claim that curvature-weighted edges alleviate "over-squashing" at structural bottlenecks. But does CGCN's improvement actually come from mitigating over-squashing? We investigate this on four real-world protein-protein interaction (PPI) datasets, comparing CGCN against a standard GCN at the level of individual edges rather than aggregate metrics alone. While CGCN improves aggregate AUC, AUPR, and F1 across all four datasets, this gain is concentrated almost entirely on low-degree edges, while performance on low-curvature (bottleneck) edges systematically degrades in three of four datasets, the opposite of what the over-squashing motivation predicts. Examining the learned edge-weight function directly, together with clustering-validity metrics, edge-distance ratios, and a layer-depth ablation across four depths, we find evidence for an alternative account: curvature-weighting sharpens the separation between clusters, which improves intra-cluster predictions at the cost of inter-cluster (bottleneck) ones. We test this account against topologically defined communities rather than the classification labels used elsewhere. Additionally, we offer practical guidance on when to prefer CGCN over standard GCN, depending on whether intra- or inter-cluster predictions matter most.

0.41

Curvature-Guided Sparsification for Graphs with Community Structure

cs.SI ·2026-10-28 ·Avin Kolahdooz, Jose Jairo Garcia, Sarah Percival
theory similarity 0.60
Abstract · 25 pages, 8 figures

Graph sparsification in large-scale networks often requires balancing structural accuracy and computational efficiency. Curvature-based methods, particularly Ollivier-Ricci curvature (ORC), have shown strong performance in identifying inter-community bridges, but their computational cost limits scalability. In this work, we propose a two-stage curvature-guided pipeline for graph sparsification with the goal of preserving community structure. We first use the Lower Ricci Curvature, a combinatorial lower bound of the ORC, to perform efficient edge filtering, substantially reducing graph size before applying the computationally intensive optimal-transport-based ORC curvature and Ricci flow. Results from empirical studies on synthetic and real-world datasets demonstrate that the combined LRC-ORC pipeline can achieve community-recovery accuracy comparable to ORC-only sparsification in terms of Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI), while reducing runtime on most evaluated benchmarks. Our findings suggest that integrating combinatorial and geometric curvature notions provides a computationally efficient and structurally principled framework for graph sparsification in complex networks.

0.20

Community Detection using the Edge Laplacian Dynamics vis-a-vis Ricci Flow

cs.SI math.DS ·2026-09-30 ·Pratibha Bhandari, Soumyendu Raha
similarity 0.55
Abstract

It has been found that utilizing the geometric properties of the graph dynamics can bring out crucial information of the data that a statistical analysis will not. The properties of Ricci flow bring out hidden dynamics of the data in the same way as decomposition of smooth manifolds. In this paper we explore an alternative to Ricci flow, where we find that we can bring out similar properties like it using a simpler and well defined Edge Laplacian to practice community detection in graphs. Moreover, the results obtained by the present approach show that a flow driven by the Edge Laplacian yields results similar to those of the Ricci flow. In contrast, computing the Forman-Ricci curvature requires looping over the adjacent edges, while computing Olivier-Ricci curvature involves the computation of Wasserstein distance and probability distribution associated with the graph nodes, making the Edge Laplacian approach computationally more efficient.

0.11

Geometric Flow enhanced Graph Coarsening

cs.AI ·2026-09-14 ·Chaoqun Fei, Guoxuan Li, Tinglve Zhou, Chuanqing Wang, Yangyang Li
similarity 0.55
Abstract

Recently, researchers have proposed a graph pooling operation, akin to the pooling process in conventional convolutional neural networks (CNN), aimed at reducing the computation cost of Graph convolutional neural networks (GCNNs). While most GCNN-based methods treat graph pooling as a node clustering problem and propose learning a cluster assignment matrix, existing clustering-based pooling methods tend to focus solely on the rough topology information of graphs, neglecting the exploitation of higher-order mutual connections among neighbors. In terms of message passing on graph, the ease of information passing on edges reflects the closeness between neighboring nodes, which significantly relies on the interconnectivity among neighbors. In this study, we address this gap by considering such local connection information and introducing a novel graph pooling method named RicciPool. We introduce discrete graph curvature, particularly Ollivier-Ricci curvature, as a measure of higher-order connectivity around an edge. Subsequently, we construct an Ollivier-Ricci flow formula to reweigh edge weights, leveraging the crucial information provided by Ricci curvature, particularly vital for extracting clusters in graphs. Building upon this foundation, we utilize the spectral clustering technique to learn a new cluster assignment matrix. Experimental results on multiple bioinformatics protein datasets and social networks underscore the effectiveness of our proposed method.

0.39

Criticality and universality in network dismantling

cs.SI physics.soc-phcond-mat.stat-mech ·2026-08-27 ·Lorenzo Cirigliano, Claudio Castellano, Minsuk Kim, Filippo Radicchi, Hanlin Sun
similarity 0.55
Abstract · 17 pages, 11 figures, 2 tables + supplemental material

Identifying the smallest set of elements whose removal dismantle a complex network, known as the network dismantling problem, is a fundamental task with many practical applications. Whereas network dismantling has been extensively studied over the past decade, most work has focused on developing efficient algorithms for large but finite networks. By contrast, the physics of the network dismantling process, namely how the network structural connectivity is affected by the removal of nodes or edges, remains largely unexplored in the thermodynamic limit. Here, we shed light on this understudied aspect of network dismantling by introducing an adaptive biased percolation process able to optimally dismantle a network. Through a systematic analysis of synthetic network models, we find that the proposed percolation process displays a universal phase transition, characterized by the abrupt and simultaneous disappearance of both the giant connected component and the largest 2-core, across networks with markedly different degree distributions. Simulations on real networks further support this universality, indicating that the physics of network dismantling is insensitive to a broad range of topological properties. Together, these results suggest that a topology-agnostic theory could be developed to explain the critical behavior of network dismantling.

0.26

Testing Central Structure for Complex Networks

cs.LG ·2026-10-11 ·Qilong Wu, Yuxiao Li, Simeng Zhang, Xinying Liu, Yan Liu +1 more
similarity 0.55
Abstract · 12 pages, 4 figures, submitted to Chaos, Solitons & Fractals

Centrality measures rank nodes even when the observed differences can be explained by ordinary structural variation. We therefore study a preceding question: whether a network contains a statistically identifiable central structure at all. We formulate this question as a network-level hypothesis testing issue using the adjacency spectral radius as the test statistic and estimate an empirical p-value from randomized networks generated under a specified null model. The framework is evaluated using G(N,M), Chung-Lu, and two implementations of the configuration model on simulated benchmarks and 55 real networks. Controlled experiments further vary the number and connection weights of designated central nodes while holding network size and density fixed. The results show a clear negative association between central-structure strength and the empirical p-value. They also demonstrate that rejection decisions depend substantially on the structural properties preserved by the null model: the detected network sets are not simply nested across models.

0.29

Theoretical relations between basic centrality measures in real-world networks

cs.SI math.CO ·2026-11-01 ·Mikhail Tuzhilin
similarity 0.54
Abstract

We establish new relationships among several fundamental measures of real-world networks, including the average clustering coefficient, the global clustering coefficient, the average shortest-path length and degree centrality, closeness centrality, betweenness centrality and ksi-centrality. We further develop the theory of $j$-neighborhood centrality, which encompasses degree centrality and ksi-centrality as special cases.

0.14