PaperlayerView exact revision on arXiv

Source-linked AI summary

A Comprehensive Survey on Spectral Clustering with Graph Structure Learning

Kamal Berahmand, Farid Saberi-Movahed, Razieh Sheikhpour, Yuefeng Li, Mahdi Jalili

arXiv:2501.13597v2cs.LG

TL;DR

Spectral clustering lacks a comprehensive survey centered on how graph structure learning affects its performance on complex, high-dimensional data. This paper systematically reviews graph construction, clustering frameworks, multi-view fusion, challenges, and future directions, concluding that GSL is fundamental to handling high-dimensional and large-scale datasets.

  • Problem

    A comprehensive survey specifically addressing graph structure learning within spectral clustering is lacking, despite GSL's importance for clustering complex, high-dimensional data.

  • Method

    The survey reviews pairwise, anchor, and hypergraph constructions in fixed and adaptive settings, categorizes single-view and multi-view one-step and two-step methods, and examines multi-view information fusion.

  • Results

    The analysis highlights graph structure learning as fundamental to improving clustering performance and handling high-dimensional and large-scale datasets.

  • Takeaways & Limitations

    The survey provides a basis for guiding future spectral-clustering research across graph construction, multi-view fusion, emerging challenges, and future directions.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Spectral clustering addresses limitations of traditional methods on high-dimensional and complex data by representing relationships through graphs. This survey centers graph structure learning, reviewing graph constructions, clustering frameworks, multi-view fusion, and future directions.

  • Motivation: Traditional clustering methods often struggle with high-dimensional data, non-convex shapes, and intricate structures.Distance measurement becomes challenging in high-dimensional spaces, while dimensionality-reduction methods preserve essential structural information for clustering.
  • Motivation: Spectral clustering captures non-linear structures and non-convex clusters by representing data points as graph nodes connected through similarities.Its graph-based embedding supports partitioning according to connectivity and relationships across diverse applications.
  • Survey scope: The survey addresses the lack of a comprehensive spectral-clustering review focused specifically on graph structure learning and its effect on clustering accuracy.It contrasts this focus with earlier surveys emphasizing graph cuts, Laplacian matrices, and clustering processes.
  • Survey scope: It reviews pairwise, anchor, and hypergraph constructions in fixed and adaptive forms, and organizes methods by single-view or multi-view and one-step or two-step frameworks.The one-step versus two-step distinction concerns whether clustering is jointly optimized with spectral embedding or performed afterward.
  • Survey scope: The survey examines multi-view information fusion and analyzes recent advances, challenges, and future directions for spectral clustering and graph learning.These topics are framed as relevant to complex, heterogeneous, and high-dimensional data.

III. MAIN STAGES OF SPECTRAL CLUSTERING

Spectral clustering is presented as a graph-cut methodology that uses Laplacian eigenspectrum analysis to reveal manifold structure. Its framework consists of graph structure learning, spectral embedding, and final partitioning.

  • Framework: Spectral clustering combines graph theory and manifold learning to handle complex, nonlinear data distributions through graph Laplacian eigenspectrum analysis.This formulation is described as retaining theoretical guarantees and computational efficiency in the clustering process.
  • Framework: The spectral clustering framework has three stages: graph structure learning, spectral embedding through eigendecomposition, and partitioning for final cluster assignment.The stages respectively model relationships, reveal manifold structure, and produce cluster assignments.

A. Graph Structure Learning

Graph structure learning in spectral clustering is organized around fixed and adaptive graph-construction strategies. Pairwise graphs use predefined neighborhood or similarity rules, whereas adaptive methods learn graph relationships from data to better represent local and intrinsic structure.

  • Fixed and Adaptive Methods: GSL in spectral clustering uses fixed protocols or adaptive optimization to construct graphs with different efficiency, flexibility, and data-specificity properties.Fixed methods use predetermined rules; adaptive methods dynamically optimize graph structure to capture dataset-specific characteristics.
  • Pairwise Graph Construction: Pairwise graph construction represents data points as vertices and their similarities as weighted edges in a similarity matrix.The graph may target local neighborhood relationships or broader global structure.
  • Fixed Pairwise Methods: Fixed pairwise graphs include KNN, Mutual KNN, fully connected, and ε-Ball constructions, each defining edges through a different neighborhood criterion.KNN connects each point to its nearest neighbors, Mutual KNN requires reciprocal neighborhoods, fully connected graphs link every pair, and ε-Ball uses a distance radius.
  • Similarity Criteria: Pairwise similarities can use binary, cosine, or Gaussian-kernel criteria to assign edge weights from connectivity, angle, or kernel distance.The Gaussian bandwidth parameter σ controls the width of the kernel function.
  • Adaptive Pairwise Methods: Adaptive methods learn neighbors, weights, or refined similarities from data, including adaptive-neighbor, initial-similarity-refinement, and self-expressive approaches.CAN learns neighbors and weights jointly, refinement methods use Frobenius or L1 constraints, and self-expressive methods reconstruct points through a global representation.
  • Adaptive Pairwise Methods: Frobenius-norm refinement favors smoother similarity updates, whereas L1-norm refinement promotes sparse similarity structures.Both approaches refine an initial similarity matrix into a more accurate relationship representation.
  • Adaptive Pairwise Methods: Self-expressive learning constructs a similarity matrix from a coefficient matrix, using reconstruction and regularization to uncover intrinsic subspace structure.Symmetrization produces S = (|Z| + |Z^T|)/2 as the similarity measure.

2) Anchor Graph:

Anchor graphs reduce graph construction to relationships between data samples and a smaller representative set of anchors. Their fixed or adaptive construction, followed by similarity-matrix generation, preserves core relationships while reducing the need to process all nodes.

  • Anchor Graph Overview: Anchor graphs represent large datasets through a smaller subset of representative nodes, with m anchors selected from n samples where m ≪ n.This anchor-centered representation improves computational manageability by avoiding direct processing of every node.
  • Anchor Point Selection: Anchor selection may use random sampling, K-means, K-means++, or balanced hierarchical K-means, trading simplicity, representativeness, diversity, and scalability.Random selection is inexpensive but may be unrepresentative, while BKHK uses a balanced binary-tree structure for large datasets.
  • Anchor Graph Construction: Anchor graph construction has fixed and adaptive forms: fixed methods prescribe neighborhood and weight rules, whereas adaptive methods learn sample–anchor connection strengths.Both approaches aim to represent local and global data structures through sample–anchor relationships.
  • Fixed Anchor Construction: Fixed anchor construction connects each sample to its nearest anchors and then assigns edge weights using schemes such as binary, polynomial-kernel, or Gaussian-kernel weighting.The weight schemes differ in how they encode the strength of sample–anchor relationships.
  • Adaptive Anchor Construction: Adaptive anchor learning jointly determines neighbors and weights from sample–anchor relationships, with γ serving as a regularization parameter.The learned weights wij encode the connection between sample xi and anchor uj.
  • Similarity Matrix Generation: Anchor-based similarity matrices can be generated through Gram-matrix formulations or bipartite graph constructions.The bipartite formulation uses n sample nodes, m anchor nodes, and a weight matrix W to model their relationships.

3) Hypergraph:

Hypergraphs extend graph-based representation by connecting multiple vertices through hyperedges, thereby modeling higher-order relationships. Their construction uses fixed or adaptive incidence strategies, including nearest-neighbor, clustering, threshold, matrix-learning, and self-expressive methods.

  • Hypergraph Overview: Hypergraphs represent complex associations by linking multiple vertices simultaneously through hyperedges, capturing higher-order relationships.Their structure includes vertices, hyperedges, weights, and an incidence matrix describing vertex–hyperedge connections.
  • Fixed Hypergraph Methods: Fixed hypergraph methods construct incidence matrices using nearest-neighbor or clustering-based strategies.Nearest-neighbor methods use KNN or ε-Ball criteria, while clustering-based methods form hyperedges from cluster memberships.
  • Adaptive Hypergraph Methods: Adaptive hypergraph methods learn structural elements such as hyperedge weights, vertex degrees, hyperedge degrees, and incidence relationships.These methods are designed to represent intricate vertex–hyperedge relationships more flexibly than predetermined constructions.
  • Self-Expressive Methods: Self-expressive hypergraph learning first solves a self-expressive problem and then derives vertex–hyperedge incidence relationships from the learned coefficient matrix.The survey identifies ℓ1-HG, ℓ2-HG, and elastic-net hypergraph variants.
  • Incidence Construction: A 0–1 incidence strategy links sample xi to hyperedge ej when coefficient zij exceeds threshold θ1.The thresholded coefficient determines whether the sample–hyperedge relationship is retained.
  • Incidence Construction: Probability-based incidence uses representation coefficients to define relationships with a specified threshold θ2.This provides an alternative to binary thresholding for constructing the incidence relation.
  • Matrix Learning: Matrix-learning techniques formulate hypergraph construction as an optimization problem involving data, incidence structure, degree matrices, hyperedge weights, regularization, and constraints.Threshold-based hyperedge construction can assign each sample a variable number of nearest neighbors.

B. Spectral Embedding

Spectral embedding uses graph Laplacian eigenspectra to capture nonlinear relationships and preserve local geometric structure. Its optimization produces a low-dimensional embedding from eigenvectors associated with the smallest non-zero Laplacian eigenvalues.

  • Embedding Principle: Spectral embedding applies spectral graph theory and manifold learning to uncover data structure while retaining local geometric characteristics.It uses graph Laplacian eigenspectra to preserve topological connections during dimensionality reduction.
  • Embedding Objective: Given a similarity graph, spectral embedding optimizes the embedding matrix F through the graph-Laplacian objective F^T L F.The embedding matrix represents the low-dimensional coordinates of the data.
  • Laplacian Forms: The graph Laplacian may be unnormalized, symmetric normalized, or random-walk normalized.These are the three principal Laplacian forms described for spectral embedding.
  • Eigenvector Selection: The orthogonality condition F^T F = I_k selects eigenvectors corresponding to the smallest non-zero eigenvalues of L.These eigenvectors preserve graph connectivity while providing a low-dimensional representation of cluster structure.

C. Partitioning Process

Spectral clustering partitions data by using a low-dimensional spectral representation produced through spectral embedding. Its partitioning process is organized into two-step and one-step frameworks based on how embedding and clustering are performed.

  • Spectral clustering assigns cluster memberships from a low-dimensional representation obtained through spectral embedding.
  • Methods are classified as two-step or one-step according to how spectral embedding and clustering are conducted.

1) Two-Step Clustering:

Two-step methods first compute a continuous spectral embedding and then cluster it, whereas one-step methods jointly learn embeddings and assignments. One-step approaches include continuous and discrete frameworks that avoid or reduce the mismatch between relaxed embeddings and discrete cluster indicators.

  • Two-Step Clustering: Two-step spectral clustering relaxes discrete constraints, decomposes the graph Laplacian, and then applies K-means to the continuous embedding F.
  • Two-Step Clustering: The embedding F may not match the true discrete solution, while K-means initialization sensitivity can produce locally optimal assignments and inaccuracies.
  • One-Step Clustering: One-step methods jointly learn spectral embeddings and cluster assignments, directly producing the final clustering outcome.
  • Continuous Framework: Continuous one-step methods learn embeddings that partition data into k clusters without a separate discretization step.
  • Discrete Framework: Discrete one-step methods use spectral rotation, discrete spectral clustering, or discrete nonnegative spectral clustering to obtain discrete-valued embeddings.
  • Discrete Framework: DNSC enforces nonnegativity and orthogonality, making embeddings more consistent with discrete indicators and eliminating post-processing such as K-means.

IV. CATEGORY OF SPECTRAL CLUSTERING

Spectral clustering is categorized into single-view and multi-view approaches, with single-view methods organized by graph construction and partitioning strategies. Graph structure learning includes pairwise, anchor, and hypergraph paradigms, using fixed or adaptive constructions.

  • Single-view methods construct graphs from one data perspective, while multi-view methods integrate multiple representations for clustering.
  • Single-view spectral clustering is analyzed through graph structure paradigms and partitioning strategies.
  • The principal graph architectures are pairwise graphs, anchor graphs, and hypergraphs.
  • Pairwise Graphs: Pairwise graph methods include fixed constructions, adaptive neighbor methods, initial similarity matrix methods, and self-expressive approaches.
  • Pairwise Graphs: Self-expressive methods encode intrinsic relationships by representing each data point as a linear combination of other data points.
  • The surveyed methods are compared according to graph construction strategies and clustering steps.

2) Anchor Graph:

Anchor graphs replace full similarity matrices with anchor-based representations, reducing computational complexity for large-scale spectral clustering. Hypergraph methods preserve or model higher-order relationships through Laplacians, reductions, or tensors, with adaptive construction targeting complex data relationships.

  • Anchor Graph: Anchor graph methods replace the full similarity matrix with an anchor-based representation for large-scale data.
  • Anchor Graph: O(n^2) or O(n^3) complexity is reduced to O(nm), where n is the number of data points and m ≪ n is the number of anchors.
  • Anchor Graph: Anchor methods vary in anchor selection, fixed or adaptive graph construction, and one-step or two-step clustering processes.
  • Hypergraph Methods: Hypergraph spectral clustering uses hypergraph Laplacians, graph reductions, or tensor modeling to represent higher-order data structures.
  • Hypergraph Methods: Hypergraph Laplacian methods preserve multi-way relationships directly but incur higher computational costs.
  • Hypergraph Methods: All surveyed hypergraph methods use two-step clustering, while adaptive construction targets complex relationships, noise, and high-dimensional data.

B. Multi-view Spectral Clustering

Multi-view spectral clustering combines heterogeneous views through graph construction, matrix formulation, information fusion, spectral embedding, and partition optimization. Its graph-learning methods span fixed and adaptive pairwise approaches, including one-step and two-step clustering frameworks.

  • Multi-view spectral clustering incorporates complementary representations from diverse feature sets, measurement modalities, or representation schemes.
  • Graph Fusion: Fusion strategies include early fusion, late fusion, hybrid fusion, and score fusion, with the choice depending on data characteristics, task requirements, efficiency, and accuracy.
  • Matrix Construction: Matrix construction uses either similarity matrices encoding pairwise similarities or Laplacian matrices encoding similarities and degree information.
  • Graph Fusion: Graph fusion integrates consensus information, complementary information, and view weighting into a unified multi-view representation.
  • Pairwise Graph: Pairwise graph methods are organized into fixed and adaptive approaches, with adaptive strategies including adaptive neighbors, initial similarity graphs, and self-expressive learning.
  • Pairwise Graph: Fixed methods use predetermined neighbors, whereas adaptive methods adjust graph structure or weights and may obtain clusters directly without separate k-means post-processing.
  • Pairwise Graph: Self-expressive methods jointly address graph construction, fusion, view diversity, and partitioning, with some formulations providing convergence guarantees through Sylvester equations.

2) Anchor Graph:

Anchor graph methods improve scalability by approximating full similarity structures with representative anchors while preserving important data relationships. Surveyed methods vary in anchor selection, graph construction, view weighting, fusion, and whether clustering is performed in one or two stages.

  • Anchor graph methods use a small set of representative points to approximate full similarity structures, reducing computational complexity while preserving critical data relationships.
  • MVSC selects anchors with k-means on concatenated features, constructs fixed bipartite anchor graphs, and applies k-means to obtain final partitions.
  • DSC uses k-means anchor selection, adaptive anchor graphs, automatic view-specific weights, and single-step continuous optimization for a consistent partition.
  • FMDC and SFMC use k-means++ anchor selection and adaptive anchor-graph construction, combining views with learned weights in discretized optimization frameworks.
  • ERMC-AGR and ECMC use k-means-selected anchors with fixed graph construction, but differ in similarity-matrix generation and subsequent clustering procedures.
  • E2OMVC uses fixed anchor graphs and learned view weights for single-step discretized optimization that directly learns cluster indicators, while FMAGC follows a similar anchor-based framework.

3) Hypergraph:

Hypergraph-based multi-view spectral clustering captures higher-order relationships beyond pairwise connections but remains relatively underexplored. Future directions emphasize adaptive hypergraphs, richer neighbor selection, semi-supervised learning, and scalable graph construction for complex data.

  • Hypergraph: Hypergraph-based multi-view spectral clustering remains underexplored, with existing work using adaptive view weighting and hypergraph Laplacians to capture higher-order relationships.
  • Future Research Directions: Advanced Good Neighbor strategies could identify representative neighbors using criteria beyond traditional distance-based selection and incorporate domain knowledge or machine learning techniques.
  • Future Research Directions: Adaptive neighbor selection could combine similarity and dissimilarity information to construct more robust and discriminative graphs.
  • High-Order Adaptive Neighbor Selection: High-order neighbor selection using motifs or hypergraphs could capture broader relational context than simple pairwise connections.
  • Semi-Supervised Multi-View Spectral Clustering: Semi-supervised multi-view spectral clustering could combine labeled and unlabeled data through label-aware regularization, loss functions, or label propagation.
  • Adaptive Hypergraphs: Future research proposes adaptive hypergraph methods whose structures adjust to data characteristics and varying view importance.
  • Conclusion: The survey covers pairwise, anchor-based, and hypergraph graph construction in fixed and adaptive settings across single-view and multi-view spectral clustering.
Loading 2501.13597v2…