Complete and continuous representations of Euclidean graphs

TL;DR — We developed complete and continuous invariants for straight-line graphs under Euclidean isometry, which are computable in polynomial time, and explain structure-property relations on the QM9 dataset of 130+ thousand molecules for the first time.

Abstract

Euclidean graphs have unordered vertices and non-intersecting straight-line edges in any Euclidean space. The main application is for molecular graphs with vertices at atomic centers and edges representing inter-atomic bonds. Euclidean graphs are considered equivalent if they are related by isometry (any distance-preserving transformation). This paper introduces the strongest descriptors that are provably (1) invariant under any isometry, (2) complete and sufficient to reconstruct any Euclidean graph up to isometry, (3) Lipschitz continuous so that perturbations of all vertices within their epsilon-neighborhoods change the complete invariant up to a constant multiple of epsilon in a suitable metric, and (4) computable (both invariant and metric) in a polynomial time in the number of vertices for a fixed dimension. These strongest invariants transparently explained a continuous structure-property landscape for molecular graphs from the QM9 database of 130K+ molecules.