Rate-optimal graphon estimation

DOI10.48550/arXiv.1410.5837zbMath1332.6005arXiv1410.5837WikidataQ59410897 ScholiaQ59410897MaRDI QIDQ159635

Chao Gao, Harrison H. Zhou, Yu Lu, Harrison H. Zhou, Yu Lu, Chao Gao

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

zbMATH Keywords

networknonparametric regressionoptimal convergence ratestochastic block modelgraphon estimation

Mathematics Subject Classification ID

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

Related Items

Isotonic regression with unknown permutations: statistics, computation and adaptation ⋮ Edgeworth expansions for network moments ⋮ Local inference by penalization method for biclustering model ⋮ 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 ⋮ Randomized Spectral Clustering in Large-Scale Stochastic Block Models ⋮ Iterative Collaborative Filtering for Sparse Matrix Estimation ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Estimating the number of connected components in a graph via subgraph sampling ⋮ 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 ⋮ Estimation of Monge matrices ⋮ Posterior contraction rates for stochastic block models ⋮ Optimal rates of statistical seriation ⋮ A general framework for Bayes structured linear models ⋮ Exponential-family models of random graphs: inference in finite, super and infinite population scenarios ⋮ Corrected Bayesian Information Criterion for Stochastic Block Models ⋮ Spectral clustering in the dynamic stochastic block model ⋮ Maximum likelihood estimation of sparse networks with missing observations ⋮ Unnamed Item ⋮ On semidefinite relaxations for the block model ⋮ Sparse exchangeable graphs and their limits via graphon processes ⋮ Towards optimal estimation of bivariate isotonic matrices with unknown permutations ⋮ Random Walks on Dense Graphs and Graphons ⋮ Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model ⋮ Optimal change point detection and localization in sparse dynamic networks ⋮ Convergence and concentration of empirical measures under Wasserstein distance in unbounded functional spaces ⋮ Sampling and estimation for (sparse) exchangeable graphs ⋮ Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing ⋮ Network representation using graph root distributions ⋮ The geometry of continuous latent space models for network data ⋮ Consistent structure estimation of exponential-family random graph models with block structure ⋮ Network Cross-Validation for Determining the Number of Communities in Network Data ⋮ Rate-optimal graphon estimation ⋮ randnet ⋮ Consistent nonparametric estimation for heavy-tailed sparse graphs ⋮ Optimal graphon estimation in cut distance ⋮ Dynamic network models and graphon estimation ⋮ Analysis of spectral clustering algorithms for community detection: the general bipartite setting ⋮ Unnamed Item ⋮ A generalization of hierarchical exchangeability on trees to directed acyclic graphs ⋮ Structured matrix estimation and completion ⋮ Random graph asymptotics for treatment effect estimation under network interference ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-likelihood methods for community detection in large sparse networks
• Rate-optimal graphon estimation
• Consistency thresholds for the planted bisection model
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Sampling, denoising and compression of matrices by coherent matrix organization
• Spectral clustering and the high-dimensional stochastic blockmodel
• Limits of dense graph sequences
• Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
• On the representation theorem for exchangeable arrays
• Representations for partially exchangeable arrays of random variables
• Degree-corrected stochastic block models and reliability in networks
• Consistency of community detection in networks under degree-corrected stochastic block models
• Matrix estimation by universal singular value thresholding
• Consistency of spectral clustering in stochastic block models
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Harmonic Analysis of Digital Data Bases
• A nonparametric view of network models and Newman–Girvan and other modularities
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Mixed membership stochastic blockmodels
• Graph limits and exchangeable random graphs
• Mixture models and exploratory analysis in networks
• An Exponential Family of Probability Distributions for Directed Graphs
• Estimation and Prediction for Stochastic Blockstructures
• Community structure in social and biological networks
• A Survey of Statistical Network Models
• Lower Bounds for the Minimax Risk Using $f$-Divergences, and Applications
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Introduction to nonparametric estimation