CS Paper Radar

Curvature-Guided Sparsification for Graphs with Community Structure

Avin Kolahdooz, Jose Jairo Garcia, Sarah Percival

cs.SI ·submitted 2026-10-28 19:06 UTC · v1
theory

Abstract

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.

Comment
25 pages, 8 figures

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.68
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

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.67
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

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.64
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.38

Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks

cs.LG ·2026-09-25 ·Siddhartha Shankar Das, Sai Karthik Navuluru, S M Ferdous, Ryan A. Rossi, Baris Coskunuzer +5 more
code/data similarity 0.61
Abstract

Graph neural networks (GNNs) rely on message passing over graph edges, making their computational and memory costs strongly dependent on graph density. Graph sparsification offers a natural way to reduce these costs, but removing edges indiscriminately can distort important communication structure and degrade predictive performance. We introduce Scaffold, a topology-based, unsupervised graph sparsification framework derived from support graph theory preconditioners. Scaffold explicitly controls two complementary structural quantities: dilation, which measures the length of rerouting paths induced by removed edges, and congestion, which measures how strongly these rerouted paths concentrate on the retained support. By jointly controlling dilation and congestion, Scaffold preserves short communication paths while avoiding structural bottlenecks. To our knowledge, Scaffold is the first scalable GNN sparsification framework to use a joint supporting-path dilation-congestion criterion. Across 19 homophilic and heterophilic benchmarks spanning small to large graphs, Scaffold achieves the best aggregate rank among the evaluated sparsification and related methods. Using only 10%-50% of the original edges per sparse support, Scaffold recovers or closely approaches full-graph GNN performance while using less than half the memory of full-graph training and reducing end-to-end training time, including sparsification overhead. We provide an open-source software package at https://github.com/siddhartha047/Scaffold.

0.25

Geometric Flow enhanced Graph Coarsening

cs.AI ·2026-09-14 ·Chaoqun Fei, Guoxuan Li, Tinglve Zhou, Chuanqing Wang, Yangyang Li
similarity 0.61
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

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

cs.SI ·2026-11-17 ·Madhumita Mondal, Priyank Vasu, Areejit Samal, Jürgen Jost
similarity 0.60
Abstract · 40 pages, 5 main figures, 3 supplementary figures, 1 main table, 17 supplementary tables

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.

0.46

SynCo: Synthetic Community-Aware Attributed Graph Generator for Graph Neural Network Benchmarking

cs.SI cs.LG ·2026-09-09 ·Guilherme Henrique Messias, Mariana Caravanti de Souza, Sylvia Iasulaitis, Alan Demétrius Baria Valejo
benchmark similarity 0.58
Abstract · 15 pages

Graph Neural Networks (GNNs) are powerful models for handling attributed graphs in tasks such as classification, link prediction, and community detection, as they enable the aggregation of information from both structural and semantic sources. However, progress in community detection is hindered by the lack of high-quality datasets, since ground-truth community labels are often unavailable and most algorithms proposed in recent literature rely on the same benchmark datasets for model training and evaluation. To address this issue, attributed random graph generators are commonly employed to create synthetic graphs for assessing the strengths and limitations of GNN-based models. Nevertheless, most existing generators rely heavily on power-law degree distributions, despite recent evidence indicating that scale-free networks are rare, particularly in social network contexts. Moreover, state-of-the-art attributed graph generators provide limited flexibility, as they do not allow users to construct communities with varying densities, degree distributions, and sub-community structures. To overcome these limitations, we introduce the Synthetic Community-Aware Attributed Graph Generator (SynCo), a graph generation algorithm that allows users to control the node degree distribution and sub-community structure. We evaluate SynCo across three different tasks: graph mimicking, hyperparameter evaluation, and node clustering tuning. The results show that our model outperforms state-of-the-art approaches in synthetic graph generation and data augmentation, while preserving the original distributions of duplicated and augmented datasets, as confirmed by statistical tests well know in literature. We also demonstrate the ability of SynCo to generate nodes in large scale, up to 2.1 million nodes.

0.13

Discretization-free exact recovery in geometric community detection

cs.SI math.PR ·2026-08-23 ·Maarten Hoeneveld, Moritz Otto, Raphaël Sala
theory similarity 0.56
Abstract · 30 pages, 2 figures

Geometric community detection seeks to recover latent communities in networks where connectivity depends jointly on community structure and continuous spatial geometry. Existing exact-recovery approaches typically discretize the underlying space, which can impose restrictive structural assumptions on the connectivity functions. We develop a polynomial-time, discretization-free algorithm for exact recovery in the Geometric Hidden Community Model (GHCM), operating directly on the continuous geometry. Our method succeeds even when connectivity functions coincide on a nontrivial portion of their visibility range and when two communities can be distinguished only through their connectivity to a third community. We prove exact recovery under these weaker conditions and provide experiments showing that the algorithm succeeds beyond the theoretically guaranteed regime.

0.23