PaperlayerView exact revision on arXiv

Source-linked AI summary

SpectralNet: Spectral Clustering using Deep Neural Networks

Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, Yuval Kluger

arXiv:1801.01587v6stat.MLcs.LG

TL;DR

Spectral clustering is difficult to scale and extend to unseen data points. SpectralNet learns a spectral-embedding function through constrained stochastic optimization, and the paper reports improved clustering quality from learned affinities and autoencoder representations, along with state-of-the-art Reuters results.

  • Problem

    Spectral clustering faces scalability limits from large-scale eigenvector computation and difficulty extending spectral embeddings to unseen data points.

  • Method

    SpectralNet uses constrained stochastic optimization to learn a feed-forward map from input data to graph-Laplacian spectral coordinates.

  • Results

    The paper reports better clustering from unsupervised Siamese-network affinities and further improvement using autoencoder code representations, with state-of-the-art results on Reuters.

  • Takeaways & Limitations

    SpectralNet provides approximate spectral clustering with scalability and a natural function for embedding new test points.

  • Takeaways & Limitations

    Without structure in the data, the required network size grows with the number of data points, and minibatches must adequately capture affinity structure.

Abstract

from arXiv · show

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 special-purpose 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 leaned from unlabeled data using a Siamese network. Additional improvement 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 .

1 INTRODUCTION

Spectral clustering is valuable for revealing structure in unlabeled data but faces scalability and out-of-sample-extension challenges. SpectralNet addresses these challenges with a deep, constrained stochastic approach that learns spectral embeddings for new points.

  • Clustering helps analyze large collections of unlabeled images, texts, and other data whose labeling is expensive, tedious, or expertise-dependent.
  • Spectral clustering embeds data in the graph Laplacian eigenspace and applies k-means, while supporting non-convex clusters through its similarity-based representation.
  • On simulated 2D and 3D datasets, SpectralNet found non-convex clusters in all five examples, whereas DCN, VaDE, DEPICT, and IMSAT failed.
  • Direct eigenvector computation can be prohibitive for large datasets, and extending spectral embeddings to unseen points is non-trivial.
  • SpectralNet learns a feed-forward map to spectral coordinates using constrained stochastic optimization, with orthogonality enforced by a QR-based linear output layer.

2 RELATED WORK

Earlier deep clustering methods commonly learn representations suited to convex clustering objectives, while related spectral approaches differ in their treatment of inputs, supervision, and out-of-sample extension. SpectralNet is distinguished by learning a data-to-embedding function without requiring true eigenvectors or full affinity preprocessing for new points.

  • DCN, DEC, and DEPICT learn codes using k-means, sharpened cluster assignments, or balanced-cluster regularization, often after autoencoder pretraining.
  • The k-means and Gaussian-mixture objectives used by several methods can bias representations toward convex clusters, unlike SpectralNet’s behavior on the illustrated tasks.
  • Tian et al. map graph-Laplacian rows to spectral embeddings, making out-of-sample extension impractical because new points require affinities to all training data.
  • Yi et al. use learned graph convolutions with eigenvector-based spectral embeddings, whereas SpectralNet enforces orthogonalization stochastically through a constraint layer.
  • Supervised spectral-learning methods require true eigenvectors or labels, limiting their suitability for fully unsupervised large-scale settings.
  • SGD-based spectral clustering can compute eigenvector embeddings, but methods such as Han and Filippone do not represent them as functions of the data, preventing out-of-sample extension.

3 SPECTRALNET

SpectralNet learns a neural spectral embedding and cluster assignments through unsupervised affinity learning, constrained optimization, and k-means. Its stochastic training targets scalability, while the learned input-to-embedding map supports out-of-sample extension.

  • SpectralNet overview: SpectralNet learns a map from each input point to spectral embedding coordinates and assigns clusters by applying k-means in the embedded space.The map is implemented as a neural network, followed by cluster assignment in R^k.
  • Training components: Training combines unsupervised Siamese affinity learning, constrained optimization of the spectral map, and k-means clustering of the embeddings.The three components respectively learn affinities, enforce orthogonality during map optimization, and determine cluster assignments.
  • Learning the spectral map: The spectral-map objective pulls embeddings of similar points together while orthogonality prevents the degenerate solution that maps every point to one output vector.The affinity function assigns larger weights to more similar point pairs, and the outputs are required to be orthonormal in expectation.
  • Learning the spectral map: Minibatch stochastic optimization replaces unknown-distribution expectations with empirical estimates and trains the network using randomly sampled batches.The method alternates orthogonalization and gradient steps, using QR decomposition for the final layer and backpropagation for the remaining weights.
  • Connection with spectral clustering: The learned map approximates spectral clustering while trading exact eigenvector embedding accuracy for scalability and generalization ability.The loss corresponds to the graph-Laplacian spectral objective on minibatches, whose minimizer spans the smallest-eigenvalue eigenspace.
  • Learning affinities: Unsupervised Siamese distances yield dramatically improved clustering quality over Euclidean distances despite being trained from relatively naive nearest-neighbor relations.The learned distances replace Euclidean distances when constructing the affinity matrix used to train SpectralNet.

4 THEORETICAL ANALYSIS

The theoretical analysis studies how expressive spectral clustering is and derives lower bounds on the size of neural networks that represent it. In the general case, the required network size grows with the number of data points, while geometric structure can permit smaller networks.

  • Setup: The analysis studies the minimum neural-network size needed to compute two-cluster spectral clustering using VC dimension theory.It considers binary outputs obtained by thresholding the second-smallest Laplacian eigenvector at zero.
  • Main result: Spectral clustering has VC dimension linear in n for data in R^d with d ≥3, making it nearly as expressive as arbitrary clustering.The theorem establishes a lower bound of at least 1/10n for the relevant function class.
  • Network-size bounds: For sigmoid networks with |v| units and |w| weights, representing all such spectral-clustering functions requires |w|^2|v|^2 ≥ O(n).This is a necessary, not sufficient, condition derived by connecting the VC-dimension lower bound to neural-network VC-dimension bounds.
  • Network-size bounds: For networks whose weights come from a finite family, representing all spectral-clustering functions requires |w| ≥ O(n).The bound uses the linear VC-dimension dependence on the number of finite-family weights.
  • Scope and qualification: These lower bounds apply without assumptions on the data distribution, but structured geometric data can admit networks whose size does not depend on n.The geometric-structure exception is associated with approximating eigenfunctions of manifold Laplacians.

5 EXPERIMENTAL RESULTS

Experiments evaluate clustering quality, spectral-subspace approximation, scalability, and generalization on MNIST and Reuters, with an additional semi-supervised demonstration. SpectralNet benefits from Siamese affinities and code-space representations, and achieves strong clustering and test performance.

  • 5.1 Evaluation Metrics: ACC and NMI evaluate correspondence between predicted clusters and true labels, with higher values indicating better correspondence.ACC uses the best label permutation, while NMI is normalized by the larger label or cluster entropy.
  • 5.2.1 MNIST: On MNIST, Siamese affinities and code-space representations significantly improve SpectralNet, which outperforms DEC, DCN, VaDE, DEPICT, and JULE and is competitive with IMSAT.The experiment uses all 70,000 images for training and compares Euclidean and Siamese distances in input and code spaces.
  • 5.2.1 MNIST: 0.026 is the stabilized Grassmann distance between SpectralNet outputs and the true Laplacian-eigenvector subspace on MNIST.The distance decreases rapidly at the beginning of training and then stabilizes as parameter updates continue.
  • 5.2.1 MNIST: 0.970 is the MNIST test accuracy when SpectralNet is trained on the training set and applied to unseen test examples.Test labels are assigned using the nearest centroid from k-means performed on the training embeddings.
  • 5.2.2 Reuters: On Reuters, SpectralNet outperforms the other methods, performs best in code space with Siamese affinity, and learns the spectral map in less than 20 minutes.Reuters contains 685,071 documents; computing the top four Laplacian eigenvectors took over 100 minutes with ARPACK, while standard spectral clustering produced unreasonable clustering.
  • 5.2.2 Reuters: 0.798 is the Reuters test accuracy after training on a random 90%-10% split and predicting labels for the held-out subset.The Siamese network and SpectralNet are retrained on the larger subset before prediction.
  • 5.3 Semi-Supervised Learning: Using randomly chosen labels for 2% of points enables SpectralNet to recognize the true cluster structure in a noisy 2D demonstration.Without labels, the method fails to recognize the true structure because of the large amount of noise.

6 CONCLUSIONS

The paper presents SpectralNet as an approximate spectral-clustering method that combines stochastic training, a parametric embedding map, learned affinities, and code representations. It reports state-of-the-art results on two benchmark datasets and a VC-dimension lower bound for networks computing spectral clustering.

  • 6 Conclusions: SpectralNet uses stochastic training to scale approximate spectral clustering and a parametric map to provide straightforward out-of-sample extension.The method learns a function that maps inputs to spectral embedding coordinates.
  • 6 Conclusions: Unsupervised Siamese distances and autoencoder code representations further improve SpectralNet's clustering performance compared with standard Euclidean distances and input representations.The paper also reports a novel VC-dimension analysis and derives a lower bound on the size of neural networks that compute spectral clustering.
  • 6 Conclusions: SpectralNet reports state-of-the-art results on two benchmark datasets and outperforms existing methods when clusters cannot be contained in non-overlapping convex shapes.The authors characterize integrating spectral clustering with deep learning as a useful tool for unsupervised deep learning.

A ILLUSTRATIVE DATASETS

On illustrative two-dimensional datasets, SpectralNet and standard spectral clustering recover nonconvex structure, whereas several deep clustering baselines fail, especially when clusters cannot be separated by non-overlapping convex shapes.

  • Nested ’C’s: SpectralNet and standard spectral clustering identify the correct nested-cluster structure, while k-means fails.SpectralNet outputs closely approximate the two true eigenvectors, with Grassmann distance approaching zero as the loss decreases.
  • Illustrative datasets: DCN, VaDE, and DEPICT failed to produce appropriate clusterings on any of the five illustrative datasets, while IMSAT succeeded on two.The experiments tested multiple network architectures and hyper-parameter settings for each method.
  • Nested ’C’s: All three tested methods fail on nested ’C’s once the clusters cannot be separated using non-overlapping convex shapes.The comparison varied the distance between the two clusters.
  • Figure 5: Figure 5 presents results for DCN, VaDE, DEPICT, and IMSAT from top to bottom on the illustrative datasets.
  • DEPICT behavior: DEPICT’s target distribution becomes corrupted during training despite its loss decreasing from 9.01 to 0.22.The target distribution was initialized with agglomerative clustering, which successfully clusters the nested ’C’s.

B CORRECTNESS OF THE QR DECOMPOSITION

The proof establishes that a Cholesky decomposition can compute the QR decomposition of a positive definite matrix by preserving the relevant column spaces and yielding Gram–Schmidt orthogonalization.

  • Column-space preservation: Because L is lower triangular, (L^-1)^T is upper triangular, so the first i columns of A and Q span the same column space.Here Q = A(L^-1)^T.
  • Orthogonalization: Showing that Q’s columns correspond to Gram–Schmidt orthogonalization completes the QR-decomposition argument.

C.1 PRELIMINARIES

The preliminaries define separated graphs and construct balanced point sets whose within-class connectivity and between-class separation support the later spectral-clustering argument.

  • Definitions and assumptions: An (α, β)-separated graph has an even vertex set, a balanced partition S∪T, and affinity constraints distinguishing within-partition paths from cross-partition affinities.The partition satisfies |S|=|T|.
  • Lemma C.2 construction: For any binary partition of m grid points, Lemma C.2 constructs 10m points with a balanced partition extending the original dichotomy.The construction uses added points, lifted copies at Z=1 and Z=−1, midpoints, and spanning-tree points.
  • Lemma C.2 construction: The construction connects points within each set through paths whose consecutive Euclidean distances are at most b<1.The spanning-tree additions ensure the required within-set connectivity.
  • Spectral-loss preliminaries: The spectral-clustering loss is analyzed for normalized, zero-sum vectors by bounding within-partition variation and comparing it with a two-valued candidate vector.The proof orders eigenvector entries and uses telescopic sums of squares.
  • Spectral-loss preliminaries: The construction and lemmas establish conditions used to control the second-smallest Laplacian eigenvector across the two partition sets.The resulting bounds constrain the spread of eigenvector entries within each set.

C.2 PROOF OF THEOREM 4.1

The theorem proof constructs a Gaussian-affinity graph whose second-smallest Laplacian eigenvector realizes every dichotomy of a selected point set, yielding a linear VC-dimension lower bound.

  • VC-dimension construction: To establish the VC-dimension bound, the proof selects m=n/10 points that can be extended to 10m-point balanced constructions for any binary dichotomy.This follows from Lemma C.2 with dimension d≥3.
  • Graph construction: The proof assigns standard Gaussian affinities to the complete graph and uses the construction’s properties to obtain an (α, β)-separated graph.
  • Eigenvector analysis: The second-smallest Laplacian eigenvector minimizes the weighted pairwise-difference objective subject to zero-sum and unit-norm constraints.The objective is ΣW_i,j(y_i−y_j)^2.
  • Eigenvector analysis: Choosing σ sufficiently small makes the within-partition eigenvector spread Δ arbitrarily small, allowing thresholding at zero to respect the constructed partition.The theorem also holds with constant σ by uniformly scaling point locations.
  • Conclusion: The proof concludes that every dichotomy is realized by a second-smallest Laplacian eigenvector, so spectral clustering has VC dimension at least m=n/10.

D TECHNICAL DETAILS

The experiments use validation loss to select hyperparameters, control learning-rate decay, and determine stopping, with implementation details varying across datasets.

  • The implementation uses sklearn.cluster defaults for k-means and 25-neighbor affinities with median-distance scaling for spectral clustering.The k-means configuration uses 300 iterations, 10 random restarts, and the run with the best objective.
  • Learning rates are divided by 10 after validation loss stops improving for the specified patience period.Training stops when the learning rate reaches 10^-8.
  • SpectralNet training typically requires fewer than 20,000 parameter updates on MNIST and Reuters.Typical Siamese-net training took about 100 epochs on both datasets.
  • MNIST affinity batches connect each point to its two nearest neighbors under the learned Siamese distance.The Siamese training pairs each point with its two nearest Euclidean neighbors, and σ uses the median nearest-neighbor distance.
  • Reuters Siamese training pairs each training point with a random point among its 100 approximate nearest neighbors.The affinity scale σ is the global median distance to the 10th neighbor, and Siamese training uses training data only for generalization evaluation.
  • Validation loss determines hyperparameters for spectral-map learning, and lower validation loss is preferred.MNIST experiments varied architectures and learning-rate policies while holding the Siamese net and Gaussian scale fixed.
Loading 1801.01587v6…