  Numerous recent works have analyzed the expressive power of message-passing
graph neural networks (MPNNs), primarily utilizing combinatorial techniques
such as the $1$-dimensional Weisfeiler-Leman test ($1$-WL) for the graph
isomorphism problem. However, the graph isomorphism objective is inherently
binary, not giving insights into the degree of similarity between two given
graphs. This work resolves this issue by considering continuous extensions of
both $1$-WL and MPNNs to graphons. Concretely, we show that the continuous
variant of $1$-WL delivers an accurate topological characterization of the
expressive power of MPNNs on graphons, revealing which graphs these networks
can distinguish and the level of difficulty in separating them. We identify the
finest topology where MPNNs separate points and prove a universal approximation
theorem. Consequently, we provide a theoretical framework for graph and graphon
similarity combining various topological variants of classical
characterizations of the $1$-WL. In particular, we characterize the expressive
power of MPNNs in terms of the tree distance, which is a graph distance based
on the concept of fractional isomorphisms, and substructure counts via tree
homomorphisms, showing that these concepts have the same expressive power as
the $1$-WL and MPNNs on graphons. Empirically, we validate our theoretical
findings by showing that randomly initialized MPNNs, without training, exhibit
competitive performance compared to their trained counterparts. Moreover, we
evaluate different MPNN architectures based on their ability to preserve graph
distances, highlighting the significance of our continuous $1$-WL test in
understanding MPNNs' expressivity.
