Introduction
Spectral clustering has long been regarded as a "gold standard" for identifying complex, non-convex clusters that traditional algorithms like K-means often fail to capture. However, its performance is fundamentally tied to the quality of the underlying similarity graph. If this graph—which defines the relationships between data points—is poorly constructed due to noise or inappropriate parameter selection (e.g., a rigid K-Nearest Neighbor approach), the resulting clusters will be inaccurate.
This survey explores the evolution of spectral clustering through the lens of Graph Structure Learning (GSL). It argues that modern advancements focus less on the clustering algorithm itself and more on moving from static, rule-based graph construction to adaptive, optimization-driven structures that can handle high-dimensional data and large-scale datasets.
Taxonomy of Graph Structure Learning
The survey categorizes the evolution of spectral clustering into three primary architectural pillars, moving from simple point-to-point relationships to complex group dynamics.
- Pairwise Graphs: This is the traditional approach. The field has shifted from Fixed Methods (like KNN or $\epsilon$-ball) to Adaptive Methods such as Clustering with Adaptive Neighbors (CAN). Adaptive methods learn graph weights dynamically during optimization to better capture local data manifolds.
- Anchor-based Graphs: To address the $O(n^3)$ computational complexity of traditional spectral clustering, anchor-based methods select a small set of $m$ "anchors" ($m \ll n$). By building an $n \times m$ matrix instead of a full $n \times n$ similarity matrix, complexity is reduced to $O(nm)$, enabling scalability to massive datasets.
- Hypergraphs: Unlike pairwise graphs that connect two points, hypergraphs use hyperedges to connect multiple nodes. This allows for the capture of higher-order relationships and group structures that are often lost in simple point-to-point links.
Evolution of the Clustering Pipeline
A significant trend highlighted in the survey is the shift from Two-Step Clustering to One-Step Clustering frameworks.
In the traditional two-step approach, researchers first calculate spectral embeddings and then run a separate algorithm like K-means to find clusters. This is often sub-optimal because errors in the embedding phase propagate to the final result. Modern "One-Step" frameworks jointly optimize graph learning and cluster assignment. By using techniques like Spectral Rotation or rank-constrained Laplacians, these methods can force the learned graph to have exactly $k$ connected components, effectively performing clustering within the graph construction phase itself.
Key Insights and Robustness
Modern GSL treats the similarity matrix as a learnable variable. Several key techniques have emerged to improve robustness:
- Self-Expressive Learning: By using the data to represent itself ($X = XZ$), researchers can learn a coefficient matrix $Z$ that provides a global view of the data structure, making it more resilient to noise than local neighborhood approaches.
- Multi-view Synergy: In multi-view clustering, GSL is used to learn "Consensus Information" across different data sources (e.g., images and text) while preserving unique "Complementary Information" from each view.
- Robust Regularization: The integration of $L_{2,1}$ norms or nuclear norm regularization (as seen in LRR and SSC) has significantly improved resilience to outliers compared to standard Gaussian kernel graphs.
Future Directions
Despite significant progress, several challenges remain. The construction of hypergraphs remains computationally heavy, and most current GSL focuses solely on similarity. The authors suggest that incorporating dissimilarity (negative relationships) could provide a more nuanced "push-pull" dynamic for better cluster separation. Furthermore, integrating GSL with deep neural networks (Deep GSL) represents a promising frontier for handling extremely complex, non-linear manifolds in unsupervised learning.
Summary updated