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

Abstract

Graph neural networks (GNNs) have been widely adopted for semi-supervised learning on graphs. A recent study shows that the graph random neural network (GRAND) model can generate state-of-the-art performance for this problem. However, it is difficult for GRAND to handle large-scale graphs since its effectiveness relies on computationally expensive data augmentation procedures. In this work, we present a scalable and high-performance GNN framework GRAND+ for semi-supervised graph learning. To address the above issue, we develop a generalized forward push (GFPush) algorithm in GRAND+ to pre-compute a general propagation matrix and employ it to perform graph data augmentation in a mini-batch manner. We show that both the low time and space complexities of GFPush enable GRAND+ to efficiently scale to large graphs. Furthermore, we introduce a confidence-aware consistency loss into the model optimization of GRAND+, facilitating GRAND+’s generalization superiority. We conduct extensive experiments on seven public datasets of different sizes. The results demonstrate that GRAND+ 1) is able to scale to large graphs and costs less running time than existing scalable GNNs, and 2) can offer consistent accuracy improvements over both full-batch and scalable GNNs across all datasets.
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},
}
Figure