Nonparametric graphon estimation

Abstract

We propose a nonparametric framework for the analysis of networks, based on a natural limit object termed a graphon. We prove consistency of graphon estimation under general conditions, giving rates which include the important practical setting of sparse networks. Our results cover dense and sparse stochastic blockmodels with a growing number of classes, under model misspecification. We use profile likelihood methods, and connect our results to approximation theory, nonparametric function estimation, and the theory of graph limits.

52 pages; submitted for publication

References in corpus (5)

• Matrix estimation by Universal Singular Value Thresholding
• Graph limits and exchangeable random graphs
• Co-clustering separately exchangeable network data
• Degree-based network models
• Universally Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs

Cited by in corpus (56)

• Matrix estimation by Universal Singular Value Thresholding
• Rate-optimal graphon estimation
• Metrics for Graph Comparison: A Practitioner's Guide
• Sparse graphs using exchangeable random measures
• Network histograms and universality of blockmodel approximation
• Stochastic blockmodel approximation of a graphon: Theory and consistent estimation
• 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
• The Class of Random Graphs Arising from Exchangeable Random Measures
• Optimal Estimation and Completion of Matrices with Biclustering Structures
• A Consistent Histogram Estimator for Exchangeable Graph Models
• Graphon Signal Processing
• Graphon Neural Networks and the Transferability of Graph Neural Networks
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• A nonparametric two-sample hypothesis testing problem for random dot product graphs
• Edge exchangeable models for network data
• A framework for statistical network modeling
• Network cross-validation by edge sampling
• Consistency of Maximum Likelihood for Continuous-Space Network Models I
• Ergodicity in Stationary Graph Processes: A Weak Law of Large Numbers
• Bootstrapping Exchangeable Random Graphs
• Network Representation Using Graph Root Distributions
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• On sparsity, power-law and clustering properties of graphex processes
• Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks
• Joint Network Topology Inference via a Shared Graphon Model
• Hierarchical Clustering: Objective Functions and Algorithms
• EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
• Why are Big Data Matrices Approximately Low Rank?
• Goodness of fit of logistic models for random graphs
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Optimal link prediction with matrix logistic regression
• Unseeded low-rank graph matching by transform-based unsupervised point registration
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• From which world is your graph?
• A theory of maximum likelihood for weighted infection graphs
• Hypothesis testing for populations of networks
• On decomposable random graphs
• Classification on Large Networks: A Quantitative Bound via Motifs and Graphons
• Manifold structure in graph embeddings
• Asymptotics of Network Embeddings Learned via Subsampling
• Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels
• Nonparametric regression for multiple heterogeneous networks
• Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising
• Corrected Bayesian information criterion for stochastic block models
• Training Graph Neural Networks by Graphon Estimation
• Robustness on Networks
• Tractably Modelling Dependence in Networks Beyond Exchangeability
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• On clustering network-valued data
• Network estimation via graphon with node features
• On the Estimation of Network Complexity: Dimension of Graphons
• Distributed Cartesian Power Graph Segmentation for Graphon Estimation
• Deconvolution with Unknown Error Distribution Interpreted as Blind Isotonic Regression