A Consistent Histogram Estimator for Exchangeable Graph Models

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.

28 pages, 5 figures

References in corpus (3)

• Graph limits and exchangeable random graphs
• Modeling homophily and stochastic equivalence in symmetric relational data
• Network histograms and universality of blockmodel approximation

Cited by in corpus (21)

• Rate-optimal graphon estimation
• Network Representation Using Graph Root Distributions
• Joint Network Topology Inference via a Shared Graphon Model
• EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
• Reducing Crowdsourcing to Graphon Estimation, Statistically
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Fundamental Limits of Deep Graph Convolutional Networks
• Priors on exchangeable directed graphs
• Graphon Estimation from Partially Observed Network Data
• Learning Graphons via Structured Gromov-Wasserstein Barycenters
• Beyond the Signs: Nonparametric Tensor Completion via Sign Series
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version
• Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
• Nonparametric Two-Sample Test for Networks Using Joint Graphon Estimation
• Nonparametric regression for multiple heterogeneous networks
• Nonparametric Trace Regression in High Dimensions via Sign Series Representation
• Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising
• Graphon based Clustering and Testing of Networks: Algorithms and Theory
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• Learning Graphon Autoencoders for Generative Graph Modeling