Nonparametric graphon estimation
arXiv:1309.5936
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.
arXiv comment52 pages; submitted for publication
References in corpus (7)
- Matrix estimation by Universal Singular Value Thresholding
- Graph limits and exchangeable random graphs
- Maximum likelihood estimation in log-linear models
- Maximum lilkelihood estimation in the -model
- 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