Maximum Likelihood Embedding of Logistic Random Dot Product Graphs

Authors

  • Luke J. O'Connor Broad Institute
  • Muriel Medard MIT
  • Soheil Feizi UMD

DOI:

https://doi.org/10.1609/aaai.v34i04.5975

Abstract

A latent space model for a family of random graphs assigns real-valued vectors to nodes of the graph such that edge probabilities are determined by latent positions. Latent space models provide a natural statistical framework for graph visualizing and clustering. A latent space model of particular interest is the Random Dot Product Graph (RDPG), which can be fit using an efficient spectral method; however, this method is based on a heuristic that can fail, even in simple cases. Here, we consider a closely related latent space model, the Logistic RDPG, which uses a logistic link function to map from latent positions to edge likelihoods. Over this model, we show that asymptotically exact maximum likelihood inference of latent position vectors can be achieved using an efficient spectral method. Our method involves computing top eigenvectors of a normalized adjacency matrix and scaling eigenvectors using a regression step. The novel regression scaling step is an essential part of the proposed method. In simulations, we show that our proposed method is more accurate and more robust than common practices. We also show the effectiveness of our approach over standard real networks of the karate club and political blogs.

Downloads

Published

2020-04-03

How to Cite

O’Connor, L. J., Medard, M., & Feizi, S. (2020). Maximum Likelihood Embedding of Logistic Random Dot Product Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04), 5289-5297. https://doi.org/10.1609/aaai.v34i04.5975

Issue

Section

AAAI Technical Track: Machine Learning