Label Deconvolution for Node Representation Learning on Large-Scale Attributed Graphs Against Learning Bias

Zhihao Shi, Jie Wang, Fanghua Lu, Hanzhu Chen, Defu Lian, Zheng Wang, Jieping Ye, Feng Wu

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.

Label deconvolution introduces a scalable objective function to approximate the original objective function based on the concept of the inverse mapping of GNNs.

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.
Comparison of different loss functions for NEs.

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-product using 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

Abstract

Node representation learning on attributed graphs—whose nodes are associated with rich attributes (e.g., texts and protein sequences)—plays a crucial role in many important downstream tasks. To encode the attributes and graph structures simultaneously, recent studies integrate pre-trained models with graph neural networks (GNNs), where pre-trained models serve as node encoders (NEs) to encode the attributes. As jointly training large NEs and GNNs on large-scale graphs suffers from severe scalability issues, many methods propose to train NEs and GNNs separately. Consequently, they do not take feature convolutions in GNNs into consideration in the training phase of NEs, leading to a significant learning bias relative to the joint training. To address this challenge, we propose an efficient label regularization technique, namely L abel D econvolution (LD), to alleviate the learning bias by a novel and highly scalable approximation to the inverse mapping of GNNs. The inverse mapping leads to an objective function that is equivalent to that by the joint training, while it can effectively incorporate GNNs in the training phase of NEs against the learning bias. More importantly, we show that LD converges to the optimal objective function values by the joint training under mild assumptions. Experiments demonstrate LD significantly outperforms state-of-the-art methods on Open Graph Benchmark datasets.
BibTeX
@article{shi2024label,
  author = {Zhihao Shi and Jie Wang and Fanghua Lu and Hanzhu Chen and Defu Lian and Zheng Wang and Jieping Ye and Feng Wu},
  title = {{Label Deconvolution for Node Representation Learning on Large-Scale Attributed Graphs Against Learning Bias}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2024},
  url = {https://openreview.net/forum?id=YjEgTcU7J4},
}
Figure