Rate-optimal graphon estimation
From MaRDI portal
Abstract: Network analysis is becoming one of the most active research areas in statistics. Significant advances have been made recently on developing theories, methodologies and algorithms for analyzing networks. However, there has been little fundamental study on optimal estimation. In this paper, we establish optimal rate of convergence for graphon estimation. For the stochastic block model with clusters, we show that the optimal rate under the mean squared error is . The minimax upper bound improves the existing results in literature through a technique of solving a quadratic equation. When , as the number of the cluster grows, the minimax rate grows slowly with only a logarithmic order . A key step to establish the lower bound is to construct a novel subset of the parameter space and then apply Fano's lemma, from which we see a clear distinction of the nonparametric graphon estimation problem from classical nonparametric regression, due to the lack of identifiability of the order of nodes in exchangeable random graph models. As an immediate application, we consider nonparametric graphon estimation in a H"{o}lder class with smoothness . When the smoothness , the optimal rate of convergence is , independent of , while for , the rate is , which is, to our surprise, identical to the classical nonparametric rate.
Recommendations
Cites work
- scientific article; zbMATH DE number 1222269 (Why is no real title available?)
- scientific article; zbMATH DE number 1064667 (Why is no real title available?)
- A nonparametric view of network models and Newman–Girvan and other modularities
- A survey of statistical network models
- A tensor approach to learning mixed membership community models
- Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
- Achieving optimal misclassification proportion in stochastic block models
- An Exponential Family of Probability Distributions for Directed Graphs
- Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
- Community structure in social and biological networks
- Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
- Consistency of community detection in networks under degree-corrected stochastic block models
- Consistency of spectral clustering in stochastic block models
- Degree-corrected stochastic block models and reliability in networks
- Estimation and Prediction for Stochastic Blockstructures
- Graph limits and exchangeable random graphs
- Harmonic analysis of digital data bases
- Introduction to nonparametric estimation
- Large networks and graph limits
- Limits of dense graph sequences
- Lower Bounds for the Minimax Risk Using $f$-Divergences, and Applications
- Matrix estimation by universal singular value thresholding
- Mixed membership stochastic blockmodels
- Mixture models and exploratory analysis in networks
- On the representation theorem for exchangeable arrays
- Pseudo-likelihood methods for community detection in large sparse networks
- Rate-optimal graphon estimation
- Representations for partially exchangeable arrays of random variables
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Sampling, denoising and compression of matrices by coherent matrix organization
- Spectral clustering and the high-dimensional stochastic blockmodel
Cited in
(63)- Consistent nonparametric estimation for heavy-tailed sparse graphs
- Network cross-validation for determining the number of communities in network data
- Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model
- Corrected Bayesian information criterion for stochastic block models
- Network Inference Using the Hub Model and Variants
- Towards optimal estimation of bivariate isotonic matrices with unknown permutations
- Structured matrix estimation and completion
- On semidefinite relaxations for the block model
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- Dynamic network models and graphon estimation
- Universal latent space model fitting for large networks with edge covariates
- Posterior contraction rates for stochastic block models
- Local inference by penalization method for biclustering model
- Edgeworth expansions for network moments
- scientific article; zbMATH DE number 7415089 (Why is no real title available?)
- The geometry of continuous latent space models for network data
- Isotonic regression with unknown permutations: statistics, computation and adaptation
- Bootstrapping exchangeable random graphs
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- Reconstruction of line-embeddings of graphons
- Uniform estimation in stochastic block models is slow
- Modularity Maximization for Graphons
- Network Estimation by Mixing: Adaptivity and More
- Co-clustering of nonsmooth graphons
- Learning sparse graphons and the generalized Kesten-Stigum threshold
- Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
- scientific article; zbMATH DE number 7626706 (Why is no real title available?)
- Consistent structure estimation of exponential-family random graph models with block structure
- Maximum likelihood estimation of sparse networks with missing observations
- Graphon estimation via nearest‐neighbour algorithm and two‐dimensional fused‐lasso denoising
- Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
- Semiparametric estimation for dynamic networks with shifted connecting intensities
- randnet
- A general framework for Bayes structured linear models
- Matrix estimation, latent variable model and collaborative filtering
- Network representation using graph root distributions
- When is non-trivial estimation possible for graphons and stochastic block models?
- On sparsity, power-law, and clustering properties of graphex processes
- Optimal graphon estimation in cut distance
- Forcing generalised quasirandom graphs efficiently
- Tractably modelling dependence in networks beyond exchangeability
- Robust recovery of Robinson property in \(L^p\)-graphons: a cut-norm approach
- Multi‐subject stochastic blockmodels with mixed effects for adaptive analysis of individual differences in human brain network cluster structure
- Sampling and estimation for (sparse) exchangeable graphs
- Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces
- Randomized Spectral Clustering in Large-Scale Stochastic Block Models
- Linear panel regressions with two-way unobserved heterogeneity
- Optimal change point detection and localization in sparse dynamic networks
- Rate-optimal graphon estimation
- scientific article; zbMATH DE number 7255138 (Why is no real title available?)
- Iterative Collaborative Filtering for Sparse Matrix Estimation
- Computational lower bounds for graphon estimation via low-degree polynomials
- Spectral clustering in the dynamic stochastic block model
- Estimating the number of connected components in a graph via subgraph sampling
- A generalization of hierarchical exchangeability on trees to directed acyclic graphs
- Oracle inequalities for network models and sparse graphon estimation
- Network online change point localization
- Sparse exchangeable graphs and their limits via graphon processes
- Optimal rates of statistical seriation
- Estimation of Monge matrices
- Random graph asymptotics for treatment effect estimation under network interference
- Analysis of spectral clustering algorithms for community detection: the general bipartite setting
- Random walks on dense graphs and graphons
This page was built for publication: Rate-optimal graphon estimation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q159635)
