摘要

图神经网络（GNNs）在处理图结构数据方面已经取得了显著的成功。鉴于此，研究其表达能力的兴趣日益浓厚。一方面，有研究探讨了GNNs在近似图上的置换不变函数的能力；另一方面，则关注它们作为图同构测试工具的效能。我们的工作将这两种视角联系起来，并证明了它们的等价性。我们进一步开发了一个框架，该框架利用σ代数（sigma-algebra）语言整合了这两种观点，通过这一框架比较了不同类型GNNs及其他图同构测试方法的表达能力。特别地，我们证明了二阶不变图网络无法区分具有相同度数的非同构正则图。随后，我们将这一架构扩展为一种新的模型——环状GNN（Ring-GNN），该模型成功地区分了这些图，并在实际数据集上表现出良好的性能。