mlsanityData to 7 Oct 2026

A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching

arXiv 1612.05476 ↗First posted 16 Dec 2016cs.CVcited by 26

Not on the map. Why?

Abstract (arXiv)

We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore s direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art any-time solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Dec 2016.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 8; 2022: 8; 2023: 5; 2024: 3; 2025: 2.

26 papers.

Sort:

By area:

  1. 2023LVM-Med: Learning Large-Scale Self-Supervised Vision Models for Medical Imaging via Second-order Graph Matchingcited by 60
  2. 2021Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Trackingcited by 47
  3. 2022Backpropagation through Combinatorial Algorithms: Identity with Projection Workscited by 29
  4. 2021Adiabatic Quantum Graph Matching with Permutation Matrix Constraintscited by 20
  5. 2022A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D Shape Matchingcited by 19
  6. 2021Fusion Moves for Graph Matchingcited by 16
  7. 2022A Comparative Study of Graph Matching Algorithms in Computer Visioncited by 14
  8. 2023Factor Graph Neural Networkscited by 13
  9. 2021Joint Graph Learning and Matching for Semantic Feature Correspondencecited by 8
  10. 2021FastDOG: Fast Discrete Optimization on GPUcited by 8
  11. 2024ExGra-Med: Extended Context Graph Alignment for Medical Vision-Language Modelscited by 6
  12. 2022Structured Prediction Problem Archivecited by 4
14 more
  1. 2021Joint Deep Multi-Graph Matching and 3D Geometry Learning from Inhomogeneous 2D Image Collectionscited by 3
  2. 2021Deep graph matching meets mixed-integer linear programming: Relax at your own risk ?cited by 3
  3. 2022Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer Visioncited by 2
  4. 2022Learning Universe Model for Partial Matching Networks over Multiple Graphscited by 2
  5. 2023Learnable Graph Matching: A Practical Paradigm for Data Associationcited by 2
  6. 2023Unsupervised Deep Graph Matching Based on Cycle Consistencycited by 2
  7. 2021Convex Joint Graph Matching and Clustering via Semidefinite Relaxationscited by 1
  8. 2022Deep Probabilistic Graph Matchingcited by 1
  9. 2025Normalized Matching Transformercited by 1
  10. 2022Training Free Graph Neural Networks for Graph Matchingcited by 0
  11. 2023M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning of Mixture Graph Matching and Clusteringcited by 0
  12. 2024Convergence of Some Convex Message Passing Algorithms to a Fixed Pointcited by 0
  13. 2024Correlation Clustering of Organoid Imagescited by 0
  14. 2025Cycle-Consistent Multi-Graph Matching for Self-Supervised Annotation of C.Eleganscited by 0