论文标题
KTH级不变图网络的表达力
The expressive power of kth-order invariant graph networks
论文作者
论文摘要
图神经网络形式主义的表达能力通常是通过区分图形的能力来衡量的。对于许多形式主义，k维weisfeiler-leman（K-WL）图同构测试被用作标准。在本文中，我们考虑了KTH阶不变（线性）图网络（K-igns）的表达能力。众所周知，k-igns表现力足以模拟k-wl。这意味着，对于可以通过k-wl区分的任何两个图，都可以找到一个k-ign，也可以区分这些图。问题仍然是K-igns是否比K-WL可以区分更多的图形。最近证明这是k = 2的错误。在这里，我们将此结果推广到任意k。换句话说，我们表明k-digns在k-wl中具有表达能力。这意味着K-Egns和K-WL在区分图方面同样强大。
The expressive power of graph neural network formalisms is commonly measured by their ability to distinguish graphs. For many formalisms, the k-dimensional Weisfeiler-Leman (k-WL) graph isomorphism test is used as a yardstick. In this paper we consider the expressive power of kth-order invariant (linear) graph networks (k-IGNs). It is known that k-IGNs are expressive enough to simulate k-WL. This means that for any two graphs that can be distinguished by k-WL, one can find a k-IGN which also distinguishes those graphs. The question remains whether k-IGNs can distinguish more graphs than k-WL. This was recently shown to be false for k=2. Here, we generalise this result to arbitrary k. In other words, we show that k-IGNs are bounded in expressive power by k-WL. This implies that k-IGNs and k-WL are equally powerful in distinguishing graphs.
