A Consistent Histogram Estimator for Exchangeable Graph Models

Stanley H. Chan, Edoardo M. Airoldi

Introduction

As social and biological networks grow in complexity, traditional parametric models (like the Stochastic Block Model) often struggle to fit the data accurately. To address this, researchers have increasingly turned to Exchangeable Graph Models (ExGM). These models represent a graph as a sample drawn from a continuous 2D function known as a graphon.

This paper introduces the Sorting-And-Smoothing (SAS) algorithm, a computationally efficient and provably consistent method for estimating these underlying graphons. By combining empirical degree sorting with total variation minimization, the authors achieve a mean squared error (MSE) that vanishes as the network grows, outperforming existing methods in both accuracy and speed.

The Challenge of Estimating Graphons

Estimating a continuous graphon from a single, discrete observed graph is notoriously difficult due to two primary bottlenecks:

  1. Identifiability: Node labels in a network are arbitrary. Two identical underlying graph structures might appear completely different in their adjacency matrix forms simply because the nodes were indexed differently. Finding a "canonical" version to compare against is mathematically challenging.
  2. Scalability: Many existing consistent estimators are computationally "heavy." Methods involving Markov Chain Monte Carlo (MCMC) sampling or complex moment matching are often impractical for large-scale, real-world networks.
Illustration of the identifiability problem: different node orderings produce different adjacency matrices for the same underlying structure.

The Sorting-And-Smoothing (SAS) Algorithm

To overcome these challenges, the authors propose the SAS algorithm, which operates in two intuitive stages:

  1. Sorting: To handle the identifiability problem, the algorithm calculates the empirical degree of every node (its total number of connections). It then rearranges the adjacency matrix so that nodes are ordered by increasing degree. Because a node's degree is often a strictly monotonic function of its latent position in many graphons, sorting by degree effectively "unscrambles" the random node indexing.
  2. Smoothing: The sorted adjacency matrix is partitioned into a 2D histogram of blocks. To remove the noise inherent in a single random sample, the authors apply Total Variation (TV) minimization. Borrowed from image processing, this technique treats the adjacency matrix as a noisy image, seeking a piecewise-smooth surface that fits the histogram while penalizing unnecessary "jumps" or noise.
The SAS algorithm pipeline: from the raw observed graph to the sorted graph, histogram, and finally the smoothed estimated graphon.

By leveraging concepts from compressed sensing, the authors prove that if the true graphon has a sparse gradient (meaning it is mostly smooth with some sharp transitions), the SAS estimator is statistically consistent.

Key Results and Performance

The paper evaluates the SAS algorithm using both synthetic graphons (ranging from low-rank to high-rank models) and real-world networks, such as the ca-AstroPh collaboration network ($\approx 18,000$ nodes) and the soc-Epinions1 social network ($\approx 75,000$ nodes).

  • Theoretical Consistency: The authors mathematically prove that the MSE of the SAS estimator is $O(\frac{\log n}{n})$. As the number of nodes $n$ goes to infinity, the error reliably drops to zero.
  • Superior Accuracy: In simulations across 10 different graphon types, SAS consistently achieved a lower MSE than competing methods like Universal Singular Value Thresholding (USVT) and Stochastic Blockmodel Approximation (SBA).
  • Computational Speedup: Unlike methods requiring singular value decompositions or complex clustering, SAS relies on sorting ($O(n \log n)$) and ADMM-based optimization. For a graph with 2,000 nodes, SAS is nearly 5x faster than USVT. For real-world graphs with 75,000 nodes, SAS produced an estimate in under three minutes on a standard PC.
  • Structural Discovery: On real data, SAS revealed clear community structures and "influential node" patterns that were entirely invisible in the raw, unordered adjacency matrices.

Limitations and Future Work

While powerful, the SAS framework does have theoretical boundaries. The proof of consistency relies heavily on the assumption that the graphon's degree function is strictly monotonic. While common, this may not hold for all theoretical graph models. Additionally, the smoothing step assumes the graphon is "gradient-sparse"; extremely "chunky" or purely random graphs might not be as well-represented.

Currently, the SAS framework is primarily designed for undirected graphs. Extending the sorting logic to handle the distinct in-degrees and out-degrees of directed networks remains an exciting avenue for future research.

Summary updated

Abstract

Exchangeable graph models (ExGM) subsume a number of popular network models. The mathematical object that characterizes an ExGM is termed a graphon. Finding scalable estimators of graphons, provably consistent, remains an open issue. In this paper, we propose a histogram estimator of a graphon that is provably consistent and numerically efficient. The proposed estimator is based on a sorting-and-smoothing (SAS) algorithm, which first sorts the empirical degree of a graph, then smooths the sorted graph using total variation minimization. The consistency of the SAS algorithm is proved by leveraging sparsity concepts from compressed sensing.
BibTeX
@inproceedings{chan2014consistent,
  author = {Stanley H. Chan and Edoardo M. Airoldi},
  title = {{A Consistent Histogram Estimator for Exchangeable Graph Models}},
  booktitle = {International Conference on Machine Learning},
  year = {2014},
  url = {https://openreview.net/forum?id=rkNcbs-_-r},
}
Figure