The problem of graph isomorphism is an important but challenging problem in
the field of graph analysis, for example: analyzing the similarity of two
chemical molecules, or studying the expressive ability of graph neural
networks. WL test is a method to judge whether two graphs are isomorphic, but
it cannot distinguish all non-isomorphic graphs. As an improvement of WL, k-WL
has stronger isomorphism discrimination ability, and as k increases, its
discrimination ability is strictly increasing. However, whether the isomorphic
discrimination power of k-WL is strictly increasing for more complex 3D graphs,
or whether there exists k that can discriminate all 3D graphs, remains
unexplored. This paper attempts to explore this problem from the perspective of
graph generation.

用图生成的角度探讨了 k-WL 在更复杂的三维图形中是否能够严格提高同构判别能力，以及是否存在能够判别所有三维图形的 k 值。

3-(F) WL 是否足够区分所有的三维图形？

Is 3-(F)WL Enough to Distinguish All 3D Graphs?

The expressive power of Graph Neural Networks (GNNs) has been studied
extensively through the Weisfeiler-Leman (WL) graph isomorphism test. However,
standard GNNs and the WL framework are inapplicable for geometric graphs
embedded in Euclidean space, such as biomolecules, materials, and other
physical systems. In this work, we propose a geometric version of the WL test
(GWL) for discriminating geometric graphs while respecting the underlying
physical symmetries: permutations, rotation, reflection, and translation. We
use GWL to characterise the expressive power of geometric GNNs that are
invariant or equivariant to physical symmetries in terms of distinguishing
geometric graphs. GWL unpacks how key design choices influence geometric GNN
expressivity: (1) Invariant layers have limited expressivity as they cannot
distinguish one-hop identical geometric graphs; (2) Equivariant layers
distinguish a larger class of graphs by propagating geometric information
beyond local neighbourhoods; (3) Higher order tensors and scalarisation enable
maximally powerful geometric GNNs; and (4) GWL's discrimination-based
perspective is equivalent to universal approximation. Synthetic experiments
supplementing our results are available at
this https URL

本研究提出了符合物理对称性的几何图卷积神经网络测试 GWL，并使用 GWL 研究了符合物理对称性的几何图卷积神经网络的表达能力，发现等变层扩展了局部邻域之外的几何信息，高阶张量和标量化使几何图卷积神经网络具有最大的表达能力。