Efficient Testing for Correlation Clustering: Improved Algorithms and Optimal Bounds
Authors: Chengyuan Deng
Jie Gao
Songhua He
Chen Wang
Venue: ICLR 2026 Poster (2026)
Keywords: Correlation Clustering
Structural Balance
Property Testing
Primary area: learning theory

Abstract: Correlation clustering is an important unsupervised learning problem with broad applications. In this problem, we are given a labeled complete graph $G=(V,E^+ \cup E^-)$, and the optimal clustering is defined as a partition of the vertices that minimizes the $+$ edges between clusters and $-$ edges within clusters. We investigate efficient algorithms to test the \emph{cost} of correlation clustering: here, we want to know whether the graph could be (nearly) perfectly clustered (with $0$ cost) or is far away from admitting any perfect clustering. The problem has attracted significant attention aimed at modern large-scale applications, and the state-of-the-art results use $\widetilde{O}({1}/{\varepsilon^7})$ queries and time (up to log factors) to decide whether a graph is perfectly clusterable or needs to flip labels of $\varepsilon {\binom n 2}$ edges to become clusterable. In this paper, we improve this bound significantly by designing an algorithm that uses ${O}({1}/{\varepsilon^2})$ queries and time. Furthermore, we derive the first algorithm that tests the cost for the special setting of correlation clustering with $k$ clusters with ${O}(1/{\varepsilon^4})$ queries and time for constant $k$. Finally, for the special case of $k=2$, which corresponds to the strong structure balance problem in social networks, we obtain tight bounds of $\Theta({1}/{\varepsilon})$ queries -- the first set of \emph{tight} bounds in these problems. We conduct experiments on simulated and real-world datasets, and empirical results demonstrate the advantages of our algorithms.

Published as a conference paper at ICLR 2026
EFFICIENT TESTING FOR CORRELATION CLUSTERING: IMPROVED ALGORITHMS AND OPTIMAL BOUNDS
Chengyuan Deng"
Jie Gao
Songhua Hel
Chen Wang
ABSTRACT
Correlation clustering is an important unsupervised learning problem with broad applications. In this problem, we are given a labeled complete graph G = EV U E and the optimal clustering is defined tices that minimizes the + edges between clusters and - edges within clusters. We investigate efficient algorithms to test the cost of correlation clustering: here, we want to know whether the graph could be (nearly) perfectly clustered (with O low cost) is far away from admitting any perfect clustering. The problem has attracted significant attention aimed at modern large-scale applications, and the state-of-the-an results use (11e²)) queries and time (up to log factors) to decide whether a graph is perfectly clusterable or needs to flip labels of =()) edges to be- come clusterable. In this paper, we improve this bound significantly by designing an algorithm that uses (11/s²) queries and time. Furthermore, we derive the first algorithm that tests the cost for the special setting of correlation clustering with k clusters with O(1/=*) queries and time for constant k. Finally, for the special case of A: = 2, which corresponds to the strong structure balance problem in social networks, we obtain tight bounds of ((1/e) queries the first set of fight bounds in these problems. We conduct experiments on simulated and weal-world datasets, and empirical results demonstrate the advantages of our algorithms.
partition of the ver-
INTRODUCTION
Correlation clustering is fundamental unsupervised problem that has been studied extensively in the literature of theoretical computer science and machine learning. At high level, the problem asks to partition the datasets based on qualitative information, i.c., whether two data points are similar. More formally, the dataset is represented as a labeled complete graph G = (V, E+ U E-). where each vertex v E V represents a data point, and each vertex pair (u, v) contains an edge with label (+) or (-) denoting "similarity" and "dissimilarity" The cost of clustering is defined as the total number (+) edges crossing clusters and the number of (-) edges inside the same clusters.
Correlation clustering has a broad range of applications, including document summarization Bansal ct al. (0022). image segmentation Kim et al. (201T): Yarkony et al. (2012). bioinformatics Hou et al. 2016), and community detection Veldt et al. (2018); Shi et al. (2021). Notably, correlation clustering corresponds to naturally emerging structures in signed social networks, where edges are classified as "friendly" and "hostile" relationships. In this setting, structural balance theory, which is well established in sociology, characterizes the "stability" of triangles in signed networks (Heider [9466] 1982); Cartwright& & Harary (1956); Davis (1967). With strong structural balance, only two types of triangles are stable - with all three edges as positive or with two negative and one positive edge ('the enemy of your enemy is your friend"). The local stability condition also implies global alignment. The vertices in a stable signed network can be partitioned into two groups with all (+) (friendly) edges inside each group and all (-) (hostile) edges between. Mathematically. this precisely the case of a perfect (zero-cost) clustering with two clusters. In addition, weaker version of structural balance also allows triangles of all three negative edges. Globally, a weakly balanced signed network corresponds to multiple clusters with only positive intra-cluster edges and negative
"Rutgers University. E-mail: cd751 @rutgers.edu. 1 Rutgees University. E-mail: 1g @ rudgers.edu. I Rutgers University. E-mail: songhuahe.co cs @eaeeeecss@mmmmoommmmmmmmm gmail.com. 6 RRnnsellarr Polytechnic Institute. F-mail: wange33@rppiedu..

---

Published as a conference paper at ICLR 2026
inter-cluster edges. That is, the network has a zero cost correlation clustering where the number of clusters can be flexible. In the remainder of this paper, such a network with a zero cost correlation clustering is called clusterable (with any number of clusters), ke-clsstrrable if the number of clusters is fixed to be k. A (strongly) balanced network is 2-clusterable.
Most of the work in correlation clustering (resp. structural balance) aims to find or approximate
the best clustering, i.e., output partition of the vertices (see, e.g. |Bansal et al. (2002); Ailon et al. (2008) Chawla et al. (2015); Cohen-Addad
al. (2021); Assadi Assadi & Wang (2022): Cohen-Addad et al. [2022] 2023); Dalirrooytard et al. (2024); Cohen-Addad et al. (2024a b): Cao et al. (2024);
Dalirrooyfard et al. (2025). and references therein). For an n-vertex graph, simply outputting the
partition requires (2(n) time. There are efficient algorithms that converge in near-optimal O(n)
time" Assadi & Wang 2022;; Cao et al. 2024 2025). Nevertheless, in applications with massive datasets, we might want to learn the cost of correlation clustering using o(n) time. For instance, in the structural balance problem, we might be interested in knowing whether the graph is close to or far away from being balanced without knowing the entire network structure. A graph that is far from balanced state may indicate high level of volatility. Additionally, might want to the clustering cost to determine whether the graph is worthy of clustering without paying 2(n) time.
The above question is closely related to the realm of property testing, in which are often inter- ested in obtaining statistics of the data with only a very limited number of queries. For correlation clustering, handful of existing results have explored this direction. For instance, Bonchi, Garefa- Soriano, and Kutzkov [onchi et al. (2013) designed an algorithm that computes a data structure that supports cluster membership query in (1///²) time, and the underlying solution is a 3OPT en? approximation Subsequently, Assadi et al. 2023) and Ashvinkumar et al. (2023) studied the prob- lem of testing for the cost of correlation clustering and structural balance the streaming model, where the edges arrive one-by-ong in stream. There, the goal was to obtain an approximation of the optimal clustering cost with o(n) space.
To the best of our knowledge, the work closest to the problem for sublinear time is Adriaens & Apers 2023) (see also Chen et al. (2024) for the quantum setting), where they designed an algo- rithm requiring Õ(1 ((1/e") queries, to test whether a graph is e/ 1e/1--/ooettoo-custeeedd
vs. E-far from being clusterable. With stronger technique by |Sohler (0012). one can use O(1/e") queries to test whether a graph is balanced vs. from being bulanced, for the special case of structural balance. Throughout, s-far indicates at least (() edge labels need to be flipped to make the graph balanced or admit a perfect clustering. To date, there are no matching lower bounds to show the tightness of these results, and we do not have knowledge on testing correlation clustering cost with & (which is given) clusters for general k. Therefore, getting improved bounds, and ideally tight bounds, for testing correlation clustering and structural balance remains important open problems.
1.1 OUR CONTRIBUTIONS
We make substantial progress towards the open problems in this paper. We consider the model where one can issue queries for the label of any edge (u, v) and we minimize the number of queries used to evaluate or approximate the cost of correlation clustering for the graph. In particular, Our contributions are summarized in the following settings.
We propose an algorithm to test whether the correlation clustering cost is at most O (()) or at least e (()) using O(1/E²) queries.
We give an algorithm to test whether the correlation clustering cost with & clusters for any constant - ( (?)) or least e()) using ((1/s4) queries.
k: is
For the case of tests if the graph is at most e/900-close to being balanced or at least e-far from being balanced using O(1/s) queries. We complement the upper bound by an 12(1/E) lower bound, showing the tightness of the proposed algorithm.
which corresponds to structural balance, we devise an algorithm that
Unless specified otherwise, we use (-)) to hide poly-logarithmic terms. Unless specified otherwise, the notation OPT denotes the optimal clustering cost for correlation clustering.
2

---

Published as a conference paper at ICLR 2026
Note that all algorithms efficient in time complexity well: it is proportional to the query complexity. Table shows comparison of results. Prior results are from Adriaens & Apers (2023).
Table I: Comparison of Results Query Complexity.
Task
Previous Best Bound
Our U.B.
Our L.B.
Remark
Structural Balance
0(1/5²)
0(1/E)
2(1/E))
Correlation Clustering
0(1/7))
0(1/=²)
(211s))
Correlation Clustering (fixed k)
0(1/s))
201/s)
0 B In for general &:
We now discuss the formal statements for these algorithmic results. We start with the results for testing clusterability for general correlation clustering, which is our main technical result.
Theorem 1. Fix 10. There exists randomized algorithm that given labeled complete graph G = (V, E UEE and a parameter' answers with the following rules
If G is clusterable, the algorithm always answers "YES";
If G is at least E-far from being clusterable, the algorithm answers "NO" with probability 2 0.9;
G C. -2close being clusterable for some small constant C, the algorithm answers "YES" with probability 2 0.9.
The algorithm queries at most O(1/E²) edges of G and runs in O(1/E²) time.
Compared to the results in Adriaens & Apers (023), our results improve the query complexity from O(1/E") to O(1==²). Similar to their setting, algorithm conduct both vanilla and tolerant property testing. Ignoring the constant factors, for = 0.01, the algorithm of Adriaens & Apers (2023) takes 10 operations, while our algorithm takes 10 operations. Assuming a machine that takes 10
10-10 10 seconds to process one operation, the running time difference between their algorithm and is 2.5 hours less than one second.
Our algorithm is straightforward: we uniformly sample O(1/e) vertices and test on their induced subgraph. The analysis rests on a key insight: if graph is e-far from being clusterable, this property will be evident even in a small, random sample. We achieve this by introducing Janson's 's inequality from the random graph theory, which is novel in analyzing property testing algorithms. The proof Theorem can be found in Appendix
We note that our contribution primarily lies in the analysis rather than the design of the algorithm. Results in the literature have shown that property testing problems for graph problems inherently admit relatively simple algorithms Goldreich Trevisan (2003). Therefore, the crucial and non- trivial part is to conduct better analysis to improve the sample complexity, which is exactly what we did in our paper.
We then investigate the test of clusterability for graphs with k clusters for any integer k 2 2. We obtain the following result.
Fix lo 2 and E E (0,1). There exists a randomized algorithm that given a labeled complete graph G = (V, E -E-) and parameter answers the following
Theorem 2.
If G is k-clusterable, the algorithm always answers "YES":
If G is at least 8-far from being k-clusterable, the algorithm answers "NO" with probability 0.9;
closs-to-kk-custtrabbl the algorithu answers "YES" with prob- addition, i ( ability 2 0.9.
The algorithm queries at most O k" la 24
edges G G and runs in O(k'lu lu k) time.
2
When & is constant, the above gives 0(1/E1) algorithm for testing k-clusterability.

---

Published as a conference paper at ICLR 2026
As far as are aware, Theorem 2 is the first nontrivial algorithm that tests the clusterability for correlation clustering with k clusters. The dependency of & is polynomial in Theorem By a com- mon observation (see, c.g. Bansal et al. (2002; AAdrianss & Apers (023)), the optimal correlation clustering cost could always be approximated by the optimal solution with at most O(1 ((1/e) clusters with (sn?² additive error. Therefore, [heorem 2 also implies testing algorithms with //pol(e)) queries for any meaningful choices of k.
Our algorithm for Theorem 2 is combination of two algorithms: the algorithm used Theorem I and a new algorithm that distinguishes whether a clusterable graph is k-clusterable or e-far from k-clusterable. We show that the second algorithm works even when the input graph close enough to be clusterable. Specifically, when the input graph is c--close to clusterable one, our second algorithm ignores its deviation from its closest clusterable graph with high probability. We prove Theorem 2 formally at (Section 3
We now move on to the special case of i 2, which is mathematically equivalent to the structural balance problem.
Theorem 3. Fix & E 10. There exists a randomized algorithu that given a labeled complete graph G = E E ",,,--UE) and a parameter answers the following
If G balanced, the algorithum always answers "YES":
If G least E-far from being balanced, the algorithi answers "NO" with probability 2 0.9.
The algorithm queries at most O(1/s) edges of G and rums in O(1/e) time.
Theorem 3 uses algorithmic procedures that fairly different from the subroutines in Theorem Theorem 2 Here, instead of sampling a subset of vertices and their induced subgraph, we sample triangles directly. This in particular avoids the quadratic blow-up in Theorem I aand Theorem 2
Similar to our results for general clusterability, our techniques for T'heorem exttend to tolerant test- ing. However, for structural balance, we obtain stronger guarantees: while the previous algorithms require the graph to be O-ee)- to clusterable, here we can distinguish graphs that are 8-close from being balanced (where 5 (e)) versus graphs that are e-far. We refer to Appendix F and Appendix for the formal proof.
Theorem 4. Fix (0, such that 5 < E/9900. There exists a randomized algorithm that given labeled complete graph G = (V, E+ U F-) and parameters E, 8 answers the following
If G is at most 8-close from being balanced, the algorithm answers "YES" with probability 2 0.99;
If G is at least E-far from being balanced, the algorithu answers "NO" with probability 2 0.99.
The algorithm queries at most Ol1/s) edges of G and runs in O(L/e) time.
Finally, we present a lower bound result, showing that 2(1/s) queries are necessary to distinguish graphs that balanced (resp. clusterable) vs. 8-far from being balanced (resp. clusterable).
Theorem 5. Any (possibly randomized) algorithm that given a complete labeled graph G =
(V,E+ U E,), with probability least 2/3 answers correctly whether G is balanced or at least E-far from being balanced requires at least (11/E) edge queries to the graph.
Furthmore, the lower bound extends testing clusterability (for both general ls and fixed k).
Theorem 5) indicates that our results for Theorem 3
and Theorem 4 are asymptotically tight. To the best of our knowledge, this is the first result that obtained tight bounds in the related literature. The proof can be found at Appendix
Experiments. We implement the proposed algorithms and evaluate them on synthetic and real- world datasets. Our algorithms demonstrate favorable efficiency in both the query complexity and the running time. For structural balance testing on graphs of size 1000, our algorithm shows reduction factor of 15 on query complexity and roughly 10a on the running time, comparing to Adriaens & Apers 2023). Our implementation is available on Anonymous Githut
4

---

Published as a conference paper at ICLR 2026
Further Comparison with Related Work. In addition to the adjacency matrix query model, Adri- aens & Apers 2023) studied another query model based on bounded-degres graphs In this model, the adjacency list cannot directly query neighbors. Instead, they only allow queries in the form of tuples (u, i), where i is an integer in [n]. The answer is the i-th neighbor if i S deg( or other- wise. The queries in that model are inherently harder, and their query bounds are O ((vn/poly(E)) While there are interesting applications the bounded-degree model, these results are not directly comparable to ours.
The bulk of the literature in structural balance and correlation clustering has focused on computing the clustering, i.c., the partition of vertices. To this end, there are several popular techniques. includ- ing linear programming (Chawla et al. (2013); Cdden-AAdad et al. (2022) 2023); Cao et al. (2024). pivot-based algorithms (Ailon et al. ( (2008); g Makarychev & Chakrabarty (2023); Dalirrooyfrrd et al. (2024); Cambus et al. (2024); Dalirrooyfard et al. (2023)). and agreement decomposition (Cohen- Addad et al.] (2021): Assadi & Wang] (2022); Cohen-Addad al. (2024a)) However, all of these techniques would need (2(z) time to write down the formulation or the solution, which is much slower than our algorithms. [Assadi al. (2023) made an attempt to combine sampling and some of the above techniques to test the cost of correlation clustering with small space. Their algorithm can be used for our application as well with poly (log n/s) time, which is worse than ours.
PRELIMINARIES
We introduce the definitions and standard techniques related to the results in this section.
Notation. We use G (V, E) to denote a graph, where V is the set of n vertices and E' is a set of labeled complete graph, defined below.
m edges. We focus
Definition (Labeled Complete Graphs), We say G = (V, E+ - is a labeled complete graph if there exists exactly one edge between each vertex pair (u, v), with a label of either (+) (-).
We assume access to labeled adjacency matrix of the graph, defined as follows.
Definition 2 (L.bbeldd Adjaceney Matrix). We say matrix A E [-1,1) is a labeled adjacency matrix of a n-vertex labeled complete graph G = (V, E+ U F-) where A = if (u, v) is (+) edge; and Au,e - if (u, v) is a edge.
We assume we could query any entry of the adjacency matrix in O(1) time. In particular, this also allows us query neighbors, sample edges, and sample triangles in O(1) time.
Correlation clustering and structural balance. On complete labeled graph, we are able to define the problem of (min-disagreement) correlation clustering and structural balance as follows.
Definition 3 (Correlation Clustering). Let G = (V, E+ U ) be a labeled complete graph and let = =C1, C2, ...) be clustering, i.e., partition of the vertices of V into disjoint vertex sets. We define the cost of correlation clustering, cost G, C), as the summation of the number of (+) edges crossing different clusters and the number of (-) edges in the same clusters:
Cost(G.C) == |[ ((,,)) v)
E+ E uUE C,,U C,, i + 5}1 + E E | |u,UE C. for some {}}
We say that G is (perfectly) clusterable if and only if there exists an optimal clustering C* that induces O cost. Besides, we say G is (perfectly) k-clusterable if and only if there exists an optimal clustering C* = (Ci...., Ck) of exactly k (possibly empty) clusters and induces 0 cost. (In other words, C* has at most k non-empty clusters.) Note that a clusterable graph does not restrict the number of clusters, i.e., we can use any number of clusters to minimize the cost. In contrast, peefeeteeuuseteeee clustering with S clusters.
k-clusterable graph must have a perfect
Structural balance is special case of correlation clustering where k 2. More formally, we say that G is (perfectly) balanced if and only if there exists a perfect optimal clustering with 2 clusters that induces 0 correlation clustering cost.
Property Testing for Graphs Close and Far from being Clusterable (Balanced). Similar to typical algorithms in property testing, we allow some "slackness" between the cases: in typical
'In their paper, the adjacency matrix query model is called the "dense graph model" and the adjacency list query model is called "bounded degree mode!".
5

---

Published as a conference paper at ICLR 2026
property testing, the algorithm should return "YES" when the property holds, and "NO" if there a sufficient degree of violations to the property. In between the cases, the algorithm is typically allowed to return anything. To the above end, introduce the notion of the distance for graph from being balanced.
Definition (E-far/close from being clusterable (b-clusttraallebbaaaneee)) Let G = VV,EUu
be labeled complete graph. We say that G is at least E-far (resp., at most E-close) from being clusterable we have to flip the labels of at least e (2) (resp., at most e (²)) edges to make the graph clusterable.
In our work, the above definition distance also apply to the other two distinct properties: k- clusterability and structural balance.
With the above terminologies, graph is most O-far from being clusterable if and only if it is clusterable. For a graph that is E-far from being clusterable (resp., balanced), we also call an edge [u, e) false edge if needs be flipped in the solution that flips the minimum number of edges to make the graph cluterable (resp., balanced). We also define a had triangle as triangle that contains two (+) edges and one (-) edge.
We will also use the following standard form Chernoff bound in our proofs.
Proposition 2.1 (Chernoff bound; Alon & Spencer (2016)). Let X1, X2, X....., X, be independent random variables such that X; E [0, 1J. Let X
Di= X₁. Then, for every > O.
8²
Pr| X E[X] 2 8 [[X]] < exp (-
[[X]
2 2
We will also use Janson's inequality Janson et al. (201T) from random graph analysis, to prove our Theorem Please refer to Appendix D for its formal statement and brief explanation.
UPPER BOUND FOR TESTING l-- CLUSTERABILITY
We showcase our algorithm results by presenting the upper bound for testing k-clusterability, there- fore proving Theorem 2
Our algorithm for k-clusterability utilizes the algorithm for testing clusterability in Appendix D in black-box way; and is self-containes In fact, our proof implies that given any algorithm for testing clusterability running in t(E) 2 1/vE time, there is algorithm for testing k-clusterability running in O(I(E2)) time, for every constant k.
Theorem 2. Fix k 2 2 and E (0,1). There exists a randomized algorithm that given a labeled complete graph = (V, E UE") and parameter e answers the following
G is k-clusterable, the algorithm always answers "YES";
If G is at least E-far from being k-clusterable, the algorithm answers "NO" with probability 2 0.9;
In addition, if is 10
closs--oo-k-chusterabbe the algorithun answers "YES" with prob-
ability 2 0.9.
The algorithm queries at most O k2 In edges of G and runs in O k* In time.
Our algorithm is combination of two one-sided-erroe algorithms, one for testing whether the graph clusterable (Algorithm 3), another for testing whether a close-t-ccusttrrable graph is k-clusterable. When the input graph is far from k-clusterable, at least of the two algorithms will output "NO" with high probability.
We start by introducing and analyzing the second algorithm under the assumption that the input graph is clusterable. Then we show that the algorithm also works for graphs that are close enough to be clusterable.

---

Published as a conference paper at ICLR 2026
An algorithm that distinguishes clusterable graphs from h-clusterable graphs Input: A labeled complete graph G = (V, E+ U LT) that is clusterable
Algorithm| 1.
1. Sample subset S of min (100 & ,n) vertices from V uniformly at random (with replacement).
2. Maintain subsets ,i,...,5p of S. Initially, all the sets are empty.
3. For each vertex S and each i E (1....,A) k)) query if (u, v) E E+ where is an arbitrary vertex from S.
For the first time when positive edge is discovered between u and a vertex in Sj, add u to Sq..
If u has no positive edge to any of the subsets S, add u to an empty subset Sy. In addition, if there is empty subset that u can add to, return "NO".
6. After iterating all the vertices in S, return "YES".
"We assume for now that G is clusterable. And we will show that with high probability a random subgraph of G will still be clusterable when G is close-enough-to -o-cuustrraab,: and the algorithm cannot distinguish the two cases, See Lemma 3.2 for details.
Lemma 3.1. Fix parameters and E (0, 1). Given labeled complete graph G = (V, E E-), Algorithm answers as follows
If G k-clusterable, the algorithm always answers "YES";
If G is clusterable but is at least from being k-clusterable, the algorithm answers "NO" with probability 2 9/10:
addition, if G is (10 1n2
22
-llos-tto-k-ccussteabble the algorithm answers "YES" with prob-
ability 99/100.
Besides, Algorithm queries at most O In edges of G and runs Ö 11 time.
We defer the proof to Lemma 3.1 to Appendix C Our analysis relies on the fact that the input
graph is clusterable. However, we will show that when the input graph is (8 (8:= g2 clusterable but e-far from k-clusterable, the above algorithm still works with high probability. Intuitively, when the input graph guaranteed to be 8-close to clusterable, a random O( & -isize subgraph will not contain any false edge with high probability. This observation formalized the following lemma.
T0 -close
Lemma 3.2. Fix 5 E (0,1), 1). Given labeled complete graphs G (V, E+ U E-) and G' EV UE") such that G' is obtained by flipping most (2) edges from G. Let S a subset of vertices from V selected uniformly at random (with replacement). Let Gs, G's denote the induced
subgraph by the sampled vertices. If < 10/6'
Pr[Gs G'sl 2 99/100.
Proof. We show by union bound that with > 99/100 probability the sampled subgraph does not contain any edge in G", the edges with labels flipped G to obtain G'.
For every single edge in G - G', this edge is sampled with probability at most
IsKKiS n 8/nnn.
Σ
2.215
where the factor of 2 counts for the same edge (u, v) of different orders (u is sampled the i-th place, v is sampled at the j-th place; vice versa). Summing over all the < (()) edges in G G², the probability that any of the edges from G - G' is sampled is at most
2
n
n S 1/100.
2

---

Published as a conference paper at ICLR 2026
Now we formally give and analyze the algorithm that combines Algorithm 3 and Algorithm I to- gether.
Algorithm 2. An algorithm for testing k-clusterability
Input: A labeled complete graph G (V, E U EE)), parameter
1. Independently run Algorithm with parameter == I0 twice. If Algorithm 3 ever answers "NO", return "NO":
Independently run Algorithm with parameter e/2 twice. Algorithm I ever answers "NO", return "NO";
3. If all the above simulations answer "YES", return "YES".
We claim that Algorithm 2 is the desired algorithm that distinguishes whether a graph is k-clusterable or e-far from k-clusterable.
Proof to Theorem 2
The query complexity and the time complexity of Algorithm 2 are dominated by calling Algorithm twice, which costs O(* k queries and time.
Given a graph that is k-clusterable, by Theorem and Lemma 3.1 the algorithm will always an-
swer "YES". In addition, by Lemma 3.2 for a graph G that [10204* In -osoos--t---clusterallt
Algorithm (sampled 200 lank vertices) and Algorithm (sampled =0²²2² x2 vertices) will return :- "YES" with probability 2 99/100. By union bound, the final output "YES" with probability
2 0.9.
If the graph is 8-far from clusterable, Theorem guarantees that the answer will be "NO" with 2 9/10 probability. The remaining case is when the input graph G is
but -far-ffrom-b-ccuutterblll Assume G' to be the clusterable graph obtained by flipping most ō (?) edges of G. By Lemma 3.2 Algorithm returns the testing answer of G' with 2 99 100 probability. By Lemma 3.1 Algorithm returns "NO" with probability 2 89/100 given G.
In this case, the probability that all the tests fail is most < 0.112 0.1. Therefore, Algorithm 2 outputs "NO" with 2 9/10 probability when the input is e-far from being k-clusterable.
4 EXPERIMENTS
We assess the empirical performance of testing correlation clustering with three proposed algo- rithms: AAlgorihhm 3 for clustering with general k, Algorithmm for clustering with fixed k; and Algorithm foror structural balance. The evaluation metrics include query complexity, running time and testing accuracy in practice. There exists only one baseline from prior work Adriaens Apers 2023), where the tester for structural balance in the adjacency matrix query model is implemented.
Setup. Since the CC problem is NP-hard, obtaining the ground-truth s-farness becomes a challenge. To address this. we generate synthetic graphs based on 6 different perturbation schemes to the well-clustered signed graph such that the optimal cost and the number of clusters are tractable. We explain them in Appendix B Together with the balanced/0-cost case, we use these synthetic graphs 7 scenarios (in total 140 instances) for experiments. Some basic statistics are shown in Table 2 For structural balance experiments, we set = 1000 and A = 2. To facilitate testing real-world graphs, we use the spectral frustration index to obtain an approximation with respect to testing structural balance. We also demonstrate the spectrum of testing outcome increases from 0.05 to 0.5, for both structural balance and general CC testing.
the ground truth s- e-farness
Table 2: Synthetic Signed Graphs and Ground Truth ε used in CC testing experiments
Model
Pure
Uniform-noise
Hetero-noise
Cycle
Half-flip
Cluster-swap
Mixed-flip
size
Range
0.32 ~ 0.49
0.28 ~ 0.42
0.30
0.30 ~ 0.38
0.25
0.4
5000
5
8

---

Published as a conference paper at ICLR 2026
4.1 TESTING ON SYNTHETIC GRAPHS
With ground truth e, we are able to report the testing accuracy for synthetic graphs. All of our testers are one-sided, therefore the accuracy defined as the percentage of the correct output of "YES/No" corresponding to the label of balance or not. Note that our algorithms use large constants for the convenience of proof, practice we only make at most 3 unless mentioned otherwise.
Table 3: Testing Performance with & = 0.1
Algorithm
Accuracy
Query Complexity (# sampled edges)
Running Time (s/graph)
Test CC (general R0 Algorithm
1.0
10000
23.8
CC (fixed Algorihm
1610
22.5
Test Structural Balance. Algonihim 4
1.0
60
1.3 10
Test Structural Balance, Adriaens & Apers 2023
1.0
900
1.1
Table 3 shows that our algorithms for testing CC and structural balance yield favorable efficiency on query complexity and running time. For testing structural balance, comparing to Adriaens & Apers 2023), our algorithm requires significantly smaller sampling size and runtime. For testing CC with fixed k, we collect results for k = 3, 4, 5 on "pure" model graphs. Finally, all algorithms give testing accuracy I, showing the effectiveness of the algorithms, thus corroborate with the theoretical results.
We next demonstrate the performance on the same set of metrics as e increases from 0.05 to 0.5 for structural balance in Figure Two algorithms are similar accuracy, which has small fluctuations but remains higher than 0.95. But for efficiency. we observe that Algorithm outperforms the baseline a algorithm by a large margin, especially when is small. Runding fire Texting Seractanl Dalones varing
S040V10
Figure 1: Performance on structural balance testing with varying s.
Scalability. The theoretical results show that the query complexity does not involve the size of graph. Therefore it is conceivable that the algorithms are scalable. We examine this issue in practice, by showcasing the performance of Algorrthhm 3 for testing CC as n scales up to 50000. Table 4 demonstrates that the testing algorithm itself still executes efficiently, however the entire program involving processes such sampling, may become prohibitive in practice scales.
Table 4: Running Time of CC testing with e = 0.1
Graph size
10000
20000
30000
40000
50000
Testing Algorithm Runtime
0.011
0.013
0.015
0.17
0.20
Total Runtime (lug)
4.51
6,36
7.81
9.89
12.03
4.2 TESTING ON REAL-WORLD GRAPHS
We move forward evaluating Algorithm 3 and Algorithm 4/ real-world graphs selected from the SNAP p The datasets encompass social, financial, collaboration and communication networks, with varying sizes between 500 and 10000. In the experiments with real-world graphs, we treat the edges in the graphs as (+) edges and the non-edge vertex pairs as (-) edges. The reduction suits well for our datasets, where the (-) relationships (e.g., no message exchanges) can be directly inferred from the (+) relationships (e.g.. has message exchanges). We illustrate the spectrum the testing output for both tasks, as ε increases from 0.05 to 0.5 in Figure 2] Although
the labels missing, we are able to approximate the structural balance frustration index using the
For practicability we test the scenario: the input graph is clusterable but not clear if k--lluterable https::/ wttp:aapp....saaoooooeeeeeeettt.

---

Published as a conference paper at ICLR 2026
smallest eigenvalue of the signed Laplacian matrix Kunegis al. (0010). We then obtain an e' as lower bound of the ground truth E, which is a signal of the testing correctness.
Congest coorse with spalorr
Calagge cissse of seperaaatii
Biaan Ontteet edt Vorrng spaie
Figure 2:
Testing output for all real-world graphs. Results are averaged on 20 repeated runs. The dotted light blue vertical line shows the lower bound of the true e.
First, we observe from Figure that all testing results transits from "NO" to "YES". Structural balance has clearer phase transition structure than correlation clustering. and the transition happens right after the estimated e lower bound, which is supporting evidence of the testing accuracy. In other words, initially, both algorithms report "not balanced" (resp. "not clusterable") due to the fact that value is very small, and the condition to pass the test is very stringent. As increase the value e, the algorithm demonstrates a "tolerate test" property such that it allows the graph to be report "balanced" (resp. "clusterable") when the graphs are relatively close to being balanced (resp. clusterable) with the given e parameter.
All experiments take very short time (< 0.1s), showing the potential of our algorithms in real- world applications. Another interesting observation that many (in our case, all) real-world graphs have e-farness with ε S 0.3.
DISCUSSION AND CONCLUSION
While our testing algorithm for structural balance tight, our algorithms for testing clusterability do not yet match the lower bounds. It remains an intriguing open problem to determine the correct complexity of testing clusterability. Notably, our proof suggests that improving the testing algorithm for clusterability will also yield a better algorithm for testing k-clusterability. We also remark that more efficient algorithms for testing clusterability exist, it must be substaintially different algo- rithm than ours, because our analysis of Algorithm is tight. More concretely, one can construct input graphs where the algorithm must sample 12(1/e) vertices to observe non-clusterable local structure, which requires 12(1=²)) queries.
Our analysis of using Janson's 's inequality may also be of independent interest. It outperforms the classic analysis using the graph removal lemma in the labeled graphs, and provides a more fine- grained way of analyzing subgraph testing algorithms. Our proof technique may find broader appli- cations in analyzing property testing algorithms.
Another future direction would be to generalize our results to general labeled graphs, where only a subset of all (7) edges labeled. This setting is more aligned with real-world applications, but it poses a significant challenge: our algorithms fundamentally rely on detecting local patterns, such as inconsistent triangles. In a sparse graph, a graph that is globally far from being clusterable may not contain any such local witnesses, rendering our current approach ineffective.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENT
The authors would like thank Vikrant Ashvinkumar for insightful discussions and anonymous ICLR reviewers for valuable feedback. Deng and Gao would like to acknowledge funding support from NSF through CCF-21119553 DMS-2311064, DMS-2220271, I1S-2229876, and CNS-2515159,
USAGE OF GENAT
We use GenAl check typos and writings in the paper.
REFERENCES
Florian Adriaens and Simon Apers. Testing cluster properties of signed graphs. In Ying Ding, Jie Tang. Juan F. Sequeda, Lora Aroyo, Carlos Castillo, and Geert-Jan Houben (eds.). Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 4 May 2023, pp. URL https: wttp:////.o..r/....o.eoe//o/oo 1145/
49 19-59. ACM, 2023. doi: 10.1 10.1145/3543307.335822
3543507. 3583213
Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering, J. ACM, 55(5):23: 2008. doi: 10.1145/441150011111511 https::::
Noga Alon and Joel H Spencer. The probabilistic method. John Wiley & Sons, 2016.
Noga Alon, W Fernandez De La Vega, Ravi Kannan, and Marek Karpinski. Random sampling and approximation of MAX-CSPs. Journal of computer and system sciences, 67(2)2212-243, 2003.
Gunnar Andersson and Lars Engebretsen. Property testers for dense constraint satisfaction programs on finite domains. Random Structures & Algorithms, 21(1):14-3) 2002.
Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, and Chen Wang. Evaluating stability in massive social networks: Efficient streaming algorithms for structural balance. In Nicole Megow and Adam D. Smith (eds.). Approximation, Randomization, and Combinatorial Optimization. Algorithums and Techniques, APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA, volume 275 of LIPlcs, pp. 58:1-58:23, Schloss Dagstuhl Leibniz- Zentrum für Informatik, 2023. doi: 10.4230/LIPICS APPROX/RANDOM.222.... https://doi... oww.llo.orgggn
URL
APPROX/ RANDOM. 2023. 58
Sepehr Assadi and Chen Wang. Sublinear time and space algorithms for correlation clustering via sparse-dense decompositions. Mark Braverman (ed.), 13th Innovations in Theoretical Com- puter Science Conference, ITCS 2022, January 31 February 3, 2022, Berkeley, CA, USA, vol- ume 215 L.PIcs, pp. 10:1-10:20. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2022. doi: 1..4230WLPICS.IICSS..00 2022.10
URL httpt: httptttst///oio//ettss http::////oo.../1..1222222 wtt.://///..........2... www.422210/L...... ITCS.
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 (eds.), Advances in Neu- ral Information Processing Systems 36: Annual Conference Neural Information Pro- cessing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. URL http::
wwtpss//pppeee/2///222aaaaas 2023/hash/hh////// html
Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. In 43rd Symposiun on Foundations of Computer Science. FOCS 2002, Vancouver, BC, Canada, November 16-19, 2002, Proceedings, pp. 238. IEEE Computer Society, 2002. doi: 10. 10..10//SSS.20021188800
URL.
https://doo httgg//..109//FCS..
1111111099FS. 2002. 1181947
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, and Dana Ron. Tolerant junta testing and the connection to submodular optimization and function isomorphism. ACM Trans. Comput. The-
ory, 1144))24:1 1-2:333, 2019. doi: 10.1145/3337789 URL actps: ://oci. orq/10.1145/
8637788

---

Published as a conference paper at ICLR 2026
Francesco Bonchi. David Garcia-Soriano, and Konstantin Kutzkov. Local correlation clustering. CoRR, abs/1312.5105, 2013. URL/att:://axxi/ wrg. abs 5105
Nader H Bshouty and Oded Goldreich. On properties that are non-trivial to test. In Computational Complexity and Local Algorithms: On the Interplay Between Randomness and Computation, pp- 383-387. Springer, 2025.
Mélanie Cambus, Fabian Kuhn, Etna Lindy, Shreyas Pai, and Jara Uitto. A (3 + e)-approximate correlation clustering algorithm in dynamic streams. In David P. Woodruff (ed.), Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pp. 2861-2880. SIAM, 2024. doi: 11177/997811119777122 attps:://ooi..o//0..1111
URL
Nairen Cao, Vincent Cohen-Addad, Fuiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl. Un- derstanding the cluster linear program for correlation clustering. In Bojan Mohar, Igor Shinkar, and Ryan O' O'Donnell (eds.), Proceedings of the 56th Annual ACM Symposium on Theory of Com- puting, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pp. 1605-1616, ACM, 2024. doi: URL http::: /tops:///ol.. org/ 10. 1141/ 010444//611666 3649749
10.1145/3618266 118.6661660..97499
Nairen Cao, Vincent Cohen-Addad Euiwoong Lee, Shi Li, David Rasmussen Loick, Alantha New- man, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang. Solving the correlation cluster LP in sublinear time. In Michal Koucký and Nikhil Bansal (eds.), Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pp. 1154-1165. ACM, 2025. doi: 10.1145/371782337718888 URL https:
7/doi //doi.org//11 10. 1145/3717825 33788881
Dorwin Cartwright and Frank Harary. Structural balance: generalization of Heider's theory. Psy- chol. Rev., 63(5):277-293, September 1956.
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In Rocco A. Servedio and Ronitt Rubinfeld (eds.). Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, doi: 00.11457746399.746666 URL https::: http///i..ggg////
pp. 219 228. 1145/2746533 2746604]
ACM, 2015.
Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh. (quantum) complexity of testing signed graph clusterability. In Frédéric Magniez and Alex Bredariol Grilo (eds.), 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, Septem- ber 9-13, 2024, Okinawa, Japan, volume 310 of LIPIcs, pp. 8:1-8: Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2024. doi: 10.4330LIPICS.TCC.2222 7/doi. 10.00//000000 4230/ TOC. 2024.8
URL https:
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 (eds.), Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pp. 2069 2078. PMLR, 2021. URLhttp:: petttp:/prooced// ngs ml wtt..pprressvvv// cohen-addad2 bb.ba.dd2bb.... html
Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman. Correlation clustering with Sherali- Adams. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 November 3, 2022, pp. 651-661, IEEE, 2022. doi: 10. DT0DCSS54457.0222000666 URL https:://dot wro.orggg//... /10. 1119/ - 20N.C55554552222222.. 2022. 00068
Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman. Handling correlated rounding error via preclustering: A 1.73-aprroximation for correlation clustering. In 64th IEEE Annual Symposium on Foundations Computer Science, FOCS 2023. Santa Cruz, CA. USA, November 6-9, 2023, pp. 1082-1104. IEEE, 2023, doi: 10. 0001109/FOC35799922200000 7/doi. 1ttbli.orrr1..1110////0553513990
URL https:
00065
12

---

Published as a conference paper at ICLR 2026
Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis. Dynamic cor- relation clustering in sublinear update time. In Forty-first International Conference on Ma- chine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024a. URL net wwwpteet////roooooooooooeooo (orrumm21--3G6555.bmm
Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipezuk, Mikkel Thorup. Shuyi Yan, and Hanwen Zhang. Combinatorial correlation clustering. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell (eds.), Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Camada, June 24-28, 2024, pp. 1617-1628. ACM, 2024b. doi: 3649771
(0,1144536182603349999
Mina Dalirrooyfard, Konstantin Makarychev, and Slobodan Mitrovic. Pruned pivot: Correlation clustering algorithm for dynamic, parallel, and local computation models. In Forty-first Interna- fional Conference Machine Learming, ICML 2024, Vienna, Austria, July 21-27, 2024. Open- net
Review.net, 2024. URL.htttss:/oppeeerr http://iwwe...eee/ooomeee1/--as meet/forummddd=s=2225
Mina fali,,ooyfard, Konstantin Makarychev, and Slobodan Mitrović. Sparse-pivot: Dynamic cor- relation clustering for node insertions. In Forty-second International Conference on Machine Learning (ICMI.), 2025. 2025.
James A Davis. Clustering and structural balance in graphs. Human relations, 20(2):181-187, 1967.
Eldar Fischer. A basic lower bound for property testing. CoRR, abx/2403.04999 2024. doi: 10. 48550/ARRXIV2400.049999 URL httphhtsss://oo.....
Jacob Fox. A new proof of the graph removal lemma. Annals of Mathematics, pp. 561-579, 2011.
Oded Goldreich and Luca Trevisan. Three theorems regarding testing graph properties. Random Structures & Algorithms, 23(1):23-57, 2003.
Fritz Heider. Attitudes and cognitive organization. Psychol., 21:107-112, January 1946.
Fritz Heider. The Psychology of Interpersonal Relations. Psychology Press, 1982.
Jack P. Hou, Amin Emad, Gregory J. Puleo, Jian Ma, and Olgica Milenkovic, A new correlation clus- tering method for cancer mutation analysis. Bioinform. 32(24)3317-33728 2016. doi: 10. 1091/ BIOINFORMATICS/BTWSSSS URL
btw546
Svante Janson, Tomasz Luczak, and Andrzej Rucinski. Random graphs. John Wiley & Sons, 2011.
Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, and Chang Dong Yoo. Higher-order correlation clustering for image segmentation. John Shawe-Taylor Richard S. Zemel, Pe- ter L. Bartlett, Fernando C. N. Pereira, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Process- ing Systems 2011. Proceedings of a meeting held 12-14 December 2011, Granada, Spain, pp- 1530, 2011. URL http::ttt//tttt http::://ooooeeddeee / htt.://aaabbbbbbbbbbbbb
nwwrips CC/ htts//ppp/22211/haaeee
Abbt-bbbbbbbbbbrttttt.a. html
Abstract
Jérôme Kunegis, Stephan Schmidt, Andreas Lommatzsch, Jürgen Lerner, Ernesto De Luca, and Sahin Albayrak. Spectral analysis of signed graphs for clustering, prediction and visualization. In Proceedings of the 2010 SIAM international conference on data mining, pp. 559-570. SIAM, 2010.
Konstantin Makarychev and Sayak Chakrabarty. Single-pass pivot algorithm for corre- lation clustering. keep simple!
Alice Oh, Tristan Naumann, Amir Glober- son, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advances in Neural In- formation Processing Systems 36: Annual Conference on Neural Information Pro- cessing Systems 2023, NeurIPS 2023, New Orleans, LA, USA. December 10 16, 2023, 2023. URL http::/ www.:/errr.iissccc.ooo http::/p.....ppapeeeeeee///////a
html
13

---

Published as a conference paper at ICLR 2026
Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approxi- mation. J. Comput. Syst. Sci., 7266):0122-104, 2006. doi: 10. 10.1016/.JCCSS.2206.....20 URL
https:://boi.org/0000 1ttp://1..1111111111 200 03.002
Dana Ron. Algorithmic and analysis techniques in property testing. Found. Trends Theor Comput.
Sci., 5(2):73-205, 2009.
doi: 10.1561/0400000002.. URI. https: //tt/////...oo/ .org/ 0rgg10.11611
0400000029
Imre Ruzsa and Endre Szemerédi. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18(939-945):2, 1978.
Jessica Shi, Laxman Dhulipala, David Eisenstat, Jakub Lacki, and Vahab S. Mirrokni. Scalable community detection via parallel correlation clustering. Proc. VLDB Endow, 14(11):2355-2133 2021. doi: 10. 10.14778/3472249.44776 p2305-shi s.i.0sshh.p...... pdf
URL http://www vldb. http./ooo/////o/..//....
Christian Sohler. Almost optimal canonical property testers for satisfiability. In 53rd Annual IEEE Symposium Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 20/2, pp. 541-550. IEEE Computer Society, 2012. doi: 10.1109/FOCS. URL https: http:/doi..e org. 1109 FOCS 2012. 59
Nate Veldt, David F. Gleich, and Anthony Wirth. A correlation clustering framework for community detection. In Pierre-Antoine Champin, Fabien Gandon, Mounia Lalmas, and Panagiotis G. Ipeiro- tis (eds.), Proceedings of the 2018 World Wide Web Conference on World Wide Web, wWW 2018, Lyon, France, April 23-27, 2018 pp. 439 448. ACM, 2018. doi: 10.1145/118876.3186611 URL https: //t::/ddo... doi org 10. 1145/ 31 88 6. 3186110
Julian Yarkony, Alexander Ihler, and Charless Fowlkes. Fast planar correlation clustering for im- age segmentation. In Andrew W. Fitzgibhon, Svetlana Lazebnik, Pietro Perona, Yoichi Sato, and Cordelia Schmid (eds.), Computer Vision ECCV 2012 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 20/2, Proceedings. Part VI, volume 7577 of Lecture Notes URL
in Computer Science, pp. 568-581 Springer, 2012. doi:
https::/doi... org.10...01000 wwt.:r/./............. 1007/970 3 642 33783-33223
A MORE DISCUSSIONS ON RELATED WORK
As discussed, the bulk of the literature in structural balance and correlation clustering has focused on computing the clustering, i.e., the partition of vertices. To this end, there are several popular techniques. including linear programming (Chawla al. Cohen-Aaadd al. 2002 2023);
Cao et al. (2024). pivot-based algorithms (Ailon et al. (2008); Makarychev & Chakrabarty 2023 ); Dalirrooyfard al. (2024); Cambus et al. (2024); Dalirrooyfard
al. (2025)), and agreement de- composition (Cohen-Addad et al.] (2021): Assadi & Wang (2022); [Chen et al. (2024a)). However, all of these technique would need [?()) time write down the formulation or the solu- tion, which is much slower than our algorithms. Assadi et al. (2023) made an attempt to combine sampling and some of the above techniques test cost of correlation clustering with small spuce. Their algorithm can be used for application well with poly(log n/z) time, which is worse than ours.
The problem of testing whether graph is clusterable (resp. balanced) is related to the MAX-CSP formulation. In the generic r-MAX-CSP problem, we are given m boolean functions, and each of the function uses most variables. Alon et al. (203) provided generic framework that approximates the number of satisfiable functions by querying O sx of testing structural balance and clusterability, we define Boolean variable for each vertex, and for each edge e = (u, v) E E we define a function fo that encodes the "right assignment" the vertex variables with respect to the label of the edge: f is satisfied if (u, v) E E+ and are in the same cluster or (u, v) E E and ut are in different clusters. is easy to see for this application, we have = 2, which induces additive error of zn?: this satisfies the definition of e-far from being balanced and/or clusterable. However, such a strategy leads to the algorithm in Adriaens & Apers (2023) which gives suboptimal bounds.
log variables. the problem
14

---

Published as a conference paper at ICLR 2026
B MORE DETAILS ON EXPERIMENTS
All of our experiments are implemented with Intel Core i9 CPU of 32GB memory, no GPU is required. Now we introduce the synthetic graph generation models. For the "good" case, the gener- ation is straightforward: create & clusters first, put every edge inside each cluster with positive sign and vice versa. Below shows perturbation for graphs in potential "bad" case, namely the optimal cost is large.
Uniform Noise: Each sign flipped with uniform probability p E [0.3, 0.5].
Heterogeneous Noise: The signs intra-cluster edges (+1) are flipped with probability
Pin E [0.2, 0.4), while the signs of inter-cluster edges (-1) are flipped with probability Pout E [0.3, 0.5).
Cycle: The clusters are arranged in a cycle. Ideal edges are set to +1 if they are within cluster or between adjacent clusters in the cycle, and -1 otherwise. All edge signs are then flipped with a 30% probability.
Half Flip: One cluster is chosen at random. The sign of every edge incident to this chosen cluster then flipped with a 50% probability.
Cluster Swap: One cluster is chosen at random, for half of its nodes, the signs of all edges connecting them any node outside the original cluster are flipped.
Mixed Flip: flip 40% edge signs inside each cluster, and 40% across clusters
Signed Laplacian and spectral approximation frustration. Denote the frustration index as f(G). Let W T denote the signed adjacency matrix of graph on n nodes, where Waj E {-1,0,+)) +13 (or more generally real weights, but not in our context). Define the absolute degree d; Ej juayl. and let D diag(d,, ...., d.). The signed Laplacian is
D W.
For any assignment æ E [+13" one has the identity
x T Lx
Σ
wayl (r, sign(w;))
When Wiy E {=1} this reduces to
LL 4 of frustrated edges under assignment æ).
Thus minimizing x La over [11)" is equivalent to computing f(G). By the Rayleigh- Ritz prin- ciple.
Ly
Amin (L)
min
y70
1/
For any {+1} vector x, since ||=||2 = n, we obtain
x La
4f(x)
T
where f(x) is the number of frustrated edges under æ. Minimizing over all x yields
Amin (L) < 4f(G)
Equivalently,
f(G) 2 Amin (L).
Hence the scaled smallest eigenvalue @ (L)in() provides computable spectral lower bound on the frustration index. This is known as the spectral approximation of the frustration index, and it has been used tractable proxy for quantifying balance in signed networks Kunegis al. (2010).
15

---

Published as a conference paper at ICLR 2026
C MISSING PROOF TO LEMMA 3.1
Proof to Lemma 3.7 The time and query complexity of Algorithm
is clear. It samples O ( vertices. For each iterated vertex will perform most & queries. The total number of queries is addition, maintaining the subsets costs time Ō 1(k1In))
0 In
lonk
Given a k-clusterable graph G. Any induced subgraph of G can be partitioned into at most & clus- c²
ters.
Algorithm
will always output "YES". Given a 10012 in -close-to-k clusterable graph, by Algorithm
Lemma
3.2
will output "YES" with probability 2 99/100.
Given graph G' that is clusterable but E-far from k-clusterable. Let be the number of clusters in G. G can be characterized by list of cluster sizes ($1, ($1)...,8:) where E 8 Without loss of generality, we assume
81 82
8t-
In addition, may assume that k, since otherwise graph of clusters is also k-clusterable, by appending empty clusters.
Let = n Ei= 8,. Then 2 sn/2, or otherwise we can make G a k-clusterable graph by merging the last & clusters into the first cluster, which costs < r(n r) < =(()) flips.
When 9 2 sn the largest & clusters are large enough, and the subset S contains vertices from all 20K the largest & clusters and a vertex from the last t k clusters with high probability. Formally, by union bound, the probability that any of the first clusters the union of the last r vertices does not have vertices in S is at most
k+1
k+1
Σ i=1
+(1-8)*
Σ
exp
S ex+ (-5 S 1/10.
20k
20k
20k:
In this case, with 2 9/10 probability the sampled subset contains an independent set (i.e., with no positive edges in between) of size 2 k and the algorithm outputs "NO".
When 8; < sn
20k we know 8, S Sk <
en for any j 2 k since the clusters are sorted decreasing 20k
order of size. In this case call all clusters but the largest & as small clusters. Since 2 en/2, the number of small clusters is at least _ 2 10k. We show that with high probability the sample set S includes vertices from 2 k + different small clusters.
Let XI,..., E {0, 1} be random bits indicating whether each sample covers small cluster that is never sampled in its previous samples, and let X Ein X; be their sum. For every i {1.....$) s}. have
k
en 10k
Pr X,
Σ
X1 <
k
> 0.4s.
n
Let YI...., {0,1) be independent random bits where Pr[Y, 1] 0.4s for each Y,, and Y
their sum. Then the sum of (X₂) is dominated by the sum of (Y: 7 Note that E = 0.4ss = 40k In By applying the Chernoff bound (Proposition 2.1 and setting
ao we have
Pr[X < k] < Pr[y= < k] < 2. exp 22
< 2 exp( 12k In k)) < 1/10.
To conclude, in both cases, Algorithm can sample an independent set of size 2 k + 1 and output "NO" with high probability.
D PRELIMINARIES ON JANSON'S INEQUALITY
In this section, we briefly review Janson's inequality, a fundamental tool from the probabilistic method. We employ this incquality in our analysis (Lemma E.2 and the proof of Theorem I) to
This also be shown by standard coupling argument.
16

---

Published as a conference paper at ICLR 2026
bound the probability that sum of dependent yet structured indicator random variables equals zero. While the standard Chernoff bound applies to sums of independent random variables, Janson's inequality provides strong bounds for sums of variables that exhibit local dependencies.
Lemma D.I. (Janson's s inequality; c.f. Janson et al.
(011)) Let > 1 be inleger. Let T be with independent probability pt.
random subset of [ni] such that for each E [n], i EL
Let R be family of subsets of [n]. For every A E R. let IA be the indicator random variable such that IA = if and only if A S 1, and A otherwise. Let X be the random variable denoting the number of sets in R that are subsets of Then
X+ (+22) )
A2
Pr[X =0 S exp min (
where À = B[X] and A EABERAARAA E[LABB]
Relevance to our analysis. In our proofs, we frequently search for a "witness" structure (such as a negative edge connected by positive path) within the induced subgraph of sampled vertices. Since multiple potential witnesses may share vertices, their appearances are not independent. Janson's inequality allows lower-bound the probability of finding at least one such witness by controlling the overlapping term A. Specifically, when A is small relative to X, the bound behaves similarly the Chernoff bound (ez e ^>)); when correlations are high (A A), the probability decays as e A2/22
E AN IMPROVED ALGORITHM FOR TESTING CLUSTERABILITY
We present the algorithm for testing general clusterability using 0(1/=²) time and queries in this section. We first recall the statement of the result.
Theorem 1. Fix & 10. There exists randomized algorithm that given labeled complete graph G = EV,E-U UEE) and a parameter answers with the following rules
G is clusterable, the algorithm always answers "YES";
If G least e-far from being clusterable, the algorithm answers "NO" with probability 2 0.9;
If G C. --cooe being clusterable for some small constant C, the algorithm answers "YES" with probability > 0.9.
The algorithm queries at most O(1/s²) edges of G and runs in O(L/s²) time.
While standard combinatorial arguments often use the graph removal lemma, a direct application of Fox's 's colored graph removal lemma only vields an upper bound of Ö(tower(logl 1/e)) for testing trianggl-freeeess bad-triangle freeness Ruzsa & Szemerédi (978); Fox 10; Adriaens & Apers (2023 Besides,
reduction to the MAX-CSP problem also gives two-sided error algorithm of O /=7) query
complexity and exp(((1/e²)) running time Andersson & Engebretsen (2002): Adriaens & Apers (2023).
We overcome this limitation by employing Janson's inequality, classic tool from random graph theory, to constructively demonstrate the existence of bad triangles in a small sample, which we will define later. To the best of our knowledge, this is also the first time Janson's inequality used in analyzing property testing algorithms. Our proof may be of independent interest. Compared to the algorithm in Adriaens & Apers (202)). our work provides one-sided error algorithm, drastically improving both the query complexity and the running time to (11/a²).
Our algorithm is simple: we sample O(1/E) vertices, query their induced subgraph, and check whether there is any inconsistency.
'The towering function tower(æ) denotes a tower of 2's of height x, i.c., 2-to-the-2-to-the t-thhe---otte....too---ff times. Thus, ((tower(log(1/e)) is much larger than 1 1/poly(s). In fact, tower(6) is more than the estimated number of elementary particles in the observable universe.
17

---

Suppose for the sake of contradiction that G' does not Published as a conference paper at ICLR 2026
Algorithm 3.
An algorithm for testing clusterability
Input: A labeled complete graph G = (V, E+ U UE);; parameter E.
Sample a subset S of = min(109/e, ni) vertices from V uniformly at random (without
replacement).
2. Let Gs be the complete subgraph induced by the sampled vertices.
Run breadth-first search (BFS) to check whether Gş contains bad triangles, i.e., a triangle (u, v), (u, w), (u, w) among which exactly two edges are (+) and one edge is (-). If Gs contains no bad triangle, return "YES". Otherwise, return "NO".
Specifically, we run BFS on the positive edges of the subgraph Gs and check if they form set of vertex-disjoint complete subgraphs. which costs O(1/s²) time.
For clusterable graphs, by proposition E. the algorithm will always output "YES". We show that for every graph that e-far from being clusterable, the algorithm will output "NO" with 2 9/10 probability. In addition, instead of showing that the algorithm can find bad triangles with high probability, we analyze a similar pattern of subgraphs, which will simplify our analysis.
Proposition E.1. Given complete labeled graph = (V, E E. The following three condi- tions are equivalent.
1. G is clusterable;
G does not contain any bad triangle.
3. There does not exist an edge (u, v) E E that is connected in G' = (V,
We call the path in G' that connects u and v positive path between u and v.
Proof. Let us first show that G' is clusterable if and only if it does not contain any bad triangle. Given a clusterable graph G, by the definition of clusterable graphs, there exists a clustering C of G with cost of O. If there is bad triangle (u, u), (v, w) E+ and (u, w) E-, u, v (resp., U, w) must belong to the same cluster. However, (u, w) E E implies that u, w cannot belong to the same cluster. This contradiction implies that graphs with bad triangles cannot be clusterable.
Now, we argue that graph G that is not clusterable must contain at least one bad triangle. Let S C V be a subset of vertices, and S a vertex, such that the induced subgraph Gs over S is clusterable, but Gsugw) is not clusterable. By the definition, there cxists clustering C = (C1, C2....) of Gs with a cost. We discuss three different cases. When u connects to all the vertices in 5 by (-) edges, the clustering C' = ((u), C1 C2. ..... will have cost, contradicting to the assumption that G is not clusterable. When has (+) edges only to one of the clusters (without loss of generality, assume it is C1), there must exists a vertex w C1 such that (u, w) E E Otherwise C' (fu) U C1, C2....) will have 0 cost. In addition, we assume V E S is one of the vertices such that (u, v) E E+ By the fact that v, w E S, (v, w) E E+. (u, v, w) forms a bad triangle. Lastly, when has (+) edges to multiple clusters in C, we assume (u, v), (u, w) E E+ where w belong to different clusters. Then (v, w) & E- and (u, v, w) forms bad triangle.
What is remained is to show that G contains bad triangle if and only if it contains positive path enclosed by a negative edge.
Since a bad triangle itself is such cycle, we only need to prove the "if" direction. Given negative edge (u, v) and a positive path P = u + w1 - _ wy - connecting u and v. For and Wt+11
simplicity, denote wo contain any bad triangle. We show by induction that for every d > and every E [0, + 1 d.. (we, wx+a) E which is a contradiction to (u,v) E ET.
The base case is when dl = 2, for every E [0, 1-), (wi, W:42) E E+ or otherwise (w,, Wi+1, Ws+2) form bad triangle. Suppose the above is true for every d dg. For every i E [0, + 1 dol. (w,, wi+a-1) E E+ by our inductive hypothesis. Then, (w, wH+a) must be positive or otherwise (we, Wi We+d) will form bad triangle.
18

---

Published as a conference paper at ICLR 2026
Our proof of correctness discusses three different types of graphs in the "NO" case. Before we delve into the proof details, below are necessary definitions and lemmas that will be used in our proof.
Definition 5. Given the labeled graph G (V, E U ) we let C (C1, C2,..... ..... C be an optimal correlation clustering of G. If there are multiple optimal clusterings, we fix an arbitrary minimal optimal clustering, i.e., for every cluster C' C, splitting C' into two non-empty clusters will always increase the clustering cost.
The clustering C defines an equivalence of the vertex set. We use u <eg v or simply u ~ v to denote that u, V E V belong to the same cluster of C. We call edges (u, v) E E" but u ~ v as false negative edges, And we call edges (u, v) E+ but * v as false positive edges.
Denote by clusters in C of 2 en/20 vertices as large clusters, and those of size < en/20 small clusters. Let F FN U Fp denote the set of false edges, i.e., flipping edges in F will yield clusterable graph, where Fp and Fy refer to the set of false positive edges and false negative edges respectively. In addition, we split Fp into two disjoint subsets Fp Fr.,. U Fr.s. Fp.,. indicates the set of false positive edges (u, v) where at least one of u, v belong to large clusters. And Fr,s indicates the set of false positive edges (u, v) whose both endpoints belong to small clusters.
We will use different proof strategies prove the correctness of our algorithm in the following three cases.
Case 1: [fx]] 2 |Fpl.
Case 2: |Fxl < |Pl and |F 2 |P,sl
Case 3: |Fxl < |Fp| and |F... < |F,,s
Our proof repeatedly uses Janson's inequality, which helps us connect the number of vertices sam- pled and the probability of including a bad triangle in the queried subgraph. We do not directly analyze the number of bad triangles in the sampled subgraph using Janson's 's inequality, because we do not even know how many bad triangles are there in an arbitrary graph from the NO case. Instead, we find a negative edge and a positive path connecting it, where the existence of each vertex of such path will be guaranteed by Janson's 's inequality.
Both our proofs to Case 1 and Case use the following lemma as a subroutine, which is built on Janson's inequality.
Lemma E.2. Let n 2 1 be a large enough integer and G = (V, E+ U EE) be an arbitrary labeled graph of n vertices. Let & E (0, 1) be fixed parameter, and c [0.01, 11. [0.25, 1] be arbitrary fixed constants. Fix minimal optimal clustering C of G. Let T be random subset of V such that each vertex is included in T with independent probability p= min( 2-10" .1). Fix cluster C in C of size 2 C-En, a vertex u E C, and a set C" S C such that |C'| 2 c' |C|. With 2 99/ /0/0 probability there exists vertex E C' such that the induced subgraph over T U {u} contains a positive path between u and v.
Proof. Our key observation is a win-win argument. Let Ne(u) denote the set of neighbors of connected by positive edges in C. Notice that [Ne(u) > (ICI- - 1)/2 or otherwise splitting out from C' will not decrease the clustering cost, contradicting to our assumption that is the minimum optimal clustering. Since Ne(u)] is an integer, equivalently [Nc(u)] > |C|/2. At a high-level, when [Nc(u) C*I = (en)) with high probability the set T contains a vertex in Ne(u) n C'. When [Nc(u)nC") is small, the number of (+) edges between (etteennNc()) and C" should still be n(=2n²) or otherwise splitting C" out from the cluster C' will yield a better clustering, which contradicts the optimality of C. Such an edge will be sampled with high probability by applying Janson's inequality. For the special case where C" is the set of positive neighbors of a vertex u E C, we refer to Figure for illustration of our ideas.
Specifically, when (Ne(u) C 2 0.1c'(C), the probability that none of these vertices are sampled in T is at most
(1 p) 0.1'' S e -..ccpp/ < 1/100
Hence T contains vertex in C' that is connected by a positive edge with high probability.
Then IC" - -N(( > 0.9c'|C]. By our assumption that C is minimal optimal correlation clustering, the number of positive edges between C' No(u)
Now we assume nN" < 0.1d(C).
19

---

Published as a conference paper at ICLR 2026
and C (C' - Nc(u is larger than IC" -N((u)l
(C' NNc))(( This implies that,
in average, every vertex in C" C"-No (Nc(u) should have positive edges to more than half of vertices
in C (C" (u)). Observe that the size of C (C" NN(u)) is at most |C] 0.9c'|C)
(1 (1-0.9c')CC) in which at least 0.5 vertices belong to Nu(u). Because 0.5|C) is at least 0.45c' C
more than half of |C- (C" Nc())) (1-0.te')] every vertex in C" Ne(u) has > 0.45e C
neighbors in (u) in average. Since -C" No(u)] | > C) the total number of edges between
No and Nc(u) is at least 0.405(c))*(C)3 2 0.025|C1 We then apply Janson's 's inequality to show that at least one of such edges will be sampled in T with high probability.
Let R be the set of positive edges between C' NN(uu) and Nc(u) where |R] 2 0.025|CI2 >
2.5 10 100"=?n? By setting the family of subsets to be R. X to be the number of positive edges (u, w) E R where both v, w T, we have À E[X] R p² and A I | [ p². By applying Janson's inequality, we get
Pr[ve, w E T, (v, w) $ R S exp
A 2A
When >> 2A,
Pr[Ve, w ET, (v, w) & R S exp(-1/22) < exp(-IR) (xp(-1R|-p?/2) S 1/100
When A < 2A, because R 2 0.025 CT2
X²
[R|2p4
Pr[ve, w E T, (v. w) $ R < exp
< exp
S e S 1/100
4A
2|C|| R/p3
Thus, with high probability there exists w E No(u) nTT' and v E C' n I' such that u + w - u the desired positive path.
Proof to Theorem] 7 By Lemma E.1 Algorithm 3 always returns "YES" G is clusterable. In
addition, by Lemma 3.2 Algorithm 3 returns "YES" with probability 2 99/199 /000 if G is (E2/1014)-
close-to-clusterable What is remained is to show that Allorithhm will output "NO" with high probability when G far from clusterable.
To accommodate Janson's inequality, instead of working on the algorithm of sampling a fixed num- ber of vertices, we introduce and analyze an intermediate algorithm where each vertex is included in the sample set with independent probability.
Let algorithm II follow the same step and 3 Algorithm For step 1, II instead samples set of vertices S = S1 U S2 U Sz, where each vertex is included in S1, S2, S3 independently with probability p= min(" 2-10 zm
By the standard Chernoff bound and union bound, with & 1/100 probability any of S1, S2, S. has size 2 103/(3)) for every (0, 1). Therefore, only with 1/100 probability Algorithm samples less vertices than Algorithm II. We instead show that Algorithm II has success probability > 91 /00100 given graph that is e-far from being clusterable.
20

---

Published as a conference paper at ICLR 2026
large cluster C
large cluster
1
V
(a) (u, v) is a false negative edge sampled in Si, in a large cluster C. If u share large proportion of positive neighbors in C, with high probability Sa can sample at one of such vertices. Any those vertices together with u, e form bad triangle.
(b) Both u, have at least half' of positive neighbors in C (due to the optimality of C). When the posi- tive neighbors of and have small intersection, the neighbors of u C. A large proportion of edges between the two parts should he positive; or otherwise splitting C into two parts will decrease the cost of C. With high probabil- ity least of such positive edges will be sampled in S2, which forms positive path between and v.
roughly
a partition to
Figure 3: Two subcases of Case 1. (Formalized at Lemma E.2
Case 1 [[Fx) 2 [Fp). Fxl 2
[Fll implies that |Fv| 2 <(²//2 and the total number of (both
positive and negative) edges in all the clusters
Σ
CCl 2
2 2 E
n2 2
Because the density of (+) edges inside the clusters of the optimal clustering C is always > 1/2. Or otherwise we can always further partition into smaller clusters without increasing the cost.
Among these edges, least 0.225(en2 n) 0.224en2 of false negative edges belonging to clusters 2 en vertices, since the total number of edges in clusters of small size at most 20
n2 sn-1 20 We will show that the sampled vertex set S₁ contains at least one false negative edges (u, v) with high probability; and, in addition, the induced subgraph over S2 U {u, o} contains positive path between and v with high probability. We denote by F'y S FN the subset of false negative edges with least one endpoint large clusters. Since the two probabilities are dependent, we will rewrite the probability as the summation of two independent probabilities. Let &.,, denote the event that "u, e are not connected by a positive path in the induced subgraph over S2 {u, v)"". We have
PriVu, v S, (. v) & FV Eu,u]
<PrVu, Sn, (u,v) & FN V Eg,e]
(1)
PriVu,u St, (u, Fx1+ +
max
Pr[Eu,.].
SICVa. (M.))F
The first half can be bounded using Janson's inequality. By setting the family of subsets to be F X
to be the number of pairs (u, v) E Fly from S1, we have X E[X] |F 1-2 and A & F'
21

---

Published as a conference paper at ICLR 2026
By applying Janson's 's inequality, we get Pr[Vu, E S1, (u, $ Fx] -Pr[X - 0]
X²
<exp(
À + 2A
|F pp
<exp(
1.1m F'r pp3
0. 0.224epm.
S <xpp(
1.1
<1/100
where the third inequality is by the fact that 1 nn F/ pd >> A, and the fourth inequality is due to [Pv] 2 0.224en².
The second probability the last line of (T) is bounded by applying Lemma E.2 When we set C' to be (v) whose size is at least |C|/2, we obtain that with 2 99/100 probability u and are connected the induced subgraph of G over S2 {u, v}.
Therefore, for every (u, E Fl and every Si that contain u, u, the probability that are not connected by a path in Gs at most 1/100. By [ and ?
Pr[vu, v E S, (u, v) & Fly V u, u are not connected in Gs] S 2/100
and the probability that Algorithm
3 succeeds is at least 9/10.
large cluster Cu
cluster Cp of size < 0.01en
large cluster Cu
of size 2: 0.01cn
Oregg
(+) path
(+) pan
Crep
(4) pah
O-e
(a) (u, v) is a false positive edge sampled in St. In the subcase where [C2l 0.01æn, belongs to large cluster C, and belongs small cluster Cs- Then e will have a large number negative edges connected to C.: or moving v from C. to C. will decrease the clustering cost. By similar argument in |Fiuure 3 (formaiized in Lemma E.2). with high probability in S2
(b) For the case the cluster size of Cv is Q(En), at least half of edges between C, and C, are neg- ative; or otherwise combining C. and C. will de- crease the clustering cost. Reusing Lemma E.2 with high probability we sample a positive path from u to u' in S2, and positive path from v to v' in Ss. such that (u' o') is negative. In this way, find negative edge (u', v') connected by positive path al
where (w,, v) negative and a positive path from и to w are sampled. Here (v, w) is the negative edge connected by a positive path v ->
u
w.
Figure 4: Two subcases of Case 2.
Case 2 ([Fxl < [Fpl and [FP, 2 Fp.s)) By our conditions, [Fp,L] 2 /4. Our proof idea to this case similar to case 1. Through we will fix an edge (u, v) from Fr.L. by using Janson's inequality in exactly the same way 2). Let C,,, Cp respectively denote the cluster of u and in C.
Without loss of generality we assume C,,l 2 [C,]. By the definition of FP,L. |Cul 2 sn/20. There two subcases whether C, is large small.
Consider the case |C,| < 0.01en. Let C" := {w E C. (v,w) w) E E Then |C'| 2 |C, //100 or otherwise moving from C. to C. will decrease the cost. By Lemma E.2, with least 99/100 probability the induced subgraph of G over {u, v) U S2 contains a path between v and vertex E C. O S2 such that (v, w) E F-
22

---

Published as a conference paper at ICLR 2026
Now turn to the case |Cu] 0.01en. Let Ru, ((u',e') E : E Cu. E C.y. By
the optimality of C, R 2 Cul -/ool/2 or otherwise combining Cu and C. into a single cluster
will decrease the cost. Let Qu C. be the set of vertices that has z |Cal negative neighbors
in C... Then 1Qul 2
Ca.l since otherwise [Ru < [Ca.] Cel/2. By applying Lemma E.2 the 3
induced subgraph over S2 U {u} contains a positive path from u to Qu with N 99/100 probability. Fix the vertex sampled in Qu as ut, we denote Qu C C. as the subset of C. whose vertices have negative edges to w'. By
definition to Qu. 1Q 2 Cel Again by applying Lemma E.2 the
induced subgraph over S3 U {w} contains a positive path from u to Qu with 2 99/100 probability. We denote by e' the vertex sampled in Qu-
Therefore, with probability 2 97 07/100 there exists a negative edge ('),"") where u', o' E such that u', v' connected by a positive path
in the induced subgraph over S. Therefore, Algorithm 3 correct with high probability.
small clusters
Figure 5: In Case 3, with high probability, the sample set S1 contains vertex u that belongs small cluster, and is connected to Q(en) vertices of small clusters by positive edges. The induced subgraph over all such positive neighbors of must contain a bounded proportition ( 0.94) of positive edges, or otherwise forming these vertices into single cluster will decrease the total cost. Therefore, with high probability a negative edge (v, w) will be sampled S2, which forms a bad triangle (u, v, w)
Case 3 ([FNl [Fll and [Frz1 < |Fr,s)). By conditions, |Fr,s <(5)/4 There are least 0.0len vertices that are incident to 2 0.23en edges from |Fp.s By Chernoff bound, at least one of such vertices u sampled in S1 with 2 99/100 probability. Define
Nu.s == {o (u, E Et u v, and belongs to a cluster of size (< en/20)}
Then |Nv.sl > 0.23En. We will show that the density of positive edges in the induced subgraph of G over Nu.s is small, or otherwise Nu,s can form a cluster with smaller cost.
Since all the vertices in Nu.s U {u} belong to clusters of size at most en/20, splitting all these vertices from their clusters will at most increase (INa,sl + 1) en/20 cost. Thus, the total number of negative edges inside Nu.s U {u} is at least
Nu.s 11) ((No.sl + 1) en/20- = (INo,sl + 5 - en 2
[N..s en
20
31
Otherwise, making Nu.s {u} cluster will decrease the cost of by calculating its relative cost.
We will again use Janson's 's incquality to show that at least one of such non-edges (1, w) will be sampled in S2 with hiob-btoba Since (u, v), (u, w E but (v,w) E E". bad triangle is observed.
Let R be the set of these non-edges, where R > Nu.s en/31. Let X be the random variable denoting the number of non-edges in R that are included in Gs,- Let À E[X] | . Let
23

---

Published as a conference paper at ICLR 2026
A |N Rl.pp. By Janson's inequality, we have
R .R Pr[X 0J S exp (-T.1- |Nu.sl S 1/100.
Therefore, with 2 98/100 probability one can observe vertices v, w E S2 and E S₁ such that (u,w) E but (u, v), (u, w) E in this case.
To summarize, in all of the above three cases, one can always observe bad triangle with probability 9/10 probability when the graph is e-far from being clusterable. Algorithm outputs correctly with probability 2 9/10.
F OPTIMAL STRUCTURAL BALANCE TESTING FOR COMPLETE GRAPHS
We now discuss our results for structural balance, i.e., the case of k for correlation clustering with fixed number of clusters. Recall that the main theorem statement is follows.
Theorem 3. Fix E 1). There exists randomized algorithm that given labeled complete graph G E UEE) and a parameter answers the following
G is balanced, the algorithm always answers "YES";
If G least E-far from being balanced, the algorithum answers "NO" with probability 2 0.9.
The algorithm queries at most ((1/s) edges of G and runs in O(1/e) time.
The algorithm for Theorem 3 Jsses different approach compared to Theorem 2: we sample O(1 triangles, take the graph G" induced by the edges (the graph might not complete), and check whether G' has any unbalanced triangle. The formal algorithm could be described as follows.
Algorithm An algorithm for structural balance property testing Input: A labeled complete graph G (V, E+ U UE"); parameter E.
Sample 300/e triangles (u, v, w) E 3 uniformly at random (with replacement).
2. Check if any of the sampled triangles is unbalanced.
We first observe that Algorithm uses O(1/E) queries and time, and the algorithm always returns "balanced" if G is indeed balanced.
Lemma F.1. Algorithm 4 makes O(1/E) queries G with 0(1/E) computation time.
Proof. The algorithm only samples O(1/E) edges and triangles, where O(1) time for each triangle to check whether it balanced or not.
Lemma F2. IfG = (V, E U E-) is balanced, then Algorithm 4 always returns "balanced".
Proof. By simple observation, any subgraph of a (strongly) balanced graph does not contain any unbalanced triangle. Therefore, the algorithm will not detect any unbalanced triangle and will al- ways return "balanced".
We now proceed with the proof of the soundness of the algorithm. At a high level, we aim to demon- strate that if the number of disagreement edges high, then the number of unbalanced triangles has similar lower bound. Proving the statement, however, is not entirely straightforward since the number of unbalanced triangles is not necessarily monotone w.r.t. the number of flipped edges depends the structure of the graph. Consider, for instance, graph of vertices with exactly two false edges. the two edges are not incident to each other, the total number of unbalanced triangles is 2(n 2), 2 unbalanced triangles induced by each false edge and each other vertex. But if the
24

---

Published as a conference paper at ICLR 2026
two edges are incident to each other, the triangle including both edges will be balanced, and the total number unbalanced triangles decrease to 2(n -3. We give clean proof to the desired statement using three different random sampling processes, avoiding discussions to the structure of the graph.
Lemma F.3. IfG = (V, E+ U E-) "not balanced" with probability at least 99/10/
) is at least e-far from being balanced, then Algorithm returns
Proof. Let Vunbalanced the set of unbalanced triangles in G, and let Eunhalanced be the set of false edges induced by (L" R"), which is the optimal partition that minimizes the frustration index of the graph. For each unbalanced triangle E Vunbalancod- We define the following sampling process for triangles.
Process random sampling process for triangles.
Sample triangle uniformly at random from G.
Let XA be the indicator random variable for the unbalanced triangle A E Nuntalanced to be sampled by Process J.
We now consider another sampling process in which we uniformly sample an edge.
Process 2: random sampling process for edges.
Sample an edge uniformly random from G.
For each false edge E Eunhalanced- we let Y. be the indicator random variable for the edge to be sampled. Our technical claim is as follows.
Claim F.4. On each time of sampling with Process and Process 2, we have that
1
Pr ( A E Aunbalanced is sampled by Process 1) 2 Pr E Eunbalanced is sampled by Process 2).
Proof. We consider the following sampling process:
Process "bridge" sampling process.
Sample vertex v E V uniformly at random;
Sample an edge e' 3 e uniformly at random.
We let (L", R²") be the partition obtained by the following rules: we arrange all the (+) neighbors of in L. The of the rest of the vertices, namely V \ L" is therefore defined R Let Eunbalancea (v) be the set of false edges induced by R"). Since (L", R*) ) is the optimal partition that minimizes the frustration index, for any V. we have that
Euntalanced [v)
Eunhalanced
Therefore, conditioning the sampling of any fixed have that
Pr (e E Eunhalanced is sampled by Process 2) < Pr (e E Eunbalanced (v) is sampled by Process 3).
On the other hand, for any fixed v, let Kgnbalanced (v) be the set of unbalanced triangles with one endpoint as and one edge in Eunbalancedd Note that each unbalanced triangle will most be counted times, which happens only when all the three edges of the triangle are false edges. As such, we have that
3 \ Munbulanced
>
Kunbalanced (v)l
VeV
25

---

Published as a conference paper at ICLR 2026
Therefore, could lower bound the probability of sampling unbalanced triangle
(A Aunbalaneed is sampled by Process
Σ
Pr (v is sampled and A E Xunbalanced(() is sampled by Process 3)
3
DEV
Pr (e is sampled by Process 3) (e E Eunbalaneed (v) is sampled by Process 3).
3
PEV
Observe that each vertex has 1/n probability to be sampled in Process 3. Therefore, we have
Pr
AA Kunbalanced is sampled by Process 1)
(r E Bunbalanced (v) is sampled by Process 3)
3
VEV
2
(r E Eunbalanced is sampled by Process 2)
3
VEV
Pr (e E Punbalanced sampled by Process 2)
3
which is as desired by the statement.
Lemma F.4
Since the graph is at least e-far from being balanced, we have that
Pr(e E Punbalunced is sampled by Process 2) 2 e.
Therefore, by Lemma F4 for each time of sampling in Algorithm 4 have that
Pr (XA for some A E Xunbulanced) 2 e/3.
Since sample triangles without replacement, the sampling at each time is independent. Therefore, the probability for us to not sample any unbalanced triangle with 100/s samples is at most (1 e/3 //3/300/z < 1 1/100, as desired by the lemma statement.
Lemma F3
Combining Lemma H.I. Lemma F2 and Lemma F33 gives the full proof of Theorem 3
G EXTENSION TO STRUCTURAL BALANCE TOLERANT TESTING
We now discuss generalizing our structural balance testing algorithm to allow graphs that are nearly balanced acceptable by the tester. This falls into the regime of tolerant testing Parnas et al. (2006); Ron (2009): Blais et al. (2019), in which we want instances that nearly satisfied the desired property also pass the test. For structural balance, testing algorithm such has strong practical motiva- tions: real-world graphs are often not perfectly balanced yet close to being balanced. Therefore, tolerant testing algorithm could have much broader impact testing wardwwoldd graphs.
Recall that main theorem for the tolerant testing algorithm is as follows.
Theorem 4. Fix E (0, 1) such that ō < 8/900. There exists a randomized algorithm that given labeled complete graph G (V, E U UEE) and parameters E, answers the following
If G is most 5-close from being balanced, the algorithm answers "YES" with probability 2 0.99:
If G is at least E-far from being balanced, the algorithu answers "NO" with probability 2 0.99.
The algorithm queries at most O(1 (11/s) edges of G and runs in O(1/e) time.
The algorithm for Theorem 4 is similar to Algorithm 4 albeit we use threshold to determine whether the graph is balanced. The algorithm could be described as follows.
26

---

Published as a conference paper at ICLR 2026
An algorithm for structural balance tolerant testing Input: A labeled complete graph G (V, E+ U UE),, parameters E, 8 such that < s/900.
Algorithm 5.
Sample 300/e triangles (u, v w) V uniformly at random (with replacement). at most 10 out of 300/e sampled triangles are unbalanced, return "balanced"' Otherwise, return "not balanced".
The efficiency of the algorithm follows directly from the argument in Lemma F.1 and we write the corresponding lemma without proof.
Lemma G.1. Algorithm 5 makes O(1/E) queries G and converges in O(1/E) time.
We first analyze the soundness of the algorithm, for which could use the conclusion in Lemma F.4] The main lemma is as follows.
Lemma G.2. If G (V, E+ U E-) least e-far from being balanced, then Algorithm returns "not balanced" with probability at least 199/200.
Proof. Let XA be the indicator random variable for an unbalanced triangle A to be sampled for one sampling step in Algorithm 5) and let X = Σ XA EXa
be the total number of unbalanced triangles sampled by Algorithm 5 By Lemma F.4. we have that
300
E
[
Pr (X& for some E Xynhulanced) 2
100.
Since X is summation of independent indicator random variables, we could apply Chernoff bound, and show that
Pr
S 10) - Pr
S (1 0.9) [X])
0.92 100
S exp
1/200,
2
as desired.
We now proceed to show the completeness of the algorithm, i.e, 8nè-close instances also to pass the test and result in a "balanced" outcome. The proof of the lemma will use a "reversed" probability calculation in Lemma F.4
Lemma G.3. IfG (V, E+ UE) is most 5-far from being balanced for some 8 S c/900, then Algorithm 4 returns "balanced" with probability at least 199/200.
we let Veubbalanced be the set of unbalanced triangles, and Euabalanced be the set of disagreement edges induced by the optimal partition (L*, R.). We now define the following processes.
Proof. Similar to the proof of Lemma F.3
Process 4: random sampling process for edges.
Sample triangle A uniformly random from G, then sample an edge from A.
Also, we will use the random Process 1 which samples triangle uniformly at random from the F.3 for the full description). We have following technical claim.
graph (see the proof Lemma F.3
Claim G.4. On each time of sampling with Process and Process 4, we have that
Pr (A Xuntsatncced is sampled by Process 1) < 3 Pr (e Eusbalanced is sampled by Process 4)
Proof. The claim follows from the fact that for each A E Xunbalanceds there must be at least one edge e E Eunbalanced by definition. Therefore, we have that
Pr (e E Eunbalanced is sampled by Process 4)
2 (sampling E Eunbelanced from A E ((unbalancdd) Pr (A Xunbalanced is sampled by Process 1)
Pr(A E Xunbalanced is sampled by Process 1),
3
27

---

Published as a conference paper at ICLR 2026
which leads to the desired statement.
Lemma G,4
For graph that is at most 8-far from being balanced, which means at most (e/900)-far from being balanced, have that
Pr(e E Funbalanced is sampled by Process 2) S 900
Let Σ Xa be the total number of unbalanced triangles sampled by Algorithm S
By
Lemma G.4, we have that
300
E E
(x for some E Xunbulancea)
900
Pr (e E Eunbalanced is sampled by Process 2) I 1.
If X then Algorithm 5 deterministtcally returns "balanced". As such, we assume w.log. that X 2 1. Since X is a summation of independent indicator random variables, we could apply the
Chernoff bound, and we get
Pr 2 10) Pr (X (1 -)]][X])
81.1
S exp
1/200,
11
as desired.
Combining Lemma G.
Lemma G.2 and Lemma G.3 with union bound gives the desired statement
of Theorem
H A LOWER BOUND FOR TESTING CLUSTERABILITY AND STRUCTURAL BALANCE
We give a lower bound for testing structural balance complete graphs in this section. Our lower bound shows that any algorithm that separates graph from being balanced vs. 8-far from being balanced requires at least ((1/E) queries to the graph. This implies our algorithms in Theorem and Theorem 4 are asymptotically optimal.
Recall that our statement for the lower bound is as follows.
Theorem 5. Any (possibly randomized) algorithm that given complete labeled graph G (V,E* U E,), with probability at least 2/3 answers correctly whether G is balanced or at least E-far from being balanced requires least (2(1/e) edge queries to the graph.
Furthmore, the lower bound extends to testing clusterability (for both general k and fixed k).
Proof. We use the following result from a recent paper to prove our lower bound.
Proposition H.1 (Fischer (024)) rephrased; cf. Bshouty & Goldreich (205 Let Σ, be an arbi- trary alphabet for an length-m m input, and let " be the set of all possible inputs. Let P S m be the set of inputs that satisfy a properly. Suppose there exists instance U P such that at least or m elements need to modified to satisfy the property prescribed by P. Then, any algorithm that with probability at least 2/3 correctly distinguishes whether input S I is in P or needs to modify at least 3 m bits to satisfy property of d requires 2(a/3) queries to S.
We apply Lemma H.l with Σ = ((+),(-) and m ("). The instances with structural balance are P. Here, we only need to find an instance U & P at least a-far from being balanced for some 9(1). We consider a graph with all (-) edges triangles, and each flip of the label could reduce the number of bad triangles by at most n -1 1. As such, the graph at least o-far from being balanced for some 12(1). Applying Lemma H.1 leads to the desired ((1/s) query lower bound.
such an instance: the graph has (*) bad
Note that since each query takes ((1) time, our algorithms are also asymptotically optimal in terms of the time complexity.
28


Reviews:
[{"review_id": "aqakJ9C6uC", "reviewer": "Reviewer_kSQi", "summary": "This paper studies property testing for correlation clustering and structural balance in dense labeled graphs. It improves the known query complexity, and achieves a tight bound for the two-cluster (balance) case. Novel results, for the $k$ clusters case are also given. The improvement comes primarily from a cleaner probabilistic analysis using Janson’s inequality, rather than from a new algorithmic idea.", "questions": "See Weaknesses section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- **Analytical improvement over prior bounds.**  \nThe work reduces the query complexity for testing correlation clustering from $\\tilde{O}(1/\\varepsilon^7)$ to $O(1/\\varepsilon^2)$, and achieves a tight $\\Theta(1/\\varepsilon)$ bound for the special case $k=2$. Although the improvement stems mainly from a sharper analysis, the result is still valuable as it narrow an asymptotic gap. Furthermore, the application of Janson’s inequality to handle dependent random variables is mathematically clean and simplifies the analysis. While not conceptually deep, it removes several unnecessary factors and clarifies the dependence on $\\varepsilon$. Finally, the case for $k$-clusters seems novel.\n\n- **Theoretically relevant within property testing.**  \nWithin the dense-graph property testing framework, correlation clustering is a natural and well-motivated property. The paper contributes a clearer understanding of its sample complexity, which is of interest to the theory community.", "weaknesses": "- **Primarily analytical, not algorithmic, contribution.**  \nThe main improvement derives from a tighter analysis rather than a novel testing algorithm. The core testing procedure remains essentially unchanged from prior work, and the use of Janson’s inequality, while effective, is a straightforward application of a standard concentration tool.\n\n- **Limited depth of the probabilistic insight.**  \nThe argument simplifies the dependency structure among sampled edges but does not introduce new combinatorial or probabilistic ideas. The simplicity of the improvement raises the question of why such a refinement was not already known.\n\n- **Coarse granularity of the testing objective.**  \nAs in all property testing formulations, the test only distinguishes between perfectly clusterable graphs ($\\mathrm{OPT}=0$) and those that are $\\varepsilon$-far from such structure ($\\mathrm{OPT} \\ge \\varepsilon \\binom{n}{2}$). This dichotomy is extremely coarse and offers little interpretive value for practical clustering, where intermediate cases are the norm.\n\n- **Relevance limited to dense theoretical settings.**  \nThe dense graph model and the assumption of oracle access to edge labels make the results largely theoretical. The test loses meaning when $\\varepsilon = O(1/n)$, since the query complexity becomes $\\Theta(n^2)$, equivalent to reading the entire input. The authors do not discuss this limitation. Moreover, while the $k$-clusters case is novel the $k^4 \\log^4 k$ runtime seems problematic.\n\n- **Moderate originality.**  \nThe methodological novelty is incremental, and the improvement, though useful, does not introduce a fundamentally new perspective or analysis technique.\n\n### Overall evaluation\n\nThis is a technically solid and clearly written paper that refines the analysis of property testing for correlation clustering. The results are correct, and the improvements close an asymptotic gap in query complexity, but the novelty is mostly analytical rather than conceptual or algorithmic. The paper will interest the property testing and theoretical graph learning communities, though its impact on broader learning theory or clustering practice is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Pzm9TAyvLf", "reviewer": "Reviewer_ENS9", "summary": "The paper presents property-testing algorithms for correlation clustering and balance property in graphs. Compared to previous work, the paper presents improved bounds, and in addition it presents a new sampling algorithm for testing k-clusterability, which as far as I understand, is a newly introduced problem. The paper gives a good overview of previous results, states its contributions clearly, provides a sketch techniques while full proofs are in the appendix, and presents an empirical evaluation of the methods.", "questions": "I would be very interested in seeing the response of the author(s) in point W1, above.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. Solid problem formulation, improving and extending earlier work. \nS2. Theoretically rigorous paper, giving a good intuition of the techniques and presenting full proofs in the appendix.\nS3. Well written paper, presenting a clear motivation, highlighting the contributions and main results, and presenting the methods with clarity.\nS4. Theoretical results are accompanied with an empirical evaluation.", "weaknesses": "W1. While O(1/epsilon^2) is a significant improvement over \\tilde{O}(1/epsilon^7), I found that the two results are not directly comparable because the earlier work of AA2023 tests of cost smaller than epsilon/10, while the current work tests for cost=0. So, I think that the current paper solves a much easier problem. Furthermore, this limitation is significant in practice, as the method essentially does not tolerate any noise, which is highly unrealistic for real-world applications. I think that the author(s) should have been more clear about this important distinction, during the discussion and when presenting Table 1. This weakness is my main motivation for not suggesting the paper for acceptance. \nW2. While researching for sublinear-time methods, I think that in practice a linear algorithm is often good enough. In this sense, I think that the paper would be a better fit for a venue in theoretical computer science.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DaZrDh95Mw", "reviewer": "Reviewer_CjKd", "summary": "This paper studies the correlation clustering (CC) problem from the perspective of property test. Theoretically, it yields three results for clusterability, $k$-clusterability ($k$ is a constant), and $2$-clusterability (also called strong balanceness), respectively. The query complexity $O(1/\\varepsilon^2)$ for clusterability gets a great improvement from the SOTA results using $\\tilde{O}(1/\\varepsilon^7)$. The query complexity $O(1/\\varepsilon^4)$ for $k$-clusterability is new, and that for $2$-clusterability $O(1/\\varepsilon)$ has reached the tight lower bound up to a constant factor. The testing algorithms are evaluated by experiments on simulated and real-world datasets.", "questions": "1. The definitions of some key concepts are missing. I didn't find the formal definition of \"structural balance\". The authors have defined the weak and strong versions of structural balance in the Introduction section. It seems that structural balance refers specifically to $2$-clusterable, isn't it? The definition of \"bad triangles\" is also missing.\n\n2. The figures in Section 4.2 is confusing. What's the difference between the blue and orange lines? Or say, what is the difference between structural balance and correlation clustering? Do they have the same number of clusters? Does a YES answer mean \"clusterable\"? Why its rate is nearly zero small (especially for structural balance) when the distance parameter $\\varepsilon$ is small?\n\n3. It is better to introduce Janson's inequality in a separate section in appendices for the readers who are not familiar with it.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The theoretical results are solid.\n\n2. It provides more insights to the CC testing problem (e.g., the hit of bad triangles and the use of Janson's inequality).", "weaknesses": "1. I am skeptical about the practical merits of the CC problem. Requiring a complete graph as input is an overly stringent condition that is rarely satisfied in real-world scenarios. While the authors have presented experimental results on real-world datasets, it remains unclear how they converted the six real-world graphs into complete ones, nor how they assigned +/- signals to missing edges. So I am uncertain about the significance of these experiments. I acknowledge that this paper has theoretical significance. If I were reviewing it for a TCS venue like SODA or STOC, I would not raise this concern. However, for an AI venue, clarifying its practical relevance is essential.\n\n   A more interesting variant of the CC problem appears to take a general graph as input and count the misclassified edges. However, the methodology to address this variant would be entirely different.\n\n2. There are some unclear points and minor issues. Please refer to the Questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ROTtFray5w", "reviewer": "Reviewer_Yvv8", "summary": "This paper studies the problem of testing the cost of correlation clustering, i.e., to test whether the input graph $G=(V,E^+\\cup E^-)$ is clusterable (with $0$ cost) or is $\\varepsilon$-far away from being clusterable. Here, the cost of correlation clustering is defined to be the number of $(+)$ edges crossing different clusters and the number of $(-)$ edges in the same cluster. $\\varepsilon$-far away from being clusterable means that one have to flip the labels of at least $\\varepsilon\\cdot \\binom{n}{2}$ edges to make the graph clusterable, where $n=|V|$.\n\nThe authors proposed new testers that achieve improved query complexity compared to prior work. Specifically, \n* for correlation clustering, they gave a new tester with $O(\\frac{1}{\\varepsilon^2})$ query complexity while  previous best result is $\\widetilde{O}(\\frac{1}{\\varepsilon^7})$, \n* for correlation clustering with fixed $k\\ge 2$, they give the the first nontrivial tester with $O(\\frac{k^4\\ln ^4 k}{\\varepsilon^4})$ query complexity,\n* for correlation clustering with $k=2$ (i.e., structural balance), they gave a new tester with $O(\\frac{1}{\\varepsilon})$ query complexity while  previous best result is $\\widetilde{O}(\\frac{1}{\\varepsilon^2})$ (all the time complexities are proportional to their query complexity). \n* Moreover, to complement their upper bounds, they gave an $\\Omega(\\frac{1}{\\varepsilon})$ query complexity lower bound for structural balance problem. The proof of lower bound relies on a direct application of an existing general lower bound result (Fischer, 2024; cf. Bshouty & Goldreich, 2025) to the problem of testing structural balance.\n\nTechnically, they employ sampling-based techniques combined with Janson’s inequality to analyze the concentration of local inconsistencies, a methodological novelty compared to classical approaches using the graph removal lemma. Experiments on synthetic and real-world datasets (from SNAP) confirm the theoretical query and runtime improvements.", "questions": "* lines 357-358: why there is a $2$ in $\\sum_{1\\le i<j\\le s}{2\\cdot \\frac{1}{n^2}}$?\n\n* about the proof of Lemma 3.1: It samples $O(\\frac{k\\ln k}{\\varepsilon})$ vertices and for each iterated vertex $u$, it will perform at most $k$ queries. Why is the total number of queries $O(\\frac{k\\ln k}{\\varepsilon})$ rather than $O(\\frac{k^2\\ln k}{\\varepsilon})$?\n\n**Typos:**\n\n* lines 362-363: missing a period after the inequality\n\n* lines 756-757: we may assume that $t>k$, since a graph ... $\\rightarrow$ we may assume that $t>k$, since **otherwise** a graph ...?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* This paper studies a problem that is well-motivated.\n\n* This paper improves the query complexity of testing the cost of correlation clustering from $\\widetilde{O}(\\frac{1}{\\varepsilon^7})$ to $O(\\frac{1}{\\varepsilon^2})$, which is a substantial and clear advancement over the state of the art.\n\n* For structural balance, the authors prove the first tight $O(\\frac{1}{\\varepsilon})$ bounds for testing structural balance.\n\n* The use of Janson’s inequality for analyzing property testers in labeled graphs is elegant and potentially applicable to other testing problems.\n\n* Experiments on both synthetic and real-world graphs show practical improvements in query complexity and runtime, enhancing the paper’s credibility.\n\n* This paper is well written.", "weaknesses": "* While the theoretical improvement is substantial, the algorithms themselves are relatively straightforward extensions of uniform sampling ideas, and much of the novelty lies in tighter analysis rather than fundamentally new algorithmic constructs.\n\n* The results for general correlation clustering and correlation clustering with fixed $k$ are not tight ($O(\\frac{1}{\\varepsilon^2})$ vs. $O(\\frac{1}{\\varepsilon})$ and $O(\\frac{1}{\\varepsilon^4})$ vs. $O(\\frac{1}{\\varepsilon})$, respectively). The authors acknowledge this but do not deeply explore whether the bound can be improved.\n\n* Nevertheless, I am generally supportive of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)