Approximate Graph Propagation

Abstract

Efficient computation of node proximity queries such as transition probabilities, Personalized PageRank, and Katz are of fundamental importance in various graph mining and learning tasks. In particular, several recent works leverage fast node proximity computation to improve the scalability of Graph Neural Networks (GNN). However, prior studies on proximity computation and GNN feature propagation are on a case-by-case basis, with each paper focusing on a particular proximity measure. In this paper, we propose Approximate Graph Propagation (AGP), a unified randomized algorithm that computes various proximity queries and GNN feature propagation, including transition probabilities, Personalized PageRank, heat kernel PageRank, Katz, SGC, GDC, and APPNP. Our algorithm provides a theoretical bounded error guarantee and runs in almost optimal time complexity. We conduct an extensive experimental study to demonstrate AGP's effectiveness in two concrete applications: local clustering with heat kernel PageRank and node classification with GNNs. Most notably, we present an empirical study on a billion-edge graph Papers100M, the largest publicly available GNN dataset so far. The results show that AGP can significantly improve various existing GNN models' scalability without sacrificing prediction accuracy.

ACM SIGKDD 2021

References in corpus (6)

• Semi-Supervised Classification with Graph Convolutional Networks
• Simplifying Graph Convolutional Networks
• Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks
• Scalable Graph Neural Networks via Bidirectional Propagation
• Personalized PageRank to a Target Node, Revisited
• Efficient Estimation of Heat Kernel PageRank for Local Clustering

Cited by in corpus (9)

• Efficient Algorithms for Personalized PageRank Computation: A Survey
• SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization
• Efficient Estimation of Pairwise Effective Resistance
• Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective
• Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds
• A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness
• Optimal Dynamic Subset Sampling: Theory and Applications
• Revisiting Local Computation of PageRank: Simple and Optimal
• Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal