# Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2013.

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

- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs](https://mlsanity.com/paper/2205.15117/) (2022)
- [Data-centric Graph Learning: A Survey](https://mlsanity.com/paper/2310.04987/) (2023)
- [Implicit Graphon Neural Representation](https://mlsanity.com/paper/2211.03329/) (2022)
- [When to Pre-Train Graph Neural Networks? From Data Generation Perspective!](https://mlsanity.com/paper/2303.16458/) (2023)
- [Fine-tuning Graph Neural Networks by Preserving Graph Generative Patterns](https://mlsanity.com/paper/2312.13583/) (2023)
- [GRAVER: Generative Graph Vocabularies for Robust Graph Foundation Models Fine-tuning](https://mlsanity.com/paper/2511.05592/) (2025)
- [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)
- [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)
- [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)
- [EPIC: Graph Augmentation with Edit Path Interpolation via Learnable Cost](https://mlsanity.com/paper/2306.01310/) (2023)
- [Transferability of Graph Neural Networks using Graphon and Sampling Theories](https://mlsanity.com/paper/2307.13206/) (2023)
- [Motif-Consistent Counterfactuals with Adversarial Refinement for Graph-Level Anomaly Detection](https://mlsanity.com/paper/2407.13251/) (2024)
- [HGOE: Hybrid External and Internal Graph Outlier Exposure for Graph Out-of-Distribution Detection](https://mlsanity.com/paper/2407.21742/) (2024)
- [A Survey of Out-of-distribution Generalization for Graph Machine Learning from a Causal View](https://mlsanity.com/paper/2409.09858/) (2024)
- [Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels](https://mlsanity.com/paper/2304.03590/) (2023)
- [Network two-sample test for block models](https://mlsanity.com/paper/2406.06014/) (2024)
- [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)
- [When does the mean network capture the topology of a sample of networks?](https://mlsanity.com/paper/2408.03461/) (2024)
- [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)
- [DiPhon: Diffusion on Graphons for Scalable Graph Generation](https://mlsanity.com/paper/2607.07232/) (2026)
- [Hawkes Processes on Graphons](https://mlsanity.com/paper/2102.02741/) (2021)

## 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.