Research map / Learning theory and algorithms / Clustering
Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
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.
Gives a tighter 3-approximation analysis for two STC-based Cluster Deletion algorithms (MatchFlipPivot and STC-LP rounding), a degree-based deterministic pivot rule, an O(m^1.5) maximal open-wedge algorithm, and a min s-t cut reduction for the STC LP.
Problem
Cluster Deletion (NP-hard: delete minimum edges to partition a graph into cliques) has approximation algorithms with weak guarantees (4) for fast STC-based methods, and existing deterministic versions are complicated and slow; the STC LP solver relies on black-box LP software that does not scale.
Approach
Tighter analysis showing both STC-based pivoting algorithms are 3-approximations; derandomization by greedily pivoting on the maximum-degree node in the auxiliary graph; and a purely combinatorial reduction of the STC LP to a minimum s-t cut problem.
Key results
- Proves MatchFlipPivot and STC-LP rounding are deterministic 3-approximations using degree-based pivoting, and a matching lower bound of 3 for MatchFlipPivot.
- Degree-based deterministic pivoting (DegMFP) achieves ratios nearly identical to RatMFP and better than RanMFP-100 on SNAP graphs, and runs an order of magnitude faster than RatMFP.
- Combinatorial min-cut STC LP solver solves the LP on 21 of 34 graphs versus 6 of 34 for Gurobi, with the largest solved graph having 1,971,281 nodes and 2,766,607 edges.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add degree-based pivoting instead of 100 random-pivot trials | MatchFlipPivot · SNAP graph experiments | approximation ratio | Helped |
| Use degree-based pivoting instead of minimizing |B_u|/|N_u| | MatchFlipPivot · SNAP graph experiments | runtime | Helped |
| Replace Gurobi with the combinatorial min-cut STC LP solver | STC LP solving · ca-AstroPh | runtime: 132.727 -> 41.889 | Helped |
| Replace Gurobi with the combinatorial min-cut STC LP solver | STC LP solving · ca-GrQc | runtime: 1.038 -> 0.318 | Helped |
| Replace Gurobi with the combinatorial min-cut STC LP solver | STC LP solving · ca-HepTh | runtime: 2.033 -> 0.815 | Helped |
| Add cluster-merging postprocessing to DegMFP (ablation) | DegMFP · Netscience, Harvard500, football, Erdos991 | approximation ratio: 1.72 -> 1.58; 1.95 -> 1.79; 1.79 -> 1.47; 1.99 -> 1.67 | Helped |
| Add cluster-merging postprocessing to DegMFP (ablation) | DegMFP · celegansmetabolic, polbooks, email, SmaGri | approximation ratio: 1.99 -> 1.78; 1.98 -> 1.68; 1.98 -> 1.80; 2.00 -> 1.85 | Helped |
| Add cluster-merging postprocessing to DegMFP (ablation) | DegMFP · Roget, celegansneural, adjnoun, polblogs | approximation ratio: 2.00 -> 1.69; 2.00 -> 1.81; 2.00 -> 1.76; 2.00 -> 1.92 | Helped |
| Round the combinatorial STC LP solution with degree-based pivoting rather than use MFP | Cluster Deletion · large SNAP graphs | approximation ratio | Hurt |
| Use degree-based or ratio-based pivoting instead of random pivoting | STC + Pivot algorithms · Cluster Deletion | approximation guarantee: 4 -> 3 | Helped |
| Use the combinatorial STC LP solver instead of Gurobi | STC LP solver · 34-graph solver evaluation | graphs solved: 6 of 34 -> 21 of 34 | Helped |
Surprising findings
- The STC LP rounding algorithm tends to give worse cluster deletion approximation ratios than MFP in practice, despite a tighter lower bound.
- MFP labels 63-99.7% of edges as weak, so on many graphs it essentially deletes nearly all edges and achieves ratios close to 2.
Limitations
- The authors' practical implementation uses push-relabel rather than the theoretically fastest max-flow solvers.
- The cluster merging post-processing heuristic does not scale well (over 2 hours on the largest Facebook100 graph used).
- The analysis for STC LP rounding is not tight as the paper notes; the rounding scheme treats half-edges and full-edges uniformly.
Experimental setup
Datasets: SNAP graphs (soc-LiveJournal1, com-Orkut, amazon, ca-*, cit-*, com-Amazon, and others) Facebook100 SuiteSparse small graphs (Arenas, Newman, Pajek, Mathworks collections)
Benchmarks: SNAP graphs Facebook100 SuiteSparse small graphs
Metrics: approximation ratio (cluster deletion solution / lower bound runtime lower bound value
Baselines: MatchFlipPivot (randomized) STC LP rounding with Gurobi RatMFP RanMFP-100
Builds on: MatchFlipPivot STC LP rounding Pivot algorithm for correlation clustering Veldt STC labeling
Closest papers by meaning
- Fast Combinatorial Algorithms for Min Max Correlation Clustering (ICML 2023 · similarity 0.89)
- Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds (ICML 2022 · similarity 0.88)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.88)
- Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges (ICML 2025 · similarity 0.88)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.87)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.87)
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.