Generalized Clustering by Learning to Optimize Expected Normalized Cuts
Authors: Azade Nazi
Will Hang
Anna Goldie
Sujith Ravi
Azalia Mirhoseini
Venue:  (2020)
Keywords: Clustering
Normalized cuts
Generalizability

Abstract: We introduce a novel end-to-end approach for learning to cluster in the absence of labeled examples. Our clustering objective is based on optimizing normalized cuts, a criterion which measures both intra-cluster similarity as well as inter-cluster dissimilarity. We define a differentiable loss function equivalent to the expected normalized cuts. Unlike much of the work in unsupervised deep learning, our trained model directly outputs final cluster assignments, rather than embeddings that need further processing to be usable. Our approach generalizes to unseen datasets across a wide variety of domains, including text, and image. Specifically, we achieve state-of-the-art results on popular unsupervised clustering benchmarks (e.g., MNIST, Reuters, CIFAR-10, and CIFAR-100), outperforming the strongest baselines by up to 10.9%. Our generalization results are superior (by up to 21.9%) to the recent top-performing clustering approach with the ability to generalize.

Under review as a conference paper at ICLR 2020
GENERALIZED CLUSTERING BY LEARNING TO OPTIMIZE EXPECTED NORMALIZED CUTS
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce novel end-to-end approach for learning cluster in the absence of labeled examples. Our clustering objective is based on optimizing normalized cuts, criterion which measures both intra-cluster similarity as well as inter-cluster dissimilarity. We define a differentiable loss function equivalent to the expected normalized cuts. Unlike much of the work in unsupervised deep learning, trained model directly outputs final cluster assignments, rather than embeddings unseen
that need further processing be usable. Our approach generalizes datasets across a wide variety of domains, including text, and image. Specifically, we achieve ofate-of-the-arr results on popular unsupervised clustering benchmarks (e.g.. MNIST, Reuters, CIFAR-10, and CIFAR- 100),, outperforming the strongest baselines by up to 10.9%. Our generalization results are superior (by up to 21 21.9%) to the recent top- perfforrnni clustering approach with the ability to generalize.
INTRODUCTION
Clustering unlabeled data is an important problem from both scientific and practical perspective. As technology plays larger role in daily life, the volume of available data has exploded. However, labeling this data remains very costly and often requires domain expertise. Therefore, unsupervised clustering methods are one of the few viable approaches gain insight into the structure of these massive unlabeled datasets.
One of the most popular clustering methods is spectral clustering (Shi & Malik 2000 Ng et al. 2002, Von Luxburg, 2007). which first embeds the similarity of each pair of data points in the Laplacian's ' eigenspace and then uses k-means to generate clusters from it. Spectral clustering not only outperforms commonly used clustering methods, such as k-means (Von Luxburg 2007), but also allows us to directly minimize the pairwise distance between data points and solve for the optimal node embeddings analytically. Moreover, it is shown that the eigenvector of the normalized Laplacian matrix can be used to find the approximate solution to the well known normalized cuts problem (Ng al. 2002 Von Luxburg. 2007).
In this work, we introduce CNC, a framework for Clustering by learning to optimize expected Normalized Cuts. We show that by directly minimizing continuous relaxation of the normalized cuts problem, CNC enables end-to-end learning approach that outperforms top-performing clustering approaches. We demonstrate that our approach indeed can produce lower normalized cut values than the baseline methods such as SpectralNet, which consequently results in better clustering accuracy.
Let us motivate CNC through a simple example. In Figure D we want to cluster 6 images from CIFAR-10 dataset into two clusters. The affinity graph for these data points is shown in Figure Ia] (details of constructing such graph is discussed in Section (4.)). In this example, is obvious that the optimal clustering is the result of cutting the edge connecting the two triangles. Cutting this edge will result in the optimal value for the normalized cuts objective. In CNC, we define a new differentiable loss function equivalent to the expected normalized cuts objective. We train deep learning model to minimize the proposed loss in an unsupervised manner without the need for any labeled datasets. Our trained model directly returns the probabilities of belonging to each cluster (Figure l(b)). In this example, the optimal normalized cuts is 0.286 (Equation and as we can see, the CNC loss also converges to this value (Figure

---

Under review as a conference paper at ICLR 2020
(a)
cut 1 edge
(b)
(C)
1.29
Ciuster
Cluster diggnenn
1Cluster
.998
.96
.004
.003
0.75
DNC
.002
.004
.004
.996
.996
.997
Iteration
CNC Model
Optimal Normalized cuts #edge cuts =1 per cluster valume - 2+2+3 =7 1/7 + 1/7 0.286
Regpaens
Figure 1: Motivational example: (a) affinity graph of images from CIFAR-IO, the objective to cluster these images into two clusters. (b) CNC model is trained to minimize expected normalized cuts in an unsupervised manner without the need for any labeled data. For each data point, our model directly outputs the probabilities of belonging to each of the clusters. (c) The CNC loss converges to the optimal normalized cuts value. In Algorithm D we show how we can scale this approach through a batch processing technique large datasets.
We compare the performance of CNC to several seeriing-basedd clustering approaches (Spectral- Net (Shaham et al. 2018). DEC (Xie et al. 2016), DCN (Yang et al. 2017 ) VaDE (Jiang et al. 2017). DEPICT (Ghasedi Dizaji et al.) 2017). ,. IMSAT (Hu et al., 2017 and IIC (Ji et al. 2019)) on four datasets: MNIST, Reuters, CIFARIO, and CIFARIO0. Our results show up to 10.9% 9 im- provement over the baselines. Moreover, generalizing spectral embeddings unseen data points, saapleees (OOSE), is a non-trivial task (Bengio et al.) 2003 [Blkinn et al., 22066) Mendoza Quispe et al. (0166). Our results confirm that CNC generalizes to unseen data. Our generalization results are superior (by up to 21 21.9%) to SpectralNet (Shaham et al. 2018). the recent top- perfoffffrmn clustering approach with the ability to generalize.
task commonly referred to as out-of-sample extensioe
2
RELATED WORK
Recent deep learning approaches to clustering attempt to embed the input data into form that is amenable to clustering by k-means or Gaussian Mixture Models. (Yang al.) 2017 Xie al. 2016) focused on learning representations for clustering. To find the clustering ceistering-frendlyy latent representations and to better cluster the data, DCN (Yang et al., (017)) proposed a joint dimensionality reduction (DR) and K-means clustering approach in which DR is accomplished via learning deep neural network. DEC (Xie et al., 2016) simultaneously learns cluster assignment and the underlying feature representation by iteratively updating target distribution to sharpen cluster associations.
Several other approaches rely on a variational autoencoder that utilizes a Gaussian mixture prior (Jiang eet al.] 2017 Dilokthanakul et al. 2016 Hu et al. 2017 Ji et al. 2019 BoseY & Weinshall] 2018). 8). These approaches are mainly based on data augmentation, where the network is trained to maximize the mutual information between inputs and predicted clusters, while regularizing the network that the cluster assignment of the data points is consistent with the assignment of the augmented points.
Different clustering objectives, such self-balanced k-means and balanced min-cut, have also been exhaustively studied (Liu et al. 2017] Chen et al. [017]] Chang et al.) 2014). One of the most effective techniques spectral clustering, which first generates node embeddings in the eigenspace of the graph Laplacian, and then applies k-means clustering to these vectors (Shi & Malik 2000 Ng et al.) 2002, Von Luxburg 2007). To address the fact that clusters with the lowest graph conductance tend to have few nodes (Leskovec) 2009. Zhang & Rohe 2018). (Zhang & Rohe 2018 proposed regularized spectral clustering to encourage more balanced clusters.
Generalizing clustering to unseen nodes and graphs is nontrivial (Bengio et al., 2003 Belkin et al. 2006, Mendoza Quispe et al., 2016). A recent work, SpectralNet (Shaham et al., 2018), takes a deep learning approach to spectral clustering that generalizes to unseen data points. This approach first learns embeddings of the similarity of each pair of data points in Laplacian's is eigenspace and then applies k-means to those embeddings to generate clusters. Unlike SpectraiNet, we propose an end-to-end learning approach with a differentiable loss that directly minimizes the normalized cuts. We show that our approach indeed can produce lower normalized cut values than the baseline methods such as SpectralNet, which consequently results in better clustering accuracy. Our evaluation results show that CNC improves generalization accuracy unseen data points by up to 21.9%.
2

---

Under review as a conference paper at ICLR 2020
3 PRELIMINARIES
Since CNC objective is based on optimizing normalized cuts, in this section, we briefly overview the formal definition of this metric.
3.1 FORMAL DEFINITION OF NORMALIZED CUTS
Let G (V, E,, W) be graph where V = {ux) and F fe(w, uy)lu; E V, V} the set of nodes and edges in the graph and Wij E W is the edge weight of the e(U,, vy). Let n be the number where the union of the nodes Sx = V). and each node belongs to only one set (Ni Sx 0), by
of nodes. A graph G can be clustered into y disjoint sets S1, -.. .2..... S.. in those sets are V simply removing edges connecting those sets. For example, in Figure [a), a)) by removing one edge two disjoint clusters are formed.
Normalized cuts (Ncuts) which is defined based on the graph conductance, has been studied by (Shi & Malik 2000: Zhang & Rohe 2018), and the cost of cut that forms disjoint sets Sj, S2, S is computed as:
cut( Sk. Sk) vol Sk. V)
Ncuts(S1, S2.... S2. Sg)) 5
(1)
k=1
Where S6 represents the complement of Sk, i.e., 3x = U.#R S.. (Sx, Ss) is called cut and the total weight of the edges that are removed from G in order to form disjoint sets Sy. and Sp. vol(Se, V) the total edge weights (wey), whose end points (ei, or 02) belong to Sk- The cut and vol are:
(u,
Σ Wij
vol(Sk, v)= Σ
Σ
Wij
D.ES BAEV
Note that in Equation 2 Sy and S₁ are disjoint, i.e., S& n S2 = 0. while in vol, St C V. In running example (Figure since the edge weights are one, cut(S), Si) = cur( S2) = 1, and vol(S1, V) vol(S, V) 2 2
7. Thus the N example one can see that such clustering results in minimum value of the normalized cuts. CNC aims to find eut that the normalized cuts (Equation T is minimized.
+ 0.286. In this
4 CNC FRAMEWORK
Finding the cluster assignments that minimizes the normalized cuts is NP-complete and an approxi- mation to the this problem is based on the eigenvectors of the normalized graph Laplacian which has been studied in (Shi Malik 2000 Zhang & Rohe 2018). CNC, on the other hand, is a neural network framework for learning to cluster in the absence of labeled examples by directly minimizing the continuous relaxation of the normalized cuts. As shown in Algorithm|] [ end-to-end training of the CNC contains two steps, i.e, (i) data points embedding (line 3), and (ii) clustering (lines 4-9). In data points embedding. the goal is to learn embeddings that capture the affinity of the data points, while the clustering step uses those embeddings assignments. Next, we first focus on the clustering step and we introduce our new differentiable loss function to train CNC model. Later in Section 4.2
learn the CNC model and outputs the cluster
we discuss the details of the embedding step.
4.1 CLUSTERING STEP: LEARN CNC MODEL
In this section, we describe the clustering step in Algorithm T (lines 4-9). For each data point x;, the input to clustering step is embedding v; IRd (detail in Section 4.2) The goal is to learn CNC model Fg I + R that for a given embedding v; R2 it returns y/ = Fb; E R2, which represents the assignment probabilities over clusters. Clearly for n data points, it returns Y E g=*y where Ya represents the probability that v; belongs to cluster Sg. The CNC model F9 is implemented using neural network, where the parameter vector denotes the network weights. We propose loss function based on output Y to calculate the expected normalized cuts. Thus CNC learns the Fo by minimizing this loss (Equation 7)..
Recall that cur(S,, St) is the total weight of the edges that are removed from G in order to form disjoint sets Sy and Sg. In our setup, embeddings are the nodes in graph G, and neighbors of an embedding v are based on the k-nearest neighbors. Let Yu be the probability that node e; belongs to cluster Sg. The probability that node v, does not belong to S₁ would be 1 Yςk. Therefore, Bleua(SE, St)) can be formulated by Equation 3 where N((e)) is the set of nodes adjacent v;
3

---

Under review as a conference paper at ICLR 2020
Algorithm 1
End-to-End Training CNC: Clustering by learning to optimize expected Normalized Cuts
1: Input: dataset X R number of clusters y, data point embedding size d, batch size b
2: Output: Cluster assignments of data points.
Preprocessing step, learn data points embedding (details in Section 4.2
3: Given dataset X
(I))...Ia). train Siamese network to find embeddings Ua)....u). 0/2 E TR& that represent the affinity of the data points. G R Clustering step, learn CNC model Fo (details in Section 4.7):
Rd
4: while CNC loss in Equation 6 converged do
5: Sample random minibatch M of size from the embeddings
6: Compute affinity graph W Rx over the M based on the k-nearest neighbors
7: Use M and W train CNC model Fg : Rd - R² that minimizes the expected normalized cuts
(Equation 6 via backpropagation. For a data point with embedding the output = (e;)
represents the assignment probabilities over g clusters.
8: end while
Inference, cluster assignments
9: For every data points z; whose embedding is vs return arg max of y4 (o())) as its cluster assignment.
Fy Sx]]=
Σ
Σ
wiy Yx Ysι)
(3)
V. (wN)
Since the weight matrix W represents the edge weights adjacent nodes, we rewrite Equation
Ey [cur( Sk. St)
Σ
Y,x(1 Y,,) @ W
recuce
The element-wise product with the weight matrix (@ W) ensures that only the adjacent nodes are matrix and reduce-sum the
considered. Moreover, the result of Y Y=,)) T @ W is sum over all of its elements. From Equation 2 (St V) is the total edge weights (wyy), whose end points (v, or v,) belong to Sy. Let be a column vector of size where D; is the total edge weights from node We can update Equation 3 follows to find the expected normalized cuts.
WiyYaa11 Yix)
EY [Ncuts]
ΣΣ Σ
(5)
L.. (NE) ΣnsEv Yu
The matrix representation is given in Equation 6 where I' = Y is a vector in IR*, and is the
number of sets/clusters. Ø element wise division and the result of (Y T) Y)T W is x n matrix where reduce-sume sunuue--uumnne is the sum over all of its elements.
Y. k
By- [Ncuts] = Σ
Y,,)
T
reduce-sum
(6)
Σ
[Yr][-Y)oo
CNC model Fg is implemented using neural network, where the parameter 0 denotes the network
weights (y: = (v:)). CNC is trained to optimize Equation via backpropagation (Algorithm 1.
arg min 8
Σ (Y W
reduce-sum
As you can see the affinity graph W is part of the CNC loss (Equation 7). Clearly, when the number of data points (n) is large, such calculation can be expensive. However, our experimental results, we show that for large dataset (e.g., Reuters contains 685,071 documents), it is possible to optimize the loss on randomly sampled minibatches of data. We also build the affinity graph over given minibach using the embeddings and based their k nearest-neighhor (Algorithm (lines 5-6)). Specifically, our implementation, CNC model Fg is a fully connected layer followed by gumble softmax, trained on randomly sampled minibatches of data to minimize Equation 6 In Section 5.7 through a sensitivity analysís we show that the minibatch size affects the accuracy of our model. When training over, the final assignment of data point with embedding v; cluster is the arg max of ys = (o( (Algorithm (line 9)).
4

---

Under review as a conference paper at ICLR 2020
4.2 EMBEDDING STEP
In this section, we discuss the embedding step (line 3 in Algorithm I). Different affinity measures, such simple euclidean distance or nearest neighbor pairs combined with Gaussian kernel, have been used in spectral clustering. Recently it is shown that unsupervised application of a Siamese network to determine the distances improves the quality of the clustering (Shaham al. 2018).
In this work, we also use Siamese networks to learn embeddings that capture the affinities of the data points. Siamese network is trained learn an adaptive nearest neighbor metric. It learns the affinities directly from euclidean proximity by "labeling" points I,, I, positive if ||2 - zyy l| is small and negative otherwise. In other words, it generates embeddings such that adjacent nodes are closer in the embedding space and non-adjacent nodes are further. Such network is typically trained to minimize contrastive loss:
-
flls - uyl1?
(x4, is a positive pair max(1 - ||;; 0yll?,07 (x4, is a negative pair
Tosiamese
where 04- Gramnee (It), and Geance Rm + Rd is Siamese network that transforms representations in the input space 24 E 1 embeddings vy IRd.
5 EXPERIMENTS
The main goals of our experiments are evaluate: (a) The performance CNC against the existing clustering approaches. (b) The ability of CNC to generalize to unseen data compared to the top- performing generalizable baseline. (c) The effectiveness of minimizing Normalized cuts on improving the clustering results. (d) The generalization performance of CNC as we vary the number of data points in training dataset.
5.1 DATASETS AND BASELINE METHODS
We evaluate the performance of CNC in comparison to several deep learning-based clustering approaches on four real world datasets: MNIST, Reuters, CIFAR-10, and CIFAR-IO0. The details of the datasets are as follows:
MNIST is collection of 70,000 28x28 gray-scale images of handwritten digits, divided into 60,000 training images and 10,000 test images.
The Reuters dataset is collection of English news labeled by category. Like SpectralNet, DEC, and VaDE, we used the following categories: corporate/industral,, govermment/social markets, and economics as labels and discarded all documents with multiple labels. Each article is represented by a tfidf vector using the 2000 most frequent words. The dataset contains 685,071 documents. We divided the data randomly to a 90%-10% split to evaluate the generalization ability of CNC. We also investigate the imapact of training data size on the generalization by considering following splits: 90%- 10%, 70%-30% 50%-50% 20%-80%, and 10%-90%
CIFAR-10 10 consists of 60000 32x32 colour images in 10 classes, with 6000 images per class. There are 50000 training images and 10000 test images.
CIFAR-100 has 100 classes containing 600 images each with 500/100 train/test split per class.
In all runs we assume the number of clusters given. In MNIST and CIFAR-10 10 number of clusters (g) is 10, g = 4 in Reuters, g 100 in CIFAR- 100. We compare CNC to SpectralNet (Shaham et al.) 2018
DEC Xie et al. 20116), DCN (Yang et al. 2017). VaDE (Jiang et al. 2017). DEPICT (Ghasedi Dizaji
et al.
2017). IMSAT (Hu et al. 2017). and IIC (Ji et al. 2019). While (Yang et al.) 2017 Xie 2016) focused on learning representations for clustering, other approaches (Jiang et al. 2017] Dilokthanakul et al. 2016 Hu et al. 2017 Di al. 2019 Ben- Yosef & Weinshall, 2018) rely on
et al.
a variational autoencoder that utilizes a Gaussian mixture prior. SpectralNet (Shaham et al. 2018). takes deep learning approach spectral clustering that generalizes unseen data points. Table shows the results reported for these six methods.
Similar to (Shaham al. 2018), for MNIST and Reuters we use publicly available and pre-trained autoencoders" The autoencoder used to map the Reuters data to code space was trained based on random subset of 10,000 samples from the full dataset. Similar (Hu et al. (017). for CIFAR-10 10 and 100 we applied 50-layer tre-trained deep residual networks trained on ImageNet to extract
features and used them for clustering.
https://g/t
5

---

Under review as a conference paper at ICLR 2020
MNIST
Reuters
CIFAR-I0
CIFAR-100
Method
ACC
NMI
ACC
NMI
ACC
NMI
ACC
NMI
DEC
0.843*
0.800
0.756
0.469
DCN
0.830*
0.810
VaDE
0.9451
0.794
DEPICT
0.965tt
0.917tt
IMSAT
0.984
0.719
0.456
0.275
IIC
0.993
0.617ttt
SpectralNet
0.971
0.924
0.803#
0.532
0.501
0.463
0.236
0.231
CNC
0.972
0.924
0.824
0.583
0.702
0.586
0.345
0.502
Table I: Performance of various clustering methods on MNIST, Reuters. CIFAR-10 and CIFAR-101
The model is trained on all data. (-) means values are not reported. (+) reported in DEC
[ et al.
2016 (**) reported in DCN [YYagg al., [017)]. (+) reported in VaDE [[Jaag al.
201 (017). (tt)
reported in DEPICT ((Ghasedi Dizaji et al. 2017)]. (t:) reported in IMSAT [(Hu et al. 2017 1, (1)
reported in SpectralNet [(Shaham et al. 2018) (ftf) reported in IIC [J] et 2019)
5.2 PERFORMANCE MEASURES
We use two commonly used measures, the unsupervised clustering accuracy (ACC), and the normal- ized mutual information (NMI) in (Cai al. (0ITT) to evaluate the accuracy of the clustering. Both ACC and NMI are in [0, 1], with higher values indicating better correspondence the clusters and the true labels. Note that true labels never used neither in training, nor in test.
Clustering Accuracy (ACC): For data points = fI1,... 22, }, let I = (4,....4) ..) and c = (C1, Cn) be the true labels and predicted clusters respectively, The ACC is defined as:
ACC(L, c) n rEll
max
Σ
= [(c))((())
where II the collection of all permutations of 1.... using the Kuhn-Munkres algorithm (Munkres 1957p.
g.
The optimal permutation i can be computed
Normalized Mutual Information (NMI): Let [(l;c) H() be their entropy. The NMI is:
be the mutual information between and c, and
I(l:c)
NMI(1,c) max (H(),, H(c)
5.3 EXPERIMENTAL RESULTS
For each dataset trained a Siamese network (Hadsell et al. 2006 Shaham & Lederman 2018) to learn embeddings which represents the affinity of data points by only considering the k-nearest neighbors of each data. In Table we compare clustering performance across four benchmark datasets. Since most of the clustering approaches do not generalize to unseen data points, all data has been used for the training (Later in Section 5.4 evaluate the generalizability use 90%-10% split for training and testing).
While the improvement of CNC is marginal over MNIST, it performs better across other three datasets. Specifically, over CIFAR-10, CNC outperforms SpectralNet and IIC on ACC by 20. 1% and 10.9% respectively. Moreover, the NMI is improved by 12.3%. The results over Reuters, and CIFAR-I00. show 0.021% % and 11 % improvement on ACC. The NMI is also 27% better over CIFAR-100. The fact that our CNC outperforms existing approaches in most datasets suggests the effectiveness of using our deep learning approach to optimize normalized cuts for clustering.
We performed an ablation study to evaluate the impact of embeddings by omitting this step in Algorithm [ We find that on both MNIST and Reuters datasets, adding the embedding step improves the performance, but CNC without embeddings still outperforms SpectralNet without embeddings. On MNIST, the ACC and NMI are 0.945 and 0.873, whereas with the embeddings, ACC and NMI increase to 0.972 and 0. 0.924 (Table [.. Without embeddings. CNC outperforms SpectralNet (with ACC of 0.8 and NMI of 0.814), On Reuters, the ACC and NMI are 0.684 and 0.428, whereas with the embeddings. ACC and NMI increase to 0.824 and 0.583, Again, even without embeddings, CNC outperforms SpectralNet (with ACC of 0.605 and NMI of 0.401).

---

Under review as a conference paper at ICLR 2020
MNIST
Reuters
CIFAR-10
CIFAR-100
Method
ACC
NMI
ACC
NMI
ACC
NMI
ACC
NMI
SpectralNet
0.970
0.9251
0.798
0.536*
0.491
0.478
0.229
0.230
CNC
0.971
0.925
0.824
0.586
0.701
0.585
0.343
0.526
Table 2: Generalization of clustering methods on MNIST, Reuters, CIFAR-I0 and CIFAR-100
datasets. The model is trained only on training set and the reported numbers the test accuracy. (-)
means values are not reported. ($) reported in SpectralNet [(Shaham et al. 2018
MNIST
Reuters
CIFAR-10
CIFAR-100
SpectralNet
0.913
0.351
4.229
82.831
CNC
0.879
0.21
2.451
58.535
Table 3: Numerical value of the normalized cut (Equation I over the clustoring results of the CNC and SpectralNet (Shaham et al. 2.18)]. CNC is able to find better cuts than the SpectralNet
5.4 GENERALIZATION
We further evaluate the generalization ability of CNC by dividing the data randomly to a 90%- 10% split and training on the training set and report the ACC and NMI on the test set (Table 2}. Among methods in Table [ only SpectralNet is able to generalize unseen data points. CNC outperforms SpectralNet in most datasets by up to 21 31.9% on ACC and up to 10.7% on NMI. Note that simple arg max over the output of CNC retrieves the clustering assignments while SpectralNet relies on k-means to predict the final clusters.
5.5 IMPACT OF NORMALIZED CUTS IN CLUSTERING
To evaluate the impact of normalized cuts for the clustering task, we calculate the numerical value of the Normalized cuts (Equation I over the clustering results of the CNC and SpectralNet. Since such calculation over whole dataset is very expensive we only show this result over the test set.
Table shows the numerical value of the Normalized cuts over the clustering results of the CNC and SpectralNet. As one can see CNC is able find better cuts than the SpectralNet. Moreover, we observe that for those datasets that the improvement of the CNC is marginal (MNIST and Reuters), the normalized cuts of CNC are also only slightly better than the SpectralNet, while for the CIFAR- 10 and CIFAR-100 that the accuracy improved significantly the normalized cuts of CNC are also much smaller than SpectralNet. The higher accuracy (ACC in Table and smaller normalized cuts (Table 3). verify that indeed CNC loss function is good notion for clustering task.
5.6 IMAPACT OF TRAINING DATA SIZE ON THE GENERALIZATION
As you may see in generalization result (Table 2). when we reduce the size of the training data to 90% the accuracy of CNC slightly changed in compare to training over the whole data (Table I]. Based on this observation, we next investigate how varying the size of the training dataset affects the generalization. In other words, how ACC and NMI of test data change when we vary the size of the training dataset.
We ran experiment over Routers dataset by dividing the data randomly based on the following data splits: 90%-10%, 70%-30% 50%-50% 20%-80% and 10%-90% For example, in 10%-90% we train CNC over 10% of the data and we report the ACC and NMI of CNC over the 90% test set. Figure shows shows how the ACC and NMI of CNC over the test data change as the size of the training data is varied. For example, when the size of the training data is 90%, the ACC CNC over the test data is 0.824.
As we expected and shown in Figure The the ACC and NMI of CNC increased as the size of the training data is increased. Interestingly, we observed that with only 10% training data the ACC of CNC is 0.68 which is only 14% lower than the ACC with 90% training data. Similarly the NMI CNC with 10% training data is only 18% lower than the NMI with 90% training data.
7

---

Under review as a conference paper at ICLR 2020
10--
Normalized Cutee (MCuts)
0787
6824
0.825
-00
E,644
Acuracy (ACC)
0.6
0.8
-30
-00
0.75
0.5
0.409
9.456
0.437
0.527
0.500
Accuracy (ACC)
0.8
0.4
-20
-30
0.25
ACC
NMI
0.775
0.2
-10
0
0.0
MNIST
Routors CIFAR-10 10 CFAR-100
Size of training data in %
30 40
50
60
70
80
90
0.75
Ni-3
hiz
himd
bwi22
bed12
be256
be612
k-3
k:3
K-10
Ind
Figure 2: Normalized cuts (right axis) and clustering ac- curacy (left axis) are anti- correlated. Lower normalized cuts results in better accuracy.
Figure 3: Reuters: with only 10% training data the ACC and NMI of CNC are only 14% and 18% lower than ACC and NMI with 90% train- ing data.
Figure 4: Reuters: CNC is trained by fixing some parameters and vary-
ing others. With Ir 5e 4,6 128, k = 3: ACC is 0.821
5.7 MODEL ARCHITECTURE AND HYPER-PAR PARAMEARMMMTSSS:
Here the details of the CNC model for each dataset.
MNIST: The Siamese network has 4 layers sized [1024, 1024, 512, 10] with ReLU (Embedding size d is 10). The clustering module has 2 layers sized [512, 512] with final gumbel softmax layer. Batch sized is 256 and we only consider nearest neighbors to find the embeddings and constructing the affinity graph for each batch. We use Adam with Ir = 0.005 with decay 0.5. Temperature starts at 1.5 and the minimum is set to 0.5.
Reuters: The Siamese network has 3 layers sized [512, 256, 128] with ReLU (Embedding size d is 128). The clustering module has 3 layers sized [512, 512, 512] with tanh activation and a final gumbel softmax layer. Batch sized is 128 and we only consider 3 nearest neighbors to find the embeddings and constructing the affinity graph for each batch. We use Adam with Ir = le-4 with decay 0.5. Temperature starts at 1.5 and the minimum set to 1.0.
CIFAR-10: 10: The Siamese network has 2 layers sized [512, 256] with ReLUU (Embedding size d is 256). The clustering module has layers sized [512, 512] with tanh activation and a final gumbel softmax layer. Batch sized is 256 and we only consider 2 nearest neighbors to find the embeddings and constructing the affinity graph for each batch. We use Adam with Ir = 1e-4 with decay 0.1. Temperature starts at 2.5 and the minimum is set to 0.5.
The Siamese network has 2 layers sized [512, 256] with ReLU (Embedding size d is 256). The clustering module has 3 layers sized [512, 512, 512] with tanh activation and a final gumbel softmax layer. Batch sized is 1024 and we only consider 3 nearest neighbors to find the embeddings and constructing the affinity graph for each batch. We use Adam with 1e-3 with decay 0.5. Temperature starts at 1.5 and the minimum is set to 1.0.
CIFAR-100:
Hyper-parameter Sensitivity: We train the CNC on the Reuters dataset by fixing some hyper- parameters and varying others. We noticed that CNC benefits from tuning the number of hidden layers (hl), learning rate (Ir), batch size (b), and the number of nearest neighbors (k), but is not particularly sensitive to any of the other hyper-parameters, including decay rate, patience parameter (cadence of epochs where decay is applied), Gumbeel-Sfftma temperature or minimum temperature (Figure 4.. More precisely, we varied decay rate over the range [0. 1-100, patience from [5-25] epochs, Gumbel-Softmax temperature from [1.0-2.0], and minimum temperature from [0.5-1.0]. When we fix hl=3, Ir=5e-5, b=64, and k=3, the average accuracy is 0.803 + 2e 3. With hl=3, Ir=5e-4, b=512, and k=10, the average accuracy is 0.811 + 2e 3. With hl=3, Ir=5e-4, b=128, and k=3, the average accuracy is 0.821 + 4e 3. With hl=2, Ir=le-4, b=256, and k=3, the average accuracy 0.766 + 9e - 4. And finally with hl=4, Ir=le-5, b=512, and k=3, the average accuracy is 0.766 - 7e 3. As one can see, the accuracy varied from 0.766 to 0.821.
CONCLUSION
We propose CNC (Clustering by learning to optimize Normalized Cuts), framework for learning to cluster unlabeled examples. We define a differentiable loss function equivalent to the expected normalized cuts and use it to train CNC model that directly outputs final cluster assignments. CNC achieves state-of-the of-te-o results on popular unsupervised clustering benchmarks (MNIST, Reuters, CIFAR-10 10, and CIFAR- 100 and outperforms the strongest baselines by up to 10.9%. CNC also enables generation, yielding up to 21.9% improvement over SpectralNet (Shaham et al. 2018), the previous besf-performing generalizable clustering approach.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In FOCS, pp. 475-486. IEFE, 2006.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, 2339,2433, 2006.
Matan Ben- Yosef and Daphna Weinshall. Gaussian mixture generative adversarial networks for diverse datasets, and the unsupervised clustering of images. CoRR, abs/1808. 10356, 2018.
Yoshua Bengio, Jean- -ran-François Paiement, Pascal Vincent, Olivier Delalleau, Nicolas Le Roux, and Marie Ouimet. Out-of-sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering. In Proceedings of the 16th International Conference on Neural Information Processing Systems, pp. 177-184, 2003.
Deng Cai, Xiaofei He, and Jiawei Han. Locally consistent concept factorization for document clustering. IEEE Trans. on Knowl. and Data Eng., 23(6))902-911 913, 2011.
Xiaojun Chang, Feiping Nie, Zhigang Ma, and Yang. Balanced k-means and min-cut clustering. arXiv preprint arXiv: /4/ 11211..222 1.6235, 2014.
Xiaojun Chen, Joshua Zhexue Huang, Feiping Nie, Renjie Chen, and Qingyao Wu. A self- self-balanced min-cut algorithm for image clustering. In ICCV, pp. 2080-2088, 2017.
Fan Chung. Four proofs for the cheeger inequality and graph partition algorithms. In Proceedings of ICCM, volume 2, pp. 378, 2007.
Nat Dilokthanakul, Pedro AM Mediano, Marta Garnelo, Matthew CH Lee, Hugh Salimbeni, Kai Arulkumaran, and Murray Shanahan. Deep unsupervised clustering with gaussian mixture varia- tional autoencoders. arXiv preprint 1rXiv:1611.02644 2016.
Kamran Ghasedi Dizaji, Amirhossein Herandi, Cheng Deng, Weidong Cai, and Heng Huang. Deep clustering via joint convolutional autoencoder embedding and relative entropy minimization. In The IEEE International Conference on Computer Vision (ICCV), Oct 2017.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington (eds.), AISTATS, volume pp. 249-256, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010, PMLR.
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning an invariant mapping. In Proceedings of the 2006 IEEE Computer Society Conference Computer Vision and Pattern Recognition Volume 2, CVPR '06. pp. 1735-1742, 2006.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 1025-1035, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Weihua Hu, Takeru Miyato, Seiya Tokui, Eicchi Matsumoto, and Masashi Sugiyama. Learning discrete representations via information maximizing self-augmented training. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 1558-1567, 2017.
Xu Ji, João F. Henriques, and Andrea Vedaldi. Invariant information distillation for unsupervised image segmentation and clustering. arXiv preprint arXiv: 1807.06653, 2019.
Zhuxi Jiang, Yin Zheng, Huachun Tan, Bangsheng Tang, and Hanning Zhou. Variational deep embedding: An unsupervised and generative approach to clustering. In Proceedings of the 26th International Joint Conference Artificial Intelligence, IJCAF'7, pp. 1965-1972, 2017.

---

Under review as a conference paper at ICLR 2020
George Karypis and Vipin Kumar. Multilevelk way partitioning scheme for irregular graphs. Journal of Parallel and Distributed computing, 48(1):96-129 1998.
George Karypis and Vipin Kumar. Multilevel k-way hypergraph partitioning. VLSI design, 11(3): 285-300, 2000.
George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel hypergraph partition- ing: applications in vlsi domain. IEEE T VLSI SYST, 7(1):69-79, 1999.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances neural information processing systems, pp. 1097-1105, 2012.
Jure Leskovec. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1):29-123, 2009.
Hanyang Liu, Junwei Han, Feiping Nie, and Xuelong Li. Balanced clustering with least square regression. In AAAI, pp. 2231-2237, 2017.
Arturo Mendoza Quispe, Caroline Petitjean, and Laurent Heutte. Extreme learning machine for out-of-sample extension in laplacian eigenmaps. Pattern Recognition, 74(C):68-73, 2016.
Pekka Miettinen, Mikko Honkala, and Janne Roos. Using METIS and hMETIS algorithms in circuit partitioning. Helsinki University of Technology, 2006.
James R. Munkres. Algorithms for the Assignment and Transportation Problems. Journal of the Society for Industrial and Applied Mathematics, 511::32-38, 1957.
Andrew Y Ng. Michael I Jordan, and Yair Weiss. On spectral clustering: Analysis and algorithm. In Advances neural information processing systems, pp. 849-856, 2002.
Peter Sanders and Christian Schulz. High quality graph partitioning. In Graph Partitioning and Graph Clustering, volume 588 of Contemporary Mathematics, pp. 1-18. American Mathematical SSocitty, 2012a.
Peter Sanders and Christian Schulz. Distributed evolutionary graph partitioning. In Proceedings of the Meeting on Algorithm Engineering & Expermiments, pp. 16-29. Society for Industrial and Applied Mathematics, 2012b.
Peter Sanders and Christian Schulz. Think Locally, Act Globally: Highly Balanced Graph Partitioning. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA 13), volume 7933 of LNCS, pp. 164-175. Springer, 2013.
Uri Shaham and Roy R. Lederman. Learning by coincidence: Siamese networks and common variable learning. Pattern Recognition, 74:52-63, 2018.
Uri Shaham, Kelly Stanton, Henry Li, Ronen Basri, Boaz Nadler, and Yuval Kluger. Spectral- net: Spectral clustering using deep neural networks. In International Conference on Learning Representations, 2018.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell., 22(8):888-905 August 2000.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1553 2014.
Christian Szegedy, Sergey loffe, Vincent Vanhoucke, and Alexander A Alemi. Inception-v4, inception- resnet and the impact of residual connections on learning. AAAI, volume 4, pp. 12, 2017.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395-44 416, 2007.
10

---

Under review as a conference paper at ICLR 2020
Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In Proceedings of the 33rd International Conference on International Conference on Machine Learning- Volume 48, ICML' 16, pp. 478 0878-4874400 2016.
Bo Yang, Xiao Fu, Nicholas D Sidiropoulos, and Mingyi Hong. Towards temeans-friendee spaces: Simultaneous deep learning and clustering. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 3861-38777 JMLR. org, 2017.
Yilin Zhang and Karl Rohe. Understanding regularized spectral clustering via graph conductance. In NeurlPS, pp. 10654-10663, 2018.
APPENDIX
Graph partitioning a well-studied subject computer science (Karypis Kumar 2000; Karypis et al. 1999 Karypis & Kumar 1998) Miettinen et al. 2006 (anndess & Schulz, 2013 Andersen et al. 2006; Chung 2007) with numerous applications in computer vision, VLSI design, biology, social networks, transportation networks and more.
In this section, we evaluate the performance of the CNC to partition computational graphs. In such graphs, nodes represent operations (e.g.. MatMul, Conv2d, Sum) and edges represent the computational flow. Partitioning of the computational graph can used for efficient mapping of the computation across the underlying hardware (e.g.. CPUs and GPUs). Minimizing the normalized cuts translates to less communication between devices and balanced computation on each device.
7.1 DATASETS AND BASELINE METHODS
We conducted experiments on five widely used TensorFlow computation graphs: ResNet, Inception- v3, AlexNet, MNIST-conv, and MNIST-conv. Clustering of operations can be used for the mapping of the computation across the underlying hardware (e.g.. CPUs and GPUs). We use the open source partitioners hMETIS (Karypis & Kumar 2000) and KaHIP (Sanders & Schulz, 2013). a family of graph partitioning programs based on (Sanders & Schulz 2012b a) to find high quality ground truth partitions on TensorFlow computation graphs. More specifically, KaHIP includes KaFFPa (Karlsruhe Fast Flow Partitioner) and KaFFPaE (KaFFPaEvolutionaar), KaFFPaE is parallel evolutionary algorithm that uses KaFFPa's combine and mutation operations, as well as KaBaPE which extends the evolutionary algorithm. We compare the generalization results of CNC against the best results among the partitioners. The details the datasets are as follows:
ResNet (He et al. 2016) is a deep convolutional network with residual connections. The TensorFlow implementation of ResNer v/ 50 with 50 layers contains 20,586 operations.
2017) consists of multiple blocks, each composed of several convolu- tional and pooling layers. The TensorFlow graph of this model contains 27,1 114 operations.
Inception-v3 (Szegedy et al.
AlexNet (Krizhevsky et al. 2012 consists of 5 convolutional layers, some of which are followed by maxpool layers, and 3 dense layers with a final softmax. The TensorFlow graph of this model has 798 operations.
MNIST-com: has 3 convolutional layers. Its TensorFlow graph contains 414 operations.
VGG (Simonyan & Zisserman 2014 has 16 convolutional layers. The TensorFlow graph of VGG contains 1,325 operations.
7.2 PERFORMANCE MEASURES
To evaluate the quality of CNC's clusterings, we use two commonly used performance metrics in graph partitioning: 1) Edge cut (Cut): the ratio of the cut to the total number of edges, and 2) Balancedness (Bal); one minus the MSE between the number of nodes in every cluster and the number of nodes an ideal balanced cluster ("). ). Both Cut and Bal are between 0 and 1. A lower Cut better while a higher Bal is better. The CNC loss function in Equation only considers optimizing the expected normalized cut. We add regularizer to improve balancedness between clusters.
11

---

Under review as a conference paper at ICLR 2020
AlexNet
Inception-v3
ResNet
Embedding
Cut
Bal
Cut
Bal
Cut
Bal
None
0.166
0.717
0.242
0.740
0.450
0.908
GCN
0.078
0.996
0.123
0.984
0.110
0,941
GraphSAGE-off
0.070
0.998
0.088
0.992
0.093
0,959
GraphSAGE-on
0.069
0.998
0.064
0.987
0.084
0.983
Table 4: Generalization results: CNC is trained on VGG and validated on MNIST-comv. During inference, the model is applied to unseen TensorFlow graphs: ResNet. Inception-v3. and AlexNet. The ground truth for AlexNet is Bal 99%, Cut = 4.6%, for Inception-v3, is Bal 99%, Cut 3.7%, and for ResNet is Bal = 99% and Cut 3.3%. GraphSAGE-on generalizes better than the other models.
7.3 EXPERIMENTAL RESULTS
To show that CNC generalizes effectively on unseen graphs, we train CNC on a single TensorFlow graph, VGG, and validate on MNIST-comv. During inference, we test the trained model on unseen TensorFlow graphs: AlexNet, ResNet, and Inception-v3. We consider the best quality result among hMETIS, KaFFPa, and KaFFPaE as the ground truth. The ground truth for AlexNer is Bal = 99%, Cut 4.6%, for Inception-v3, is Bal = 99%, Cut 3.7%, and for ResNet is Bal 99% and Cut = 3.3%.
Table 4 shows the result of our experiments, and illustrates the importance of graph embeddings in generalization. The operation type (such as Add, Conv2d, and L2loss in TensorFlow) is used as the node feature as a one-hot. We leverage GCN (Kipf & Welling 2017) and GraphSAGE (Hamilton et al., 2017) to capture similarities across graphs. In GraphSAGE-on both node embedding and clustering modules are trained jointly, while in GCN and GraphSAGE-off. only the clustering module is trained. Table X shows that the GraphSAGE-on (last row) achieves the best performance and generalizes better than the other models. Note that this model is trained on single graph, VGG with only 1325 nodes, and tested on AlexNet, ResNet, and Inception-v3 with 798, 20586, and 27 14 nodes respectively. On the other hand, the ground truth is the result of running different partitioning algorithms on each graph individually. In this work, our goal is not to beat the existing graph partitioning algorithms which involve a lot of heuristics on a given graph. Our generalization results show promise that rather than using heuristics, CNC able to learn graph structure for generalizable graph partitioning.
Model Architecture and Hyper-parameters: The details of the model with the best performance (GraphSAGE-on are follows: the input feature dimension is 1518. GraphSAGE has 5 layers sized 512 with shared pooling, and the graph clustering module has layers sized 64 with a final softmax layer. We use ReLU, Xavier initialization (Glorot & Bengio 2010), and Adam with Ir 7.5e-5.
12


Reviews:
[{"review_id": "Hyx0Uc59tS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 presents an end-to-end approach for clustering. The proposed model is called CNC. It simultaneously learns a data embedding that preserve data affinity using Siamese networks, and clusters data in the embedding space. The model is trained by minimizing a differentiable loss function that is derived from normalized cuts. As such, the embedding phase renders the data point friendly to spectral clustering. \nThe paper follows the general setup of deep clustering: map data to a feature space while maintaining data distributional characteristic, and make data clustering-friendly in the feature space. The authors use Siamese networks for the first part and use a normalized-cut motivated loss for the second part.  The choices are reasonable and the loss is somewhat novel. \nCNC is evaluated on standard datasets, including MNIST, Reuters, CIFAR-10, and CIFAR-100. The results are impressive. However, deep clustering has been around for quite a few years. It might be time to move on to more challenging benchmarks. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Hygd6m3lKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 new clustering method, called CNC, which is composed of two-step procedures.\nIt first embeds an input dataset into a d-dimensional space, followed by performing relaxed normalized cut to detect clusters.\nAlthough the contribution of introducing a new relaxed formulation of the normalized cut is interesting, I have the following concerns regarding with the clarity, significance, and evaluation of the proposed method.\n\n- The paper is not clearly written at many points and the quality of presentation is not high, which also deteriorates the significance of the paper.\n    In particular, the optimization process for clustering discussed in Section 4.1 is not clearly presented.\n    Although the objection function, which is the expectation of the Ncut, is introduced in Equation (6), how to solve it is not presented.\n    Since this is the key step for CNC, it should be carefully discussed.\n- In the embedding step, how to choose the dimensionality d?\n    This is not even reported in experiments.\n- Empirical evaluation is not thorough and important evaluation is missing.\n    * First, the contribution of embedding is not evaluated.\n      The performance between CNC with the proposed embedding and without it should be compared.\n      Moreover, the sensitivity of the performance with respect to changes in d should be examined.\n    * A number of resulting scores are missing; in particular, CNC is compared to only SpectralNet for CIFAR-10 and CIFAR-100 under NMI.\n      It would be more convincing if the NMI for other methods are also reported.\n- Parameter sensitivity is not evaluated, while there are a number of parameters in the proposed method as reported in Section 5.7.\n    Since parameter tuning is fundamentally difficult in the unsupervised setting, parameter sensitivity is crucial.\n    Also how to choose such parameters is not clear.\n\nMinor comments:\n- In Algorithm 1, line 1, \"X \\in R^n\" -> \"X \\subseteq R^m\"?\n- In Algorithm 1, the dimensionality \"m\" of data points and the batch size \"m\" are the same. Is it correct?\n- At the first line in Section 4.1: \"for each data point\" -> \"For each data point\"\n- P.4, L.-4: \"nreast-neighbor\" -> \"nearest-neighbor\"\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgdoUmCYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 paper suggests a differentiable objective that can be used to train a network to output cluster probabilities for a given datapoint, given a fixed number of clusters and embeddings of the data points to be clustered. In particular, this objective can be seen as a relaxation of the normalized cut objective, where indicator variables in the original formulation are replaced with their expectations under the trained model. The authors experiment with a number of clustering datasets where the number of cluster is known beforehand (and where, for evaluation purposes, the ground truth is known), and find that their method generally improves over the clustering performance of SpectralNet (Shaham et al., 2018) in terms of accuracy and normalized mutual information, and that it finds solutions with lower normalized cut values.\n\nThe method proposed in this paper is very simple and appears to work well, and so this paper represents an important contribution. However, there are some issues with the presentation that I think should be fixed before publication:\n- Equation (3): I'm not sure I understand the sum over z; don't we just want w_{ij} Y_{ik} (1 - Y_{jk})?\n- Equation (6): I don't think the final objective should be presented as an expectation. It is rather the quotient of two expectations. In general, it might be better to just present the objective as a relaxation of the normalized cut objective.\n\nA question regarding the results and parameterization: was using Gumbel-Softmax necessary to get good results? Did ordinary softmax not work?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a deep clustering method based on normalized cuts.  As the general idea of deep clustering has been investigated a fair bit, the reviewers suggest a more thorough empirical validation.  Myself, I would also like further justification of many of the choices within the algorithm, the effect of changing the architecture.
Decision: Reject