# Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 93 references that are in the map.
- First posted on arXiv 20 Oct 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Deep Graph Matching Consensus](https://mlsanity.com/paper/2001.09621/) (2020)
- [Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers](https://mlsanity.com/paper/2003.11657/) (2020)
- [NeVAE: A Deep Generative Model for Molecular Graphs](https://mlsanity.com/paper/1802.05283/) (2018)
- [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)
- [GLSearch: Maximum Common Subgraph Detection via Learning to Search](https://mlsanity.com/paper/2002.03129/) (2020)
- [UNIQORN: Unified Question Answering over RDF Knowledge Graphs and Natural Language Text](https://mlsanity.com/paper/2108.08614/) (2021)
- [Stochastic Iterative Graph Matching](https://mlsanity.com/paper/2106.02206/) (2021)

## Built on by (most cited first, 8 of 8)

- [Graph Edit Distance with General Costs Using Neural Set Divergence](https://mlsanity.com/paper/2409.17687/) (2024)
- [Neural Graduated Assignment for Maximum Common Edge Subgraphs](https://mlsanity.com/paper/2505.12325/) (2025)
- [Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval](https://mlsanity.com/paper/2510.22538/) (2025)
- [Graph2Region: Efficient Graph Similarity Learning with Structure and Scale Restoration](https://mlsanity.com/paper/2510.00394/) (2025)
- [Hierarchy-Aware Neural Subgraph Matching with Enhanced Similarity Measure](https://mlsanity.com/paper/2510.00402/) (2025)
- [Contextual Tokenization for Graph Inverted Indices](https://mlsanity.com/paper/2510.22479/) (2025)
- [Federated Layer-Wise Exchange for Cross-Client Money Laundering Pattern Detection](https://mlsanity.com/paper/2605.06433/) (2026)
- [Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs](https://mlsanity.com/paper/2609.32661/) (2026)

## Abstract (arXiv)

The graph retrieval problem is to search in a large corpus of graphs for ones that are most similar to a query graph. A common consideration for scoring similarity is the maximum common subgraph (MCS) between the query and corpus graphs, usually counting the number of common edges (i.e., MCES). In some applications, it is also desirable that the common subgraph be connected, i.e., the maximum common connected subgraph (MCCS). Finding exact MCES and MCCS is intractable, but may be unnecessary if ranking corpus graphs by relevance is the goal. We design fast and trainable neural functions that approximate MCES and MCCS well. Late interaction methods compute dense representations for the query and corpus graph separately, and compare these representations using simple similarity functions at the last stage, leading to highly scalable systems. Early interaction methods combine information from both graphs right from the input stages, are usually considerably more accurate, but slower. We propose both late and early interaction neural MCES and MCCS formulations. They are both based on a continuous relaxation of a node alignment matrix between query and corpus nodes. For MCCS, we propose a novel differentiable network for estimating the size of the largest connected common subgraph. Extensive experiments with seven data sets show that our proposals are superior among late interaction models in terms of both accuracy and speed. Our early interaction models provide accuracy competitive with the state of the art, at substantially greater speeds.