Universally consistent vertex classification for latent positions graphs

Abstract

In this work we show that, using the eigen-decomposition of the adjacency matrix, we can consistently estimate feature maps for latent position graphs with positive definite link function $\kappa$, provided that the latent positions are i.i.d. from some distribution F. We then consider the exploitation task of vertex classification where the link function $\kappa$ belongs to the class of universal kernels and class labels are observed for a number of vertices tending to infinity and that the remaining vertices are to be classified. We show that minimization of the empirical $\phi$-risk for some convex surrogate $\phi$ of 0-1 loss over a class of linear classifiers with increasing complexities yields a universally consistent classifier, that is, a classification rule with error converging to Bayes optimal for any distribution F.

Published in at http://dx.doi.org/10.1214/13-AOS1112 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (9)

• Stochastic blockmodels and community structure in networks
• Mixed membership stochastic blockmodels
• The phase transition in inhomogeneous random graphs
• Consistency of spectral clustering
• Spectral clustering and the high-dimensional stochastic blockmodel
• Matrix estimation by Universal Singular Value Thresholding
• Graph limits and exchangeable random graphs
• Statistical performance of support vector machines
• Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

Cited by in corpus (16)

• Nonparametric Bayes Modeling of Populations of Networks
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Joint Embedding of Graphs
• One-Hot Graph Encoder Embedding
• Statistical inference for network samples using subgraph counts
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• Robust Vertex Classification
• Discovering Communication Pattern Shifts in Large-Scale Labeled Networks using Encoder Embedding and Vertex Dynamics
• Motif Estimation via Subgraph Sampling: The Fourth Moment Phenomenon
• Stratified stochastic variational inference for high-dimensional network factor model
• A Simple Spectral Failure Mode for Graph Convolutional Networks
• Community detection and percolation of information in a geometric setting
• Correcting a Nonparametric Two-sample Graph Hypothesis Test for Graphs with Different Numbers of Vertices with Applications to Connectomics
• Markov Random Geometric Graph (MRGG): A Growth Model for Temporal Dynamic Networks
• Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery
• Maximum a Posteriori Inference of Random Dot Product Graphs via Conic Programming