Abstract
Spectral clustering is one of the most popular clustering approaches with the capability to handle challenging clustering problems. Most spectral clustering methods provide a nonlinear map from the data manifold to a subspace, but explicit linear maps for unsupervised distance metric learning remain less explored. In practice, the selection of the affinity matrix exhibits a tremendous impact on unsupervised learning. We propose a novel method, Adaptive Affinity Matrix (AdaAM), to learn an adaptive affinity matrix and derive a distance metric from the affinity. We assume the affinity matrix to be positive semidefinite with the ability to quantify pairwise dissimilarity. Our method is based on posing the optimization of the objective function as a spectral decomposition problem. We yield the affinity from both the original data distribution and the widely-used heat kernel. Extensive experiments on a number of real-world datasets show the effectiveness and efficiency of AdaAM.
Introduction
Spectral clustering is a powerhouse in unsupervised learning, but it faces three major challenges: out-of-sample extension, scalability, and graph robustness. Traditional methods often fail to provide embeddings for new data points without re-running the entire algorithm, and their complexity often scales poorly with dataset size. Furthermore, the quality of clustering depends entirely on the "affinity graph." If the initial distance metric is noisy—for instance, if lighting conditions make different faces appear similar—the clustering fails. AdaAM addresses these issues by learning an adaptive similarity measure that captures global structure while remaining computationally efficient.
Methodology
The core innovation of AdaAM is its construction of the affinity matrix ($\Delta$). Instead of relying solely on a standard heat kernel, the framework assumes the ideal affinity matrix should be low-rank to reflect underlying cluster structures.
- Low-Rank Decomposition: The affinity matrix is decomposed into a product of two identical low-rank matrices ($PP^T$).
- Optimization via SVD: By reformulating the objective of locality preservation into a spectral decomposition problem, the model can be solved using Singular Value Decomposition (SVD). This "one-shot" approach is significantly faster than iterative optimization methods.
- Hybrid Approach: The final affinity matrix combines this learned global structure with a standard $k$-Nearest Neighbor ($k$-NN) graph, allowing the model to capture both global manifold relationships and local nuances.
- Metric Learning via LPP: To solve the out-of-sample problem, the authors apply Locality Preserving Projections (LPP) to the learned graph, producing a linear transformation matrix that can project new data points into the learned metric space.
Experimental Results
The authors evaluated AdaAM on five image benchmarks: UMIST, COIL20, USPS, MNIST, and ExYaleB.
Robustness to Illumination
The most striking result occurs with the ExYaleB dataset. Standard methods typically fail here because lighting changes create more variance than the actual differences between faces. AdaAM’s ability to learn a global structure allows it to see past these lighting artifacts, achieving 54.36% average accuracy, while competing methods like $k$-NN and PCAN-kMeans hover around 23-26%.
Efficiency and Scalability
AdaAM is designed for high efficiency. While the mathematical framework allows for iterative updates, empirical results show that a single iteration provides nearly all the accuracy gains, making it much faster than competing adaptive methods. In execution time tests on MNIST, AdaAM was significantly faster than ClustRF-Bi and PCAN-kMeans, maintaining a complexity profile closer to simpler, non-adaptive methods.
Conclusion and Future Work
AdaAM introduces a robust framework for learning adaptive affinity matrices that significantly improves clustering performance on high-variance data. By leveraging low-rank priors and SVD-based optimization, it achieves state-of-the-art accuracy without the computational burden of iterative learning. Future work may address the model's sensitivity to neighborhood size ($k$) and explore automated parameter tuning for its sparsification strategy.
Summary updated