# (Probably) Concave Graph Matching

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2018.

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

- [Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters](https://mlsanity.com/paper/2202.03813/) (2022)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [Linear Partial Gromov-Wasserstein Embedding](https://mlsanity.com/paper/2410.16669/) (2024)
- [Incentive Compatible Pareto Alignment for Multi-Source Large Graphs](https://mlsanity.com/paper/2112.02792/) (2021)
- [Chaining 2-FWL GNNs for Combinatorial Graph Alignment](https://mlsanity.com/paper/2510.03086/) (2025)
- [On sparsity, extremal structure, and monotonicity properties of Wasserstein and Gromov-Wasserstein optimal transport plans](https://mlsanity.com/paper/2602.16265/) (2026)

## Abstract (arXiv)

In this paper we address the graph matching problem. Following the recent works of citezaslavskiy2009path,Vestner2017 we analyze and generalize the idea of concave relaxations. We introduce the concepts of conditionally concave and probably conditionally concave energies on polytopes and show that they encapsulate many instances of the graph matching problem, including matching Euclidean graphs and graphs on surfaces. We further prove that local minima of probably conditionally concave energies on general matching polytopes (e.g., doubly stochastic) are with high probability extreme points of the matching polytope (e.g., permutations).