Robust Graph Representation Learning for Local Corruption Recovery

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

TL;DR

MAGnet is a new "detect-and-then-recover" framework designed to protect Graph Neural Networks (GNNs) from local attribute corruptions. By combining an unsupervised graph autoencoder for anomaly detection with a multi-scale framelet optimizer, it successfully pinpoints and repairs poisoned node features, outperforming standard robust GNNs on both homophilic and heterophilic datasets.

What Problem Does This Paper Address?

Graph representation learning has seen massive success, but it has a "garbage in, garbage out" problem. Real-world graphs are often riddled with inaccuracies—think fraudulent users in a social network faking their profiles or sensor errors in a biological network.

Most existing defenses focus on global noise (smoothing everything out) or structural attacks (rewiring edges). However, local corruptions in node attributes are particularly insidious. Because GNNs work by aggregating information from neighbors, a single corrupted node can "poison" the latent representations of its entire neighborhood. Standard smoothing techniques often fail here because they either blur out important local details or fail to distinguish between a legitimate outlier and a malicious corruption.

Methods

The authors propose MAGnet (Mask, ADMM, and Graph), which operates in two distinct phases:

  1. Mask Matrix Generation: The model uses an unsupervised Graph Autoencoder (GAE) to reconstruct the input graph. The intuition is that corrupted attributes will have significantly higher reconstruction errors than clean ones. By applying a tunable threshold to these errors, MAGnet generates a "mask matrix" that identifies exactly which attributes of which nodes are likely compromised.
  2. Robust Recovery via Framelets: Once the "where" is identified, the model needs to figure out the "what"—the true underlying signal. MAGnet formulates an optimization problem that balances two goals: staying close to the observed data (where it isn't masked) and maintaining sparsity in the framelet domain.
Figure 1: Illustrative architecture of the proposed MAGnet. Input feature attributes (gray) are assumed locally corrupted. The first module constructs a mask matrix (red) as the indices of locally-corrupted input feature attributes (gray). They are sent to an inertia ADMM optimizer (yellow) to iterate a robust feature representation, which is functioned as hidden embeddings by typical graph convolutional layers. It can be encoded by other convolutions or sent to a predictor (blue).

Unlike standard graph convolutions that just smooth data, graph framelets allow for multi-scale analysis. This means the model can remove high-frequency noise while preserving the low-frequency global trends and important local patterns. To solve this complex optimization efficiently, the authors employ an inertial ADMM (Alternating Direction Method of Multipliers) algorithm, which provides fast convergence.

Datasets

The researchers evaluated MAGnet across eight diverse benchmarks:

  • Citation Networks: Cora, Citeseer, PubMed, and OGB-arxiv (large-scale).
  • Knowledge/Social Graphs: Wiki-CS and Coauthor-CS.
  • Heterophilic Graphs: Wisconsin and Texas (where connected nodes often have different labels).

To test robustness, they applied two types of "black-box" poisoning: attribute injection (swapping attributes with distant samples) and meta-attacks (using gradients to find the most damaging perturbations).

Key Insights and Ideas

  • Local vs. Global: The paper argues that "globally smoothed" embeddings (the default for many GNNs) are a double-edged sword. While they remove noise, they also kill the expressivity needed to handle rare but important anomalies.
  • The Power of the Mask: By explicitly labeling suspicious attributes rather than just smoothing the whole feature matrix, MAGnet avoids the "over-smoothing" pitfall. It only "fixes" what it thinks is broken.
  • Framelets over Dirichlet Energy: Most GNNs minimize Dirichlet energy to ensure smoothness. MAGnet uses framelets because they provide a more granular, multi-scale view of the graph signal, allowing it to distinguish between "meaningful detail" and "random noise."
  • Thresholding Sparsity: The sparsity of the generated mask is directly controllable. As shown in the paper's analysis, a higher threshold leads to a sparser mask, allowing practitioners to tune the sensitivity of the detection module based on the expected level of corruption.
Figure 2: The sparsity of GAE-approximated 1 −𝑴is directly controlled by the threshold 𝜏.

Key Results

MAGnet demonstrated significant performance gains over state-of-the-art baselines like GNNGuard, ElasticGNN, and AirGNN:

  • Accuracy Recovery: On homophilic graphs (like Cora), MAGnet recovered up to 94% of the test accuracy lost to perturbations.
  • Heterophilic Superiority: The model was surprisingly effective on heterophilic graphs. On the Wisconsin dataset, MAGnet's performance on a corrupted graph was actually higher than a standard GCN's performance on a clean graph, showing a relative improvement of over 180%.
  • Efficiency: Despite the two-stage process, MAGnet's computational cost remains competitive. On the large OGB-arxiv dataset, it achieved significantly higher accuracy than baselines with comparable training times.

Limitations and Future Work

While MAGnet is robust, its success relies heavily on the initial GAE's ability to detect anomalies. If the corruption is so subtle that the autoencoder reconstructs it perfectly, the mask will fail to catch it.

The authors also noted that while the results on heterophilic graphs (like Wisconsin and Texas) were excellent, the underlying reasons for this success deserve deeper investigation. Future work could involve refining the mask approximation tools to be even faster and exploring how this "detect-and-recover" logic might be applied to structural (edge-based) attacks.

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 Yu Guang 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