betaFeedback

WorksComputer Science

Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time

Abstract

We present a fully dynamic algorithm for correlation clustering that supports vertex insertions and deletions while maintaining an O(1)O(1) approximation in polylogarithmic amortized update time. This resolves an open problem of vertex deletions posed by a recent line of work on dynamic correlation clustering. We adopt the min-disagreement objective for correlation clustering, i.e., given a signed complete graph G=(V,E+∪E−)G=(V,E^+\cup E^-), we want to minimize the total number of (+)(+) edge crossing clusters and (−)(-) edges within clusters. The input is given in the adjacency list model, where each update inserts or deletes a node along with its full set of (+)(+) neighbors. Our main technical contribution is a fault-tolerant sparse-dense decomposition framework which unlike the existing decomposition-based frameworks allows for structural inconsistencies as long as the induced cost is bounded. We also show a separation between explicitly maintaining the (stronger) sparse-dense decomposition and maintaining a constant-factor approximation to correlation clustering, which may be of independent interest.

Introduction

Correlation clustering is a fundamental problem in unsupervised learning that formalizes the goal of grouping similar elements together and separating dissimilar elements. Given a complete graph G=(V,E+∪E−)G=(V,E^+ \cup E^-) with edges partitioned into positive (+)(+) edges E+E^+ and negative (−)(-) edges E−E^-, correlation clustering seeks a partition of VV minimizing the number of disagreements, i.e., (+)(+) edges with endpoints in different clusters and (−)(-) edges with endpoints in the same cluster. Correlation clustering was first introduced by Bansal, Blum, and Chawla [9] and has since been the subject of extensive theoretical study (see, e.g., [GG06, BGK13, BDV18, AEKM20, CLM+21, AW22, BCMT22, [CFL⁺22, Vel22, BCMT23, CLMP24, CCL⁺24, DMM24, BDP⁺25, CCL⁺25, GS26], and references therein), as well as a wide range of practical applications, including automated labeling [AHK⁺09, CKP08], community mining [31, 38, 42, 41 SDE⁺21, AAD⁺23], document clustering [9 ZCC⁺08, 17], duplicate detection [6], and many others.

While the classical formulation of correlation clustering assumes a fixed signed complete graph G=(V,E+∪E−)G=(V,E^{+}\cup E^{-}), many real-world applications involve data that evolves over time. For example, in a social network, individuals can join and leave the network, causing the friendly and hostile relationships to evolve, reflected as the changes in (+)(+) and (−)(-) edges. More generally, input labels can fluctuate due to noisy data sources, and a vertex might be temporarily dropped from the network due to reliability issues. In such scenarios, the most straightforward way to maintain correlation clustering solutions is to recompute an optimal clustering from scratch after every update. However, this approach is computationally expensive and impractical, which motivates the design of efficient and high-quality correlation clustering algorithms in the dynamic setting.

As a result, there has recently been considerable research studying dynamic algorithms for correlation clustering [BDH⁺19, CZ19, BCMT23, DMM24, CLMP24, BCC⁺24, BDP⁺25, CCL⁺26]. One line of work assumes that the input is a signed complete graph in which all edges are initially negative, and each update consists of flipping the label of a single edge, either from negative to positive or vice versa. The goal is to maintain a clustering that approximately minimizes disagreement after each such update. Efficiency is typically measured by the amortized update time, defined as the total time spent over a sequence of updates divided by the number of updates performed. Achieving an update time of polylog⁡(n)\operatorname{polylog}(n) is a natural target, as it almost matches the cost of reading a single edge label. Initial breakthroughs by [BDH⁺19, CZ19] gave dynamic algorithms with 3-approximation guarantees and polylog⁡(n)\operatorname{polylog}(n) amortized update time. Subsequent work improved the efficiency further: [12, 33] achieved constant update time for O(1)O(1) approximation, and [BCC⁺24] improved the approximation ratio to 3−Ω(1)3-\Omega(1) while retaining polylog⁡(n)\operatorname{polylog}(n) update time. Most recently, [CCL⁺26] designed a dynamic algorithm that almost matches the best offline approximation factor using polylog⁡(n)\operatorname{polylog}(n) update time, as long as the clustering is represented with a special data structure.

Vertex insertions/deletions. While much of the prior work focuses on edge label updates in a fixed vertex set, many practical scenarios involve more fundamental structural changes, namely, the insertion or deletion of vertices along with their incident edges. For instance, in evolving social or communication networks, users may join or leave the system, causing a cascade of updates to the pairwise relationships encoded in the graph. This naturally motivates the study of fully dynamic correlation clustering algorithms that can efficiently handle vertex updates.

Formally, the input is an evolving signed complete graph on a fixed set of at most nn nodes. The algorithm operates in the adjacency list model, where it has direct access to the current set of (+)(+) neighbors for each node. We assume that adjacency lists are maintained and updated externally by users or an upstream system, and are provided to the algorithm in fully updated form at each step. This reflects common practical settings, such as social or communication networks, where users independently report their connections, and such updates can be performed in parallel or asynchronously outside the algorithm’s control. As a result, the algorithm is not charged for assembling or modifying adjacency lists.

The graph is implicitly defined by these lists: a pair of nodes shares a (+)(+) edge if they appear in each other’s lists, and a (−)(-) edge otherwise. Each update consists of either the insertion or deletion of a single node’s adjacency list. In an insertion, a new node vv arrives along with its full set of (+)(+) neighbors, which implicitly defines the labels of all edges incident to vv. In a deletion, a node vv and all of its incident edges are removed from the graph. The algorithm must maintain, at all times, a clustering that achieves a constant-factor approximation to the minimum number of disagreements. We remark that while it is natural to aim for polylog⁡(n)\operatorname{polylog}(n) update time for each edge insertions and deletions, it is significantly less clear what is achievable for vertex insertions and deletions. In particular, a single vertex update can simultaneously affect up to Θ(n)\Theta(n) edge labels. Therefore, the following question is a major open problem in dynamic algorithms for correlation clustering:

Is it possible to maintain a constant-factor approximation for correlation clustering using polylog⁡(n)\operatorname{polylog}(n) update time in the vertex insertion/deletion model?

Our Contributions

In this paper, we answer the above question in the affirmative, presenting the first fully dynamic algorithm for correlation clustering that maintains an O(1)O(1)-approximation under a worst-case fixed ordering of vertex insertions and deletions, with polylogarithmic amortized update time. A key distinction between our work and recent dynamic correlation clustering algorithms [30, 34] lies in the treatment of deletions. While all of these works, including ours, support arbitrary order of vertex insertions, prior algorithms are limited to random-order deletions, where deleted vertices are sampled at random from the current vertex set. In contrast, our algorithm is the first to support arbitrary order of vertex deletions while maintaining an O(1)O(1)-approximation and polylogarithmic amortized update time. This makes our method substantially more robust in fully dynamic settings.

En route to our efficient dynamic algorithm, we encountered and resolved several major technical challenges, and the ideas in our solutions can be of independent interest (see § 2 for an overview). First, explicitly maintaining the standard sparse-dense decomposition needs Ω(n)\Omega(\sqrt{n}) amortized update time (Lemma A.1). We bypass this bottleneck by introducing a “partially correct tolerant decomposition” framework. This allows for controlled structural errors by partitioning the graph into singletons, tolerant clusters, and isolated clusters, which makes it possible to maintain efficiently. We form each cluster as a standard almost-clique, but maintain it only under the relaxed definition (Lemma 4.1). Second, we extend the charging scheme of [8 ASV23] to bound the costs of tolerant and isolated clusters, and we charge misclassified singletons, level by level, to the truly sparse singletons (Theorem 2). Third, to achieve polylogarithmic update time, we combine three mechanisms: (i) lazy refreshment: a cluster KK is rebuilt only after ε∣K∣\varepsilon|K| newly inserted vertices have joined it, or ε∣K∣\varepsilon|K| of its past members have been deleted, where ∣K∣|K| is its size at formation (Algorithm 1 and Algorithm 3); (ii) identification: when a cluster forms, the outside vertices adjacent to at least half of it are moved to the singleton set, so that vertices which a later deletion may make dense with the new cluster are already tracked (Algorithm 2); (iii) approximate degree buckets: every singleton enters all O(log⁡n)O(\log n) degree lists, and periodically, sampling decides whether level ii must be scanned fully, or only until 2ipolylog⁡(n)2^i\operatorname{polylog}(n) scanned vertices test sparse (Algorithm 4 and Algorithm 5). Finally, for the running time, a forward-charging budget scheme lets each new cluster pay for its formation from the budgets of past updates and pass fresh budgets to the vertices it identifies (§ 10.3). Together, these techniques give the guarantees of Theorem 1.

Theorem 1. For the correlation clustering problem on a signed complete graph G=(V,E+∪E−)G = (V, E^{+} \cup E^{-}), there exists a randomized fully dynamic vertex-update algorithm that, given the positive subgraph

G+=(V,E+)G^{+} = (V, E^{+}) and a sequence of poly⁡(∣V∣)\operatorname{poly}(|V|) worst-case vertex insertions and deletions, together with all incident (+)(+) edges, maintains an O(1)O(1)-approximation to the optimal correlation clustering with high probability in polylog⁡(n)\operatorname{polylog}(n) amortized update time.

Adversarial robustness is an important goal for dynamic and streaming algorithms whose future inputs may depend on their past behavior. Instead of having an input stream fixed before the algorithm starts, in the standard black-box model, the adversary chooses each update after seeing the algorithm’s past outputs. This matters in practice whenever the output feeds back into the input, for instance, on social platforms, users join, leave, or change connections in response to the communities they are shown, and a dynamic clustering algorithm used as a subroutine to determine the communities receives updates that depend on its earlier answers [43]. Therefore, adversarial robustness has been studied extensively for streaming problems [16, 37], and it has also drawn more attention in dynamic graph algorithms [26, 43, 18, 14]. Essentially, our algorithm in Theorem 1 is robust against the more powerful white-box model [2], where a computationally unbounded adversary may inspect the entire maintained state and all previously drawn random bits before choosing the next vertex insertion or deletion. Thus we achieve robustness while preserving the O(1)O(1)-approximation and the polylog⁡(n)\operatorname{polylog}(n) amortized update time guarantees (see Theorem 8).

Technical Overview

Our goal is to maintain an O(1)O(1)-approximate solution for min-disagreement correlation clustering under vertex insertions and deletions, while using only polylogarithmic amortized time per update. The main difficulty is that a single vertex update can modify Θ(n)\Theta(n) edges, which may drastically change the structural role of many remaining vertices. In particular, under vertex deletions, dense structure can emerge after a carefully chosen blocking set disappears, and an algorithm that search for local neighborhood changes may fail to detect this change with polylogarithmic time. This makes the model much more challenging than the comparable edge dynamic settings in [12, 33, 14, 24].

Our framework: partially correct tolerant sparse-dense decomposition

Roughly speaking, there are two popular ways to obtain O(1)O(1)-approximation for correlation clustering, pivot algorithm (see, e.g. [3, 11, 12 CKL+24, 33, 34]) and sparse-dense decomposition (see, e.g. [29, 8, 7, 30])1.

Difficulty of pivot-based algorithms. Pivot-based algorithms iteratively select an unassigned vertex as a “pivot” and form a cluster around it, based on the similarity relationships with the remaining vertices. They often achieve strong approximation ratios, but although [34] adapted them to handle vertex insertions. However, the pivot algorithm faces some inherent challenges with vertex deletions. To see the issue, suppose a pivot is selected and its cluster is formed, and then the pivot is deleted. Then this can invalidate a large number of cluster assignments, requiring a large number of updates that seem incompatible with both efficiency and maintaining a good approximation guarantee.

The sparse-dense decomposition technique. Another popular technique for correlation clustering is the sparse-dense decomposition (SDD) technique (also called “preclustering” in the literature), which partitions the graph into sparse singleton vertices and dense almost-cliques. Roughly speaking, we define a sparse edge as one whose endpoints have significantly different neighborhoods and a sparse vertex if many of its incident edges are sparse; intuitively, these vertices act as bridges connecting unrelated parts of the graph. Removing them leaves a graph that decomposes into “almost-cliques”: groups of vertices whose sizes are similar to their degrees, and whose numbers of non-neighbors inside and neighbors outside are small. In the offline setting, this decomposition gives a constant-factor approximation by clustering each almost-clique together and keeping each sparse vertex as singletons (see, e.g. [29, 8, 7]).

A notable advantage of the sparse-dense decomposition technique is that, when randomization is allowed, we can efficiently use samples to determine whether a vertex should join a cluster. As such, it is quite natural to use this technique in the vertex dynamic setting, where sampling is perhaps the most natural operation. Indeed, building on the decomposition techniques, [30] gave the first dynamic algorithm that achieves O(1)O(1)-approximation with polylog nn update time that supports arbitrary-order insertion and random deletion. Indeed, their analysis crucially relies on the assumption that only a random vertex can be deleted, as this randomness ensures that the graph structure only change gradually, thereby ruling out worst-case scenarios in which the removal of a carefully chosen set of “blocking” vertices suddenly force the formation of a dense cluster.

Sparse-dense decomposition cannot work. We would naturally wonder whether a simple variant of the algorithm in [30] can support worst-case vertex deletion. Alas, the story becomes much more involved when arbitrary deletions are allowed: the standard decomposition is far too rigid for the fully dynamic vertex-update model. We formally prove in Section A that strictly maintaining a valid standard ε\varepsilon-sparse-dense decomposition (defined as in, e.g., [29, 8]) would necessarily require an expected amortized update time of Ω(n)\Omega(\sqrt{n}) per update.

To see the difficulty, consider O(n)O(\sqrt{n}) disjoint cliques, each of size O(n)O(\sqrt{n}), so the graph is fully structured into dense components. Now insert O(n)O(\sqrt{n}) new vertices, each connecting to all existing vertices across all cliques. These new connections create many cross-cluster inconsistencies, causing every original vertex to become incident to a large number of “sparse” edges, and thus forcing essentially all vertices to be reclassified as sparse. This triggers a global recomputation of the decomposition and incurs Θ(n)\Theta(n) changes. However, removing these O(n)O(\sqrt{n}) inserted vertices restores the original clique structure, so the algorithm will need to put the Θ(n)\Theta(n) vertices back into the clusters, which induces a high time complexity!

From exact decomposition to partially correct tolerant decomposition. The above issue suggests a fundamental barrier for maintaining exact sparse-dense decompositions. However, the example also reveals that exact maintenance is unnecessary for achieving an O(1)O(1)-approximation in correlation clustering. In particular, even if we do not update cluster assignments when sparse vertices are inserted, the resulting inconsistencies can be charged to the cost of the sparse edges, preserving a constant-factor guarantee in the above example. As such, our first step is to relax the definition of dense structure. In what follows, we will see that the min-disagreement correlation clustering is surprisingly “graceful”, in the sense that even some strong structural inconsistency in the decomposition can still lead to constant-factor approximation in the cost. Conceptually, our new “tolerant” SDD framework provides the first separation between the stronger decomposition problem and the correlation clustering objective.

To ensure efficiency under worst-case deletion, our framework tolerates three specific structural inconsistencies:

  1. Tolerant Clusters (Out-edge violations): Clusters may have many outgoing positive edges, provided those external edges are sufficiently sparse and there are not many internal non-edges inside. Intuitively, clusters remain internally cohesive but need not be externally isolated. This is useful because it makes the decomposition robust to vertex insertions that introduce many external connections, since we do not need to modify clusters in response. In fact, observe that such relaxation already overcomes the Ω(n)\Omega(\sqrt{n}) update time lower bound we discussed above: when high-degree sparse interlopers are inserted, we simply do not make any updates to the clusters.

  1. Isolated Clusters (Non-edge violations): Clusters may contain many non-edges, provide they have enough number of sparse edges outside the cluster. Intuitively, clusters are relaxed from near-cliques to loosely coherent groups that may be internally incomplete. This avoids costly restructuring when internal density is violated due to outside clustering “stealing” vertices from this cluster (more details to be discussed later).

  1. Partially Correct Singletons: The pool of singletons (denoted as V~singleton\widetilde{V}_{\mathrm{singleton}}) is permitted to include vertices that should belong to clusters, provided the total number of accumulated edges does not dominate the total number of edges that are actually sparse. Intuitively, singletons act as a buffer for uncertain assignments. This is useful because it allows us to defer reassignment decisions while still controlling the overall disagreement cost.

At a high level, the first two types of tolerant structure can ensure that the algorithm does not need to update the clusters too often, and the misclassification of the dense clusters can ease the required time complexity for cluster-forming subroutines. We call this new decomposition framework a partially correct tolerant decomposition.

Why the relaxed structure still gives an O(1)O(1)-approximation. While our relaxed structure deviates considerably from the sparse-dense decomposition, we can nevertheless still guarantee a constant-factor approximation with the following analysis:

  • Tolerant Clusters (Bounding out-edge cost): As long as the number of non-edges inside a cluster is small, grouping the set of vertices would still induce a relatively small cost. The main risk of tolerating many outgoing edges is accidentally splitting a larger truly dense cluster. However, our rules ensure that these outgoing edges point primarily to either sparse vertices or to disagreement neighbors of the cluster. Hence, OPT must pay a cost comparable to these edges, allowing us to charge the cost to OPT.

  • Isolated Clusters (Bounding non-edge cost): When the number of non-edges inside a cluster is large, grouping kk vertices together joins many non-neighbors and can induce Θ(k2)\Theta(k^2) disagreement costs. However, our rules require that each of these vertices must have Ω(k)\Omega(k) sparse incident edges outside of the cluster. Again, these edges induce Ω(k2)\Omega(k^2) cost for any valid clustering (including OPT); as such, we can still keep the vertices together and charge the cost to OPT.

  • Partially Correct Singletons (Bounding misclassification cost): Finally, for kk dense vertices with degree around 2i2^i, mistakenly putting them as singletons incurs roughly k⋅2ik \cdot2^i cost. We tolerate this only when there are many sparse vertices in the graph, which induces cost much more than k⋅2ik \cdot2^i to OPT. Hence we can still keep the dense vertices as singletons and charge the cost to OPT.

The formal proof is built on the charging argument similar to the techniques in [29, 8, 7], albeit it is considerably more involved. In a standard analysis, the clustering costs are charged to edges with unavoidable costs in the graph (and thus to OPT). One major complication in our setting is that since the pool of singleton vertices can still contain dense vertices, we cannot always find edge sets for the charging of edges going out of a cluster. Instead, our novel charging scheme charges these costs to the edges on singleton vertices, and then transfer the charges of singleton vertices to OPT.

Tracking the set of singleton vertices and merging into clusters

The immediate advantage of allowing a tolerant structure in singleton vertices is that it becomes much easier to merge dense vertices into clusters. To understand why, we first give some intuition for what it means for a set of vertices to “block” clusters from forming. In correlation clustering, a valid dense cluster must be both well-connected internally (forming a near-clique) and isolated externally (having few edges to outside vertices). Thus, even if a clique VV exists, a large external set SS with many connections to this clique can prevent VV from being recognized as a cluster because the clique no longer appears sufficiently isolated. In this sense, the external set SS acts as a “blocking set” that hides the clique and prevents it from being merged.

Consider a concrete example where a large blocking set SS of size Θ(n)\Theta(n) hides two such groups of vertices. The first group is n0.49n^{0.49} disjoint O(1)O(1)-sized cliques, each connecting to O(1)O(1) vertices in SS, and the second group is a single n\sqrt{n}-sized clique connecting to O(n)O(\sqrt{n}) vertices in SS. If we keep deleting the “blocking vertices” inside SS that correspond to the O(1)O(1)-sized cliques, those tiny cliques suddenly become perfectly isolated and should be clustered. However, if we insist that dense clusters must be formed immediately upon being unblocked, it is virtually impossible for us to efficiently locate these newly freed singleton vertices from the large pool of V~singleton\widetilde{V}_{\mathrm{singleton}} (here, and throughout, we use V~singleton\widetilde{V}_{\mathrm{singleton}} to denote the set of singleton vertices maintained by the algorithm). Note that notification-based approaches will not work here since no random neighbors for a vertex s∈Ss \in S outside SS can be sampled unless we sample Ω(n)\Omega(n) neighbors. On the other hand, if we only care about unclustered vertices that are “dominating” because their aggregate contribution to the approximation cost is large enough, then we do not need to search for or form any of the tiny O(1)O(1)-sized cliques until the n\sqrt{n}-sized clique becomes unblocked. Therefore, since the large n\sqrt{n}-sized clique dominates the singleton pool, it suffices to sample O(2ilog⁡2n)=O~(n)O(2^i \log^2 n) = \widetilde{O}(\sqrt{n}) vertices from the singleton vertices every O(2i)O(2^i) updates, i.e. with polylog nn work each update, find the unblocked massive clique, form a cluster, and recurse.

Illustration of a large blocking set

Figure 2. Illustration of a large blocking set SS that blocks potential clusters of different sizes. If we insist on forming clusters for all dense vertices, then deleting the vertices adjacent to the triangles becomes very hard to detect unless we go over the entire V~singleton\widetilde{V}_{\mathrm{singleton}} set. On the other hand, the tolerant structure in V~singleton\widetilde{V}_{\mathrm{singleton}} can effectively resolve the issue.

It turns out that we can formalize the notion of “dominating” for groups of vertices with degree around 2i2^{i}. In particular, we say a level ii is dominating if the kk dense vertices with degree around 2i2^{i} satisfy k⋅2i=Ω(∣V~singleton∣/log⁡n)k \cdot2^{i} = \Omega(|\widetilde{V}_{\mathrm{singleton}}|/\log n). The intuition behind this definition is that the quantity k⋅2ik \cdot2^{i} captures the total contribution of these vertices to the approximation cost; therefore, a dominating level contributes a significant fraction of the overall correlation clustering cost. A uniformly sampled vertex of V~singleton\widetilde{V}_{\mathrm{singleton}} is one of these kk dense vertices with probability k/∣V~singleton∣≥1/(2ilog⁡n)k/|\widetilde{V}_{\mathrm{singleton}}| \ge1/(2^{i}\log n). Hence, Θ(2ilog⁡2n)\Theta(2^{i}\log^{2} n) samples detect a dominating level with high probability, which if we perform after every O(2i)O(2^{i}) updates costs polylog(n)(n) per event.

Tracking a few vertices merging to a large cluster. Unfortunately, the reality is much more challenging than the ideal case for entire clusters waiting to be formed: it could happen that a few vertices for a dominating group need to be merged to an already-existing large cluster. Consider a scenario where a large cluster KK of size nn has only O(1)O(1) vertices in V~singleton\widetilde{V}_{\mathrm{singleton}} waiting to merge into it. Furthermore, suppose there are also n0.99n^{0.99} sparse vertices elsewhere. Since the O(1)O(1) vertices have degree 2i≈n2^{i} \approx n, then level ii is dominating. However, uniform sampling over V~singleton\widetilde{V}_{\mathrm{singleton}} would hit these O(1)O(1) dense vertices with probability O(1/n0.99)O(1/n^{0.99}), making it impossible to sample these vertices in polylogarithmic time.

References

  1. [2]Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou. The white-box adversarial data stream model. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 15–27. ACM, 2022. 4arxiv.org/abs/2204.09136
  2. [3]Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating Inconsistent Information: Ranking and Clustering. Journal of the ACM (JACM), 55(5):1–27, 2008. 4
  3. [6]Arvind Arasu, Christopher Ré, and Dan Suciu. Large-scale deduplication with constraints using dedupalog. In Proceedings of the 25th International Conference on Data Engineering, ICDE, pages 952–963, 2009. 2DOI
  4. [7]Sepehr Assadi, Vihan Shah, and Chen Wang. Streaming algorithms and lower bounds for estimating correlation clustering cost. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. 3, 4, 5, 7, 14, 15, 22, 23, 27DOI
  5. [8]Sepehr Assadi and Chen Wang. Sublinear time and space algorithms for correlation clustering via sparse-dense decompositions. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 10:1–10:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. 2, 3, 4, 5, 7, 12, 14, 15, 22, 23, 27arxiv.org/abs/2109.14528
  6. [9]Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation Clustering. Machine learning, 56(1):89–113, 2004. 1, 2
  7. [11]Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li-Yang Tan. Almost 3-approximate correlation clustering in constant rounds. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 720–731. IEEE, 2022. 2, 4arxiv.org/abs/2205.03710
  8. [12]Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li-Yang Tan. Single-pass streaming algorithms for correlation clustering. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 819–849. SIAM, 2023. 2, 4DOI
  9. [14]Vladimir Braverman, Prathamesh Dharangutte, Shreyas Pai, Vihan Shah, and Chen Wang. Fully dynamic adversarially robust correlation clustering in polylogarithmic update time. In International Conference on Artificial Intelligence and Statistics, pages 1477–1485. PMLR, 2025. 2, 4, 12, 16, 31arxiv.org/abs/2411.09979
  10. [16]Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 63–80. ACM, 2020. 4
  11. [17]Francesco Bonchi, David García-Soriano, and Konstantin Kutzkov. Local correlation clustering. CoRR, abs/1312.5105, 2013. 2arxiv.org/abs/1312.5105
  12. [18]Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. 4
  13. [20]Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman. Correlation clustering with sherali-adams. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 651–661, 2022.
  14. [22]Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl. Understanding the cluster linear program for correlation clustering. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1605–1616. ACM, 2024.DOI
  15. [23]Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang. Solving the correlation cluster LP in sublinear time. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1154–1165. ACM, 2025.DOI
  16. [24]Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang. Static to dynamic correlation clustering. In Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis, editors, 53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, Royal Holloway, University of London, Egham, United Kingdom, July 7-10, 2026, volume 374 of LIPIcs, pages 48:1–48:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.arxiv.org/abs/2504.12060
  17. [26]Julia Chuzhoy and Sanjeev Khanna. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 389–400. ACM, 2019.arxiv.org/abs/1905.11512
  18. [29]Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub Tarnawski. Correlation clustering in constant many parallel rounds. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2069–2078. PMLR, 2021. 2, 4, 5, 7
  19. [30]Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis. Dynamic correlation clustering in sublinear update time. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. 2, 3, 4, 5, 12, 13, 31
  20. [31]Yudong Chen, Sujay Sanghavi, and Huan Xu. Clustering sparse graphs. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems, pages 2213–2221, 2012. 2
  21. [33]Mina Dalirrooyfard, Konstantin Makarychev, and Slobodan Mitrovic. Pruned pivot: Correlation clustering algorithm for dynamic, parallel, and local computation models. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. 2, 4arxiv.org/abs/2402.15668
  22. [34]Mina Dalirrooyfard, Konstantin Makarychev, and Slobodan Mitrović. Sparse-pivot: Dynamic correlation clustering for node insertions. In Proceedings of the 42nd International Conference on Machine Learning, ICML 2025, Proceedings of Machine Learning Research, 2025. 3, 4, 12, 13arxiv.org/abs/2507.01830
  23. [37]Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In Advances in Neural Information Processing Systems, volume 33, 2020. 4arxiv.org/abs/2004.05975
  24. [38]Mario Levorato, Rosa Figueiredo, Yuri Frota, and Lúcia Drummond. Evaluating balancing on social networks through the efficient solution of correlation clustering problems. EURO Journal on Computational Optimization, 5(4):467–498, 2017. 2DOI
  25. [41]Nate Veldt, David F. Gleich, and Anthony Wirth. A correlation clustering framework for community detection. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW, pages 439–448, 2018. 2DOI
  26. [42]Nate Veldt, Anthony Ian Wirth, and David F. Gleich. Correlation clustering with low-rank matrices. In Proceedings of the 26th International Conference on World Wide Web, WWW, pages 1025–1034, 2017. 2arxiv.org/abs/1611.07305
  27. [43]David Wajc. Rounding dynamic matchings against an adaptive adversary. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 194–207. ACM, 2020. 4arxiv.org/abs/1911.05545

Paper details

vlnc:W_swyngb89
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT Astra, Claude Opus 5.5

View statement
Looking for related papers…
Contents