For decades, evaluating whether two graphs are structurally identical relied on combinatorial algorithms like the Weisfeiler-Lehman (WL) isomorphism test. These tests operate under a strict binary paradigm: two graphs are either isomorphic or they are not.
However, as highlighted by Morris et al. (2024), this binary mindset is fundamentally ill-suited for modern machine learning and optimization. In the real world, data is noisy. If you change a single edge in a massive social network or a molecular graph, a binary test will simply declare the new graph "not isomorphic" to the old one. It cannot tell you that the two graphs are $99.9\%$ identical. This lack of a continuous gradient prevents graph neural networks (GNNs) from smoothly optimizing structural representations, as noted by Böker et al. (2023).
To bridge this gap, a powerful research direction has emerged: reimagining discrete graphs as continuous metric spaces. By treating graph topology geometrically, researchers can measure how much two graphs differ on a smooth, quantifiable scale.
Graphs as Continuous Geometric Objects
The core intuition behind this shift is to stop viewing a graph as merely a static checklist of vertices and edges, and instead view it as a continuous metric space where distances can be measured smoothly.
Discrete View: (A)-------(B)-------(C) --> Nodes are isolated points
Continuous View: A=========[x]========B --> Every point x on the edge
has a real-valued distance
For instance, Dey et al. (2015) propose treating graphs as continuous geometric objects where every point along an edge is a valid position. This ensures that the graph's topological signature remains invariant to how it is discretized or sampled—meaning that adding dummy nodes along an edge won't distort its true shape. Similarly, Gupta et al. (2007) demonstrate that treating edges as continuous line segments allows researchers to analyze structural properties like the "doubling dimension" across the entire metric space without dimensionality explosions.
When edges represent real-world physical distances, this continuous framing becomes essential. Monod and Cao (2025) leverage algebraic geometry to map metric graphs into continuous spaces that are completely robust to edge subdivisions, ensuring that adding a landmark in the middle of a road network doesn't break the similarity calculation.
Softening Isomorphism via Optimal Transport
Once graphs are framed as metric spaces, comparing them becomes a problem of aligning geometric shapes. Instead of looking for an exact combinatorial match, we can use optimal transport to calculate the minimum "work" required to deform one graph into another.
Two primary tools for this are the Gromov-Hausdorff and Gromov-Wasserstein distances:
- Gromov-Hausdorff Distance: Measures the worst-case distortion when embedding one metric space into another. Kaul et al. (2025) use this to model LLM prompts as metric hypergraphs, allowing them to catch adversarial jailbreaks by identifying malicious underlying intent, even when the surface text looks completely different.
- Gromov-Wasserstein Distance: Measures the average distortion based on probability distributions. He et al. (2026) utilize this to build graph foundation models. By treating node degrees as probability measures over a structural metric space, the authors can align completely different datasets (e.g., matching a social network to a molecule) via shared geometric templates.
This geometric relaxation can even be applied directly to the Weisfeiler-Lehman algorithm. Instead of updating discrete color labels, Chen et al. (2022) introduce a continuous WL distance by aggregating neighbor information into probability distributions and comparing them via the Wasserstein distance.
Similarly, Böker et al. (2023) generalize color refinement into continuous "iterated degree measures" over graphons (the continuous limits of graphs), providing a fine-grained expressivity metric. To make these representations resilient to structural noise, Rieck et al. (2019) combine the WL procedure with persistent homology, treating label propagation as a continuous filtration process.
Preserving Metric Structures in Vector Spaces
If graphs have an intrinsic metric structure, then graph neural networks and embedding algorithms should ideally preserve those distances when mapping nodes into vector spaces.
Graph Space (Geodesics) Continuous Embedding Space
(A)---(B)---(C) ==GNN==> A . . B . . C
Distance(A,C) = 2 edges Euclidean Distance = 2.0
To achieve this, Zambon et al. (2018) embed streaming graphs into constant-curvature manifolds (spherical or hyperbolic spaces) where the geodesic distance between points directly approximates the Graph Edit Distance. For algorithmic tasks, Gavrilev (2023) demonstrates that a GNN can be trained to act as a metric mapping into an $L_1$ space, allowing complex graph properties like geodesic convex hulls to be computed in linear time.
However, forcing a model to preserve graph metrics perfectly can introduce trade-offs. Su et al. (2024) study metric distortion—the discrepancy between shortest-path distances in the graph and geometric distances in the embedding space. The authors prove that minimizing metric distortion too aggressively can harm generalization, causing the model to overfit to the local topology of the training set.
When calibrated correctly, these continuous dissimilarity frameworks provide a powerful lens for physical discovery. For example, Tan et al. (2023) utilize a continuous graph dissimilarity metric (ranging smoothly from 0 for identical structures to 1 for completely different ones) to analyze the disordered atomic networks of silica glass, successfully pinpointing the structural origins of its anomalous density behaviors.
Key Foundational Work
Comparing Graphs via Persistence Distortion (2015) — contributed 2 concept elements to this direction.
How to Complete a Doubling Metric (2007) — contributed 1 concept elements to this direction.