Abstract
State-of-the-art subspace clustering methods are based on self-expressive model, which represents each data point as a linear combination of other data points. However, such methods are designed for a finite sample dataset and lack the ability to generalize to out-of-sample data. Moreover, since the number of self-expressive coefficients grows quadratically with the number of data points, their ability to handle large-scale datasets is often limited. In this paper, we propose a novel framework for subspace clustering, termed Self-Expressive Network (SENet), which employs a properly designed neural network to learn a self-expressive representation of the data. We show that our SENet can not only learn the self-expressive coefficients with desired properties on the training data, but also handle out-of-sample data. Besides, we show that SENet can also be leveraged to perform subspace clustering on large-scale datasets. Extensive experiments conducted on synthetic data and real world benchmark data validate the effectiveness of the proposed method. In particular, SENet yields highly competitive performance on MNIST, Fashion MNIST and Extended MNIST and state-of-the-art performance on CIFAR-10.
Introduction
Subspace clustering aims to partition data points into groups, where each group corresponds to a low-dimensional subspace. This technique is fundamental in computer vision, where high-dimensional data like face images or motion trajectories often lie in a union of low-dimensional subspaces. The dominant paradigm is the self-expressive model, which assumes each data point $x_j$ can be represented as a linear combination of other points: $x_j = \sum_{i \neq j} c_{ij} x_i$.
While effective, traditional self-expressive methods face two critical bottlenecks. First, they are transductive, meaning they cannot generalize to new, unseen data without re-optimizing the entire coefficient matrix. Second, they suffer from poor scalability; the coefficient matrix $C \in \mathbb{R}^{N \times N}$ grows quadratically with the number of samples $N$, making it computationally prohibitive for large-scale datasets.
The SENet Framework
To overcome these limitations, we introduce the Self-Expressive Network (SENet). Instead of treating coefficients as independent variables to be optimized, SENet learns a function $f(x_i, x_j; \Theta)$ that predicts the relationship between any pair of points.
The architecture employs a "Query-Key" structure. A Query-Net transforms point $x_j$ into a representation $u_j$, while a Key-Net transforms $x_i$ into $v_i$. Their inner product is then passed through a learnable soft-thresholding layer $\mathcal{T}_b(\cdot)$. This layer is crucial as it enforces sparsity, ensuring that the network only identifies the most relevant points within the same subspace—a property known as being "subspace-preserving."
The model is trained using an Elastic Net loss, which combines $\ell_1$ and $\ell_2$ regularizations. This balance encourages sparse connections while maintaining enough graph connectivity for effective spectral clustering.
Scalability and Generalization
A key innovation of SENet is its ability to handle massive datasets. Traditional methods require storing the full $N \times N$ matrix. In contrast, SENet uses a two-pass Stochastic Gradient Descent (SGD) algorithm. The first pass computes a global residual, and the second pass computes gradients for a mini-batch. This approach keeps memory requirements constant relative to the dataset size, enabling clustering on datasets with hundreds of thousands of points.
Furthermore, because SENet learns a parametric function, it can perform out-of-sample clustering. Once trained on a representative subset, the network can instantly predict coefficients for new data points, effectively learning the underlying geometry of the subspaces.
Experimental Results
SENet was evaluated across several benchmarks, demonstrating both superior accuracy and efficiency. On CIFAR-10, SENet achieved a state-of-the-art accuracy of 76.5%, outperforming the previous best method (EnSC) by over 15%. On the large-scale EMNIST dataset (approx. 190,000 points), SENet maintained high performance while traditional methods became computationally impractical.
As shown in the coefficient matrix visualizations, SENet successfully recovers the block-diagonal structure essential for subspace clustering. This indicates that the network correctly learns to associate points belonging to the same subspace while ignoring those from different ones.
Conclusion
SENet represents a significant shift in subspace clustering, moving from static optimization to dynamic neural learning. By addressing the core issues of scalability and generalization, it opens the door for subspace clustering applications in large-scale, real-world scenarios. Future work will explore integrating SENet into end-to-end deep clustering pipelines and applying it to related tasks like outlier detection.
Summary updated