TY - JOUR
AU - Wan, Guihong
AU - Mao, Wei
AU - Semenov, Yevgeniy R.
AU - Schweitzer, Haim
PY - 2024/03/24
Y2 - 2024/07/25
TI - Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract)
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 38
IS - 21
SE - AAAI Student Abstract and Poster Program
DO - 10.1609/aaai.v38i21.30521
UR - https://ojs.aaai.org/index.php/AAAI/article/view/30521
SP - 23673-23675
AB - The common criteria for evaluating spectral clustering are NCut and RatioCut. The seemingly unrelated column subset selection (CSS) problem aims to compute a column subset that linearly approximates the entire matrix. A common criterion is the approximation error in the Frobenius norm (ApproxErr). We show that any algorithm for CSS can be viewed as a clustering algorithm that minimizes NCut by applying it to a matrix formed from graph edges. Conversely, any clustering algorithm can be seen as identifying a column subset from that matrix. In both cases, ApproxErr and NCut have the same value. Analogous results hold for RatioCut with a slightly different matrix. Therefore, established results for CSS can be mapped to spectral clustering. We use this to obtain new clustering algorithms, including an optimal one that is similar to A*. This is the first nontrivial clustering algorithm with such an optimality guarantee. A variant of the weighted A* runs much faster and provides bounds on the accuracy. Finally, we use the results from spectral clustering to prove the NP-hardness of CSS from sparse matrices.
ER -