Robust Graph Representation Learning for Local Corruption Recovery

Bingxin Zhou, Yuanhong Jiang, Yuguang Wang, Jingwei Liang, Junbin Gao, Shirui Pan, Xiaoqun Zhang

TL;DR

This paper introduces MAGNET, a novel framework for robust graph representation learning that tackles the problem of corrupted node attributes. By combining a graph autoencoder for anomaly detection with an inertia ADMM optimizer and framelet-based regularization, MAGNET effectively identifies and recovers from local corruptions, leading to significantly improved performance on downstream tasks.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) have become incredibly powerful for learning from graph-structured data. However, their performance is highly sensitive to the quality of the input graph, particularly the node features. While much research has focused on smoothing out global noise or handling edge corruptions, this paper highlights a critical vulnerability: local corruptions in node attributes. These anomalies, like fake user profiles in social networks or mislabeled items in recommender systems, can severely degrade GNN performance by propagating misleading information. Existing methods often struggle to precisely identify and correct these localized attribute errors without sacrificing valuable information or introducing over-smoothing.

Methods

MAGNET employs a two-pronged strategy: detect and recover.

  1. Anomaly Detection (Mask Matrix Generation):
    • A Graph Autoencoder (GAE) is trained to reconstruct the input graph features. The assumption is that corrupted attributes will lead to higher reconstruction errors.
  2. The difference between the original and reconstructed features is used to generate a mask matrix. This matrix highlights the likely positions of corrupted node attributes. Crucially, this detection is unsupervised and makes no assumptions about the distribution of the corruptions.
  3. Robust Representation Recovery:
    • An inertia ADMM optimizer is used to learn a robust graph representation.
  4. This optimization leverages a framelet-based regularization technique. Framelets are well-suited for capturing both global and local information in graph signals. By applying sparsity-promoting regularization in the framelet domain, MAGNET can effectively denoise the graph while preserving fine-grained local patterns.
  5. The optimization objective is designed to be conditionally close to the input observations, meaning it prioritizes accurate reconstruction only at the locations identified as potentially corrupted by the mask matrix.

Datasets

The paper evaluates MAGNET on eight benchmark datasets:

  • Citation Networks: Cora, Citeseer, PubMed
  • Other Graph Datasets: Wiki-CS, Coauthor-CS, OGB-arxiv, Wisconsin, Texas

These datasets cover a range of characteristics, including heterophilic and homophilic graphs, varying feature dimensions, and different graph sizes. The authors do not introduce new benchmarks but rather use established datasets to demonstrate the robustness of their method against common poisoning attacks.

Key Insights and Ideas

  • Local attribute corruption is a significant threat: The paper convincingly argues that localized, subtle corruptions in node features are as detrimental as global noise or edge attacks, and often overlooked.
  • Unsupervised mask generation is key: The ability of the GAE to generate a mask without prior knowledge of anomaly types or distributions is a major advantage, making the method broadly applicable.
  • Framelets for targeted denoising: Using framelet transforms allows for a multi-scale analysis of graph signals, enabling MAGNET to denoise effectively by focusing on high-frequency components that often contain anomalies, while preserving low-frequency global structure.
  • Conditional recovery is more effective: By using the generated mask to guide the recovery process, MAGNET avoids over-smoothing and preserves the integrity of clean node attributes.

Key Results

  • Superior performance on corrupted graphs: MAGNET consistently outperforms baseline GCN and other robust graph learning methods (APPNP, GNNGUARD, ELASTICGNN, AIRGNN) under both attribute injection and meta-attack scenarios.
  • Significant accuracy gains: On corrupted graphs, MAGNET achieved up to a 94% test accuracy recovery for homophilic graphs and over 180% improvement for heterophilic graphs (Wisconsin dataset).
  • Competitive computational cost: Despite its sophisticated approach, MAGNET achieves comparable or better performance than baselines with reasonable training times, especially when considering the efficiency of mask approximation.
  • Reliable mask approximation: The paper demonstrates that the GAE-generated mask captures a significant portion of true anomalies, providing a solid foundation for the subsequent recovery phase.

Limitations and Future Work

  • Mask approximation recall: While effective, the GAE-generated mask doesn't perfectly capture all anomalies. The paper shows it can seize around 60% of anomalies in some cases, suggesting room for improvement in mask quality.
  • Heterophilic graph potential: The paper notes that MAGNET shows promising results on heterophilic graphs, but suggests further investigation into its representation power for such graph structures.
  • Hyperparameter tuning: Like most deep learning models, MAGNET's performance is sensitive to hyperparameter choices, though the paper provides a search space.
  • Future work: The authors suggest exploring faster mask approximation tools and investigating the model's efficiency with fewer training epochs for the GAE. Further research into handling heterophilic graphs is also implied.

Summary updated

Abstract

The performance of graph representation learning is affected by the quality of graph input. While existing research usually pursues a globally smoothed graph embedding, we believe the rarely observed anomalies are as well harmful to an accurate prediction. This work establishes a graph learning scheme that automatically detects (locally) corrupted feature attributes and recovers robust embedding for prediction tasks. The detection operation leverages a graph autoencoder, which does not make any assumptions about the distribution of the local corruptions. It pinpoints the positions of the anomalous node attributes in an unbiased mask matrix, where robust estimations are recovered with sparsity promoting regularizer. The optimizer approaches a new embedding that is sparse in the framelet domain and conditionally close to input observations. Extensive experiments are provided to validate our proposed model can recover a robust graph representation from black-box poisoning and achieve excellent performance.
BibTeX
@inproceedings{zhou2023robust,
  author = {Bingxin Zhou and Yuanhong Jiang and Yuguang Wang and Jingwei Liang and Junbin Gao and Shirui Pan and Xiaoqun Zhang},
  title = {{Robust Graph Representation Learning for Local Corruption Recovery}},
  booktitle = {The Web Conference},
  year = {2023},
  doi = {10.1145/3543507.3583399},
}
Figure