# A Consistent Histogram Estimator for Exchangeable Graph Models

arXiv: https://arxiv.org/abs/1402.1888 · HTML: https://mlsanity.com/paper/1402.1888/

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2014.

## Built on by (most cited first, 30 of 37)

- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [Implicit Graphon Neural Representation](https://mlsanity.com/paper/2211.03329/) (2022)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [GraphMAD: Graph Mixup for Data Augmentation using Data-Driven Convex Clustering](https://mlsanity.com/paper/2210.15721/) (2022)
- [Fine-tuning Graph Neural Networks by Preserving Graph Generative Patterns](https://mlsanity.com/paper/2312.13583/) (2023)
- [Joint Network Topology Inference via a Shared Graphon Model](https://mlsanity.com/paper/2209.08223/) (2022)
- [Scalable Implicit Graphon Learning](https://mlsanity.com/paper/2410.17464/) (2024)
- [Graphon based Clustering and Testing of Networks: Algorithms and Theory](https://mlsanity.com/paper/2110.02722/) (2021)
- [Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials](https://mlsanity.com/paper/2308.15728/) (2023)
- [Learning Graphon Autoencoders for Generative Graph Modeling](https://mlsanity.com/paper/2105.14244/) (2021)
- [Beyond the Signs: Nonparametric Tensor Completion via Sign Series](https://mlsanity.com/paper/2102.00384/) (2021)
- [Nonparametric Modeling of Higher-Order Interactions via Hypergraphons](https://mlsanity.com/paper/2105.08678/) (2021)
- [Network Estimation by Mixing: Adaptivity and More](https://mlsanity.com/paper/2106.02803/) (2021)
- [Prior-Informed Flow Matching for Graph Reconstruction](https://mlsanity.com/paper/2601.22107/) (2026)
- [Transfer Learning for Latent Variable Network Models](https://mlsanity.com/paper/2406.03437/) (2024)
- [A Few Moments Please: Scalable Graphon Learning via Moment Matching](https://mlsanity.com/paper/2506.04206/) (2025)
- [Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations](https://mlsanity.com/paper/2111.04681/) (2021)
- [Learning graphons from data: Random walks, transfer operators, and spectral clustering](https://mlsanity.com/paper/2507.18147/) (2025)
- [The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis](https://mlsanity.com/paper/2510.17515/) (2025)
- [Modularity maximisation for graphons](https://mlsanity.com/paper/2101.00503/) (2021)
- [Graphon-aided Joint Estimation of Multiple Graphs](https://mlsanity.com/paper/2202.05686/) (2022)
- [Transfer Learning on Edge Connecting Probability Estimation under Graphon Model](https://mlsanity.com/paper/2510.05527/) (2025)
- [Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2602.16196/) (2026)
- [Hawkes Processes on Graphons](https://mlsanity.com/paper/2102.02741/) (2021)
- [Nonparametric Trace Regression in High Dimensions via Sign Series Representation](https://mlsanity.com/paper/2105.01783/) (2021)
- [Estimation of the Sample Frechet Mean: A Convolutional Neural Network Approach](https://mlsanity.com/paper/2210.07401/) (2022)
- [Statistical and computational rates in high rank tensor estimation](https://mlsanity.com/paper/2304.04043/) (2023)
- [SC-MAD: Mixtures of Higher-order Networks for Data Augmentation](https://mlsanity.com/paper/2309.07453/) (2023)
- [Graph data augmentation with Gromow-Wasserstein Barycenters](https://mlsanity.com/paper/2404.08376/) (2024)
- [Estimating Dyadic Treatment Effects with Unknown Confounders](https://mlsanity.com/paper/2405.16547/) (2024)

## Abstract (arXiv)

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.