From Local Structures to Size Generalization in Graph Neural Networks

Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, Haggai Maron
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:11975-11986, 2021.

Abstract

Graph neural networks (GNNs) can process graphs of different sizes, but their ability to generalize across sizes, specifically from small to large graphs, is still not well understood. In this paper, we identify an important type of data where generalization from small to large graphs is challenging: graph distributions for which the local structure depends on the graph size. This effect occurs in multiple important graph learning domains, including social and biological networks. We first prove that when there is a difference between the local structures, GNNs are not guaranteed to generalize across sizes: there are "bad" global minima that do well on small graphs but fail on large graphs. We then study the size-generalization problem empirically and demonstrate that when there is a discrepancy in local structure, GNNs tend to converge to non-generalizing solutions. Finally, we suggest two approaches for improving size generalization, motivated by our findings. Notably, we propose a novel Self-Supervised Learning (SSL) task aimed at learning meaningful representations of local structures that appear in large graphs. Our SSL task improves classification accuracy on several popular datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-yehudai21a, title = {From Local Structures to Size Generalization in Graph Neural Networks}, author = {Yehudai, Gilad and Fetaya, Ethan and Meirom, Eli and Chechik, Gal and Maron, Haggai}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {11975--11986}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/yehudai21a/yehudai21a.pdf}, url = {https://proceedings.mlr.press/v139/yehudai21a.html}, abstract = {Graph neural networks (GNNs) can process graphs of different sizes, but their ability to generalize across sizes, specifically from small to large graphs, is still not well understood. In this paper, we identify an important type of data where generalization from small to large graphs is challenging: graph distributions for which the local structure depends on the graph size. This effect occurs in multiple important graph learning domains, including social and biological networks. We first prove that when there is a difference between the local structures, GNNs are not guaranteed to generalize across sizes: there are "bad" global minima that do well on small graphs but fail on large graphs. We then study the size-generalization problem empirically and demonstrate that when there is a discrepancy in local structure, GNNs tend to converge to non-generalizing solutions. Finally, we suggest two approaches for improving size generalization, motivated by our findings. Notably, we propose a novel Self-Supervised Learning (SSL) task aimed at learning meaningful representations of local structures that appear in large graphs. Our SSL task improves classification accuracy on several popular datasets.} }
Endnote
%0 Conference Paper %T From Local Structures to Size Generalization in Graph Neural Networks %A Gilad Yehudai %A Ethan Fetaya %A Eli Meirom %A Gal Chechik %A Haggai Maron %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-yehudai21a %I PMLR %P 11975--11986 %U https://proceedings.mlr.press/v139/yehudai21a.html %V 139 %X Graph neural networks (GNNs) can process graphs of different sizes, but their ability to generalize across sizes, specifically from small to large graphs, is still not well understood. In this paper, we identify an important type of data where generalization from small to large graphs is challenging: graph distributions for which the local structure depends on the graph size. This effect occurs in multiple important graph learning domains, including social and biological networks. We first prove that when there is a difference between the local structures, GNNs are not guaranteed to generalize across sizes: there are "bad" global minima that do well on small graphs but fail on large graphs. We then study the size-generalization problem empirically and demonstrate that when there is a discrepancy in local structure, GNNs tend to converge to non-generalizing solutions. Finally, we suggest two approaches for improving size generalization, motivated by our findings. Notably, we propose a novel Self-Supervised Learning (SSL) task aimed at learning meaningful representations of local structures that appear in large graphs. Our SSL task improves classification accuracy on several popular datasets.
APA
Yehudai, G., Fetaya, E., Meirom, E., Chechik, G. & Maron, H.. (2021). From Local Structures to Size Generalization in Graph Neural Networks. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:11975-11986 Available from https://proceedings.mlr.press/v139/yehudai21a.html.

Related Material