Robust Correlation Clustering Problem with Locally Bounded Disagreements

In this subsection, we analyze the number of disagreements generated by positive cut edges at each vertex $q\in C_{q_i^{*}},i\in [m]$ .

Lemma 2 For each vertex $q\in C_{q_i^{*}},i\in [m]$ , the number of positive cut edge $(p,q),p\in M_i(q)\cup D_j(q),j\in [i-1]$ , is no more than

$$\frac{7}{1-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{+}\\ p\in M_i(q)\cup D_j(q)\\ j\in [i-1]\end{array}}{\sum }}{Z}_{pq}^{*}.$$

Proof From the construction of sets $D_j,j\in [i-1]$ , and $M_i(q)$ , for each cut edge $(p,q)\in E^{+},p\in M_i(q)\cup D_j(q),j\in [i-1]$ , we have

$$X_{pq}^{*}⩾\frac{1}{7}.$$

Moreover, from Property 1-(3), we can obtain

$$Z_{pq}^{*}⩾X_{pq}^{*}-2\delta ⩾\frac{1}{7}-2\delta ,$$

which indicates that the disagreement generated by $(p,q)$ is no more than

$$\frac{7}{1-14\delta }{Z}_{pq}^{*}.$$

We sum all the $p\in M_i(q)\cup D_j(q),j\in [i-1]$ , and we have that the number of positive cut edge $(p,q),p\in M_i(q)\cup D_j(q),j\in [i-1]$ is no more than

$$\frac{7}{1-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{+}\\ p\in M_i(q)\cup D_j(q)\\ j\in [i-1]\end{array}}{\sum }}{Z}_{pq}^{*}.$$

The lemma is concluded.

■

Lemma 3 For each vertex $q\in C_{q_i^{*}},i\in [m]$ , the number of positive cut edge $(p,q),p\in A_j(q)\cup B_j(q),j\in [i-1]$ is no more than

$${\displaystyle \underset{\begin{array}{l}(p,q)\in E^{+}\\ p\in A_j(q)\\ j\in [i-1]\end{array}}{\sum }}\frac{7}{1-7\delta }{Z}_{pq}^{*}+{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_j(q)\\ j\in [i-1]\end{array}}{\sum }}\frac{7}{2-14\delta }{Z}_{pq}^{*}.$$

Proof Given a vertex $q\in C_{q_i^{*}},i\in [m]$ and any $j\in [i-1]$ , for each positive edge $(p,q),p\in A_j(q)$ , from Property 1-(3) we receive that

$$\begin{array}{lll}{Z}_{pq}^{*}\hfill & ⩾\hfill & X_{pq}^{*}-2\delta ⩾\hfill \\ \hfill & \hfill & X_{q{q}_j^{*}}^{*}-X_{p{q}_j^{*}}^{*}-2\delta ⩾\hfill \\ \hfill & \hfill & \frac{2}{7}-2\delta .\hfill \end{array}$$

Moreover, for each negative edge $(p,q),p\in A_j(q)$ , from Property 1-(4) we achieve that

$$\begin{array}{lll}{Z}_{pq}^{*}\hfill & ⩾\hfill & 1-X_{pq}^{*}-2\delta ⩾\hfill \\ \hfill & \hfill & 1-\left(X_{p{q}_j^{*}}^{*}+X_{w{q}_j^{*}}^{*}+X_{qw}^{*}\right)-2\delta ⩾\hfill \\ \hfill & \hfill & 1-\left(\frac{1}{7}+\frac{3}{7}+\frac{1}{7}\right)-2\delta =\frac{2}{7}-2\delta ,\hfill \end{array}$$

where $w$ is any vertex in set $B_j(q)$ .

From Line $8$ of Algorithm 1, we have that

$$|B_j(q)|⩽|C_q^{*}(j)|⩽|A_j(q)|.$$

Then, the number of positive cut edge $(p,q),p\in A_j(q)\cup B_j(q)$ equals $|\{(p,q)\in E^{+}:A_j(q)\cup B_j(q)\}|$ and it is no more than

$$\begin{array}{l}\left|\right\{(p,q)\in E:p\in A_j(q)\left\}\right|+\\ \{(p,q)\in E^{+}:p\in A_j(q)\}|=\\ 2\left|\right\{(p,q)\in E^{+}:p\in A_j(q)\left\}\right|+\\ \left|\right\{(p,q)\in E^{-}:p\in A_j(q)\left\}\right|.\end{array}$$

Above all, we get

$$\begin{array}{l}\left|\right\{(p,q)\in E^{+}:p\in A_j(q)\cup B_j(q)\left\}\right|⩽\\ 2\left|\right\{(p,q)\in E^{+}:p\in A_j(q)\left\}\right|+\\ \left|\right\{(p,q)\in E^{-}:p\in A_j(q)\left\}\right|⩽\\ 2{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{+}\\ p\in A_j(q)\end{array}}{\sum }}\frac{7}{2-14\delta }{Z}_{pq}^{*}+\\ {\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_j(q)\end{array}}{\sum }}\frac{7}{2-14\delta }{Z}_{pq}^{*}⩽\\ {\displaystyle \underset{\begin{array}{l}(p,q)\in E^{+}\\ p\in A_j(q)\end{array}}{\sum }}\frac{7}{1-7\delta }{Z}_{pq}^{*}+\\ {\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_j(q)\end{array}}{\sum }}\frac{7}{2-14\delta }{Z}_{pq}^{*}.\end{array}$$

Therefore, we have

$$\begin{array}{l}\left|\right\{(p\mathrm{,}q)\in E^{+}:p\in A_j(q)\cup B_j(q),j\in [i-1]\left\}\right|⩽\\ {\displaystyle \underset{\begin{array}{l}6(p\mathrm{,}q)\in E^{+}\\ p\in A_j(q)\\ j\in [i-1]\end{array}}{\sum }}\frac{7}{1-7\delta }{Z}_{pq}^{*}+\\ {\displaystyle \underset{\begin{array}{l}6(p\mathrm{,}q)\in E^{-}\\ p\in A_j(q)\\ j\in [i-1]\end{array}}{\sum }}\frac{7}{2-14\delta }{Z}_{pq}^{*}\mathrm{.}\end{array}$$

The lemma is concluded.

■

Lemma 4 For each vertex $q\in C_{q_i^{*}},i\in [m]$ , the number of positive cut edges $(p,q),p\in F_i(q)$ , is no more than

$${\displaystyle \underset{\begin{array}{l}(p,q)\in E^{+}\\ p\in A_i(q)\end{array}}{\sum }}\frac{7}{1-14\delta }{Z}_{pq}^{*}+{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_i(q)\end{array}}{\sum }}\frac{7}{3-14\delta }{Z}_{pq}^{*}.$$

Proof From Line $8$ of Algorithm 1, we receive that

$$|F_i(q)|⩽|C_q^{*}(i)|⩽|A_i(q)|.$$

Therefore, we have

$$\begin{array}{l}\left|\right\{(p,q)\in E^{+}:p\in F_i(q)\left\}\right|⩽\\ \left|\right\{(p,q)\in E^{+}:p\in A_i(q)\left\}\right|+\\ \left|\right\{(p,q)\in E^{-}:p\in A_i(q)\left\}\right|.\end{array}$$

Similar to Lemma 3, we only need to analyze the lower bound of $Z_{pq}^{*}$ for each edge $(p,q),p\in A_i(q)$ .

For each positive edge $(p,q)\in E^{+}$ with $q\in A_i(q)$ , from Property 1-(3) and the first constraint of Formula ( 2 ), we can get

$$\begin{array}{lll}{Z}_{pq}^{*}\hfill & ⩾\hfill & X_{pq}^{*}-2\delta ⩾\hfill \\ \hfill & \hfill & X_{q_i^{*}w}^{*}-X_{p{q}_i^{*}}^{*}-X_{qw}^{*}-2\delta ⩾\hfill \\ \hfill & \hfill & \frac{3}{7}-\frac{1}{7}-\frac{1}{7}-2\delta =\frac{1}{7}-2\delta ,\hfill \end{array}$$

where $w$ is any vertex in set $F_i(q)$ .

Moreover, from Property 1-(4) and the first constraint of Formula ( 2 ), for each $(p,q)\in E^{-}$ with $p\in A_i(q)$ , we achieve

(3) $$\begin{array}{lll}{Z}_{pq}^{*}\hfill & ⩾\hfill & 1-X_{pq}^{*}-2\delta ⩾\hfill \\ \hfill & \hfill & 1-\left(X_{q{q}_i^{*}}^{*}+X_{p{q}_i^{*}}^{*}\right)-2\delta ⩾\hfill \\ \hfill & \hfill & 1-\left(\frac{3}{7}+\frac{1}{7}\right)-2\delta =\frac{3}{7}-2\delta \hfill \end{array}$$

Above all, we obtain that

$$\begin{array}{l}\left|\right\{(p,q)\in E^{+}:p\in F_i(q)\left\}\right|⩽\\ \left|\right\{(p,q)\in E^{+}:p\in A_i(q)\left\}\right|+\\ \left|\right\{(p,q)\in E^{-}:p\in A_i(q)\left\}\right|⩽\\ {\displaystyle \underset{\begin{array}{l}(p,q)\in E^{+}\\ p\in A_i(q)\end{array}}{\sum }}\frac{7}{1-14\delta }{Z}_{pq}^{*}+\\ {\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_i(q)\end{array}}{\sum }}\frac{7}{3-14\delta }{Z}_{pq}^{*}.\end{array}$$

The lemma is concluded.

■

In this subsection, we analyze the number of negative non-cut edges for each vertex $q\in C_{q_i^{*}},i\in [m]$ .

Lemma 5 For each vertex $q\in C_{q_i^{*}},i\in [m]$ , the number of negative edges $(p,q),p\in C_{q_i^{*}}$ , is no more than

$$\begin{array}{l}{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in D_i(q)\end{array}}{\sum }}\frac{7}{1-14\delta }{Z}_{pq}^{*}+\\ {\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_i(q)\end{array}}{\sum }}\frac{7}{3-14\delta }{Z}_{pq}^{*}.\end{array}$$

Proof From Property 1-(4) and the first constraint of Formula ( 2 ), for each $(p,q)\in E^{-},p\in D_i(q)$ , we have

(4) $$\begin{array}{lll}{Z}_{pq}^{*}\hfill & ⩾\hfill & 1-X_{pq}^{*}-2\delta ⩾\hfill \\ \hfill & \hfill & 1-X_{q{q}_i^{*}}^{*}-X_{p{q}_i^{*}}^{*}-2\delta ⩾\hfill \\ \hfill & \hfill & \frac{1}{7}-2\delta \hfill \end{array}$$

Combining Formulas ( 3 ) and ( 4 ), we have

$$\begin{array}{l}{\text{dis}}_q^{-}(\mathcal{C},V\backslash O)⩽\\ {\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in D_i(q)\end{array}}{\sum }}\frac{7}{1-14\delta }{Z}_{pq}^{*}+\\ {\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_i(q)\end{array}}{\sum }}\frac{7}{3-14\delta }{Z}_{pq}^{*}.\end{array}$$

The lemma is concluded.

■

From Lemmas 2–5, we can obtain the upper bound of disagreements generated by each vertex.

Lemma 6 For each vertex $q\in C_{q_i^{*}},i\in [m]$ , we have

$${\text{dis}}_q(\mathcal{C},V\backslash O)⩽\frac{7}{1-14\delta }{\displaystyle \underset{(p,q)\in E}{\sum }}{Z}_{pq}^{*}.$$

Proof For each vertex $q\in C_{q_i^{*}},i\in [m]$ , from Lemmas 2–4, we have

(5) $$\begin{array}{l}{\text{dis}}_q^{+}(\mathcal{C}\mathrm{,}V\backslash O)=\\ \left|\right\{(p\mathrm{,}q)\in E^{+}:p\in M_i(q),j\in [i-1]\left\}\right|+\\ \left|\right\{(p\mathrm{,}q)\in E^{+}:p\in D_j(q),j\in [i-1]\left\}\right|+\\ \left|\right\{(p\mathrm{,}q)\in E^{+}:p\in A_j(q),j\in [i-1]\left\}\right|+\\ \left|\right\{(p\mathrm{,}q)\in E^{+}:p\in B_j(q),j\in [i-1]\left\}\right|+\\ \left|\right\{(p\mathrm{,}q)\in E^{+}:p\in F_i(q)\left\}\right|⩽\end{array}$$ $$\begin{array}{l}\frac{7}{1-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{+}\\ p\in M_i(q)\cup D_j(q)\\ j\in [i-1]\end{array}}{\sum }}{Z}_{pq}^{*}+\\ \frac{7}{1-7\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{+}\\ p\in A_j(q)\\ j\in [i-1]\end{array}}{\sum }}{Z}_{pq}^{*}+\\ \frac{7}{2-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_j(q)\\ j\in [i-1]\end{array}}{\sum }}{Z}_{pq}^{*}+\\ \frac{7}{1-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{+}\\ p\in A_i(q)\end{array}}{\sum }}{Z}_{pq}^{*}+\end{array}$$ $$\begin{array}{l}\frac{7}{3-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_i(q)\end{array}}{\sum }}{Z}_{pq}^{*}⩽\\ \frac{7}{1-14\delta }{\displaystyle \underset{(p,q)\in E^{+}}{\sum }}{Z}_{pq}^{*}+\\ \frac{7}{2-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_j(q)\\ j\in [i-1]\end{array}}{\sum }}{Z}_{pq}^{*}+\\ \frac{7}{3-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_i(q)\end{array}}{\sum }}{Z}_{pq}^{*}\end{array}$$

Combining Lemma 5 and Formula ( 5 ), we can get

$$\begin{array}{l}{\text{dis}}_q(\mathcal{C},V\backslash O)=\\ {\text{dis}}_q^{+}(\mathcal{C},V\backslash O)+\text{d}i{s}_q^{+}(\mathcal{C},V\backslash O)⩽\\ \frac{7}{1-14\delta }{\displaystyle \underset{(p,q)\in E^{+}}{\sum }}{Z}_{pq}^{*}+\\ \frac{7}{2-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_j(q)\\ j\in [i-1]\end{array}}{\sum }}{Z}_{pq}^{*}+\\ \frac{14}{3-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in A_i(q)\end{array}}{\sum }}{Z}_{pq}^{*}+\\ \frac{7}{1-14\delta }{\displaystyle \underset{\begin{array}{l}(p,q)\in E^{-}\\ p\in D_i(q)\end{array}}{\sum }}{Z}_{pq}^{*}⩽\\ \frac{7}{1-14\delta }{\displaystyle \underset{(p,q)\in E}{\sum }}{Z}_{pq}^{*}.\end{array}$$

The lemma is concluded.

■

From Lemmas 1 and 6, we can obtain Theorem 1.

Theorem 1 For each instance $ℐ=\{G=(V,E),r\}$ of the min-max disagreements with outliers, Algorithm 1 can return a set $O$ with $|O|⩽r/\delta$ as well as a clustering of $V\backslash O$ , such that

$$\begin{array}{l}\underset{q\in V\backslash O}{{\displaystyle \max }}{\text{dis}}_q(\mathcal{C}\mathrm{,}V\backslash O)⩽\\ \frac{7}{1-14\delta }\underset{q\in V\backslash O^{*}}{{\displaystyle \max }}{\text{dis}}_q({\mathcal{C}}^{*}\mathrm{,}V\backslash O^{*}),\end{array}$$

where $O^{*}$ and ${𝒞}^{*}$ are the set of outliers and the clustering of non-outliers returned by the optimal algorithm, respectively.