Source-linked AI summary
Learning Graph Matching
Tiberio S. Caetano, Julian J. McAuley, Li Cheng, Quoc V. Le, Alex J. Smola
TL;DR
Graph matching is often formulated as an NP-hard quadratic assignment problem with handcrafted node and edge compatibilities. This paper learns those compatibilities from labeled graph pairs, and reports substantial improvements, including linear assignment outperforming Graduated Assignment with bistochastic normalisation.
Problem
Graph matching typically relies on handcrafted compatibility functions and focuses on approximately solving an NP-hard quadratic assignment problem rather than learning the matching criterion.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
Learning matching criteria can substantially improve graph-matching accuracy, and linear assignment may be useful when speed is important.
Source: §6 · p. 9For quadratic assignment, the estimator is approximate because the most violated constraints cannot be found, so the duality gap may not be properly minimized.
Source: §3.5 · p. 5
Abstract
from arXiv · showhide
As a fundamental problem in pattern recognition, graph matching has applications in a variety of fields, from computer vision to computational biology. In graph matching, patterns are modeled as graphs and pattern recognition amounts to finding a correspondence between the nodes of different graphs. Many formulations of this problem can be cast in general as a quadratic assignment problem, where a linear term in the objective function encodes node compatibility and a quadratic term encodes edge compatibility. The main research focus in this theme is about designing efficient algorithms for approximately solving the quadratic assignment problem, since it is NP-hard. In this paper we turn our attention to a different question: how to estimate compatibility functions such that the solution of the resulting graph matching problem best matches the expected solution that a human would manually provide. We present a method for learning graph matching: the training examples are pairs of graphs and the `labels' are matches between them. Our experimental results reveal that learning can substantially improve the performance of standard graph matching algorithms. In particular, we find that simple linear assignment with such a learning scheme outperforms Graduated Assignment with bistochastic normalisation, a state-of-the-art quadratic assignment relaxation algorithm.
1 Introduction
Graph matching is typically treated as an approximate quadratic assignment problem with handcrafted compatibility functions, but this paper instead learns matching criteria from labeled graph pairs. Experiments show that learning substantially improves standard algorithms, including a linear-assignment approach that outperforms Graduated Assignment with bistochastic normalisation.
1 Introduction
- Graph matching commonly uses a quadratic assignment objective with linear node compatibility and quadratic edge compatibility, while compatibility functions are typically handcrafted.The problem is NP-hard, motivating approximate algorithms rather than exact general solutions.Source: §1 · p. 1
- Learning compatibility functions from manually labeled graph pairs addresses the limitation of treating the optimal match as determined solely by the graph pair.The method uses graphs extracted under relevant conditions and learns a map from graph pairs to matches.Source: §1 · p. 1
- The learning formulation adjusts node and edge compatibility functions so predicted test matches agree with expected manually provided matches, using a convex quadratic program solved by column generation.Source: §1 · p. 1
- Learning substantially improves standard graph matching performance, with linear assignment outperforming Graduated Assignment with bistochastic normalisation, a state-of-the-art quadratic assignment relaxation.Source: §1 · pp. 1–2
1.1 Related Literature
- Prior graph-matching research mainly develops approximations and heuristics for quadratic assignment, leaving principled determination of compatibility functions largely unaddressed.Related work includes spectral, probabilistic, semidefinite, replicator, tree-search, and graduated-assignment approaches.Source: §1.1 · p. 2
2 The Graph Matching Problem
The paper formulates attributed graph matching through binary matching matrices, unary node compatibilities, and pairwise edge compatibilities in a quadratic assignment problem. It relaxes fixed compatibility forms by learning their parameterization, with linear assignment arising when pairwise compatibilities vanish.
2 The Graph Matching Problem
- Attributed graph matching seeks a binary matrix whose entries indicate which node in the first graph maps to each node in the second.Node and edge attributes may be empty or binary in the standard exact-matching case.Source: §2 · pp. 2–3
- The objective combines unary assignment compatibility c for node matches with pairwise compatibility d for edge-pair matches, producing an NP-hard quadratic assignment problem.Source: §2 · p. 3
- Injectivity imposes one-to-one mappings, whereas the function constraint permits many-to-one mappings.Source: §2 · p. 3
- When pairwise compatibilities d are zero, graph matching becomes a linear assignment problem solvable exactly in worst-case cubic time.This applies to both training and test-time assignment in the stated special case.Source: §2 · p. 3
- The paper relaxes fixed compatibility forms by parameterizing node and edge compatibility functions and learning their coefficients within a convex optimization framework.The feature maps can use arbitrary node- and edge-indexed features, including graph structure viewed from a node.Source: §2 · p. 3
3 Learning Graph Matching
The paper formulates graph matching as supervised learning from graph pairs and matching labels, learning compatibility parameters for predictions. It replaces the difficult optimization with margin constraints and column generation, while using assignment solvers at training and test time.
3.1 General Problem Setting
- Learning uses graph pairs as structured observations and matching matrices as labels, estimating a predictor that minimizes empirical loss with regularization.The predictor maps graph pairs and parameters to matching matrices; regularization controls complexity and generalization.Source: §3.1 · p. 3
3.2 The Model
- The model selects the match maximizing a linear discriminant over a joint feature map, with learned compatibility functions encoding graph and match properties.The formulation treats graph matching as an inverse optimization problem, and traditional matching is recovered when compatibility parameters are fixed constants.Source: §3.2 · pp. 3–4
3.3 The Loss
- The loss measures matching error as a matrix mismatch fraction for large graphs and uses endpoint error when one graph is small.Endpoint error penalizes matches according to their Euclidean distance from the correct point correspondence, scaled by image width.Source: §3.3 · p. 4
3.4 The Optimization Problem
- The original empirical-risk objective is nonconvex and piecewise constant, so margin constraints upper-bound prediction loss while slack variables permit penalized violations.The constraints enforce larger discriminant gaps for predictions with larger losses; an optimal feasible solution bounds the average prediction loss.Source: §3.4 · pp. 4–5
3.5 The Algorithm
- Column generation makes exponentially constrained learning tractable by iteratively adding the most violated constraint, although quadratic-assignment separation remains approximate.When edge compatibilities vanish, the training and test subproblems become linear assignment problems solvable in worst-case cubic time; experiments use dedicated assignment solvers and Graduated Assignment for quadratic cases.Source: §3.5 · p. 5
4 Features for the Compatibility Functions
The compatibility functions use learned feature maps for node and edge correspondences. Experiments use Shape Context node features and a simple binary edge-match representation, with squared differences outperforming exponential decay after learning.
4 Features for the Compatibility Functions
- The method parameterizes node and edge compatibility functions linearly using graph-derived feature maps φ1 and φ2.The feature maps are selected to produce a working model, with node features discussed before quadratic edge terms.Source: §4 · p. 5
4.1 Node Features
- Squared coordinate differences in node features perform better after learning than the exponential decay used in.The coordinates represent corresponding attribute-vector components.Source: §4.1 · p. 5
- Node compatibility weights are learned from training data, allowing the model to tune the relevance of individual feature coordinates.The experiments use 60-dimensional Shape Context features describing how each node sees the other nodes.Source: §4.1 · pp. 5–6
4.2 Edge Features
- Edge features use standard binary graph adjacency, with a scalar parameter for the edge compatibility term.The edge feature is one when an edge exists between the paired nodes and zero otherwise.Source: §4.2 · p. 6
5 Experiments
Experiments on house, video, and bicycle-matching data show that learning improves graph-matching accuracy across varied settings, while retaining computational advantages for linear assignment.
5.1 House Sequence
- Learning significantly improves accuracy for both linear and quadratic assignment on the house sequence, while learned linear assignment performs similarly to an established quadratic relaxation.Before learning, quadratic assignment can underperform linear assignment because feature scales are poorly tuned; learned linear assignment remains much less computationally intensive.Source: §5.1 · p. 6
- On the house sequence, learning reduces one illustrated linear-assignment loss from 12/30 to 6/30 for frames 3 and 93.The example uses λ = 10 after learning; mismatches are visualized in red.Source: Figure 1 · p. 6
- Around three orders of magnitude separate linear from quadratic assignment in running time, while learned linear and quadratic methods outperform quadratic assignment with bistochastic normalisation.Learning does not affect running time, and quadratic assignment with bistochastic normalisation remains slower despite its best non-learning accuracy.Source: Figure 3 · p. 7, §5.1 · p. 7
5.2 Video Sequence
- For the video sequence, learning outperforms non-learning at every baseline despite noisy landmark detection and nonmonotonic performance as the subject moves in and out of view.Because only 11 important points are matched, results are presented only for linear assignment and use endpoint error rather than normalized Hamming loss.Source: §5.2 · p. 8
5.3 Bikes
- The bicycle experiment uses a fixed template and reports further endpoint-error improvement from learning on side-on images with six identified frame points.This fixed-template problem is easier than matching all image pairs but is relevant to applications such as image retrieval.Source: §5.3 · p. 8
- In the illustrated bicycle match, learning lowers loss from 0.105 without learning to 0.038 with learning.The figure compares inferred matches against correct matches outlined in green, with inferred matches outlined in red.Source: Figure 4 · p. 8
6 Conclusions and Discussion
The paper concludes that learning matching criteria from labeled graph pairs substantially improves graph matching, while retaining strong performance across different settings. It also highlights practical benefits for faster matching and context-specific applications.
6 Conclusions and Discussion
- Learning compatibility functions from labeled graph pairs substantially improves graph matching accuracy across three experimental settings.The training input is a graph pair and the training output is a matching matrix.Source: §6 · p. 9
- Linear assignment with learning performs similarly to Graduated Assignment with bistochastic normalisation, a state-of-the-art quadratic assignment relaxation.This result suggests linear assignment may be useful when matching speed is a major concern.Source: §6 · p. 9
- Learning introduced into Graduated Assignment improves both accuracy and speed over the best existing quadratic assignment relaxation.Source: §6 · p. 9
- Learning matching criteria can adapt graph matching to context-specific settings such as camera pairs with different calibrations and viewpoints.In surveillance, relatively stable camera and viewpoint conditions provide reusable context for learning.Source: §6 · p. 9