Learning a Self-Expressive Network for Subspace Clustering

Shangzhi Zhang, Chong You, René Vidal, Chun-Guang Li

Abstract

State-of-the-art subspace clustering methods are based on the 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 is a fundamental technique for grouping data points that lie near low-dimensional linear subspaces, with applications ranging from image processing to motion segmentation. The current "gold standard" is the self-expressive model, which assumes that every data point can be represented as a linear combination of other points within the same cluster.

Despite its success, traditional self-expressive methods suffer from two critical limitations. First is scalability: they typically require solving for an $N \times N$ coefficient matrix, leading to $O(N^2)$ complexity that becomes prohibitive for large datasets. Second is the transductive nature: these models are tied to the specific dataset they are trained on. If new data points arrive, the entire optimization must be re-run, as the model cannot generalize to out-of-sample data.

SENet (Self-Expressive Network) addresses these issues by transforming subspace clustering into a scalable deep learning task. By training a neural network to predict how data points represent one another, the authors enable subspace clustering to handle hundreds of thousands of points and generalize to previously unseen data for the first time.

The SENet Framework

Instead of treating the self-expressive coefficients as static variables to be optimized, SENet parameterizes the self-expression as a learned function $f(x_i, x_j; \Theta)$.

The SENet architecture featuring Query and Key networks followed by a soft-thresholding operator to produce self-expressive coefficients.

Architecture Details

The architecture is inspired by the attention mechanism found in modern transformers:

  • Query and Key Networks: Two Multi-Layer Perceptrons (MLPs) map input data points $x_j$ and $x_i$ into a latent space as a "query" vector $u_j$ and a "key" vector $v_i$.
  • Inner Product & Soft-Thresholding: The self-expressive coefficient is derived from the inner product $u_j^T v_i$. To ensure the mathematical requirement of sparsity—which is essential for accurate subspace discovery—the network applies a learnable soft-thresholding operator $\mathcal{T}_b(\cdot)$.
  • Elastic Net Regularization: The model is trained using a loss function that combines $\ell_1$ (sparsity) and $\ell_2$ (connectivity) penalties, ensuring the learned coefficients are both sparse and robust.

Scalable Optimization via Two-Pass SGD

To overcome the memory bottleneck of $O(N^2)$ coefficients, the authors developed a two-pass Stochastic Gradient Descent (SGD) algorithm. In the first pass, the reconstruction error for a data point is calculated relative to the rest of the dataset. In the second pass, gradients are accumulated. This approach allows for constant memory complexity, enabling the model to scale to datasets of virtually any size, provided individual points fit in memory.

Experimental Results

SENet was evaluated on several standard benchmarks, including MNIST, Fashion-MNIST, CIFAR-10, and the massive Extended MNIST (EMNIST) dataset containing over 190,000 images.

Visualization of the learned self-expressive coefficient matrices for training (tr) and test (ts) sets across different training stages, demonstrating the model's inductive capability.

Key Findings

  • Inductive Power: As shown in the visualization of the coefficient matrices, SENet successfully learns the underlying subspace structure. Crucially, a network trained on a subset of data can accurately cluster unseen test data ($C_{ts}$), proving it captures the geometry of the subspaces rather than just point-to-point relationships.
  • State-of-the-Art Performance: On CIFAR-10, SENet achieved an accuracy of 76.5%, a significant 15.2% improvement over previous leading methods like EnSC.
  • Massive Scalability: SENet successfully clustered the EMNIST dataset with 72.1% accuracy. Traditional methods would take over 24 hours to process a dataset of this size, whereas SENet handles it efficiently.

Conclusion

SENet represents a significant step forward in subspace clustering by moving from transductive optimization to inductive learning. By "baking in" sparsity through its architecture and utilizing a scalable two-pass SGD algorithm, it overcomes the long-standing barriers of scalability and generalization. Future work may involve pairing SENet with convolutional front-ends for non-linear high-dimensional data or extending the self-expressive framework to tasks like outlier detection and image completion.

Summary updated

Abstract

State-of-the-art subspace clustering methods are based on the 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.
BibTeX
@inproceedings{zhang2021learning,
  author = {Shangzhi Zhang and Chong You and René Vidal and Chun-Guang Li},
  title = {{Learning a Self-Expressive Network for Subspace Clustering}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2021},
  url = {https://openreview.net/forum?id=clgjzZGMP2y},
}
Figure