TL;DR
LEGNN (Label-Enhanced Graph Neural Network) transforms semi-supervised node classification by treating labels as "virtual center" nodes in a heterogeneous graph. By combining this structure with a leakage-proof training strategy and confidence-aware self-training, it significantly improves intra-class representation smoothing and outperforms state-of-the-art models on large-scale academic benchmarks.
What Problem Does This Paper Address?
In semi-supervised node classification, we have a graph where only a tiny fraction of nodes are labeled. The goal is to predict the labels for the rest. Standard Graph Neural Networks (GNNs) like GCN or GAT typically use labels only at the very end of the pipeline to calculate loss.
The authors argue that this "output-only" approach wastes the rich information inherent in labels. While some recent works try to "inject" labels at the input (e.g., by concatenating one-hot encodings to node features), they often fail to capture label semantics (how classes relate to each other) or effectively smooth intra-class representations (ensuring nodes of the same category look similar in vector space). Furthermore, using labels as inputs often leads to "label leakage," where the model simply memorizes the input label rather than learning to generalize from features and structure.
Methods
The authors propose LEGNN, which introduces three core innovations:
- Heterogeneous Graph Construction: Instead of just nodes and edges, the authors add a new type of node: the Label Node. If a training node belongs to "Class A," an edge is created between that node and the "Class A" label node. This makes the label node a "virtual center"—any two nodes of the same class are now at most two hops away from each other, regardless of their distance in the original graph.
- Heterogeneous Message Passing: The model uses distinct parameters for different types of interactions (node-to-node vs. node-to-label). This allows the GNN to explicitly learn label embeddings that capture semantic correlations between classes.
- Training Node Selection (TNS): To prevent the model from "cheating" (label leakage), the authors use a clever sampling trick. In each training epoch, they split the labeled nodes: one subset acts as the "ground truth" for the loss function, while the other subset is used to build the edges to label nodes. This forces the model to learn how to predict a label without having a direct edge to it.
Finally, they introduce AS-Train (Adaptive Self-Training). Unlike standard self-training, which greedily adds pseudo-labels based on a fixed threshold, AS-Train uses "Training Confidence" to decide when the model is mature enough to start pseudo-labeling and "Evaluating Confidence" to weight the importance of those pseudo-labels in the loss function.
Datasets
The model was evaluated on several large-scale, real-world benchmarks from the Open Graph Benchmark (OGB) and Microsoft Academic Graph:
- ogbn-arxiv: A citation network of 169k papers.
- ogbn-mag: A massive heterogeneous academic graph with 1.9M nodes and 349 classes.
- oag-venue: A graph focused on paper venues with 731k nodes.
- syn-arxiv: A synthetic dataset created by the authors to test how the model handles low "homophily" (graphs where neighbors often have different labels).
Key Insights and Ideas
- Labels as Bridges: The "aha moment" here is treating labels as physical nodes. This effectively "short-circuits" the graph for nodes of the same class, facilitating much faster and more effective feature smoothing than standard message passing.
- Semantic Awareness: Because label nodes have their own learnable embeddings, the model can discover that "Machine Learning" is semantically closer to "Optimization" than it is to "Cell Biology," even if the graph structure is sparse.
- Confidence is Dynamic: The AS-Train strategy recognizes that a model’s predictions are only as good as its current state. By waiting for the model to "fit" the training data before trusting its pseudo-labels, they avoid the common pitfall of self-training: error propagation.
Key Results
LEGNN consistently outperformed vanilla GNNs and existing label-augmentation methods across all datasets:
- Accuracy Gains: On
ogbn-mag, LEGNN + AS-Train achieved 53.78% accuracy, a significant jump over the vanilla GAT backbone (~49%) and other sophisticated designs like R-GSN (~50.3%). - Smoothing Effect: Using a metric called "Graph Difference" (GD), the authors proved that LEGNN produces much tighter clusters for intra-class nodes compared to baselines.
- Robustness to Noise: In the synthetic
syn-arxivtests, LEGNN's performance remained stable even as the graph became "noisier" (lower homophily), whereas baseline GNNs saw sharp declines in accuracy.
Limitations and Future Work
- Complexity: The model introduces more parameters and a more complex training loop. The authors note a 1.23x increase in inference time and a 2.05x increase in parameter count on average.
- Hyperparameter Tuning: The success of the TNS and AS-Train strategies depends on several hyperparameters (like the selection rate $\alpha$ and the scale factor $\delta$), which may require careful grid searching for new datasets.
- Future Directions: The authors suggest exploring more complex initial features for label nodes (beyond one-hot encodings) and extending the framework to other graph tasks like link prediction or graph-level classification.
Summary updated