Universally consistent vertex classification for latent positions graphs

DOI10.1214/13-AOS1112zbMATH Open1273.62147arXiv1212.1182OpenAlexW3104477937MaRDI QIDQ366983FDOQ366983

Minh Tang, Carey E. Priebe, Daniel L. Sussman

Publication date: 25 September 2013

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

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 $varphi$-risk for some convex surrogate $varphi$ 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.

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

zbMATH Keywords

classificationBayes-risk consistencyconvergence of eigenvectorsconvex cost functionlatent space model

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Empirical decision procedures; empirical Bayes procedures (62C12) Statistical decision theory (62C99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Spectral clustering and the high-dimensional stochastic blockmodel
• Functional Classification in Hilbert Spaces
• The Rotation of Eigenvectors by a Perturbation. III
• Consistent nonparametric regression. Discussion
• Matrix estimation by universal singular value thresholding
• Mixed membership stochastic blockmodels
• Universality, Characteristic Kernels and RKHS Embedding of Measures
• Random Dot Product Graph Models for Social Networks
• Consistency of spectral clustering
• On the mathematical foundations of learning
• Mercer's theorem on general domains: on the interaction between measures, kernels, and RKHSs
• Latent Space Approaches to Social Network Analysis
• Statistical behavior and consistency of classification methods based on convex risk minimization.
• On the influence of the kernel on the consistency of support vector machines
• Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are Unknown
• The phase transition in inhomogeneous random graphs
• Graph limits and exchangeable random graphs
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• Convexity, Classification, and Risk Bounds
• Learning Theory
• Support vector machines are universally consistent
• On learning with integral operators
• Freedman's inequality for matrix martingales
• Statistical performance of support vector machines
• Random matrix approximation of spectra of integral operators
• Learning Theory
• Variation of discrete spectra
• On the Bayes-risk consistency of regularized boosting methods.
• Learning Eigenfunctions Links Spectral Embedding and Kernel PCA
• On the Eigenspectrum of the Gram Matrix and the Generalization Error of Kernel-PCA
• Learning Theory

Cited In (28)

• Consistent nonparametric estimation for heavy-tailed sparse graphs
• Title not available (Why is that?)
• A limit theorem for scaled eigenvectors of random dot product graphs
• Perfect clustering for stochastic blockmodel graphs via adjacency spectral embedding
• Entropic Optimal Transport on Random Graphs
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• Adaptive estimation of nonparametric geometric graphs
• Motif estimation via subgraph sampling: the fourth-moment phenomenon
• A probabilistic view of latent space graphs and phase transitions
• Markov random geometric graph, MRGG: a growth model for temporal dynamic networks
• Bayesian vertex nomination using content and context
• Vertex nomination
• Testing for Equivalence of Network Distribution Using Subgraph Counts
• Title not available (Why is that?)
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Community detection and percolation of information in a geometric setting
• Title not available (Why is that?)
• Statistical inference on random dot product graphs: a survey
• On the estimation of latent distances using graph distances
• Maximum A Posteriori Inference of Random Dot Product Graphs via Conic Programming
• Empirical Bayes estimation for the stochastic blockmodel
• Title not available (Why is that?)
• Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
• Title not available (Why is that?)
• Title not available (Why is that?)
• Hyperlink regression via Bregman divergence
• Stratified Stochastic Variational Inference for High-Dimensional Network Factor Model

This page was built for publication: Universally consistent vertex classification for latent positions graphs

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