Information-Theoretic Active Correlation Clustering

## Abstract

Abstract We study correlation clustering where the pairwise similarities are not known in advance. For this purpose, we employ active learning to query pairwise similarities in a cost-efficient way. We propose a number of effective information-theoretic acquisition functions based on entropy and information gain. We extensively investigate the performance of our methods in different settings and demonstrate their superior performance compared to the alternatives.

## 1 Introduction

Clustering is an important unsupervised learning problem for which several methods have been proposed in different contexts.
*Correlation clustering* (CC) (Bansal et al., ; Demaine et al., ) is a well-known clustering problem, especially beneficial when both similarity and dissimilarity assessments exist for a given set of $N$ objects. Consequently, CC studies the clustering of objects where pairwise similarities can manifest as positive or negative numbers.
It has found a wide range of applications including image segmentation (Kim et al., ), bioinformatics (Bonchi et al., ), spam filtering (Ramachandran et al., ; Bonchi et al., ), social network analysis (Bonchi et al., ; Tang et al., ), duplicate detection (Hassanzadeh et al., ), co-reference identification (McCallum and Wellner, ), entity resolution (Getoor and Machanavajjhala, ), color naming across languages (Thiel et al., ), clustering aggregation (Gionis et al., ; Chehreghani and Chehreghani, ) and spatiotemporal trajectory analysis (Bonchi et al., ).

CC was initially explored using binary pairwise similarities in $\{-1,+1\}$ (Bansal et al., ), and was later extended to support arbitrary positive and negative pairwise similarities in $\mathbb{R}$ (Charikar et al., ; Demaine et al., ). Finding the optimal solution for CC is known to be NP-hard and APX-hard (Bansal et al., ; Demaine et al., ), presenting significant challenges. As a result, various approximate algorithms have been developed to address this problem (Bansal et al., ; Charikar et al., ; Demaine et al., ; Giotis and Guruswami, ; Ailon et al., ; Elsner and Schudy, ). Among these, methods based on local search are noted for their superior performance in terms of clustering quality and computational efficiency (Thiel et al., ; Chehreghani, ).

Existing methods generally assume that all $N\choose 2$ pairwise similarities are available beforehand. However, as discussed in (Bressan et al., ; García-Soriano et al., ), generating pairwise similarities can be computationally intensive and may need to be obtained through resource-intensive queries, e.g., from a human expert. For instance, determining interactions between biological entities often requires the expertise of highly trained professionals, consuming both time and valuable resources (García-Soriano et al., ). In tasks like entity resolution, obtaining pairwise similarity queries through crowd-sourcing could also involve monetary costs. Therefore, a central question emerges: *How can we design a machine learning paradigm that effectively delivers satisfactory CC results with a limited number of queries for pairwise similarities between objects?*

In machine learning, *active learning* is generally employed to address such a question. Its objective is to acquire the most informative data within a constrained budget.
Active learning has proven effective in various tasks, including recommender systems (Rubens et al., ), sound event detection (Shuyang et al., ), analysis of driving time series (Jarl et al., ), drug discovery (Viet Johansson et al., ), and analysis of logged data (Yan et al., ). In the context of active learning, the selection of which data to query is guided by an *acquisition function*. Active learning is most commonly studied for classification and regression problems (Settles, ). However, it has also been studied for clustering and is sometimes referred to as *supervised clustering* (Awasthi and Zadeh, ). The objective is to discover the ground-truth clustering with a minimal number of queries to an *oracle* (e.g., a human expert).
In this scenario, queries are typically executed in one of two ways: (i) By asking whether two clusters should merge or if one cluster should be divided into multiple clusters (Balcan and Blum, ; Awasthi and Zadeh, ; Awasthi et al., ); (ii) By querying the pairwise relations between objects (Basu et al., ; Eriksson et al., ; Krishnamurthy et al., ; Bonchi et al., ; Korlakai Vinayak and Hassibi, ; Ailon et al., ; Mazumdar and Saha, , ; Saha and Subramanian, ; Bressan et al., ; García-Soriano et al., ; van Craenendonck et al., ; Soenen et al., ; Silwal et al., ; Aronsson and Chehreghani, ).

Among the aforementioned works on active learning for clustering, only (Mazumdar and Saha, ; Bressan et al., ; García-Soriano et al., ; Aronsson and Chehreghani, ) consider the setting that we are interested in: (i) The clustering algorithm is based on CC; (ii) The pairwise similarities are not assumed to be known in advance; (iii) We assume access to a single noisy oracle, which can be queried for pairwise similarities; (iv) Access to feature vectors is not assumed by the algorithm, meaning that information about the ground-truth clustering is solely obtained through querying the oracle for pairwise similarities (see Section 2.2 for details). Throughout the paper, this setting will be referred to as *active correlation clustering*.

The work in (Mazumdar and Saha, ) develops a number of *pivot-based* CC algorithms that satisfy 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 which is unrealistic). The work in (Bressan et al., ; García-Soriano et al., ) proposes adaptive and query-efficient versions of the simple pivot-based CC algorithm KwickCluster (Ailon et al., ). However, as demonstrated in detail in (Aronsson and Chehreghani, ), such pivot-based methods perform very poorly for active correlation clustering with noise. The work in (Aronsson and Chehreghani, ) proposes a generic active correlation clustering framework that overcomes the limitations of (Mazumdar and Saha, ; Bressan et al., ; García-Soriano et al., ) and offers several advantages: (i) The pairwise similarities can be any positive or negative real number, even allowing for inconsistencies (i.e., violation of transitivity). This allows the oracle to express uncertainty in their feedback; (ii) The process of querying pairwise similarities is decoupled from the clustering algorithm, enhancing flexibility in constructing acquisition functions that can be employed in conjunction with *any* CC algorithm. (Aronsson and Chehreghani, ) employs an efficient CC algorithm based on local search, whose effectiveness (and superiority over pivot-based methods) has also been demonstrated in the standard CC setting (Thiel et al., ; Chehreghani, ), and dynamically computes the number of clusters; (iii) The framework is robust w.r.t. a noisy oracle and supports multiple queries for the same pairwise similarity if needed (to deal with noise).

Furthermore, (Aronsson and Chehreghani, ) proposes two novel acquisition functions, namely *maxmin* and *maxexp*, to be used within their framework. They demonstrate that the algorithm QECC from (García-Soriano et al., ) performs poorly in the presence of even a very small amount of noise and is significantly outperformed by their methods. In this paper, we adopt the generic active CC framework in (Aronsson and Chehreghani, ) with a focus on the development of more effective acquisition functions. The contributions of this paper are the following:

- •
We investigate the use of information-theoretic acquisition functions based on *entropy* and *information gain* for active CC. We propose four different acquisition functions inspired by this (see Section 3). Information-theoretic acquisition functions have been extensively investigated in prior research on active learning (Roy and McCallum, ; Kirsch and Gal, ), but these studies primarily focus on (active) *supervised learning* scenarios, where the goal is to query data labels from the oracle instead of pairwise relations. *To our knowledge, our work is the first attempt that extends the information-theoretic acquisition functions to active learning with pairwise relations, as well as to non-parametric models such as CC.* Thus, the methods proposed in this paper can be employed beyond active CC, i.e., for active learning of many other pairwise (non-parametric) clustering models.
- •
We conduct extensive experimental studies on various datasets that demonstrate the superior performance of our acquisition functions compared to maxmin and maxexp (and other baselines), and investigate a number of interesting insights about the active CC framework from (Aronsson and Chehreghani, ) (see Section 4 and Appendix C).

## 2 Active Correlation Clustering

In this section, we begin by introducing the problem of active CC. After this, we describe the active clustering procedure used to solve this problem.

### 2.1 Problem Formulation

We are given a set of $N$ objects (data points) indexed by $\mathcal{V}=\{1,\ldots,N\}$. The set of pairs of objects in $\mathcal{V}$ is denoted by $\mathcal{E}=\{(u,v)\;|\;u,v\in\mathcal{V}\}$. We assume the existence of a ground-truth similarity matrix ${\bm{S}}^{\ast}\in\mathbb{R}^{N\times N}$, which represents the true pairwise similarities between every pair $(u,v)\in\mathcal{E}$. However, ${\bm{S}}^{\ast}$ is not known beforehand. Instead, one can only query the oracle for a noisy version of this matrix for a desired pair of objects, while incurring some cost. We use ${\bm{S}}\in\mathbb{R}^{N\times N}$ to represent an estimate of the pairwise similarities. If ${S}_{uv}={S}^{\ast}_{uv}$ for all $(u,v)\in\mathcal{E}$ we have a perfect estimate of the true pairwise similarities, which we assume is unrealistic in practice. Hence, the objective is to discover the ground-truth clustering solution with a minimal number of (active) queries for the pairwise similarities to the oracle, since each query incurs some cost. A similarity matrix ${\bm{S}}$ is symmetric, and we assume zeros on the diagonal, i.e., ${S}_{uv}={S}_{vu}$ and ${S}_{uu}=0$. This means there are ${N\choose 2}=(N\times(N-1))/2$ unique pairwise similarities to estimate. Without loss of generality, we assume all similarities are in the range $[-1,+1]$. In this case, $+1$ and $-1$ respectively indicate definite similarity and dissimilarity. Thus, a similarity close to 0 0 indicates a lack of knowledge about the relation between the two objects. This allows the oracle to express uncertainty in their feedback.

A clustering is a partition of $\mathcal{V}$. In this paper, we encode a clustering with $K$ clusters as a clustering solution ${\bm{c}}\in\mathbb{K}^{N}$ where $\mathbb{K}=\{1,\ldots,K\}$ and $c_{u}\in\mathbb{K}$ denotes the cluster label of object $u\in\mathcal{V}$. We denote by $\mathcal{C}$ the set of clustering solutions for all possible partitions (clusterings) of $\mathcal{V}$.
Given a clustering solution ${\bm{c}}\in\mathcal{C}$, let $V:\mathcal{E}\rightarrow\mathbb{R}^{+}$ be a function representing cluster violations. Specifically, $V(u,v\mid{\bm{S}},{\bm{c}})$ is defined as $|{S}_{uv}|$ if $c_{u}=c_{v}$ and ${S}_{uv}<0$ or if $c_{u}\neq c_{v}$ and ${S}_{uv}\geq 0$, and zero otherwise. Given this, the CC cost function $R:\mathcal{C}\rightarrow\mathbb{R}^{+}$ aims to penalize the sum of violations and is defined as

$$ $R({\bm{c}}\mid{\bm{S}})\triangleq\sum_{(u,v)\in\mathcal{E}}V(u,v\mid{\bm{S}},{ \bm{c}}).$ (1) $$

###### Proposition 2.1 .

The CC cost function in Eq. 1 can be simplified to $R({\bm{c}}\mid{\bm{S}})=-\sum_{\begin{subarray}{c}(u,v)\in\mathcal{E}\\
c_{u}=c_{v}\end{subarray}}{S}_{uv}+\text{constant}$, where the constant is independent of different clustering solutions (Chehreghani, , ). Thus, if we define the max correlation cost function $\Delta({\bm{c}}\mid{\bm{S}})\triangleq-\sum_{\begin{subarray}{c}(u,v)\in
\mathcal{E}\\
c_{u}=c_{v}\end{subarray}}{S}_{uv}$, we have $\operatorname*{arg\,min}_{{\bm{c}}\in\mathcal{C}}\;R({\bm{c}}\mid{\bm{S}})=
\operatorname*{arg\,min}_{{\bm{c}}\in\mathcal{C}}\;\Delta({\bm{c}}\mid{\bm{S}})$.

The proofs of all propositions can be found in Appendix A. Based on Proposition 2.1, we will use the max correlation cost function $\Delta$ throughout most of the paper, as it leads to a number of simplifications in the algorithms that will be derived. The conditioning on ${\bm{S}}$ for $R$ and $\Delta$ will often be dropped, unless it is not clear from context. Finally, the goal is to recover the ground-truth clustering solution ${\bm{c}}^{\ast}=\operatorname*{arg\,min}_{{\bm{c}}\in\mathcal{C}}\;\Delta({\bm
{c}}\mid{\bm{S}}^{\ast})$ with a minimal number of queries to the oracle.

###### Proposition 2.1 .

### 2.2 Active Correlation Clustering Procedure

In this paper, we adopt the recent generic active CC procedure outlined in (Aronsson and Chehreghani, ). The procedure is shown in Alg. 1. It takes an initial similarity matrix ${\bm{S}}^{0}$ as input, which can contain partial or no information about ${\bm{S}}^{\ast}$, depending on the initialization method. While feature vectors are never used explicitly by Alg. 1, we note that information from feature vectors may still be used implicitly through the initialization of ${\bm{S}}^{0}$. However, not relying on feature vectors comes with a number of benefits in practice: (i) We avoid possible noise/ambiguity that may exist in feature space, enabling easier discovery of the ground-truth clustering; (ii) In many applications, obtaining feature vectors can be costly. In the literature, this problem is addressed by *active feature acquisition* (Bilgic and Getoor, ; Horvitz, ), where features are actively queried in a cost-efficient way. The procedure then follows a number of iterations, where each iteration $i$ consists of four steps: (i) Obtain the current clustering solution ${\bm{c}}^{i}\in\mathcal{C}$ by running a CC algorithm given the current similarity matrix ${\bm{S}}^{i}$. In this paper, we use the CC algorithm introduced in (Aronsson and Chehreghani, ), which we have described in Appendix D. This algorithm uses Proposition 2.1 in order to derive an efficient local search method which dynamically determines the number of clusters and is highly robust to noise in ${\bm{S}}^{i}$; (ii) Select a batch $\mathcal{B}\subseteq\mathcal{E}$ of pairs of size $B=|\mathcal{B}|$ based on an acquisition function $a:\mathcal{E}\rightarrow\mathbb{R}$. The value $a(u,v)$ indicates how informative the pair $(u,v)\in\mathcal{E}$ is, where a greater value implies higher informativeness. The optimal batch is selected as $\mathcal{B}=\operatorname*{arg\,max}_{\mathcal{B}\subseteq\mathcal{E},|
\mathcal{B}|=B}\sum_{(u,v)\in\mathcal{B}}a(u,v)$. This corresponds to selecting the top-$B$ pairs based on their acquisition value according to $a$; (iii) Query the oracle for the pairwise similarities of the pairs in $\mathcal{B}$. In this paper, we consider a strictly noisy oracle where each query for $(u,v)\in\mathcal{B}$ returns $S^{\ast}_{uv}$ with probability $1-\gamma$ or a value in the range $[-1,+1]$ uniformly at random with probability $\gamma$. This models an oracle that can express uncertainty in their feedback (with probability $\gamma$). For generality, we assume multiple queries for the same pair are allowed. Importantly, each query for the same pair $(u,v)$ is equally likely to be noisy. This models an oracle that is allowed to correct previous mistakes. This is a common approach in active learning for improving robustness to a noisy oracle (Sheng et al., ; Settles, ). However, our acquisition functions perform about equally well when multiple queries of the same pair is not allowed (e.g., by setting $a(u,v)=-\infty$ for all pairs that have already been queried). See our experiments in Section 4 for more details (Figure 8 in particular); (iv) Update the similarity ${S}_{uv}^{i+1}$ based on the response from the oracle for all pairs $(u,v)\in\mathcal{B}$. If multiple queries for the same pair are allowed, we set ${S}_{uv}^{i+1}$ to be the average of all queries made for the pair $(u,v)$ so far. This may lead to robustness against noise, since a noisy query of a pair will have less impact in the long run. For brevity, the current similarity matrix ${\bm{S}}^{i}$ will be referred to as ${\bm{S}}$ throughout the paper.

Figure: Algorithm 1 Active CC

## 3 Information-Theoretic Acquisition Functions

In this section, we introduce four information-theoretic acquisition functions for active CC which directly quantify the *model uncertainty*.

###### Definition 3.1 (Model uncertainty) .

The pairwise relation of a pair $(u,v)\in\mathcal{E}$ is uncertain if the clustering model (i.e., minimization of Eq. 1 given ${\bm{S}}$) cannot infer the pairwise relation with high certainty.

In Appendix B.1, we include an example that provides further intuition about the notion of model uncertainty in our setting. Querying the pair $(u,v)\in\mathcal{E}$ with maximal model uncertainty will maximally reduce uncertainty of the model, which is highly indicative of informativeness for active CC. This provides strong motivation for all acquisition functions introduced in this section. All quantities defined below are conditioned on the current similarity matrix ${\bm{S}}$, but it is left out for brevity. All acquisition functions defined in this section depend on the Gibbs distribution

$$ $\displaystyle P^{\text{Gibbs}}({\mathbf{y}}={\bm{c}})\triangleq\frac{\exp(- \beta\Delta({\bm{c}}))}{\sum_{{\bm{c}}^{\prime}\in\mathcal{C}}\exp(-\beta \Delta({\bm{c}}^{\prime}))},$ (2) $$

where $\beta\in\mathbb{R}^{+}$ is a concentration parameter, ${\mathbf{y}}=\{{\textnormal{y}}_{1},\ldots,{\textnormal{y}}_{N}\}$ is a random vector with sample space $\mathcal{C}$ (all possible clustering solutions of $\mathcal{V}$) and ${\textnormal{y}}_{u}$ is a random variable for the cluster label of $u$ with sample space $\mathbb{K}$. However, computing $P^{\text{Gibbs}}$ is intractable due to the sum over all possible clustering solutions $\mathcal{C}$ in the denominator. Therefore, in the next section, we describe a mean-field approximation of $P^{\text{Gibbs}}$ which makes it possible to efficiently calculate the proposed acquisition functions.

###### Definition 3.1 (Model uncertainty) .

### 3.1 Mean-Field Approximation for CC

We here describe the mean-field approximation of $P^{\text{Gibbs}}$. The family of factorial distributions over the space of clustering solutions is defined as $\mathcal{Q}=\{Q\in\mathcal{P}\mid Q({\bm{c}})=\prod_{u\in\mathcal{V}}Q({c}_{u})\}$, where $\mathcal{P}$ is the space of all probability distributions with sample space $\mathcal{C}$. The goal of mean-field approximation is to find a factorial distribution $Q\in\mathcal{Q}$ that best approximates the intractable distribution $P^{\text{Gibbs}}$. In general, we can compute the optimal $Q$ by minimizing the KL-divergence $Q^{*}=\operatorname*{arg\,min}_{Q\in\mathcal{Q}}D_{\mathrm{KL}}(Q\|P^{\text{
Gibbs}})$ (Hofmann and Buhmann, ; Chehreghani et al., ). Let ${\bm{M}}\in\mathbb{R}^{N\times K}$ and ${\bm{Q}}\in[0,1]^{N\times K}$, where $Q_{uk}=Q({\textnormal{y}}_{u}=k)$ is the probability that object $u$ is assigned to cluster $k$ and $M_{uk}$ is the cost of assigning object $u$ to cluster $k$. Given this, in Proposition 3.1 we propose how the KL-divergence can be minimized efficiently, when $P^{\text{Gibbs}}$ is defined in terms of the max correlation cost function $\Delta$.

Figure: Algorithm 2 Mean-Field Approximation

###### Proposition 3.1 .

Minimizing the KL-divergence corresponds to the following optimization problem.

$$ $\displaystyle Q^{*}=\operatorname*{arg\,min}_{Q\in\mathcal{Q}}-\sum_{k\in \mathbb{K}}\sum_{(u,v)\in\mathcal{E}}{S}_{uv}{Q}_{uk}{Q}_{vk}-\frac{1}{\beta} \sum_{u\in\mathcal{V}}H({\textnormal{y}}_{u})$ $\displaystyle\text{s.t.}\quad\sum_{k\in\mathbb{K}}Q_{uk}=1\quad\forall u\in \mathcal{V},$ (3) $$

where $H({\textnormal{y}}_{u})\triangleq-\sum_{k\in\mathbb{K}}{Q}_{uk}\log{Q}_{uk}$ is the entropy of ${\textnormal{y}}_{u}$. Additionally, by applying a Lagrangian relaxation to the constrained optimization in Eq. 3, we obtain the necessary condition for its extremum as

$$ $\displaystyle Q_{uk}$ $\displaystyle=\frac{\exp(-\beta M_{uk})}{\sum_{k^{\prime}\in\mathbb{K}}\exp(- \beta M_{uk^{\prime}})},\quad\forall u\in\mathcal{V},\forall k\in\mathbb{K}$ (4) $\displaystyle M_{uk}$ $\displaystyle=-\sum_{v\neq u}S_{uv}Q_{vk},\quad\forall u\in\mathcal{V},\forall k \in\mathbb{K}.$ $$

The assignment probabilities $Q_{uk}$ depend on the assignment costs $M_{uk}$, which leads to a system of $N\times K$ coupled transcendental equations. Thus, no closed form solution exists, but it can be approximated by an iterative EM-type algorithm by mutual conditioning. Alg. 2 outlines the procedure. The mean-field approximation assumes a fixed number of clusters $K$. We use the number of clusters $K$ dynamically determined by the CC algorithm used at each iteration $i$ of Alg. 1 to find ${\bm{c}}^{i}$ (see Appendix D for details of this algorithm). ${\bm{M}}^{0}$ could be initialized randomly. However, since we have the current clustering solution ${\bm{c}}^{i}$, we initialize it based on ${\bm{c}}^{i}$ as ${M}_{uk}^{0}=-\sum_{v:c^{i}_{v}=k}{S}_{uv}$, in order to speed up the convergence and potentially improve the solution found. This initialization of ${\bm{M}}^{0}$ is based on the total similarity between object $u$ and cluster $k$ in relation to the similarity between $u$ and all other clusters. A smaller similarity should correspond to a higher cost (hence the negation). Iteration $t$ of the algorithm consists of two main steps. First, ${\bm{Q}}^{t}$ is estimated as a function of ${\bm{M}}^{t-1}$. Second, ${\bm{M}}^{t}$ is calculated based on ${\bm{Q}}^{t}$. In this paper, we treat the concentration parameter $\beta\in\mathbb{R}^{+}$ as a hyperparameter. Finally, due to the form of the max correlation cost function $\Delta$ (from Proposition 2.1), both the E-step and M-step is calculated in vectorized form. In particular, the M-step is a dot product between ${\bm{S}}$ and ${\bm{Q}}^{t}$, which is extremely efficient in practice (especially if ${\bm{S}}$ is assumed sparse, which it is in our experiments).

###### Proposition 3.1 .

### 3.2 Entropy

In this section, we propose an acquisition function based on entropy. Let ${\mathbf{E}}\in\{-1,+1\}^{N\times N}$ be a random matrix where each element ${\textnormal{E}}_{uv}\in\{-1,+1\}$ is a binary random variable, where $+1$ indicates $u$ and $v$ should be in the same cluster, and $-1$ implies $u$ and $v$ should be in different clusters.

###### Proposition 3.2 .

Given mean-field approximation ${\bm{Q}}$, we have $P({\textnormal{E}}_{uv}=1)=\sum_{k\in\mathbb{K}}Q_{uk}Q_{vk}$ and $P({\textnormal{E}}_{uv}=-1)=\sum_{k,k^{\prime}\in\mathbb{K}}Q_{uk}Q_{vk^{
\prime}}\bm{1}_{\{k\neq k^{\prime}\}}=1-P({\textnormal{E}}_{uv}=1)$.

From Proposition 3.2, we define an acquisition function based on the entropy of ${\textnormal{E}}_{uv}$ as

$$ $\displaystyle a^{\text{Entropy}}(u,v)$ $\displaystyle\triangleq H({\textnormal{E}}_{uv})=\mathbb{E}_{P({\textnormal{E} }_{uv})}[-\log P({\textnormal{E}}_{uv})].$ (5) $$

###### Proposition 3.2 .

### 3.3 Information Gain

The acquisition function $a^{\text{Entropy}}$ approximates the model uncertainty based on the mean-field approximation ${\bm{Q}}$ given the current similarity matrix ${\bm{S}}$. In this section, we investigate acquisition functions inspired by the notion of information gain. In this case, the similarity matrix ${\bm{S}}$ is first augmented with pseudo-similarities (predicted by current model ${\bm{Q}}$ as ${S}_{uv}\sim P({\textnormal{E}}_{uv})$), after which a new mean-field approximation is obtained. In other words, we simulate the effect of querying one or more pairs in expectation w.r.t. the current model ${\bm{Q}}$, potentially resulting in a more accurate estimation of the model uncertainty. Due to the efficiency of Alg. 2 (mean-field), we can afford to run it many times per iteration of the active CC procedure, in order to accurately estimate the information gain. In this paper, we consider two types of information gain. First, the information gain (or equivalently the mutual information) between a pair ${\textnormal{E}}_{uv}$ and the cluster labels of objects ${\mathbf{y}}$. Due to symmetry of the mutual information we have

$$ $\displaystyle I({\mathbf{y}};{\textnormal{E}}_{uv})$ $\displaystyle=H({\mathbf{y}})-H({\mathbf{y}}\mid{\textnormal{E}}_{uv})$ (6) $\displaystyle=H({\textnormal{E}}_{uv})-H({\textnormal{E}}_{uv}\mid{\mathbf{y}}).$ (7) $$

The interpretation of $I({\mathbf{y}};{\textnormal{E}}_{uv})$ is the amount of information one expects to gain about the cluster labels of objects by observing ${\textnormal{E}}_{uv}$, where the expectation is w.r.t. $P({\textnormal{E}}_{uv})$. In other words, it measures the expected reduction in uncertainty (in entropic way) over the possible clustering solutions w.r.t. the value of ${\textnormal{E}}_{uv}$. Second, the information gain between a pair ${\textnormal{E}}_{uv}$ and all pairs ${\mathbf{E}}$:

$$ $\displaystyle I({\mathbf{E}};{\textnormal{E}}_{uv})$ $\displaystyle=H({\mathbf{E}})-H({\mathbf{E}}\mid{\textnormal{E}}_{uv})$ (8) $\displaystyle=H({\textnormal{E}}_{uv})-H({\textnormal{E}}_{uv}\mid{\mathbf{E}}).$ (9) $$

Intuitively, $I({\mathbf{E}};{\textnormal{E}}_{uv})$ measures the amount of information the pair ${\textnormal{E}}_{uv}$ provides about all pairs in ${\mathbf{E}}$. All expressions above are closely related, but the formulation used will impact how it can be approximated in practice, leading to differences in performance and efficiency. This is discussed in detail in the following subsections.

#### 3.3.1 Conditional Mean-Field Approximation

All conditional entropies defined above are approximated following the same general principle: We update the similarity matrix ${\bm{S}}$ based on what is being conditioned on, run Alg. 2 given this similarity matrix, and calculate the corresponding entropy given the updated mean-field approximation. Motivated by this, the following notation will be used throughout this section. Let ${\bm{e}}$ denote a vector in $\{-1,+1\}^{|\mathcal{D}|}$, where $\mathcal{D}\subseteq\mathcal{E}$ is a subset of the pairs. Given this, we denote by ${\bm{Q}}^{({\bm{S}}_{\mathcal{D}}={\bm{e}})}$ to be the mean-field approximation found by Alg. 2 after modifying ${\bm{S}}$ according to ${\bm{e}}$ for all pairs $(u,v)\in\mathcal{D}$ (with remaining pairs unchanged). In addition, ${\bm{Q}}$ will continue to denote the mean-field approximation given the (unchanged) similarity matrix ${\bm{S}}$. Finally, let $P({\textnormal{E}}_{uv}\mid{\bm{Q}}^{\prime})$ be the probability of ${\textnormal{E}}_{uv}$ computed as shown in Proposition 3.2 given some mean-field approximation ${\bm{Q}}^{\prime}$.

#### 3.3.2 Expected Information Gain

In this section, we consider the expressions in Eq. 6 (Expected Information Gain over cluster labels of Objects) and Eq. 8 (Expected Information Gain over the clustering relation of Pairs). We use the acronyms EIG-O and EIG-P to describe these respectively. We have $H({\mathbf{y}}\mid{\textnormal{E}}_{uv})=\mathbb{E}_{e\sim P({\textnormal{E}}_
{uv})}[H({\mathbf{y}}\mid{\textnormal{E}}_{uv}=e)]$ and $H({\mathbf{E}}\mid{\textnormal{E}}_{uv})=\mathbb{E}_{e\sim P({\textnormal{E}}_
{uv})}[H({\mathbf{E}}\mid{\textnormal{E}}_{uv}=e)]$. In this paper, we approximate $H({\mathbf{y}}\mid{\textnormal{E}}_{uv}=e)$ and $H({\mathbf{E}}\mid{\textnormal{E}}_{uv}=e)$ using conditional mean-field approximation ${\bm{Q}}^{(S_{uv}=e)}$. Given some mean-field approximation ${\bm{Q}}^{\prime}$, let

$$ $H({\textnormal{y}}_{w}\mid{\bm{Q}}^{\prime})\triangleq-\sum_{k\in\mathbb{K}}Q^ {\prime}_{wk}\log Q^{\prime}_{wk},$ (10) $$

and

$$ $H({\textnormal{E}}_{wl}\mid{\bm{Q}}^{\prime})\triangleq-\sum_{e\in\{-1,+1\}}P( {\textnormal{E}}_{wl}=e\mid{\bm{Q}}^{\prime})\log P({\textnormal{E}}_{wl}=e \mid{\bm{Q}}^{\prime}).$ (11) $$

Given this, in Proposition 3.3, we show how all relevant entropies can be computed.

###### Proposition 3.3 .

Given mean-field approximation ${\bm{Q}}$, we have $H({\mathbf{y}})=\sum_{w\in\mathcal{V}}H({\textnormal{y}}_{w}\mid{\bm{Q}})$ and $H({\mathbf{E}})=\sum_{(w,l)\in\mathcal{E}}H({\textnormal{E}}_{wl}\mid{\bm{Q}})$. In addition, given conditional mean-field approximation ${\bm{Q}}^{(S_{uv}=e)}$ for some $e\in\{-1,+1\}$, we have $H({\mathbf{y}}\mid{\textnormal{E}}_{uv}=e)=\sum_{w\in\mathcal{V}}H({
\textnormal{y}}_{w}\mid{\bm{Q}}^{(S_{uv}=e)})$ and $H({\mathbf{E}}\mid{\textnormal{E}}_{uv}=e)=\sum_{(w,l)\in\mathcal{E}}H({
\textnormal{E}}_{wl}\mid{\bm{Q}}^{(S_{uv}=e)})$.

Using Proposition 3.3, we propose the following two acquisition functions.

$$ $\displaystyle a^{\text{EIG-O}}(u,v)$ $\displaystyle\triangleq\sum_{w\in\mathcal{V}}H({\textnormal{y}}_{w}\mid{\bm{Q} })-\sum_{e\in\{-1,+1\}}P({\textnormal{E}}_{uv}=e\mid{\bm{Q}})H({\textnormal{y} }_{w}\mid{\bm{Q}}^{(S_{uv}=e)}),$ (12) $\displaystyle a^{\text{EIG-P}}(u,v)$ $\displaystyle\triangleq\sum_{(w,l)\in\mathcal{E}}H({\textnormal{E}}_{wl}\mid{ \bm{Q}})-\sum_{e\in\{-1,+1\}}P({\textnormal{E}}_{uv}=e\mid{\bm{Q}})H({ \textnormal{E}}_{wl}\mid{\bm{Q}}^{(S_{uv}=e)}).$ (13) $$

$a^{\text{EIG-O}}$ and $a^{\text{EIG-P}}$ will perform similarly in practice for the following reason. The random variable ${\textnormal{E}}_{uv}$ is determined by the random variables ${\textnormal{y}}_{u}$ and ${\textnormal{y}}_{v}$ (from Proposition 3.2). Consequently, a reduction in entropy for ${\textnormal{y}}_{u}$ and ${\textnormal{y}}_{v}$, will generally result in a reduction in entropy for ${\textnormal{E}}_{uv}$. Calculating $a^{\text{EIG-O}}$ and $a^{\text{EIG-P}}$ for all pairs requires executing Alg. 2 $N\choose 2$ times, which can be inefficient for large $N$. In Appendix B.2, we propose Alg. 3, which improves the efficiency of $a^{\text{EIG-O}}$ and $a^{\text{EIG-P}}$. The key step in this algorithm is to only evaluate Eq. 12 or Eq. 13 for a subset of the pairs $\mathcal{E}^{\text{EIG}}\subseteq\mathcal{E}$, such that Alg. 2 is only executed $|\mathcal{E}^{\text{EIG}}|$ times. We select $\mathcal{E}^{\text{EIG}}$ as the top-$|\mathcal{E}^{\text{EIG}}|$ pairs according to $a^{\text{Entropy}}$, where $|\mathcal{E}^{\text{EIG}}|=O(N)$.

###### Proposition 3.3 .

#### 3.3.3 Joint Expected Information Gain

In this section, we consider the information gain formulated in Eq. 7 and Eq. 9. The conditional entropy $H({\textnormal{E}}_{uv}\mid{\mathbf{E}})=\mathbb{E}_{{\bm{e}}\sim P({\mathbf{E
}})}[H({\textnormal{E}}_{uv}\mid{\mathbf{E}}={\bm{e}})]$ in Eq. 9 is approximated using conditional mean-field approximation ${\bm{Q}}^{({\bm{S}}_{\mathcal{E}}={\bm{e}})}$. The conditional entropy $H({\textnormal{E}}_{uv}\mid{\mathbf{y}})=\mathbb{E}_{{\bm{c}}\sim Q({\mathbf{y
}})}[H({\textnormal{E}}_{uv}\mid{\mathbf{y}}={\bm{c}})]$ in Eq. 7 is less straightforward. However, a natural way would be to compute a conditional mean-field approximation given ${\bm{S}}$ updated based on ${\bm{c}}$ as follows: set ${S}_{uv}=+1$ if ${c}_{u}={c}_{v}$, and $-1$ otherwise. In both cases, we approximate the entropy of ${\textnormal{E}}_{uv}$ given a mean-field approximation conditioned on all (or a subset) of the similarities being updated. Given this, we now derive a general estimator based on the information gain

$$ $I({\textnormal{E}}_{uv};{\mathbf{E}}_{\mathcal{D}})=H({\textnormal{E}}_{uv})-H ({\textnormal{E}}_{uv}\mid{\mathbf{E}}_{\mathcal{D}}),$ (14) $$

where ${\mathbf{E}}_{\mathcal{D}}=\{{\textnormal{E}}_{uv}\mid(u,v)\in\mathcal{D}\}$ for some $\mathcal{D}\subseteq\mathcal{E}$. From the discussion above, the expressions in Eq. 7 and Eq. 9 can be seen as special cases of Eq. 14. The entropy $H({\textnormal{E}}_{uv})$ is approximated based on Eq. 5. In addition, we have

$$ $\displaystyle H({\textnormal{E}}_{uv}\mid{\mathbf{E}}_{\mathcal{D}})$ $\displaystyle=\mathbb{E}_{{\bm{e}}\sim P({\mathbf{E}}_{\mathcal{D}})}[H({ \textnormal{E}}_{uv}\mid{\mathbf{E}}_{\mathcal{D}}={\bm{e}})]$ (15) $\displaystyle=\sum_{{\bm{e}}\in\{-1,+1\}^{|\mathcal{D}|}}P({\mathbf{E}}_{ \mathcal{D}}={\bm{e}})H({\textnormal{E}}_{uv}\mid{\mathbf{E}}_{\mathcal{D}}={ \bm{e}}).$ $$

The conditional entropy $H({\textnormal{E}}_{uv}\mid{\mathbf{E}}_{\mathcal{D}}={\bm{e}})$ is approximated with $H({\textnormal{E}}_{uv}\mid{\bm{Q}}^{({\bm{S}}_{\mathcal{D}}={\bm{e}})})
\triangleq P({\textnormal{E}}_{uv}=e\mid{\bm{Q}}^{({\bm{S}}_{\mathcal{D}}={\bm
{e}})})\log P({\textnormal{E}}_{uv}=e\mid{\bm{Q}}^{({\bm{S}}_{\mathcal{D}}={
\bm{e}})})$. In other words, we estimate the *joint* impact of pairs in $\mathcal{D}$ on the entropy of ${\textnormal{E}}_{uv}$. The expectation in Eq. 15, which involves a sum over all possible outcomes of ${\mathbf{E}}_{\mathcal{D}}$, quickly becomes intractable for large $|\mathcal{D}|$. However, one can easily obtain a sample ${\bm{e}}\sim P({\mathbf{E}}_{\mathcal{D}})$ by sampling ${e}_{uv}\sim P({\textnormal{E}}_{uv})$ for each ${\textnormal{E}}_{uv}\in{\mathbf{E}}_{\mathcal{D}}$, which allows a Monte-Carlo estimation of this sum. For generality, assume we have $m$ subsets $\mathcal{D}_{1},\ldots,\mathcal{D}_{m},\mathcal{D}_{i}\subseteq\mathcal{E}$ and $n$ samples ${\bm{e}}_{i}^{1},\ldots,{\bm{e}}_{i}^{n}\sim P({\mathbf{E}}_{\mathcal{D}_{i}})$ for each $\mathcal{D}_{i}$. Given this, we define the acquisition function

$$ $a^{\text{JEIG}}(u,v)\triangleq H({\textnormal{E}}_{uv})-\frac{1}{mn}\sum_{i=1} ^{m}\sum_{l=1}^{n}H({\textnormal{E}}_{uv}\mid{\bm{Q}}^{({\bm{S}}_{\mathcal{D}_ {i}}={\bm{e}}^{l}_{i})}).$ (16) $$

For $a^{\text{JEIG}}$, we only need to execute Alg. 2 (mean-field) $mn$ times, and in practice, we observe good performance with small values of $m$ and $n$. In Appendix B.3, we include Alg. 4 which describes the details of this method. Using $m$ subsets $\mathcal{D}_{1},\ldots\mathcal{D}_{m}$ where each $|\mathcal{D}_{i}|\ll|\mathcal{E}|$ yields a number of benefits: (i) The Monte-Carlo estimation of the expectation $\mathbb{E}_{{\bm{e}}\sim P({\mathbf{E}}_{\mathcal{D}_{i}})}[H({\textnormal{E}}
_{uv}\mid{\mathbf{E}}_{\mathcal{D}_{i}}={\bm{e}})]$ becomes more accurate for smaller $n$ when $|\mathcal{D}_{i}|$ is smaller, which reduces the number of times Alg. 2 needs to be executed; (ii) If $\mathcal{D}_{i}=\mathcal{E}$, the conditional mean-field approximation ${\bm{Q}}^{({\bm{S}}_{\mathcal{D}_{i}}={\bm{e}})}$ is computed based on a similarity matrix where all pairs $(u,v)\in\mathcal{E}$ are sampled from ${S}_{uv}\sim P({\textnormal{E}}_{uv})$, which will lead to extreme selection bias for the following reason: The probability $P({\textnormal{E}}_{uv})$ (which is computed using ${\bm{Q}}$) may already be biased (in particular in early iterations when ${\bm{S}}$ contains incomplete/wrong information, see Appendix B.1 for discussion about this). Then, running Alg. 2 from scratch with a new similarity matrix fully augmented with biased information, will exaggerate the bias further; (iii) Using $m$ different subsets makes the estimator in Eq. 16 generic and flexible, but also captures more information about ${\textnormal{E}}_{uv}$, while remaining efficient and avoiding exaggerated selection bias.

## 4 Experiments

In this section, we describe our experimental studies, where extensive additional results are presented in Appendix C.

### 4.1 Experimental Setup

Datasets. In this paper, we use the datasets investigated by (Aronsson and Chehreghani, ) (except one excluded due to space limit): 20newsgroups, CIFAR10, cardiotocography, ecoli, forest type mapping, user knowledge modeling, yeast and synthetic. See Appendix C.2 for details about all datasets.

Pairwise similarities. For each experiment, we are given a dataset with ground-truth labels, where the ground-truth labels are only used for evaluations. Then, for each $(u,v)\in\mathcal{E}$ in a dataset, we set $S^{\ast}_{uv}$ to $+1$ if $u$ and $v$ belong to the same cluster, and $-1$ otherwise. Let $\mathcal{E}^{0}$ be a uniform random subset of $\mathcal{E}$ (where $|\mathcal{E}^{0}|\ll|\mathcal{E}|$). Then, unless otherwise specified, we initialize the current similarity matrix as $S_{uv}^{0}=S^{\ast}_{uv}$ for $(u,v)\in\mathcal{E}^{0}$, and $S_{uv}^{0}=0$ for $(u,v)\in\mathcal{E}\setminus\mathcal{E}^{0}$. Having $|\mathcal{E}^{0}|=0$ or $|\mathcal{E}^{0}|>0$ correspond to a *cold-start* or *warm-start* setting, respectively. In this paper, like most previous work on active learning, we focus on a warm-start setting. See Appendix C.2 for the value of $|\mathcal{E}^{0}|$ for each dataset ($|\mathcal{E}^{0}|$ is chosen based on the size $N$ of each dataset).

Acquisition functions. We have introduced four novel acquisition functions in this paper: $a^{\text{Entropy}}$ (Eq. 5), $a^{\text{EIG-O}}$ (Eq. 12), $a^{\text{EIG-P}}$ (Eq. 13) and $a^{\text{JEIG}}$ (Eq. 16). We compare these methods with *maxexp* and *maxmin* from (Aronsson and Chehreghani, ). In short, both maxmin and maxexp aim to query pairs with small absolute similarity that belong to triples $(u,v,w)$ that violate the transitive property of pairwise similarities. In other words, the goal is to reduce the inconsistency of ${\bm{S}}$ by resolving violations of the transitive property in triples. In Appendix C.1, we include a detailed explanation of these methods. Finally, we include a simple baseline $a^{\text{Uniform}}(u,v)\sim\text{Uniform}(0,1)$ which selects pairs uniformly at random. The work in (Aronsson and Chehreghani, ) compares maxexp/maxmin to a pivot-based active CC algorithm called QECC (García-Soriano et al., ) and two adapted state-of-the-art active constraint clustering methods, called COBRAS (van Craenendonck et al., ) and nCOBRAS (Soenen et al., ). However, these methods perform very poorly compared to maxexp and maxmin in a noisy setting, so we exclude them here.

Batch diversity. In this paper, we consider single-sample acquisition functions that do not explicitly consider the joint informativeness among the elements in a batch $\mathcal{B}$. This has the benefit of avoiding the combinatorial complexity of selecting an optimal batch, which is a common problem for batch active learning (Ren et al., ). However, the work in (Kirsch et al., ) proposes a simple method for improving the batch diversity for single-sample acquisition functions using noise. In this paper, we utilize the power acquisition method. Given some acquisition function $a^{\text{X}}$, this corresponds to $a^{\text{PowerX}}(u,v)=\log(a^{\text{X}}(u,v))+\epsilon_{uv}$ where $\epsilon_{uv}\sim\text{Gumbel}(0;1)$. This is used for all information-theoretic acquisition functions proposed in this paper. We observe no benefit of this for maxmin/maxexp, likely due to their inherent randomness.

Hyperparameters. Unless otherwise specified, the following hyperparameters are used. The batch size $B$ depends on the dataset (since each dataset is of different size $N$). See Appendix C.2 for the value of $B$ for each dataset. For all information-theoretic acquisition functions (which depend on $P^{\text{Gibbs}}$, see Eq. 2), we set $\beta=3$. For $a^{\text{EIG-O}}$ and $a^{\text{EIG-P}}$, we set $|\mathcal{E}^{\text{EIG}}|=20N$ (See Appendix B.2 for details). For $a^{\text{JEIG}}$ we set $m=5$, $n=50$, $|\mathcal{D}_{i}|=\lceil|\mathcal{E}|/50\rceil$ (i.e., 2% of all pairs) and each $\mathcal{D}_{i}$ is selected to contain pairs with large entropy (see Appendix B.3 for details). Finally, see Appendix C.7 for a detailed analysis and discussion of all hyperparameters.

Performance evaluation. In each iteration of the active CC procedure (Alg. 1), we calculate the Adjusted Rand Index (ARI) between the current clustering ${\bm{c}}^{i}$ and the ground truth clustering ${\bm{c}}^{\ast}$ (i.e., ground truth labels of dataset). Intuitively, ARI measures how similar the two clusterings are, where a value of 1 indicates they are identical. In Appendix C.3, we report the performance w.r.t. other evaluation metrics. Each active learning procedure is repeated 15 times with different random seeds, where the standard deviation is indicated by a shaded color or an error bar.

### 4.2 Results

Figure: (a) Synthetic
Refer to caption: extracted/2402.03587v2/figures/rand_synthetic_0.6.png

Figure: Figure 2: Results on the synthetic dataset when varying the noise level $\gamma$ and the batch size $B$.
Refer to caption: extracted/2402.03587v2/figures/app/noise_level.png

Figure 1 shows the results for different datasets with noise level $\gamma=0.6$. In Appendix C.3, we include results for all datasets with $\gamma=0.4$. We observe that all information-theoretic acquisition functions introduced in this paper significantly outperform the baseline methods. In addition, the acquisition functions based on information gain ($a^{\text{EIG-O}}$, $a^{\text{EIG-P}}$ and $a^{\text{JEIG}}$) consistently outperform $a^{\text{Entropy}}$. This indicates the effectiveness of augmenting the similarity matrix ${\bm{S}}$ with pseudo-similarities predicted by the current model ${\bm{Q}}$ as ${S}_{uv}\sim P({\textnormal{E}}_{uv}\mid{\bm{Q}})$, before quantifying the model uncertainty. Expectedly, the acquisition functions based on information gain perform similarly. This is due to the fact that all of them are based on closely connected quantities (as described in Section 3.3). However, $a^{\text{JEIG}}$ is consistently among the best performing acquisition functions, while also being more computationally efficient compared to $a^{\text{EIG-O}}$ and $a^{\text{EIG-P}}$ (see Appendix C.5 for an investigation of the runtime of all methods). Both maxmin and maxexp perform rather poorly. This is likely because they spend too many queries with the goal of resolving the inconsistency of ${\bm{S}}$. In particular, this may lead to numerous repeated queries of the same pair, in order to correct for previous mistakes by the oracle. However, the correlation clustering algorithm used (described in Appendix D) is robust to inconsistency in ${\bm{S}}$. See Appendix C.6 for a detailed investigation of the performance of different acquisition functions when repeated queries of the same pair are not allowed. Finally, in Appendix C.4 we show experiments on a small synthetic dataset with $N=70$ objects using a small batch size $B=5$. The purpose of this experiment is to further illustrate the benefit of the acquisition functions based on information gain, when differences due to batch diversity are eliminated.

### 4.3 Sensitivity Analysis

We here investigate the sensitivity of acquisition functions when varying different hyperparameters. All the results in this section are performed on the synthetic dataset. Figures 2-2 show the results when varying the noise level $\gamma$ and batch size $B$, respectively. The $y$-axis corresponds to the area under the curve (AUC) of the active learning plot w.r.t. the respective performance metric (i.e., ARI) where higher is better. We see that our acquisition functions are very robust to noise. In addition, the benefit of our proposed acquisition functions increases with larger noise levels. Expectedly, the performance decreases slightly as the batch size increases. However, the performance of our acquisition functions remains good even with large batch sizes.

## 5 Conclusion

In this paper, we proposed four effective information-theoretic acquisition functions to be used for active correlation clustering: $a^{\text{Entropy}}$, $a^{\text{EIG-O}}$, $a^{\text{EIG-P}}$ and $a^{\text{JEIG}}$. All of our methods significantly outperform the baseline methods by utilizing *model uncertainty*. We investigated the effectiveness of these methods via extensive experimental studies. The acquisition functions based on information gain ($a^{\text{EIG-O}}$, $a^{\text{EIG-P}}$ and $a^{\text{JEIG}}$) were consistently the best performing, where $a^{\text{JEIG}}$ has the benefit of being more computationally efficient.

## Appendix A Proofs

See 2.1

###### Proof.

As described in [Chehreghani, , ], we can write the cost function in Eq. 1 as

$$ $\displaystyle R({\bm{c}}\mid{\bm{S}})$ $\displaystyle=\sum_{(u,v)\in\mathcal{E}}V(u,v\mid{\bm{S}},{\bm{c}})$ $\displaystyle=\sum_{\begin{subarray}{c}(u,v)\in\mathcal{E}\\ c_{u}=c_{v}\end{subarray}}\frac{1}{2}(|S_{uv}|-S_{uv})+\sum_{\begin{subarray}{ c}(u,v)\in\mathcal{E}\\ c_{u}\neq c_{v}\end{subarray}}\frac{1}{2}(|S_{uv}|+S_{uv})$ $\displaystyle=\frac{1}{2}\sum_{(u,v)\in\mathcal{E}}|S_{uv}|-\frac{1}{2}\sum_{ \begin{subarray}{c}(u,v)\in\mathcal{E}\\ c_{u}=c_{v}\end{subarray}}S_{uv}+\frac{1}{2}\sum_{(u,v)\in\mathcal{E}}S_{uv}- \frac{1}{2}\sum_{\begin{subarray}{c}(u,v)\in\mathcal{E}\\ c_{u}=c_{v}\end{subarray}}S_{uv}$ $\displaystyle=\underbrace{\frac{1}{2}\sum_{(u,v)\in\mathcal{E}}(|S_{uv}|+S_{uv })}_{\text{constant}}-\sum_{\begin{subarray}{c}(u,v)\in\mathcal{E}\\ c_{u}=c_{v}\end{subarray}}S_{uv}.$ (17) $$

The first term in Eq. A is *constant* w.r.t. the choice of a particular clustering ${\bm{c}}$.

∎

See 3.1

###### Proof.

We have

$$ $\displaystyle D_{\mathrm{KL}}(Q\|P^{\text{Gibbs}})$ $\displaystyle=\sum_{{\bm{c}}\in\mathcal{C}}Q({\bm{c}})\log\frac{Q({\bm{c}})}{P ^{\text{Gibbs}}({\bm{c}})}$ (18) $\displaystyle=\sum_{c\in\mathcal{C}}Q({\bm{c}})\log\frac{Q({\bm{c}})}{\exp \left(-\beta\left(\Delta({\bm{c}})-\mathcal{F}\right)\right)}$ $\displaystyle=\sum_{c\in\mathcal{C}}Q({\bm{c}})\left[\log Q({\bm{c}})+\beta \left(\Delta({\bm{c}})-\mathcal{F}\right)\right]$ $\displaystyle=\sum_{u\in\mathcal{V}}\sum_{k\in\mathbb{K}}Q_{uk}\log Q_{uk}+ \beta\mathbb{E}_{Q({\bm{c}})}[\Delta({\bm{c}})]-\beta\mathcal{F}$ $\displaystyle=\beta\mathbb{E}_{Q({\bm{c}})}[\Delta({\bm{c}})]-\sum_{u\in \mathcal{V}}H({\textnormal{y}}_{u})-\beta\mathcal{F},$ $$

where $\mathcal{F}\triangleq-\frac{1}{\beta}\log\mathcal{Z}$ is the free energy and $\mathcal{Z}\triangleq\sum_{{\bm{c}}^{\prime}\in\mathcal{C}}\exp(-\beta\Delta({
\bm{c}}^{\prime}))$ is the normalizing constant of the Gibbs distribution in Eq. 2. The free energy $\mathcal{F}$ (and $\beta$) are constant w.r.t. $Q$, so minimizing the KL-divergence corresponds to minimizing $\mathbb{E}_{Q({\bm{c}})}[\Delta({\bm{c}})]-\frac{1}{\beta}\sum_{u\in\mathcal{V
}}H({\textnormal{y}}_{u})$ w.r.t. $Q$. We can simplify

$$ $\displaystyle\mathbb{E}_{Q({\bm{c}})}[\Delta({\bm{c}})]$ $\displaystyle=\mathbb{E}_{Q({\bm{c}})}\left[-\sum_{\begin{subarray}{c}(u,v)\in \mathcal{E}\\ c_{u}=c_{v}\end{subarray}}S_{uv}\right]$ (19) $\displaystyle=\mathbb{E}_{Q({\bm{c}})}\left[-\sum_{k\in\mathbb{K}}\sum_{(u,v) \in\mathcal{E}}\bm{1}_{\{c_{u}=k\}}({\bm{c}})\bm{1}_{\{c_{v}=k\}}({\bm{c}})S_{ uv}\right]$ $\displaystyle=-\sum_{k\in\mathbb{K}}\sum_{(u,v)\in\mathcal{E}}\mathbb{E}_{Q({ \bm{c}})}\left[\bm{1}_{\{c_{u}=k\}}({\bm{c}})\bm{1}_{\{c_{v}=k\}}({\bm{c}}) \right]S_{uv}$ $\displaystyle=-\sum_{k\in\mathbb{K}}\sum_{(u,v)\in\mathcal{E}}S_{uv}Q_{uk}Q_{ vk}.$ $$

Then, by applying a Lagrangian relaxation to the constraint in Eq. 3 and setting the gradient of the objective w.r.t. $Q_{uk}$ to zero, we obtain

$$ $\displaystyle 0$ $\displaystyle=\frac{\partial}{\partial Q_{uk}}\left[\mathbb{E}_{Q({\bm{c}})}[ \Delta({\bm{c}})]-\frac{1}{\beta}\sum_{v\in\mathcal{V}}H({\textnormal{y}}_{v}) +\sum_{w\in\mathcal{V}}\mu_{w}\left(\sum_{k\in\mathbb{K}}Q_{wk}-1\right)\right]$ (20) $\displaystyle=\frac{\partial}{\partial Q_{uk}}\left[\sum_{{\bm{c}}\in\mathcal{ C}}\prod_{v\in\mathcal{V}}Q_{vc_{v}}\Delta({\bm{c}})-\frac{1}{\beta}\sum_{v\in \mathcal{V}}H({\textnormal{y}}_{v})+\sum_{w\in\mathcal{V}}\mu_{w}\left(\sum_{k \in\mathbb{K}}Q_{wk}-1\right)\right]$ $\displaystyle=\sum_{{\bm{c}}\in\mathcal{C}}\prod_{\begin{subarray}{c}v\in \mathcal{V}\\ v\neq u\end{subarray}}Q_{vc_{v}}\bm{1}_{\{c_{u}=k\}}\Delta({\bm{c}})+\frac{1}{ \beta}\left(\log Q_{uk}+1\right)+\mu_{u}$ $\displaystyle=\mathbb{E}_{Q({\bm{c}}\mid c_{u}=k)}[\Delta({\bm{c}})]+\frac{1}{ \beta}\left(\log Q_{uk}+1\right)+\mu_{u},$ $$

where $\mu_{u}$’s are the Lagrange multipliers and we define ${M}_{uk}\triangleq\mathbb{E}_{Q({\bm{c}}\mid c_{u}=k)}[\Delta({\bm{c}})]$ as the mean-fields, which correspond to the expected cost subject to the constraint that object $u$ is assigned to cluster $k$. We can simplify

$$ $\displaystyle{M}_{uk}$ $\displaystyle=\mathbb{E}_{Q({\bm{c}}\mid c_{u}=k)}[\Delta({\bm{c}})]$ (21) $\displaystyle=\mathbb{E}_{Q({\bm{c}}\mid c_{u}=k)}\left[-\sum_{(v,w)\in \mathcal{E}}S_{vw}\right]$ $\displaystyle=\mathbb{E}_{Q({\bm{c}}\mid c_{u}=k)}\left[-\sum_{l\in\mathbb{K}} \sum_{(v,w)\in\mathcal{E}}\bm{1}_{\{c_{v}=l\}}({\bm{c}})\bm{1}_{\{c_{w}=l\}}({ \bm{c}})S_{vw}\right]$ $\displaystyle=-\sum_{l\in\mathbb{K}}\sum_{(v,w)\in\mathcal{E}}\mathbb{E}_{Q({ \bm{c}}\mid c_{u}=k)}[\bm{1}_{\{c_{v}=l\}}({\bm{c}})\bm{1}_{\{c_{w}=l\}}({\bm{ c}})]S_{vw}$ $\displaystyle=-\sum_{l\in\mathbb{K}}\sum_{(v,w)\in\mathcal{E}}S_{vw}Q_{vl}Q_{wl}$ $\displaystyle=-\sum_{l\in\mathbb{K}}\sum_{\begin{subarray}{c}v\in\mathcal{V}\\ v\neq u\end{subarray}}S_{uv}Q_{ul}Q_{vl}-\sum_{l\in\mathbb{K}}\sum_{\begin{ subarray}{c}(v,w)\in\mathcal{E}\\ v\neq u\\ w\neq u\end{subarray}}S_{vw}Q_{vl}Q_{wl}$ $\displaystyle=-\sum_{\begin{subarray}{c}v\in\mathcal{V}\\ v\neq u\end{subarray}}S_{uv}Q_{vk}-\underbrace{\sum_{l\in\mathbb{K}}\sum_{ \begin{subarray}{c}(v,w)\in\mathcal{E}\\ v\neq u\\ w\neq u\end{subarray}}S_{vw}Q_{vl}Q_{wl}}_{\text{constant}},$ $$

where the last equality uses that $Q_{ul}=1$ if $l=k$ and 0 0 otherwise, according to $Q({\bm{c}}\mid c_{u}=k)$. The second term of the last expression is a constant w.r.t. $Q_{uk}$ and is thus irrelevant for optimization (since it does not depend on $u$).

With the definition of ${M}_{uk}$, we can rewrite Eq. 20 as

$$ $\displaystyle 0$ $\displaystyle={M}_{uk}+\frac{1}{\beta}\left(\log Q_{uk}+1\right)+\mu_{u}.$ (22) $$

Then, we have

$$ $\displaystyle\log Q_{uk}=-\beta{M}_{uk}-\beta\mu_{u}$ (23) $\displaystyle\Rightarrow$ $\displaystyle Q_{uk}=\exp{(-\beta{M}_{uk})}\exp{(-\beta\mu_{u})}.$ $$

On the other hand, we have: $\sum_{k^{\prime}}Q_{uk^{\prime}}=1$. Therefore,

$$ $\displaystyle\sum_{k^{\prime}}\log Q_{uk^{\prime}}=\sum_{k^{\prime}}{\exp{(- \beta{M}_{uk^{\prime}})}\exp{(-\beta\mu_{u})}}=1$ (24) $\displaystyle\Rightarrow$ $\displaystyle\exp{(-\beta\mu_{u})}=\frac{1}{\sum_{k^{\prime}}{\exp{(-\beta{M}_ {uk^{\prime}})}}}\,.$ $$

Finally, inserting Eq. 24 into Eq. 23 yields

$$ $\displaystyle Q_{uk}=\frac{\exp{(-\beta{M}_{uk})}}{\sum_{k^{\prime}}{\exp{(- \beta{M}_{uk^{\prime}})}}}\,.$ (25) $$

This derivation suggest an EM-type procedure for minimizing the KL-divergence $D_{\mathrm{KL}}(Q\|P^{\text{Gibbs}})$, which consists of alternating between estimating $Q_{uk}$’s given ${M}_{uk}$’s and then updating ${M}_{uk}$’s given the new values of $Q_{uk}$’s (as described in Alg. 2).

∎

See 3.2

###### Proof.

Motivated by the intuitive example of model uncertainty explained in Appendix B.1, we interpret the probability of ${\textnormal{E}}_{uv}$ to be $+1$ (i.e., that $u$ and $v$ should be placed in the same cluster) as the fraction of clustering solutions in $\mathcal{C}$ that assign $u$ and $v$ to the same cluster, weighted by the probability of each clustering solution (which is determined by its cost based on $P^{\text{Gibbs}}$ in Eq. 2). From this, we define $P({\textnormal{E}}_{uv}=1)$ as the expectation of $\bm{1}_{\{c_{u}=c_{v}\}}({\bm{c}})$ w.r.t. the distribution $Q({\bm{c}})$ (which approximates $P^{\text{Gibbs}}$). We have

$$ $\displaystyle P({\textnormal{E}}_{uv}=1)$ $\displaystyle=\mathbb{E}_{Q({\bm{c}})}[\bm{1}_{\{c_{u}=c_{v}\}}({\bm{c}})]$ (26) $\displaystyle=\mathbb{E}_{c_{u}\sim Q_{u}}[\mathbb{E}_{c_{v}\sim Q_{v}}[\bm{1} _{\{c_{u}=c_{v}\}}]]$ $\displaystyle=\sum_{k^{\prime}\in\mathbb{K}}Q_{uk^{\prime}}\sum_{k^{\prime \prime}\in\mathbb{K}}Q_{uk^{\prime\prime}}\bm{1}_{\{c_{u}=c_{v}\}}$ $\displaystyle=\sum_{k\in\mathbb{K}}Q_{uk}Q_{vk}+\underbrace{\sum_{k^{\prime} \in\mathbb{K}}\sum_{\begin{subarray}{c}k^{\prime\prime}\in\mathbb{K}\\ k^{\prime\prime}\neq k^{\prime}\end{subarray}}Q_{uk^{\prime}}Q_{vk^{\prime \prime}}\bm{1}_{\{c_{u}=c_{v}\}}}_{=0}$ $\displaystyle=\sum_{k\in\mathbb{K}}Q_{uk}Q_{vk}.$ $$

The second equality of Eq. 26 utilizes the fact that the cluster labels of all objects are independent given mean-field approximation ${\bm{Q}}$. The probability of ${\textnormal{E}}_{uv}$ to be $-1$ is interpreted in a corresponding way. Thus, we have $P({\textnormal{E}}_{uv}=-1)=\mathbb{E}_{Q({\bm{c}})}[\bm{1}_{\{c_{u}\neq c_{v}
\}}({\bm{c}})]$ which can be simplified to $P({\textnormal{E}}_{uv}=-1)=\sum_{k,k^{\prime}\in\mathbb{K}}Q_{uk}Q_{vk^{
\prime}}\bm{1}_{\{k\neq k^{\prime}\}}=1-P({\textnormal{E}}_{uv}=1)$ similar to the derivation in Eq. 26.

∎

See 3.3

###### Proof.

We have

$$ $H({\mathbf{y}})=-\sum_{{\bm{c}}\in\mathcal{C}}P^{\text{Gibbs}}({\mathbf{y}}={ \bm{c}})\log P^{\text{Gibbs}}({\mathbf{y}}={\bm{c}}).$ (27) $$

A mean-field approximation $Q({\mathbf{y}}={\bm{c}})=\prod_{u=1}^{N}Q({\textnormal{y}}_{u}=c_{u})$ of $P^{\text{Gibbs}}$ assumes independence between each cluster label ${\textnormal{y}}_{u}$. This means we have

$$ $\displaystyle H({\mathbf{y}})$ $\displaystyle=-\sum_{{\bm{c}}\in\mathcal{C}}Q({\mathbf{y}}={\bm{c}})\log Q({ \mathbf{y}}={\bm{c}})$ (28) $\displaystyle=-\sum_{{\bm{c}}\in\mathcal{C}}\prod^{N}_{u=1}Q({\textnormal{y}}_ {u}={c}_{u})\log\prod^{N}_{v=1}Q({\textnormal{y}}_{v}={c}_{v})$ $\displaystyle=-\sum_{{\bm{c}}\in\mathcal{C}}\prod^{N}_{u=1}Q({\textnormal{y}}_ {u}={c}_{u})(\sum_{v=1}^{N}\log Q({\textnormal{y}}_{v}={c}_{v}))$ $\displaystyle=-\sum_{{\bm{c}}\in\mathcal{C}}\sum_{v=1}^{N}\prod^{N}_{u=1}Q({ \textnormal{y}}_{u}={c}_{u})\log Q({\textnormal{y}}_{v}={c}_{v})$ $\displaystyle=-\sum_{v=1}^{N}\sum_{k\in\mathbb{K}}\sum_{\begin{subarray}{c}{ \bm{c}}\in\mathcal{C}\\ c_{v}=k\end{subarray}}\prod^{N}_{u=1}Q({\textnormal{y}}_{u}={c}_{u})\log Q({ \textnormal{y}}_{v}={c}_{v})$ $\displaystyle=-\sum_{v=1}^{N}\sum_{k\in\mathbb{K}}\log Q({\textnormal{y}}_{v}= {c}_{v})\sum_{\begin{subarray}{c}{\bm{c}}\in\mathcal{C}\\ c_{v}=k\end{subarray}}\prod^{N}_{u=1}Q({\textnormal{y}}_{u}={c}_{u})$ $\displaystyle=-\sum_{v=1}^{N}\sum_{k\in\mathbb{K}}\log Q({\textnormal{y}}_{v}= {c}_{v})Q({\textnormal{y}}_{v}={c}_{v})\underbrace{\left(\sum_{\begin{subarray }{c}{\bm{c}}\in\mathcal{C}\\ c_{v}=k\end{subarray}}\prod^{N}_{\begin{subarray}{c}u=1\\ u\neq v\end{subarray}}Q({\textnormal{y}}_{u}={c}_{u})\right)}_{=1}$ $\displaystyle=-\sum_{v=1}^{N}\sum_{k\in\mathbb{K}}Q({\textnormal{y}}_{v}={c}_{ v})\log Q({\textnormal{y}}_{v}={c}_{v})$ $\displaystyle=\sum_{v=1}^{N}H({\textnormal{y}}_{v}\mid{\bm{Q}}).$ $$

Furthermore, we assume independence between pairs ${\mathbf{E}}$ given a mean-field approximation ${\bm{Q}}$. Consequently, we have $P({\mathbf{E}})=\prod_{(w,l)\in\mathcal{E}}P({\textnormal{E}}_{wl}\mid{\bm{Q}})$. Then, one can derive $H({\mathbf{E}})=\sum_{(w,l)\in\mathcal{E}}H({\textnormal{E}}_{wl}\mid{\bm{Q}})$ following the same derivation as shown in Eq. 28. In addition, we choose to approximate $H({\mathbf{y}}\mid{\textnormal{E}}_{uv}=e)$ and $H({\mathbf{E}}\mid{\textnormal{E}}_{uv}=e)$ using conditional mean-field approximation ${\bm{Q}}^{(S_{uv}=e)}$. As a consequence, the joint conditional entropies reduces to the sum of entropies over individual variables. This is shown following the same derivation shown in Eq. 28.

∎

###### Proof.

###### Proof.

###### Proof.

###### Proof.

## Appendix B Additional Details about Information-Theoretic Acquisition Functions

In this section, we provide additional information about the information-theoretic acquisition functions.

### B.1 Model Uncertainty Example

For simplicity of explanation, assume we have three objects $\mathcal{V}=\{u,v,w\}$. In this case, we have at most $K=N$ clusters, i.e., $\mathbb{K}=\{1,2,3\}$. Given this, the space of clustering solutions contains five unique solutions $\mathcal{C}=\{{\bm{c}}^{1},\ldots,{\bm{c}}^{5}\}=\{\{1,1,1\},\{2,1,1\},\{1,2,1
\},\{1,1,2\},\{1,2,3\}\}$, where each ${\bm{c}}^{i}=\{{c}^{i}_{u},{c}^{i}_{v},{c}^{i}_{w}\}$. Assume the pairwise similarities $S_{uv}=+1$, $S_{uw}=+1$ and $S_{vw}=0$. The cost (Eq. 1) of each clustering solution would be $\{R({\bm{c}}^{1}),R({\bm{c}}^{2}),R({\bm{c}}^{3}),R({\bm{c}}^{4}),R({\bm{c}}^{
5})\}=\{0,2,1,1,2\}$. The optimal clustering is then ${\bm{c}}^{1}=\operatorname*{arg\,min}_{{\bm{c}}\in\mathcal{C}}R({\bm{c}})$ with cost 0 0, which corresponds to assigning all objects to the same cluster. In this case, ${\bm{c}}^{1}$ is a unique minimizer of the cost implying that the model can infer that objects $v$ and $w$ should be in the same cluster, despite the similarity ${S}_{vw}=0$ (i.e., the similarity ${S}_{vw}=+1$ is inferred by the clustering model).

In contrast, assume the pairwise similarities $S_{uv}=-1$, $S_{uw}=-1$ and $S_{vw}=0$. In this case, the cost of each clustering solution would be $\{R({\bm{c}}^{1}),R({\bm{c}}^{2}),R({\bm{c}}^{3}),R({\bm{c}}^{4}),R({\bm{c}}^{
5})\}=\{2,1,1,1,2\}$. Consequently, we have $\{{\bm{c}}^{2},{\bm{c}}^{3},{\bm{c}}^{4}\}=\operatorname*{arg\,min}_{{\bm{c}}
\in\mathcal{C}}R({\bm{c}})$ all with a cost of $1$. The solution ${\bm{c}}^{2}$ assigns $v$ and $w$ to the same cluster, whereas ${\bm{c}}^{3}$ and ${\bm{c}}^{4}$ assigns $v$ and $w$ to different clusters. One could estimate the probability that $v$ and $w$ should be in the same cluster to be $1/3$ and the probability that they are in different clusters to be $2/3$. In other words, there is uncertainty about the relation between $v$ and $w$ according to the model. Therefore, querying the pair $(v,w)$ in order to reveal ${S}_{vw}$ may reveal the correct clustering.

From the above reasoning, querying pairs guided by model uncertainty is guaranteed to maximally reduce the uncertainty of the model given the current similarity matrix ${\bm{S}}$. However, ${\bm{S}}$ may contain incomplete/noisy information, particularly in early iterations of the active CC procedure, leading to biased selections. In other words, solely exploiting model uncertainty may not lead to optimal selections in the long term.

### B.2 EIG Algorithm

Alg. 3 outlines an efficient procedure to calculate the acquisition functions $a^{\text{EIG-O}}$ and $a^{\text{EIG-P}}$ defined in Eq. 12 and Eq. 13, respectively. The algorithm begins by initializing ${\bm{Q}}$ and ${\bm{M}}$ by running Algorithm 2. Then, it selects a subset of pairs $\mathcal{E}^{\text{EIG}}\subseteq\mathcal{E}$, for which the information gain is computed. In this step, we can exclude a significant portion of the pairs for which we suspect the information gain will not be large. For example, one could select the top-$|\mathcal{E}^{\text{EIG}}|$ pairs according to $a^{\text{Entropy}}$ (which is easily done by using ${\bm{Q}}$ from line 3), which we do in this paper. Alternatively, one could sample $|\mathcal{E}^{\text{EIG}}|$ pairs uniformly at random. We found $|\mathcal{E}^{\text{EIG}}|=20N$ to perform well for all datasets, which means we need to run Alg. 2 $O(N)$ times (instead of $O(N^{2})$). See Appendix C.7 for additional details. Then, the algorithm efficiently computes the information gain for each pair in $|\mathcal{E}^{\text{EIG}}|$. Lines 7-8 invoke Alg. 2 conditioned on $S_{uv}$ being equal to $+1$ and $-1$, respectively. In practice, the algorithm remains quite efficient even for large $|\mathcal{E}^{\text{EIG}}|$. This efficiency is possible for the following reasons: (i) We do not expect ${\bm{Q}}^{({S}_{uv}=j)}$ to be much different from ${\bm{Q}}$. Therefore, by initializing ${\bm{M}}^{0}$ with ${\bm{M}}$ (on lines 7-8), the convergence speed of Alg. 2 is significantly improved; (ii) As discussed in Section 3.1, both the E-step and M-step of Alg. 2 are computed in a vectorized form, leading to efficient calculations. In particular, the M-step is a dot product between ${\bm{S}}$ and ${\bm{Q}}^{t}$ if one assumes zeros on the diagonal of ${\bm{S}}$ (which we do). This is due to the form of the max correlation cost function $\Delta$ from Proposition 2.1 and the mean-field equations in Eq. 4; (iii) By initializing ${\bm{S}}^{0}$ to all zeros, this dot product becomes extremely efficient by utilizing the sparsity of ${\bm{S}}$ (e.g., by storing ${\bm{S}}$ as a scipy.sparse.csr_array [Virtanen et al., ]).

Figure: Algorithm 3 EIG

### B.3 JEIG Algorithm

Alg. 4 outlines how the acquisition function $a^{\text{JEIG}}$ (Eq. 16) is calculated. The algorithm begins by initializing ${\bm{Q}}$ and ${\bm{M}}$ by running Algorithm 2. Then, the algorithm loops $m$ times. In each of the $m$ iterations, a subset $\mathcal{D}_{i}\subseteq\mathcal{E}$ is selected. Then, lines 7-10 computes a Monte-Carlo estimation of the expectation $\mathbb{E}_{{\bm{e}}\sim P({\mathbf{E}}_{\mathcal{D}_{i}})}[H({\textnormal{E}}
_{uv}\mid{\mathbf{E}}_{\mathcal{D}_{i}}={\bm{e}})]$. We found that the selection of $\mathcal{D}_{i}$ (on line 6) can be done in a number of ways, with good performance. In the experiments of this paper, we select the top-$|\mathcal{D}_{i}|$ pairs according to $\log(a^{\text{Entropy}}(u,v))+\epsilon_{uv}$ where $\epsilon_{uv}\sim\text{Gumbel}(0;1)$. In other words, the top-$|\mathcal{D}_{i}|$ pairs according to $a^{\text{Entropy}}$ with some added acquisition noise (as explained in Section 4.1). This leads to diversity among the selected $\mathcal{D}_{i}$, while containing pairs with large entropy. Pairs with large entropy are likely to have large impact on each ${\textnormal{E}}_{uv}$, and are therefore important to include in $\mathcal{D}_{i}$. We set $|\mathcal{D}_{i}|=0.02|\mathcal{E}|$ (i.e., 2% of all pairs), $m=5$ and $n=50$ for all datasets. See Appendix C.7 for more details about this.

Figure: Algorithm 4 JEIG

## Appendix C Experiments: More Details and Further Results

In this section, we describe the datasets in more detail and provide further experimental results. The experimental settings are identical to Section 4, unless otherwise specified.

### C.1 Maxmin and Maxexp

In this section, we explain the acquisition functions maxmin and maxexp introduced in [Aronsson and Chehreghani, ]. First, the transitive property implies if ${S}_{uv}\geq 0$ and ${S}_{uw}\geq 0$ then ${S}_{vw}\geq 0$ or if ${S}_{uv}\geq 0$ and ${S}_{uw}<0$ then ${S}_{vw}<0$. Then, assuming the ground-truth similarity matrix ${\bm{S}}^{\ast}$ is consistent (i.e., it does not violate transitive property) would imply that explicitly resolving (or preventing) the inconsistency in ${\bm{S}}$ may be informative. Both maxmin and maxexp are based on this idea.

Let $\mathcal{T}$ be the set of triples $(u,v,w)$ of distinct objects in $\mathcal{V}$, i.e., $|\mathcal{T}|={N\choose 3}$. Let $\mathcal{T}_{uv}=\{t\in\mathcal{T}\mid u,v\in t\}$ be the set of triples that include the pair $(u,v)$. Let $\mathcal{C}_{t}$ be the set of clustering solutions for the objects in the triple $t$. Finally, let $\mathcal{E}_{t}=\{(u,v)\in\mathcal{E}\mid u,v\in t\}$ be the set of pairs in the triple $t$, and $e_{t}=\operatorname*{arg\,min}_{(u,v)\in\mathcal{E}_{t}}|{S}_{uv}|$ is the pair in $\mathcal{E}_{t}$ with the smallest absolute similarity. Given this, maxmin is defined as(^1^11This formulation of maxmin is equivalent to Algorithm 3 of [Aronsson and Chehreghani, ], except the algorithm overcomes the computational issues of iterating all $N\choose 3$ triples.)

$$ $a^{\text{Maxmin}}(u,v)\triangleq\operatorname*{max}_{t\in\mathcal{T}_{uv}} \operatorname*{min}_{{\bm{c}}\in\mathcal{C}_{t}}R({\bm{c}}\mid\mathcal{E}_{t}) \bm{1}_{e_{t}=(u,v)},$ (29) $$

where $R({\bm{c}}\mid\mathcal{E}_{t})\triangleq\sum_{(u,v)\in\mathcal{E}_{t}}V(u,v
\mid{\bm{c}})$. Intuitively, maxmin begins by ranking each triple according to how much inconsistency they induce (i.e., violation of transitive property). Then, from each of the top-$B$ triples $t$, the pair in $\mathcal{E}_{t}$ with smallest absolute similarity is selected (i.e., most uncertain according to its similarity). The goal is thus to reduce inconsistency by resolving violations of the transitive property in triples. In our experiments, we observe that this can be ineffective, likely due to robustness to inconsistency in ${\bm{S}}$ by the CC algorithm used. See discussion in experiments for more details. From Eq. 29 we see that maxmin quantifies the inconsistency by the cost of the best clustering in $\mathcal{C}_{t}$ (in short, this cost is non-zero for triples that violate the transitive property, and zero otherwise). The maximization over $\mathcal{T}_{uv}$ ensures the most violating triple that includes the pair $(u,v)$ is considered. Maxexp works analogously to maxmin except the term $\operatorname*{min}_{{\bm{c}}\in\mathcal{C}_{t}}R({\bm{c}}\mid\mathcal{E}_{t})$ is replaced by an expectation of the cost of all clustering solutions in $\mathcal{C}_{t}$.

### C.2 Description of Datasets

A detailed description of all eight datasets used is provided below. Datasets 2-7 are taken from the UCI machine learning repository [Kelly et al., ] (all of which are released under the CC BY 4.0 license).

- 1.
CIFAR10 [Krizhevsky, ]. This dataset consists of 60000 $32\times 32$ color images in 10 different classes (with 6000 images per class). A random subset of $N=1000$ images (with $|\mathcal{E}|=499,500$) is used. Cluster sizes: [91, 96, 107, 89, 99, 113, 96, 93, 112, 104]. We set $|\mathcal{E}^{0}|=2500$. The batch size is set to $B=1250$.
- 2.
20newsgroups. This dataset consists of 18846 newsgroups posts (in the form of text) on 20 topics (clusters). We use a random sample of $N=1000$ posts (with $|\mathcal{E}|=499,500$). Cluster sizes: [46, 57, 45, 48, 63, 47, 48, 65, 51, 53, 39, 57, 46, 56, 65, 47, 52, 48, 38, 29]. We set $|\mathcal{E}^{0}|=2500$. The batch size is set to $B=2500$.
- 3.
Cardiotocography. This dataset includes 2126 fetal cardiotocograms consisting of 22 features and 10 classes. We use a sample of $N=1000$ data points (with $|\mathcal{E}|=499,500$). Cluster sizes: [180, 275, 27, 35, 31, 148, 114, 62, 28, 100]. We set $|\mathcal{E}^{0}|=2500$. The batch size is set to $B=750$.
- 4.
Ecoli. This is a biological dataset on the cellular localization sites of 8 types (clusters) of proteins which includes $N=336$ samples (with $|\mathcal{E}|=56,280$). Cluster sizes: [137, 76, 1, 2, 37, 26, 5, 52]. We set $|\mathcal{E}^{0}|=280$. The batch size is set to $B=85$.
- 5.
Forest Type Mapping. This is a remote sensing dataset of $N=523$ samples collected from forests in Japan and grouped in 4 different forest types (clusters) (with $|\mathcal{E}|=136,503$). Cluster sizes: [168, 84, 86, 185]. We set $|\mathcal{E}^{0}|=500$. The batch size is set to $B=350$.
- 6.
User Knowledge Modelling. This dataset contains 403 students’ knowledge status on Electrical DC Machines grouped in 4 classes (with $|\mathcal{E}|=81,003$). Cluster sizes: [111, 129, 116, 28, 19]. We set $|\mathcal{E}^{0}|=400$. The batch size is set to $B=200$.
- 7.
Yeast. This dataset consists of 1484 samples with 8 real-valued features and 10 clusters. We use a sample of $N=1000$ data points (with $|\mathcal{E}|=499,500$). Cluster sizes: [319, 4, 31, 17, 28, 131, 169, 271, 12, 18]. We set $|\mathcal{E}^{0}|=2500$. The batch size is set to $B=750$.
- 8.
Synthetic. This is a synthetically generated dataset with $N=500$ (and $|\mathcal{E}|=124,750$) data points split evenly into $10$ clusters. We set $|\mathcal{E}^{0}|=500$. The batch size is set to $B=300$.

### C.3 Further Results

Figure 3 shows the results for all datasets with noise level $\gamma=0.4$ using the adjusted rand index (ARI) metric. Figures 4 and 5 show the results for all datasets with the adjusted mutual information (AMI) metric for noise levels $\gamma=0.4$ and $\gamma=0.6$, respectively. All results are consistent with the insights from Figure 1 from the main paper, where all information-theoretic acquisition functions proposed in this paper outperform the baselines. In addition, we observe that the acquisition functions based on information gain consistently outperforms $a^{\text{Entropy}}$. Finally, we observe increased benefit of our acquisition functions for larger noise levels.

Figure: (a) Synthetic
Refer to caption: extracted/2402.03587v2/figures/rand_synthetic_0.4.png

Figure: (a) Synthetic
Refer to caption: extracted/2402.03587v2/figures/ami_synthetic_0.4.png

Figure: (a) Synthetic
Refer to caption: extracted/2402.03587v2/figures/ami_synthetic_0.6.png

### C.4 Small Batch Size

In Figure 6, we show results for a synthetic dataset with $N=70$ objects (and $|\mathcal{E}|=2415$ pairs) using a batch size of $B=5$. The noise level is $\gamma=0.4$. In this experiment, *we do not use any acquisition noise* in order to improve batch diversity. The purpose of this experiment is to further illustrate the benefit of the acquisition functions based on information gain compared to entropy, when differences due to batch diversity are (mostly) removed. We observe that $a^{\text{EIG-O}}$, $a^{\text{EIG-P}}$ and $a^{\text{JEIG}}$ outperform $a^{\text{Entropy}}$.

Figure: Figure 6: Results on synthetic dataset with $N=70$ and $|\mathcal{E}|=2415$ using a small batch size $B=5$ without any acquisition noise. The noise level is $\gamma=0.4$.
Refer to caption: extracted/2402.03587v2/figures/app/small.png

### C.5 Runtime

Figure: (a) Synthetic
Refer to caption: extracted/2402.03587v2/figures/time_select_batch_synthetic_0.4.png

Each active learning procedure was executed on 1 core of an Intel(R) Xeon(R) Gold 6338 CPU @ 2GHz (with 32 cores total). We have access to a compute cluster with many of these CPU’s allowing us to execute many procedures in parallell. Each CPU has access to 128GB of RAM (shared among cores), but much less would suffice for our experiments.

In Figure 7 we show the runtime of each iteration in seconds for all acquisition functions and datasets. We observe that $a^{\text{Entropy}}$ is very efficient (comparable to other baseline methods). In addition, we see that out of the acquisition functions based on information gain, $a^{\text{JEIG}}$ is the most efficient and is quite close to $a^{\text{Entropy}}$. Expectedly, $a^{\text{EIG-O}}$ and $a^{\text{EIG-P}}$ are the least efficient. This is because we run Alg. 2 numerous times (as discussed in Section B.2). Out of these two, $a^{\text{EIG-P}}$ is the most inefficient since it involves a sum over all $N\choose 2$ pairs (see Eq. 13) in each iteration of Alg. 3.

### C.6 Re-Querying of Pairs

Figure: (a) $\gamma=0.4$
Refer to caption: extracted/2402.03587v2/figures/app/time_rand.png

In Figure 8, we illustrate how all acquisition functions tend to re-query the same pair multiple times. The middle plot shows how many pairs are queried at each iteration that have already been queried at least once in previous iterations. The left plot shows the corresponding active learning curves w.r.t. the ARI metric. We observe that maxmin and maxexp perform many re-queries in most iterations. This is because the goal of both of these methods is to query pairs that cause inconsistency in ${\bm{S}}$. Very often, it will be pairs that have already been queried that are responsible for the inconsistency, due to noise in the oracle. However, we see that the information-theoretic methods make far less re-queries while performing much better. This indicates the information-theoretic methods are able to more effectively detect which pairs should be re-queried. In contrast, maxmin and maxexp perform a lot of unnecessary re-queries leading to worse performance.

Finally, the right plot shows the performance of each acquisition functions when re-querying is allowed (dashed line) compared to when it is not allowed (solid line). We observe that all information-theoretic acquisition functions perform roughly the same when re-queries are not allowed. In contrast, we see that maxexp does benefit from re-querying.

### C.7 Hyperparameters

In this section, we present a detailed analysis of all hyperparameters.

#### C.7.1 EIG

Figure: (a) EIG-O
Refer to caption: extracted/2402.03587v2/figures/app/eigo.png

In Figure 9, we show results for the acquisition functions $a^{\text{EIG-O}}$ (left) and $a^{\text{EIG-P}}$ (right) with different values of $|\mathcal{E}^{\text{EIG}}$|. See Alg. 3 for the usage of $\mathcal{E}^{\text{EIG}}$. We observe that the performance does not improve much beyond $|\mathcal{E}^{\text{EIG}}|=10N$. This indicates both of these acquisition functions will perform well when evaluation Eq. 12 or Eq. 13 for $O(N)$ of the pairs (instead of all $O(N^{2})$ pairs).

#### C.7.2 JEIG

Figure: (a) $m=5$, $n=50$
Refer to caption: extracted/2402.03587v2/figures/app/jeig1.png

In Figure 10, we show results for the acquisition function $a^{\text{JEIG}}$ when varying $m$, $n$ and $|\mathcal{D}_{i}|$. The left plot show results when varying $|\mathcal{D}_{i}|$ with $m$ and $n$ fixed to $5$ and $50$, respectively. As explained in Appendix B.3, each $\mathcal{D}_{i}$ is selected as the top-$|\mathcal{D}_{i}|$ pairs according to $\log(a^{\text{Entropy}}(u,v))+\epsilon_{uv}$ where $\epsilon_{uv}\sim\text{Gumbel}(0;1)$. The right plot show results when varying $m$ and $n$ with $|\mathcal{D}_{i}|$ fixed to $0.02|\mathcal{E}|$ (2% of all pairs). We observe that $|\mathcal{D}_{i}|=0.02|\mathcal{E}|$ performs the best. A smaller value means we do not capture enough information about each ${\textnormal{E}}_{uv}$ and a too large value leads to exaggerated selection bias, as explained at the end of Section 3.3.3. We find $|\mathcal{D}_{i}|=0.02|\mathcal{E}|$ to work well for all datasets considered in this paper. However, there may be other values that perform equally well (or better). Finally, we observe that larger values of $m$ and $n$ expectedly lead to better performance. A larger value of $m$ means we capture more information about each ${\textnormal{E}}_{uv}$. A larger value of $n$ means the Monte-Carlo estimation of the expectation $\mathbb{E}_{{\bm{e}}\sim P({\mathbf{E}}_{\mathcal{D}_{i}})}[H({\textnormal{E}}
_{uv}\mid{\mathbf{E}}_{\mathcal{D}_{i}}={\bm{e}})]$ becomes more accurate.

#### C.7.3 Concentration parameter β 𝛽 \beta italic_β

Figure: (a) Entropy
Refer to caption: extracted/2402.03587v2/figures/app/entropy_beta.png

In Figure 11, we show results for the information-theoretic acquisition functions $a^{\text{Entropy}}$, $a^{\text{EIG-O}}$ and $a^{\text{JEIG}}$ when varying the hyperparameter $\beta$. The parameter $\beta$ is a concentration parameter used in the definition of the Gibbs distribution from Eq. 2. As a consequence, it is also used in Alg. 2 (mean-field), which is frequently used in this paper. In this setting, $\beta$ is the well-known inverse temperature of a Gibbs distribution (having this parameter with a Gibbs distribution is very common). A large $\beta$ will concentrate more probability mass on a cluster $k$ with larger cost $M^{t}_{uk}$. A smaller $\beta$ will make the probabilities $Q^{t}_{uk}$ more uniform across different clusters. $\beta$ may therefore have an impact on the resulting clustering (i.e., assignment probabilities ${\bm{Q}}$ which is used by all information-theoretic acquisition functions). See [Chehreghani et al., ] for more details about the impact of $\beta$. We observe that a value of $\beta=3$ performs the best for all acquisition functions.

## Appendix D Max Correlation Clustering Algorithm

In this section, we describe the CC algorithm used in the active CC procedure outlined in Section 2.2. The algorithm was derived in [Aronsson and Chehreghani, ] based on the max correlation cost function $\Delta({\bm{c}}\mid{\bm{S}})\triangleq-\sum_{\begin{subarray}{c}(u,v)\in
\mathcal{E}\\
c_{u}=c_{v}\end{subarray}}{S}_{uv}$ introduced in Proposition 2.1.

The method is based on local search and is outlined in Alg. 5. It takes as input a set of objects $\mathcal{V}$, a similarity matrix ${\bm{S}}$, an initial number of clusters $K$, the number of repetitions $T$, and a stopping threshold $\eta$. In our experiments, we set $T=5$, $\eta=2^{-52}$ (double precision machine epsilon) and $K=|\mathcal{V}|$ in the first iteration of the active CC procedure, and then $K=K^{i}$ for all remaining iterations where $K^{i}$ denotes the number of clusters in the current clustering ${\bm{c}}^{i}$. The output is a clustering ${\bm{c}}\in\mathcal{C}$. The main part of the algorithm (lines 4-22) 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 4) consists of initializing the current clustering ${\bm{c}}$ randomly. Then, it loops for as long as the current *max correlation* objective changes by at least $\eta$ compared to the last iteration. If not, we assume it has converged to some (local) optimum. Each repetition consists of iterating over all the objects in $\mathcal{V}$ in a random order $\mathcal{V}_{\text{rand}}$ (this ensures variability between the $T$ runs). For each object $u\in\mathcal{V}_{\text{rand}}$, it calculates the similarity (correlation) between $u$ and all clusters $k\in\{1,\ldots,K\}$, which is denoted by $S_{k}(u)$. Then, the cluster $k_{\text{max}}$ that is most similar to $u$ is obtained. 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. Consequently, 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 each repetition the current max correlation objective is computed efficiently by only updating it based on the current change of the clustering ${\bm{c}}$ (i.e., lines 14 and 20). The computational complexity of the procedure is $O(KN^{2})$. See [Aronsson and Chehreghani, ] for additional details about how the algorithm was derived.

Figure: Algorithm 5 Max Correlation Clustering Algorithm $\mathcal{A}$ (dynamic $K$)

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: I don't understand why only noisy oracles are considered. I would like to know how the approach performs if the oracle returns the precise pair similarity. This is a realistic and practical use case and I think it should be considered. Would we be then able to obtain some approximation guarantees, maybe after assuming some properties of the acquisition function?
soundness: 4
strengths: - The considered problem is important and has practical applications.
- An interesting approach for the selection of object pairs whose similarity should be computed.
- Good experimental results.
summary: The paper presents a new approach to correlation clustering with a limited budget for similarity queries between pair objects. The main contribution is the design of new techniques (the so-called acquisition functions) for selecting object pairs whose similarity should be computed by a noisy oracle and which can then be used as input to a correlation clustering algorithm.
weaknesses: - The approach is just a heuristic, there are no approximation guarantees, not even an attempt to discuss the quality of approximation from a theoretic point of view.
- The writing can be improved. For example, Theorem 1 is not central to the presented approach, it is rather about an efficient approximation of Gibbs sampling. I think the presentation should first focus on the 4 acquisition functions and then explain how to approximate Gibbs sampling.
- I couldn't understand why only noisy oracles are considered, see my question below.

---

confidence: 2
contribution: 2
initial_rating: 3
presentation: 2
questions: The objective function, as outlined in Equations (1) and (2), aims to minimize clustering disagreement. However, the rationale behind the objective function is somewhat unclear, as it appears that clustering disagreement may also be influenced by the scale of the data points.

The main theoretical guarantee presented is a local minimum in Theorem 3.1, though it is unclear how this guarantee compares to those in existing literature. 

It would be helpful to understand the authors' considerations regarding the number of clusters, as how to infer the number of clusters from the structure of the similarity matrix graph.

How do authors define "budget" in Algorithm 1? In Algorithm 2 (on page 5), the criteria for defining the convergence of Q in Step 2 remain unclear.
soundness: 2
strengths: The paper addresses an interesting problem: mapping data points into distinct clusters with high accuracy by querying the similarity between them a limited number of times. 

The experimental results are a positive aspect of a theoretical paper.
summary: The paper addresses an interesting problem: mapping data points into distinct clusters with high accuracy by querying the similarity between them a limited number of times. The objective function, as outlined in Equations (1) and (2), aims to minimize clustering disagreement. However, the rationale behind the objective function is somewhat unclear, as it appears that clustering disagreement may also be influenced by the scale of the data points.

The main theoretical guarantee presented is a local minimum in Theorem 3.1, though it is unclear how this guarantee compares to those in existing literature. Additionally, it would be helpful to understand the authors' considerations regarding the number of clusters, as how to infer the number of clusters from the structure of the similarity matrix graph.

Notably, this approach diverges from the usual practice of providing a guarantee for the distance between ground truth and predicted cluster centers. Achieving the guarantee in Theorem 3.1 involves multiple steps of relaxation by introducing concepts such as information gain, entropy, and mean-field approximation, which raises questions about the accuracy of the theorem.

The technical details in Algorithms 1 and 2 are not discussed. Algorithm 1 (on page 4) queries similarity through an oracle, producing a similarity matrix with both positive and negative values. A positive value indicates that a data pair belongs to the same class, while a negative one implies otherwise. This differs from the standard approach of thresholding positive similarity values, so I am curious about how this algorithm would perform in real-world applications. Additionally, the "budget," a critical parameter, is not discussed. In Algorithm 2 (on page 5), the criteria for defining the convergence of Q in Step 2 remain unclear.

The experimental results are a positive aspect of a theoretical paper.
weaknesses: It is not clear if the objective function makes sense. The objective function, as outlined in Equations (1) and (2), aims to minimize clustering disagreement. However, the rationale behind the objective function is somewhat unclear, as it appears that clustering disagreement may also be influenced by the scale of the data points.


The technical details in Algorithms 1 and 2 are not discussed. For example, the "budget" in Algorithm 1 (on page 4)  a critical parameter, is not discussed.  In Algorithm 2 (on page 5), the criteria for defining the convergence of Q in Step 2 remain unclear.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: How does the cluster imbalance impact the performance of the proposed method?
soundness: 3
strengths: The authors proposed novel information-theoretic acquisition functions to active correlation clustering. Mean-field approximations are derived for these functions.

The paper presents comprehensive empirical validation across diverse datasets. The authors discuss how noisy oracles with different types impact the performance of the model. 

The authors utilize clear mathematical notation and describe the algorithms in detail. The comprehensive appendices provide details in the implementation and in the experiments.
summary: This manuscript presents information-theoretic acquisition functions for active correlation clustering, where pairwise similarities are queried from an oracle to construct clusters. The authors introduce four acquisition functions: Entropy, EIG-O, EIG-P, and JEIG. mean-field approximations are adopted to make computations tractable. Through extensive experiments across multiple datasets and noisy oracles of various types, the proposed approaches show superior performance compared to existing methods.
weaknesses: This manuscript proposes a correlation clustering method that operates solely on pairwise similarities, without utilizing sample features. A significant limitation is the method's extensive labeling requirements. As shown in the experiments, for datasets with no more than 1,000 samples, thousands of pairwise labels are needed to achieve acceptable performance. This high labeling burden makes the method impractical for real-world applications, where collecting pairwise labels is typically more resource-intensive than collecting instance-level labels. Given these practical constraints, the paper's impact is likely to be limited despite its contributions.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: Please See Weaknesses.
soundness: 3
strengths: Strengths:
1. The idea of information-theoretic active correlation clustering together with the mean-field approximation is interesting. 
2. The experimental results are good.
3. The presentation and organization are good.
summary: This paper proposes an active correlation clustering method based on information theory. It applies the mean-field approximation to approximate the Gibbs distribution and proposes four acquisition functions for active correlation clustering based on the approximation.
weaknesses: Weaknesses and Questions:
1. The setting where we can only access to noisy similarities of some pairs is interesting. However, it would be better to introduce some application scenarios in real world, and apply at least one of the real-world data sets in the experiments instead of synthetically adding some noises to the ground truth, because the oracles used in the experiments may not follow the distribution of real-world noises. 

2. The mean-field approximation method seems similar to the widely-used variational inference. What are the differences between the mean-field approximation and variational inference?

3. In many data sets, the paper only uses a subset. Why not use the whole data set? Cannot the proposed method handle large-scale data sets?

4. In some data sets of Figures 1 and 2, the results seem incomplete. For example, in Figure 1(g) and 1(h), the results of EIG-O and EIG-P are missing. Why?

Meta-review: This paper aims to design correlation clustering methods with a limited number of queries for pairwise similarities between objects.  It introduces active learning and devises four information-theoretic acquisition functions. Specially, it utilizes mean-field approximation to approximate complex quantities and encodes the mean-field approximation using a matrix of assignment probabilities. Experimental results on eight public datasets illustrate the effectiveness. After rebuttal, this manuscript receives divergent scores. Although reviewer gKTJ provides a positive score, he/she acknowledges that his support is lukewarm. 


After reviewer discussion, they hold that this manuscript seems to be a practical work and does not balance theoretical insights with practical application. The mean-field approximation scheme seems similar to the commonly used variational inference. Also, the writing can be improved. In view of these, the authors are encouraged to develop more theories to enrich this manuscript in the future.

Decision: Reject