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.
This paper proposes a new clustering method, called CNC, which is composed of two-step procedures.
It first embeds an input dataset into a d-dimensional space, followed by performing relaxed normalized cut to detect clusters.
Although 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.
- 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.
    In particular, the optimization process for clustering discussed in Section 4.1 is not clearly presented.
    Although the objection function, which is the expectation of the Ncut, is introduced in Equation (6), how to solve it is not presented.
    Since this is the key step for CNC, it should be carefully discussed.
- In the embedding step, how to choose the dimensionality d?
    This is not even reported in experiments.
- Empirical evaluation is not thorough and important evaluation is missing.
    * First, the contribution of embedding is not evaluated.
      The performance between CNC with the proposed embedding and without it should be compared.
      Moreover, the sensitivity of the performance with respect to changes in d should be examined.
    * A number of resulting scores are missing; in particular, CNC is compared to only SpectralNet for CIFAR-10 and CIFAR-100 under NMI.
      It would be more convincing if the NMI for other methods are also reported.
- Parameter sensitivity is not evaluated, while there are a number of parameters in the proposed method as reported in Section 5.7.
    Since parameter tuning is fundamentally difficult in the unsupervised setting, parameter sensitivity is crucial.
    Also how to choose such parameters is not clear.
Minor comments:
- In Algorithm 1, line 1, "X \in R^n" -> "X \subseteq R^m"?
- In Algorithm 1, the dimensionality "m" of data points and the batch size "m" are the same. Is it correct?
- At the first line in Section 4.1: "for each data point" -> "For each data point"
- P.4, L.-4: "nreast-neighbor" -> "nearest-neighbor"