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: this https URL

本文介绍了一个新的工具 Graphtester，用于对 40 个不同的图形数据集进行分析，以确定各种 GNNs 的性能上限，并扩展其范围以对 Graph Transformer 进行分析，并提供了一个用于基准测试节点和边缘特征的合成数据集和 positional encodings