# Neural Manifold Clustering and Embedding

Zengyi Li1,2, Yubei Chen4, Yann LeCun4, Friedrich T. Sommer1,3
1 Redwood Center 2 Physics Dept. 3 Helen Wills Neuroscience Inst., UC Berkeley
4 Facebook AI Research
{zengyi_li<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Given a union of non-linear manifolds, non-linear subspace clustering or
manifold clustering aims to cluster data points based on manifold structures
and also learn to parameterize each manifold as a linear subspace in a feature
space. Deep neural networks have the potential to achieve this goal under
highly non-linear settings given their large capacity and flexibility. We
argue that achieving manifold clustering with neural networks requires two
essential ingredients: a domain-specific constraint that ensures the
identification of the manifolds, and a learning algorithm for embedding each
manifold to a linear subspace in the feature space. This work shows that many
constraints can be implemented by data augmentation. For subspace feature
learning, Maximum Coding Rate Reduction (MCR2) objective can be used. Putting
them together yields Neural Manifold Clustering and Embedding (NMCE), a novel
method for general purpose manifold clustering, which significantly
outperforms autoencoder-based deep subspace clustering. Further, on more
challenging natural image datasets, NMCE can also outperform other algorithms
specifically designed for clustering. Qualitatively, we demonstrate that NMCE
learns a meaningful and interpretable feature space. As the formulation of
NMCE is closely related to several important Self-supervised learning (SSL)
methods, we believe this work can help us build a deeper understanding on SSL
representation learning.

##  1 Introduction

Here we investigate unsupervised representation learning, which aims to learn
structures (features) from data without the use of any label. If the data lie
in a linear subspace, the linear subspace can be extracted by Principal
Component Analysis (PCA) (Jolliffe, 1986), one of the most basic forms of
unsupervised learning. When the data occupy a union of several linear
subspaces, subspace clustering (SC) (Vidal et al., 2016) is needed to cluster
each data point to a subspace as well as estimating the parameters of each
subspace. Here we are concerned with even more challenging scenarios, when
data points come from a union of several non-linear low-dimensional manifolds.
In such scenarios, the clustering problem can be formulated as follows
(Elhamifar & Vidal, 2011):

######  Task 1.

Manifold Clustering and Embedding: Given that the data points come from a
union of low-dimensional manifolds, we shall segment the data points based on
their corresponding manifolds, and obtain a low-dimensional embedding for each
manifold.

Various methods have been developed to solve this problem (Abdolali & Gillis,
2021), but it is still an open question how to use neural networks effectively
in manifold clustering problems (Haeffele et al., 2020). In this paper, we
propose neural manifold clustering and embedding (NMCE) that follows three
principles: 1) The clustering and representation should respect a domain-
specific constraint, e.g. local neighborhoods, local linear interpolation or
data augmentation invariances. 2) The embedding of a particular manifold shall
not collapse. 3) The embedding of identified manifolds shall be linearized and
separated, i.e. they occupy different linear subspaces. We achieve 1) using
data augmentations, and achieve 2) and 3) with the subspace feature learning
algorithm maximal coding rate reduction (MCR2) objective (Yu et al., 2020).
This work make the following specific contributions:

  1. 1.

We combine data augmentation with MCR2 to yield a novel algorithm for general
purpose manifold clustering and embedding (NMCE). We also discuss connections
between the algorithm and self-supervised contrastive learning.

  2. 2.

We demonstrate that NMCE achieves strong performance on standard subspace
clustering benchmarks, and can outperform the best clustering algorithms on
more challenging high-dimensional image datasets like CIFAR-10 and CIFAR-20.
Further, empirical evaluation suggests that our algorithm also learns a
meaningful feature space.

##  2 Related Work

Manifold Learning. In classical manifold learning, the goal is to map the
manifold-structured data points to a low-dimensional representation space such
that the manifold structure is preserved. There are two key ingredients: 1)
Choosing a geometric property from the original data space to be preserved.
For example, the local euclidean neighborhood (Belkin & Niyogi, 2003), or
linear interpolation by neighboring data points (Roweis & Saul, 2000). 2) The
embedding should not collapse to a trivial solution. To avoid the trivial
solution, the variance of the embedding space is typically constrained in
spectral-based manifold learning methods.

Manifold Clustering and Embedding. When the data should be modeled as a union
of several manifolds, manifold clustering is needed in addition to manifold
learning. When these manifolds are linear, subspace clustering algorithms (Ma
et al., 2007; Elhamifar & Vidal, 2013; Vidal et al., 2016) can be used. When
they are non-linear, manifold clustering and embedding methods were proposed.
They generally divide into 3 categories (Abdolali & Gillis, 2021): 1. Locality
preserving. 2. Kernel based. 3. Neural Network based. Locality preserving
techniques implicitly make the assumption that the manifolds are smooth, and
are sampled densely (Souvenir & Pless, 2005; Elhamifar & Vidal, 2011; Chen et
al., 2018). Additionally, smoothness assumption can be employed (Gong et al.,
2012). Our method generalizes those techniques by realizing them with
geometrical constraints. The success of kernel based techniques depends
strongly on the suitability of the underlying kernel, and generally requires a
representation of the data in a space with higher dimension than the data
space (Patel & Vidal, 2014). Deep subspace clustering methods, such as Ji et
al. (2017); Zhang et al. (2019); Zhou et al. (2018) jointly perform linear
subspace clustering and representation learning, and has the potential to
handle high dimensional non-linear data effectively. However, it has been
shown that most performance gains obtained by those methods should be
attributed to an ad-hoc post-processing step applied to the self-expression
matrix. Using neural networks only provide a very marginal gain compared to
clustering the raw data directly using linear SC (Haeffele et al., 2020). Our
work differs from those techniques mainly in two aspects: i) While most of the
previous methods were generative (autoencoders, GANs), our loss function is
defined in the latent embedding space and is best understood as a contrastive
method. ii) While previous methods use self-expression based SC to guide
feature learning, ours uses MCR2 to learn the subspace features. Recently,
some deep SC techniques also applied data augmentation (Sun et al., 2019;
Abavisani et al., 2020). However, in those works, data augmentation played a
complementary role of improving the performance. In our method, data
augmentation plays a central role for enabling the identification of the
clusters.

Self-Supervised Representation Learning. Recently, self-supervised
representation learning achieved tremendous success with deep neural networks.
Similar to manifold clustering and embedding, there are also two essential
ingredients: 1) Data augmentations are used to define the domain-specific
invariance. 2) The latent representation should not collapse. The second
requirement can be achieved either by contrastive learning (Chen et al.,
2020), momentum encoder (He et al., 2020; Grill et al., 2020) or siamese
network structure (Chen & He, 2021). More directly related to our work is Tao
et al. (2021), which proposed feature orthogonalization and decorrelation,
alongside contrastive learning. Recently, variance regularization along was
also successfully used to achieve principle 2) (Zbontar et al., 2021; Bardes
et al., 2021), attaining state-of-the-art SSL representation performance. Part
of our method, the total coding rate (TCR) objective achieves a similar
effect, see discussion in Appendix A.6. However, beyond self-supervised
features, our algorithm additionally show strong clustering performance, and
directly learns a meaningful latent space. The simultaneous manifold
clustering and embedding in NMCE is also related to online deep clustering
(Caron et al., 2018; 2020) method. Also notable is Deshmukh et al. (2021),
where the concept of population consistency is closely related to the
constraint functional we discussed.

Clustering with Data Augmentation Our method use data augmentation to ensure
correct clustering of the training data. Although not explicitly pointed out,
this is also the case for other clustering techniques (Shen et al., 2021; Tsai
et al., 2020; Li et al., 2021). Our understanding of data augmentation is also
consistent to works that specifically study the success of data augmentations
(HaoChen et al., 2021; von Kügelgen et al., 2021).

##  3 Neural Manifold clustering and Embedding

###  3.1 Problem Setup

Let’s assume data points $x_{i}\in\mathbb{R}^{d}$ are sampled from a union
$\bigcup_{j=1}^{n}\mathsf{X}_{j}$ of manifolds
$\mathsf{X}_{1},\mathsf{X}_{2},...,\mathsf{X}_{n}$.111We do not consider
topological issues here and assume that all of them are homeomorphic to
$\mathbb{R}^{d_{i}}$ for some $d_{i}$ As stated in Task 1, the goal of
manifold clustering and embedding is to assign each data point to the
corresponding manifold (clustering), as well as learning a coordinate for each
manifold (manifold learning). To achieve this goal, we use neural network $f$,
which learns to map a data point $x$ to the feature embedding
$z\in\mathbb{R}^{d_{emb}}$ and the cluster assignment $c\in[1,n]$, i.e.
$z,c=f(x)$. The cluster assignment shall be equal to the ground-truth manifold
assignment,222Up to a permutation since the training is unsupervised. $z$
should parameterize the coordinates of the corresponding manifold
$\mathsf{X}_{c}$.

To make the feature space easier to work with, one can enforce the additional
separability requirement that for any $\mathsf{X}_{j},\mathsf{X}_{k}$ and
$j\neq k$, the feature vectors are perpendicular,
$\mathsf{Z}_{j}\perp\mathsf{Z}_{k}$. Here $\mathsf{Z_{j}}$ denotes the
embedding feature vectors of data points in $\mathsf{X_{j}}$, and we define
perpendicular between two sets in the following fashion: If
$\tilde{\mathsf{Z}}_{j}\subseteq\mathsf{Z}_{j},\tilde{\mathsf{Z}}_{k}\subseteq\mathsf{Z}_{k}$
such that $\forall
z_{j}\in\tilde{\mathsf{Z}}_{j},z_{k}\in\tilde{\mathsf{Z}}_{k}$, we have
$z_{j}\cdot z_{k}\neq 0$, then either $\tilde{\mathsf{Z}}_{j}$ or
$\tilde{\mathsf{Z}}_{k}$ has zero measure.

In the following, we first argue that to make clustering possible with a
neural network, one should define the additional geometric constraint that
makes the manifold clusters identifiable. Second, we discuss how to implement
the required geometric constraints and combine them with a recently proposed
joint clustering and subspace learning algorithm MCR2 (Yu et al., 2020) to
achieve neural manifold clustering and embeddng (NMCE).

Figure 1: Locality constraint enforced by adding Gaussian noise as data
augmentation allows neural network to find the desired non-linear manifolds.

###  3.2 Clustering always involves implicit assumptions

Even the simplest clustering algorithms rely on implicit assumptions. For
example, in k-means clustering, the implicit assumption is that the clusters
in the original data space are continuous in terms of L2 distance. For Linear
SC, the assumption is that data points are co-linear within each cluster. If a
neural network is trained on example data to learn a cluster assignment
function $c=f(x)$, the resulting clustering will be arbitrary and not resemble
the solution of k-means or linear SC clustering. This is because neural
networks are flexible and no constraint is imposed on the clustering function
to force the result to respect the geometry of the original data. One example
of this is shown in Figure 1 left panel, where a deep clustering method
outputs a rather arbitrary clustering for the double spiral data.

To make the clusters learnable for a neural network, one needs to introduce
constraints explicitly. In the example in Figure 1, one can easily reason
that, to be able to separate the two spirals from each other, the clustering
function needs to ensure that all close neighbors of a point from the data
distribution are assigned to the same cluster, essentially the same assumption
implicitly made in locality-based manifold clustering algorithms (Abdolali &
Gillis, 2021). We formalize the notion of constraints to a constraint
functional $D(f)$ (for a specific data distribution) that has the following
property: All cluster assignment functions $f$ that makes $D$ attain its
minimum value (assumed to be 0) and also cluster data points to the ground
truth number of clusters will correctly cluster all data points. For example,
we can construct a functional $D$ that takes value $D=0$ for all clustering
functions that satisfy the locality constraint on the dataset, and $D>0$
otherwise. This notion of constraint function is completely general. For
example, linear subspace clustering is recovered if the constraint function
take value $0$ if and only if the found clusters are linear subspace.

In practice, one usually cannot optimize the neural network clustering
function $f$ subject to $D=0$, since the correct solution would have to be
found at initialization. A more practical way to use the constraint function
is to use the relaxed objective with weighting $\lambda$:

$L(f)=L_{clst}(f)+\lambda*D(f)$ (1)

where $L_{clst}$ is some objective function that will force $f$ to cluster the
dataset. With a suitable $\lambda$, optimizing this objective leads to
learning of the correct clusters, by the assumption above. To achieve manifold
clustering, one just needs to find the appropriate constraint functional.

###  3.3 Subspace feature learning with Maximum Coding Rate Reduction

Having introduced explicit constraints for learning the manifold clustering
with neural networks, we still need a concrete algorithm for learning a linear
subspace-structured representation given the clustering (manifold learning).
Fortunately, the recently proposed principle of Maximum Coding Rate Reduction
(MCR2) (Yu et al., 2020) provides a principled learning objective for this
purpose. We denote the dataset (union of all manifolds) by $\mathsf{X}$, and
random variable that represent distribution on each manifold $\mathsf{X}_{i}$
by $\mathcal{X}_{i}$. For a certain encoder $\mathcal{Z}=f(\mathcal{X})$
(without clustering output), $z\in\mathbb{R}^{d_{emb}}$, the Gaussian coding
rate function is defined to be:

$R(\mathcal{Z},\epsilon)=\frac{1}{2}\mathsf{logdet}(\mathbf{I}+\frac{d_{emb}}{\epsilon^{2}}\mathsf{cov}(\mathcal{Z}))$
(2)

where $\mathsf{cov}$ denotes the covariance matrix function for a vector
random variable: $\mathsf{cov}(\mathcal{Z})=\mathbf{E}_{p(z)}[zz^{T}]$. This
function is approximately the Shannon coding rate of a multivariate Gaussian
distribution given average distortion $\epsilon$ (Cover, 1999), and can be
motivated by a ball-packing argument. However, we focus on its geometric
implication and do not discuss the information-theoretic aspect further.
Readers interested to the full introduction of this objective can refer to the
original papers (Yu et al., 2020; Ma et al., 2007).

Suppose for now that we are also given the cluster assignment function $c(x)$
that outputs the manifold index $c(x)=i$ for $x\in\mathsf{X}_{i}$. We can then
calculate the average coding rate for a particular cluster $i$ as
$R(\mathcal{Z}_{i},\epsilon)$, where $\mathcal{Z}_{i}=f(\mathcal{X}_{i})$. The
MCR2 principle states that, to learn a subspace-structured representation, one
needs to optimize $f$ by maximizing the difference between the coding rate of
all of $\mathcal{Z}$ and the sum of coding rate for each cluster
$\mathcal{Z}_{i}$:

$\Delta
R(\mathcal{Z},c,\epsilon)=R(\mathcal{Z},\epsilon)-\sum_{i=1}^{n}R(\mathcal{Z}_{i},\epsilon)$
(3)

Intuitively, this objective minimizes the sum of volume of each cluster to
push each of them into a lower-dimensional representation, while a the same
time maximize the total volume of the union of all clusters to avoid collapse.
It has been shown that MCR2 guarantees the perpendicularity requirement in the
problem setup above. Theorem A.6 in Yu et al. (2020) states that under the
assumption that $\mathsf{rank}(\mathsf{Z}_{i})$ is bounded, and the coding
error $\epsilon$ is sufficiently low, maximizing the MCR2 objective guarantees
that $\mathsf{Z}_{i}\perp\mathsf{Z}_{j}$ for any $i\neq j$, and the rank of
each $\mathsf{Z}_{i}$ is as large as possible.

###  3.4 Neural Manifold Clustering and Embedding

The MCR2 principle can be extended to the case where the labeling function
$c(x)$ is not given, but is instead learned jointly by optimizing the MCR2
objective. In this case, we fuse the clustering function into $f$: $z,c=f(x)$,
note that now $\mathcal{Z}_{i}$ depends on $f$ implicitly. However, as
discussed earlier, one will not be able to find the correct clusters by using
MCR2 alone, as it is unconstrained in the data space. An additional constraint
term $D(f)$ has to be included to make the clusters identifiable. This leads
to the Neural Manifold Clustering and Embedding (NMCE) objective:

$L_{NMCE}(f,\epsilon)=\sum_{i=1}^{n}R(\mathcal{Z}_{i},\epsilon)-R(\mathcal{Z},\epsilon)+\lambda
D(f)$ (4)

It is possible to replace the MCR2 objective in (4) by any other objective for
subspace feature learning, however, this generalization is left for future
work. Given a suitable constraint functional $D$, the NMCE objective will
guide the neural network to cluster the manifold correctly and also learn the
subspace-structured feature, thus achieving manifold clustering and embedding.
We explain in the next section how $D$ can be practically implemented.

###  3.5 Implementing constraints via data augmentation

Here we propose a simple method to implement various very useful constraints.
The proposed method uses data augmentations, a very common technique in
machine learning, and enforce two conditions on the clustering and embedding
function $f$: 1. Augmented data points generated from the same point should
belong to the same cluster. 2. The learnt feature embedding of augmented data
points should be similar if they are generated from the same point. We use
$\mathcal{T}(x)$ to represent a random augmentation of $x$:
$c,z=f(\mathcal{T}(x))$,
$c^{\prime},z^{\prime}=f(\mathcal{T}^{{}^{\prime}}(x))$, then
$D(f)=E_{p(x)}\mathsf{sim}(z,z^{\prime})$. Here, $\mathsf{sim}$ is a function
that measures similarity between latent representations, for example cosine
similarity, or L2 distance. The requirements $c=c^{\prime}$ can be enforced by
using average of $c$ and $c^{\prime}$ to assign $z$ and $z^{\prime}$ to
clusters during training.

For the double spiral example, the augmentation is simply to add a small
amount of Gaussian noise to data points. This will have the effect of forcing
neighboring points in the data manifold to also be neighbors in the feature
space and be assigned to the same cluster. The result of using this constraint
in the NMCE objective can be seen in Figure 1 middle and right panel. For more
difficult datasets like images, one needs to add augmentations to constrain
the clustering in the desired way. The quality of clustering is typically
measured by how well it correspond to the underlying content information
(object class). Therefore, we need augmentations that perturbs style
information (color, textures and background) but preserves content
information, so that the clustering will be based on content but not style.
Fortunately, extensive research in self-supervised contrastive learning has
empirically found augmentations that achieves that very effectively (Chen et
al., 2020; von Kügelgen et al., 2021).

###  3.6 Multistage training and relationship to self-supervised contrastive
learning

In practice, we find that for all but the simplest toy experiments it is
difficult to optimize the full NMCE objective (Eq. 4) from scratch. This is
because the clusters are incorrectly assigned at the start of training, and
the sum in Eq 4 effectively cancels out the total coding rate term
$R(\mathcal{Z},\epsilon)$, making it hard to initialize the training. We
observe that to achieve high coding rate difference, it is critical to achieve
high total coding rate first, so we resort to a multistage training procedure,
with the first stage always being optimizing the following objective:

$L_{TCR}(f,\epsilon)=-R(\mathcal{Z},\epsilon)+\lambda D(f)$ (5)

We call this the Total Coding Rate (TCR) objective, which is a novel self-
supervised learning objective by itself. Through simple arguments (Appendix
A.6) one can see that this objective encourages the covariance matrix of
$\mathcal{Z}$ to be diagonal. Along with a similarity constraint between
augmented samples, this objective turns out to asymptotically achieve the same
goal as VICReg (Bardes et al., 2021) and BarlowTwins (Zbontar et al., 2021).
We discuss this further in Appendix A.6.

After training with the TCR objective, we found that usually the feature
$\mathcal{Z}$ already possess approximate subspace structure. For simple
tasks, the features can be directly clustered with standard linear SC
techniques such as EnSC (You et al., 2016). For more difficult tasks, we found
that the full NMCE objective performs much better.

##  4 Results

We provide code for our experiment here [ link],

For the synthetic experiments, a MLP backbone is used as backbone and two
linear last layers are used to produce feature and cluster logits output, ELU
is used as the activation function. For all image datasets, standard ResNet
with ReLU activation and various sizes is used as the backbone. After the
global average pooling layer, one linear layer with 4096 output units, batch
normalization and ReLU activation is used. After this layer, two linear heads
are used to produce feature and cluster logits outputs. The number of clusters
used is always equal to the ground truth. For all experiments, two augmented
samples, or ”views”, are used for each data sample in a batch. Gumbel-Softmax
(Jang et al., 2016) is used to learn the cluster assignments. Similar to Yu et
al. (2020), feature vectors are always normalized to the unit sphere. The
constraint term $D$ is always cosine similarity between two augmented samples.
Cluster assignment probabilities and feature vectors are averaged between
augmentations before sending into the NMCE loss, which enforce consistency
between the augmentations. The regularization strength $\lambda$ is always
determined empirically. Hyper-parameters and further details are available in
the Appendix B.

Table 1: Clustering performance comparison on COIL20 and COIL100. Listed are error rates, NMCE is our method, see text for references for other listed methods . Dataset | SSC | KSSC | AE+EDSC | DSC | S2ConvSCN | MLRDSC-DA | NMCE (Ours)
---|---|---|---|---|---|---|---
COIL20 | 14.83 | 24.65 | 14.79 | 5.42 | 2.14 | 1.79 | 0.0
COIL100 | 44.90 | 47.18 | 38.88 | 30.96 | 26.67 | 20.67 | 11.53

###  4.1 Synthetic and image datasets

For the toy example in Figure 1, data augmentation is simply adding a small
amount of noise, and full NMCE objective is directly used, the clustering
output is jointly learned.

To verify the NMCE objective, we perform synthetic experiment by clustering a
mixture of manifold-structured data generated by passing Gaussian noise
through two randomly initialized MLPs. Small Gaussian noise data augmentation
is used to enforce the locality constraint. A two stage training process is
used, the first stage uses TCR objective while the second stage uses full NMCE
objective. Much like the toy experiment, the result is consistent with our
interpretation, see Appendix A.1 for results and details.

To compare NMCE with other subspace clustering methods, we apply it to COIL20
(Nene et al., 1996a) and COIL100 (Nene et al., 1996b), both are standard
datasets commonly used in SC literature. They consist of images of objects
taken on a rotating stage in 5 degree intervals. COIL20 has 20 objects with
total of 1440 images, and COIL100 has 100 objects with total of 7200 images.
Images are gray-scaled and down-sampled by 2x. For COIL20, a 18-layer ResNet
with 32 filters are used as the backbone, the feature dimension is 40. For
COIL100, and 10-layer ResNet with 32 filters is used, and feature dimension is
200. We determined the best augmentation policy for this experiment by manual
experimentation on COIL20, and the same policy is applied to COIL100. Details
on the searched policy can be found in Appendix B. For this experiment, we use
EnSC (You et al., 2016) to cluster features learned with TCR objective. We
found this procedure already performs strongly, and full NMCE objective is not
necessary.

We compare with classical baseline such as Sparse Subspace Clustering (SSC)
(Elhamifar & Vidal, 2013) as well as recent deep SC techniques including
KSSC(Patel & Vidal, 2014), AE+EDSC(Ji et al., 2014), DSC(Ji et al., 2017),
S2ConvSCN(Zhang et al., 2019) and MLRDSC-DA(Abavisani et al., 2020). As can be
seen in Table 1, our method achieves 0.0 error rate for COIL20, and error rate
of 11.53 for COIL100, substantially outperforming previous state of the art of
1.79 and 20.67. This suggests that NMCE can leverage the non-linear processing
capability of deep networks better, unlike previous deep SC methods, which
only marginally outperform linear SC on the pixel space (Haeffele et al.,
2020).

###  4.2 Self-supervised learning and clustering of natural images

Recently, unsupervised clustering has been extended to more challenging image
datasets such as CIFAR-10, CIFAR-20 (Krizhevsky et al., 2009) and STL-10
(Coates et al., 2011). The original MCR2 paper (Yu et al., 2020) also
performed those experiments, but they used augmentation in a very different
way (See Appendix A.2 for a discussion). The CIFAR-10 experiment used 50000
images from the training set, CIFAR-20 used 50000 images from training set of
CIFAR-100 with 20 coarse labels. The STL-10 experiment used 13000 labeled
images from original train and test set. ImageNet-10 and ImagetNet-Dogs used
13000 and 19500 images subset from ImageNet, respectively (Li et al., 2021).
We use ResNet-18 as the backbone to compare with MCR2, and use ResNet-34 as
the backbone to compare with other clustering methods. In both cases, the
feature dimension is 128. Standard image augmentations for self-supervised
learning is used (Chen et al., 2020).

Table 2: Supervised evaluation performance for different feature types and evaluation algorithms. See text for details. Model | Proj | Pre-feature | Pool | Proj (16 avg) | Pre-feature (16 avg) | Pool (16 avg)
---|---|---|---|---|---|---
SVM | 0.911 | 0.889 | 0.895 | 0.922 | 0.905 | 0.929
kNN | 0.904 | 0.851 | 0.105 | 0.910 | 0.800 | 0.103
NearSub | 0.898 | 0.902 | 0.903 | 0.903 | 0.909 | 0.911

####  4.2.1 Training strategy, supervised evaluation

Here we use a three stage training procedure: 1. Train with TCR objective. 2.
Reinitialize the last linear projection layer and add a cluster assignment
layer. Then, freeze parameters in the backbone network and train the two new
layers with full NMCE objective. 3. Fine tune the entire network with NMCE
objective.

As discussed earlier, the first stage is very similar to self-supervised
contrastive learning. Therefore, we study features learned at this stage with
supervised evaluation, the result with ResNet-34 is listed in Table 2. To
evaluate the learned features, we use SVM, kNN and a Nearest Subspace
classifier (NearSub). We use SVM instead of linear evaluation training because
we find that it is more stable and insensitive to particular parameter
settings. Here we compare three types of features, Proj: 128d output of the
projector head. Pre-feature: 4096d output of the linear layer after backbone.
Pool: the 2048d feature from the last average pooling layer. We find that
averaging features obtained from images processed by training augmentations
improves the result. Therefore we also compare performance in this setting and
denote it by 16avg, as 16 augmentations are used per image. Images from both
training and test set are augmented. As can be seen from the table, without
augmentation, SVM using the projector head feature gives the best accuracy.
This is surprising, as most self-supervised learning techniques effectively
use Pool features because the performance obtained with Proj features is poor.
When averaging is used, a SVM with Pool feature becomes the best performer,
however, SVM and kNN with Proj feature also achieve very high accuracy. In
Appendix, we further compared Proj and Pool features using SVM in cases where
limited labeled data are available. In such cases, Proj feature significantly
outperform Pool feature, showing that the TCR objective encourages learning of
meaningful feature in the latent space – unlike other algorithms, where the
gap between performance of Pool and Proj features can be very large (Chen et
al., 2020).

Table 3: Clustering performance comparisons. Clustering: clustering specific
methods. SC: subspace clustering methods. See text for details.

Models | CIFAR-10 | CIFAR-20 | STL-10 | ImageNet-10 | ImageNet-Dogs
---|---|---|---|---|---
ACC | NMI | ARI | ACC | NMI | ARI | ACC | NMI | ARI | ACC | NMI | ARI | ACC | NMI | ARI
Clustering |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
k-means | 0.525 | 0.589 | 0.276 | 0.130 | 0.084 | 0.028 | 0.192 | 0.125 | 0.061 | 0.241 | 0.119 | 0.057 | 0.105 | 0.055 | 0.020
Spectral | 0.455 | 0.574 | 0.256 | 0.136 | 0.090 | 0.022 | 0.159 | 0.098 | 0.048 | 0.271 | 0.151 | 0.076 | 0.111 | 0.038 | 0.013
CC | 0.790 | 0.705 | 0.637 | 0.429 | 0.431 | 0.266 | 0.850 | 0.764 | 0.726 | 0.893 | 0.859 | 0.822 | 0.429 | 0.455 | 0.474
CRLC | 0.799 | 0.679 | 0.634 | 0.425 | 0.416 | 0.263 | 0.818 | 0.729 | 0.682 |  |  |  |  |  |
MoCo Baseline | 0.776 | 0.669 | 0.608 | 0.397 | 0.390 | 0.242 | 0.728 | 0.615 | 0.524 | - | - | - | 0.338 | 0.347 | 0.197
MiCE | 0.835 | 0.737 | 0.698 | 0.440 | 0.436 | 0.280 | 0.752 | 0.635 | 0.575 | - | - | - | 0.439 | 0.428 | 0.286
TCC | 0.906 | 0.790 | 0.733 | 0.491 | 0.479 | 0.312 | 0.814 | 0.732 | 0.689 | 0.897 | 0.848 | 0.825 | 0.546 | 0.512 | 0.409
ConCURL | 0.846 | 0.762 | 0.715 | 0.479 | 0.468 | 0.303 | 0.749 | 0.636 | 0.566 | 0.958 | 0.907 | 0.909 | 0.695 | 0.630 | 0.531
IDFD | 0.815 | 0.711 | 0.663 | 0.425 | 0.426 | 0.264 | 0.756 | 0.643 | 0.575 | 0.954 | 0.898 | 0.901 | 0.591 | 0.546 | 0.413
SC |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
MCR2-EnSC | 0.684 | 0.630 | 0.508 | 0.347 | 0.362 | 0.167 | 0.491 | 0.446 | 0.290 | - | - | - | - | - | -
MCR2-ESC | 0.653 | 0.629 | 0.438 | - | - | - | - | - | - | - | - | - | - | - | -
MCR2-SENet | 0.765 | 0.655 | 0.573 | - | - | - | - | - | - | - | - | - | - | - | -
Ours |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
NMCE-Res18 | 0.830 | 0.761 | 0.710 | 0.437 | 0.488 | 0.322 | 0.725 | 0.614 | 0.552 | 0.906 | 0.819 | 0.808 | 0.398 | 0.393 | 0.227
NMCE-Res34 | 0.891 | 0.812 | 0.795 | 0.531 | 0.524 | 0.375 | 0.711 | 0.600 | 0.530 | - | - | - | - | - | -

Figure 2: Visualization of principal components from subspace representation
learned from CIFAR-10. Rows in each panel are training images that has the
largest cosine similarities with different principle components of that
subspace. Similarity of images within each component is apparent. For a more
complete visualization, see Figure A.6.

####  4.2.2 Clustering Performance

We compare clustering performance of NMCE after all 3 stages of training to
other techniques. Due to space limits, we only compare with important baseline
methods as well as highest performing deep learning based techniques, rather
than being fully comprehensive. For a more complete list of methods, see for
example Shen et al. (2021). We follow the convention in the field and use
clustering Accuracy (ACC), Normalized Mutual Information (NMI), and Adjusted
Rand Score (ARI) as metrics. For definitions, see Yu et al. (2020), for
example. We list results in Table 3, K-means(MacQueen et al., 1967) and
Spectral clustering(Ng et al., 2002) results were adopted from Zhang et al.
(2021) and Shen et al. (2021), we always selected the best result. For deep
learning based techniques, we compare our ResNet-34 results with CC(Li et al.,
2021), CRLC(Do et al., 2021), MiCE(Tsai et al., 2020), TCC(Shen et al., 2021),
ConCURL(Deshmukh et al., 2021), and IDFD(Tao et al., 2021). We did not include
Park et al. (2021) or Kinakh et al. (2021) since the former is a post
processing step, and the later uses a special network architecture. We also
separately compare ResNet-18 result with features learned by MCR2 (MCR2-CTRL
to be precise, see Appendix A.2) and clustered by EnSC(You et al., 2016),
ESC(You et al., 2018) or SENet(Zhang et al., 2021). They are denoted by
MCR2-EnSC, MCR2-ESC and MCR2-SENet, respectively. For MCR2-EnSC, we adopt the
result from Yu et al. (2020), since the result is higher and include all 3
datasets, MCR2-ESC and MCR2-SENet results are from Zhang et al. (2021).

Compared with the result from MCR2, our method achieved a substantial gain in
all metrics considered. For example, the accuracy is improved by more than 6%
on CIFAR-10, and by 9% on CIFAR-20. This shows that we used data augmentation
in a much more effective way than original MCR2. Our method can also
outperform previous techniques which were specifically optimized for
clustering, this happens on most CIFAR-10 and CIFAR-20 metrics, for example.

In the experiments above, stage 1 learns pre-features that are approximately
subspace-structured, and stage 2 can be seen as performing subspace clustering
on the pre-feature output, as MCR2 was originally a subspace clustering
objective (Ma et al., 2007). For CIFAR and STL-10 experiments, fine tuning the
entire network with the NMCE objective (stage 3) improves performance by a
small but significant amount, see Appendix A.3). Features learned from stage 1
of the training can also be directly clustered by methods like EnSC, but the
results were rather poor for the image dataset. It seems that NMCE is a more
robust way to cluster the learned features for the image experiments.

After all 3 training stages, one can visualize the structure of each subspace
by performing PCA and displaying the training examples that have the highest
cosine similarity to each of the principle components. In Figure 2 we show
this for 4 out of 10 clusters of CIFAR-10. As can be seen, principle
components in each cluster correspond to semantically meaningful sub-clusters.
For example, the first row in ”dog” cluster are mostly close-ups of white
dogs. This shows that after training with the full NMCE objective, samples are
clustered based on content similarity in the latent space, instead of being
distributed uniformly on the hyper-sphere, as training with just the TCR
objective or other self-supervised learning methods would encourage Wang &
Isola (2020); Durrant & Leontidis (2021); Zbontar et al. (2021); Bardes et al.
(2021); Zimmermann et al. (2021).

##  5 Discussion

In this paper we proposed a general method for manifold clustering and
embedding with neural networks. It consists of adding geometric constraint to
make the clusters identifiable, then performing clustering and subspace
feature learning. In the special case where the constraint is implemented by
data-augmentation, we discussed its relationship to self-supervised learning
and demonstrated its competitive performance on several important benchmarks.

In the future, it is possible to extend this method beyond data augmentation
to other type of constraint functions, or improves its performance using a
stronger subspace feature learning algorithm.

## References

  * Abavisani et al. (2020) Mahdi Abavisani, Alireza Naghizadeh, Dimitris N Metaxas, and Vishal M Patel.  Deep subspace clustering with data augmentation.  In _NeurIPS_ , 2020.
  * Abdolali & Gillis (2021) Maryam Abdolali and Nicolas Gillis.  Beyond linear subspace clustering: A comparative study of nonlinear manifold clustering algorithms.  _arXiv preprint arXiv:2103.10656_ , 2021.
  * Bardes et al. (2021) Adrien Bardes, Jean Ponce, and Yann LeCun.  Vicreg: Variance-invariance-covariance regularization for self-supervised learning.  _arXiv preprint arXiv:2105.04906_ , 2021.
  * Belkin & Niyogi (2003) Mikhail Belkin and Partha Niyogi.  Laplacian eigenmaps for dimensionality reduction and data representation.  _Neural computation_ , 15(6):1373–1396, 2003\.
  * Caron et al. (2018) Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze.  Deep clustering for unsupervised learning of visual features.  In _Computer Vision - ECCV 2018 - 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XIV_ , volume 11218 of _Lecture Notes in Computer Science_ , pp. 139–156. Springer, 2018.
  * Caron et al. (2020) Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual_ , 2020.
  * Chen et al. (2020) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _International conference on machine learning_ , pp. 1597–1607. PMLR, 2020.
  * Chen & He (2021) Xinlei Chen and Kaiming He.  Exploring simple siamese representation learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 15750–15758, 2021.
  * Chen et al. (2018) Yubei Chen, Dylan M. Paiton, and Bruno A. Olshausen.  The sparse manifold transform.  In _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada_ , pp. 10534–10545, 2018.
  * Coates et al. (2011) Adam Coates, Andrew Ng, and Honglak Lee.  An analysis of single-layer networks in unsupervised feature learning.  In _Proceedings of the fourteenth international conference on artificial intelligence and statistics_ , pp. 215–223. JMLR Workshop and Conference Proceedings, 2011.
  * Cover (1999) Thomas M Cover.  _Elements of information theory_.  John Wiley & Sons, 1999.
  * da Costa et al. (2021) Victor G Turrisi da Costa, Enrico Fini, Moin Nabi, Nicu Sebe, and Elisa Ricci.  Solo-learn: A library of self-supervised methods for visual representation learning.  _arXiv preprint arXiv:2108.01775_ , 2021.
  * Deshmukh et al. (2021) Aniket Anand Deshmukh, Jayanth Reddy Regatti, Eren Manavoglu, and Urun Dogan.  Representation learning for clustering via building consensus.  _arXiv preprint arXiv:2105.01289_ , 2021.
  * Do et al. (2021) Kien Do, Truyen Tran, and Svetha Venkatesh.  Clustering by maximizing mutual information across views.  _arXiv preprint arXiv:2107.11635_ , 2021.
  * Durrant & Leontidis (2021) Aiden Durrant and Georgios Leontidis.  Hyperspherically regularized networks for byol improves feature uniformity and separability.  _arXiv preprint arXiv:2105.00925_ , 2021.
  * Elhamifar & Vidal (2011) Ehsan Elhamifar and René Vidal.  Sparse manifold clustering and embedding.  _Advances in neural information processing systems_ , 24:55–63, 2011.
  * Elhamifar & Vidal (2013) Ehsan Elhamifar and René Vidal.  Sparse subspace clustering: Algorithm, theory, and applications.  _IEEE transactions on pattern analysis and machine intelligence_ , 35(11):2765–2781, 2013.
  * Gong et al. (2012) Dian Gong, Xuemei Zhao, and Gérard Medioni.  Robust multiple manifolds structure learning.  In _International Conference on Machine Learning_. PMLR, 2012.
  * Grill et al. (2020) Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent: A new approach to self-supervised learning.  _arXiv preprint arXiv:2006.07733_ , 2020.
  * Haeffele et al. (2020) Benjamin D Haeffele, Chong You, and René Vidal.  A critique of self-expressive deep subspace clustering.  _arXiv preprint arXiv:2010.03697_ , 2020.
  * HaoChen et al. (2021) Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma.  Provable guarantees for self-supervised deep learning with spectral contrastive loss.  _arXiv preprint arXiv:2106.04156_ , 2021.
  * He et al. (2020) Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 9729–9738, 2020.
  * Jang et al. (2016) Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with gumbel-softmax.  _arXiv preprint arXiv:1611.01144_ , 2016.
  * Ji et al. (2014) Pan Ji, Mathieu Salzmann, and Hongdong Li.  Efficient dense subspace clustering.  In _IEEE Winter Conference on Applications of Computer Vision_ , pp. 461–468. IEEE, 2014.
  * Ji et al. (2017) Pan Ji, Tong Zhang, Hongdong Li, Mathieu Salzmann, and Ian Reid.  Deep subspace clustering networks.  _arXiv preprint arXiv:1709.02508_ , 2017.
  * Jolliffe (1986) Ian T. Jolliffe.  _Principal Component Analysis_.  Springer, 1986.
  * Kang et al. (2015) Zhao Kang, Chong Peng, Jie Cheng, and Qiang Cheng.  Logdet rank minimization with application to subspace clustering.  _Computational intelligence and neuroscience_ , 2015, 2015.
  * Kinakh et al. (2021) Vitaliy Kinakh, Slava Voloshynovskiy, and Olga Taran.  Scatsimclr: self-supervised contrastive learning with pretext task regularization for small-scale datasets.  In _2nd Visual Inductive Priors for Data-Efficient Deep Learning Workshop_ , 2021.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Li et al. (2021) Yunfan Li, Peng Hu, Zitao Liu, Dezhong Peng, Joey Tianyi Zhou, and Xi Peng.  Contrastive clustering.  In _2021 AAAI Conference on Artificial Intelligence (AAAI)_ , 2021\.
  * Ma et al. (2007) Yi Ma, Harm Derksen, Wei Hong, and John Wright.  Segmentation of multivariate mixed data via lossy data coding and compression.  _IEEE transactions on pattern analysis and machine intelligence_ , 29(9):1546–1562, 2007.
  * MacQueen et al. (1967) James MacQueen et al.  Some methods for classification and analysis of multivariate observations.  In _Proceedings of the fifth Berkeley symposium on mathematical statistics and probability_ , volume 1.14, pp. 281–297. Oakland, CA, USA, 1967\.
  * Nene et al. (1996a) SA Nene, SK Nayar, and H Murase.  Columbia object image library (coil-20).  _Technical Report_ , 005-96, 1996a.
  * Nene et al. (1996b) Sameer A Nene, Shree K Nayar, Hiroshi Murase, et al.  Columbia object image library (coil-100).  _Technical Report_ , 006-96, 1996b.
  * Ng et al. (2002) Andrew Y Ng, Michael I Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  In _Advances in neural information processing systems_ , pp. 849–856, 2002.
  * Park et al. (2021) Sungwon Park, Sungwon Han, Sundong Kim, Danu Kim, Sungkyu Park, Seunghoon Hong, and Meeyoung Cha.  Improving unsupervised image clustering with robust learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 12278–12287, 2021.
  * Patel & Vidal (2014) Vishal M Patel and René Vidal.  Kernel sparse subspace clustering.  In _2014 ieee international conference on image processing (icip)_ , pp. 2849–2853. IEEE, 2014.
  * Roweis & Saul (2000) Sam T Roweis and Lawrence K Saul.  Nonlinear dimensionality reduction by locally linear embedding.  _science_ , 290(5500):2323–2326, 2000.
  * Shen et al. (2021) Yuming Shen, Ziyi Shen, Menghan Wang, Jie Qin, Philip HS Torr, and Ling Shao.  You never cluster alone.  _arXiv preprint arXiv:2106.01908_ , 2021.
  * Souvenir & Pless (2005) R. Souvenir and R. Pless.  Manifold clustering.  In _International Conference on Computer Vision (ICCV)_ , pp. 648–653, 2005.
  * Sun et al. (2019) Xiukun Sun, Miaomiao Cheng, Chen Min, and Liping Jing.  Self-supervised deep multi-view subspace clustering.  In _Asian Conference on Machine Learning_ , pp. 1001–1016. PMLR, 2019.
  * Tao et al. (2021) Yaling Tao, Kentaro Takagi, and Kouta Nakata.  Clustering-friendly representation learning via instance discrimination and feature decorrelation.  In _International Conference on Learning Representations_ , 2021.
  * Tsai et al. (2020) Tsung Wei Tsai, Chongxuan Li, and Jun Zhu.  Mice: Mixture of contrastive experts for unsupervised image clustering.  In _International Conference on Learning Representations_ , 2020.
  * Vidal et al. (2016) René Vidal, Yi Ma, and S Shankar Sastry.  _Generalized principal component analysis_ , volume 5.  Springer, 2016.
  * von Kügelgen et al. (2021) Julius von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello.  Self-supervised learning with data augmentations provably isolates content from style.  _arXiv preprint arXiv:2106.04619_ , 2021.
  * Wang & Isola (2020) Tongzhou Wang and Phillip Isola.  Understanding contrastive representation learning through alignment and uniformity on the hypersphere.  In _International Conference on Machine Learning_ , pp. 9929–9939. PMLR, 2020.
  * You et al. (2016) Chong You, Chun-Guang Li, Daniel P Robinson, and René Vidal.  Oracle based active set algorithm for scalable elastic net subspace clustering.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 3928–3937, 2016.
  * You et al. (2018) Chong You, Chi Li, Daniel P Robinson, and René Vidal.  Scalable exemplar-based subspace clustering on class-imbalanced data.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pp. 67–83, 2018.
  * You et al. (2017) Yang You, Igor Gitman, and Boris Ginsburg.  Large batch training of convolutional networks.  _arXiv preprint arXiv:1708.03888_ , 2017.
  * Yu et al. (2020) Yaodong Yu, Kwan Ho Ryan Chan, Chong You, Chaobing Song, and Yi Ma.  Learning diverse and discriminative representations via the principle of maximal coding rate reduction, 2020.
  * Zbontar et al. (2021) Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny.  Barlow twins: Self-supervised learning via redundancy reduction.  _arXiv preprint arXiv:2103.03230_ , 2021.
  * Zhang et al. (2019) Junjian Zhang, Chun-Guang Li, Chong You, Xianbiao Qi, Honggang Zhang, Jun Guo, and Zhouchen Lin.  Self-supervised convolutional subspace clustering network.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 5473–5482, 2019.
  * Zhang et al. (2021) Shangzhi Zhang, Chong You, René Vidal, and Chun-Guang Li.  Learning a self-expressive network for subspace clustering.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 12393–12403, 2021.
  * Zhou et al. (2018) Pan Zhou, Yunqing Hou, and Jiashi Feng.  Deep adversarial subspace clustering.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 1596–1604, 2018.
  * Zimmermann et al. (2021) Roland S Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel.  Contrastive learning inverts the data generating process.  _arXiv preprint arXiv:2102.08850_ , 2021.

##  Appendix A Additional Results and Discussions

###  A.1 Synthetic experiment

We verify the proposed manifold clustering and embedding algorithm by a simple
synthetic experiment. Ground truth data from a union of two manifolds with
dimension 3 and 6 is generated by passing 3d and 6d iid. Gaussian noise
through two randomly initialized neural networks with Leaky-ReLU activation
function (negative part slop 0.2). Data augmentation is Gaussian noise with
manitude 0.1. Training used two stages, the first stage used only TCR
objective, the second stage with full NMCE objective.

Two situations are examined. One where the random neural network also has
randomly initialized biases, which will cause the two manifold to be far
apart, making locality constraint implemented by noise augmentation sufficient
for identifying the manifolds. Another situation is when bias is not used, the
two manifolds then intersect at 0, where the density is rather high. This
makes the manifolds not identifiable with only locality constraint.

Results are listed in Table A.1. As can be seen, when the clusters are
identifiable, NMCE is able to correctly cluster the data points, as well as
learn latent features that is perpendicular between different clusters. At the
same time, the feature is not collapsed within each cluster, since if so the
average cosine similarity within cluster would be 1. When the clusters are not
identifiable, they cannot be learned correctly.

Table A.1: Result from synthetic experiment. Accuracy is in % (chance level is 50%), z-sim is the average absolute value of cosine similarity between feature vectors $z$ for different pairs of $z$. True Cluster: pairs of $z$ are from different ground truth clusters. Found Clusters: pairs of $z$ are from two different found clusters. Within Cluster: pairs of $z$ are randomly picked from the same found cluster, averaged between two found clusters. Dataset | Accuracy | z-sim: True Cluster | z-sim: Found Clusters | z-sim: Within Cluster
---|---|---|---|---
Identifiable | 100.0 | 0.017 | 0.017 | 0.503
Not-identifiable | 69.8 | 0.717 | 0.287 | 0.770

###  A.2 relationship to self-supervised learning with $MCR^{2}$

The original paper (Yu et al., 2020) performed self-supervised learning using
MCR2 objective without any additional term. Their method treats different
augmentations of the same image as a self-labeled subspace. They used large
number of augmentations (50) of each image, with only 20 images in each batch.
The performance of this method is rather poor, which is expected based on our
understanding. In this case, augmented images will form a subspace with
certain dimension in the feature space, thus large amount of information about
augmentations will be preserved in the latent space. Clustering can then
utilize style information and not respect class information.

To improve performance, a variant called MCR2-CTRL is developed, where the
total coding rate term is down-scaled. This variant performs significantly
better, and is also used in our comparison. This result is also expected,
since decreasing the subspace term effectively contract different
augmentations of the same image in the feature space, making the feature
better respect the constraint needed for correct clustering. However, since
the total coding rate is not high in this case, the feature is not diverse
enough to achieve good performance.

###  A.3 fine-tuning backbone with NMCE objective

For CIFAR-10, CIFAR-20 and STL-10 experiments, the first training stage
already learns very strong self-supervised features, which is then clustered
into subspaces in the second stage with backbone network frozen. The
clustering performance is already quite good after this stage. In the third
stage, the backbone is fine-tuned, which further improves clustering
performance. In Table A.2, we show the effect of fine-tuning backbone network
on CIFAR-10 and CIFAR-20 experiment with ResNet-18. As can be seen, fine-
tuning produces a small but noticeable gain in clustering performance for all
metrics and both datasets. This indicates that using the full NMCE objective
can improve performance. If the optimization issue can be resolved, and the
entire network is trained with the NMCE objective from scratch, the
performance may be further improved.

Table A.2: Fine tuning backbone with NMCE objective. Results shown are from ResNet-18. Fine tuning backbone improves result slightly but notably. Model | ACC | NMI | ARI
---|---|---|---
CIFAR-10 before | 0.819 | 0.743 | 0.690
CIFAR-10 after | 0.830 | 0.761 | 0.710
CIFAR-20 before | 0.422 | 0.471 | 0.300
CIFAR-20 after | 0.437 | 0.488 | 0.322

###  A.4 compare pool and proj feature on low data classification

Here we compare SVM accuracy of Pool and Proj features from CIFAR-10 ResNet-18
experiment. The feature averaged over 16 augmentations. The accuracy is
plotted as a function of the number of labeled training samples used, see
Figure A.1.

As can be seen, Proj feature clearly outperforms Pool feature when few labeled
examples are available. This makes Proj feature much more useful than Pool
feature, since labeled examples are often scarce real applications.

Note that what shown here is obviously not the optimal way to use labeled
example, if one further leverage the clustering information, accuracy should
reach 90 with only 10 labeled examples.

Figure A.1: CIFAR-10 SVM test accuracy plotted against number of labeled
examples used for Pool and Proj feature from ResNet-18 experiment. Features
averaged over 16 augmentations is used. Error bar is std. over 10 random
sampling of training examples.

###  A.5 Effect of Lambda parameter

Here we study the effect of $\lambda$ parameter that balances the constraint
and subspace feature learning term. CIFAR-10 self-supervised accuracy with SVM
and kNN evaluation on Proj feature is listed in Table A.3. As can be seen, the
accuracy is reasonable in a range of $\lambda$ spanning more than 3x low to
high, indicating that the quality of the learned feature is not very sensitive
to this parameter.

Table A.3: Effect of parameter $\lambda$. $\lambda$ | 20 | 30 | 40 | 50 | 60 | 70
---|---|---|---|---|---|---
Proj SVM acc | 0.899 | 0.902 | 0.903 | 0.902 | 0.903 | 0.903
Proj kNN acc | 0.890 | 0.895 | 0.894 | 0.896 | 0.895 | 0.897

###  A.6 understanding the feature space

Here we show that the TCR objective used in the first stage in our training
procedure for CIFAR and STL-10 datasets theoretically achieve the same result
as the recently proposed VICReg (Bardes et al., 2021) and BarlowTwins(Zbontar
et al., 2021), both are self-supervised learning algorithms. The optimization
target of the two techniques are both making the covariance matrix of latent
vector $Z$ approach the diagonal matrix. The first stage training using TCR
essentially achieves the same result. To see this, we note the following
property of the coding rate function (Kang et al., 2015): For any
$Z\in\mathbb{R}^{m\times d}$:

$\mathsf{logdet}(\mathbf{I}+Z^{T}Z)=\sum_{i=1}^{\mathsf{min}(m,d)}\mathsf{log}(1+\sigma^{2}_{i})$
(6)

Where $\sigma_{i}$ is the $i$th singular value of $Z$. Additionally, we have:
$\sum_{i=1}^{\mathsf{min}(m,d)}\sigma^{2}_{i}=||Z||_{\mathbf{F}}^{2}$, which
follows easily from $||Z||_{\mathbf{F}}^{2}=\mathsf{tr}(Z^{T}Z)$. Since the
function $\mathsf{log}(1+x)$ is concave, the optimization problem
$\mathsf{max}_{x_{1},x_{2},...,x_{n}}\sum_{i=1}^{n}\mathsf{log}(1+x_{i})$
given $\sum_{i=1}^{n}x_{i}=C$ reaches maxima when all $x$ are equal to each
other. Since we normalize the row of $Z$, $||Z||^{2}_{\mathbf{F}}=m$,
optimization of Equation 6 result in solution with uniform singular value,
which is equivalent to diagonal covariance.

We could not successfully reproduce VICReg in our setup due to the large
amount of hyper-parameters that needs to be tuned. Therefore we resort to the
open-source library solo-learn (da Costa et al., 2021), which provided VICReg
implementation. Running the provided script for VICReg produced accuracy of
91.61% on CIFAR-10. We also implemented TCR objective in solo-learn library.
Running TCR obtained accuracy of 92.1%. All hyper-parameters and augmentations
are the same as VICReg, except batch size is 1024 instead of 256, projection
dimension is 64 instead of 2048. Larger batch size or smaller projection
dimension didn’t work for VICReg, so we stayed with the original parameters.

The covariance matrices of learned feature for SimCLR, VICReg and TCR computed
over entire training set are visualized in Figure A.2. For VICReg, first 128
dimension is visualized out of 2048. As can be seen, the diagonal structure is
visible in SimCLR feature space, TCR feature space is the closest to diagonal
matrix. VICReg feature space is also quite close to diagonal, but the off-
diagonal terms seems noisier. Additionally, we plot normalized singular values
for VICReg projection space in Figure A.4. This can be compared to TCR and
SimCLR singular values in Figure A.3 a). As can be seen, TCR achieves flatter
singular value distributions than VICReg, neither SimCLR or VICReg are close
to full rank in projection space.

We demonstrate subspace structure of feature space after clustering with full
NMCE objective by plotting singular values of each learned subspace in Figure
A.3 b). Each subspace found are around rank 10. In all other panels of Figure
A.3, we display samples whose feature vector has the highest cosine similarity
to the top 10 principle components of each subspace. One can see that most
principle components represent a interpretable sub-cluster within each class
(even if the sub-cluster is of a different class than the cluster). Same as in
Figure 2, feature vectors calculated by averaging 16 augmented images are
used.

Figure A.2: a), b), c) Covariance matrix of feature vector computed over
training set for TCR, SimCLR and VICReg. VICReg result is slightly noisier on
the diagonal than TCR. VICReg result is the first 128 dimensions out of 2048,
see text for details. Figure A.3: a) Singular values of feature vector
distribution for SimCLR and TCR. b) Singular values for subspaces learned
after all 3 training stages. The rest of panels: visualizing 10 training
examples most similar to principal components of each clustered subspaces.
Figure A.4: Singular values of feature vector distribution for VICReg using
ResNet-18. VICReg uses 2048d feature space.

##  Appendix B Experimental Details

We list hyper-parameters for each experiment in Table B.1.

###  B.1 Toy and synthetic experiments

The toy dataset consists of double spiral with radius approximately equal to
15 and Gaussian noise magnitude of 0.05, samples are generated online for each
batch. Data augmentation is Gaussian noise with magnitude 0.05.

###  B.2 COIL-20 and COIL-100

The augmentation policy we found with manual search on COIL20 is (all are from
torchvision transforms): 1. Random Horizontal Flip with $p=0.5$. 2.
RandomPerspective with magnitude 0.3 and $p=0.6$ 3\. ColorJitter with manitude
(0.8, 0.8, 0.8, 0.2), always applied. The entire dataset is passed as a single
batch.

###  B.3 CIFAR-10, CIFAR-20, STL-10, ImageNet-10 and ImageNet-Dogs

For CIFAR-10 and CIFAR-20, we use standard ResNet-18 and ResNet-34 with 64
input filters. The first layer uses 3x3 kernel, and and no max pooling is
used. For other experiments, we use standard ResNet-18 and ResNet-34 with 5x5
first layer kernel and max pooling. For COIL-20 and COIL-100 experiment, 32
input filters is used, and the ResNet-10 is obtained by reducing number of
blocks in each stage in ResNet-18 to 1. For full details, see our code
release.

For CIFAR-10, CIFAR-20, STL-10, ImageNet-10 and ImageNet-Dogs experiments, we
used LARS optimizer (You et al., 2017), with base batch size 256, for other
experiments we used Adam. We note that stage 2 and 3 in the 3 stage training
process is quite sensitive to weight decay, a careful search of this parameter
is usually required for good performance.

###  B.4 Computational Cost

All experiments involving ResNet-34 requires 8 GPUs, others can be done in 1
GPU.

Our objective doesn’t add significant computational burden compared to neural-
networks involved. The covariance matrix is computed within a batch. For a
batch of latent feature vectors with shape $[B,d]$, where $B$ is batch size
and $d$ is latent dimension. We first compute the covariance matrix with shape
$[d,d]$, with $\mathcal{O}(B^{2}d)$ cost. Then the log determinant of this
matrix is calculated, which we assume has $\mathcal{O}(d^{3})$ cost. The
$\mathcal{O}(B^{2})$ scaling with respect to batch size is the same as most
contrastive learning method such as SimCLR, which is known to scale to very
large batch size.

Table B.1: Hyper-parameters for all experiments. lr: learning rate. wd: weight decay. $\epsilon$: coding error. $d_{z}$: dimension of feature output. $\lambda$: regularization constant. bs: batch size. epochs (steps): total epochs trained, or total steps trained if the entire dataset is passed at once. S1, S2, S3 denote 3 training stages. Model | lr | wd | $\epsilon$ | $d_{z}$ | $\lambda$ | bs | epochs (steps)
---|---|---|---|---|---|---|---
Double Spiral | 1e-3 | 1e-6 | 0.01 | 6 | 4000 | 4096 | 30000
Synthetic | 1e-3 | 1e-6 | 0.01 | 12 | 100 | 4096 | 3000
COIL-20 | 1e-3 | 1e-6 | 0.01 | 40 | 20 | 1440 | 2000
COIL-100 | 1e-3 | 1e-6 | 0.001 | 200 | 20 | 7200 | 10000
CIFAR-10 ResNet-18 S1 | 1 | 1e-6 | 0.2 | 128 | 50 | 1024 | 600
CIFAR-10 ResNet-18 S2 | 0.5 | 0.005 | 0.2 | 128 | 50 | 1024 | 100
CIFAR-10 ResNet-18 S3 | 0.003 | 0.005 | 0.2 | 128 | 50 | 1024 | 100
CIFAR-10 ResNet-34 S1 | 1 | 1e-6 | 0.2 | 128 | 50 | 1024 | 1000
CIFAR-10 ResNet-34 S2 | 0.5 | 0.001 | 0.2 | 128 | 0 | 1024 | 100
CIFAR-10 ResNet-34 S3 | 0.003 | 0.001 | 0.2 | 128 | 0 | 1024 | 100
CIFAR-20 ResNet-18 S1 | 1 | 1e-6 | 0.2 | 128 | 50 | 1024 | 600
CIFAR-20 ResNet-18 S2 | 0.5 | 0.001 | 0.2 | 128 | 0 | 1024 | 100
CIFAR-20 ResNet-18 S3 | 0.003 | 0.001 | 0.2 | 128 | 0 | 1024 | 100
CIFAR-20 ResNet-34 S1 | 1 | 1e-6 | 0.2 | 128 | 50 | 1024 | 1000
CIFAR-20 ResNet-34 S2 | 0.5 | 0.002 | 0.2 | 128 | 0 | 1024 | 100
CIFAR-20 ResNet-34 S3 | 0.003 | 0.002 | 0.2 | 128 | 0 | 1024 | 100
STL-10 ResNet-18 S1 | 1 | 1e-6 | 0.2 | 128 | 30 | 1024 | 1000
STL-10 ResNet-18 S2 | 0.5 | 0.002 | 0.2 | 128 | 0 | 1024 | 400
STL-10 ResNet-18 S3 | 0.0005 | 0.002 | 0.2 | 128 | 30 | 1024 | 400
STL-10 ResNet-34 S1 | 1 | 1e-6 | 0.2 | 128 | 30 | 1024 | 2000
STL-10 ResNet-34 S2 | 0.5 | 0.002 | 0.2 | 128 | 0 | 1024 | 400
STL-10 ResNet-34 S3 | 0.0005 | 0.002 | 0.2 | 128 | 30 | 1024 | 400


11institutetext: Cognitive Intelligence, Cisco Systems, Prague, Czech
Republic. 22institutetext: Faculty of Information Technology, Czech Technical
University in Prague, Czech Republic. 33institutetext: Faculty of Electrical
Engineering, Czech Technical University in Prague, Czech Republic.

# Cluster Representatives Selection in Non-Metric Spaces for Nearest Prototype
Classification

Jaroslav Hlaváč 1122 Martin Kopp 1122 Jan Kohout 1133

###### Abstract

The nearest prototype classification is a less computationally intensive
replacement for the $k$-NN method, especially when large datasets are
considered. In metric spaces, centroids are often used as prototypes to
represent whole clusters. The selection of cluster prototypes in non-metric
spaces is more challenging as the idea of computing centroids is not directly
applicable.

In this paper, we present CRS, a novel method for selecting a small yet
representative subset of objects as a cluster prototype. Memory and
computationally efficient selection of representatives is enabled by
leveraging the similarity graph representation of each cluster created by the
NN-Descent algorithm. CRS can be used in an arbitrary metric or non-metric
space because of the graph-based approach, which requires only a pairwise
similarity measure. As we demonstrate in the experimental evaluation, our
method outperforms the state of the art techniques on multiple datasets from
different domains.

###### Keywords:

Cluster Representation Nearest Prototype Classification Prototype Selection

##  1 Introduction

The $k$-NN classifiers are often used in many application domains due to their
simplicity and ability to trace the classification decision to a specific set
of samples. However, their adoption is limited by high computational
complexity. Because contemporary datasets are often huge, containing hundreds
of thousands or even millions of samples, computing similarity between the
classified sample and the entire dataset may be computationally intractable.

In order to decrease computational and memory requirements, the nearest
prototype classification (NPC) method is commonly used, c.f. [1, 2, 3]. In
NPC, each class is divided into one or more clusters, and each cluster is
represented by its _prototype_. The classified sample is then compared just to
the prototypes instead of calculating similarity to the entire dataset.

Therefore, the goal of prototype selection is to find a memory-efficient
representation of clusters such that classification accuracy is preserved
while the number of comparisons is significantly reduced.

However, in many application domains, objects might exist in a non-metric
space where only a pairwise similarity is defined, e.g., bioinformatics [4],
biometric identification [5], computer networks [6] or pattern recognition
[7].

In such application domains, standard representations such as centroids may
not be easily determined, or their interpretation does not make much sense.
For these scenarios, only a few methods have been developed, and to best of
our knowledge the only general (not domain-specific) approach is based on the
selection of small subsets of objects to represent the remaining cluster
members. These object, called _representatives_ , are then used as a
prototype.

While several methods capable of solving representatives selection on non-
metric spaces exist (i.e. DS3 [8], $\delta$-medoids [9]), there has not been
much research activity in this direction.

Our focus on non-metric spaces comes from the problem of behavioural
clustering of network hosts [6]. Nevertheless, the problem of selecting a
minimal number of representative samples is of more general interest.
Therefore, we present a novel method to solve the problem of Cluster
Representatives Selection (CRS). CRS is a general method capable of selecting
small representative subset of objects from a cluster as its prototype. Its
core idea is fast construction of an approximate reverse $k$-NN graph and then
solving minimal vertex cover problem on that graph. Only a pairwise similarity
is required to build the reverse $k$-NN graph, therefore application of CRS is
not limited to metric spaces.

To show that CRS is general and domain-independent, we present an experimental
evaluation on datasets from image recognition, document classification and
network host classification, with appealing results when compared to the
current state of the art.

The paper is organized as follows. The related work is briefly reviewed in the
next section. Section 3 formalises the representative selection as an
optimization problem. The proposed CRS method is described in detail in
Section 4. The experimental evaluation is summarized in Section 5 followed by
the conclusion.

##  2 Related Work

During the past years, significant effort has been made to represent clusters
in the most condensed way. The approaches could be categorized into two main
groups.

The first group gathers all prototype generation methods [10], which create
artificial samples to represent original clusters, e.g. [11, 12]. The second
group contains the prototype selection methods. As the name suggests, a subset
of samples from the given cluster is selected to represent it. Prototype
selection is a well-explored field with many approaches, see, e.g. [13].

However, most of the current algorithms exploit the properties of the metric
space, e.g., structured sparsity [14], $l_{1}$-norm induced selection [15] or
identification of borderline objects [16].

When we leave the luxury of the metric space and focus on situations where
only a pairwise similarity exists or where averaging of existing samples may
create an object without meaning, there is not much previous work.

The $\delta$-medoids [9] algorithm uses the idea of $k$-medoids to semi-
greedily cover the space with $\delta$-neighbourhoods, in which it then looks
for an optimal medoid to represent a given neighbourhood. The main issue of
this method is the selection of $\delta$: this hyperparameter has to to be
fine-tuned based on the domain.

The DS3 [8] algorithm calculates the full similarity matrix and then selects
representatives by a row-sparsity regularized trace minimization program which
tries to minimize the rows needed to encode the whole matrix. The overall
computational complexity is the most significant disadvantage of this
algorithm, despite some proposed approximate estimation of the similarity
matrix using only a subset of the data.

The proposed method for Cluster Representatives Selection (CRS) approximates
the topological structure of the data by creating a reverse $k$-NN graph. CPS
then iteratively selects nodes with the biggest reverse neighbourhoods as
representatives of the data. This approach systematically minimizes the number
of pairwise comparisons to reduce computational complexity while accurately
representing the data.

##  3 Problem Formulation

In this section, we define the problem of prototype-based representation of
clusters and the nearest prototype classification (NPC). As we already stated
in Introduction, we study the prototypes selection in general cases, including
non-metric spaces. Therefore, we further assume that a cluster prototype is
always specified as (possibly small) subset of its members.

##### Cluster prototypes

Let $\mathrm{T}$ be an arbitrary space of objects for which a pairwise
similarity function $s:\mathrm{T}\times\mathrm{T}\to\mathbb{R}$ is defined and
let $X\subseteq\mathrm{T}$ be a set of (training) samples. Let
$\mathcal{C}=\\{C_{1},...,C_{m}\\}$ be a clustering of $X$ such that
$C_{i}\cap C_{j}=\varnothing,\forall i\neq j$ and $\bigsqcup C_{i}=X.$ Let
$C_{i}=\\{x_{1},x_{2},...,x_{n}\\}$ be a cluster of size $n$. For $x\in
C_{i}$, let us denote $U^{k}_{x}$ the $k$ closest samples to $x$, i.e., the
set of $k$ samples that have the highest similarity to $x$ in the rest of the
cluster $C_{i}\setminus\\{x\\}$. Then the goal of the prototype selection is
to find a subset of samples $R_{i}\subseteq C_{i}$ for each cluster such that:

$\forall x\in C_{i}\;\exists\;r\in R_{i}\;:\;x\in U^{k}_{r}$ (1)

The set $R_{i}$ is then called the prototype of the cluster $C_{i}$. In case
of ties, we pick the samples with lowest indices $i$.

In order to minimize computational requirements of NPC, we search for a
minimal set of cluster representatives $R_{i}$ for each cluster, which
satisfies the coverage requirement (1):

$\left|R_{i}\right|=\min_{R}\;\left|\left\\{\bigcup_{r\in
R}U^{k}_{r}=C_{i}\right\\}\right|$ (2)

Note that several sets might satisfy this coverage requirement.

##### Relaxed prototypes

Finding cluster prototypes that fully meet the coverage requirement (1) might
pose an unnecessary computational burden. In many cases, a smaller prototype
which is much easier to obtain can capture enough of the important
characteristics of a cluster despite possibly not covering all of its members
(e.g., a few outliers). Motivated by this observation, we introduce a relaxed
requirement on cluster prototypes. We say that a set $R_{i}\subseteq C_{i}$ is
a representative prototype of cluster $C_{i}$ if the following condition is
met:

$\left|\bigcup_{r\in R_{i}}U_{r}^{k}\cap C_{i}\right|\geq\epsilon|C_{i}|,$ (3)

for a preset parameter $\epsilon\in(0,1]$.

In further work, we replace the requirement (1) with its relaxed version (3).
In case of need, the full coverage requirement can be enforced by simply
setting $\epsilon=1$. Similarly, also in the relaxed version, we seek for a
prototype with minimal cardinality which satisfies (3).

##### Nearest Prototype Classification

Having the representative prototypes for all clusters, we now describe how the
classification is performed. In the nearest prototype classification (NPC), an
unseen sample $x$ is classified to the cluster (i.e., the respective target
class is assigned to the sample) which is represented by the prototype with
the highest similarity to the sample $x$. As the cluster prototypes are
disjoint sets, the nearest prototype is defined as the prototype containing
the sample with the highest similarity to $x$. Formally, given the prototypes
of all clusters $\mathcal{R}=\\{R_{1},...,R_{m}\\}$, the nearest prototype,
denoted $R^{*}$, is the prototype containing $r^{*}$, where

$r^{*}=\mathop{\arg\max}_{r\in\bigcup R_{i}}s(x,r).$

Again, we resolve ties by picking the candidate with lowest index in the
dataset.

Finally, the sample $x$ is classified with the same label as that of the
cluster represented by the prototype $R^{*}$.

##  4 Cluster Representatives Selection

In this section, we describe our method CRS for building the cluster
prototypes. The entire method is composed of two steps that are discussed in
more detail in individual subsections. First, given a cluster $C$ and a
similarity measure $s$, a reverse $k$-NN graph $G$ is constructed from objects
$C$ using the pairwise similarity $s$. Then, the graph $G$ is used to select
the representatives that satisfy the coverage requirement while minimizing the
size of the cluster prototype. The simplified scheme of the whole process is
depicted in Figure 1.

(a) dataset (b) k-neighbourhood (c) reverse neighbourhood

Figure 1: Illustration of the steps of CRS algorithm. (a) Visualization of a
toy 2D dataset. (b) 2-NN graph created from from the dataset. (c) Reverse
graph created from the graph depicted in (b). Point C is a representative of
A, B, D, E and would be a good choice first choice of a representative.
Depending on the coverage parameter $\epsilon$, the node F could be considered
an outlier or also added to the representation.

###  4.1 Building the Prototype

For the purpose of building the prototype for a cluster $C$ a weighted reverse
$k$-NN graph $G^{-1}_{C}$ is used. It is defined as $G^{-1}_{C}=(V,E,w)$,
where $V$ is the set of all objects in cluster $C$, $E$ is a set of edges and
$w$ is a weight vector. An edge between two nodes $v_{i},v_{j}\in V_{i\neq j}$
exists if $v_{i}\in U_{v_{j}}^{k}$, while the edge weight $w_{ij}$ is given by
the similarity $s$ between the connected nodes, $w_{ij}=s(v_{i},v_{j})$.

The effective construction of such graph is enabled by employing the NN-
Descent [17] algorithm which produces a $k$-NN graph $G_{C}$. The reverse
$k$-NN graph $G^{-1}_{C}$ is then obtained from $G_{C}$ by simply reversing
directions of the edges in $G_{C}$.

NN-Descent is a fast converging approximate method for the $k$-NN graph
construction. It exploits the idea that “a neighbour of a neighbour is also
likely to be a neighbour” to locally explore neighbouring nodes for better
solutions.

Having the reverse $k$-NN graph $G_{C}^{-1}$, we want to ensure that each
object $x$ is at least $\tau$-similar to all its neighbours, i.e.,

$\left(\forall y\in U_{x}:s(x,y)\geq\tau\right).$

Omitting all edges with weight lower than $\tau$ not only lowers the memory
requirements, but it also unfolds objects with large neighbourhood as good
representative candidates.

The selection of representatives is treated as a minimum vertex cover problem
on $G_{C}^{-1}$. We use a greedy algorithm which iteratively selects objects
with maximal $|U|$ as representatives and marks them and their neighbourhood
as covered. The algorithm stops when the coverage requirement (3) is met (see
Section 3).

The whole algorithm is summarized in Algorithm 1.

Data: cluster $C=\\{c_{1},...,c_{n}\\}$, similarity $s$, coverage threshold
$\epsilon$

Result: set of selected representatives $R\subseteq C$

1 $G_{C}=$ NN-Descent($C$, $s$)

2 $G_{C}^{-1}=$ ReverseGraph($G_{C}$)

3 $Z=C$ //set of uncovered objects

4 $R=\\{\\}$ //set of representatives

5 while  _$\frac{|C|-|Z|}{|C|} <\epsilon$_ do

6 $r=\mathop{\arg\max}(\sum\limits_{c\in Z}s(c,u),u\in U_{c}$)

7 $Z=Z\setminus U_{r}$

8 $R=R\cup\\{r\\}$

9

10 end while

return $R$

Algorithm 1 Pseudocode for Cluster Representatives Selection

An example of a cluster prototype selected by the CRS algorithm is presented
in Figure 2.

Figure 2: Selection of representatives CRS with different $K$s for a
2-dimensional dataset with 255 samples. For better comparison $\delta$-medoids
and DS3 are also shown. CRS takes into account the density of different parts
of the cluster and selects representatives accordingly. $\delta$-Medoids
covers the dataset entirely by evenly distributed representatives. DS3 in
selects the least representatives but does not capture the overall structure
of the cluster very well.

###  4.2 Discussion on parameters

This subsection summarizes the parameters of the CRS method.

  * •

$k$: number of neighbors for the $k$-NN graph creation. When $k$ is high, each
object covers more neighbours, but on the other hand it also increases the
number of pairwise similarity calculations. This trade-off is illustrated for
different values of $k$ in Figure 3. Due to the large impact of this parameter
on properties of the produced representations and computational requirements,
we further study its behaviour in more detail in a dedicated experiment in
Section 5.

Figure 3: Number of representatives being selected and the quality of
representation are both controlled by $k$. As each object explores a bigger
neighbourhood for higher $k$, the number of other objects it represents grows,
therefore the number of representatives decreases. On the other hand, with
less representatives, some information about the structure is lost, as in the
case of $k=15$.

  * •

$\epsilon$: coverage parameter for the relaxed coverage requirement as
introduced in Section 3. In this work, we set it to 0.95 such that the vast
majority of each cluster is still covered but outliers do not influence the
prototypes.

  * •

$\tau$: threshold on weights, determining which edges will be kept in the
graph $G_{C}^{-1}$ (see Section 4.1). By default it is automatically set to
the value of _homogeneity_ $h(C)$ of the cluster $C$:

$h(C)={1\over|C|(|C|-1)}\sum_{x_{i},x_{j}\in C,i\neq j}s(x_{i},x_{j})$ (4)

Additionally, the NN-Descent algorithm, used within the CRS method, has two
more parameters that specify its behaviour during the $k$-NN graph creation.
First, the $\delta_{nn}$ parameter which is used for early termination of the
NN-Descent algorithm when the number of changes in the constructed graph is
minimal. We set it to 0.001, as suggested by the authors of the original work
[17]. Second, the sample rate $\rho$ controls the number of reverse neighbours
to be explored in each iteration of NN-Descent. Again, we set it to 0.7 to
speed up the $k$-NN creation while not diverging too far from the optimal
solution in accordance with suggestions published in [17].

##  5 Experiments

This section presents experimental evaluation of the CRS algorithm on multiple
datasets from very different domains that cover computer networks, text
documents processing and image classification. In the first experiment, we
study the influence of the parameter $k$ (which determines the number of
nearest neighbors used for building the underlying $k$-NN graph). Next, we
compare the CRS method to the state of the art techniques DS3[8] and
$\delta$-medoids [9] in the nearest prototype classification task on different
datasets.

We set $h$ as an approximate homogeneity calculated from random 5% of the
cluster. We use $h$ as $\delta$ for $\delta$-Medoids algorithm. It makes the
most sense in comparing with CRS, because CRS is also restricting the
similarity by $h$ in reverse graph creation. The best results for DS3 we
obtained with $p=\inf$ and $\alpha=3$, while creating the full similarity
matrix for the entire cluster. Finally the parameters for CRS are discussed in
Section 4.2. The following experiment explores the impact of $k$ in greater
detail.

###  5.1 Impact of $k$

When building cluster prototypes by the CRS method, the number of nearest
neighbors considered for building the $k$-NN graph (specified by the parameter
$k$) plays very important role. With small values of $k$, each object
represents only few of its neighbors that are most similar to it. However,
this also increases the number of representatives needed to sufficiently cover
the cluster. On the other hand, higher values of $k$ produce smaller
prototypes as each representative is able to cover more objects. Nonetheless,
this is at the cost of increased computational burden because the cost of
$k$-NN creation increases rapidly with higher $k$s. These trends can be well
observed in Figure 4 which shows classification precision, sizes of created
prototypes and numbers of similarity function evaluations depending on $k$ for
several clusters that differ in their homogeneity and sizes. We can see the
changing trade-off between computational requirements (blue line) and memory
requirements (red line) as the $k$ increases. However, this is mostly without
significant impact on classification precision. The parameter $k$ can be
therefore set depending on the preferences on computational requirements
without significantly decreasing the classification performance.

(a) MNIST Fashion - Dress

(b) Medium Network Cluster

(c) MNIST Fashion - Sandal

(d) Big Network Cluster

Figure 4: Illustration of how the selection of $k$ influences the number of
representatives and number of similarity computations. The number of
representatives is in relative numbers to the size of the cluster. For
different clusters as $k$ increases the relative number of comparisons also
increases. However, the size of prototype selected decreases steeply while the
precision only decreases slowly.

###  5.2 Datasets

In this section we briefly describe the three datasets used in the ongoing
subsections for experimental comparison of individual methods.

####  5.2.1 MNIST Fashion

The MNIST Fashion [18] is a well established dataset for image recognition
consisting of 60000 black and white images of fashion items belonging to 10
classes. It recently replaced the overused handwritten digits datasets in many
benchmarks. In case of this dataset, the cosine similarity was used as the
similarity function $s$.

####  5.2.2 20 Newsgroup

This dataset is a known benchmark dataset for text documents processing. It is
composed of nearly 20 thousand newspaper documents from 20 different classes
(topics). The dataset was preprocessed such that each document is represented
by a TF-IDF frequency vector. As a similarity function, we again use the
cosine similarity which is a common choice in the domain of text documents
processing.

####  5.2.3 Private Network Dataset

This dataset was collected on a corporate computer network, originally for the
purpose of network host clustering based on their behavior [6]. The work
defines a specific similarity measure on top of network hosts which we adopt
for this paper. Clusters of network hosts were defined according to results
achieved in the original work as well. Additionally, for the purposes of the
evaluation, clusters smaller than 10 members were not considered, since such
small clusters can be easily represented by any method. In contrast to the
previous datasets, the sizes and values of homogeneity of clusters in the
Network dataset differ significantly.

###  5.3 Evaluation of Results

In this section we present the results for each dataset in detail. The main
results are summarized in Table 1. For a more complete picture we also
included results for a random 5% and all 100% of the cluster as a prototype.
The statistical comparison of the methods can be found in Figure 5. Better
rankings for some of CRS methods reflect, that CRS only covers $\epsilon$
which removes the outliers that decrease precision and recall of full cluster
representation.

Method | MNIST Fashion | 20Newsgroup | Network
---|---|---|---
$\delta$-medoids | 0.763/0.744 (4.73%) | 0.542/0.515 (14.51%) | 0.865/0.978 (7.38%)
DS3 | 0.657/0.563 (0.07%) | 0.133/0.132 (0.64%) | 0.87/0.977 (1.88%)
random-5% | 0.793/0.784 (5.0%) | 0.452/0.435 (5.06%) | 0.958/0.97 (5.09%)
full-100% | 0.823/0.817 (100.0%) | 0.56/0.548 (100.0%) | 0.987/0.963 (100.0%)
CRS-k5 | 0.855/0.852 (87.71%) | 0.635/0.632 (56.58%) | 0.988/0.958 (65.31%)
CRS-k10 | 0.836/0.826 (15.37%) | 0.538/0.516 (7.14%) | 0.985/0.965 (7.74%)
CRS-k15 | 0.828/0.823 (5.08%) | 0.522/0.488 (5.17%) | 0.983/0.982 (5.26%)
Table 1: Average precision/recall values for each method used on each dataset.
The table also shows the percentage of the cluster that was selected as a
prototype. Our algorithm is on par with existing methods while selecting
noticeably fewer representatives.

(a) MNIST precision (b) news precision (c) network precision

(d) MNIST recall (e) news recall (f) network recall

Figure 5: Critical difference diagram comparison (cf. [19]) of algorithms
constructed using Friedman’s test with correction for multiple post-hoc
hypotheses by Shaffer [20]. The diagrams show the average rank of each
algorithm over all clusters in each dataset, groups of algorithms that are not
significantly different (p=0.05) are connected.

When evaluating the experiments, we take into account both precision/recall
and the percentage of samples selected as prototypes. As we have shown in the
experiment in Section 5.1, CRS can be tuned by the parameter $k$ to
significantly reduce the number of representatives and maintain a high
precision/recall values. When using the full cluster as its prototype, the
average values of precision and recall are slightly lower than when using the
CRS method. This shows that CRS with $\epsilon=0.95$ makes the classification
immune to outliers which can otherwise decrease the classification quality.
The DS3 method selects a significantly lower number of representatives than
any other method. However, it is at the cost of lower precision and recall
values.

Runtimes of individual algorithms also differ significantly. We evaluate the
runtime requirements of each algorithm by the relative number of similarity
computations $S$ defined as:

$S=\frac{S_{actual}}{S_{full}},$ (5)

where $S_{actual}$ stands for the actual number of comparisons made and
$S_{full}$ is the hypothetical number needed for computing full similarity
matrix.

We use DS3 with the full similarity matrix to get most accurate results,
therefore $S_{DS3}=1$. For $\delta$-Medoids the number of computations
performed can not be easily preset. Therefore, we averaged the number of
comparisons over different values of $S_{\delta}\in[0.45,0.7]$ (the number
might differ significantly for different values of $S_{\delta}$). For CRS the
number of comparisons is influenced by $k$, homogeneity of each cluster and
its size. The impact of $k$ was discussed in detail in Section 5.1. The
experiment shows that one can make assumptions about $S$ based on the size of
the cluster and $k$ (i.e. for MNIST Fashion dataset $S_{CRS-k10}=0.063$,
$S_{CRS-k15}=0.13$).

####  5.3.1 MNIST Fashion

The average homogeneity of a cluster in the MNIST Fashion dataset is 0.76.
This corresponds with a slower decline of the precision and recall values as
the number of representatives decreases. In Figure 6 the steep decline of
representatives selected decreases only slightly decreases the precision and
recall for the each cluster. In the case of the the Dress cluster it even
slightly increases from $k=10$ to $k=15$. In Figure 7 are the confusion
matrices for the methods.

Figure 6: Visualization of precision and recall of all methods in relation to
percentage of cluster selected on chosen clusters for the MNIST Fashion
dataset. Values 0.0 for some clusters for DS3 mean that less than 0.1% objects
were selected as representatives.

(a) CRS-k10

(b) $\delta$-Medoids

(c) DS3

Figure 7: Confusion matrices for a cluster from each category in the MNIST
Fashion dataset show the performance all 3 methods compared. The Sandal class
was the hardest to represent for all methods. This is also quantified in
Figure 6.

####  5.3.2 20Newsgroup

The 20Newsgroup dataset has the lowest average homogeneity $h=0.0858$ from all
the datasets. The samples are less similar on average, therefore the lower
precision and recall values. It reflects in the percentage of objects selected
as representatives by the $\delta$-Medoids algorithm. Confusion matrices for
one cluster form each subgroup are in Figure 8.

(a) CRS-k10

(b) $\delta$-Medoids

(c) DS3

Figure 8: Confusion matrices for a cluster from each category in the
20Newsgroup dataset show the performance all 3 methods compared. The confusion
matrix for DS3 visualizes the results from Table 1

####  5.3.3 Network Dataset

The results for data collected in real network further prove assumptions made
in Section 5.1.

Figure 9 shows comparison of individual methods by means of precision and
recall for selected large clusters as well as the impact of different values
of $k$. The depicted clusters were chosen for their sizes and different
homogeneity, see Table 2.

Cluster | A | B | C | D | E | F | G | H | I | J | K | L | M | N
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Size | 1079 | 2407 | 75 | 2219 | 346 | 59 | 248 | 49 | 52 | 108 | 218 | 44 | 42 | 32
Homogeneity | 0.58 | 0.14 | 0.84 | 0.64 | 0.60 | 0.92 | 0.34 | 0.84 | 0.69 | 0.35 | 0.78 | 0.35 | 0.79 | 1.0
Table 2: Sizes and approximate homogeneity for each cluster from network
dataset.

Increasing $k$ significantly reduces the percentage of dataset selected for
its representation while still retaining high precision and recall values. The
results on the network dataset are very important because it is a non-metric
dataset, where only a pair-wise similarity is defined.

Figure 9: Visualization of precision and recall of all methods in relation to
percentage of cluster selected on chosen clusters from the Network dataset.

##  6 Conclusion

This paper proposed a new method called CRS for building representations of
clusters — cluster prototypes which are small subsets of the original
clusters. CRS leverages nearest neighbor graphs to map structure of each
cluster and to identify the most important representatives that will form the
cluster prototype. Thanks to this approach, CRS can be equally applied in both
metric and non-metric spaces. The proposed method was compared to the prior
art in a nearest prototype classification setup on multiple datasets from
different domains. The experimental results show that the CRS method achieves
superior classification quality while producing comparably compact
representations of clusters.

## References

  * [1] Sambu Seo, Mathias Bode, and Klaus Obermayer.  Soft nearest prototype classification.  IEEE Transactions on Neural Networks, 14(2):390–398, 2003.
  * [2] F-M Schleif, Thomas Villmann, and Barbara Hammer.  Local metric adaptation for soft nearest prototype classification to classify proteomic data.  In International Workshop on Fuzzy Logic and Applications, pages 290–296. Springer, 2005.
  * [3] Alejandro Cervantes, Inés Galván, and Pedro Isasi.  An adaptive michigan approach pso for nearest prototype classification.  In International Work-Conference on the Interplay Between Natural and Artificial Computation, pages 287–296. Springer, 2007.
  * [4] Alessio Martino, Alessandro Giuliani, and Antonello Rizzi.  Granular computing techniques for bioinformatics pattern recognition problems in non-metric spaces.  In Computational Intelligence for Pattern Recognition, pages 53–81. Springer, 2018.
  * [5] Glenn C Becker.  Methods and apparatus for clustering templates in non-metric similarity spaces, October 12 2010.  US Patent 7,813,531.
  * [6] Martin Kopp, Martin Grill, and Jan Kohout.  Community-based anomaly detection.  In 2018 IEEE International Workshop on Information Forensics and Security (WIFS), pages 1–6. IEEE, 2018.
  * [7] Walter J Scheirer, Michael J Wilber, Michael Eckmann, and Terrance E Boult.  Good recognition is non-metric.  Pattern recognition, 47(8):2721–2731, 2014.
  * [8] Ehsan Elhamifar, Guillermo Sapiro, and S Shankar Sastry.  Dissimilarity-based sparse subset selection.  IEEE transactions on pattern analysis and machine intelligence, 38(11):2182–2197, 2015.
  * [9] Elad Liebman, Benny Chor, and Peter Stone.  Representative selection in nonmetric datasets.  Applied Artificial Intelligence, 29(8):807–838, 2015.
  * [10] Isaac Triguero, Joaquín Derrac, Salvador Garcia, and Francisco Herrera.  A taxonomy and experimental study on prototype generation for nearest neighbor classification.  IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(1):86–100, 2011.
  * [11] Shlomo Geva and Joaquin Sitte.  Adaptive nearest neighbor pattern classification.  IEEE Trans. on Neural Networks, 2(0):2, 1991.
  * [12] Qiaobing Xie, Charles A Laszlo, and Rabab K Ward.  Vector quantization technique for nonparametric classifier design.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 15(12):1326–1330, 1993.
  * [13] Salvador Garcia, Joaquin Derrac, Jose Cano, and Francisco Herrera.  Prototype selection for nearest neighbor classification: Taxonomy and empirical study.  IEEE transactions on pattern analysis and machine intelligence, 34(3):417–435, 2012.
  * [14] Hongxing Wang, Yoshinobu Kawahara, Chaoqun Weng, and Junsong Yuan.  Representative selection with structured sparsity.  Pattern Recognition, 63:268–278, 2017.
  * [15] Xingxing Zhang, Zhenfeng Zhu, Yao Zhao, Dongxia Chang, and Ji Liu.  Seeing all from a few: l1-norm-induced discriminative prototype selection.  IEEE transactions on neural networks and learning systems, 30(7):1954–1966, 2018.
  * [16] J Arturo Olvera-López, J Ariel Carrasco-Ochoa, and J Martínez-Trinidad.  Accurate and fast prototype selection based on the notion of relevant and border prototypes.  Journal of Intelligent & Fuzzy Systems, 34(5):2923–2934, 2018\.
  * [17] Wei Dong, Charikar Moses, and Kai Li.  Efficient k-nearest neighbor graph construction for generic similarity measures.  In Proceedings of the 20th international conference on World wide web, pages 577–586, 2011.
  * [18] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
  * [19] Janez Demšar.  Statistical comparisons of classifiers over multiple data sets.  The Journal of Machine Learning Research, 7(Jan):1–30, 2006.
  * [20] Juliet Popper Shaffer.  Multiple hypothesis testing.  Annual review of psychology, 46(1):561–584, 1995.