# Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach

arXiv: https://arxiv.org/abs/2505.18043 · HTML: https://mlsanity.com/paper/2505.18043/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 53 references that are in the map.
- First posted on arXiv 23 May 2025.

## Builds on (most cited first, 10 of 10)

- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Generative hypergraph clustering: from blockmodels to modularity](https://mlsanity.com/paper/2101.09611/) (2021)
- [Inhomogeneous Hypergraph Clustering with Applications](https://mlsanity.com/paper/1709.01249/) (2017)
- [Clustering in graphs and hypergraphs with categorical edge labels](https://mlsanity.com/paper/1910.09943/) (2019)
- [Unifying Sparsest Cut, Cluster Deletion, and Modularity Clustering Objectives with Correlation Clustering](https://mlsanity.com/paper/1712.05825/) (2017)
- [Motif Clustering and Overlapping Clustering for Social Network Analysis](https://mlsanity.com/paper/1612.00895/) (2016)
- [Correlation Clustering Generalized](https://mlsanity.com/paper/1809.09493/) (2018)
- [Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs](https://mlsanity.com/paper/2208.06506/) (2022)
- [Overlapping and Robust Edge-Colored Clustering in Hypergraphs](https://mlsanity.com/paper/2305.17598/) (2023)
- [Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges](https://mlsanity.com/paper/2502.13000/) (2025)

## Abstract (arXiv)

Clustering is a fundamental task in both machine learning and data mining. Among various methods, edge-colored clustering (ECC) has emerged as a useful approach for handling categorical data. Given a hypergraph with (hyper)edges labeled by colors, ECC aims to assign vertex colors to minimize the number of edges where the vertex color differs from the edge's color. However, traditional ECC has inherent limitations, as it enforces a nonoverlapping and exhaustive clustering. To tackle these limitations, three versions of ECC have been studied: Local ECC and Global ECC, which allow overlapping clusters, and Robust ECC, which accounts for vertex outliers. For these problems, both linear programming (LP) rounding algorithms and greedy combinatorial algorithms have been proposed. While these LP-rounding algorithms provide high-quality solutions, they demand substantial computation time; the greedy algorithms, on the other hand, run very fast but often compromise solution quality. In this paper, we present an algorithmic framework that combines the strengths of LP with the computational efficiency of combinatorial algorithms. Both experimental and theoretical analyses show that our algorithms efficiently produce high-quality solutions for all three problems: Local, Global, and Robust ECC. We complement our algorithmic contributions with complexity-theoretic inapproximability results and integrality gap bounds, which suggest that significant theoretical improvements are unlikely. Our results also answer two open questions previously raised in the literature.