Consistent nonparametric estimation for heavy-tailed sparse graphs

DOI10.1214/20-AOS1985zbMATH Open1486.62080arXiv1508.06675OpenAlexW3204583332MaRDI QIDQ2054468FDOQ2054468

Authors: Henry Cohn, Shirshendu Ganguly, Christian Borgs, Jennifer T. Chayes 

Publication date: 3 December 2021

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

Abstract: We study graphons as a non-parametric generalization of stochastic block models, and show how to obtain compactly represented estimators for sparse networks in this framework. Our algorithms and analysis go beyond previous work in several ways. First, we relax the usual boundedness assumption for the generating graphon and instead treat arbitrary integrable graphons, so that we can handle networks with long tails in their degree distributions. Second, again motivated by real-world applications, we relax the usual assumption that the graphon is defined on the unit interval, to allow latent position graphs where the latent positions live in a more general space, and we characterize identifiability for these graphons and their underlying position spaces. We analyze three algorithms. The first is a least squares algorithm, which gives an approximation we prove to be consistent for all square-integrable graphons, with errors expressed in terms of the best possible stochastic block model approximation to the generating graphon. Next, we analyze a generalization based on the cut norm, which works for any integrable graphon (not necessarily square-integrable). Finally, we show that clustering based on degrees works whenever the underlying degree distribution is atomless. Unlike the previous two algorithms, this third one runs in polynomial time.

Full work available at URL: https://arxiv.org/abs/1508.06675

Recommendations

• Sampling and estimation for (sparse) exchangeable graphs
• Bootstrap estimators for the tail-index and for the count statistics of graphex processes
• When is non-trivial estimation possible for graphons and stochastic block models?
• Rate-optimal graphon estimation
• Oracle inequalities for network models and sparse graphon estimation

zbMATH Keywords

estimationsparse networksgraphons

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Probabilistic graphical models (62H22) Random graphs (graph-theoretic aspects) (05C80)

Cites Work

• A nonparametric view of network models and Newman–Girvan and other modularities
• Spectral clustering and the high-dimensional stochastic blockmodel
• Limits of dense graph sequences
• Pseudo-likelihood methods for community detection in large sparse networks
• Measure preserving transformations and rearrangements
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Rate-optimal graphon estimation
• Matrix estimation by universal singular value thresholding
• Consistency of spectral clustering in stochastic block models
• Mixed membership stochastic blockmodels
• A Simple SVD Algorithm for Finding Hidden Partitions
• Stochastic Blockmodels for Directed Graphs
• Community detection thresholds and the weak Ramanujan property
• The method of moments and degree distributions for network models
• Latent Space Approaches to Social Network Analysis
• Stochastic blockmodels with a growing number of classes
• Exact Recovery in the Stochastic Block Model
• Oracle inequalities for network models and sparse graphon estimation
• Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
• The phase transition in inhomogeneous random graphs
• Representations for partially exchangeable arrays of random variables
• A tensor approach to learning mixed membership community models
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions
• Graph limits and exchangeable random graphs
• Moments of two-variable functions and the uniqueness of graph limits
• Counting graph homomorphisms
• Random graphs with a given degree sequence
• Universally consistent vertex classification for latent positions graphs
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• The Metropolis algorithm for graph bisection
• An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
• The solution of some random NP-hard problems in polynomial expected time
• Quick approximation to matrices and applications
• An 𝐿^{𝑝} theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions
• Multivariate sampling and the estimation problem for exchangeable arrays
• Graphons, cut norm and distance, couplings and rearrangements
• Variational Bayes model averaging for graphon functions and motif frequencies inference in \(W\)-graph models
• Graph partitioning via adaptive spectral techniques
• Co-clustering separately exchangeable network data
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Metrics for sparse graphs
• Spectral Clustering by Recursive Partitioning
• Generic sample splitting for refined community recovery in degree corrected stochastic block models

Cited In (16)

• Large deviation for uniform graphs with given degrees
• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• On the continuum limit of epidemiological models on graphs: convergence and approximation results
• Dynamic network models and graphon estimation
• Adaptive estimation of nonparametric geometric graphs
• Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
• Learning sparse graphons and the generalized Kesten-Stigum threshold
• When is non-trivial estimation possible for graphons and stochastic block models?
• Bootstrap estimators for the tail-index and for the count statistics of graphex processes
• Forcing generalised quasirandom graphs efficiently
• Tractably modelling dependence in networks beyond exchangeability
• Optimal graphon estimation in cut distance
• Sampling and estimation for (sparse) exchangeable graphs
• Variational Bayes model averaging for graphon functions and motif frequencies inference in \(W\)-graph models
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Computational lower bounds for graphon estimation via low-degree polynomials

This page was built for publication: Consistent nonparametric estimation for heavy-tailed sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2054468)