Graph Neural Networks (GNNs) have achieved much success on graph-structured data. In light of this, there have been increasing interests in studying their expressive power. One line of work studies the capability of GNNs to approximate permutation-invariant functions on graphs, and another focuses on the their power as tests for graph isomorphism. Our work connects these two perspectives and proves their equivalence. We further develop a framework of the expressive power of GNNs that incorporates both of these viewpoints using the language of sigma-algebra, through which we compare the expressive power of different types of GNNs together with other graph isomorphism tests. In particular, we prove that the second-order Invariant Graph Network fails to distinguish non-isomorphic regular graphs with the same degree. Then, we extend it to a new architecture, Ring-GNN, which succeeds in distinguishing these graphs and achieves good performances on real-world datasets.
翻译:图形神经网络(GNNs)在图形结构数据上取得了很大成功。 有鉴于此, 人们越来越有兴趣研究它们的表达力。 一种工作线研究GNNs在图形上近似变异函数的能力, 另一种工作线研究它们作为图形异形测试的能力。 我们的工作将这两个观点连接起来, 并证明它们具有等同性。 我们进一步开发了GNNs的表达力框架, 将这两种观点都包含在Sigma- algebra的语言中, 我们通过它将不同类型GNes的表达力与其他图形异形测试进行比较。 特别是, 我们证明二等异性图形网络无法以同样的程度区分非正态常规图形。 然后, 我们把它扩展到一个新的结构, 即 Ring- GNN, 它成功地区分了这些图形并在真实世界数据集上取得良好的表现。