Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering

In the MPC model, data is distributed across a set of machines, and computation proceeds in synchronous rounds. During each round, each machine first receives messages from other machines, then performs computations based on this information and its own allocated memory, and finally sends messages to other machines to be received at the start of the next round. Each machine has limited local memory, restricting the total number of messages it can receive or send in a round. The efficiency of the algorithm is measured by the number of rounds, the memory used by each machine, the total memory used by all machines, and the running time over all machines, also known as the total work.

In this paper, we consider the MPC model in the strictly sublinear regime: Each machine has $O(n^{\delta })$ local memory, where $n$ is the input size and $\delta >0$ is a constant that can be made arbitrarily small. Under this model, we assume the input received by each machine has size $O(n^{\delta })$.

We then describe the correlation clustering problem under the MPC model in the strictly sublinear regime. We use $n=|V|$ and $m=|E|$ to denote the number of vertices and edges respectively in the input graph $G=(V,E)$. The edges $E$ are distributed across the machines, where each machine has $O(n^{\delta })$ memory for a constant $\delta >0$ which can be made arbitrarily small. At the end of the algorithm, each machine needs to store in its local memory the IDs of the clusters for all the vertices incident to its assigned edges.

Our main result regarding MPC algorithm is given as follows,

In particular, the algorithm can be converted into a nearly linear time algorithm that with high probability outputs a $(63.3+O(ϵ))$-simultaneous approximation for all monotone symmetric norms.

Along the way, we develop an MPC rounding algorithm with a per-vertex $(5+55ϵ)$ approximation guarantee, based on the sequential algorithm due to [26]. Given its potential independent interest, we state it here for future references.

The $O({\log }^{3}n)$ round in the above theorem might not be desirable for many applications. Our next result shows that we can reduce the number of rounds to $O(1)$, albeit with a worse $O(1)$ approximation ratio:

Overall, relative to [21], our algorithms demonstrate the following improvements.

1. 1.

   We generalize the family of norms for the simultaneous approximation from ${\mathrm{\ell }}_p$ norms to all monotone symmetric norms.

2. 2.

   We obtain a simpler construction, which leads to a much smaller approximation ratio. Using a result from [11], to simultaneously approximate all monotone symmetric norms, it suffices to approximate all top-$k$ norms: the top-$k$ norm of a non-negative vector is the sum of its largest $k$ coordinates. Though being more general mathematically, the top-$k$ norms are more convenient to deal with compared to ${\mathrm{\ell }}_p$ norms.

3. 3.

   We can make our algorithm run in nearly linear time. This is the first nearly-linear time simultaneous $O(1)$-approximation algorithm for the problem, even when we restrict to ${\mathrm{\ell }}_p$ norms. In contrast, the algorithm of [21] runs in nearly linear time only when the graph $G$ has $O(1)$ maximum degree.

4. 4.

   We can make our algorithm run in the MPC model with $O(1)$ rounds. Our work is the first to consider the problem in the MPC model.

By [11], we can reduce the problem of approximating all monotone symmetric norms to approximating all top-$k$ norms. We then construct a fractional solution $x$, which is a metric over $V$ with range $[0,1]$, such that the fractional disagreement vector for $x$ has top-$k$ norm at most $12.66\cdot {\mathrm{opt}}_k$ for any $k\in [n]$, where ${\mathrm{opt}}_k$ is the cost of the optimum clustering under the top-$k$ norm. Then, we can use the 5-approximate rounding algorithm of KMZ [26], to obtain a simultaneous $63.3$-approximation for all top-$k$ norms. The KMZ rounding algorithm has two crucial properties that we need: it does not depend on $k$ and it achieves a per-vertex guarantee.

We elaborate more on how to construct the metric $x:\left(\genfrac{}{}{0pt}{}{V}{2}\right)\to [0,1]$. A natural idea to assign the LP values, that was used by [21], is to set $x_{uv}$ based on the intersection of the neighborhood between $u$ and $v$. Intuitively, the more common neighbors two nodes share, the closer they should be. A straightforward approach to implementing this idea is to set $x_{uv}=1-\frac{|N(u)\cap N(v)|}{\max (d(u),d(v))}$, where $N(u)$ denotes the neighboring nodes of $u$ in $G$ and $d(u)=|N(u)|$ denotes the degree of $u$; it is convenient to assume $u\in N(u)$. This approach works for the top-$1$ norm (i.e., the ${\mathrm{\ell }}_{\mathrm{\infty }}$ norm) as discussed in [20], but fails for the top-$n$ norm (i.e., the ${\mathrm{\ell }}_1$ norm). Consider a star graph, where the optimal clustering under the top-$n$ norm has a cost of $n-2$. This approach will assign $x_{uv}=1-\frac{1}{2}=1/2$ for all $-$edges, leading to an LP cost of $\mathrm{\Theta }(n^2)$ and a gap of $\mathrm{\Omega }(n)$. [21] addressed the issue by rounding up LP values to $1$ for $-$edge, if for a given node, its total $-$edges LP disagreement is larger than the number of its $+$edges. After the transformation, the triangle inequalities are only satisfied approximately, but this can be handled with $O(1)$ loss in the approximation ratio.

We address this issue using a different approach, that is inspired by the pre-clustering technique in [17]. We first preprocess the graph $G$ by removing edges $uv\in E$ for which $|N(u)\cap N(v)|$ is small compared to $\max \{d(u),d(v)\}$. Let the resulting graph be $H$. We then set our LP values as $x_{uv}=1-\frac{|N_H(u)\cap N_H(v)|}{\max \{d(u),d(v)\}}$ if $u\ne v$, where $N_H(u)$ is the set of neighbors of $u$ in $H$. We show that this solution is a $12.66$-approximation for all top-$k$ norms simultaneously. When compared to [21], in addition to the improved approximation ratio, we obtain a considerably simpler analysis.

We then proceed to discuss our techniques to improve the running time of the algorithm to nearly-linear. The algorithm contains two parts: the construction of the fractional solution $x$ and the rounding procedure. We discuss the two procedures separately.

Constructing $x$ in nearly linear time poses several challenges. First, the construction of the subgraph $H$ requires us to identify edges $uv\in E$ with small $|N(u)\cap N(v)|$. Second, we can not explicitly assign $x$ values to all $-$edges. Finally, to compute $x_{uv}$, we need to compute $|N_H(u)\cap N_H(v)|$.

The first and third challenges can be addressed through sampling, with an $O(\log n)$ factor loss in the running time. To avoid considering too many $-$edges, we only consider $-$edges with length at most $1-ϵ$. Consequently, we only need to consider $-$edges whose other endpoints share at least an $ϵ$ fraction of neighbors with $u$. Given that each neighbor of $u$ in $H$ has degree similar to $u$, we demonstrate that there will be at most $O(d(u)/ϵ)$ $-$edges to consider for each node $u$. Overall, there will be $\tilde{O}(m\cdot \mathrm{poly}(1/ϵ))$ $-$edges for which we need to explicitly assign $x$ values. Moreover, the nearly-linear time algorithm for the construction of $x$ can be naturally implemented in the MPC model, with $O(1)$ number of rounds.

Then we proceed to the rounding algorithm for $x$. We are explicitly given the $x$ values for $+$edges, and for nearly-linear number of $-$edges. For other $-$edges, their $x$ values are $1$. The KMZ algorithm works as follows: in each round, the algorithm selects a node $u$ as the cluster center and then includes a ball with some radius, meaning the algorithm includes all nodes $v$ such that $x_{uv}\le \text{radius}$ into the cluster, removes the clustered nodes, and repeats the process on the remaining nodes. The rounding algorithm can be easily implemented in nearly-linear time using a priority queue structure. This leads to a nearly-linear time simultaneous $O(1)$-approximation for correlation clustering for all monotone symmetric norms.

The challenge to implement the algorithm in MPC model is the sequential nature of the algorithm. [26] observes that in each round, if we select the nodes that maximize $L(u)={\sum }_{x_{uv}\le r}(r-x_{uv})$ as cluster center, we can effectively bound each node’s algorithmic cost, where $r$ is the final ratio. However, choosing a node that maximizes some target inherently makes the process sequential. Our key observation is that, instead of selecting the node that maximizes $L(u)$, we can allow some approximation. This strategy still permits achieving a reasonable approximate ratio with an additional $1+ϵ$ overhead while allowing the selection of multiple nodes as cluster centers, thereby parallelizing the rounding process. In each round, there might be several candidate cluster centers with conflicts. To resolve these conflicts, we employ the classical Luby’s algorithm [27, 16] to find a maximal independent set, ensuring that none of the cluster centers have conflicts.

We give some preliminary remarks in Section 2. In Section 3, we describe our simultaneous $O(1)$-approximation algorithm for correlation clustering for all top-$k$ norms. The reduction from any monotone symmetric norm to top-$k$ norms is deferred to Appendix A. Combining the results leads to a simultaneous $O(1)$-approximation algorithm for all monotone symmetric norms. Then in Appendix B and C, we show how we can run the algorithm in the MPC model with nearly linear work. In particular, Appendix B and C discuss how to solve the LP and round the LP solution in the MPC model, respectively. The constant round MPC algorithm is described in Appendix D. Theorem 2, 3, 4 and 5 are proved in Section 3, Appendix C, C and D respectively.

Once we obtain Lemma 9, [26] provides a rounding algorithm for any feasible solution. Assume the final clustering is ${𝒞}_{\text{KMZ}}$. [26] ensures that for any node $u$, we have ${\mathrm{cost}}_{{𝒞}_{\text{KMZ}}}(u)\le 5\mathrm{c}\mathrm{o}\mathrm{s}{\mathrm{t}}_x(u)$, meaning the disagreement for ${𝒞}_{\text{KMZ}}$ is at most 5 times the disagreement in the LP solution. We can apply the KMZ rounding algorithm to $x_{uv}$ as output by Lemma 9. For any integer $k\in [n]$, let $U^{\prime }$ be the set of $k$ vertices with the largest disagreement values with respect to ${𝒞}_{\text{KMZ}}$. Then we have:

By Lemma 6, we know that ${𝒞}_{\text{KMZ}}$ is a simultaneous 63.3-approximate clustering for all monotone symmetric norms. $◀$

We will first show that our $x$ is feasible in Section 3.2, then we will bound the approximate ratio in Section 3.3.

We can assume $u,v,w$ are distinct since otherwise the inequality holds trivially. We assume that $d(v)\ge d(w)$ wlog.

The first inequality used that $d(v)\le M_{uv}$, the second one follows from $|N_H(u)\cap N_H(v)|-|N_H(v)\cap N_H(w)|\le |(N_H(u)\cap N_H(v))\setminus (N_H(v)\cap N_H(w))|=|(N_H(v)\cap (N_H(u)\setminus N_H(w))|\le |N_H(u)\setminus N_H(w)|$, and the third one used $d(u)\le M_{uv}$ and $d(u)\le M_{uw}$. $◀$

We fix the integer $k\in [n]$. Let $𝒞$ be the clustering that minimizes the top-$k$ norm of disagreement vector, but our analysis works for any clustering. For every $v\in V$, let $C(v)$ be the cluster in $𝒞$ that contains $v$.

For every $u\in V$, let ${\mathrm{cost}}_{𝒞}^{+}(u),{\mathrm{cost}}_{𝒞}^{-}(u)$ and ${\mathrm{cost}}_{𝒞}(u)$ respectively be the number of $+$edges, $-$edges and edges incident to $u$ that are in disagreement in the clustering $𝒞$. Recall ${\mathrm{cost}}_{𝒞}^k={\max }_{S\subseteq V:|S|=k}{\sum }_{u\in S}{\mathrm{cost}}_{𝒞}(u)$ is the top-$k$ norm cost of the clustering $𝒞$, thus we have ${\mathrm{opt}}^k={\mathrm{cost}}_{𝒞}^k$.

Let $U$ be the set of $k$ vertices $u$ with the largest ${\mathrm{cost}}_x(u)$ values. So, ${\mathrm{cost}}_x^k={\sum }_{u\in U}{\mathrm{cost}}_x(u)$. In order to provide a clear demonstration, we divide all of the edges in $G$ into five parts. First, we separate out the parts that are easily constrained by ${\mathrm{cost}}_{𝒞}^k$. Let ${\phi }_1^{+}$ be the set of $+$edges that are cut in $𝒞$, and ${\phi }_1^{-}$ be the set of $-$edges that are not cut in $𝒞$. For the remaining $+$edges in $E$ that are not cut in $𝒞$, it is necessary to utilize the properties of $+$edges in $E_H$. To this end, let ${\phi }_2^{+}$ be the set of $+$edges in $E\setminus E_H$ that are not cut in $𝒞$, and ${\phi }_3^{+}$ be the set of $+$edges in $E_H$ that are not cut in $𝒞$. Finally, we define ${\phi }_2^{-}$ as the set of $-$edges that are cut in $𝒞$. Formally, we set

For every $(i,j)\in \{(1,+),(2,+),(3,+),(1,-),(2,-)\}$ and $u\in V$, we let ${\phi }_i^j(u)$ be the set of pairs in ${\phi }_i^j$ incident to $u$. Notice that ${\phi }_3^{+}$ contains all the self-loops. We use ${\varphi }_i^j(u)=\{v:uv\in {\phi }_i^j(u)\}$ to denote the end-vertices of the edges in ${\phi }_i^j(u)$ other than $u$; so $|{\varphi }_i^j(u)|=|{\phi }_i^j(u)|$. We let $y_i^j(u)$ denote the cost of edges in ${\phi }_i^j(u)$ in the solution $x$. For every $(i,j)\in \{(1,+),(2,+),(3,+),(1,-),(2,-)\}$, we define $f_i^j={\sum }_{u\in U}{y}_i^j(u)$. Therefore, the top-$k$ norm cost of $x$ is $f_1^{+}+f_2^{+}+f_3^{+}+f_1^{-}+f_2^{-}$.

With the notations defined, we can proceed to the analysis. Prior to this, several propositions are presented, which will prove useful in the following analysis. We start with the property of edges in $E\setminus E_H$.

Since $C(u)=C(v)$, there are at least $|N(u)\mathrm{\Delta }N(v)|$ disagreements incident to $u$ and $v$. For every $uv\in {\phi }_2^{+}$, we have ${\mathrm{cost}}_{𝒞}(u)+{\mathrm{cost}}_{𝒞}(v)\ge |N(u)\mathrm{\Delta }N(v)|\ge \beta \cdot M_{uv}.$ $◀$

Then, we show that edges in $E_H$ have similar degrees.

For every $uv\in E_H$, we have $|N(u)\mathrm{\Delta }N(v)|\le \beta \cdot M_{uv}$. Therefore,

which gives us $(1-\beta )\cdot d(v)\le d(u)\le \frac{1}{1-\beta }\cdot d(v)$ since $\beta \in (0,1)$. $◀$

As we are about to analyze the top-$k$ norm objective, we can bound the cost in the solution $x$ using coefficients of ${\mathrm{cost}}_{𝒞}$. This key observation can be formally demonstrated as follows:

We have ${|c/\alpha |}_1\le k$ and ${|c/\alpha |}_{\mathrm{\infty }}\le 1$. It is well known that $c/\alpha$ is a convex combination of $\{0,1\}$-vectors, each of which has at most $k$ 1’s. For each $\{0,1\}$-vector $d$ in the combination, we have ${\sum }_{r\in V}d(r){\mathrm{cost}}_{𝒞}(r)\le {\mathrm{cost}}_{𝒞}^k$. Taking the convex combination of these inequalities gives ${\sum }_{r\in V}\frac{c(r)}{\alpha }\cdot {\mathrm{cost}}_{𝒞}(r)\le {\mathrm{cost}}_{𝒞}^k$, which is equivalent to the inequality in the claim. $\mathrm{⊲}$

From the definitions of $f_1^{+}$ and $f_1^{-}$, we can see that it can be constrained by ${\mathrm{cost}}_{𝒞}^k$.

$\mathrm{⊲}$

To bound the cost of the remaining $+$edges, we separately analyze the cost coefficients of vertices in $f_2^{+}$ and $f_3^{+}$.

We bound $f_2^{+}$ as follows:

The second inequality used Lemma 11. Therefore, Lemma 15(a) holds.

To show Lemma 15(b), we bound the coefficients for ${\mathrm{cost}}_{𝒞}(u)$ and ${\mathrm{cost}}_{𝒞}(v)$ respectively. If $u\in U$, the coefficient for ${\mathrm{cost}}_{𝒞}(u)$ is ${\sum }_{uv\in {\phi }_2^{+}}\frac{1}{\beta \cdot M_{uv}}\le \frac{|{\phi }_2^{+}(u)|}{\beta \cdot d(u)}$; if $u\notin U$, the coefficient is $0$. The coefficient for ${\mathrm{cost}}_{𝒞}(v)$ is ${\sum }_{u\in U\cap {\varphi }_2^{+}(v)}\frac{1}{\beta \cdot M_{uv}}\le \frac{|{\phi }_2^{+}(v)|}{\beta \cdot d(v)}$. Therefore, $c_2^{+}(r)\le \frac{2\cdot |{\phi }_2^{+}(r)|}{\beta \cdot d(r)}$.

To bound ${|c_2^{+}|}_1$, we can replace ${\mathrm{cost}}_{𝒞}(u)$ and ${\mathrm{cost}}_{𝒞}(v)$ with 1.

Then ${|c_2^{+}|}_1={\sum }_{u\in U,uv\in {\phi }_2^{+}}\frac{2}{\beta \cdot M_{uv}}\le \frac{2}{\beta }{\sum }_{u\in U}\frac{|{\phi }_2^{+}(u)|}{d(u)}$. This proves Lemma 15(c). $◀$

Following the analysis of the cost coefficients $c_2^{+}$ of $f_2^{+}$, we analyze the cost coefficients of $f_3^{+}$ in edge set $E_H$.

Fix some $uv\in {\phi }_3^{+}\subseteq E_H$ with $u\ne v$. We let $\tilde{u}=\arg {\max }_{w\in \{u,v\}}d(w)$, and $\tilde{v}$ be the other vertex in $\{u,v\}$. Notice that $d(\tilde{u})=M_{uv}$. Then we have

We prove the first inequality in sequence (3). Notice $N_H(\tilde{u})\supseteq {\varphi }_3^{+}(\tilde{u})$. Therefore,