Semi-supervised Orthogonal Graph Embedding with Recursive Projections

Hanyang Liu, Junwei Han, Feiping NieIJCAI 2017 · DOI

Abstract

Semi-supervised graph-based dimensionality reduction (DR) often faces constraints regarding the rigidity of linear mappings and a strict limit on output dimensionality based on the number of classes. This paper introduces Semi-supervised Orthogonal Graph Embedding with Recursive Projections (SOGE) to overcome these hurdles. SOGE utilizes orthogonal projections on the Stiefel manifold combined with a recursive learning process to preserve complex data structures and allow for high-dimensional representations beyond the class count. Evaluations across face, object, and digit recognition benchmarks show that SOGE significantly outperforms existing state-of-the-art methods, particularly in low-label scenarios.

Introduction

Dimensionality reduction is essential for handling high-dimensional data, but semi-supervised graph-based methods often encounter three significant limitations. First, traditional methods are often too rigid, assuming a strictly linear mapping that fails to capture the "wiggly" nonlinear manifolds found in real-world data. Second, many algorithms suffer from a "dimension bottleneck," where the reduced dimensionality is strictly limited to the number of classes ($c$). Finally, the lack of orthogonality in standard projections can distort Euclidean distances and lead to uneven feature weighting.

Methodology

The proposed SOGE framework addresses these issues through a three-pronged approach integrated into a single optimization framework:

  • Regression Regularization: Instead of forcing a perfect linear mapping, SOGE introduces a residue term to "soften" the projection. This allows the model to better approximate nonlinear data manifolds while remaining computationally efficient.
  • Orthogonal Constraints: By constraining the projection matrix to the Stiefel manifold ($W^T W = I$), SOGE ensures that the geometric shape of the data is preserved and different features are balanced.
  • Recursive Projections: To break the dimension bottleneck, SOGE employs a recursive strategy. After identifying an initial optimal projection, the data is projected into its orthogonal complement to find subsequent projection matrices. This allows for a final representation with $K \times c$ dimensions, capturing fine-grained details often discarded by one-shot methods.

Experimental Results

The researchers evaluated SOGE on six diverse benchmarks, including face recognition (JAFFE, AT&T, CMU-PIE), object recognition (COIL-20, MPEG7), and handwritten digits (MNIST). These datasets provide a robust test across varying illuminations, facial expressions, and geometric shapes.

Performance Comparison

SOGE consistently outperformed state-of-the-art methods such as LapRLS, SDA, TCA, and FME. The performance gains are particularly notable in scenarios with very few labeled samples. For example, on the CMU-PIE dataset with only one labeled sample per class, SOGE achieved 55.44% accuracy, far exceeding LapRLS (18.41%) and SDA (26.67%).

Performance comparison of SOGE against baseline methods across various datasets and labeled sample counts.

Dimensionality Stability

A key advantage of the recursive approach is the ability to tune the final dimensionality far beyond the number of available classes. As shown in the experimental results, classification accuracy remains remarkably stable even as the number of recursive projections increases. This allows users to choose higher dimensionalities for richer data representation without worrying about a sudden drop in classification performance.

Accuracy of SOGE as a function of dimensionality (Kc) for the COIL-20 and JAFFE datasets, demonstrating stability beyond the class-count bottleneck.

Conclusion

SOGE provides a flexible and robust framework for semi-supervised dimensionality reduction. By softening linear constraints and utilizing recursive orthogonal projections, it effectively captures complex data structures and overcomes traditional dimensionality limits. While the current implementation is efficient, future work may involve extending this framework to kernel-based or deep learning architectures to further enhance its ability to handle complex nonlinearities.

Summary updated

BibTeX
@inproceedings{liu2017semi,
  author = {Hanyang Liu and Junwei Han and Feiping Nie},
  title = {{Semi-supervised Orthogonal Graph Embedding with Recursive Projections}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/321},
}
Figure