Research map / Learning theory and algorithms / Clustering
Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
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.
Proposes a primal-dual, LP-based combinatorial framework for overlapping (Local, Global) and robust (Robust) edge-colored clustering of hypergraphs, giving linear-time and fast approximation algorithms with matching integrality-gap and hardness results.
Problem
Edge-colored clustering (ECC) on hypergraphs and its overlapping (Local, Global) and robust variants, which are NP-hard; prior LP-rounding methods are slow and greedy methods are low quality.
Approach
A primal-dual method on a new LP relaxation that yields combinatorial algorithms: Local ECC gets a (b_local+1)-approximation in linear time; Robust and Global ECC get true 2(b+1)-approximations, using a stronger LP for Robust ECC with integrality gap O(b_robust).
Key results
- Local ECC: proposed algorithm averages 0.141 relative error vs 0.297 for greedy, and runs in 0.121s on average vs 146.47s for LP-rounding.
- Robust ECC: average relative error 0.042 vs 0.272 for greedy; much faster than LP-rounding on most datasets.
- Robust ECC LP integrality gap is at least b_robust+1 (vs infinite for the prior LP); Global ECC average relative error on nontrivial instances is 0.039 vs 0.912 for greedy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace the greedy combinatorial algorithm with the proposed primal-dual algorithm | Local ECC · Local ECC benchmark | average relative error estimate: 0.297 -> 0.141 | Helped |
| replace the greedy combinatorial algorithm with the proposed primal-dual algorithm | Local ECC · Local ECC benchmark | running time: The overall average running time was 0.121sec (proposed) versus 146.470sec (LP-rounding); proposed was more than twice a | Helped |
| replace the greedy combinatorial algorithm with the proposed primal-dual algorithm | Robust ECC · Robust ECC nontrivial instances | average relative error estimate: 0.272 -> 0.042 | Helped |
| replace the greedy combinatorial algorithm with the proposed primal-dual algorithm | Robust ECC · Robust ECC benchmark | running time | Hurt |
| replace the greedy combinatorial algorithm with the proposed primal-dual algorithm | Global ECC · Global ECC nontrivial instances | average relative error estimate: 0.912 -> 0.039 | Helped |
| replace the greedy combinatorial algorithm with the proposed primal-dual algorithm | Global ECC · Global ECC benchmark | running time | Hurt |
| replace the LP-rounding algorithm with the proposed algorithm | Local ECC · Local ECC benchmark | running time: 146.470sec -> 0.121sec | Helped |
| replace the LP-rounding algorithm with the proposed algorithm | Local ECC · Local ECC benchmark | relative error estimate | Hurt |
| replace the bicriteria Robust ECC algorithm with the proposed algorithm using a tripled budget | Robust ECC · Robust ECC benchmark | number of mistakes: the proposed algorithm's mistakes were, on average, 57.2% of those made by the bicriteria algorithm | Helped |
| replace the bicriteria Global ECC algorithm with the proposed algorithm using a doubled budget | Global ECC · Global ECC benchmark | number of mistakes: the proposed algorithm's mistakes were, on average, 68.9% of those made by the bicriteria algorithm | Helped |
Surprising findings
- The prior LP-rounding algorithm for Robust ECC often outputs solutions that violate the removal budget, so its results are 'superoptimal'.
Limitations
- Robust and Global ECC algorithms have superlinear running time due to dual updates.
- Inapproximability for Local ECC relies on UGC for the tight bound; the NP-hardness bound is weaker.
- Theoretical gap for Robust ECC between O(b) and the best known ratio remains open.
Experimental setup
Datasets: Brain MAG-10 Cooking DAWN Walmart Trivago
Benchmarks: Brain MAG-10 Cooking DAWN Walmart Trivago
Metrics: relative error estimate running time approximation ratio integrality gap
Baselines: Greedy combinatorial algorithm (Crane et al.) LP-rounding algorithm (Crane et al.)
Builds on: edge-colored clustering Crane et al. LP-rounding and greedy algorithms primal-dual method for approximation
Closest papers by meaning
- Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs (ICML 2023 · similarity 0.94)
- Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges (ICML 2025 · similarity 0.93)
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (NeurIPS 2025 · similarity 0.88)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.86)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.86)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.86)
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.