Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract)

Guihong Wan, Wei Mao, Yevgeniy R. Semenov, Haim SchweitzerAAAI 2024 · DOI

Abstract

This work identifies a fundamental mathematical link between Graph Spectral Clustering (GSC) and Column Subset Selection (CSS). By demonstrating that these two problems are formally equivalent when applied to vertex-edge matrices, we enable the cross-pollination of algorithms and complexity results between graph theory and linear algebra. Specifically, we show that the Frobenius norm error in CSS is exactly equal to the cut value in GSC. This equivalence allows for the development of clustering algorithms with optimality guarantees and proves the NP-hardness of CSS for sparse matrices.

Introduction

In data science, partitioning data into meaningful groups is a core challenge. Graph Spectral Clustering (GSC) addresses this by finding partitions in a network that minimize the weight of edges between clusters, typically using metrics like Normalized Cut (NCut). Separately, Column Subset Selection (CSS) seeks to find a subset of columns that best approximates a given matrix. While GSC often relies on eigenvector-based heuristics, CSS has a rich history of approximation algorithms. This paper bridges these domains, establishing that GSC can be framed as a CSS problem.

Methodology

The researchers propose a mapping based on the vertex-edge matrix of a graph. They prove that selecting $n-k$ columns from this matrix is mathematically identical to partitioning the graph into $k$ clusters.

  1. Equivalence Theorem: The squared Frobenius norm error of a column subset is shown to be exactly equal to the cut value of the corresponding graph partition.
  2. Algorithmic Framework: By treating CSS as a "black box," any CSS algorithm can be utilized for graph clustering. The authors specifically adapt the $A^*$ search algorithm to provide the first non-trivial GSC algorithm with optimality guarantees or provable error bounds.

Key Results and Discussion

The proposed method was tested against the standard NJW spectral clustering algorithm using the "cockroach" graph, a structure designed to be difficult for spectral methods.

Comparison of NCut values and approximation bounds across different cluster counts (k) and error tolerances (epsilon).

As shown in the table above, the CSS-based approach (with $\epsilon=0$) consistently identifies the optimal NCut, matching or exceeding the performance of the NJW algorithm. The parameter $\epsilon$ serves as a tunable trade-off between computational efficiency and solution quality. For instance, at $\epsilon=0.1$, the algorithm provides a significant speedup while maintaining a provable bound on the distance from the optimal cut.

Beyond algorithmic improvements, this equivalence has profound implications for complexity theory. By leveraging the known NP-hardness of the NCut problem, the authors proved that Column Subset Selection is NP-hard even for extremely sparse matrices (those with only two non-zero entries per column), settling an open question in the field.

Conclusion

The formal equivalence between GSC and CSS provides a powerful new lens for both fields. While the current optimal implementation is computationally demanding for very large graphs, the theoretical framework paves the way for a new class of clustering algorithms with rigorous guarantees. Future work will explore the application of this relationship to other clustering objectives and larger-scale datasets.

Summary updated

BibTeX
@inproceedings{wan2024equivalence,
  author = {Guihong Wan and Wei Mao and Yevgeniy R. Semenov and Haim Schweitzer},
  title = {{Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i21.30521},
}

Loading related content...

Figure