Aleksandar Bojchevski
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.
- S. Abu-El-Haija, A. Kapoor, B. Perozzi, and J. Lee. 2018. N-gcn: multi-scale graph convolution for semi-supervised node classification. arXiv preprint arXiv:1802.08888.Google Scholar
- S. Abu-El-Haija et al. 2019. MixHop: higher-order graph convolutional architectures via sparsified neighborhood mixing. ICML, 21--29.Google Scholar
- R. Andersen, C. Borgs, J. T. Chayes, J. E. Hopcroft, V. S. Mirrokni, and S.-H. Teng. 2008. Local computation of pagerank contributions. Internet Mathematics, 5, 23--45.Google ScholarCross Ref
- R. Andersen, F. Chung, and K. Lang. 2006. Local graph partitioning using pagerank vectors. FOCS, 475--486.Google Scholar
- P. W. Battaglia et al. 2018. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261.Google Scholar
- A. Bojchevski and S. Günnemann. 2018. Deep gaussian embedding of graphs: unsupervised inductive learning via ranking.Google Scholar
- P. Boldi, V. Lonati, M. Santini, and S. Vigna. 2006. Graph fibrations, graph isomorphism, and pagerank. RAIRO Theor. Informatics Appl., 40, 2, 227--253.Google ScholarCross Ref
- J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. 2013. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203.Google Scholar
- E. Buchnik and E. Cohen. 2018. Bootstrapped graph diffusions: exposing the power of nonlinearity. SIGMETRICS, 8--10.Google Scholar
- C. Chambers, A. Raniwala, F. Perry, S. Adams, R. R. Henry, R. Bradshaw, and N. Weizenbaum. 2010. Flumejava: easy, efficient data-parallel pipelines. ACM Sigplan Notices, 45, 6, 363--375.Google ScholarDigital Library
- I. Chami, S. Abu-El-Haija, B. Perozzi, C. Ré, and K. Murphy. 2020. Machine learning on graphs: a model and comprehensive taxonomy. arXiv preprint arXiv:2005.03675.Google Scholar
- J. Chen, J. Zhu, and L. Song. 2018. Stochastic training of graph convolutional networks with variance reduction. ICML, 941--949.Google Scholar
- J. Chen, T. Ma, and C. Xiao. 2018. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801.10247.Google Scholar
- Z. Chen, L. Li, and J. Bruna. 2018. Supervised community detection with line graph neural networks.Google Scholar
- W. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C. Hsieh. 2019. Cluster-gcn: an efficient algorithm for training deep and large graph convolutional networks. KDD. ACM, 257--266.Google Scholar
- M. Defferrard, X. Bresson, and P. Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems, 3844--3852.Google Scholar
- M. Fey and J. E. Lenssen. 2019. Fast graph representation learning with pytorch geometric. CoRR, abs/1903.02428. arXiv: 1903.02428.Google Scholar
- D. Fogaras and B. Rácz. 2004. Towards scaling fully personalized pagerank. WAW.Google Scholar
- Y. Fujiwara, M. Nakatsuji, H. Shiokawa, T. Mishima, and M. Onizuka. 2013. Fast and exact top-k algorithm for pagerank. AAAI.Google Scholar
- H. Gao, Z. Wang, and S. Ji. 2018. Large-scale learnable graph convolutional networks. KDD, 1416--1424.Google Scholar
- J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. 2017. Neural message passing for quantum chemistry. arXiv preprint arXiv:1704.01212.Google Scholar
- D. F. Gleich, K. Kloster, and H. Nassar. 2015. Localization in seeded pagerank. arXiv preprint arXiv:1509.00016.Google Scholar
- M. Gori, G. Monfardini, and F. Scarselli. 2005. A new model for learning in graph domains. IJCNN, 729--734.Google Scholar
- W. Hamilton, Z. Ying, and J. Leskovec. 2017. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 1024--1034.Google Scholar
- K. He, X. Zhang, S. Ren, and J. Sun. 2016. Deep Residual Learning for Image Recognition. CVPR, 770--778.Google Scholar
- W. Huang, T. Zhang, Y. Rong, and J. Huang. 2018. Adaptive sampling towards fast graph representation learning. Advances in Neural Information Processing Systems, 4563--4572.Google Scholar
- G. Jeh and J. Widom. 2003. Scaling personalized web search. WWW.Google Scholar
- A. Kannan et al. 2016. Smart reply: automated response suggestion for email. KDD, 955--964.Google Scholar
- G. Karypis and V. Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20, 1.Google Scholar
- D. P. Kingma and J. Ba. 2014. Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980.Google Scholar
- T. N. Kipf and M. Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.Google Scholar
- J. Gasteiger, A. Bojchevski, and S. Günnemann. 2019. Predict then propagate: graph neural networks meet personalized pagerank. ICLR.Google Scholar
- Q. Li, Z. Han, and X.-M. Wu. 2018. Deeper insights into graph convolutional networks for semi-supervised learning. arXiv preprint arXiv:1801.07606.Google Scholar
- P. Lofgren, S. Banerjee, and A. Goel. 2016. Personalized pagerank estimation and search: a bidirectional approach. WSDM.Google Scholar
- H. Nassar, K. Kloster, and D. F. Gleich. 2015. Strong localization in personalized pagerank vectors. International Workshop on Algorithms and Models for the Web-Graph. Springer, 190--202.Google Scholar
- M. Niepert, M. Ahmed, and K. Kutzkov. 2016. Learning convolutional neural networks for graphs. ICML, 2014--2023.Google Scholar
- L. Page, S. Brin, R. Motwani, and T. Winograd. 1998. The pagerank citation ranking: bringing order to the web.Google Scholar
- B. Perozzi, M. Schueppert, J. Saalweachter, and M. Thakur. 2016. When recommendation goes wrong: anomalous link discovery in recommendation networks. KDD, 569--578.Google Scholar
- S. Ravi. 2016. Graph-powered machine learning at google. https://ai.googleblog. com/2016/10/graph-powered-machine-learning-at-google.html. (2016).Google Scholar
- R. Al-Rfou, D. Zelle, and B. Perozzi. 2019. Ddgk: learning graph representations for deep divergence graph kernels. WWW, 37--48.Google Scholar
- R. Sato, M. Yamada, and H. Kashima. 2019. Constant time graph neural networks. arXiv preprint arXiv:1901.07868.Google Scholar
- F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. 2009. The graph neural network model. IEEE Transactions on Neural Networks, 20, 1.Google ScholarDigital Library
- A. Sinha, Z. Shen, Y. Song, H. Ma, D. Eide, B.-J. P. Hsu, and K. Wang. 2015. An overview of microsoft academic service (mas) and applications. WWW 2015.Google ScholarDigital Library
- P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903, 1, 2.Google Scholar
- S. Wang, Y. Tang, X. Xiao, Y. Yang, and Z. Li. 2016. Hubppr: effective indexing for approximate personalized pagerank. PVLDB, 10, 205--216.Google ScholarDigital Library
- S. Wang, R. Yang, X. Xiao, Z. Wei, and Y. Yang. 2017. Fora: simple and effective approximate single-source personalized pagerank. KDD.Google Scholar
- X. Wang, A. Shakery, and T. Tao. 2005. Dirichlet pagerank. SIGIR.Google Scholar
- Z. Wei, X. He, X. Xiao, S. Wang, S. Shang, and J.-R. Wen. 2018. Topppr: topk personalized pagerank queries with precision guarantees on large graphs. SIGMOD.Google Scholar
- F. Wu, T. Zhang, A. H. d. Souza Jr, C. Fifty, T. Yu, and K. Q. Weinberger. 2019. Simplifying graph convolutional networks. arXiv preprint arXiv:1902.07153.Google Scholar
- Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. 2019. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596.Google Scholar
- K. Xu, W. Hu, J. Leskovec, and S. Jegelka. 2018. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826.Google Scholar
- K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. 2018. Representation learning on graphs with jumping knowledge networks. arXiv preprint arXiv:1806.03536.Google Scholar
- J. Yang and J. Leskovec. 2015. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 42, 1, 181--213.Google ScholarDigital Library
- R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec. 2018. Graph convolutional neural networks for web-scale recommender systems. arXiv preprint arXiv:1806.01973.Google Scholar
- M. Zhang and Y. Chen. 2018. Link prediction based on graph neural networks. arXiv preprint arXiv:1802.09691.Google Scholar
Index Terms
- Scaling Graph Neural Networks with Approximate PageRank
Recommendations
GRAND+: Scalable Graph Random Neural Networks
WWW '22: Proceedings of the ACM Web Conference 2022Graph 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 ...
Scalable Graph Neural Networks with Deep Graph Library
WSDM '21: Proceedings of the 14th ACM International Conference on Web Search and Data MiningLearning from graph and relational data plays a major role in many applications including social network analysis, marketing, e-commerce, information retrieval, knowledge modeling, medical and biological sciences, engineering, and others. Recently, ...
Scalable Graph Neural Networks with Deep Graph Library
KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data MiningLearning from graph and relational data plays a major role in many applications including social network analysis, marketing, e-commerce, information retrieval, knowledge modeling, medical and biological sciences, engineering, and others. In the last ...
Comments