End-to-end Differentiable Clustering with Associative Memories

Bishwajit Saha 1 Dmitry Krotov 2 Mohammed J. Zaki 1 Parikshit Ram 2 3

Abstract

ing, which combines representation learning and clustering
while utilizing continuous relaxation of the discrete assignment problem (Ren et al., 2022; Zhou et al., 2022). However,This relaxation replaces the discrete assignment with partial
cluster assignments, which violates a fundamental premiseof clustering – each point belongs to only one cluster. Additionally, to the best of our knowledge, there is currently no
differentiable clustering scheme that can seamlessly leverage the stochastic gradient descent or SGD (Nemirovski
et al., 2009) based optimization frameworks (Duchi et al.,2011; Kingma & Ba, 2014) for unconstrained optimization
while preserving the discrete nature of clustering. We believe that the problem of clustering can benefit from utilizing
SGD based solutions and to that end, we look for ideas in avery distant field of associative memories.

Clustering is a widely used unsupervised learning technique involving an intensive discrete optimization problem. Associative Memory models
or AMs are differentiable neural networks defining a recursive dynamical system, which havebeen integrated with various deep learning architectures. We uncover a novel connection between
the AM dynamics and the inherent discrete assignment necessary in clustering to propose a novel
unconstrained continuous relaxation of the discrete clustering problem, enabling end-to-end differentiable clustering with AM, dubbed ClAM.
Leveraging the pattern completion ability of AMs,
we further develop a novel self-supervised clustering loss. Our evaluations on varied datasets
demonstrate that ClAM benefits from the selfsupervision, and significantly improves upon boththe traditional Lloyd’s k-means algorithm, andmore recent continuous clustering relaxations (byupto 60% in terms of the Silhouette Coefficient).

Recently, traditional associative memory or AM models (Hopfield, 1982; 1984) have been reformulated to significantly increase their memory storage capacity and integrated
with modern deep learning techniques (Krotov & Hopfield,
2016; Ramsauer et al., 2020; Krotov & Hopfield, 2021;
Krotov, 2021; 2023). These novel models, called Dense
Associative Memories, are fully differentiable systems capable of storing a large number of multi-dimensional vectors,
called patterns or “memories”, in their synaptic weights. We
believe that this ability to learn synaptic weights of the AM
in an end-to-end differentiable manner together with the discrete assignment (association) of each data point to exactly
one memory makes AM uniquely suited for the task of differentiable clustering. Specifically, we make the following
contributions:

1. Introduction
Clustering is a fundamental unsupervised technique used toanalyze and organize large amounts of data based on theirsimilarities. Various formulations and algorithms have beenstudied to identify an efficient clustering of the data. Amongthem k-means (MacQueen, 1967), Spectral Clustering (Donath & Hoffman, 1973), Hierarchical Clustering (Johnson,1967), Density-based Clustering (Ester et al., 1996), andExpectation Maximization (Dempster et al., 1977) havebeen widely used. However, these formulations are computationally expensive involving an intensive combinatorial
task due to their discrete nature and lack of differentiability:
for example, exact k-means is NP-hard (Dasgupta, 2008),
though approximations can be efficient. To address thislimitation, recent approaches have focused on deep cluster-▶ We develop a flexible mathematical framework forclustering with AM or ClAM, which is a novel continuous unconstrained relaxation of the discrete optimization problem of clustering that allows for clustering in an
end-to-end differentiable manner while maintaining
the discrete cluster assignment throughout the training,with linear time cluster assignment.
▶ We leverage the pattern completion capabilities of AMs
to develop a differentiable self-supervised loss that
improves the clustering quality.
▶ We empirically demonstrate that ClAM is able to consistently improve upon k-means by upto 60%, while being
competitive to spectral and agglomerative clustering, andproducing insightful interpretations.

1
CS Department, Rensselaer Polytechnic Institute, Troy, NY,
USA 2 MIT-IBM Watson AI Lab, IBM Research, Cambridge, MA,
USA 3 IBM Research, Yorktown Heights, NY, USA. Correspondence to: Bishwajit Saha <sahab@rpi.edu>.

Published at the Differentiable Almost Everything Workshop of the
40 th International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s).

1End-to-end Differentiable Clustering with Associative Memories

This serves as an initial state of the AM network v 0 ← ṽ.
The AM dynamics is defined by the learnable weightsρµ , µ = 1, . . . , M , which also correspond to the fixed
points of the dynamics (memories). The network evolves
in time for T recursions according to equation 4, where T
is chosen to ensure sufficient convergence to a fixed point.
The final state v T is compared with the uncorrupted v todefine the loss functionXL=∥v − v T ∥2 , where v 0 ← ṽ(5)

2. Associative Memories for Clustering
In this section, we present (i) the mathematical framework
for ClAM, (ii) motivate its suitability for clustering, and(iii) present a way of learning the memories for clustering.
2.1. Associative memories: Mathematical Framework
In a d-dimensional Euclidean space, consider M memoriesρµ ∈ Rd , µ ∈ [M ] ≜ {1, . . . , M } (we will discuss later
how the memories are learned). The critical aspects of thismathematical framework are the energy function and theattractor dynamics (Krotov & Hopfield, 2021; Millidge
et al., 2022). A suitable energy for clustering should be
a continuous function of a point (or a particle) v ∈ Rd .
Additionally, the energy should have M local minima, corresponding to each memory. Finally, as a particle progressively approaches a memory, its energy should be primarily
determined by that single memory, while the contribution of
the remaining M − 1 memories should be small. An energyfunction satisfying these requirements is given byX
12
exp(−β∥ρµ − v∥ )(1)
E(v) = − logµ∈[M ]
βv∈Swhich is minimized with backpropagation through time withrespect to the AM parameters ρµ .
2.2. AM as a differentiable discrete arg min solver
Consider the original k-means objective with a dataset S ⊂Rd , where we learn k prototypes R ≜ {ρµ , µ ∈ [k]} with[k] ≜ {1, . . . , k} by solving the following problem:X∥x − ρµ⋆x ∥2 , s.t. µ⋆x = arg min ∥x − ρµ ∥2 (6)minR

The discrete selection of µ⋆x (for each x) makes equation 6
a combinatorial optimization problem that cannot directly
be solved via (stochastic) gradient descent. A common
continuous relaxation of this problem is as follows:XXwµ (x) ∥x − ρµ ∥2(7)minwith a scalar β > 0 interpreted as an inverse “temperature”.
As β grows, the exp(·) in equation 1 ensures that only theleading term remains significant, while the remaining M − 1
terms are suppressed. The energy function, in this limit, isrepresented by a parabola centered on the nearest memory,
dividing the space into M basins of attraction. The attractor dynamics control how v moves in the space over time,
via dv/dt, while ensuring that energy decreases. That is
dE(v)/dt < 0, which ensures that a particle convergences
to a local minimum. The particle dynamics is described bygradient descent on the energy landscape:τRµ∈[M ]

where τ > 0 is a characteristic time constant, describing
how quickly the particle moves on the energy landscape,and σ(·) is the softmax function over the scaled distances
to the memories. This is guaranteed to reduce the energy
2 (c)

≤0

µ∈[k]

We propose a novel alternative continuous relaxation to
the discrete k-means problem leveraging the AM dynamics(§2.1) that preserves the discrete assignment in the k-means
objective. Given the prototypes (memories) R = {ρµ , µ ∈[k]}, the dynamics (equation 2) and the updates (equation 4)
ensure that any example (particle) x ∈ Rd will converge toexactly one of the prototypes ρµbx corresponding to a single
basin of attraction. Furthermore, for appropriate β, µbxmatches the discrete assignment µ⋆x in the k-means objective(equation 6). This implies that, for appropriately set β and T ,xT ≈ ρµ⋆x , allowing us to replace the desired per-example(3)

where (a) is the chain rule, (b) follows from equation 2, andthe equality in (c) implying local stationarity. A valid updateδ t+1 for the point v from state v t to v t+1 = v t + δ t+1 at a
discrete time-step t + 1 is via finite differences:δ t+1 =x∈S

P
where (usually) wµ (x) ∈ [0, 1] andµ∈[k] wµ (x) =1 ∀x ∈ S. Hence, these weights {wµ (x), µ ∈ [k]} define aprobability over the k prototypes, and are designed to put
the most weight on the closest prototype ρµ⋆x , and as small
a weight as possible on the remaining prototypes. Other
weighting functions have been developed with similar properties (Xie et al., 2016), and essentially utilize a weighted
sum of distances to the learned prototypes, resulting in something different in essence to the discrete assignment µ⋆x in
the original problem (equation 6). Another subtle point isthat this soft weighted assignment of any x ∈ S acrossall prototypes at training time does not match the hardcluster assignment to the nearest prototype at inference,
introducing an incongruity between training and inference.

Xdv
1= − ∇v E =(ρµ −v) σ(−β∥ρµ −v∥2 ) (2)dt
2dE(v) (a)dv (b)dv= ∇v E(v) ·
= −2τ
dt
dt
dt

µ∈[k]

x∈S

dt X
(ρµ − v t ) σ(−β∥ρµ − v t ∥2 ) (4)µ∈[M ]τGiven a dataset of points S, for each point v ∈ S one cancorrupt it with some noise to produce a distorted point ṽ.
2

End-to-end Differentiable Clustering with Associative Memories
Self-supervised
loss Lx0 ← m ⊙ x

m
x1
R
x2
R
t
xR

ρ1

∇R L
AM recursion

ρ3

xT
R

Updatedprototypes R
ρ2xters for each dataset are selected based on its number ofunderlying classes (the class information is not involvedin clustering or hyperparameter selection). See details inAppendix A.1. First, we compare ClAM with establishedschemes, k-means (Lloyd, 1982), spectral & agglomerative
clustering, and to DEC (Xie et al., 2016) and DCEC (Guoet al., 2017) (for 3 image sets since DCEC uses CAE). Then
we ablate the effect of self-supervision in ClAM. Qualitatively, we visualize memory evolution through the learning.

R = {ρ1 , ρ2 , ρ3 }For implementation, we use Tensorflow (Abadi et al., 2016)
for ClAM and scikit-learn (Pedregosa et al., 2011) forthe clustering baselines and quality metrics. DCEC/DEC
seed the optimization with the prototypes from the Lloyd’ssolution; we also consider a randomly seeded DECr . Further details are in Appendix A.3. We perform an elaborate hyperparameter search for all methods and utilize
the configuration for each method corresponding to thebest Silhouette Coefficient (SC) (Rousseeuw, 1987) oneach dataset. The code is available at https://github.
com/bsaha205/clam.

Figure 1: ClAM Algorithm. For x ∈ S, we first apply
a mask (in purple) m to x to get the initial iterate x0 for
the AM recursion. With T recursions, we have a completed
version xTR . The prototypes R are updated with the gradient∇R L on the self-supervised loss L (equation 9).
loss ∥x − ρµ⋆x ∥2 in the k-means objective (equation 6) with∥x − xT ∥2 , allowing us to rewrite k-means (equation 6) as
the following continuous optimization problem:X2(8)x − xTR , where x0 ← x
min
R

x∈S

Q1: How does ClAM compare against baselines? We
present the best SC obtained by all schemes in Table 1.
ClAM consistently improves over k-means across all 10
datasets (up to 60%), and outperforms both versions ofDEC, highlighting the advantage of the novel relaxation.
Furthermore, Lloyd’s seeding is critical in DEC – DECrdoes worse than base k-means (via Lloyd (1982)) in allcases – while ClAM performs well with random seeding.
ClAM even improves upon DCEC, which uses rich image
representations from a CAE. Overall, ClAM performs beston 5/10 datasets, showing significant improvements overeven spectral and agglomerative clustering (these are notprototype-based, and hence can be more expressive). On theremaining datasets, both spectral and agglomerative clustering show improvements over ClAM. To understand thisbetter, we also compare the clusters generated by the different methods to the ground-truth class structure in each of
the datasets.The Normalized Mutual Information (NMI) &Adjusted Rand Index (ARI) (Hubert & Arabie, 1985) scores(Vinh et al., 2009) are shown in Table 3 from Appendix.
The results indicate that the datasets on which spectral andagglomerative clustering have a significantly higher SC than
k-means and ClAM (GCM, USPS, CTG, Segment), theircorresponding NMI & ARI scores are significantly lower(see underlined entries in Table 3 from Appendix), indicating clusters that are misaligned with the ground-truth labels.
Upon further investigation, we see that both spectral andagglomerative clustering end up with a single large cluster,and many really small (even singleton) ones, indicating thatthe clustering is overly influenced by geometric outliers.

where xTR is obtained by applying update in equation 4 toany x ∈ S through T recursion steps.
This is a significantly different relaxation of the k-means
objective compared to the existing “weighted-sum” approaches. The tightness of this relaxation relies on the
choices of β (inverse temperature) and T (the recursion
depth) – we treat them as hyperparameters and select themin a data-dependent manner. See Appendix B.1 to understand the partitions induced by AMs.
2.3. ClAM: Clustering with AMs and self-supervision
The AM framework allows for a novel end-to-end differentiable unconstrained continuous relaxation (equation 8)of the discrete k-means problem leveraging the strong pattern completion abilities of AMs. We use standard maskingfrom self-supervised learning – we apply a (random) maskm ∈ {0, 1}d to a point x ∈ S ⊂ Rd and utilize the AMrecursion to complete the partial pattern x0 = m ⊙ x andutilize the distortion between the ground-truth masked value
and completed pattern as our loss as follows. Given a mask
distribution M and denoting m̄ as the complement of m:
X
L=Em∼M ∥m̄⊙(x−xTR )∥2 , x0 ← m⊙x, (9)x∈S

where xTR evolves from x0 with T recursions of equation 4.
Prototypes R are learned by minimizing the self-supervised
pattern completion loss (equation 9) via SGD.

3. Empirical evaluation

Q2: How beneficial is self-supervision in ClAM? In ClAM,
we use the pattern completion ability of AMs, and optimize

We evaluate ClAM on 10 datasets of varying sizes – 716000 features, 101-60000 points. The number of clus3

End-to-end Differentiable Clustering with Associative Memories

Table 1: Silhoutte Coefficient (SC) obtained by ClAM, its variants and baselines (higher is better). ▲(▼) show theperformance gain (drop) by ClAM, given by (a−b)/b × 100% where a is the SC for ClAM, and b is the SC for the baseline;
positive (negative) values indicate performance gain (drop). The best performance for a dataset is in boldface. W/L denote
Wins/Losses. Note ablations ClAM w/ (8) is ClAM without self-supervision.
DECr

Datasetk-means

SpectralZoo
Ecoli
MovLibYale
USPS
Segment
FMNIST
GCM
MicePE
CTG

▲10%

0.374
0.262▲26%0.252▲3%0.117▲10%0.135▲1%0.357▲35%0.126▲10%0.118▲62%0.128▲56%0.161▲53%

▲3%

0.398
0.381▼13%
0.247▲5%0.120▲8%0.228▼40%
0.702▼31%
0.075▲84%0.205▼7%
0.156▲28%0.449▼45%

0.398
0.404▼18%
0.247▲5%0.114▲13%0.231▼41%
0.697▼31%
0.096▲44%0.288▼34%
0.193▲4%0.387▼36%———
0.089▲45%0.119▲14%—0.121▲14%
—
—
—

0.374
0.262▲26%0.258▲1%0.123▲5%0.135▲1%0.357▲35%0.129▲7%0.115▲66%0.137▲46%0.164▲50%

ClAM W/L

10/0

5/5

5/5

3/0

10/0

Agglo
▲3%

DCEC

DEC
▲10%

ClAM

w/ (8)

0.367
0.255▲30%
0.184▲41%0.088▲47%0.108▲26%0.287▲68%0.070▲97%0.054▲254%
0.115▲74%0.130▲89%

0.412
0.331
0.260
0.129
0.136
0.483
0.138
0.191
0.201
0.246

0.382
0.301
0.248
0.121
0.127
0.357
0.131
0.142
0.126
0.147

10/0

—

10/0

▲12%

of fashion items into 10 clusters, and visualize the evolutionof the 10 memories in figure 2. Each sub-figure in figure 2
corresponds to a particular epoch during the training, andshows all 10 memories stacked vertically. We can see that at
epoch 0 (figure 2a) the memories are initialized with random
values, but gradually reveal discernible patterns by epoch 10(Figure 2c) and further sharpen by epoch 50 (figure 2e). By
epoch 100 (figure 2f), the shapes have stabilized althoughsome learning might still be happening. Some memories
evolve into individual forms (such as rows 3–pants, 4–shoes,
8–bags, 9–long-sleeve shirts and 10–boots), while others
evolve into mixtures of 2 forms (such as rows 1–pants andshoes, 6–pants and short-sleeve shirts, 7–shoes and longsleeve shirts). The remaining evolve into less distinguishable forms though we can still visualize some shapes (likein rows 2–long-sleeve shirts and 5–shoes).

4. Limitations and Future Work(a) n0(b) n5In this paper, we present a novel continuous relaxation of
the discrete prototype-based clustering problem leveraging
the AM dynamical system that allows us to solve the clustering problem with SGD based schemes. We show that thisrelaxation better matches the essence of the discrete clustering problem, and empirical results show that our ClAM approach significantly improves over standard prototype-based
clustering schemes, and existing continuous relaxations. We
note that ClAM is still a prototype-based clustering scheme,
hence inherits the limitations of prototype-based clustering.
Given the end-to-end differentiable nature of ClAM, we will
extend it to clustering with kernel similarity functions and
Mahanalobis distances, and to deep clustering where we also
learn a latent space. We plan to explore new energy functions and update dynamics that enable spectral clustering.
Finally, given ClAM’s flexibility, we want to automaticallyestimate the number of clusters on a per-dataset basis, much
like Pelleg & Moore (2000) and Hamerly & Elkan (2003).

(c) n10 (d) n20 (e) n50 (f) n100

Figure 2: Evolution of ClAM prototypes. We visualize the prototypes at the nth training epoch for n =0, 5, 10, 20, 50, 100 (with T = 10). The images pixels arecolored as red for positive, white for zero and blue for negative values, with their intensity denoting magnitude.
for the self-supervised loss (equation 9). Here, we ablate theeffect of this choice – we utilize a version of ClAM that does
not use any masking and learns memories by minimizing
the loss in equation 8. Table 1 (ClAM and ClAM w/ (8)columns) show their SC, highlighting the positive effect ofself-supervision, with around 10% gain in all cases.
Q3: How to interpret ClAM? An interesting aspect of AMs
is the prototype-based representation of memories (Krotov& Hopfield, 2016). We study this for ClAM with the FashionMNIST images. We use ClAM to partition the 60k images
4End-to-end Differentiable Clustering with Associative Memories

Acknowledgements

Hopfield, J. J. Neural networks and physical systems withemergent collective computational abilities. Proceedingsof the national academy of sciences, 79(8):2554–2558,
1982.

This work was supported by the Rensselaer-IBM AI Research Collaboration (http://airc.rpi.edu), a partof the IBM AI Horizons Network. The work was done
during Bishwajit Saha’s externship at MIT-IBM Watson AI
Lab, IBM Research.

Hopfield, J. J. Neurons with graded response have collective
computational properties like those of two-state neurons.
Proceedings of the national academy of sciences, 81(10):3088–3092, 1984.

References
Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A.,
Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard,M., et al. {TensorFlow}: a system for {Large-Scale}machine learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16), pp.
265–283, 2016.

Hubert, L. and Arabie, P. Comparing partitions. Journal ofclassification, 2(1):193–218, 1985.

Aurenhammer, F. Voronoi diagrams – a survey of a fundamental geometric data structure. ACM Computing Surveys(CSUR), 23(3):345–405, 1991.

Johnson, S. C. Hierarchical clustering schemes. Psychometrika, 32(3):241–254, 1967.

Hull, J. J. A database for handwritten text recognition
research. IEEE Transactions on pattern analysis andmachine intelligence, 16(5):550–554, 1994.

Kingma, D. P. and Ba, J. Adam: A method for stochastic
optimization. arXiv preprint arXiv:1412.6980, 2014.

Chakraborty, S., Paul, D., and Das, S. Automated clusteringof high-dimensional data with a feature weighted mean
shift algorithm. In Proceedings of the AAAI Conferenceon Artificial Intelligence, pp. 6930–6938, 2021.

Krotov, D. Hierarchical associative memory. arXiv preprint
arXiv:2107.06446, 2021.

Dasgupta, S. The hardness of k-means clustering. Department of Computer Science and Engineering, Universityof California . . . , 2008.

Krotov, D. A new frontier for hopfield networks. Nature
Reviews Physics, pp. 1–2, 2023.
Krotov, D. and Hopfield, J. J. Dense associative memory
for pattern recognition. Advances in neural information
processing systems, 29, 2016.

Dempster, A. P., Laird, N. M., and Rubin, D. B. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B(Methodological), 39(1):1–22, 1977.

Krotov, D. and Hopfield, J. J. Large associative memory
problem in neurobiology and machine learning. In International Conference on Learning Representations, 2021.

Donath, W. E. and Hoffman, A. J. Lower bounds for thepartitioning of graphs. IBM Journal of Research andDevelopment, 17(5):420–425, 1973. doi: 10.1147/rd.175.
0420.

Li, J., Cheng, K., Wang, S., Morstatter, F., Trevino, R. P.,
Tang, J., and Liu, H. Feature selection: A data perspective.
ACM computing surveys (CSUR), 50(6):1–45, 2017.

Duchi, J., Hazan, E., and Singer, Y. Adaptive subgradientmethods for online learning and stochastic optimization.
Journal of machine learning research, 12(7), 2011.

Lloyd, S. Least squares quantization in pcm. IEEE transactions on information theory, 28(2):129–137, 1982.

Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. A densitybased algorithm for discovering clusters in large spatial
databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data
Mining, pp. 226–231, 1996.

MacQueen, J. Classification and analysis of multivariate
observations. In 5th Berkeley Symp. Math. Statist. Probability, pp. 281–297, 1967.
Millidge, B., Salvatori, T., Song, Y., Lukasiewicz, T., andBogacz, R. Universal hopfield networks: A general framework for single-shot associative memory models. arXiv
preprint arXiv:2202.04557, 2022.

Guo, X., Liu, X., Zhu, E., and Yin, J. Deep clustering withconvolutional autoencoders. In International conferenceon neural information processing, pp. 373–382. Springer,
2017.

Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574–
1609, 2009.

Hamerly, G. and Elkan, C. Learning the k in k-means.
Advances in neural information processing systems, 16,
2003.
5

End-to-end Differentiable Clustering with Associative Memories

Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V.,
Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P.,
Weiss, R., Dubourg, V., et al. Scikit-learn: Machinelearning in python. the Journal of machine Learning
research, 12:2825–2830, 2011.
Pelleg, D. and Moore, A. W. X-means: Extending k-means
with efficient estimation of the number of clusters. In
ICML, volume 1, pp. 727–734, 2000.
Ramsauer, H., Schäfl, B., Lehner, J., Seidl, P., Widrich,
M., Adler, T., Gruber, L., Holzleitner, M., Pavlović, M.,
Sandve, G. K., et al. Hopfield networks is all you need.
arXiv preprint arXiv:2008.02217, 2020.
Ren, Y., Pu, J., Yang, Z., Xu, J., Li, G., Pu, X., Yu, P. S., andHe, L. Deep clustering: A comprehensive survey. arXiv
preprint arXiv:2210.04142, 2022.
Rousseeuw, P. J. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal ofcomputational and applied mathematics, 20:53–65, 1987.
Vinh, N. X., Epps, J., and Bailey, J. Information theoretic
measures for clusterings comparison: is a correction forchance necessary? In Proceedings of the 26th annualinternational conference on machine learning, pp. 1073–
1080, 2009.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: a
novel image dataset for benchmarking machine learningalgorithms. arXiv preprint arXiv:1708.07747, 2017.
Xie, J., Girshick, R., and Farhadi, A. Unsupervised deep
embedding for clustering analysis. In International conference on machine learning, pp. 478–487. PMLR, 2016.
Zhou, S., Xu, H., Zheng, Z., Chen, J., Bu, J., Wu, J., Wang,
X., Zhu, W., Ester, M., et al. A comprehensive survey
on deep clustering: Taxonomy, challenges, and future
directions. arXiv preprint arXiv:2206.07579, 2022.

6

End-to-end Differentiable Clustering with Associative Memories

A. Experimental Details
A.1. Dataset details
To evaluate ClAM, we conducted our experiments on ten standard benchmark data sets. The datasets are taken fromvarious sources such as Yale from ASU feature selection repository1 (Li et al., 2017), USPS from Kaggle2 (Hull, 1994),
Fashion-MNIST from Zalando3 (Xiao et al., 2017), GCM from Chakraborty et al. (2021) and the rest of the datasets fromthe UCI machine learning repository4 . The statistics of datasets used in our experiment are given in Table 2.

Table 2: Descriptions of various benchmark datasets, used in our experiments.
DatasetShort name

# Points# Features# Classes

Zoo
Yale
GCM
Ecoli
Movement Libras
Mice Protien Expression
USPS
CTG
Segment
Fashion MNIST

Zoo
Yale
GCM
Ecoli
MovLibMicePE
USPS
CTG
Segment
FMNIST

101
165
190
336
360
1080
2007
2126
2310
60000

16
1024
16063
7
90
77
256
21
19
784

7
15
14
8
15
8
10
10
7
10

A.2. Metrics usedTo evaluate the performance of ClAM, we use Silhouette Coefficient (SC) (Rousseeuw, 1987) as the unsupervised metric thatis used to measure the quality of clustering. The score is between −1 and 1; a value of 1 indicates perfect clustering while avalue of −1 indicates entirely incorrect clustering labels. A value of near 0 indicates that there exist overlapping clusters in
the partition. To observe which existing clustering scheme is ClAM most similar to, we use Normalized Mutual Information(NMI) (Vinh et al., 2009) & Adjusted Rand Index (ARI) (Hubert & Arabie, 1985) between the obtained partition by ClAM
and obtained partition by baselines. For NMI, a value of 1 indicates perfect clustering while a value of 0 indicates completely
wrong class labels. ARI scores range between −1 and 1 and the interpretation is same as SC. We also use the NMI & ARI
scores between the ground truth and the obtained partition from ClAM and the baselines to measure how they are aligned totrue clustering labels.
A.3. Implementation Details
We use Tensorflow (Abadi et al., 2016) numerical machine learning library to implement and evaluate our model. We train
ClAM on a single node with 1 NVIDIA Geforce RTX 3090 (24GB RAM), and 8-core 3.5GHz Intel Core-i9 CPUs (32GB
RAM). We train on the original data with masking where we utilize the distortion between the ground-truth masked value
and completed pattern from ClAM as the loss function to find the best model. In the forward pass, in each step, the feature
vector is updated in such a way so that gradually it moves toward one of the stored memories. In the backward path, thememories are learned to minimize the loss. Hyperparameters are tuned for each dataset to find the best result. For thebaseline schemes of k-means, spectral, and agglomerative, we use the implementation from scikit-learn (Pedregosa
et al., 2011) library and tune different hyperparameters to get the best results for each dataset. For DCEC (Guo et al.,2017), as it is based on convolutional autoencoders (CAE) and works with only image dataset, we evaluate on three image
datasets to compare with ClAM (we leverage their Tensorflow implementation5 ). For the soft-clustering part of DEC (Xieet al., 2016) (where they utilize KL divergence loss between predicted and target probability distribution), besides theirk-means-initialized cluster centers, we also employ random-initialized cluster centers (DECr ) to study how randomization
works in DEC soft clustering network.
1

http://featureselection.asu.edu/
https://www.kaggle.com/datasets/bistaumanga/usps-dataset
3
https://github.com/zalandoresearch/fashion-mnist
4https://archive.ics.uci.edu/ml/index.php
5
https://github.com/XifengGuo/DCEC
2

7

End-to-end Differentiable Clustering with Associative Memories

Table 3: NMI and ARI score comparison among ClAM and the baseline clustering schemes in terms of groundtruth (higher is better). The best performance for each dataset is in boldface. The underlined entries for Spectral andAgglomerative mark low NMI but high SC in Table 1.
DatasetMetrick-means

SpectralAgglomerative

DCEC

DEC

DECr

ClAM

Zoo

NMI
ARI

0.83300.73730.88910.86640.84290.9109N/A
N/A

0.83300.73730.79920.67550.94290.9642

Yale

NMI
ARI

0.60340.36440.57440.3226

0.67230.45670.54280.28170.54990.29200.50680.23980.64180.4230

GCM

NMI
ARI

0.43850.13080.1715-0.01190.1882-0.0071

N/A
N/A

0.42280.11880.39230.08800.4476
0.2492

Ecoli

NMI
ARI

0.63320.49970.66060.65050.71110.7261

N/A
N/A

0.63320.49970.57070.38930.66330.7027

Movement Libras

NMI
ARI

0.60440.32600.61180.3236

0.60860.3144

N/A
N/A

0.59590.31470.31470.22230.61420.3351

Mice Protien Exp

NMI
ARI

0.23730.12600.00560.00190.2596
0.1558N/A
N/A

0.28730.1756

0.29510.17960.31080.1652

USPS

NMI
ARI

0.53680.43040.0777-0.0033

0.01800.00020.69610.59070.53760.43060.45380.3226

0.55660.4537

CTG

NMI
ARI

0.35810.17800.03910.00600.04190.0078N/A
N/A

0.35070.1766

0.35870.18180.31540.1736

Segment

NMI
ARI

0.58460.46070.01020.00050.00850.0003

N/A
N/A

0.58530.46120.61020.50380.54890.4331FMNIST

NMI
ARI

0.5036
0.34610.64290.43070.00510.00050.59480.41130.50080.33690.33390.22790.51830.3665(a) β = 0.001(b) β = 0.1(c) β = 1(d) β = 10(e) β = 15(f) β = 20(g) β = 25(h) β = 30(i) β = 50(j) β = 100

Figure 3: Basins of attraction vs Voronoi partition for five clusters. Partitions induced by AM basins of attraction withgiven memories (black dots) for different β are shown by the colored regions (T =10). Dashed lines show the Voronoi
partition.

B. Additional Experimental Results
B.1. Understanding the partitions induced by AMs
An interpretation of the discrete assignment µ⋆x for each x ∈ S in the k-means objective (equation 6) is that the prototypes
R induce a Voronoi partition (Aurenhammer, 1991) of the whole input domain, and the examples x ∈ S are assigned to theprototype whose partition they lie in. Voronoi partitions have piecewise linear boundaries, with all points in a partition having
the same closest prototype. Given prototypes R, the AM dynamics induces a partition of the domain into non-overlapping8

End-to-end Differentiable Clustering with Associative Memories

basins of attraction. For an appropriately set β and T , the basins of attraction approximately match the Voronoi partition
induced by the prototypes. However, when β is not “large enough”, the cluster assignment happens in a more “collective”
manner, involving all prototypes, leading to non-Voronoi partitions. We visualize the basins of attraction for different β infigure 3, contrasting them to the Voronoi partition. For a small β (figure 3a), the basins do not match the Voronoi partition.
As β increases, the basins of attraction evolve to match the Voronoi partition (figure 3j). Furthermore, while the Voronoi
partition boundaries are piecewise linear, the AM basins of attraction can have nonlinear boundaries (see boundaries infigure 3e). As mentioned earlier, we treat β and T as hyperparameters, and select them in a data-dependent fashion, so that
the AM partition sufficiently matches the Voronoi one.

9