# Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 26 Sep 2026.

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

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [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)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [SimGNN: A Neural Network Approach to Fast Graph Similarity Computation](https://mlsanity.com/paper/1808.05689/) (2018)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [GLSearch: Maximum Common Subgraph Detection via Learning to Search](https://mlsanity.com/paper/2002.03129/) (2020)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [More Interpretable Graph Similarity Computation via Maximum Common Subgraph Inference](https://mlsanity.com/paper/2208.04580/) (2022)
- [Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks](https://mlsanity.com/paper/2210.11020/) (2022)
- [Learning structured approximations of combinatorial optimization problems](https://mlsanity.com/paper/2107.04323/) (2021)
- [Ensemble Quadratic Assignment Network for Graph Matching](https://mlsanity.com/paper/2403.06457/) (2024)
- [New Auction Algorithms for the Assignment Problem and Extensions](https://mlsanity.com/paper/2310.03159/) (2023)
- [Neural Graduated Assignment for Maximum Common Edge Subgraphs](https://mlsanity.com/paper/2505.12325/) (2025)

## Abstract (arXiv)

Maximum common edge subgraph (MCES) matching finds a partial vertex correspondence between two labeled graphs that preserves as many labeled edges as possible. Molecular similarity search requires matching many graph pairs, making the cost of repeated queries important. The strongest baseline attains accurate MCES solutions but trains a separate network for each pair. We introduce Equivariant Neural Primal-Dual Assignment (ENPDA), which learns a shared matching policy and applies it to new pairs without further training, answering queries roughly three orders of magnitude faster and recovering its training cost after a few dozen queries. The policy recomputes exact objective marginals for candidate matches and learns corrections and step sizes that update their scores. Target prices respond to competition when several source vertices favor the same target. Four update rounds and a Hungarian projection produce a partial one-to-one matching. We prove per-pair guarantees that hold for any network parameters. In exact arithmetic, reordering either graph permutes the assignment and price states, the projected matching is one-to-one, and repaired prices give a valid MCES upper bound. Subtracting the preserved-edge count bounds the optimality gap; combined with structural caps, these certificates prove global optimality for 60 of 291 native test pairs. On three molecular benchmarks with disjoint train/validation/test splits, ENPDA improves over an analytic counterpart with the same update and projection budget by 7.4-8.6 accuracy points; after one second of refinement search, 2.5-3 points of the gain remain. Transferred without fine-tuning to edge-deletion tasks from social and protein graphs, the policy gains 9.1-17.6 points over the analytic counterpart. When output matchings must keep aromatic rings intact, ENPDA recovers more reference bonds than the baselines on all three datasets.