RARE: Robust Masked Graph Autoencoder

Wenxuan Tu, Qing Liao, Sihang Zhou, Xin Peng, Chuan Ma, Zhe Liu, Xinwang Liu, Zhiping Cai, Kunlun He

TL;DR

RARE (Robust mAsked gRaph autoEncoder) improves self-supervised graph pre-training by moving beyond simple raw data reconstruction. By predicting and matching masked nodes in a high-order latent feature space alongside the traditional raw attribute space, RARE achieves significantly higher stability and performance, particularly on noisy or complex non-Euclidean datasets.

What Problem Does This Paper Address?

Masked Autoencoders (MAEs) have been wildly successful in Computer Vision and NLP. The idea is simple: hide part of the data (like an image patch or a word) and task the model with reconstructing it. However, the authors argue that applying this directly to graphs is problematic.

Unlike images (where a dog's eye is predictably near its nose) or text (where grammar provides strong context), graphs are non-Euclidean. Local connections in a social or biological network are often "unstable"—masking a single node can create massive structural ambiguity. If a model only tries to reconstruct raw, low-level attributes from this unstable neighborhood, it often ends up with unreliable self-supervision signals, leading to poor representations for downstream tasks like classification.

Methods

The authors propose a framework called RARE, which introduces a Masked Latent Feature Completion (MLFC) scheme. The process works in three main stages:

  1. Dual Masking: The graph is partitioned into visible and masked nodes.
  2. Latent Feature Prediction:
    • An Online Graph Encoder processes visible nodes to create representations.
  3. A Latent Feature Predictor then tries to guess the latent representations of the masked nodes based on those visible ones.
  4. Crucially, a Momentum Graph Encoder (which is a slowly moving average of the online encoder, inspired by BYOL) processes the raw data of the masked nodes to provide a stable "target" for the predictor to match.
  5. Joint Reconstruction: The model minimizes two losses simultaneously:
  6. Latent Matching Loss ($L_M$): Ensures the predicted latent features match the momentum encoder's output.
  7. Raw Attribute Reconstruction Loss ($L_R$): Uses a decoder to map the latent features back to the original raw attribute space (e.g., node features).

By matching in the latent space, the model captures high-order correlations and structural patterns that are invisible in the raw data alone.

Datasets

The authors evaluated RARE on a massive suite of 17 datasets across three categories:

  • Node Classification: Cora, Citeseer, Pubmed, WikiCS, Corafull, Flickr, and Yelp.
  • Graph Classification: IMDB-B, IMDB-M, PROTEINS, COLLAB, MUTAG, PTC-MR, and NCI1.
  • Image Classification (treated as graphs): Usps, Mnist, and Fashion-mnist.

Key Insights and Ideas

  • Latent Space is More Stable: The "aha moment" is that while raw node attributes might be noisy or ambiguous, the high-dimensional latent space provides a more "certain" signal for the model to learn from.
  • Implicit vs. Explicit Supervision: Traditional MGAEs use explicit supervision (reconstructing the input). RARE adds implicit supervision (matching latent states), which acts as a powerful regularizer.
  • Pushing Categories Apart: Theoretical analysis and visualizations (T-SNE) show that RARE's latent matching helps the model better differentiate between nodes of different categories that might share a common neighbor, a scenario where previous models like GraphMAE often struggled.
  • Robustness to Noise: RARE is significantly more robust to "outliers" (nodes with shuffled features). While other models' performance drops sharply with 5% noise, RARE maintains high accuracy and training stability.

Key Results

  • SOTA Performance: RARE consistently outperformed state-of-the-art competitors (like GraphMAE and MaskGAE). On large-scale datasets like Flickr and Yelp, it improved accuracy by margins of 7.7% to 14.8% over supervised baselines.
  • Efficiency: Despite the extra latent prediction step, RARE remains computationally efficient and scales linearly with the number of nodes and edges, making it suitable for large-scale graphs.
  • Image Benchmarks: Even on image datasets (converted to graphs), RARE outperformed specialized edge-masking and node-masking models by up to 7.1%.

Limitations and Future Work

The authors identify a few areas for improvement:

  • Local Focus: The current version of RARE primarily reconstructs masked nodes from their immediate adjacent neighbors via graph attention layers.
  • Global Features: Future work could involve developing MGAEs that explore global structural features, allowing the model to understand the "big picture" of the graph rather than just local neighborhoods.
  • Incomplete Data: The authors suggest extending RARE to "data-incomplete" scenarios where some information is missing from the start, rather than just being masked during training.

Summary updated

Abstract

Masked graph autoencoder (MGAE) has emerged as a promising self-supervised graph pre-training (SGP) paradigm due to its simplicity and effectiveness. However, existing efforts perform the mask-then-reconstruct operation in the raw data space as is done in computer vision (CV) and natural language processing (NLP) areas, while neglecting the important non-Euclidean property of graph data. As a result, the highly unstable local structures largely increase the uncertainty in inferring masked data and decrease the reliability of the exploited self-supervision signals, leading to inferior representations for downstream evaluations. To address this issue, we propose a novel SGP method termed R obust m A sked g R aph auto E ncoder (RARE) to improve the certainty in inferring masked data and the reliability of the self-supervision mechanism by further masking and reconstructing node samples in the high-order latent feature space. Through both theoretical and empirical analyses, we have discovered that performing a joint mask-then-reconstruct strategy in both latent feature and raw data spaces could yield improved stability and performance. To this end, we elaborately design a masked latent feature completion scheme, which predicts latent features of masked nodes under the guidance of high-order sample correlations that are hard to be observed from the raw data perspective. Specifically, we first adopt a latent feature predictor to predict the masked latent features from the visible ones. Next, we encode the raw data of masked samples with a momentum graph encoder and subsequently employ the resulting representations to improve the predicted results through latent feature matching. Extensive experiments on seventeen datasets have demonstrated the effectiveness and robustness of RARE against state-of-the-art (SOTA) competitors across three downstream tasks.
BibTeX
@article{tu2024rare,
  author = {Wenxuan Tu and Qing Liao and Sihang Zhou and Xin Peng and Chuan Ma and Zhe Liu and Xinwang Liu and Zhiping Cai and Kunlun He},
  title = {{RARE: Robust Masked Graph Autoencoder}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2024},
  url = {https://openreview.net/forum?id=90hTA48WK3},
}

Loading related content...

Figure