Abstract
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.
Introduction
For years, the gold standard for measuring the expressive power of a Graph Neural Network (GNN) has been the 1-dimensional Weisfeiler-Leman (1-WL) test. If the 1-WL test can distinguish two graphs, a sufficiently powerful GNN can too. However, this approach is inherently binary: it determines if two graphs are isomorphic or not, but provides no insight into the degree of similarity between them. In practical applications, structural "closeness" is vital; for instance, a small change in a molecule's structure should ideally result in a proportional change in its neural representation.
Furthermore, existing Universal Approximation theorems for GNNs often rely on edit distance, which counts edge flips. Edit distance is often a poor metric for machine learning because graphs with different vertex counts are automatically considered distant, even if they share identical underlying structural patterns. This paper addresses these limitations by moving toward a continuous framework of similarity.
Methodology
The authors bridge the gap between discrete isomorphism and continuous similarity using Graphon Theory. Graphons are continuous limit objects that represent the structure of large, dense graphs.
Continuous 1-WL and Iterated Degree Measures
The core contribution is the extension of the discrete 1-WL test to graphons via Iterated Degree Measures (IDMs). Instead of assigning discrete labels to nodes, the continuous 1-WL assigns measures that describe the distribution of their neighbors' structures. This process is illustrated in Figure 1, where node labels evolve over iterations $h$ to capture increasingly complex neighborhood information.
To quantify the distance between these IDMs, the authors introduce two new metrics:
- $\delta_P$: Based on the Prokhorov metric.
- $\delta_W$: Based on an unbalanced Wasserstein metric.
Topological Framework and Universal Approximation
By treating the space of all graphs as a subset of the compact space of graphons, the authors apply the Stone-Weierstrass theorem. This leads to a Universal Approximation Theorem: MPNNs can approximate any continuous function on graphons that is invariant to the 1-WL test. This unifies several disparate ways of measuring graph similarity—including tree homomorphism densities and "tree distances"—into a single topological framework.
Experimental Evaluation
The theoretical findings were evaluated on standard benchmarks from the TUDataset, including bioinformatics (MUTAG, NCI1, PROTEINS) and social networks (IMDB, REDDIT). Synthetic sequences generated via Stochastic Block Models (SBM) and Erdős-Rényi (ER) models were also used to test structural distance preservation.
Key Results
- Untrained MPNNs: A striking empirical result is that randomly initialized, untrained MPNNs perform competitively with trained ones. For instance, on the MUTAG dataset, an untrained GIN model achieved 82.56% accuracy, compared to 79.01% for a trained version. This suggests that the message-passing architecture itself, mimicking the 1-WL process, captures essential topological features.
- Distance Preservation: Experiments demonstrate that as the hidden dimensionality of an MPNN increases, the Euclidean distance between graph embeddings converges to the structural distance ($\delta_W$) between them.
- Efficiency: Untrained MPNNs offer significant speedups (20%–46% time savings) as they only require optimizing the final linear readout layer.
Discussion and Limitations
While the metrics $\delta_P$ and $\delta_W$ are polynomial-time computable, their upper bounds ($O(h \cdot n^7)$ and $O(h \cdot n^5 \log n)$) may be prohibitive for very large datasets. In such cases, MPNNs can serve as efficient proxies to lower-bound these distances.
Future work remains in extending this fine-grained analysis beyond the 1-WL/MPNN framework to more powerful $k$-WL tests or GNNs capable of counting cycles. Additionally, while the current theory focuses on graph structure and sum-aggregation, exploring other aggregation methods (e.g., max, mean) and a full quantitative treatment of graphs with node features are promising directions for further research.
Summary updated