KwikBucks: Correlation Clustering with Cheap-Weak and Expensive-Strong Signals
Authors: Sandeep Silwal
Sara Ahmadian
Andrew Nystrom
Andrew McCallum
Deepak Ramachandran
Seyed Mehran Kazemi
Venue: ICLR 2023 poster (2023)
Keywords: correlation clustering
text clustering
learning-augmented algorithms
weak and strong signals
query efficient clustering
query efficient
budgeted clustering

Abstract: The unprecedented rate at which the sizes of machine learning (ML) models are growing necessitates novel approaches to enable efficient and scalable solutions. We contribute to this line of work by studying a novel version of the Budgeted Correlation Clustering problem (\bcc) where along with a limited number of queries to an expensive oracle for node similarities (e.g. a large ML model), we have unlimited access to a cheaper but less accurate second oracle. Our formulation is inspired by many practical scenarios where coarse approximations of the expensive similarity metric can be efficiently obtained via weaker models. We develop a theoretically motivated algorithm in this setting that leverages the cheap oracle to judiciously query the strong oracle while maintaining high clustering quality. We empirically demonstrate gains in query minimization and clustering metrics on a variety of datasets with diverse strong and cheap oracles. Most notably, we demonstrate a practical application in text clustering based on expensive cross-attention language models by showing that cheaper (but weaker) embedding-based models can be leveraged to substantially reduce the number of inference calls to the former.

Published as a conference paper at ICLR 2023
KWIKBUCKS: CORRELATION CLUSTERING WITH CHEAP- AND EXPENSIVE-STRONG SIGNALS
Sandeep Silwal! Sara Ahmadian', Andrew Nystrom,, Andrew McCallum', Deepak Ramachandran"3, Mehran Kazemi MIT, Google Research
si welwwlemitteen {sahmadian, nystrom, mocallum, ramachandrand, mehrankazemi mebrankkaeeii)@google..coo jegoogle.com
ABSTRACT
The unprecedented rate at which machine learning (ML) models are growing in size necessitates novel approaches to enable efficient and scalable solutions. We contribute to this line of work by studying a novel version of the Budgeted Cor- relation Clustering problem (BCC) where along with a limited number of queries to an expensive oracle for node similarities (e.g. large ML model), we have unlimited access to cheaper but less accurate second oracle. Our formulation is inspired by many practical scenarios where coarse approximations of the expen- sive similarity metric can be efficiently obtained via weaker models. We develop theoretically motivated algorithm that leverages the cheap oracle judiciously query the strong oracle while maintaining high clustering quality. We empirically demonstrate gains in query minimization and clustering metrics on variety of datasets with diverse strong and cheap oracles. Most notably. we demonstrate practical application in text clustering based on expensive cross-attention lan- guage models by showing that cheaper (but weaker) embedding -based models can be leveraged substantially reduce the number of inference calls the former.
INTRODUCTION
Modern ML techniques have made incredible advances at the cost of needing resource-intensiv models (Sharir et al. 2022). Many recent approaches are resource-intensive that despite amazing accuracy, they only serve as proof-of-concepts and are infeasible to be scaled as-is in practical usage. The total effect of all such deployments on energy usage is also major sustainability concern (Wul ct al., 2022). While the high performance of these models motivates incorporation of their signal, their high inference cost limits the interactions that any practical algorithm have with them.
With the increased cost in querying ML models, the cost of obtaining similarities between objects of different types (texts, images, etc.) has also substantially increased. In this paper, aim to answer a challenging question when working with such costly similarity measure models: how can we group similar objects together when similarities of objects are obtained via expensive queries? This problem can be naturally cast as a popular and versatile clustering framework, named Correlation Clustering (CC), which has been extensively studied over the past 15+ years (Bonchi et al. 2022): given similarities between arbitrary objects represented as graph, CC minimizes a natural objective that attempts to cluster together similar vertices while simultaneously separating dissimilar ones. The high cost of querying large MI. models motivates the use of the Budgeted CC (BCC) setting studied in (Bressan et al. 2019 Gareía-Soriano et al. 2020b) where relationships between nodes are determined by making limited number of queries an oracle, e.g. large ML model.
We posit that many practical settings, coarse but efficient approximations of an expensive model can be obtained through substantially cheaper but weaker models. These weaker models can be used as a guide to spend the query budget for the expensive model more carefully. A motivating example, which heavily inspires work. is in text clustering where wishes obtain similarity signals from the latest highly-accural cross-attention (CA) language models (e.g., (Brown et al.
"Co-advised. Work done while interning Google Research.

---

Published as a conference paper at ICLR 2023
Thoppilan et al. 2022)), but may be hindered by the computational burden as obtaining each pair-wise similarity between data points requires an inference call to the model, giving rise to a worse case Onn²) inference calls, where n is the number of data points. Embedding based models (e.g.. (Mikolov et al. 2013; Devlin et al. 2018) can come to the rescue as they require only O(n) inference calls to obtain embedding vectors for each data point that can then be used for fast similar- ity computation. While embedding models typically produce substantially lower quality similarity signals than CA models (see, e.g., Menon et al. (2022)), they can still provide a good approximation to guide where the budget for the CA model should be spent.
2020
Inspired by the above, we introduce a variant of BCC where, along with a limited number of queries to an expensive oracle, we also have unlimited access to a cheaper but less accurate second oracle. This variant of BCC bridges algorithm design and practical considerations. Indeed, recent book (Bonchi et al. 2022) on CC states "A further intriguing question is whether one can devise other graph--uerying models that allow for improved theoretical results while being reasonable from practical viewpoint." " This is exactly the gap our work fills through the introduction of query- efficient setting with access to two oracles with differing quality and cost.
We develop an algorithm dubbed KwikBucks that extends the well-known KwikCluster algorithm to budgeted CC with theap-weate and expensive-streee strong signals. KwikBucks uses the weak signal guide to minimize the number of calls to the strong signal. Under the assumption that the weak signal returns a strict superset of the strong signal edges, our algorithm can approximately match the performance of Kwi kC1 uster, i.e., 3-approximation, using only exceedingly small fraction of all possible queries to the expensive model (Theorem In our experiments, we strengthen our theoretical modelling with several well-motivated optimizations and demonstrate that Kwi kBucks manages to produce high quality clusterings with only a small number of queries to the expensive oracle even when there is only a weak correlation between the weak and strong signal.
We conduct extensive experiments with multiple well-studied datasets to evaluate the performance of KwikBucks over natural extensions of previous algorithms for closely-related problems. In all settings, Kwi kBucks recovers the best clustering solution with a much smaller strong signal budget than the alternatives, and in many cases it finds asymptotically better solutions as well. Our algorithm is also robust to the choice of weak signal oracle across different dataset settings and obtains significant improvements over five baselines 64 % relative improvement in clustering quality (measured in terms of F1 score) when averaging over 9 datasets, and over 3.5x reduction in query complexity compared to the best baseline.
Lastly, Our contributions can be summarized follows:
Introducing a novel formulation of the BCC problem which strengthens the connection between theory and practice through the interplay between algorithm design and modern ML, where cheap-weak signal guides the queries made to the expensive-strong signal,
Developing an algorithm for this setting with strong theoretical motivations/guarantes
Identifying a highly impactful application domain (text clustering) where the introduced formu- lation and the developed algorithm are effectively applicable,
A comprehensive empirical analysis showing large gains over extensions of existing algorithms for closely-related problems.
1.1 RELATED WORK
Our paper spans correlation clustering, clustering with budget constraints, and learning from multi- ple annotators. For brevity, we focus on the closely related key works in these areas.
Correlation clustering is one of the most well studied graph clustering problems and has been actively researched over the past 15+ years (see the book (Bonchi et al.) 2022)). has numerous applications in ML and beyond, including spam detection (Ramachandran et al. 2007] BBnchi et al., 2014), social network analysis (Bonchi et al. 2015 Tang et al. 2016)), entity resolution (Getoor &
Machanavatjhala 2012). and many others GGions et al. [2005] Hassanzadeh et al., 2009 Cohen & Richman 2002; Kim et al., 2011). Bansal et al. (2004) introduced and gave the first constant factor approximation for complete graphs (see Def. I.I.. Variants include incomplete signed graph
(Bansal et al.) 2004) Ailon et al. 2008). where the problem is APX-Hard (Demaine et al.) 2006). and
weighted graphs (Charikar et al. 2005). where it is Unique-Games hard (Chawla et al. 2006).
2

---

Published as a conference paper at ICLR 2023
Clustering under budget constraints studies the problem of limited number of pairwise similarity queries. In this setting, a line of work looked at spectral clustering on partially sampled matrices: Fetaya et al. (2013) in general setting, and (Shmmir& & Tishby (201T) and Wauthier et al. (2012) for bi-partitioning. The most relevant works to our paper are those of Garefa-Soriano et al. (2020b)
and Bressan et al. (202T) who devised algorithms for correlation clustering that given budget of Q
queries attain a solution whose expected number of disagreements is at most 3- OPT +0 a ) where OPT is the optimal cost for the instance. Another closely related line of work studies clusterl queries for various clustering problems including CC (Ailon al., 2018 Saha & Subramanian 2019). The differences between these works and ours are (I) they assume all (2) similarity queries are already known in advance whereas we must query the strong signal to obtaín similarities, (2)
q
their queries give access to the optimal clustering, whereas we only query for edge signs.
Learning from multiple annotators considers cost-effective learning from multiple annotators where the cost of a labeler is proportional to its overall quality. The most relevant work to our setting is (Guha al. 2015) as it considers hierarchical clustering which uses lightweight similarity scores to identily candidate pairs with high similarity and they present a near-linear algorithm that 8 to 30 times faster than previous algorithms practice; see Section A for a detailed comparison. Lastly we survey additional related works on learning from multiple annotators as well as algorithms with predictions in Section A
1.2 PRELIMINARIES AND NOTATION
The input of correlation clustering is complete undirected graph G = (V, (V,E+UE)) on V = vertices. E+ and F represent the partitions of all possible (2) edges where an edge (u. v) E
E indicates that u and u are similar and e = (u, v) E E indicates that and are dissimilar. We simplify the notation G (V, E E+) so any present edge is a positive edge and any missing
edge is a negative edge. Additionally, we use m to denote the size of EE and I(v) = {u (v.u) E} to denote the neighborhood of vertex V.
:..................... } of V into disjoint subsets. Let Cv denote the indi- cator variable the vertices v and u are assigned to the same cluster. We study the min-disagreement formulation of the correlation clustering problem defined as follows (Bansal et al.) (2004).
A clustering is partitioning C' = {C1, C......
Definition 1.1 (Correlation Clustering (CC)), Given a graph G (V, E), the objective of correla- tion clustering (CC) is to output a clustering C that minimizes:
Σ
Cu.u +
Σ (1-Cr,u). c=(r,a)E
(1)
(=(UN))E
The most well-known CC algorithm is KwikCluster (Ailon et al., 2008), which proceeds by successively picking vertex p. called a pivot, uniformly at random from the graph and forming cluster {p] (p)). The algorithm removes this cluster and recurses on the remaining graph until all vertices are assigned to clusters. Based on the fact that the set of pivots a maximal independent set constructed from a random order of vertices, Bonchi et al. (2013) suggests an equivalent algorithm that first constructs the independent set and then assigns any non-pivot to its first neighbor in the in- dependent set. Both algorithms yield 3-approximation in expectation, however the second algorithm more efficient as the assignment of non-pivots can be performed in parallel.
Despite practicality and simplicity of KwikC access to the full similarity graph G and is not feasible when similarity measures are expensive to acquire. We consider budget CC studied before by (Garcia-SSoraano et al.] [220a]] Bressan et al.) 2019) where there is a limit (budget) for the number of queries that can be made.
(and its variants), the algorithm assumes
Definition 1.2 (Expensive Strong Oracle). Given an edge e, the query Os(e) outputs whether e E, ie.., is positive edge.
Following the motivations provided in Section we also introduce second weaker oracle which is cheaper to query.
Definition 1.3 (Cheap / Weak Oracle), Given any vertex v, the query Ow (v) outputs a similarity score in R between and every other vertex in V, where higher values indicate higher similarity
3

---

Published as a conference paper at ICLR 2023
We frequently refer to the graph G' as the strong signal graph and likewise strong signal edge refers to an edge in E. We interchangeably use the terms signal or oracle, the terms strong and expensive signal, and also the terms weak and cheap signal.
THEORETICAL MODELLING FOR ALGORITHM DESIGN
We introduce an algorithm that leverages the cheap signal for strong signal query efficiency. Our goals are twofold: (1) Design a flexible algorithm paradigm which can adapt to incorporate con- straints necessitated by practice, i.e., limited access expensive queries, (2) Analyze the quality of the produced solution with respect to the CC objective (see equation D We first introduce a mod- elling assumption for the weak oracle for the purpose of theoretical analysis. While this results in a different but related weak oracle formulation compared to Definition 1.3 it lets us derive a robust algorithm design which we subsequently adapt to the more realistic setring of Definition [.3
First, we introduce a noise factor that determines the usefulness of a weak signal. ? 0 corre- sponds perfect weak signal that exactly matches the strong signal and 7 = n corresponds to completely uninformative weak signal.
Assumption 2.1. For fixed noise parameter y > 0, the query (v) outputs subset of V such that T(u) S (u) and (w)( S (1 (1+)))
The existence of such signal with a small 7, say O(1/n) or < 1 might seem like strong assumption for most applications. However, our experiments show that weak signal can actually provide predictive hints about the true underlying strong signal graph. More precisely, given vertex v. we order V with respect to the weak signal, and observe that true strong signal neighbors of v are often ranked higher. Thus the simple procedure of returning the most similar vertices for input node captures many of the true strong signal neighbors of v and mimics the clean abstraction of Assumption (See Appendix [.6 for further empirical justification).
Using the above characterization. we next explain the high level ideas of our algorithm KwikBucks (Algorithm []. It is inspired by variant of Kwi kkl uster (Bonchi et al. 2013) adapted to two oracle setting. In this variant, we first pick pivots by forming a maximal independent set from a random ordering of vertices, and then assign non-pivots to their first neighbor (which must exist by maximality of the independent set). A naive extension of this algorithm can result in 2(n2-5) queries to the strong signal (see B.I). However, one may argue that by using the weak signal, we can prune the possible neighborhood of vertices which results in fewer strong signal queries.
While the weak signal can help us make smarter queries to the strong signal, we can still show that even for a weak signal with small error rate, i.e., 7 (1). we still need 2(n²) queries to the strong signal when forming a maximal independent set (see B.2 To circumvent this difficulty, we consider another modification of KwikClusts a maximal independent set, we pick vertices uniformly at random and then pick an independent set from them. The caveat of this approach is that some non-pivots may not have any neighbor in the chosen pivot set, and so these non-pivots are returned as singleton clusters. This results in an algorithm which returns solution with cost at most 30PT + +O(n /t). We additionally modify this algorithm by incorporating the weak signal to further prune possible strong signal queries. While this algorithm has additive error for correlation clustering cost, it helps direct queries to "impactful" portions of graph. We now have all the ingredients (and motivation behind them) for describing our algorithm, KwikBucks.
by Bonchi et al. (2013) where instead of picking
Kwi wwikkuuks first picks all pivots via random sampling as shown in Get rettivoos: each sampled vertex is added the pivot set if it is not connected to the current subset of pivots that trimmed down by WeakFin willerr (which uses the weak signal). Then, it continues to assign non-pivots to clusters, through
which finds the first vertex (rirstNeighbor) in the subset of ordered pivots trimmed down by the weak signal via WeakF i lter. If no such vertex exists, then the vertex is assigned to its own cluster, i.e., a singleton cluster. Note that having a small t (the number of sampled vertices) helps query efficiincy by functionally reducing the set of vertices that the weak signal is applied to (both when selecting pivots and when assigning to pivots) and then further queried by the strong signal. This comes at the cost of small additive error. Our next theorem formally bounds the number of queries and the effect of t (See Appendix [B] for full proof).
4

---

Published as a conference paper at ICLR 2023
Algorithm GetPivots(t,,)
Algorithm KwikBucks (Our Algorithm)
Require: A bound on the number of sampled vertices,
Require: A bound on sampled vertices, t, the
t. the remaining strong signal budget, Q.
strong signal budget. Q.
{uI,.... ...: 0t)
t sampled vertices
1: P f- GetPivots(,.Q)
2: P + {
2: return aasiignoolusttes(((
for 2 do
4: N₃ f- WeakFilter(v,, P)
#FirstNeighboz(ee N,, Q) then
Algorithm Assi.gntoclusteerssP...
6:
P PU {u;
Require: List of pivots. P, vertex set, U, re-
return
maining strong signal budget, Q.
Algorithm #FirstMeighbor(u..
1: < 0 (the set singletons}
2: Cp f {p} {cluster for any pivot E P)
Require:
ordered list of vertices, N, the remaining strong signal budget, Q. while > 0 and N * 0 do
Input vertex,
3: while Q > and U * do
4: и extract first vertex of U
5:
N, t WeakFilter(v, P)
2: u f- extract first vertex from N
6:
p FirstNeighborr No, Q)
3:
Q+
7:
p + then
4: Of u) = then
8:
C C, [c}
5:
return {u}
9: else
6:
return
A Au
11: A 1++A4 AUU
Algorithm WeakF
return UperCp UsEA {c}
Return (w)
Theorem 2.1. Under Assumption 2.1 KwikBucks uses n + 2ytm/n + 2/t2m/n2 queries to Os to achieve approximation 3OPT Onn²/t).
Proof Sketch. For a fixed vertex the number of vertices incorrectly identified as neighbors of by Ow (u) is bounded by 7 [,)],, so FirstNeighbor algorithm makes at most [/]] + to the strong oracle. The additional +1 term for sampled É vertices and non-pivots can be bounded by + f term. So we need to bound 7 ( for an arbitrary vertex u. Now for each vertex u, since look at intersection of its weak signal neighbors and pivots, average
queries
expect t/n (n)/[[[[)) Since Evev [[v)] = 2m, this means that the total number calls from non non-pivots pivots can be bounded by 2ytm/nn For randomly chosen vertices, we can again apply the similar argument with additional information that vertex is included in this set by probability t/n and hence get 2yt2m/n² The approximation guarantees of our algorithm follow from those of WwikClustee with a caveat: is possible that some non-pivots do not connect to any pivot. Picking suitable value for the number of initially sampled pivots ensures that such vertices only introduce small additive error.
Our next corollary, considers the interesting case of constant-size pivot set, i.e., ( 1/e, which will incur an additive error of En?. This can be thought as the 'right scale' as we make a mistake on only an fraction of all edges. We complement
corollary by presenting matching lower bound the appendix (Lemma B.7) showing that O(n + dy/e) strong signal queries are necessary obtain the guarantees of Corollary 2.2
Corollary 2.2. Let d be the average degree of the strong signal graph and suppose is sufficiently large (n > 1/e). We can achieve approximation 3-OPT +en? with n - O(dr/E) queries to O
Importantly, our design is modular, i.e. composed of few fundamental components which can be individually optimized based on practical constraints. In the next section, augment some of these components to address pragmatic considerations to better align the algorithm to practice.
3 THE FINAL EMPIRICAL ALGORITHM
We now extend the algorithm for the idcalized setting of Section 2 into a practical version of Kwi kBucks for general weak signals, i.e. Definition 1.3 While this version does not satisfy
5

---

Published as a conference paper at ICLR 2023
Assumption 2.1 and hence does not have similar approximability guarantees, it still retains some theoretical motivation (sketched below), and is empirically very successful (see Section 4
The modifications make for our practical algorithm are based the following natural inductive bias: 'similar' edges according to the strong signal are likely to have a high weak signal similarity score. At high level, we incorporate this assumption throughout our algorithm design by ranking potential queries to the strong signal according to weak signal similarity values.
The most noticeable change occurs for BeakFilters In our theoretical modelling, it returns a subset of S which intersects with the noisy neighborhood returned by the cheap oracle. For the general weak signal version (Definition [.3). update the WeakFilted
Modifying MeakFilter to WeakFi
function to instead rank the vertices in S with respect to the weak signal similarity to and then output the top k elements in S with the highest similarities (Algorithm ()) Intuitively, for a suitable parameter k, the top k candidates capture many of the strong signal neighbors of in S. Indeed, we empirically verify this in our experiments and show that predictive weak signals usually rank true strong signal neighbors much higher compared to random ordering. For our experiments we fix k = 100 and perform ablation studies on this parameter.
To better understand the effect of this modification, consider AssignClusters where non- pivot vertices attempt to connect to pivot. In our theoretical modeling and in the classical KwikCluster algorithm, each non-pivot vertex
Algorithm 6 WeakFi SeakkFilteBeee LeaakiiiLer.yy/lakm.nggg... S,k)
Require: Input vertex et set C V
I: w; + similarity of (v, u.) for all u, E S as computed by weak signal
2: Sort elements of S in decreasing w, values
3: Return First k elements of new sorted order
checks for a strong signal edge
among the list of pivots in an ordering which is fixed for all vertices. This ordering can be thought of as the ordering inherited from GetP ivoos.. In contrast, WeakFin ilt erBeerrkynin introduces a data adaptive ordering step where each non-pivot vertex can re-rank pivots based on weak signal similarities. As shown in Section 4 this has a sizeable impact on the empirical performance of our algorithm. In Section D.I we explain these gains by introducing natural data model that makes some well-motivated assumptions about the relationship between the strong and weak signal, as well as the inherent clusterability of the underlying graph. Under this model, we prove that the quality of the clustering after re- re-ranking is strictly better than for the unranked filter.
Further optimizations. Exploiting the ranking theme further, we make three additional enhance- ments to KwikBucks. The first one simply sorts the non-pivots based on the maximum weak signal similarity to the pivots so that 'easier' non-pivots are assigned clusters first which improves query efficiency. The second one modifies the WeakF 1terByRank ing function slightly by increasing the weak signal similarity value between a non-pivot e and a pivot p if p has 'many' nearest neigh- bors (in weak signal similarity) of already in its cluster. Finally, the last enhancement introduces a post-processing step where we potentially merge some clusters after our algorithm terminates. As shown in Section D.2, this optimization is motivated by a theoretical worst-case example for Kwi wwikCluster. The merging step proceeds by first curating a list of clusters to consider for merg- ing based on the average weak signal value between the two clusters and we sample small number of strong signal edges between potential clusters to merge to determine if the pair is suitable for merging. Each of these optimizations is described in detail in Section
4 EXPERIMENTS
Datasets. We use 9 datasets, 8 publicly available and 1 proprietary internal. Each dataset exhibits different properties such as varying strong signal graph densities and diverse strong and weak signals to demonstrate the versatility of our method. We provide high-level descriptions here and refer to Section E for more details.
Four public datasets are comprised of text inputs: Stackoverflow (SOF) (Xu et al. 2017) Search- Snippets (Phan et al. 2008), Tweet (Yin Wang 2016) and AgNews (Rakib et al. 2020). For Stackoverflow and SearchSnippets, as the cheap signal and a large cross-attention based language model as the strong signal. For Tweet and AgNews, BERT embedding similarities (Devlin et al. 2018) are the cheap signal; the strong
word2vec embedding similarities (Mikolov et al. 2013)

---

Published as a conference paper at ICLR 2023
signal of an imput pair is the indicator variable of the two examples belonging to the same class plus a small amount of i.i.d. noise to prevent the formation of disconnected connected components, which is the 'easy' case for KwikCluster |
The other four public datasets are comprised of attributed graphs: Cora (Sen et al. 2008), Ama- zon Photos (Shchur al. 2018), Citeseer (Sen et al. 2008), and Microsoft Medicine (Shchur & Günnemann, 2019). For Cora and Amazon photos, node embedding (learned using deep graph infomax (Velickovic et al. 2019) similarities are the cheap signal; the strong signal is generated similarly to those of Tweet and AgNews. For Citeseer and Microsoft Medicine, node attribute simi- larities are the cheap signal and the existence/absence of edges in the graph is the strong signal.
Moreover, we report results on a large proprietary dataset based on the shopping reviews of a com- mercial website. We use internally developed (and finetuned) embedding based and cross-attention based language models for the cheap and expensive signals respectively; both models are based on the publicly available language models such as BERT and T5 (Raffel et al., 2020).
Baselines. Since our work is the first correlation clustering algorithm which utilizes both strong and weak signals, we adapt algorithms from prior work, e.g. some which only use a strong signal, to our setting. In addition we propose several new natural algorithms as baselines.
Baseline 1: A variant of Kwi wwikkssks where we do not use the weak signal ordering computed in Algorithm [ when checking for a strong signal edge between node and a set of pivots. Rather we use the the order the pivots were picked (each vertex always queries pivots in the same order). This is the ordering necessary for the theoretical guarantees of the Kwi KwikCluster algorithm and our guarantees of Section 2
Baseline 2: Algorithm presented in
et al. 2020a Bressan et al. 2019). It follows the KwikClus Sriikklustee algorithm and uses the strong signal to query edges. II the query budget is depleted, the algorithm is terminated and any remaining vertices are returned as singletons.
Baseline 3 / 4: We compute a k--N graph based on the weak signal to narrow down the set of all possible queries
small set of relevant pairs. Each edge of the k-NN graph is re-weighted (either 0 or 1) based on the strong signal. Baseline 3 runs the classic spectral clustering algorithm and baseline 4 runs the vanilla Kwi kC usstr algorithm to completion on this graph.
Baseline 5: This baseline is inspired by the baseline used in (Garcia-Soriano et al., 2020a). We pick random vertices and query their complete neighborhood using the strong signal. kt is again chosen as high as possible within the allotted query budget. Instead of running propagation algorithm, which was already shown in (Garcia-Sore) Soriano et al. (020a) to be inferior to Baseline 2, we simply run the vanilla Kwi kCluster algorithm to completion on this graph.
affinity
Evaluation metrics. We evaluate our algorithm and baselines based on the correlation clustering objective (equation TT. For the purpose of evaluating metrics, we use all edges of the strong signal graph in contrast to the duration of algorithm execution which we limit the access. In addition, we compute the precision and recall of edges of the strong signal graph. Given a clustering C, its precision is defined the ratio between the number of strong signal edges whose endpoints together in the same cluster and the total number of pairs of vertices clustered together in C. The recall is defined as the fraction of all strong signal edges whose vertices are clustered together in some cluster of C; see equation 2 andd 3
These values represent two extremes which must be balanced: recall maximized if all vertices are clustered together whereas precision is maximized if clusters just consist of single edges. These values are more meaningful than the CC objective alone in cases where the strong signal graph is sparse (see Section F). It's not always possible to maximize both precision and recall; Section D.3 provably shows an inherent trade-off between these values. We combine the precision and recall into a single metric via the standard Fi score and report this value as function of the query budget. In our experiments, we plot averages of 25 trials and the standard deviation.
Parameter configurations. Our algorithm has two main parameters to select: t in Algorithm corresponding to the number of vertices we select uniformly at random which is then pruned to form the set of pivots, and l in (oarithmmmoocrrreppooon based on the vignal similarity for the strong signal to query. We pick both these parameters in data-driven manner. Thorough motivation and trade-off' associated with both parameters are
to the number of top vertices we select
One can easily show that in such case the classical Kwi kCT uster algorithm is able to recover OPT.

---

Published as a conference paper at ICLR 2023
Table 1: F1 values for a fixed budget of 3n the expensive-strong signal, where a indicates the dataset size. For Citeseer and Medicine, we use a budget of 50n as they have substantially sparse graphs. Winners are bold and second winners are underlined.
SOF
Search
Tweet
AgNews
Cora
Photos
Citeseer
Medicine
Internal
Avg.
B1
.1=.0
.73+
.02.0
74+.01
.57
-4 o1
007.01
.02+m
.00+.0
.30
B2
.28 i
1
.15
_4
1
.53 is
.09 or
.031m
.0
.36
B3
.33-ur
-1+
666..04
.4
.66+
.00
.00+
B4
_01_1e
1.
.031m
.001.co
101
100
.61..
.25
.00
.08
B5
.00-to
.00+m
.00+.00
.00..co
.00+.0
.00+00
.04..0
.00+
.00+00
.00
KwikBucks
.72_.06
.92
.2
.87
.8
.3:mm
21
.29
.14:a1
.59
presented in Section H2, ablation studies of these parameters provided in our empirical results. Lastly, we always reserve 10% of the query budget for performing the merge post processing step. If the main algorithm terminates with remaining budget, we correspondingly increase the merge post processing budget to incorporate this.
Results. We highlight the key experimental themes and defer additional details to Appendix F
Superior performance over baselines: Table D shows that our algorithm outperforms the baselines in terms of the Fi metrie: it consistently has the highest Fi value for the fixed query budget result displayed in Table T. For example for the SOF dataset, the best baseline has a 2.2x factor smaller F1 value. Figures (b) show the CC objective and F1 score as a function of the query budget for the SOF dataset. It shows that our algorithm achieves a higher Fi score and a lower correlation clustering objective value with only s 7 100 queries whereas the baselines require at least 25 10 queries to match KwikBuck, a 3.6x reduction in query complexity. Intuitively, the weak signal allows us to make clustering progress much faster by directing the query budget to impactful strong signal queries after filtering using the weak signal. The results for other datasets are deferred to Figures 3 and ii the appendix which display qualitatively similar behaviour. The strong signal graphs of Citeseer and Medicine are quite sparse. Therefore for these datasets, the trivial clustering of all singletons already achieves very low CC objective score. As argued above, in these cases the Fi score is much more meaningful measure of cluster quality. As shown in Figures [ our algorithm achieves superior Fi values compared the baselines. Lastly we note that the performance of our algorithm stabilizes once it has exploited sufficiently many strong signal queries. We note that B3 is omitted from the CC objective value plots for clarity as it always had much higher objective value than other algorithms.
with 7 -003 queries, showing the efficacy of our algorithm with
Relative performance of baselines is dataset dependent: As shown in Table I for many datasets such as Cora, Search, and AgNews, B2 is the best among our five baselines. However this does not generalize across all datasets. As shown in Figures 4 B3 is the best baseline (with respect to the Fi score) for the Tweet and Photos datasets while B4 is the best baseline for the Citeseer and Medicine datasets. B4 can be competitive bascline in the case where the strong signal graph is extremely sparse, such as in Citeseer (see Figure 4.. This is because the weak signal k-NN graph is able to recover many relevant edges of the (sparse) graph if the weak signal is informative.
Varying weak signal performance: We perform addition weak signal ablation studies with the SOF and Search datasets. We replace the Word2 (W2V) embeddings used in our cheap oracle with tf-idf embeddings and fix all other components of the algorithm. Figure (Tc) and 7 show the performance of our algorithm on these datasets and in both cases, the algorithm's performance noticeably worsens. The intuitive answer for why this is the case is because the alternative weak similarities computed from tf-idf embeddings are worse than W2V embeddings at ranking strong signal neighbors. We empirically verify this claim. For every vertex v in the SOF dataset, we rank all other vertices in decreasing weak signal similarities to v. The average rank of the true strong signal neighbors of v is then computed and this value is plotted in histogram for all vertices in Figure [d). A 'good' weak signal should rank actual strong signal neighbors much higher than non strong signal neighbors. Indeed we observe this to be the case for the W2V embeddings and this fact is qualitatively captured the aforementioned figures which show that W2V has superior Fl score plots. We also observe that even the weaker tf-idf embeddings still provide significant gains over not using a weak signal. Overall, these experiments along with Baseline B empirically verify that (1) the quality of the weak signal correlates with the performance of the algorithm, and (2) the
8

---

Published as a conference paper at ICLR 2023
Stackoverlow
Stackoverllww
Stac Stackoverllw
1.6
0.8
0.8
0.7
1.4
0.5
B2
Correatie Clustering
1.2
0.5
WZV Weak Signal (owkBucks) tr-if Weak
1.0
KeikBucks
05
0.4
0.3
Bascline
0.8-
82
0.2
0.2
0.6
0.1
0.0
300
6625
12750 Query Budget
18875
25000
500
6625
12750
10075
25000
300
12/50
18875
25000
Query Budget
Query Budget
(a)
(b)
(c)
16-41
Stackeverllow
cleveverr
Stackoverllew
W2V Weak Signal
8
tr-iff Weak Signal
0.5
0.4
0.4
4
0.3
KwikBucks
C 0.3
0.2
Without Marging
0.2
KwikBudk
0.1
Without Nelghborhood
0.1
Small Pivot Choice
Without Ordering Non-Pavots
Large Plvot Choice
%
1900
2000
3000
4000
0.0
500
6525
13750
18875
25050
0.0
535
6:25
33753
18575
25300
Average Rank of Strong Signaa Neighbors
Query Budget
Quary Budget
(d)
(c)
(a) and (b) represent the CC objective and the Fi-scores for the Stackoverflow dataset across various query budgets. (c) compares performance across weak signals of various strength (Baseline 1 corresponds to random weak signal). (d) represents (normalized) histogram showing average rank assigned to actual strong signal neighbors by two different weak signals (lower is better). (e) represents an ablation study on some of the main components of the algorithm. (f) represents a sensitivity analysis to the parameter corresponding to the number of pivots selected.
Figure 1:
two-oracle framework introduced is superior than the previously studied single-oracle setting even when the cheap signal is considerably weak.
Ablation studies. We perform ablation studies all tune-able parameters of our algorithm. A sam- ple of the ablation studies for SOF is shown in Figure Te) and details of other results are presented Section F.4 We observe that removing any of the main components of the algorithm (merging, ordering with respect to weak signal, and ordering with respect to the statistics of the neighbor- ing nodes) deteriorates the performance of the algorithm, thus all the introduced components are paramount in Kw i Bucks. We also verify the role of the parameter t corresponding to the number of pivots we select for our algorithm Figure I[). We observe that both large and small choices for this parameters can be harmful, but choosing larger values is safer option compared to smaller values as it asymptotically offers a similar performance as the optimal value. Section F2 provides more details on the choice of this parameters and the other parameters of KwikBucks.
5 CONCLUSION
We introduced and studied novel variant of the (budgeted) correlation clustering algorithm where besides having a limited query budget to an expensive-strong oracle, one also has access to a read- ily available cheap-weak oracle. We developed an algorithm for this setting with strong theoreti- cal motivations. We also demonstrated strong practical motivations by showing how the proposed framework and algorithm can be effectively used for realistic clustering applications, where mas- sively scaled MI models yield highly accurate signals but cannot be used indiscriminately. We anticipate the proposed framework could become a standard building block, especially for text clus- tering strategies, and envision extensions of the framework to several other ML problems where combinations of expensive-strow cial recommendation systems, the "standard practice for machine learning-din driven recommendations in industry" (Wong) 2022) is a two-step procedure of cheaply retrieving a set of candidates and then iterating over them with more powerful but costlier scoring model (Wong. 2022
and cheap-weal weak signals are available. For example in commer-

---

Published as a conference paper at ICLR 2023
REFERENCES
Retrieval, scoring, and re-ranking, Jul 2022. URL htt.:ppps///eeellgrrs.g.ogggeoee com/
machine- httrr////e..coeeaaaaaaao////eeae
Re-ranking, Sep 2022. latest
URL httpps///ggprrrtttrorddd///////p
Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5):23:1 2008
Nir Ailon, Anup Bhattacharya, and Ragesh Jaiswal. Approximate correlation clustering using same-cluster queries. In Michael A. Bender, Martin Farach-Colton and Miguel A. Mosteiro (eds.), LATIN 2018: Theoretical Informatics 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, volume 10807 of Lecture Notes in Computer Science, pp. 14-27, Springer, 2018. doi: 10.1007997833331--7740--
Science
URL
Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions, 2022.
Alcxandr Andoni, Piotr Indyk, and lly Razenshteyn. Approximate nearest neighbor search in high dimensions. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pp. 3287-3318. World Scientific, 2018.
Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In International Conference Machine Learning. pp. 345-355. PMLR, 2020a.
Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online match- ing problems with machine learned advice. Advances Neural Information Processing Systems, 33:7933-7944, 2020b.
Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Gar- nett (eds.), Advances in Neural Information Processing Systems 29: Annuul Conference Neurul Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp- 2016. URL httpttsss///ppopeeeeennee neur. pps. cc http/paprr/2ccc6 htt.///211hhah///// 9597353e41e695778 (tt.:oo527779211444lcll1o Atsteeaaatta---ttaaattt..... html
Abstract
Pranjal Awasthi, Avrim Blum, and Or Sheffet. Center-based clustering under perturbation stability. Inform. Process. Lett., 1 (1:(1-)):49 2012.
Maria Florina Balcan and Yingyu Liang. Clustering under perturbation resilience. In International Colloquium on Automata, Languages and Programming, 2012.
Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented en- ergy minimization via speed scaling. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020a.
Étienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning aug- mented algorithms. In Advances in Neural Information Processing Systems 33: Annual Confer- ence on Neural Information Processing Systems, NeurlPS, 2020b.
Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning, 56(1): 89-113, 2004.
Michael Barz and Daniel Sonntag. Incremental improvement of a question answering system by re-ranking answer candidates using machine learning. In Increasing Naturalness and Flexibility in Spoken Dialogue Interaction, pp. 367-379. Springer, 2021.
Jo
Bergum.
Pretrained
transformer
language
models
for
search,
June
2022.
URL
vespa. ai/
pretral ned- trans former- la language -aw-fffr-srraraaat---a
10

---

Published as a conference paper at ICLR 2023
Francesco Bonchi, David García-Soriant and Konstantin Kutzkov. Local correlation clustering. CoRR, abs/l 2013. URL_atp:://axxx: org/ absa/aas/.....
Francesco Bonchi, David Garcia-Soriano, and Edo Liberty. Correlation clustering: From theory to practice. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '14, pp. 1972, New York, NY, USA, 2014, Association for Computing Machinery. ISBN 978145039 doi: 10.1145/2622333.26600000 URL https:
1.0b..or9/1..114//222333333 2251////22223333230003388 2630880
Francesco Bonchi, A. Gionis, Francesco Gullo, Charalampos E. Tsourakakis, and Antti Ukkonen.
Chromatic correlation clustering. ACM Trans. Knowl. Discov. Data, 9:34:1-34:24, 2015.
Francesco Bonchi, David García-Soriano, and Francesco Gullo. Conclusions and open problems.
Correlation Clustering, pp. 113-114, 2022.
Marco Bressan, Nicolò Cesa-Biance Andrea Paudice, and Fabio Vitale. Correlation Clustering with Adaptive Similarity Queries. Curran Associates Inc., Red Hook, NY, USA, 2019.
Marco Bressan, Nicolò Dasa-BBanchi, Silvio Lattanzi, and Andrea Paudice. On margin-based cluster recovery with oracle queries. Advances Neural Information Processing Systems, 34:25231- 25243, 2021.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020.
Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In Proceedingy the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '01, pp. 642-651, USA, 2001. Society for Industrial and Applied Mathematics. ISBN 0898714907.
Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative informa- tion. Journal of Computer and System Sciences, 7 71(3):60-338, 2005.
Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D Sivakumar, On the hardness of approximating multicut and sparsest-cut. computational complexity, 15(2):94-114 114, 2006.
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, and Michael Zhang. Triangle and four cycle counting with predictions in graph streams. In The Tenth International Conference on Learning Representations, ICLR, 2022.
William W Cohen and Jacob Richman. Learning to match and cluster large high-dimensional data sets for data integration. In Proceedings of the eighth ACM SIGKDD international conference Knowledge discovery and data mining, pp. 475-480, 2002.
Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple teachers. The Journal of Machine Learning Research, 13(1):2655-2997, 2012.
Erik D Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, (61(2-3) 2006.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 11x1v:1810.04800, 2018.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In Proceedings of the 38th International Conference on Machine Learning, ICML, pp. 2687-2696, 2021.
Pinar Donmez. Proactive learning: Towards cost-sensitive active learning with multiple imperfect oracles. 2008
Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner. Learning-based support estimation in sublinear time. In 9th International Conference on Learning Representations, ICI.R 2021.
11

---

Published as a conference paper at ICLR 2023
Derek
Eder,
Jun 2022.
URL
http::///icrooottt.giiiii Lew.s/bbaeee/be//e/////a/
Meng Fang, Xingquan Zhu, Bin Li, Wei Ding, and Xindong Wu. Self-taught active learning from crowds. In 2012 IEEE 12th international conference data mining, pp- 858-863. IEEE, 2012.
Ethan Fetaya, Ohad Shamir, and Shimon Ullman. Graph approximation and clustering budget. In Artificial Intelligence and Statistics, pp. 241-249. PMLR, 2015.
David Garcfa-Soriano, Konstantin Kutzkov, Francesco Bonchi, and Charalampos Tsourakakis. Query-efficient correlation clustering. In Proceedings of The Web Conference 2020, pp. 1468- 1478, 2020a.
David Garefa-Soriano, Konstantin Kutzkov, Francesco Bonchi, and Charalampos Tsourakakis. Query-efficient correlation clustering. In Proceedings of The Web Conference 2020, pp. 1468 1478, 2020b.
Lise Getoor and Ashwin Machanavajhalla Entity resolution: Theory, practice & open challenges. Proc. VLDB Endow., 5:2018 1-201820019 2012.
A. Gionis, Heikki Mannila, and Panayiotis Tsaparas. Clustering aggregation. 21 International Conference on Data Engineering (ICDE (CCDE'05), pp. 341-352, 2005.
Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Proceedings the 36th International Conference on Machine Learning, ICML, pp. 2019.
Ramanathan Guha, Vineet Gupta, Vivek Raghunathan, and Ramakrishnan Srikant. User modeling for personal assistant. In Proceedings of the Eighth ACM International Conference Web Search and Data Mining, pp. 275-284, 2015.
Oktie Hassanzadeh, Fei Chiang, Renée J. Miller, and Hyun Chul Lec. Framework for evaluating clustering algorithms in duplicate detection. Proc. VLDB Endow,, 2()::)(221222229999 2009. doi: 10. 14778/16677277.687771 pdf
vldb. http::/wwwwww.bbbboooooooo//////
Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In 7th International Conference on Learning Representations, ICLR, 2019.
Sheng-Jun Huang, Jia-Lve Chen, Xin Mu, and Zhi-Hua Zhou. Cost-effective active learning from diverse labelers. In IJCAI, pp. 1879-1885, 2017.
Panagiotis G Ipeirotis, Foster Provost, Victor S Sheng, and Jing Wang. Repeated labeling using multiple noisy labelers. Data Mining and Knowledge Discovery, 28(2):402 441, 2014.
Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff. stream algorithms. In 8th International Conference on Learning Representations, ICLR, 2020.
data
Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, and Chang Yoo. Higher-order correlation clustering for image segmentation. Advances in neural information processing systems, 24:1530- 1538, 2011.
Christopher Lin, Daniel S Weld, et al. To (label), not (label). In Second conference on human computation and crowdsourcing, 2014.
Christopher H Lin, Mausam, and Daniel S Weld. Reactive learning: Actively trading off larger noisier training against smaller cleaner ones. In Proceedings of the 32nd International Con- ference on Machine Learning, Lille, France (ICML), 2015.
Thodoris Lykouris and Sergei Vassilvitsküi. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference Machine Learning, ICML., pp. 3302-3311, 2018.
Luigi Malago, Nicolo Cesa- Bisa-Bianchi, and Renders. Online active learning with strong and weak annotators. In NIPS Workshop Learning from the Wisdom of Crowds, 2014.
12

---

Published as a conference paper at ICLR 2023
Aditya Menon, Sadeep Jayasumana, Ankit Singh Rawat, Seungyeon Kim, Sashank Reddi, and San- jiv Kumar. In defense of dual-encoders for neural ranking. In International Conference on Ma- chine Learning, pp. 15376-15400. PMLR, 2022.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. arXiv preprint arXivv1301.3788 2013.
Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. Ad- vances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurlPS, pp. 462-471, 2018.
Kim Thang Nguyen and Christoph Dürr Online primal-dual algorithms with predictions for packing problems. CoRR, abs/2110.00391, 2021.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn Machine learning in python. the Journal of machine Learning research, 12:2825-28 2011.
Xuan-Hieu Phan, Le-Minh Nguyen, and Susumu Horiguchi. Learning to classify short and sparse text & web with hidden topics from large-scale data collections. In Proceedings of the 17th international conference on World Wide Web, pp. 91-100, 2008.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Infor- mation Processing Systems, NeurIPS, pp. 9684-9693, 2018.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al. Exploring the limits of transfer learning with a unified text-to-text transformer. Mach. Learn. Res., 21 ((1140):1667, 2020.
Md Rashadul Hasan Rakib, Norbert Zeh, Magdalena Jankowska, and Evangelos Milios. Enhance- ment short text clustering by iterative classification. In International Conference on Applica- fions of Natural Language Information Systems, pp. 105-117. Springer, 2020.
Anirudh Ramachandran, Nick Feamster, and Santosh S. Vempala. Filtering spam with behav- ioral blacklisting. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson (eds.). Proceedings of the 2007 ACM Conference on Computer and Communications Security, CCS 2007, Alexandria, Virginia, USA, October 28-31, 2007, pp. 342 351. ACM, 2007. doi: 10. 00.1145/1315245.1155588 /ttp//////////ooo.oo///////////0
11w.:111111111451111111 1315228
Radim Rehurek and Petr Sojka. Gensim-python framework for vector space modelling. NLP Centre, Faculty of Informatics, Masaryk University, Brno, Czech Republic, 3(2), 2011.
Barna Saha and Sanjay Subramanian. Correlation clustering with same-cluster queries bounded by optimal cost. In Michael A. Bender, Ola Svensson, and Grzegorz Herman (eds.). 27th An- nual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of L/Ples, pp. 81:1-81:17. Schloss Dagstuhl Leibniz-Zentrum für In- formatik, 2019. doi: 15S URL. https: /ww. 0ot.e...or/10.233... LIPICs. ESA. 2019.81
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
Ohad Shamir and Naftali Tishby. Spectral clustering budget. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 661-669. JMLR Workshop and Conference Proceedings. 2011.
Or Sharir, Barak Peleg, and Yoav Shoham. The cost of training nlp models: A concise overview. arXiv preprint 20Xiv:2004.08900, 2020.
Oleksandr Shchur and Stephan Günnemann. Overlapping community detection with graph neural networks. arXiv preprint arXiv: /909. /220/, 2019.
13

---

Published as a conference paper at ICLR 2023
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1eI.iv:8111.00000 2018.
Jiliang Tang, Yi Chang, Charu C. Aggarwal, and Huan Liu. A survey of signed network mining in social media. ACM Computing Surveys (CSUR), 49:1 37, 2016.
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng-Tze Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al. Lamda: Language models for dialog applications. arXiv preprint arXiv:2201. 008239. 2022.
Ruth Umer, Shai Ben David, and Ohad Shamir. Learning from weak teachers. In Artificial intelli- gence and statistics, pp. 1252-1260. PMLR, 2012.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR, 203):4,00 2019.
Fabian L Wauthier, Nebojsa Jojic, and Michael I Jordan. Active spectral clustering via iterative uncertainty reduction. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1339-1347,
Alexander Wei and Fred Zhang. Optimal robustness robustness-connsisteney trade-offs for online algorithms. In Advances in Neural Information Processing Systems 33: Anmual Conference Neural Information Processing Systems 2020. NeurlPS, 2020.
Jing Wong. Model-based candidate generation for account recommendationns, Jan 2022. URL
/2C22/
Carole-Jean Wu, Ramya Raghavendra, Udit Gupta, Bilge Acun, Newsha Ardalani, Kiwan Maeng, Gloria Chang, Fiona Aga, Jinshi Huang, Charles Bai, et al. Sustainable ai: Environmental impli- cations, challenges and opportunities. Proceedings of Machine Learming and 4:5tems,,:795-811 4:795-813, 2022.
Jaaming Xu, Bo Xu, Peng Wang, Suncong Zheng, Guanhua Tian, and Jun Zhao. Self-taught convo- lutional neural networks for short text clustering, Neural Networks, 88:22-31, 2017.
Yan Yan, Romer Rosales, Glenn Fung, and Jennifer G Dy. Active learning from crowds. In ICML, 2011.
Yan Yan, Rómer Rosales, Glenn Fung, Faisal Farooq, Bharat Rao, and Jennifer Dy. Active learning from multiple knowledge sources. In Artificial Intelligence and Statistics, pp. 1357. 1.5.....R 2012.
PMLR,
Jianhua Yin and Jianyong Wang. A model-based approach for text clustering with outlier detection. In 2016 IEEE 32nd International Conference Data Engineering (ICDE), pp. 625-636. IEEE, 2016.
Taranch Younesian, Dick Epema, and Lydia Y Chen. Active learning for noisy data streams using weak and strong labelers. arXiv preprint arXiv:2010. 14149, 2020.
Chicheng Zhang and Kamalika Chaudhuri. Active learning from weak and strong labelers. Advances in Neural Information Processing Systems, 28, 2015.
Xiang Zhang and Yann LeCun. Text understanding from scratch. arXiv preprint arXiv: 2015.
Zhun Zhong, Liang Zheng, Donglin Cao, and Shaozi Li. Re-ranking person re-identification with k-reciprocal encoding. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1318-1327, 2017.
14

---

Published as a conference paper at ICLR 2023
A ADDITIONAL RELATED WORKS
In the realm of learning from multiple annotators, there is a long line of work studying these both empirically and theoretically. Empirical work on this can be divided into two main streams: (I) each labeler is coming from a different generative model, (2) each labeler is an expert over an unknown subset of categories, (3) different labelers with quality proportional to their cost. In the first casc, the learning algorithm focuses on learning parameters of each labeler and then for each example decides which labeler to query (Yan et al. 2011 2012 Lin al., 2015 2014 Fang et al. 2012). In the second case, it uses data to measure the wise expertise in order to optimally place label queries (Ipeirotis et al. 2014 Donmez 2008). In the last case, empirical results comparing designed algorithms to baselines are developed: active learning from noisy data streams (Younesian) al., 2020), active learning using diverse labelers (Huang et al., 2017), and content segmentation for personal assistants (Guha et al. 2015). Theoretical work looked at the setting where the weak labeler made mistakes mostly heterogeneous regions of space, i.e., correct in habll-homogeneous regions but may deteriorate near classification boundaries. Different formulations were considered in this setting: non-pan non-parametric setting (Urner et al., 2012), fitting classifiers in hypothesis class [hhng & Chaudhuri, 2015)) online selective sampling with applications in linear classifiers and robust regression (Malago et al. 2014 Dekel et al. 2012).
The idea of judiciously utilizing an expensive but accurate strong model with the help of cheaper but noisier methods have already been successfully used in many practical and important domains. In nearest neighbor search and information retrieval, the dominant algorithmic paradigm is to turn multiple possible nearest neighbors using scalable methods and then re-rank the returned points using exact distance calculations (which is prohibitive to perform over the entire input In rec- ommendation systems, the "standard practice for machine learning-driven recommendations in in- dustry" (Wong 2022) is driven by the two-step procedure of cheaply retrieving set of possible candidates and iterating over them using a more powerful but costlier ML models (Wong, [202]]
?
Bergum 2022 Eder 2022 goo 2022 pap 2022). Similar ideas are also used in question answer-
ing and vision applications /Zhong et al. 2017 Barz & Sonntag 2021).
There has also been extensive work in incorporating additional predictions in algorithmic design for online algorithms (Bamas et al.] [2020b] Purohit et al. [0118] Lykouris & Vassilvitskii] 2018 Purohit
af.] 2018; Gollapudi & Panigrahi| 2019), sublinear space and time algorithms Chen et al. (2022);
Hsu et al. (2019): Eden et al. (2021). ). and other algorithmic and data structural problems (Mitzen-
macher 2018 Bamas et al. 2020b a Wei & Zhang 2020 Jiang et al.) 2020; Diakonikolas et al., 2021 @0arikaa Charikar et al. 2001| Antoniadis et al. 2020a b Anand et al. [022]] Nguyen & Dür 2021) We refer to the Algorihhms- PrethhPredittions website for comprehensive references. The high level motivations of these works is to apply predictions
aid in beyond worst-case analysis of algo- rithmic problems. The prototypical examples of predictions used in these works include algorithm parameter settings (for example 'warm starts' or 'seeds" which be constructed from past inputs). Thus a common underlying assumption is that many similar inputs are given so that predictions are meaningful and feasible. Furthermore in many of these works, the predictions are modeled after particular problem settings in mind and the inputs are always fully specified. In contrast, our predic- tions are inspired by particular application domain, e.g. text clustering, which we connect to CC, rather than motivating the predictions from purely algorithmic problem perspective. Furthermore, our predictions (e.g. queries from the weak signal) help us learn about the true underlying input (e.g- the strong signal graph).
We also give a detailed comparision to the work of (Guha et al. 2015). While a high level both (Guha et al.) 2015) and our work aggregate information across various signals, the two works differ in terms of the generality of oracles considered, the formal guarantees given, and the problems studied. The oracles used in (Guha et al. (215)) are highly specialized to the datasets at hand; for example, the cheap oracle used in (Guha et al. 2015) is an inverted index model which heavily relies on the specifics of the datasets used. In contrast, oracles and present theoretically founded algorithms which only assume query access to the weak and strong model and not any particular model idiosyncrasies. Therefore, our algorithm has provable
take a broader view of weak and strong
2 We refer to http: / han//ann-oot wwn.hhanchaate www.e ccmm for large collection of practical nearest neighhor search algorithms and Andoni ct al. (2018) for overview of theoretical works. pottps://alee thms wi th- predi ct ons, .an..githin thu.. 1
15

---

Published as a conference paper at ICLR 2023
guarantees both the approximation quality and the query complexity, making it broadly applicable across different oracles. In terms of problems, we study correlation clustering while the focus of (Guha et al. 2015) is not clustering problem. Rather, they use hierarchical clustering intermediate problem to perform user modeling and do not consider any specific clustering objective functions. The strong signal queries made by algorithm
guided through formal reasoning and they exploit the structure of the clustering problem we are studying. In (Guha et al. (2015) the weak signal is used more intuitive level and serves the informal role of filtering possible strong signal queries with no formal reasoning.
B OMITTED PROOFS OF SECTION 2
Proposition B.1. There exists strong signal graph G such that the KwikCluster algorithm makes (n strong signal queries.
Proof. Consider the case where the strong signal graph consists of yn cliques, all of size vτ. In this case, every time KwikCluster picks a pivot, it has to examine an existence of an edge from this pivot to all the unassigned vertices. So for at least the first vn/2 times Kwi kCluster picks pivot, has make least n/2 calls to Os resulting in 22n 1.5) calls to Os.
Proposition B.2. Consider variation of Kwi kllkkkluuster called Rwi kCl kCluster", which for chosen pivol p from uncovered vertices V', only queries V Ow(p) from strong signal. There exists a graph such that KwikCluster" still makes (2n2) strong signal queries expectation even when = O1).
Proof. Consider the following strong signal graph: the graph G comprised fully connected clique on 0.9n nodes. The graph also has 0.1n nodes, called 'outside vertices' which all connect the same In vertices the fully connected clique but have no edges between them. Suppose that O returns the correct strong signal neighborhood for vertices in the clique but for the outside vertices, it returns an additional ((m) arbitrary vertices among the outside vertices.
Now consider the simulation of KwikClus kilkkeesrrr on G. With constant probability, the first time a pivot is picked, comes from the clique vertices which have no neighbors among the outside vertices. Condition
this event. Now the algorithm still needs to run until the outside vertices cluster. However, every time each such vertex is picked as a pivot, we need to check over (n)) erroneous vertices. Furthermore, removing borhood I'v) does not remove any of the other outside vertices. Thus it follows that the expected number of queries made to Os, while still utilizing O in this natural variant of Kwi kCl uster, is ((n²) with constant probability since there 2(n) outside vertices, each which requires (2)) queries to Og. Altogether, this natural algorithm can incur 2(n²) queries, a super linear amount.
have been selected
outside vertex and its neigh-
Lemma B.3. Let t be the parameter of GetPivots (Algorithm 3 Algorithm Quses t 2yy moffmm/nn queries to Os.
Proof. Let T /ei.....u }1 denote the set of sampled vertices in line of Algorithm Fix a vertex V T, we show that there are Elyt]E//n 1) queries expectation for such vertex. When we check for the neighbors of vertex Us we immediately stop if a strong signal neighbor in P, is found. Let A(t) = (ex) \ ((())) be the vertices which O errs for query U, and can result in needless calls to Og. The number of expected calls to the strong signal is exactly the expected number of unnecessary calls B[IA(s:) P: plus call that may result in the early stoppage in line 4 of Algorithm 4 So
Let P. denote the set of pivots right before we start scanning vertex
16

---

Published as a conference paper at ICLR 2023
for each U4 the expected number of calls to Og be bounded by
1 + B(()(vs) n P:]] - 1 (((A(()) nT]
= RR, B(IA((;))
nT]
md
1
< 2 E
|||
1/
n
$ 1 2ty
n
2tym
= 1 +
n2
Summing over all t vertices in T results in the final bound.
Lemma B.4. Let P be the oulput of Get (t, Q), then Asssiggnoccllsssess((
makes n + 2ytm/n queries Og.
Proof. Consider fixed vertex V V.P. We perform similar analysis as in Lemma B.3 ideally = w (u) n P informs us the pivot which u should connect to. However since the cheap oracle can be noisy, we can have many vertices in (O% (u) \ I(u)) n The number of queries to Og is at most (u) \ ((()) n PI + 1. It remains to calculate the following expected value:
(OW (w) \ [(w)) PI] & ([[(w)
Thus the total expected number of queries for non-pivot vertices is
Σ PEVIP
[1+
& n = -V 7
Σ u PP
I nn+
2ytm
n
Theorem B.5 (Bonchi et al. 2013)). Let T be the maximal independent set formed by scanning randomly sampled t vertices of a graph G. Then the expected number of edges of G not incident with an element T" union the neighborhood T" in G is at most n²² /2t.
Theorem 2.1. Under Assumption 2.1 Kwik kBucks Os to achieve approximation 3OPT Onn//t).
+ 4-22: 27tm/n + 2y12m/ m/n? queries to
Proof. The bound on the number of queries to Os. There are two tasks which require calls Os: forming the set of pivots in GetPivots and assigning non-pivot vertices to pivot in Ass ggnlgllusss luseers. The expected number of queries forGetPivots is handled by Lemma B.3 and the expected number of queries for AssignCluster"
handled by Lemma B.4
We now need to bound the approximation guarantee. Consider the subgraph G' of the strong signal graph which the union of the pivots returned by GetPi ivots and their neighborhood. Theorem B.5 gives us that the number of edges not part of this subgraph is at most O(n² /t) which can be charged the additive error incurred by our algorithm (all vertices which do not have strong signal edge to any of the pivots are clustered as singletons). Now on this subgraph note that we are exactly mimicking the Kwi wwikkllu usteer algorithm from the same distribution as the Kwi kCluste algorithm since we ensure that all pivots chosen are not in the neighborhood of previously chosen pivots. Thus we obtain a 3- OPT guarantee on G'. To obtain the final guarantee on the original strong signal graph, note that the OPT clustering of G restricted to G' cannot be better than the OPT correlation clustering of G'. The result follows from considering additive error well.
G". This because the pivots of Get-Pivots are chosen
We now show lower bound on the query complexity of our algorithm. First we recast the lower bound result of (Garcia-Soriane Soriano et al. (020a)) in the language of strong and weak oracles. They show that any algorithm which only has access to the strong signal must make 2(n3/(Ac (((ce)) queries to obtain a c- OPT + correlation clustering objective guarantee. We can translate their lower bound into setting of strong and weak oracles by essentially making the weak oracle useless through
17

---

Published as a conference paper at ICLR 2023
suitable choice of y. The lower bound shows that for constant and large enough, Corollary 2.2 is optimal. First we formally state the guarantees given by (García-Soriane et al. 2020a) in our language of strong and weak signals.
Theorem B.6 ((Gareía- ((García-Srriano Soriano et al. 2020aa). For any 2 1 and A such that 8n < < n²
2015
any algorithm finding clustering with expected cost at most e- OPT +A must make at least S2n2 (Ac²)) adaptive strong signal queries.
Lemma B.7. Let e 2 (n) be sufficiently small. In the worst case inpul, any algorithm must at least [nn + dr) strong signal queries to obtain 3- OPT +O(=n²) approximation to the correlation clustering objective.
Proof. We recall the lower bound example of (García-Soriano et al. 2020a) (which is proved in Theorem 4.1 in (Garcfa-Soriane et al.) 2020aa). Let i = (32cA) (note that < n by design). Their worst case strong signal graph example consists of l equal sized cliques and all vertices have degree (nn/k). Now we consider the case where the weak oracle is completely useless and always returns the entire set of vertices any query. This corresponds to the case where y (k) (for y defined in Assumption 2. Now directly applying Theorem 4.1 of (Garefa-Soriano al. 2020a) gives us that any algorithm which only has access to the strong signal must make at least [ Ac²)) queries to obtain c- OPT +A correlation clustering objective guarantee. The theorem follows by noting that if A en2 then any algorithm must make ((n/c)) I2(n + k n/k) [nn + d queries in this worst case example, as desired. Note that the valid range of e here follows from the restriction on A so e 2 8/n and cannot be larger than some fixed constant.
C ADDITIONAL ALGORITTMIC DETAILS FOR EMPIRICAL ALGORITHM.
We provide additional details on the algorithm design of Section 3
Algorithm 7 SortNenPivot (T)
Require: T, the set of pivots; \T, vertices which are not pivots 1: for vertices E V \T do
2: Wi Maximum weak signal similarity
between and any vertex in T
3: Return V \ T sorted in decreasing w, values
Optimizing non-pivot order. Continuing on the theme of ranking, once we curate the pivots, we need assign the non-pivots to a pivot. To do so, we sort the non-pivots based on 'easiness' assign to pivot. Hence we sort the non-pivots by the maximum weak similarity to some pivot. This has the effect of utilizing our query budget as efficiently as possible as 'easier' non-pivots are checked first. We re-rank the vertices V P in SortNonPiven vots before calling AssignClusters in KwikBucks.
Utilizing Weak Signal Neighborhood. We can strong signal queries that have already made for vertices in the weak signal neighborhood to further optimize the sorting of the pivots in WeakFil SesiiterBee BeteeByRRaninnngg immediate weak signal neighborhood of vertex v connect to the same pivot p. then the likelihood u having strong signal edge to p is high. Thus to better utilize our expensive query budget, we should query (v, p) earlier than later. To make the intuition more precise, we simply update the similarities pivots computed by v in WeakFil wwrFiileeByaankk.
The inductive bias are using that if many vertices in the
to account for the inductive bias. The new similarity score w'p of pivot is equal to Up. the similarity score between and p computed by the weak signal, plus a term for the number of vertices in the k-weakk signal neighborhood of u that are already connected to p:
w/ = Wp + X( # of vertices in k-weak signal neighborhood of v that are already in p's cluster).
This has the affect of "boosting' some pivots higher ranking. See Section F22 for further details.
18

---

Published as a conference paper at ICLR 2023
C.I DETAILS ON POST-PROCESSING MERGING
In this section we provide the details of our post-processing merging strategy outlined in Section 3
Let CI,-..,Cr C, be the clusters outputted by algorithm. First we curate list of cluster pairs to consider for merging. Then we rank the pairs in terms of suitability for merging. Finally we enumerate over the pairs in the order computed (until we run out of any query budget) and determine if the pair should be merged. Each of the three steps is described in detail below.
Curating pairs of clusters. It prohibitive to consider all pairs of clusters (which might be super linear if there many clusters). We again appeal to the weak signal and construct a k-nn weak signal similarity graph on the vertices for some small k, such as k = 20. Then only consider pairs of clusters which are edges in the graph. More precisely, consider the pair (Ci, C₃) for merging if there is some & E C₁ and u E Cj such that (v, u) is edge in the k-nn graph. This narrows down the number of pairs considerably.
2. Ranking pairs by suitability. For each pair (Ci, Cj) of clusters from the prior step, we compute the average weak signal value between vertices in C₁ and C2 respectively. We then rank the pairs in decreasing order based on this value.
3. Determining if pair should be merged. Finally, we enumerate over the pairs in the order computed previously. Suppose we are deciding if we want merge the pair (C,, Cý). We must ensure the pair has a high number of strong signal edges (more than 0.5 fraction). To do so we simply sample small number of random pairs of vertices (say 20), one vertex from each cluster, and estimate the fraction of these random edges which are strong signal edges.
D THEORETICALLY MOTIVATING PRACTICAL MODIFICATIONS OF THE ALGORITHM
In this section we provide theoretical justifications for the practical modifications of our algorithm.
D. THEORETICALL MOTIVATING RAKING PIVOTS BY WEAK SIGNAL
In the classical KwikCluster algorithm and our query efficient variant in the two oracle model of Section 2 it is imperative that the pivots are selected in random order to provide theoretical guar- antees on the quality of the computed clustering. Specifically, the worst case theoretical guarantees dictate that vertices must connect to the first pivot in the random order which they have strong signal edge to.
Nevertheless, in our data driven optimization of the algorithm, we choose adaptive ordering of the pivots for each vertex where the order based on the weak-signal similarity scores. We empirically observed that this ordering is superior to the random ordering and achieves higher clustering quality while utilizing a >> 3.5x factor or more less strong signal queries. The explanation behind this improvement is two fold:
1. Increased query efficiency: fewer strong signal queries are used when a vertex attempts connect pivot.
2. Maintaining cluster quality: connecting to pivots with larger weak signal similarities are high quality pivots.
The positive effects of the first point are straightforward to explain. Indeed, making the natural assumption that higher weak signal similarities are more indicative of strong signal edge, checking pivots in the weak signal ordering leads to less queries wasted when vertex attempts to connect to a pivot. addition to the empirical results of Section this point is further expanded upon in Figure and Section F.6
Thus the main goal of this section is to provide an intuitive and theoretically motivated understanding of the second point. While it may not be true that re- re-ranking pivots according to the weak signal similarities maintains the worst case guarantees proved in Section 2 we study a natural data set model where such re-ranking provably helps. We wish capture data driven observations that
19

---

Published as a conference paper at ICLR 2023
pivots with larger weak signal similarities are of high quality and larger weak signal values indicate better cluster relationships.
In our experiments, the weak signal scores are mostly computed using distances between embedding vectors. If a weak signal is useful, then it must have be predicative of the strong signal values, even if the weak signal is noisy. To mimic this, we consider the following general family of data sets:
Each vertex e has an associated vector pa E IR representing it's 'true' embedding repre- sentation.
The weak signal values are computed according to appropriate distance measure d on the embedding vectors (for example cosine or Euclidean distances) plus a random noise term ç (expanded upon shortly). This models the setting where the weak signals are helpful but noisy signals as they only have noisy access to the 'true' representations.
There exists a function f I > [0, 1] which gives the probability of a strong signal edge. More precisely, let Pa and Pa, denote the embedding of vertices v and u. Then the probability having the strong signal edge (v,, u) is given by [(((,, u)). This quite a general formulation as it includes wide array of geometric or kernel similarity graphs for appropriate choices of and d.
For example, if f exp(-z/o) and is the Euclidean distance, then the true strong signal graph is the Gaussian kernel similarity graph where a is the scale of the kernel. Intuitively, the closer u and are under the metric d, the higher probability assigns the edge between u and v.
We additionally impose the following clusterability assumptions on the data set. Our goal is to capture a natural underlying cluster structure which can be accessed via strong and weak signal queries. Vertices which are part of the same underlying cluster should have higher weak signal similarity scores, even if the scores are noisy, and the strong signal edges should be highly accurate. Our model defined below satisfies these intuitive criteria. Furthermore under our natural model, there is 'true" pivot for vertex v. even though v may have strong signal edges to other pivots.
Our cluster assumptions on the data set is the following.
1. The 'true' embedding vectors Pe E Rd can be partitioned into k clusters such that all vectors in a cluster are within distance of each other.
2. All embedding vectors in different clusters are distance at least 2R from each other.
3. The probability of a strong signal edge is at least 1 - for distances at most 2R and at most p for distances at least 2R. We think of p < 1/2 as a small parameter close O.
4. Given inputs u, v, the weak signal outputs d(pu. P.) + & where is uniformly random in [-R, R]. Thus smaller values are interpreted as having higher weak signal similarity.
Note that we only have access to the strong and weak signal values via queries and do not know the true underlying embedding vectors Pv. We now argue that the above assumptions are motivated and natural.
The assumption (1) gives a cluster structure to the data and allows us to compare the classi- cal Kwi kCluster algorithm and our re-ranking modification under natural clusterability assumptions. The exact formulation we are employing inspired by the works of (Awasthi) (et al. 2012; Balcan & Liang, 2012. Ashtiani et al. 2016) which study clustering under similar proximity assumptions. For example, it can be casily checked that the 'margin' property assumption of (Ashtiani al. 2016) directly implies assumptions (1) and (2).
Our assumption (3) is a natural and necessary assumption on the function f as it ensures the true strong signal graph captures the underlying cluster structure of the inputs. This also corresponds to picking appropriate scale parameter if is a kernel function, for example picking a in the Gaussian kernel. A judicious choice of a ensures that the underlying kernel similarity graph, which corresponds to the strong signal, is able to capture the cluster structure of the data set. Thus our assumption that << 1 ensures that the similarity graph has strong inter-cluste connectivity while having sparse connectivity across different clusters. Indeed in practice, the kernel scale parameter is often picked using the 'median' rule and thus O(R) is natural choice which ensures choice of p.
20

---

Published as a conference paper at ICLR 2023
Our data set construction ensures that the strong signal is 'more powerful' than the weak signal. Indeed, the weak signal only has access to the distances between the true embedding vectors up some additive noise stated in assumption (4). While the exact form of the random noise is not very consequential, we stick to the uniform noise model as it as several desirable properties:
1. Given vertices v u, w where u is in e's true cluster (according to the true embedding vectors) and w is not, the weak signal can potentially output smaller value on query (u, w) compared to (v, u). Thus the weak signal incorrectly states w is more similar to than due to the additive noise. For example if d(uu, u) R and d(v, w) 2R, this happens with probability 1/8. Therefore the weak signal accurately reflects our desired goal of an indicative but noisy signal.
2. The weak signal can be modeled by fast nearest neighbor search algorithms which return noisy nearest neighbor estimates. On the other hand, we imagine the strong signal as being expensive since needs the true distances among the embedding vec- tors without any additive noise.
We believe that this natural graph model we examined for our algorithm modification helps explain and predict the strong empirical performance of our method. Thus our goal is to show that under the above data set modelling, re-ranking pivots based on weak signal similarity values provably helps. Assume that we have picked a pivot u. from each of the k clusters of Assumption (1). We permute them randomly to form an ordering ",,..., Us. This corresponds to the random ordering used by the Kwi wrikkllas lster algorithm and our theoretical algorithm of Section 2 Each non-pivot vertex v re-ranks the pivots forming the ordering Uz (I) (k) where T. is a permutation depending on the weak signal similarities from the pivots to The weak signal similarities are calculated as detailed above: the weak signal outputs "noisy" distances based on the true embedding vectors and smaller distances correspond to higher similarities. Note that each non-pivot vertex has 'true' pivot u corresponding to the pivot chosen from the cluster that the true embedding vector Pe is part of. We say that non-pivot vertex v is correctly assigned by a clustering algorithm C if C. assigns to its 'tree' pivot. The following lemma shows that assigning vertices to pivots based on weak signal similarities strictly outperforms using random order.
Intuitively. if another pivot u' is ranked higher than in the random ordering, our proposed medica- tion of re-ranking asked on weak signal similarities is likely to correct the ordering re- re-ranking u to ahead. The lemma below provides theoretical justification of why this is sound and complements our experimental evaluation which demonstrates the empirical advantage of our re-ranking procedure.
Lemma D.1. Consider the setting above. Let be the clustering where every non pivot vertex picks the first pivot in this ordering that it has a strong signal edge to. Let C' be the clustering where each non pivot vertex re-ranks the pivots using weak signal similarities then picks the first pivot that it has strong signal edge to. Let A be the number of non-pivot vertices that C correctly assigns and similarly define B. We have E[A] < B.B
Proof. Fix a non-pivot vertex Let X denote the indicator variable for C correctly assigning u and define Y similarly for C'. It suffices to show that E[X] < E[ The lemma then follows by linearity of expectations and summing across all non non-pivot vertices v. Note here that the expectation of each variable is with respect to the randomness used by the respective algorithms.
Let denote the true pivot of v. If v does not have strong signal edge to u (according the strong signal) then both algorithms will fail. Similarly, if only has a strong signal edge to u and to no other pivots, then the performance of either clustering is the same. Now consider the case that has at least two strong signal edges to pivots, one to and rest arbitrary. Then the probability that is correctly classified by the random ordering at most 1/2. This is because if there is at least 1 other strong signal edge to, then the probability that the random ordering places u ahead
pivot that of it is at most 1/2.
One the other hand, the probability that is correctly classified by the weak signal ordering is strictly larger than 1/2. To see this, we calculate the probability that u has the highest weak signal similarity. Identically. it suffices to calculate the probability that the weak signal outputs the smallest noisy distance value for u. Recall the modelling assumptions of the data set: we know that d(v, u) < R whereas d(v, u') 2 2R for all other pivots w' that are not equal to The weak signal outputs
21

---

Published as a conference paper at ICLR 2023
d(v, 2') plus uniformly random value in [-R, R). Let Eu be the random value added for d(v, u). With probability 1/2, this value is negative so the noisy distance computed by the weak signal is strictly smaller for than all other pivots u' (since in the best case, their distance is at least 2R R = R). Furthermore, conditioning on the additive noise being positive for u, there is a non-zero probability that has the smallest additive noise (in absolute value) among all pivots. is again ranked the highest in this case. Altogether, the probability that u is ranked the highest in terms of the weak signal similarity is strictly larger than 1/2. It follows that E[ < [ ) as desired. [
D.2 EXPLAINING WHY MERGING HELPS
We consider a particular worst case example for the KwikClusted algorithm which motivates why a post processing merging step helps. At a high level, it is possible to pick pivots which do not have a strong signal edge but nevertheless 'should' belong to the same cluster. Then when we a clustering algorithm is run, these two pivots can possibly lead to two disjoint clusters whereas that merging them lowers the correlation clustering objective and improves the overall clustering quality.
Concretely, consider the following example: we have complete graph on vertices where every edge is a strong signal edge except a single edge (u, v) which is not. In the classical KwikCluster algorithm, if u is picked as pivot then we will form two clusters, one consisting of all vertices besides u and the the other cluster being the singleton {u}. The same is true if we pick e to be the pivot. Thus the expected correlation clustering objective of the algorithm is
2 (n- n
1 72
1-33.
On the other hand, clustering every vertex to be one cluster has correlation clustering objective value 1. Thus in the case where there are two clusters in the above example, a merging post-processing improves the overall cluster quality. This crisply captures our motivation.
While the above situation may not be representative, our merging post processing verifies that possible merge is sound (after ranking possible cluster candidates to merge using the weak signal) by querying (small) number of strong single values and merging only if the average strong single similarity is sufficiently high. Thus our post processing merge routine can only help the overall clustering.
D.3 INHERENT TRADE-OFFS BETWEEN PRECISION AND RECALL
The goal of this section is to show that there is an inherent tradeoff between precision and recall of any clustering algorithm on graphs. We first restate the definitions of precision and recall as defined in our experimental section. Let G be an unweighted (not necessarily complete) graph and let be a clustering of its vertices. The edges of G correspond to the edges in the strong signal graph (i.e., the edges are pairs of vertices the strong signal labels as 'similar.), ). Correspondingly, the non-edges of G represent the negative edges of the strong signal.
We first restate the definitions of precision and recall as defined in our experimental section. The recall of C is defined as the fraction of edges of G which are together in some cluster given by C. The precision of C is defindd as the fraction whose numerator the number of edges of G which are together in some cluster and the denominator is the total number of pairs of vertices that are clustered together.
We state natural (random) graph dataset such that with high probability, any clustering C' has either recall or precision bounded away from 1 by a fixed constant. In particular, G will be sampled from the standard Gin,, 1/2) Erdos-Renyi graph distribution. Note the order of the quantifiers: generate a random graph. There is an event E which G satisfies with high probability. Condition on this event, any clustering of the vertices of G will either have its precision recall bounded away from 1, including the OPT correlation clustering.
first
Note that we have not made attempt optimize the constants in the following lemma for clarity. It is likely that one can optimize our proof and obtain a smaller constant than 0.75.
Lemma D.2. Let G be sampled from the G(n, 1/2) distribution. With probability at least 1 1n) all clusterings of G have recall or precision at most 0.75.
22

---

Published as a conference paper at ICLR 2023
Proof. Let C > be a fixed constant. We first consider the following event E for any subset S of vertices of size least C log n. there are at most 1.01|S| 4 and at least 0.99 0.99|S|/ /4 edges of G within S.
We now show that E' holds with probability at least 1 [/poly(n). For fixed subset of vertices for k 2 C log n, the expected number of edges within is /2) Thus the probability that there are more than 1.01k² /4 and less than 0.994 /4 edges within S is at most exp(-ck²) by standard Chernoff bound for fixed constant > There are (2) such choices S and thus union bounding over all S and all & 2 C log n. have that the probability there exists some set S with |S| 2 C'log vertices violating the required number of edges is at most
exp
-cch
ne 2
exp(-E
k
k
log
k2C log n
Σ
exp(1og + klog(ne) k log k. ch2)
k2C log
3 exp(-
poly(n)
for l: 2 Colog n for sufficiently large constant C' and n large enough. Thus ((E) 2 11-1/poly(N) where make the polynomial arbitrarily large by increasing C. We also condition the fact that G itself has at least 0.999n /4 edges with also happens with inverse polynomial failure probability.
Now consider an arbitrary clustering C. If the recall of C is at most 0.75 then we are done so suppose the recall is at least 0.75. Given this, we claim that there exist cluster within C' of size least 0.74n.
To see this, let CI,... ,, be the clusters of C. The clusters of size at most C' log n have at most n log n))²/ edges of G inside them. All other clusters C, have at most 1.01|C,|2/ //4 edges of G inside them. Altogether, the number of edges of G inside some cluster is at most
1.01/C,/2
n- log n2
Σ
10,120logı
subject to the constraint that |C,] S 0.74n and Σ; C S n. This is convex function which is maximized at its boundary, meaning the number of edges of G inside some cluster of C is at most
1 1.01
0.74
0.75 0.999n²
n 2
0.74
4
which contradicts the fact that the recall of C is at least 0.75. Thus there exists cluster of C of size at least 04.. Now given this, we show that the precision must at most 0.75.
Towards this end, let C2 be the cluster of C of size at least 0. It has most [.01|,11 edges of G inside it and (IC.l) pairs of vertices. Let A be the other edges of not inside C, and let B be the total pairs of vertices where both of the vertices in the pair lie outside of C. Then the precision of C2 is bounded by
1.01/C,/2/4 4
(1)
B
Since |C,| 2 0.74n, one can easily verify that
(0.26m)²
1
((C))
B <
<
2
8
23

---

Published as a conference paper at ICLR 2023
Cere
Neets
0.8
02
04
Hearrs Reighters
Neighters
Nearei feighters
(b)
(c)
Figure 2:
The propensity for vertex v to connect to a pivot p given that of v's neighbors have already connected to p.
and thus
1O1/C A
//44 B
(Q)) + +B
(221 + B
1.01/
B
((21
(C. + B
$ 0.51 +
9B
< 0.75,
as desired.
D.4 MOTIVATING USING WEAK SIGNAL NEIGHBORHOOD STATISTICS.
In Figure 2 we plot the the fraction of times vertex U connects to pivot p in the Kwi Kwi wBiks al- gorithm as function of the number of nearest neighbors of (in terms of the weak signal similarity) which have already connected the same pivot p.. We see that the probability increases as a func- tion of the number of nearest neighbors, empirically justifying our algorithmic design optimization of "Utilizing Weak Signal Neighborhood' in Section C. Note that this optimization has the affect of slightly boosting such pivots (if they exist) to higher similarity (and thus better ranking).
E DETAILS FOR DATASET WEAK/STRONG SIGNALS
We provide a detailed description of the datasets used in the paper as well as the weak and strong signals used for each of the datasets. Table provides summary.
Stackoverflow (SOF) and SearchSnippets: Stackoverflow and SearchSnippets are commonly used for short-text clusteringCcasssffcatinn For stackoverflow, used subset collected by Xu et al. 2017) consisting of of 20,000 question titles associated with 20 different categories obtained from dataset released part of Kaggle challenge. For SearchSnippets, we used the dataset from Phan et al. (2008) which consists of 12,340 snippets (extracted from web search snippets) asso- ciated with 8 groups For these two datasets, we experimented with two different types of cheap signals: word2vec embeddings Mikolov et al.] (2013) and tf-idf embeddings. In both cases. we trained/finetuned on the training set the datasets. We used the Gensim package Rehurek & Sojka (011) for word2vec and sklearn Pedreeosa et al. (201 for tf-idf. Word2vec provides a vector rep- resentation for each English word; to compute the embedding for a sentence/document, we average the embeddings of each of its words. For the strong signal, for each dataset we finetuned a T5-1.1 XXL model (I parameters) Raffel et al. (2020) on the training data where given two examples, the model finetuned to predict if they belong to the same cluster not. In both cases, sampled 10K positive pairs and 50K negative pairs and finetuned the model for 10 epochs on a 4x4 DragonFish TPU architecture.
24

---

Published as a conference paper at ICLR 2023
Twitter and AgNews: Twitter and News data commonly used for short-text cluster- ing/classification. From Twitter, we use the dataset created by Yin & Wang (2016) consisting of 2,472 tweets with 89 categories. From News, we use the data from Rakib et al. (2020) which is a subset of the dataset from /Zhang & LeCun (2015) containing 4 topics. For the cheap signal, we use pretrained BERT embeddings Devlin et al. (2018) where we feed each example into the BERT model, obtain contextual token embeddings, and then average them (ignoring the [CLS] and [SEP] tokens) to obtain the embedding for each example. We use the 12-layer uncased BERT-Base model for this experiment. For the strong signal, we first created a graph by connecting two nodes if they belong to the same category, then added noise to the graph by flipping the existence/non eexireeeeeenneeiittneneeeeeeeeee of an edge for 5% of node pairs selected uniformly at random (note that without adding noise, the prob- lem becomes much easier as graph of the strong signal becomes composed of multiple connected components).
Internal:
This a vertical of large, internal, proprietary text dataset. The weak signal is embed- ding similarity, and the strong is an indicator variable from cross-attention model.
Citeseer and Microsoft Medicine: Citeseer [Sn et al. 2008 and Microsoft Medicine Shehur & Günnemann (219)) are attributed graph datasets. Citeseer is citation network in which nodes rep- resent papers, edges represent citations, and features are bag-of-wordd abstracts. Microsoft Medicine is subset of the Microsoft Academic graph where the nodes represent authors, edges represent co-authorship, and node features are a collection of paper keywords from author's papers. For both datasets, we used the cosine similarity between the node features as the weak signal and we assume the edges of the graph correspond to the strong signal.
Cora and Amazon Electronics Photos: Similar to Citeseer and Microsoft Medicine, Cora and Amazon Electronics Photos are also attributed graph datasets. They are typically used for node classification but here we adapt them to our problem. Cora [Sen et al. (2008) is citation network similar to the Citeseer dataset with the node labels corresponding to paper topics. Amazon Elec- tronics Photos Shchur al.] (2018) is subgraphs of the Amazon copurchase graph where the nodes represent goods. an edge between two nodes represents that they have been frequently purchased together, node features are bag-of-word reviews, and class labels are product categories. For these two datasets, we used the deep graph infomax (DGI) model Velickovic et al. (2019) to learn un- supervised node representations and used these representations as the cheap signal. We also used noisy labels as the strong signal similar to the Twitter dataset.
Total cost analysis: Our work is mostly based on the applications where the weak oracle values computed via distances based on embeddings and the strong signal values are the output of large cross-attention transformer model. In this case, there are three different factors that comprise the total cost of the clustering algorithm: 1- the cost of the queries to the strong signal, 2- the cost of computing embeddings from the cheap signal, and 3- the cost of geometric operations on the embeddings. So the total cost can be summarized as follows:
Total Cost T + VEξE + TGGG
where Ms represents the number of calls to the strong signal, (s represents the cost of making a call the strong signal, Ve represents the number of calls needed compute embeddings, ÇE represents the cost of obtaining one embedding. 7G represents the number of geometric operations (cosine similarity in our case) we perform on the embeddings. and (G represents the cost of single geometric operation.
The number of calls NE required to obtain embeddings is n (i.e. the number of data points) which is smaller than ys (which, in our case, is typically linear factor of n) and the cost ÇE of obtaining one embedding is significantly smaller than the cost of obtaining one strong signal similarity (s- Therefore, T can be subsumed in nsss.
When using 32 TPU v3 chips for the strong signal and CPU for the geometric operations, each call to the strong signal was approximately 10a times slower (i.c. Çs x 10*(a). This gap becomes even more stark if we use fast geometric algorithms such as nearest neighbor search or use TPUs for geometric operations. It follows from the analysis of our algorithm that ne E O(nk) where k is the parameter defined in Algorithm 6 This is comparable to ns. Therefore, naÇG is negligible compared to AsSs in our experiments.
Following the above justifications, as well as for theoretical simplicity, in this paper we ignored the cost of querying the weak signal in our analysis (i.e. assume NECE + noSo 0). However, if future
25

---

Published as a conference paper at ICLR 2023
work considers costlier operations for the cheap signal, these extra terms should also be considered in determining the total clustering cost.
F ADDITIONAL EXPERIMENTAL RESULTS
F.1 PRECISION AND RECALL
The precision and recall (with respect to a clustering C) definitions used in Section 4 are defined as follows:
Precision(C,, C,)s) = Ee=(id) OssOs(e)
(2)
Ee=(io) Cis
where Oig is the indicator for if vertices i.j are in the same cluster.
Recall(C,Os) Ex=(i,) Cs,O((e)
(3)
Ee=(,,) Os(e)
As stated in (Garcia-Soriano et al. 2020a),, while our algorithm and baselines have been designed to minimize the total correlation clustering objective, it important to consider precision and recall as they problem independent measures of cluster quality. Furthermore in cases where the underly- ing strong signal graph is extremely sparse, the correlation cost objective might not be meaningful. For example in such case, returning all vertices as singleton clusters already has low objective value (equation T). We use the entire strong signal graph for the purposes evaluating the experimental metrics, such CC objective, precision, and recall.
Table 2: Properties of datasets used in our experiments. n denotes the number of vertices and Non- zero entries denotes the number of non-zero entries in the adjacency matrix of the strong signal graph (i.e. twice the number of edges), both rounded two significant digits.
Name
Type
Weak Signal
Strong Signal
Non-zero entries
SOF
Text
W2V / tf-idf
Cross-attention model
4.9 10a
2.3 10
Search
Text
W2V / tf-idf
Cross-attention model
3.3 10a
2.0 10s
Twitter
Text
BERT Embeddings
Noisy label indicator
2.4 10a
4.7 1O
AgNews
Text
BERT Embeddings
Noisy label indicator
8.0 10a
1.8 107
Internal
Text
Embeddings
Cross-attention model
1.0 105
9.5- 107
Cora
Attributed Graph
DGI Embeddings
Noisy label indicator
2.7 103
1
Photos
Attributed Graph
DGI Embeddings
Noisy label indicator
7.7 103
1.2-10 107
Citeseer
Attributed Graph
Node Features
Adjacency matrix
3.3-
10
Med.
Attributed Graph
Node Features
Adjacency matrix
6
1.6- 10
F.2 PARAMETER SELECTION DETAILS
We first describe how to select the value in Algorithm 3 and ls in Algorithm 6 which selects the top l vertices in weak-signal similarity for the strong signal to query.
The intuition in picking is that must be sufficiently large so that only few vertices do have pivot in their neighborhood (and thus contribute to the additive eтror of Theorem 2.1) This param- eter naturally depends on the density of the underlying strong signal graph: for sparser graphs, one must pick larger value of since each vertex average has a small degree and is thus less likely to have a pivot chosen its neighborhood than a vertex with larger degree. We use the above intu- ition to design the following data-dependent method to select t: we first sample sublinear number of random strong signal edges ( (vTz strong signal edges to be exact). This returns an estimate of the density of the graph up to small additive error (for example via standard Chernoff bounds). We then set to be 10 times the inverse of the density. If the density is extremely sparse, i.e. less than 1/1000 fraction of possible edges exist, simply set & to be equal n/2.
The second parameter we set is in WeakFilter WeakFiiterByRanking because intuitively, meaningful weak signal assigns high similarity score to relevant pivots
We can pick a value of l &
26

---

Published as a conference paper at ICLR 2023
relative to all other pivots and thus such pivots have higher ranking. To understand the trade offs in selecting k consider the most prominent place where it is used in our algorithm: when a vertex v attempts to find strong signal edge one of the pivots by iterating through them in the weak signal ordering. The trade offs are the following: a smaller value l leads to better query efficiency as is guaranteed to only make & strong signal queries in this step. However the clustering quality can suffer because the first & pivots, for a small k, in the weak signal order might not have a strong signal edge to Conversely larger value of k leads to increased exploration from to connect to pivot. However in the case that is truly singleton cluster, i.e. it has no strong signal edges any pivot, we potentially waste many strong signal queries. To balance these trade offs, we pick 'intermediate" value of k 100 for all our experiments. Ablation studies for both parameters are given in Section
it attempts
We also always set k 10 when we use the "Utilizing Weak Signal Neighborhood" optimization of Section We also always À 1/10 which appropriately normalizes the second term to be between 0 and (note the weak signal similarity w, is between -1 and 1). The parameter 10 here is fairly robust and can likely be replaced by any (small) reasonable value and we also perform ablation studies this optimization.
For spectral clustering. we always use = 25 for the number of clusters. Higher values were computationally prohibitive to use.
F.3 RESULTS
We present additional experimental results in Fi our algorithm Bucks has superior query complexity over the baselines as it achieves a higher Fi value (and lower CC objective values) while utilizing fewer strong signal queries than baselines.
show similar qualitative results as
Table 3: CC objective values shown for fixed budget of 3n. See Table for the corresponding F2 values. We normalize the smallest CC value to 1.0 so smaller quantities are desirable. See Figures and Lnddffor for results as function of query budget. For the sparser graph datasets of Citeseer, Med., and Internal we use the budget of 50n. Due to their sparsity, the CC objective value is less meaningful than F1 values for these two datasets.
SOF
Search
Tweet
AgNews
Cora
Photos
Citeseer
Medicine
Internal
1.9
2.5
1.2
2.0
2.0
2.5
1.3
1.1
1.01
B2
1.8
2.0
1.2
2.0
2.0
2.4
1.3
1.1
1.04
B3
6,4
4.0
6.3
2.5
2.5
2.2
745.1
2550.8
B4
2.0
6.0
1.1
4.1
3.0
3.2
1.0
1.0
1.01
B5
2.0
6.0
1.1
4.1
3.0
3.2
1.3
1.3
1.01
KwikBucks
1.0
1.0
1.0
1.0
1.0
1.0
1.1
1.0
1.0
F.4 ADDITIONAL ABLATION RESULTS
In our ablation experiments, we fix all parameter settings except the component we are altering. We perform ablation studies on representative datasets: Cora, Citeseer, Stackoverflow (SOF), and Search. Our first observation that the merge post processing procedure can help return higher quality clustering, for example for the Cora, SOF, and Citeseer datasets; see Figures 5 and for details and Section D.2 for theoretical intuition of why post processing merging helps.
Next we consider removing the Nont vots step and replacing it with an using an arbitrary ordering of non pivot vertices. We see that the positive benefits of removing this component are more subdued compared to the merge post processing. However, this change never hurts the quality of the clustering. Overall, we view the different data-driven components introduced in Section 3Jad and C as having complementary benefits each optimize different part of the algorithm.
We observe that one must choose a sufficiently large value in GetPivots which is the initial number of random vertices sampled which are later processed to be pivots. As argued in Section F.2 is important to select a sufficiently large value of t to limit the number of vertices which do not have a pivot in their strong signal neighborhood (as captured by the additive term in Theorem
27

---

Published as a conference paper at ICLR 2023
1,55
Cora
Cora
Correlation Clustering Objective
81
0.6
B4
85
KwikBucks
0.2-
85
500
2875
5250
7625
10000
500
2875
5:25.
7625
10000
Query Budget
Query Budget
Search
Search
1.0
1.0
Correlation Clustering Objedive
0.8
KwikBB ucks
KwikBucks
0.6
B1
B2
B3
B4
0.4
B4
85
B5
0.2
0.2
0.0
0.0
500
6625
12750
18675
25000
500
6625
12750
18875
25000
Budget
Budget
AgNews
AgNiws
KwikBucks
Correla tion Clstering Objective
0.8
B2
0.6
B4
B5
0.4
KwikBucks
B2
6625
12750
18875
25000
6625
12750
18875
25000
Query Budget
Query Budget
Figure 3: Empirical results for the Cora, Stackoverflow, Search, and News datasets.
2.1 For ablation studies, consider other settings of which factor of 10 smaller than the choice used in our main experimental results and one which is factor of 10 larger. They represent the 'Small' and 'Large' pivot choices respectively. We see in Figures and 6 for the Cora and Citeseer datasets, that smaller choice of can lead to decrease in the performance of our algorithm. Nevertheless, our data driven density based approach outlined in F:2 hits the 'sweet spot' and performs comparable to the best choice of pivots in all cases shown in Figures and 6
We also perform ablation experiments on the choice of & WeaksignalFiter:z considering k = 10 and A = 1000 (a 'small' and 'large' choice respectively as before). Our ablation experiments also show that large choice of 1: in Weaks gna wwwalelllerrrrrrr wer.lteerrrtiiii... can lead to many queries wasted as argued in Section
by
Indeed, we see in the above figures that for the Citeseer dataset, large value of leads to worse performance initially as we waste many strong signal queries vertices which have no strong signal edge to any of the pivots. This is due to the sparse nature of the Citeseer dataset. However as the query budget is increased, the quality of the clustering improves. The choice of & seems have negligible impact the other datasets tested on and our choice of 100 (which we fixed the main experimental results) was always competitive.
28

---

Published as a conference paper at ICLR 2023
Electronics
0.8
KwikBudss
81
B3
84
Score
85
0.4
0.2
500
9125
17750
26375
35000
Query Budget
1e5
Tweet
KwikBucks
Correlation Clusterino Objective
B1
0.4
B2
2.6
Score
0.3
B4
2.4
B5
0.2
2.2
KwikBucks
B1
2.0
B4
1.8
500
14125
27750 Query Budget
41375
Query Budget
1e3
C tesser
Citeseer
KwikBBccs
Correlation Clssternng Objective
5.5
0.5
B4
KwikBucks
Score
B1
B2
4.5
B4
85
0.1
3.5
0.0
0.050
0.537
1.025
1.512
2.000
0.050
0.537
1.025
1.512
2.000
Query Budget
1e6
Query Budget
1e6
Microsoft Medi
Microsoft Medicine
0.30
Correaation Clusterinp objective
8.4
0.25
8.2
KWw KwikBucks
8.0
0.15
7.8
KwikBucks
0.10
B1
7.6
0.05
B4
85
0.00
0.10
0.95
1.80
2.65
3.50
0.10
0.95
1.80
2.65
3.50
Query Budget
1e5
Query Budget
1e6
Figure 4: Empirical results on the datasets omitted from Figure similar to that of Figure
The results are qualitatively
29

---

Published as a conference paper at ICLR 2023
Cora
Cora
0.6
0.6
11ooee
F1 Score
0.4
KwikBucks
0.2
Without Merging
KwikBucks
Without Neighborhood Stats
Small Pivot Choice
0.0
Without Ordering Non-Pivets
0.0
Large Pivot Choice
Query Budget
Query Budget
Cora
Citeseer
0.55
0.8
0.6
Score
0.440
0.35
0.30
kBucks (k=100)
Without Merging
k 10
0.25
Without Neighborhoed Stats
0.0
1000
0.20
Without Ordering Non- Pivots
500
2875
5250
7625
10000
0.050
0.537
1.025
1.512
2,000
Query Budget
Query Budget
leb
Citsseer
Citsseer
0.55
0.5
0.4
0.45
F1 Score
0.40
0.35
0.2
0.30
KwikBucks
KwikBucks (k-100)
0.1
Pivot Choice
0.25
10
Large Plvot Choice
1000
0.050
0.537
1.025
1.512
2,000
0.050
0.537
1.025
1.512
2,000
Query Budget
1e6
Query Budget
le6
Figure 5: Figures for ablation studies for Cora and Citeseer datasets.
30

---

Published as a conference paper at ICLR 2023
Stackoverflow
0.8
Stackoverllow
0.7
0.8
0.6
0.6
F1 Score
0.5
0.5
0.4
0.4
0.3
0.3
0.2
KwikBucks
0.2
Small Pivot Choice
Kwiksuukk (k=100)
0.1
10
Large Pivot Choice
0.0
0.0
500
6625
12750
18875
2500
6625
12750
16875
25000
Query Budget
Query Budget
Search
Search
1.0
1.0
0.8
0.6
Score
0.6
0.4
0.4
Kwi kBucks
Without Merging
0.2
KwikBucks
Without Neighborhood
Small Pivot Choice
Without Ordering Non Pivots
Large Pivot Chaice
0.0
500
6625
12750
18875
25000
500
6625
12750
18875
25000
Query Budget
Query Budget
0.8
0.6
0.4
0.2
KwikBucks (k=100)
10
1000
0.0
Query Budget
Figure 6: Figures for ablation studies for SOF and Search datasets.
F.5 MEASURING THE QUALITY OF WEAK SIGNALS
We design a simple and informative experiment to measure the quality of weak signals. For the Stackoverflow (SO) dataset, we run Kwi kBucks where we replace the weak signal with a linear interpolation of the strong signal and a random matrix will all entries i.i.d. from the uniform distri- bution in [-,, The purpose of this experiment is to show a higher quality weak signal gives better clustering results than using a lower quality weak signal. Indeed, Figure&sshowe that Kw Bucks performs the best if we replace the weak signal completely with the strong signal, as naturally ex- pected. As we vary the amount of randomness in the weak signal, the performance degrades and the case where the weak signal is fully random matrix performs the worst as a function of query budget. It is also interesting to consider the cases where the weak signal are given by the (stronger) W2V model versus the comparatively weaker tf-idf model: the performance of using the W2V em- beddings for the weak signal lies between the 'half-random' and '2/3 random' case whereas the ff-idf plot lies between the '2/3 random' and 'fully random' cases. The random interpolated weak
31

---

Published as a conference paper at ICLR 2023
Search
Search
1.0
2.00
1.75
U-idf Weak Signal
0.8
150
Scooe
0.6
125
1.00
W2V Weak Signal Alo)
0.50
tfiicf Weak Signal
0.25
10000
15000
20000
0.00
0
500
1000
15000
2000
2500
3000
Query Budget
Average Rank of Strong Sigral Neighbors
Figure The figure shows qualitatively similar result as the SOF results shown in Figure
signal cases, while artificial, help us qualitatively access the usefulness of particular real world weak signal instance.
Stackoverflow
0.8
0.6
F1 Score
0.4
0.2
Signal (KwikBuccs))
tf-idf Weak Siggnal
Raridom
Weak Signal
1/2 Random Weak Signal
0.0
Strong Si gignaa
2/3 Random Weak Signal
500
6625
12750 Query Budget
18875
25000
Figure 8: Interpolating the weak signal between uniformly random values and the strong signal.
F.6 AVERAGE RANKINGS OF STRONG SIGNAL NEIGHBORS
In this Section we present additional experiments in the similar spirit as the right figure of the second row of Figure D for the Tweet, Med., and Cora datasets. For every vertex in these datasets, rank the other vertices decreasing weak signal similarities v. The average rank of true strong signal neighbors of v is computed and plotted as histogram (normalized to be distribution). Intuitively, a good weak signal should have the property that true strong signal neighbors have much higher weak signal similarity scores (and thus better rankings) than the arbitrary vertex. Indeed, we see that to be the case of the datasets in Figure 9 where the distributions are much more left shifted and has a much smaller mean compared the case if the weak signal was fully random. This validates the connection between our empirical weak signal Definition I.3 and the theoretical assumption made for the weak oracle in Assumption 2. Indeed, Figure gives empirical validation to the claim that returning top & most similar vertices to vertex in terms of weak signal similarity captures many actual true strong signal neighbors.
32

---

Published as a conference paper at ICLR 2023
1e-3
Tweet
1e-4
Medical
Weak Signal
Weak Signal
Random Weak Signal
Random Weak Signal
500
1000
1500
2000
10000 20000 30000
40000
50000
60000
Average Rank of Strong Signal Neighbors
Average Rank of Strong Sigral Neighbors
1e
Cora
Weak Signal
Random Weak Signal
2
1
500
1000
1500
2000
2500
Average Rank of Strong Signal Neighbors
Figure 9: The average weak signal rank of actual strong signal neighbors is shown in orange. The blue curve shows the average rank the weak signal was fully random.
33


Reviews:
[{"review_id": "n4UgZ4SRnM", "reviewer": "Reviewer_Mf8c", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies a version of correlation clustering where the learner has access to a weak predictor of node similarity in addition to an accurate stronger predictor. The weak model is assumed to have negligible query cost, and can be used in addition to the stronger model. For a free parameter $\\epsilon$, he paper proposes a new algorithm which uses both the weak and strong oracle to retrieve a clustering which has objective value at most $3 \\text{OPT} + \\epsilon n^2$, and makes $O (d \\gamma / \\epsilon)$ queries to the strong oracle - here $\\text{OPT}$ is the optimal objective value, $n$ is the number of nodes in the graph, $d$ is the average degree of the graph, and $\\gamma$ captures the approximation power of the weak oracle compared to the strong oracle. The algorithm is implemented in practice and shown to have significant improvements in practical performance compared to standard baselines - a 64% relative improvement in clustering quality (in terms of F1 score) averaged over 9 datasets, and over > 3.5x reduction in number of queries made to the strong predictor compared to the best baseline.", "summary_of_the_review": "I think the paper considers an interesting problem, and I think it is a fit for ICLR.", "strength_and_weaknesses": "I like the paper, and think the contribution is interesting. The experimental results are very good.\n\nThe paper focuses on the number of queries made to the strong oracle. However, the theoretical number of queries made to the weak oracle is reported nowhere. I think this is important, as the runtime of the algorithm might be end up being governed by the number of queries to the weak model if it is indeed queried many times.\n\nThe paper also claims (or cites) that correlation clustering is \"perhaps the most natural formulation of clustering\". I feel this is a subjective statement, and is better off not in the paper.\n\nThis leads to the question of designing an algorithm to optimize $Q_1 + \\alpha Q_2$ where $Q_1$ is the number of queries to the strong model, and $Q_2$ is the number of queries to the weak model. $\\alpha = 0$ is the setting studied in this paper, $\\alpha = 1$ corresponds to the standard correlation clustering setting (since given a choice, one would always query the stronger model over the weaker one).\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "hRVWP5oZaHK", "reviewer": "Reviewer_neu8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "In this work, the authors introduce and study an interesting and pragmatic variant of the popular Correlation Clustering (Minimizing Disagreements) problem. In this problem, we are given a limited budget on the number of queries allowed to make to an expensive oracle that given an edge returns the true labeling of the edge (returned by possibly a large ML model). Moreover, we are also given unlimited access to a cheap but less accurate second oracle (for example embedding-based models, etc.). The authors propose an extension of the well-known KWIKCLUSTER algorithm, that uses the cheaper oracle wisely to reduce the number of queries to the expensive oracle. They prove a matching (to the original version of the problem) 3-approximation for a stronger assumption on the cheap oracle, except for an additive error. They show that the additive error term is unavoidable by demonstrating a tight lower-bound instance. They extend their algorithm to work for the more practical assumptions on the cheaper oracle, but with no theoretical guarantees. An extensive empirical analysis is performed to motivate the problem formulation, demonstrate the superior performance of their algorithm over baselines, and ablation studies on all tunable parameters of their algorithm.", "summary_of_the_review": "Overall, this is a very well-written paper. The problem considered is of significant importance, the proposed algorithm is simple and efficient, and the empirical evaluation is extensive and supports the claims well. Therefore, I think this paper is a good fit for ICLR. Following are a few minor line-by-line comments:\n\nMinor Comments:\n- Page 2: Sec 1.1, para 2, line 1 - cluster -> clustering\n- Page 3: para 1, line 4 - queries in for -> queries for\n- Page 3: Sec 1.2, para 1, line 5 - “we use” is written twice\n- Page 5: Thm 2.1 Proof Sketch, Line 1: inocrrectly -> incorrectly\n- Page 6: Last para of Section 3, Line 10 - two cluster -> two clusters\n", "strength_and_weaknesses": "The proposed model (with strong-expensive and weak-cheap oracles) is powerful and pragmatic, in the sense that it allows one to navigate the trade-offs imposed due to the computationally-expensive process of obtaining the actual similarities between entities in real-world datasets. Further, this model helps one to leverage the existence of weaker-yet-useful models for predicting similarities to obtain more scalable algorithms. The theoretical results obtained complement the known results for the original version of the problem, except for the additive error term. The algorithm is simple and efficient (and as demonstrated in previous work has scope for parallelism as well.) The set of experiments performed is well-motivated and supports all the claims of the paper well.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "M0L2d-Ah9xB", "reviewer": "Reviewer_6pez", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "Please refer to Summary Of The Review.", "summary_of_the_review": "In this study, the author(s) propose(s) a novel correlation clustering algorithm named KwikBucks. It’s an extension of a well-known correlation clustering algorithm KwikCluster with the consideration of the limited query budget for reliable pairwise similarity. So the designed KwikBucks algorithm less the queries for expensive-strong signal by adding cheap-weak signal acquisition steps. The performance of the KwikBucks algorithm was tested by 9 datasets with different properties (having density changes of strong signal and weak signal). The experimental results shows KwikBucks can get a lower objective function value and higher F1 scores. Besides, it obtain 3-pproximation more efficiently.\n\nThe topic of this paper is meaningful as the problem of high cost of obtaining correlations among samples does exist because of the high computation of some machine learning models. Meanwhile, the theories about this work is sufficient. As a reader, I summarize some detailed issues as follows.\n\n1) The introduction section overemphasizes the high cost of some machine learning models in obtaining the similarity between points, and neglects the in-depth analysis of the existing works and problems related to this paper. So the motivation and innovation of this paper are not presented well.\n2) On page 1, there is too much analysis of experimental results so that parts of section 4 are repeated. Please just summarize in short words.\n3) I believe that when we talk about correlation clustering, it is necessary to mention the research of Bansal (for ex. Bansal N, Blum A, Chawla S. Correlation clustering. Machine learning, 2004, 56(1):89–113).\n4) On page 3, the differences with the existing work are not clearly explained. For example, how does the algorithm proposed by Guha et al. differ from the work in terms of obtaining information from multiple sources? What are the advantages and disadvantages of the existing work?\n5) Section 1.2 has an extra ‘we use’ in the first paragraph.\n6) What is the basis for Assumption 2.1? Also, what is the significance of the \\gamma parameter? Why is it not specifically analyzed through experiments to explain its influence on the proposed algorithm in section 4, or explain this parameter theoretically?\n7) The statement on page 8 that for many datasets such as Cora and Search, B1 and B2 are the best among our five baselines is not rigorous because only B2 is the best among five baselines on Cora and Search datasets.\n\nIn general, this paper needs more carefully revisions before fully accepting it.\n", "strength_and_weaknesses": "Please refer to Summary Of The Review.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster