Is 3-(F)WL Enough to Distinguish All 3D Graphs?
This work tackles a foundational problem in graph theory and machine learning, with implications for domains like chemistry and graph neural networks, but it appears incremental as it builds on existing k-WL methods.
The paper investigates whether the k-WL test, an extension of the Weisfeiler-Lehman test for graph isomorphism, can distinguish all non-isomorphic 3D graphs as k increases, addressing an unexplored gap in graph analysis.
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.