Comparing two vectors is computationally trivial: you simply calculate their dot product or Euclidean distance. This simplicity arises because vectors exist in a fixed coordinate system where the $i$-th dimension of one vector directly corresponds to the $i$-th dimension of another.
Graphs enjoy no such luxury. They are combinatorial structures defined purely by relationships, lacking a natural coordinate system or an inherent ordering of nodes. To determine how similar two graphs are, we must solve a fundamental alignment problem: which node in Graph A corresponds to which node in Graph B?
The gold standard for quantifying this structural discrepancy is the Graph Edit Distance (GED)—the minimum cost of sequence operations (node/edge insertions, deletions, and substitutions) required to transform one graph into another. However, as documented across decades of structural pattern recognition research, calculating exact GED or finding a Maximum Common Subgraph (MCS) is an NP-hard combinatorial problem (Graph Edit Distance Computation via Graph Neural Networks; Deep graph similarity learning: a survey). Traditional exact solvers rely on search algorithms like $A^*$ that scale exponentially with graph size, creating a severe computational bottleneck for large-scale applications like molecular analysis, knowledge graph verification, and real-time stream classification.
To bypass this exponential explosion, a powerful research direction has emerged: replacing exact combinatorial search with scalable neural and geometric approximations.
Shifting from Search to Learning
Instead of explicitly traversing an exponential search tree to find the optimal sequence of graph edits, can we train a machine learning model to directly predict the similarity score?
Early attempts at neural graph similarity relied on late fusion (or embedding-based) architectures. In these models, a Graph Neural Network (GNN) maps each graph independently into a fixed-size vector space, and the similarity is computed using a simple metric like cosine distance. While highly scalable—allowing graph embeddings to be pre-computed and indexed offline—compressing an entire graph topology into a single vector inevitably discards fine-grained structural nuances.
To capture these details without sacrificing polynomial-time efficiency, researchers introduced early fusion architectures that incorporate cross-graph matching mechanisms.
Late Fusion: Graph A ──> [ GNN ] ──> Vector A ──┐
├──> Similarity Score
Graph B ──> [ GNN ] ──> Vector B ──┘
Early Fusion: Graph A ──┐
├──> [ Cross-Graph Attention ] ──> Similarity Score
Graph B ──┘
In frameworks like SimGNN, proposed by Yunsheng Bai et al., and Graph Matching Networks, developed by Yujia Li et al., the model does not embed graphs in isolation. Instead, it leverages cross-graph attention layers where nodes in Graph A dynamically "look" at nodes in Graph B during the message-passing phase. This allows the network to compute a soft, differentiable node-alignment matrix early in the pipeline. By aggregating these fine-grained node-to-node interactions before final pooling, the network learns to approximate the underlying combinatorial cost function with remarkable accuracy while maintaining polynomial time complexity.
Enforcing Combinatorial and Geometric Constraints
While unconstrained deep learning models excel at pattern recognition, they often struggle with mathematical consistency. A pure neural network might output a similarity score that violates basic geometric axioms—such as the triangle inequality—or propose node alignments that map a single node to multiple destinations simultaneously.
To address this, modern architectures inject explicit structural and geometric constraints into the learning process.
One approach focuses on regularizing the node-alignment matrix during training. For example, Yun Peng 0002 et al. introduced explicit regularizers, such as a "plane intersection" penalty, to mathematically enforce one-to-one node mapping constraints within the neural network.
To resolve the trade-off between the accuracy of early fusion and the speed of late fusion, Wei Zhuo et al. proposed moving the expensive node-matching computation entirely into a training-only regularization term. By penalizing the model during training if its independent graph embeddings fail to reflect the optimal structural alignment, the framework preserves cross-graph awareness while allowing lightning-fast, pair-independent inference.
Furthermore, for applications like database retrieval where indexing is mandatory, the learned representations must behave like a true metric space. The GREED framework, introduced by Rishabh Ranjan et al., achieves this by embedding graphs into a representation space that strictly preserves the triangle inequality. This geometric guarantee ensures that standard metric trees can prune the search space effectively, enabling efficient indexing without exhaustive pairwise comparisons.
The Geometric Alternative: Optimal Transport
A parallel paradigm avoids neural black boxes altogether by reformulating graph matching as a continuous geometric optimization problem through the lens of Optimal Transport (OT).
Instead of treating node alignment as a discrete, all-or-nothing permutation matrix, OT treats nodes as probability masses distributed across a metric space. The goal is to find a continuous "coupling matrix" that minimizes the total work required to transport the probability mass of Graph A into Graph B.
When graphs contain both local node attributes and global topological structures, this problem is naturally framed using the Fused Gromov-Wasserstein (FGW) distance. Jianheng Tang demonstrates that reformulating GED computation as an FGW alignment problem allows researchers to relax the hard, discrete combinatorial constraints into a continuous optimization landscape. This continuous relaxation can be solved efficiently using iterative algorithms, bypassing the NP-hard bottleneck entirely while providing explicit, explainable node alignments and massive speedups.
Discrete Matching (NP-Hard): Continuous OT Relaxation (Polynomial):
Graph A Graph B Graph A Graph B
Node 1 ───> Node 1 Node 1 ───┬─0.7───> Node 1
Node 2 ───> Node 2 └─0.3───> Node 2
(Hard 1-to-1 permutations) (Soft, continuous mass distribution)
By bridging qualitative graph structures with quantitative optimal transport distances—as explored by Samantha Chen et al. in their unification of the Weisfeiler-Lehman isomorphism test with Gromov-Wasserstein metrics—this research direction provides a mathematically rigorous, polynomial-time foundation for comparing complex networks. Whether through continuous geometric relaxations or structured neural networks, the field has successfully shifted graph similarity from an intractable search problem to a scalable, continuous computation.