mlsanityData to 7 Oct 2026

A Consistent Histogram Estimator for Exchangeable Graph Models

arXiv 1402.1888 ↗First posted 8 Feb 2014stat.MEcited by 36

Not on the map. Why?

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.

Key facts. Cited by 36 papers in the map (data through 7 Oct 2026). First posted on arXiv 8 Feb 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 6; 2023: 5; 2024: 4; 2025: 7; 2026: 5.

36 papers.

Sort:

By area:

  1. 2022G-Mixup: Graph Data Augmentation for Graph Classificationcited by 145
  2. 2022Implicit Graphon Neural Representationcited by 18
  3. 2023A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarseningcited by 15
  4. 2022GraphMAD: Graph Mixup for Data Augmentation using Data-Driven Convex Clusteringcited by 13
  5. 2023Fine-tuning Graph Neural Networks by Preserving Graph Generative Patternscited by 13
  6. 2022Joint Network Topology Inference via a Shared Graphon Modelcited by 11
  7. 2024Scalable Implicit Graphon Learningcited by 8
  8. 2021Graphon based Clustering and Testing of Networks: Algorithms and Theorycited by 6
  9. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  10. 2021Beyond the Signs: Nonparametric Tensor Completion via Sign Seriescited by 4
  11. 2021Nonparametric Modeling of Higher-Order Interactions via Hypergraphonscited by 4
  12. 2021Learning Graphon Autoencoders for Generative Graph Modelingcited by 4
24 more
  1. 2021Network Estimation by Mixing: Adaptivity and Morecited by 4
  2. 2024Transfer Learning for Latent Variable Network Modelscited by 3
  3. 2025A Few Moments Please: Scalable Graphon Learning via Moment Matchingcited by 3
  4. 2026Prior-Informed Flow Matching for Graph Reconstructioncited by 3
  5. 2021Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutationscited by 2
  6. 2025Learning graphons from data: Random walks, transfer operators, and spectral clusteringcited by 2
  7. 2025The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysiscited by 2
  8. 2021Modularity maximisation for graphonscited by 1
  9. 2022Graphon-aided Joint Estimation of Multiple Graphscited by 1
  10. 2025Transfer Learning on Edge Connecting Probability Estimation under Graphon Modelcited by 1
  11. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1
  12. 2021Hawkes Processes on Graphonscited by 0
  13. 2021Nonparametric Trace Regression in High Dimensions via Sign Series Representationcited by 0
  14. 2022Estimation of the Sample Frechet Mean: A Convolutional Neural Network Approachcited by 0
  15. 2023Statistical and computational rates in high rank tensor estimationcited by 0
  16. 2023SC-MAD: Mixtures of Higher-order Networks for Data Augmentationcited by 0
  17. 2024Graph data augmentation with Gromow-Wasserstein Barycenterscited by 0
  18. 2024Estimating Dyadic Treatment Effects with Unknown Confounderscited by 0
  19. 2025Model-Driven Graph Contrastive Learningcited by 0
  20. 2025From Moments to Models: Graphon-Mixture Learning for Mixup and Contrastive Learningcited by 0
  21. 2025A Spectral Framework for Graph Neural Operators: Convergence Guarantees and Tradeoffscited by 0
  22. 2026Low-Complexity and Consistent Graphon Estimation from Multiple Networkscited by 0
  23. 2026Network Learning with Semi-relaxed Gromov-Wassersteincited by 0
  24. 2026Attention Graphons: A Graph Limit Perspective on Graph Transformerscited by 0