Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
Authors: Changyeol Lee
Yongho Shin
Hyung-Chan An
Venue: NeurIPS 2025 poster ()
Keywords: overlapping edge-colored clustering
robust edge-colored clustering
edge-colored clustering
hypergraph clustering
primal-dual methods
approximation algorithms
Primary area: general_machine_learning
TL;DR: This paper presents improved algorithms for overlapping and robust clustering of edge-colored hypergraphs; our algorithms combine the strengths of LP with the efficiency of combinatorial algorithms, efficiently producing high-quality solutions.

Abstract: 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 a family of algorithms 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.

Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach
Changyeol Lee"
Yongho Shin' Institute of Computer Science University of Wroctaw Wroclaw, Poland yonghoßcs. uni wroc. pl
Department of Computer Science and Engineering Yonsei University Seoul, South Korea 777 [77]joh@@yonei.. ac kr
Hyung-Chan An
Department of Computer Science and Engincering Yonsei University
Seoul, South Korea
hyung- an@yonsei. ac.
Abstract
Clustering is fundamental task in both machine learning and data mining. Among various methods, edge-colored clustering (ECC) has emerged as useful approach for handling categorical data. Given 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 L-rronnding 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, present family of algorithms that combines the strengths of LP with the computational efficiency combinatorial algorithms. Both experimental and theoretical analyses show that algorithms efficiently produce high-quality solutions for all three problems: LOCAL, GLOBAL, and ROBUST ECC. We complement our algorithmic contributions with complexity-theoren 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.
1 Introduction
Edge-colored clustering (ECC), in particular, is useful model when interactions between the items be clustered are represented as categorical data [ To provide intuition, let us consider the following simple, given a set of food ingredients.
Clustering is a fundamental task in both machine learning and data mining [24 35 25
illustrative example from prior work 34
19 20
"Equal contributions.
t Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

recipes that use them, and (noisy) labeling of these recipes indicating their cuisine (e.g., Italian or Indian), can we group the food ingredients by their cuisine? To address this question. we can begin by considering a hypergraph whose vertices correspond to ingredients, (hyper)edges represent recipes, and edge colors correspond to cuisines. We can then find labeling of the ingredients such that, in most recipes, all ingredient labels match the recipe's label. This is precisely what ECC does: given an edge-colored hypergraph, the goal is to assign colors to its vertices so that the number of edges where vertex colors differ from the edge color is minimized. Intuitively, this problem offers an approach for clustering vertices when edge labels are noisy.
However, ECC has an inherent limitation in that it insists on assigning exactly one color to every vertex, enforeing nonoverlapping and exhaustive clustering. In the above illustrative example, food ingredients are often shared across geographically neighboring cuisines, indicating that overlapping clustering may be preferable. Moreover, some ingredients, such as salt, commonly appear in nearly all cuisines and may be considered outliers that should ideally be excluded from the clustering process. To address these limitations, three generalizations of ECC, namely, LOCAL. ECC, GLOBBL ECC, and ROBUST ECC, have been proposed [1]. Among them, LOCAL ECC and GLOBAL ECC allows overlapping clustering: in LOCAL ECC, a local budget blocal that specifies the maximum number of colors each vertex can receive is given an input parameter, thereby allowing clusters to overlap. In GLOBAL ECC, vertices may be assigned multiple colors, but with the total number of extra assignments constrained by global budger bglobal given as input. On the other hand, ROBUST ECC enhances robustness against vertex outliers by allowing up to brobust vertices to be deleted from the hypergraph. This budget brabust is also specified as part of the input. (Alternatively, this can be viewed as designating those vertices as "wildcards" that can be treated as any color.)
While LOCAL ECC, GLOBAL ECC, and ROBUST ECC are useful extensions of ECC that effec- tively address its limitations, these problems are unfortunately NP-hard, making exact solutions computationally intractable. This directly follows from the NP-hardness of ECC B a common special case of all three problems. This computational intractability naturally motivates the study of approximation algorithms for these problems. Recall that an algorithm is called a p-approximation algorithm if it runs in polynomial time and guarantees a solution within a factor of p relative to the optimum.
In this paper, we present a new family of algorithms for overlapping and robust clustering of edge- colored hypergraphs that is linear programming- based (LP--based) yet also combinatorial. Previously, combinatorial algorithms and )ombinaaiaaao LP-based algorithms have been proposed for these problems. For LOCAL ECC, Crane et al. [9] gave greedy combinatorial r- r-approximation algorithm, where r is the rank of the hypergraph. Their computational evaluation demonstrated that this algorithm runs remarkably faster than their own LP-rounding algorithm, at the expense of trade-off solution quality. The theoretical analysis [99 of the LP-rounding algorithm successfully obtains approximation ratio that does not depend on they showed that their algorithm is (brocal + 1) --aappooximation algorithm. They state it as an open question whether there exists an ((1)- approximation algorithm for LOCAL ECC. For ROBUST ECC as well, Crane et al. gave a greedy r-approximation algorithm; however, their LP-rounding algorithm in this case does not guarantee solution feasibility. According to their computational evaluation, solutions produced by the LP-rounding algorithm were of very high quality but violated the budget constraint, which is reflected in the theoretical result: their algorithm is bicriteria (2 + e, 2 & )-approoxmnttion algorithm for any positive e, i.e., an algorithm that produces an (2 + + appproxxinttoo solution but violates the budget constraint by a multiplicative factor of most 2 + 4. Finally for GLOBAL ECC, Crane al. gave
similar results: a greedy r-approximation algorithm and a bicriteria (bglobal + 3 3 c, 0atobar +2) approximation algorithm for any positive e, where the latter, empirically, was slow but produced solutions of high quality. Since their bicriteria approximation ratio is not (O(1), O(1)) for GLOBAL ECC, Crane et al. left another open question whether bicriteria (0(1).0(1) (0)aaappxxpoooiiattoo is possible for GLOBAL ECC.
The primal-dual method is an algorithmic approach that constructs combinatorial algorithms based on LP, allowing one to combine the strengths of both worlds (29 30). Our algorithms are designed using the primal-dual method. We analyze its performance both experimentally and theoretically. For LOCAL ECC, our approach yields combinatorial (brocal + 1) apprroxiimttoon algorithm, which the same approximation ratio as Crane al.'s LP-rounding algorithm; however, our algorithm is combinatorial and runs in linear time. The experiments confirmed that, compared to the previous combinatorial algorithm, our algorithm brings improvement in both computation time and solution
2

---

quality. We complement this algorithmic result by showing inapproximability results that match our approximation ratio; this answers one of Crane et al.'s 's open questions. For ROBUST ECC and GL.OBAT. ECC, our results give a true (non-bicriteria) approximation algorithm, avoiding the need for bicriteria approximation Our true approximation algorithm for ROBUST ECC, with the ratio of (bbrobust + 1), was enabled by our new LP relaxation: the integrality gap of the relaxation used by previous results is +00 [9), whereas our LP has an integrality gap of (brobust). In fact, we show that our gap is (brobust) suggesting that our ratio may be asymptotically the best one can achieve based on this relaxation. For GLOBAL ECC, our true approximation algorithm has the ratio of 2(bglobal + 1), and our bicriteria approximation algorithm has the ratio of (2 c, + 2). This affirmatively answers another open question of Crane et al.: bicriteria (0( (a)aaapproiimaaoonn for GLOBAL ECC is indeed possible. We also show that our relaxation has the integrality gap of (Uggobaa).
Below, we summarize which contributions of our work are presented in which sections of the paper.
In Section we present our algorithm for LOCAL ECC; its performance is analyzed both experimentally (Section 4.2) and theoretically (Section 3.I and Appendix [A.I]. We also present the inapproximability result (Theorems 3.3 and 3.4) that answers Crane et al.'s open question [19
whose technical proof is deferred to Appendix A.3
Section 3.2 we present our true approximation algorithm for ROBUST ECC based on new stronger LP Formulation. Our algorithm's performance is analyzed both experimentally (Section 4.3
and theoretically (Section 3.2 and Appendix [B.2). including an integrality gap lower bound (Section 3.2 note that an upper bound is implied by the proof of Theorem 3.5).
In Section 3 2 and Appendix C.2 present our approximation algorithm for GLOBBAL. ECC, whose performance is analyzed both experimentally (Section 4.3) and theoretically (Appendix C.3) This algorithm extends the bicriteria setting (Section 3.2 and Appendix C.5), answering another open question of Crane et al. 19
We note that LP-rounding algorithms based on our relaxations can match the ratios of our combi- natorial true approximation algorithms. However, we omit them from this paper, they offer no improvement in performance guarantees while requiring significantly more computation time to solve LPs.
Related work. ECC has been used for a variety of tasks including categorical community detection, temporal community detection 4 and diverse and experienced group discovery [5] recently, it has also been applied to fair and balanced clustering [20]. Angel et al. [8] initiated the study of clustering edge-colored graphs (not hypergraphs). After showing its NP-hardness, they gave the first approximation algorithm for the (maximization) problem, with the approximation ratio
of = Subsequent studies [ 3 2 improved this ratio, and recently, Crane et al. 200 achieved 154 405 -approximationn Veldt [48) showed its -Prhhardness.
Given the emerging importance of clustering data with higher-order interactions 12 40 Amburg et al. 4 addressed clustering on edge-colored hypergraphs for the first time, and gave a-apprxximation algorithms. Veldt [48) presented combinatorial 2-approximation algorithm along with a UGC- hardness ruling out any constant smaller than
As was highlighted by previous studies 6 4 48), ECC is closely related to correlation clustering
problems 9. which has been extensively studied in machine learning and data mining [52 They share the common feature of taking (hyper)edges representing similarity between vertices as input, and thus both have been applied to similar sets of taks such community detection 49 4. However, correlation clustering differs from ECC in that it treats the absence of an edge as an indication of dissimilarity, whereas ECC interprets merely as lack of information. Chromatic correlation clustering, which introduces categorical edges to correlation clustering, is another closely related problem to ECC 15 on hypergraphs and received significant interest [36] 26 28 it appears that the chromatic hypergraph correlation clustering has never been studied to the best of our knowledge. We note that this may be an
43 50]
51 Interestingly, unlike correlation clustering which was studied
*If. in some contexts, bicriteria approximation algorithm acceptable use, we could instead use true approximation algorithm with a relaxed budget. Thus, once a true approximation algorithm becomes available, the need for bicriteria approximation algorithms is reduced. However, our algorithms can also be analyzed in the bicriteria setting for both GLOBAL ECC and ROBUST ECC. See Appendices C.5 and B.3
3

---

interesting future direction of research. Other variants of correlation clustering, including overlapping variants 6 7 39 17], and robust variants [2] 32 have been studied. We refer interested readers to the book by Bonchi, García-Soriano, and Gullo 14 and references therein.
2 Problem definitions
In this section, we formally define the problems considered in this paper. First, we describe the part of the input that is common to all three problems. We are given hypergraph H EV and set of colors as input. Since is hypergraph, we have C 2V. Each edge e E E' is associated with color Ce C.
Given a node coloring - C, we say an edge e E is a mistake if there exists node v E whose assigned color a (v) differs from Ce, i.e., ce * (v). Otherwise, we say that is satisfied. In LOCAL ECC and GLOBAL ECC, a node coloring a V 2 assigns (possibly) a multiple number of colors to each node. In these problems, we say E E is a mistake if there exists a node E whose assigned color does not include ce, i.c. ce & (v)).
Definition 2.1. In LOCAL ECC, in addition to H. C, and {Ce]eEB. g. a local budget blocal E Σz1 is given as input. The goal is to find node coloring o V - 2 such that [o(()) S blocal for all to minimize the number of mistakes.
Definition 2.2. In GLOBAL ECC, in addition to H, C, and feeJee a global budger bglobal E Zzo is given as input. The goal to find node coloring a : V + 2 such that [o(v)] 2 1 for all e and Evev (o) $ [V] + bglobal. minimize the number of mistakes.
Definition 2.3. In ROBUST ECC, in addition H, C, and {CoJeER, node-removal budget brobust E Z20 is given as input. The goal is to remove at most brobust nodes from the hypergraph and find a node coloring a (V VR) C minimize the number of mistakes, where VR denotes the set of removed nodes.
Recall that removing a node from H makes the node disappear from all the incident edges.
In Section 3 our algorithms will be presented for slightly generalized versions the problems. We introduce edge weights we Q2o that minimize the total weight, not number, of mistakes. In LOCAL ECC, instead of bocal that uniformly applies to all nodes, we will let each node specify its own budget by. Note that suffices to solve these generalizations.
We conclude this section by introducing notation to be used throughout this paper. For C E, let X(F) == fce e E F} be the set of colors of the edges in F. For E V, let 8(v) be the set of edges that are incident with 0; d, = 10(v) is the degree of v. Let (c(v) be the set of edges in 8(v) whose color is i.e., (v) = {e d(v) c. = c].
3 Proposed algorithms
3.1 Local ECC
In this section, informally present our approximation algorithm for LOCAL ECC. Although we will discuss all the necessary technical details here, we will still present a formal analysis in Appendix A for the completeness' sake.
Following are an LP relaxation (left) and its dual (right). Intuitively, Fv, = indicates that node v is colored with and Z otherwise; Ue if is mistake and ye otherwise.
min EcEg Wele
max EeEE,VEe Be,0 -vev b.a.
s.t. Eceo Tu,e 5 bbr
Vo EeE EV, Ve E, e,, Ve V, C, Ve E.
s.t. Eees.(r) Be,v S Uu.
Wu E V,CEC,
Ju.c, He 2 1,
Evco Be,u I Wer
We E,
Fn. 0,
0r 2 0, 3ar 2 20
Yu E EV, Ve E E, U Ee.
ye 2 0,
As primal-dual algorithm, our algorithm maintains dual solution (a,, ()), which changes throughout the execution of the algorithm but remains feasible at all times. The algorithm constructs the "primal"

---

solution partially guided by the complementary slackness: namely, it allows an edge e to be mistake only if the corresponding dual constraint Evee Sa,, I we is right, i.e. Evee Say we This useful since the cost of the algorithm's output can then be written as LeeF We EeEB... Evee Se,e S EeEg Luse Se,., where En is the set of mistakes in the output. Let By == EeER(1) Se.v. and the algorithm's 's output cost is no greater than Σvev By at termination.
In order to maintain dual feasibility, the algorithm begins with trivial dual feasible solution (). = (0, 0) and only increases dual variables, never decreasing them. The first set of constraints will never be violated because whenever we increase -ess,(o) Se,er will increase a, by the same amount. The second set of constraints will never be violated simply because will stop increasing all Be, for v E e once edge e becomes tight.
We are now ready to present the algorithm. To better convey the intuition, we will describe the algorithm as if it is a "continuous" process that continuously increases a set of variables as time progresses. In this process over time perspective (see, e.g., [31), primal-dual algorithm starts with an initial (usually all-zero) dual solution at time 0, and the algorithm specifies the increase rate at which each dual variable increases. The dual variables continue to increase at the specified rates until an event of interest-typicallyy a dual constraint becomes tight- occurs. At that point, the algorithm pauses the progression of time to handle the event and recompute the increase rates. Once updated, time procedds again. In Appendix (A.5) we also provide a discretized version of the algorithm, making all implementation details explicit.
Consider the following algorithm. maintains a set of all those edges that are not tight. We call these edges loose. One point that requires additional explanation in this pseudocode is that it increases a sum of variables Ee Se, at unit rate, rather than a single variable. This should be interpreted as increasing the variables in the summation in an arbitrary way, provided that their total increase rate is I and that no variable is ever decreased. The algorithm's is analysis holds for any such choice of the increase rates of individual variables as long as their total is
Algorithm Proposed algorithm for LOCAL ECC
a 0: 8 -
L + fe E w. > 0}
for v E do
while (((
by do increase a and Leed. Be, for each c x(5(w) at unit rate, until there exists e such that Enco Be,u- = We
if Euco Be,u = We then remove all such edges from L (u) f (L)
return
This algorithm can be implemented as a usual discrete algorithm using the standard technique for emulating "continuous" algorithms by discretizing them. Once the increase rates are determined, the discretized algorithm computes, for each edge, after how much time the edge would become tight if we continuously and indefinitely increased the dual variables, and selects the minimum among them. That is the amount time the emulated algorithm runs before getting paused. The discretized algorithm then handles the event, recomputes the increase rates, and repeat. See Appendix A.5
is easy to see that Algorithm I returns feasible solution: we assign (8(()) n L) to u only after ensuring (x) L) S by. The analysis can focus on bounding the final value of Σ B,: recall that it was an upper bound on the algorithm's 's output cost. We will compare Evev B, against the dual objective value, which a lower bound on the true optimum from the LP duality.
Both Evev B, and the dual objective value change throughout the algorithm's 's execution. At the beginning, both are zeroes because (a,, 3) (0, 0). How do they change over the execution? each iteration of the while loop, the algorithm increases a at unit rate and B, at rate Ix(8(e) where v is the vertex being considered at the moment. (Note that B, = EeEX((()nLL) Eee, Se, ExErONy B.....) That is, at any given moment of the algorithm's 's execution, the rate by which Σvev B. gets increased is (x((()) n L)l > by and the increase rate of the dual objective is
5

---

Ix(6()) n L) b.. Note that the ratio between these two rates is 1x( [x( S b, + since (x((()) b.. Since the upper bound on the algorithm's output and the lower bound on the true optimum were initially both zeroes and the ratio between their increase rate is no greater than
by 1 at all times, the overall approximation ratio dmax + 1 where bmax 0max blocal under the original definition of LOCAL ECC.
maX by. Note that
Theorem 3.1. Algorithm is a (blocal + ) approximation algorithm for LOCAL ECC.
Algorithm H can be implemented to run in linear time (see Lemma A.3 in Appendix A.I).
Our algorithm harnesses the full "power" of the I.P relaxation, in that its approximation ratio matches the integrality gap of the relaxation. We defer the proof of Theorem 3.2 Appendix
Theorem 3.2. There sequence of instances of LOCAL ECC such that the ratio between fractional solution and an optimal integral solution converges to blocal + 1.
In fact, our inapproximability results further show that our approximation ratio essentially the best possible. We note that these results answer one of the open questions raised by Crane al. [19]. namely, whether an O aappooxxoinitaoo algorithm is possible for LOCAL ECC.
Theorem 3.3. For any constant e > 0, it is UGC-hard to approximate LOCAL ECC within a factor of blocal +
If one prefers milder complexity-theorete assumption, we show the following theorem well. Theorem 3.4. For any blocal 2 2 and any constant >> 0, there does not exist (brcca e)-
approximation algorithm for LOCAL ECC unless NP.
The proofs of Theorems and 3.4 are deferred to Appendix A.3
Final remarks. Since our algorithm considers the nodes one by one and operates locally, Algorithm| ! online algorithm, in which vertices revealed to the algorithm in an online manner[] In Appendix A.4 we also show that the algorithm can be analyzed in the bicriteria setting, yielding a (1 [1+6) e, bigcal "سum""" Puw >-approximation for e (0, blocal]. Finally, we note that Algorithm| doess not specify the order in which the for loop processes the vertices, which may leave room for optimization in practice. However, our empirical evaluation indicated that such room was rather limited.
immediately works
3.2 Robust ECC and Global ECC
In this section, we summarize our algorithmic results ROBUST ECC and GLOBAL ECC. Both problems involve global constraints, and result, their LP formulations (and the proposed algo- rithms) become quite similar. As such, in the interest of space, we will sketch our algorithm only for ROBUST ECC in this section. The only real difference between the two algorithms is in the constraints the dual LPs.
Following are an LP relaxation (left) and its dual (right) used by the algorithm for ROBUST ECC, where 2, 1 indicates that the node is removed from the hypergraph.
min E.EF Welle
max EeEF,VER Be,u - -VEE ag -Xbrobust
s.l. 2u + Ener Tv.o S 1,
Ve E Ve E,ee,
s.t. Encr((o) BB,v S avs
V C,
2v + Tn,cs + ye 2 1,
Ever S Wes
Ve E E,
ΣvEV < brobust:
Eecō(v) Be,0 av S X,
Vo V Ve E
Fn,e 2 0,
V.EV C,
Br 2
ye 2 0,
Ve E E,
X 0.
2v
Vo E V.
*There are several ways to describe online setting, but simple (albeit slightly weak) formulation is as follows: initially, the algorithm is given only the number of hyperedges. Then, at each timestep. when a new vertex arrives, the algorithu is informed of which hyperedges are incident to v. At that point of time, the algorithm required to irrevocably color

---

We note that the only difference between our LP and Crane et al.'s [19] lies in the constraint 2, Eeec Tv.c I 1. (The two LPs use opposite senses for the binary variable z; but this not an inherent difference.) This difference, which does not change the value of optimal integral solutions, turns out to enough to reduce the integrality gap of our relaxation. See Theorem 3.5
Let us now sketch the algorithm for ROBUST ECC we propose. The algorithm maintains a dual feasible solution (a, 3, A), initially as (0, 0, 0). The set will be kept as the of loose edges; R S V is the set of nodes with at least two incident loose edges of distinct colors. Intuitively, R is the set of nodes we will remove from the hypergraph. The algorithm therefore continues its execution until R| I brobust holds. When increasing the dual variables, the algorithm increases variables associated with all vertices R at the same time, unlike Algorithm I which handles one node at a time. The following two properties will hold:
The algorithm increases À and Ene8(w)ns Be,. -a a₂ for each R at the same rate.
(ii) For each E R, the algorithm increases ay and (eE Se,u for each c E x(6(u) n L) at the same rate. In general, the increase rate of Ow, may be different from that of Ovz for 01 * 02.
These properties can be ensured as follows: the increase rate of À is set as 1. For each E R, we increase Oe and Eeed,(e)nz (e, for each c E x(6(u) L) at rate (x((())(Z)-1
Once [ becomes less than or equal to brobust. the algorithm removes R from the hypergraph and assigns every node E V \ R the (only) color in x(((v) n L). If x(((e) n L) 0, an arbitrary color can be assigned without affecting the theoretical guarantee on solution quality: in practical implementation, we could employ heuristics for marginal improvement. In the interest of space, the full pseudocodes are deferred to Appendices B.1 I and B.4
We prove the following theorems in Appendices B.2 and
Theorem 3.5. Algorithm a 2(brobust + 1) approxxmmaiin algorithm for ROBUST ECC.
Theorem 3.6. Algorithm 5 is a 2(bglobal + 1) aaprroximation algorithm for GLOBAL ECC.
Both algorithms can be implemented to run in O(EE EvEv de) time (see Lemma
The LP relaxation of Crane et al. [9] for ROBUST ECC has infinite integrality gap, whereas the
integrality gap of our LP is Obbrobust). following from the proof of Theorem 3.5 This makes it possible to obtain a true (non-bicriteria) approximation algorithm based on our LP. In fact, the following theorems show that our LP for ROBUST ECC (and GLOBAL ECC) has integrality gap of (brobusst) (and ((bgtobal)), respectively. The proof of Theorem 3.8 is deferred to Appendix C.4
Theorem 3.7. The integrality gap of our LP for ROBUST ECC is at least brobust + 1.
1. Proof. Consider hypergraph H = (V {ui.-. +1). E = e2)) where e1 = 62 = V.
We, -ee, 1. and Ce, # Ce.- Any integral solution incurs at least 1 since at least one node should remain in the hypergraph and at least one edge cannot be satisfied. However, consider the solution for all e E V and yes
given by 2, TT Tuyees Te,
2(b
Bez
2
This solution is feasible and the cost is brahure +I'
Theorem 3.8. The integrality gap of the for GLOBAL ECC is at least balobal +
Final remarks. Our algorithms can be analyzed in the bicriteria setting as well, yielding a bicriteria + 1,,
1 26 apprrooxiinno algorithm for E (0, 2b), where brabust for ROBUST ECC and b Oglobal for GLOBAL ECC. This improves the best bicriteria approximation ratios previously known; furthermore, it affirmatively answers one of the open questions Crane et al. [19] namely, whether there exists bicriteria (O(1), (()))-approximmatee algorithm for GLOBAL ECC. See Appendices B.3 and C.5
Experiments
In this section, we analyze the performance of the proposed family of algorithms through experiments.
We describe the setup in Section 4.1 We evaluate and discuss the performance of our algorithm for
LOCAL ECC in Section 4.2 In Section 4.3 we address ROBUST and GLOBAL ECC.
7

---

Table Statistics of the benchmark datasets.
Datasets
[
E
[C]
d
4
dx
p
Brain
638
21,180
2
66.4
2
1.92
0.91
MAG-10
80,198
51,889
10
25
2.3
9
1.26
0.18
Cooking
6,714
39,774
20
65
63.8
20
4.35
0.61
DAWN
2,109
87,104
10
22
162.7
10
3.72
0.74
Walmart
88,837
65,898
44
25
5.1
40
2.65
0.52
Trivago
207,974
247,362
55
85
3.6
32
1.55
0.23
4.1 Setup
Our experiments used the same benchmark as Crane et al. [9]] which contains six datasets. See Appendix D for further description of the individual datasets. We remark that these datasets have been used as a benchmark to experimentally evaluate ECC also in other prior work 4 48 Table summarizes some statistics of the datasets: the number of nodes [V], number of edges E number of colors [C], rank == mäX.eE |e), average degree d == Vvev de/[V), maximum color-degree Ax == max.ev Ix()())), average color-degree dx == Σ REV (x((e))) and the ratio of vertices whose color degree is at least 2, i.e., = (u E V (x((()) 2 2///IV/
All experiments were performed In our experiments, we used the original code Crane et al. 47 [9] as the implementation of the previous algorithms. Since their code was written in Julia,
machine with Intel Core 19-9900K CPU and 64GB of RAM.
implemented our algorithms also in Julia to ensure a fair comparison. When running the original codes for the LP-rounding algorithms, used Gurobi-122 12.0 as the LP solver. Gurobi the solver of choice in previous work [47 48 and it is widely recognized for its excellent speed 42).
Our experiments focus on two aspects of the algorithms' performance: solution quality and running time. To compare solution quality, we will use relative error estimate, normalized, estimated error of the algorithm's 's output cost (or quality) compared to the optimum. Since the problems are NP-hard is hard to compute the exact error compared to the optimum: as such, Crane et al. [19] used the optimal solution to their LP relaxation in lieu of the true optimum, giving overestimate of the error. followed this approach, but we used our LP relaxation instead since we can prove that our relaxation always yields better estimate of the true optimum. To normalize the estimated error, divide it by the estimated optimum: that is, the relative error estimate is defined as (A - L) L, where A denotes the algorithm's 's output cost and L is the LP optimum F
Crane et al.'s experiment 19 used Mocal E f1,2,3, 3,3,,445, 4, 16, 16,32) 32) for LOCAL ECC, brobust / E (0, 001, .5. 115,, 2, .5) for ROBUST ECC, and / E {0, 1.5, 2, 2.5, 3, 3.5, 4] for GLOBAL ECC. While these choices were carefully made to help avoid trivial instances, we decided to extend their choice for GLOBAL ECC. To explain what trivial instances are, suppose that blocal greater than the maximum color-degree Ay an instance of LOCAL ECC. The problem then becomes trivial since the local budget allows assigning each vertex all the colors of its incident edges. We call an instance of LOCAL ECC trivial if blocal 2 Ax: similarly, ROBUST ECC instances are trivial if Drobust 2 p V/. and GLOBALL ECC instances are trivial Igoobal 2 [V 1). For LOCAL nontrivial: each data set has 0, 1, or at most trivial instances, possibly with the exception of at most one dataset. However, for GLOBAL ECC, only 44 instances out of 78 in the original benchmark are nontrivial, so we decided to additionally test /global/ /V| | E {.1, 2, ...4, budgets in total for each dataset for GLOBAL ECC.
ECC and ROBUST ECC, Crane et al.'s choice of budgets ensure that most instances
.4.. As a result, we tested thirteen different
4.2 Local ECC
We measured the solution quality and running time of the proposed algorithm in comparison with the greedy combinatorial algorithm and the IP-rounding algorithm of Crane et al. [19
'When L = O, we define the relative error estimate as O. Note that L 00 implies A = 0 since our LP has bounded integrality gap.

---

Brain
K6G-10
Brain
MAG
0032
52100
3700
16
Frot
Pose
Deat
Accal
Cooking
Cooking
177
50
Walmart
Welmart
Irivago
Poos
Plesal
Proposed
Gready [19]
Ulvitunding [1M]
(a) Running times seconds, log scale)
(b) Relative estimates
Figure 1: (a) Running times (in seconds, log scale) and (b) relative error estimates of the LOCAL
ECC algorithms. Empty square markers denote trivial instances.
Figure aa) depicts the running times, and Table 2able22a (in Appendix Eb lists their average for each dataset. Figure shows that our proposed algorithm was the fastest in most instances. It not surprising that algorithm, with the overall average running time of 0.121sec, LP-rounding algorithm whose overall average running time was 146.470sec, since our algorithm is combinatorial. This gap no smaller even when consider only nontrivial instances: the overall average running times were 0. 142sec (proposed) and 180.367sec (LP-rounding). Remarkable was that the proposed algorithm more than twice as fast as the greedy algorithm running times became more outstanding in larger datasets: for Trivago, our proposed algorithm was 11 times faster than the greedy algorithm and 2, 100 times faster than the LP-rounding algorithm.
much faster than the
faster than the greedy algorithm, too. In fact, average, was most datasets except for Brain. Such gap in the
Figure (b) shows the relative error estimates of the algorithms' outputs. We note that, except for Brain and MAG-10. the relative eтrоr estimate of our algorithm (and the greedy algorithm) tends to increase as blocal increases, and then some point starts decreasing. This appears to be the result of the fact that the problem becomes more complex as bloaa initially increases, but when bocal becomes too large, the problem becomes easy again. It can be seen from Figure [bb) that our proposed algorithm outperformed the greedy algorithm in all cases. The overall average relative error estimate of our proposed algorithm was 0. 0.141, which is less than half of the greedy algorithm's 's average of 0.297. The LP LP-rounding algorithm output near-optimal solutions in every case.
Overall, these experimental results demonstrate that the proposed family of algorithms is scalable, and produces solutions of good quality. As was noted by Veldt 448 and observed in this section, LP- LP-rounding approach does not scale well due to its time consumption, even though it produces near- optimal solutions when it is given sufficient amount of time. Compared to the greedy combinatorial algorithm, our proposed algorithm output better solutions in smaller amount of time in most cases. This suggests that the proposed algorithm can provide improvement upon the greedy algorithm.
4.3 Robust ECC and Global ECC
We present the experimental results of both problems together in this section, starting with ROBUST ECC. We measured the performance of our proposed algorithm in addition to the greedy combinato- rial algorithm and the I.Prounding algorithm of Crane al. 19 However, as their LP-rounding algorithm is bicriteria approximation algorithm that possibly violates the budget brobust we cannot directly compare their solution quality with the proposed algorithm. In fact, the I.Prrunding algo- rithm turned out output "superoptimal" solutions violating brobust in most cases of the experiment.

---

The bicriteria approximation ratio was chosen as (6,3), which is the same choice as in Crane et al.'s experiment 19
Comparing the average running times of each dataset reveals that the proposed algorithm ran much faster than the LP-rounding algorithm for most datasets, except for DAWN. The proposed algorithm was slower than the greedy algorithm for all datasets; however, it tended to produce solutions of much better quality than the greedy algorithm. The relative error estimate of the proposed algorithm was strictly better than that of the greedy algorithm in all nontrivial instances; the overall average relative error estimate of the proposed algorithm was 0.042, six times better than the greedy algorithm' average of 0.272. We also note that the relative enror estimate of our algorithm stayed relatively even regardless of the budget, while that of the greedy algorithm fluctuated as brobust changed in some datasets, such as MAG-10 and Trivago. Due to space constraints, detailed table and a figure presenting the experimental results have been deferred to Appendix F
For GL.BBAL. ECC, the bicriteria approximation ratio of the LP-rounding algorithm was chosen as (2bglobal + 5, 2). which again is the same choice as in Crane et al.'s experiment. For GLOBAL ECC, the bicriteria approximation algorithm did not violate the budget for any instances of the benchmark. This may be due the fact that their LP relaxation for GLOBAL ECC has bounded integrality gap, unlike their LP for ROBUST E
The experimental results for Global ECC exhibited similar trends to those for Robust ECC. The relative error estimate of the proposed algorithm was strictly better than that of the greedy algorithm in all nontrivial instances. The average relative error estimate nontrivial instances was 0.039 for the proposed a algorithm, while that of the greedy algorithm was 0.912-more than 23 times higher. We also note that the relative error estimate of the greedy algorithm rapidly increased as Oglobal increased. While the proposed algorithm was on average slower than the greedy algorithm for all datasets, it was much faster than the LP-rounding algorithm in all datasets except for DAWN. A detailed table and a figure presenting the experimental results have been again deferred to Appendix [ due to the space constraints.
The above results together indicate that our proposed algorithms for ROBUST ECC and GLOBAL ECC are likely to be preferable when high-quality solution is desired possibly at the expense of small increase in computation time.
5 Conclusion and discussion
In this paper, we presented new family of algorithms for overlapping and robust clustering of edge-colored hypergraphs. Experimental results demonstrated that our algorithm improves upon the previous combinatorial algorithm for LOCAL ECC in both computation time and solution quality; compared to LP-rounding, it achieves significantly faster computation, with a slight trade-off in solution quality. For ROBUST ECC and GLOBAL ECC, our approach delivers improved solution quality with a slight increase in computation time compared to the previous combinatorial algorithms, while strictly satisfying the budget constraint. On the theoretical side, our analyses show that we achieve true (bocal + 1)-, 2(brabust + 1)- 2(hgtobal + 1)-approximation for LOCAL, ROBUST, and GLOBAL ECC, respectively. We also provide inapproximability results for LoCAL ECC and integrality gap results for all three problems, suggesting that significant theoretical improvements are unlikely. These results lead to answers to two open questions posed in the literature 19)
There remain a few promising directions for future research. Although our combinatorial algorithm runs significantly faster than L.Prrunding algorithms, its running time is still superlinear for ROBUST ECC and GLOBAL ECC. Can we optimize the dual update steps of our algorithms to obtain a linear- timer-timeeao algorithm for these two problems? Also, while work focused giving better algorithm for ECC, it would be also interesting to explore additional applications of ECC, e.g., to the clustering tasks solved via correlation clustering. Given that k- PARTIAL VERTEX COVER admits 2- approximation algorithm 27], another interesting question is if we can obtain an O(1) approximmatoo algorithm for ROBUST ECC well.
As a side remark, when we reran the proposed algorithm with the budget tripled to enable a comparison with the I.P ..Prrundiig (6. 3)-approxinntion algorithm, the number of mistakes made by the proposed algorithm was, average, small as 57.2% of that made by the bicriteria algorithm.
Whhe we reran the proposed algorithm with the budget doubled, the number of mistakes made by the pro- posed algorithm was, on average, as small as 68.9% of that made by the bicriteria (20yoohal + 5, approximatiin algorithm.
10

---

Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful comments. Supported by NCN grant number 2020/39/B/ST6/0144) This work was partly supported by Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS- 1221-11220068 Artificial Intelligence Innovation Hub). This work was partly supported by an IITP grant funded by the Korean Government (MSIT) (No. RSS-200-II201360 Graduate School Program (Yonsei University)). This work was supported by the National Research Foundation of Korca(NRF) grant funded by the Korea MSS)) ASS-2025-00563770 Part of this research conducted while Y. Shin at Yonsei University.
Artificial Intelligence
References
[1] Alexander Ageev and Alexander Kononov. Improved approximations for the max k-colored clustering problem. In Proceedings of the International Workshop Approximation and Online Algorithms (WAOA), pages 1-10. Springer, 2014.
[2] Alexander Ageev and Alexander Kononov. A 2622-Approximation Algorithm for the Max- imum TEdg-Coolore Clustering Problem. In International Conference on Matherattiaa Optimization Theory and Operations Research (MOTOR), pages 3-15. Springer, 2020.
[3] Yousef M Alhamdan and Alexander Kononov. Approximability and inapproximability for maximum k-edge-colored clustering problem. In Computer Science-Theory and Applications: 14th International Computer Science Symposium Russia (CSR), pages 1-12. Springer, 2019.
[4] Ilya Amburg, Nate Veldt, and Austin Benson. Clustering in graphs and hypergraphs with categorical edge labels. In Proceedings of The Web Conference (WWW), pages 706-717, 2020.
[5] Ilya Amburg, Nate Veldt, and Austin R Benson. Diverse and experienced group discovery via hypergraph clustering. In Proceedings of the 2022 SIAM International Conference on Data Mining (SDM), pages 145-153. SIAM, 2022.
[6] Yael Anava, Noa Wwigdor-Elgrabee and Iftah Gamzu. Improved theoretical and practical guarantees for chromatic correlation clustering. In Proceedings of the 24th International Conference on World Wide Web (WWW), pages 55-65, 2015.
[7] Carlos E Andrade, Mauricio GC Resende, Howard Karloff, and Flávio K Miyazawa, Evolu- tionary algorithms for overlapping correlation clustering. In Proceedings of the 2014 Annual Conference Genetic and Evolutionary Computation (GECCO), pages 405-412, 2014.
[8] Eric Angel, Evripidis Bampis, Kononov, Dimitris Paparas, Emmanouil Pountourakis, and Vassilis Zissimopoulos. Clustering on k-edge-colored graphs. Discrete Applied Mathematics, 211:15-22, 2016.
[9] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine Learning, 56:89-113, 2004.
[10] Nikhil Bansal and Subhash Khot. Inapproximability of hypergraph vertex cover and appli- cations to scheduling problems. In International Colloquium on Automala, Languages, and Programming (ICALP), pages 250-261. 250-ier..pringeer 2010.
[11] Thorsten Beier, Thorben Kroeger, Jorg H Kappes, Ullrich Kothe, and Fred A Hamprecht. Cut, glue & cut: A fast, approximate solver for multicut partitioning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 73-80, 2014.
[12] Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 353(6295):163-166 2016.
[13] Manuel Blum, Robert W Floyd, Vaughan Pratt, Ronald I. Rivest, and Robert E Tarjan. Linear time bounds for median computations. In Proceedings of the 4th Annual ACM Symposium on Theory of Computing (STOC), pages 119-124 1972.

---

[14] Francesco Bonchi, David Aarcia-Soriano, and Francesco Gullo. Correlation Clustering. Morgan Claypool Publishers, 2022.
[15] Francesco Bonchi, Aristides Gionis, Francesco Gullo, Charalampos E Tsourakakis, and Antti Ukkonen. Chromatic correlation clustering, ACM Transactions on Knowledge Discovery from Data (TKDD), 14):1-24, 2015.
[16] Francesco Bonchi, Aristides Gionis, and Antti Ukkonen. Overlapping correlation clustering. In 2011 IEEE/ 11th International Conference Data Mining (ICDM), pages 51-60, 2011.
[17] Guilherme Oliveira Chagas, Luiz Antonio Nogueira Lorena, and Rafael Duarte Coelho dos Santos. A hybrid heuristic for the overlapping cluster editing problem. Applied Soft Computing, 81:105482, 2019.
[18) Philip S Chodrow, Nate Veldt, and Austin R Benson. Hypergraph clustering: from blockmodels to modularity, Science Advances, 2021.
[19] Alex Crane, Brian Lavallee, Blair D Sullivan, and Nate Veldt. Overlapping and robust edge- colored clustering in hypergraphs. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining (WSDM), pages 143-151, 2024.
[20] Alex Crane, Thomas Stanley, Blair D. Sullivan, and Nate Veldt. Edge-colored clustering in hypergraphs: Beyond minimizing unsatisfied edges. Forty-second International Conference on Machine Learning (ICML), 2025.
[21] Nicolas A Crossley, Andrea Mechelli, Petra E Vértes, Toby T Winton-Brown Ameera X Patel, Cedric E Ginestet, Philip McGuire, and Edward T Bullmore. Cognitive relevance of the community structure of the human brain functional coactivation network. Proceedings of the National Academy of Sciences, 110(88): 1eee:11513-111111 11588, 2013.
[22] Devvrit, Ravishankar Krishnaswamy, and Nived Rajaraman. Robust Correlation Clustering. In Approximation, Randomization, and Combinatorial Optimization. Algorithmss and Techniques (APPROX/RANDOM 2019), volume 145, pages 33:1-33:18 2019.
[23] Irit Dinur, Venkatesan Guruswami, Subhash Khot, and Oded Regev. A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM Journal on Computing, 346$):1129-1146. 2005.
[24] Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. A density- algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD), page 226-231, 1996.
[25] Absalom Ezugwu, Abiodun M Ikotun, Olaide O Oyelade, Laith Abualigah, Jeffery O Agushaka, Christopher I Eke, and Andronicus A Akinyelu. A comprehensive survey of clustering algorithms: Statc-of-the-art machine learning applications, taxonomy, challenges, and future research prospects. Engineering Applications of Artificial Intelligence, 110:104743, 2022.
[26] Takuro Fukunaga. Lp-based pivoting algorithm for higher-order correlation clustering. Journal of Combinatorial Optimization, 17:1312-1326, 1326, 2019.
[27] Rajiv Gandhi, Samir Khuller, and Aravind Srinivasan. Approximation algorithms for partial covering problems. Journal of Algorithms, 53(1):55-84, 2004.
[28] David F Gleich, Nate Veldt, and Anthony Wirth. Correlation clustering generalized. In 29th International Symposium on Algorithms and Computation (ISAAC), 2018.
[29] Michel X Goemans and David P Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing. 24(2):296-317 1995.
[30] Michel X. Goemans and David P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In Dorit Hochbaum, editor, Approximation Algorithms for Na-hard Problems. 1996.
12

---

[31] Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, and Mauro Sozio. A primal- bicriteria distributed algorithm for capacitated vertex cover. SIAM Journal on Computing. 38(3):825 840, 2008
[32] Sai Ji, Gaidi Li, Dongmei Zhang, and Xianzhao Zhang. Approximation algorithms for the ca- pacitated correlation clustering problem with penalties. Journal of Combinatorial Oplimization, 45(1), January 2023.
[33] iprenci, Walmart Competition Admin, and Will Cukierski.
Walmart Re-
cruiting: Trip Type Classification. attps://kages com/ cotpetition/i
walmart - recruiting trip-typi--tt-eee wwtps-cccsssssiiiiiioooo 2013.
[34]
Wendy Kan. What's Cooking?
2015. Kaggle.
[35] Alboukadel Kassambara. Practical guide to cluster analysis in R: Unsupervised machine learning, volume 1. Sthda, 2017.
[36] Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, and Chang Yoo. Higher-order correla- tion clustering for image segmentation. Advances in Neural Information Processing Systems (NTPS), 24, 2011.
[37] Nicolas Klodt, Lars Seifert, Arthur Zahn, Katrin Casel, Davis Issac, and Tobias Friedrich. A color-blind 3-approximation for chromatic correlation clustering and improved heuristics. In Proceedings of the 27th ACM SICKDD Conference on Knowledge Discovery & Data Mining (KDD), pages 882-891, 2021.
[38] Peter Knees, Yashar Deldjoo, Farshad Bakhshandegan Moghaddam, Jens Adamezak, Gerard- Paul Leyson, and Philipp Monreal. Recsys challenge 2019: Session-basse hotel recommenda- tions. In Proceedings of the 13th ACM Conference on Recommender Systems, pages 570-571, 2019.
[39] Pan Li, Hoang Dau, Gregory Puleo, and Olgica Milenkovic. Motif clustering and overlapping clustering for social network analysis. In Proceedings of the IEEE Conference Computer Communications (INFOCOM), pages 1-9. IEEE, 2017.
[40] Pan Li and Olgica Milenkovic. Inhomogeneous hypergraph clustering with applications. Ad- vances in neural information processing systems (NeurIPS). 30, 2017.
[41] Hans D. Mittelmann. Latest benchmark results. In INFORMS Annual Conference, Phoenix, AZ, USA, 2018.
[42] Hans Mittelmann. Latest progress in optimization software. INFORMS Annual Meeting, Phoenix, AZ, USA, 2023.
[43] Divya Pandove, Shivani Goel, and Rinkle Rani. Correlation clustering methodologies and their fundamental results. Expert Systems, 15222, 1229,, 2018
[44] Mikail Rubinov and Olaf Sporns. Complex network measures of brain connectivity: uses and interpretations. Neuroimage, 5259)1009- 2010.
[45] Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Hsu, and Kuansan Wang. An overview of Microsoft Academic Service (MAS) and Applications. In Proceedings of the 24th International Conference on World Wide Web (WWW) Companion, pages 243-246, 2015.
[46] Substance Abuse and Mental Health Services Administration. ing Network (DAWN). Samn-drug-abuse warning- 2011.
Drug Abuse Warn
https://wwit
[47] TheoryInPractice. Github repository for "Overlapping and Robust Edge-Colored Clus- tering Hypergraphs" (Crane et al. [19). https://githhb. com//heeoryInPractice//
overlapping-ech 2024.
13

---

[48] Nate Veldt. Optimal LP rounding and linear-time approximation algorithms for clustering edge-colored hypergraphs. International Conference on Machine Learning (ICML), pages 34924-34951. PMLR, 2023.
[49] Nate Veldt, David F Gleich, and Anthony Wirth. A correlation clustering framework for community detection. In Proceedings of the 2018 World Wide Web Conference (WWW), pages 439-448, 2018.
[50] Dewan F Wahid and Elkafi Hassini. A literature review correlation clustering: cross- disciplinary taxonomy with bibliometric analysis. In Operations Research Forum, volume 3, page 47. Springer, 2022.
[51] Qing Xiu, Kai Han, Jing Tang, Shuang Cui, and He Huang. Chromatic correlation clustering, revisited. Advances Neural Information Processing Systems (NeurIPS), 35:26147-261555 2022.
[52] Julian Yarkony, Alexander Ihler, and Charless C Fowlkes. Fast planar correlation clustering for image segmentation. In Computer Vision: 12th European Conference Computer Vision (ECCV), pages 568-581. Springer, 2012.
A Technical details and proofs for Local ECC deferred from Section 3.1
A.1 Formal proof of Theorem 3.1
Lemma A.1. Algorithm 1 satisfies the following:
(a) At any moment, (a, B) is feasible to the dual LP.
(b) At any moment, for all E V, ar S 1
but1 Emeg(r) Se,e-
(c) At termination, every mistake e under a is tight, i.e., not loose.
Proof. Properties aa and (b) were shown in Section 3.1 let us show Property ( Let be an arbitrary loose edge, and suppose towards contradiction that c. é (v) for some e c. Observe that, once an edge becomes tight, the algorithm never makes it loose again. Therefore, was loose at the end of the iteration for of the for loop. Then 5(v) L contained e and therefore e, E x(((v) n L). leading to contradiction.
Let ALG be the total weight of mistakes in the output of Algorithm I and OPT be the weight of an optimal solution.
Lemma A.2. We have ALG < (bmax + +1) OPT.
Proof. By Properties and (b) of Lemma A.I
we have
OPT ΣΣ
Ber Σ bea Σ
Σ
Be,v boar)
Σ
Σ ecσ(u)
Be,u)
by +
E NEc
VEV
NEV
eEσ(v)
AEV
where the first inequality is due to the (weak) LP duality, On the other hand, we have
ALG <
Σ we
Σ
Σ Be. S
ΣΣ Be.
Σ Σ Be.
L
LEEAL
UEE
F. UEE
DEV cE8(n)
where the first inequality is due to Property
The two inequalities together completes the proof.
Now need to show that the algorithm runs in polynomial time. In fact, the algorithm can be implemented to run in linear time. Recall that the size of H is Evev dy.
Lemma A.3. Algorithm 7 can be implemented to run in O de) time.
14

---

Proof. For each edge, let us maintain the "level" le := Euse Pe. Consider an iteration for node v E V. By enumerating d(v), we can compute, for every color e E x()(v)), the "slack" x()(e)) that has the (b, 1)-st largest
slack(c) = Eeed,(o) (we ke). Let et be the color slack. Let 8* == slack(c*). Note that we can identify c* in O(d,) time using the algorithm of increase LeEde(u) Se, by (in(slack(c)) (c), sh} while maintaining the dual feasibility, i.e., for each edge e E. Euge Se,v wa must be satisfied the end. We then update (fe)eeb.(v) accordingly. Note that single iteration can be implemented to rum in Odd,), completing the proof.
Blum et al. 13 Once we found c², for every color e E x(6(e)),
Theorem 3.1. Algorithm 7 is (blocal + -pppprooximation algorithm for LOCAL ECC.
Proof. Immediate from Lemmas A.2 and A.3
A.2 Proof of Theorem 3.2
Theorem 3.2. There sequence of instances of LOCAL ECC such that the ratio between fractional solution and an optimal integral solution converges to blocal + 1.
Proof. Consider hypergraph H (V, E) where |E] is sufficiently large and [V bbgeat++1 .) All edge weights 1. In the hypergraph, each node is uniquely labeled by subset S of E such that |S|= = bocal + 1. Let dy denote the node whose label is S. For each iy E V. the set of edges that are incident to US is S. The colors of edges are distinet, ie.,, Ce Ce for all + e' E.
[
claim that, any integral solution, the number of satisfied edges (i.e., edges that are not mistakes) does not exceed blocal- Suppose toward contradiction that there is color assignment where at least Blocal + edges are satisfied. Let S any subset of the satisfied edges of size exactly bocal + 1. Since the colors all distinct, node Us must be colored with (at least) blccal colors, contradicting the budget constraint. Therefore, the total number of mistakes any integral solution is at least [E| blocal-
Now consider the following fractional solution. Let Zes.e, has value bocat if e E S, otherwise 0. bbca++11
Let ye
hocrt1 for all E E. Observe that the constructed solution is feasible to the LP and its cost The integrality gap is at least
[E]
blcar+1
E
Dlocal
(EE)
blocal)
(Bhocal (bhocal + 1) blocal blocal (blocal + 1)
[Ej
E
E
bI
which converges to blocal + 1 as |E| tends to infinity.
A.3 Proof of Theorems 3.3 and 3.4
Theorem 3.3. For any constant > 0, it is UGC-hard to approximate LOCAL ECC within a factor bical +
Theorem 3.4. For any brccal 2 and any constant c >> 0, there does not exist a (brcca c)- approximation algorithm for LOCAL ECC unless P = NP.
We say a hypergraph H = (V, is k-uniform if, for all e E E, |e| = k. Given a k-uniform hypergraph // (V, E), Ek- WEE--VEREEE-OEEEE called a veriex cover, such that every hyperedge E E intersects S, i.e., e S & 0 for each e E E. Bansal and Khot [10 showed the following theorem.
asks to find minimum-size subset S V of vertices,
Theorem A.4 (Bansal and Khot [10). For any k > 2 and any constant > there does not exists (k- - -)apprxximmtiion algorithm for Ek- S--VERTEX-COVER assuming the Unique Game Conjecture.
Dinur, Guruswami, Khot, and Regev 23 showed the following theorem.
Theorem A.5 (Dinur al. (23). For any k 2 3 and any constant > 0, there does not exists (k- 1 apapproximation algorithm for Ek-
unless P NP.
15

---

reduction from Ek- VERTEX-COVER to Due to Theorems A.4 and A.5 it suffices to present an approximation perpoxiimatto--peeeviinnng reduction from Ek-VERTEE VERTEX-COVER to LOCAL ECC with bocall
k 1.
Given a k-uniform hypergraph И = (W, as an input to Ek- VERTEX- let H' EV, be hypergraph defined as follows:
Proof of Theorems
3.3 and 3.4
. = {uy I E F) and
== few w E W) where 6w := {oy If w).
Let := (Cm I w E W be a set of [W] number of distinct colors. Let us then consider the input to LOCAL ECC where H' is given as the hypergraph, the color of ew Cw for every ew E, and the budget blocal is set to
For any vertex cover S [ W in H. let dg be the node coloring defined as follows: for every Vy V, as(wy) = fCar w E f S}. Note that, for every w E W S, ev satisfied by as- Moreover, since [|| - & and f * 0, we can see that (15(())] I k feasible node coloring whose number of mistakes minimum size of a vertex cover in the original input is at least the minimum number of mistakes in the reduced input.
blocal- This shows as is indeed most (S]. We can therefore deduce that the
For the other direction, let us now consider feasible node coloring a. Observe that, for any Vy E V, least one edge in 8(2y) must be mistake since 18(vy)] | = blocal + 1 and the colors of E are distinct. This implies that, for every f E F. there exists a vertex E W such that ew E E a mistake due reduced input, we can construct in polynomial time feasible vertex cover in the original input whose size the same as the number of mistakes due a. Together with the above argument that the minimum number of mistakes in the reduced input is at most the minimum size of vertex cover in the original input, this implies an approximation-preseeee LOCAL ECC.
the reduced input. This shows that, given a feasible node coloring o the
A.4 Bicriteria algorithm for Local ECC
Theorem A.6. For any 6 E (0, booall), there exists a (1 + 6, 1 + algorithm for LOCAL ECC.
bbcal
-aprrxximation
Tiocal
bosal
Proof. Letr [ blsel 1. Consider the algorithm where the condition of while loop of Algorithm 1 replaced by (x() n L.) > hocal + r. Let a be the assignment output by the modified algorithm. Observe first that the number of colors assigned each is most biccal +
brocal Observe that Properties (a) and (c) of Lemma A. still hold. Moreover, instead of Property (b). it is easy show stronger property that, at any moment, for all v V.
Oocal hocal
Q
Σ Be,v-
(1)
blocal EEδ(e)
We therefore have
ALG &
Σ
Σ
Be.u
bloca + T +
Σ
Be,v biocalayy
++1
V cEδ(v)
VEV
(EE(()
Iooca
Σ NEV
1+
Σ
Bar - blcalla,
T ++1/
(EE((v)
s (1++c)
Σ
Bo.u - brocal
I =
DEV
(EE(U)
where the first inequality follows from Property (c). the second from Equation ① and the last from Property (a).
Note that 1 +
1 bucal
< 1 1.
Gocal
16

---

A.5 Discretized version of Algorithm
Algorithm is discretized version of Algorithm) Note that the proof Lemma A.3 is based on this discretized version.
Algorithm 2 Discretized primal-dual algorithm for LOCAL ECC
le < for all E E L + {e E E
We > 0}
for v V do
if (x(((e) n L) b then
slack(c) & for all E x(6(e) L) for e E 8(v) n do
slack(c.) + slack(ce) + (we - ka)
s* be the (b, + 1)-st largest value in the (multi)set (slack(c)) for CE (()(t) L)ddo do
le 1.+++ min (slacc((c))
(we- (w,
te) for all E 5.(v) n L
scack(c)
slack(c) s then Le L 5,(v) return
(0) - x()())
B Technical details and proofs for Robust ECC deferred from Section 3.2
B.1 Proposed algorithm for Robust ECC
In Section 3.2
we sketched our algorithm for ROBUST ECC. We present its pseudocode below.
Algorithm 3 Proposed algorithm for ROBUST ECC
a - 0: 3 + 0; A + L - fe E W. > 0} R + euEV V Ix(o(v)
2 2}
while R| > brobust do increase À and a and Be,v for E R and e E 5(v) n L in a way that the increase rate of À and that of EcES(y)nL Be,v a₂ for each R are uniform and, for each R, the increase rate of an and that of LeEô,(o) Be, for each e E x()(v) n L) are uniform, until there exists such that Enee Br,u = W/
if Be Enee Be,u we then remove all such edges from
3v (x((()) L)] < then remove all such nodes from R remove R from the hypergraph
for $ do
if (x() LL) then (u)) - e where e (()
else
(v) f e where c an arbitrary color
return o
B.2 Proof of Theorem 3.5
We have the following key lemma. Let us prove only Property (a), since Properties (b) and (c) can be seen from the same argument the one for Lemma A.I
Algoritumssatisiice Lemma B.l. Algorithm satisfies the following:
(a) At any moment, (a, 3, X) is feasible to the dual LP.
17

---

(b) At any moment, for all E V, a, S 2 Eesō(o) Pe.e.
(c) At termination, every mistake e under a is light.
Proof of Property (a). Recall the two properties of the algorithm. Observe that the first of dual constraints remain feasible due to Property (it: the second set of constraints are satisfied since the algorithm stops increasing dual variables soon as discovers a tight edge; the third of dual constraints are kept feasible due to Property
Let ALG be the total weight of mistakes in the output of Algorithm 3 and OPT be the weight of an optimal solution.
Lemma B.2. We have ALG (2brobust + 2)- OPT.
Proof. Observe that, if [R] < brobust from the very beginning of the algorithm, the algorithm immediately terminates and incurs no weight. Let us thus assume that |R] brabust at the beginning.
Consider the timepoint when the algorithm terminates. Let Ro denote the value of R at termination. Let R' == {v E V Eegs(w) Se,, 0₂ >}. We claim that Ro & R' and R brobust- (Proof. Right before the algorithm terminates, it removes some nodes from R. Consider the moment right before this removal. At this moment, every node in R satisfies Ee Pe.e - a0 = À and therefore is in R.. Note that I contains more than brobust vertices at this moment, since otherwise the algorithm would have terminated earlier. Note that Ro is the set resulting from the removal.) Let R" be any set such that Ro R" Ç R' with RR|| brobust, and let denote arbitrary node in R' R". We can then bound OPT from below as follows:
OPT 2 ΣΣ
Be, Σas av
Abrobust ΣΣ
Be,
Σ "EV
ag cEδ(v)
Σ "ER"
Σ
Be, av
AER
NEV
RE
Σ
Be,u - Ot))
RE (Eδ(1)
2
Σ
Beyu:
(3)
2
VEV cεō(v)
where the first inequality is due to Property and the second inequality due to Property (b) Moreover, since E Rt' R² and R"" brobust, find another lower bound OPT from
OPT
Σ
Σ cEA(w)
Be,v av)
Be,w Ow
Σ R
Be ag eE
Σ
brobust
VEV
nEo(wc)
Σ
Be
(4)
2brobust
DE 12" egā(v)
where the equality follows from the fact that w R' and the last inequality is again due to Property (b). Therefore, by Property (c). we have
ALG Σ Σ
Pe,
Σ
Be +
Σ
Be, S (20robust + OPT, (5)
vEV cEδ(e)
VE R" cEδ(v)
"EV\R" cEā(u)
where the last inequality follows from 5 and from without
Note that, if Drobust 0. immediately follows
Lemma C.3 in Appendix time.
C.3 shows that Algorithm 3 can be implemented to run in O( Evey dw)
Theorem 3.5. Algorithm a 2(brobust -)pppproximttion algorithm for ROBUST ECC.
Proof. Immediate from Lemmas B.2 and C.3
18

---

B.3 Bicriteria algorithm for Robust ECC
Theorem B.3. Suppose that 2 1. For any E (0, 2/robust), there exists a (2+e, 1 1+
20
Drobust
approximation algorithm for ROBUST ECC.
brehurt
Proof. Let T Algorithm is replaced by [ Brabust
2hrebuz
Consider the algorithm where the condition of the while loop in
+ T. It is clear that the number of removals most
Drobust + T brobust (1 + Boghove
2hatum
Note also that the modified algorithm satisfies all brouue
the properties of Lemma B.1
basically follow the proof of Lemma B.2 Let Rg the set nodes that are removed from hypergraph H. Observe that |Rol I Grobust + from the construction. Let be the color assignment of V Rg output by the algorithm and let Em be the set of mistakes under o. We have
Σ
W Σ Σ
Be
Σ
Σ
Be,
aie
(6)
VEV cEδ(w)
.EV
(E
where the first incquality follows from Property
(c) and the second from Property (6). Let R' := fo e R'
V Desō(e) Be,u 0gy A}. Observe that Ro R' and |R||
brobust Let R" be subset of
R' such that R" with |R brobust + We then have
OPT 2 ΣΣ>
3r. Σ VEV
Og Xlrobust
eEE DER
Σ
Σ (CE(())
Be, av
brobust
Σ
Σ (c
B0,v
brobust
+
VEV
Ve RM
Σ
Σ
Be, avv
+
T
Σ
Σ
Be,v
(8)
brobust +
vEV
(EE(())
(E((v)
Let w denote any node in R'
R"
We give lower bound on the first term of (8) as follows:
Σ
Be au
Se,w aw
Σ DE 12!
Σ (EE(v)
Be,v ar
(9)
brobust
+
R*
(E
<Ed(w)
Therefore by plugging 99) into
we have
OPT
++1
Σ
Σ
Be.v Ohy
(10)
brobust
+ T
De (eEŌ(1)
We then have
Σ
Σ
Be,v ane
VEV
(EE((e)
brobust
Begv Cr
Ber atv
brobust + T
VEV
cEō(v)
cEO(v)
brobust
Σ (eE((e)
Be,
an
brobust + T
VER"
< <1++
(robustt brobust
OPT (1+ OPT,
T
where the first inequality follows from and 10 Combining this inequality with (6) proves the theorem.
Recall that Crane al. 119 gave an I.P-runding bicriteria (2+ + e, + --aaprooximation algorithm for ROBUST ECC for > O. Note that this algorithm provides an better performance guarantee.
19

---

B.4 Discretized version of Algorithm
Algorithm is discretized version of Algorithm Note that the proof Lemma C.3 is based on this
discretized version.
Algorithm 4 Discretized primal dual algorithm for ROBUST ECC
4e + 0 for all e E E L {e E E We >
R + {u E V (x(ó(v))L) 2 2}
while R| > brobust do
rate(e) <- 0 for all e E L
for R do
for x(ó(v) do
rate(e) + rate(e) I((()))) [att)]z for all E do(v)
(eghhen((e) wa-f for all rate(e)
t t mingeL (e) for do Le + le + t* raae(e)
if le We then L
remove all e from R such that Ix(5(u) n) s remove R from the hypergraph for & do if (x())) n L.] then
(v) - c where c (()
else
(v) + c where c an arbitrary color
return
C Technical details and proofs for Global ECC deferred from Section 3.2
C.1 Primal and dual LP
Following is the LP relaxation, where 2. E Zzo indicates the number of additional colors budget assigned to v, i.e., 2e number of colors is assigned to u.
min EeSE Webe
s.t. Eceo Jnze S zu + 1,
VeEV,
Tv.c, Be 1,
Ve E,ve,,
Σ 20 < bglobal,
Fv.c 20. 0,
Vu V.EV,
Ue 2 0,
Ve E E, V V.
2 0,
Following the dual of this LP.
max EeeE,be Be, Evev ar Abglobal
Enehdto Bar S Ovr
E V, C, Ve E,
Even Bagv S Wes av S,
Vu E
ar 2 0,
Ve EV
Bar 0,
Ve E E, v e,
A 2 0.
20

---

C.2 Proposed algorithm for Global ECC
Let us now present our algorithm. Similarly, we consider the problem where each edge has an associated weight We.
The algorithm shares many similarity with the algorithm for ROBUST ECC. It maintains a dual feasible solution (a, B. A), starting from (0, O, 0), the set of loose edges, and the set R of nodes with at least two incident loose edges of distinct colors. It also simultaneously increases À and (a,, (9) associated with the nodes in R. Intuitively, is the set of nodes that we will assign (possibly) more than one color.
As the dual formulation differs, the way the algorithm increases the dual solution slightly varies, The following properties will hold:
À and Og for each E R increas the same rate.
(ii) For all v E R, Or and (ved Be,o for each e E x(6(u) O L.) increase at the same rate.
Observe that these properties can be easily ensured.
The algorithm increases the dual solution until E n - 1) becomes at most gglobal and once the algorithm reaches this point, it assigns every node v E V the color in x(6(v) L). clear that the returned node coloring is feasible. As before, if x(6(v) n L) 0, an arbitrary color can be assigned without affecting the theoretical guarantee; in practical implementation, we could employ heuristies for marginal improvement. See Algorithm 5 for a detailed pseudocode. The full
discretized version of the algorithm is presented in Appendix C.6
Algorithm 5 Proposed algorithm for GLOBAL ECC
X - 0 - 0: 3 + 0
L {e {ee E we > 0}
2} while EvER(1x((()) LL) 1) > bglobal do
R EVEV (x((())
increase and an and Be, for and that of a for each v E R are uniform and, for each E R, the increase rate of o2 and that of Eeerd Be for each x(6(e) L) are uniform, until there exists such that Ence Be,u = We
R and 5(v) n L in way that the increase rate of
if Eneo Baru w. then remove all such edges from if Ee Ix((()) L)) < 1 then remove all such nodes from R
for v E V do
if (x) LL] then
(v) - x(6(v)
else
(v) t {c} where c is an arbitrary color
return o
C.3 Proof of Theorem
3.6
We have the following key lemma. Let prove only Property since Properties b through ( can be seen from the same argument as the one for Lemma A.
Lemma C.I. Algorithm 5 satisfies the following:
(a) At any moment, (a, 3, is feasible to the dual L.P.
(b) At any moment, for all E V, av < Encō(n) S0
(c) At any moment, for all v E R, a I (x(8())1)) Eees(e) Bex-
(d) At termination, every mistake under a is tight.
Proof of Property @a. Recall the two properties of the algorithm. Observe that the first set dual constraints remain feasible due to Property ii; the second set of constraints satisfied since the
21

---

algorithm stops increasing dual variables soon as it discovers a tight edge; the third set of dual constraints are kept feasible due to Property (i).
Given L C E, let (c) == Ix()(u) L) for E V. Let budget = (Ns - 1) for S SCV. V. Let ALG be the total weight of mistakes the output of Algorithm 5 and OPT be the weight of an optimal solution.
Lemma C.2. We have ALG < (2bgtobal + 2) OPT.
Proof. Observe that, b (Rt) S Igiobal from the very beginning of the algorithm, the algorithm immediately terminates and incurs no weight. Let us thus assume that budget, (R) 3 bglobal the beginning.
Consider the last iteration of while loop of the algorithm. In this iteration, the algorithm removes some edges from L (and possibly removes some vertices). Consider the moment right before the removal of edges. Let R' and I', respectively, denote the value of R and L at this moment. Let := budget, (R'). Note that b' > bgloball since otherwise the algorithm would have terminated earlier. Moreover, this moment-or at the termination-we have 0² = X, for every R'.
then bound OPT from below as follows:
OPT 2 ΣΣ
Be,v Σ
Cvy
Abglobal =
Σ
Σ (EE((v)
Be, - av
Oglabal
(NL 1) VER
Σ
oE DEC
NEV
DEV
Σ
Σ
Be,
av
+ Σ
Σ
Be,
(1
Oglobal V
(KL: - -1) ar
R
(EE(v))
oElr'
(EE5(v)
Σ
Σ
Bev
+ Σ
1+
Oglobal
(112 -1) 11)
Σ Be,
2
REV
(E8(w)
EE
eEd(w)
Σ
Σ
Ber
+ Σ
F. ( (1
bglobal
Σ
Bar
D'
R
(EE(w)
VER
nEa(1)
Σ
Σ
Bex
+ Σ
Igglbbll
Σ
Beg
2
D'
RE
cEδ(v)
VE R'
eEσ(v)
bglobal
Σ
Σ
Se.
(11)
b'
NEV eE5())
where the first inequality is due to Property
a the first equality comes from À = Op for every E R', the second inequality is due to Property (b) and (c), and the second to last inequality comes from K2 (v) 2 2 for every E R². Therefore, by Property (d), we have
ALG S
ΣΣ Be,w S (2bgiobal + + OPT,
VEV REA(M)
where the last inequality comes from D' 2 bglobal which implies 1 bgotbll
bytobal
1
Lemma C.3. Both Algorithm 3 and Algorithm 5 can implemented to run in O((E) O(LEE do)
time.
Proof. It suffices to show that we can decide in O(Evev d,) time which edge becomes tight, as well as the increment of the dual variables. By iterating each node v and its incident edges d(v), we can compute the increase rates of a, and (3e,v bee(()) From this, we can obtain the increase rate of the "level" La : Σuse 3e,u for each E L. Let rate(e) denote this increase rate. As E will become tight in fiighten (e) = Emee 9:.. time, we can determine the edge that will become tight the carliest. We can also compute the increment of the dual variables accordingly.
rate(c)
22

---

Theorem 3.6. Algorithm 5 is 2(bglobal + 1) approximaatio algorithm, for GLOBAL ECC.
Proof. Immediate from Lemmas C.2 and
We note that our approach yields true (non-bicriteria) approximation algorithm. This shows that the I.P. which is equivalent that of Crane et [9], has an integrality gap of Obgllobal..
C.4 Proof of Theorem
Theorem 3,8. The integrality gap of the LP
LP for GLOBAL ECC is at least bglobal + 1.
Proof. We construct an instance similar to the one used in the proof of Theorem 3.7 Consider
hypergraph H (V = {v1,-.. Mbbwwst1] ): (c1,e2)) where and Gej * Ceg. Any integral solution incurs least since at least one node is assigned one color
V. Wey Weg 1,
and at least one edge cannot be satisfied. However, consider the solution given by 2e
bgoear I
Je,ces T2,co2
vo +1 2(beeeu +1)
for all V and Ve. Ve
2(0guu This solution is feasible and
the cost is bI
C.5 Bicriteria algorithm for GLOBAL ECC
Theorem C.4. Suppose that b 2 1. For any c E (0, (0,2hgiobal), there exists a (2+ (2+ approximation algorithm for GLOBAL ECC.
20global
Ogioool
Proof. Let T
2hatsbal 1. Consider the algorithm where the condition of the while loop in bylobal + T. is clear that
Algorithm
is replaced by Even(1x(((e L)] L)[
(axo)] - 1,03 < bglobal + = Oglobal
(1+ b
2bglobal
Igiobal
.EV
Note also that the modified algorithm satisfies all the properties of Lemma
We basically follow the proof of Lemma C.2
With the same definition of R' and L', we have besae
6' budget (R') > bylobal т. Note that equation
Together with
+T+
26 25global
ALG Σ
Σ
Be, S (2+
OPT S (2+)))-0)
T
VEV cεδ(v)
where the last inequality comes from 2byaral
approximation algorithm for GLOBAL ECC for é O. Both approximation factor and violation factor of Crane al.'s algorithm are linear in lglobal- They raised an open question whether we can give a bicriteria approximation algorithm for GLOBAL ECC with both factor being constant (or give hardness
Recall that Crane et al. 19 gave an LP-rounding bicriteria +-gtobal+++4 1,+ 4
result). Observe 2batshal
< + 2. Our bicriteria algorithm satisfies the condition,
byobal
answering the open question of Crane et al.
19
23

---

C.6 Discretized version of Algorithm
Algorithm i discretized version of Algorithm discretized version.
Note that the proof Lemma C.3 is based on this
Algorithm 6 Discretized primal- algorithm for GLOBAL ECC
&e + 0 for all e E E
L + {e E
We > 0}
R E (x(6())))) 2 2] while [ven((x((()) LT) - 1)
bglobal
rate(e) 0 for all L
for R do for ( do
rate(e) + r-te)ee)) (6( for all e 6
highten (e) ma for all e t' t- mineeL Trighten (e)
for e E do le La if le W. then L L {e}
rate(e)
remove all E e from R such that Ix(6(u) (L) s
a(v) x(((e) n L) for all v e V
return 0
D Dataset description
The benchmark data of Crane et al. 19 contains six datasets. Cooking 334 described in Section a hypergraph whose nodes correspond food ingredients, edges represent recipes, and edge colors indicate cuisines. Brain [4]] 21 contains the relation between brain regions: there are two types of relations, coactivation and connectivity, encoded by colors. The nodes corresponds to brain regions, and colored edges represent relations between them. In MAG-10 [5] 4. each node corresponds researcher, and edge indicates the author set of published paper. Its color represents the publication venue (e.g., NeurlPS). DAWN 46 4 is a dataset on the relation between drug use and emergency room (ER) visit disposition such as "discharged"" "surgery", and "transferred". Each node corresponds to drug, an edge corresponds to the combination of drugs taken by an ER patient, and colors represent the visit disposition. Walmart [33 each node represents a product, an edge indicates set of products purchased together, and colors are "trip type" labels determined by Walmart. Lastly in Trivago (38 [8], nodes are vacation rental properties and an edge represents set of rental properties clicked during single browsing session of single user. Colors correspond to the countries where the browsing sessions happen.
E Tables and figures deferred from Section
Table 2: Average running times of each dataset (in seconds): LOCAL ECC. Values in parentheses averages excluding trivial instances.
Proposed
Greedy
LP-rounding
Brain
0.023 (0.12
0.007
(0.028)
0.743
(3.739)
MAG-10
0.142
(0.134)
0.587 (0.554)
10.413
(10.677)
Cooking
0.032
(0,035)
0.099 (0.103)
39,702
(44.916)
DAWN
0.016 (0.019)
0.040 (0.040)
3.948
(4.658)
Walmart
0.190 (0.190)
1.443
(1.443)
145.427
(145.427)
Trivago
0.323 (0.313)
3.709
(3.608)
678.585
(677.036)

---

Table Average running times each dataset (in seconds): ROBUST ECC. Values in parentheses are averages excluding trivial instances.
Proposed
Greedy
LP- LP-rounding
Brain 1.345
(1.345)
0,005
(0.005)
2.007
(2.007)
MAG-10
11.056
(15.303)
0.666 (0.588)
15.871
(17.660)
Cooking
42.571
(42.571)
0.118 (0.118)
220.107
(220.107)
DAWN
39.905
(39.905)
0.048 (0.048)
16.464
(16.464)
Walmart
243.881
(243.881)
1.995 (1.995)
3766.539
(3766.539)
Trivago
195.337
(227.799)
5,210 (5.144)
705.323
(709.378)
MAG-11
20
Cooking
Cooliin
Whimort
Tivgoo
Wolmart
Trivago
30
NowelM
(a) Running times (in seconds, log scale)
(b) Relative errr estimates
Figure 2: (a) Running times (in seconds, log scale) and (b) relative error estimates of the ROBUST ECC algorithms. Empty square markers denote trivial instances.
25

---

Table Average running times of each dataset (in seconds): GLOBAL ECC. Values in parentheses are averages excluding trivial instances.
Proposed
Greedy
LP-rrunding
Brain 0,415
(0.885)
0.008
(0.012)
1.849
(3.381)
MAG-10
3.143
(12.541)
0.787
(0.625)
12.194
(14.418)
Cooking
26.755
(31.609)
0.171
(0.177)
75,953
(88.883)
DAWN
20.345
(26.443)
0.054 (0.052)
7.944
(9.263)
Walmart
117.046
(189.895)
2.310
(2.247)
511.011
(754.344)
Trivago
50.162
(107.449)
7.234
(6.795)
684.776
(662.595)
Riaih
MAG-10
MAG-11
131
Dy
Cocking
DAVIN
Coolding
Opess/M
Wismmrrt
Tivago
Welmart
Trivago
(a) Running times (in seconds, log scale)
(b) Relative errr estimates
Figure 3: (a) Running times (in seconds, log scale) and (b) relative error estimates of the GLOBAL ECC algorithms. Empty square markers denote trivial instances.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract provides a high-level overview our contributions, and the introduction (Section elaborates them.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Scalability and computational efficiency of the proposed algorithms are heavily
discussed throughout the paper, including Sections 4.2 and 4.3 and Appendices A B and
as they are one of the key contributions of this paper. Other limitations and possible future directions of research related them are also discussed in Section 5
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
27

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Theorems are stated in Section 3 some proofs are sketched in Section 3.1 and
the full proof' are presented in Appendices A B and
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Detailed description of the algorithms are presented in Section 3.1 and Ap- pendices A.3 [B B.4
C.2 and C.6 and the experimental setting and details can be found in Sections 1. | 4.2 and 4.3 Moreover, the code is available as supplemental material, and the data used by the experiments are publicly available [47]. One also needs to obtain license for Gurobi LP solver; academic licenses are available.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
28

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is available as supplemental material. The data used by the experiments are publicly available 47
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https Swwoeeeuumisssoooooooo
/ wttppsscc/ppblic////
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All experimenta setting and details can be found in Sections 4.1
4.2 and
4.3
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Neither the proposed algorithms nor the data used in the experiments involve any randomness in their execution or preparation. Due to this deterministic nature of the experiments, statistical errors not need to reported; however, the guideline explicitly states that NA means that the paper does not include experiments at all, which does not
29

---

apply to this paper. Although not directly related to statistical errors, we do report the approximation errors of the algorithms as relative enror estimate normalized, estimated error of the algorithms' output (see Section 4.1 for its definition).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the information the experiment setup in Section 4.1
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: httt://nnusisspe
Answer: [Yes]
Justification:
The paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
30

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper presents foundational research which is generic and does not directly lead to any societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We properly credited the original owners of the code and data used in this
paper 44 21 45
[8] We also obtained valid academic license of
Gurobi and used it.
31

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
32

---

Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
33


Reviews:
[{"review_id": "ZZqMjgUVb1", "reviewer": "Reviewer_oc1j", "summary": "The authors consider several variants of edge coloring clustering (ECC) in hypergraphs. The goal\nof the problem is to given colored edges, color vertices minimizing disagreements. The variants are\nwhere we allow multiple colors for vertices but restricting the number of allowed colors. The authors\npropose approximation algorithms for their LP-based problems, and provide inapproximability results.\nThe authors also combine additional experiments.", "questions": "What is the computational complexity of the original ECC?\nCan we develop combinatorial algorithms for the proposed variants?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "+ The approximation results are interesting, and the inapproximability results provide a more complete results.\n+ The paper is well-written, though relatively dense.\n- As the algorithms are LP-based, the running times are not clear. Are these \n  algorithms scalable? What is the running time for these?  Can one do a combinatorial algorithm derived from LP?\n- The practical impact of these problems may be limited, nevertheless the relaxation variants are worth studying.", "was_revised": true, "final_justification": "In my view, this is a good submission, and the upsides outweigh downsides.", "rebuttal": "Thank you for your valuable comments and questions. They will be very helpful in improving this paper. In particular, multiple comments of yours prompted us to reconsider what should be included in the main body of the paper rather than in the appendix.\n\nWhile we did present the asymptotic running times of all our algorithms, most of them were in the appendix and not very visible:\n\n- Our algorithm for Local ECC runs in linear time, i.e., $O(\\\\sum_{v\\\\in V}d_v)$ time. Note that the length of the description of a hypergraph is $O(\\\\sum_{v\\\\in V}d_v)$. This is the only algorithm whose running time was mentioned in the main body of the paper, on page 5. The analysis is, however, in the appendix, Lemma B.3.\n\n- Our algorithm for Robust ECC and our algorithm for Global ECC both run in $O(|E|\\\\sum_{v\\\\in V}d_v)$ time. This fact was not mentioned in the main body. The analysis is also in the appendix, Lemma D.3.\n\nWe will include a short discussion on these asymptotic running times in the main body of the paper.\n\nA summary of previous work was presented also in the appendix (Appendix A), illustrating how ECC and its overlapping and robust generalizations are applied and how they relate to correlation clustering (CC). We will move this summary to the main body as well.\n\nWhile the aforementioned theoretical running time bounds of our algorithms are small, their scalability can be fully established only after verifying their empirical performance as well. We empirically evaluated our algorithms' running times in Section 4. The experiments confirmed that our algorithms run significantly faster than previous LP-rounding algorithms, demonstrating their scalability. This is because our algorithm does not solve an LP: only in its analysis LPs are used. This is exactly the reason why all our algorithms are indeed combinatorial.\n\nAnother question was on the computational complexity of the ECC. Angel et al. [8] showed the NP-hardness of the \"vanilla\" version of ECC as we mentioned in Section 1, and Veldt [48] showed its APX-hardness.\n\n**We hope our responses have adequately addressed your comments. We greatly appreciate your thoughtful review and consideration.**"}, {"review_id": "SytoyTXYSC", "reviewer": "Reviewer_fUgt", "summary": "This paper studies overlapping and robust edge-colored clustering (ECC) problem on hypergraphs. It is a node multi-coloring task such that the total number (even weight) of mistaken hyperedges whose colors are not covered by their nodes is minimized. The authors investigate three versions named Local, Global and Robust ECCs that have some kinds of budgeted number of node colors or node deletion, and present several algorithmic and lower bound results on them. The main technical contributions include new characterizations of ECCs by linear programming, and combinatorial algorithms based on the primal-dual schema that brings improvements in solution quality. Since the new algorithmic framework is combinatorial and doesn’t need to actually solve LP, it also brings great improvement in time complexity (theoretically). The proofs of lower bound results, including the reductions and instance designs, are constructive. The solution quality and efficiency of their algorithms are evaluated by experiments.", "questions": "N/A.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This paper has provided a new framework of primal-dual schema for the three kinds of ECC problems.\n- It is well written and easy to follow.\n- The experimental results are good.\n\nWeaknesses:\n- I did not find many weaknesses except that the six subfigures of Figure 1(a) are hard to read. The running times of Greedy and Proposed methods are indistinguishable. It is better to have logarithmic scaling on the y-axis also.", "was_revised": true, "final_justification": "This paper proposes combinatorial algorithms for ECC based on the classic primal-dual schema. I think it should be accept.", "rebuttal": "Thank you for your valuable comments. They will be very helpful in improving this paper, especially in the presentation of the experimental results.\n\nAs you suggested, we replotted Figure 1(a) with the y-axis in log scale, which makes the differences between the lines much clearer. We will update the figure, and indicate in its caption that the y-axis is in log scale.\n\n**We hope our responses have adequately addressed your comments. We greatly appreciate your thoughtful review and consideration.**"}, {"review_id": "DLWYaIW9wt", "reviewer": "Reviewer_HJYD", "summary": "The edge-coloring clustering problem is given a hypergraph $(V,E)$ along with a coloring of the edges $c:E\\rightarrow [C]$. Given a coloring of the nodes $\\sigma: V\\rightarrow [2^C]$, we say that $\\sigma(v)$ induces a mistake on $e\\in E$ if $v\\in e$ and $c(e)\\notin \\sigma(v)$.\n\nThe goal is to find $\\sigma$ such that the number of mistakes are minimized. Since a trivial solution making no mistakes colors all nodes with all colors, the authors consider constrained versions of the problem where each node can have at most $b$ many colors (LECC) or the total number of colors is at most $|V|+b$ (GECC). Finally, the authors also consider a variant where $\\sigma: V\\rightarrow [C]$, but nodes may be removed from the graph (RECC).\n\nFor all of these problems, the authors design approximation algorithms. Specifically for LECC, the authors propose a primal dual algorithm that with an approximation ratio of $b+1$, which is optimal assuming the unique games conjecture and nearly optimal assuming $P\\neq NP$. For the other two algorithms the authors devise approximation algorithms that match the integrality gap of their proposed linear program.", "questions": "No questions.", "limitations": "yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "I am not sure how to rate a paper like this in the context of NeurIPS. To me this is a classic approximation algorithms paper that belongs at a theory conference. The connection to clustering or machine learning is fairly strenuous, in my opinion, regardless of whether or not this problem has been previously in a paper published at similar conferences.\n\nAs is often the case with theory papers submitted to NeurIPS, nearly all technical details are in the appendix. While it is hard to fault the authors for this, they might want to consider how to distribute the pages that the reviewers are expected to read. I read the LECC algorithms and lower bounds, as well as the RECC algorithm as this was the chronological order in which they were presented in the main body and also seemed to be how the authors themselves valued the results. If for some reason the GECC result was the most important one (which I didn't read), the authors may want to consider revising the paper.\n\nI would also encourage the authors to not \"waste\" three pages of main body on experiments with a rather dubious quality. The main take-away message seems to be that the previous greedy algorithm (that algorithm is never specified), is worse than the LP-based algorithm. I would have believed that with significantly less space, and preferred more theoretical content in the main body. If the authors did this because some previous reviewer did not engage with the proofs and instead complained about a lack of experiments, then they have my sympathies, but the criticism remains.\n\nIn any case, as far as approximation algorithms go, the algorithm for LECC is technically fairly basic, being a standard primal dual algorithm that commits to colors when complimentary slackness conditions are satisfied. People familiar with similar algorithms for set cover and facility location should be able to derive these results very quickly without looking at this paper. The hardness results for LECC are also standard reductions to vertex cover in hypergraphs. The RECC problem is likewise solved with a primal dual approach. I did not read [19,20], but apparently it is based on the same LP relaxation save for adding the constraint that encodes that every node is assigned at most one color or it is removed. Why the previous algorithms did not consider this constraint is puzzling, as without it the integer linear program can assign multiple colors to a node. Then even the ILP will have an unbounded gap to the value of the optimal solution. In any case, including both LP formulations in the main body would have been nice as while it is not to difficult for the reader familiar with primal dual algorithms to formulate the LPs, I do not believe that merely stating the dual in the main body will be of much use to readers that are not familiar.\n\nIf I were to rate this paper for a top algorithms conference, it would be a reject as the techniques are well known. The problem has been studied previously, so it seems that there might be some interest in having a solution, though I still doubt that this algorithm or for that matter the problem are practically viable. I eventually talked myself into a minor positive rating for this paper, as it is a thorough treatment of the problem.", "was_revised": true, "final_justification": "Nothing changed, so my opinion also has not changed.", "rebuttal": "Thank you for your valuable comments. They will be very helpful in improving this paper. In particular, they have been insightful in guiding us on how to reorganize the paper for the camera-ready version that will be prepared if the paper is accepted, where one additional page will be allowed.\n\nAlthough the Questions section did not contain any questions, we would still like to briefly give one mathematical clarification and share a few explanations of our perspectives.\n\nThe clarification is regarding the comment \"*the ILP [of Crane et al.] will have an unbounded gap*\". Our LP relaxation for Robust ECC is as follows:\n$$\n\\\\begin{aligned}\n\\\\min \\\\ & \\\\sum_{e \\\\in E} w_e y_e \\\\\\\\\n\\\\text{s.t. } \\\\ & z_v + \\\\sum_{c \\\\in C} x_{v,c} \\\\le 1, & & \\\\forall v \\\\in V, \\\\\\\\\n& z_v + x_{v,c_e} + y_e \\\\ge 1, & & \\\\forall e \\\\in E, \\\\ v \\\\in e, \\\\\\\\\n& \\\\sum_{v \\\\in V} z_v \\\\le b_{\\\\mathrm{robust}}, & & \\\\\\\\\n& x_{v,c} \\\\ge 0, & & \\\\forall v \\\\in V, c \\\\in C, \\\\\\\\\n& y_e \\\\ge 0, & & \\\\forall e \\\\in E, \\\\\\\\\n& z_v \\\\ge 0, & & \\\\forall v \\\\in V,\n\\\\end{aligned}\n$$\nwhereas Crane et al. [19] uses the following LP (slightly modified for easier comparison):\n$$\n\\\\begin{aligned}\n\\\\min \\\\ & \\\\sum_{e \\\\in E} y_e \\\\\\\\\n\\\\text{s.t. } \\\\ & \\\\sum_{c \\\\in C} x_{v,c} \\\\ge |C|-1, & & \\\\forall v \\\\in V, \\\\\\\\\n& x_{v,c_e} - z_v \\\\le y_e, & & \\\\forall e \\\\in E, \\\\ v \\\\in e, \\\\\\\\\n& \\\\sum_{v \\\\in V} z_v \\\\le b_{\\\\mathrm{robust}}, & & \\\\\\\\\n& x_{v,c} \\\\in [0,1], & & \\\\forall v \\\\in V, c \\\\in C, \\\\\\\\\n& y_e \\\\in [0,1], & & \\\\forall e \\\\in E, \\\\\\\\\n& z_v \\\\in [0,1], & & \\\\forall v \\\\in V.\n\\\\end{aligned}\n$$\n(The two LPs use opposite senses for the \"binary\" variable $x$.) Note that the ILPs obtained by adding the integrality constraint $x_{v,c},y_{e},z_{v}\\in\\mathbb{Z}$ to the above two LPs both yield the exact optimal value of the original problem. To put it differently, if we take all *integral* feasible solutions to each LP and project them onto the space of $y$'s and $z$'s, the two LPs give the same set, whereas doing the same for all *fractional* feasible solutions results in different sets (as is often the case between two lifted LP relaxations for an optimization problem with differing integrality gaps).\n\nThere was a comment that the volume of experimental analysis in the main body is too large compared to the theoretical content. Thank you for the comment. We agree that the theoretical analysis did not receive ideal coverage in the main body of the paper. While we provided an almost complete *sketch* of the analysis for our algorithm for Local ECC in Section 3, we were not able to do the same for the other algorithms. In determining the relative amount of theoretical and experimental analysis, we also referred to the literature as the three problems were previously studied; however, as the reviewer noted, our main consideration was what should be presented within the first nine pages. Since the primary contribution of this paper is in giving new algorithms that outperform existing ones, it was crucial to demonstrate the advantages of the new methods. We felt that not all readers would readily be convinced of these improvements without thorough *experimental* results on both solution quality and running time. That said, if the paper is accepted, the camera-ready version allows one additional page, which will help address the concern. Additionally, the description of the experimental setup currently occupies about one page of the main body; we plan to condense this part and reallocate space to bring part of the theoretical analysis from the appendix into the main body. Thank you for this helpful comment.\n\nAnother point made in the review was that the hardness proof is relatively simple. We agree that this proof is not technically challenging, and we do not consider it to be a primary contribution of the paper. However, we felt it was important to make this hardness result part of the published record, as it was not known in the existing literature and, in fact, questions had even been posed that this hardness result rules out. To settle these questions and to provide a better landscape of the problems, we thought it worthwhile to point out that a relatively simple argument can be used to show the desired hardness results. For the same reason—to provide a better landscape—we also reported  integrality gap results.\n\nThe review also pointed out that, in Section 3.2, we presented only the dual LP without the primal. We fully agree that additionally including the primal would be preferable, and we will do so in the camera-ready version. In that section, we provided only (an outline of) the algorithm without detailed analysis due to space constraints, and the dual alone was \"sufficient\" for the mechanical description of the algorithm. However, we completely agree that presenting both the primal and dual LPs would be much better, and we will make this improvement in the camera-ready version with the additional page allowed.\n\nOverall, taking the reviewer’s valuable comments into account and making use of the additional page available in the camera-ready version, we will make adjustments to the organization of the paper—particularly regarding what belongs in the main body versus the appendix.\n\n**We hope our responses have adequately addressed your comments. We greatly appreciate your thoughtful review and consideration.**"}, {"review_id": "tFa3D6YOVL", "reviewer": "Reviewer_oQ2L", "summary": "This paper studies the recently-introduced clustering problems on edge-colored hypergraphs, generally called Edge-Colored Clustering (ECC). In ECC, we are given an edge-colored hypergraph, where each hyperedge has a single color, and asked to assign colors to nodes so as to minimize the number of mistakes, i.e., the number of hyperedges that contain a node that does not have the hyperedge's color. The authors specifically consider the following three problems: Local ECC, Robust ECC, and Global ECC. Local ECC and Global ECC formulate the overlapping nature of clustering. Both problems consider assigning possibly multiple colors to each node; the former imposes an upper bound $b_\\text{local}$ on the number of colors that each node can receive (i.e., Local), while the latter imposes an upper bound $b_\\text{global}$ on the total number of colors that the nodes can receive beyond the single colors (i.e., Global). On the other hand, Robust ECC is capable of taking into account the existence of outliers in hypergraphs, where we can ignore at most $b_\\text{robust}$ nodes. The contribution of this paper is to develop primal-dual approximation algorithms for the above three problems. For Local ECC, the proposed algorithm achieves the state-of-the-art approximation ratio of $b_\\text{local}+1$. For Global ECC and Robust ECC, the proposed algorithms have the approximation ratios of $2(b_\\text{global}+1)$ and $2(b_\\text{robust}+1)$, respectively. The authors also complement their positive results with some inapproximability results and integrality-gap results. Computational experiments demonstrate that the proposed algorithms work well in terms of both solution quality and running time.", "questions": "- In the problem formulations, Local ECC and Global ECC look similar; however, in the algorithm section, it is stated that the proposed algorithms are similar for Global ECC and Robust ECC. Could the authors give a brief explanation why this happens? The reviewer imagines it is due to the global nature of the constraints, but some additional comments would be helpful. \n- In the algorithm descriptions, the concept of \"unit rate\" is a bit ambiguous. Why don't the authors explicitly specify such rates using the notation in the constraints?\n- Also, it is stated that the node selection ordering is arbitrary to prove the approximation ratio. However, the selection might be critical in the practical performance. Which selection rule do the authors employ in the experiments? Don't the authors investigate the effect of the selection in the practical performance? Figure 1(b) shows that the relative error comes almost solely from the mistakes of the algorithms, and thus, there might be some room for improving the practical performance.", "limitations": "yes.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\nThis is a technically solid paper. Clustering is one of the central topics in data mining and machine learning, and particularly, ECC has recently been actively studied in the literature. The proposed algorithms are well motivated. Existing algorithms for ECC fall into two classes: (i) scalable combinatorial algorithms that only achieve poor approximation ratios (i.e., the maximum size of hyperedges) and (ii) LP rounding algorithms that achieve a good (bicriteria) approximation but require much time complexity. The proposed algorithms bridge this gap: The algorithms are scalable and recover (or sometimes discover) the best-known approximation ratios. The authors also complement their positive results with some inapproximability results. In particular, the authors show that Local ECC is $(b_\\text{local}+1-\\epsilon)$-inapproximable and $(b_\\text{local}-\\epsilon)$-inapproximable under UGC and P != NP, respectively, which (almost) match the proposed algorithm's approximation ratio. The technical claims are all validated with rigorous mathematical discussions. Computational experiments are performed under reasonable setups, and it is observed that the proposed algorithms outperform the baseline methods. \n\n**Weaknesses:**\nThe novelty is slightly limited. As the problems studied are all existing problems, there is no essential novelty in the problem formulations. The only novelty can be found in the algorithm design and analysis, but all algorithms follow the standard technique for designing approximation algorithms, i.e., the primal-dual method, and the approximation-ratio analysis is an expected outcome. The reviewer does not say those are straightforward, but still, their novelty is not that significant. At least, the current statements like \"we present a new algorithmic framework...\" are exaggerations. Indeed, the authors do not present a new algorithmic framework; they follow the well-established algorithmic framework (i.e., the primal-dual method) to design approximation algorithms. \n\n\nMinor comments:\n- The problem generalizations for which the authors present the proposed algorithms should be mentioned in the problem formulations. \n- Algorithm 1 should return $\\sigma$. \n- Theorems 3.7 and 3.8 should be modified so that they refer to the concrete algorithms. \n- Figure 1 should be enlarged for readability.", "was_revised": true, "final_justification": "My original assessment was borderline accept. After carefully reviewing the authors’ responses and the discussions with the other reviewers, I find the proposed revisions to be reasonable. Although I still consider the novelty of the work to be somewhat limited, I maintain a positive overall view of the paper.", "rebuttal": "Thank you for your valuable comments and questions. They will be very helpful in improving this paper, especially in refining how we describe our algorithms and enhancing its clarity.\n\nWe view the main contributions of our paper as (i) providing improved algorithms for Local ECC, Robust ECC, and Global ECC that are both fast and produce high‑quality solutions, and (ii) answering previous questions about whether the existing algorithms could be improved, thereby offering a clearer picture of these problems. Using the primal-dual method, in conjunction with existing or new LPs, we obtain a family of algorithms that solves all three problems. Of course, we do not claim credit for the primal–dual method itself. If our choice of the word \"framework\" may give rise to such a misunderstanding (and we see how that might happen), we will find a more appropriate expression. At present, we are considering the term \"collection of algorithms\", but we would welcome suggestions for better alternatives.\n\nWe now address the minor comments and questions one by one.\n\n- *The problem generalizations ...*\n\nWhile the algorithms we present in Section 3 (and in the appendix) solve slightly generalized versions of the problems, we defined the problems without these generalizations in Section 2. We initially made this choice because the paper did not include an explanation of the contexts in which such generalizations arise, and moreover, the existing literature had only considered the versions defined in Section 2. However, we agree with the comment that the generalized version of the problem definition should be introduced earlier rather than waiting until we present the algorithms. If the paper is accepted, we will include in Section 2 of the camera-ready version an explanation of these generalizations. Thank you for this suggestion.\n\n- *Algorithm 1 should return $\\\\sigma$.*\n\nWe will fix this in the camera-ready version.\n\n- *Theorems 3.7 and 3.8 should ...*\n\nTheorems 3.7 and 3.8 provide lower bounds on the integrality gaps. An integrality gap is a property of an LP relaxation itself, rather than of any algorithm using the relaxation. It measures how much relaxing the integrality constraints of an ILP can change the optimal value, revealing an inherent limitation on the performance of any algorithm whose analysis compares its output against the LP optimum. The two theorems did not refer to a concrete algorithm as they concern integrality gaps.\n\n- *Figure 1 should be enlarged for readability.*\n\nThank you for bringing this issue to our attention. Another review also raised a related point. As suggested in that review, we will redraw Figure 1(a) using a log scale. We will also enlarge both Figure 1(a) and Figure 1(b) in the camera-ready version.\n\n- *In the problem formulations, Local ECC and Global ECC look similar; ...*\n\nThat is exactly correct. Both problems involve global constraints, and as a result their LP formulations become somewhat similar. Consequently, the algorithm for Global ECC is closer to that for Robust ECC than to that for Local ECC, which is why we presented the first two algorithms together. As suggested, we will add a comment in the paper explaining this similarity. We appreciate this helpful suggestion.\n\n- *In the algorithm descriptions, the concept of \"unit rate\" is ...*\n\nThank you for sharing this feedback. We have carefully considered throughout the preparation of this manuscript how to best present the algorithms—balancing between an intuitive *process‑over‑time* presentation and a fully mechanical *discretized* one. The process‑over‑time view does not directly correspond to how the algorithm is mechanically implemented; in this view, only the relative rates matter, and their absolute values do not. For example, suppose two variables $x_1$ and $x_2$ start at 0 and increase at rates 1 and 2, respectively, until one reaches 1. After 0.5 units of *imaginary* \"time\", we obtain $x_1 = 0.5$ and $x_2 = 1$. If the rates were instead 2 and 4, the elapsed time would be 0.25, but the resulting values of $x_1$ and $x_2$ would be identical. This illustrates that the specific absolute values of the rates are irrelevant, which is why we used \"unit rates\" to keep the presentation (and, more importantly, the analysis) simple.\n\nThat said, your comment is especially helpful, as it highlights a point that was not adequately emphasized in the paper. While the process‑over‑time presentation is intuitive, it hides details of how the algorithm is actually implemented. This may cause confusion. For this reason, we provided a discretized version (see, e.g., Algorithm 2) that makes all details explicit enough to be directly translated into code, but this point was not sufficiently emphasized in the paper. We will clarify this point in the camera‑ready version. Thank you for raising this issue.\n\n- *Also, it is stated that the node selection ordering is ...*\n\nWe are not entirely certain whether we have correctly understood this question. We presume it concerns our algorithm for Local ECC, since it is the only algorithm that involves a node ordering. If \"*node selection ordering*\" refers to the order by which vertices are considered in the for loop of Algorithm 1, then it is correct that this choice leaves some flexibility in implementation. Initially, we did not think that this ordering would be important, and our implementation of Algorithm 1 simply processed the vertices in the order they appear in the input.\n\nIn response to this comment, we conducted an additional experiment where the vertices were selected in a random order. For each instance, we performed 20 independent runs and observed that the solution quality is improved by <2.1% on average compared to the original implementation, suggesting that the potential for optimization is relatively limited. We will add a discussion of this point to the camera‑ready version of the paper.\n\n**We hope our responses have adequately addressed your comments. We greatly appreciate your thoughtful review and consideration.**"}]

Author rebuttal:

Meta-review: Reviewer fUgt provides a perfect summary of this submission: “This paper studies overlapping and robust edge-colored clustering (ECC) problem on hypergraphs. It is a node multi-coloring task such that the total number (or weight) of mistaken hyperedges whose colors are not covered by their nodes is minimized. The authors investigate three versions named Local, Global and Robust ECCs that have some kinds of budgeted number of node colors or node deletion, and present several algorithmic and lower bound results on them. The main technical contributions include new characterizations of ECCs by linear programming, and combinatorial algorithms based on the primal-dual schema that brings improvements in solution quality. Since the new algorithmic framework is combinatorial and doesn’t need to actually solve LP, it also brings great improvement in time complexity (theoretically). The proofs of lower bound results, including the reductions and instance designs, are constructive. The solution quality and efficiency of their algorithms are evaluated by experiments.”

The general opinion about this submission is quite positive. The considered problem is interesting, and the paper provides a thorough and comprehensive treatment of the problem. The only weakness mentioned by reviewers HJYD and oQ2L is that the novelty of the work is somewhat limited because the methods (e.g. primal-dual approximation algorithms) are well-known. On a technical level this submission is not a breakthrough, however, the problem and the results are interesting.
Decision: Accept (poster)