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

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.

We 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.

We now address the minor comments and questions one by one.

• The problem generalizations ...

While 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.

• Algorithm 1 should return $\\sigma$.

We will fix this in the camera-ready version.

• Theorems 3.7 and 3.8 should ...

Theorems 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.

• Figure 1 should be enlarged for readability.

Thank 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.

• In the problem formulations, Local ECC and Global ECC look similar; ...

That 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.

• In the algorithm descriptions, the concept of "unit rate" is ...

Thank 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.

That 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.

• Also, it is stated that the node selection ordering is ...

We 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.

In 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.

We hope our responses have adequately addressed your comments. We greatly appreciate your thoughtful review and consideration.

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.

Although 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.

The 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:

\\begin{aligned} \\min \\ & \\sum_{e \\in E} w_e y_e \\\\ \\text{s.t. } \\ & z_v + \\sum_{c \\in C} x_{v,c} \\le 1, & & \\forall v \\in V, \\\\ & z_v + x_{v,c_e} + y_e \\ge 1, & & \\forall e \\in E, \\ v \\in e, \\\\ & \\sum_{v \\in V} z_v \\le b_{\\mathrm{robust}}, & & \\\\ & x_{v,c} \\ge 0, & & \\forall v \\in V, c \\in C, \\\\ & y_e \\ge 0, & & \\forall e \\in E, \\\\ & z_v \\ge 0, & & \\forall v \\in V, \\end{aligned}

whereas Crane et al. [19] uses the following LP (slightly modified for easier comparison):

\\begin{aligned} \\min \\ & \\sum_{e \\in E} y_e \\\\ \\text{s.t. } \\ & \\sum_{c \\in C} x_{v,c} \\ge |C|-1, & & \\forall v \\in V, \\\\ & x_{v,c_e} - z_v \\le y_e, & & \\forall e \\in E, \\ v \\in e, \\\\ & \\sum_{v \\in V} z_v \\le b_{\\mathrm{robust}}, & & \\\\ & x_{v,c} \\in [0,1], & & \\forall v \\in V, c \\in C, \\\\ & y_e \\in [0,1], & & \\forall e \\in E, \\\\ & z_v \\in [0,1], & & \\forall v \\in V. \\end{aligned}

(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).

There 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.

Another 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.

The 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.

Overall, 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.

We hope our responses have adequately addressed your comments. We greatly appreciate your thoughtful review and consideration.

Thank you for your valuable comments. They will be very helpful in improving this paper, especially in the presentation of the experimental results.

As 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.

We hope our responses have adequately addressed your comments. We greatly appreciate your thoughtful review and consideration.

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.

While we did present the asymptotic running times of all our algorithms, most of them were in the appendix and not very visible:

• 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.

• 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.

We will include a short discussion on these asymptotic running times in the main body of the paper.

A 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.

While 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.

Another 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.

We hope our responses have adequately addressed your comments. We greatly appreciate your thoughtful review and consideration.