Clustering over Logistic Random Dot Product Graphs

Luke J. O’Connor, Muriel Médard, Soheil Feizi

TL;DR

This paper introduces the Logistic Random Dot Product Graph (RDPG), a flexible latent space model for networks that maps node positions to edge probabilities via a logistic function. The authors provide a computationally efficient spectral algorithm that achieves asymptotically exact maximum-likelihood inference by combining mean-centering of the adjacency matrix with a novel logistic regression scaling step.

What Problem Does This Paper Address?

In network science, we often want to represent nodes as vectors in a low-dimensional "latent space" where the distance or dot product between vectors determines the probability of an edge. The Random Dot Product Graph (RDPG) is a popular model for this, but standard ways to fit it (like taking the top eigenvectors of the adjacency matrix) often rely on heuristics that fail in practice.

For example, in a simple community structure, the first eigenvector of the adjacency matrix often correlates with node degrees (finding "popular" nodes) rather than the actual community clusters. While methods like Modularity or the Normalized Laplacian attempt to fix this, they can be inconsistent across different types of network structures. The authors seek a principled, maximum-likelihood (ML) approach that is both mathematically grounded and computationally efficient.

Methods

The authors propose the Logistic RDPG, where the probability of an edge between nodes $i$ and $j$ is defined as: $$P_{i,j} = \text{logistic}(v_i \cdot v_j - \mu)$$ where $v_i$ and $v_j$ are latent position vectors and $\mu$ is an offset controlling the network's sparsity.

Their key contribution is Algorithm 1, a spectral inference method that is asymptotically equivalent to the Maximum Likelihood Estimate (MLE). The process works as follows:

  1. Mean-Centering: Instead of the raw adjacency matrix $A$, they work with a mean-centered matrix $B = A - \bar{A}$, where $\bar{A}$ represents the average edge density.
  2. Eigen-decomposition: They compute the top $d$ eigenvectors of $B$.
  3. Logistic Regression Scaling: This is the "secret sauce." Standard spectral methods just use the eigenvectors. Here, the authors perform a logistic regression of the observed edges in $A$ against the outer products of the eigenvectors to find optimal scaling coefficients ($\lambda$).
  4. Embedding: The final latent positions are the eigenvectors scaled by the square root of these coefficients.

Datasets

The paper evaluates the method using both synthetic and real-world datasets:

  • Synthetic SBMs: Various Stochastic Block Models, including cases with dense clusters, single dense clusters, and overlapping communities.
  • Non-SBM Logistic RDPGs: Synthetic networks generated specifically from the logistic latent space model to test recovery.
  • Zachary’s Karate Club: A classic social network of 34 nodes representing a university club that split into two factions.
  • Political Blogs: A network of 1,221 blogs from the 2004 US election, labeled as liberal or conservative.

Key Insights and Ideas

  • The Logistic Link Advantage: By using a logistic link function, the log-likelihood of the model separates into a linear term (dependent on the adjacency matrix) and a nonlinear penalty term. This mathematical structure allows the authors to approximate the ML problem as a tractable spectral optimization.
  • Mean-Centering is Essential: The authors show that simply subtracting the average density from the adjacency matrix (mean-centering) removes the "degree confounder" that plagues standard spectral clustering, allowing the eigenvectors to focus on community structure.
  • Scaling Matters: Most spectral clustering algorithms treat all top eigenvectors as equally important or use their raw eigenvalues. This paper argues that a dedicated regression step to scale these vectors is necessary to truly approximate the maximum likelihood solution.
  • Asymptotic Exactness: They prove that as the graph grows and latent positions remain relatively small (the "centered" regime), their spectral solution converges to the true maximum likelihood estimate.

Key Results

  • Robustness: In synthetic tests (Figure 1), the Logistic RDPG consistently recovered latent positions with low error across different SBM configurations, whereas the Adjacency and Modularity methods failed in at least one specific scenario (e.g., when community structure was highly correlated with node degrees).
  • Clustering Accuracy: On "hard" clustering tasks (Figure 2), the proposed method matched or outperformed state-of-the-art methods like the Bethe Hessian and Semidefinite Programming (SDP) approaches, especially as the "signal strength" of the communities increased.
  • Real-World Success:
    • On the Karate Club network, the first eigenvector of their embedding perfectly separated the two factions.
  • On the Political Blogs network, the embedding clearly separated liberal and conservative blogs in the latent space, even identifying low-degree nodes that are harder to classify.

Limitations and Future Work

  • Dimensionality: The algorithm requires the user to specify the dimension $d$ of the latent space. While the authors mention existing heuristics for this, the paper doesn't propose a new automated way to choose $d$.
  • The "Small Position" Assumption: The proof for asymptotic exactness relies on the latent position magnitudes going to zero as the graph grows. While this covers many interesting "hard-to-detect" regimes, it might not apply to extremely dense or highly structured small graphs.
  • Future Directions: The authors suggest extending this framework to multi-edge graphs (where edge counts follow a binomial distribution) and further characterizing the performance of the MLE in non-asymptotic regimes.

Summary updated

Abstract

Inference of low-dimensional structures, such as clusters, on large networks is a central problem in network science. An important class of models describing such structures is the Random Dot Product Graph (RDPG), which assigns low dimensional latent position vectors to nodes and computes edge probabilities using dot products between these vectors. The RDPG provides a more flexible network model compared with the standard Stochastic Block Model (SBM). In this paper, we introduce the Logistic RDPG, which uses a logistic link function mapping from latent positions to edge probabilities. The logistic RDPG includes most SBMs as well as other low-dimensional structures, such as degree-corrected models, that are not described by SBMs. Over this model, we derive a method for efficient, asymptotically exact maximum-likelihood inference of latent position vectors. Our method involves computing the top eigenvectors of the mean-centered adjacency matrix and performing a logistic regression step to recover the appropriate eigenvalue scaling. Applied to the network clustering problem on diverse synthetic network models, we illustrate that our method is more accurate and more robust than existing spectral and semidefinite network clustering methods.
BibTeX
@misc{oconnor2015clustering,
  author = {Luke J. O’Connor and Muriel Médard and Soheil Feizi},
  title = {{Clustering over Logistic Random Dot Product Graphs}},
  year = {2015},
  eprint = {1510.00850},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.00850},
}

Loading related content...

Figure