Sparse-pivot: Dynamic correlation clustering for node insertions

Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović · 2025

Read Sparse-pivot: Dynamic correlation clustering for node insertions by Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-01830.txt.

Introduction

Mina Dalirrooyfard, Konstantin Makarychev, and Slobodan Mitrović cluster a graph that keeps gaining members in a 2025 paper. Correlation clustering sorts nodes into groups using friendships and feuds: pull the friendly together, push the feuding apart. In the dynamic version, studied here, nodes arrive one at a time and the clustering must update on the spot, reading the graph only through queries.

Their algorithm, Sparse-Pivot, rebuilds its answer as each node lands. The amortized update time stays near-logarithmic, light enough for huge streams. Its approximation guarantee, a factor near twenty, improves substantially on the prior algorithm for this model. Experiments back the theory: on test data the new method beat its predecessor's quality in practice as well. The setting fits social platforms and any network that grows by accretion rather than redesign.

Catalog record

CREATORMina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-01830

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sparse-pivot: Dynamic correlation clustering for node insertions Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović Abstract We present a new Correlation Clustering algorithm for a dynamic setting where nodes are added one at a time. In this model, proposed by Cohen-Addad, Lattanzi, Maggiori, and Parotsidis (ICML 2024), the algorithm uses database queries to access the input graph and updates the clustering as each new node is added. Our algorithm has the amortized update time of O ε ​ ( log O ⁡ ( 1 ) ⁡ ( n ) ) O_{\varepsilon}(\log^{O(1)}(n)) . Its approximation factor is 20 + ε 20+\varepsilon , which is a substantial improvement over the approximation factor of the algorithm by Cohen-Addad et al. We complement our theoretical findings by empirically evaluating the approximation guarantee of our algorithm. The results show that it outperforms the algorithm by Cohen-Addad et al. in practice. † † affiliationnotice: Equal contribution 1 Introduction In this paper, we present a new dynamic algorithm with node updates for the Correlation Clustering problem with complete information. 1 1 1 By complete information, it is meant that for each pair of nodes there is information on their similarity. Correlation Clustering is a well-studied problem that seeks to partition a set of objects into clusters based on their similarity. The problem is defined on a set of items represented as nodes in a graph, with similarity information provided through a set of edges. We assume that all pairs of nodes are classified as either “similar” or “dissimilar” by a noisy classifier. For every pair of similar nodes u and v , there is an edge (u,v) between them (sometimes referred to as a positive edge). For every pair of dissimilar nodes u and v , no edge exists between them (such pairs are sometimes called negative edges). The objective is to find a clustering that minimizes the number of disagreements with the given edge set. An edge (u,v) disagrees with the clustering if u and v are placed in different clusters, while a non-edge (u,v) disagrees if u and v are placed in the same cluster. The problem was introduced by Bansal et al. 2004 . It can be easily solved if a disagreement-free clustering exists, as each cluster then corresponds to a connected component of the similarity graph G . However, when the classifier makes mistakes, and a disagreement-free solution does not exist, the problem becomes NP-hard. In their original paper, Bansal, Blum, and Chawla proposed a constant-factor approximation, which was subsequently improved in a series of works Charikar et al. 2005 ; Demaine et al. 2006 ; Chawla et al. 2015 ; Cohen-Addad et al. 2022 ; Cohen-Addad et al. 2023 ; Cao et al. 2024 . In 2005, Ailon et al. 2008 introduced combinatorial and LP-based algorithms with approximation factors of 3 and 2.5 , respectively. The best-known approximation factor for Correlation Clustering with Complete Information is currently 1.437 ( Cao et al. 2024 ) . Nevertheless, the combinatorial algorithm by Ailon et al. 2008 , known as Pivot , remains one of the preferred choices in practice due to its simplicity and good empirical performance. Researchers have proposed various variants of Pivot that operate in parallel and streaming settings ( Bonchi et al. 2014 ; Chierichetti et al. 2014 ; Pan et al. 2015 ; Cohen-Addad et al. 2021 ; Cambus et al. 2022 ; Behnezhad et al. 2022 ; Behnezhad et al. 2023 ; Cambus et al. 2022 ; Chakrabarty & Makarychev 2023 ) . Recently, there has been growing interest in algorithms that support dynamic updates. Consider a scenario where similarity information is received over time, requiring the clustering to be updated dynamically. Dalirrooyfard et al. 2024 showed how to maintain a (3+\varepsilon) -approximation clustering with constant update time per edge insertion or deletion (see also papers by Behnezhad et al. 2019 and Chechik & Zhang 2019 ). Cohen-Addad et al. proposed an algorithm designed for a setting where nodes and edges are stored in a database. Over time, new nodes are added to the database along with their incident edges. After nodes are added, the dynamic algorithm updates the existing clustering. In this model, each edge is included in the database immediately after both its endpoints are inserted; no additional edges can be inserted or deleted afterward. The sequence of inserted nodes is non-adaptive, meaning it does not depend on the decisions of the clustering algorithm. Formally, we assume that the graph and the order of node arrivals are fixed in advance. Cohen-Addad et al. showed how to achieve a constant (albeit very large) approximation with an update time of \log^{O(1)}n , measured in terms of database operations defined as follows: (1) retrieving the degree of a node v ; (2) selecting a random neighbor of v ; and (3) checking whether two nodes u and v are connected by an edge. The database model was introduced by Assadi & Wang 2022 . The algorithm by Cohen-Addad et al. was the first dynamic algorithm for node insertions with sublinear update time. Although it provides a constant approximation, the proof suggests that the constant is very large (the paper does not estimate it). In this work, we propose a (20+\varepsilon) -approximation algorithm for Correlation Clustering with an update time of O_{\varepsilon}(\log^{O(1)}n) database operations per node insertion. In addition to node insertion, the algorithm by Cohen-Addad et al. supports deleting random nodes. Our algorithm supports a slightly weaker type of deletion: soft deletions of random vertices. When a node is soft-deleted from the graph, it initially remains in the database but is marked as soft-deleted. Moreover, the classifier continues creating edges between newly arriving and soft-deleted nodes. Only when the algorithm requests their deletion are they purged from the database. To motivate the model, consider the following example: An online store adds new items to its stock daily and aims to cluster all items based on similarity. Whenever a new item is added, the store runs a classifier to identify items similar to the new one. A record for the new item is then created and inserted into the database, along with edges connecting it to similar items. Instead of reclustering the entire dataset, the dynamic algorithm efficiently updates the clustering, requiring only O(\log^{O(1)}n) operations per item insertion. 2 Algorithm Our algorithm is based on the 5 -approximation variant of Pivot , developed by Behnezhad et al. 2023 for the semi-streaming model. Their algorithm in the static setting works as follows: First, it selects a random ordering \pi of all nodes. For each node u , it picks the neighbor of u with the smallest rank and stores this neighbor in the pivot array p : p(u)=\arg\min_{w\in N(u)}\pi(w) . Next, the algorithm identifies all nodes u such that p(u)=u , which we refer to as pivots. We call p(v) the pivot for node v . Then, the algorithm creates a new cluster for every pivot u and assigns to it nodes v with p(v)=u . All remaining unassigned nodes are placed in singleton clusters. Note that for each node u in a singleton cluster, p(u) remains equal to the neighbor of u with the smallest rank. To reiterate, in this variant of Pivot

Read the complete text