Source-linked AI summary
Correlation Clustering with Random Partial Information
Rajath Rao K. N., Jens Schlöter, Sami Davies, Amira Ouchene, Yasamin Nazari
TL;DR
Correlation clustering lacks strong approximation guarantees on incomplete general graphs, unlike on complete graphs. This paper studies random edge-deletions from complete signed graphs and proves substantially better guarantees, including an O(log n/(1−q))-approximation with high probability.
Problem
Incomplete-graph correlation clustering has a disparity between complete-graph and general-graph approximation factors, motivating natural graph classes with better guarantees.
Method
The paper randomly deletes each edge of a complete signed graph with probability q and develops combinatorial algorithms under different information-access assumptions.
Results
O(log n/(1−q))-approximation with high probability is achieved from the subsampled graph, while access to both graphs yields O(max{1/(1−q)^2, log log n + log(1/(1−q))}) approximation.
Takeaways & Limitations
Randomly subsampled complete signed graphs can admit approximation guarantees significantly better than the O(log n) or O(√n) guarantees known for general graphs.
Takeaways & Limitations
The guarantees assume a complete signed graph whose edges are independently deleted with probability q, with results varying by whether the algorithm knows G, G′, or both.
Abstract
from arXiv · showhide
Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, yet on general (non-complete) graphs, the best guarantees blow up to $O(\log n)$ and $O(\sqrt{n})$. This gap between the two regimes motivates the following question: are there classes of incomplete graphs that circumvent the lower bounds on general graphs and admit approximation guarantees approaching those attainable on complete graphs? We study a natural class of graphs obtained by randomly subsampling a complete signed graph $G$, where each edge is independently deleted with probability $q$. For such graph instances both for the min-max and the min-disagreement objectives, we prove approximation guarantees (depending on $q$) that are substantially better than the bounds achievable for general graphs. We supplement our theoretical results with experiments that also suggest that the approximation ratios of our algorithm are close to those of the complete graph and better than the worst-case bounds for general (non-complete) graphs.
1 Introduction
The paper studies correlation clustering when a complete signed graph is randomly sparsified by independently deleting edges, targeting the gap between complete- and general-graph approximation guarantees. It gives improved min-max and min-disagreement guarantees under different information assumptions and supports the theory with experiments.
- Approximation gap: For general graphs, min-disagreement has an O(log n) approximation, while min-max has an O(√n) approximation.These bounds contrast with the constant-factor guarantees available on complete graphs.
- Problem setting: Random deletion forms a non-complete graph class by independently removing each edge from a complete signed graph with probability q.The resulting graph G′ is sampled from Sq(G).
- Min-Max Correlation Clustering: O(log n/1−q)-approximation: Theorem 1 gives a high-probability min-max algorithm under random deletions.The algorithm is deterministic, and the probability is over the edge deletions.
- Min-disagreement: O(α/(1−q)2)-approximation: access to the original complete graph G transfers any α-approximation for G to G′ in expectation, and with high probability when OPT(G) ∈Ω(log n).The expectation guarantee follows from E[OPT(G′)] ≥Ω((1−q)3 · OPT(G)).
- Min-disagreement: O(log( log n/(1−q)2 ))-approximation: with OPT(G) = O(logγ n), a polynomial-time algorithm using only G′ succeeds with high probability.For constant q, this improves on the O(log n) general-graph guarantee by exploiting the small number of clusters with disagreements and identifying large optimal clusters.
- Experimental results: Experiments indicate that the min-max empirical approximations are at least as good as O(log n/1−q), while Pivot on G′ may satisfy the theoretical O(α/(1−q)2) guarantee.Experiments use Facebook ego-network random-deletion instances and planted-clique stochastic-block-model instances.
2 Min-disagreement Objective
For min-disagreement correlation clustering on randomly subsampled signed graphs, the paper relates the sampled optimum to bad triangles and derives improved expected and high-probability approximation guarantees. The guarantees depend on the deletion probability q and, in one regime, on the size of OPT(G).
- Bad-triangle structure: τ(G) ≤ OPT(G) for every signed graph, while complete graphs satisfy OPT(G) ≤ 9·τ(G).Here τ(G) is the maximum number of edge-disjoint bad triangles.
- Expected guarantees: 9α/(1−q)^2: An α-approximation for the complete graph G yields this expected approximation for the sampled graph G′ when only G is available.The stronger bound improves the more direct 9·α/(1−q)^3 guarantee.
- High-probability guarantees: 18α/[(1−β)(1−q)^2]: If OPT(G) ≥ c log n, then an α-approximation for G achieves this approximation for G′ with probability at least 1−n^−2.5.The constant is c = 54/[β^2(1−q)^3], with β ∈ (0,1).
- Algorithms and guarantees: O(max{1/(1−q)^2, log log n + log(1/(1−q))}): Given both G and G′, a polynomial-time algorithm achieves this approximation with high probability.This is Theorem 3’s guarantee for the min-disagreement objective.
- Algorithms and guarantees: O(log(c^2/(1−q)^2 · log^(2γ) n)): Given only G′, a polynomial-time algorithm achieves this approximation with high probability when OPT(G) < c·log^γ n.The theorem assumes c, γ ≥ 1.
3 Min-max Objective
For randomly subsampled signed graphs, the section gives a robust min-max clustering algorithm that recovers optimal non-singleton clusters with high probability and achieves an O(1/(1−q)) · max{log n, OPT∞(G′)} guarantee.
- Theorem 5 guarantees cost at most O(1/(1−q)) · max{log n, OPT∞(G′)} with high probability.
- The min-max cost is the maximum vertex disagreement, with optimum OPT∞(G′) = minC costG′(C).
- Algorithm 2 identifies high-positive-degree vertices, links vertices with sufficiently many common positive neighbors, and makes the remaining vertices singletons.The full procedure runs the algorithm over guesses d ∈ {c log n, 2c log n, 4c log n, . . . , n} and returns the clustering with minimum observed cost.
- Singleton vertices have disagreement cost at most λd, while non-singleton vertices retain their optimal-clustering cost.Lemma 10 establishes the singleton bound under Eλ,d, and the proof bounds non-singleton vertices by d ≤ λ ˆd.
- With probability 1−n−1, every connected component of the auxiliary graph containing a high-degree vertex coincides with exactly one optimal cluster.
4 Experiments
Experiments on randomly edge-deleted Facebook ego-graphs and planted-clique instances broadly support the theoretical guarantees for both objectives. Algorithm 2’s min-max ratios worsen with deletion probability on smaller graphs, while Pivot shows the predicted dependence on planted-clique instances but no clear trend on ego-graphs.
- Experimental setup: Experiments used 10 Facebook ego-graphs, with 30 independently edge-deleted realizations for each q ∈ {0.05, 0.15, 0.25, 0.4}.The experiments ran Python 3.11.8 on an Apple M2 with 8 cores and 8 GB of memory.
- Min-max: On smaller ego-graphs, Algorithm 2 achieved an approximation at least as good as Theorem 5’s guarantee, with the approximation factor worsening as q increased.The min-max LP was solved on G′ to obtain a lower bound on the optimal cost.
- Min-max: On larger ego-graphs, Algorithm 2 performed at least as well as the theoretical O(1/(1 −q)) · max{c log n, OPT∞(G′)} guarantee when the rescaled DMN objective served as a proxy for optimum.A true optimal-cost lower bound was computationally infeasible on these instances.
- Min-disagreement: Pivot performed well on all tested randomly deleted graphs, suggesting behavior similar to the in-expectation results of Lemma 2.For min-disagreement, comparisons used the LP optimum of G′ rather than the unobserved complete graph G.
- Min-disagreement: On planted-clique instances, Pivot’s approximation ratio increased steadily with q for every n, consistent with Lemma 2’s O(1/(1−q)2) dependence.The planted-clique experiments varied clique number and sizes while controlling community structure.
- Min-disagreement: On Facebook ego-graphs, Pivot showed no visible increase in approximation ratio with q, unlike the planted-clique instances.The passage attributes this suspected difference to degree variation between the instance families.
A Supplementary Experiment Information
This supplementary section provides additional experimental plots and graph statistics for the Facebook ego-networks. It also distinguishes networks where the LP relaxation was solved exactly from those where it was not.
- Additional plots are provided for the experiments discussed in the Experiments section.
- Table 1 reports graph statistics for Facebook ego-networks, separating four graphs with exact LP solutions from six graphs without solved LPs.
A.1 Min-Max
The min-max experiments run Algorithm 2 on randomly deleted ego-graphs and record maximum disagreement, using LP relaxations on the four smallest instances to certify approximation ratios against lower bounds. Across tested parameter values, λ = 5 performed best on most instances and was used throughout, so the broader experimental results represent practical performance rather than a certified guarantee.
- Experimental protocol: Algorithm 2 was run on each ego-graph after independent deletions at probability q, with the maximum disagreement recorded.The protocol repeats this for each ego-graph and deletion probability.
- Experimental protocol: On the four smallest ego-graphs, solving the min-max LP relaxation with Gurobi 13.0.2 yields certified approximation ratios against a lower bound on the optimum.Table 3 reports means, standard deviations, and 95% confidence intervals over 30 seeds for the first group.
- Parameter selection: λ = 5 was best on most instances among λ ∈ {5, 8, 12} and was used throughout the experiments.Larger values degraded solution quality in the runs, while λ = 5 is below the range required by Theorem 5.
- Parameter selection: The reported experiments therefore measure practical performance rather than a certified guarantee.The theorem constants are described as worst-case and unoptimised.
A.2 Min-disagreement
The section evaluates Pivot on randomly subsampled graphs using planted-clique instances and Facebook ego-networks. It also reports experimental comparisons involving LP-based objectives and running time.
- Experimental setup: Pivot is evaluated on two instance families: planted-clique graphs and the four smallest Facebook ego-graphs.The planted-clique instances use within-part positive-label probability 0.9 and across-part probability 0.1.
- Runtime: Figure 3 compares the average running time of combinatorial Algorithm 2 and LP on Facebook ego-networks as a function of n.Running time is shown on a logarithmic scale.
- Planted-clique experiments: Table 5 reports the ratio of average Pivot cost on G′ to the min-disagreement LP optimum for planted-clique instances.Each instance uses 50 independent seeds, or 20 seeds when n = 100; zero-optimum realizations at n = 10 are omitted.
- Facebook experiments: Table 6 reports the ratio of average Pivot cost on the subsampled graph to the min-disagreement LP optimum for Facebook ego-networks under deletion probability q.Each cell aggregates 30 independent runs and includes a mean, standard deviation, and 95% confidence interval margin.