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