EDEN: Learning Deterministic Node Position with Equivariant Distance Encoding

Abstract Despite Graph Neural Networks' (GNNs) achievements in graph representation learning tasks, how to learn the deterministic node position embedding in non-Euclidean graph data is still an open question. Additionally, most existing message-passing-based graph neural networks' expressive power is commonly limited by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test. Many works have recently proposed different ideas to solve the above two problems separately. However, they cannot guarantee all-level tasks generalization, intense expressiveness, and efficient reasoning on all graph tasks simultaneously.In this work, we connect these lines of inquiry to propose a plug-in Equivariant Distance ENcoding (EDEN). EDEN is derived from a series of interpretable transformations on the graph's distance matrix. We theoretically prove that EDEN is permutation-equivariant for all level graph learning task generalization, and we empirically illustrate that EDEN's expressive power can reach up to the 3-WL test. Extensive experiments on real-world datasets show that combining EDEN with conventional GNNs surpasses recent advanced GNNs and position encodings at the same or lower computational complexity.