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

Abstract

We propose a one-step procedure to estimate the latent positions in random dot product graphs efficiently. Unlike the classical spectral-based methods, 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 (OSE) 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 OSE 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 OSE 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.

KEYWORDS:

• Approximate linearization property
• Asymptotic normality
• Bernoulli likelihood information
• Latent position estimation
• Normalized Laplacian

Supplementary Material

The supplementary material contains a comprehensive list of notations, the proofs of the technical results in Sections 2, Section 3, and Section 4, the behavior of the OSE for positive-definite stochastic block models, further discussion regarding sparse graph models, and additional simulated examples.

Additional information

Funding

The work of Xu was supported by NSF 1918854 and NSF 1940107.