# Learning Combinatorial Embedding Networks for Deep Graph Matching

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

## Key facts

- Cited by 99 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2019.

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

- [Vision GNN: An Image is Worth Graph of Nodes](https://mlsanity.com/paper/2206.00272/) (2022)
- [Robust Point Cloud Registration Framework Based on Deep Graph Matching](https://mlsanity.com/paper/2103.04256/) (2021)
- [Learning to Match Features with Seeded Graph Matching Network](https://mlsanity.com/paper/2108.08771/) (2021)
- [ClusterGNN: Cluster-based Coarse-to-Fine Graph Neural Network for Efficient Feature Matching](https://mlsanity.com/paper/2204.11700/) (2022)
- [Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking](https://mlsanity.com/paper/2103.16178/) (2021)
- [Multi-scale Matching Networks for Semantic Correspondence](https://mlsanity.com/paper/2108.00211/) (2021)
- [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)
- [Densely Constrained Depth Estimator for Monocular 3D Object Detection](https://mlsanity.com/paper/2207.10047/) (2022)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [Eliminating Gradient Conflict in Reference-based Line-Art Colorization](https://mlsanity.com/paper/2207.06095/) (2022)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [Annealed Training for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2207.11542/) (2022)
- [A Graph-Based Approach for Category-Agnostic Pose Estimation](https://mlsanity.com/paper/2311.17891/) (2023)
- [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)
- [Factor Graph Neural Networks](https://mlsanity.com/paper/2308.00887/) (2023)
- [SRFeat: Learning Locally Accurate and Globally Consistent Non-Rigid Shape Correspondence](https://mlsanity.com/paper/2209.07806/) (2022)
- [Learning to Count Isomorphisms with Graph Neural Networks](https://mlsanity.com/paper/2302.03266/) (2023)
- [Learning Multi-Attention Context Graph for Group-Based Re-Identification](https://mlsanity.com/paper/2104.14236/) (2021)
- [Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More](https://mlsanity.com/paper/2107.06876/) (2021)
- [Pose-guided Inter- and Intra-part Relational Transformer for Occluded Person Re-Identification](https://mlsanity.com/paper/2109.03483/) (2021)
- [Stochastic Iterative Graph Matching](https://mlsanity.com/paper/2106.02206/) (2021)
- [Multi-Robot Active Mapping via Neural Bipartite Graph Matching](https://mlsanity.com/paper/2203.16319/) (2022)
- [MATA*: Combining Learnable Node Matching with A* Algorithm for Approximate Graph Edit Distance Computation](https://mlsanity.com/paper/2311.02356/) (2023)
- [SG-PGM: Partial Graph Matching Network with Semantic Geometric Fusion for 3D Scene Graph Alignment and Its Downstream Tasks](https://mlsanity.com/paper/2403.19474/) (2024)
- [TacoDepth: Towards Efficient Radar-Camera Depth Estimation with One-stage Fusion](https://mlsanity.com/paper/2504.11773/) (2025)
- [Joint Graph Learning and Matching for Semantic Feature Correspondence](https://mlsanity.com/paper/2109.00240/) (2021)
- [Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks](https://mlsanity.com/paper/2210.11020/) (2022)

## Abstract (arXiv)

Graph matching refers to finding node correspondence between graphs, such that the corresponding node and edge's affinity can be maximized. In addition with its NP-completeness nature, another important challenge is effective modeling of the node-wise and structure-wise affinity across graphs and the resulting objective, to guide the matching procedure effectively finding the true matching against noises. To this end, this paper devises an end-to-end differentiable deep network pipeline to learn the affinity for graph matching. It involves a supervised permutation loss regarding with node correspondence to capture the combinatorial nature for graph matching. Meanwhile deep graph embedding models are adopted to parameterize both intra-graph and cross-graph affinity functions, instead of the traditional shallow and simple parametric forms e.g. a Gaussian kernel. The embedding can also effectively capture the higher-order structure beyond second-order edges. The permutation loss model is agnostic to the number of nodes, and the embedding model is shared among nodes such that the network allows for varying numbers of nodes in graphs for training and inference. Moreover, our network is class-agnostic with some generalization capability across different categories. All these features are welcomed for real-world applications. Experiments show its superiority against state-of-the-art graph matching learning methods.