🤖 machine learning

Correlation Clustering with Random Partial Information

This paper demonstrates that correlation clustering on graphs formed by randomly subsampling a complete signed graph admits approximation guarantees that significantly improve upon general incomplete graph bounds and approach those achievable on complete graphs, a finding supported by both theoretical analysis and experimental results.

Original authors: Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari

Published 2026-08-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of data science, there is a fundamental challenge known as clustering: the task of sorting a collection of items into groups based on how similar they are to one another. Imagine a social network where some people are friends and others are strangers. The goal is to organize everyone into communities where friends are kept together and strangers are kept apart. This is not just a matter of social organization; it is a mathematical problem where every connection between two people is either a positive sign of friendship or a negative sign of distance. When researchers have a complete map of every single relationship in a group, they have developed reliable methods to find the best possible arrangement. However, in the real world, data is rarely perfect. Often, we only see a fragment of the picture, with many connections missing or unknown. For decades, mathematicians have struggled with this "incomplete" version of the problem, finding that the best methods available for partial information were significantly worse than those for complete information, often producing results that were far from optimal.

A team of researchers from the Netherlands and the United States has now explored a specific way to bridge this gap. They asked a simple but profound question: if we start with a perfect map of relationships and then randomly remove some of the connections, does the problem of finding the best groups become impossible, or can we still find a very good solution? Their work focuses on a scenario where a complete network of friends and strangers is subjected to random deletions, simulating the loss of information that happens in real-world data collection. They discovered that even with these missing pieces, it is possible to find groupings that are remarkably close to the best possible arrangement, far better than what was previously thought achievable for incomplete graphs.

The researchers approached this by first looking at two different ways to measure success. One method counts the total number of mistakes made, such as putting friends in different groups or strangers in the same group. The other method looks at fairness, ensuring that no single person is involved in an excessive number of mistakes. In the past, when dealing with incomplete data, the best guarantees for these methods were quite loose, meaning the solutions could be far from perfect. The team proved that when the missing information is random, the situation changes dramatically. They developed algorithms that can handle these random gaps and still produce high-quality groupings. For the fairness objective, they showed that the quality of the solution depends on how many connections are missing, but it remains much stronger than the worst-case scenarios found in general incomplete graphs.

For the method that counts total mistakes, the team found that if the original, perfect network had a relatively small number of mistakes to begin with, their new algorithm could recover the large, correct groups with high confidence. The logic is that even after random deletions, the core structure of the large groups remains visible. The algorithm identifies these robust clusters first, removes them from the problem, and then solves the much smaller remaining puzzle using existing techniques. This two-step process allows them to achieve a level of accuracy that was previously out of reach for incomplete data. They also demonstrated that if they have access to both the original perfect map and the incomplete version, they can combine strategies to get the best possible result, though their main contribution is showing that even without the perfect map, the random nature of the missing data is not a fatal flaw.

To ensure their mathematical proofs held up in practice, the researchers tested their ideas on real-world data. They used a dataset of Facebook friend networks, where they artificially removed connections to simulate missing information. They also created synthetic networks based on known community structures. In these experiments, their algorithms performed consistently well. The results suggested that the theoretical guarantees they proved were not just abstract limits but reflected reality, with the algorithms often performing as well as, or better than, the worst-case predictions. The experiments also revealed that the behavior of their methods was stable; as more connections were removed, the quality of the solution degraded in a predictable and manageable way, rather than collapsing entirely.

The significance of this work lies in its ability to turn a weakness into a manageable condition. By showing that random missing information does not destroy the ability to find good solutions, the researchers provide a new tool for handling messy, real-world data. Their findings suggest that for many practical applications where data is incomplete due to random errors or gaps, we do not need to settle for poor approximations. Instead, we can rely on algorithms that are specifically designed to navigate these gaps, offering a level of precision that was previously thought impossible for such imperfect datasets. This shifts the perspective on incomplete data from a source of insurmountable difficulty to a condition that can be effectively managed with the right approach.

Technical Summary: Correlation Clustering with Random Partial Information

Problem Definition

Correlation clustering is an unsupervised learning problem where the input is an undirected signed graph $G = (V, E)$ with edges labeled positive ( $+$ ) or negative ($-$). The goal is to partition the vertices into clusters to minimize disagreements. A disagreement occurs if a positive edge connects vertices in different clusters or a negative edge connects vertices within the same cluster.

The paper addresses the gap in approximation guarantees between complete graphs and general (incomplete) graphs:

Complete Graphs: Both the min-disagreement (minimizing total disagreements) and min-max (minimizing the maximum disagreements incident to any vertex) objectives admit constant-factor approximations.
General Graphs: The best known guarantees degrade significantly to $O(\log n)$ for min-disagreement and $O(\sqrt{n})$ for min-max.

The central question motivating this work is whether there exist natural classes of incomplete graphs that circumvent these lower bounds and approach the approximation guarantees attainable on complete graphs. The authors study graphs generated by randomly subsampling a complete signed graph $G$ , where each edge is independently deleted with probability $q$ . The resulting graph is denoted $G' \sim S_q(G)$ .

Methodology and Algorithms

The paper proposes algorithms and theoretical analyses under three information settings:

Access only to the original complete graph $G$ .
Access only to the incomplete graph $G'$ .
Access to both $G$ and $G'$ .

Min-Max Objective

For the min-max objective, the authors present a combinatorial algorithm (Algorithm 2) that operates solely on the incomplete graph $G'$ .

Core Idea: The algorithm leverages structural properties derived from the work of Heidrich, Irmai, and Andres (2024) on complete graphs. Specifically, vertices with large overlapping positive neighborhoods must belong to the same cluster, while vertices with very different positive neighborhoods must belong to different clusters.
Mechanism: The algorithm iterates through guesses for the optimal cost $d$ . For a fixed guess, it constructs an auxiliary graph $H$ where an edge $(u, v)$ exists if the intersection of their positive neighborhoods in $G'$ exceeds a threshold ( $2d$ ). The connected components of $H$ form the clustering. Vertices not part of large components are treated as singletons.
Analysis: Using Chernoff bounds, the authors prove that with high probability, edge deletions do not destroy enough edges to obscure the cluster structure for high-degree vertices. The algorithm outputs the clustering with the minimum cost among all guesses.

Min-Disagreement Objective

The approach for min-disagreement varies based on the magnitude of the optimal cost on the complete graph, $OPT(G)$.

Case 1: Access to $G$ (or $OPT(G)$ is large)
If the algorithm has access to $G$ , or if $OPT(G)$ is sufficiently large ( $\Omega(\log n)$ ), the authors show that any $\alpha$ -approximation algorithm for the complete graph $G$ yields an $O(\alpha/(1-q)^2)$ -approximation for $G'$ . This relies on the observation that the expected cost of the optimal solution on $G'$ does not decrease too rapidly relative to the deletion probability.

Case 2: Access only to $G'$ and $OPT(G)$ is small
This is the technically most challenging setting. The authors propose a hybrid algorithm (Algorithm 1) for the case where $OPT(G) = O(\log^\gamma n)$ :

Identify Trivial Clusters: Remove clusters that incur zero disagreements in $G'$ .
Recover Large Clusters: Construct a similarity graph $H$ $H$ based on the intersection of positive neighborhoods in $G'$ $G^{'}$ . If two vertices share a sufficiently large number of common positive neighbors in $G'$ $G^{'}$ , they are connected. The algorithm identifies large connected components in $H$ $H$ as recovered optimal clusters.
- Theoretical Justification: Lemma 5 proves that for large optimal clusters in $G$ , the intersection of positive neighborhoods in $G'$ remains large with high probability, allowing accurate recovery.
Cluster Residuals: The remaining vertices (residual set $R$ ) induce a subgraph of size $O(\text{polylog}(n))$ . The algorithm applies the general graph approximation algorithm (Demaine et al., 2006) to this small residual instance.

Key Results and Theoretical Guarantees

Min-Max Results

Theorem 1: Given $G' \sim S_q(G)$ , there exists a deterministic algorithm that returns a clustering with cost $O(\frac{\log n}{1-q})$ with high probability.
Significance: This improves upon the $O(\sqrt{n})$ bound for general graphs. The algorithm is combinatorial, avoiding the linear programming (LP) relaxations used in previous general graph approaches.

Min-Disagreement Results

Theorem 2 (Small OPT): If $OPT(G) = O(\log^\gamma n)$ $O P T (G) = O (lo g^{γ} n)$ , there is a polynomial-time algorithm using only $G'$ $G^{'}$ that achieves an $O(\log(\frac{\log n}{(1-q)^2}))$ $O (lo g (\frac{l o g n}{( 1 - q ) ^{2}}))$ -approximation with high probability.
- For constant $q$ , this is significantly better than the $O(\log n)$ bound for general graphs.
Theorem 3 (Full Range with Access to G): If the algorithm has access to both $G$ $G$ and $G'$ $G^{'}$ , there exists a polynomial-time algorithm achieving an $O(\max\{\frac{1}{(1-q)^2}, \log \log n + \log(\frac{1}{1-q})\})$ $O (max {\frac{1}{( 1 - q ) ^{2}}, lo g lo g n + lo g (\frac{1}{1 - q})})$ -approximation with high probability.
- This is achieved by running the standard approximation on $G$ (for large $OPT$) and the specialized Algorithm 1 on $G'$ (for small $OPT$), then selecting the better result.

Experimental Findings

The authors validate their theoretical results using:

Facebook Ego-Networks: Subgraphs from the Stanford Large Network Dataset Collection, converted to signed graphs.
Planted-Clique Instances: Graphs generated from a stochastic block model with controlled parameters.

Min-Max Experiments:

On smaller graphs where the optimal cost can be bounded via LP, Algorithm 2's empirical approximation ratio is at least as good as the theoretical guarantee $O(\frac{\log n}{1-q})$ .
On larger graphs, the algorithm performs consistently against a rescaled combinatorial baseline.
The algorithm is computationally efficient as it does not solve LPs, making it scalable to large graphs.

Min-Disagreement Experiments:

The authors tested the Pivot algorithm (Ailon, Charikar, and Newman, 2008) directly on the incomplete graph $G'$ .
While the theoretical guarantee in Lemma 2 applies to clustering computed on $G$ , empirical results suggest that running Pivot on $G'$ also yields a constant approximation ratio in practice, particularly on planted-clique instances where the ratio scales with $O(\frac{1}{(1-q)^2})$ .

Significance and Claims

The paper claims to bridge the gap between the approximation guarantees of complete and general graphs for correlation clustering under random edge deletions.

Natural Class: It identifies a natural class of incomplete graphs (randomly subsampled complete graphs) where approximation factors can approach those of complete graphs, rather than suffering the worst-case bounds of general graphs.
Algorithmic Efficiency: The proposed min-max algorithm is combinatorial, offering a practical alternative to LP-based methods which are often intractable for large graphs.
Robustness: The results demonstrate that correlation clustering is robust to missing information, provided the missingness is random and the underlying structure (optimal clusters) is sufficiently large or the total cost is low.
Modest Scope: The authors explicitly note that the assumption of small $OPT(G)$ in their strongest min-disagreement result is a natural setting related to recovering ground truth clusterings from noisy perturbations, but they do not claim to solve the problem for all general graph instances. They also acknowledge that the experimental observation of Pivot's performance on $G'$ is empirical and not yet proven theoretically.