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

DOI10.1080/01621459.2021.1948419MaRDI QIDQ6107237zbMATH OpenOpenAlexFDO

Authors Fangzheng Xie, Yanxun Xu

Publication date 3 July 2023

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

Full work available at URL https://arxiv.org/abs/1910.04333, https://figshare.com/articles/journal_contribution/Efficient_Estimation_for_Random_Dot_Product_Graphs_via_a_One-Step_Procedure/14919528

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• A Consistent Adjacency Spectral Embedding for Stochastic Blockmodel Graphs
• A limit theorem for scaled eigenvectors of random dot product graphs
• A nonparametric two-sample hypothesis testing problem for random graphs
• Achieving optimal misclassification proportion in stochastic block models
• Asymptotic Statistics
• 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
• Laplacian matrices of graphs: A survey
• Latent Space Approaches to Social Network Analysis
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Mathematical statistics. Basic ideas and selected topics. Volume I
• On estimation and inference in latent structure random graphs
• Optimal Bayesian estimation for random dot product graphs
• Probabilistic Community Detection With Unknown Number of Communities
• Random Dot Product Graph Models for Social Networks
• Role of normalization in spectral clustering for stochastic blockmodels
• Sparse Bayesian infinite factor models
• Sparse graphs using exchangeable random measures
• Spectral clustering and the high-dimensional stochastic blockmodel
• Statistical inference on random dot product graphs: a survey
• Universally consistent vertex classification for latent positions 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)