Stochastic blockmodel approximation of a graphon: Theory and consistent estimation

2013/11/07 by Edoardo M Airoldi, Edoardo M. Airoldi, Thiago B. Costa +6 · 11 citations
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Data Analysis #FOS: Computer and information sciences #FOS: Physical sciences #Graph theory and applications #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Methodology (stat.ME) #Social and Information Networks (cs.SI) #Statistics and Probability (physics.data-an) #cs.LG #cs.SI #physics.data-an #stat.ME #stat.ML

paper · pdf · doi:10.48550/arxiv.1311.1731

20 pages, 4 figures, 2 algorithms. Neural Information Processing Systems (NIPS), 2013

openalex publication_date 2013/11/07 · arxiv created 2013/11/08 · arxiv updated 2013/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Nonparametric graphon estimation
• Modeling homophily and stochastic equivalence in symmetric relational data

Cited by

• GRAVER: Generative Graph Vocabularies for Robust Graph Foundation Models Fine-tuning
• Transfer Learning on Edge Connecting Probability Estimation under Graphon Model
• From Moments to Models: Graphon-Mixture Learning for Mixup and Contrastive Learning
• A Generative Model for Controllable Feature Heterophily in Graphs
• Simultaneous estimation of connectivity and dimensionality in samples of networks
• Model-Driven Graph Contrastive Learning
• Simultaneous global and local clustering in multiplex networks with covariate information
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• Automatic Dimension Selection for a Non-negative Factorization Approach to Clustering Multiple Random Graphs
• Unified Statistical Theory of Spectral Graph Analysis
• Why are Big Data Matrices Approximately Low Rank?

Related

• Nonparametric graphon estimation
• Stochastic Block Smooth Graphon Model
• When is Nontrivial Estimation Possible for Graphons and Stochastic Block Models?
• An empirical Bayes Approach to stochastic blockmodels and graphons: shrinkage estimation and model selection
• Tractably Modelling Dependence in Networks Beyond Exchangeability