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:
- 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.
- 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.
- 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.
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.
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