Introduction
Training massive node encoders (NEs), such as BERT or ESM2, in conjunction with Graph Neural Networks (GNNs) on large-scale graphs presents a significant computational challenge. The standard approach for node representation learning involves combining rich local attributes with global graph structure. However, joint training of these components often leads to "neighbor explosion," where memory requirements scale exponentially with GNN depth.
To circumvent this, researchers frequently resort to "separate training," where the NE is trained independently to extract features, which are then used to train a GNN. This approach introduces a learning bias: the NE, trained in isolation, fails to account for the subsequent graph convolutions, potentially extracting features that are suboptimal for neighborhood aggregation.
Methodology: Label Deconvolution (LD)
This paper introduces Label Deconvolution (LD), a framework designed to eliminate learning bias while maintaining the scalability of separate training. The core intuition is to treat GNN feature convolution as a mathematical mapping that can be approximately inverted.
The LD Workflow
- Inverse Mapping: If a GNN predicts labels $Y$ from features $F$ via a convolution $\phi$, the "ideal" features for the NE should satisfy $F \approx \phi^{-1}(Y)$.
- Polynomial Approximation: Since direct inversion of large graph matrices is computationally prohibitive, the authors utilize a scalable approximation based on the Cayley-Hamilton theorem. The inverse mapping is represented as a linear combination of $i$-hop labels (neighbor labels at varying distances).
- Training Process:
- Pre-processing: Compute $i$-hop labels as weighted averages of neighbor labels.
- NE Training: The Node Encoder is trained to predict these "inverse labels" rather than raw labels. This process injects structural information into the NE without requiring full GNN passes during this phase.
- GNN Training: A standard GNN is then trained using the high-quality features produced by the LD-trained encoder.
Experimental Evaluation
The authors evaluated LD on three major benchmarks from the Open Graph Benchmark (OGB):
- ogbn-arxiv: A citation network (textual attributes).
- ogbn-product: A co-purchase network (textual descriptions).
- ogbn-protein: A biological network (amino acid sequences).
These datasets include up to 2.4 million nodes and 61 million edges, testing the scalability of the proposed method.
Key Results and Insights
LD provides "structural supervision for free" by training the NE on neighbor-averaged labels, effectively pre-smoothing features for the GNN.
- Accuracy: On
ogbn-arxiv, LD achieved a test accuracy of 77.26%, outperforming standard separate training (75.52%) and the iterative GLEM method (76.97%). - Efficiency: LD is significantly faster than iterative methods. On
ogbn-product, LD was 3x faster than GLEM while delivering superior accuracy (86.45% vs 85.09%). - Scalability: As shown in the complexity analysis, LD maintains $O(|\mathcal{V}|)$ time complexity and $O(|\mathcal{B}|)$ memory complexity, making it as efficient as GLEM but with the added benefit of utilizing both labels ($Y$) and adjacency ($A$) for supervision.
- Inductive Performance: LD demonstrates strong generalization on unseen nodes, confirming that the learned features capture robust structural properties.
Conclusion
Label Deconvolution offers a scalable and effective solution to the learning bias inherent in separate training for large-scale graphs. By approximating the inverse of graph convolutions, LD allows for the efficient training of massive node encoders that are structurally aware, bridging the gap between joint and separate training paradigms. Future work may address refinements for non-linear spatial GNNs and adaptive weighting for varying graph densities.
Summary updated