Complete Neural Networks for Complete Euclidean Graphs
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph Neural NetworkProperty PredictionRecommendation SystemsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Three iterations of $(d-1)$-WL test distinguish non isometric clouds of $d$-dimensional points
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 capabi…
Graph Neural NetworkThree Iterations of (d − 1)-WL Test Distinguish Non Isometric Clouds of d-dimensional Points
The Weisfeiler-Lehman (WL) test is a fundamental iterative algorithm for checking the isomorphism of graphs. It has also been observed that it underlies the design of several graph neural network architectures, whose cap…
Geometric learning of the conformational dynamics of molecules using dynamic graph neural networks
We apply a temporal edge prediction model for weighted dynamic graphs to predict time-dependent changes in molecular structure. Each molecule is represented as a complete graph in which each atom is a vertex and all vert…
Graph Neural NetworkAn $\tilde{O}(n^{5/4})$ Time $\varepsilon$-Approximation Algorithm for RMS Matching in a Plane
The 2-Wasserstein distance (or RMS distance) is a useful measure of similarity between probability distributions that has exciting applications in machine learning. For discrete distributions, the problem of computing th…
Geometry Contrastive Learning on Heterogeneous Graphs
Self-supervised learning (especially contrastive learning) methods on heterogeneous graphs can effectively get rid of the dependence on supervisory data. Meanwhile, most existing representation learning methods embed the…
Contrastive LearningNode ClassificationNode ClusteringRepresentation Learning+1