Research map / Learning theory and algorithms / Clustering
Graph Clustering Methods Derived from Column Subset Selection (Student Abstract)
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 spectral clustering under the NCut criterion can be reformulated as column subset selection on a normalized edge matrix, yielding a black-box graph clustering algorithm that can use any CSS method.
Problem
Multi-way spectral clustering minimizes NCut, which is an NP-hard combinatorial problem usually approximated by relaxations; the paper asks whether CSS, a feature selection/dimension reduction technique, can compute spectral clusterings.
Approach
Builds a normalized edge matrix whose columns are scaled edge vectors; proves that selecting n-k linearly independent columns (a CSS solution) yields a subgraph whose connected components are a k-way partition, with NCut equal to the CSS approximation error. This gives a black-box graph clustering algorithm that plugs in any CSS algorithm (QRP, GREEDY).
Key results
- On a COIL-derived pixel graph, GREEDY achieves the lowest NCut (e.g., 0.0006 at k=2), NJW second, and QRP third (e.g., 0.0031 at k=2).
- QRP, despite worse NCut, produces clusters the authors describe as 'very reasonable' visually.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use GREEDY instead of QRP for CSS-based clustering | CSS-derived graph clustering · COIL image graph, k=2 | NCut: 0.0031 -> 0.0006 | Helped |
| Use GREEDY instead of QRP for CSS-based clustering | CSS-derived graph clustering · COIL image graph, k=3 | NCut: 0.0059 -> 0.0029 | Helped |
| Use GREEDY instead of QRP for CSS-based clustering | CSS-derived graph clustering · COIL image graph, k=4 | NCut: 0.0164 -> 0.0058 | Helped |
| Use GREEDY instead of QRP for CSS-based clustering | CSS-derived graph clustering · COIL image graph, k=6 | NCut: 0.0253 -> 0.0137 | Helped |
| Use GREEDY instead of NJW | Graph clustering · COIL image graph, k=2 | NCut: 0.0006 -> 0.0006 | No clear effect |
| Use GREEDY instead of NJW | Graph clustering · COIL image graph, k=3 | NCut: 0.0037 -> 0.0029 | Helped |
| Use GREEDY instead of NJW | Graph clustering · COIL image graph, k=4 | NCut: 0.0076 -> 0.0058 | Helped |
| Use GREEDY instead of NJW | Graph clustering · COIL image graph, k=6 | NCut: 0.0169 -> 0.0137 | Helped |
| Use QRP instead of NJW | Graph clustering · COIL image graph, k=2 | NCut: 0.0006 -> 0.0031 | Hurt |
| Use QRP instead of NJW | Graph clustering · COIL image graph, k=3 | NCut: 0.0037 -> 0.0059 | Hurt |
| Use QRP instead of NJW | Graph clustering · COIL image graph, k=4 | NCut: 0.0076 -> 0.0164 | Hurt |
| Use QRP instead of NJW | Graph clustering · COIL image graph, k=6 | NCut: 0.0169 -> 0.0253 | Hurt |
Surprising findings
- QRP has the worst NCut in the experiments yet yields visually reasonable clusters.
Limitations
- Experiments are a small qualitative/NCut comparison on a single COIL image graph.
- Full proofs are deferred to an extended version, so the equivalence is only sketched here.
Experimental setup
Datasets: COIL image dataset (graph constructed from adjacent pixels)
Benchmarks: COIL image graph clustering
Metrics: NCut visual inspection of clusters
Baselines: NJW spectral clustering QRP GREEDY
Builds on: spectral clustering (Ng, Jordan, Weiss 2001) QR factorization with column pivoting (Businger and Golub 1965) greedy column subset selection (Farahat et al. 2015)
Closest papers by meaning
- Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.94)
- Local and Global Optimization Techniques in Graph-Based Clustering (CVPR 2018 · similarity 0.88)
- Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract) (AAAI 2024 · similarity 0.87)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.85)
- Clustering by Mining Density Distributions and Splitting Manifold Structure (AAAI 2025 · similarity 0.85)
- Dynamic Spectral Clustering with Provable Approximation Guarantee (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.