Online Correlation Clustering: Simultaneously Optimizing All ${\mathbf{\ell }}_{𝒑}$-Norms

We answer the above questions affirmatively, showing that in the AOS model, there is an algorithm that is locally fair (${\mathrm{\ell }}_{\mathrm{\infty }}$-norm) without sacrificing global efficiency (${\mathrm{\ell }}_1$-norm), and that our guarantees are nearly best possible for both norms. Moreover, we obtain a robustness guarantee for all norms in between, thus translating the offline all-norms guarantee into the online world.

Let ${\text{OPT}}_p$ denote the cost of an optimal clustering for the ${\mathrm{\ell }}_p$-norm objective. We assume in the AOS model that an adversary fixes the online input. However, we see upfront a random sample $S$ of $\epsilon n$ nodes and the induced subgraph $G[S]$, where each node is sampled uniformly and independently into $S$ with probability $\epsilon$. The parameter can be anything in our upper bound results (Theorem 1), and as small as $n^{-1/4}$ in our lower bound results (Theorem 2).

Complementing our upper bounds, we show that the competitive ratios of our algorithm are nearly optimal for the ${\mathrm{\ell }}_1$- and ${\mathrm{\ell }}_{\mathrm{\infty }}$- norms. In particular, the logarithmic factor for the ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm and a dependence on $1/\epsilon$ for the ${\mathrm{\ell }}_1$- and ${\mathrm{\ell }}_{\mathrm{\infty }}$- norms are necessary. While the lower bound for the ${\mathrm{\ell }}_1$-norm is known [37], we contribute the new lower bound for the ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm.

Finally, we give a hardness result for the ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm in the RO model, justifying our focus on the AOS model.

This result establishes a fundamental separation between the ${\mathrm{\ell }}_1$- and ${\mathrm{\ell }}_{\mathrm{\infty }}$- norm objectives in the RO model, where an $O(1)$-competitive ratio for the ${\mathrm{\ell }}_1$-norm trivially follows from the Pivot algorithm. Recent work [27] shows that for a general class of minimization problems (called augmentable integer programs), there is a reduction from the AOS model to the RO model with loss of a factor at most $1/\epsilon$ in the competitive ratio, i.e., if there is an algorithm with competitive ratio $\mathrm{\Delta }$ in the RO model, then there is an algorithm with competitive ratio $\mathrm{\Delta }/\epsilon$ in the AOS model. In contrast, ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm correlation clustering is an example of a minimization problem where the AOS model is actually much stronger at breaking through worst-case instances than the RO model. Thus in this regard, ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm correlation clustering is more similar to online Steiner tree, where the AOS model can achieve competitive ratio $O(\log (1/\epsilon ))$, even though the RO model has a lower bound of $\mathrm{\Omega }(\log n)$.

Our primary challenge is to adapt an offline algorithm that requires complete, global knowledge of the graph to an online setting with limited information. The offline algorithm for all-norms correlation clustering due to Davies, Moseley and Newman [22] relies on two offline-only steps. Step (1) is to compute a semi-metric $d^{\ast }$ over all vertex pairs; $d^{\ast }$ is an (almost) feasible solution to the canonical convex relaxation for the problem, but can be computed using explicit combinatorial properties of the graph. Step (2) is to, in place of an optimal solution $x^{\ast }$ to the relaxation, feed $d^{\ast }$ into the convex program rounding algorithm by Kalhan, Makarychev, and Zhou [32] (from now on, the KMZ algorithm). This is a ball-cutting procedure that iteratively cuts out clusters based on “suggestions” from $d^{\ast }$ (i.e., if $d_{uv}^{\ast }$ is small, then nodes $u$ and $v$ “want” to be clustered together). As in Step (1), the whole graph is required to determine the order in which clusters are cut out. So, both steps require significant changes in order to be adapted to the online setting.

To replace step (1), we compute a semi-metric $\tilde{d}$, only using the sample $S$, as a proxy for $d^{\ast }$. This will imply that when a node $v$ arrives online, its distances ${\tilde{d}}_{uv}$ can immediately be computed for all $u$ that have already arrived. To replace step (2), we note that the offline all-norms result holds (up to constants) when $d^{\ast }$ is fed into any constant-approximate convex program rounding algorithm. We adapt the offline rounding algorithm of Charikar, Gupta, and Schwartz [16] (from now on, the CGS algorithm) instead of the KMZ algorithm, as we find the former easier to adapt to our online setting. The CGS algorithm is as follows: choose the unclustered node $v$ that has the most unclustered vertices in the ball of radius $r$ around it, then let $v$ and all unclustered nodes in its ball of radius $3r$ form a new cluster (where the balls are w.r.t the semi-metric that is the solution to the convex program). Notably, the algorithm is dynamic in that the sizes of the balls changes at each iteration, because nodes are removed when they are clustered.

We next discuss some of the main technical challenges to computing a semi-metric based on the offline sample $S$, developing an online algorithm for ${\mathrm{\ell }}_p$-norm correlation clustering, and analyzing our algorithm.

In Section 2, we discuss the AOS model and define the correlation metric and adjusted correlation metric. In Section 3, we define Algorithm 1, whose output satisfies Theorem 1. We prove item 2 of Theorem 1 (the statement for all finite $p$) in Section 4, though many proofs of lemmas and constructions stated are deferred to the full version of the paper. The proofs of items 1 and 3 of Theorem 1, and the lower bound results, Theorems 2 and 3, can be found in the full version.

In the AOS model, an adversary fixes the online input, then we are given a sample $S$, where each element of the universe $V$ is in $S$ independently with probability $\epsilon >0$. We assume $\epsilon$ is known.⁶⁶6One can immediately remove this assumption if we consider an “online-with-samples” model, suggested in the next footnote. So for our problem, we see the induced subgraph on $S$ a priori.

We will estimate various quantities using the sample $S$, and, for the analysis to be tractable, these estimations should not be correlated with each other. To this end, we show how to “split” the sample $S$ into four independent subsamples $S_p,S_d,S_b,S_r$ (where vertices in $S$ may be in more than one subsample). We define this notion formally in the full version of the paper, but it will suffice to think of these subsamples as having the same joint distribution as four random subsets of vertices, each obtained by taking a uniformly random sample of (expected) size $\mathrm{\Theta }({\epsilon }^{2}n)$, and repeating this procedure independently four times.⁷⁷7Alternatively, one could consider a type of “online-with-samples” model, where an algorithm is given access to a constant number $k$ of independent random samples of size ${\epsilon }_i\cdot n$ of $V$, where ${\sum }_{i\in [k]}{\epsilon }_i=\epsilon$. We find this to be a perfectly reasonable model; the reader may find it simpler to assume this model.

Since the four samples are constructed from $S$, edges in the (complete) subgraph induced by $S_d\cup S_p\cup S_b\cup S_r$ are known to the online algorithm a priori. Then, the remaining vertices arrive one by one in adversarial order. When a vertex arrives, it reveals the signs of its incident edges to all vertices that have previously arrived (including all of $S$), and it must be irrevocably assigned a cluster.

We define $q(\epsilon ):=\mathbb{P}[v\in S_i]={\epsilon }^2/2$ for any subsample $S_i\in \{S_d,S_p,S_b,S_r\}$.

The correlation metric is a near-optimal feasible solution to the canonical convex program⁸⁸8See [22] for more details on this convex program which, while motivating, is not necessary for understanding the work herein. for ${\mathrm{\ell }}_p$-norm correlation clustering. The correlation metric $d$ is feasible for this convex program, meaning here that it satisfies the triangle inequality. So we may think of $d_{uv}$ as specifying a distance between $u$ and $v$, where the smaller the distance, the more that $u$ and $v$ would like to be clustered together. Relevant theorems on the (adjusted) correlation metric from [21, 22] are in the full version.

Below, we generalize the definition of the correlation metric by defining it on a subgraph of $G$. Taking $U=V$ below recovers the correlation metric in [21].

The correlation metric distances are near-optimal for the convex program with the ${\mathrm{\ell }}_{\mathrm{\infty }}$-norm objective, but the metric must be adjusted in order to be simultaneously near-optimal for all ${\mathrm{\ell }}_p$-norms. We likewise generalize the definition of the so-called adjusted correlation metric in [22]; taking $U=W=V$ recovers their definition.

A key takeaway is that the correlation metric and the adjusted correlation metric, while intended as surrogates for non-combinatorial optimal solutions to a convex program, are based solely on combinatorial properties of the graph – thus making them more amenable to the online setting. In the AOS model, we obviously cannot exactly compute the correlation metric or the adjusted correlation metric as we go, as the full positive neighborhood of a vertex is not necessarily known upon its arrival. But, for any $u,v\in V$, we can compute, e.g., $d_{uv}^U$ in the case that $U$ is a subset of $S$, as soon as $u,v$ have arrived, since $S$ is known to the algorithm upfront! The hope is that $d^U$ and $d^{U,W}$ should be good approximations of $d=d^V$ and $d^{\ast }=d^{V,V}$, respectively, since $S$ is a random sample of $V$ – while also being usable online.

To estimate the adjusted correlation metric, we proceed in two steps. First, we estimate the correlation metric using the distance sample $S_d$; call this $\overline{d}$. Then, using the rounding sample $S_r$, we round $\overline{d}$ to estimate the adjusted correlation metric; call this $\tilde{d}$.

The next observation ensures our algorithm for the AOS model is an online algorithm.

If $u$ has no positive neighbors in the sample $S_d$, then $\tilde{d}$ isolates $u$ from all other vertices.

Both $\overline{d}$ and $\tilde{d}$ enjoy similar properties to $d$ and $d^{\ast }$, respectively, in that they are a semi-metric and near semi-metric, respectively. Thus, we can still view $\overline{d}$ and $\tilde{d}$ as specifying distances between vertices.

Given a map $f:V\times V\to [0,1]$ on the vertices of $G$, for $c\in V$, $U\subseteq V$, and $\rho \ge 0$ we define: ${\text{Ball}}_f(c,\rho ):=\{v\in V:f_{cv}\le \rho \}$ and ${\text{Ball}}_f^U(c,\rho ):=\{v\in U:f_{cv}\le \rho \}.$

A subroutine of our algorithm will be an adaptation of the CGS algorithm (see Section 1.2). This algorithm takes as input a metric $f$ on the vertices and orders the vertices in decreasing order of their densities with respect to $f$ and some radius $r$. Due to our online setting, we will only be able to estimate these densities, which we do using the counting sample $S_b$. We note that $|{\text{Ball}}_{\tilde{d}}^{S_b}(c,r)|$ depends on the randomness of $S_b$, $S_d$, and $S_r$. The following observation will ensure our algorithm is well-defined.

Lastly, we order the centers $S_p$ based on their estimated densities.

If the else statement in Algorithm 2 holds, we say $v_i$ is a pivot, and that $v_i$’s pivot is itself, $v_i$. If the if statement holds, we refer to $v_{j^{\ast }}$ as $v_i$’s pivot.

We say $v$ is pre-clustered by $u_i$ if $v$ is added to $C_i$. Otherwise, $v\in V^{\prime }$, and we say $v$ is unclustered or not pre-clustered. Note that a vertex $v$ may be unclustered for one of two reasons: either $v$ has no positive neighbors in $S_d$ ($v\notin V_0$ or as written in Algorithm 1, $v\in {\overline{V}}_0$, where ${\overline{V}}_0=V\setminus V_0$), or $v\in V_0$ but $v$ is not close to any vertex in $S_p$ with respect to $\tilde{d}$. We call the vertices in $V_0$ eligible for pre-clustering, or simply eligible, and otherwise ineligible.

If $v$ is pre-clustered by $s$, we denote $s$ by $s^{\ast }(v)$. We may refer to $s^{\ast }(v)$ as $v$’s center. We say $u$ is clustered after $v$ or $v$ is clustered before $u$ if either both $u$ and $v$ are pre-clustered, but $s^{\ast }(v)$ is before $s^{\ast }(u)$ (w.r.t the ordering of $S_p$), or if $v$ is pre-clustered but $u$ is not. Notationally, this will denoted as $v\succ u$.

Throughout, we use the choices of $\delta ,c,r$ in Algorithm 1, and let $t:=r/(2\delta )$ be a threshold parameter, which will be used in our analysis.

Recall that for nodes $u$ assigned to clusters during the Pre-clustering phase, there is some node in $S_p$ that has close $\tilde{d}$ distance to $u$. The highest ordered, with respect to the ordering of $S_p$, is said to pre-cluster $u$ and is denoted by $s^{\ast }(u)$. We may refer to $s^{\ast }(u)$ as $u$’s center. Recall we say $v$ is clustered before $u$ (or $u$ is clustered after $v$) if either both $u$ and $v$ are pre-clustered, but $s^{\ast }(v)$ is before $s^{\ast }(u)$ (with respect to the ordering of $S_p$), or if $v$ is pre-clustered but $u$ is not. For shorthand, we write $v\succ u$ when $v$ is clustered before $u$.

Fix a node $u$ that is assigned a cluster during the Pre-clustering phase of Algorithm 1. Consider all nodes $v\in V_0$, so that $uv$ is a disagreement in the output of Algorithm 1.

Let $G^{\prime }=(V^{\prime },E^{\prime })$ be the subgraph induced by the vertices that are not pre-clustered in Algorithm 1. In this section, we bound the cost of disagreements in $G^{\prime }$. Recall that $V_0$ is the set of eligible vertices, i.e., those vertices $v\in V$ such that $|N_v^{+}\cap S_d|\ne \mathrm{\varnothing }$. So $V^{\prime }$ contains the vertices that are not eligible (those in $\overline{V_0}=V\setminus V_0$), as well as vertices that are eligible but that are far from all vertices in $S_p$:

Algorithm 1 runs the standard Pivot algorithm on $G[\overline{V_0}]$, and runs Modified Pivot on $G[V_0^{\prime }]$. In Lemma 26, we bound the disagreements incurred by Pivot on $G[\overline{V_0}]$, and in Lemma 29 we bound the disagreements incurred by Modified Pivot on $G[V_0^{\prime }]$.

We note the arguments in this section may look rather different than those in the Pre-clustering phase. This is a consequence of the fact that we are using totally different clustering subroutines in each phase. In this Pivot phase, we use two versions of the (modified) Pivot algorithm. Therefore, the analysis is more combinatorial; often the charging arguments use “bad triangles” as intermediaries:

Note every clustering incurs a disagreement on at least one edge in a bad triangle.