TL;DR
Label Deconvolution (LD) bridges the gap between computationally prohibitive joint training and accuracy-damaging separate training for large-scale graph node representation learning. By efficiently approximating the inverse mapping of Graph Neural Networks (GNNs), LD generates "inverse labels" that inject graph structure directly into the node encoder training phase, achieving state-of-the-art accuracy with massive speedups.
What Problem Does This Paper Address?
Many real-world networks—such as citation databases, e-commerce platforms, and protein-protein interaction networks—contain nodes rich with textual or sequence attributes. To learn from this data, researchers typically combine a Node Encoder (NE) (like a large language model) to process local attributes with a Graph Neural Network (GNN) to capture global structural relationships.
However, training these models jointly on massive graphs is a computational nightmare. GNNs suffer from the "neighbor explosion" problem, where the neighborhood size grows exponentially with network depth, quickly exhausting GPU memory when paired with large NEs.
To scale, existing frameworks train the NE and GNN separately: they first train the NE on node attributes alone, freeze its parameters, and then train the GNN on the extracted features. While scalable, this introduces a severe learning bias. Because the NE is trained without considering the GNN's feature convolutions, it fails to learn features that optimize the final graph-based predictions.
Methods
The authors introduce Label Deconvolution (LD) to eliminate this learning bias while maintaining the scalability of separate training.
Instead of pushing features forward through a GNN during the NE training phase, LD takes the true node labels and maps them backward through an approximate inverse of the GNN's feature convolution. This process creates inverse labels. If the NE can successfully fit its output features to these inverse labels, the subsequent GNN will naturally map those features to the correct true labels.
To make computing this inverse mapping scalable, the authors leverage the Cayley-Hamilton theorem. They prove that the inverse of a GNN's linear feature convolution can be expressed as a linear combination of matrix powers of the normalized adjacency matrix ($\hat{A}$). This allows them to pre-compute $i$-hop neighbor labels ($K_i = \hat{A}^i Y$) just once.
During the NE training phase, the model optimizes the NE parameters ($\beta$), GNN non-linear layers ($\theta$), and trainable deconvolution weights ($\gamma$) simultaneously using standard, efficient mini-batches:
$$\min_{\beta, \theta, \gamma} \mathcal{L}(\psi(\mathbf{F}^{(\beta)}_B; \theta), \mathbf{Y}^{(\gamma)}_B)$$
Datasets
The method was evaluated on three large-scale benchmark datasets from the Open Graph Benchmark (OGB):
- ogbn-arxiv: A citation network where nodes are papers with title/abstract text attributes (169K nodes, 1.15M edges).
- ogbn-product: An Amazon co-purchase network with product text descriptions (2.44M nodes, 61.8M edges).
- ogbn-protein: A protein-protein association network where node attributes are biological protein sequences (132K nodes, 39.5M edges).
Key Insights and Ideas
- The Dual Nature of Labels: Node labels in attributed graphs depend on both local attributes and global structure. Training an NE purely on raw labels ignores structure (causing bias), while self-supervised methods like GIANT ignore labels entirely. LD elegantly unifies both signals.
- Mathematical Elegance via Cayley-Hamilton: Calculating the exact inverse of a massive graph's diffusion matrix is impossible. Showing that this inverse can be parameterized as a simple polynomial expansion of $i$-hop labels makes the structural integration incredibly cheap.
- Breaking the Scaling Bottleneck: As node encoders grow larger (from 100M to 750M parameters), the learning bias of traditional separate training limits performance gains. LD exhibits excellent scaling laws, with accuracy improving sharply as the underlying language model scales up.
Key Results
- State-of-the-Art Accuracy: LD consistently outperformed top separate-training baselines (like GLEM and GIANT) across all three OGB datasets. For instance, on
ogbn-productusing a GAMLP backbone, LD achieved a test accuracy of 86.45%, outperforming GLEM (85.09%) and standard fine-tuning (82.88%). - Massive Speedups: Because LD avoids the expensive iterative pseudo-label distillation loops required by methods like GLEM, it is significantly faster. On
ogbn-product, LD matched or exceeded GLEM's accuracy while reducing total training time from 75.67 hours down to 24.78 hours (more than a 3x speedup). - Inductive Capability: Unlike transductive methods that require seeing the entire graph structure beforehand, LD naturally adapts to inductive settings (where new nodes arrive post-training), outperforming baselines on unseen test data by a wide margin.
Limitations and Future Work
The authors note that on highly dense graphs (such as ogbn-protein, which has a very high average node degree of 298.5), calculating high-hop inverse labels can lead to an over-smoothing issue, making the inverse labels indistinguishable. To counteract this, they introduced a hyperparameter $\alpha$ to balance the true labels and the inverse labels. Future work could explore adaptive, node-dependent hop selections to automatically mitigate over-smoothing in dense clusters.
Summary updated