Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification

Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, Yu Sun

TL;DR

This paper introduces UniMP, a novel message-passing model that unifies feature and label propagation for semi-supervised graph classification. By incorporating a "masked label prediction" strategy during training, UniMP effectively prevents label leakage and achieves state-of-the-art results on challenging graph datasets.

What Problem Does This Paper Address?

Semi-supervised node classification on graphs is a crucial task with applications ranging from recommendation systems to drug discovery. Traditional approaches often rely on either Graph Neural Networks (GNNs) for feature propagation or Label Propagation Algorithms (LPAs) for label propagation. While both methods have shown success, directly combining their strengths within a unified message-passing framework has been challenging. Existing methods often treat feature and label propagation separately or only use label information indirectly. This paper aims to bridge this gap by proposing a model that can effectively leverage both feature and label information simultaneously during both training and inference.

Methods

The core of UniMP lies in its Unified Message Passing Model (UniMP), which integrates feature and label propagation.

  • Graph Transformer: UniMP employs a Graph Transformer network as its backbone. This allows for attentive information propagation between nodes, taking both node features and (embedded) labels as input.
  • Label Embedding: Partially observed labels are embedded into the same feature space as node features. This allows them to be treated similarly to node features within the message-passing framework.
  • Masked Label Prediction: A key innovation is the introduction of a "masked label prediction" strategy during training. Inspired by BERT's masked language modeling, UniMP randomly masks a percentage of the input labels and trains the model to predict these masked labels. This prevents "label leakage" (where the model learns to predict labels it's already seen in the training set) and encourages the model to learn more robust representations by relying on both features and neighborhood information.
  • Gated Residual Connections: To combat over-smoothing, a common issue in deep graph networks, UniMP incorporates gated residual connections between layers.

Datasets

The experiments were conducted on the Open Graph Benchmark (OGB), specifically focusing on the Node Property Prediction tasks:

  • ogbn-products: A large-scale dataset for multi-class classification.
  • ogbn-proteins: A dataset for binary classification, notable for including edge features.
  • ogbn-arxiv: A dataset for multi-class classification.

The paper highlights that these OGB datasets are designed to overcome the limitations of smaller, older graph datasets, offering more realistic splits and challenging scenarios.

Key Insights and Ideas

  • Unifying Feature and Label Propagation is Powerful: The paper strongly suggests that effectively combining feature and label propagation within a single message-passing framework leads to significant performance gains, outperforming models that focus solely on one aspect.
  • Masked Label Prediction is Crucial for Training: The "masked label prediction" strategy is not just a training trick; it's essential for preventing label leakage and enabling the model to learn robustly from partially labeled data. This approach effectively simulates the process of propagating labels from labeled to unlabeled nodes.
  • Label Information is Highly Informative: The results indicate that even with just labels and graph structure (without node features), performance can be competitive, underscoring the inherent value of label information in semi-supervised settings.
  • Neighborhood Matters: The experimental results show that nodes with more neighbors tend to achieve higher accuracy, reinforcing the importance of graph structure in propagating information.

Key Results

UniMP achieved state-of-the-art results on all three OGBN datasets:

  • ogbn-products: 82.56% Accuracy.
  • ogbn-proteins: 86.42% ROC-AUC.
  • ogbn-arxiv: 73.11% Accuracy.

These results represent absolute improvements of 0.6-1.6% over existing state-of-the-art methods. Ablation studies further demonstrated the effectiveness of each component of UniMP, particularly the unified approach and the masked label prediction strategy.

Limitations and Future Work

  • Label Rate Tuning: The paper notes that the optimal label_rate for masked label prediction is around 0.625, suggesting that careful tuning of this hyperparameter is important for achieving peak performance.
  • Inference vs. Training Discrepancy: While training uses masked labels, inference utilizes all available labels. The paper acknowledges this slight inconsistency and investigates its impact, finding that performance can be sensitive to the label_rate during inference.
  • Future Work: The paper implicitly suggests that further exploration of how to best leverage progressively accumulating labeled data during inference, without retraining, could be a fruitful direction. The unified framework also opens doors for extending this approach to other graph-based tasks.

Summary updated

Abstract

Graph neural network (GNN) and label propagation algorithm (LPA) are both message passing algorithms, which have achieved superior performance in semi-supervised classification. GNN performs feature propagation by a neural network to make predictions, while LPA uses label propagation across graph adjacency matrix to get results. However, there is still no effective way to directly combine these two kinds of algorithms. To address this issue, we propose a novel Unified Message Passaging Model (UniMP) that can incorporate feature and label propagation at both training and inference time. First, UniMP adopts a Graph Transformer network, taking feature embedding and label embedding as input information for propagation. Second, to train the network without overfitting in self-loop input label information, UniMP introduces a masked label prediction strategy, in which some percentage of input label information are masked at random, and then predicted. UniMP conceptually unifies feature propagation and label propagation and is empirically powerful. It obtains new state-of-the-art semi-supervised classification results in Open Graph Benchmark (OGB).
BibTeX
@inproceedings{shi2021masked,
  author = {Yunsheng Shi and Zhengjie Huang and Shikun Feng and Hui Zhong and Wenjing Wang and Yu Sun},
  title = {{Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/214},
}
Figure