Edge-colored Clustering in Hypergraphs: A MaxECC Approximation

We study the MaxECC problem, where given an edge-colored hypergraph with $k$ colors and edge size $r$, we seek to color the vertices of the graph in order to maximize the number of satisfied edges (edges having the same color as their extremities): this is an effective mechanism for clustering (coloring) objects based on their multi-way interactions with one another in a system, providing significant applications in machine learning, clustering, and data mining. We exponentially improve upon the approximation ratio of an existing algorithm to $\frac{1}{r+1}$, present another novel dependent-rounding algorithm with an approximation ratio of $1/ \lceil \frac{k}{2}\rceil$, and modify the initial algorithm via analytical scaling techniques in order to achieve an approximation factor of $(1-e^{-r})/r$. We then apply our scaling algorithm to graph MaxECC and improve the best-known approximation factor for all hypergraphs: in particular, our algorithm provides an approximation factor of $0.43$ as opposed to the previously-known $0.38$ factor for graphs.

Hypergraph clustering is a fundamental problem in machine learning, but it is computationally intractable (NP-hard). This motivates the development of approximation algorithms. We use LP relaxation (solving a variant of the problem with fewer constraints) and randomized rounding (adding the constraints back). Our main contribution improves upon the previous best approximation exponentially, and we also develop a new approximation algorithm parameterized by the number of clusters. In practice, better approximation guarantees can translate into more accurate clustering, improved robustness, and more reliable performance in machine learning applications that rely on these complex higher-order relationships.