SPECTRALNET: SPECTRAL CLUSTERING USING DEEP NEURAL NETWORKS
Spectral clustering is a leading and popular technique in unsupervised data analysis. Two of its major limitations are scalability and generalization of the spectral embedding (i.e., out-of-sample-extension). In this paper we introduce a deep learning approach to spectral clustering that overcomes the above shortcomings. Our network, which we call SpectralNet, learns a map that embeds input data points into the eigenspace of their associated graph Laplacian matrix and subsequently clusters them. We train SpectralNet using a procedure that involves constrained stochastic optimization. Stochastic optimization allows it to scale to large datasets, while the constraints, which are implemented using a specialpurpose output layer, allow us to keep the network output orthogonal. Moreover, the map learned by SpectralNet naturally generalizes the spectral embedding to unseen data points. To further improve the quality of the clustering, we replace the standard pairwise Gaussian affinities with affinities learned from the given unlabeled data using a Siamese network. Additional improvement of the resulting clustering can be achieved by applying the network to code representations produced, e.g., by standard autoencoders. Our end-to-end learning procedure is fully unsupervised. In addition, we apply VC dimension theory to derive a lower bound on the size of SpectralNet. State-of-the-art clustering results are reported on the Reuters dataset. Our implementation is publicly available at https://github.com/kstant0725/SpectralNet.
PAPER SUMMARY
This paper aims to address two limitations of spectral clustering: its scalability to large datasets and its generalizability to new samples. The proposed solution is based on designing a neural network called SpectralNet that maps the input data to the eigenspace of the graph Laplacian and finds an orthogonal basis for this eigenspace. The network is trained by alternating between orthogonalization and gradient descent steps, where scalability is achieved by using a stochastic optimization scheme that instead of computing an eigendecomposition of the entire data (as in vanilla spectral clustering) uses a Cholesky decomposition of the mini batch to orthogonalize the output. The method can also handle out-of-sample data by applying the learned embedding function to new data. Experiments on the MNIST handwritten digit database and the Reuters document database demonstrate the effectiveness of the proposed SpectralNet.
COMMENTS
1) I find that the output layer (i.e. the orthogonalization layer) is not well-justified. In principle, different batches require different weights on the output layer. Although the authors observe empirically that orthogonalization weights are roughly shared across different batches, the paper lacks a convincing argument for why this can happen. Moreover, it is not clear why an output layer designed to orthogonalized batches from the training set would also orthogonalize batches from the test set?
2) One claimed contribution of this work is that it extends spectral clustering to large scale data. However, the paper could have commented more on what makes spectral clustering not scalable, and how the method in this paper addresses that. The authors did mention that spectral clustering requires computing eigenvectors for large matrices, which is prohibitive. However, this argument is not entirely true, as eigen-decomposition for large sparse matrices can be carried out efficiently by tools such as ARPACK. On the other hand, computing the nearest neighbor affinity or Gaussian affinity is N^2 complexity, which could be the bottleneck of computation for spectral clustering on large scale data. But this issue can be addressed using approximate nearest neighbors obtained, e.g., via hashing. Overall, the paper compares only to vanilla spectral clustering, which is not representative of the state of the art. The paper should do an analysis of the computational complexity of the proposed method and compare it to the computational complexity of both vanilla as well as scalable spectral clustering methods to demonstrate that the proposed approach is more scalable than the state of the art. 
3)  Continuing with the point above, an experimental comparison with prior work on large scale spectral clustering (see, e.g. [a] and the references therein) is missing. In particular, the result of spectral clustering on the Reuters database is not reported, but one could use other scalable versions of spectral clustering as a baseline.
4)  Another benefit of the proposed method is that it can handle out-of-sample data. However, the evaluation of such benefit in experiments is rather limited. In reporting the performance on out-of-sample data, there is no other baseline to compare with. One can at least compare with the following baseline: apply k-means to the training data in input space, and classify each test data to the nearest centroid.
5) The reason for using an autoencoder to extract features is unclear. In subspace clustering, it has been observed that features extracted from a scattering transform network [b] can significantly improve clustering performance, see e.g. [c] where all methods have >85% accuracy on MNIST. The methods in [c] are also tested on larger datasets.
[a] Choromanska, et. al., Fast Spectral Clustering via the Nystrom Method, International conference on algorithmic learning theory, 2013
[b] Bruna, Mallat, Invariant Scattering Convolution Networks, arXiv 2012
[c] You, et. al., Oracle Based Active Set Algorithm for Scalable Elastic Net Subspace Clustering, CVPR 2016