Rate-optimal graphon estimation

DOI10.48550/ARXIV.1410.5837MaRDI QIDQ159635zbMATH OpenWikidataFDO

Authors Chao Gao, Yu Lu, Harrison H. Zhou

Publication date 21 October 2014

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.5837, https://projecteuclid.org/euclid.aos/1444222087

zbMATH Keywords

graphon estimationnetworknonparametric regressionoptimal convergence ratestochastic block model

Mathematics Subject Classification ID

Limit theorems in probability theory (60F99) Nonparametric estimation (62G05) Nonparametric regression and quantile regression (62G08)

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 $k$ clusters, we show that the optimal rate under the mean squared error is $n^{-1}logk+k^2/n^2$. The minimax upper bound improves the existing results in literature through a technique of solving a quadratic equation. When $kleqsqrtnlogn$, as the number of the cluster $k$ grows, the minimax rate grows slowly with only a logarithmic order $n^{-1}logk$. 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 $alpha$. When the smoothness $alphageq1$, the optimal rate of convergence is $n^{-1}logn$, independent of $alpha$, while for $alphain(0,1)$, the rate is $n^{-2alpha/(alpha+1)}$, which is, to our surprise, identical to the classical nonparametric rate.

Recommendations

• When is non-trivial estimation possible for graphons and stochastic block models?
• Optimal graphon estimation in cut distance
• Oracle inequalities for network models and sparse graphon estimation
• Uniform estimation in stochastic block models is slow
• Dynamic network models and graphon estimation

Cites work

• 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
• scientific article; zbMATH DE number 1222269 (Why is no real title available?)
• scientific article; zbMATH DE number 1064667 (Why is no real title available?)
• 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

(78)

• Network cross-validation for determining the number of communities in network data
• Rate-optimal graphon estimation
• randnet
• Local inference by penalization method for biclustering model
• Optimal rates of statistical seriation
• On semidefinite relaxations for the block model
• Towards optimal estimation of bivariate isotonic matrices with unknown permutations
• Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Network representation using graph root distributions
• Consistent nonparametric estimation for heavy-tailed sparse graphs
• A generalization of hierarchical exchangeability on trees to directed acyclic graphs
• Random graph asymptotics for treatment effect estimation under network interference
• Isotonic regression with unknown permutations: statistics, computation and adaptation
• Edgeworth expansions for network moments
• Reconstruction of line-embeddings of graphons
• Bootstrapping exchangeable random graphs
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
• Uniform estimation in stochastic block models is slow
• Estimating the number of connected components in a graph via subgraph sampling
• Estimation of Monge matrices
• Posterior contraction rates for stochastic block models
• A general framework for Bayes structured linear models
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• Maximum likelihood estimation of sparse networks with missing observations
• Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces
• Sampling and estimation for (sparse) exchangeable graphs
• The geometry of continuous latent space models for network data
• Consistent structure estimation of exponential-family random graph models with block structure
• Optimal graphon estimation in cut distance
• Dynamic network models and graphon estimation
• Structured matrix estimation and completion
• Co-clustering of nonsmooth graphons
• Sparse exchangeable graphs and their limits via graphon processes
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Universal latent space model fitting for large networks with edge covariates
• Change point estimation in a dynamic stochastic block model
• scientific article; zbMATH DE number 7626706 (Why is no real title available?)
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Matrix estimation, latent variable model and collaborative filtering
• Corrected Bayesian information criterion for stochastic block models
• Nonparametric modeling of higher-order interactions via hypergraphons
• Random walks on dense graphs and graphons
• When is non-trivial estimation possible for graphons and stochastic block models?
• Oracle inequalities for network models and sparse graphon estimation
• Modularity Maximization for Graphons
• Graphon estimation via nearest‐neighbour algorithm and two‐dimensional fused‐lasso denoising
• Multi‐subject stochastic blockmodels with mixed effects for adaptive analysis of individual differences in human brain network cluster structure
• Linear panel regressions with two-way unobserved heterogeneity
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• On sparsity, power-law, and clustering properties of graphex processes
• Network online change point localization
• Network Inference Using the Hub Model and Variants
• Recent advances on mechanisms of network generation: community, exchangeability, and scale-free properties
• Semiparametric estimation for dynamic networks with shifted connecting intensities
• Network Estimation by Mixing: Adaptivity and More
• Tractably modelling dependence in networks beyond exchangeability
• Forcing generalised quasirandom graphs efficiently
• Robust recovery of Robinson property in L^p-graphons: a cut-norm approach
• Computational lower bounds for graphon estimation via low-degree polynomials
• Spectral clustering in the dynamic stochastic block model
• The spectral barycentre of a set of graphs with community structure
• U-Statistic Reduction: Higher-Order Accurate Risk Control and Statistical-Computational Trade-Off
• Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
• Minimax optimal probability matrix estimation for graphon with spectral decay
• Limit results for estimation of connectivity matrix in multi-layer stochastic block models
• Can smooth graphons in several dimensions be represented by smooth graphons on \([0, 1]\)?
• Stochastic Block Smooth Graphon Model
• Multiway empirical likelihood
• Node-Level Community Detection within Edge Exchangeable Models for Interaction Processes
• Forcing generalized quasirandom graphs efficiently (extended abstract)
• Goodness-of-fit testing based on graph functionals for homogeneous Erdős-Rényi graphs
• Denoising over networks with applications to partially observed epidemics
• Joint estimation of edge probabilities for multi-layer networks via neighborhood smoothing
• Spatially adaptive neighborhood smoothing for directed sparse graphons
• Higher-order graphon theory: fluctuations, degeneracies and inference
• Optimal change point detection and localization in sparse dynamic networks

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)