  Graph neural networks (GNN) are very popular methods in machine learning and
have been applied very successfully to the prediction of the properties of
molecules and materials. First-order GNNs are well known to be incomplete,
i.e., there exist graphs that are distinct but appear identical when seen
through the lens of the GNN. More complicated schemes have thus been designed
to increase their resolving power. Applications to molecules (and more
generally, point clouds), however, add a geometric dimension to the problem.
The most straightforward and prevalent approach to construct graph
representation for molecules regards atoms as vertices in a graph and draws a
bond between each pair of atoms within a chosen cutoff. Bonds can be decorated
with the distance between atoms, and the resulting "distance graph NNs" (dGNN)
have empirically demonstrated excellent resolving power and are widely used in
chemical ML, with all known indistinguishable configurations being resolved in
the fully-connected limit, which is equivalent to infinite or sufficiently
large cutoff. Here we present a counterexample that proves that dGNNs are not
complete even for the restricted case of fully-connected graphs induced by 3D
atom clouds. We construct pairs of distinct point clouds whose associated
graphs are, for any cutoff radius, equivalent based on a first-order
Weisfeiler-Lehman test. This class of degenerate structures includes
chemically-plausible configurations, both for isolated structures and for
infinite structures that are periodic in 1, 2, and 3 dimensions. The existence
of indistinguishable configurations sets an ultimate limit to the expressive
power of some of the well-established GNN architectures for atomistic machine
learning. Models that explicitly use angular or directional information in the
description of atomic environments can resolve this class of degeneracies.
