Understanding Doubly Stochastic Clustering

Tianjiao Ding, Derek Lim, René Vidal, Benjamin D. HaeffeleICML 2022 · OpenReview

Introduction

Spectral clustering is a workhorse of machine learning, allowing practitioners to find clusters in data with complex geometric shapes. It operates by building an "affinity matrix" that describes the similarity between every pair of data points. However, real-world data is inherently noisy, leading to "false connections"—high similarity scores between points that actually belong to different clusters.

To mitigate this, researchers often normalize the affinity matrix. One of the most principled approaches is projecting the matrix onto the set of doubly stochastic matrices (matrices where every row and column sums to a constant). While empirical studies have shown that using the $\ell_2$ distance for this projection works remarkably well, the theoretical justification has remained elusive. This paper provides the first rigorous theoretical analysis explaining the geometric and algebraic conditions that make projecting affinity matrices onto the space of doubly stochastic matrices so effective, particularly in the context of subspace clustering.

Methodology

The authors focus on the $\ell_2$ doubly stochastic projection (DS-D). Given a noisy affinity matrix $K$, the objective is to solve for a new matrix $A^*$ that is as close as possible to $K$ in the $\ell_2$ sense, subject to being doubly stochastic and non-negative.

Key technical contributions include:

  • The Decoupling Theorem: The authors prove that the massive global projection problem can be broken down into smaller, independent sub-problems for each cluster. If specific conditions are met, solving these local problems and stitching them together yields the exact same result as solving the global problem.
  • Continuous Analysis: To handle the "big data" limit, they develop a continuous version of the problem. This allows them to analyze clustering performance based on the underlying geometry of the data (such as the angles between subspaces) rather than relying solely on individual data points.
  • Geometric Conditions: For the specific case of subspace clustering, the paper derives explicit bounds on subspace angles and dimensions that guarantee the projection will perfectly separate clusters.

Key Insights

  • Sparsity vs. Connectivity: Unlike other normalizations (like $\ell_1$ or KL-divergence), the $\ell_2$ projection naturally introduces sparsity. It effectively zeros out small, noisy entries (false connections) while preserving strong, meaningful internal connectivity.
  • Invariance to Additive Noise: A surprising finding is that the projection is invariant to certain types of low-rank additive noise. For instance, adding a constant to every entry of the affinity matrix does not change the final projected result.
  • The "Ideal" Affinity: The authors define an ideal affinity as one with zero connections between clusters and full connectivity within clusters. They demonstrate that the DS-D projection is a powerful tool for transforming a messy, real-world matrix into something much closer to this ideal state.
Figure 1: A noisy affinity matrix from a stochastic block model (left) is transformed into a nearly ideal, block-diagonal matrix after doubly stochastic projection (right).

Experimental Results

The paper validates its theoretical claims using both synthetic graph models and high-dimensional subspace data.

  • Perfect Recovery in WSBM: Using a Weighted Stochastic Block Model (WSBM)—a synthetic graph model where edges within and between clusters are drawn from different probability distributions—the algorithm's ability to handle noisy, overlapping clusters was tested. In experiments with 5 clusters and significant noise, the DS-D projection achieved 1.0 clustering accuracy and normalized mutual information, even when the original noisy affinity yielded much lower scores (around 0.79 accuracy).
  • Subspace Separation: Using high-dimensional data points sampled from multiple linear subspaces in $\mathbb{R}^{20}$, the theory correctly predicts that as the angle between subspaces ($\theta_{min}$) increases or the dimension of the subspaces ($d$) decreases, the projection becomes more likely to perfectly separate the clusters.
  • Improving Existing Kernels: The authors showed that applying DS-D as a post-processing step to standard kernels like Least Squares Regression (LSR) consistently reduces "Feature Detection Error" and boosts final clustering accuracy.
Figure 2: Analysis of the minimum angle required between subspaces to guarantee cluster separation as a function of their relative sizes (mixture weights).

Limitations and Future Work

While the paper provides a strong theoretical foundation, it primarily assumes that data points are uniformly distributed within their clusters (or subspaces) in the continuous limit. Real-world data often exhibits more complex, non-uniform densities.

Future research directions include extending the analysis to non-linear manifolds beyond linear subspaces, investigating the impact of different distance measures (beyond $\ell_2$) within this new theoretical framework, and developing faster, more scalable algorithms for the projection step to handle massive datasets.

Summary updated

Abstract

The problem of projecting a matrix onto the space of <em>doubly stochastic</em> matrices finds several applications in machine learning. For example, in spectral clustering, it has been shown that ...
BibTeX
@inproceedings{ding2022understanding,
  author = {Tianjiao Ding and Derek Lim and René Vidal and Benjamin D. Haeffele},
  title = {{Understanding Doubly Stochastic Clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=5wh7BZR5GG8},
}
Figure