Complete Neural Networks for Complete Euclidean Graphs
This provides a foundational theoretical guarantee for geometric deep learning, enabling more reliable modeling in domains like molecular dynamics and recommender systems.
The paper addresses the theoretical gap in neural networks for point clouds by proving that applying the 3-WL graph isomorphism test to centralized Gram matrices can completely distinguish non-isomorphic point clouds up to permutation and rigid motion, and demonstrates this with an Euclidean graph neural network on symmetrical point clouds.
Neural networks for point clouds, which respect their natural invariance to permutation and rigid motion, have enjoyed recent success in modeling geometric phenomena, from molecular dynamics to recommender systems. Yet, to date, no model with polynomial complexity is known to be complete, that is, able to distinguish between any pair of non-isomorphic point clouds. We fill this theoretical gap by showing that point clouds can be completely determined, up to permutation and rigid motion, by applying the 3-WL graph isomorphism test to the point cloud's centralized Gram matrix. Moreover, we formulate an Euclidean variant of the 2-WL test and show that it is also sufficient to achieve completeness. We then show how our complete Euclidean WL tests can be simulated by an Euclidean graph neural network of moderate size and demonstrate their separation capability on highly symmetrical point clouds.