The Weisfeiler--Lehman (WL) test is a fundamental iterative algorithm for checking isomorphism of graphs. It has also been observed that it underlies the design of several graph neural network architectures, whose capabilities and performance can be understood in terms of the expressive power of this test. Motivated by recent developments in machine learning applications to datasets involving three-dimensional objects, we study when the WL test is {\em complete} for clouds of euclidean points represented by complete distance graphs, i.e., when it can distinguish, up to isometry, any arbitrary such cloud. Our main result states that the $(d-1)$-dimensional WL test is complete for point clouds in $d$-dimensional Euclidean space, for any $d\ge 2$, and that only three iterations of the test suffice. Our result is tight for $d = 2, 3$. We also observe that the $d$-dimensional WL test only requires one iteration to achieve completeness.
翻译:Weisfeiler-Lehman(WL)测试是检查图同构的基本迭代算法。最近,研究人员发现它是几个图神经网络架构的设计基础,这些网络的能力和性能可以通过测试的表达能力来理解。受机器学习应用于涉及三维对象的数据集的最新发展的启发,我们研究了 WL 测试在表示完全距离图的欧几里得点云时何时是完备的,即它是否能区分任意点云直至同构。我们的主要结果是 $(d-1)$ 维 WL 测试对于 $d$ 维欧几里得空间中的点云是完备的,对于任何 $d \geq 2$ ,仅需要进行三次迭代。我们还观察到,$d$ 维 WL 测试只需要进行一次迭代即可实现完整。对于 $d=2,3$ ,我们的结果是最紧密的。