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.
Introduction
In network science, mapping nodes to low-dimensional vectors in a "latent space" is crucial for tasks like community detection and visualization. A popular model for this is the Random Dot Product Graph (RDPG), where the probability of an edge is the dot product of two nodes' latent vectors. While RDPGs are computationally efficient to fit using spectral methods, these methods often rely on heuristics that can fail, particularly when high-degree nodes obscure the underlying community structure. This paper addresses these limitations by introducing the Logistic RDPG model and a mathematically rigorous spectral method for its solution.
Methodology: Algorithm 1
The authors propose a multi-step process for Maximum Likelihood (ML) inference, designed to be both efficient and robust:
- Mean-Centering: Instead of using the raw adjacency matrix $A$, the algorithm forms a matrix $B$ by subtracting a constant value related to the graph's average density. This step "centers" the model and helps mitigate degree bias.
- Spectral Decomposition: The top $d$ eigenvectors of the mean-centered matrix $B$ are computed.
- Logistic Regression Scaling: This is the critical innovation. Rather than using raw eigenvectors, the authors perform a logistic regression of the actual edges in $A$ against the eigenvector entries to find optimal scaling coefficients ($\lambda$).
- Embedding: The final latent positions are the eigenvectors scaled by the square root of these coefficients.
The key insight is that the logistic link function allows the log-likelihood objective to be approximated by a Frobenius norm, enabling a spectral solution that is asymptotically exact.
Experimental Results
Synthetic Simulations
The method was evaluated using various Stochastic Block Models (SBMs), which are standard benchmarks for community detection.
In these tests, the Logistic RDPG consistently achieved lower Mean Squared Error (MSE) in latent position estimation compared to traditional Adjacency or Modularity-based methods. The regression step effectively "regresses out" degree bias, making the method more robust to variations in node activity.
Real-World Applications
- Zachary’s Karate Club: The first eigenvector of the Logistic RDPG embedding separated the two factions of the club perfectly.
- Political Blogs: In a network of 1,221 blogs from the 2004 US election, the method successfully separated liberal and conservative blogs in the latent space, accurately classifying even low-degree nodes that are typically difficult for standard algorithms to handle.
Conclusion and Key Insights
The Logistic RDPG framework bridges the gap between fast-but-heuristic spectral methods and slow-but-accurate optimization methods. By leveraging the unique properties of the logistic link function, the authors provide a theoretically grounded approach that is more accurate and robust than common practices. Future work may involve integrating automatic dimension selection and extending the model to handle weighted or multi-edge graphs.
Summary updated