# Deep Clustering with Incomplete Noisy Pairwise Annotations: A Geometric
Regularization Approach

Tri Nguyen  Shahana Ibrahim  Xiao Fu

###### Abstract

The recent integration of deep learning and pairwise similarity annotation-
based constrained clustering—i.e., deep constrained clustering (DCC)—has
proven effective for incorporating weak supervision into massive data
clustering: Less than 1% of pair similarity annotations can often
substantially enhance the clustering accuracy. However, beyond empirical
successes, there is a lack of understanding of DCC. In addition, many DCC
paradigms are sensitive to annotation noise, but performance-guaranteed noisy
DCC methods have been largely elusive. This work first takes a deep look into
a recently emerged logistic loss function of DCC, and characterizes its
theoretical properties. Our result shows that the logistic DCC loss ensures
the identifiability of data membership under reasonable conditions, which may
shed light on its effectiveness in practice. Building upon this understanding,
a new loss function based on geometric factor analysis is proposed to fend
against noisy annotations. It is shown that even under unknown annotation
confusions, the data membership can still be provably identified under our
proposed learning criterion. The proposed approach is tested over multiple
datasets to validate our claims.

constrained clustering, matrix completion, identifiability

##  1 Introduction

Clustering is one of the most prominent unsupervised learning tasks (Jain &
Dubes, 1988). Classic clustering paradigms, e.g., K-means and spectral
clustering, are designed to work without any label information. In practice,
it was observed that limited supervision may significantly boost the
clustering performance. The so-called constrained clustering (CC) method
(Wagstaff & Cardie, 2000) is one of such weak (or semi-)supervised approaches.
The CC paradigm has many variants (see (Basu et al., 2008; Schultz & Joachims,
2003; Yeung & Yeo, 1996; Davidson et al., 2010; Zhang et al., 2019, 2021)).
The arguably most widely used paradigm annotates the similarity (using binary
codes) of data pairs and restrains the clustering outcomes to respect these
pairwise constraints; see, e.g., (Basu et al., 2004a; Segal et al., 2003;
Wagstaff et al., 2001; Givoni & Frey, 2009; Hsu & Kira, 2015; Manduchi et al.,
2021). Note that annotating similarity is considerably easier than annotating
the exact class labels of data, yet it was observed that such “simple”
annotations could boost the performance of data categorization. These findings
may assist designing economical annotation mechanisms in the era of data
explosion.

Early CC approaches are often combined with existing clustering modules like
K-means (Basu et al., 2004a; Wagstaff et al., 2001; Bilenko et al., 2004; Li
et al., 2009; Kamvar et al., 2003; Wang et al., 2014; Cucuringu et al., 2016).
The pairwise annotations are used to construct regularization terms that are
similar to graph-Laplacian based regularization. Variants using Bayesian
perspectives were also proposed (Basu et al., 2004b; Law et al., 2005). These
methods were observed to largely outperform their unsupervised counterparts,
e.g., K-means and spectral clustering, even only as few as 1% of the pairs are
annotated.

In recent years, clustering modules and deep neural network-based feature
extractors are proposed to be learned jointly—leading to the so-called end-to-
end deep clustering approaches; see, e.g., (Yang et al., 2017; Caron et al.,
2018). These methods use clustering structures in the latent space to
regularize the neural networks, and the neural networks offers enhanced
transformation power to find latent spaces where the data can be well
clustered. The CC methods also benefited from similar ideas. The so-called
deep constrained clustering (DCC) approaches were proposed in (Zhang et al.,
2019, 2021; Manduchi et al., 2021), and substantial performance enhancement
relative to classic CC methods was observed.

Although the DCC methods have enjoyed empirical successes, some notable
challenges remain. First, there is a general lack of understanding to the
effectiveness of DCC. It is unclear under what conditions the loss functions
constructed for DCC could succeed or fail in finding the ground-truth cluster
membership of the data entities. However, understanding the identifiability of
the membership is critical for designing principled and robust DCC systems.
The interplay of key aspects, e.g., neural network complexity and the
generalization ability of the learned feature extractor, in the context of DCC
is also of great interest—yet no pertinent study exists. Second, most of the
existing (D)CC methods (implicitly) assumed that annotations are accurate;
see, e.g., (Basu et al., 2004a; Wagstaff et al., 2001; Li et al., 2009; Zhang
et al., 2019; Ren et al., 2019; Hsu et al., 2018). Hence, many of these
methods may not be robust to annotation noise. This is particularly
detrimental to DCC methods as large over-parameterized neural models easily
overfit (Du et al., 2019). Some works took noisy annotations into
consideration (e.g., (Luo et al., 2018; Manduchi et al., 2021)), but no
guarantees of recovering the cluster membership.

##### Contributions.

In this work, we take a deeper look at the DCC problem from a membership-
identifiability analysis viewpoint. Our contribution is twofold:

First, we re-examine a recently emerged effective loss function of DCC,
namely, the logistic loss-based DCC criterion, which was proposed by (Hsu et
al., 2018; Zhang et al., 2021). We show that, if the pairwise annotations are
generated following a model that is reminiscent of the mixed-membership
stochastic blockmodel (MMSB) (Airoldi et al., 2008; Huang & Fu, 2019), then,
the logistic loss can provably recover (i) the data entities’ cluster
membership and (ii) the nonlinear function that maps the data features to the
membership indicator for both seen and unseen data—and thus generalization of
the learned neural network is guaranteed.

Second, using our understanding, we propose a noisy annotation-robust version
of logistic loss for DCC. We explicitly model the annotators’ confusion as a
probability transition matrix, which is inspired by classic noisy label
analysis such as the Dawid-Skene model (Dawid & Skene, 1979; Ghosh et al.,
2011; Zhang et al., 2014). We propose a geometric factor analysis (Fu et al.,
2018, 2019) based learning criterion to provably ensure the identifiability of
the ground-truth cluster membership, in the presence of annotation confusion.

We test our method over a series of DCC tasks and observe that the proposed
approach significantly improves the performance over existing paradigms,
especially when annotation noise exists. Our finding shows the significance of
identifiability in DCC, echoing observations made in similar semi-
supervised/unsupervised problems, e.g., (Arora et al., 2013; Kumar et al.,
2013; Anandkumar et al., 2014; Zhang et al., 2014). We also evaluate the
algorithms using real data collected through the Amazon Mechanical Turk (AMT)
platform. The code is published at github.com/ductri/VolMaxDCC.

##### Notation.

We use $x$, $\bm{x}$ and $\bm{X}$ to denote scalar, vector and matrix,
respectively; both $[\bm{x}]_{k},x_{k}$ refer to the $k$th element of vector
$\bm{x}$; $X_{ij}$ (and $[\bm{X}]_{i,j}$) is the element in the $i$th row and
$j$th column of $\bm{X}$; $\bm{I}_{K}$ denotes the identity matrix of size
$K$; $\bm{0}$ and $\bm{1}$ are all-zero and all-one matrices with proper
sizes; $\langle\bm{x},\bm{y}\rangle$ and $\langle\bm{X},\bm{Y}\rangle$ denote
dot products between two vectors and two matrices, respectively;
$\left\lVert\bm{x}\right\rVert$ denotes the $\ell_{2}$-norm;
$\left\lVert\bm{X}\right\rVert_{\rm F}$ and
$\left\lVert\bm{X}\right\rVert_{2}$ denote the Frobenius norm and spectral
norm of $\bm{X}$, respectively; $\sigma_{\max}(\bm{X}),\sigma_{\min}(\bm{X})$,
and $\sigma_{i}(\bm{X})$ represent the largest, the smallest, and the $i$th
singular value of matrix $\bm{X}$, respectively; $[N]$ is the set of natural
numbers from 1 to $N$, i.e., $[N]=\\{1,\ldots,N\\}$; $[N]\times[N]$ denotes
the set of all possible pairs of $(i,j)$ where $i\in[N],j\in[N]$; ${\rm
cone}(\bm{X})$ to denote conic hull of the column vectors of $\bm{X}$, i.e.,
${\rm
cone}(\bm{X})=\left\\{\bm{y}\mid\bm{y}=\bm{X}\bm{\theta},\bm{\theta}\geq\bm{0}\right\\}$.

##  2 Background

##### Problem Setting.

We consider the CC setting as follows: There are $N$ data samples
$\bm{x}_{1},\ldots,\bm{x}_{N}$. Each sample belongs to one or multiple
clusters of in total $K$ clusters. The association of $\bm{x}_{n}$ with the
clusters is represented by a vector $\bm{m}_{n}\in\mathbb{R}^{K}$. The element
$[\bm{m}_{n}]_{k}$ represents the probability that data $n$ belongs to cluster
$k$. Note that in hard clustering, $[\bm{m}_{n}]_{k}\in\\{0,1\\}$ for all
$k\in[K]$, which means the clusters have no overlaps. In more general cases,
we have

$\displaystyle\bm{1}^{\\!\top\\!}\bm{m}_{n}=1,~{}\bm{m}_{n}\geq\bm{0}.$ (1)

A collection of $M$ pairwise annotations are available, which are denoted by
$(i_{1},j_{1},y_{1}),\ldots,(i_{M},j_{M},y_{M})$. Here,

$\displaystyle y_{m}=\begin{cases}1,~{}&\text{$\bm{x}_{i_{m}},\bm{x}_{j_{m}}$
are ``similar''},\\\ 0,~{}&\text{otherwise},\end{cases}$ (2)

where the similarity of the membership of $\bm{x}_{i_{m}}$ and
$\bm{x}_{j_{m}}$ is often deemed by an annotator. Note that there are in total
$N(N-1)/2$ such data pairs, and we often have

$M\ll N(N-1)/2;$

that is, only a small portion of the data pairs are annotated. The objective
of pairwise annotation-based CC is to find the cluster membership vector
$\bm{m}_{n}$ of each $\bm{x}_{n}$ using the data and the $M$ annotations.

##### Early CC Methods.

The task of clustering with the pairwise constraints can be dated back to the
early 2000s, where (Wagstaff & Cardie, 2000; Wagstaff et al., 2001) used the
pairwise annotations to impose extra constraints of the classic K-means
iterations. The work (Basu et al., 2004a) considered using pairwise
annotation-induced “soft” constraints (or, regularization terms) to modify
K-means; see similar ideas in (Bilenko et al., 2004). Instead of modifying
K-means, another line of approaches proposed to work with pairwise constraints
under the spectral clustering framework. The idea is to incorporate the
pairwise annotation-based constraints into the construction of the graph
affinity matrix; see, e.g., (Kulis et al., 2005; Lu & Carreira-Perpinan, 2008;
Li et al., 2009; Cucuringu et al., 2016).

##### DCC Developments.

In recent years, deep neural network-based feature extractors were proposed to
combine with CC—leading to the deep constrained clustering (DCC) paradigms,
e.g., (Manduchi et al., 2021; Luo et al., 2018; Zhang et al., 2019, 2021). In
DCC, a deep neural network (DNN) $\bm{f}_{\bm{\theta}}(\cdot)$ is used to link
the data vector $\bm{x}_{n}$ with its membership, i.e.,

$\bm{m}_{n}=\bm{f}_{\bm{\theta}}(\bm{x}_{n}).$

The use of DNN helps nonlinearly transform the data to spaces that are
“friendly” to clustering (Yang et al., 2017). Learning
$\bm{f}_{\bm{\theta}}(\cdot)$ also allows the neural network to generalize to
unseen data. By (1),

$\bm{m}_{i_{m}}^{\\!\top\\!}\bm{m}_{j_{m}}\in[0,1]$

can be considered as the probability that $\bm{x}_{i_{m}}$ and
$\bm{x}_{j_{m}}$ belong to the same cluster, i.e., $y_{m}\sim{\sf
Bernoulli}(\bm{m}_{i_{m}}^{\\!\top\\!}\bm{m}_{j_{m}})$. From this perspective,
recent works have proposed an extension of logistic regression to incorporate
pairwise annotations (Hsu et al., 2018; Zhang et al., 2019, 2021):

$\displaystyle{\sf Loss}_{\rm
cc}(\bm{\theta})=\dfrac{1}{M}\sum^{M}_{m=1}\Big{(}y_{m}\log\dfrac{1}{\bm{f}_{\bm{\theta}}(\bm{x}_{i_{m}})^{{\\!\top\\!}}\bm{f}_{\bm{\theta}}(\bm{x}_{j_{m}})}+$
(3)
$\displaystyle(1-y_{m})\log\dfrac{1}{1-\bm{f}_{\bm{\theta}}(\bm{x}_{i_{m}})^{{\\!\top\\!}}\bm{f}_{\bm{\theta}}(\bm{x}_{j_{m}})}\Big{)}.$

In the literature, the ${\sf Loss}_{\rm cc}$ term is sometimes used with other
loss functions; e.g., (Zhang et al., 2019, 2021) used an overall loss function
consisting of two terms:

$\displaystyle\operatorname*{\textrm{minimize}}~{}{\sf Loss}_{\rm
recon}+\lambda{\sf Loss}_{\rm cc},$ (4)

where $\lambda\geq 0$ and the reconstruction loss ${\sf Loss}_{\rm recon}$ was
realized using an autoencoder. Such combination is advocated for practical
reasons, e.g., utilizing all available data. Nonetheless, as we will show,
${\sf Loss}_{\rm cc}$ itself suffices to offer strong guarantees under
reasonable conditions.

##### Challenges.

Although there have been abundant empirical evidence demonstrating the
effectiveness of CC and DCC, theoretical understanding has been largely
behind. This is particularly obvious for the DCC case, where aspects such as
the identifiability of $\bm{m}_{n}$ and the generalization ability of the
learned $\bm{f}_{\bm{\theta}}(\cdot)$ are of great interest—yet no theoretical
support exists, to our best knowledge.

Another challenge lies in noise robustness. Although it has been widely
observed that noisy annotations could greatly impact the performance of CC and
DCC (Liu et al., 2017; Covoes et al., 2013; Pelleg & Baras, 2007; Manduchi et
al., 2021; Luo et al., 2018; Chang et al., 2017b; Zhang et al., 2021; Zhu et
al., 2015), effective solutions—especially performance-guaranteed ones—for
handling this problem have been largely lacking. Many works did test their
algorithms with noisy labels (see, e.g., (Cucuringu et al., 2016; Wang et al.,
2014)), but no special care was taken to alleviate the impact of such noisy
labels. Some heuristics—such as pre-processing the data (Yi et al., 2012),
modeling annotation uncertainties (Manduchi et al., 2021), and introducing
concepts reflecting human behaviors (Luo et al., 2018; Chang et al., 2017b)
and annotators’ accuracy (Luo et al., 2018; Chang et al., 2017b)—were also
proposed in the literature. However, performance guarantees have been elusive.

##  3 DCC Loss Revisited: Identifiability and Generalization

In this section, we take a deeper look into the DCC loss in (3) and understand
its theoretical properties. Such understanding will allow us to design a
performance-guaranteed new DCC loss in the presence of noisy pairwise
annotations.

###  3.1 A Generative Model of Annotations

To better present the results, in this section, we use the superscript
“$\natural$” to denote all the ground-truth terms; e.g.,
$\bm{f}^{\natural}(\cdot)$ denotes the ground-truth nonlinear mapping from
data to membership and $\bm{m}_{n}^{\natural}=\bm{f}^{\natural}(\bm{x}_{n})$
denotes the ground-truth membership vector of sample $n$. We propose to employ
the following generative model of $y_{m}$: Given
$\bm{x}_{1},\ldots,\bm{x}_{N}\sim\mathcal{P}_{\mathcal{X}},\bm{x}_{n}\in\mathcal{X}$,

$\displaystyle\text{$i,j$ are sampled over $[N]\times[N]$ };$ (5a)
$\displaystyle\text{$\bm{m}_{i}^{\natural}=\bm{f}^{\natural}(\bm{x}_{i})$ and
$\bm{m}_{j}^{\natural}=\bm{f}^{\natural}(\bm{x}_{j})$};$ (5b)
$\displaystyle\text{$y_{i,j}\sim{\sf
Bernoulli}({\langle}\bm{m}_{i}^{\natural},\bm{m}_{j}^{\natural}{\rangle})$}.$
(5c)

Note that the logistic loss in (3) is the maximum likelihood estimator (MLE)
of the parameters in the generative model. The model is reminiscent of the
classic generative models of logistic regression and network analysis,
particularly, MMSB (Airoldi et al., 2008). In MMSB, the nonlinear mapping from
the data features to the membership vectors were not considered. Incorporating
the nonlinear mapping $\bm{f}^{\natural}$ follows the ideas from supervised
learning, where the relationship between the data features and the data class
is often modeled as the following conditional probability represented by
$\bm{f}^{\natural}$ (Shalev-Shwartz & Ben-David, 2014):

$[\bm{m}^{\natural}_{n}]_{k}={\sf
Pr}(y=k|\bm{x}_{n})=[\bm{f}^{\natural}(\bm{x}_{n})]_{k}.$

Once $\bm{f}^{\natural}$ is learned, it can be used as a multi-class
classifier. This perspective was also mentioned in (Hsu et al., 2018; Zhang et
al., 2019, 2021)—for algorithm design purpose. However, membership
identifiability was not addressed.

In this section, we will show that the logistic loss (3) ensures identifying
the membership vectors $\bm{m}_{n}$ under the generative model in (5). It also
ensures that $\bm{f}_{\bm{\theta}}\approx\bm{f}^{\natural}$, under reasonable
conditions. These findings may shed some light onto the effectiveness and good
generalization performance of DCC using (3) in the literature.

###  3.2 Performance Analysis

##### Finite-Sample Identifiability and Generalization.

We first show that ${\sf Loss}_{cc}$ is a sound criterion for identifying
$\bm{m}_{n}^{\natural}$ and $\bm{f}^{\natural}(\cdot)$ by itself.
Specifically, let us denote

$\bm{\theta}^{\star}=\arg\min_{\bm{\theta}}{\sf Loss}_{\rm cc}(\bm{\theta})$
(6)

and ${\bm{f}}^{\star}=\bm{f}_{{\bm{\theta}}^{\star}}$. Here,
$\bm{f}_{\bm{\theta}}$ is represented by a deep neural network. To be more
specific, we consider $\bm{f}_{\bm{\theta}}$ belonging to a function class
$\mathcal{F}$ defined by

$\mathcal{F}\triangleq\left\\{\texttt{softmax}(\texttt{net}(\bm{x};\bm{\theta}))~{}|~{}\forall\bm{x}\in{\cal
X}\right\\},$

where $\texttt{net}(\cdot;\bm{\theta})$ is a neural network that maps $\bm{x}$
to $\mathbb{R}^{K}$, and
$[\texttt{softmax}(\bm{x})]_{k}\triangleq\exp(x_{k})/\sum^{K}_{\ell=1}\exp(x_{\ell})$
is imposed onto the output layer of the neural network, which is used to
reflect the constraints in (1).

We will show that ${\bm{f}}^{\star}\approx\bm{f}^{\natural}$ and
${{\bm{m}}^{\star}_{n}={\bm{f}}^{\star}(\bm{x}_{n})\approx\bm{m}_{n}^{\natural}}$
under reasonable conditions. To proceed, let us invoke the following
assumptions:

######  Assumption 3.1 (Anchor Sample Condition (ASC)).

Let $\bm{m}_{n}^{\natural}=\bm{f}^{\natural}(\bm{x}_{n})$,
$\bm{M}^{\natural}=[\bm{m}^{\natural}_{1},\ldots,\bm{m}^{\natural}_{N}]$.
$\bm{M}^{\natural}$ satisfies ASC if there exists a set $\mathcal{K}$ of $K$
indices such that $\bm{M}^{\natural}[:,\mathcal{K}]=\bm{I}$. Accordingly,
define
$\bm{V}^{\natural}\triangleq\bm{M}^{\natural}[:,\mathcal{K}^{c}],\mathcal{K}^{c}\triangleq[N]\setminus\mathcal{K}$.

######  Assumption 3.2.

(Function Class) There exist $0<\nu<1$ and $\widetilde{\bm{f}}\in\mathcal{F}$
such that

$\displaystyle\left\lVert\widetilde{\bm{f}}(\bm{x})-\bm{f}^{\natural}(\bm{x})\right\rVert\leq\nu,\forall\bm{x}\in\mathcal{X}.$
(7)

In addition,
$\alpha<\bm{f}(\bm{x})^{{\\!\top\\!}}\bm{f}(\bm{y})<1-\alpha,\;\forall\bm{x},\bm{y}\in\mathcal{X},\forall\bm{f}\in\mathcal{F}$,
for some $0<\alpha<1$. The complexity measure of the neural network
$\texttt{net}(\bm{x};\bm{\theta})$ is $R_{\texttt{NET}}$.

The ASC means that there exist samples that solely belong to a single cluster,
which are called the anchor samples. This assumption is reminiscent of the
anchor point assumption in the community detection literature (Panov et al.,
2017; Mao et al., 2017). Condition (7) takes the approximation error of the
employed neural network class ${\cal F}$ into consideration. The assumption on
$\alpha$ is a regularity condition that prevents pathological unbounded cases
of the logistic loss from happening. The constant $R_{\texttt{NET}}$ is
proportional to the upper bound of the so-called spectral complexity in
(Bartlett et al., 2017). A formal definition of $R_{\texttt{NET}}$ is given in
Lemma A.10. The parameters $\nu$ and $R_{\texttt{NET}}$ present a tradeoff:
Roughly speaking, if one has a deeper and wider neural network, then $\nu$ is
smaller—but $R_{\texttt{NET}}$ is bigger.

Define $\bm{P}^{\natural}\in\mathbb{R}^{N\times N}$ such that
$P^{\natural}_{ij}=\langle\bm{f}^{\natural}(\bm{x}_{i}),\bm{f}^{\natural}(\bm{x}_{j})\rangle$,
$\bm{P}^{\star}\in\mathbb{R}^{N\times N}$ such that
$P^{\star}_{ij}=\langle\bm{f}^{\star}(\bm{x}_{i}),\bm{f}^{\star}(\bm{x}_{j})\rangle$,
and
$\bm{S}_{\bm{X}}=[\bm{x}_{i_{1}},\bm{x}_{j_{1}},\ldots,\bm{x}_{i_{M}},\bm{x}_{i_{M}}]$.
We first show that the matrix $\bm{P}^{\natural}$ is approximately recoverable
via minimizing (3):

######  Lemma 3.3.

Let $S=\left\\{(i_{1},j_{1},y_{1}),\ldots,(i_{M},j_{M},y_{M})\right\\}$, where
$(i_{1},j_{1}),\ldots,(i_{M},j_{M})$ are drawn independently and uniformly at
random from $[N]\times[N]$. Suppose that ${y_{m}\mid(i_{m},j_{m})\sim{\sf
Bernoulli}(P^{\natural}_{i_{m},j_{m}})}$ following the generative model in (5)
and that ${\cal F}$ satisfies Assumption 3.2. Then, with probability at least
$1-\delta$, we have

$\dfrac{1}{N^{2}}\left\lVert\bm{P}^{\star}-\bm{P}^{\natural}\right\rVert_{\rm
F}^{2}\leq\epsilon(M,\delta)^{2},$

where $\epsilon(M,\delta)^{2}$ is defined as follows:

$\displaystyle\epsilon(M,\delta)^{2}\triangleq\dfrac{64\log(1/\alpha)}{M}+\dfrac{96\sqrt{2}\log
M}{\alpha M\log 2}\left\lVert\bm{S}_{\bm{X}}\right\rVert_{\rm
F}\sqrt{R_{\texttt{NET}}}$ (8)
$\displaystyle+64\log(1/\alpha)\sqrt{\dfrac{2\log(4/\delta)}{M}}+\dfrac{16\nu}{\alpha}.$

The proof of Lemma 3.3 is relegated to Appendix A. It is not surprising that
$\bm{P}^{\natural}$ can be recovered from minimizing the logistic loss, as the
problem of recovering $\bm{P}^{\natural}$ can be regarded as a generalized
1-bit matrix completion (MC) problem. Unlike the conventional 1-bit MC
frameworks that leveraged the low-rank structure of the complete data (see,
e.g., (Davenport et al., 2014)), here we exploit the neural generative model
in (5), which is also a low-dimensional model, as long as $R_{\texttt{NET}}$
is sufficiently small (compared to $M$ and $N$).

Before proceeding to showing recovery of $\bm{M}^{\natural}$, let us observe
the following fact based on Lemma 3.3: It can be seen in (8) that
$\epsilon(M,M^{-0.5})^{2}$ is decreasing with a rate of
$\mathcal{O}(\sqrt{(\log M)/M})$, hence there exists $M_{0}\in\mathbb{N}$
independent to $N$ such that $\;\forall M>M_{0}$,

$\epsilon^{\prime}(M)^{2}\triangleq
M^{0.25}\epsilon(M,M^{-0.5})^{2}+M^{-0.25}\leq\dfrac{1}{8K^{2}}.$ (9)

Using the above fact, we show that

######  Theorem 3.4.

Under the same assumptions as in Lemma 3.3, further assume that Assumption 3.1
is satisfied. Let
${\bm{M}^{\star}=[\bm{f}^{\star}(\bm{x}_{1}),\ldots,\bm{f}^{\star}(\bm{x}_{N})]}$,
and consider $M>M_{0}$, then there exists a permutation matrix
$\bm{\Pi}^{\star}$ such that

$\dfrac{1}{NK}\left\lVert\bm{\Pi}^{\star}\bm{M}^{\star}-\bm{M}^{\natural}\right\rVert_{\rm
F}^{2}\leq\frac{4N}{K}\epsilon(M,\delta)^{2}\\\
+\dfrac{2K}{N}(1+8\sigma_{\max}^{2}(\bm{V}^{\natural}))\epsilon^{\prime}(M),$

holds with probability at least $1-\delta-K^{2}/M^{0.25}$, where
$\epsilon^{\prime}(M)$ is defined in (9).

The proof of Theorem 3.4 is in Appendix B. We should mention that the sample
complexity in Theorem 3.4 is based on a worst-case analysis, and thus the
bound tends to be pessimistic—it starts to make sense when

$N\leq{\cal O}(K\sqrt{M}),$

as reflected in the first term on the right hand side. In practice, ${\sf
Loss}_{\rm cc}$ can work fairly well using a much smaller $M$. Nonetheless,
Theorem 3.4 for the first time shows the soundness of using ${\sf Loss}_{\rm
cc}$ in (3), in terms of being able to guarantee the identifiability of
$\bm{M}^{\natural}$.

With Theorem 3.4, it is readily to show the following:

######  Theorem 3.5 (Generalization).

Under the same conditions as in Theorem 3.4, with probability at least
$1-\delta-K^{2}/M^{1/4}$,

$\mathop{\mathbb{E}}_{\bm{x}\sim\mathcal{P}_{\mathcal{X}}}\left[\frac{1}{K}\left\lVert\bm{\Pi}^{\star}\bm{f}^{\star}(\bm{x})-\bm{f}^{\natural}(\bm{x})\right\rVert^{2}\right]\leq\frac{4N}{K}\epsilon(M,\delta)^{2}\\\
+\dfrac{2K}{N}(1+8\sigma_{\max}^{2}(\bm{V}^{\natural}))\epsilon^{\prime}(M)\\\
+\dfrac{4}{NK}+\dfrac{12\sqrt{2R_{\texttt{NET}}}\left\lVert\bm{X}\right\rVert_{\rm
F}\log N}{NK\log 2}+8\sqrt{\dfrac{2\log(4/\delta)}{NK^{2}}}.$

See the proof in Appendix C. Theorem 3.5 confirms that the learned
$\bm{f}^{\star}$ via minimizing ${\sf Loss}_{\rm cc}$ can generalize to
classify unseen data, which was observed in the literature (Hsu et al., 2018;
Zhang et al., 2019, 2021) but never formally shown.

##### Enhanced Identifiability with Large Sample.

In Theorem 3.4, the identifiability of $\bm{M}^{\natural}$ was established
under finite samples. The proof relies on the ASC. One may argue that the
anchor samples may not exist in some cases, as some data naturally exhibit
mixed membership, e.g., social network users (Airoldi et al., 2008) and multi-
topic documents (Blei et al., 2003). Here, we relax the finite sample
assumption to show that at the limit of large $M$, the logistic loss enjoys
enhanced membership identifiability that does not hinge on the ASC.

To see this, let us introduce the following condition:

######  Assumption 3.6 (Sufficiently Scattered Condition (SSC)).

Let $\bm{m}_{n}^{\natural}=\bm{f}^{\natural}(\bm{x}_{n})$,
$\bm{M}^{\natural}=[\bm{m}^{\natural}_{1},\ldots,\bm{m}^{\natural}_{N}]$.
$\bm{M}^{\natural}$ satisfies SSC if there exists a subset ${\cal S}\in[N]$
such that

${\cal C}\subseteq{{\rm cone}}(\bm{M}^{\natural}[:,{\cal S}]),$

where ${\cal
C}=\left\\{\bm{x}\in\mathbb{R}^{K}\mid\sqrt{K-1}\left\lVert\bm{x}\right\rVert\leq\bm{1}^{{\\!\top\\!}}\bm{x}\right\\}$,
and ${\rm cone}(\bm{M}^{\natural}[:,\mathcal{S}])\subseteq{\rm cone}(\bm{Q})$
does not hold for any orthogonal $\bm{Q}$ except for the permutation matrices.

Membership $\bm{m}^{\natural}_{n}$’s
---
${\rm cone}(\bm{M}^{\natural}[:,{\cal S}])$
---
${\cal C}$
---
Figure 1: An example of $\bm{M}^{\natural}$ satisfying SSC when $K=3$.

The SSC is illustrated in Fig. 1 with a $K=3$ case. The triangle represents
the nonnegative orthant and the green circle the second-order cone ${\cal C}$.
SSC means that the conic hull of a subset of the $\bm{m}_{n}^{\natural}$’s
(the blue region) covers the green region as a subset. This means that the
columns of $\bm{M}^{\natural}$ are sufficiently different. The SSC is widely
used in the nonnegative matrix factorization literature; see (Fu et al., 2018,
2015b). Note that $\bm{M}^{\natural}$ satisfying the SSC is much more relaxed
compared to the ASC, which means that ${\rm
cone}(\bm{M}^{\natural})=\mathbb{R}_{+}^{K}$, i.e., the blue region in Fig. 1
covers the entire triangle. In the context of membership learning, an SSC-
satisfying $\bm{M}^{\natural}$ means that the membership of the data should
contain enough diversity, but an ASC-satisfying $\bm{M}^{\natural}$ means that
some single-membership data samples need to exist—which is more stringent.

Using the SSC, we show that the following holds:

######  Theorem 3.7.

(Enhanced Identifiability) Under the same assumptions as in Lemma 3.3, suppose
that $\bm{M}^{\natural}$ satisfies SSC (Assumption 3.6) and that
${\bm{f}^{\natural}}\in{\cal F}$. Then, at the limit of
$\max\big{(}\log(1/\alpha),\log(M)\sqrt{R_{\texttt{NET}}}/\alpha\big{)}/\sqrt{M}\rightarrow
0$, the following statements hold:

  * (i)

There exists a permutation matrix $\bm{\Pi}^{\star}$ such that
$\bm{\Pi}^{\star}\bm{M}^{\star}=\bm{M}^{\natural}.$

  * (ii)

The learned neural network $\bm{f}^{\star}$ satisfies

$\mathop{\mathbb{E}}_{\bm{x}\sim\mathcal{P}_{\mathcal{X}}}\left[\frac{1}{K}\left\lVert\bm{\Pi}^{\star}\bm{f}^{\star}(\bm{x})-\bm{f}^{\natural}(\bm{x})\right\rVert^{2}\right]\leq\dfrac{8}{NK}+\\\
\dfrac{12\sqrt{2R_{\texttt{NET}}}\left\lVert\bm{X}\right\rVert_{\rm F}\log
N}{NK\log 2}+8\sqrt{\dfrac{2\log(4/\delta)}{NK^{2}}}$

with probability at least $1-\delta$.

The proof of Theorem 3.7 is in Appendix D. Theorem 3.7 has plausible
implications in practice: When the sample size $M$ is large and ${\cal F}$ is
expressive, even no anchor samples exist, identifying $\bm{M}^{\natural}$ and
finding a generalizable $\bm{f}^{\star}$ are still possible.

##  4 DCC with Noisy Labels: Geometric Regularization

##### Incorporating Annotation Confusion.

We should mention that the generative model in (5) can already model
annotation noise to a certain extent: The Bernoulli sampling process can
encode some 0-1 flipping probability of observing $y_{m}$. Nonetheless, this
level of noise consideration is not enough, as annotations could be grossly
inaccurate. To take more severe annotation errors into consideration, we
modify the generative model as follows. We assume that the annotator confuses
class $i$ with class $j$ with probability ${\sf Pr}(j|i)$. Let $A_{i,j}={\sf
Pr}(i|j)$, we have a “confusion matrix” $\bm{A}\in\mathbb{R}^{K\times K}$
where $[\bm{A}]_{i,j}=A_{i,j}$. Hence, the annotator’s “confused membership
vector” is modeled as

$\displaystyle{\bm{m}}_{n}^{\rm
confused}=\bm{A}\bm{m}_{n}^{\natural}=\bm{A}\bm{f}^{\natural}(\bm{x}_{n}).$
(10)

Then, the annotator’s output is sampled from the following:

$\displaystyle y_{m}\sim{\sf
Bernoulli}(\langle\bm{A}\bm{f}^{\natural}(\bm{x}_{i_{m}}),\bm{A}\bm{f}^{\natural}(\bm{x}_{j_{m}}){\rangle}).$
(11)

Note that using a confusion matrix to model noisy labels’ generating process
is widely seen in noisy label learning—but mostly under the supervised
learning setting; see, e.g., (Dawid & Skene, 1979; Liu et al., 2012; Zhang et
al., 2014; Chu et al., 2021). We argue that this confusion model is also
suitable for pairwise annotation. The rationale is that the error happened in
comparison is mainly caused by the annotator’s confusion on the membership of
$\bm{x}_{i_{m}}$ or that of $\bm{x}_{j_{m}}$—which is exactly reflected in
(11).

##### Volume Maximization DCC.

To proceed, we propose the following modified logistic loss:

$\displaystyle{\sf Loss}^{\prime}_{\rm
cc}(\bm{\theta},\bm{B})=\dfrac{1}{M}\sum^{M}_{m=1}\Big{(}y_{m}\log\dfrac{1}{\bm{f}_{\bm{\theta}}(\bm{x}_{i_{m}})^{{\\!\top\\!}}\bm{B}\bm{f}_{\bm{\theta}}(\bm{x}_{j_{m}})}+$
$\displaystyle(1-y_{m})\log\dfrac{1}{1-\bm{f}_{\bm{\theta}}(\bm{x}_{i_{m}})^{{\\!\top\\!}}\bm{B}\bm{f}_{\bm{\theta}}(\bm{x}_{j_{m}})}\Big{)},$

where $\bm{B}\in\mathbb{R}^{K\times K}$ satisfies $0\leq\bm{B}\leq 1$, as it
is induced by $\bm{B}=\bm{A}^{{\\!\top\\!}}\bm{A}$. Note that we will use
$\bm{\theta}$ and $\bm{B}$ as our optimization variables (instead of $\bm{A}$)
as it simplifies the loss function. In addition, as our ultimate goal is to
learn $\bm{M}^{\natural}$ and $\bm{f}^{\natural}$, the intermediate variable
$\bm{A}$ does not need to be explicitly estimated.

We show that minimizing ${\sf Loss}^{\prime}_{\rm cc}(\bm{\theta},\bm{B})$
provably recovers the data membership and finds a generalizable
$\bm{f}^{\star}$, with an additional volume requirement satisfied by the
solution. Specifically, we have the following theorem:

######  Theorem 4.1 (Identifiability of Noisy Case).

Assume that the assumptions in Lemma 3.3 hold, except that the generative
model is replaced by (11). Suppose that $\bm{M}^{\natural}$ satisfies SSC
(Assumption 3.6) and that ${\bm{f}^{\natural}}\in{\cal F}$. Also assume that
${\rm rank}(\bm{A}^{{\\!\top\\!}}\bm{A}\bm{M}^{\natural})=K$. Denote

$(\bm{\theta}^{\star},\bm{B}^{\star})=\arg\min~{}{\sf Loss}^{\prime}_{\rm
cc}(\bm{\theta},\bm{B})$ (12)

and $\bm{f}^{\star}=\bm{f}_{\bm{\theta}^{\star}}$ and
$\bm{m}^{\star}_{n}=\bm{f}^{\star}(\bm{x}_{n}).$ In addition, assume that
${\sf Loss}^{\prime}_{\rm cc}$ is minimized with a solution
$\bm{M}^{\star},\bm{B}^{\star}$ such that
$\log\det(\bm{M}^{\star}(\bm{M}^{\star})^{{\\!\top\\!}})$ is maximized among
all possible optimal solutions. Then, at the limit of
$\max\big{(}\log(1/\alpha),\log(M)\sqrt{R_{\texttt{NET}}}/\alpha\big{)}/\sqrt{M}\rightarrow
0$, the following statements hold:

  * (i)

There exists a permutation matrix $\bm{\Pi}^{\star}$ such that
$\bm{\Pi}^{\star}\bm{M}^{\star}=\bm{M}^{\natural}.$

  * (ii)

The learned neural network $\bm{f}^{\star}$ satisfies

$\mathop{\mathbb{E}}_{\bm{x}\sim\mathcal{P}_{\mathcal{X}}}\left[\frac{1}{K}\left\lVert\bm{\Pi}^{\star}\bm{f}^{\star}(\bm{x})-\bm{f}^{\natural}(\bm{x})\right\rVert^{2}\right]\leq\dfrac{8}{NK}+\\\
\dfrac{12\sqrt{2R_{\texttt{NET}}}\left\lVert\bm{X}\right\rVert_{\rm F}\log
N}{NK\log 2}+8\sqrt{\dfrac{2\log(4/\delta)}{NK^{2}}}$

with probability at least $1-\delta$.

The proof of Theorem 4.1 is in Appendix E. The take-home point is that, when
one has large samples and an expressive neural network, the membership
identifiability and generalization performance of using ${\sf Loss}_{\rm
cc}^{\prime}$ can be as good as that of using ${\sf Loss}_{\rm cc}$—as if
there is no annotation confusion.

Of course, there are more requirements to satisfy under Theorem 4.1.
Particularly, the maximal
$\log\det(\bm{M}^{\star}(\bm{M}^{\star})^{\\!\top\\!})$ requirement is
nontrivial. In practice, the optimization criterion in Theorem 4.1 can be
approximated via a regularized version of ${\sf Loss}_{\rm cc}^{\prime}$ as
follows:

$\operatorname*{\textrm{minimize}}_{\bm{\theta},\bm{0}\leq\bm{B}\leq\bm{1}}~{}{\sf
Loss}^{\prime}_{\rm cc}+{\sf Loss}_{\rm vol},$ (13)

where ${\sf Loss}_{\rm vol}=-\lambda\log\det(\bm{M}\bm{M}^{\\!\top\\!})$ and
$\bm{m}_{n}=\bm{f}_{\bm{\theta}}(\bm{x}_{n})$. Note that
$\log\det(\bm{M}\bm{M}^{\\!\top\\!})$ is proportional to the volume of the
Gram matrix $\bm{M}\bm{M}^{{\\!\top\\!}}$ (Boyd et al., 2004). Hence, the term
can be regarded as a geometry-driven regularization. We name our method using
(13) as the Volume Maximization-Regularized Deep Constrained Clustering
(VolMaxDCC). An overall architecture is shown in Fig. 2.

$\bm{x}_{i_{m}}$
---
$\bm{x}_{1},\ldots,\bm{x}_{N}$
---
$\bm{x}_{j_{m}}$
---
$y_{m}$
---
softmax
---
softmax
---
softmax
---
All the weights $\bm{\theta}$ are shared
---
.
---
.
---
.
---
.
---
.
---
.
---
.
---
.
---
.
---
$\Big{\langle}\quad,\quad\Big{\rangle}$
---
$\bm{m}_{i_{m}}$
---
$\bm{m}_{j_{m}}$
---
${\sf Loss}^{\prime}_{\rm cc}$
---
$\bm{M}=[\bm{m_{1}},\ldots,\bm{m}_{N}]$
---
${\sf Loss}_{\rm vol}$
---
.
---
.
---
.
---
$+$
---
Figure 2: The architecture of the VolMaxDCC approach.

##  5 Related Work

Recovering the underlying unseen matrix from incomplete and binary measurement
is related to 1-bit low-rank matrix completion (Davenport et al., 2014), which
was often studied in the context of recommender systems. The generative model
in (5) is reminiscent of the MMSB (Airoldi et al., 2008; Huang & Fu, 2019)
that has been a workhorse in overlapped community detection. The MMSB model
with missing links was also used for clustering-related tasks, e.g.,
crowdclustering (Gomes et al., 2011). The ASC and SSC are commonly seen
conditions in identifiability analysis of nonnegative matrix factorization (Fu
et al., 2018, 2015a, 2019, 2016; Huang et al., 2014; Donoho & Stodden, 2003;
Gillis, 2014; Gillis & Vavasis, 2014; Gillis & Luce, 2014; Gillis, 2020;
Nguyen et al., 2022). Using volume maximization/minimization to enhance NMF
identifiability appeared as early as 1994 (Craig, 1994) in the context of a
blind source separation (BSS) problem in spectral image analysis. The volume-
based geometric regularization was connected to ASC- and SSC-like conditions
(e.g., the so-called “pure pixel condition” and “local dominance condition”)
in (Chan et al., 2009) and (Fu et al., 2015b, 2016; Lin et al., 2015),
respectively, to attain uniqueness of matrix factorization models, again, in
the context of BSS. All these models do not involve nonlinear function
learning or deep neural networks. In addition, the classic geometric
factorization models were developed with continuous low-rank matrix
data—instead of binary data generated from models involving complex unknown
nonlinear function. Confusion matrices are often used in supervised noisy
label learning and crowdsourcing (Dawid & Skene, 1979; Zhang et al., 2014;
Rodrigues & Pereira, 2018), to model probabilistic label transition in the
annotating process. The ASC and SSC were also used to establish
identifiability in supervised (crowdsourced) noisy label learning (Xia et al.,
2019; Li et al., 2021a; Ibrahim et al., 2019; Ibrahim & Fu, 2021; Ibrahim et
al., 2023). Incorporating the idea of confusion matrix-based modeling in
similarity annotation was not seen before. The proposed generative model
connects label confusion matrices, volume maximization (more generally,
ASC/SSC-based identifiable factor analysis), and DCC for the first time, to
our best knowledge.

##  6 Experiments

##### Datasets.

We use STL-10 (Coates et al., 2011), ImageNet-10 (Chang et al., 2017a), and
CIFAR-10 (Krizhevsky et al., 2009). For three datasets, we use $N=10000$
samples as the seen data, and set aside $2000$, $2000$ and $45000$ unseen
data, respectively, for testing the generalization performance. In all
experiments, $M=10,000$ pairwise constraints are uniformly and randomly drawn
from $[N]\times[N]$. There are no more than 0.02% of the total number of pairs
annotated for all three datasets.

##### Baselines.

We compare our method with several baselines, including the classic CC
methods, i.e., PCKMeans (Basu et al., 2004a), COP-KMeans (Wagstaff et al.,
2001), and the DCC methods, namely, DC-GMM (Manduchi et al., 2021) and C-IDEC
(Zhang et al., 2019, 2021). We also include the plain-vanilla K-means as a
reference. We use a validation set for the baselines whenever proper for
parameter tuning and algorithm stopping. The sizes of the validation sets are
$N_{\rm valid}=1000$ for STL-10 and ImageNet-10 and $N_{\rm valid}=5000$ for
CIFAR-10. For C-IDEC, the regularization parameters is chosen from
$\left\\{0,1{e-}1,1{e-}2,1{e-}3,1{e-}4,1{e-}5\right\\}$. For DC-GMM, we use
their heuristic to set the constraint violation penalty with the true (oracle)
label flipping rate. For the proposed VolMaxDCC, we also choose $\lambda$
among $\lambda\in\left\\{0,1{e-}1,1{e-}2,1{e-}3,1{e-}4,1{e-}5\right\\}$. We
also include the result of using the simple logistic loss ${\sf Loss}_{\rm
cc}$ in (3), which is referred to as VanillaDCC.

##### Neural Network Settings.

For all the DCC methods, we employ the unsupervised pre-training method by (Li
et al., 2021b) to convert the images to feature vectors
$\\{\bm{x}_{1},\ldots,\bm{x}_{N}\\}{\subseteq\mathbb{R}^{512}}$ (Li et al.,
2021b). The feature vectors are then fed to a two-hidden-layer fully connected
neural network $\bm{f}_{\bm{\theta}}(\cdot)$, where each hidden layer has 512
ReLU activation functions. The output layer of $\bm{f}_{\bm{\theta}}(\cdot)$
has $K=10$ dimensions with the softmax constraints. The classic methods also
work with the pre-trained feature vectors.

##### Algorithm Implementation.

To tackle the proposed criterion in (13), we first parameterize $\bm{B}$ such
that each element $B_{ij}=1/(1+\exp(-B^{\prime}_{ij}))$, where
$B^{\prime}_{ij}\in\mathbb{R}$ is a trainable parameter. By doing so, (13)
becomes an unconstrained optimization problem. We then employ the commonly
used stochastic gradient-based solvers to tackle the re-parameterized problem.
In our implementation, we use stochastic gradient descent with a batch size of
$128$. We set the learning rate for $\bm{B^{\prime}}$ and $\bm{\theta}$ to be
0.1 and 0.5, respectively. The initialization of $\bm{\theta}$ is chosen
randomly following uniform distributions with parameters depending on output
dimension of each layer. To initialize $\bm{B}^{\prime}$, we make the diagonal
elements to be $1$ and the other elements $-1$. The baselines are handled by
their respective author-provided code for optimization.

###  6.1 Noisy Machine Annotations.

##### Noisy Annotation Settings.

We first conduct experiments under noise-controlled settings. To be specific,
we divide the experiments into two cases, where the annotations are accurate
and noisy, respectively. In the former case, the annotations are set to $1$ if
the pair of data are from the same class, and set to $0$ otherwise. In the
latter case, to generate noisy pairwise constraints, several supervised
machine annotators (i.e., classifiers) are trained using different number of
training samples. By doing this, the trained classifiers have different
prediction errors. The pairs are then annotated based on the class predictions
made by these imperfect classifiers. If the pair of samples share the same
predicted membership by the machine annotator, the annotation is set to be 1
(and 0 otherwise). The annotations are noisy as the machine annotators are far
from perfect. The annotation noise level can be controlled by tuning the
prediction error of the classifiers, via using various amounts of training
samples. The statistics of the annotation errors are provided with our
experiment results (see the “noise level” column in the tables).

##### Results.

Table 1: Clustering performance of (seen data, unseen data) on STL10; $N_{\rm
unseen}=2000$.

Noise level Methods | Kmeans | COP-Kmeans | PCKmeans | DC-GMM | C-IDEC | VanillaDCC | VolMaxDCC
---|---|---|---|---|---|---|---
0.0% | ACC | 0.71, — | 0.66, — | 0.70, — | 0.88, 0.87 | 0.89, 0.88 |  0.93, 0.91 |  0.91, 0.89
NMI | 0.75, — | 0.67, — | 0.72, — |  0.82, 0.80 |  0.81, 0.80 |  0.84, 0.81 |  0.82, 0.80
ARI | 0.54, — | 0.52, — | 0.55, — | 0.80, 0.78 | 0.79, 0.77 |  0.85, 0.83 |  0.84, 0.82
8.3% | ACC | — | 0.70, — | 0.70, — | 0.75, 0.76 | 0.77, 0.79 |  0.78, 0.80 |  0.80, 0.81
NMI | — | 0.64, — |  0.71, — |  0.67, 0.69 |  0.67, 0.69 | 0.59, 0.62 |  0.64, 0.65
ARI | — | 0.51, — | 0.56, — | 0.57, 0.59 | 0.59, 0.61 |  0.69, 0.71 |  0.73, 0.74
10.3% | ACC | — | 0.62, — | 0.69, — | 0.70, 0.72 | 0.70, 0.71 |  0.72, 0.73 |  0.79, 0.81
NMI | — | 0.59, — |  0.73, — |  0.62, 0.64 | 0.60, 0.62 | 0.50, 0.51 |  0.68, 0.70
ARI | — | 0.44, — | 0.55, — | 0.51, 0.52 | 0.50, 0.52 |  0.62, 0.64 |  0.77, 0.78
15.0% | ACC | — | 0.62, — |  0.64, — |  0.60, 0.61 | 0.57, 0.57 | 0.56, 0.58 |  0.79, 0.81
NMI | — | 0.54, — |  0.72, — |  0.54, 0.55 | 0.50, 0.50 | 0.33, 0.35 |  0.68, 0.69
ARI | — | 0.41, — |  0.52, — | 0.38, 0.39 | 0.38, 0.39 |  0.50, 0.51 |  0.76, 0.77

Table 2: Clustering performance of (seen data, unseen data) on CIFAR10;
$N_{\rm unseen}=45000$.

Noise level Methods | Kmeans | COP-Kmeans | PCKmeans | DC-GMM | C-IDEC | VanillaDCC | VolMaxDCC
---|---|---|---|---|---|---|---
0.0% | ACC | 0.78, — | 0.67, — | 0.67, — |  0.91, 0.89 |  0.90, 0.89 |  0.92, 0.90 |  0.91, 0.90
NMI | 0.71, — | 0.66, — | 0.71, — |  0.83, 0.81 |  0.83, 0.81 |  0.84, 0.80 |  0.83, 0.80
ARI | 0.62, — | 0.54, — | 0.55, — | 0.82, 0.79 | 0.81, 0.79 |  0.85, 0.81 |  0.84, 0.82
4.9% | ACC | — |  0.75, — | 0.70, — |  0.86, 0.86 |  0.86, 0.86 |  0.86, 0.86 |  0.86, 0.86
NMI | — | 0.69, — | 0.69, — |  0.77, 0.77 |  0.77, 0.77 |  0.73, 0.73 |  0.73, 0.74
ARI | — | 0.60, — | 0.57, — |  0.73, 0.74 |  0.73, 0.74 |  0.77, 0.77 |  0.77, 0.77
8.7% | ACC | — | 0.64, — | 0.72, — |  0.76, 0.76 |  0.76, 0.76 |  0.76, 0.77 |  0.83, 0.83
NMI | — | 0.63, — | 0.69, — |  0.71, 0.71 |  0.70, 0.70 | 0.58, 0.59 |  0.70, 0.70
ARI | — | 0.49, — | 0.59, — | 0.58, 0.59 | 0.59, 0.60 |  0.70, 0.70 |  0.75, 0.75
10.9% | ACC | — | 0.68, — | 0.70, — |  0.74, 0.74 | 0.73, 0.73 | 0.68, 0.69 |  0.82, 0.82
NMI | — | 0.61, — |  0.68, — |  0.67, 0.68 |  0.65, 0.66 | 0.48, 0.49 |  0.68, 0.68
ARI | — | 0.50, — | 0.57, — | 0.55, 0.55 | 0.56, 0.57 |  0.62, 0.63 |  0.74, 0.74

Table 3: Clustering performance of (seen data, unseen data) on ImageNet10;
$N_{\rm unseen}=2000$.

Noise level Methods | Kmeans | COP-Kmeans | PCKmeans | DC-GMM | C-IDEC | VanillaDCC | VolMaxDCC
---|---|---|---|---|---|---|---
0.0% | ACC |  0.85, — | 0.79, — | 0.70, — |  0.97, 0.96 |  0.97, 0.96 |  0.97, 0.96 |  0.97, 0.96
NMI | 0.80, — | 0.77, — | 0.75, — |  0.93, 0.91 |  0.93, 0.92 |  0.94, 0.91 |  0.94, 0.91
ARI | 0.68, — | 0.66, — | 0.55, — |  0.94, 0.92 |  0.94, 0.92 |  0.93, 0.91 |  0.93, 0.91
3.4% | ACC | — | 0.79, — | 0.66, — |  0.93, 0.92 |  0.93, 0.93 | 0.92, 0.91 |  0.94, 0.94
NMI | — | 0.75, — | 0.73, — | 0.86, 0.85 |  0.87, 0.86 | 0.83, 0.82 |  0.88, 0.87
ARI | — | 0.65, — | 0.52, — | 0.84, 0.83 |  0.86, 0.85 | 0.84, 0.84 |  0.89, 0.88
6.9% | ACC | — | 0.74, — | 0.72, — | 0.84, 0.84 |  0.88, 0.88 | 0.84, 0.84 |  0.92, 0.91
NMI | — | 0.70, — | 0.76, — | 0.79, 0.79 |  0.82, 0.82 | 0.70, 0.70 |  0.84, 0.83
ARI | — | 0.58, — | 0.59, — | 0.71, 0.71 |  0.77, 0.77 |  0.77, 0.77 |  0.88, 0.87
11.2% | ACC | — | 0.72, — | 0.62, — | 0.71, 0.72 |  0.80, 0.81 | 0.65, 0.66 |  0.91, 0.90
NMI | — | 0.64, — | 0.73, — | 0.68, 0.70 |  0.74, 0.76 | 0.49, 0.52 |  0.83, 0.82
ARI | — | 0.54, — | 0.51, — | 0.56, 0.58 |  0.66, 0.68 | 0.62, 0.63 |  0.87, 0.86

We report average performance on the seen set
$\\{\bm{x}_{1},\ldots,\bm{x}_{N}\\}$ and the unseen data over 5 random trials
in Tables 1, 2, and 3—which correspond to STL10, CIFAR10, and ImageNet10,
respectively. For K-means, COP-Kmeans, and PCKMeans, we only report results on
the seen set since these methods do not have the notion of generalization. The
performance is measured by three commonly seen metrics, namely, clustering
accuracy (ACC) (Cai et al., 2010), normalized mutual information (NMI) (Cai et
al., 2010), and adjusted rank index (ARI) (Yeung & Ruzzo, 2001). For all
metrics, a higher score indicates a better performance.

In case where accurate pairwise constraints are used (i.e., the rows in all
the tables corresponding to “Noise Level = 0%”), most methods work reasonably
well. As expected, all the DCC methods exhibit tangible edges over the CC
methods that do not use deep neural networks. This is consistent with the
observations made from previous DCC works (Manduchi et al., 2021; Zhang et
al., 2019, 2021). The good performance of VanillaDCC on both training and
testing set are also as expected, per our identifiability analysis.

The rows in the tables associated with nonzero noise levels show that the
performance of DC-GMM, C-IDEC, and VanillaDCC drops quickly. For example, in
Table 2, the ACC of DC-GMM drops from (0.91,0.89) to (0.74,0.74) when the
noise level changes from 0% to 10.9%. Similar performance degradation is
observed for C-IDEC and VanillaDCC, which are both DCC methods that do not
explicit consider annotation noise. Nonetheless, the proposed VolMaxDCC’s
performance decline is much more graceful on all three datasets. In
particular, Table 3 shows that the ACC of VolMaxDCC is still at (0.91,0.90)
when the noise level reaches 11.2%, while the baselines have a best ACC of
(0.80,0.81). The results show the usefulness of our confusion model, as well
as the effectiveness of our identifiability-driven loss function design. More
experiment results can be seen in Appendix F.

Table 4: Clustering performance of (seen data, unseen data) on ImageNet10 with
pairwise annotations acquired from the AMT platform; $N_{{\rm unseen}}=2000$,
noise level: $23.09$%.

Metrics Methods | Kmeans | COP-Kmeans | PCKmeans | DC-GMM | C-IDEC | VolMaxDCC
---|---|---|---|---|---|---
ACC | 0.84, — | 0.68, — | 0.84, — | 0.87, 0.85 |  0.91, 0.90 |  0.95, 0.94
NMI | 0.79, — | 0.49, — | 0.79, — |  0.88, 0.86 | 0.86, 0.85 |  0.89, 0.87
ARI | 0.67, — | 0.42, — | 0.67, — | 0.82, 0.79 |  0.83, 0.82 |  0.89, 0.88

###  6.2 Noisy AMT Annotations.

##### Data Acquisition.

In addition to using machine classifier-annotated data, we also conduct
experiments using pairwise annotations that are obtained from the AMT
platform. We uploaded $8994$ data pairs to AMT, where the samples are from the
ImageNet10 dataset. The annotators were asked to provide their judgement on
the similarity of the pairs. Recall that there are $N=10000$ samples in the
ImageNet10 dataset, which means that $0.018$% of all the pairs were annotated.
We manually checked the error rate, which was found to be 23.09%. The
annotated pairs are also released with the code.

##### Results.

Table 4 shows the results on this AMT dataset. As before, we use the available
pairs to learn the membership of training data and observe the testing
accuracy over $N_{\rm unseen}=2,000$ samples. One can see that the proposed
VolMaxDCC exhibits the highest clustering accuracy over the seen and unseen
data. The clustering accuracy of the second best baseline is 4% lower than
that of VolMaxDCC over both seen and unseen data. The margins of the proposed
method over the baselines in terms of NMI and ARI are also obvious. The
performance on the noisy AMT data speaks for the usefulness and effectiveness
of the proposed method in real-world scenarios.

##  7 Conclusion

We revisited the pairwise annotation-based DCC problem from a membership
identifiability viewpoint. We showed that a recently emerged logistic DCC loss
is a sound criterion in terms of model identification—if the annotations are
generated following a model that is reminiscent of the MMSB and deep learning
based classifier learning. Based our understanding to the vanilla logistic
loss, we moved forward to consider the noisy annotation case and proposed a
confusion-matrix based generative model. We proposed a modified logistic loss
with a geometric regularization for provable membership identification—whose
identifiability guarantee is the first of the kind under noisy annotations-
based DCC, to our best knowledge. We tested our new design over various
datasets under multiple noisy levels. We observed tangible improvements over
all cases, showing our confusion-based modeling and identifiability-driven
design are promising.

##### Limitations.

The proposed approach has a couple of notable limitations. First, the model
used for annotator noise relies on a confusion matrix model, assuming uniform
confusion across all data samples, which may not always hold true in practical
scenarios. Developing a framework that takes into account more realistic
confusion models could lead to further improvements in performance. Second,
the establishment of membership identifiability under the SSC assumption lacks
finite sample analysis (cf. Theorem 3.7 and Theorem 4.1). The assumption that
$M$ reaches infinity can never be met in practice. It is of great interest to
show how the performance of the volume-based criterion scales with different
sample sizes.

##### Acknowledgement.

This work is supported in part by the National Science Foundation (NSF) under
project NSF IIS-2007836.

## References

  * Airoldi et al. (2008) Airoldi, E. M., Blei, D., Fienberg, S., and Xing, E.  Mixed membership stochastic blockmodels.  _Advances in Neural Information Processing Systems_ , 21, 2008.
  * Anandkumar et al. (2014) Anandkumar, A., Ge, R., Hsu, D., and Kakade, S. M.  A tensor approach to learning mixed membership community models.  _The Journal of Machine Learning Research_ , 15(1):2239–2312, 2014.
  * Arora et al. (2013) Arora, S., Ge, R., Halpern, Y., Mimno, D., Moitra, A., Sontag, D., Wu, Y., and Zhu, M.  A practical algorithm for topic modeling with provable guarantees.  In _International Conference on Machine Learning_ , pp. 280–288. PMLR, 2013.
  * Bartlett et al. (2017) Bartlett, P. L., Foster, D. J., and Telgarsky, M. J.  Spectrally-normalized margin bounds for neural networks.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Basu et al. (2004a) Basu, S., Banerjee, A., and Mooney, R. J.  Active semi-supervision for pairwise constrained clustering.  In _Proceedings of the 2004 SIAM International Conference on Data Mining_ , pp. 333–344, 2004a.
  * Basu et al. (2004b) Basu, S., Bilenko, M., and Mooney, R. J.  A probabilistic framework for semi-supervised clustering.  In _Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , pp. 59–68, 2004b.
  * Basu et al. (2008) Basu, S., Davidson, I., and Wagstaff, K.  _Constrained clustering: Advances in algorithms, theory, and applications_.  CRC Press, 2008.
  * Bilenko et al. (2004) Bilenko, M., Basu, S., and Mooney, R. J.  Integrating constraints and metric learning in semi-supervised clustering.  In _Proceedings of the Twenty-First International Conference on Machine Learning_ , pp. 11, 2004.
  * Blei et al. (2003) Blei, D. M., Ng, A. Y., and Jordan, M. I.  Latent dirichlet allocation.  _Journal of Machine Learning Research_ , 3(Jan):993–1022, 2003.
  * Boyd et al. (2004) Boyd, S., Boyd, S. P., and Vandenberghe, L.  _Convex optimization_.  Cambridge university press, 2004.
  * Cai et al. (2010) Cai, D., He, X., and Han, J.  Locally consistent concept factorization for document clustering.  _IEEE Transactions on Knowledge and Data Engineering_ , 23(6):902–913, 2010.
  * Cai & Zhou (2016) Cai, T. T. and Zhou, W.-X.  Matrix completion via max-norm constrained optimization.  _Electronic Journal of Statistics_ , 10(1):1493 – 1525, 2016.
  * Caron et al. (2018) Caron, M., Bojanowski, P., Joulin, A., and Douze, M.  Deep clustering for unsupervised learning of visual features.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pp. 132–149, 2018.
  * Chan et al. (2009) Chan, T.-H., Chi, C.-Y., Huang, Y.-M., and Ma, W.-K.  A convex analysis-based minimum-volume enclosing simplex algorithm for hyperspectral unmixing.  _IEEE Transactions on Signal Processing_ , 57(11):4418–4432, 2009.
  * Chang et al. (2017a) Chang, J., Wang, L., Meng, G., Xiang, S., and Pan, C.  Deep adaptive image clustering.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 5879–5887, 2017a.
  * Chang et al. (2017b) Chang, Y., Chen, J., Cho, M. H., Castaldi, P. J., Silverman, E. K., and Dy, J. G.  Multiple clustering views from multiple uncertain experts.  In _International Conference on Machine Learning_ , pp. 674–683, 2017b.
  * Chu et al. (2021) Chu, Z., Ma, J., and Wang, H.  Learning from crowds by modeling common confusions.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pp. 5832–5840, 2021.
  * Coates et al. (2011) Coates, A., Ng, A., and Lee, H.  An analysis of single-layer networks in unsupervised feature learning.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , volume 15, pp. 215–223. PMLR, 11–13 Apr 2011.
  * Covoes et al. (2013) Covoes, T. F., Hruschka, E. R., and Ghosh, J.  A study of K-means-based algorithms for constrained clustering.  _Intelligent Data Analysis_ , 17(3):485–505, 2013\.
  * Craig (1994) Craig, M. D.  Minimum-volume transforms for remotely sensed data.  _IEEE Transactions on Geoscience and Remote Sensing_ , 32(3):542–552, 1994.
  * Cucuringu et al. (2016) Cucuringu, M., Koutis, I., Chawla, S., Miller, G., and Peng, R.  Simple and scalable constrained clustering: A generalized spectral method.  In _Artificial Intelligence and Statistics_ , pp. 445–454, 2016\.
  * Davenport et al. (2014) Davenport, M. A., Plan, Y., van den Berg, E., and Wootters, M.  1-bit matrix completion.  _Information and Inference: A Journal of the IMA_ , 3(3):189–223, 2014.
  * Davidson et al. (2010) Davidson, I., Ravi, S., and Shamis, L.  A SAT-based framework for efficient constrained clustering.  In _Proceedings of the 2010 SIAM International Conference on Data Mining_ , pp. 94–105. SIAM, 2010.
  * Dawid & Skene (1979) Dawid, A. P. and Skene, A. M.  Maximum likelihood estimation of observer error-rates using the EM algorithm.  _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ , 28(1):20–28, 1979.
  * Donoho & Stodden (2003) Donoho, D. and Stodden, V.  When does non-negative matrix factorization give a correct decomposition into parts?  In _Advances in Neural Information Processing Systems_ , volume 16, pp. 1141–1148, 2003.
  * Du et al. (2019) Du, S. S., Zhai, X., Poczos, B., and Singh, A.  Gradient descent provably optimizes over-parameterized neural networks.  In _International Conference on Learning Representations_ , 2019.
  * Fu et al. (2015a) Fu, X., Ma, W.-K., Chan, T.-H., and Bioucas-Dias, J. M.  Self-dictionary sparse regression for hyperspectral unmixing: Greedy pursuit and pure pixel search are related.  _IEEE Journal of Selected Topics in Signal Processing_ , 9(6):1128–1141, 2015a.
  * Fu et al. (2015b) Fu, X., Ma, W.-K., Huang, K., and Sidiropoulos, N. D.  Blind separation of quasi-stationary sources: Exploiting convex geometry in covariance domain.  _IEEE Transactions on Signal Processing_ , 63:2306–2320, 2015b.
  * Fu et al. (2016) Fu, X., Huang, K., Yang, B., Ma, W.-K., and Sidiropoulos, N. D.  Robust volume minimization-based matrix factorization for remote sensing and document clustering.  _IEEE Transactions on Signal Processing_ , 64(23):6254–6268, 2016.
  * Fu et al. (2018) Fu, X., Huang, K., and Sidiropoulos, N. D.  On identifiability of nonnegative matrix factorization.  _IEEE Signal Processing Letters_ , 25(3):328–332, 2018.
  * Fu et al. (2019) Fu, X., Huang, K., Sidiropoulos, N. D., and Ma, W.-K.  Nonnegative matrix factorization for signal and data analytics: Identifiability, Algorithms, and Applications.  _IEEE Signal Process. Mag._ , 36(2):59–80, March 2019.
  * Ghosh et al. (2011) Ghosh, A., Kale, S., and McAfee, P.  Who moderates the moderators? crowdsourcing abuse detection in user-generated content.  In _Proceedings of the 12th ACM Conference on Electronic Commerce_ , pp. 167–176, 2011.
  * Gillis (2014) Gillis, N.  The why and how of nonnegative matrix factorization.  In _Regularization, Optimization, Kernels, and Support Vector Machines_ , pp. 275–310. Chapman and Hall/CRC, 2014.
  * Gillis (2020) Gillis, N.  _Nonnegative matrix factorization_.  SIAM, 2020.
  * Gillis & Luce (2014) Gillis, N. and Luce, R.  Robust near-separable nonnegative matrix factorization using linear optimization.  _The Journal of Machine Learning Research_ , 15(1):1249–1280, 2014.
  * Gillis & Vavasis (2014) Gillis, N. and Vavasis, S. A.  Fast and robust recursive algorithmsfor separable nonnegative matrix factorization.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 36(4):698–714, 2014.
  * Givoni & Frey (2009) Givoni, I. and Frey, B.  Semi-supervised affinity propagation with instance-level constraints.  In _Artificial Intelligence and Statistics_ , pp. 161–168. PMLR, 2009.
  * Gomes et al. (2011) Gomes, R., Welinder, P., Krause, A., and Perona, P.  Crowdclustering.  _Advances in Neural Information Processing Systems_ , 24, 2011.
  * Hsu & Kira (2015) Hsu, Y.-C. and Kira, Z.  Neural network-based clustering using pairwise constraints.  _arXiv preprint arXiv:1511.06321_ , 2015.
  * Hsu et al. (2018) Hsu, Y.-C., Lv, Z., Schlosser, J., Odom, P., and Kira, Z.  A probabilistic constrained clustering for transfer learning and image category discovery.  _CVPR Deep-Vision workshop_ , 2018.
  * Huang & Fu (2019) Huang, K. and Fu, X.  Detecting overlapping and correlated communities without pure nodes: Identifiability and algorithm.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97, pp. 2859–2868. PMLR, 09–15 Jun 2019.
  * Huang et al. (2014) Huang, K., Sidiropoulos, N. D., and Swami, A.  Non-negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition.  _IEEE Transactions on Signal Processing_ , 62:211–224, 2014\.
  * Huang et al. (2016) Huang, K., Fu, X., and Sidiropoulos, N. D.  Anchor-free correlated topic modeling: Identifiability and algorithm.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Ibrahim & Fu (2021) Ibrahim, S. and Fu, X.  Crowdsourcing via annotator co-occurrence imputation and provable symmetric nonnegative matrix factorization.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139, pp. 4544–4554. PMLR, 18–24 Jul 2021.
  * Ibrahim et al. (2019) Ibrahim, S., Fu, X., Kargas, N., and Huang, K.  Crowdsourcing via pairwise co-occurrences: Identifiability and algorithms.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Ibrahim et al. (2023) Ibrahim, S., Nguyen, T., and Fu, X.  Deep learning from crowdsourced labels: Coupled cross-entropy minimization, identifiability, and regularization.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Jain & Dubes (1988) Jain, A. K. and Dubes, R. C.  _Algorithms for Clustering Data_.  Prentice-Hall, Inc., USA, 1988.  ISBN 013022278X.
  * Kamvar et al. (2003) Kamvar, K., Sepandar, S., Klein, K., Dan, D., Manning, M., and Christopher, C.  Spectral learning.  In _International Joint Conference of Artificial Intelligence_. Stanford InfoLab, 2003.
  * Krizhevsky et al. (2009) Krizhevsky, A., Hinton, G., et al.  Learning multiple layers of features from tiny images.  2009\.
  * Kulis et al. (2005) Kulis, B., Basu, S., Dhillon, I., and Mooney, R.  Semi-supervised graph clustering: A kernel approach.  In _Proceedings of the 22nd International Conference on Machine Learning_ , pp. 457–464, 2005.
  * Kumar et al. (2013) Kumar, A., Sindhwani, V., and Kambadur, P.  Fast conical hull algorithms for near-separable non-negative matrix factorization.  In _International Conference on Machine Learning_ , pp. 231–239, 2013.
  * Law et al. (2005) Law, M. H. C., Topchy, A., and Jain, A. K.  Model-based clustering with probabilistic constraints.  In _Proceedings of the 2005 SIAM International Conference on Data Mining (SDM)_ , pp. 641–645, 2005.
  * Li et al. (2021a) Li, X., Liu, T., Han, B., Niu, G., and Sugiyama, M.  Provably end-to-end label-noise learning without anchor points.  In _International Conference on Machine Learning_ , pp. 6403–6413. PMLR, 2021a.
  * Li et al. (2021b) Li, Y., Hu, P., Liu, Z., Peng, D., Zhou, J. T., and Peng, X.  Contrastive clustering.  In _2021 AAAI Conference on Artificial Intelligence (AAAI)_ , 2021b.
  * Li et al. (2009) Li, Z., Liu, J., and Tang, X.  Constrained clustering via spectral regularization.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 421–428, 2009.
  * Lin et al. (2015) Lin, C.-H., Ma, W.-K., Li, W.-C., Chi, C.-Y., and Ambikapathi, A.  Identifiability of the simplex volume minimization criterion for blind hyperspectral unmixing: The no-pure-pixel case.  _IEEE Transactions on Geoscience and Remote Sensing_ , 53(10):5530–5546, 2015.
  * Liu et al. (2017) Liu, H., Tao, Z., and Fu, Y.  Partition level constrained clustering.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 40(10):2469–2483, 2017.
  * Liu et al. (2012) Liu, Q., Peng, J., and Ihler, A. T.  Variational inference for crowdsourcing.  _Advances in Neural Information Processing Systems_ , 25, 2012.
  * Lu & Carreira-Perpinan (2008) Lu, Z. and Carreira-Perpinan, M. A.  Constrained spectral clustering through affinity propagation.  In _2008 IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 1–8, 2008.
  * Luo et al. (2018) Luo, Y., Tian, T., Shi, J., Zhu, J., and Zhang, B.  Semi-crowdsourced clustering with deep generative models.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Manduchi et al. (2021) Manduchi, L., Chin-Cheong, K., Michel, H., Wellmann, S., and Vogt, J.  Deep conditional gaussian mixture model for constrained clustering.  _Advances in Neural Information Processing Systems_ , 34:11303–11314, 2021.
  * Mao et al. (2017) Mao, X., Sarkar, P., and Chakrabarti, D.  On mixed memberships and symmetric nonnegative matrix factorizations.  In _International Conference on Machine Learning_ , pp. 2324–2333, 2017.
  * Nguyen et al. (2022) Nguyen, T., Fu, X., and Wu, R.  Memory-efficient convex optimization for self-dictionary separable nonnegative matrix factorization: A frank–wolfe approach.  _IEEE Transactions on Signal Processing_ , 70:3221–3236, 2022.
  * Panov et al. (2017) Panov, M., Slavnov, K., and Ushakov, R.  Consistent estimation of mixed memberships with successive projections.  _International Workshop on Complex Networks and their Applications_ , pp. 53–64, 2017.
  * Pelleg & Baras (2007) Pelleg, D. and Baras, D.  K-means with large and noisy constraint sets.  In _European Conference on Machine Learning_ , pp. 674–682. Springer, 2007.
  * Ren et al. (2019) Ren, Y., Hu, K., Dai, X., Pan, L., Hoi, S. C., and Xu, Z.  Semi-supervised deep embedded clustering.  _Neurocomputing_ , 325:121–130, 2019.
  * Rodrigues & Pereira (2018) Rodrigues, F. and Pereira, F.  Deep learning from crowds.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Schultz & Joachims (2003) Schultz, M. and Joachims, T.  Learning a distance metric from relative comparisons.  _Advances in Neural Information Processing Systems_ , 16, 2003.
  * Segal et al. (2003) Segal, E., Wang, H., and Koller, D.  Discovering molecular pathways from protein interaction and gene expression data.  _Bioinformatics_ , 19(suppl_1):i264–i272, 2003\.
  * Shalev-Shwartz & Ben-David (2014) Shalev-Shwartz, S. and Ben-David, S.  _Understanding machine learning: From theory to algorithms_.  Cambridge university press, 2014.
  * Wagstaff & Cardie (2000) Wagstaff, K. and Cardie, C.  Clustering with instance-level constraints.  _AAAI/IAAI_ , 1097:577–584, 2000.
  * Wagstaff et al. (2001) Wagstaff, K., Cardie, C., Rogers, S., Schrödl, S., et al.  Constrained K-means clustering with background knowledge.  In _International Conference on Machine Learning_ , volume 1, pp. 577–584, 2001.
  * Wang et al. (2014) Wang, X., Qian, B., and Davidson, I.  On constrained spectral clustering and its applications.  _Data Mining and Knowledge Discovery_ , 28(1):1–30, 2014.
  * Weyl (1912) Weyl, H.  Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung).  _Mathematische Annalen_ , 71(4):441–479, 1912\.
  * Xia et al. (2019) Xia, X., Liu, T., Wang, N., Han, B., Gong, C., Niu, G., and Sugiyama, M.  Are anchor points really indispensable in label-noise learning?  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Yang et al. (2017) Yang, B., Fu, X., Sidiropoulos, N. D., and Hong, M.  Towards K-means-friendly spaces: Simultaneous deep learning and clustering.  In _Proceedings of the 34th International Conference on Machine Learning_ , volume 70, pp. 3861–3870. PMLR, 06–11 Aug 2017.
  * Yeung & Ruzzo (2001) Yeung, K. Y. and Ruzzo, W. L.  Details of the adjusted rand index and clustering algorithms, supplement to the paper an empirical study on principal component analysis for clustering gene expression data.  _Bioinformatics_ , 17(9):763–774, 2001.
  * Yeung & Yeo (1996) Yeung, M. M. and Yeo, B.-L.  Time-constrained clustering for segmentation of video into story units.  In _Proceedings of 13th International Conference on Pattern Recognition_ , volume 3, pp. 375–380. IEEE, 1996.
  * Yi et al. (2012) Yi, J., Jin, R., Jain, S., Yang, T., and Jain, A.  Semi-crowdsourced clustering: Generalizing crowd labeling by robust distance metric learning.  _Advances in Neural Information Processing Systems_ , 25, 2012.
  * Zhang et al. (2019) Zhang, H., Basu, S., and Davidson, I.  A framework for deep constrained clustering-algorithms and advances.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pp. 57–72, 2019.
  * Zhang et al. (2021) Zhang, H., Zhan, T., Basu, S., and Davidson, I.  A framework for deep constrained clustering.  _Data Mining and Knowledge Discovery_ , 35(2):593–620, 2021.
  * Zhang et al. (2014) Zhang, Y., Chen, X., Zhou, D., and Jordan, M. I.  Spectral methods meet EM: A provably optimal algorithm for crowdsourcing.  _Advances in Neural Information Processing Systems_ , 27, 2014.
  * Zhu et al. (2015) Zhu, X., Loy, C. C., and Gong, S.  Constrained clustering with imperfect oracles.  _IEEE Transactions on Neural Networks and Learning Systems_ , 27(6):1345–1357, 2015.

##  Appendix A Proof of Lemma 3.3

Denote $(I,J)$ and $Y$ as two random variables (RVs) such that ${\sf
Pr}\left(I,J,Y\right)={\sf Pr}\left((I,J)\right){\sf Pr}\left(Y|(I,J)\right)$
and

$\begin{cases}&I,J\sim\mathcal{U}([N]\times[N]),\\\ &Y|(I,J)\sim{\sf
Bernoulli}(P^{\natural}_{IJ}),\end{cases}$

where $(i_{1},j_{1},y_{1}),\ldots,(i_{M},j_{M},y_{M})$ are $M$ i.i.d
realizations of $(I,J,Y)$. Denote $\mathcal{D}_{\bm{P}^{\natural}}$ as the
joint distribution of $(I,J,Y)$, i.e,
$(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}$. We first note the following
relationship, which was also used in 1-bit matrix completion literature
(Davenport et al., 2014; Cai & Zhou, 2016):

$\displaystyle D_{\sf kl}(\bm{P}^{\natural}\;\|\;\bm{P}^{\star})$
$\displaystyle=\dfrac{1}{N^{2}}\sum_{(i,j)\in[N]^{2}}d_{\sf
kl}(P^{\natural}_{ij}\;\|\;P^{\star}_{ij})\quad\text{(by definition in
\eqref{eq:dkl_matrix})}$
$\displaystyle=\mathop{\mathbb{E}}_{(I,J)\sim\mathcal{U}}\left[d_{\sf
kl}(P_{IJ}^{\natural}\;\|\;P^{\star}_{IJ})\right]$
$\displaystyle=\mathop{\mathbb{E}}_{(I,J)\sim\mathcal{U}}\left[P^{\natural}_{IJ}\log\dfrac{P^{\natural}_{IJ}}{P^{\star}_{IJ}}+(1-P_{IJ}^{\natural})\log\dfrac{1-P_{IJ}^{\natural}}{1-P^{\star}_{IJ}}\right]\quad\text{(by
definition in \eqref{eq:dkl_element})}$
$\displaystyle=\mathop{\mathbb{E}}_{(I,J)\sim\mathcal{U}}\left[\mathop{\mathbb{E}}_{Y|(I,J)\sim\text{Bern($P^{\natural}_{IJ}$)}}\left[Y\log\dfrac{P^{\natural}_{IJ}}{P^{\star}_{IJ}}+(1-Y)\log\dfrac{1-P^{\natural}_{IJ}}{1-P^{\star}_{IJ}}\right]\right]$
$\displaystyle=\mathop{\mathbb{E}}_{(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}}\left[Y\log
P^{\natural}_{IJ}+(1-Y)\log
P^{\natural}_{IJ}\right]-\mathop{\mathbb{E}}_{(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}}\left[Y\log
P^{\star}_{IJ}+(1-Y)\log P^{\star}_{IJ}\right]$
$\displaystyle=L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P}^{\star})-L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P}^{\natural}),$
(14)

where we define $L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P})$ for any matrix
$0\leq\bm{P}\leq 1$ as

$\displaystyle L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P})$
$\displaystyle\triangleq\mathbb{E}_{(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}}\left[\ell(\bm{P},(I,J,Y))\right],\text{
where }$ $\displaystyle\ell(\bm{P},(I,J,Y))$ $\displaystyle\triangleq-Y\log
P_{IJ}-(1-Y)\log(1-P_{IJ}).$ (15)

Recall
$S\triangleq\left\\{(i_{1},j_{1},y_{1}),\ldots,(i_{M},j_{M},y_{M})\right\\}$.
Define
$L_{S}(\bm{P})\triangleq(1/M)\sum_{i=1}^{M}\ell(\bm{P},(i_{m},j_{m},y_{m}))$.
By this definition, $\bm{P}^{\star}$ is an optimal solution of the following
problem

$\displaystyle\operatorname*{\textrm{minimize}}_{\bm{P}\in\mathcal{P}_{\mathcal{F},\bm{X}}}\quad$
$\displaystyle L_{S}(\bm{P}),$

where $\mathcal{P}_{\mathcal{F},\bm{X}}$ is a set of matrices defined by the
function class $\mathcal{F}$ and the data set
$\bm{X}=[\bm{x}_{1},\ldots,\bm{x}_{N}]$. Specifically, it is defined as

$\displaystyle\mathcal{P}_{\mathcal{F},\bm{X}}$
$\displaystyle\triangleq\left\\{\bm{P}\in\mathbb{R}^{N\times N}\mid
P_{ij}=\texttt{dot}(\bm{f}^{\prime}(\bm{x}_{i},\bm{x}_{j}))\right\\},$ (16a)
$\displaystyle\texttt{dot}([\bm{u};\bm{v}])$
$\displaystyle\triangleq\bm{u}^{{\\!\top\\!}}\bm{v},$ (16b)
$\displaystyle\bm{f}^{\prime}(\bm{x},\bm{y})$
$\displaystyle\triangleq[\bm{f}(\bm{x});\bm{f}(\bm{y})],\quad\bm{f}\in\mathcal{F}.$
(16c)

Define $\widetilde{\bm{P}}\in\mathbb{R}^{N\times N}$ such that
$\widetilde{P}_{ij}=\widetilde{\bm{f}}(\bm{x}_{i})^{{\\!\top\\!}}\widetilde{\bm{f}}(\bm{x}_{j})$
where $\widetilde{\bm{f}}$ is defined in Assumption 7, i.e., the “best
approximation” for $\bm{f}^{\natural}$ by the class ${\cal F}$. Using (A) and
the above notations, we have

$\displaystyle D_{\sf kl}(\bm{P}^{\natural}\;\|\;\bm{P}^{\star})$
$\displaystyle=L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P}^{\star})-L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P}^{\natural})$
$\displaystyle=\big{(}L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P}^{\star})-L_{S}(\bm{P}^{\star})\big{)}+\big{(}L_{S}(\bm{P}^{\star})-L_{S}(\widetilde{\bm{P}})\big{)}+\big{(}L_{S}(\widetilde{\bm{P}})-L_{\mathcal{D}_{\bm{P}^{\natural}}}(\widetilde{\bm{P}})\big{)}+\big{(}L_{\mathcal{D}_{\bm{P}^{\natural}}}(\widetilde{\bm{P}})-L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P}^{\natural})\big{)}$
$\displaystyle\leq\big{(}L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P}^{\star})-L_{S}(\bm{P}^{\star})\big{)}+\big{(}L_{S}(\widetilde{\bm{P}})-L_{\mathcal{D}_{\bm{P}^{\natural}}}(\widetilde{\bm{P}})\big{)}+\big{(}L_{\mathcal{D}_{\bm{P}^{\natural}}}(\widetilde{\bm{P}})-L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P}^{\natural})\big{)}$
$\displaystyle\leq
2\sup_{\bm{P}\in\mathcal{P}_{\mathcal{F},\bm{X}}}\left\lvert
L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P})-L_{S}(\bm{P})\right\rvert+\left\lvert
L_{\mathcal{D}_{\bm{P}^{\natural}}}(\widetilde{\bm{P}})-L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P}^{\natural})\right\rvert,$
(17)

where the first inequality holds because $L_{S}(\bm{P}^{\star})\leq
L_{S}(\widetilde{\bm{P}})$ which holds by the definition of $\bm{P}^{\star}$,
and the second inequality holds as both
$\bm{P}^{\star},\widetilde{\bm{P}}\in\mathcal{P}_{\mathcal{F},\bm{X}}$.

##### Bound the first term in (17).

Notice that $L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P})$ and $L_{S}(\bm{P})$
are the expected loss and the empirical loss, respectively. Hence, the
difference between these two quantities can be bounded using generalization
analysis via concentration inequalities.

To this end, we first determine an upper bound on the loss function
$\ell(\bm{P},(i,j,y))$. Under the assumption stated in Assumption 3.2,

$\alpha<P_{ij}<1-\alpha,\quad\forall(i,j)\in[N]\times[N],$

which leads to

$\ell(\bm{P},(i,j,y))=y\log\dfrac{1}{P_{ij}}+(1-y)\log\dfrac{1}{1-P_{ij}}\leq\log\dfrac{1}{P_{ij}}+\log\dfrac{1}{1-P_{ij}}\leq
2\log\dfrac{1}{\alpha},\quad\;\forall(i,j)\in[N]^{2},y\in\left\\{0,1\right\\},$
(18)

As $\ell(\bm{P},(i,j,y))$ is bounded, the sample set $S$ contains $M$ samples
of $(i_{m},j_{m},y_{m})$’s, where each sample $(i_{m},j_{m},y_{m})$ is
generated independently with the same distribution
$\mathcal{D}_{\bm{P}^{\natural}}$, one can readily apply the following
generalization bound (Shalev-Shwartz & Ben-David, 2014, Theorem 26.5):

$\displaystyle\sup_{\bm{P}\in\mathcal{P}_{\mathcal{F},\bm{X}}}\left\lvert
L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P})-L_{S}(\bm{P})\right\rvert$
$\displaystyle\leq 2\mathcal{R}(\ell\circ\mathcal{P}_{\mathcal{F},\bm{X}}\circ
S)+8\log(1/\alpha)\sqrt{\dfrac{2\log(4/\delta)}{M}}$
$\displaystyle\leq\dfrac{{8}\log(1/\alpha)}{M}+\dfrac{12\sqrt{2}\log M}{\alpha
M\log 2}\left\lVert\bm{S}_{\bm{X}}\right\rVert_{\rm
F}\sqrt{R_{\texttt{NET}}}+8\log(1/\alpha)\sqrt{\dfrac{2\log(4/\delta)}{M}}$
(19)

holds with probability at least $1-\delta$, where we have applied Lemma A.3 to
reach the final bound.

##### Bound the second term in (17).

We have

$\displaystyle\left\lvert
L_{\mathcal{D}_{\bm{P}^{\natural}}}(\widetilde{\bm{P}})-L_{\mathcal{D}_{\bm{P}^{\natural}}}(\bm{P}^{\natural})\right\rvert$
$\displaystyle=\left\lvert\mathop{\mathbb{E}}_{(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}}\left[\ell(\widetilde{\bm{P}},(I,J,Y))-\ell(\bm{P}^{\natural},(I,J,Y))\right]\right\rvert$
$\displaystyle=\left\lvert\mathop{\mathbb{E}}_{(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}}\left[Y\left(\log
P^{\natural}_{IJ}-\log\widetilde{P}_{IJ}\right)+(1-Y)\left(\log(1-P^{\natural}_{IJ})-\log(1-\widetilde{P}_{IJ})\right)\right]\right\rvert$
$\displaystyle\leq\mathop{\mathbb{E}}_{(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}}\left[\left\lvert
Y\left(\log
P^{\natural}_{IJ}-\log\widetilde{P}_{IJ}\right)+(1-Y)\left(\log(1-P^{\natural}_{IJ})-\log(1-\widetilde{P}_{IJ})\right)\right\rvert\right]$
$\displaystyle\leq\mathop{\mathbb{E}}_{(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}}\left[Y\left\lvert\log\dfrac{P^{\natural}_{IJ}}{\widetilde{P}_{IJ}}\right\rvert+(1-Y)\left\lvert\log\dfrac{1-P^{\natural}_{IJ}}{1-\widetilde{P}_{IJ}}\right\rvert\right]$
$\displaystyle\leq\mathop{\mathbb{E}}_{(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}}\left[\left\lvert\log\dfrac{P^{\natural}_{IJ}}{\widetilde{P}_{IJ}}\right\rvert+\left\lvert\log\dfrac{1-P^{\natural}_{IJ}}{1-\widetilde{P}_{IJ}}\right\rvert\right]\quad\text{(since
$Y\in\left\\{0,1\right\\}$)}$
$\displaystyle\leq^{(a)}\mathop{\mathbb{E}}_{(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}}\left[\left\lvert\dfrac{P^{\natural}_{IJ}-\widetilde{P}_{IJ}}{\widetilde{P}_{IJ}}\right\rvert+\left\lvert\dfrac{\widetilde{P}_{IJ}-P^{\natural}_{IJ}}{1-\widetilde{P}_{IJ}}\right\rvert\right]$
$\displaystyle\leq\dfrac{1}{\alpha}\mathop{\mathbb{E}}_{(I,J,Y)\sim\mathcal{D}_{\bm{P}^{\natural}}}\left[\left\lvert
P^{\natural}_{IJ}-\widetilde{P}_{IJ}\right\rvert\right],$ (20)

where (a) holds by applying inequality $\log(x+1)\leq x,\;\forall x>-1$.

In order to bound (20), consider arbitrary $\bm{x},\bm{y}\in\mathcal{X}$,

$\displaystyle\left\lvert\bm{f}^{\natural}(\bm{x})^{{\\!\top\\!}}\bm{f}^{\natural}(\bm{y})-\widetilde{\bm{f}}(\bm{x})^{{\\!\top\\!}}\widetilde{\bm{f}}(\bm{y})\right\rvert$
$\displaystyle=\left\lvert\left(\bm{f}^{\natural}(\bm{x})-\widetilde{\bm{f}}(\bm{x})+\widetilde{\bm{f}}(\bm{x})\right)^{{\\!\top\\!}}\left(\bm{f}^{\natural}(\bm{y})-\widetilde{\bm{f}}(\bm{y})+\widetilde{\bm{f}}(\bm{y})\right)-\widetilde{\bm{f}}(\bm{x})^{{\\!\top\\!}}\widetilde{\bm{f}}(\bm{y})\right\rvert$
$\displaystyle=\left\lvert\left(\bm{f}^{\natural}(\bm{x})-\widetilde{\bm{f}}(\bm{x})\right)^{{\\!\top\\!}}\left(\bm{f}^{\natural}(\bm{y})-\widetilde{\bm{f}}(\bm{y})\right)+\left(\bm{f}^{\natural}(\bm{x})-\widetilde{\bm{f}}(\bm{x})\right)^{{\\!\top\\!}}\widetilde{\bm{f}}(\bm{y})+\widetilde{\bm{f}}(\bm{x})^{{\\!\top\\!}}\left(\bm{f}^{\natural}(\bm{y})-\widetilde{\bm{f}}(\bm{y})\right)\right\rvert$
$\displaystyle\leq\left\lVert\bm{f}^{\natural}(\bm{x})-\widetilde{\bm{f}}(\bm{x})\right\rVert\left\lVert\bm{f}^{\natural}(\bm{y})-\widetilde{\bm{f}}(\bm{y})\right\rVert+\left\lVert\bm{f}^{\natural}(\bm{x})-\widetilde{\bm{f}}(\bm{x})\right\rVert\left\lVert\widetilde{\bm{f}}(\bm{y})\right\rVert+\left\lVert\widetilde{\bm{f}}(\bm{x})\right\rVert\left\lVert\bm{f}^{\natural}(\bm{y})-\widetilde{\bm{f}}(\bm{y})\right\rVert$
$\displaystyle\leq\nu^{2}+2\nu\quad\text{(by Eq. \eqref{assumption:prox})}$
$\displaystyle<4\nu,\quad\text{(since $\nu\leq\sqrt{2}$ due to the fact that
all $\bm{f}(\bm{x})$ are in the probability simplex ) }$ (21)

where we have used
$\|\widetilde{\bm{f}}(\bm{x})\|_{2}\leq\|\widetilde{\bm{f}}(\bm{x})\|_{1}=1$
in the second inequality, as the neural network uses a softmax output layer.

Substituting (21) into (20), we have

$L_{S}(\widetilde{\bm{P}})-L_{S}(\bm{P}^{\natural})\leq\dfrac{4\nu}{\alpha}.$
(22)

##### Putting together.

Combining (17), (19), (22) gives

$D_{\sf
kl}(\bm{P}^{\natural}\;\|\;\bm{P}^{\star})\leq\dfrac{16\log(1/\alpha)}{M}+\dfrac{24\sqrt{2}\log
M}{\alpha M\log 2}\left\lVert\bm{S}_{\bm{X}}\right\rVert_{\rm
F}\sqrt{R_{\texttt{NET}}}+16\log(1/\alpha)\sqrt{\dfrac{2\log(4/\delta)}{M}}+\dfrac{4\nu}{\alpha}$

By Lemma A.4, we can upper bound our quantity of interest by the following:

$\left\lVert\bm{P}^{\star}-\bm{P}^{\natural}\right\rVert_{\rm F}^{2}\leq
4N^{2}D_{\sf kl}(\bm{P}^{\natural}\;\|\;\bm{P}^{\star}).$ (23)

That is,

$\dfrac{1}{N^{2}}\left\lVert\bm{P}^{\star}-\bm{P}^{\natural}\right\rVert_{\rm
F}^{2}\leq\dfrac{64\log(1/\alpha)}{M}+\dfrac{96\sqrt{2}\log M}{\alpha M\log
2}\left\lVert\bm{S}_{\bm{X}}\right\rVert_{\rm
F}\sqrt{R_{\texttt{NET}}}+64\log(1/\alpha)\sqrt{\dfrac{2\log(4/\delta)}{M}}+\dfrac{16\nu}{\alpha}$

hold with probability at least $1-\delta$ over
$S=\left\\{(i_{1},j_{1},y_{1})\ldots,(i_{M},j_{M},y_{M})\right\\}$.

###  A.1 Supporting lemmas for the proof of Theorem 3.3

####  A.1.1 Rademacher complexity bound for $\mathcal{P}_{\mathcal{F},\bm{X}}$

######  Definition A.1 (Rademacher complexity).

Let $A\subset R^{m}$ be a set of vectors. We define Rademacher complexity of
$A$ as

$R(A)\triangleq\frac{1}{m}\mathop{\mathbb{E}}_{\bm{\sigma}}\left[\sup_{\bm{a}\in
A}\sum_{i=1}^{m}\sigma_{i}a_{i}\right],$

where $\sigma_{1},\ldots,\sigma_{m}\in\left\\{-1,1\right\\}$ are i.i.d.
distributed according to ${\sf Pr}\left(\sigma_{i}=1\right)={\sf
Pr}\left(\sigma_{i}=-1\right)=0.5$.

######  Definition A.2 (Covering number).

Let $A\subset R^{m}$ be a set of vectors. We say that $A$ is $r$-covered by a
set $A^{\prime}$, with respect to metric $d$ if for all $\bm{a}\in A$, there
exists $\bm{a}^{\prime}\in A^{\prime}$ with $d(a,a^{\prime})\leq r$. We define
by $\mathcal{N}(r,A,d)$ the cardinality of the smallest $A^{\prime}$ that
$r$-covers $A$.

######  Lemma A.3 (Rademacher complexity bound).

Consider function class $\mathcal{F}$ satisfying Assumptions 3.2 , and that
$\alpha<\bm{f}(\bm{x})^{{\\!\top\\!}}\bm{f}(\bm{y})<1-\alpha,\;\forall\bm{x},\bm{y}\in\mathcal{X},\forall\bm{f}\in\mathcal{F}$.
Then, we have

$\mathcal{R}(\ell\circ\mathcal{P}_{\mathcal{F},\bm{X}}\circ
S)\leq\dfrac{4\log(1/\alpha)}{M}+\dfrac{6\sqrt{2}\log M}{\alpha M\log
2}\left\lVert\bm{S}_{\bm{X}}\right\rVert_{\rm F}\sqrt{R_{\texttt{NET}}},$

where $\ell\circ\mathcal{P}_{\mathcal{F},\bm{X}}\circ
S\triangleq\left\\{[\ell(\bm{P},(i_{1},j_{1},y_{1})),\ldots,\ell(\bm{P},(i_{M},j_{M},y_{M}))]\in\mathbb{R}^{M}\mid\bm{P}\in\mathcal{P}_{\mathcal{F},\bm{X}}\right\\}$,
$\mathcal{R}(A)$ denotes Rademacher complexity of set
$A\subseteq\mathbb{R}^{M}$, $\mathcal{P}_{\mathcal{F},\bm{X}}$ was defined in
(16), $S=\left\\{(i_{1},j_{1},y_{1}),\ldots,(i_{M},j_{M},y_{M})\right\\}$, and
the loss function $\ell$ was defined in (15).

###### Proof.

We start with deriving the covering number of an $\epsilon$-net of the set
$\ell\circ\mathcal{P}_{\bm{X}}\circ S$:

$\displaystyle\mathcal{N}(\epsilon,\ell\circ\mathcal{P}_{\bm{X}}\circ
S,\left\lVert\cdot\right\rVert)$
$\displaystyle=\mathcal{N}(\epsilon,\ell\circ\texttt{dot}\circ\bm{f}^{\prime}\circ
S,\left\lVert\cdot\right\rVert)$
$\displaystyle\leq\mathcal{N}(\epsilon/L_{\ell},\texttt{dot}\circ\bm{f}^{\prime}\circ
S,\left\lVert\cdot\right\rVert)$ (24)
$\displaystyle\leq\mathcal{N}\big{(}\epsilon/(2L_{\ell}),\bm{f}^{\prime}\circ
S,\left\lVert\cdot\right\rVert_{\rm F}\big{)}$ (25)
$\displaystyle\leq\mathcal{N}\big{(}\epsilon/(L_{\ell}\sqrt{2}),\bm{f}\circ
S_{\bm{X}}^{(1)},\left\lVert\cdot\right\rVert_{\rm
F}\big{)}\mathcal{N}\big{(}\epsilon/(L_{\ell}\sqrt{2}),\bm{f}\circ
S_{\bm{X}}^{(2)},\left\lVert\cdot\right\rVert_{\rm F}\big{)}$ (26)
$\displaystyle=\mathcal{N}\big{(}\epsilon/(L_{\ell}\sqrt{2}),\texttt{softmax}\circ\texttt{net}\circ
S_{\bm{X}}^{(1)},\left\lVert\cdot\right\rVert_{\rm
F}\big{)}\mathcal{N}\big{(}\epsilon/(L_{\ell}\sqrt{2}),\texttt{softmax}\circ\texttt{net}\circ
S_{\bm{X}}^{(2)},\left\lVert\cdot\right\rVert_{\rm F}\big{)}$
$\displaystyle\leq\mathcal{N}\big{(}\epsilon/(L_{\ell}\sqrt{2}),\texttt{net}\circ
S_{\bm{X}}^{(1)},\left\lVert\cdot\right\rVert_{\rm
F}\big{)}\mathcal{N}\big{(}\epsilon/(L_{\ell}\sqrt{2}),\texttt{net}\circ
S_{\bm{X}}^{(2)},\left\lVert\cdot\right\rVert_{\rm
F}\big{)}\quad\text{({softmax} is $1$-Lipschitz continuous)}$
$\displaystyle\leq\exp\left(\dfrac{\left\lVert\bm{S}_{\bm{X}}^{(1)}\right\rVert^{2}_{\rm
F}}{\epsilon^{2}/(2L^{2}_{\ell})}R_{\texttt{NET}}+\dfrac{\left\lVert\bm{S}_{\bm{X}}^{(2)}\right\rVert^{2}_{\rm
F}}{\epsilon^{2}/(2L^{2}_{\ell})}R_{\texttt{NET}}\right)\quad\text{(By
Lemma~{}\ref{lemma:covering_number_resnet})}$
$\displaystyle=\exp\left(\left(\left\lVert\bm{S}_{\bm{X}}^{(1)}\right\rVert_{\rm
F}^{2}+\left\lVert\bm{S}_{\bm{X}}^{(2)}\right\rVert_{\rm
F}^{2}\right)\dfrac{2R_{\texttt{NET}}L^{2}_{\ell}}{\epsilon^{2}}\right)$ (27)

Eq. (24) holds by applying Lemma A.7 and the fact that function
$\phi_{y}(P_{W})\triangleq-y\log(P_{W})-(1-y)\log(1-P_{W})$ is
$L_{\ell}$-Lipschitz continuous. Specifically, $L_{\ell}=(1/\alpha)$ since for
$\alpha\leq p_{1},p_{2}\leq 1-\alpha$,

$\displaystyle\left\lvert\phi_{y}(p_{1})-\phi_{y}(p_{2})\right\rvert$
$\displaystyle=\left\lvert-y\log\dfrac{p_{1}}{p_{2}}-(1-y)\log\dfrac{1-p_{1}}{1-p_{2}}\right\rvert$
$\displaystyle\leq\left\lvert\log\dfrac{p_{1}}{p_{2}}\right\rvert+\left\lvert\log\dfrac{1-p_{1}}{1-p_{2}}\right\rvert$
$\displaystyle\leq\left\lvert\dfrac{p_{1}-p_{2}}{p_{2}}\right\rvert+\left\lvert\dfrac{p_{2}-p_{1}}{1-p_{2}}\right\rvert\quad(\text{
by }\log(1+x)\leq x)$ $\displaystyle\leq\dfrac{1}{\alpha}\left\lvert
p_{1}-p_{2}\right\rvert=L_{\ell}\left\lvert p_{1}-p_{2}\right\rvert.$

Similarly, Eq. (25) holds by Lemma A.7 and the fact that for
$\;\forall\bm{u},\bm{v}\in\left\\{\bm{x}\mid\bm{x}\geq
0,\bm{1}^{{\\!\top\\!}}\bm{x}=1\right\\}$, function
$\texttt{dot}([\bm{u};\bm{v}])$ defined in (16b) is 2-Lipschitz continuous. To
see this, consider the following:

$\left\lVert\nabla\texttt{dot}([\bm{u};\bm{v}])\right\rVert=\left\lVert\begin{bmatrix}\bm{u}\\\
\bm{v}\end{bmatrix}\right\rVert\leq 2.$

Eq. (26) holds as a consequence of applying Lemma A.9 to the set
$\bm{f}^{\prime}\circ S$ which is

$\displaystyle\bm{f}^{\prime}\circ S$
$\displaystyle=\left\\{[\bm{Z}_{1},\bm{Z}_{2}]\in\mathbb{R}^{M\times
2K}\mid\bm{Z}_{1}\in\bm{f}\circ S_{\bm{X}}^{(1)},\bm{Z}_{2}\in\bm{f}\circ
S_{\bm{X}}^{(2)}\right\\},$ $\displaystyle\bm{S}^{(1)}_{\bm{X}}$
$\displaystyle=[\bm{x}_{\omega_{1}^{1}},\bm{x}_{\omega_{2}^{1}},\ldots,\bm{x}_{\omega_{M}^{1}}]\in\mathbb{R}^{D\times
M},$ $\displaystyle\bm{S}^{(2)}_{\bm{X}}$
$\displaystyle=[\bm{x}_{\omega_{1}^{2}},\bm{x}_{\omega_{2}^{2}},\ldots,\bm{x}_{\omega_{M}^{2}}]\in\mathbb{R}^{D\times
M}.$

Now we can proceed to bound $\mathcal{R}(\ell\circ\mathcal{P}_{\bm{X}}\circ
S)$ with the help of Dudley’s entropy integral.

Apply Lemma A.6 onto the set $\ell\circ\mathcal{P}_{\bm{X}}\circ S$ with
$c=2\log(1/\alpha)\sqrt{M}$ (by (18)), for any integer $T>0$,

$\displaystyle\mathcal{R}(\ell\circ\mathcal{P}_{\bm{X}}\circ S)$
$\displaystyle\leq\dfrac{c2^{-T}}{\sqrt{M}}+\dfrac{6c}{M}\sum^{T}_{t=1}2^{-t}\sqrt{\log(\mathcal{N}(c2^{-t},A))}\quad\text{(By
Lemma~{}\ref{lemma:chaining})}$
$\displaystyle\leq\dfrac{c2^{-T}}{\sqrt{M}}+\dfrac{6c}{M}\sum^{T}_{t=1}2^{-t}\sqrt{\left(\left\lVert\bm{S}_{\bm{X}}^{(1)}\right\rVert_{\rm
F}^{2}+\left\lVert\bm{S}_{\bm{X}}^{(2)}\right\rVert_{\rm
F}^{2}\right)\dfrac{2R_{\texttt{NET}}L^{2}_{\ell}}{c^{2}2^{-2t}}}\quad\text{(By
\eqref{eq:upper_bound_N})}$
$\displaystyle\leq\dfrac{c2^{-T}}{\sqrt{M}}+\dfrac{6T}{M}\sqrt{\left(\left\lVert\bm{S}_{\bm{X}}^{(1)}\right\rVert_{\rm
F}^{2}+\left\lVert\bm{S}_{\bm{X}}^{(2)}\right\rVert_{\rm
F}^{2}\right)2R_{\texttt{NET}}L^{2}_{\ell}}$
$\displaystyle=\dfrac{c2^{-T}}{\sqrt{M}}+\dfrac{6\sqrt{2}T}{M}\left\lVert\bm{S}_{\bm{X}}\right\rVert_{\rm
F}L_{\ell}\sqrt{R_{\texttt{NET}}}$
$\displaystyle=2\log(1/\alpha)2^{-T}+\dfrac{6\sqrt{2}T}{M}\left\lVert\bm{S}_{\bm{X}}\right\rVert_{\rm
F}L_{\ell}\sqrt{R_{\texttt{NET}}}\quad\text{(substitute $c$)}.$

Lastly, choosing $T=\lfloor\log_{2}M\rfloor$ and substituting
$L_{\ell}=1/\alpha$ concludes the proof,

$\displaystyle\mathcal{R}(\ell\circ\mathcal{P}_{\mathcal{F},\bm{X}}\circ S)$
$\displaystyle\leq
2\log(1/\alpha)2^{-\lfloor\log_{2}M\rfloor}+\dfrac{6\sqrt{2}{\lfloor\log_{2}M\rfloor}}{M}\left\lVert\bm{S}_{\bm{X}}\right\rVert_{\rm
F}L_{\ell}\sqrt{R_{\texttt{NET}}}$
$\displaystyle\leq\dfrac{4\log(1/\alpha)}{M}+\dfrac{6\sqrt{2}\log M}{\alpha
M\log 2}\left\lVert\bm{S}_{\bm{X}}\right\rVert_{\rm
F}\sqrt{R_{\texttt{NET}}}.$

This concludes the proof. ∎

####  A.1.2 Some others lemmas

######  Lemma A.4.

For $0\leq\bm{P},\bm{Q}\leq 1$ with the same size $N\times N$,

$\left\lVert\bm{P}-\bm{Q}\right\rVert_{\rm F}^{2}\leq
4N^{2}D_{H}^{2}(\bm{P},\bm{Q})\leq 4N^{2}D_{\rm kl}(\bm{Q}||\bm{P}),$

where

$\displaystyle D_{H}^{2}(\bm{P},\bm{Q})$
$\displaystyle\triangleq\dfrac{1}{N^{2}}\sum_{\omega\in[N]\times[N]}d_{H}^{2}(P_{\omega},Q_{\omega}),$
$\displaystyle D_{\rm kl}(\bm{P}||\bm{Q})$
$\displaystyle\triangleq\dfrac{1}{N^{2}}\sum_{\omega\in[N]\times[N]}d_{\rm
kl}(P_{\omega}||Q_{\omega}),$ (28)

and $d_{H}(p,q)$, $d_{\rm kl}(p,q)$ are typical Hellinger distance and KL
divergence for $0\leq p,q\leq 1$, resp, i.e.,

$\displaystyle d_{H}^{2}(p,q)$
$\displaystyle\triangleq\big{(}\sqrt{p}-\sqrt{q}\big{)}^{2}+\big{(}\sqrt{1-p}-\sqrt{1-q}\big{)}^{2},$
$\displaystyle d_{\rm kl}(p,q)$ $\displaystyle\triangleq
p\log\left(\dfrac{p}{q}\right)+(1-p)\log\left(\dfrac{1-p}{1-q}\right).$ (29)

###### Proof.

For the first inequality, we use the following result.

######  Lemma A.5 (Lemma 2, scalar version, (Davenport et al., 2014)).

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be any differential function, and s,t
are two real numbers satisfying $\left\lvert s\right\rvert,\left\lvert
t\right\rvert\leq\alpha$. Then

$d^{2}_{H}(f(s);f(t))\geq\inf_{\left\lvert
x\right\rvert\leq\alpha}\dfrac{f^{\prime}(x)^{2}}{8f(x)(1-f(x))}(s-t)^{2}.$

As a result, for $f(x)=x$, $0\leq p,q\leq 1$,

$d^{2}_{H}(p,q)\geq\inf_{\left\lvert x\right\rvert\leq
1}\dfrac{1}{8x(1-x)}(p-q)^{2}=\dfrac{1}{4}(p-q)^{2}.$

Summing across all elements of $\bm{P},\bm{Q}$ leads to,

$\left\lVert\bm{P}-\bm{Q}\right\rVert_{\rm F}^{2}\leq
4N^{2}D^{2}_{H}(\bm{P},\bm{Q}).$

The second inequality is simply derived from Jensen’s inequality and the fact
that $1-x\leq-\log x,\forall x>0$. ∎

######  Lemma A.6 (Dudley entropy integral).

((Shalev-Shwartz & Ben-David, 2014, Lemma 27.4)) Let $A\subset\mathbb{R}^{m}$,
$c=\min_{\overline{\bm{a}}\in\mathbb{R}^{m}}\max_{\bm{a}\in
A}\;\left\lVert\overline{\bm{a}}-\bm{a}\right\rVert$. Then, for any integer
$T>0$,

$R(A)\leq\dfrac{c2^{-T}}{\sqrt{m}}+\dfrac{6c}{m}\sum^{T}_{k=1}2^{-k}\sqrt{\log(N(c2^{-k},A))}.$

######  Lemma A.7.

For each $i\in[m]$, let
$\bm{\phi}_{i}:\mathbb{R}^{d_{1}}\rightarrow\mathbb{R}^{d_{2}}$ be a
$\rho$-Lipschitz function; namely, for all
$\bm{x},\bm{y}\in\mathbb{R}^{d_{1}}$ we have
$\left\lVert\bm{\phi}_{i}(\bm{x})-\bm{\phi}_{i}(\bm{y})\right\rVert\leq\rho\left\lVert\bm{x}-\bm{y}\right\rVert$.
For $\bm{A}\in\mathbb{R}^{d_{1}\times m}$ let $\bm{\Phi}(\bm{A})$ denote the
matrix $[\bm{\phi}_{1}(\bm{a}_{1}),\ldots,\bm{\phi}_{m}(\bm{a}_{m})]$. For
$\mathcal{A}\subset\mathbb{R}^{d_{1}\times m}$, let
$\bm{\Phi}\circ\mathcal{A}=\left\\{\bm{\Phi}(\bm{A})\mid\bm{A}\in\mathcal{A}\right\\}\subset\mathbb{R}^{d_{2}\times
m}$. Then,

$\mathcal{N}(\rho
r,\bm{\Phi}\circ\mathcal{A},\left\lVert\cdot\right\rVert_{\rm
F})\leq\mathcal{N}(r,\mathcal{A},\left\lVert\cdot\right\rVert_{\rm F}).$ (30)

######  Remark A.8.

Firstly, the choice of Frobenius norm in (30) is tied to $\ell_{2}$-norm
defining the $\rho$-Lipschitz function. Secondly, Lemma A.7 is a natural
generalization of (Shalev-Shwartz & Ben-David, 2014, Lemma 27.3).

###### Proof.

Define $\mathcal{A}^{\prime}$ as one of the smallest $r$-cover of
$\mathcal{A}$, i.e., for all $\bm{A}\in\mathcal{A}$ there exists
$\bm{A}^{\prime}\in\mathcal{A}^{\prime}$ such that
$\left\lVert\bm{A}-\bm{A}^{\prime}\right\rVert_{\rm F}\leq r$. By definition,
$\left\lvert\mathcal{A}^{\prime}\right\rvert=\mathcal{N}(r,\mathcal{A},\left\lVert\cdot\right\rVert_{\rm
F})$. Since

$\left\lVert\bm{\Phi}(\bm{A})-\bm{\Phi}(\bm{A}^{\prime})\right\rVert_{\rm
F}^{2}=\sum^{m}_{i=1}\left\lVert\bm{\phi}_{i}(\bm{a}_{i})-\bm{\phi}_{i}(\bm{a}^{\prime}_{i})\right\rVert^{2}\leq\sum^{m}_{i=1}\rho^{2}\left\lVert\bm{a}_{i}-\bm{a}^{\prime}_{i}\right\rVert^{2}=\rho^{2}\left\lVert\bm{A}-\bm{A}^{\prime}\right\rVert_{\rm
F}^{2}\leq\rho^{2}r^{2},$

$\bm{\Phi}\circ\mathcal{A}^{\prime}$ is a $\rho r$-cover of
$\bm{\Phi}\circ\mathcal{A}$. That implies $\mathcal{N}(\rho
r,\bm{\Phi}\circ\bm{A},\left\lVert\cdot\right\rVert_{\rm
F})\leq\left\lvert\bm{\Phi}\circ\mathcal{A}^{\prime}\right\rvert=\left\lvert\mathcal{A}^{\prime}\right\rvert=\mathcal{N}(r,\mathcal{A},\left\lVert\cdot\right\rVert_{\rm
F})$. ∎

######  Lemma A.9.

Given two sets $\mathcal{A}_{1},\mathcal{A}_{2}\subseteq\mathbb{R}^{m\times
d}$. Define
$\mathcal{A}_{3}\triangleq\left\\{[\bm{A}_{1},\bm{A}_{2}]\in\mathbb{R}^{m\times
2d}\mid\bm{A}_{1}\in\mathcal{A}_{1},\bm{A}_{2}\in\mathcal{A}_{2}\right\\}$,
then

$\mathcal{N}(\epsilon/\sqrt{2},\mathcal{A}_{3},\left\lVert\cdot\right\rVert_{\rm
F})\leq\mathcal{N}(\epsilon,\mathcal{A}_{1},\left\lVert\cdot\right\rVert_{\rm
F})\mathcal{N}(\epsilon,\mathcal{A}_{2},\left\lVert\cdot\right\rVert_{\rm
F}).$

###### Proof.

Let $\overline{\mathcal{A}}_{1},\overline{\mathcal{A}}_{2}$ be minimum
$\epsilon$-cover sets of $\mathcal{A}_{1},\mathcal{A}_{2}$, resp. By
definition, for all
$\bm{A}_{1}\in\mathcal{A}_{1},\bm{A}_{2}\in\mathcal{A}_{2}$,

$\displaystyle\exists\overline{\bm{A}}_{1}\in\overline{\mathcal{A}}_{1},\quad$
$\displaystyle\left\lVert\bm{A}_{1}-\overline{\bm{A}}_{1}\right\rVert_{\rm
F}^{2}\leq\epsilon^{2},\text{ and}$
$\displaystyle\exists\overline{\bm{A}}_{2}\in\overline{\mathcal{A}}_{2},\quad$
$\displaystyle\left\lVert\bm{A}_{2}-\overline{\bm{A}}_{2}\right\rVert_{\rm
F}^{2}\leq\epsilon^{2}$
$\Longrightarrow\quad\left\lVert[\bm{A}_{1},\bm{A}_{2}]-[\overline{\bm{A}}_{1},\overline{\bm{A}_{2}}]\right\rVert^{2}_{\rm
F}\leq 2\epsilon^{2}.$

Therefore, set
$\overline{\mathcal{A}}_{3}\triangleq\left\\{[\overline{\bm{A}}_{1},\overline{\bm{A}}_{2}]\in\mathbb{R}^{m\times
2d}\mid\overline{\bm{A}}_{1}\in\overline{\mathcal{A}}_{1},\overline{\bm{A}}_{2}\in\overline{\mathcal{A}}_{2}\right\\}$
is a $(\epsilon/\sqrt{2})$-cover set of $\mathcal{A}_{3}$, which leads to our
conclusion,

$\mathcal{N}(\epsilon/\sqrt{2},\mathcal{A}_{3},\left\lVert\cdot\right\rVert_{\rm
F})\leq\left\lvert\overline{\mathcal{A}}_{3}\right\rvert=\left\lvert\overline{\mathcal{A}}_{1}\right\rvert\left\lvert\overline{\mathcal{A}}_{2}\right\rvert=\mathcal{N}(\epsilon,\mathcal{A}_{1},\left\lVert\cdot\right\rVert_{\rm
F})\mathcal{N}(\epsilon,\mathcal{A}_{2},\left\lVert\cdot\right\rVert_{\rm
F}).$

∎

######  Lemma A.10.

Covering number of neural networks (Bartlett et al., 2017, Theorem 3.3) Let
fixed nonlinearities $(\sigma_{1},\ldots,\sigma_{L})$ and reference matrices
$(M_{1},\ldots,M_{L})$ be given, where $\sigma_{i}$ is $\rho_{i}$-Lipschitz
and $\sigma_{i}(0)=0$. Let spectral norm bounds $(s_{1},\ldots,s_{L})$, and
matrix (2,1) norm bounds $b_{1},\ldots,b_{L}$ be given. Let data matrix
$\bm{X}\in\mathbb{R}^{n\times d}$ be given, where the $n$ rows correspond to
data points. Let $\mathcal{H}_{\bm{X}}$ denote the family of matrices obtained
by evaluating $\bm{X}$ with all choices of network $F_{\mathcal{A}}$:

$\mathcal{H}_{\bm{X}}\triangleq\left\\{F_{\mathcal{A}}(\bm{X}^{{\\!\top\\!}})\mid\mathcal{A}=(\bm{A}_{1},\ldots,\bm{A}_{L}),\left\lVert\bm{A}_{i}\right\rVert_{\sigma}\leq
s_{i},\left\lVert\bm{A}_{i}^{{\\!\top\\!}}-\bm{I}\right\rVert_{2,1}\leq
b_{i}\right\\},$

where each matrix has dimension at most $D$ along each axis. Then for any
$\epsilon>0$,

$\displaystyle\log\mathcal{N}(\epsilon,\mathcal{H}_{\bm{X}},\left\lVert\cdot\right\rVert_{\rm
F})$ $\displaystyle\leq\dfrac{\left\lVert\bm{X}\right\rVert_{\rm
F}^{2}R_{\texttt{NET}}}{\epsilon^{2}},$

where
$R_{\texttt{NET}}=\log(2D^{2})\left(\prod_{j=1}^{L}s_{j}^{2}\rho_{j}^{2}\right)\left(\sum^{i}_{L}(b_{i}/s_{i})^{2/3}\right)^{3}$
is a constant depending only on the neural network’s properties.

##  Appendix B Proof of Theorem 3.4

Let
$\bm{M}^{\natural}=[\bm{f}^{\natural}(\bm{x}_{1}),\ldots,\bm{f}^{\natural}(\bm{x}_{N})]$.
As $\bm{M}^{\natural}$ satisfies separability condition, we assume that
$\bm{M}^{\natural}=[\bm{I},\bm{V}^{\natural}]$, which is w.o.l.g. Let
$\bm{M}^{\star}=[\bm{f}^{\star}(\bm{x}_{1}),\ldots,\bm{f}^{\star}(\bm{x}_{N})]$
denote the predicted cluster memberships, and also partition $\bm{M}^{\star}$
as
$\bm{M}^{\star}=[\bm{U}^{\star},\bm{V}^{\star}],\bm{U}^{\star}\in\mathbb{R}^{K\times
K}$. Then,

$\displaystyle\left\lVert\bm{P}^{\star}-\bm{P}^{\natural}\right\rVert_{\rm
F}^{2}$
$\displaystyle=\left\lVert(\bm{M}^{\star})^{{\\!\top\\!}}\bm{M}^{\star}-(\bm{M}^{\natural})^{{\\!\top\\!}}\bm{M}^{\natural}\right\rVert_{\rm
F}^{2}$
$\displaystyle=\left\lVert\begin{bmatrix}(\bm{U}^{\star})^{{\\!\top\\!}}\\\
(\bm{V}^{\star})^{{\\!\top\\!}}\end{bmatrix}\begin{bmatrix}\bm{U}^{\star}&\bm{V}^{\star}\end{bmatrix}-\begin{bmatrix}\bm{I}_{K}\\\
(\bm{V}^{\natural})^{{\\!\top\\!}}\end{bmatrix}\begin{bmatrix}\bm{I}_{K}&\bm{V}^{\natural}\end{bmatrix}\right\rVert_{\rm
F}^{2}$
$\displaystyle=\left\lVert(\bm{U}^{\star})^{{\\!\top\\!}}\bm{U}^{\star}-\bm{I}_{K}\right\rVert_{\rm
F}^{2}+2\left\lVert(\bm{U}^{\star})^{{\\!\top\\!}}\bm{V}^{\star}-\bm{V}^{\natural}\right\rVert_{\rm
F}^{2}+\left\lVert(\bm{V}^{\star})^{{\\!\top\\!}}\bm{V}^{\star}-(\bm{V}^{\natural})^{{\\!\top\\!}}\bm{V}^{\natural}\right\rVert_{\rm
F}^{2}.$ (31)

##### Analysis of the first term in (31).

Let
$Z=\dfrac{1}{N^{2}}\left\lVert\bm{P}^{\star}-\bm{P}^{\natural}\right\rVert_{\rm
F}^{2},0\leq Z\leq 1$ be a random variable with a PDF $f(z)$. By Lemma 3.3,

${\sf Pr}\left(Z\leq\epsilon(M,\delta)^{2}\right)\geq 1-\delta.$

We have

$\displaystyle\mathop{\mathbb{E}}[Z]=\int^{1}_{0}zf(z)dz=\int^{\epsilon(M,\delta)^{2}}_{0}zf(z)dz+\int^{1}_{\epsilon(M,\delta)^{2}}zf(z)dz$
$\displaystyle\leq\int^{\epsilon(M,\delta)^{2}}_{0}\epsilon(M,\delta)^{2}f(z)dz+\int^{1}_{\epsilon(M,\delta)^{2}}f(z)dz$
$\displaystyle\leq\epsilon(M,\delta)^{2}+\delta.$

Recall $S=\left\\{(i_{1},j_{1},y_{1}),\ldots,(i_{M},j_{M},y_{M})\right\\}$.
According to Lemma B.3,

$\mathop{\mathbb{E}}_{\bm{X},S}\left[(P^{\star}_{ij}-P^{\natural}_{ij})^{2}\right]=\text{const},\quad\;\forall(i,j)\in[N]^{2}.$

Therefore, for arbitrary $i,j\in[N]^{2}$,

$\displaystyle\mathop{\mathbb{E}}_{\bm{X},S}\left[(P^{\star}_{ij}-P^{\natural}_{ij})^{2}\right]$
$\displaystyle=\mathop{\mathbb{E}}_{\bm{X},S}\left[\dfrac{1}{N^{2}}\left\lVert\bm{P}^{\star}-\bm{P}^{\natural}\right\rVert_{\rm
F}^{2}\right]\leq\epsilon(M,\delta)^{2}+\delta.$

Meanwhile, by Markov inequality, for $\tau>0,$

${\sf
Pr}\left(\left(P^{\star}_{ij}-P^{\natural}_{ij}\right)^{2}\leq\tau\mathop{\mathbb{E}}_{\bm{X},S}\left[\left(P^{\star}_{ij}-P^{\natural}_{ij}\right)^{2}\right]\right)\geq
1-\dfrac{1}{\tau}.$

Setting $\tau=M^{1/4},\delta=e^{-\sqrt{M}}$ gives

$\displaystyle\left(P^{\star}_{ij}-P^{\natural}_{ij}\right)^{2}\leq
M^{1/4}\mathop{\mathbb{E}}_{\bm{X},S}\left[\left(P^{\star}_{ij}-P^{\natural}_{ij}\right)^{2}\right]\leq
M^{1/4}\epsilon(M,e^{-\sqrt{M}})^{2}+M^{1/4}e^{-\sqrt{M}}$

holds with probability at least $1-1/M^{1/4}$.

By union bound, the following holds with probability at least
$1-K^{2}/M^{1/4}$,

$\left\lVert(\bm{U}^{\star})^{{\\!\top\\!}}\bm{U}^{\star}-\bm{I}_{K}\right\rVert_{\rm
F}^{2}=\sum_{(i,j)\in[K]^{2}}(P^{\star}_{ij}-P^{\natural}_{ij})^{2}\leq
K^{2}\underbrace{(M^{1/4}\epsilon(M,e^{-\sqrt{M}})^{2}+M^{1/4}e^{-\sqrt{M}})}_{\epsilon^{\prime}(M)^{2}}=K^{2}\epsilon^{\prime}(M)^{2},$
(32)

where $\epsilon^{\prime}(M)$ is defined in (9). Inequality (32) implies

$\displaystyle
1-K\epsilon^{\prime}(M)\leq\left\lVert\bm{u}^{\star}_{k}\right\rVert^{2}\leq
1,\quad\forall k\in[K]$ (33) $\displaystyle
0\leq\langle\bm{u}^{\star}_{k},\bm{u}^{\star}_{\ell}\rangle\leq
K\epsilon^{\prime}(M),\quad\quad\;\forall k\neq\ell,k,\ell\in[K].$ (34)

For any permutation matrix $\bm{\Pi}\in\mathbb{R}^{K\times K}$,

$\displaystyle\left\lVert\bm{\Pi}\bm{U}^{\star}-\bm{I}\right\rVert_{\rm
F}^{2}=\sum^{K}_{k=1}\left\lVert\bm{u}^{\star}_{k}-\bm{\pi}_{k}\right\rVert^{2}$
$\displaystyle=K+\sum^{K}_{k=1}\left\lVert\bm{u}^{\star}_{k}\right\rVert^{2}-2\sum^{K}_{k=1}\langle\bm{u}^{\star}_{k},\bm{\pi}_{k}\rangle$
$\displaystyle\leq
2K-2\sum^{K}_{k=1}\langle\bm{u}^{\star}_{k},\bm{\pi}_{k}\rangle\quad\text{(Since
$\bm{u}_{k}^{\star}\geq 0,\bm{1}^{{\\!\top\\!}}\bm{u}_{k}^{\star}=1$ and thus
$\|\bm{u}_{k}^{\star}\|\leq 1$)}.$

Minimizing over $\bm{\Pi}$ on both sides,

$\min_{\bm{\Pi}}\left\lVert\bm{\Pi}\bm{U}^{\star}-\bm{I}\right\rVert_{\rm
F}^{2}\leq
2K-2\max_{\bm{\Pi}}\sum^{K}_{k=1}\langle\bm{u}^{\star}_{k},\bm{\pi}_{k}\rangle.$
(35)

Denote $k^{\star}_{i}:=\operatorname*{\arg\max}_{k}U^{\star}_{ki}$. Invoking
Lemma B.2 where $K\epsilon^{\prime}(M)<0.381$ (by (9)) and
$\bm{u}^{\star}_{k}$’s satisfy (33) and (34), it holds that
$k^{\star}_{1},\ldots,k^{\star}_{K}$ are all different integers, and we assume
w.o.l.g. that $k^{\star}_{1}=1,\ldots,k^{\star}_{K}=K$, i.e.,
$U^{\star}_{ii}=\operatorname*{\arg\max}_{k}U^{\star}_{ki}$. With that in
mind, we get a simple lower bound,

$\max_{\bm{\Pi}}\sum^{K}_{k=1}(\bm{u}_{k}^{\star})^{{\\!\top\\!}}\bm{\pi}_{k}\geq\sum^{K}_{k=1}U^{\star}_{kk}.$
(36)

Since $\left\lVert\bm{u}^{\star}_{1}\right\rVert^{2}\geq
1-K\epsilon^{\prime}(M)$ by (33),

$\displaystyle(U^{\star}_{11})^{2}$ $\displaystyle\geq
1-K\epsilon^{\prime}(M)-\sum^{K}_{k=2}(U^{\star}_{k1})^{2}\geq
1-K\epsilon^{\prime}(m)-\left(\sum^{K}_{k=2}U^{\star}_{k1}\right)^{2}=1-K\epsilon^{\prime}(m)-(1-U^{\star}_{11})^{2},$

where the second inequality holds since $U^{\star}_{k1}\geq 0,\;\forall
k\in[K]$, and the last equality holds since $\bm{u}_{1}$ is a probability
simplex vector. As $U_{11}^{\star}=\max_{k}U_{k1}$, $U_{11}^{\star}\geq 1/K$.
Solving the above quadratic inequality with respect to $1/K\leq
U^{\star}_{11}\leq 1$ and $K\epsilon^{\prime}(M)\leq 0.381$ (by (9)) leads to

$U^{\star}_{11}\geq\dfrac{1+\sqrt{1-2K\epsilon^{\prime}(M)}}{2}\geq
1-K\epsilon^{\prime}(M).$

Applying the same argument for $U^{\star}_{22},\ldots,U^{\star}_{KK}$,

$U^{\star}_{kk}\geq 1-K\epsilon^{\prime}(M),\quad k\in[K].$

Therefore,

$\min_{\bm{\Pi}}\left\lVert\bm{\Pi}\bm{U}^{\star}-\bm{I}\right\rVert_{\rm
F}^{2}\leq
2K-2\left(K-K^{2}\epsilon^{\prime}(M)\right)=2K^{2}\epsilon^{\prime}(M).$ (37)

This implies that $\bm{U}^{\star}$ is close to an identity matrix up to some
permutation.

##### Analysis of the second term in (31).

For a fixed $0<\delta<1$, suppose that the following event happens

$\dfrac{1}{N^{2}}\left\lVert\bm{P}^{\star}-\bm{P}^{\natural}\right\rVert_{\rm
F}^{2}\leq\epsilon(M,\delta)^{2}.$ (38)

Recall that
$\bm{M}^{\star}=[\bm{U}^{\star},\bm{V}^{\star}],\bm{M}^{\natural}=[\bm{I}_{K},\bm{V}^{\natural}]$,
then

$\left\lVert(\bm{U}^{\star})^{{\\!\top\\!}}\bm{V}^{\star}-\bm{V}^{\natural}\right\rVert_{\rm
F}\leq\dfrac{N\epsilon(M,\delta)}{\sqrt{2}}.$

Denote $\bm{\Pi}^{\star}$ as the optimal permutation matrix in LHS of (37). We
have

$\displaystyle\left\lVert(\bm{U}^{\star})^{{\\!\top\\!}}\bm{V}^{\star}-\bm{V}^{\natural}-((\bm{U}^{\star})^{{\\!\top\\!}}(\bm{\Pi}^{\star})^{{\\!\top\\!}}-\bm{I})\bm{V}^{\natural}\right\rVert_{\rm
F}$
$\displaystyle\leq\left\lVert(\bm{U}^{\star})^{{\\!\top\\!}}\bm{V}^{\star}-\bm{V}^{\natural}\right\rVert_{\rm
F}+\left\lVert((\bm{U}^{\star})^{{\\!\top\\!}}(\bm{\Pi}^{\star})^{{\\!\top\\!}}-\bm{I})\bm{V}^{\natural}\right\rVert_{\rm
F}$
$\displaystyle\leq\dfrac{N\epsilon(M,\delta)}{\sqrt{2}}+\sigma_{\max}(\bm{V}^{\natural})\left\lVert\bm{\Pi}^{\star}\bm{U}^{\star}-\bm{I}\right\rVert_{\rm
F}$
$\displaystyle\leq\dfrac{N\epsilon(M,\delta)}{\sqrt{2}}+\sigma_{\max}(\bm{V}^{\natural})K\sqrt{2\epsilon^{\prime}(M)}\quad\text{(thanks
to \eqref{eq:bound_first_partition})}.$ (39)

On the other hand,

$\displaystyle\left\lVert(\bm{U}^{\star})^{{\\!\top\\!}}\bm{V}^{\star}-\bm{V}^{\natural}-((\bm{U}^{\star})^{{\\!\top\\!}}(\bm{\Pi}^{\star})^{{\\!\top\\!}}-\bm{I})\bm{V}^{\natural}\right\rVert_{\rm
F}$
$\displaystyle=\left\lVert(\bm{U}^{\star})^{{\\!\top\\!}}(\bm{V}^{\star}-(\bm{\Pi}^{\star})^{{\\!\top\\!}}\bm{V}^{\natural})\right\rVert_{\rm
F}$
$\displaystyle\geq\sigma_{\min}(\bm{U}^{\star})\left\lVert\bm{V}^{\star}-(\bm{\Pi}^{\star})^{{\\!\top\\!}}\bm{V}^{\natural}\right\rVert_{\rm
F}$
$\displaystyle=\sigma_{\min}(\bm{U}^{\star})\left\lVert\bm{\Pi}^{\star}\bm{V}^{\star}-\bm{V}^{\natural}\right\rVert_{\rm
F}.$ (40)

Using Lemma B.1, we can upper bound $\sigma_{\min}(\bm{U}^{\star})$ as

$\left\lvert\sigma_{\min}(\bm{I}+\bm{\Pi}^{\star}\bm{U}^{\star}-\bm{I})-\sigma_{\min}(\bm{I})\right\rvert\leq\left\lVert\bm{\Pi}^{\star}\bm{U}^{\star}-\bm{I}\right\rVert_{\rm
F}\leq K\sqrt{2\epsilon^{\prime}(M)}\quad\text{(thanks to
\eqref{eq:bound_first_partition})}$

or,

$\sigma_{\min}(\bm{U}^{\star})=\sigma_{\min}(\bm{\Pi}^{\star}\bm{U}^{\star})\geq
1-K\sqrt{2\epsilon^{\prime}(M)}.$ (41)

Combine (39), (40), (41),

$\displaystyle\left\lVert\bm{\Pi}^{\star}\bm{V}^{\star}-\bm{V}^{\natural}\right\rVert_{\rm
F}^{2}$
$\displaystyle\leq\left(\dfrac{N\epsilon(M,\delta)+2\sigma_{\max}(\bm{V}^{\natural})K\sqrt{\epsilon^{\prime}(M)}}{\sqrt{2}-2K\sqrt{\epsilon^{\prime}(M)}}\right)^{2}$
$\displaystyle\leq
2\left(N\epsilon(M,\delta)+2\sigma_{\max}(\bm{V}^{\natural})K\sqrt{\epsilon^{\prime}(M)}\right)^{2}\quad\text{(Since
$8K^{2}\epsilon^{\prime}(M)\leq 1$ by \eqref{eq:condition_for_M})}$
$\displaystyle\leq
4N^{2}\epsilon(M,\delta)^{2}+16\sigma^{2}_{\max}(\bm{V}^{\natural})K^{2}\epsilon^{\prime}(M)\quad\text{(Cauchy-
Schwarz inequality)}.$ (42)

Lastly, combine (37) and (42), we finish our proof,

$\displaystyle\left\lVert\bm{\Pi}^{\star}\bm{M}^{\star}-\bm{M}^{\natural}\right\rVert_{\rm
F}^{2}$
$\displaystyle=\left\lVert\bm{\Pi}^{\star}\bm{U}-\bm{I}\right\rVert_{\rm
F}^{2}+\left\lVert\bm{\Pi}^{\star}\bm{V}-\bm{V}^{\natural}\right\rVert_{\rm
F}^{2}$ $\displaystyle\leq
2K^{2}\epsilon^{\prime}(M)+4N^{2}\epsilon(M,\delta)^{2}+16\sigma_{\max}^{2}(\bm{V}^{\natural})K^{2}\epsilon^{\prime}(M)$
$\displaystyle=4N^{2}\epsilon(M,\delta)^{2}+2K^{2}(1+8\sigma_{\max}^{2}(\bm{V}^{\natural}))\epsilon^{\prime}(M).$

Note that the whole computation is derived based on the realizations of 2
independent events in (32), (38) with probability of happening at least
$1-K^{2}/M^{1/4}$ and $1-\delta$, resp,

$\dfrac{1}{N}\left\lVert\bm{\Pi}^{\star}\bm{M}^{\star}-\bm{M}^{\natural}\right\rVert_{\rm
F}^{2}\leq
4N\epsilon(M,\delta)^{2}+\dfrac{2}{N}K^{2}(1+8\sigma_{\max}^{2}(\bm{V}^{\natural}))\epsilon^{\prime}(M).$

holds with probability at least $1-(\delta+K^{2}/M^{1/4})$.

###  B.1 Supporting Lemmas for proof of Theorem 3.4

######  Lemma B.1 ((Weyl, 1912)).

Let $\bm{X},\bm{\Delta}\in\mathbb{R}^{m\times n}$,

$\left\lvert\sigma_{i}(\bm{X}+\bm{\Delta})-\sigma_{i}(\bm{\Delta})\right\rvert\leq\left\lVert\bm{\Delta}\right\rVert_{2}\quad(\;\leq\left\lVert\bm{\Delta}\right\rVert_{\rm
F}),\quad 1\leq i\leq\min(m,n).$

######  Lemma B.2.

Define
$A_{\epsilon}=\left\\{\bm{x}\in\mathbb{R}^{K}\mid\bm{1}^{{\\!\top\\!}}\bm{x}=1,\bm{x}\geq
0,\left\lVert\bm{x}\right\rVert_{2}^{2}\geq 1-\epsilon\right\\}$. If
$\epsilon\leq 0.381$, then

$\max_{\bm{x},\bm{y}\in
A_{\epsilon}}\bm{x}^{{\\!\top\\!}}\bm{y}\leq\epsilon\quad\Rightarrow\quad\operatorname*{\arg\max}_{k}x_{k}\neq\operatorname*{\arg\max}_{k}y_{k}.$

###### Proof.

We use contradiction to prove the claim. Suppose that
$\operatorname*{\arg\max}_{k}x_{k}=\operatorname*{\arg\min}_{k}y_{k}=\widetilde{k}$.
Without loss of generality, let us assume $\widetilde{k}=1$. Using these
assumptions, we will show that $\min_{\bm{x},\bm{y}\in
A_{\epsilon}}\;\bm{x}^{{\\!\top\\!}}\bm{y}>\epsilon$. Indeed,

$\displaystyle 1-\epsilon\leq\left\lVert\bm{x}\right\rVert^{2}\leq
x_{1}\left(\sum^{K}_{k=1}x_{k}\right)=x_{1}.$

Similarly, we obtain $y_{1}\geq 1-\epsilon$, which leads to

$\bm{x}^{{\\!\top\\!}}\bm{y}\geq(1-\epsilon)^{2}>\epsilon,$

where the second inequality holds because $\epsilon\leq 0.381$. ∎

######  Lemma B.3.

Assume that $\omega=(\omega^{1},\omega^{2})$ is a uniform RV over
$[N]\times[N]$ where $\omega^{1}\in[N],\omega^{2}\in[N]$, and
$\bm{x}_{1},\ldots,\bm{x}_{N}$ are i.i.d. Define the following mappings:

$\displaystyle\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{N},\omega)$
$\displaystyle\triangleq(\bm{x}_{\omega^{1}},\bm{x}_{\omega^{2}}),$
$\displaystyle\texttt{gen}(\omega_{1},\ldots,\omega_{M},y_{1},\ldots,y_{M},\bm{x}_{1},\ldots,\bm{x}_{N})$
$\displaystyle\triangleq\left\\{\bm{\psi}_{1},\ldots,\bm{\psi}_{M}\right\\},\quad\bm{\psi}_{i}\triangleq(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{N},\omega_{i}),y_{i}),$

where

$\displaystyle\omega_{i}=(k,\ell)\in[N]^{2},\quad$ $\displaystyle 1\leq i\leq
M,$ $\displaystyle y_{i}\in\left\\{0,1\right\\},$ $\displaystyle 1\leq i\leq
M,$ $\displaystyle\bm{x}_{i}\in\mathcal{X},$ $\displaystyle 1\leq i\leq N.$

For a real-valued function
$h(\bm{u},\bm{v},\texttt{gen}(\omega_{1},\ldots,\omega_{M},y_{1},\ldots,y_{M},\bm{x}_{1},\ldots,\bm{x}_{N}))$
with $\bm{u},\bm{v}\in\mathcal{X}$, we have: $\;\forall y_{1},\ldots,y_{M}$,
and $\;\forall i,j,i^{\prime},j^{\prime}\in[N]$,

$\mathop{\mathbb{E}}_{\begin{subarray}{c}\omega_{i},1\leq i\leq M,\\\
\bm{x}_{i},1\leq i\leq
N\end{subarray}}[h(\bm{x}_{i},\bm{x}_{j},\texttt{gen}(\omega_{1},\ldots,\omega_{M},y_{1},\ldots,y_{M},\bm{x}_{1},\ldots,\bm{x}_{N}))]=\\\
\mathop{\mathbb{E}}_{\begin{subarray}{c}\omega_{i},1\leq i\leq M,\\\
\bm{x}_{i},1\leq i\leq
N\end{subarray}}[h(\bm{x}_{i^{\prime}},\bm{x}_{j^{\prime}},\texttt{gen}(\omega_{1},\ldots,\omega_{M},y_{1},\ldots,y_{M},\bm{x}_{1},\ldots,\bm{x}_{N}))].$
(43)

###### Proof.

We have the following property on the mapping gen: $\;\forall i\neq
j,i,j\in[N]$,

$\texttt{gen}(\omega_{1},\ldots,\omega_{M},y_{1},\ldots,y_{M},\ldots,\bm{x}_{i},\ldots,\bm{x}_{j},\ldots,\bm{x}_{N})=\\\
\texttt{gen}(s_{ij}(\omega_{1}),\ldots,s_{ij}(\omega_{M}),y_{1},\ldots,y_{M},\ldots,\bm{x}_{j},\ldots,\bm{x}_{i},\ldots,\bm{x}_{N}),$
(44)

where $s_{ij}:[N]^{2}\to[N]^{2}$,

$s_{ij}(\omega)=s_{ij}((k,\ell))\triangleq\begin{cases}(k,\ell)\quad&\text{ if
}k\neq i\text{ and }\ell\neq j\\\ (j,\ell)\quad&\text{ if }k=i\text{ and
}\ell\neq j\\\ (k,i)\quad&\text{ if }k\neq i\text{ and }\ell=j\\\
(j,i)\quad&\text{ if }k=i\text{ and }\ell=j\end{cases}$

To see this, let

$\displaystyle\mathcal{G}_{1}$
$\displaystyle=\texttt{gen}(\omega_{1},\ldots,\omega_{M},y_{1},\ldots,y_{M},\ldots,\bm{x}_{i},\ldots,\bm{x}_{j},\ldots,\bm{x}_{N}),$
$\displaystyle\mathcal{G}_{2}$
$\displaystyle=\texttt{gen}(s_{ij}(\omega_{1}),\ldots,s_{ij}(\omega_{M}),y_{1},\ldots,y_{M},\ldots,\bm{x}_{j},\ldots,\bm{x}_{i},\ldots,\bm{x}_{N}).$

Pick
$\bm{\psi}=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{i},\ldots,\bm{x}_{j},\ldots,\bm{x}_{N},\omega),y)\in\mathcal{G}_{1}$.
Assume $\omega=(k,\ell)$. Consider the following cases,

  * •

If $k\neq i$ and $\ell\neq j$, then $s_{ij}(\omega)=\omega$. So

$\bm{\psi}=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{j},\ldots,\bm{x}_{i},\ldots,\bm{x}_{N},s_{ij}(\omega)),y)\in\mathcal{G}_{2}.$

  * •

If $k=i$ and $\ell\neq j$, then $s_{ij}(\omega)=s_{ij}((i,\ell))=(j,\ell)$. So

$\displaystyle\bm{\psi}$
$\displaystyle=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{i},\ldots,\bm{x}_{j},\ldots,\bm{x}_{N},(i,\ell)),y)$
$\displaystyle=(\bm{x}_{i},\bm{x}_{\ell},y)$
$\displaystyle=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{j},\ldots,\bm{x}_{i},\ldots,\bm{x}_{N},(j,\ell)),y)$
$\displaystyle=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{j},\ldots,\bm{x}_{i},\ldots,\bm{x}_{N},s_{ij}(\omega)),y)\in\mathcal{G}_{2}\quad\text{(by
definition of the mapping {gen})}.$

  * •

If $k\neq i$ and $\ell=j$, then $s_{ij}(\omega)=s_{ij}((k,j))=(k,i)$. So

$\displaystyle\bm{\psi}$
$\displaystyle=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{i},\ldots,\bm{x}_{j},\ldots,\bm{x}_{N},(k,j)),y)$
$\displaystyle=(\bm{x}_{k},\bm{x}_{j},y)$
$\displaystyle=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{j},\ldots,\bm{x}_{i},\ldots,\bm{x}_{N},(k,i)),y)$
$\displaystyle=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{j},\ldots,\bm{x}_{i},\ldots,\bm{x}_{N},s_{ij}(\omega)),y)\in\mathcal{G}_{2}\quad\text{(by
definition of the mapping {gen})}.$

  * •

If $k=i$ and $\ell=j$, then $s_{ij}(\omega)=s_{ij}((i,j))=(j,i)$. So

$\displaystyle\bm{\psi}$
$\displaystyle=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{i},\ldots,\bm{x}_{j},\ldots,\bm{x}_{N},(i,j)),y)$
$\displaystyle=(\bm{x}_{i},\bm{x}_{j},y)$
$\displaystyle=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{j},\ldots,\bm{x}_{i},\ldots,\bm{x}_{N},(j,i)),y)$
$\displaystyle=(\texttt{pick}(\bm{x}_{1},\ldots,\bm{x}_{j},\ldots,\bm{x}_{i},\ldots,\bm{x}_{N},s_{ij}(\omega)),y)\in\mathcal{G}_{2}\quad\text{(by
definition of the mapping {gen})}.$

Since $\psi\in\mathcal{G}_{1}$ is arbitrary,
$\mathcal{G}_{1}\subseteq\mathcal{G}_{2}$. Moreover,
$\left\lvert\mathcal{G}_{1}\right\rvert=\left\lvert\mathcal{G}_{2}\right\rvert$,
so $\mathcal{G}_{1}=\mathcal{G}_{2}$, and hence (44) holds.

Notice that the mapping $s_{ij}(\omega)$ is surjective and onto $[N]^{2}$, we
proceed with the following

$\displaystyle\mathop{\mathbb{E}}_{\begin{subarray}{c}\bm{x}_{i},\bm{x}_{i^{\prime}},\\\
\bm{x}_{k,k=[N]\setminus\left\\{i,i^{\prime}\right\\}},\\\
\omega_{1},\ldots,\omega_{M}\end{subarray}}\left[h(\bm{x}_{i},\bm{x}_{j},\texttt{gen}(\omega_{1},\ldots,\omega_{M},y_{1},...,y_{M},\ldots,\bm{x}_{i},\ldots,\bm{x}_{i^{\prime}},\ldots))\right]$
$\displaystyle\quad=\mathop{\mathbb{E}}_{\begin{subarray}{c}\bm{x}_{i},\bm{x}_{i^{\prime}},\\\
\bm{x}_{k,k=[N]\setminus\left\\{i,i^{\prime}\right\\}},\\\
\omega_{1},\ldots,\omega_{M}\end{subarray}}\left[h(\bm{x}_{i},\bm{x}_{j},\texttt{gen}(s_{ii^{\prime}}(\omega_{1}),\ldots,s_{ii^{\prime}}(\omega_{M}),y_{1},\ldots,y_{M},\ldots,\bm{x}_{i^{\prime}},\ldots,\bm{x}_{i},\ldots)\right]$
$\displaystyle\quad=\mathop{\mathbb{E}}_{\begin{subarray}{c}\bm{u},\bm{v},\\\
\bm{x}_{k,k=[N]\setminus\left\\{i,i^{\prime}\right\\}},\\\
\omega_{1},\ldots,\omega_{M}\end{subarray}}\left[h(\bm{u},\bm{x}_{j},\texttt{gen}(s_{ii^{\prime}}(\omega_{1}),\ldots,s_{ii^{\prime}}(\omega_{M}),y_{1},\ldots,y_{M},\ldots,\bm{v},\ldots,\bm{u},\ldots))\right]$
$\displaystyle\quad=\mathbb{E}_{\begin{subarray}{c}\bm{x}_{i^{\prime}},\bm{x}_{i},\\\
\bm{x}_{k,k=[N]\setminus\left\\{i,i^{\prime}\right\\}},\\\
\omega_{1},\ldots,\omega_{M}\end{subarray}}\left[h(\bm{x}_{i^{\prime}},\bm{x}_{j},\texttt{gen}(s_{ii^{\prime}}(\omega_{1}),\ldots,s_{ii^{\prime}}(\omega_{M}),y_{1},\ldots,y_{M},\ldots,\bm{x}_{i},\ldots,\bm{x}_{i^{\prime}},\ldots))\right].$

The first equality holds by property (44), the second and the third equality
hold as we just rename some random variables under the expectation. Proceed
with the same argument to replace $j$ with $j^{\prime}$, we obtain

$\mathbb{E}_{\begin{subarray}{c}\bm{x}_{1},\ldots,\bm{x}_{N},\\\
\omega_{1},\ldots,\omega_{M}\end{subarray}}\left[h(\bm{x}_{i^{\prime}},\bm{x}_{j},\texttt{gen}(s_{ii^{\prime}}(\omega_{1}),\ldots,s_{ii^{\prime}}(\omega_{M}),y_{1},\ldots,y_{M},\bm{x}_{1},\ldots,\bm{x}_{N}))\right]\\\
=\mathbb{E}_{\begin{subarray}{c}\bm{x}_{1},\ldots,\bm{x}_{N},\\\
\omega_{1},\ldots,\omega_{M}\end{subarray}}\left[h(\bm{x}_{i^{\prime}},\bm{x}_{j^{\prime}},\texttt{gen}(s_{jj^{\prime}}(s_{ii^{\prime}}(\omega_{1})),\ldots,s_{jj^{\prime}}(s_{ii^{\prime}}(\omega_{M})),y_{1},\ldots,y_{M},\bm{x}_{1},\ldots,\bm{x}_{N}))\right].$
(45)

Since $s_{ii^{\prime}}(\omega)$ is surjective and onto itself,
$s_{ii^{\prime}}(\omega)$ has the same probability distribution as $\omega$.
So $s_{jj^{\prime}}(s_{ii^{\prime}}(\omega))$ also define a RV with the same
PDF as $\omega$, and hence (45) implies (43).

∎

##  Appendix C Proof of Theorem 3.5

We start with the following key lemma:

######  Lemma C.1.

With probability at least $1-\delta$ over $\bm{x}_{1},\ldots,\bm{x}_{N}$,

$\mathop{\mathbb{E}}_{\bm{x}\sim\mathcal{P}_{\mathcal{X}}}\left[\left\lVert\bm{\Pi}^{\star}\bm{f}^{\star}(\bm{x})-\bm{f}^{\natural}(\bm{x})\right\rVert^{2}\right]\leq\dfrac{1}{N}\left\lVert\bm{\Pi}^{\star}\bm{M}^{\star}-\bm{M}^{\natural}\right\rVert_{\rm
F}^{2}+\dfrac{8}{N}+\dfrac{12\sqrt{2R_{\texttt{NET}}}\left\lVert\bm{X}\right\rVert_{\rm
F}\log N}{N\log 2}+8\sqrt{\dfrac{2\log(4\delta)}{N}},$

where $\bm{\Pi}^{\star}$ is the optimal permutation matrix in LHS of (37) in
the proof of Theorem 3.4.

###### Proof.

Let us define the following:

$\displaystyle L_{\bm{X}}(\bm{f})$
$\displaystyle\triangleq\dfrac{1}{N}\sum^{N}_{n=1}{\rm
SE}(\bm{f},(\bm{x}_{n},\bm{m}^{\natural}_{n})),$ $\displaystyle{\rm
SE}(\bm{f},(\bm{x},\bm{m}))$
$\displaystyle\triangleq\left\lVert\bm{\Pi}^{\star}\bm{f}(\bm{x})-\bm{m}\right\rVert^{2}.$

Note that $L_{\bm{X}}(\bm{f})$ can be viewed as the empirical loss in
statistical learning where a dataset of $N$ i.i.d samples
$(\bm{x}_{1},\bm{m}_{1}^{\natural}),\ldots,(\bm{x}_{N},\bm{m}^{\natural}_{N})$
are given. Denote $\mathcal{P}_{\mathcal{X},\bm{f}^{\natural}}$ as the PDF of
the joint distribution of $(\bm{x}_{n},\bm{m}^{\natural}_{n})$, and define

$L_{\mathcal{P}_{\mathcal{X},\bm{f}^{\natural}}}(\bm{f})\triangleq\mathop{\mathbb{E}}_{(\bm{x},\bm{m}^{\natural})\sim\mathcal{P}_{\mathcal{X},\bm{f}^{\natural}}}\left[{\rm
SE}(\bm{f},(\bm{x},\bm{m}^{\natural}))\right],$

which is the expected loss. Then it is readily to apply a standard
generalization bound from (Shalev-Shwartz & Ben-David, 2014, Theorem 26.5)
using the fact that ${\rm SE}(\bm{f},(\bm{x},\bm{m}))\leq 2$. That is, we have
that

$L_{\mathcal{P}_{\mathcal{X},\bm{f}^{\natural}}}(\bm{f}^{\star})\leq
L_{\bm{X}}(\bm{f}^{\star})+2\mathcal{R}({\rm
SE}\circ\mathcal{F}\circ\bm{X})+8\sqrt{\dfrac{2\log(4/\delta)}{N}},$

holds with probability of at least $1-\delta$. The first term is

$L_{\bm{X}}(\bm{f}^{\star})=\dfrac{1}{N}\left\lVert\bm{\Pi}^{\star}\bm{M}^{\star}-\bm{M}^{\natural}\right\rVert_{\rm
F}^{2}.$

The second term is bounded by following the proof of Lemma A.3,

$\displaystyle\mathcal{N}\left(\epsilon,{\rm
SE}\circ\mathcal{F}\circ\bm{X},\left\lVert\cdot\right\rVert\right)$
$\displaystyle\leq\mathcal{N}\left(\dfrac{\epsilon}{2\sqrt{2}},\mathcal{F}\circ\bm{X},\left\lVert\cdot\right\rVert_{\rm
F}\right)$ (46)
$\displaystyle\leq\exp\left(\dfrac{8R_{\texttt{NET}}\left\lVert\bm{X}\right\rVert_{\rm
F}^{2}}{\epsilon^{2}}\right)\quad\text{(By
Lemma~{}\ref{lemma:covering_number_resnet})}.$

Inequality (46) holds by applying Lemma A.7 and the fact that function
$\phi_{\bm{m}}(\bm{x})\triangleq\left\lVert\bm{x}-\bm{m}\right\rVert^{2}$ is
$2\sqrt{2}$-Lipschitz continuous on the domain
$\bm{\Delta}=\left\\{\bm{x}\in\mathbb{R}^{K}\mid\bm{x}\geq
0,\bm{1}^{{\\!\top\\!}}\bm{x}=1\right\\}$. This is because of the following
fact:

$\left\lVert\nabla\phi_{\bm{m}}(\bm{x})\right\rVert=2\left\lVert\bm{x}-\bm{m}\right\rVert\leq
2\sqrt{2}.$

We proceed by deriving a bound on $\mathcal{R}({\rm
SE}\circ\mathcal{F}\circ\bm{X})$ with the help of Dudley’s entropy integral
technique. In particular, applying Lemma A.6 on the set ${\rm
SE}\circ\mathcal{F}\circ\bm{X}$, the following holds: For any integer $T>0$,

$\displaystyle\mathcal{R}({\rm SE}\circ\mathcal{F}\circ\bm{X})$
$\displaystyle\leq\dfrac{c2^{-T}}{\sqrt{N}}+\dfrac{6c}{N}\sum^{T}_{t=1}2^{-t}\sqrt{\log(\mathcal{N}(c2^{-t},{\rm
SE}\circ\mathcal{F}\circ\bm{X}))}$
$\displaystyle\leq\dfrac{c2^{-T}}{\sqrt{N}}+\dfrac{6c}{N}\sum^{T}_{t=1}2^{-t}\sqrt{\dfrac{8R_{\texttt{NET}}\left\lVert\bm{X}\right\rVert_{\rm
F}^{2}}{c^{2}2^{-2t}}}$
$\displaystyle=\dfrac{c2^{-T}}{\sqrt{N}}+\dfrac{12T\sqrt{2R_{\texttt{NET}}}\left\lVert\bm{X}\right\rVert_{\rm
F}}{N}.$

Substituting $c=2$ as the upper bound of the loss ${\rm SE}$ and setting
$T=\lfloor 0.5\log_{2}(N)\rfloor$ gives

$\mathcal{R}({\rm
SE}\circ\mathcal{F}\circ\bm{X})\leq\dfrac{4}{N}+\dfrac{6\sqrt{2R_{\texttt{NET}}}\left\lVert\bm{X}\right\rVert_{\rm
F}\log N}{N\log 2}.$

Therefore,

$\mathop{\mathbb{E}}_{(\bm{x},\bm{m}^{\natural})\sim\mathcal{P}_{\mathcal{X}},\bm{f}^{\natural}}\left[\left\lVert\bm{\Pi}^{\star}\bm{f}^{\star}(\bm{x})-\bm{m}^{\natural}\right\rVert^{2}\right]\leq\dfrac{1}{N}\left\lVert\bm{\Pi}^{\star}\bm{M}^{\star}-\bm{M}^{\natural}\right\rVert_{\rm
F}^{2}+\dfrac{8}{N}+\dfrac{12\sqrt{2R_{\texttt{NET}}}\left\lVert\bm{X}\right\rVert_{\rm
F}\log N}{N\log 2}+8\sqrt{\dfrac{2\log(4/\delta)}{N}}$

holds with probability of at least $1-\delta$. ∎

By Theorem 3.4,

$L_{\bm{X}}(\bm{f}^{\star})=\dfrac{1}{N}\min_{\bm{\Pi}}\sum^{N}_{n=1}\left\lVert\bm{\Pi}\bm{M}^{\star}-\bm{M}^{\natural}\right\rVert_{\rm
F}^{2}\leq
4N\epsilon(M,\delta)^{2}+\dfrac{2}{N}K^{2}(1+8\sigma_{\max}^{2}(\bm{V}^{\natural}))\epsilon^{\prime}(M)$

holds with probability of at least $1-\delta-K^{2}/M^{0.25}$. Invoking Lemma
C.1 gives the conclusion,

$\mathop{\mathbb{E}}_{(\bm{x},\bm{m}^{\natural})\sim\mathcal{P}_{\mathcal{X}},\bm{f}^{\natural}}\left[\left\lVert\bm{\Pi}^{\star}\bm{f}^{\star}(\bm{x})-\bm{m}^{\natural}\right\rVert^{2}\right]\leq
4N\epsilon(M,\delta)^{2}+\dfrac{2}{N}K^{2}(1+8\sigma_{\max}^{2}(\bm{V}^{\natural}))\epsilon^{\prime}(M)\\\
+\dfrac{8}{N}+\dfrac{12\sqrt{2R_{\texttt{NET}}}\left\lVert\bm{X}\right\rVert_{\rm
F}\log N}{N\log 2}+8\sqrt{\dfrac{2\log(4/\delta)}{N}},$

hold with probability of at least $1-\delta-K^{2}/M^{0.25}$.

##  Appendix D Proof of Theorem 3.7

As
$\max\big{(}\log(1/\alpha),\log(M)\sqrt{R_{\texttt{net}}}/\alpha\big{)}/\sqrt{M}\rightarrow
0$, $\left\lVert\bm{P}^{\star}-\bm{P}^{\natural}\right\rVert_{\rm F}^{2}\to 0$
accords to Lemma 3.3, which means

$(\bm{M}^{\star})^{{\\!\top\\!}}\bm{M}^{\star}=\bm{P}^{\natural}.$

This gives a guarantee that there exists permutation matrix $\bm{\Pi}$ such
that $\bm{\Pi}\bm{M}^{{}^{\star}}=\bm{M}^{\natural}$ by invoking (Huang et
al., 2014, Theorem 4). Lastly, applying Lemma C.1 concludes the proof.

##  Appendix E Proof of Theorem 4.1

Invoking Lemma 3.3 and considering
$\max\big{(}\log(1/\alpha),\log(M)\sqrt{R_{\texttt{net}}}/\alpha\big{)}/\sqrt{M}\rightarrow
0$ gives

$\bm{P}^{\star}=(\bm{M}^{\star})^{{\\!\top\\!}}(\bm{A}^{\star})^{{\\!\top\\!}}\bm{A}^{\star}\bm{M}^{\star}=\bm{P}^{\natural}$

at the limit. As assumed in Theorem 4.1,
$\operatorname{rank}((\bm{M}^{\natural})^{{\\!\top\\!}}(\bm{A})^{{\\!\top\\!}}\bm{A})=K$,
thus $\operatorname{rank}(\bm{M}^{\star})=K$. As proved in (Huang et al.,
2016), $\bm{M}^{\natural}$ satisfying SSC means ${\rm
rank}(\bm{M}^{\natural})=K$, which also means
$\operatorname{rank}((\bm{M}^{\natural})^{{\\!\top\\!}}(\bm{A})^{{\\!\top\\!}}\bm{A})=K$
if ${\rm rank}(\bm{A})=K$. It implies that there exists an invertible matrix
$\bm{Q}$ such that $\bm{M}^{\star}=\bm{Q}^{-1}\bm{M}^{\natural}$. To proceed,
we use the following proposition which is a part of the proof of Theorem 1 in
(Fu et al., 2015b).

######  Proposition E.1.

For $K\leq N$, let $\bm{M}\in\mathbb{R}^{K\times N}$ be a matrix of rank $K$
and $\bm{M}\geq 0,\bm{1}^{{\\!\top\\!}}\bm{M}=\bm{1}$. For any invertible
matrix $\bm{Q}$ such that $\widehat{\bm{M}}\triangleq\bm{Q}^{-1}\bm{M}$
satisfies $\widehat{\bm{M}}\geq
0,\bm{1}^{{\\!\top\\!}}\widehat{\bm{M}}=\bm{1}^{{\\!\top\\!}}$, then
$\left\lvert\det\bm{Q}\right\rvert\geq 1$. In addition, the equality holds if
and only if $\bm{Q}$ is a permutation matrix.

By Proposition E.1, $\left\lvert\det(\bm{Q})\right\rvert\geq 1$, and hence

$\det(\bm{M}^{\star}(\bm{M}^{\star})^{{\\!\top\\!}})=\det(\bm{Q}^{-1}\bm{M}^{\natural}(\bm{M}^{\natural})^{{\\!\top\\!}}\bm{Q}^{-{\\!\top\\!}})=\det(\bm{Q})^{-2}\det\left(\bm{M}^{\natural}(\bm{M}^{\natural})^{{\\!\top\\!}}\right)\leq\det\left(\bm{M}^{\natural}(\bm{M}^{\natural})^{{\\!\top\\!}}\right).$
(47)

As we take the solution of (12) with the $\bm{M}^{\star}$ that has the largest
volume, the equality in (47) is attained. Therefore, $\bm{Q}$ can only be a
permutation matrix. The rest follows by applying Lemma C.1.

##  Appendix F Additional Experiments

###  F.1 Effect of Neural Network Complexity

In this section, we present some additional experiments. To be specific, we
repeat experiments in Tables 1 and 2 using a more complex neural network for
all the DCC methods. The purpose is to observe the effect of $R_{\sf NET}$,
i.e., the complexity of the neural network. Here, all the DCC methods use a
three-hidden-layer fully connected neural networks, where each hidden layer
has 512 ReLU activation functions. In the main text, the DCC methods used a
two-hidden layer network, also with 512 activation functions in each layer.

Tables 5 and 6 show the new results. Overall, similar results as in the main
text can be seen: VolMaxDCC outperforms all other baselines, especially when
noise level is getting larger. In addition, VolMaxDCC enjoys a better
clustering performance when using a more complex (and thus more expressive)
neural network on STL10. When, the noise level is 15%, the new ACC of
VolMaxDCC is (0.85,0.86), which is much higher than the previous case that
used a two-hidden layer neural network (0.79,0.81). On CIFAR-10, some slight
decrease of clustering accuracy occasionally appears. This may also suggest
that using a deeper neural network may not always be the best choice. As
implied in our theorems, a more complex neural network increases
$R_{\texttt{NET}}$, which may increase the risk of overfitting—especially when
$N$ is not very large. In practice, the neural network structure may be
selected following standard procedures, e.g., using validation sets, if
available.

Table 5: Clustering performance of (seen data, unseen data) on STL10; $N_{\rm
unseen}=2000$.

Noise level Methods | DC-GMM | C-IDEC | VanillaDCC | VolMaxDCC
---|---|---|---|---
0.0% | ACC |  0.89, 0.87 |  0.88, 0.87 | 0.88, 0.86 |  0.92, 0.91
NMI |  0.83, 0.80 | 0.79, 0.78 | 0.79, 0.76 |  0.84, 0.82
ARI | 0.80, 0.78 | 0.77, 0.76 |  0.82, 0.80 |  0.84, 0.83
8.3% | ACC |  0.78, 0.79 |  0.77, 0.79 | 0.76, 0.77 |  0.85, 0.86
NMI |  0.68, 0.70 | 0.67, 0.69 | 0.56, 0.59 |  0.73, 0.75
ARI | 0.59, 0.61 | 0.59, 0.61 |  0.66, 0.68 |  0.77, 0.78
10.3% | ACC |  0.72, 0.74 | 0.69, 0.70 | 0.69, 0.71 |  0.84, 0.85
NMI |  0.63, 0.65 | 0.58, 0.60 | 0.47, 0.49 |  0.72, 0.73
ARI | 0.51, 0.53 | 0.49, 0.51 |  0.60, 0.61 |  0.77, 0.78
15.0% | ACC |  0.59, 0.59 | 0.56, 0.57 | 0.54, 0.55 |  0.85, 0.86
NMI |  0.52, 0.53 | 0.49, 0.50 | 0.33, 0.34 |  0.72, 0.74
ARI | 0.36, 0.37 | 0.37, 0.38 |  0.48, 0.49 |  0.77, 0.78

Table 6: Clustering performance of (seen data, unseen data) on CIFAR10;
$N_{\rm unseen}=45000$.

Noise level Methods | DC-GMM | C-IDEC | VanillaDCC | VolMaxDCC
---|---|---|---|---
0.0% | ACC |  0.90, 0.89 | 0.88, 0.87 | 0.89, 0.87 |  0.91, 0.90
NMI |  0.83, 0.80 |  0.81, 0.79 | 0.80, 0.77 |  0.83, 0.80
ARI |  0.82, 0.79 | 0.79, 0.76 |  0.82, 0.79 |  0.84, 0.82
4.9% | ACC |  0.86, 0.86 |  0.85, 0.86 |  0.85, 0.86 |  0.86, 0.86
NMI |  0.77, 0.77 |  0.77, 0.77 |  0.73, 0.73 |  0.73, 0.74
ARI |  0.73, 0.73 |  0.73, 0.74 |  0.77, 0.77 |  0.77, 0.77
8.7% | ACC |  0.78, 0.78 | 0.76, 0.77 | 0.76, 0.77 |  0.81, 0.81
NMI |  0.72, 0.72 |  0.70, 0.70 | 0.58, 0.58 | 0.65, 0.66
ARI | 0.59, 0.60 | 0.59, 0.59 |  0.70, 0.70 |  0.73, 0.73
10.9% | ACC | 0.70, 0.71 |  0.74, 0.75 | 0.67, 0.68 |  0.81, 0.81
NMI |  0.64, 0.65 |  0.66, 0.66 | 0.47, 0.48 |  0.65, 0.66
ARI | 0.50, 0.51 | 0.56, 0.57 |  0.61, 0.61 |  0.74, 0.74

###  F.2 Effect of Pretrained Features

To see the effect of pre-training, we re-run the methods with feature vectors
output by less well-trained feature extractors by (Li et al., 2021b). To be
specific, here, the extractor is trained using 600 epochs, instead of 1000
epochs as in the main text. Nonetheless, similar results are observed in Table
7.

Table 7: Clustering performance of (seen data, unseen data) on ImageNet10;
$N_{\text{unseen}}=2000$; embedding vectors are extracted by training (Li et
al., 2021b) for 600 epochs.

Noise level Methods | K-means | COP-Kmeans | PCKmeans | DC-GMM | C-IDEC | VanillaDCC | VolMaxDCC
---|---|---|---|---|---|---|---
0.0% | ACC |  0.83, — |  0.79$\pm$0.06, — |  0.74$\pm$0.07, — |  0.97$\pm$0.00, 0.96$\pm$0.00 |  0.96$\pm$0.00, 0.96$\pm$0.00 |  0.96$\pm$0.00, 0.96$\pm$0.00 |  0.97$\pm$0.00, 0.96$\pm$0.00
NMI | 0.78, — |  0.76$\pm$0.03, — |  0.76$\pm$0.03, — |  0.92$\pm$0.00, 0.90$\pm$0.01 |  0.91$\pm$0.00, 0.91$\pm$0.00 |  0.93$\pm$0.00, 0.91$\pm$0.00 |  0.93$\pm$0.00, 0.91$\pm$0.00
ARI | 0.66, — |  0.66$\pm$0.06, — |  0.59$\pm$0.10, — |  0.93$\pm$0.00, 0.90$\pm$0.01 |  0.92$\pm$0.00, 0.91$\pm$0.00 |  0.92$\pm$0.00, 0.91$\pm$0.00 |  0.92$\pm$0.01, 0.91$\pm$0.00
4.4% | ACC | — |  0.81$\pm$0.03, — |  0.66$\pm$0.05, — |  0.91$\pm$0.00, 0.91$\pm$0.00 |  0.94$\pm$0.01, 0.94$\pm$0.01 |  0.89$\pm$0.01, 0.90$\pm$0.01 |  0.92$\pm$0.02, 0.92$\pm$0.02
NMI | — |  0.75$\pm$0.01, — |  0.73$\pm$0.02, — |  0.85$\pm$0.01, 0.86$\pm$0.01 |  0.89$\pm$0.01, 0.89$\pm$0.01 |  0.80$\pm$0.00, 0.80$\pm$0.01 |  0.85$\pm$0.02, 0.85$\pm$0.02
ARI | — |  0.66$\pm$0.03, — |  0.54$\pm$0.07, — |  0.82$\pm$0.01, 0.82$\pm$0.01 |  0.88$\pm$0.02, 0.87$\pm$0.02 |  0.83$\pm$0.01, 0.84$\pm$0.01 |  0.87$\pm$0.01, 0.87$\pm$0.01
5.8% | ACC | — |  0.80$\pm$0.03, — |  0.73$\pm$0.07, — |  0.85$\pm$0.03, 0.85$\pm$0.04 |  0.92$\pm$0.01, 0.92$\pm$0.01 |  0.81$\pm$0.00, 0.81$\pm$0.00 |  0.92$\pm$0.01, 0.92$\pm$0.01
NMI | — |  0.74$\pm$0.01, — |  0.76$\pm$0.04, — |  0.81$\pm$0.01, 0.82$\pm$0.01 |  0.86$\pm$0.01, 0.87$\pm$0.00 |  0.72$\pm$0.01, 0.72$\pm$0.01 |  0.84$\pm$0.01, 0.85$\pm$0.02