Optimal Bayesian estimation for random dot product graphs

DOI10.1093/BIOMET/ASAA031zbMATH Open1457.62192arXiv1904.12070OpenAlexW3038586155MaRDI QIDQ5145702FDOQ5145702

Yanxun Xu, Fangzheng Xie

Publication date: 21 January 2021

Published in: Biometrika (Search for Journal in Brave)

Abstract: We propose a Bayesian approach, called the posterior spectral embedding, for estimating the latent positions in random dot product graphs, and prove its optimality. Unlike the classical spectral-based adjacency/Laplacian spectral embedding, the posterior spectral embedding is a fully-likelihood based graph estimation method taking advantage of the Bernoulli likelihood information of the observed adjacency matrix. We develop a minimax-lower bound for estimating the latent positions, and show that the posterior spectral embedding achieves this lower bound since it both results in a minimax-optimal posterior contraction rate, and yields a point estimator achieving the minimax risk asymptotically. The convergence results are subsequently applied to clustering in stochastic block models, the result of which strengthens an existing result concerning the number of mis-clustered vertices. We also study a spectral-based Gaussian spectral embedding as a natural Bayesian analogy of the adjacency spectral embedding, but the resulting posterior contraction rate is sub-optimal with an extra logarithmic factor. The practical performance of the proposed methodology is illustrated through extensive synthetic examples and the analysis of a Wikipedia graph data.

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

Recommendations

• Empirical Bayes estimation for the stochastic blockmodel
• Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
• Maximum a posteriori inference of random dot product graphs via conic programming
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels

zbMATH Keywords

minimax optimalitylikelihood-based graph estimationpositive semidefinite stochastic block modelposterior spectral embedding

Mathematics Subject Classification ID

Probabilistic graphical models (62H22) Minimax procedures in statistical decision theory (62C20) Inference from stochastic processes and spectral analysis (62M15)

Cited In (5)

• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Title not available (Why is that?)
• Euclidean Representation of Low-Rank Matrices and Its Geometric Properties
• Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure
• Bayesian Projected Calibration of Computer Models

This page was built for publication: Optimal Bayesian estimation for random dot product graphs

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