Robust Triple-Matrix-Recovery-Based Auto-Weighted Label Propagation for Classification

Huan Zhang, Zhao Zhang, Mingbo Zhao, Qiaolin Ye, Min Zhang, Meng Wang

In the world of semi-supervised learning (SSL), Label Propagation (LP) is a classic. The idea is intuitive: take a few labeled examples, build a graph where similar items are connected, and let the labels "flow" from the known samples to the unknown ones. But there’s a catch. Real-world data is messy, noisy, and often corrupted. If your data is noisy, your graph connections (weights) will be wrong, and your propagated labels will be even worse.

A new paper by Huan Zhang and colleagues introduces ALP-TMR (Auto-Weighted Label Propagation via Triple Matrix Recovery), a framework designed to clean up the mess by simultaneously recovering clean data, clean labels, and clean weights.

TL;DR

ALP-TMR is a robust semi-supervised classification framework that uses a "triple matrix recovery" mechanism to jointly decompose noisy data, soft labels, and graph weights into clean components and sparse error terms. By cleaning all three elements simultaneously, it achieves state-of-the-art accuracy on face, object, and text datasets, even under heavy noise.

What Problem Does This Paper Address?

Standard Label Propagation algorithms suffer from three main headaches:

  1. Noisy Input: Real-world features are rarely "clean." Propagating labels over noisy features leads to inaccurate similarity measures.
  2. The "Mixed Sign" Problem: Soft labels (the probability-like scores assigned to classes) often contain noise and "mixed signs," where a sample might erroneously show high affinity for multiple conflicting classes.
  3. Static, Noisy Graphs: Most methods calculate graph weights once at the start. If these weights are calculated on noisy data, the errors propagate through the entire learning process.

While some newer methods try to address these individually (e.g., using sparse constraints on labels), ALP-TMR argues that these three issues are deeply interconnected and should be solved together.

Methods: The Triple Matrix Recovery (TMR)

The core innovation is the Triple Matrix Recovery mechanism. The authors model the original data ($X$), the predicted soft labels ($F$), and the graph weights ($W$) as a combination of a "clean" part and an "error" part:

  • $X = X_{clean} + E_X$
  • $F = F_{clean} + E_F$
  • $W = W_{clean} + E_W$

To handle "gross" errors and outliers, they use the $l_{2,1}$-norm on the error terms ($E_X, E_F, E_W$). This mathematical choice encourages the error matrices to be sparse, effectively "filtering out" the noise.

Key Features: * Auto-Weighting: Instead of manually picking a "kernel width" or a fixed number of neighbors (which is notoriously difficult), the model learns the weights $W$ by minimizing reconstruction errors over the recovered clean data and labels. * Joint Optimization: The algorithm iteratively updates the clean versions of $X, F,$ and $W$. This means the label propagation informs the data cleaning, and the cleaned data improves the graph weights, creating a virtuous cycle of refinement.

Datasets

The authors evaluated ALP-TMR on an extensive suite of benchmarks:

  • Face Recognition: YaleB-UMIST and CMU PIE.
  • Handwriting Digits: USPS and CASIA-HWDB1.1.
  • Object Recognition: ETH80, COIL100, and the challenging CIFAR100.
  • Text/Document Categorization: TDT2 and RCV1.

These datasets represent a wide variety of challenges, from varying lighting conditions in faces to high-dimensional sparse features in text.

Key Insights and Ideas

  • The Power of "Clean" Weights: Visualization of the recovered weight matrices (Fig. 5 in the paper) shows that ALP-TMR produces a much sharper "block-diagonal" structure than standard methods. This means it's much better at connecting samples of the same class while ignoring "inter-class" noise.
  • Label De-noising: By treating soft labels as a matrix to be recovered, the model effectively wipes away the "mixed sign" noise. The resulting soft labels are more discriminative, making the final classification much more reliable.
  • Robustness to Corruption: One of the most impressive "aha" moments is the model's performance under pixel corruption. Even when images are heavily distorted with Gaussian noise, ALP-TMR maintains high accuracy because it explicitly models that noise as the $E_X$ term.

Key Results

ALP-TMR consistently outperformed nine popular methods (including GFHF, LLGC, and AdaptiveNP).

  • Accuracy Gains: On the YaleB-UMIST face database, ALP-TMR achieved 86.45% mean accuracy, significantly higher than the baseline GFHF (71.11%).
  • Object Recognition: On COIL100, it reached 91.51% accuracy, outperforming the next best robust method, ProjLP (90.14%).
  • Text Classification: On the RCV1 dataset, it hit 88.24% accuracy, while the classic GFHF struggled at 54.74%.
  • Convergence: Despite the complex joint optimization, the model typically converges in fewer than 10 iterations, making it computationally efficient for its class.

Limitations and Future Work

While ALP-TMR is powerful, the authors note a few areas for growth:

  • Out-of-Sample Extension: Currently, handling new, unseen data requires a separate reconstruction step. The authors aim to integrate this "data inclusion" process into a single, unified model in the future.
  • Application Expansion: The current study focuses on classification. The authors suggest that this triple-recovery approach could be highly effective for other tasks like image retrieval and automated annotation.
  • Deep Learning Integration: While the paper compares ALP-TMR to deep features (like VGG16), a promising future direction is incorporating this robust label propagation directly into the loss functions of deep neural networks.

Summary updated

Abstract

The graph-based semisupervised label propagation (LP) algorithm has delivered impressive classification results. However, the estimated soft labels typically contain mixed signs and noise, which cause inaccurate predictions due to the lack of suitable constraints. Moreover, the available methods typically calculate the weights and estimate the labels in the original input space, which typically contains noise and corruption. Thus, the encoded similarities and manifold smoothness may be inaccurate for label estimation. In this article, we present effective schemes for resolving these issues and propose a novel and robust semisupervised classification algorithm, namely the triple matrix recovery-based robust auto-weighted label propagation framework (ALP-TMR). Our ALP-TMR introduces a TMR mechanism to remove noise or mixed signs from the estimated soft labels and improve the robustness to noise and outliers in the steps of assigning weights and predicting the labels simultaneously. Our method can jointly recover the underlying clean data, clean labels, and clean weighting spaces by decomposing the original data, predicted soft labels, or weights into a clean part plus an error part by fitting noise. In addition, ALP-TMR integrates the auto-weighting process by minimizing the reconstruction errors over the recovered clean data and clean soft labels, which can encode the weights more accurately to improve both data representation and classification. By classifying samples in the recovered clean label and weight spaces, one can potentially improve the label prediction results. Extensive simulations verified the effectiveness of our ALP-TMR.
BibTeX
@article{zhang2020robust,
  author = {Huan Zhang and Zhao Zhang and Mingbo Zhao and Qiaolin Ye and Min Zhang and Meng Wang},
  title = {{Robust Triple-Matrix-Recovery-Based Auto-Weighted Label Propagation for Classification}},
  journal = {IEEE Trans. Neural Networks Learn. Syst.},
  year = {2020},
  url = {https://openreview.net/forum?id=EGajyagF95},
}
Figure