Min-Max Correlation Clustering via MultiCut

Correlation clustering is a fundamental combinatorial optimization problem arising in many contexts and applications that has been the subject of dozens of papers in the literature. In this problem we are given a general weighted graph where each edge is labeled positive or negative. The goal is to obtain a partitioning (clustering) of the vertices that minimizes disagreements – weight of negative edges trapped inside a cluster plus positive edges between different clusters. Most of the papers on this topic mainly focus on minimizing total disagreement, a global objective for this problem.

In this paper we study a cluster-wise objective function that asks to minimize the maximum number of disagreements of each cluster, which we call min-max correlation clustering. The min-max objective is a natural objective that respects the quality of every cluster. In this paper, we provide the first nontrivial approximation algorithm for this problem achieving an \(\mathcal {O}(\log n)\) approximation for general weighted graphs. To do so, we also obtain a corresponding result for multicut where we wish to find a multicut solution while trying to minimize the total weight of cut edges on every component. The results are then further improved to obtain an \(\mathcal {O}(r^2)\)-approximation for min-max correlation clustering and min-max multicut for graphs that exclude \(K_{r,r}\) minors.

1. 1.

   defined later.

We are grateful to Nikhil Bansal for useful discussions during a Dagstuhl workshop on scheduling (18101).

Authors and Affiliations

1. University of Maryland, College Park, College Park, USA

   Saba Ahmadi

2. Northwestern University, Evanston, USA

   Samir Khuller

3. College of Information and Computer Science, University of Massachussetts Amherst, Amherst, USA

   Barna Saha

Corresponding author

Correspondence to Saba Ahmadi .

Editors and Affiliations

1. École Polytechnique de Montréal, Montreal, QC, Canada

   Andrea Lodi

2. University of Michigan, Ann Arbor, MI, USA

   Viswanath Nagarajan

A Missing Proofs

1.1 A.1 Proof of Lemma 2

Proof

Consider a vertex u and let \(A_u = \{v: \left\| {\bar{u}-\bar{v}}\right\| ^2 \ge \beta \left\| {\bar{u}}\right\| ^2\}\) and \(B_u = \{v: \left\| {\bar{u}-\bar{v}}\right\| ^2 < \beta \left\| {\bar{u}}\right\| ^2\}\). Assume for now that \(u\in S\). We show with high probability \(\eta (A_u \cap S)\) is small, and \(\eta (B_u)\) is also small. Vertex u satisfies the spreading constraint. It is easy to see that:

Since \(\eta (V) = 1\) and \(A_u \cup B_u = V\), \(\eta (A_u)+\eta (B_u) = 1\), and \(\beta =1/2\) therefore:

Consider an arbitrary vertex \(v\in A_u\) where \(\left\| {\bar{v}}\right\| \ne 0\). By definition of \(A_u\), \(\left\| {\bar{u}-\bar{v}}\right\| ^2 \ge \beta \left\| {\bar{u}}\right\| ^2 \ge \beta \min \{\left\| {\bar{u}}\right\| ^2, \left\| {\bar{v}}\right\| ^2\}\). Therefore, by the second property of orthogonal separators and since we assumed \(u\in S\), then \(\Pr [v\in S \,\vert \,u \in S] \le \frac{1}{n^3} \le H\). The second inequality holds since \(H\ge 1/n\).

Now we show a bound for :

Now, we want to bound \(\Pr [\eta (S)\ge 12H\,\vert \,u\in S]\). The event \(\{\eta (S)\ge 12H\,\vert \,u\in S\}\) implies the event \(\{\eta (A_u\cap S)\ge 8H\,\vert \,u\in S\}\) since \(\eta (B_u\cap S)\le \eta (B_u)\le 4H\). (The second inequality holds by (12)). Now we are ready to complete the proof.

We showed \(\Pr [\eta (S)\ge 12H\,\vert \,u\in S]\le 1/8\), therefore \(\Pr [\eta (S)\le 12H\,\vert \,u\in S]\ge 7/8\) and the proof is complete.

1.2 A.2 Proof of Theorem 6

Proof

For an iteration t, let \(Y^t = \sum _{v\in V}y^t(v)\). Consider the optimal solution \(\{S_i^*\}_{i=1}^k\) to the min-max multicut problem. There exists at least a \(S_j^* \in \{S_i^*\}_{i=1}^k\) with weight greater than or equal to the average (\(y_t(S_j^*)\ge \frac{Y^t}{k}\)), \(vio(S_j^*)=0\), and \(\delta (S_j^*)\le OPT\). Therefore by Corollary 1 where \(H=\frac{1}{k}\), a set \(S_t = \{S_1,S_2,\cdots , S_j\}\) could be found where \(\forall S_i \in S_t\), \(\delta (S_i)\le \mathcal {O}(\log n)\cdot OPT\), \(\Pr [vio(S_i)\ge 1] \le 1/n\).

Now we show the second property of the theorem holds. Let \(\ell \) denote the number of iterations in the while loop. Let \(|\{S\in \mathcal {S}: v\in S\}| = N_v\). By the updating rules \(y^{\ell +1}(v) = 1/2^{N_v}\). Therefore \(\frac{1}{2^{N_v}} = y^{\ell +1}(v) \le 1/n\), which implies \(N_v \ge \log (n)\). By Corollary 1, \(y^t(S^t)\ge \frac{1}{\gamma k}Y^t\) where \(\gamma = \mathcal {O}(1)\). Therefore:

Which implies \(Y^{\ell } \le (1-\frac{1}{2\gamma k})^{\ell - 1}Y^1 = (1-\frac{1}{2\gamma k})^{\ell - 1}n\). Also \(Y^{\ell }>1/n\) therefore, \(\ell \le 1+4\gamma k\ln (n) \le 5\gamma k \log (n)\). In each iteration t, the number of sets in \(S_t\) is at most n (since all the sets in \(S_t\) are disjoint), therefore \(|\mathcal {S}|\le 5\gamma k n \log (n)\), and the second property is proved.

1.3 A.3 Proof of Theorem 7

Proof

A similar proof to the one given by Bansal et al. [4] shows after step 2, for each \(P_i\in \mathcal {P}\), \(\delta (P_i)\le 2B\). We start by analyzing Step 1. Observe that after Step 1, the collection of sets \(\{P_i\}\) is a partition of V and \(P_i\subseteq S_i\) for every i. Particularly, \(vio(P_i)\le vio(S_i)\). Note, however, that the bound \(\delta (P_i)\le B\) may be violated for some i since \(P_i\) might be a strict subset of \(S_i\).

We finish the analysis of Step 1 by proving that . Fix an \(i\le |\mathcal {S}|\) and estimate the expected weight of edges \(E(P_i, \cup _{j>i}P_j)\), given that the \(i^{th}\) set in the random ordering is S. If an edge (u, v) belongs to \(E(P_i, \cup _{j>i}P_j)\), then \((u,v)\in E(S_i, V\setminus S_i) = E(S,V\setminus S)\) and both \(u,v\notin \cup _{j<i} S_j\). For any edge \((u,v)\in \delta (S)\) (with \(u\in S, v\notin S\)), \(\Pr ((u,v)\in E(P_i,\cup _{j>i}P_j)\,\vert \,S_i = S)\le \Pr (v\notin \cup _{j<i}S_j\,\vert \,S_i = S)\le (1-\frac{c}{nk})^{i-1}\), since v is covered by at least \(\frac{c}{nk}\) fraction of sets in \(\mathcal {S}\) and is not covered by \(S_i = S\). Hence,

and . Therefore:

Now we want to analyze step 2. Consider potential function \(\sum _i \delta (P_i)\), we showed after step 1, . We prove that this potential function reduces quickly over the iterations of Step 2, thus, Step 2 terminates after a small number of steps. After each iteration of Step 2, the following invariant holds: the collection of sets \(\{P_i\}\) is a partition of V and \(P_i\subseteq S_i\) for all i. Particularly, \(vio(P_i)\le vio(S_i)\). Using an uncrossing argument, we show at every iteration of the while loop in step 2, \(\sum _i \delta (P_i)\) decreases by at least 2B.

The above inequalities use the facts that \(P_i\subseteq S_i\) for all i and that all the \(P_j\)’s are disjoint. The second inequality uses the facts that \(\sum _{j\ne i}w(E(P_j\setminus S_i,S_i)) = w(E(V\setminus S_i,S_i))\), and \(\sum _{j\ne i} w(E(S_i\setminus P_j,P_j)) \ge w(E(P_i,V\setminus P_i))\), which hold since the collection of sets \(\{P_i\}\) is a partition of V, and \(P_i\subseteq S_i\). In particular, \(\sum _{j\ne i} w(E(S_i\setminus P_j,P_j)) \ge w(E(P_i,V\setminus P_i))\) holds since for each edge e if \(e\in E(P_i,P_j)\) then \(e\in E(S_i\setminus P_j, P_j)\). The last inequality holds since \(\delta (S_i)\le B \) and \(\delta (P_i)>2B\).

This proves that the number of iterations of the while loop is polynomially bounded and after step 2, \(\delta (P_i)\le 2B\) for each \(P_i\).

In addition, since each \(P_i\) is a subset of \(S_i\), \(vio(P_i)\le vio(S_i)\). Therefore \(\Pr [vio(P_i)\ge 1] \le 1/n\).

Reprints and permissions

© 2019 Springer Nature Switzerland AG

Policies and ethics