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_ratefor 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_rateduring 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