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.
Introduction: The Challenge of Graphon Estimation
In network science, understanding the generative process behind a graph is a fundamental task. Exchangeable graph models provide a powerful framework for this, where the underlying structure is captured by a graphon—a symmetric, measurable function $w: [0, 1]^2 \to [0, 1]$ that represents the probability of an edge between nodes based on their latent positions.
A primary obstacle in estimating graphons is identifiability. Because node labels in an observed graph are arbitrary, any permutation of these labels results in an isomorphic graph that represents the same underlying graphon. As shown in Figure 1, different labelings can obscure the true structure, making it difficult to recover the generating function directly from raw data.
To estimate a graphon accurately, one must find a "canonical" ordering of nodes. Previous methods often relied on computationally intensive clustering or lacked rigorous proofs of consistency (convergence to the true graphon as the network size $n$ increases).
The Sorting-And-Smoothing (SAS) Algorithm
The authors introduce the Sorting-And-Smoothing (SAS) algorithm, a two-stage approach designed for both theoretical consistency and computational efficiency. The pipeline is visualized in Figure 2.
1. Sorting by Empirical Degree
The first stage addresses the node-ordering problem. The algorithm calculates the empirical degree of each node and sorts them from lowest to highest. For a broad class of graphons, this simple degree-based sorting effectively recovers a canonical ordering, transforming a seemingly random adjacency matrix into a structured pattern.
2. Smoothing via Total Variation Minimization
The sorted adjacency matrix is a noisy realization of the underlying graphon. To denoise it, the SAS algorithm treats the matrix as a 2D image:
- Local Histogram: The sorted nodes are grouped into $k \times k$ blocks to create a 2D histogram $\widehat{H}$, which serves as an initial, piecewise-constant estimate.
- TV Minimization: The algorithm then applies Total Variation (TV) minimization to $\widehat{H}$. This technique, common in image processing, assumes the underlying signal is mostly smooth but allows for sharp transitions. The optimization is solved efficiently using the ADMM (Alternating Direction Method of Multipliers) framework.
Theoretical Foundations and Key Results
The core contribution of this work is the proof of consistency for the SAS estimator. By viewing the graphon estimation problem through the lens of compressed sensing, the authors demonstrate that if the graphon has "sparse gradients" in its canonical form, the SAS estimator achieves a Mean Squared Error (MSE) of $O(\frac{\log n}{n})$. This ensures that the error vanishes as the network grows.
Performance Highlights
- Superior Accuracy: SAS consistently outperformed competing methods like Universal Singular Value Thresholding (USVT) and Stochastic Blockmodel Approximation (SBA) in terms of MSE across various synthetic models.
- Dramatic Speedups: The algorithm is remarkably fast. While USVT took nearly 5 seconds for a 2,000-node network, SAS completed the task in under 1.5 seconds. On the 75,000-node Epinions network, SAS produced an estimate in just 170 seconds on standard hardware.
Conclusion and Future Directions
The SAS algorithm provides a robust, scalable solution for graphon estimation by bridging network science with image processing. While highly effective, the current proof of consistency assumes strictly monotonic node degrees. Future work may explore handling "twin" nodes (groups with identical connection profiles) and extending the framework to directed graphs.
Summary updated