# Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching

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

## Key facts

- Cited by 84 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2019.

## Built on by (most cited first, 30 of 84)

- [Going Beyond Linear Mode Connectivity: The Layerwise Linear Feature Connectivity](https://mlsanity.com/paper/2307.08286/) (2023)
- [Graph Matching with Bi-level Noisy Correspondence](https://mlsanity.com/paper/2212.04085/) (2022)
- [Jigsaw: Learning to Assemble Multiple Fractured Objects](https://mlsanity.com/paper/2305.17975/) (2023)
- [A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2106.04927/) (2021)
- [C2M3: Cycle-Consistent Multi-Model Merging](https://mlsanity.com/paper/2405.17897/) (2024)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs](https://mlsanity.com/paper/2406.05938/) (2024)
- [LinSATNet: The Positive Linear Satisfiability Neural Networks](https://mlsanity.com/paper/2407.13917/) (2024)
- [Graph Mixup with Soft Alignments](https://mlsanity.com/paper/2306.06788/) (2023)
- [Factor Graph Neural Networks](https://mlsanity.com/paper/2308.00887/) (2023)
- [Equivariant Hypergraph Neural Networks](https://mlsanity.com/paper/2208.10428/) (2022)
- [Stochastic Iterative Graph Matching](https://mlsanity.com/paper/2106.02206/) (2021)
- [Joint Graph Learning and Matching for Semantic Feature Correspondence](https://mlsanity.com/paper/2109.00240/) (2021)
- [Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approach](https://mlsanity.com/paper/2201.05158/) (2022)
- [Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching](https://mlsanity.com/paper/2301.02780/) (2023)
- [SG-Reg: Generalizable and Efficient Scene Graph Registration](https://mlsanity.com/paper/2504.14440/) (2025)
- [GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent](https://mlsanity.com/paper/2409.17500/) (2024)
- [DOGE-Train: Discrete Optimization on GPU with End-to-end Training](https://mlsanity.com/paper/2205.11638/) (2022)
- [Double-Bounded Optimal Transport for Advanced Clustering and Classification](https://mlsanity.com/paper/2401.11418/) (2024)
- [Ensemble Quadratic Assignment Network for Graph Matching](https://mlsanity.com/paper/2403.06457/) (2024)
- [TsCA: On the Semantic Consistency Alignment via Conditional Transport for Compositional Zero-Shot Learning](https://mlsanity.com/paper/2408.08703/) (2024)
- [Kissing to Find a Match: Efficient Low-Rank Permutation Representation](https://mlsanity.com/paper/2308.13252/) (2023)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Categorical Data Clustering via Value Order Estimated Distance Metric Learning](https://mlsanity.com/paper/2411.15189/) (2024)
- [Explaining Vision and Language through Graphs of Events in Space and Time](https://mlsanity.com/paper/2309.08612/) (2023)
- [Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem](https://mlsanity.com/paper/2406.09899/) (2024)
- [Joint Deep Multi-Graph Matching and 3D Geometry Learning from Inhomogeneous 2D Image Collections](https://mlsanity.com/paper/2103.17229/) (2021)
- [SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching](https://mlsanity.com/paper/2205.13679/) (2022)
- [Kernelized multi-graph matching](https://mlsanity.com/paper/2210.05206/) (2022)

## Abstract (arXiv)

Graph matching involves combinatorial optimization based on edge-to-edge affinity matrix, which can be generally formulated as Lawler's Quadratic Assignment Problem (QAP). This paper presents a QAP network directly learning with the affinity matrix (equivalently the association graph) whereby the matching problem is translated into a constrained vertex classification task. The association graph is learned by an embedding network for vertex classification, followed by Sinkhorn normalization and a cross-entropy loss for end-to-end learning. We further improve the embedding model on association graph by introducing Sinkhorn based matching-aware constraint, as well as dummy nodes to deal with unequal sizes of graphs. To our best knowledge, this is one of the first network to directly learn with the general Lawler's QAP. In contrast, recent deep matching methods focus on the learning of node/edge features in two graphs respectively. We also show how to extend our network to hypergraph matching, and matching of multiple graphs. Experimental results on both synthetic graphs and real-world images show its effectiveness. For pure QAP tasks on synthetic data and QAPLIB benchmark, our method can perform competitively and even surpass state-of-the-art graph matching and QAP solvers with notable less time cost. We provide a project homepage at http://thinklab.sjtu.edu.cn/project/NGM/index.html.