Influence-Based Mini-Batching for Graph Neural Networks

Johannes Gasteiger, Chendi Qian, Stephan Günnemann
Proceedings of the First Learning on Graphs Conference, PMLR 198:9:1-9:19, 2022.

Abstract

Using graph neural networks for large graphs is challenging since there is no clear way of constructing mini-batches. To solve this, previous methods have relied on sampling or graph clustering. While these approaches often lead to good training convergence, they introduce significant overhead due to expensive random data accesses and perform poorly during inference. In this work we instead focus on model behavior during inference. We theoretically model batch construction via maximizing the influence score of nodes on the outputs. This formulation leads to optimal approximation of the output when we do not have knowledge of the trained model. We call the resulting method influence-based mini-batching (IBMB). IBMB accelerates inference by up to 130x compared to previous methods that reach similar accuracy. Remarkably, with adaptive optimization and the right training schedule IBMB can also substantially accelerate training, thanks to precomputed batches and consecutive memory accesses. This results in up to 18x faster training per epoch and up to 17x faster convergence per runtime compared to previous methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v198-gasteiger22a, title = {Influence-Based Mini-Batching for Graph Neural Networks}, author = {Gasteiger, Johannes and Qian, Chendi and G{\"u}nnemann, Stephan}, booktitle = {Proceedings of the First Learning on Graphs Conference}, pages = {9:1--9:19}, year = {2022}, editor = {Rieck, Bastian and Pascanu, Razvan}, volume = {198}, series = {Proceedings of Machine Learning Research}, month = {09--12 Dec}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v198/gasteiger22a/gasteiger22a.pdf}, url = {https://proceedings.mlr.press/v198/gasteiger22a.html}, abstract = {Using graph neural networks for large graphs is challenging since there is no clear way of constructing mini-batches. To solve this, previous methods have relied on sampling or graph clustering. While these approaches often lead to good training convergence, they introduce significant overhead due to expensive random data accesses and perform poorly during inference. In this work we instead focus on model behavior during inference. We theoretically model batch construction via maximizing the influence score of nodes on the outputs. This formulation leads to optimal approximation of the output when we do not have knowledge of the trained model. We call the resulting method influence-based mini-batching (IBMB). IBMB accelerates inference by up to 130x compared to previous methods that reach similar accuracy. Remarkably, with adaptive optimization and the right training schedule IBMB can also substantially accelerate training, thanks to precomputed batches and consecutive memory accesses. This results in up to 18x faster training per epoch and up to 17x faster convergence per runtime compared to previous methods.} }
Endnote
%0 Conference Paper %T Influence-Based Mini-Batching for Graph Neural Networks %A Johannes Gasteiger %A Chendi Qian %A Stephan Günnemann %B Proceedings of the First Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2022 %E Bastian Rieck %E Razvan Pascanu %F pmlr-v198-gasteiger22a %I PMLR %P 9:1--9:19 %U https://proceedings.mlr.press/v198/gasteiger22a.html %V 198 %X Using graph neural networks for large graphs is challenging since there is no clear way of constructing mini-batches. To solve this, previous methods have relied on sampling or graph clustering. While these approaches often lead to good training convergence, they introduce significant overhead due to expensive random data accesses and perform poorly during inference. In this work we instead focus on model behavior during inference. We theoretically model batch construction via maximizing the influence score of nodes on the outputs. This formulation leads to optimal approximation of the output when we do not have knowledge of the trained model. We call the resulting method influence-based mini-batching (IBMB). IBMB accelerates inference by up to 130x compared to previous methods that reach similar accuracy. Remarkably, with adaptive optimization and the right training schedule IBMB can also substantially accelerate training, thanks to precomputed batches and consecutive memory accesses. This results in up to 18x faster training per epoch and up to 17x faster convergence per runtime compared to previous methods.
APA
Gasteiger, J., Qian, C. & Günnemann, S.. (2022). Influence-Based Mini-Batching for Graph Neural Networks. Proceedings of the First Learning on Graphs Conference, in Proceedings of Machine Learning Research 198:9:1-9:19 Available from https://proceedings.mlr.press/v198/gasteiger22a.html.

Related Material