Attention-Based Clustering: Learning a Kernel from Context
Authors: Samuel Coward
Erik Visse-Martindale
Chithrupa Ramesh
Venue:  (2021)
Keywords: Similarity learning
kernel methods
constrained clustering
transformer analysis
spectral clustering
supervised learning
deep learning

Abstract: In machine learning, no data point stands alone. We believe that context is an underappreciated concept in many machine learning methods. We propose Attention-Based Clustering (ABC), a neural architecture based on the attention mechanism, which is designed to learn latent representations that adapt to context within an input set, and which is inherently agnostic to input sizes and number of clusters. By learning a similarity kernel, our method directly combines with any out-of-the-box kernel-based clustering approach. We present competitive results for clustering Omniglot characters and include analytical evidence of the effectiveness of an attention-based approach for clustering. 

Under review as a conference paper at ICLR 2021
ArTENTION-BASED CLUSTERING: LEARNING A KERNEL FROM CONTEXT
Anonymous authors Paper under double-blind review
ABSTRACT
In machine learning, data point stands alone. We believe that context is an underappreciated concept in many machine learning methods. We propose Attention-Based Clustering (ABC), neural architecture based on the attention mechanism, which is designed to learn latent representations that adapt to context within an input set, and which is inherently agnostic to input sizes and number of clusters. By learning a similarity kemel, our method directly combines with any out-of-the-box kernel-based clustering approach. We present competitive results for clustering Omniglot characters and include analytical evidence of the effec- tiveness an attention-based approach for clustering.
INTRODUCTION
Many problems in machine learning involve modelling the relations between elements of set. A notable example, and the focus of this paper, is clustering, in which the elements are grouped ac- cording to some shared properties. A common approach uses kernel methods: a class of algorithms that operate pairwise similarities, which are obtained by evaluating specific kernel function (Fil- ippone et al. 2008). However, for data points that are not trivially comparable, specifying the kernel function is not straightforward.
With the advent of deep learning. this gave rise to metric learning frameworks where a parameterized binary operator, either explicitly or implicitly, is taught from examples how measure the distance between two data points (Bromley et al., 1993] Koch et al.) 2015 Zagoruyko & Komodakis 2015) Hsu al., 2018 Wojke & Bewley] 2018 Hsu et 2019). These cases operate on the assumption that there exists global metric, that is, the distance between points depends solely on the two operands. This assumption disregards situations where the underlying metric is contextual, by which we mean that the distance between two data points may depend on some structure of the entire dataset.
We hypothesize that the context provided by a set of data points can be helpful in measuring the distance between any two data points in the set. As an example of where context might help, con- sider the task of clustering characters that belong to the same language. There are languages, like Latin and Greek, that share certain characters, for example the Latin T and the Greek upper case should have
T However, given two sentences, one from the Aeneid and one from the Odyssey, less trouble clustering the same character in both languages correctly due to the context, even when ignoring any structure meaning derived from the sentences themselves. Indeed, human perform- ing this task will not need to rely on prior knowledge of the stories of Aeneas or Odysseus, nor on literacy in Latin or Ancient Greek. As larger principle, it is well recognized that humans perceive emergent properties in configurations of objects, as documented in the Gestalt Laws of Perceptual Organization (Palmer 1999. Chapter 2).
We introduce Attention-Basse Clustering (ABC) which uses context to output pairwise similarities between the data points in the input set. Like other approaches in the literature (Hsu et al. 2018 2019 Han et al.; 2019 Lee et al. 2019b), our model is trained with ground-trutt labels in the form of pairwise constraints, but in contrast other methods, ours can be used with an unsupervised clustering method to obtain cluster labels. To demonstrate the benefit of using ABC over pairwise
To the extend that there not even LaTeX command Vrau

---

Under review as a conference paper at ICLR 2021
A
B
C
D
Figure 1: Illustration of the output of different clustering methods for points sampled from four overlapping circles. (A) ABC with additive attention. (B) ABC with multiplicative attention. (C) Pairwise similarity with additive attention. Pairwise similarity with multiplicative attention per- formed similarly. (D) Out-of-the box spectral clustering. Only D was given the true number of clusters. (Best viewed in colour.)
metric learning methods, we propose clustering problem that requires the use of properties emerg- ing from the entire input set in order to be solved. The task to cluster set of points that lie on number of intersecting circles, which is a generalization of the Olympic circles problem (Anand itt al., 2014). Pairwise kernel methods for clustering perform poorly on the circles problem, whereas our ABC handles it with ease, displayed in Figure I We use the circles dataset for ablation study in Section 6.
In recent years, numerous deep neural network architectures have been proposed for clustering Xie jet al. 2016; Min et al.) 2018). The idea of using more than pairwise interactions between elements of imput set in order to improve clustering has been pursued recently in Lee al. (2019a b), and is motivated by the problem of amortized clustering (Gershman & Goodman 2014 Stuhlmüller al. (203). Our architecture is inspired by the Transformer ( (Vaswani al. [0.0 7), which was used by Lee et al. (2019a) as the Set Transformer to improve clustering (Lee et al.) (019b). We inherit its benefits such as being equivariant under permutations as well as agnostic to input size. However, our approach is motivated by the use of context to improve metric learning, giving moreover agnostic to the number of clusters in the sense that neither prediction nor bound on the number of clusters needs to be specified for the architecture definition. We also provide theoretical evidence that the Transformer architecture is effective for metric learning and clustering, and to our knowledge, are the first to do so.
model that is
The idea of using deep metric learning to improve clustering has been pursued Koch et al. (215)); Zagoruyko & Komodakis (2015); Hsu et al. (2018) 2019h; Han et al. (2019). but without considering the use of context. We use ground-truth labels, only in the form of pairwise constraints, to train a similarity kernel, making our approach
example of constrained clustering. These algorithms often categorized by whether they use the constraints to only learn a metric or to also generate clus- ter labels (Hsu et al.) 2018). Our architecture belongs to the former category, where we only the constraints to learn metric and rely on an unconstrained clustering process to obtain cluster labels. Despite this, we achieve nearly state-of-the-arr clustering results on the Omniglot, embedded Ima- geNet, and CIFAR- 100 datasets, comparable to sophisticated methods that synthesize clusters, either using the constraints (Hsu et al. 2018 2019 Han al. 2019) or otherwise (Lee et al. 2019a b).
Our main contributions are:
ABC incorporates context in a general and flexible manner improve metric learning for clustering. Our competitive results on Omniglot, embedded ImageNet, and CIFAR-100, as well as our ablation study on our circles dataset provide support for the use of context in metric learning algorithms.
We provide theoretical evidence of why the self-attention module in the Transformer archi- tecture is well suited for clustering, justifying its effectiveness for this task.
2

---

Under review as a conference paper at ICLR 2021
2 RELATED WORKS
Our method is similar to line of research where a distance metric, rather than a similarity score, learned in a supervised manner, which can then be used as input off-the-shelf clustering meth- ods (Xing et al.] 2003] (Shale--Swartz et al. 2004 Davis et al. 2007). Only certain classes of distances, such as the Mahalanobis distance, are learned. In general. deep neural nets offer the ability to learn a more general class of distances, and have been used to learn pairwise metric in numerous works (Zagoruyko & Komodakis 2013 Hsu et al.) 2018 Wojke & Bewley 2018 Hsu et al. 2019), most notably in the Siamese network (Bromley et al., 1993; Koch et al. 2015). The
idea of using contextual information has not been explored in any of these papers. Many models go further than metric learning by also learning how synthesize clusters. An example of constrained clustering can be found in Anand et al. (014)); Amid et al. (2015). where pairwise constraints are used transform a predefined kernel in an iterative manner, which is used in a kernel mean shift clustering algorithm. Constrained clustering algorithmss have been implemented using deep neural nets as well. In Hsu et al. 2018 2019), the authors train a similarity metric and transfer learning to secondary clustering model. Both models are trained using only pairwise constraints, and any available context information remains unused in both components of their architecture. In Han et al. 2019). constrained clusterer inspired by the deep embedded clustering idea (Xie et al. 2016) is proposed, along with a number of best practices such as temporal ensembling and consistency con- straints in the loss function. These techniques are fairly generic and can perhaps be applied to any other clustering algorithm to improve its results. Their model generates clusters by slowly annealing them, requiring optimization and
even test time. The models from Hsu et al. (018)) Hsu al. (2019) also have this requirement. This may not be feasible during deployment.
A more detailed discussion of the differences between our approach and that Lee al. (2019a b) is in order. The Set Transformer architecture (Lee et al.) 2019a) uses the Transformer as contextual encoder, followed by pooling layer that uses fixed number of seed vectors as queries. This architecture is used to cluster a mixture of Gaussians, but is less flexible than ours for two reasons: requires the number of clusters in advance in setting the number of seed vectors, and those seed vectors being learned makes their approach less adaptable to unseen classes. The first limitation is addressed in follow-up paper (Lee et al. 2019b), with the use of an iterated process to filter out clusters and stopping condition. Our architecture, due to its use of metric learning in place of the pooling layer with learned seed vectors, is inductive and better suited to handle new classes. We also present mathematical justification for the use of the Transformer in clustering applications. Lastly, Lee et al. (2019)) contains no clustering results on real-world data. Lee et al. (2019b) does and our results on embedded ImageNet are similar, while Omniglot are significantly better.
BACKGROUND
Taking inspiration from kernel methods, we aim to compute similarity matrix from sequence of data points. Our architecture is inspired by ideas from two streams: the metric learning literature and the Siamese network (Bromley et al. 1993; Koch et al. 2015) on how learn compatibility scores, and the Transformer architecture ( (Vaswani et al.) (017) and the Set Transformer (Lee et al. (001a) on how to use context to make decisions. We discuss a few concepts from the literature which will form building blocks of our architecture in the next section.
3.1 COMPATIBILITY
In this section we introduce some compatibility functions which compute a similarity score between two vector arguments, called the query and key respectively. We present the forms of compatibility used in this paper in Table for both of these forms, keys and queries are required to have equal dimension d.
In Siamese Networks (Koch et al. 2015). compatibility between two input images is measured by the sigmoid of weighted Li-distance between representations of the input. This be seen as a special case of additive compatibility above. The Transformer (Vaswani et al. 2017) and Set Transformer (Lee et al. 2019a make use of multiplicative compatibility
3

---

Under review as a conference paper at ICLR 2021
Table 1: Possible implementations of the compatibility function. act is any elementwise activation function, such as tanh or s immoidd.
Form
Parameters
Expression
Reference
Multiplicative
None
qTk/vo /d
(Vaswani et 2017
Additive
w R
act (q + k)w (Bahdanau et 2015
3.2
THE TRANSFORMER
The attention mechanism forms the core of the Transformer architecture, and generates contextually weighted convex combinations of vectors. The elements included in this combination called values and the weights are provided via compatibilities between queries and keys as the previous section.
Suppose we have a length m sequence of query vectors and a length n sequence of key-value pairs. We denote the the dimensionality of each query, key and value vector by dg. dg. and d, respectively. In matrix form, these are expressed as E mmxd, for the queries, K Raxde for the keys, and V E 1nxd for the values. The attention function Att with sofumax activation is given as
ACt(Q, K, V) AV, exp(Cr.)
with Aij E exp(C(,k)
(i.e. row wise softmax),
for C== compat (erppattQQ,A (Q, R
The result is a new encoded sequence of length m. We use the terms additive or multiplicative attention specify the compatibility function that particular form of attention uses.
Multi-head Attention (MHA) (Vaswani et al., 2017) extends the standard attention mechanism to employ multiple representations of the data in parallel. The parallel outputs of that are concatenated and linearly transformed. The result is matrix in Rmaxd, For our purposes we will only need the
Self Attention Block (SAB) where the queries, keys, and values are all equal. denote the special case as
Lee et al. (2019a)
SAB(X, X, X) LayerNorm H FF())), with H = LayerNorm( X MHA(X, X,X)),
(1)
(2)
where FF is a feed-forward layer operating elementwise, and LayerNorm is layer normalisa- tion (Ba et al. 2016)
ARCHITECTURE
The ABC architecture is a composition of previously introduced components. the most general case, ABC expects variable-sized set of elements input, where each element is represented by fixed-sized feature vector. From this, ABC outputs a square matrix of the similarity scores between all pairs of elements in the input.
note on terminology: some literature uses the word mini-batch to mean a single input set whose elements to be clustered. To avoid confusion with the concept of neural network, from now on we opt to reserve the terminology input instance instead.
used in training
4.1 ABSTRACT DEFINITION
Let d2 be the dimensionality of input elements and d, be the desired number of latent features. chosen hyper-parameter ABC consists of two sequential components:
1. Embedding: A function T mapping an any length sequence of elements in IR same- length sequence of encoded elements in Rdd, or in tensor notation: for any E N we have T dg Raxd.
2. Similarity: A kernel function
Rdd x dR R.

---

Under review as a conference paper at ICLR 2021
such that for X E Rexde the output is x n-matrix. Explicitly, composing these parts gives us for any n E a function ABC Raxd, - R=*x with
ABC(X) ((T())
4.2 EXPLICIT EMBEDDING AND SIMILARITY
We construct the embedding layer by composing fixed number of SAB
T(X) = (SAB) o ... 3XX
and we rely on the embedding stage to capture the relevant information related to all terms of the input instance and encode that within every term of its output. As such, computing the similarity can simply be performed pairwise. We now make the choice constrain the output of the similarity function k to lie in the unit interval. Our choice for the symmetric similarity component is
<,Zz, 2,) = 2 i gmoid gmoid(compat(/..). k;)) + s gmo derooidccompaaa [3)]]
where z, is the ith term the encoded sequence. This choice satisfies the two constraints of sym- metry and mapping to the unit interval.
4.3 LOSS FUNCTION AND TRAINING
Given a labelled input instance comprised of a collection of elements and corresponding cluster labels, train ABC in supervised manner using binary ground-truth matrix indicating same- cluster membership. Each cell of the output matrix can be interpreted as the probability that two elements are members of the same cluster. The loss is given as the mean binary cross entropy (BCE) of each cell of the output matrix.
4.4 SUPERVISED KERNEL TO INSUPERVISED CLUSTERING
ABC learns mapping directly from an input instance to kernel matrix. We pass this matrix in to off-the-shell kernel-based clustering method, such as spectral clustering, to obtain the cluster labels.
What remains is to specify the number of clusters present in the predicted kernel. Depending on the use-case this can be supplied by the user or inferred from the kernel matrix by using the eigengap method (von Luxburg 2007). Let A be the symmetric kernel matrix. The number of clusters inferred from this matrix is
NumClusters( A) argmax (2: Ait1);
where is the vth largest eigenvalue of the normalized Laplacian - D and where D is the diagonal degree matrix of A.
5 ANALYSIS
In this section we discuss some theoretical properties of the architecture. We focus on the role of attention and the effects of skip-connections (He et al. (0166). In particular, elements are able to separate clusters from other clusters, making it easier for the similarity block of ABC to learn pairwise similarity scores based on the context given by the entire input instance.
show how these
We consider simplified version of the SAB using just single attention head. It is not difficult prove that attention with any compatibility function maps set of vectors into its convex hull, and that the diameter of the image is strictly smaller than the diameter of the original. This leads repeated application to blur the input data too much to extract relevant features. This behaviour is also noticed in Bello et al.] (2017) and is counteracted in the Transformer by the use of skip- connections. Reports showing that skip-connections play a role preserving the scale of the output in feed-forward networks can for example be found in Balduzzi et al. (2017). Zaeemzadeh et al.
In particular this forces d, d, in the abstract definition of

---

Under review as a conference paper at ICLR 2021
2018), and include short discussion the same effect in our setting in Appendix A.2
We
note that the remaining parts of the Multi-Head attention block as described in equations ① and (2)
Le. the layer normalizations and the elementwise feed-forward layer, are of 'global' nature, by which we mean that they do not depend on different elements in the input instance. These parts
merely support the functionality of the network along more general deep learning terms and they do not form an interesting component to this particular analysis.
The counterbalanced contraction discussed above holds for the entire dataset whole, but more structure can be uncovered that motivates the use of the set encoder in our architecture. Somewhat informally we may state it as the following, of which the formal statement and proof are treated in Appendix A.I
Proposition 1. Assume are given set of points that falls apart into two subsets A and B, where the painwise compatibility weights within each of A and B are larger than the pairwise weights between A and B. Under repeated application of SABs and under some symmetry conditions, the two subsets become increasingly separated.
Anand et al. (2014) use a similar idea to devise a transformation for their kernel. A linear trans- formation is designed to bring pairs of points from a cluster closer together and to push pairs of points from different clusters apart, by iterating over all labelled pairs. The Transformer architecture accomplishes this without the restriction of linearity and without the need for iteration over points in an input instance due to an amortization of the clustering process.
6 EXPERIMENTS
We conduct some experiments to validate the feasibility of our architecture and to evaluate the claim that context helps learn good similarity output. We give details on how we sample training instances in Appendix B It is interesting to see that neither form of additive or multiplicative attention is consistently better than the other. For this reason we refrain from making a choice between them and report both results for each experiment.
6.1 ToY PROBLEM: POINTS ON CIRCLE
To generalize the phenomenon of real-world datasets intersecting, such as characters in multiple languages, as well as to illustrate the necessity for context during some clustering tasks, we devise the following toy problem. Given a fixed-length sequence of points, where each point lies four likely overlapping circles, cluster points according to the circle they lie on. As we will demonstrate, only considering the pairwise similarities between points is insufficient to solve this problem, but our architecture does give a satisfactory solution.
We try variants of ABC, with additive attention and the other with multiplicative attention. As an ablation study, we compare against a pairwise metric learning method as well as out-of-the- box spectral clustering. For the pairwise metrie learning method, we remove the embedding block from ABC and use only the similarity block with additive compatibility. For all these methods, the 128-dimensional space including tanh activation,
input data is first transformed elementwise and this pre-embedding is trained independently for each method. By comparing with spectral clustering, we show the improvement that our architecture brings.
In Figure 2 we present the adjusted Rand score of all these clustering methods for different values of input instance length. For each instance, four circles with a random radii and centers are gen- erated, while guaranteeing that every circle overlaps with at least one other circle. For each point, one of the circles is picked with equal probability, and the point then sampled uniformly from that circle. Notice that the pairwise method performs poorly, in fact worse than out-of-the-box spectral clustering. This can be explained by the use of radial basis functions in spectral clustering intermally to compute the affinity matrix, which is relatively well-suited for the circles problem. The multi- plicative and additive variants of ABC far outperform the other two methods on the circles problem, thus validating our of context in learning metric.

---

Under review as a conference paper at ICLR 2021
Comparison of Clustering Methods on Circles Dataset
NMI for validation set
livel
20-
hilictaee MBC
nomaa Ded mubua intermizoon score Sohe-1NN
Spectrol [emd]
livel Painese
kandam
2.7-
020
3.--
124
0003204
04-
0.3
0.-
022
1%, (Roww))
-0.2
z0 Schonn 10
200
175
Input Instance
Figure 2: Comparative performance on the cir- cles problem of ABC with either additive multiplicative attention, as well as ablated ver- sions of the ABC architecture. The horizontal axis shows the number of points sampled from the combined eircles. The vertical axis shows the Rand score adjusted so that random assign- ment gives score of The big gap in perfor- mance between pairwise and spectral clustering on the one hand and the two versions of ABC on the other shows the benefit that context brings.
Figure 3: Clustering performance on the test set for our three clustering tasks Omniglot over the course of training. It is worth noting that training is visibly noisier for unknown numbers of clusters, which indicates that the off-the-shelf cluster number estimates are unstable. As the model improves, estimating the number of clus- ters becomes more accurate, and the disadvan- tage of not knowing the true number of clusters becomes negligible.
6.2 OMNIGLOT CLUSTERING
The Omniglot training dataset (Lake et al. 2015) consists of hand-drawn images of characters from 30 alphabets, with another 20 alphabets reserved for testing. Each alphabet has varying numbers of characters, each with 20 unique example images. This dataset was proposed to test model per- formance one-shot learning tasks (Lake et al. 2019), where model must learn from single examples of novel categories. We attempt clustering of images from classes within novel alphabets. We treat each character as class such that alphabet is grouping of related classes. Notice that context is still relevant within the same alphabet, as we also discuss in section 7 Tand Figure 4
For training, each input instance consists of 100 within alphabet images, where the number of unique characters per input instance varies as much as permitted by the available data. We use the CNN from Vinyals et al. (2016) the image embedding function. Training conducted using our imple- mentation in P and uses the standard Adam optimizer. Details of the data augmentation and the hyperparameters can be found in Appendix C.I
For testing, we use the 20 alphabets from the reserved lot in Omniglot, as a standalone dataset each. At test time, an instance of 100 images are presented to the model, assembled as random number of elements chosen from certain number of clusters as described below. We report clustering performance on three tasks with: (i) a variable number of clusters, unknown inference, (ii) a variable number of clusters, known at inference, and (iii) fixed number of clusters (k 20), known at inference. Note that training is independent of the task; at inference time, all tasks use the same trained model. The scores are similar across the three tasks, and can be found in the bottom row of Table 5 in the Appendix. This indicates that the kernel is well-trained irrespective of the specifies of the downstream out-of- the box clustering task.
Our results show that ABC performs equally well on all three tasks. In particular, the Normalized Mutual Information score (NMI)) obtained with an unknown number of clusters matches the val-
*Code will be available redacted.
'Contrary to the adjusted Rand score, NMI is not adjusted for randomness. Despite this it appears to be the default metric in recent clustering results. We report our results on real-world data in NMI so that we compare against alternative methods.
7

---

Under review as a conference paper at ICLR 2021
Table 2: Comparative results on Omniglot. The table presents results for known and unknown number of clusters. Where the architecture relies on knowning a (maximum) number of clusters, such KLC, that maximum is set 100. The first four entries are copied from (Hsu (2018) as their methods are most relevant in comparison to ours. The table is split up explained in the main text.
Method
NMI (known)
NMI (unknown)
Reference
ITML
0.674
0.727
Daviis et al.
2007
SKMS
0.693
Anand al.
2014
SKKm
0.770
0.781
Anand et al.
2014
SKLR
0.791
0.760
Amid al.
2015)
ABC (add. compat.)
0.873
0.816
(ours)
ABC (mul. compat.)
0.893
0,874
(ours)
DAC
0.829
LLee et al.
2019b)
KLC
0.889
0.874
Hsu a..
2018
MLC
0.897
0,893
(Hsu et al.
2019)
DTC-II
0.949
0,945
(Han et al.
2019)
that are obtained when the number of clusters is known. Hence, after training the model to convergence, it is not necessary to know the true number of clusters to obtain good performance.
In [ we compare against previous results reported on this problem. In this table, there are two categories of clustering methods; the first four methods use supervised metric learning in combina- synthesize tion with unsupervised clusterers, whereas the last four methods use the constraints clusters, which adds to the model complexity. ABC belongs to the former category, but performs comparably to the latter category of clustering methods. Also notice that ABC with multiplicative compatibility outperforms the only other method that uses context, distinguished by the t symbol added to name Table 2 This validates our hypothesis that context can improve metric learning. and that using context be valuable when working with real world data.
6.3 EMBEDDED IMAGENET CLUSTERING
We also perform experiments on embedded ImageNet (Deng et al., 2009), where ABC again gets competitive results, using the embeddings generated by Rusu results. Each embedded image is represented as a feature vector of length 640. Matching the setup described by [ee et al. (2019b), the predetermined training and validation subsets are used as the labelled data and the test subset is used as the unlabelled data. This produces a training set consisting of 620000 feature vectors across 495 classes, and a test set consisting of 8000 samples across 176 classes, with overlap between training and test classes. Both training and test instances are of length 300, each consisting of minimum of 2 and maximum 12 classes. ABC operates on the embeddings directly.
(2019). See Tables for the
Table 3: Clustering results embedded Ima- Table 4: Clustering results CIFAR- 100. The geNet. The cited scores are copied from Lee et al. (019b)).
cited scores are copied from Han et al. 2019).
Method
NMI (known)
NMI (unk.)
Method
NMI (known)
NMI (unk.)
KLC
0.361
KLC
0.151
MLC
0.350
MLC
0.202
DAC
0,579
DTC-TE
0.634
ABC (add.)
0.612
0.521
ABC (add.)
0.527
0.505
ABC (mul.)
0.630
0.550
ABC (mul.)
0.591
0.567
6.4 CIFAR-100 CLUSTERING
As third exhibit of competitiveness on real-world data, we include experimental results on CIFAR-
100 (Krizhevsky 2009) in T CIFAR-100 consist of 60000 colour images of size x2 32 across
8

---

Under review as a conference paper at ICLR 2021
100 classes, where each class has exactly 500 training examples and 100 evaluation examples. We combine the training and evaluation examples, and partition the dataset by classes. Similar to Han reserved as unlabelled data and are not seen during training.
et al. (2019), the last 10 classes Training and test instances are of length 128, each consisting of a minimum of and a maximum of 10 clusters. Images are embedded using the VGG-like architecture (Simonyan & Zisserman, 2015) from Han et al. (2019) before being passed in to ABC. This elementwise encoder is randomly initialized and trained together with the rest of our model.
DISCUSSION
is perhaps unsurprising that the Transformer architecture performs well for clustering in addition to number of other areas. The self- self-attention module in the Transformer architecture offers unique advantage neural networks: this module acts as linear layer whose weights are determined by the compatibility scores of the queries and keys rather than fixed set of learned values. This makes the self-attention module nonparametric approximator (Wasserman) 2006 Orbanz Teh 2010), whose expressivity is far more than what might be expected by looking at the parameter reuse in the compatibility module (Yun et al. 2020).
The encoder in ABC can be seen to be balancing the two objectives of using context and learning from ground-truth labels, the manner in which combines the multi-head attention term with skip-connection. This sometimes gives rise to conflicts, the imput instance consists of all the variations the letter k. The predicted similarity matrix is far from the ground-truth: a perceived mistake by the model. Upon closer look however, that while each element represents the same character, each of them written a slightly different way. For this particular input instance, those small differences are precisely what makes up the relevant context, and the model is able to pick up on that. A modified version of the Transformer
in the example in Figure 4 Here,
using weighted skip-connections as in Highway Networks (Srivastava al. 2013) should enable to learn when to focus context and when not to.
A
B
K
K
K
K
K
Actual
Predicted
H
R
K
K
K
K
K
K
K
K
K
K
K
K
K
Figure 4: (A) Example input instance of characters all of the same class. (B) Ground-truth and predicted similarity matrices and their difference in greyscale, where white means value of 1 and black a value of ABC picks up on the small differences between each of the characters; this is precisely the context that this input instance provides.
Reimagining ABC graph neural network (Scarselli et al. 2009 Zhang et al. 2019) could enable handle datasets where explicit context is available the form of a weighted adjacency matrix rather than merely binary ground-truth cluster labels. To accomplish this, we would use graph attention network that incorporates weighted adjacency data in the encoder. (Veličković et al. 2018)
So far, the use of constraints has been limited to learning similarity kernel in ABC, in contrast the approach taken in Hsu et al. (2018). A hybrid approach where the similarities are learned instance wise, like in ABC, and then processed using learned model which is robust to noise would be an interesting avenue for future research. We would also be interested to see how far we can push our method by including general good practices as in Han et al. 2019)

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ehsan Amid, Aristides Gionis, and Antti Ukkonen. A kernel-learning approach to semi-supervised clustering with relative distance comparisons. Machine Learning and Knowledge Discovery in Databases, pp. 219-234, 2015.
Saket Anand, Sushil Mittal, Oncel Tuzel, and Peter Meer. Semi-supervised kernel mean shift clus- tering. IEEE Trans. Pattenn Anal. Mach. Intell., 36(6):1201-12155 2014.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. 2016. arXiv preprint 1607.06450
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In Yoshua Bengio and Yann LeCun (eds.), International Confer- ence on Learning Representations, 2015.
David Balduzzi, Marcus Frean, Lennox Leary, J. P. Lewis, Kurt Wan-Duo Ma. and Brian McWilliams. The shattered gradients problem: resnets are the answer, then what the ques- tion? In Proceedings of Machine Learning Research, volume 70, pp. 342-34233 350, 2017.
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Learning Representa- tions, 2017.
Jane Bromley, J.W. Bentz, Leon Bottou, I. Guyon, Yann Lecun, C. Moore, Eduard Sackinger, and R. Shah. Signature verification using siamese time delay neural network. International Journal of Pattern Recognition and Artificial Intelligence, 7(4), 1993.
Jason V. Davis, Brian Kulis, Prateek Jain, Suvrit Sra, and Inderjit Dhillon, Information-theoree metric learning. In ICML '07, pp. 209-216, 2007.
J. Deng. W. Dong, R. Socher, L. Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp- 248-255, 2009. doi: 10. 00.1009/CVP.220095200 5206848..
Maurizio Filippone, Francesco Camastra, Francesco Masulli, and Stefano Rovetta. A survey of kernel and spectral methods for clustering. Pattern Recognition, 41(1):176 190, 2008
S. Gershman and Noah D. Goodman. Amortized inference in probabilistic reasoning. Cognitive Science, 36, 2014.
Kai Han, Andrea Vedaldi, and Andrew Zisserman. Learning discover novel visual categories via deep transfer clustering. In International Conference on Computer Vision (ICCV), 2019.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Yen-Chang Hsu, Zhaoyang Lv, and Zsolt Kira. Learning cluster in order to transfer across do- mains and tasks. In International Conference on Learning Representations, 2018.
Yen-Chang Hsu, Zhaoyang Lv. Joel Schlosser, Phillip Odom, and Zsolt Kira. Multi-class classi- fication without multi-class labels. In International Conference on Learning Representations, 2019.
Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov. Siamese neural networks for one-shot image recognition. In Proceedings of ICML, 2015.
Alex Krizhevsky, Learning multiple layers of features from tiny images. Technical Report, 2009.
Brenden M. Lake, Ruslan Salakhutdinov, and Joshua Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 13026266) 2015.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. The omniglot challenge: 3-year progress report. Current Opinion in Behavioral Sciences, 29:97 - 104, 2019. SI: 29: Artificial Intelligence (2019).
10

---

Under review as a conference paper at ICLR 2021
Juho Lee, Yoonho Lee, Jungtack Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set permutation-invariie neural networks. In Pro-
transforeer: A framework for attention- ceedings of ICML, volume 97. pp. 3744-3753, 2019a.
Juho Lee, Yoonho Lee, and Yee Whye Teh. Deep amortized clustering. 2019b. arXiv preprint 1909.13433.
E. Min, X. Guo, Q. Liu, G. Zhang, J. Cui, and J. Long. A survey of clustering with deep learning: From the perspective of network architecture. IEEE Access, 6:39501-39514, 2018.
Peter Orbanz and Yee Whye Teh. Bayesian Nonparametric Models, pp. 81-89. Springer US, 2010.
Stephen E Palmer. Vision science: Photons to phenomenology- MIT press, 1999.
Andrei A. Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osindero, and Raia Hadsell. Meta-learning with latent embedding optimization. In International Conference on Learning Representations, 2019.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2009.
Shai Shalev-Shwarzz, Yoram Singer, and Andrew Y. Ng. Online and batch learning of pseudo- metrics. In /CML '04, pp. 94, 2004.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
Rupesh K Srivastava, Klaus Greff, and Jürgen Schmidhuber. Training very deep networks. In Adv. Neural Inf. Process. Sys 28, pp. 2377-2385, 2015.
Andreas Stuhlmüller, Jacob Taylor, and Noah Goodman. Learning stochastic inverses. In Adv Neural Inf. Process. Sys 26, pp. 3048-3056, 2013.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Adv. Neural Inf. Process. Sys, pp. 5998-6008, 2017.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Match- ing networks for one shot learning. In Adv. Neural Inf. Process. Sys 29, pp. 3637-3645, 2016.
Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-416. 2007.
Larry Wasserman. All of Nonparametric Statistics. Springer, 2006.
Nicolai Wojke and Alex Bewley. Deep cosine metric learning for person re-identification. In 2018 IEEE winter conference on applications of computer vision (WACV), pp. 748-756. IEEE, 2018.
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In Proceedings of Machine Learning Research, volume 48 pp. 478-487, 2016.
Eric Xing, Andrew Ng. Michael Jordan, and Stuart Russell. Distance metric learning, with applica- tion to clustering with iddeinfformatin. Adv. Neural Inf. Process. Sys, 15, 2003.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequeee functions? In International Con- ference on Learning Representations, 2020.
Alireza Zacemzadeh. Nazamin Rahnavard, and Mubarak Shah. Norm porm-rreservation: Why residual networks become extremely deep? 2018. arXiv preprint 1805.07477.
11

---

Under review as a conference paper at ICLR 2021
S. Zagoruyko and N. Komodakis. Learning to compare image patches via convolutional neural networks. In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 4353 153-43361,20 2015.
Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: comprehensive review. Computational Social Networks, 2019.
12

---

Under review as a conference paper at ICLR 2021
A MORE DETAILS ON THE ANALYSIS
A. FORMAL TREATMENT OF PROPOSITION |
Let n and m two positive integers. We will write LA [I...., Consider the discrete time dynamical system on set of points Zi,t Re for E LIU.B E N and some d 2 0, given by the update rule
n) and 1B = (n+l,.... n m.).
A= :=
Ii,t
Wij
(3)
jETAUIB
under the following assumptions:
Wiji = a₁ for i.j Ia, i i j.
Wija = 5; > 0 for i,j IB, i i
Wi, "t. > for i La, j E IB.
Wi,it 5: 0 for i E LA U TB.
Assume for any E U U 1B and / & N moreover
Σ
Wiji =
(4)
jELAUlg
Notice that this is the setup described informally in Proposition 1 for the two clusters given by A = {I1,0 1 IA} and B {=i, : E IB}. The use of skop-conncttions visible in equation
yielding A rather than 21,441 itself.
We will write
Σ Ni,t for p == A,
Cp.t
#Ip tEIp
for the centroids of the two clusters.
We will assume 6; > max 3r} for all / E N. This assumption is natural in our application do- main of similarity scores, and it will fact be necessary Corollary [ While strictly necessary for the proof of Proposition 2 ittsef, we already assume it now so that the quantities involved in the statement of the proposition are non-negative
Proposition Using the notation and assumptions outlined above, the following statements hold:
1. For all i,j Ta and t N have 51,4 Tj,4+1 + 5, (x) -zj,)--
2. For all i,j Ig and I have 24,441 Ij,++1 (1+ + 3.) -z,,).
3. For all we have C1,++1 - 02 (2 - (n + m)):)( - -22)).
Note before we start the proof itself, that expanding for E IA and IB separately gives relations between the different weights:
6 + (n - 1)aa + m = 1, and
(5)
8, + (m 11)8 + no/e 1.
Proof of Proposition 2 The proofs of parts [ and are identical up to switching the roles of IA and TB, so merely give the former, which is by simple computation. For i,j E TA have
ATiit Arj.+1=
Σ WiE.
Σ CETB
W.E.T
Σ BETA
WJ..TTE
Σ
Wj..
EETA
EETB
Notice that the second and fourth sum both equal 71 Etela Fz.1- As they have opposite signs, these two sums disappear from the overall expression. Similarly, each term in the first and third sum that
13

---

Under review as a conference paper at ICLR 2021
corresponds to some & E LA {i,j} occurs with opposite signs in the overall expression and hence disappears. Therefore we arrive at
ATi,11 Atjet1 wiit + wij, W Wj,,
which equals (d, an) wz2 + (a, 61) = (òr - az) Tz.e). Retrieval of the statement of proposition follows by expanding Are,111 = 11,411 - Li,t giving rise to the additional 1 inside the parentheses.
For the proof of part we notice that we may write
C1,++1 02,44
Σ
2is+1
Ij,+1
(6)
THTT
iELA.Ell
for all E we first study the individual differences 24,41 Ij,41 for i La and E 1B. Again, straightforward computation yields
Az A0j.e11
Σ
(wiee - w,,,,t)) Te,t +
Σ
(WiRk. -
w..k,e) - Thet
tESA
kEIn
16. 71) +
Σ
(at - 7e)
AREELA
+ (7/e -60) +
Σ (7: - Be k
j#kEIn
(6: (214 I.j,))
+ Σ (a: v1.
Σ
(3, - (8.-7)akk
jKKEI
and substitution into G together with expansion of Ar; allows to write
c1,+11 2, =(1 + 6,
7.)(1 c2,1)
Σ
Σ
(ac-n)0Er
E
(Be-
iET
j#kEIB
Let us investigate the double sum here. Each term involving Fte for E E TA occurs m(n - 1) times since for any fixed j E [B. among the outer terms involving LA, happens exactly once that there is no term involving zt,,. Similarly for the terms involving Th, for k LB, which each occur nmm times. Hence the double sum equals
m(n () 7:)
Σ -i,t n 1)(3: - 7t) Σ Kj.t
iETA
jeIn
Accounting for the factor 1 and reinserting the definition of C1,² and C2 we arrive at
61,1+1 - 2, = (1+ 8, (n 1)a, n)) Cı,t (1 + + (mn 1)3, - n7)) 02
To finalize the proof make of earlier observation from (5) that allows recognize that the coefficients for C1 and C2 in the last line are in fact equal (up to sign) and have the values #(2 - (n + m))))
The proposition above does not yet include one of the assumptions that were outlined in the informal statement, namely that the weights within either cluster are larger than the weights between clusters, i.c. " min(ar, 3.}. Adding this assumption to the formalism leads to the following corollary.
Corollary 1. For any t E N, if of > holds, then at time the diameter of {z : LA} expands slower rate than the rate which the centroids CA. and CB. are pushed apart. Moreover, the same statement holds when replacing aa by 3r and I by Ig.
Proof. We will only give the proof for the former statement. The proof of the latter statement is identical after performing the symbolic replacement indicated.
14

---

Under review as a conference paper at ICLR 2021
The rates mentioned in the corollary are dt aq and 2 (n + myy respectively. Their ratio equals
+ 6, at
2 na; mi
(n m)a 2 nt m/7
which is evidently smaller than in case a holds. Moreover, both rates are strictly lower bounded by the respective diameters grow and so does the separation between the cluster
centroids.
L
discussion on the practical applicability of these results is in order. While the setup of Proposi- tion [2 and Corollary is artificial in its specifics, these statements still relevant for real-world phenomena. The results of these statements remain approximately true if the individual weights are independently perturbed by small amount, so situation close to the one studied here follows the same behaviour.
A.2 THE USE OF SKIP- CXIP-CONNECTIONS
As noted in Section 5 the skip-connections serve a specific purpose in the Set Transformer archi- tecture, which discuss in little more detail here. We will focus specifically their use in the proofs of Proposition and Corollary
Without skip-connections, equation becomes
E
jELaUIn
and the statement of Proposition would be modified. The multiplication factors 1 + 6, ar and 1+6,--8 33 from the first and second statements and 22(n++m) from the third statement would each decrease by This would mean that these factors would fall into the interval (0, 1) and each encoder block would operate in contractive way. While the result of Corollary would remain morally correct each cluster would contract faster than the rate at which the cluster centroids would come together- this would complicate training a network containing multiple stacked encoder blocks.
B MORE DETAILS ON THE SAMPLING PROCEDURE
Given a classification dataset containing collection of examples with corresponding class labels, we briefly outline a general procedure synthesize an ABC-ready dataset. single input instance is independently generated using the procedure outlined in Algorithm
Algorithm 1: Generating a cluster instance from a classification dataset
input desired length of output sequence L
constraint: number of classes C, number of available examples per class b by output length L sequence of examples, kernel matrix of size L, number of clusters present
Initialize 0 1-11 Pick & + uniform (1, min (C
Pick per cluster frequencies "1, ny with n, S b, and Σt_ 74
for i 1
1--10 to k do
Pick class not yet chosen uniformly random
append n; uniform examples of chosen class to O
Let A +- true kernel matrix corresponding to return A,
15

---

Under review as a conference paper at ICLR 2021
C MORE DETAILS ON EXPERIMENTS
C.I DETAILS OF EXPERIMENTAL SETUP
The results discussed Section G on Omniglot, Embedded ImageNet, and CIFAR-I00 are produced with the following hyperparameters: the embedding component uses two Self Attention Blocks (SAB), each with four heads. The dimensionality of keys, queries, and values set 128. The learning rate is set to 0.0001 except for Embedded ImageNet, where it is factor 10 larger. We found that using larger batch sizes of up to 128 tends to improve training. Each these settings was found by tuning the Omniglot experiment and subsequently copied over for the other experiments. No further hyperparameter search was done for CIFAR-100 nor for Embedded ImageNet, except the learning rate for the latter to speed up training.
We used a few data augmentation techniques for Omniglot and for CIFAR- 100. For Omniglot, we invert and downscale all images from the original 105 105 to 28 28. Additionally, perform class expansion on the training set as in Vinyals et al. (2016) and apply random rotations between 115% For CIFAR-100
the same augmentations in Han (2019).
C.2 NORMALIZED MUTUAL INFORMATION PER ALPIIBET
In Table we show more details on Omniglot testing results, split out per alphabet.
Table 5: Average NMI scores for 1000 random instances, each of size 100, for each alphabet in the evaluation set. The number clusters varies uniformly up to maximum available for each alphabet, which is 47 for Malayalam. 'Mul' refers multiplicative attention, while 'Add' means ABC with additive attention.
5, 47 (unknown)
1: E
5, 47 (known)
(known)
Alphabet
Mul
Add
Mul
Add
Mul
Add
Angelic
0.8944
0.8566
0.8977
0.8757
0.8593
0.8435
Atemayar Qelisayer
0,8399
0.8003
0.8761
0.8570
0.8692
0,8315
Atlantean
0.9182
0.8927
0.9272
0.9188
0.9104
0.8994
Aurek-Besh
0.9371
0.9247
0.9444
0.9312
0.9367
0.9247
Avesta
0.901
0.8728
0.9067
0.8956
0.8939
0.8733
Ge.ez
0.8877
0.8833
0.8931
0.8943
0.8725
0.8864
Glagolitic
0.9046
0.8366
0.9186
0.8965
0.9158
0.8943
Gurmukhi
0.8685
0.7999
0.8949
0.8668
0.9018
0.8674
Kannada
0.8120
0.6837
0.8545
0.8267
0.8648
0.8225
Keble
0.8671
0.8195
0.8921
0.8623
0.9042
0.8291
Malayalam
0.8810
0.8494
0.8963
0.8869
0.8909
0.8854
Manipuri
0.9035
0.8637
0.9152
0.8948
0.9039
0.8918
Mongolian
0.9200
0.8879
0,9277
0.9143
0.9176
0,9020
Old wwwurrchSlavooic...m (Cyrili
0.9358
0.9336
0.9419
0.9425
0.9302
0.9372
Oriya
0.8008
0.6734
0.8460
0.8019
0.8466
0.7912
Sylheti
0.7725
0.6414
0.8220
0.7923
0.8151
0.7708
Syriac.(Serto)
0.8909
0.8381
0.8946
0.8762
0.8794
0.8535
Tengwar
0.8758
0.8359
0.8872
0.8697
0.8571
0.8524
Tibetan
0.8840
0.8694
0.8996
0.8961
0.8982
0.8935
ULOG
0.7895
0,5621
0.8185
0.7656
0.8132
0.7544
mean
0.8742
0.8163
0.8927
0.8733
0.8840
0.8602
16


Reviews:
[{"review_id": "TB56MT9o_Du", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a method for producing representations for clustering that take into account global trends in the dataset, rather than considering each pair of instances in isolation. They claim to achieve competitive clustering performance on omniglot, which they attribute to the use of these contextualised embeddings. They also present a theoretical justification for using transformers in metric learning\n\n## Strengths\n* The need to make use of context is well motivated, and the authors show that their method does make use of context effectively.\n* Both the algorithmic and theoretical work described by the paper appear to be technically correct.\n\n## Weaknesses\n* Important details pertaining to both the proposed architecture and experimental evaluation are missing (see questions below).\n* The novelty seems limited, given that Lee et al. (2019a, 2019b) have already proposed using a set transformer to compute contextualised embeddings for clustering.\n* While technically correct, it is unclear to me how the theoretical analysis directly relates to the SAB components used in the architecture. In particular, assuming all within cluster weights are equal to $\\alpha$ or $\\beta$, while all between cluster weights are equal to $\\gamma$ does not seem like a realistic model of an SAB module.\n* The experimental evaluation could be improved. Currently only one real-world dataset is used in the evaluation, which makes it hard to say whether the findings will generalise to other situations.\n* The way the experiments on omniglot are set up does not match the motivation for the method. In particular, one would expect context to be useful when elements from different clusters can sometimes look very similar (e.g., letters from different alphabets that resemble each other). However, the omniglot experiments consider each alphabet in isolation, so this impies that context will be useful when individual letters in the same alphabet can sometimes look similar.\n\n## Questions\n* How does $\\mathcal{T}$ map from $\\mathbb{R}^{n \\times d_x}$ to $\\mathbb{R}^{n \\times d_z}$ when the input and output of each SAB is the same dimensionality? Does this mean $d_x = d_z$?\n* In the circles experiment, are multiple datasets (i.e., \"instances\") synthesised in order to train the embedding block?\n* It is said that the \"pairwise\" baseline, the embedding block is removed, but also that it is a metric learning method. What metric learning is going on here?\n* When would one expect additive attention to outperform multiplicative attention, and vice versa?\n\n## Other comments\n* Siamese networks were proposed by Bromley et al. (1994), not by Koch et al. (2015).\n\n## After Author Response\nMy concerns are only somewhat addressed by the authors' response. While the results on extra datasets are encouraging, I still think there is limited novelty in the proposed approach and some of the important details remain unclear. In particular, terminology seems to be used inconsistently, which results in ambiguity when describing variants of the model used in experiments.\n\nJane Bromley, et al. Signature verification using a \"siamese\" time delay neural network. NeurIPS, 1994.", "extra_scores": {}, "extra_text": {}}, {"review_id": "SjLQ0S-7LK", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": " Summary:\nThe hypothesis of this paper is that learning a contextual metric (allowing pairwise distances to depend on the data) can improves clustering, and is motivated by two examples (Omniglot, intersecting circles).  The paper proposes a new method - Attention based clustering (ABC) that incorporates context to learn a metric in the form of an embedding and kernel similarity layer (predefined). The embedding layer uses repeated self attention blocks (SABs) from the transformer architecture and is theoretically shown to make the clusters more condensed. An off-the-shelf clustering algorithm (e.g. spectral clustering) is used to cluster the similarity matrix (number of clusters pre-specified or inferred). The experiments show favorable results on the toy dataset and are competitive with methods that use a prespecified clustering.\n\nReasons for score:\nThe paper proposes a novel combination of approaches to improve clustering using a supervised learning method. Given that ABC’s results are surpassed for the Omniglot task by methods leveraging context for clustering, it would help to have a real world task where the approach taken (learning the similarity metric followed by off the shelf clustering) is the best.  This would help better motivate the proposed approach compared to previous approaches in the literature. It would also help to have further experiments on other datasets to increase the range of validity of the experiments.\n\nOther suggestions:\nIt could be interesting to visualize (say with T-SNE) what the geometry of the embeddings layer of the intersecting circles looks like. Further insight (theoretical or experimental) on the choice of kernel and/or other kernels would also be valuable.\n\nMinor:\nPerhaps displaying plots from the eigengap method of inference to validate that the inferred gap (number of clusters) is significant.\n\nClarity:\nSome details for the other methods compared to in the experiments would be helpful. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "N0gV_VaEmEY", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes Attention-Based Clustering (ABC) that learns latent representations to adapt to context within an input set. They use ideas from the metric learning literature and the Siamese network on how to learn compatibility scores, and the transformer architecture and the Set Transformer on how to use context to make decisions.\n\nThe paper is well written and considers using the context in clustering which is an important problem however the proposed solution is not new. \n\n1- Transformer already being used as the Set Transformer to improve clustering (Lee et al., 2019b).  \n2- Also they mentioned that their model uses context to output pairwise similarities between the data points in the input set. They use the ground-truth labels and they train ABC in a supervised manner using those labels which is not realistic in clustering tasks!! \n3- The paper also claims that the ABC model is agnostic to the number of clusters. The known eigengap method (von Luxburg, 2007) is used to find the number of clusters.\n4- The paper only shows the result on OMNIGLOT and Olympic circles problems. Clustering is a very old problem and there are  known datasets from different domains to evaluate a new approach. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EYy4Lui4M11", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a metric learning and clustering method based on the idea of learning the metric from the context. They use the self-attention block module of the multi-head attention based transformer to embed the data and learn a kernel using the ground truth labels.  \nThey demonstrate their idea on a toy dataset and present results on the Omniglot dataset. \nAlthough their results look reasonable, I am concerned that the idea seems very incremental and simply uses a combination of techniques that have been proposed in the literature. It is unclear to me what the authors' primary contribution is to the field of metric learning \nThe following are my other main concerns with this paper: \n1. It is unclear if the proposed ABC method uses all the ground truth labels of the dataset to train the similarity kernel. If so, this would make their method highly impractical. Why would one cluster data using a method which requires it to have all the cluster labels in advance? In the Introduction the author say \" We use ground truth labels, only in the form of pairwise constraints, to train a similarity kernel, making our approach an example of constrained clustering.\" Constrained clustering techniques are semi-supervised and do not require all of the data set to be labeled.  The authors need to clarify and further discuss this point.\n2. In Section 5.1 the authors do not cite or mention what pairwise metric learning method was used. Was any hyperparameter tuning or other optimizations done for this method? It is very surprising that a clustering done after learning a metric performs worse than out-of-the-box spectral clustering.\n3. The authors demonstrate their results only on one real data set and there is no clear discussion of the results. They need to provide more details on why they chose the three tasks (variable number of clusters known and unknown and fixed number of clusters). If the training is independent of the task then why do they observe a slightly different NMI for the three tasks? Wouldnt the same kernel be learnt for all the tasks and thereby the same number of clusters chosen as specified in Section 3.4? There is a need for clarity in the description of the experimental setup and results. I would also recommend adding a few more data sets to the results. \n4. The description of the Ominiglot data set can be improved. For instance, they use the words alphabet and language interchangeably. The Omniglot data set only refers to alphabets and the authors should be consistent. \n5. Why are different metrics used for the two data sets (Rand Index and NMI)? \n\nIn summary, I believe this idea is incremental and possibly has some potential, but the authors have not done justice to it in this paper. There are a lot of unclear aspects that need to be better explained. \n\n\n\nReview update after rebuttal: The authors have addressed some of my concerns in the rebuttal and the modified version of the paper. They have added results on more real datasets and explained some aspects that were unclear in the first version. However, I am still not convinced that this is a comprehensive enough contribution as it is right now. The results on the new datasets have, in fact, raised more questions. Their proposed method seems to perform worse than the baselines in some scenarios. Though this is not bad and it is important to show negative results, I did not see any discussion or insights into the poor performance. I would recommend the authors run some baselines themselves and compare rather than copying the results from the baseline papers. This would ensure that the experimental setup and environment are similar leading to a fairer comparison, and possibly some insight into their methods' performance. In summary, I still believe that this is an idea with potential but the authors still have ways to go in putting their idea clearly on paper and justifying it completely and comprehensively. I am sticking to the score I had assigned before. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to use context-based metric learning, where an attention/Transformer-based mechanism is used to incorporate neighborhood information for deep learning-based metric learning. This was initially demonstrated on two simpler datasets, although larger ones were added during the rebuttal. On the whole, reviewers appreciated the simplicity and intuition behind the idea, but the consensus among all of the reviewers found several aspects lacking, including: 1) clarity of the descriptions in the paper, 2) novelty compared to existing work, especially that of Set Transformer for clustering, 3) lack of convincing results compared to baselines, or at least analysis/justification for negative results. While the reviewers appreciated the authors' rebuttal and experiments, it did not address many of these concerns. The idea is interesting and seems to hold some promise, so the authors are encouraged to refine these aspects in order to fully explore this idea and submit to a future venue. 
Decision: Reject