PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Pratibha Bhandari, Soumyendu Raha

arXiv:2609.38988v1math.DScs.SI

TL;DR

Graph community detection can benefit from geometric graph dynamics, but Ricci-flow curvature calculations involve optimal transport or adjacent-edge computations. The paper uses edge-Laplacian-driven perturbations as an alternative and reports results similar to Ricci flow, with stronger performance on several stated comparisons.

  • Problem

    The paper seeks a simpler alternative to Ricci-flow-based graph community detection, whose curvature calculations involve Wasserstein distance and node probability distributions or looping over adjacent edges.

    Source: §I · p. 1, §VI · p. 9

  • Method

    The method applies heat-equation perturbations through an Edge Laplacian to edge weights, then removes the perturbation and analyzes weight dynamics for community detection.

    Source: §I · p. 2

  • Results

    The method produces results similar to Ricci flow, outperforms direct Louvain and Ricci flow on real-world datasets, except Polblog, and outperforms Ricci flow and traditional methods on the stated 500-node, two-community synthetic graph.

    Source: B. Experimental Results · p. 7, §VI · p. 8

  • Takeaways & Limitations

    The experiments support using the Laplacian as an alternative to discrete Ricci flow for certain graph datasets, with potential use in graph pruning or graph embeddings.

    Source: B. Experimental Results · p. 7, §VI · p. 8

    The evaluation uses only small graphs, and the authors identify large-scale implementation and a sustainable edge-surgery method as future work.

    Source: §VI · p. 9

Abstract

from arXiv · show

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.

I. INTRODUCTION

The introduction motivates geometry-aware graph analysis because many graph-learning approaches assume Euclidean or grid-like structure, while graph data may be non-Euclidean. It proposes an Edge-Laplacian perturbation approach to community detection as a simpler alternative to Ricci flow.

I. INTRODUCTION

  • Graph-learning methods commonly use node and edge properties for link prediction and classification, but often work best on Euclidean or grid-like data.The introduction motivates geometric approaches for graph applications including sensor networks, brain imaging, social networks, disease spread, and genetics.Source: §I · p. 1
  • Ricci flow and curvature methods provide geometric approaches to graph analysis, with prior applications including financial fragility, gene networks, wireless networks, and noisy graph matching.The introduction also names label propagation, random walks, edge-betweenness optimization, and modularity as traditional community-detection methods.Source: §I · pp. 1–2
  • The paper uses Edge-Laplacian-driven edge perturbations to study changing edge weights and pursue Ricci-flow-like results for graph community detection.It removes the perturbation before analyzing the resulting edge-weight dynamics.Source: §I · p. 2

1) Diffusion as the Fundamental Dynamical Process:

2) Manifolds as Continuous Geometric Domains:

The paper describes manifolds as locally Euclidean spaces that can be globally curved or topologically complex. It introduces differential operators that support descriptions of functions and flows on these domains.

2) Manifolds as Continuous Geometric Domains:

  • A manifold may be globally curved or topologically complex while locally resembling Euclidean space; a smooth manifold has neighborhoods homeomorphic to R^d.Its tangent spaces provide local linear approximations, and together form the tangent bundle.Source: 2) Manifolds as Continuous Geometric… · p. 2
  • A Riemannian metric equips tangent spaces with inner products, allowing intrinsic distances, angles, and volumes to be measured.Metric-determined properties are intrinsic, while properties depending on a particular embedding are extrinsic.Source: 2) Manifolds as Continuous Geometric… · p. 2

3) Fields and Differential Operators on Manifolds:

  • On manifolds, differentiation is defined locally; the gradient and its formal adjoint combine to form the Laplace–Beltrami operator.Tangent vector fields describe flows of material or information, and the text also introduces the Dirichlet energy as a measure of smoothness.Source: 3) Fields and Differential Operators… · pp. 2–3

4) Graphs as Discrete Analogues of Manifolds:

The paper treats weighted graphs as discrete geometric spaces, with vertex and edge functions serving as counterparts to continuous fields. Graph gradient and divergence operators lead to a graph Laplacian.

4) Graphs as Discrete Analogues of Manifolds:

B. Discrete Ricci Flow:

The section presents discrete Ricci flow as an edge-reweighting process informed by curvature and optimal transport. It connects vertex probability measures and Wasserstein distance to Ollivier-Ricci curvature and describes threshold-based community extraction.

B. Discrete Ricci Flow:

1) Ricci curvature and Optimal transportation:

  • Optimal transport seeks a low-cost transport plan between probability measures, and Wasserstein distance is the resulting optimal transport cost when cost is metric distance.The passage distinguishes Monge's transport-map formulation from Kantorovich's transport-plan formulation.Source: 1) Ricci curvature and Optimal… · p. 3

3) Ollivier Ricci curvature on general metric spaces.:

4) Ricci flow on graphs.:

The paper motivates edge-perturbation dynamics as a simpler way to reproduce Ricci flow’s community-separating behavior. Forman–Ricci curvature is defined on weighted-graph edges, with curvature signs linked to local connectivity and bottlenecks.

C. Forman–Ricci curvature.

  • Forman–Ricci curvature is defined on weighted-graph edges; positive curvature indicates locally dense connectivity, while negative curvature reflects bottlenecks or bridge-like structures.Source: C. Forman–Ricci curvature · p. 4

III. MOTIVATION AND CONTRIBUTIONS

  • The proposed dynamics use edge-weight perturbations and the Edge Laplacian to seek Ricci-flow-like curvature smoothing without explicitly computing Ricci curvature.The edge perturbation is associated with the graph edge, and the Edge Laplacian is the operator used in the analogous dynamics.Source: §III · p. 4
  • Ricci flow updates edge weights using graph Ricci curvature, while the proposed hypothesis assigns structural meaning to perturbations: intra-community edges contract and inter-community edges receive negative or constrained perturbations.The paper investigates whether this reproduces Ricci flow’s community-separating behavior.Source: §III · p. 4

IV. PROPOSED ALGORITHM

The proposed algorithm evolves edge perturbations with an Edge Laplacian and iteratively updates edge weights. It uses the lower Hodge 1-Laplacian when there are no higher-dimensional simplices.

A. Hodge 1-Laplacian

  • The Hodge 1-Laplacian acts on edge flows and models interactions through shared vertices and triangles, distinguishing gradient, curl, and harmonic components.Source: A. Hodge 1-Laplacian · p. 4

B. Edge-Based Flow Dynamics

  • The algorithm evolves edge perturbations with an irrotational Edge Laplacian and uses the normalized lower Hodge 1-Laplacian when higher-dimensional simplices are absent.The edge and vertex weights enter the stated flow equation through the incidence matrix and weight vectors.Source: B. Edge-Based Flow Dynamics · pp. 4–5
  • Discretizing the flow yields iterative edge-weight updates, allowing local perturbations to be tracked as they reshape the global graph structure.The proposed algorithm replaces Ricci curvature with the Edge Laplacian as the diffusion operator.Source: B. Edge-Based Flow Dynamics · p. 5
  • Figure 1 compares a tree, an infinite graph, and a complete graph by their curvature patterns, and its caption says Laplacian dynamics produce results similar to Ricci flow.Source: Figure 1 · p. 5

C. Edge Laplacian: Definition and Spectral Properties

The paper defines a weighted Edge Laplacian acting on edge functions, with positive diagonal weight matrices. Under symmetric normalization, the operator is self-adjoint in the standard Euclidean inner product.

C. Edge Laplacian: Definition and Spectral Properties

1) Self-Adjointness:

  • With symmetric normalization, the Edge Laplacian is self-adjoint with respect to the standard Euclidean inner product.The paper notes that the operator is symmetric and therefore self-adjoint in the finite-dimensional vector space.Source: 1) Self-Adjointness · p. 5

2) Positive Semidefiniteness:

The Edge Laplacian is positive semidefinite, and its kernel consists of weighted harmonic edge flows corresponding to divergence-free flows in discrete Hodge theory.

2) Positive Semidefiniteness:

3) Kernel and Structural Interpretation:

D. Intrinsic Stability of the Edge Heat Equation

The edge heat equation is stable through the edge Laplacian’s operator properties, without requiring a curvature lower bound. Its flow is exponentially stable on the orthogonal complement of the Laplacian kernel.

D. Intrinsic Stability of the Edge Heat Equation

  • The negative edge Laplacian generates a strongly continuous contraction semigroup on the edge-space ℓ2 domain.The theorem also gives an estimate for solutions in the orthogonal complement of ker(L).Source: D. Intrinsic Stability of the Edge… · p. 6
  • On ker(L)⊥, the edge heat flow is exponentially stable, and its stability estimate remains valid for sufficiently small perturbations.The spectral gap persists under those perturbations.Source: D. Intrinsic Stability of the Edge… · p. 6
  • The proposed operator is a weighted, normalized lower Hodge 1-Laplacian acting on edge quantities, reducing to MMᵀ without higher-dimensional simplices or weights.This contrasts with the Hodge 0-Laplacian-like Beltrami operator, which acts on node features.Source: D. Intrinsic Stability of the Edge… · p. 6
  • Stability holds independently of curvature interpretation and requires no explicit curvature lower bound, following from positivity and self-adjointness of the operator.The framework does not impose a curvature bound to ensure stability.Source: D. Intrinsic Stability of the Edge… · p. 6

V. RESULTS

The experiments compare edge-Laplacian community detection with Ricci flow and Louvain across real-world networks and a synthetic graph. The reported results are broadly similar to Ricci flow, with faster convergence and stronger performance in specified settings.

1) Karate club Network[27]:

  • The Karate Club network represents members as nodes and their connections as edges; its two classes formed after a conflict among members.Source: 1) Karate club Network[27] · p. 6

2) Football Network[23] :

  • The Football network records Division I game matchups and is partitioned into 12 conferences, with within-conference matches defining the community idea.Source: 2) Football Network[23] · p. 6

3) Political blogs network[28] :

4) Email-EU-core network[29]:

B. Experimental Results

  • 3–5 iterations produced good results, compared with more than 50 iterations for discrete Ricci flow; cutoffs were selected by best ARI.The authors updated edge weights, examined weight histograms, removed edges above a cutoff, and applied Louvain.Source: B. Experimental Results · p. 7
  • Across datasets, the method is similar to Ricci flow, outperforms Louvain and Ricci flow on real-world data except Polblog, and beats both on a 500-node, 2-community synthetic graph.The authors suggest graph pruning or graph embeddings in neural-network dynamics as possible uses.Source: B. Experimental Results · p. 7
  • The authors present the edge-Laplacian approach as a simpler, more computationally efficient alternative for capturing curvature dynamics.They contrast it with complex, computationally expensive algorithms.Source: B. Experimental Results · p. 7

C. Computational efficiency

The Edge-Laplacian flow has linear per-iteration cost for calculating the edge Laplacian, compared with the higher cost of Ricci-flow methods based on optimal transport. Experiments describe ARI evaluations on model networks, SBM graphs, and varying cutoff thresholds; the conclusion presents the method as an alternative for certain graph datasets while noting that the tested graphs were small.

C. Computational efficiency

  • O(m) per iteration for calculating the edge Laplacian, versus O(m d̄^3) for Ollivier-Ricci flow; the overall method is approximately O(TKm).The paper attributes practical speedups to this reduction; K is treated as a small constant independent of graph size.Source: C. Computational efficiency · p. 7
  • The model-network evaluation measures Edge-Laplacian community-detection accuracy using ARI.The supplied figure caption gives the metric and scope but no result values.Source: Figure 2 · p. 7
  • The SBM evaluation considers 500 nodes in two equal communities, varying p_inter/p_intra with p_intra fixed at 0.15 and measuring accuracy by ARI.The supplied caption specifies the evaluation setup, not comparative values.Source: Figure 3 · p. 8
  • The analysis plots ARI behavior across five iterations while testing 100, 600, and 1,000 equally discretized cutoff values in [0, 1] for karate club, football, and polblog graphs, respectively.Source: Figure 4 · p. 8

VI. CONCLUSION

  • The conclusion describes the Laplacian as an alternative to discrete Ricci flow for certain graph datasets, but the considered datasets are small and large-scale implementation remains future work.It also proposes exploring threshold-based surgery instead of Louvain and further real-world applications.Source: §VI · pp. 8–9

Related papers

Loading 2609.38988v1…