GRAND+: Scalable Graph Random Neural Networks

Wenzheng Feng, Yuxiao Dong, Tinglin Huang, Ziqi Yin, Xu Cheng, Evgeny Kharlamov, Jie Tang

Abstract

Graph Neural Networks (GNNs) often struggle to balance generalization with scalability, particularly when applied to massive, real-world graphs. This paper introduces GRAND+, a scalable evolution of the Graph Random Neural Network (GRAND). By decoupling graph propagation from neural network training through a "Generalized Forward Push" (GFPush) algorithm and implementing a confidence-aware consistency loss, GRAND+ achieves state-of-the-art accuracy while running up to 10x faster than existing scalable baselines on graphs with millions of nodes.

Introduction

Semi-supervised learning on graphs typically relies on GNNs, which are prone to overfitting due to the limited availability of labeled nodes. The original GRAND model addressed this via "random propagation"—a data augmentation technique that creates multiple corrupted versions of a node's neighborhood to enforce consistency. However, GRAND's reliance on repeated power iterations of the adjacency matrix during training makes it computationally prohibitive for "web-scale" graphs. GRAND+ addresses these limitations by moving expensive graph structure processing to a pre-computation phase, enabling efficient training on massive datasets.

Methodology

GRAND+ is built upon three primary architectural pillars designed to ensure both efficiency and robust generalization:

  1. Generalized Forward Push (GFPush): Instead of calculating graph iterations dynamically during training, GRAND+ utilizes GFPush to pre-compute a sparsified propagation matrix ($\Pi$). This algorithm, inspired by PageRank approximations, efficiently identifies the most influential neighbors for each node with a bounded error.
  2. Mini-batch Random Propagation: With the propagation matrix pre-computed and sparsified (retaining only the top-$k$ neighbors), the model performs data augmentation in small, efficient mini-batches. This eliminates the requirement to load the entire graph into memory, facilitating scalability.
  3. Confidence-Aware Consistency Loss: To enhance generalization, GRAND+ employs a consistency regularization term. To mitigate noise from uncertain pseudo-labels, a confidence threshold ($\gamma$) is introduced, ensuring the consistency loss is only applied to nodes where the model exhibits high prediction confidence.
The GRAND+ pipeline: from sub-matrix approximation to mini-batch training.

Experimental Setup

The authors evaluated GRAND+ across seven public datasets, ranging from small citation networks to massive web-scale graphs:

  • Small/Medium Scale: Cora, Citeseer, and Pubmed.
  • Large Scale: AMiner-CS, Reddit, Amazon2M, and MAG-Scholar-C.

Notably, MAG-Scholar-C contains over 10.5 million nodes and 265 million edges, serving as a rigorous benchmark for the scalability of the proposed framework.

Results and Discussion

Experimental results demonstrate that GRAND+ consistently outperforms both full-batch GNNs (e.g., GCN, GAT) and existing scalable baselines (e.g., SGC, PPRGo). On the 10.5M-node MAG-Scholar-C dataset, GRAND+ achieved a 10x speedup over popular scalable methods like FastGCN and GraphSAINT. Compared to PPRGo, it offered a 4.9% absolute accuracy gain with comparable running time.

Key Insights

  • Decoupling and Sparsity: Moving graph structure processing to a pre-computation step allows the training phase to function as a simple MLP-based task on augmented features. Preserving only the top-$k$ (e.g., $k=32$ or $64$) most important neighbors is sufficient to maintain high accuracy while drastically reducing computational overhead.
  • Stability through Confidence: The confidence threshold acts as a curriculum, focusing the model on reliable data first and reducing the noise inherent in standard consistency regularization.
  • Hyperparameter Sensitivity: The model's performance is influenced by the consistency loss weight ($\lambda_{max}$) and the confidence threshold ($\gamma$), as shown in the sensitivity analysis below.
The effect of the consistency loss weight and confidence threshold on accuracy.

Conclusion

GRAND+ represents a significant advancement in scalable GNNs, providing a robust framework for handling massive graphs without sacrificing generalization. While the pre-computation step (GFPush) introduces an initial overhead, its parallelizability and the resulting training efficiency make it a powerful tool for large-scale graph analysis. Future work may explore more advanced matrix approximation techniques and the extension of this framework to tasks such as link prediction and graph-level classification.

Summary updated

BibTeX
@inproceedings{feng2022grand,
  author = {Wenzheng Feng and Yuxiao Dong and Tinglin Huang and Ziqi Yin and Xu Cheng and Evgeny Kharlamov and Jie Tang},
  title = {{GRAND+: Scalable Graph Random Neural Networks}},
  booktitle = {The Web Conference},
  year = {2022},
  url = {https://openreview.net/forum?id=yZzXAXC8qc},
}

Loading related content...

Figure