Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers

Abstract

Building on recent progress at the intersection of combinatorial optimization and deep learning, we propose an end-to-end trainable architecture for deep graph matching that contains unmodified combinatorial solvers. Using the presence of heavily optimized combinatorial solvers together with some improvements in architecture design, we advance state-of-the-art on deep graph matching benchmarks for keypoint correspondence. In addition, we highlight the conceptual advantages of incorporating solvers into deep learning architectures, such as the possibility of post-processing with a strong multi-graph matching solver or the indifference to changes in the training setting. Finally, we propose two new challenging experimental setups. The code is available at https://github.com/martius-lab/blackbox-deep-graph-matching

arXiv commentECCV 2020 conference paper

References in corpus (13)

• Adam: A Method for Stochastic Optimization
• Very Deep Convolutional Networks for Large-Scale Image Recognition
• FaceNet: A Unified Embedding for Face Recognition and Clustering
• Learning Combinatorial Optimization Algorithms over Graphs
• Neural Combinatorial Optimization with Reinforcement Learning
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Attention, Learn to Solve Routing Problems!
• OptNet: Differentiable Optimization as a Layer in Neural Networks
• SparseMAP: Differentiable Sparse Structured Inference
• Learning to Branch
• Optimizing Rank-based Metrics with Blackbox Differentiation
• Deep Graph Matching Consensus
• A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching

Cited by in corpus (12)

• Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities
• Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching
• CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
• Efficient Linear Attention for Fast and Accurate Keypoint Matching
• Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions
• Deep graph matching meets mixed-integer linear programming: Relax at your own risk ?
• Convolutional Hough Matching Networks for Robust and Efficient Visual Correspondence
• Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching
• Combinatorial Optimization for Panoptic Segmentation: A Fully Differentiable Approach
• Combinatorial Learning of Graph Edit Distance via Dynamic Embedding
• Differentiable Combinatorial Losses through Generalized Gradients of Linear Programs
• Convolutional Hough Matching Networks