PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers

Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, Georg Martius

arXiv:2003.11657v2cs.LGstat.ML

TL;DR

Deep graph matching methods can compromise on combinatorial quality, while purely combinatorial methods may rely on fixed, often suboptimal features. This paper embeds optimized graph-matching solvers in an end-to-end trainable architecture and reports higher matching accuracy than previous methods, especially in challenging scenarios.

  • Problem

    Hybrid deep graph-matching approaches compromise on the combinatorial side, while purely combinatorial approaches typically rely on fixed features that are often suboptimal.

    Source: §1 · p. 2

  • Method

    The end-to-end architecture embeds blackbox combinatorial solvers while maintaining strong feature extraction and processing global image information.

    Source: §1 · pp. 2–3

  • Results

    The approach achieves higher matching accuracy than previous methods, particularly in more challenging scenarios, and reaches state-of-the-art results on Pascal VOC and Willow ObjectClass.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The paper demonstrates that deep learning architectures integrating combinatorial graph-matching solvers perform well on deep graph-matching benchmarks.

    Source: §5 · p. 13

    On Willow ObjectClass, small dataset size, varied training setups, and high standard deviations prevent statistically significant comparisons.

    Source: §4.2 · p. 12

Abstract

from arXiv · show

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

1 Introduction

The paper addresses deep graph matching methods that compromise on combinatorial optimization, proposing an end-to-end architecture that embeds an unmodified solver while retaining strong feature extraction. It reports stronger matching accuracy, especially in challenging scenarios, and introduces two experimental setups.

1 Introduction

  • Existing hybrid deep graph matching approaches compromise on the combinatorial side, limiting the competitiveness of their matching blocks.The paper frames this as a trade-off between deep networks’ limited combinatorial generalization and the fixed, often suboptimal features of purely combinatorial methods.Source: §1 · p. 2
  • The proposed end-to-end architecture embeds blackbox implementations of combinatorial algorithms to use optimized graph matching solvers without concessions on the combinatorial side.The solvers are based on dual block coordinate ascent for Lagrange decompositions.Source: §1 · p. 2
  • Global feature attention adjusts node- and edge-feature weights using a global feature vector, leveraging cues such as viewpoint, rigidity, and scale.The architecture also builds graph-matching instances from visual and geometric information, including relative keypoint locations via SplineCNN.Source: §1 · p. 2
  • The architecture supports evaluation-time post-processing with a multi-graph solver that jointly resolves matching instances consistently.This uses a multi-graph matching solver.Source: §1 · p. 2
  • The paper proposes SPair-71k evaluation and unfiltered keypoints, where matching instances may include unmatched points, as two future benchmark setups.The motivation is the lack of challenging standardized benchmarks.Source: §1 · p. 2
  • The approach achieves higher matching accuracy than previous methods, particularly in more challenging scenarios.The paper reports state-of-the-art results on Pascal VOC and Willow ObjectClass; it also proposes SPair-71k and unfiltered keypoints as challenging experimental setups.Source: §1 · pp. 2–3

2 Related Work

Related work covers two directions for combining combinatorial optimization and deep learning, then reviews graph-matching solvers and deep graph-matching architectures. Prior methods use relaxations, assignment normalization, and graph neural networks, with recent work extracting more geometric signal.

Combinatorial Optimization Meets Deep Learning

  • One research direction uses deep learning to improve combinatorial optimization, while another makes combinatorial algorithms differentiable building blocks for neural networks.Examples of the first include reinforcement learning for branch-and-bound decisions and heuristic greedy algorithms for NP-hard graph problems; the second includes differentiable quadratic programming and blackbox wrappers.Source: Combinatorial Optimization Meets Deep… · p. 3

Combinatorial Graph Matching

  • Graph matching, also known as the quadratic assignment problem, is NP-complete, while Lagrangian decomposition solvers can produce high-quality solutions for sparse vision instances.These solvers link smaller subproblems with Lagrange multipliers updated to reach agreement.Source: Combinatorial Graph Matching · p. 3
  • Graph matching solvers have been applied in computer vision to landmark correspondence, optical flow, multi-object tracking, object categorization, and cell-nuclei matching.The cited examples span several semantic object classes and biological image analysis.Source: Combinatorial Graph Matching · p. 4

Peer Methods

  • Prior deep graph-matching methods use differentiable relaxations, Sinkhorn normalization, row normalization, and graph neural networks to refine node embeddings.The literature also discusses loss functions and has recently extracted more signal from geometric information.Source: Peer Methods · p. 4

3 Methods

The methods embed intact combinatorial solvers in a trainable graph-matching architecture using blackbox differentiation. They combine valid graph-matching instances, a cost margin, specialized solvers, and visual and geometric feature processing.

3.1 Differentiability of Combinatorial Solvers

  • Implicit interpolation addresses the solver’s piecewise-constant mapping: the intact solver runs in the forward pass, with one additional solver call supplying backward gradient information.The framework does not require an explicit description of the feasible set.Source: §3.1 · pp. 4–5

3.2 Graph Matching

  • Graph matching minimizes the combined vertex and edge costs over valid matchings, with the matching encoded by vertex and edge indicator vectors.The forward pass runs the solver and saves its output for the backward pass.Source: §3.2 · pp. 5–6

3.3 Cost Margin

  • The cost-margin training procedure increases unary costs for ground-truth matches by α > 0; experiments use α = 1.0.The margin addresses the limitation that Hamming loss can be zero even when the ground-truth matching has only fractionally lower cost than competitors.Source: §3.3 · p. 6

3.4 Solvers

  • Pairwise matching uses a dual block coordinate ascent solver with Lagrangian decomposition and minimum-cost-flow rounding; multi-graph matching adds cycle-consistency constraints and permutation-synchronization rounding.The multi-graph solver supports partial matchings.Source: §3.3 · p. 6, §3.4 · p. 7

3.5 Architecture Design

  • BB-GM has three stages: visual feature extraction, geometry-aware feature refinement, and construction of a solver-ready matching instance; the third stage is the principal novelty.The matching output is trained against ground truth using Hamming distance.Source: §3.5 · p. 7
  • SplineCNN refines keypoint features using normalized relative coordinates, while a global feature vector adjusts node- and edge-feature weights for affinity computation.The global vector is concatenated across the two images; the architecture uses it to condition similarity coefficients.Source: Geometric Feature Refinement · p. 8, Matching Instance Construction · pp. 8–9

4 Experiments

The experiments evaluate BB-GM on standard keypoint-matching datasets and two challenging setups, including matching without keypoint filtering. Results include gains on Pascal VOC and SPair-71k, while the Willow comparison is inconclusive.

4 Experiments

  • The experiments use Pascal VOC, Willow ObjectClass, and SPair-71k; the two new setups are SPair-71k evaluation and Pascal VOC matching without keypoint filtering.DGMC is reproduced in some evaluations, and experiments run on a Tesla-V100 GPU process around 30 image pairs per second.Source: §4 · p. 9, Runtime · p. 9
  • Evaluation pair sampling and keypoint filtering must remain consistent because changing test instances can affect metrics and fair comparisons.Inclusion filtering underrepresents pairs with different viewpoints and produces large differences in individual-class accuracy, although its effect on mean accuracy is not strong.Source: Image Pair Sampling and Keypoint… · pp. 9–10, Table 1 · p. 10

4.1 Pascal VOC

  • The proposed unfiltered Pascal VOC setup retains outliers and unequal numbers of keypoints, and uses F1-score rather than accuracy to account for false positives.BB-GM applies to partial matchings; competing architectures based on Sinkhorn or softmax are hardwired to maximal matchings.Source: Image Pair Sampling and Keypoint… · p. 10, All keypoints · p. 11
  • Under standard intersection filtering on Pascal VOC, BB-GM outperforms competing approaches in matching accuracy.Table 2 reports accuracy for this setup; DGMC* and BB-GM means are over five restarts.Source: §4.1 · p. 11, Table 2 · p. 11
  • The Pascal VOC evaluation also tests multi-graph post-processing on sets of five images, with the solver seeking globally optimal consistent matchings.Table 3 reports BB-GM-Multi and the BB-GM-Max reference ablation; its statistics cover ten restarts.Source: Table 3 · p. 11, All keypoints · p. 12

4.2 Willow ObjectClass

  • Willow ObjectClass results do not support a claim of superiority because the dataset is small and comparisons have high standard deviations across training setups.The authors state that these factors prevent statistically significant comparisons.Source: §4.2 · p. 12, Table 4 · p. 13

4.3 SPair-71k

  • On SPair-71k, BB-GM consistently improves on DGMC, particularly for image pairs with very different viewpoints.The paper reports this pattern across viewpoint-difficulty results and all classes.Source: §4.3 · p. 12, Table 5 · p. 13

4.4 Ablations Studies

  • Ablation studies on Pascal VOC isolate architecture components, with the results summarized in Table S1.The supplementary material describes these as studies of individual components.Source: §4.4 · p. 13

5 Conclusion

The paper concludes that architectures integrating combinatorial graph-matching solvers perform well on deep graph-matching benchmarks. It identifies further work in improving the network and solver, and in testing solver-centered architectures on other problems.

5 Conclusion

  • Deep-learning architectures that integrate combinatorial graph-matching solvers perform well on deep graph-matching benchmarks.Source: §5 · p. 13
  • Future work includes making input costs more discriminative and using solvers with better solution quality or richer cost structures, such as hypergraph matching.Source: §5 · p. 14
  • The authors also propose exploring solver-centered architectures for other computer-vision combinatorial problems, including multicut and max-cut.Source: §5 · p. 14

Supplementary Material

Supplementary ablations examine the effects of global features, VGG fine-tuning, quadratic costs, and replacing the solver with Sinkhorn normalization.

Ablation Studies

  • The Pascal VOC ablations are summarized in Table 7, which highlights large performance differences.Source: Ablation Studies · p. 15, Table 7 · p. 15
  • The fixed-affinity ablation removes the global-feature vector's influence by using a single learnable vector instead of a network applied to the global vector.Source: Ablation Studies · p. 15
  • The frozen-VGG ablation uses ImageNet-pretrained VGG without fine-tuning, matching DGMC's setting for a fair comparison.Source: Ablation Studies · p. 15
  • The unary-cost ablation sets quadratic costs to zero, leaving matching instances with unary costs only.Source: Ablation Studies · p. 15
  • The Sinkhorn comparison replaces the solver and reports good performance only after increasing ε from 10^-8 to 10^-4; the authors connect this to reported vanishing-gradient issues.Source: Ablation Studies · p. 15
Loading 2003.11657v2…