# Charting the Design Space of Neural Graph Representations for Subgraph Matching

arXiv: https://arxiv.org/abs/2510.22897 · HTML: https://mlsanity.com/paper/2510.22897/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 55 references that are in the map.
- First posted on arXiv 27 Oct 2025.

## Builds on (most cited first, 22 of 22)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [Entailment as Few-Shot Learner](https://mlsanity.com/paper/2104.14690/) (2021)
- [Order-Embeddings of Images and Language](https://mlsanity.com/paper/1511.06361/) (2015)
- [Relation-Aware Entity Alignment for Heterogeneous Knowledge Graphs](https://mlsanity.com/paper/1908.08210/) (2019)
- [A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multimodal](https://mlsanity.com/paper/2212.05767/) (2022)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [FIRST: Faster Improved Listwise Reranking with Single Token Decoding](https://mlsanity.com/paper/2406.15657/) (2024)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)
- [TransEdge: Translating Relation-contextualized Embeddings for Knowledge Graphs](https://mlsanity.com/paper/2004.13579/) (2020)
- [Uncertain Natural Language Inference](https://mlsanity.com/paper/1909.03042/) (2019)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [RAGA: Relation-aware Graph Attention Networks for Global Entity Alignment](https://mlsanity.com/paper/2103.00791/) (2021)
- [Efficient Graph Similarity Computation with Alignment Regularization](https://mlsanity.com/paper/2406.14929/) (2024)
- [Deep Graph Matching and Searching for Semantic Code Retrieval](https://mlsanity.com/paper/2010.12908/) (2020)
- [Relation-Aware Neighborhood Matching Model for Entity Alignment](https://mlsanity.com/paper/2012.08128/) (2020)
- [Unsupervised Graph Neural Architecture Search with Disentangled Self-supervision](https://mlsanity.com/paper/2403.05064/) (2024)
- [Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval](https://mlsanity.com/paper/2510.22538/) (2025)

## Abstract (arXiv)

Subgraph matching is vital in knowledge graph (KG) question answering, molecule design, scene graph, code and circuit search, etc. Neural methods have shown promising results for subgraph matching. Our study of recent systems suggests refactoring them into a unified design space for graph matching networks. Existing methods occupy only a few isolated patches in this space, which remains largely uncharted. We undertake the first comprehensive exploration of this space, featuring such axes as attention-based vs. soft permutation-based interaction between query and corpus graphs, aligning nodes vs. edges, and the form of the final scoring network that integrates neural representations of the graphs. Our extensive experiments reveal that judicious and hitherto-unexplored combinations of choices in this space lead to large performance benefits. Beyond better performance, our study uncovers valuable insights and establishes general design principles for neural graph representation and interaction, which may be of wider interest.