Determining if two graphs are similar is a fundamental challenge in computer science, underlying everything from drug discovery to social network analysis. Traditionally, this was treated as a combinatorial search problem—finding the minimum number of edits (insertions, deletions, or relabelings) to transform one graph into another, known as the Graph Edit Distance (GED). Because this is NP-hard, traditional solvers are notoriously slow.
The first wave of deep learning solutions, surveyed by Guixiang Ma and Philip S. Yu, replaced these slow algorithms with Graph Neural Networks (GNNs). These models compress entire graphs into vectors and compute a scalar similarity score. While fast, these models are "black boxes": they might tell you two molecules are 90% similar, but they cannot explain which atoms match or why the score was given.
A new research direction is moving beyond these scalar scores toward interpretable structural alignments. Instead of just predicting a number, these models reveal the specific node-to-node mappings and transformation paths that define similarity.
From Vectors to Similarity Matrices
The first step toward interpretability is moving away from global graph embeddings. In GraphSim and GSimCNN, Yunsheng Bai and Wei Wang proposed treating graph similarity as a pattern recognition task.
Instead of condensing a graph into a single vector, they compute pairwise similarities between all nodes in Graph A and all nodes in Graph B. This creates a similarity matrix—essentially an image where each pixel represents how well two nodes match. By processing these matrices with Convolutional Neural Networks (CNNs), the model can "see" structural patterns and clusters of matching nodes. This provides a visual heatmap of the correspondence between two graphs, making the model’s reasoning transparent.
Differentiable Node Alignment
While similarity matrices show potential matches, they don't always provide a strict one-to-one mapping. To solve this, Jingjing Wang and Haoran Xie introduced GNA (Neural Node Alignment).
GNA uses a differentiable Gumbel-Sinkhorn module to force the network to commit to a specific permutation matrix. This mathematical "trick" allows the model to learn an explicit node-to-node alignment during training without needing expensive ground-truth labels. Surprisingly, providing this structural explanation doesn't hurt performance; Wang found that enforcing these alignments actually improves the precision of graph retrieval.
Similarity as a Sequential Process
Real-world graph comparison often requires knowing the exact sequence of changes—the "edit path." Recent work by Paolo Pellizzoni in GELATO treats graph matching as an autoregressive decision process.
Instead of predicting a score in one shot, the model builds a matching step-by-step, conditioning each new node match on the ones made previously. This mirrors how a human might compare two diagrams, piece by piece. Similarly, Runzhong Wang and Junchi Yan developed GENN-A*, a hybrid approach that uses GNNs to learn a heuristic for the classic A* search algorithm. This combination provides the best of both worlds: the speed of neural networks and the guaranteed, interpretable edit paths of traditional combinatorial solvers.
Expanding the Scope: Edges and Symbolic Logic
The push for interpretability has also shifted the focus from nodes to edges and symbolic reasoning:
- Edge Alignment: In ISONET, Indradyumna Roy and Abir De argue that for subgraph matching, aligning edges is more critical than aligning nodes. By focusing on how relationships (edges) map between graphs, they achieve higher accuracy in finding small query graphs within large databases.
- Symbolic Heuristics: Samidha Verma and Sayan Ranu introduced GRAIL, which uses Large Language Models (LLMs) to generate symbolic code for graph matching. This moves the "logic" of the similarity out of the neural weights and into readable, executable code.
By shifting from "what is the score?" to "how do these structures align?", this research direction is making graph similarity models more reliable for sensitive domains like medical diagnosis and software security, where understanding the why is just as important as the result.