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.
- 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.
- 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.
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