We propose an end-to-end learning framework for graph matching that incorporates both unary (node) and pairwise constraints. Our key contribution is making all parameters of the graph matching process learnable, encompassing unary and pairwise node neighborhoods, represented as deep feature extraction hierarchies. The main technical challenge we address is enabling consistent, efficient propagation of gradients through the combinatorial matching solver — from the loss function through the optimization layer and the deep feature hierarchy. We validate our approach on challenging benchmarks including PASCAL VOC keypoints, Sintel, and CUB.

Graph matching is a fundamental problem in computer vision, with applications in object recognition, action recognition, shape matching, and image registration. Classical approaches formulate graph matching as a quadratic assignment problem (QAP), which is NP-hard and typically solved using relaxation techniques. The node and edge features used for matching are traditionally hand-crafted descriptors such as SIFT or shape context, which are not optimized for the matching task. We propose to learn the entire matching pipeline end-to-end, from feature extraction through the combinatorial solver, enabling the features to be directly optimized for matching accuracy.

Graph matching has a rich history in combinatorial optimization. Classical methods include spectral methods, semidefinite programming relaxations, and graduated assignment algorithms. Recent deep learning approaches have incorporated learned features into matching pipelines, but typically only learn the unary features while keeping the pairwise terms and solver fixed. Differentiable optimization has emerged as a paradigm for incorporating combinatorial solvers into neural networks, but applying it to graph matching poses unique challenges due to the quadratic nature of the objective and the discrete output space. Our work is the first to jointly learn both unary and pairwise features while backpropagating through the matching solver.

Our framework consists of three components. First, a deep feature extraction network computes unary descriptors for each node and pairwise descriptors for each edge in both graphs. The unary descriptors capture local appearance, while the pairwise descriptors encode geometric relationships between neighboring nodes. These features are organized into an affinity matrix that encodes the compatibility between all possible node-to-node assignments. Second, a combinatorial matching solver (based on spectral relaxation or graduated assignment) operates on this affinity matrix to produce the optimal matching. Third, a loss function compares the predicted matching to the ground truth.

The key technical challenge is backpropagating gradients through the combinatorial matching solver. The matching solver produces a permutation matrix — a discrete object with no natural gradient. We address this by operating on the continuous relaxation of the matching problem: instead of requiring a binary permutation matrix, we work with doubly stochastic matrices obtained via Sinkhorn normalization. The gradients of the relaxed objective with respect to the affinity matrix can be computed analytically, allowing consistent gradient propagation from the matching loss back to the feature extraction network. This enables the feature hierarchies to be optimized specifically for the matching task rather than repurposed from other applications.

We evaluate on three benchmarks. On PASCAL VOC keypoint matching, our method achieves significant improvements over methods using hand-crafted features, with the end-to-end trained features providing substantially better matching accuracy across all 20 object categories. On Sintel optical flow correspondence, our approach outperforms classical graph matching baselines by learning features adapted to the dense correspondence task. On CUB bird dataset, the learned pairwise features provide consistent improvements over unary-only variants, confirming that learning both unary and pairwise terms is crucial. Importantly, our framework maintains competitive computational efficiency despite the end-to-end training requirement.

We have presented an end-to-end deep learning framework for graph matching that jointly learns unary and pairwise feature representations while backpropagating through a combinatorial matching solver. The key enabler is the continuous relaxation via Sinkhorn normalization, which allows consistent gradient flow throughout the entire pipeline. Our results on PASCAL VOC, Sintel, and CUB demonstrate that task-specific learned features significantly outperform hand-crafted alternatives. This work opens the door to applying deep learning to a broader class of combinatorial optimization problems in vision.