A Theoretical Comparison of Graph Neural Network Extensions

Pál András Papp, Roger Wattenhofer
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:17323-17345, 2022.

Abstract

We study and compare different Graph Neural Network extensions that increase the expressive power of GNNs beyond the Weisfeiler-Leman test. We focus on (i) GNNs based on higher order WL methods, (ii) GNNs that preprocess small substructures in the graph, (iii) GNNs that preprocess the graph up to a small radius, and (iv) GNNs that slightly perturb the graph to compute an embedding. We begin by presenting a simple improvement for this last extension that strictly increases the expressive power of this GNN variant. Then, as our main result, we compare the expressiveness of these extensions to each other through a series of example constructions that can be distinguished by one of the extensions, but not by another one. We also show negative examples that are particularly challenging for each of the extensions, and we prove several claims about the ability of these extensions to count cliques and cycles in the graph.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-papp22a, title = {A Theoretical Comparison of Graph Neural Network Extensions}, author = {Papp, P{\'a}l Andr{\'a}s and Wattenhofer, Roger}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {17323--17345}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/papp22a/papp22a.pdf}, url = {https://proceedings.mlr.press/v162/papp22a.html}, abstract = {We study and compare different Graph Neural Network extensions that increase the expressive power of GNNs beyond the Weisfeiler-Leman test. We focus on (i) GNNs based on higher order WL methods, (ii) GNNs that preprocess small substructures in the graph, (iii) GNNs that preprocess the graph up to a small radius, and (iv) GNNs that slightly perturb the graph to compute an embedding. We begin by presenting a simple improvement for this last extension that strictly increases the expressive power of this GNN variant. Then, as our main result, we compare the expressiveness of these extensions to each other through a series of example constructions that can be distinguished by one of the extensions, but not by another one. We also show negative examples that are particularly challenging for each of the extensions, and we prove several claims about the ability of these extensions to count cliques and cycles in the graph.} }
Endnote
%0 Conference Paper %T A Theoretical Comparison of Graph Neural Network Extensions %A Pál András Papp %A Roger Wattenhofer %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-papp22a %I PMLR %P 17323--17345 %U https://proceedings.mlr.press/v162/papp22a.html %V 162 %X We study and compare different Graph Neural Network extensions that increase the expressive power of GNNs beyond the Weisfeiler-Leman test. We focus on (i) GNNs based on higher order WL methods, (ii) GNNs that preprocess small substructures in the graph, (iii) GNNs that preprocess the graph up to a small radius, and (iv) GNNs that slightly perturb the graph to compute an embedding. We begin by presenting a simple improvement for this last extension that strictly increases the expressive power of this GNN variant. Then, as our main result, we compare the expressiveness of these extensions to each other through a series of example constructions that can be distinguished by one of the extensions, but not by another one. We also show negative examples that are particularly challenging for each of the extensions, and we prove several claims about the ability of these extensions to count cliques and cycles in the graph.
APA
Papp, P.A. & Wattenhofer, R.. (2022). A Theoretical Comparison of Graph Neural Network Extensions. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:17323-17345 Available from https://proceedings.mlr.press/v162/papp22a.html.

Related Material