Three-Stage Subspace Clustering Framework with Graph-Based Transformation and Optimization

Shuai Yang, Wenqi Zhu, Yuesheng ZhuarXiv 2019 · OpenReview

TL;DR

This paper introduces a "Three-Stage Subspace Clustering" (3S-SC) framework that enhances existing subspace clustering methods by adding a crucial intermediate step: Graph-Based Transformation and Optimization (GBTO). GBTO refines the affinity matrix generated by initial data representation, leading to more accurate and robust clustering by better capturing the true relationships between data points.

What Problem Does This Paper Address?

High-dimensional data, common in fields like computer vision and document analysis, often lies within a union of lower-dimensional subspaces. Subspace clustering (SC) aims to group data points belonging to these underlying subspaces. Current state-of-the-art SC methods typically follow a two-stage process: first, a data representation technique (like sparse coding) generates an affinity matrix, and second, spectral clustering uses this matrix to partition the data. However, the affinity matrix produced in the first stage often fails to accurately reflect the true similarities between data points. This can be due to sparsity or low-rank properties that obscure genuine connections or introduce misleading ones, ultimately leading to suboptimal clustering results. The paper addresses this by proposing a way to improve the quality of the affinity matrix before spectral clustering is applied.

Methods

The core contribution is the Three-Stage Subspace Clustering (3S-SC) framework. This framework inserts a novel Graph-Based Transformation and Optimization (GBTO) module between the initial data representation and the final spectral clustering step.

Here's how it works:

  1. Stage 1: Data Representation: This stage is standard and involves using techniques like sparse coding (e.g., SSC-l1, LRR, OMP) to generate an initial coefficient matrix (C) and subsequently an affinity matrix (W) from the input data (X).
  2. Stage 2: Graph-Based Transformation and Optimization (GBTO): This is the novel part.
  3. Weight-Distance Transformation (WDT): The affinity matrix W is first transformed into a simulated distance matrix D. This step aims to convert similarities into dissimilarities, treating zero affinities as infinite distances.
  4. Distance Optimization (Floyd-Warshall): The Floyd-Warshall algorithm is applied to the simulated distance matrix D. This classic all-pairs shortest path algorithm effectively minimizes distances between data points by considering all possible intermediate paths, thereby uncovering and optimizing potential connections that were not apparent in the initial affinity matrix. This results in an optimized distance matrix D*.
  5. Distance-Weight Transformation (DWT): The optimized distance matrix D is then transformed back into a new, refined affinity matrix W using an inverse transformation. This W* is expected to represent a more authentic relationship between data points.
  6. Stage 3: Spectral Clustering: The refined affinity matrix W* is finally used for spectral clustering to obtain the final data partitions.

The paper also distinguishes between two implementations of 3S-SC:

  • Hard 3S-SC: Optimizes all elements in the affinity matrix, potentially increasing the number of non-zero entries.
  • Soft 3S-SC: Optimizes only the non-zero elements, preserving sparsity and acting as a more conservative refinement.

Datasets

The proposed 3S-SC framework was evaluated on:

  • Synthetic data: Used to demonstrate the general performance improvements.
  • Handwritten digits dataset: MNIST.
  • Human faces dataset: Extended Yale B (EYaleB).
  • USPS dataset: Another dataset for handwritten digits.

The paper does not introduce new benchmark datasets.

Key Insights and Ideas

  • The "missing middle" in SC: The paper highlights that the affinity matrix generated in the first stage of traditional SC methods is often the bottleneck. It's either too sparse (missing connections) or its non-zero entries don't accurately reflect true similarity.
  • GBTO as a universal enhancer: The GBTO module is designed to be a plug-in for various existing SC methods that rely on affinity matrices. This universality is a key strength, suggesting it can improve a wide range of SC algorithms.
  • Shortest paths reveal true connections: The application of Floyd-Warshall to simulated distances is a clever way to "discover" and strengthen weak or indirect connections between data points that are genuinely part of the same subspace but were not explicitly captured by the initial representation.
  • Optimizing similarity for better clustering: By minimizing distances (and thus maximizing optimized similarities), the framework aims to create a more cohesive and accurate representation of the underlying subspace structure, which directly benefits spectral clustering.
  • Hard vs. Soft refinement: The distinction between Hard and Soft 3S-SC offers flexibility. Hard 3S-SC might be better for dense data, while Soft 3S-SC provides a more cautious refinement, preserving sparsity and potentially avoiding the introduction of spurious cross-subspace connections.

Key Results

  • Improved Accuracy and NMI: Across various synthetic and real-world datasets (MNIST, USPS, EYaleB), 3S-SC methods (both Hard and Soft variants) consistently showed improved clustering accuracy and Normalized Mutual Information (NMI) compared to their base two-stage counterparts. For example, on USPS, 3S-SSC-l1 achieved 82.30% accuracy with 400 samples per subspace, compared to 60.13% for SSC-l1.
  • Enhanced Connectivity: The paper reports that 3S-SC methods generally achieve higher connectivity, as measured by the second smallest eigenvalue of the normalized Laplacian.
  • Universality Demonstrated: The framework successfully improved performance for SC methods using $\ell_0$, $\ell_1$, $\ell_2$, and nuclear norm regularizations, underscoring its broad applicability.
  • Robustness to Data Size: While 3S-SC generally improves performance, the paper notes that it sometimes doesn't work as well on very small datasets, which is acknowledged as a limitation. For larger datasets, GBTO's ability to capture more authentic relationships becomes more pronounced.
  • Time Complexity: The time complexity of Floyd-Warshall is $O(n^3)$, which is considered acceptable for many applications, especially when compared to the gains in accuracy.

Limitations and Future Work

  • Performance on Small Datasets: The authors acknowledge that 3S-SC may not perform optimally on very small datasets. This is identified as an area for future research.
  • Parameter Sensitivity (for base methods): While 3S-SC aims to improve existing methods, some base methods (like BDR) can still be sensitive to parameter choices. The paper suggests that 3S-BDR might mitigate some of this over-dependence.
  • Further Exploration of GBTO: The paper proposes two implementations (Hard/Soft) and discusses the transformation strategies. Future work could explore other transformation techniques or optimization strategies within the GBTO module.
  • Theoretical Guarantees: While theoretical analysis is mentioned, further exploration of the theoretical underpinnings of GBTO's effectiveness could be beneficial.

Summary updated

Abstract

Subspace clustering (SC) refers to the problem of clustering high-dimensional data into a union of low-dimensional subspaces. Based on spectral clustering, state-of-the-art approaches solve SC problem within a two-stage framework. In the first stage, data representation techniques are applied to draw an affinity matrix from the original data. In the second stage, spectral clustering is directly applied to the affinity matrix so that data can be grouped into different subspaces. However, the affinity matrix obtained in the first stage usually fails to reveal the authentic relationship between data points, which leads to inaccurate clustering results. In this paper, we propose a universal Three-Stage Subspace Clustering framework (3S-SC). Graph-Based Transformation and Optimization (GBTO) is added between data representation and spectral clustering. The affinity matrix is obtained in the first stage, then it goes through the second stage, where the proposed GBTO is applied to generate a reconstructed affinity matrix with more authentic similarity between data points. Spectral clustering is applied after GBTO, which is the third stage. We verify our 3S-SC framework with GBTO through theoretical analysis. Experiments on both synthetic data and the real-world data sets of handwritten digits and human faces demonstrate the universality of the proposed 3S-SC framework in improving the connectivity and accuracy of SC methods based on $\ell_0$, $\ell_1$, $\ell_2$ or nuclear norm regularization.
BibTeX
@misc{yang2019three,
  author = {Shuai Yang and Wenqi Zhu and Yuesheng Zhu},
  title = {{Three-Stage Subspace Clustering Framework with Graph-Based Transformation and Optimization}},
  year = {2019},
  eprint = {1905.01145},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.01145},
}

Loading related content...

Figure