Multilayer Correlation Clustering

We greatly appreciate your careful reading and invaluable feedback.

W1

Regarding the motivations, please read Lines 63–73 in our manuscript: Multilayer Correlation Clustering is motivated by real-world scenarios. Suppose that we want to find a clustering of users of $\mathbb{X}$ using their similarity information. In this case, various types of similarity can be defined through analysis of users' tweets and observations of different types of connections among users such as follower relations, retweets, and mentions. In the original Correlation Clustering, we need to deal with that information one by one and manage to aggregate resulting clusterings. On the other hand, Multilayer Correlation Clustering enables us to handle that information simultaneously, directly producing a clustering that is consistent (as much as possible) with all types of information. As another example scenario, suppose that we analyze brain networks, where nodes correspond to small regions of a brain and edges represent similarity relations among them. Then it is often the case that the edge set is not determined uniquely; indeed, there would be at least two types of similarity based on the structural connectivity and the functional connectivity among the small pieces of a brain. Obviously, Multilayer Correlation Clustering can again find its advantage in this context.

Your suggested aggregation rules of weight functions over layers are not well-defined. For instance, the reviewer suggests $w^+:= \max\_{\ell \in [L]} w^+\_\ell$ and $w^-:= \max\_{\ell \in [L]} w^-\_\ell$; however, as $w^+\_\ell$ and $w^-\_\ell$ are functions, the max-operator over $\ell\in [L]$ is not well-defined. Instead, we could consider aggregation rules such as $w^+(u,v):= \max\_{\ell \in [L]} w^+\_\ell(u,v)$ and $w^-(u,v):= \max_{\ell \in [L]} w^-\_\ell(u,v)$ for $\\{u,v\\}\in E$.

Of course, aggregating different layers into one layer, and then solving MinDisagree on only one layer, is an efficient attempt at solving our problem, and this is exactly what the baseline Aggregate does. However, as demonstrated by the example below, and in our experiments, such methods perform very poorly with respect to approximating the objective function. Please note that one of the suggested aggregation rules is exactly the same as that employed in the baseline Aggregate.

As in the definition, the objective of Multilayer Correlation Clustering is to find a clustering that minimizes the $\ell_p$-norm of the multilayer-disagreement vector. In particular, as the most intuitive case, if we set $p=\infty$, we can minimize the maximum disagreement over layers. This is the clear benefit of solving Multilayer Correlation Clustering.

W2

Please notice that the suggested aggregation rule does not perform well. Intuitively speaking, for each pair of elements, the rule forgets about anything except for the maximum weight, resulting in a poor performance even in the case of $p=\infty$. We can prove this theoretically. Consider the following instance: Fix $p=\infty$. The set $V$ consists of $n$ elements. There are ${n\choose 2}$ layers, where in each layer there is only one pair having `$+$’ label with weight $1$ and all the other ${n\choose 2} - 1$ pairs have `$-$’ label with weight $1$, such that the pairs having `$+$’ label with weight $1$ are distinct over the layers. Then the optimal solution to this instance is a clustering consisting of $n$ singleton clusters, achieving the optimal value being just $1$ for Problem 1. On the other hand, the suggested aggregation rule produces $w^+(u,v)= 1$ and $w^-(u,v)=1$ for all $\{u,v\}\in E$, and it is obvious that the optimal solution to MinDisagree with these weights can be any clustering, e.g., the clustering consisting of a single cluster containing all elements, achieving the objective value being ${n\choose 2}-1$ for Problem 1. Therefore, the approximation ratio of this algorithm is $\Omega(n^2)$. On the other hand, the above instance is an instance of Problem 1 of the unweighted case, and therefore, our proposed algorithm, i.e., Algorithm 2, achieves the approximation ratio of $3.437+\epsilon$, for any $\epsilon >0$.

W3

It is not clear what the information gain for Problem 1 means. If the reviewer could provide its exact definition, we would be open to discuss it. On the other hand, as Problem 1 is an optimization problem, the clustering accuracy should be measured using the objective function, which is exactly what we did in the experiments. The objective value (the lower the better) achieved by Algorithm 1 is often quite close to the lower bound (and thus the optimal value).

What additional information...?

As mentioned above, Multilayer Correlation Clustering provides additional information, e.g., a clustering that minimizes the maximum agreements over layers. As proved above, simply aggregating weight functions works very poorly to solve the problem, highlighting the effectiveness of our proposed algorithms.

Thank you. As a summary:

1, Problem 1 with $p=1$ is equivalent to MinDisagree with dissimilarity measure $w^{+}(u,v) = \sum_{l=1}^L w^{+}(u,v)$ (proposed in literature), which is the baseline approach Aggregate in the numerical studies.

2, Problem 1 with $p=\infty$ is the method algorithm 1 in numerical studies, which may NOT be equivalent to MinDisagree with $w^{+}(u,v) = \max_{l} w^{+}(u,v)$. MinDisagree with $w^{+}(u,v) = \max_{l} w^{+}(u,v)$ is the new added method Aggregate (new) in numerical studies.

The clustering results of algorithm 1 and Aggregate are evaluated by computing Problem 1 with $p=\infty$. The clustering results of algorithm 1 are obtained by minimizing Problem 1 with $p=\infty$, of course, it will win. This comparison is insufficient, I keep my ratings.

You wrote ``Despite these findings, the reviewer’s final assessment disregards Aggregate (new) entirely and bases their conclusion solely on a comparison between our proposed algorithm and the original baseline Aggregate."

In my opinion, the comparison between algorithm 1 (problem 1 with $p=\infty$) and Aggregate (new) is also inadequate for the same reason: the clustering results are evaluated by computing problem 1 with $p=\infty$, algorithm 1 wins for sure.

We greatly appreciate your careful reading and invaluable feedback.

Lack of theoretical justification for the effectiveness of the results: There is no comparative analysis of the algorithm with related work (e.g., MCCC, Bonchi et al. (2015)), nor is there a lower bound provided.

Although the input of MCCC is essentially the same as that of our problem of the unweighted case, the objective function is completely different, as explained on Lines 155–161. Therefore, it is very unlikely that the existing algorithms for MCCC provide an approximation guarantee for our problem, even if we only consider the unweighted case. If we consider the general weighted case, it seems impossible, because MCCC does not take into account the weights and the way to generalize it to the weighted case is not trivial. Please note that as mentioned on Lines 43--45, improving the $O(\log n)$-approximation for MinDisagree, a quite special case of our problem, is at least as hard as improving the $O(\log n)$-approximation for Minimum Multicut (Garg et al., 1996), which is one of the major open problems in theoretical computer science. This is not a lower bound, but provides a certificate of difficulty of approximation.

The approach requires to solve CV or LP which are heavy for larger datasets. (In the experiments, only $p=\infty$ was tested; I suspect that if other values of $p$ are used, the running time will be longer due to the need to solve CV.)

Yes, if other values of $p$ are used, the running time could be longer. However, the reason why we decided not to perform our experiments with other values of $p$ is based on the following facts:

• CV is still solvable to arbitrary precision in polynomial time, but implementing the algorithms for the problem (e.g., the interior-point method (Boyd & Vandenberghe, 2004)) requires much effort, which is beyond the interest of our work focusing particularly on the theory.

• For reference, let us mention the experimental settings of the papers that study the local objectives for MinDisagree, as the contexts in which this model and our model are situated are very similar. As reviewed in Appendix A.1, in the model with the local objectives, the disagreements of a clustering are quantified locally rather than globally, at the level of single elements. Specifically, the papers consider a disagreements vector (with dimension equal to the number of elements), where $i$-th element represents the disagreements incident to the corresponding element $i\in V$. The goal is then to minimize the $\ell_p$-norm ($p\geq 1$) of the disagreements vector. This model is totally different from our model, but in the sense that both of them deal with $\ell_p$-norms in the objective, they are similar. To the best of our knowledge, there exists no paper that performs experiments for the case of $p\in (1,\infty)$, though Davies et al. (2023) and Heidrich et al. (2024) conducted experiments for the case of $p=\infty$. Therefore, our experimental setting is consistent with those in the literature.

Only arXiv version is cited for several papers — are they published in a conference? Please check.

In our reference list, we have two arXiv papers: Ahmadi et al. (2020) and Kuroki et al. (2024). We could not find any conference or journal version of Ahmadi et al. (2020), but we found Kuroki et al. (2024) accepted to NeurIPS 2024. In our revised version, we will update the information properly. Thank you for your question.

The baselines (Pick-a-Best and Aggregate) are relatively trivial algorithms, but in the experiments, their results seem to also approach the optimal solution of the LP. Does this suggest that there may be some issues with the experimental setup?

Pick-a-Best and Aggregate do not approach the lower bound provided by the LP. For convenience, we summarize the results of Table 1 below. Indeed, the objective value achieved by Pick-a-Best is almost equal to twice the lower bound for the first and fourth dataset. Pick-a-Best works slightly better, but it usually achieves the objective value greater than 1.3 times the lower bound; in particular, for the last dataset, it achieves 1.64 times the lower bound. On the other hand, the objective value achieved by Algorithm 1 is often quite close to the lower bound, and even for the worst case (i.e., aves-weaver-social), the objective value is less than 1.24 times the lower bound.

We greatly appreciate your careful reading and invaluable feedback.

Not sure how suitable the paper is for ICLR audience, as it is more of an SODA/ALENEX type paper...

Thank you for recognizing the technical merits of our work. According to the Call for Papers of ICLR 2025, the conference welcomes submissions from all areas of machine learning. Considering the fact that Correlation Clustering has actively been studied in the literature of machine learning, we believe that our work completely falls into the scope of the conference.

In Section 5.1, Authors could do much more justice in explaining how they use Problem 2...

In our current manuscript, the descriptions are provided in the proof of Lemma 2, which can be found in Appendix C.1. Fix $p\geq 1$. Let $V$ and $(w^+\_\ell,w^-\_\ell)\_{\ell \in [L]}$ be the input of Problem 1 with the probability constraint, satisfying $w^+\_\ell(u,v)+w^-\_\ell(u,v)=1$ for any $\ell\in [L]$ and $\{u,v\}\in E$. We construct an instance of Problem 2 as follows: Let $X = [0,1]^E$, where $E$ is the set of unordered pairs of distinct elements in $V$, and $d\colon X\times X\rightarrow \mathbb{R}\_{\geq 0}$ be a metric such that $d(x,y)\coloneqq \\|x-y\\|\_1$ for $x,y\in X$. For $x\in X$ and $\\{u,v\\}\in E$, we denote by $x(u,v)$ the element of $x$ associated with $\\{u,v\\}$. For each $\ell \in [L]$, let $x_\ell\in X$ be the element such that $x_\ell(u,v)=w^-\_\ell(u,v)$ for $\\{u,v\\}\in E$. Let F=\\{x\in \\{0,1\\}^E : \text{x$induces a clustering of$V}\\}. Here $x$ is said to induce a clustering of $V$ if every connected component in $(V,E\_x)$, where $E_x=\\{\\{u,v\\}\in E : x(u,v)=0\\}$, is a clique. Then we see that there is a one-to-one correspondence between $F$ and the set of clusterings of $V$, and moreover, the objective function of Problem 2 becomes equivalent to that of Problem 1 with the probability constraint.

Please note that Algorithm 2 for Problem 2 with the above input produces a clustering of $V$ rather than a metric over $V$. Therefore, the solution is different from the pseudometric obtained from our convex programming relaxations. Even if the reviewer refers to the solution obtained by Algorithm 3 based on our convex programming relaxations, there is no direct relationship between the solutions. As discussed above, the metric space is the space of all vectors in $[0,1]^E$, but please also note that we do not need to store the entire metric space as input when considering Problem 1 with the probability constraint.

In our revised version, we will move the above description from Appendix C.1 to the main body while stressing that Problem 3 is challenging. We believe that this modification will improve the readability and further highlight the technical merits of our work. Thank you very much for your suggestion.

6.1 Are there no real-world datasets without any semi-synthetic aspect...

To the best of our knowledge, there is no publicly-available dataset that can be directly used as an instance of our problem. To overcome this, we implemented the reasonable way to generate our instances.

Why is pick the best not run for the larger datasets?

Pick-a-Best was indeed run for the larger datasets, but as "OT" indicates in Table 1, the algorithm did not terminate in 3,600 seconds.

Are there any other baselines one can think of?...

We believe that we have already implemented and tested all reasonable baselines, although there are always many possibilities to design heuristic methods.

Line 135: "2.5 approximation, respectively" -- means what?...

We mean that Ailon et al. (2008) demonstrated that (i) the counterpart of KwikCluster achieves a 5-approximation for MinDisagree with the probability constraint, and (ii) the counterpart of KwikCluster with the pseudometric computed by the LP relaxation achieves a 2.5-approximation for MinDisagree with the probability constraint. We will modify the sentence so that it makes more sense. If we say that the weights of `$-$’ labels satisfy the triangle inequality constraint, we assume that the weights themselves are nonnegative values, as we always assume it throughout the paper. In our revised version, we will clarify this point. Thank you for your question.

Line 231: "Note however that for Problem 1 of the unweighted case" -- what does this mean?

We mean the following: Assume that $p=1$. As Problem 1 of the unweighted case is a special case of Problem 1 with the probability constraint, the aforementioned reduction, simply summing up the weights over all layers for each pair of elements and dividing it by $L$, still provides a 2.5-approximation for Problem 1 of the unweighted case. However, despite the fact that MinDisagree of the unweighted case is $(1.437+\epsilon)$-approximable, there is no trivial reduction that can beat this 2.5-approximation. In our revised version, we will modify this sentence too. Thank you for your question.

We greatly appreciate your careful reading and invaluable feedback.

one major concern I have is that there is limited novelty. Introducing a new problem is always interesting however in terms of techniques the paper heavily relies on prior works. The L layers in the input are handled in a relatively straighforward way and the analysis is a bit incremental, given the large bode of works for correlation clustering. I like the paper, but this is an important concern that I have.

We respectfully disagree that there is limited novelty in terms of techniques, based on the following facts:

Algorithm 1: This algorithm is an extension of the $O(\log n)$-approximation algorithms for MinDisagree (Charikar et al., 2005; Demaine et al., 2006) and thus employs the region growing technique (Garg et al., 1996). However, the algorithm carefully selects the radius that minimizes the maximal ratio of the cut value to the volume of the ball of the chosen pivot over all layers $\ell\in [L]$ with $F_\ell\neq 0$. It is worth mentioning that the rule of the selection, i.e., minimization of the maximal ratio, is not straightforward, given the fact that we are interested in our general objective of the $\ell_p$-norm not only with $p=\infty$ but also with $p\in (1,\infty)$. Thanks to this rule, our algorithm achieves the approximation ratio of $O(L\log n)$. Moreover, the analysis is not a direct outcome of the previous analysis of the $O(\log n)$-approximation algorithms for MinDisagree.

Algorithm 2: To design this algorithm, we first provided a polynomial-time approximation-preserving reduction from Problem 1 with the probability constraint to a novel optimization problem in a metric space (i.e., Problem 2). Then, Algorithm 2 was designed for Problem 2, based on a subproblem in a metric space (i.e., Problem 3). We proved that Algorithm 2 is an $(\alpha+2)$-approximation algorithm for Problem 2, where $\alpha$ is a possible approximation ratio for Problem 3. Thanks to the generality of the algorithm and analysis, we can derive a series of approximation results for various problem settings: the approximation ratios 4.5 for Problem 1 with the probability constraint, $3.437+\epsilon$ for Problem 1 of the unweighted case, and 3.5 for Problem 1 with the probability constraint and the triangle inequality constraint.

Algorithm 3: We agree that this algorithm is a simple extension of the 4-approximation algorithm for MinDisagree of the unweighted case, designed by Charikar et al. (2005), as it only replaces their LP relaxation with our convex programming relaxations. However, it is worth emphasizing that Theorem 3 indicates that the 4-approximation algorithm for MinDisagree of the unweighted case (Charikar et al., 2005) can be extended to the probability constraint case, which has yet to be mentioned before. Although some approximation ratios better than 4 are known for MinDisagree of the unweighted case, thanks to its simplicity and extendability, the algorithm has been generalized to various settings of the unweighted case, as mentioned on Lines 446–448. The extendability comes particularly from the fact that the analysis is not based on the bad triples, unlike the analysis of the approximation ratio of 3 of KwikCluster (Ailon et al., 2008). Our analysis implies that those results may be further generalized from the unweighted case to the probability constraint case.

The main premise, could it be applied to more problems? Are there related works that are directly related? This is a nice twist in a famous problem and I am curious if this has been studied for more traditional clustering problems like k-means or other graph partitioning problems.

Our idea in the problem formulation, i.e., generalizing from a single layer to multiple layers and employing the $\ell_p$-norm as the objective function, can be applied to many other problems. On the other hand, in terms of the algorithmic techniques, it is not clear whether our technique can be applied to other problems. In our understanding, the directly related problem, in the reviewer’s definition, would be only the problem called Simultaneous Max-Cut introduced by Bhangale and Khot (2018), which is now mentioned in Appendix E.1. To the best of our knowledge, except for this problem, there are no multilayer generalizations for traditional clustering problems such as k-means, k-median, and k-center. In our revised version, we will put the paper by Bhangale et al. (2018) and Bhangale and Khot (2020) in the related work section, and mention the generalization of our problem formulation and algorithmic techniques to other problems as one of the interesting future directions. Thank you very much for your question.