A Comprehensive Survey on Spectral Clustering with Graph Structure Learning

Kamal Berahmand, Farid Saberi-Movahed, Razieh Sheikhpour, Yuefeng Li, Mahdi JaliliarXiv 2025 · DOI · arXiv

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.

Taxonomy of Graph Structure Learning methods, categorized by graph type and adaptivity.
  1. 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.
  2. 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.
  3. 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.

The transition from traditional two-step spectral clustering to modern one-step joint optimization 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

Abstract

Spectral clustering is a powerful technique for clustering high-dimensional data, utilizing graph-based representations to detect complex, non-linear structures and non-convex clusters. The construction of a similarity graph is essential for ensuring accurate and effective clustering, making graph structure learning (GSL) central for enhancing spectral clustering performance in response to the growing demand for scalable solutions. Despite advancements in GSL, there is a lack of comprehensive surveys specifically addressing its role within spectral clustering. To bridge this gap, this survey presents a comprehensive review of spectral clustering methods, emphasizing on the critical role of GSL. We explore various graph construction techniques, including pairwise, anchor, and hypergraph-based methods, in both fixed and adaptive settings. Additionally, we categorize spectral clustering approaches into single-view and multi-view frameworks, examining their applications within one-step and two-step clustering processes. We also discuss multi-view information fusion techniques and their impact on clustering data. By addressing current challenges and proposing future research directions, this survey provides valuable insights for advancing spectral clustering methodologies and highlights the pivotal role of GSL in tackling large-scale and high-dimensional data clustering tasks.
BibTeX
@misc{berahmand2025comprehensive,
  author = {Kamal Berahmand and Farid Saberi-Movahed and Razieh Sheikhpour and Yuefeng Li and Mahdi Jalili},
  title = {{A Comprehensive Survey on Spectral Clustering with Graph Structure Learning}},
  year = {2025},
  eprint = {2501.13597},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.13597},
}
Figure