mlsanityData to 7 Oct 2026

Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

arXiv 1311.1731 ↗First posted 7 Nov 2013stat.ME cs.LG cs.SIcited by 38

Not on the map. Why?

Abstract (arXiv)

Non-parametric approaches for analyzing network data based on exchangeable graph models (ExGM) have recently gained interest. The key object that defines an ExGM is often referred to as a graphon. This non-parametric perspective on network modeling poses challenging questions on how to make inference on the graphon underlying observed network data. In this paper, we propose a computationally efficient procedure to estimate a graphon from a set of observed networks generated from it. This procedure is based on a stochastic blockmodel approximation (SBA) of the graphon. We show that, by approximating the graphon with a stochastic block model, the graphon can be consistently estimated, that is, the estimation error vanishes as the size of the graph approaches infinity.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). First posted on arXiv 7 Nov 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

38 papers.

Sort:

By area:

  1. 2022G-Mixup: Graph Data Augmentation for Graph Classificationcited by 145
  2. 2021Size-Invariant Graph Representations for Graph Classification Extrapolationscited by 82
  3. 2022OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphscited by 38
  4. 2023Data-centric Graph Learning: A Surveycited by 22
  5. 2022Implicit Graphon Neural Representationcited by 18
  6. 2023When to Pre-Train Graph Neural Networks? From Data Generation Perspective!cited by 17
  7. 2023Fine-tuning Graph Neural Networks by Preserving Graph Generative Patternscited by 13
  8. 2025GRAVER: Generative Graph Vocabularies for Robust Graph Foundation Models Fine-tuningcited by 13
  9. 2022Joint Network Topology Inference via a Shared Graphon Modelcited by 11
  10. 2024Scalable Implicit Graphon Learningcited by 8
  11. 2023Computational Lower Bounds for Graphon Estimation via Low-degree Polynomialscited by 6
  12. 2021Nonparametric Modeling of Higher-Order Interactions via Hypergraphonscited by 4
26 more
  1. 2021Learning Graphon Autoencoders for Generative Graph Modelingcited by 4
  2. 2021Network Estimation by Mixing: Adaptivity and Morecited by 4
  3. 2023EPIC: Graph Augmentation with Edit Path Interpolation via Learnable Costcited by 3
  4. 2024Motif-Consistent Counterfactuals with Adversarial Refinement for Graph-Level Anomaly Detectioncited by 3
  5. 2024HGOE: Hybrid External and Internal Graph Outlier Exposure for Graph Out-of-Distribution Detectioncited by 3
  6. 2024A Survey of Out-of-distribution Generalization for Graph Machine Learning from a Causal Viewcited by 3
  7. 2026Prior-Informed Flow Matching for Graph Reconstructioncited by 3
  8. 2023Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labelscited by 2
  9. 2023Transferability of Graph Neural Networks using Graphon and Sampling Theoriescited by 2
  10. 2024Network two-sample test for block modelscited by 2
  11. 2025The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysiscited by 2
  12. 2021Modularity maximisation for graphonscited by 1
  13. 2022Graphon-aided Joint Estimation of Multiple Graphscited by 1
  14. 2024When does the mean network capture the topology of a sample of networks?cited by 1
  15. 2025Transfer Learning on Edge Connecting Probability Estimation under Graphon Modelcited by 1
  16. 2026Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learningcited by 1
  17. 2026DiPhon: Diffusion on Graphons for Scalable Graph Generationcited by 1
  18. 2021Hawkes Processes on Graphonscited by 0
  19. 2024Graph data augmentation with Gromow-Wasserstein Barycenterscited by 0
  20. 2025The Spectral Barycentre of a Set of Graphs with Community Structurecited by 0
  21. 2025Model-Driven Graph Contrastive Learningcited by 0
  22. 2025Simultaneous estimation of connectivity and dimensionality in samples of networkscited by 0
  23. 2025A Generative Model for Controllable Feature Heterophily in Graphscited by 0
  24. 2025From Moments to Models: Graphon-Mixture Learning for Mixup and Contrastive Learningcited by 0
  25. 2026Low-Complexity and Consistent Graphon Estimation from Multiple Networkscited by 0
  26. 2026Attention Graphons: A Graph Limit Perspective on Graph Transformerscited by 0