Scaling Graph Neural Networks with Approximate PageRank

Abstract

Graph neural networks (GNNs) have emerged as a powerful approach for solving many network mining tasks. However, learning on large graphs remains a challenge - many recently proposed scalable GNN approaches rely on an expensive message-passing procedure to propagate information through the graph. We present the PPRGo model which utilizes an efficient approximation of information diffusion in GNNs resulting in significant speed gains while maintaining state-of-the-art prediction performance. In addition to being faster, PPRGo is inherently scalable, and can be trivially parallelized for large datasets like those found in industry settings. We demonstrate that PPRGo outperforms baselines in both distributed and single-machine training environments on a number of commonly used academic graphs. To better analyze the scalability of large-scale graph learning methods, we introduce a novel benchmark graph with 12.4 million nodes, 173 million edges, and 2.8 million node features. We show that training PPRGo from scratch and predicting labels for all nodes in this graph takes under 2 minutes on a single machine, far outpacing other baselines on the same graph. We discuss the practical application of PPRGo to solve large-scale node classification problems at Google.

arXiv commentPublished as a Conference Paper at ACM SIGKDD 2020. Author name changed from Johannes Klicpera to Johannes Gasteiger

References in corpus (32)

• Adam: A Method for Stochastic Optimization
• Semi-Supervised Classification with Graph Convolutional Networks
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• Graph Convolutional Neural Networks for Web-Scale Recommender Systems
• Spectral Networks and Locally Connected Networks on Graphs
• Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
• Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
• Fast Graph Representation Learning with PyTorch Geometric
• Simplifying Graph Convolutional Networks
• Representation Learning on Graphs with Jumping Knowledge Networks
• Learning Convolutional Neural Networks for Graphs
• Large-Scale Learnable Graph Convolutional Networks
• FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
• Predict then Propagate: Graph Neural Networks meet Personalized PageRank
• Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning
• Scaling Graph Neural Networks with Approximate PageRank
• How Powerful are Graph Neural Networks?
• Link Prediction Based on Graph Neural Networks
• MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing
• Adaptive Sampling Towards Fast Graph Representation Learning
• Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking
• Stochastic Training of Graph Convolutional Networks with Variance Reduction
• Smart Reply: Automated Response Suggestion for Email
• Personalized PageRank Estimation and Search: A Bidirectional Approach
• Supervised Community Detection with Line Graph Neural Networks
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification
• DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
• Bootstrapped Graph Diffusions: Exposing the Power of Nonlinearity
• Constant Time Graph Neural Networks
• Localization in Seeded PageRank

Cited by in corpus (61)

• Scaling Graph Neural Networks with Approximate PageRank
• Combining Label Propagation and Simple Models Out-performs Graph Neural Networks
• Adaptive Universal Generalized PageRank Graph Neural Network
• TRacer: Scalable Graph-based Transaction Tracing for Account-based Blockchain Trading Systems
• Accelerating Large Scale Real-Time GNN Inference using Channel Pruning
• Scalable Graph Neural Networks via Bidirectional Propagation
• Efficient Algorithms for Personalized PageRank Computation: A Survey
• Topology-Imbalance Learning for Semi-Supervised Node Classification
• Approximate Graph Propagation
• Learning Strong Graph Neural Networks with Weak Information
• Adaptive Dependency Learning Graph Neural Networks
• Domain-adaptive Message Passing Graph Neural Network
• Efficient Heterogeneous Graph Learning via Random Projection
• Understanding the Message Passing in Graph Neural Networks via Power Iteration Clustering
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs
• DPAR: Decoupled Graph Neural Networks with Node-Level Differential Privacy
• New Benchmarks for Learning on Non-Homophilous Graphs
• Lifelong Learning of Graph Neural Networks for Open-World Node Classification
• PANE: scalable and effective attributed network embedding
• Graph Convolutional Networks based on Manifold Learning for Semi-Supervised Image Classification
• Effective and Scalable Clustering on Massive Attributed Graphs
• Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data
• Towards Graph Self-Supervised Learning with Contrastive Adjusted Zooming
• Pre-train and Learn: Preserve Global Information for Graph Neural Networks
• SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization
• LPFormer: An Adaptive Graph Transformer for Link Prediction
• DPGNN: Dual-Perception Graph Neural Network for Representation Learning
• Addressing Heterophily in Node Classification with Graph Echo State Networks
• Large-scale graph representation learning with very deep GNNs and self-supervision
• Deep Graph Neural Networks with Shallow Subgraph Samplers
• Node Dependent Local Smoothing for Scalable Graph Learning
• Edge-based Local Push for Personalized PageRank
• SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization
• FairSample: Training Fair and Accurate Graph Convolutional Neural Networks Efficiently
• The Impact of Global Structural Information in Graph Neural Networks Applications
• FastGL: A GPU-Efficient Framework for Accelerating Sampling-Based GNN Training at Large Scale
• Chickenpox Cases in Hungary: a Benchmark Dataset for Spatiotemporal Signal Processing with Graph Neural Networks
• Hierarchically Regularized Deep Forecasting
• DiffusAL: Coupling Active Learning with Graph Diffusion for Label-Efficient Node Classification
• CogDL: A Comprehensive Library for Graph Deep Learning
• FTF-ER: Feature-Topology Fusion-Based Experience Replay Method for Continual Graph Learning
• Optimal Dynamic Subset Sampling: Theory and Applications
• OmniSage: Large Scale, Multi-Entity Heterogeneous Graph Representation Learning
• Robustness of Graph Neural Networks at Scale
• Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds
• A Study of Joint Graph Inference and Forecasting
• Boosting Multitask Learning on Graphs through Higher-Order Task Affinities
• Revisiting Local Computation of PageRank: Simple and Optimal
• Local2Global: Scaling global representation learning on graphs via local training
• Graph Belief Propagation Networks
• On the Impact of Communities on Semi-supervised Classification Using Graph Neural Networks
• LPS-GNN : Deploying Graph Neural Networks on Graphs with 100-Billion Edges
• Fea2Fea: Exploring Structural Feature Correlations via Graph Neural Networks
• Minimally-Supervised Structure-Rich Text Categorization via Learning on Text-Rich Networks
• Jointly Learnable Data Augmentations for Self-Supervised GNNs
• Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
• Efficient Variational Graph Autoencoders for Unsupervised Cross-domain Prerequisite Chains
• ${\ell }_2$-norm Flow Diffusion in Near-Linear Time
• Scaling Up Graph Neural Networks Via Graph Coarsening
• Efficient Integration of Multi-View Attributed Graphs for Clustering and Embedding