# Deep Graph Matching Consensus

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

## Key facts

- Cited by 85 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2020.

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

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Learning to Match Features with Seeded Graph Matching Network](https://mlsanity.com/paper/2108.08771/) (2021)
- [A comprehensive survey on point cloud registration](https://mlsanity.com/paper/2103.02690/) (2021)
- [ClusterGNN: Cluster-based Coarse-to-Fine Graph Neural Network for Efficient Feature Matching](https://mlsanity.com/paper/2204.11700/) (2022)
- [PyG 2.0: Scalable Learning on Real World Graphs](https://mlsanity.com/paper/2507.16991/) (2025)
- [CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints](https://mlsanity.com/paper/2105.02343/) (2021)
- [MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers](https://mlsanity.com/paper/2205.14210/) (2022)
- [Boost then Convolve: Gradient Boosting Meets Graph Neural Networks](https://mlsanity.com/paper/2101.08543/) (2021)
- [Convolutional Hough Matching Networks](https://mlsanity.com/paper/2103.16831/) (2021)
- [Equivariant Deep Weight Space Alignment](https://mlsanity.com/paper/2310.13397/) (2023)
- [SelfKG: Self-Supervised Entity Alignment in Knowledge Graphs](https://mlsanity.com/paper/2203.01044/) (2022)
- [Graph Matching with Bi-level Noisy Correspondence](https://mlsanity.com/paper/2212.04085/) (2022)
- [RAGA: Relation-aware Graph Attention Networks for Global Entity Alignment](https://mlsanity.com/paper/2103.00791/) (2021)
- [Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey](https://mlsanity.com/paper/2305.05080/) (2023)
- [From Alignment to Assignment: Frustratingly Simple Unsupervised Entity Alignment](https://mlsanity.com/paper/2109.02363/) (2021)
- [Towards Graph Contrastive Learning: A Survey and Beyond](https://mlsanity.com/paper/2405.11868/) (2024)
- [Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks](https://mlsanity.com/paper/2211.03232/) (2022)
- [Knowing the No-match: Entity Alignment with Dangling Cases](https://mlsanity.com/paper/2106.02248/) (2021)
- [ClusterEA: Scalable Entity Alignment with Stochastic Training and Normalized Mini-batch Similarities](https://mlsanity.com/paper/2205.10312/) (2022)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [Unsupervised Entity Alignment for Temporal Knowledge Graphs](https://mlsanity.com/paper/2302.00796/) (2023)
- [Deep Graph Matching under Quadratic Constraint](https://mlsanity.com/paper/2103.06643/) (2021)
- [LightEA: A Scalable, Robust, and Interpretable Entity Alignment Framework via Three-view Label Propagation](https://mlsanity.com/paper/2210.10436/) (2022)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [A Unified Framework for Rank-based Evaluation Metrics for Link Prediction in Knowledge Graphs](https://mlsanity.com/paper/2203.07544/) (2022)
- [Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport](https://mlsanity.com/paper/2301.12721/) (2023)
- [Graph Mixup with Soft Alignments](https://mlsanity.com/paper/2306.06788/) (2023)
- [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)

## Abstract (arXiv)

This work presents a two-stage neural architecture for learning and refining structural correspondences between graphs. First, we use localized node embeddings computed by a graph neural network to obtain an initial ranking of soft correspondences between nodes. Secondly, we employ synchronous message passing networks to iteratively re-rank the soft correspondences to reach a matching consensus in local neighborhoods between graphs. We show, theoretically and empirically, that our message passing scheme computes a well-founded measure of consensus for corresponding neighborhoods, which is then used to guide the iterative re-ranking process. Our purely local and sparsity-aware architecture scales well to large, real-world inputs while still being able to recover global correspondences consistently. We demonstrate the practical effectiveness of our method on real-world tasks from the fields of computer vision and entity alignment between knowledge graphs, on which we improve upon the current state-of-the-art. Our source code is available under https://github.com/rusty1s/ deep-graph-matching-consensus.