Abstract
In spectral clustering, one defines a similarity matrix for a collection of data points, transforms the matrix to get the Laplacian matrix, finds the eigenvectors of the Laplacian matrix, and obtains a partition of the data using the leading eigenvectors. The last step is sometimes referred to as rounding, where one needs to decide how many leading eigenvectors to use, to determine the number of clusters, and to partition the data points. In this paper, we propose a novel method for rounding. The method differs from previous methods in three ways. First, we relax the assumption that the number of clusters equals the number of eigenvectors used. Second, when deciding the number of leading eigenvectors to use, we not only rely on information contained in the leading eigenvectors themselves, but also use subsequent eigenvectors. Third, our method is model-based and solves all the three subproblems of rounding using a class of graphical models called latent tree models. We evaluate our method on both synthetic and real-world data. The results show that our method works correctly in the ideal case where between-clusters similarity is 0, and degrades gracefully as one moves away from the ideal case.
Introduction
Spectral clustering is a powerful technique that treats data points as nodes in a graph and partitions them by examining the "vibrational modes" (eigenvectors) of that graph. However, it faces a significant "last-mile" challenge known as rounding. After calculating the eigenvectors, researchers are left with real-valued coordinates and must solve three critical subproblems:
- Selection: How many leading eigenvectors ($q$) should be used?
- Estimation: How many clusters ($k$) are actually present in the data?
- Assignment: Which data point belongs to which cluster?
Traditional methods often assume $q = k$ or rely on manual inspection of "eigenvalue gaps," which can fail in noisy real-world scenarios. This paper introduces LTM-Rounding, a unified, principled framework that automates these steps using Latent Tree Models (LTMs).
Methods
The LTM-Rounding approach consists of three primary stages:
- Binarization: Continuous eigenvectors are transformed into binary "indicator" vectors using a confidence parameter $\delta$. This simplifies complex real-valued signals into discrete features representing potential cluster memberships.
- Latent Class Models (LCM): For a fixed number of eigenvectors ($q$), an LCM—essentially a Naive Bayes model with a hidden class—is used to cluster the data. The Bayesian Information Criterion (BIC) is employed to automatically determine the optimal number of clusters ($k$).
- Latent Tree Models (LTM): To determine the optimal $q$, the algorithm constructs a tree-structured graphical model. It uses leading eigenvectors to form primary clusters and subsequent eigenvectors as secondary "witness" features. If the later eigenvectors contradict the current cluster structure, the BIC score drops, signaling that the incorrect number of eigenvectors has been selected.
Experimental Evaluation
The authors evaluated LTM-Rounding against several benchmarks, including synthetic datasets, MNIST handwritten digits, and the Berkeley Segmentation Data Set (BSDS500).
- Robustness to Noise: On noisy synthetic "crescent" data, LTM-Rounding maintained a Rand Index (RI) of 0.97, significantly outperforming the popular rotation-based "ROT-Rounding" method, which dropped to 0.52.
- MNIST Accuracy: LTM-Rounding estimated an average of 9.3 clusters for the 10-digit dataset, whereas rotation-based methods over-estimated at 19 clusters.
- Image Segmentation: In real-world image tasks, LTM-Rounding successfully identified complex objects (e.g., a bottle and glass) where traditional methods failed to produce meaningful segments.
Key Insights
- Decoupling $q$ and $k$: By allowing the number of eigenvectors to differ from the number of clusters, the method handles noisy data where a single cluster might be spread across multiple eigenvectors.
- The "Witness" Effect: Using unused eigenvectors to validate used ones provides a built-in statistical sanity check for the partitioning logic.
- Principled Automation: Framing rounding as a model selection problem replaces subjective heuristics with a statistically grounded objective function.
Conclusion
LTM-Rounding offers a robust, automated alternative to traditional rounding heuristics in spectral clustering. While the method relies on iterative EM (Expectation-Maximization) algorithms—which can be more computationally intensive than simple K-means—it provides superior accuracy and graceful degradation in the presence of noise. Future work may involve integrating image-specific analysis techniques to reduce over-segmentation in uniform regions.
Summary updated