Incompleteness of $k$-dimensional geometric Weisfeiler-Leman in $\mathbb R^{O(k)}$

Distance invariant machine learning models have found wide applications in fields such as image recognition, molecular property prediction, and natural language processing in recent years. A crucial requirement for these models is their independence from the particular ordering of data points or their specific positions in the Euclidean space. Instead, they should rely on the relative information between data points, that is, the distances between them in the Euclidean space. In other words, these models should be invariant to isometries -- translations, rotations, and symmetries. Such models are often based on ($k$-dimensional) graph neural networks ($k$-GNNs) applied to the distance graph induced by a given point cloud. The expressive power of $k$-GNNs has been shown to be limited by the $k$-dimensional Weisfeiler-Leman ($k$-WL) test. Our focus is on the expressivity of these models, specifically addressing the following question for different correspondences of $k$ and $d$: ``Does $k$-WL recognise all point clouds up to isometry in $\mathbb R^d$? '' The question was answered negatively by Pozdnyakov and Ceriotti (Machine Learning: Science and Technology, 2022) for $k = 1$ and $d = 3$. Furthermore, Rose et al. (NeurIPS 2023) found that $d$-WL identifies all point clouds up to isometry in $\mathbb R^{d+1}$ (for any $d \geq 1$). We show that their result is asymptotically tight by finding two non-isometric point clouds in $\mathbb R^{O(d)}$ that are not distinguished by $d$-WL. In the talk, we present the current state-of-the-art, discuss the basic idea of our construction, and formulate open questions for future research.

Authors

• Tomáš Novotný

Keywords

No keywords are indexed for this paper.