Matrix Completion for Graph-Based Deep Semi-Supervised Learning

Fariborz Taherkhani, Hadi Kazemi, Nasser M. NasrabadiAAAI 2019 · DOI

Abstract

Training deep Convolutional Neural Networks (CNNs) is traditionally a data-intensive process, often limited by the high cost of manual labeling. This paper introduces a novel iterative framework for Semi-Supervised Learning (SSL) that integrates matrix completion with triplet loss regularization. By modeling feature-label pairs as a low-rank matrix, the proposed Graph-based Semi-supervised CNN (GSCNN) predicts labels for unlabeled data and utilizes them to refine the feature space. Evaluations on standard benchmarks like MNIST and CIFAR-10 show that GSCNN achieves competitive performance with significantly fewer labels than traditional supervised methods.

Introduction

The success of deep learning is largely predicated on the availability of large-scale labeled datasets. However, in many real-world scenarios, unlabeled data is abundant while labeled samples are scarce. Semi-Supervised Learning (SSL) seeks to exploit the underlying structure of unlabeled data to enhance model generalization. Existing Graph-Based SSL (GSSL) methods often face challenges regarding computational complexity or the use of static graphs that do not adapt as the model learns.

This work proposes an iterative approach where the graph structure and CNN features co-evolve. By combining the mathematical principles of matrix completion—based on the manifold assumption that data lies on a low-dimensional structure—with the geometric constraints of triplet loss, the authors create a robust pipeline for learning from limited supervision.

Methodology: The GSCNN Framework

The GSCNN operates through an iterative loop designed to improve both label predictions and feature representations simultaneously.

The GSCNN architecture: Matrix completion (MC) predicts labels to construct a graph for triplet regularization.

1. Feature Extraction and Matrix Completion

For each batch, the CNN extracts features for both labeled and unlabeled samples. These features, combined with the available labels, form a matrix $\mathbf{Z}$. Under the assumption that high-dimensional data resides on a low-rank manifold, the missing labels are treated as a matrix completion problem. The Soft-Impute algorithm is employed to solve a nuclear norm minimization problem, effectively "filling in the blanks" for the unlabeled nodes.

2. Graph Construction and Triplet Regularization

The predicted labels are used to construct a similarity graph where connections represent shared class membership. Unlike standard SSL methods that apply a classification loss directly to predicted labels, GSCNN utilizes this graph to mine triplets (anchor, positive, and negative samples).

3. Joint Optimization

The network is trained using a composite loss function:

  • Supervised Loss: A standard softmax cross-entropy loss applied to the ground-truth labeled data.
  • Semi-Supervised Triplet Loss: This term regularizes the feature space by pulling similar samples together and pushing dissimilar ones apart, thereby reducing intra-class variance.

To maintain efficiency, these operations are performed on local batches, avoiding the $O(n^2)$ complexity associated with global graph construction.

Experiments and Results

The model was evaluated on four benchmarks: MNIST (100 labels), SVHN (1,000 labels), NORB (1,000 labels), and CIFAR-10 (4,000 labels).

t-SNE visualization of the learned feature space, showing clear cluster separation.

GSCNN consistently outperformed contemporary SSL models. On MNIST, it achieved an error rate of 0.84%, surpassing Triple GAN (0.91%) and Ladder Networks (1.06%). On the SVHN dataset, GSCNN reached a 5.13% error rate, a significant improvement over Virtual Adversarial Training (VAT) at 24.63%. Ablation studies confirmed that the inclusion of triplet regularization provided a performance boost of up to 3.28%, highlighting the importance of the learned geometric constraints.

Conclusion

GSCNN provides a stable and efficient framework for semi-supervised learning by bridging matrix completion and deep metric learning. The iterative refinement of the feature space through triplet loss proves to be a powerful regularizer. Future research may address the sensitivity to batch composition and the computational overhead of SVD-based matrix completion, as well as the model's performance on highly imbalanced real-world datasets.

Summary updated

BibTeX
@inproceedings{taherkhani2019matrix,
  author = {Fariborz Taherkhani and Hadi Kazemi and Nasser M. Nasrabadi},
  title = {{Matrix Completion for Graph-Based Deep Semi-Supervised Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33015058},
}
Figure