Graphtester: Exploring Theoretical Boundaries of GNNs on Graph Datasets
Eren Akbiyik Florian Grötschla Beni Egressy Roger Wattenhofer
Graph Neural Networks (GNNs) have emerged as a powerful tool for learning
from graph-structured data. However, even state-of-the-art architectures have
limitations on what structures they can distinguish, imposing theoretical
limits on what the networks can achieve on different datasets. In this paper,
we provide a new tool called Graphtester for a comprehensive analysis of the
theoretical capabilities of GNNs for various datasets, tasks, and scores. We
use Graphtester to analyze over 40 different graph datasets, determining upper
bounds on the performance of various GNNs based on the number of layers.
Further, we show that the tool can also be used for Graph Transformers using
positional node encodings, thereby expanding its scope. Finally, we demonstrate
that features generated by Graphtester can be used for practical applications
such as Graph Transformers, and provide a synthetic dataset to benchmark node
and edge features, such as positional encodings. The package is freely
available at the following URL: https://github.com/meakbiyik/graphtester.