PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Graph Learning from Noisy Data

Zhao Kang, Haiqi Pan, Steven C. H. Hoi, Zenglin Xu

arXiv:1812.06673v1cs.CVcs.AIcs.LGcs.MM

TL;DR

Noisy raw data can make automatically learned graphs unreliable for downstream learning. The paper jointly separates clean low-rank data from errors and learns an adaptive graph from the clean component, reporting improved clustering, semisupervised classification, and recovery across benchmark tasks.

  • Problem

    Automatically learned graphs may be inexact or unreliable when constructed from contaminated raw data, limiting graph-based clustering and semisupervised learning.

  • Method

    The model jointly decomposes observations into clean low-rank data and sparse errors while adaptively learning the graph from the clean data.

  • Results

    The method outperforms various state-of-the-art clustering, semisupervised classification, and data recovery techniques across benchmark experiments.

  • Takeaways & Limitations

    Graph construction from recovered clean data and graph smoothness regularization support improved graph quality and low-rank recovery within the evaluated applications.

Abstract

from arXiv · show

Learning graphs from data automatically has shown encouraging performance on clustering and semisupervised learning tasks. However, real data are often corrupted, which may cause the learned graph to be inexact or unreliable. In this paper, we propose a novel robust graph learning scheme to learn reliable graphs from real-world noisy data by adaptively removing noise and errors in the raw data. We show that our proposed model can also be viewed as a robust version of manifold regularized robust PCA, where the quality of the graph plays a critical role. The proposed model is able to boost the performance of data clustering, semisupervised classification, and data recovery significantly, primarily due to two key factors: 1) enhanced low-rank recovery by exploiting the graph smoothness assumption, 2) improved graph construction by exploiting clean data recovered by robust PCA. Thus, it boosts the clustering, semi-supervised classification, and data recovery performance overall. Extensive experiments on image/document clustering, object recognition, image shadow removal, and video background subtraction reveal that our model outperforms the previous state-of-the-art methods.

1 Introduction

The paper addresses unreliable graphs learned from contaminated data by jointly learning clean data and graph structure. It targets clustering, semisupervised classification, and low-rank recovery, reporting broad empirical effectiveness.

  • Motivation: Graph quality is crucial for spectral clustering and graph-based semisupervised classification because both rely on relationships encoded by graph edges.Spectral clustering uses the graph spectrum, while semisupervised classification infers labels through local graph smoothness.
  • Motivation: Existing adaptive graph methods automatically select informative neighbors but generally learn from raw data that may be contaminated, producing inexact or sub-optimal relationships.Their similarity measures are intended to avoid manually chosen metrics, yet the raw-data dependence leaves them sensitive to noise and outliers.
  • Contribution: The proposed robust graph learning scheme decomposes raw data into clean and error parts while jointly learning the graph and clean data in one unified model.This replaces a sequential cleaning-then-graph-construction strategy with mutual enhancement through joint optimization.
  • Contribution: The model also acts as a robust graph-Laplacian-regularized RPCA method, using graph smoothness to enhance low-rank recovery and clean data to improve graph construction.The paper identifies these two mutually reinforcing components as central to its gains.
  • Evaluation: Extensive experiments cover face and document clustering, face/object recognition, shadow removal, and video background separation.The paper presents these applications as evidence of the proposed technique’s effectiveness.

2 Adaptive Neighbor Graph Learning Revisited

Adaptive neighbor graph learning assigns neighborhood probabilities from data distances and uses them as similarities. Its central weakness is sensitivity to noisy raw inputs, motivating robustification.

  • Adaptive neighbor graph: Adaptive neighbor learning treats sij as the probability that xj is a neighborhood point of xi, with larger values assigned to closer data points.The learned probabilities define the graph similarities.
  • Adaptive neighbor graph: The graph is learned by optimizing an objective involving graph smoothness and a regularization term, subject to row-sum and bounded-weight constraints.The associated graph Laplacian is defined from S and its degree matrix.
  • Adaptive neighbor graph: Unlike LPP’s predetermined neighborhood relationships, adaptive graph learning automatically discovers structure from the data and has been used in clustering, NMF, feature selection, and multiview learning.The learned graph can preserve local manifold structure across these applications.
  • Limitation: The method is highly sensitive to noisy input because S is constructed directly from corrupted raw data, which deteriorates performance.This motivates a principle for robust graph learning.

3 Robust Graph Construction

Robust graph construction jointly decomposes observations into clean low-rank data and sparse errors while learning an adaptive graph from the clean component. An alternating ADMM-based procedure updates the model variables until convergence.

  • 3.1 Formulation: The model assumes X = D + E, where D is clean low-rank data and E represents sparse corruptions, then learns the graph from D.Graph learning and noise removal are optimized jointly rather than performed as separate preprocessing and analysis stages.
  • 3.1 Formulation: The formulation is a manifold-regularized RPCA model: it retains RPCA’s decomposition while assuming the low-rank data lie on a smooth manifold.This is described as an MRPCA model.
  • 3.1 Formulation: Constructing the graph on clean data is intended to improve graph quality for clustering and semisupervised classification.The graph is learned jointly with the recovered data, allowing the two components to mutually enhance one another.
  • 3.1 Formulation: The graph smoothness regularizer is intended to enhance low-rank recovery, while adaptive graph learning is intended to improve robustness to noise and outliers.These are presented as distinct advantages of the objective.
  • 3.2 Optimization Algorithm: ADMM solves the constrained formulation by alternating updates of D, E, S, Z, and the Lagrange multipliers.The D update uses singular value shrinkage, the E update has a closed form, and S is updated through its adaptive-neighbor subproblem.
  • 3.2 Optimization Algorithm: The adaptive-neighbor subproblem yields a sparse graph by updating only k nearest neighbors, with k positive entries per row and the remaining entries zero.The algorithm sets γ using averaged γi values so the average number of nonzero row entries stays close to k.
  • 3.2 Optimization Algorithm: The main computational costs are SVD and matrix inversion, each having general complexity O(n3).Partial SVD is suggested as a way to accelerate the computation.

4 Experiments on Clustering

The experiments evaluate robust graph construction for clustering across eight benchmark datasets, using standard clustering metrics and comparisons with representative methods. The proposed RGC method generally achieves stronger results, while parameter and convergence analyses examine its behavior.

  • Experimental setup: RGC is evaluated against representative graph-learning and clustering methods on eight publicly available datasets, including face, image, binary-alpha, and text datasets.Several datasets contain severe corruption from illumination conditions or other configurations.
  • Evaluation metrics: The clustering evaluation uses accuracy (Acc), normalized mutual information (NMI), and Purity.Acc measures cluster–class correspondence, NMI measures clustering quality, and Purity measures the prevalence of the most common category within clusters.
  • Results: RGC outperforms CAN in all reported cases and improves CAN’s Acc from 36.83%, 38.89%, and 56.96% to 51%, 71.37%, and 75.51% on BA, TR41, and TR45.The comparison is attributed to constructing the graph from clean data rather than raw data.
  • Results: RGC performs better than SSR and TLSC in most cases and much better than MRPCA in all cases, while also improving over RKKM and SC.The paper relates these gains to noise removal and adaptive graph learning.
  • Parameter analysis: The model works well across a wide range of β and µ values, and the objective-function optimization is reported to converge.The experiments fix α according to RPCA, use k = 10, and select β by cross validation.

5 Semisupervised Classification

The method is evaluated for semisupervised classification using an RGC-learned graph with LGC, and it consistently outperforms comparison methods, especially with few labels.

  • Method: RGC first obtains a graph matrix S, which is then used by local and global consistency (LGC) for semisupervised classification.The classification function is learned using the graph Laplacian calculated from S.
  • Comparison Algorithms: The comparison includes LGC, GFHF, SCAN, and self-expression graph-based methods including S2LRR and S3R.
  • Results: RGC consistently outperforms existing techniques across labeling ratios of 10%, 30%, and 50%.Accuracy is averaged over 20 random label selections with deviations reported.
  • Results: The improvements over LGC are attributed to noise removal and higher-quality learned graph construction rather than manually built graphs.LGC directly adopts a manually built graph, whereas RGC uses the learned graph S.
  • Results: RGC's gains are more considerable when the labeling ratio is low, supporting applications with extremely rare labeled instances.
  • Parameter Sensitivity: On YALE, k = 5 often produces the highest accuracy, although the reported Tables 2 and 3 results use k = 10.The algorithm also provides reasonable results across a wide range of β values.

6 Experiments on Data Recovery

The data-recovery experiments assess RGC on face-image shadow removal and video-background extraction, comparing it with established RPCA variants and related methods.

  • Experimental Tasks: The recovery evaluation focuses on shadow removal from face images and static-background extraction from videos.These are presented as two practical low-rank recovery tasks.
  • Comparison Methods: RGC is compared with RPCA, CRPCA, and NRPCA while incorporating manifold smoothness and retaining the convex nuclear norm.
  • Shadow Removal: For Extended Yale B, the experiment uses 64 vectorized face images of size 192×168 under different lighting conditions.The resulting data matrix has size X ∈ R^32256×64.
  • Shadow Removal: RGC totally removes specularities and shadows in the example face-image recovery, while other methods retain artifacts, especially RPCA and CRPCA.

7 Conclusion

The paper presents RGC as a robust graph-learning model that learns reliable graphs from raw data and improves clustering, semisupervised classification, and low-rank recovery.

  • RGC addresses robustness in adaptive-neighbor graph learning by learning reliable graphs from raw data.
  • The framework generalizes Robust PCA by leveraging graph regularization on the low-rank representation.
  • Experiments report improvements in clustering, semisupervised classification, and data recovery on several benchmark datasets.
Loading 1812.06673v1…