Source-linked AI summary
Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, Yu Sun
TL;DR
Semi-supervised classification has lacked an effective model that directly combines GNN feature propagation with LPA label propagation during both training and inference. UniMP uses a Graph Transformer with feature and label embeddings plus masked label prediction, and reports new state-of-the-art results across three OGB tasks. Its ablations further examine the contribution of label propagation and input-label rates.
Problem
Existing methods do not directly incorporate GNN feature propagation and LPA label propagation within one message passing model during both training and inference.
Method
UniMP combines feature and label propagation in a Graph Transformer and uses masked label prediction to reduce overfitting to self-loop label information.
Results
UniMP achieves new state-of-the-art results on three OGB tasks: 82.56% ACC on ogbn-products, 86.42% ROC-AUC on ogbn-proteins, and 73.11% ACC on ogbn-arxiv.
Takeaways & Limitations
Ablation studies support unifying feature and label propagation, and additional labels can boost performance without retraining from scratch.
Abstract
from arXiv · showhide
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).
1 Introduction
Semi-supervised node classification commonly uses feature propagation through GNNs or label propagation through LPAs, but existing methods do not directly combine both during training and inference. UniMP addresses this gap with joint feature-label propagation and masked label prediction, achieving state-of-the-art results across three OGB tasks.
- Existing message passing methods: GNNs propagate and aggregate node features through neural layers, whereas LPAs iteratively propagate labels across graph connections.Both approaches support predictions for unlabeled nodes in semi-supervised node classification.
- Research gap: Existing combinations such as APPNP, TPN, and GCN-LPA do not directly propagate features and labels in both training and inference.They either propagate predicted soft labels or use label propagation as a training regularizer.
- UniMP approach: UniMP jointly incorporates node features and labels in both training and inference using a unified message passing model.It transforms partially observed labels into dense embeddings alongside node features.
- UniMP approach: Masked label prediction randomly hides some training labels and predicts them to prevent overfitting to self-loop label inputs.The strategy simulates transducing label information from labeled to unlabeled graph nodes.
- Results: 82.56% ACC on ogbn-products, 86.42% ROC-AUC on ogbn-proteins, and 73.11% ACC on ogbn-arxiv are reported as new state-of-the-art results.The evaluation covers three semi-supervised classification datasets in the Open Graph Benchmark.
2 Preliminaries
The paper formulates graph-based semi-supervised classification using node features, target labels, adjacency, and degree matrices. It reviews GNN feature propagation, LPA label propagation, and prior indirect combinations of the two.
- Notation: A graph is represented as G = (V, E), with node features X, target classes Y, adjacency matrix A, and diagonal degree matrix D.The degree of node i is defined from the adjacency entries, and D^-1A is adopted as the normalized adjacency matrix.
- Graph Neural Networks: GCN transforms and propagates node features across graph layers to approximate the mapping X → Y.The model uses linear transformations, nonlinear activation, and a final output layer for prediction.
- Label propagation algorithms: LPA predicts using labels and graph relations by iteratively propagating an initial label matrix through the normalized adjacency matrix D^-1A.Labeled nodes begin with one-hot indicators, while unlabeled nodes begin with zero vectors.
- Combining GNN and LPA: APPNP and TPN propagate GCN-predicted soft labels, while GCN-LPA uses label propagation indirectly to regularize GNN edge weights.UniMP instead combines feature and label propagation directly within one network during training and prediction.
3 Unified Message Passing Model
UniMP combines node features and partially observed labels within a Graph Transformer, using masked label prediction to avoid label leakage during training. Its message passing framework propagates both information sources during training and inference.
- Graph Transformer: A Graph Transformer replaces normalized adjacency with multi-head attention for message passing over graph edges.Edge features are encoded into the key vector, and transformed neighbor values are aggregated using attention weights.
- Graph Transformer: A gated residual connection is used between layers to prevent oversmoothing.The final output layer averages multi-head outputs and removes the nonlinear transformation.
- Label and feature propagation: UniMP jointly uses node features and partially observed labels as propagation inputs in both training and inference.Labels are embedded into the same space as node features, with zero vectors for unlabeled nodes.
- Label and feature propagation: Adding embedded labels to node features unifies label propagation and feature propagation within one shared message passing framework.The model’s hidden representation can be approximately decomposed into separate propagated feature and label components.
- Masked label prediction: Masked label prediction prevents training-time leakage from self-loop label information by masking input labels and predicting them.At inference, UniMP uses all observed labels as input to predict the remaining unlabeled nodes.
4 Experiments
Experiments evaluate UniMP on realistic OGB node-classification datasets, compare it with strong baselines, and analyze how label propagation and model components affect performance.
- Comparison with SOTA Models: UniMP outperforms comparative models across three OGBN datasets, achieving state-of-the-art results on products, proteins, and arxiv.The reported scores are 82.56% ACC, 86.42% ROC-AUC, and 73.11% ACC, respectively.
- Comparison with SOTA Models: 82.56% ACC on ogbn-products and 86.42% ROC-AUC on ogbn-proteins improve over newly reported SOTA methods by about 0.6–1.6% absolute.
- Comparison with SOTA Models: 73.11% ACC on ogbn-arxiv improves over GCNII by 0.37% absolute despite using four times fewer parameters.
- Ablation Studies: Models using observed labels with features and adjacency outperform models using only features, showing the value of jointly incorporating feature and label propagation.
- Relation between Label Coverage and Performance: UniMP performs best at an input label rate of about 0.625, and label propagation benefits more as the labeled-data proportion increases.
- Relation between Label Coverage and Performance: At inference, lowering the label rate can reduce UniMP accuracy below baseline, whereas increasing label coverage raises performance to 0.73; nodes with more neighbors also achieve higher accuracy.
5 Conclusion
UniMP jointly performs feature and label propagation within a Graph Transformer for semi-supervised node classification, using masked label prediction to prevent overfitting on self-loop label information. Experiments report improved performance across three OGBN datasets, with ablations supporting the unified approach.
- UniMP jointly performs feature propagation and label propagation within a Graph Transformer for semi-supervised classification.
- Masked label prediction prevents overfitting to self-loop label information during supervised training.
- UniMP outperforms previous state-of-the-art models on ogbn-products, ogbn-proteins, and ogbn-arxiv by a large margin.
- Ablation studies demonstrate the effectiveness of unifying feature propagation and label propagation.