Rate-optimal graphon estimation

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}\log k+k^2/n^2$. The minimax upper bound improves the existing results in literature through a technique of solving a quadratic equation. When $k\le \sqrt{n\log n}$, as the number of the cluster $k$ grows, the minimax rate grows slowly with only a logarithmic order $n^{-1}\log k$. 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ölder class with smoothness $\alpha$. When the smoothness $\alpha \ge 1$, the optimal rate of convergence is $n^{-1}\log n$, independent of $\alpha$, while for $\alpha \in (0,1)$, the rate is $n^{-2\alpha /(\alpha +1)}$, which is, to our surprise, identical to the classical nonparametric rate.

Published at http://dx.doi.org/10.1214/15-AOS1354 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (15)

• Stochastic blockmodels and community structure in networks
• Missing and spurious interactions and the reconstruction of complex networks
• Mixture models and exploratory analysis in networks
• Consistency of spectral clustering in stochastic block models
• Graph limits and exchangeable random graphs
• Modeling homophily and stochastic equivalence in symmetric relational data
• Network histograms and universality of blockmodel approximation
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Nonparametric Link Prediction in Dynamic Networks
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
• A Consistent Histogram Estimator for Exchangeable Graph Models
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Impact of regularization on Spectral Clustering

Cited by in corpus (74)

• Sparse exchangeable graphs and their limits via graphon processes
• Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
• Consistent estimation of dynamic and multi-layer block models
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
• Centrality measures for graphons: Accounting for uncertainty in networks
• Optimal Estimation and Completion of Matrices with Biclustering Structures
• Graphon Signal Processing
• Private Graphon Estimation for Sparse Graphs
• Graphon Neural Networks and the Transferability of Graph Neural Networks
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Optimal Change Point Detection and Localization in Sparse Dynamic Networks
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• A General Framework for Bayes Structured Linear Models
• Change-point detection in dynamic networks via graphon estimation
• Estimating network edge probabilities by neighborhood smoothing
• A framework for statistical network modeling
• Consistent structure estimation of exponential-family random graph models with block structure
• Network cross-validation by edge sampling
• Bootstrapping Exchangeable Random Graphs
• Consistency of Maximum Likelihood for Continuous-Space Network Models I
• Random Walk Models of Network Formation and Sequential Monte Carlo Methods for Graphs
• Nearest Neighbors for Matrix Estimation Interpreted as Blind Regression for Latent Variable Model
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral
• Subsampling large graphs and invariance in networks
• Network Representation Using Graph Root Distributions
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• On sparsity, power-law and clustering properties of graphex processes
• Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• A review on minimax rates in change point detection and localisation
• Consistency of adjacency spectral embedding for the mixed membership stochastic blockmodel
• Random Graph Asymptotics for Treatment Effect Estimation under Network Interference
• Causal Inference in Possibly Nonlinear Factor Models
• Joint Network Topology Inference via a Shared Graphon Model
• EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
• Optimal network online change point localisation
• Optimal Bayesian estimation in stochastic block models
• Optimal link prediction with matrix logistic regression
• General framework for projection structures
• Phase Transitions in Approximate Ranking
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• Fundamental Limits of Deep Graph Convolutional Networks
• Unseeded low-rank graph matching by transform-based unsupervised point registration
• Consistent Bayesian Community Detection
• Spectral clustering in the dynamic stochastic block model
• Reconstruction of Line-Embeddings of Graphons
• Consistent polynomial-time unseeded graph matching for Lipschitz graphons
• Clustering of Diverse Multiplex Networks
• Maximum Likelihood Estimation of Sparse Networks with Missing Observations
• Pseudo-likelihood-based $M$-estimation of random graphs with dependent edges and parameter vectors of increasing dimension
• Manifold structure in graph embeddings
• Estimating the Number of Connected Components in a Graph via Subgraph Sampling
• Identifiability and consistency of network inference using the hub model and variants
• Graphon Estimation from Partially Observed Network Data
• Matrix factorisation and the interpretation of geodesic distance
• Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version
• Corrected Bayesian information criterion for stochastic block models
• Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels
• Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising
• Tractably Modelling Dependence in Networks Beyond Exchangeability
• Multiway empirical likelihood
• Distributed Cartesian Power Graph Segmentation for Graphon Estimation
• On clustering network-valued data
• Network estimation via graphon with node features
• Training Graph Neural Networks by Graphon Estimation
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• On the Estimation of Network Complexity: Dimension of Graphons
• Outliers Detection in Networks with Missing Links
• Can smooth graphons in several dimensions be represented by smooth graphons on $[0,1]$?
• Discretizing Unobserved Heterogeneity