  Graph Neural Networks (GNNs) have emerged as a prominent research topic in
the field of machine learning. Existing GNN models are commonly categorized
into two types: spectral GNNs, which are designed based on polynomial graph
filters, and spatial GNNs, which utilize a message-passing scheme as the
foundation of the model. For the expressive power and universality of spectral
GNNs, a natural approach is to improve the design of basis functions for better
approximation ability. As for spatial GNNs, models like Graph Isomorphism
Networks (GIN) analyze their expressive power based on Graph Isomorphism Tests.
Recently, there have been attempts to establish connections between spatial
GNNs and geometric concepts like curvature and cellular sheaves, as well as
physical phenomena like oscillators. However, despite the recent progress,
there is still a lack of comprehensive analysis regarding the universality of
spatial GNNs from the perspectives of geometry and physics. In this paper, we
propose MetricGNN (MGNN), a spatial GNN model inspired by the
congruent-insensitivity property of classifiers in the classification phase of
GNNs. We demonstrate that a GNN model is universal in the spatial domain if it
can generate embedding matrices that are congruent to any given embedding
matrix. This property is closely related to the Distance Geometry Problem
(DGP). Since DGP is an NP-Hard combinatorial optimization problem, we propose
optimizing an energy function derived from spring networks and the
Multi-Dimensional Scaling (MDS) problem. This approach also allows our model to
handle both homophilic and heterophilic graphs. Finally, we propose employing
the iteration method to optimize our energy function. We extensively evaluate
the effectiveness of our model through experiments conducted on both synthetic
and real-world datasets. Our code is available at:
https://github.com/GuanyuCui/MGNN.
