Sparse graphs using exchangeable random measures

Francois Caron, Emily FoxOpenReview 2025 · OpenReview

TL;DR

This paper introduces a novel framework for modeling sparse networks by representing them as exchangeable random measures, overcoming a key limitation of traditional exchangeable graph models that are inherently dense. This new approach, based on Completely Random Measures (CRMs), allows for tunable sparsity and power-law degree distributions, while still retaining the desirable properties of exchangeability for statistical inference.

What Problem Does This Paper Address?

Statistical network modeling often relies on the assumption of "exchangeability," which means the order in which nodes are observed doesn't affect the graph's properties. This is a powerful assumption for simplifying models and enabling statistical inference. However, a fundamental result known as the Aldous-Hoover theorem states that if a graph's adjacency matrix is exchangeable, the graph must be either entirely empty or "dense" (meaning the number of edges grows quadratically with the number of nodes). This is a major problem because most real-world networks are sparse, with the number of edges growing much slower than quadratically. This paper addresses this critical gap by proposing a new way to define exchangeability for networks that allows for sparsity.

Methods

The authors shift from representing graphs as discrete adjacency matrices to representing them as continuous-space random measures on $\mathbb{R}^2$. They leverage the Kallenberg representation theorem, which provides a continuous-space counterpart to the Aldous-Hoover theorem for exchangeable random measures. The core of their approach involves using "Completely Random Measures" (CRMs), a flexible class of random measures. By carefully choosing the "Lévy measure" that defines the CRM, they can construct models that exhibit sparse graphs with power-law degree distributions. Specifically, infinite-activity CRMs lead to sparse graphs, while finite-activity CRMs lead to dense graphs. They also develop a scalable Hamiltonian Monte Carlo (HMC) algorithm for efficient posterior inference, which is crucial for analyzing large networks.

Datasets

The paper evaluates their model on a variety of real-world network datasets, including:

  • Facebook social circles (facebook107)
  • Political blogosphere (polblogs)
  • US airport connection network (USairport)
  • University of California, Irvine social network (UCirvine)
  • Yeast protein interaction network (yeast)
  • US power grid network (USpower)
  • IMDB actor collaboration network (IMDB)
  • Co-authorship networks (cond-mat1, cond-mat2)
  • Enron collaboration network (Enron)
  • Internet router network (internet)
  • World Wide Web network (www)

These datasets vary in size, ranging from a few hundred nodes to hundreds of thousands of nodes and millions of edges.

Key Insights and Ideas

  • Exchangeability without Density: The most significant insight is demonstrating that exchangeability, a desirable property for statistical modeling, does not necessarily imply dense graphs when applied to a continuous-space representation of networks. This breaks a long-standing theoretical barrier.
  • CRMs as a Flexible Tool: Completely Random Measures (CRMs) prove to be a powerful and flexible framework for generating sparse graphs with tunable properties. The choice of the Lévy measure within the CRM directly controls the sparsity and degree distribution of the resulting network.
  • Sparsity from Infinite Activity: The paper clearly links the sparsity of the generated graphs to the "infinite activity" property of the CRM's Lévy measure. This provides a theoretical handle on achieving sparsity.
  • Scalable Inference for Complex Models: The development of an efficient HMC algorithm is a key practical contribution, enabling the application of these sophisticated exchangeable sparse graph models to large, real-world datasets.

Key Results

  • The proposed model can generate sparse graphs with power-law degree distributions, a characteristic of many real-world networks.
  • The sparsity of the graph is directly controlled by the properties of the Lévy measure defining the CRM. Specifically, infinite-activity CRMs lead to sparse graphs.
  • For a specific class of CRMs (generalized gamma process), a single parameter ($\sigma$) can tune the graph from dense to sparse.
  • The HMC sampler demonstrates scalability, successfully analyzing networks with hundreds of thousands of nodes and millions of edges.
  • Empirical analysis on real-world datasets shows that the model can effectively capture network properties and distinguish between sparse and dense networks. For instance, the test for sparsity using the $\sigma$ parameter correctly identified sparse networks like Enron and WWW.

Limitations and Future Work

  • Community Structure: The authors acknowledge that their current model does not explicitly capture community structure or dense "spots" within the network. They suggest that incorporating inhomogeneous CRMs could be a direction for future work to address this.
  • Power-Law Cutoffs: For some very large networks, the model might underestimate the tail of the degree distribution, potentially due to the presence of power-law behavior with a cutoff, which is not explicitly modeled.
  • Stable Processes: The proof techniques for some results exclude stable processes (where $\tau=0$ and $\sigma \in (0,1)$), although the authors conjecture that graphs generated by these processes are also sparse.
  • Future Directions: The paper suggests future work could involve incorporating notions of community structure and node attributes into their generative framework.

Summary updated

Abstract

Statistical network modelling has focused on representing the graph as a discrete structure, namely the adjacency matrix. When assuming exchangeability of this array—which can aid in modelling, computations and theoretical analysis—the Aldous–Hoover theorem informs us that the graph is necessarily either dense or empty. We instead consider representing the graph as an exchangeable random measure and appeal to the Kallenberg representation theorem for this object. We explore using completely random measures (CRMs) to define the exchangeable random measure, and we show how our CRM construction enables us to achieve sparse graphs while maintaining the attractive properties of exchangeability. We relate the sparsity of the graph to the Lévy measure defining the CRM. For a specific choice of CRM, our graphs can be tuned from dense to sparse on the basis of a single parameter. We present a scalable Hamiltonian Monte Carlo algorithm for posterior inference, which we use to analyse network properties in a range of real data sets, including networks with hundreds of thousands of nodes and millions of edges.
BibTeX
@misc{caron2025sparse,
  author = {Francois Caron and Emily Fox},
  title = {{Sparse graphs using exchangeable random measures}},
  year = {2025},
  url = {https://openreview.net/forum?id=6jvbRrYYRW},
  howpublished = {OpenReview},
}
Figure