# Many-to-Many Matching via Sparsity Controlled Optimal Transport

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 65 references that are in the map.
- First posted on arXiv 31 Mar 2025.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Smooth and Sparse Optimal Transport](https://mlsanity.com/paper/1710.06276/) (2017)
- [Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application](https://mlsanity.com/paper/1309.1541/) (2013)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Sparsity-Constrained Optimal Transport](https://mlsanity.com/paper/2209.15466/) (2022)
- [Structured Optimal Transport](https://mlsanity.com/paper/1712.06199/) (2017)
- [Making transport more robust and interpretable by moving data through a small number of anchor points](https://mlsanity.com/paper/2012.11589/) (2020)
- [Improving Cross-lingual Information Retrieval on Low-Resource Languages via Optimal Transport Distillation](https://mlsanity.com/paper/2301.12566/) (2023)
- [Interior-Point Methods Strike Back: Solving the Wasserstein Barycenter Problem](https://mlsanity.com/paper/1905.12895/) (2019)
- [Order Constraints in Optimal Transport](https://mlsanity.com/paper/2110.07275/) (2021)
- [Pareto Optimal Matchings in Many-to-Many Markets with Ties](https://mlsanity.com/paper/1507.02866/) (2015)
- [Two exact algorithms for the generalized assignment problem](https://mlsanity.com/paper/1303.4031/) (2013)
- [Many-to-Many Matching Games for Proactive Social-Caching in Wireless Small Cell Networks](https://mlsanity.com/paper/1405.5390/) (2014)
- [Pareto optimal matchings of students to courses in the presence of prerequisites](https://mlsanity.com/paper/1603.00858/) (2016)
- [A faster algorithm for the limited-capacity many-to-many point matching in one dimension](https://mlsanity.com/paper/1904.03015/) (2019)
- [Sparse Partial Least Squares for Coarse Noisy Graph Alignment](https://mlsanity.com/paper/2104.02810/) (2021)
- [Partial Relaxed Optimal Transport for Denoised Recommendation](https://mlsanity.com/paper/2204.08619/) (2022)

## Abstract (arXiv)

Many-to-many matching seeks to match multiple points in one set and multiple points in another set, which is a basis for a wide range of data mining problems. It can be naturally recast in the framework of Optimal Transport (OT). However, existing OT methods either lack the ability to accomplish many-to-many matching or necessitate careful tuning of a regularization parameter to achieve satisfactory results. This paper proposes a novel many-to-many matching method to explicitly encode many-to-many constraints while preventing the degeneration into one-to-one matching. The proposed method consists of the following two components. The first component is the matching budget constraints on each row and column of a transport plan, which specify how many points can be matched to a point at most. The second component is the deformed q-entropy regularization, which encourages a point to meet the matching budget maximally. While the deformed q-entropy was initially proposed to sparsify a transport plan, we employ it to avoid the degeneration into one-to-one matching. We optimize the objective via a penalty algorithm, which is efficient and theoretically guaranteed to converge. Experimental results on various tasks demonstrate that the proposed method achieves good performance by gleaning meaningful many-to-many matchings.