Research map / Learning theory and algorithms / Clustering

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

AAAI 2024 · Learning theory and algorithms › Clustering · approach: Correlation clustering · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that graph spectral clustering (NCut/RatioCut) is equivalent to column subset selection on a vertex-edge matrix, transferring CSS algorithms to clustering and proving CSS NP-hard for sparse matrices.

Problem

Spectral clustering criteria (NCut, RatioCut) and column subset selection (CSS) with Frobenius approximation error appear unrelated; the paper asks whether results transfer between them.

Approach

Builds a vertex-edge matrix from graph edges so that any CSS selection of n-k independent columns yields a k-cluster partition whose NCut (or RatioCut) equals the CSS approximation error, enabling CSS algorithms (e.g., a weighted A*-like method) to be used for clustering.

Key results

• Proves equivalence: ApproxErr of CSS on the normalized vertex-edge matrix equals NCut (and RatioCut with the unnormalized matrix) for the induced partition.
• A weighted A*-like CSS algorithm gives an optimal NCut clustering for epsilon=0 and bounded suboptimal clustering for epsilon>0, compared against NJW on the cockroach graph (n=20, m=23).
• Proves CSS is NP-hard even when each column has only two nonzero elements, by reduction from NCut minimization.

Measured effects reported in the paper

Limitations

• Full proofs are deferred to the full paper, so the theory is only sketched here.
• Experiments are limited to a single small synthetic graph (cockroach graph, n=20).
• Optimal algorithm is very slow for epsilon=0; practical scaling is only addressed by the epsilon>0 variant.

Experimental setup

Datasets: cockroach graph (Guattery and Miller 1998)

Benchmarks: cockroach graph clustering accuracy (n=20, m=23)

Metrics: clustering accuracy NCut bound

Baselines: NJW spectral clustering

Builds on: spectral clustering (Ng, Jordan, Weiss 2001) weighted A* for CSS (He et al. 2019) NP-hardness of CSS for dense matrices (Shitov 2021)

Closest papers by meaning

• Graph Clustering Methods Derived from Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.94)
• Spectral Modification of Graphs for Improved Spectral Clustering (NeurIPS 2019 · similarity 0.89)
• Compressive Spectral Clustering (ICML 2016 · similarity 0.89)
• Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.89)
• Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.89)
• Signed Laplacians for Constrained Graph Clustering (ICML 2025 · similarity 0.87)