Curved Markov Chain Monte Carlo for Network Learning

John Sigbeku, Emil Saucan, Anthea Monod

Abstract

As network datasets grow in complexity and scale, traditional uniform sampling methods often fail to capture essential structural characteristics. This paper introduces a geometrically enhanced Markov Chain Monte Carlo (MCMC) framework that utilizes Graph Forman curvature to guide the sampling process. By biasing random walks toward regions of high curvature, the proposed methods achieve significantly faster convergence to key network statistics compared to traditional uniform sampling. Evaluations on social and biological networks demonstrate the efficacy of using intrinsic geometry to learn network structures efficiently.

Introduction

Analyzing massive networks, such as social media graphs or biological neural pathways, is often computationally prohibitive. Network sampling—creating a smaller, representative subnetwork—is the standard solution. However, traditional random walks often miss critical hubs or clusters because they do not account for the "shape" or "geometry" of the data. This research addresses whether the intrinsic geometry of a network, specifically its discrete curvature, can be used to guide sampling more effectively.

Methodology: Integrating Graph Forman Curvature

The core innovation lies in the application of Graph Forman curvature, a discrete measure that quantifies how "concentrated" or "flat" a network is at a specific point. In this context, curvature serves as a proxy for information flow: edges connecting highly connected hubs exhibit high absolute curvature, while edges in uniform regions have lower curvature.

Basic graph structures used to define discrete curvature.

The authors propose two distinct integration strategies:

  1. Edge-Based Approach (Explicit): This method modifies the transition probabilities of the Markov chain. Instead of uniform movement, the sampler is biased toward edges with higher absolute Forman curvature.
  2. Node-Based Approach (Implicit): Utilizing the Metropolis-Hastings algorithm, this approach targets a specific stationary distribution where the sampler spends more time on nodes with high curvature (normalized by degree).

Because Forman curvature is a local measure—requiring only information about a node and its immediate neighbors—the method is "semi-crawl-like," making it suitable for networks where the global map is not known upfront.

Experimental Evaluation

The researchers evaluated the curved MCMC samplers on two deterministic real-world networks: the Les Misérables interaction network (77 nodes) and the C. elegans neural network (306 nodes). These datasets represent different connectivity patterns, allowing for a robust test of the geometric sampling approach.

Visualization of sampling on the Les Misérables network (77 nodes).

Key Results and Insights

Performance was measured using the Mean Squared Error (MSE) between the sampled subnetwork's statistics and the true values of the full network. Key findings include:

  • Faster Convergence: Curved samplers consistently reached lower MSE values with fewer samples than the uniform base case.
  • Superiority in Local Metrics: The improvement was most pronounced when estimating local statistics such as node strength (weighted degree) and the clustering coefficient.
  • Centrality Dynamics: For Betweenness Centrality, the curved sampler provided an initial advantage, though its performance eventually converged with uniform sampling as the sample size increased.

Conclusion and Future Work

Curved MCMC sampling demonstrates that geometric information can significantly enhance the efficiency of network learning. While calculating curvature adds a minor computational overhead per iteration, the reduction in the total number of steps required for convergence offers a net gain in efficiency. Future research will focus on scaling these methods to million-node graphs and exploring alternative normalization strategies to further refine the sampling bias in weighted networks.

Summary updated

Abstract

We present a geometrically enhanced Markov chain Monte Carlo sampler for networks based on a discrete curvature measure defined on graphs. Specifically, we incorporate the concept of graph Forman curvature into sampling procedures on both the nodes and edges of a network explicitly, via the transition probability of the Markov chain, as well as implicitly, via the target stationary distribution, which gives a novel, curved Markov chain Monte Carlo approach to learning networks. We show that integrating curvature into the sampler results in faster convergence to a wide range of network statistics demonstrated on deterministic networks drawn from real-world data.
BibTeX
@inproceedings{sigbeku2021curved,
  author = {John Sigbeku and Emil Saucan and Anthea Monod},
  title = {{Curved Markov Chain Monte Carlo for Network Learning}},
  booktitle = {COMPLEX NETWORKS},
  year = {2021},
  doi = {10.1007/978-3-030-93413-2\_39},
}
Figure