Exact Recovery in the Latent Space Model

Chuyang Ke, Jean Honorio

We analyze the necessary and sufficient conditions for exact recovery of the symmetric Latent Space Model (LSM) with two communities. In a LSM, each node is associated with a latent vector following some probability distribution. We show that exact recovery can be achieved using a semidefinite programming (SDP) approach. We also analyze when NP-hard maximum likelihood estimation is correct. Our analysis predicts the experimental correctness of SDP with high accuracy, showing the suitability of our focus on the Karush-Kuhn-Tucker (KKT) conditions and the second minimum eigenvalue of a properly defined matrix.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment