A Consistent Histogram Estimator for Exchangeable Graph Models

2014/02/08 by Stanley H. Chan, Edoardo M. Airoldi, Chan, Stanley H. +1 · 8 citations
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Error Correcting Code Techniques #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Methodology (stat.ME)

paper · pdf · doi:10.48550/arxiv.1402.1888

openalex publication_date 2014/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Nonparametric graphon estimation

Cited by

• A Short Note on Upper Bounds for Graph Neural Operator Convergence Rate
• Transfer Learning on Edge Connecting Probability Estimation under Graphon Model
• From Moments to Models: Graphon-Mixture Learning for Mixup and Contrastive Learning
• Graphon Estimation from Partially Observed Network Data
• Network Representation Using Graph Root Distributions
• Nonparametric regression for multiple heterogeneous networks
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Learning graphons from data: Random walks, transfer operators, and spectral clustering

Related

• Sampling and Estimation for (Sparse) Exchangeable Graphs
• An iterative step-function estimator for graphons
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
• Network estimation via graphon with node features
• Graphon Estimation from Partially Observed Network Data