Interpretable Graph Similarity and Structural Alignment

16 concepts14 papers1 proposal

Imagine comparing two complex networks—such as chemical molecules or social graphs. A traditional deep learning model might ingest both structures and output a single scalar value: Similarity = 0.85. While computationally efficient, this black-box number leaves domain experts entirely in the dark. Why are they similar? Which subgraphs match? What specific transformations bridge the gap between them?

As noted in comprehensive surveys by Guixiang Ma et al. and Shruti Saxena, this lack of structural interpretability has long been a major bottleneck in deploying graph similarity models to high-stakes fields like drug discovery and network alignment. The limitation traces back to early graph mining paradigms; as Glen Jeh et al. observed, providing numerical metrics without underlying explanations severely hinders our capacity to understand data relationships.

To solve this, a major research direction has emerged that shifts the focus from opaque distance estimation to interpretable structural alignment. Instead of compressing graphs into isolated embeddings, these modern frameworks force models to expose their internal reasoning through explicit node mappings, traceable edit paths, or shared structural descriptions.

Explicit Node and Edge Alignment Matrices

The most direct way to make a graph comparison interpretable is to force the model to compute a node-to-node or edge-to-edge correspondence matrix. Instead of reducing a graph pair to a single scalar via global pooling, these methods preserve fine-grained structural relationships throughout the alignment process.

For instance, Titouan Vayer et al. demonstrated how the mathematical framework of Optimal Transport can be leveraged to yield a principled metric that provides an explicit, interpretable mapping between the components of structured objects. In the neural domain, rather than relying on unconstrained representations, Chaolong Ying et al. introduced a framework that replaces fixed heuristics with a learnable neural mechanism to produce an explicit node-to-node assignment matrix.

This concept extends naturally to subgraphs and alternative modalities. Indradyumna Roy et al. developed networks that utilize explicit soft-alignment matrices to approximate complex similarity measures like the maximum common subgraph. In natural language processing, Chen Xu et al. framed semantic sentence matching as a fine-grained graph alignment problem, using explicit alignment matrices to allow researchers to audit the specific linguistic and syntactic patterns driving a model's decisions.

Why it works: By constraining the model to output a matrix where elements represent the strength of alignment between specific pairs of nodes or edges, the network cannot hide its reasoning. If the model claims two graphs are highly similar, it must justify that claim by showing a coherent, structurally sound mapping across the entire topology. This matrix serves as a built-in visual explanation that can be audited directly by domain experts.

Traceable Edit Paths and Sequential Decisions

Another prominent paradigm focuses on Graph Edit Distance (GED)—the minimum cost required to transform one graph into another via node and edge insertions, deletions, or substitutions. Traditional neural networks attempt to regress this distance directly as a scalar, which often fails to guarantee that the predicted distance corresponds to a physically possible sequence of edits.

To inject transparency, researchers have begun designing hybrid and generative architectures that output the exact sequence of transformations. Runzhong Wang et al. pioneered this by combining the interpretability of traditional A* search with the efficiency of Graph Neural Networks (GNNs), using a dynamic embedding strategy to learn a search heuristic that uncovers optimal edit paths.

Taking a purely generative approach, Paolo Pellizzoni et al. formulated GED as an autoregressive decision process. Their framework, GELATO, predicts node matches step-by-step, conditioning each choice on previous decisions to ensure a mathematically valid upper bound for the transformation cost. Similarly, Aditya Bommakanti et al. developed EUGENE, an algebraic optimization method that bypasses black-box neural training entirely to provide an explicit, explainable edit path. To avoid expensive ground-truth training data altogether, Samidha Verma et al. introduced GRAIL, which utilizes Large Language Models to discover symbolic heuristics that explicitly map node alignments and edit sequences.

Why it works: By breaking down a global distance score into a discrete, sequential recipe of edits, these models replace abstract vector math with concrete structural operations. The final distance score is no longer an unverified guess; it is the direct, verifiable summation of the step-by-step edit path generated by the model.

Similarity as a Shared Structural Model

A third facet of this research direction redefines graph similarity entirely: moving away from measuring distance to describing commonality.

For example, Indradyumna Roy et al. shifted the focus from global node alignment to explicit edge alignment in their ISONET framework, allowing users to extract and visualize the exact subgraphs responsible for a retrieval match.

Taking this descriptive philosophy further, Corinna Coupette et al. argued that graph similarity should be treated as a description problem rather than a measurement problem. Their framework, Momo, leverages the Minimum Description Length (MDL) principle to identify specific shared structures—such as cliques, stars, and dense clusters—providing a qualitative "common model" alongside a robust similarity score. To handle multiple, unaligned graphs of varying sizes, Iiro Kumpulainen et al. introduced the Shared Stochastic Block Model (SSBM), which qualifies similarity by identifying common connectivity patterns and functional regions across complex systems without needing prior node correspondences.

Why it works: This approach works by decomposing graph comparison into a shared core model plus individual differences. By framing similarity through the lens of data compression or block modeling, the model naturally isolates the conserved topological motifs. The explanation is built directly into the objective function: two graphs are similar precisely because they can be efficiently described by the same structural blueprint.

Key Foundational Work

Optimal Transport for structured data with application on graphs (2019) — contributed 1 concept elements to this direction.
Mining the space of graph properties (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_black_box_similarity_scoring_629c146f,
  title = {black-box similarity scoring},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/black-box-similarity-scoring/rdr_629c146f5893490bb8a3f8a47e43b4b5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_black_box_similarity_scoring_629c146f_v1,
  title = {black-box similarity scoring},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/black-box-similarity-scoring/rdr_629c146f5893490bb8a3f8a47e43b4b5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake