A Unified Framework for Discrete Spectral Clustering

Yang Yang, Fumin Shen, Zi Huang, Heng Tao ShenIJCAI 2016 · OpenReview

Abstract

Spectral clustering has been playing a vital role in various research areas. Most traditional spectral clustering algorithms comprise two independent stages (i.e., first learning continuous labels and then rounding the learned labels into discrete ones), which may lead to severe information loss and performance degradation. In this work, we study how to achieve discrete clustering as well as reliably generalize to unseen data. We propose a unified spectral clustering scheme which jointly learns discrete clustering labels and robust out-of-sample prediction functions. Specifically, we explicitly enforce a discrete transformation on the intermediate continuous labels, which leads to a tractable optimization problem with a discrete solution. Moreover, to further compensate the unreliability of the learned labels, we integrate an adaptive robust module with $\ell_{2,p}$ loss to learn prediction function for unseen data. Extensive experiments conducted on various data sets have demonstrated the superiority of our proposal as compared to existing clustering approaches.

Introduction

Spectral clustering is a cornerstone of modern machine learning, prized for its ability to uncover complex, non-linear structures that simpler algorithms like $k$-means often overlook. However, the method faces two significant challenges: the Discretization Gap and the Out-of-Sample Problem.

The discretization gap arises because finding discrete cluster labels is an NP-hard problem. Traditional methods relax this constraint to find continuous solutions, which are then rounded—often using $k$-means—into discrete categories. This two-stage approach frequently results in substantial information loss. Furthermore, traditional spectral clustering lacks a natural mechanism for handling new, unseen data, requiring computationally expensive re-runs or independent, sub-optimal regression models.

Methodology

To address these issues, we propose a unified objective function that optimizes three components simultaneously:

  1. Discrete Label Learning ($Y$): A discrete indicator matrix is integrated directly into the objective function to avoid the pitfalls of post-hoc rounding.
  2. Spectral Rotation ($Q$): A rotation matrix is employed to align the continuous manifold ($F$) with the discrete cluster space ($Y$), minimizing transformation errors.
  3. Robust Prediction ($W$): A linear mapping is integrated to facilitate out-of-sample predictions. By utilizing an $\ell_{2,p}$ loss function ($0 < p < 2$), the model becomes sample-wise sparse, effectively down-weighting noisy samples and outliers.

The resulting non-convex problem is solved via an efficient iterative algorithm. As shown in the convergence analysis, the objective function value stabilizes rapidly, ensuring computational efficiency.

Convergence curve for the Wine dataset.

Experimental Results

The framework was evaluated on six diverse datasets from the UCI repository: Segment, Vehicle, Vote, Ecoli, Solar, and Wine. We compared our method against established baselines including $k$-means (KM), Discriminative $k$-means (DKM), standard Spectral Clustering (SC), and Spectral Embedding Clustering (SEC).

Comparison of ACC and NMI across datasets.

Our unified framework (denoted as 'Y' in the figures) consistently outperformed competitors in both Accuracy (ACC) and Normalized Mutual Information (NMI). For instance, on the Wine dataset, the model achieved an ACC of 0.9101, a significant improvement over SEC's 0.7416. Similarly, the NMI on the Vote dataset reached 0.6441, demonstrating superior alignment with ground truth labels compared to the next best method, LLC (0.5189). The comparison against intermediate configurations—'FQ+Binarization' and 'F+Spectral Rotation'—highlights that the joint optimization of discrete labels is the primary driver of these performance gains.

Discussion and Future Work

The results underscore the importance of joint optimization. By forcing discrete labels and the prediction function to interact during training, the model produces labels that generalize more effectively. The use of spectral rotation proves superior to simple binarization, and the $\ell_{2,p}$ norm provides essential robustness against outliers.

While effective, the current model relies on a linear mapping for predictions, which may be limited in extremely high-dimensional, non-linear scenarios. Future research could explore non-linear predictors or kernel-based methods. Additionally, scaling the initial Laplacian matrix construction for massive datasets remains a challenge to be addressed through approximation techniques like Nyström methods.

Summary updated

Abstract

Spectral clustering has been playing a vital role in various research areas. Most traditional spectral clustering algorithms comprise two independent stages (i.e., first learning continuous labels and then rounding the learned labels into discrete ones), which may lead to severe information loss and performance degradation. In this work, we study how to achieve discrete clustering as well as reliably generalize to unseen data. We propose a unified spectral clustering scheme which jointly learns discrete clustering labels and robust out-ofsample prediction functions. Specifically, we explicitly enforce a discrete transformation on the intermediate continuous labels, which leads to a tractable optimization problem with a discrete solution. Moreover, to further compensate the unreliability of the learned labels, we integrate an adaptive robust module with l2,p loss to learn prediction function for unseen data. Extensive experiments conducted on various data sets have demonstrated the superiority of our proposal as compared to existing clustering approaches.
BibTeX
@inproceedings{yang2016unified,
  author = {Yang Yang and Fumin Shen and Zi Huang and Heng Tao Shen},
  title = {{A Unified Framework for Discrete Spectral Clustering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=rkWvrHz_Wr},
}
Figure