Correlation Clustering with Active Learning of Pairwise Similarities
Authors: Linus Aronsson
Morteza Haghir Chehreghani
Venue: Accepted by TMLR ()

Abstract: Correlation clustering is a well-known unsupervised learning setting that deals with positive and negative pairwise similarities. In this paper, we study the case where the pairwise similarities are not given in advance and must be queried in a cost-efficient way. Thereby, we develop a generic active learning framework for this task that benefits from several advantages, e.g., flexibility in the type of feedback that a user/annotator can provide, adaptation to any correlation clustering algorithm and query strategy, and robustness to noise. In addition, we propose and analyze a number of novel query strategies suited to this setting. We demonstrate the effectiveness of our framework and the proposed query strategies via several experimental studies.

Published in Transactions on Machine Learning Research (02/2024)
Correlation Clustering with Active Learning of Pairwise Sim- ilarities
Linus Aronsson Chalmers University of Technology
linaro Snnaro@chammers.see
Morteza Haghir Chehreghani
marteza.chchrgghan@ccchhhi
Chalmers University of Technology
Reviewed on OpenReview: https: // openreview. net/ forum? id- Ryf
Abstract
Correlation clustering is a well-known unsupervised learning setting that deals with positive and negative pairwise similarities. In this paper, we study the case where the pairwise sim- ilarities are not given in advance and must be queried in a cost-efficient way. Thereby, we develop a generic active learning framework for this task that benefits from several advan- tages, e.g., flexibility in the type of feedback that user/annotator to any correlation clustering algorithm and query strategy, and robustness to noise. In ad- dition, we propose and analyze a number of novel query strategies suited to this setting. We demonstrate the elfectiveness of our framework and the proposed query strategies via several experimental studies.
provide, adaptation
1 Introduction
Clustering constitutes an important unsupervised learning task for which several methods have been pro- posed in different settings. Correlation clustering (Bansal et al., 2004; Demaine al., 2006) is well-known clustering problem that is partieularly useful when both similarity and dissimilarity judgments between set of objects. In this setting, dissimilarity is represented by negative relation between the respective pair of objects, and thus correlation clustering deals with clustering of objects where their pair- wise similarities can be positive or negative numbers. Correlation clustering has been employed in numerous applications including image segmentation (Kim et al., 2011), spam dctection and filtering (Bonchi et al., 2014; Ramachandran et al., 2007), social network analysis (Tang et al., 2016; 1;; Bonchi et al., 2012), bioin- formatics (Bonchi al., 2013b), duplicate detection (Hassanzadeh et al., 2009), co-reference identification (McCallum & Wellner, 2004), entity resolution (Getoor & Machanavajjhala, 2012), color naming across lan- guages (Thiel et al., 2019), clustering aggregation (Gionis et al., 2007; Chehreghani & Chchreghani, 2020) and spatiotemporal trajectory analysis (Bonchi et al., 2013b).
available
This problem was first introduced with pairwise similarities in {-1, (Bansal et al., 2004) and then it was extended to arbitrary positive and negative pairwise similarities (Demaine et al., 2006; Charikar et al., 2005). Finding the optimal solution of correlation clustering NP-hard (and even APX-hard) (Bansal et al., 2004;
Demaine al., 2006). Thereby, several approximate algorithms have been proposod for this problem (c.g.. (Bansal et al., 2004; Demaine et al., 2006; Ailon al., 2008; Charikar al., 2005; Elsner & Schudy, 2009;
Giotis & Guruswami, 2006)) among which the methods based local search perform significantly better in terms of both the quality of clustering and the computational runtime (Thiel et al., 2019; Chehreghani, 2022).
All of the aforementioned methods assume the pairwise similarities are provided advance. However, as discussed in (Bressan et al., 2019; García-Soriano et al., 2020), computing such pairwise similaritics can be computationally demanding, or they might not even be given a priori and must be queried from costly oracle (e.g., human expert). For example, as described in (García-Soriano et al., 2020), computing the

---

Published in Transactions on Machine Learning Research (02/2024)
interactions between biological entities may require highly trained professionals spending time and costly resources, or, in the entity resolution task, crowd-sourcing the queries about pairwise similarities can involve a monetary cost. Thus, a fundamental question is concerned with design of a machine learning paradigm that yields a satisfactory correlation clustering solution with a limited number of queries for pairwise similarities between the objects.
In machine learning, such question is usually studied in the context of active learning where the goal is to obtain the most informative data given limited budget. Active learning has been successfully used in several tasks including recommender systems (Rubens et al., 2015), sound event detection (Shuyang et al., 2020), analysis of driving time scries (Jarl et al., 2022), reaction prediction in drug discovery (Vict Johansson et al., 2022) and logged data analysis (Yan et al., 2018). Within active learning, the querying strategy is performed using an acquisition function.
Active learning has been applicd to clustering as well, and sometimes called supervised clustering (Awasthi & Zadeh, 2010), where the goal is to discover the ground-iruth clustering with a minimal number of queries. In this setting, the queries are generally performed in one of two ways: i) Queries asking if two clusters should merge or if one cluster should be split into multiple clusters (Balcan & Blum, 2008; Awasthi & Zadeh, 2010; Awasthi et al., 2017). ii) Queries for the pairwise relations between objects (Basu et al., 2004; Eriksson et al., 2011; Krishnamurthy et al., 2012; Bonchi et al., 2013a; Korlakai Vinayak & Hassibi, 2016; Ailon et al., 2018; Mazumdar & Saha, 2017b;a; Saha& & Subramanian, 2019; Bressan et al., 2019; 2020; van Craenendonck et al., 2018b; Soenen et al., 2021).
et al.,
Among the aforementioned active learning works, only (Mazumdar & Saha, 2017b; Bressan et al., 2019; Garcia-Soriano ct al., 2020) are in the setting that we consider: i) the clustering algorithm used is based correlation clustering, ii) the pairwise similarities are not assumed to be known in advance and iii) we do not assume access to feature vectors (i.e., we only get information about the gound-truth clustering by querying the oracle for pairwise relations). I All of these studies propose algorithms that are derived from a theoretical perspective, resulting in multiple practical restrictions. The work in -Cariia-Soriano et al., 2020) introduces a pinol-bused query-efficient correlation clustering algorithm called QECC. Tt starts by randomly selecting a pivot object u and then queries the similarity between u and all other (unclustered) objects to form a cluster with and the objects with positive similarity with u. It then continues iteratively with the remaining objects until all objects are assigned to a cluster the querying budget is reached. The met hod in (Bressan et al., 2019) is very similar to QECC, except that after selecting a pivot u it only queries the similarity between u and a random subset S of all other objects. Only if there exists an object in S with a positive similarity to u will it query the remaining objects in order to form a cluster. Otherwise, the pivot u is assumed to be a singleton cluster. Finally, (Mazumdar & Saha, 2017b) develop a number of more complex pivot-based algorithms that satisfy theoretical guarantees on the query complexity, assuming a noisy oracle, However, the algorithms are purely theoretical and are not implemented and investigated in practice, and require setting a number of non-trivial parameters (e.g., they assume the noise level is known in advance).
These works on active correlation clustering suffer from various limitations: i) They only consider binary pairwise similarities in {1,,1}, whereas, as exlensively discussed in the correlation clustering literature (e.g., (Demaine et al., 2006; Bun et al., 2021; Ailon et al., 2008)), having real-number pairwise similarities provides more ficxibility, informativeness and tolerance to noise. ii) They do not follow the generic active learning procedure as they assume the querying process is tightly integrated into the clustering algorithm itself. In fact, the pairwise relations to be queried are selected randomly without considering the notion of informativeness. iii) They are severely affected by the presence of noise in the oracle. While the algorithms in (Mazumdar& & Saha, 2017b) are meant to be robust to noise, they are quite limited in practice. For example, they rely on precisely defined constants and the true noise level is assumed to be known in ad advance. iv) Only pivot-based active correlation clustering methods (i.e., (Bressan et al., 2019; García-Soriano et al., 2020)) have been investigated. However, as studied for non-active (standard) correlation clustering (Thiel et al., 2019), pivot- methods yield poor clustering results. This is consistent with our experimental studies in the active correlation clustering setting (Section 4).
The works (Basu et al., 2004; van Craenendonck et al., 2018h; Soenen et al., 2021) are developed for active constraint clustering. We adapt the latter two our setting and investigate them our experiments.
2

---

Published in Transactions on Machine Learning Research (02/2024)
Motivated by these limitations,, develop generic framework for active learning for correlation clustering that better resembles the standard active learning framework. First, the pairwise similarities can be any positive or negative real number, and might even be inconsistent (ie., violate transitivity). This yields full flexibility in the type of feedback that a user or annotator can provide, in particular in uncertain settings. For example, assume the true similarity wetween objects u and v is +1. With binary leedback, the annotator may simply return -1 in the case of uncertainty/mistall titaake/uueeraantty may yield for example -0.1. A faulty feedback of -0.1 is much less severe than -1, and our framework can take advantage of this. Second, the process of querying pairwise similarities is separated from the clustering algorithm. This leads to more flexibility in how the query strategies can be constructed and they can be used in conjunction with any correlation clustering algorithm. In particular, we adapt an efficient correlation clustering method based on local search whose elfectiveness has been demonstrated in standard correlation clustering setting (Thiel et al., 2019; Chehreghani, 2022). Third, the queries are robust w.r.t. a noisy oracle by allowing multiple queries for the same pairwise similarity (i.c., a non-persistent noise model considered). Finally, it automatically identifies the number of clusters based on the available pairwise similarities. To the best of our knowledge, this framework is the first work that fulfills all the above-mentioned advantages.
However, with fcodback in [-1, 1] their
In addition to the generic active clustering framework, we propose and analyze a number of novel acquisition functions (query strategies) suited for correlation clustering. In particular, we analyze the triangles of objects and their relations in correlation clustering and propose two novel query strategies called mazmin and marezp. We finally demonstrate the effectiveness of the framework and the proposed query strategies via several experimental studies.
2 Active Correlation Clustering
In this section, we introduce our framework for active learning for correlation clustering. We start with the problem formulation, then describe the respective active learning procedure, and finally explain the clustering algorithm to be used in our framework.
2.1 Problem formulation
We are given set of N objects (data points) denoted by V {1,..., Nj. The set of the pairs of objects in V is denoted by E {(u, v) u. E V and u >> v} and will be used to indicate the pairwise relations between objects. Thus, we have E (M)
We assume there exists a generic similarity function o" E + IR representing the true pairwise similarities between every pair v) E E. However, this similarity function is not known in advance; one can only query the oracle for a noisy instantiation of this function for desired pair of objects while incurring some cost. We then use a
R to refer to some estimate of the pairwise similarities. If ou, v) = a" fu, v) for all uu E E have perfect estimate of the true pairwise similaritics, which is unrealistic in practice. Therefore, the goal is to recover the ground-truth clustering with minimal number of (active) queries for the pairwise similarities to the oracle, as each query incurs some cost." 2
The set V together with a similarity function a can be viewed as a weighted (undirccted) graph Go = (V, E) where the weight of edge (u,v) E E ou, v). We denote by e == (u, v) an edge in E. Let Go (z) = (z, E2) denote the subgraph of 9. induced by C V, where E_ {(u, E E u. E z and u > 0) S E. A clustering of S V is a partition of z into k disjoint sets (clusters). Let Cz be the set of all clusterings of z. Consider a clustering C E Cz. According to correlation clustering, edge (u,v) E, violates the clustering C if v), 2 0 while and u are in different clusters or if o(u, u) < 0 while u and e are in the
Quuerying an edge in E. means querying its weight, i.e., the pairwise similarity that represents.
3

---

Published in Transactions on Machine Learning Research (02/2024)
same cluster." Thus, given C' and o, the function of cluster violations R(2,0,0) E2 - R is defined as (o( w) iff (u, v) violates C
R (,,,o.((u.1))
0,
(1)
otherwise
Then, we define the correlation clustering cost function ((,,)) C2 RR given similarity function as Σ (ux,o,y(u,.))
(C)
(2)
(a,e)EB,
We aim for a clustering that is maximally consistent with a set of (provided) feedbacks a. The optimal clustering of z given a is ((2.)) arg mincec, (C), Thus, given o* the optimal correlation clustering solution w.r.t. the true pairwise similarities would be CiV.o.)- In this work, consider the case when o* is unknown and aim to estimate it appropriately via active learning in order to perform a proper correlation clustering. Finally, we let A(z,o) E Cz be the clustering found by some correlation clustering algorithm A given Go (z).
2.2 Active correlation clustering procedure
Algorithm Active clustering procedure
Input: Data objects V, initial similarity function do, clustering algorithm A, query strategy S, noise level y E [0, I], batch size B
Output: Clustering C E Cv
1: @ +- [
Qu + Ou V))(u,v), V(u,v) E E
i+0 0
while stopping criterion is not met do
C - A(V. oi)
6:
B - S(C', 2',0;, B)
D
|
B
7:
for (u,v) E B do
8:
Q ORACLE(U, v,7)
9:
@it + Cav UQ
10:
I:41 r) & 1 Enertt
11: end for
12: i i+i+1
13: end while
14:
Return C*
Algorithm outlines the active correlation clustering procodure. It takes as input the set of objects V. an imitial similarity function do: a correlation clustering algorithm A and a query strategy S. The initial similarity function can contain partial or no information about a*, depending on the initialization method. We will assume that [oo(e)] < À for all E E, where À [o, I]. In this paper, À 0.1 this indicates that are not confident about the initial edge weights. The algorithm begins by initializing a query matrix Q' where O is set containing all queries made for edge (u, E until iteration i. Each iteration consists of three steps. First, it runs the clustering algorithm A on objects V given the current similarity function This returns the clustering C E Cv. Second, the query strategy S selects a batch B C E of B edges. Then, the oracle is queried for the weights of all the edges (u, v) E B. In this paper, we consider a noisy oracle where the noise is non-persistent. This means that cach query for (u, v) E E returns a"(u, v) with probability 1 y or value from the set [-1, (A) 1] uniformly at random with probability y. This noise
S v) implies neutral feedback, where the oracle cannot. decide the objects similar dissimilar. For brevity, this similarly to positive pairwise similarities.
4

---

Published in Transactions on Machine Learning Research (02/2024)
model ensures that querying the same edge multiple times may be beneficial (which models an oracle that is allowed to correct for previous mistakes) and that noisy queries will not be smaller in absolute value than the initial edge weights in øo- This will lead to better exploration for some of the query strategies proposed in Section 3. In addition, we assume that the cost of cach query (to different pairs) is equal (c.g., 1), though our framework generic enough to encompass a varying query cost as well (where the acquisition function is divided by the respective cost). This choice means that the problem reduces to minimizing the number of queries made. This is the setting studied in most of the prior active learning work. Finally, the current similarity function o; is updated based on the queries to the oracle by setting (1 t) equal to the average of all queries made for the edge (u, v) so far. This leads to robustness against noise since a noisy query of an edge (u, v) will have less impact in the long run.
2.3 Active correlation clustering with zero noise
If a given similarity function a is fully consistent (which means that there is no noise flipping the sign of pairwise similarities and the transitive property of the pairwise similarities is satisfied); there will always exist solution for the correlation clustering objective in Eq. 2 with the cost of zero, and finding the solution is no longer NP-hard (unlike general correlation clustering). It is sufficient to simply extract the edges (u, u) E E such that o(u, v) > O and assign objects to their corresponding clusters. Therefore, in this paper, we consider the more challenging noisy setting where the information obtained from the oracle is noisy and leads to inconsistency among pairwise relations.
Most of the previous studies on active clustering that query pairwise relations between objects consider the zero noise setting and utilize methods that fully exploit this assumption. This is generally done by using the queried pairwise similarities to infer the pairwise relations that have not been queried yet, which may lead to improvement in performance in the zero noise setting. Let Equeried C E be the set of edges that have been queried so far. Consider the three objects u, v, w E V, where (u, v). (u, w) E Equeried: (u, w) E E \ Equeried: ou(u, v) = 1, (,(u,w) = 1. Given this, one can casily infer o;(e, w) = using the transitive property of the pairwise similarities. In principle, one can perform a multi-level inference where previously inferred information is used to infer new information. These methods are highly sensitive to noise and will in general perform very badly with even a small amount of noise since propagating noisy information in this manner cannot be recovered from. Therefore, they are not suitable for moisy setting.
2.4 Correlation clustering algorithm
Unlike the previous active correlation clustering methods (Mazumdar & Saha, 2017b; Bressan et al., 2019; Gareia-Soriano et al., 2020) that are bound to specific correlation clustcring algorithms, our framcwork is generic in the sense that it can be employed with any arbilrary correlation clustering method. Thereby, can use any of the several approximate algorithms proposed in the literature, e.g., (Bansal et al,, 2004; Demaine et al., 2006; Ailon et al., 2008; Charikar et al., 2005; Elsner & Schudy, 2009; Giotis & Guruswami, 2006). Among them, the methods based on local search perform significantly better in terms of both the quality of clustering and the computational runtimes (Thiel et. al., 2019; Chehreghani, 2022). Thereby, we employ a local search approach to solve the correlation clustering problem for a pairwise similarity matrix 0.4 The local search method in (Chchreghani, 2022) assumes a fixed number of clusters for correlation clustering. However, given the pairwise similarities a, the minimal violation objective should automatically determine the most consistent number of clusters. Consider, for example, the case where all the pairwise similarities are negative. Then, the clustering algorithm should place every object in separate cluster. On the other hand, when all the pairwise similarities are positive, then only one cluster must be identified from the data.
The work in (Thiel et al., 2019) develops a Prank-Wolfe optimization approach to correlation clustering, which then leads to a local search method with an optimized choice of the update parameter. To deal with the non-fixed (data-dependent) number of clusters, it sets the initial number of clusters to be equal to the number of objects N, and lets the algorithm try all numbers and thus leave some clusters empty. This
'hh effectiveness of greedy methods based on local search has been studied extensively in several other clustering settings as well, e.g, (Dhillon et. al., 2004; 2005).
5

---

Published in Transactions on Machine Learning Research (02/2024)
method yields some unnecessary extra computation that leads to increasing the overall runtime. Thereby, in this paper, we develop local search method for correlation clustering that at each local search step, automatically increases or decreases the number of clusters only if needed. In this method, we begin with a randomly initialized clustering solution and then we iteratively assign each object to the cluster that achieves maximally reduced). We allow for
a maximal reduction the violations (i.e., the cost function in Eq. the possibility that the object moves to a new (empty) cluster, and this way, we provide the possibility to expand the number of clusters. On the other hand, when the last object in an existing cluster leaves to move to another cluster, then the cluster disappears. We repeat this local search procedure until further changes (in the assignments of objects to clusters) happen for an entire round of investigating the objects. In this case, a local optimal solution is attained and we stop the local search. We may repeat the local search procedure multiple times and choose the solution with a minimal cost.
A naive implementation of this method would require a time complexity of (k:N3) (assume & is the number of clusters). We instead use an efficient algorithm whose time complexity is O(kN3). Given clustering C, assume C. indicates the cluster label for object u. Then, similar to the shifted Min Cut or correlation clustering with fixed number of clusters in (Chehreghani, 2013; 2022), can write the cost function in Eq. 2 as
(z)
Σ
R (xx,ocy(u,u))
(u,o)EE2
Σ
2 -
Σ
(lo(u, + ((u,)))
2
(u.u)EEx Cu=Cv
(u,ejEEz
CuzCo
Σ
la(u, b)
Σ
au, v) + 2 (u,))E,,
Σ
olu v)
Σ au,
2
2
(u,n)EE,
(u.0)EE, C.=C.
(u.v)EE, CC=Cv
Σ
Σ ouu, v). (a. C.=C.
(3)
(u,jjEE,
constant
The first term in Eq. 3 is constant w.r.t. the choice of a particular clustering C. Thereby, we have
(m,, (C) Max (C) + constant, (2,0)
(4)
where the mar correlation objective function A MaxCor C2 - IR is defined as (2,0)
A MaxCor
(C)=
Σ
auu, v).
(5)
22,0)
(,.v)EE, C.=C.
Then, we have
arg max A MaxCor (C) = arg min (C). CEC,
(6)
(2.)) CeC,
Therefore, we will seek to maximize
MaxCorr (C), while the number of clusters is non-fixed and dynamic. (2.07
Assume in clustering C the cluster label of object is 1, ie., Cn L. Then, A MaxCor (C) is written
(2,0)

---

Published in Transactions on Machine Learning Research (02/2024)
A Maxtor (C) = Σ ((,
(2.0)
(B,w)EBB
C.=Cw
Σ (u, +
Σ o(u.
(F,w)EE2
C.=CC. 0,107f
C,=l
where the first term (i.c., ()) is independent of u and only the second term d depends on
As mentioned, we perform a local search in order to minimize the cost function (C) or equivalently maximize the objective A MaxCor (C). In this method, we start with random clustering solution and then (z.0) we iteratively assign each object to the cluster that yields maximal reduction in the cost function or a maximal improvement of the objective A Maar (C). Consider an intermediate clustering C' with clusters in an arbitrary step of local search. To compute the new cluster of an object u, one needs to evaluate the cost/objective function for different clusters and choose the cluster which leads to maximal improvement. Assuming the clustering is performed on all the objects in V. One evaluation of the cost. function ((, (C) or the objective function A MaxCor (C)) would have the computational complexity O(N2). Since this evaluation is performed for each of l clusters (i.e., w is investigated to be assigned to each of k clusters), then the naive implementation of the method would have the complexity of O(NN2). If this is repeated for all objects, then it will be OK.N3) However, introducing A (e..)) MMxxCrr (C) and in particular its formulation in Eq. 7 provides a computationally efficient way to implement the local search, similar to the Shifted Min Cut method in (Chehreghani, 2022). For each object u, only the second term ō in Eq. 7 varies as we investigate different clusters for this object. Thus, the first term (i.e., μ)) is the same when evaluating the assignment of object u to different clusters and can be discarded. In this way, evaluating an object for & different clusters will have the computational complexity of OKNN) (instead of (kN22), and hence the complexity for all the objects becomes O(N?2) (instead of )l:
(V.r)
This local search method is outlined in Algorithm 2. takes as input a set of objects 2, a similarity function or an initial number of clusters k; the number of repetitions T, and a stopping threshold n,. In our experiments, we set T = 3, 1 2- (double precision machine epsilon) and k |z] in the first iteration of Algorithm 1, and then k = |C*| for all remaining iterations where |C*| denotes the number of clusters in the current clustering C³ (in Algorithm 1). The output is a clustering C' e Cz. The main part of the algorithm (lines 6-27) is based on the local search of the respective non-convex objective. Therefore, we run the algorithm T times with different random initializations and return the best clustering in terms of the objective function. The main algorithm (starting from line 6) consists of initializing the current clustering C' randomly. Then, it loops for as long as the current mar correlation objective changes by at least 1) compared to the last itcration. If not, assume it has converged to some (local) optimum. Each repetition consists of iterating over all the objects in z in a random order O (this ensures variability between the T runs). For each object u E O, it calculates the similarity (correlation) between u and all clusters E C, which is denoted by Su(u). (u) is computed based on the second term (i.e., 5) in Eq. 7. Then, the cluster that is most similar to u is obtained by arg max (u). Now, if the most similar cluster to u has a negative correlation score, this indicates that u is not sufficiently similar to any of the existing clusters. Thus, we construct a new cluster with u as the only member. If the most similar cluster to u is positive, we simply assign u to this cluster. Thus, the number of clusters will dynamically change based on the pairwise similarities (it is possible that the only object of a singleton cluster is assigned to another cluster and thus the singleton cluster disappears). Finally, in cach repetition the current maz correlation objective is computed efficiently by only updating it based on the current change of the clustering C' (i.e., lines 19 and 25).
3 Query Strategies
In this section, we describe and investigate number of query strategies for active learning applied to correlation clustering. A simple baseline query strategy would be to query the weight of the edge e E E
7

---

Published in Transactions on Machine Learning Research (02/2024)
Algorithm 2 Max Correlation Clustering Algorithm A (dynamic k)
Input: Objects 2 C V, similarity function o, initial number of clusters k, number of iterations T, stopping threshold "
Output: Clustering C' E Cz
1: N - |z]
2: k f min(k, N)
best f -00
Chest f- {z}
for j [L...., T do
C+ (cl (c',..,,e ), where c' (0) for all i (1,...,k) ...
Assign each object in z to one of the clusters in C' uniformly at random
A + A MaxCor (C)
8:
(2.0)
Aold A
10:
while |A Aotal do
11:
Sold < A
12:
< a random permutation of the objects in z
13:
for each u in O do
14:
Sc(u) c EEee,uzt a(u,)) v) for ceC Cmax t arg max So(u) Cu cluster
15:
16:
C that currently involves if Semaa (u) < 0 then
17:
18:
Remove from its current cluster
19:
A + A.S. (u)
20:
Cnew + {u}
21:
C + C Gnew
22:
+ k+1
23:
else
24:
Move u from its current cluster to Cmax
25:
A + A - Se. (u) + (t)..(u) (u)
26:
Remove empty clusters from C and decrease accordingly
27:
end if
28:
end for
29:
end while
30:
if A
Abrst then
31:
Chest + C Abest f- A end if
32:
33:
34: end for
35: return Chest
selected uniformly at random. However, this strategy may not lead to querying the most informative edge weights. Instead, one construct more sophisticated query strategies based on information in one of the following three components: the current clustering C², the current query matrix Q' and the current similarity function
3.1 Uncertainty and frequency
In this section, we propose two simple query strategies that are meant to be used as baselines. Uncertainty usually refers to lack knowledge. Therefore, one way to quantify uncortainty to consider the edge with the smallest edge weight in absolute value, since a smaller magnitude indicates lack of confidence. In other words, we select and query the edge according
8

---

Published in Transactions on Machine Learning Research (02/2024)
é arg min (az(e)). eEE
(8)
However, this may not always be an optimal strategy since low magnitude of an edge weight does not necessarily imply informativeness. To see this, consider three distinct nodes (u, v w) S V with pairwise similaritics {u v), (u, w), (v, w)} = 1..1. While ou, w) has a small absolute value, one can infer that its value must be using the transitive property of pairwise similarities (see Section 3.2). Thus, querying the odge (v, w) is unlikely impact the resulting clustering.
An alternative strategy, called frequency, aims to query the edge with the smallest nunber of queries so far, ie.,
é min O oc E
(9)
Eq. 8 and Eq- 9 will behave very similarly if the pairwise similarities in the initial similarity matrix on are small in absolute value, e.g., [oo(e]] & 0.1 for all e E E. Additionally, with a more noisy oracle, Eq. 8 may query the same edge more than once (which could be beneficial), although this is quite unlikely. Finally, a batch of edges B S E can be selected by selecting the top [B] edges from Eq. or Eq. 9.
3.2 Inconsistency and the maxmin query strategy
Inconsistency indicates that there is no clustering C' E C2 of some = C V such that the correlation clustering cost. (C) is O. This occurs when the similarity function a consists of conflicting information about how particular edge vu Eg is to be clustered. In turn, this happens when a does not satisfy the transitive property of the pairwise similarities. Sets of three objects (u, u, w) S V, which we call triangles, are the smallest collection of objects for which an inconsistency can occur. The transitive property says that if a(u, v) 2 0 and ou, w) 2 then (v, w) 0 or if (u, 2 0 and ou,, w) < 0 then (v, w) < 0. The inconsistencies in set of four or more objects in V come down to considering each of the triangles that can be constructed from the objects in the set. We discuss this in more detail later, but it highlights the importance of triangles. We denote by T the set of triangles f = (u, v, w) of distinct objects in V, i.c., T = (%). and E. = ((u, v), (u, w), (v, })} indicates the edges between the objects of triangle = (u, U, w) T.
In this section, we propose query strategy that queries the weight of an edge in some triangle E T with the smallest contribution to the inconsistency of t. Such an edge represents the minimal correction of the edge weights in the triangle / in order to satisfy consistency. Furthermore, since are in an active learning setting, we want to choose the marimum of such corrections among all the triangles (to gain maximal information/
(formnation/correction)) /correction). We call this query strategy mazmin. Theorem I provides a way to select an edge
according to the maxmin query strategy.
Theorem 1. Given o, let To C T be the set of triangles t t (u, v, w) E T with exactly two positive edge weights and one negative edge weight. Then, the mazmin query strategy corresponds to querying the weight of the edge é selected by
(i, () = arg max min (a(e)..
(10)
TET, eEE,
Proof. See Appendix A.1.
The set To introduced in Theorem 1 will be referred to the set of bad triangles (given σ). The reason is (C)=
that for every t E To there is no clustering C E C, such that (C), 0 (i.c., they induce inconsistency). On the other hand, T To will be referred to as the set of good triangles, i.e., those for which there is a clustering C' E C, such that (C)= = 0.
We now provide some further motivation for why we consider triangles (i.c., collections of thrce objects) instead of collections of four or more objects in V. We say that two triangles t t2 E T are correlated if they share edge. A lower bound of mincecy (C) can be obtained by summing the minimal cost.
9

---

Published in Transactions on Machine Learning Research (02/2024)
mincec, (C) of all edge-disjoint (uncorrelated) bad triangles. This is because all uncorrelated bad triangles must contain at least one unique edge (u, v) E E, that violates the clustering. Tt is a lower bound since additional mistakes can occur in any triangle t E T (whether it is good or bad) if it is correlated with one or more bad triangles. Thus, a correlation clustering algorithm A must consider such correlations in order to find a clustering that. best. balances all of the (possibly conflicting) inconsistencies. The inconsistencies that can occur among collections of four or more objects in V boil down to considering the (potentially correlated) triangles that can be constructed from the objects in the collection.
Thereby, it is clear that maxmin prefers to select edges in bad triangles. Assuming To- = 0, if To, * 0 in some itcration i (due to a poor initialization of d or noisy oracle), then all bad triangles t E To, are guaranteed to contain at least one edge e E E, with a similarity ai(e) that does not agree with o² (i.e., wrong information). Therefore, it would be beneficial to query the edges in bad triangles in order to reveal o² as quickly as possible.
We observe that maxmin would prefer a bad triangle with the edge weights {1,0.7, -0.7 over bad triangle with the edge weights {1,1, -0.1). The reason is that the first triangle is more confidently inconsistent compared to the second one. This means that the clustering of the three objects involved in the first triangle will increase the value of the clustering cost A(v,)) more than the second triangle (also see proof of Theorem for more on this). Therefore, it makes sense to prioritize querying one of the edges in the first triangle to resolve the inconsistency.
Finally, since maxmin ranks all good triangles equally we will follow the random query strategy to select an edge if To: 0 in some iteration i. Also, batch of edges B C E can be selected by selecting the top [B] edges from Eq. 10 (sce Section 3.5 for dctails).
3.3 Maxexp query strategy
Consider a triangle (u, v w) with edge weights {a(u, v),, ou, w), (v, where au, v) is fixed, la w) 2 (a(u, v)] and |a(v, w)] 2 lo(u, v)). Then, the maxmin strategy will give equal scores to all such triangles regardless of what (u, w) and ol, w) are, since (o v)] is always the smallest edge weight in absolute value. Hence, a triangle l with edge weights -0.1) will be ranked equally to a triangle le with edge weights 1.1,0.1,-0.111
We would like for t to be selected over 12 since it is more confidently inconsistent. This issue occurs because maxmin discards all edges except for the edge with minimal weight in absolute value. One way to fix this is to replace the smallest absolute edge weight (i.e., the minimal inconsistency) with the expected inconsistency or violation. We call this query strategy mazerp.
Given a triangle& / E T, maxexp defines the probability of clustering C CEC Ce
(p(- (C]()) Ecrec, exp( exp(-33App 34 (1,)))((
(11)
where 3 is a hyperparameter to be discussed later. Eq. 11 assigns a higher probability to clusterings with a smaller clustering cost in the triangle t. Then, we can compute the expected cost of a triangle t as
E[A:] = Bc-Picc)AAnn((0)
Σ (())))) CEC.
(12)
While maxmin gives all good triangles a score of 0, maxexp will not do in general (except if B co, see next section). However, larger expected cost for good triangle does not imply that it is more informative, like it does for a bad triangle. Therefore, we restrict maxexp to query edge weights from bad triangles, i.e., those that are guaranteed to contribute to an inconsistency:
i == arg max R( A.).
(13)
tET,
10

---

Published in Transactions on Machine Learning Research (02/2024)
We can then select the edge from é with the smallest absolute edge weight, ie., é minegE, |o(e)]. A batch B S E is selected as for maxmin (see Section 3.5 for details). Thus, in summary, maxexp queries edges in bad triangles with the largest expected clustering cost. In the case that To, = 0 in iteration i, we query an odge weight uniformly at random. In Appendix B.2 we discuss some further extensions of maxexp.
3.4 Further analysis of maxmin and maxexp
In this section, we analyze the behavior of maxexp compared to maxmin. Any triangle t = (u, v, w) E T can be clustered in five different ways, i.e., C. = (C ...... c(.)) = {[(u, v, w)). {(u), (v, w)), {(w), (u, w)). {(w), (u, v)}, (()).()), (w)}} (order is important here). The pairwise similarities of a triangle E T are denoted by {81, 82, 83} = {a(u, v), ou, w), (w, w)} (order important here too). Let Pj = p(C(-))))) for ........ Then, Proposition 1 provides an expression for the expected cost E[As].
Proposition Given a bad triangle E To where 81 and 82 are positive and 83 is negative. We have
E E| = pi |33 + p2 ([11 + |s2| (ssl) +
(14)
p3/81| p2 p5([ |s2))
Proof. See Appendix A.2.
From Proposition 1 we conclude two insights. First, the larger the pairwise similarities are in absolute value the larger the expected cost (i.e., maxexp prioritizes the bad triangles that more confidently inconsistent). Second, the two positive edges violate three of the five clusterings while the negative edge only violates two of the five clusterings. This implies that there is a bias towards the bad triangles wherein the positive edge weights are larger compared to the negative edge weight in absolute value. See Appendix B.1 for more details.
special case of maxexp when oc, as shown in Proposition 2. Proposition 2. Given a bad triangle I E Ta where 81 and 82 are posilive and 83 is negalive. The oplimization problems in Eq. 10 and Eq. 13 are equivalent if 3 00, i.e.,
Furthermore, maxmin can be regarded
lim E [ min (e()).. Vt E To 80000
(15)
eEB.
Furthermore, if 3 0 we have
2 |52| + |s3). |ss|
lim B[A:]
(16)
8-30
Proof. See Appendix A.3.
Proposition 2 implies that 3 can be used to control the level of confidence we put in each of the clusterings when computing the expected cost. The most optimistic case is when B = oo where we put all the confidence in the most likely clustering (i.c., the clustering with the smallest cost). The most pessimistic case when B = 0 where all clusterings are weighted equally. Intermediate values of 3 will result in different weightings of the clustcrings, lcading to different rankings of the triangles. The best value of B depends on the problem, and usually, wide range of values is acceptable.
3.5 Efficient implementation of maxmin and maxexp
Solving the optimization problems of maxmin and maxexp (Eq. 10 and Eq. 13, respectively) requires enumerating all the [T| = (5) ((v3) triangles. However, we are only concerned with the bad triangles To C T, i.c., the triangles for which there is no clustering C E C, such that (C) 0. This means that at least one edge in each bad triangle t E To has to violate the current clustering C³. Given this, we maintain a set Eyiolates of edges that violate the current clustering C³. Constructing this set is O(N2), since we need to iterate over all (N) edges. Given Eviolates, we can efficiently locate all bad triangles without having to iterate over all (3) triangles as follows. We iterate over each edge (u, v) Exlolates and for each
11

---

Published in Transactions on Machine Learning Research (02/2024)
edge, we iterate over all remaining objects V fu, u) which gives us all the bad triangles. This step requires EEyiolate|| x N iterations, which is ((N3) in the worst case when all edges violate C*, i.e., when Exiolates = E. However, in practice [BViolaee|| < | which makes this procedure siguificantly more efficient. Despite this, to further improve the efficiency (as well as the exploration of maxmin and maxexp, as discussed below), we consider random subset of Eviolates of size N. The total iterations of the whole procedure will then be (2) N ((N)), which significant improvement over naively iterating over all O(NS) triangles. Algorithm 3 outlines our implementation of maxmin and maxexp.
Exploration with maxmin and maxexp. If we have To- = and Too = 0, then maxmin and maxexp can be interpreted follows. They begin querying edges randomly (since Tap 0 implies that there are bad triangles initially) and once bad triangles appear due to the new queries, they will begin to actively fix the bad triangles (i.c., turn them into good triangles). If the noise level is large, they might waste too many queries on fixing bad triangles, leading to a lack of exploration of other edges, thus degrading the performance in the long run. By sampling N edges from Eviolates we only consider a random subset of the bad triangles (as explained before), which results in improved exploration overall. We have observed improved performance of this method compared considering all the bad triangles. In addition, sampling the bad triangles can enhance the diversity of the B edges queried in each iteration which can be useful in batch active learning (Ren al., 2021).
There are various other options to alleviate the exploration issue. In this paper, we consider two additional methods, First, we consider a hard limit on the number of times one can query an edge. This limit is denoted by T and we have m [2/] S 7 for all i. Second, we consider 6-groedy selection where one queries edge weights according to maxmin (or maxexp) with probability 1 --c e or uniformly at random with probability e. More sophisticated exploration techniques adopted from multi-armed bandits can also be employed which we postpone to future work.
Algorithm Efficient implementation of maxmin and maxexp
Input: Data objects V, current similarity function o,, current clustering C¹, batch size B Output: Batch B
N N V
Eviolates + {(u, E R(v.or,. v) > 0}
3: Efand < Uniform random subset of Eviolates of size N I NNN
b N x matrix of zeros.
for (u, v) Erand do
for E V {u do
7:
if 1-= (u, v, w) is bad triangle then
8:
Eminn +- arg min [e)(e)
9:
emiin +- Randomly selected edge from Emiia
10:
if maxmin then
I(emin)= < (efiin)
11:
12:
end if
13:
if maxexp then
14:
I(emin) (a I(e!iin)
[[ defined in Eq. 12.
15:
end if end if
16:
17: end for
18:
end for
19: B arg ma Eee E
20: Return 3*
4 Experiments
In this section, describe our experimental studies, where additional results are presented in Appendix C.
12

---

Published in Transactions on Machine Learning Research (02/2024)
4.1 Experimental setup
Initial pairwise similarities. For each experiment, we given dataset with ground-truth labels, where the ground-truth labels are only used for evaluations. Then, for each (u, v) E E in dataset, we set o"(u (u, v) to +1 if u and v belong to the same class, and -1 otherwise. In active learning, a* is not available to the correlation clustering algorithm. The similarity function dg can for example be initialized with random weights or based on a partially correct pre-computed clustering. We investigate both methods in our experiments. For random initialization, we randomly assign cach of the objects to one of the ten different clusters resulting in clustering C. Then, for each (u, v) E E, the initial similarity cn v) is set to +0.1 if u and v are in the same cluster according to C, and -0.1 otherwise. The initial similarities are set to 0.1 in absolute value in order to indicate uncertainty about their correct values. In the other initialization method, we run +-means++ on the corresponding dataset which results in a clustering that is given to the active learning procedure. The clustering is converted into a similarity function in the same way as described above. The feature vectors are used by k-means++ to yield the initial clustering, but the active learning procedure does not have access to them and only uses the initial pairwise similaritics.
Clustering algorithm. All the experiments use the correlation clustering algorithm described in Section
2.4.
Query strategies. We consider five different query strategies: uniform, uncertainty (Eq. 8), frequency (Eq. 9), maxmin (Eq. 10) and maxexp (Eq. 13). We set <= 0.3, t == and , = 1 for all experiments unless otherwise specified. See Appendix C for experiments with different values of these parameters.
Baselines. As previously discussed, none of the existing methods naturally align with our framework, especially in terms of supporting batch selection of a fixed size. Consequently, we have adapted these methods to fit our framework by performing the corresponding method from scratch while maintaining fixed query budget equivalent to the total number of edges queried in the current iteration i of our framework. Below, we provide a description of cach of the bascline methods.
QECC. This method is pivot-based active correlation clustering algorithm introduced in (García- Soriano et al., 2020). It starts by randomly selecting a pivot (object) u E V and then queries the similarity between u and all other objects V \Yu u to form a cluster with u and all the objects with a positive similarity with u. It then continues iteratively with the remaining objects until all objects are assigned to a cluster or if the query budget is reached. More specifically, we implement QECC- heur (also introduced in (García-Soriano et al., 2020)) which is heuristic improvement over QECC, but the general idea of this method is the same as QECC.
COBRAS. This is an active semi-supervised clustering method developed in the constraint clus- tering setting. It is an extension of COBRA (van Craenendonck et al., 2018a). COBRA initially clusters the data into l clusters (super-instances using k-mcans. The modoid of each cluster is then considered a representative of the super-instance. The goal is to cluster the medoids (and thus indi- rectly all data points represented by the medoids) with pairwise queries between the medoids. Thus, the pairwise relations involving all non-medoid objects are assumed fixed after running k-means initially, which may be a significant limitation if the feature representation is insufficient. COBRAS extends COBRA by allowing refinement of the super-instances as more pairwise queries are made.
COBBASS. This method is also an active constraint clustering method introduced in (Soenen et al., 2021). nCOBRAS extends COBRAS to the noisy setting by attempting to detect and correct the noisy pairwise constraints. This method suffers from varions limitations and issues, e.g., it assumes the underlying noise level known (which is very unrealistic). and the performance (and computation time) is severely affected by larger noise levels and larger query budgets.
It is worth mentioning that COBRAS and nCOBRAS use feature vectors which give them an unfair advantage over our methods. Implementations of COBRAS and nCOBRAS are publicly available and are thus used in
13

---

Published in Transactions on Machine Learning Research (02/2024)
our experiments." Finally, we note that there exist other active semi-supervised clustering methods developed in the constraint clustering setting such as NPU (Xiong et al., 2014) used a baseline in (Soenen et al., 2021). These methods are not directly relevant to our setting: They do not consider correlation clustering, use feature vectors, and assumc zero noisc. Morcover, has been shown that COBRAS and nCOBRAS outperform these methods (Soenen et al., 2021), and, therefore, we do not include them in our experiments.
Performance evaluation. In cach iteration of the active correlation chustering procodure, we calculate the Adjusted Rand Index (ARI) between the current clustering C' and the ground truth clustering C(V,o') Intuitively, ARI measures how similar the two clusterings are, where value of 1 indicates they are identical. We report results for additional evaluation metrics in Appendix C. Each active learning procedure is repeated 15 times with different random seeds, where the variance is indicated by shaded color.
Datasets. We perform experiments on ten different datasets, all of which are listed and explained below. For a dataset of N objects, the number of pairwise similarities is E = (N x (N - 1))/2, which implies the huge querying space that active learning needs deal with. We use a batch size of B [E]/1000] for all datascts, unless otherwise specified.
1. Synthetic: consists of NN 500 (and E 124750) normally distributed 10-dimensional data points split evenly into 10 clusters.
20newsgroups: consists of 18846 newsgroups posts (in the form of text) on 20 topics (clusters). We use a random sample of N 1000 posts (with |E| = 499500). The cluster sizes are 46, 57, 45, 48, 63, 47, 48, 65, 51, 53, 39, 57, 46, 56, 65, 47, 52, 48, 38 and 29. For the k-means initialization of do we use k = 20. We use the distilbert-base-uneee Python library (Akbik et al., 2018) in order to embed each of the 1000 documents (data points) into a 768-dimensional latent space, in which k-means is performed.
transformer model loaded from the Flair
3. CIFAR10: consists of 60000 32 32 color images in 10 classes, with 6000 images per class. We use random sample of N 1000 images (with |E| 499500). The cluster sizes are 91, 96, 107, 89, 99, 113, 96, 93, 112 and 104. For the k-means initialization of ag we use k == 3. We use a ResNet18 model (He et al., 2015) trained on the full CIFAR10 dataset in order to embed the 1000 images into a 512-dimensional space, in which k-means is performed.
4. MNIST: consist of 60000 28 x 28 grayscale images of handwritten digits. We use sample of N = 1000 images (with [E| = 499500). The cluster sizes are 105, 109, 111, 112, 104, 86, 99, 88, 88 and 98. For the k-means initialization of op we use k = 3. We use simple CNN model trained on the MNIST dataset in order to embed the 1000 images into a 128-dimensional space, in which k-means is performed.
5. Cardiotocography: includes 2126 fetal cardiotocograms consisting of 22 features and 10 classes. We use a sample of N = 1000 data points (with |E| = 499500). The cluster sizes are 180, 275, 27, 35. 31, 148, 114, 62, 28, 100. For the k-means initialization of do we use k == 10.
6. Ecoli: a biological dataset on the cellular localization sites of 8 types (clusters) of proteins which includes N 336 samples (with |E| 56280). The samples are reprosented by 8 real-valued features. The cluster sizes are 137, 76, 1, 2, 37, 26, 5, and 52. For the k-means initialization of oo use k = 10.
Forest Type Mapping: remote sensing dataset of N 523 samples with 27 real-valued attributes collected from forests in Japan and grouped in 4 different forest types (clusters) (with EE| = 136503). The cluster sizes are 168, 84, 86, and 185. For the k-mcans initialization of d use k = 10.
8. Mushrooms: consists 8124 samples corresponding to 23 species of gilled mushrooms in the Agaricus and Lepiota Family. Each sample consists of 22 categorical features. We use a sample of N 1000
Liik the open-source implementations of COBRAS and nCOBRAS: http::///stttuulccc/m////seeeees cobras
14

---

Published in Transactions on Machine Learning Research (02/2024)
1.0
0.6
0.6
0.6
Maxexp
Maxexp
Maxmin
M
Maxmin
ARI
Maxmin
0.4
Uncertainly
0.4
Uncertainty
0.4
Uncertainly
Frequency
Froquency
Frequency
Unifom
Uniform
Uniform
nCDBRAS
ACOBRAS
nCOBRAS
COBRAS
COBRAS
COBRAS
GECC
0.0
GECC
0.0
OECC
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(a) 20uewsgroups
(b) Cardiotocography
(c) CIPAR10
0.8
0.8
0.8
0.6
0.6
0.6
ARI
Maxcxp
ARI
Maxoxp
ARI
Maxcxp
Maxmin
Maxmin
Uncertainty
Uncertainty
Uncertainty
Frequency
Frequency
www
Frequency
Unifor
Unifor
Uniform
0.2
ACDBRAS
0.2
ACOBRAS
0.2
nCOBRAS
COBRAS
COBRAS
COBRAS
0.0
QECC
0.0
QECC
0.0
QECC
0.0
0.2
0.4
0.6
0.0
D.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges querled
Proportion of edges queried
Proportion of edges queried
(d) Ecoli
(e) Forest type mapping
(f) MNIST
1.0
1.0
1.0
0.8
0.8
0.8
0.6
ARI
Maxsaxp
Maxexp
Maxexp
Maxmin
Maxmin
Maxmin
0.4
Uncertainty
0.4
Uncertainty
0.4
Uncertainty
Frequency
Frequency
Frequency
Uniform
Uniform
Uniform
0.2
ICOBRAS
0.2
RCOBRAS
0.2
nCOBRAA
COBRAS
COBRAS
COBRAS
0.0
GECC
QECC
OECC
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges queried
Proportion edges queried
Proportion edges queried
(g) Mushrooms
(h) User knowledge
Yeast
Figure Results for different datascts with 20% noise (7 = 0.2) and random initialization of the pairwisc similarities. The evaluation metric the adjusted rand index (ARI).
data points (with E = 499500). The cluster sizes are 503 and 497. For the k-means initialization of do we use 2.
User Knowledge Modelling: contains 403 students' knowledge status on Electrical DC Machines with 5 integer attributes grouped in categories (with E 81003). The cluster sizes are 111, 129, 116, 28, and 19. For the k-means initialization of do we use 5.
15

---

Published in Transactions on Machine Learning Research (02/2024)
1.0
0.6
0.6
0.6
Maxexp
Maxexp
Maxmin
Maxmin
Maxmin
0.4
Uncertainly
0.4
Uncertainty
0.4
Uncertainly
Frequency
Froquency
Frequency
Unifom
Uniform
Uniform
MCDBRAS
nCOBRAS
nCOBRAS
COBRAS
COBRAS
COBRAS
GECC
0.0
GECC
0.0
aECC
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(a) 20uewsgroups
(b) Cardiotocography
(c) CIPAR10
0.8
0.8
0.8
0.6
0.8
0.6
ARI
Maxcxp
AR
Maxoxp
AR
Maxcxp
Maxmin
Uncertainty
Uncertainty
Uncertainty
Frequency
Frequency
Frequency
Unifom
Unifom
Uniform
ACOBRAS
0.2
#COBRAS
0.2
nCOBRAS
COBRAS
COBRAS
COBRAS
0.0
QECC
0.0
QECC
0.0
QECC
0.0
0.2
0.4
0.6
0.0
D.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(d) Ecoli
(e) Forest type mapping
(f) MNIST
1.0
1.0
1.0
0.8
0.8
0.8
0.6
Maxstop
Maxexp Maxmin
Maxexp
ARI
Maxmin
Maxmin
0.4
Uncertainty
0.4
Uncertainty
0.4
Uncerteinty
Frequency
Frequency
Frequency
Uniform
Uniform
Unitorm
0.2
ICOBRAS
0.2
RCOBRAS
0.2
nCOBRAS
COBRAS
COBRAS
COBRAS
GECC
QECC
QECC
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges queried
Proportion ledgs queried
Proportion edges queried
(g)
Mushrooms
(h) User knowledge
Yeast
Figure 2: Results for different datascts with 40% noise (7 0.4) and random initialization of the pairwisc similarities. The evaluation metrie the adjusted rand index (ARI).
10. Yeast: consists of 1484 samples with real-valued features and 10 clusters. We use a sample of N 1000 data points (with |E| = 499500). The cluster sizes are 319, 4, 31, 17, 28, 131, 169, 271, 12 and 18. For the k-means initialization of do we use 10.
16

---

Published in Transactions on Machine Learning Research (02/2024)
1.0
0.6
0.6
0.6
Maxexp
Maxexp
ARI
Maxmin
Maxmin
Maxmin
0.4
Uncertainly
0.4
Uncertainty
0.4
Uncertainly
Frequency
Froquency
Frequency
Unifom
Uniform
Unifom
1CDBRAS
nCOBRAS
nCOBRAS
COBRAS
COBRAS
COBRAS
GECC
0.0
GECC
0.0
OECC
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(a) 20uewsgroups
(b) Cardiotocography
(c) CIPAR10
0.8
0.8
0.8
0.6
0.8
0.6
Maxcxp
Maxoxp
Maxcxp
ARI
ARI
ARI
Maxmin
Uncertainty
Uncertainty
Uncertainty
Frequency
Frequency
Mayy
Frequency
Unifom
Unifom
Uniform
ACDBRAS
0.2
ECOBRAS
0.2
nCOBRAS
COBRAS
COBRAS
COBRAS
0.0
QECC
0.0
QECC
0.0
QECC
0.0
0.2
0.4
0.6
0.0
D.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges querled
Proportion of edges queried
Proportion of edges queried
(d) Ecoli
(e) Forest type mapping
(f) MNIST
1.0
1.0
1.0
0.8
0.8
0.8
hwwp:///ttmmmmmm/taa/t/eee/ Neveral
ARI
Maxseop
Maxexp
Maxexp
Maxmin
Maxmin
Maxmin
0.4
Uncertainty
0.4
Uncertainty
0.4
Uncerteinty
Frequency
Frequency
Frequency
Unifomm
Uniform
Uniform
0.2
ICOBRAS
0.2
RCOBRAS
0.2
nCOBRRS
COBRAS
COBRAS
GECC
QECC
QECC
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion edges queried
Proportion edges queried
Proportion edges queried
(g) Mushrooms
(h) User knowledge
Yeast
Figure Results for different datascts with 20% noise (? 0.2) and k-means initialization of the pairwise similarities. The evaluation metric the adjusted rand index (ARI).
4.2 Experiments on real-world datasets
Figures 1 and 2 illustrate the results for different real-world datasets with a random initialization of ap and noise levels y = 0.2 and 7 = 0.4, respectively. We observe that with even a fairly small amount of noise, all the basclines (nCOBRAS, COBRAS and QECC) perform very poorly. In general, nCOBRAS (which is supposed to be robust noise) has a lot of trouble with larger query budgets and noise levels. For smaller budgets, nCOBRAS usually outperforms COBRAS in the noisy setting (as demonstrated in (Soenen et. al.,
17

---

Published in Transactions on Machine Learning Research (02/2024)
1.0
0.6
0.6
0.6
Maxexp
Maxexp
Maxmin
Maxmin
Maxmin
0.4
Uncertainly
0.4
Uncertainty
0.4
Uncertainly
Frequency
Froquency
Frequency
Unifom
Uniform
Uniform
nCDBRAS
nCOBRAS
nCOBRAS
COBRAS
COBRAS
COBRAS
GECC
0.0
GECC
0.0
OECC
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(a) 20uewsgroups
(b) Cardiotocography
(c) CIPAR10
0.8
0.8
0.8
0.6
0.8
0.8
Maxcxp
Maxoxp
Maxcxp
ARI
ARI
Uncertainty
Uncertainty
Uncertainty
Frequency
Frequency
Frequency
Unifomm
Unifom
Uniform
ACOBRAS
0.2
#COBRAS
0.2
RCOBRAS
COBRAS
COBRAS
COBRAS
0.0
QECC
0.0
QECC
0.0
QECC
0.0
0.4
0.6
0.0
D.2
0.4
0.6
0.0
D.2
0.4
0.6
Proportion of edges querled
Proportion of edges queried
Proportion of edges queried
(d) Ecoli
(e) Forest type mapping
(f) MNIST
1.0
1.0
1.0
0.8
0.8
0.8
0.6
Manstop
Maxexp
Maxexp
ARI
Maxmin
Maxmin
Maxmin
0.4
ww
Uncertainty
0.4
Uncertainty
0.4
Uncerteinty
Frequency
Frequency
Frequency
Unifomm
Uniform
Unitorm
0.2
ICOBRAS
0.2
RCOBRAS
0.2
nCOBRAS
COBRAS
COBRAS
GECC
QECC
QECC
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges queried
Proportion edges queried
Proportion edges queried
(g) Mushrooms
(h) User knowledge
Yeast
Figure 4: Results for different datasets with 40% noise (? 0.4) and k-means initialization of the pairwise similarities. The evaluation metrie the adjusted rand index (ARI).
2021)). However, they tolerate only very small query budgets such as 200, resulting in ARI of 0.45 average with 10% noise, which is very low compared to our results. In contrast, our methods can handle any query budget and essentially always converge to optimal clustering (i.e., perfect ARI) even for high noise levels. The inconsistency-base based query strategy maxexp outperforms the other methods with the best performance overall. We also see that maxmin performs well in many cases, but has trouble converging for some of the datascts. As expected, uncertainty and frequency perform very similarly (as discussed Section 3), while outperforming the random query strategy in all cases.
18

---

Published in Transactions on Machine Learning Research (02/2024)
1.0
0.8
0.8
0.6
ARI (AUC)
0.6
ARI (AUC)
Maxexp
Maxexp
Maxmin
0.4
Maxmin
0.4
Uncertainty
Uncertainty.
Frequency
Frequency
Uniform
0.2
Uniform
0.2
nCOBRAS
nCOERAS
COBRAS
COBRAS
0.0
QECC
QECC
0.0
0.2
0.4
0.6
0.8
500
1000
1500
2000
Noise level
Batch size
(a)
(b)
Figure 5: Performance of different query strategies on the synthetic dataset with varying values of the noise level 7 and batch size B. When varying the noise level, we fix B = [E|11000 When varying the batch size, we fix 7 = 0.2.
Figures 3 and 4 show the results for different real-world datasets with k-means initialization of do and with noise levels of y 0.2 and 7 0.4, respectively. The overall conclusion is very similar the random initialization of Øu. i.c., maxexp and then maxmin yicld the best results with remarkable margin. We also observe that the performance of our methods is slightly belter with this initialization, in particular, maxmin seems to perform significantly better on some of the datasets. This is expected since we use some prior information when computing do-
4.3 Analysis noise level and batch size
Figure 5(a) shows the results for the synthetic dataset when varying the noise level 7. For each noise level, we keep the batch size fixed at B [[E0000 The y-axis corresponds to the area under the curve (AUC) the active learning plot w.r.t. the respective performance metric (i.c., ARI). This metric is used summarize the overall performance of query strategy by single number (instead of the full active learning plots shown in the previous figures). We observe that our methods are very robust to the noise level, whereas the baselines perform well only for zero noise, but very poorly even with small amount of noise. In particular, we see that maxexp is more robust to varions noise levels, and maxmin is consistently the second best choice.
Finally, Figure 5(b) shows the results for the synthetic dataset when varying the batch size B. For each batch size keep the noise level fixed at y 0.2. The best performing methods are again maxexp and maxmin, where their performance degrades only slowly and frequency perform similarly for different batch sizes even with small values, where both significantly under perform compared to maxexp and maxmin, indicating that looking at the query frequency the absolute weight of an edge might not be sufficient. This was already hinted at in Section 3.1, and the reason is that they discard the correlation between edges. order to make the froquency and uncortainty uscful, one needs to combine them with more sophisticated methods that take such correlations into account. This is essentially what maxmin and maxexp do.
increase the batch size. We also that uncertainty
4.4 Runtime investigation for maxmin and maxexp
Algorithm 3 introduces an efficient implementation of maxmin and maxexp. The key step is line 3 of this algorithm, where sample random subset. Epaad from the set Eyiolates, In this section, we analyze how
19

---

Published in Transactions on Machine Learning Research (02/2024)
the size of this subset impacts performance and runtime of the active clustering procedure the synthetic dataset. The noise level is set to 0.4 for all experiments in this section. Let & be number in [0, 1]. Then, let the size of E be [ x EEgiolates, J. Note that Ç = means we use E = Exiolates, which implies that all bad triangles are considered. Also, ç = mcans no bad triangles are considered, which renders maxmin and maxexp equivalent to uniform selection.
In Figure 6, we investigate the performance and runtime of the maxexp query strategy for different values of &, in comparison to QECC. Figure 6(a) shows the ARI at each iteration of the active clustering procedure. Figure 6(b) shows the runtime of the query strategy (in seconds) of each iteration. Figure 6(c) shows the number of violations, i.c., EEiiolates, at each iteration. Figure illustrates similar results for the maxmin query strategy.
For both maxexp and maxmin, we observe that even very small values of & result in very good performance. In fact, smaller values of { may even perform better than larger values (in particular for maxmin), due to improved exploration
hinted in Section 3.5. Furthermore, we that smaller values of & result in significant improvement in the runtime. Setting & 0.05 can be seen to perform well for both maxmin and maxexp, while also being comparable with QECC in terms of runtime.
These results also provide insights about the difference between maxmin and maxexp. For example, we see that the number of violations approaches zero for maxexp as the active clustering procedure progresses. Maxmin, on the other hand, does not detect and fix the inconsistencies as effectively. However, maxmin converges perfect ARI score slightly faster for this dataset, which indicates that putting too much focus correcting inconsistencces is not necessarily the best route. Tn fact, sclection), the ARI still reaches ARI score of 1, despite having very large number of violations. The conclusion is that while resolving inconsistency in the queried pairwise relations (which maxmin and maxexp aim to do) helps the performance, fixing all of them may not be necessary for optimal performance. This will be investigated in detail in future work.
that with & = 0 (i.e., uniform
1.0
0.0
20000
0.005
E 0.06
E 0.0
{ 0.05
0.005
Time (s]
40
50
E
E
E 0.6
Num. violations
15000
g=
E 0.2
QECC
10000
0.8
1.0
0.2
QECC
10
5000
0
-10
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.8
0.0
0.2
0.4
0.6
Proportion edges queried
Proportion of edges queried
Proportion of edges queried
(b)
(c)
Figure 6: Performance and runtime of the maxexp query strategy for different values of &, in comparison to QECC.
5 Conclusion
In this paper, we developed a generic framework for active learning for correlation clustering where queries for pairwise similarities can be any positive or negative real number. It provides robustness and flexibility w.r.t. the type of fcodback provided by user or an annotator. We then proposod a number of novel query strategies suited well to our framework, where maxmin and maxexp yield superior results various experimental studies.
20

---

Published in Transactions on Machine Learning Research (02/2024)
35
E 0.0
0.0.
0.005
= 0.005
20000
E 0.005
0.8
0.05
E 0.05
0
E 0.2
0.2
Num. vialallons
15000
& 0.8
0.6
Time (8)
E 1.0
= 1.0
QEGC
15
QECC
10000
10
5000
0.0
0
0.0
0.2
0.4
0.6
0.0
0.6
0.0
0.2
0.4
Proportion of edges querled
Proportion of edges queried
Proportion of edges queried
(b)
(c)
Figure 7: Performance and runtime of the maxmin query strategy for different values of &, in comparison to QECC.
Acknowledgments
This work partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. The computations and data handling were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS) and the Swedish National Infrastructure for Computing (SNIC) at Chalmers Contre for Computa- tional Science and Engineering (C3SE), High Performance Computing Center North (HPC2N) and Uppsala Multidiscipliaayy Center for Advanced Computational Science (UPPMAX) partially funded by the Swedish Research Council through grant agreements no. 2022-06725 and no. 2018-05973.
References
Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5):23:1 23:27, 2008. doi: 011145/141150.1411111
Nir Ailon, Anup Bhattacharya, and Ragesh Jaiswal. Approximate correlation clustering using same-cluster queries. In Michael A. Bender, Martín Farach-Colton and Miguel A. Mosteiro (eds.), LATIN 2018: Theoretical Informatics, pp. 14-27, Cham, 2018. Springer International Publishing. ISBN 978-3-319- 77404-6.
Alan Akbik, Duncan Blythe, and Roland Vollgraf. Contextual string embeddings for sequence labeling. In COLING 2018, 27th International Conference on Computational Linguistics, pp. 1638-1649, 2018.
Pranjal Awasthi and Reza Bosagh Zadeh. Supervised clustering. In Advances in Neural Information Pro- cessing Systems (NTPS), pp. 91 91-99, 2010.
Pranjal Awasthi, Maria Florina Balcan, and Konstantin Voevodski. Local algorithms for interactive cluster- ing. Journal of Machine Learning Research, 18(3):133) 35, 2017.
Maria-Flowe Frorina Balcan and Avrim Blum. Clustering with interactive feedback. In Yoav Freund, László Györfi, György Turán, and Thomas Zeugmann (eds.), ), Algorithmic Learning Theory, pp. 316-30 166-328, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. ISBN 978-3-540-87987-9.
Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering, Machine Learning, 56(1-3):89 113, 2004. doi: 10.1023 BBMAACH.000000311..61111
Sugato Basu, Arindam Banerjee, and Raymond Mooney, Active semi-supervision for pairwise constrained clustering. In SDM, 2004.
21

---

Published in Transactions on Machine Learning Research (02/2024)
Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Antti Ukkonen. Chromatic correlation clustering. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '12, pp. 1321 1329, 2012. doi: 022145/233953.22339977 URL https://doi.org/bt
1145/2839530 2339735.
Francesco Bonchi, David Garcia-Soriano, and Konstantin Kutzkov, Local correlation clustering, 2013a.
Francesco Bonchi, Aristides Gionis, and Antti Ukkonen. Overlapping correlation clustering. Knowl. Inf. Sysh. 35(1):1-35 32, 2013b. doi: 00.100//10111-001222
Francesco Bonchi, David García-Soriano, and Edo Liberty. Correlation clustering: from theory practice. Tn The 20th ACM STGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, pp. 1972. ACM, 2014. doi: 01055//62333002666
Marco Bressan, Nicolò Cesa-Bianchi, Andrea Paudice, and Fabio Vitale. Correlation clustering with adaptive similarity queries. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.); Adeances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Mark Bun, Marek Flias, and Janardhan Kulkarni. Differentially private correlation clustering. In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139, pp. 1966-116,, 2021.
Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. J. Comput. Syst. Sci., 71(3):360 383, 2005. doi: 200016//..sss.204410...
Morteza Haghir Chchreghani. Information-theoret validation of clustering algorithms. PhD thesis, 2013.
Morteza Haghir Chehreghani. Shift of pairwise similarities for data clustering. Machine Learning, 2022.
Morteza Haghir Chehreghani and Mostafa Haghir Chehreghani. Learning reprosentations from dendrograms. Mach. Learn., 109(9-10)11779 1802, 2020. doi: 10. 10.10077/100991--00--665---3-
Erik D. Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Theor. Compul. Sei., 361 361 (2-3):1772-11) 2006. doi: 10.1016/j.tss.2006.00 .5.008.
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and normalized cuts. In Won Kim, Ron Kohavi, Johannes Gehrke, and William DuMouchel (eds.), Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 551 556. ACM, 2004.
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. A unified view of kernel k-means, spectral clustering and graph cuts. Technical Report TR-04-25, 2005.
Micha Elsner and Warren Schudy. Bounding and comparing methods for correlation clustering beyond TIP. Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing, pp. 19 27, Boulder, Colorado, June 2009. Association for Computational Linguistics.
Brian Eriksson, Gautam Dasarathy, Aarti Singh, and Rob Nowak. Active clustering: Robust and efficient hierarchical clustering using aveptively selected similarities. In Geolfrey Gordon, David Dunson, and Miroslav Dudík (eds.), Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 260-268, Fort Lauderdale, FL, USA, 11 13 Apr 2011. PMLR.
David García-Soriano, Konstantin Kutzkov, Francesco Bonchi, and Charalampos Tsourakakis. Query- efficient correlation clustering. In Proceedings of The Web Conference 2020, WWW '20, pp. 1668-1478, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450330233. doi:
00.1145/336644233332222
Lise Getoor and Ashwin Machanavajihala. Entity resolution: Theory, practice & open challenges. Proc. VLDB Endow. 5(12):2018 201222001-20099 2012.
22

---

Published in Transactions on Machine Learning Research (02/2024)
Aristides Gionis, Heikki Mannila, and Panayiotis Tsaparas. Clustering aggregation. ACM Trons. Knowl. Discov. Dala, 1(1):4, 2007. doi: D0.1145/1217299)
Toannis Giotis and Venkatesan Guruswami. Correlation clustering with fixed number of clusters. In Pro- ceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithoms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pp. 1167-1176. ACM Press, 2006.
Oktie Hassanzadeh, Fei Chiang, Renée J. Miller, and Hyun Chul Lee. Framework for evaluating clustering algorithms duplicate detection. Proc. VLDB Endow., 2(1):1282 1293, 2009, doi: 10.14778/1687677. 1687771.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition.
CoRR, abs/1512.03385,, 2015.
Sanna Jarl, Linus Aronsson, Sadegh Rahrovani, and Morteza Haghir Chehreghani. Active learning of driving scenario trajectories. Eng. Appl. Artif. Intell., 113:104972, 2022.
Sungwoong Kim, Sebastian Nowozin, Pushmeet Kohli, and Chang Dong Yoo. Higher-order correlation clustering for image segmentation. In Advances in Neural Information Processing Systems 24 (NTPS), pp. 1530 1538, 2011.
Ramya Korlakai Vinayak and Babak Hassibi. Crowdsourced clustering: Querying edges vs triangles. In D. Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett. (eds.), Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Akshay Krishnamurthy, Sivaraman Balakrishnan, Min Xu, and Aarti Singh. Efficient active algorithms for hierarchical clustering. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML'12 pp. 267-2744 Madison, WI, USA, 2012. Omnipress. ISBN 9781450312851.
Arya Mazumdar and Barna Saha. Query complexity of clustering with side information. In 1. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (ods.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 20.
Arya Mazumdar and Barna Saha. Clustering with noisy queries. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (cds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017b.
Andrew McCallum and Ben Wellner. Conditional models of identity uncertainty with application to noun coreference. In Advances in Neural Information Processing Systems 17 [Neural Information Processing Systems, NIPS, pp. 905-912, 2004.
Anirudh Ramachandran, Nick Feamster, and Santosh Vempala. Filtering spam with behavioral blacklisting. In Proceedings of the 14th ACM Conference on Computer and Communications Security, pp. 342 351, 2007. ISBN 9781595937032. doi: 10.1445/1115245.1115888.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B. Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning. ACM Comput. Sure., 54(9), oct 2021. ISSN 0360-0300. doi: 10.1145/3472291 URL https: //doi org/ 10. 1145/3472291.
Neil Rubens, Mchdi Elahi, Masashi Sugiyama, and Dain Kaplan. Active Learning in Recommender Systems. pp. 809 846. 2015. ISBN 978-1-4899--637-6 doi: 10.1007/978-11448
24.
Barna Saha and Sanjay Subramanian. Correlation Clustering with Same-Cluster Queries Bounded by Op- timal Cost. In Michael A. Bender, Ola Svensson, and Grzegorz Herman (eds.), 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leūbniz International Proceedings in Informatics (LIPIes), pp. 81:1-81:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibing Zentrum fuer Informatik. ISBN 978-3-95977-124-5. doi: To.4Ps3 T..PlcsEESA.2111..... 20..901..1
23

---

Published in Transactions on Machine Learning Research (02/2024)
Zhao Shuyang, Toni Heittola, and Tuomas Virtanen. Active learning for sound event detection. IEEE/ACM Trans. Audio, Speech and Lang. Proc., 28:2895- 2905, nov 2020. ISSN 2329-9290. doi: 10.1109/TASLJ 2020.3029652.
Jonas Soenen, Sebastijan Dumancic, Hendrik Blockeel, Toon Van Craenendonck, F Hutter, K Kersting, J Lijffijt, and I Valera. Tackling noise in active semi-supervised clustering, 2021. ISSN 978-3-030-67661-2.
Jiliang Tang, Yi Chang, Charu Aggarwal, and Huan Liu. survey of signed network mining in social media.
ACM Comput. Surv., 49(3), 2016. doi: 20.114/29561885
Erik Thiel, Morteza Haghir Chehreghani, and Devdatt P. Dubhashi. A non-convex optimization approach to correlation clustering. In The Thirly-Thing Third AAAI Conference on Artificial Intelligence, AAAI, pp. 5159 5166. AAAI Press, 2019. doi: wa..6099aaai.v3iii v331013300111555
Toon Craenendonck, Sebastijan Dumancic, and Hendrik Blockeel. Cobra: A last and simple method for active clustering with pairwise constraints. In International Joint Conference on Artificial Intelligence, 2018a.
Toon Craenendonck, Schastijan Dumancic, Elia Van Wolputte, and Hendrik Blockeel. Cobras: Interac- live clustering with pairwise queries. In International Symposium Intelligenl Dala Analysis, 2018b.
Simon Viet Johansson, Hampus Gummesson Svensson, Esben Bjerrum, Alexander Schliep, Morteza Haghir Chehreghani, Christian Tyrchan, and Ola Engkvist. Using active learning to develop ma- chine learning models for reaction yield prediction. Molecular Informatics, 21(12):2200033, 2022. doi:
https://doi.or/// 10. 10.10...../..m 1ttp:110.1100.m..111 10002/minn.222200043.
Sicheng Xiong, Javad Azimi, and Xiaoli Z. Fern. Active learning of constraints for semi-supervised clustering. IEEE Transactions on Knowledge and Data Engineering. 26(1):43-5) 54, 2014. doi: 10.1109/TKDD.2013222
Songbai Yan, Kamalika Chaudhuri, and Tara Javidi. Active learning with logged data. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pp. 5517-5526, PML.R, 2018.
24

---

Published in Transactions on Machine Learning Research (02/2024)
A Proofs
A.1 Proof of theorem 1
Theorem 1. Given o, let To T
T be the set of triangles t = (u, v w) E with exoctly two positive edge weights and one negative edge weight. Then, the mazmin query strategy corresponds to querying the weight of the edge & selected by
(i, 8) = arg max min (e())..
(10)
LET, LET, eEE.
Proof. Consider triangle t = (u, e, w) E T with pairwise similarities {21, s3} = (a(u, ou, w), du, w)). The clustorings of a triangle {(w), v)}, {(u), (v), (w))}. Given this, Table 1 shows the clustering cost for each clustering in C, for all possible signs of the edge weights $2, 83). From this, we see that only the triangles with two positive edge weights and one negative edge weight have no clustering with clustering cost of O. Thus, the triangles in To are guaranteed to be inconsistent while the minimal clustering cost of all other triangles t E T To is always 0 (i.e., they can yield a consistent clustering).
C. (C',...,c') {(u, e w), {(u), (v, w)}, {(u), (u, w)).
Furthermore, for the triangles t E To we see that the clusterings C³, C and Ca corresponds to only one of the edges (i.e., $3, $1 and 82, respectively) violating the clustering. For the clustering C2 all edges violate the clustering and for C we have that 81 and 82 violate the clustering. This implies that C2 C or Ct will always correspond the clustering with minimal cost, i.c., mincec, (C. = min E, [a(e)] for all E Ta. Thus, for given triangle Ta; we should pick the edge according to arg min.e E. (e(e)]
Finally, among all the triangles t Ta, choose the edge that yields maximal inconsistency, ie., (f, arg maxteT, minegE, [e())-
It should be noted that if To # 0, then Eq. 10 corresponds first selecting the triangle T with the maximal minimum clustering cost, i.e.,
i
arg max min A (C),))(C), EET CEC,
and then selecting an edge from according to
arg min (a(e).
E
This is true since mincec. (C) 2 for all e To while mincec. A (1.,)) (C) for all E T To.
{81, $2, 83)
A (Ct)
A
(t.r)
A (t.z)
3
(t.or
(C*)
A (t.o))
(
{+,
0
81
82
82
83
[8]
82
+
83
181
+
82
+
183
81
82
88
82
52
13
81
+
|s3
+ 82
81
81
82
+
183
83
82
[8]
0
Table 1: Consider a triangle t (u, w) T with pairwise similarities (21,82, 83) (a(u, alu, w).
al,, The clustcrings of triangle t C. (C',..,,C') [(w), (u, v)), {u)), (v), (w))). The first column indicates the sign of the pairwise similarities 82,88288))
{(u, v,w), {(u), (v. w)), {(0), (u, w))
The remaining columns show the clustering cost for each of the clusterings.
25

---

Published in Transactions on Machine Learning Research (02/2024)
A.2 Proof of proposition 1
Proposition 1. Given bad triangle To where $1 and $2 are positive and 83 is negative, We have
E E|A.] = pi |53l + (1s |22| |sal)
(14)
pa|si + |22| + p5(ss (s2))
Proof. Given the clusterings C. it follows directly from the definition of the clustering cost in Eq. in the main text, ie.,
E[A.] = Σ pi (1o)
i=
Σ Pr Σ
(17)
i=1
(a,))EE,
pilssl
P2(111
P2
[82| + (syl) + + Ps([sa] + (82)).
pa|
The last equality can easily be understood from inspecting the row where {si, s2) ++, +, -} in Table
1.
A.3 Proof of proposition 2
Proposition 2. Given bad triangle t To where 81 and s2 positive and s3 is negative. The optimization problems in Eq. 10 and Eq. 13 are equivalent if 3 = 0o, i.e.,
lim E[Ad] = min (o(e).. 80000
Vt e To
(15)
e
Furthermore, have
2 [82| + |8a).
lim B[A.] x |ss| 8
(16)
Proof. Based on Eq. 11 we see that as 8 + oo all probability mass will be put on the clustering(s) with the smallest clustering cost which yields Eq. 15 (from Theorem 1). Furthermore, from Eq. 11 we have that lim p: = for all 1,...,5 which gives
5 A Acinn (a;)
lim [|A 8-50
1=1
(3
3|
+ 22sss))
2
+
|22
+
szl
(18)
3
B More on Maxmin and Maxexp
In this section, further investigate maxmin and maxexp, and then discuss extensions to maxexp.
26

---

Published in Transactions on Machine Learning Research (02/2024)
B.1 Further analysis of maxmin and maxexp
Figure 8 visualizes how maxexp ranks triangles for different values B. We observe that a higher value of I makes the maxexp cost more concentrated around bad triangles with the odge weights f1,1,-13. When 3 < 00, maxexp will still give the highest. cost. to 11,1,-11 (as desired), but the cost for surrounding triangles is assigned in a smoother and more principled manner. Also, while the ranking of good triangles is not relevant in case,
how different values of 3 rank them differently. Additionally, Table 2 illustrates some more subtle differences of maxexp with different values of B. The main takeaway is that when B < 2o, the ranking of various triangles follows more accurately the intuition that triangles that are more confidently inconsistent should be ranked higher (i.e., more likely to be selected).
0z(u, v)
(U, w)
(1(,W)
A
3
E
E
3
1
-1
1.18
1.6
0.8
0.5
-0.5
0.77
0.5
0.98
-0.8
0.5
0.5
0.74
0.5
0.92
1
-0.1
0.71
0.1
1.24
-1
1
0.1
0.69
0.1
1.06
1
1
0.66
0
1.8
0.1
0.1
-0.1
0.15
0.1
0.16
Table 2: The expected cost E[As] of triangle (u, v, w) for different values of B.
1.0
1.00
Te M
-013
(a) B =
(b) 1=1
620
(c) 3=3
(d) = oc (maxxinn)
Figure 8: The expected cost E[A,] of a triangle t = (u, u, w) with different values of B.
27

---

Published in Transactions on Machine Learning Research (02/2024)
B.2 Further extensions of maxexp
One can in principle extend the probabilistic perspective to selecting edges and triangles. We can define the probability of an edge E E, given clustering C' C. as
exp(3B((..c)(e)) ple|C) = EeER, exp(3Riu....o (R.,,
(19)
Then, after selecting triangle t using Eq. 13, first sample clustering from Eq. 11 and then given this sampled clustering, sample an edge from Eq. 19. This may result in improved exploration.
Alternatively, we can define the expected cost of an edge given a triangle t as
B[A, = EC-PIC.) R (c)
Σ B(.c)))
(20)
CEC.
Then, we define the probability of edge given triangle
exp( (4)
p(elt)
(21)
EE cxp BE Ae (t)
An edge can either be selected according
é arg max B[Ae](] [e],
(22)
eE
can sample edge è from p(e]f).
Additionally, we can define the probability of triangle given an edge according to
exp(3E(AA) (.))
p(tle) = EreT, (xp(3E(Ax))
(23)
where T. S T is the set of triangles containing the edge Now we can define informativeness measure of any edge E by
I(e) EICCCP(T..C) (.c.--PT.c.)((ttco(0()) (e))
= EM-P(T.) [ [EC ((..)Baa))
= Σ p(tle) Σ (CCR
(24)
ET.
CEC.
Given this, could select edge to be queried according to
غ = arg max I(e).
(25)
eEE
C
Experiments: Further Results
In this section, we present several additional experimental results. The experimental setting is identical the setting in Section 4.1 unless otherwise specified.
28

---

Published in Transactions on Machine Learning Research (02/2024)
C.1 Results with the adjusted mutual information metric
The results presented in Figures 9-12 identical to the results shown in Figures 1-4 of the main paper; except with the adjusted mutual information (AMI) the performance metric. The overall conclusions are very similar to the results with ARI. The main difference is that the performance of our query strategies seems to be somewhat worse for the datasets with unbalanced clusters (e.g,, the ecoli dataset), as such datasets make the problem harder.
1.0
1.0
1.0
0.8
0.8
AMI
Maxexp
AMI
Maxexo
Maxexp
Masmin
Maxmin
Masmin
0.4
Uncertainly
0.4
Uncertainly
0.4
Uncertainly
Frequency
Frequency
Frequency
Unifom
Uniform
Uniform
0.2
ACOBRAS
0.2
1COBRAS
0.2
RCOBRAS
COBRAS
COBRAS
COBRAS
QECC
GECC
QECC
0.0
0.2
04
0.8
0.0
0.2
0.4
0.5
0.0
0.2
0.4
0.8
Proportion edges queried
Proportion edges queried
Proportion edges queried
(a) 20newsgroups
(b) Cardiotocography
(c) CIFAR1O
1.0
0.6
0.6
Maxexp
M wwe
Maxexp
Maxmin
Maxmin
Maxmin
0.4
Uncertainly
0.4
Uncertainly
0.4
www.
Uncertainty
Frequency
Frequency
Frequency
Uniform
Unifom
Uniform
#CDBRAS
#COBRAS
nCOBRAS
COBRAS
COBRAS
COBRAS
QECC
0.0
QECC
0.0
QECC
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(d) Ecoli
(e) Forest type mapping
(f) MNIST
1.0
0.8
0.8
0.8
0.6
0.8
0.8
AMI
Maxexp
Maxexp
AMI
Maxesp
Maxmin
Maxmin
Uncortainty
Uncortannty
Uncortainty
Frequency
Frequancy
Frequency
Unifom
Uniform
Uniform
0.2
ACOBRAS
0.2
nCOBRAS
0.2
aCOBRAS
COBRAS
COBRAS
COBRAS
0.0
CECC
0.0
QECC
0.3
QECC
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(g) Mushrooms
(h) User knowledge
Yeast.
Figure 9: Results for different datasets with 20% noise (y 0.2) and random initialization of the pairwise similarities. The evaluation metric is the adjusted mutual information (AMT).
29

---

Published in Transactions on Machine Learning Research (02/2024)
1.0
0.8
0.6
0.6
0.6
Maxexp
Maxexa
Maxexp
Maxmin
Maxmin
Maxmin
10.4
Uncertainly
0.4
Uncertainty
0.4
Uncertainly
Frequency
Froquency
Frequency
Unfomm
Uniform
Uniform
nCDBRAS
0.2
ACOBRAS
nCOBRAS
COBRAS
COBRAS
COBRAS
0.0
GECC
0.0
OECC
0.0
OECC
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(a) 20uewsgroups
(b) Cardiotocography
(c) CIPAR10
1.0
0.8
0.8
0.8
0.6
0.8
0.6
Maxcxp
Maxoxp
Maxcxp
AMI
AM
AM
Maxmin
Maxmin
Maxmin
Uncertainty
Uncertainty
Uncertainty
Frequency
Frequency
Frequency
Hadyy Yul
Unifor
Unifom
Uniform
RCDBRAS
0.2
ECOBRAS
0.2
nCDBRAS
COBRAS
COBRAS
COBRAS
0.0
QECC
0.0
GECC
0.0
QECC
0.0
0.2
0.4
0.6
0.0
D.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(d) Ecoli
(e) Forest type mapping
(f) MNIST
1.0
1.0
1.0
0.8
0.8
0.8
0.6
AMI
Maxetop
Maxexp
AMI
Maxexp
Maxmin
Maxmin
Maxmin
0.4
Uncertainly
0.4
Uncertainty
0.4
Uncertainty
Frequency
Frequency
Frequency
Uniform
Uniform
Pww www.praa
Uniform
0.2
ICOBRAS
0.2
RCOBRAS
0.2
nCOBRRS
COBRAS
COBRAS
COBRAS
0.0
GECC
QECC
0.3
OECC
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges queried
Proportion of edges queried
Proportion edges queried
(g) Mushrooms
(h) User knowledge
Yeast
Figure 10: Results for different datasots with 40% noise (> = 0.4) and random initialization of the pairwise similarities. The evaluation metric is the adjusted mutual information (AMI).
C.2 Analysis of the impact of and -
Figure 13 illustrates the results for the synthetic dataset w.r.t. the adjusted rand index where we investigate the impact of different parameters. Each row shows the results for the noise levels y = 0, 0.2, 0.4, respectively. The first column shows the results for all query strategies. The second column shows the results for maxmin and maxexp with 0.0.2, 0.4. The third column shows the results for maxexp with 2, 5, 20, co. The fourth column shows the results for maxexp with B = 0, 0.5, 1, 5, 25, oo.
30

---

Published in Transactions on Machine Learning Research (02/2024)
1.0
0.6
0.6
0.6
Maxexp
Maxexp
Maxmin
Maxmin
Maxmin
10.4
Uncertainly
0.4
Uncertainty
0.4
Uncertainly
Frequency
Froquency
Frequency
Unifom
Uniform
Uniform
nCDBRAS
ACOBRAS
nCOBRAS
COBRAS
COBRAS
COBRAS
GECC
0.0
GECC
0.0
OECC
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(a) 20uewsgroups
(b) Cardiotocography
(c) CIPAR10
0.8
0.8
0.6
0.8
0.6
Maxcxx
Maxexp
Maxcxp
AMI
AM
AM
Maxmin
Uncertainty
Uncertainty
Uncertaitty
Frequency
Frequency
Frequency
Unifom
Unifom
Uniform
rCDBRAS
0.2
ECOBRAS
0.2
nCOBRAS
COBRAS
COBRAS
COBRAS
0.0
QECC
0.0
QECC
0.0
QECC
0.0
0.2
0.4
0.6
0.0
D.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges querled
Proportion of edges queried
Proportion of edges queried
(d) Ecoli
(e) Forest type mapping
(f) MNIST
1.0
1.0
1.0
0.8
0.8
0.8
0.6
AMI
Maxsaop
Maxexp
AMI
Maxexp
Maxmin
Maxmin
Maxmin
0.4
Uncertainty
0.4
Uncertainty
0.4
Uncerteinty
Frequency
Frequency
Frequency
Uniform
Uniform
Uniform
0.2
ICOBRAS
0.2
RCOBRAS
0.2
nCOBRRA
COBRAS
COBRAS
COBRAS
0.0
GECC
QECC
QECC
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges queried
Proportion edges queried
Proportion edges queried
(g) Mushrooms
(h) User knowledge
Yeast
Figure 11: Results for different datasets with 20% noise (y 0.2) and k-mcans initialization of the pairwise similarities. The evaluation metrie the adjusted mutual information (AMI).
From these figures, conclude consistent results with the previous results. In particular, observe that for all datascts the performance of maxexp remains the same for various values of r 2 1 when 0 (scc, c.g., Figure 13(c)). This makes sense since with zero noise one gains no extra information from querying the same edge more than once, which maxexp (and maxmin) accurately detect. However, for 7 = 0.2, we see (in, e.g., Figure 13(g)) that maxexp performs worse when 7 < This confirms that maxexp (and maxmin) benefit from querying the same edge more than once when the oracle is noisy. Finally, when ? 0.4, the noise is high such that maxexp will query the same edges more than what should be, leading to exploration issues.
31

---

Published in Transactions on Machine Learning Research (02/2024)
1.0
0.6
0.6
0.6
Maxexp
Maxexp
Maxmin
Maxmin
Maxmin
10.4
Uncertainly
0.4
Uncertainty
0.4
Uncertainly
Frequency
Froquency
Frequency
Unifom
Uniform
Uniform
nCDBRAS
nCOBRAS
nCOBRAS
COBRAS
COBRAS
COBRAS
GECC
0.0
OECC
0.0
OECC
Proportion of edges queried
Proportion of edges queried
Proportion of edges queried
(a) 20uewsgroups
(b) Cardiotocography
(c) CIPAR10
0.8
0.8
0.6
0.8
0.6
AMI
Maxexp
AM
Maxoxp
AM
Maxcxp
Maxmin
Maxmin
Uncertainty
Uncertainty
Uncertainty
Frequency
Frequency
Frequency
Unitom
Unifom
Uniform
RCDBRAS
0.2
#COBRAS
0.2
nCOBRAS
COBRAS
COBRAS
COBRAS
0.0
QECC
0.0
GECC
0.0
QECC
0.0
0.2
0.4
0.6
0.0
D.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges querled
Proportion of edges queried
Proportion of edges queried
(d) Ecoli
(e) Forest type mapping
(f) MNIST
1.0
1.0
1.0
0.8
0.8
0.8
0.6
AMI
Manstop
Maxeep
AMI
Maxexp
Maxmin
Maxmin
Maxmin
0.4
Uncertainty
0.4
Uncertainty
0.4
Uncerteinty
Frequency
Frequency
Frequency
Uniform
Uniform
Uniform
0.2
ICOBRAS
0.2
RCOBRAS
0.2
nCOBRRS
COBRAS
COBRAS
COBRAS
GECC
QECC
OECC
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Proportion of edges queried
Proportion edges queried
Proportion edges queried
(g) Mushrooms
(h) User knowledge
Yeast
Figure 12: Results for different datasets with 40% noise (y 0.4) and k-mcans initialization of the pairwise similarities. The evaluation metrie the adjusted mutual information (AMI).
This can be observed in, e.g., Figure 13(k) where the performance gets worse when 7 = xo while the best performance is obtained with r 20. Thus, for higher noise levels one cannot simply set T = oo and should limit its value.
From the experiments with different values of B, we observe that wide range of values for / are acceptable. However, as B + the performance seems to degrade, which in this case maxexp converges to maxmin according to Proposition 2.
32

---

Published in Transactions on Machine Learning Research (02/2024)
Adjused Bcore
N0 aged Roadd Soors
0.9
Adueted Kand Score
0.9
0.9
0.8
0.8
Nakmin
0.0
0.8
Maxeq: (3- Q)
Uncorla Frequency
Rancom
Nasmi 15 0..2)
Noomin -0.4) 4)
Maxexp (T 21
Mexwap
07
Maxeup () 0.5)
Maxeqp (9-1)
0.8
0.6
Kiowep [1 m0
0.8
Maxopp (T-
0.5
( =5)
Mesmin
Nexcxp - 0.23
Maxeip 20
Mowp (# - 25)
0.5
12
0.6
0.6
0.5
500
1000
1990
2000
500
1000
1600
2002
500
1000
500
1000
1900
2000
Number of quarriss
Namber of queeias
Number of quariss
Number of quaariii
(a) 7 ==
(b) 7 =0
(c) 7 =0 0
(d) 7 =
1.0
1.0
0.9
Adusted Roand Sooe
Aduuted sand Soore
0.0
0.9
0.8
Maxmin
Aluttd Rand
0.5
Maxeup 29- 0)
Aduuted
Random Unce my Frequeney
07
Masmin (0.4.)
Masmin (0.0.))
Mexwop (1-21 21
Mansip (1=
Stecepp 2 6.5)
Maxsey
0.8
0.0
Maxeup Ir 0)
0.0
Maxerp
0.8
Mecnep /0 5)
Maarin
Masnep = 02)
Maxeip = 201
Macnep [ 251
0.5
0.
0.8
0.5
1000
2000
3020
500
1200 Number of quirrics
1500
2000
1000
2000
3000
500
1020
1630
2030
Number of quaries
Number of quarics
Number of quofiess
(e) 7 0.2
(f) Y = 0.2
(g) 7 0.2
(h) Y 0.2
1.0
Adjubb Pand Score
0.9
Adjuaed Rand Score
0.9
0.9
Adjateed Rand Scote
0.9
0.5
Moxmin (c- 0)
80luttdd Rand
Mecwep (T-1) 1;
Macsep (8-
Maxmin 0.2)
Maxoopp (T 2)
Maxesp (850.
0.7
Uncortality Frequency
Menmin (2- 0.4)
0.7
Maxeep (T- 3)
Macwep (8- 5)
0.8
0.6
Maseop 0)
0.8
Massup
5.5
Nassa; [9- 5)
Meernn
Meswep (/-00 0.7]
Maxcce (T 20)
Maceap ( 25)
Maserp 0
Maxcrp
0.8
Maxiigg
1000
2000
2000
4500
0
1000
2000
2020
1000
2000
2000
4000
1000
2000
X0C
Number quaries
Number of queries
Number queries
Number of querress
(i) 7 = 0.4
(i) 0.4
(lk 7 0.4
(1) 7 = 0.4
Figure 13: Results for the synthetic dataset in different settings w.r.t. adjusted rand index (ARI). In these experiments, we investigate the impact of different parameters and demonstrate that the results are consistent among different choices of parameters.
C.3 Analysis of the performance on the MNIST dataset
Figure 14 provides some additional insights into the active clustering procodure applicd to the MNIST dataset (with the maxexp query strategy). It shows the computed clusters and the distribution of the true clusters (digits) into these clusters at 11 different iterations. We observe that the quality of the clustering improves as more pairwise relations are queried. It is known that separating digits 1 and 7 tends to be difficult for the MNIST dataset, since they look similar in feature space. However, we see that the procedure does not struggle with any of such cases. The reason for this is that we do not consider the feature vectors, thereby any ambiguity that may exist in the feature space does not affect the performance of our procedure. This shows one benefit of not considering the feature vectors, they may degrade performance due to the mismatch with the true clustering. Another benefit of not relying on feature vectors is that for certain applications, one may not even have access to features at all, because acquiring them can be costly.
33

---

Published in Transactions on Machine Learning Research (02/2024)
Hortop
200
22.5
20.0
121
2.-
"rue Lebels
770 Labbal
25
12.5
20
10.0
15
12
10
5
2
6
8 10 14222446662 14222222222
dom of Edges Queried
Clusters
Clusters
Iteration.
Iteration
60
10
30
30
60
40
True Labels
40
Truo Labais
True
30
20
10
10
Clusters
Clusters
Clusters
Iteration: 100
Ieertion: 125
Itaration: 150
80
90
60
True Labels
True Labels
50
True Labels
60
40
6
40
20
20
14
16 18
14
18 22
Iteration: 200
Ieeraion: 300
Iteration: 360
100
100
80
True Labels
True Labels
True Labals
60
50
60
20
20
20
0
1
2
3
4
5
6
8
Clusters
Clusters
Clusters
(a)
Figure 14: Performance of the active clustering procedure on the MNIST dataset (with the maxexp query strategy). The clusters found and the distribution of the true labels (digits) into these clusters at 11 different iterations are shown.
34


Reviews:
[{"review_id": "NT1BRC01b6", "reviewer": "Reviewer_L3E6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The proposal is of interest, it is well written and has a convincing experimental section that shows a clear advantage of the proposed method.  \nThe empirical results demonstrate a clear advantage w.r.t. other approaches, however the setup is such (i.e. no access to the features of the instances but only to their correlations) that the effective number of pairwise similarities that one needs to query is still large in practice (10-30% of all the pairwise similarities in a given dataset). One wonders if by relaxing some assumption greater efficiencies could be obtained (see next part).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors investigate the problem of correlation clustering and propose a framework to allow active learning under arbitrary correlation clustering algorithms and query strategies. In addition they allow information to be affected by noise and propose to constantly re-estimate the correlation information in an efficient way.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are two additional experimental conditions that would perhaps be of interest to analyse:\n\n1. in the Experimental Setup section at page 13, the authors describe their initialisation procedure which consists in estimating an initial clustering partition and then setting $\\sigma_0$ with +0.1 if two instances are in the same cluster and -0.1 otherwise; however it would be of interest to analyse the performance efficiency when some notion of confidence is allowed, i.e. when a noisy correlation score can be used in the initialisation phase; it is conceivable that users can in fact express an informed opinion on their beliefs. A correct estimate of the correlations/scores should significantly improve the efficiency of the queries and it would be interesting to devise an experimental setup that could show much better efficiencies in this conditions.  \n\n2. the initial pairs in $\\sigma_0$ are chosen at random. What would happen if instead one could assume some other (more informative) strategy? For example starting from a (noisy) minimum spanning tree? What one should be able to see is that the exploitation of transitivity should be able to yield far greater efficiency than having to query 10-30% of all possible $n^2$ pairs of scores.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "T0SrrEqt4Z", "reviewer": "Reviewer_xX2D", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- An algorithm of active correlation clustering is carefully designed and analyzed. Related work is well discussed.\n- Various types of queries have been considered and their effectiveness has been empirically examined, which can be valuable findings for TMLR's audience.\n- Empirical performance of the proposed query strategies, in particular **maxmin** and **maxexp**, is promising.\n\n**Weaknesses**\n- Although the paper assumes that each query can be noisy; the oracle may return a false answer with probability $1 - \\gamma$, this setting is not explicitly considered in the formulation of the proposed method. Moreover, the cost of each query is not considered at all in the formulation, although it is said as \"must be queried in a cost-efficient way\" in Abstract. Thus, a naïve approach where one makes the same query many times and taking the mode of them, would perfectly work if $\\gamma$ is not too small. Thus investigation of the robustness of the proposed method to the noisy oracles is not sufficient. \n- Although the computational complexity of the proposed approaches has been analyzed, which itself is a good contribution, the actual running time can vary due to the techniques implemented in the proposal. Therefore it is important to examine and compare the actual running time of proposed query strategies.\n- About the time complexity of **maxmin** and **maxexp**, although I understand that it can be efficiently computed in practice using the proposed approach, the worst case still remains to be cubic w.r.t. $N$, and it finally reduces to be quadratic w.r.t. $N$ by random sampling for $\\mathbf{E}_{i}^{\\text{violates}}$. I think random sampling could affect the resulting performance, hence **maxmin** and **maxexp** without random sampling should be empirically compared.\n- Presentation should be improved (please see the requested changes below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers correlation clustering, where active learning is used to incorporate the setting in which the information about pairwise similarities is given via queries to the oracle. The authors address four limitations of the current approaches: (1) using continuous pairwise similarities instead of binary pairwise similarities, (2) constructing a generic approach, (3) taking noisy oracles into account, and (4) automatically selecting the number of clusters. Empirical evaluation shows superior performance compared to existing active correlation-based or distance-based clustering methods in particular if the proportion of queried pairs is small.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address all the weakness issues listed above.\nIn addition, I have the following issues:\n\n- The last sentence in Section 2.2 and the first sentence in Section 3.3 are almost the same. One of them should be removed.\n- In Eq.(7), since γ has been already used as the noise level, this γ should be replaced with another greek letter.\n- The authors say \"the oracle by setting σi+1(u,v) equal to the average of all queries made for the edge (u,v) so far\", while I think taking the mode instead of the average could be also effective. Is such an approach considered?", "broader_impact_concerns": "I do not have any concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IF7oDwXRBP", "reviewer": "Reviewer_9mYY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written.\n2. The approach is well-grounded in theoretical concepts like the transitivity of similarities, clustering cost and adaptive number of clusters for correlation clustering.\n3. The approach is extensively evaluated on various datasets and in comparison with SOTA approaches to active correlation clustering.\n\nWeaknesses:\n1. Querying similarities of data points in triangle relationships can be quite expensive, and although the authors employ a smart/efficient querying strategy, an efficiency comparison on different datasets and with different SOTA approaches might give further insights on the practical scalability of the approach.\n2. Along similar lines, it is unclear how the approach would behave in realistic dynamic scenarios, where data may change over time or new data points have to be considered.\n3. Qualitative experiments, e.g., on datasets like MNIST (for example, similar digits such as 1,7, should be grouped into the same cluster), could further improve the presentation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose a novel active learning approach to correlation clustering. Different strategies for querying similarities between data points are considered. The most effective strategy queries the similarities between nodes that are in a \"confidently inconsistent\" ternary (i.e., triangle) similarity relationship  (e.g., two nodes are close/similar to a third node but dissimilar to each other). Experiments on various datasets and in comparison with SOTA approaches demonstrate the effectiveness of the proposed active clustering technique.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please go carefully through the text, as there are some inconsistencies, e.g., on Page 7 \"where the first term (i.e., γ) is independent of u and only the second term γ depends on u.\".\n2. An efficiency and scalability evaluation would considerably improve the work.\n3. Are there other, maybe more principled ways to define \"confident inconsistency\"? A discussion might be insightful and better motivate your approach.", "broader_impact_concerns": "--", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers recommended acceptance. During the discussion period, several concerns were raised including relaxing the setup of having no access to the features of the instance, providing more in-depth investigation of the robustness of the proposed framework to the noisy oracles, and providing running time of the proposed query strategies. The revised manuscript adequately addresses these concerns. It's worth noting that the paper focuses on pool-based active learning rather than stream-based active learning, where new data arrives over time, potentially altering its distribution.
Decision: Accept (poster)