Nonlinear Subspace Clustering via Adaptive Graph Regularized Autoencoder

Qiang Ji, Yanfeng Sun, Junbin Gao, Yongli Hu, Baocai YinIEEE Access 2019 · DOI · OpenReview

Introduction

High-dimensional data, such as facial images or handwritten digits, often reside in a union of low-dimensional subspaces. Subspace clustering is a fundamental task in computer vision and machine learning that aims to identify these underlying structures to group data points effectively. Traditional methods typically rely on the "self-expressiveness" property, assuming that a data point can be represented as a linear combination of others within the same subspace. However, these methods often falter when faced with real-world data characterized by complex nonlinear distributions and noise. Furthermore, they frequently overlook local geometric relationships, focusing solely on global correlations.

To address these challenges, this paper proposes Nonlinear Subspace Clustering via Adaptive Graph Regularized Autoencoder (NSC-AGA). This framework integrates deep feature learning with subspace clustering in a unified optimization process.

The NSC-AGA Framework

The NSC-AGA architecture is built upon three primary components designed to capture both the global and local structures of data in a nonlinear feature space.

1. Deep Autoencoder for Nonlinear Mapping

At the core of the framework is a stacked autoencoder. Unlike traditional linear models, the autoencoder maps raw, high-dimensional data into a latent feature space ($H$). This allows the model to learn complex, nonlinear representations that are more suitable for clustering than raw pixel values.

The basic architecture of a deep autoencoder, which serves as the foundation for feature extraction in NSC-AGA.

2. Self-Expressive Layer

Integrated within the autoencoder is a self-expressive layer that learns a representation matrix ($C$). This matrix enforces the self-expressiveness property on the deep features, capturing the global linear correlations between data points in the latent space.

3. Adaptive Graph Regularization

The most significant innovation of NSC-AGA is the adaptive graph regularizer. This component ensures that the representation matrix $C$ respects the local Euclidean distances of the learned deep features. By treating $C$ as a learnable similarity graph, the model creates a feedback loop: as the autoencoder learns more discriminative features, the graph becomes more accurate, which in turn guides the feature learning process.

Optimization and Constraints

The model is optimized using the Alternating Direction Method (ADM), which iteratively updates the neural network weights via backpropagation and the representation matrix. To enhance interpretability and performance, a non-negativity constraint ($C \ge 0$) is applied to the coefficients. This ensures that the resulting matrix can be directly interpreted as a similarity graph for spectral clustering, avoiding the issues associated with negative weights in sparse representation methods.

Experimental Evaluation

The effectiveness of NSC-AGA was validated on five standard image benchmarks: Extended Yale B, COIL20, COIL100, USPS, and ORL. These datasets represent a variety of challenges, including varying illumination, object rotation, and handwritten digit variations.

Key results include:

  • Superior Accuracy: NSC-AGA consistently outperformed 11 state-of-the-art methods. For instance, on the COIL100 dataset, it achieved an accuracy of 72.56%, surpassing other deep models like NSC-Nets.
  • Scalability and Stability: The model demonstrated remarkable stability as the number of subspaces increased. On the Extended Yale B dataset, it maintained approximately 97.8% accuracy even when scaled to 38 subjects.
  • Structural Clarity: Qualitative analysis of the affinity matrices revealed a sharp "block-diagonal" structure, indicating clear separation between clusters with minimal inter-cluster noise.

Conclusion and Future Work

NSC-AGA demonstrates that joint optimization of feature learning and clustering is essential for handling complex, nonlinear data. By combining global self-expressiveness with local graph regularization, the model achieves state-of-the-art performance and robustness. Future research may focus on reducing the $O(N^3)$ computational complexity to better accommodate large-scale "Big Data" applications and exploring automated methods for hyperparameter tuning.

Summary updated

Abstract

Most existing subspace clustering methods focus on learning a meaningful (e.g., sparse or low-rank) representation of the data. However, they have the following two problems which greatly limit the performance: 1) They neglect the intrinsic local geometrical structures within the data to result in locality preserving property be missing. 2) They neglect the feature learning of the raw data which is usually so complex that the learned representation coefficient is not an optimal graph for clustering. This paper addresses the above problems and proposes a novel nonlinear subspace clustering model via adaptive graph regularized autoencoder (NSC-AGA). This model unifies feature learning, locality preserving, and representation matrix learning into a framework, and a new adaptive graph regularizer is introduced, which takes the representation coefficient matrix as a learnable similarity graph imposed on the Euclidean distance matrix of the deep features. Two matrices interact with each other to make the representation coefficient matrix reflect both the global linear correlation and the local geometric distance relationship. A number of experimental results on the five public image database demonstrate that the proposed NSC-AGA model achieves superior clustering performance compared with the state-of-the-art methods.
BibTeX
@article{ji2019nonlinear,
  author = {Qiang Ji and Yanfeng Sun and Junbin Gao and Yongli Hu and Baocai Yin},
  title = {{Nonlinear Subspace Clustering via Adaptive Graph Regularized Autoencoder}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2920592},
}
Figure