论文标题
Weisfeiler-Leman等效类的拓扑表征
A Topological characterisation of Weisfeiler-Leman equivalence classes
论文作者
论文摘要
图形神经网络（GNN）是旨在处理图表和信号的学习模型。最受欢迎，最成功的GNN是基于消息传递方案的基础。在区分两个非同态图时，这些方案固有地具有有限的表达能力。在本文中，我们依靠覆盖空间的理论来充分表征GNN无法区分的图形类别。然后，我们将任意生成许多无法通过GNN来区分的非同态图，导致GraphCovers数据集。我们还表明，数据集中没有可区分的图的数量随节点的数量增长。最后，我们在几个GNN体系结构上测试GraphCovers数据集，表明它们都无法区分其包含的任何两个图。
Graph Neural Networks (GNNs) are learning models aimed at processing graphs and signals on graphs. The most popular and successful GNNs are based on message passing schemes. Such schemes inherently have limited expressive power when it comes to distinguishing two non-isomorphic graphs. In this article, we rely on the theory of covering spaces to fully characterize the classes of graphs that GNNs cannot distinguish. We then generate arbitrarily many non-isomorphic graphs that cannot be distinguished by GNNs, leading to the GraphCovers dataset. We also show that the number of indistinguishable graphs in our dataset grows super-exponentially with the number of nodes. Finally, we test the GraphCovers dataset on several GNN architectures, showing that none of them can distinguish any two graphs it contains.
