Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure

DOI10.1080/01621459.2021.1948419zbMATH Open1514.62100arXiv1910.04333OpenAlexW3179669439MaRDI QIDQ6107237FDOQ6107237

Authors: Fangzheng Xie, Yanxun Xu 

Publication date: 3 July 2023

Published in: Journal of the American Statistical Association (Search for Journal in Brave)

Abstract: We propose a one-step procedure to estimate the latent positions in random dot product graphs efficiently. Unlike the classical spectral-based methods such as the adjacency and Laplacian spectral embedding, the proposed one-step procedure takes advantage of both the low-rank structure of the expected adjacency matrix and the Bernoulli likelihood information of the sampling model simultaneously. We show that for each vertex, the corresponding row of the one-step estimator converges to a multivariate normal distribution after proper scaling and centering up to an orthogonal transformation, with an efficient covariance matrix. The initial estimator for the one-step procedure needs to satisfy the so-called approximate linearization property. The one-step estimator improves the commonly-adopted spectral embedding methods in the following sense: Globally for all vertices, it yields an asymptotic sum of squares error no greater than those of the spectral methods, and locally for each vertex, the asymptotic covariance matrix of the corresponding row of the one-step estimator dominates those of the spectral embeddings in spectra. The usefulness of the proposed one-step procedure is demonstrated via numerical examples and the analysis of a real-world Wikipedia graph dataset.

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

Recommendations

• Optimal Bayesian estimation for random dot product graphs
• Statistical inference on random dot product graphs: a survey
• A limit theorem for scaled eigenvectors of random dot product graphs
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• A nonparametric two-sample hypothesis testing problem for random graphs

zbMATH Keywords

asymptotic normalitynormalized Laplacianapproximate linearization propertyBernoulli likelihood informationlatent position estimation

Mathematics Subject Classification ID

Probabilistic graphical models (62H22) Programming involving graphs or networks (90C35) Minimax procedures in statistical decision theory (62C20) Inference from stochastic processes and spectral analysis (62M15) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Asymptotic Statistics
• Spectral clustering and the high-dimensional stochastic blockmodel
• Sparse Bayesian infinite factor models
• Title not available (Why is that?)
• Automatic dimensionality selection from the scree plot via the use of profile likelihood
• Community structure in social and biological networks
• Concentration inequalities. A nonasymptotic theory of independence
• Mathematical statistics. Basic ideas and selected topics. Volume I
• Probabilistic Community Detection With Unknown Number of Communities
• Achieving optimal misclassification proportion in stochastic block models
• Random Dot Product Graph Models for Social Networks
• Latent Space Approaches to Social Network Analysis
• A nonparametric two-sample hypothesis testing problem for random graphs
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• Laplacian matrices of graphs: A survey
• A limit theorem for scaled eigenvectors of random dot product graphs
• Universally consistent vertex classification for latent positions graphs
• Role of normalization in spectral clustering for stochastic blockmodels
• Statistical inference on random dot product graphs: a survey
• Sparse graphs using exchangeable random measures
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• On estimation and inference in latent structure random graphs
• Optimal Bayesian estimation for random dot product graphs

Cited In (5)

• A limit theorem for scaled eigenvectors of random dot product graphs
• Maximum a posteriori inference of random dot product graphs via conic programming
• Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals
• Hypothesis testing for equality of latent positions in random graphs
• Optimal Bayesian estimation for random dot product graphs

This page was built for publication: Efficient Estimation for Random Dot Product Graphs via a One-Step Procedure

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