PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching

Runzhong Wang, Junchi Yan, Xiaokang Yang

arXiv:1911.11308v3cs.LGcs.CVstat.ML

TL;DR

Graph matching requires solving a difficult affinity-based combinatorial problem, while existing learning methods generally cannot directly handle the most general Lawler’s QAP. The paper proposes a network that learns from the affinity matrix through association-graph embedding and extends the framework to hypergraph and multiple-graph matching. Experiments show effectiveness and competitive performance across synthetic, real-world, and QAPLIB settings.

  • Problem

    Existing graph matching networks cannot directly handle the most general Lawler’s QAP, limiting use when individual graph information is unavailable.

  • Method

    The network treats the affinity matrix as an association graph, embeds it for vertex classification, and applies Sinkhorn normalization with end-to-end loss; extensions handle hypergraph and multiple-graph matching.

  • Results

    Experiments on synthetic and real-world data show effectiveness, while the method directly supports Lawler’s QAP evaluation on QAPLIB and achieves competitive performance.

  • Takeaways & Limitations

    The framework enables network-based learning and evaluation for general Lawler’s QAP as well as higher-order and multiple-graph matching scenarios.

  • Takeaways & Limitations

    Performance becomes more challenging with sparse association graphs, which can block message-passing paths; spectral fusion also requires a bypass strategy for repeated eigenvalues to avoid numerical errors.

Abstract

from arXiv · show

Graph matching involves combinatorial optimization based on edge-to-edge affinity matrix, which can be generally formulated as Lawler's Quadratic Assignment Problem (QAP). This paper presents a QAP network directly learning with the affinity matrix (equivalently the association graph) whereby the matching problem is translated into a constrained vertex classification task. The association graph is learned by an embedding network for vertex classification, followed by Sinkhorn normalization and a cross-entropy loss for end-to-end learning. We further improve the embedding model on association graph by introducing Sinkhorn based matching-aware constraint, as well as dummy nodes to deal with unequal sizes of graphs. To our best knowledge, this is one of the first network to directly learn with the general Lawler's QAP. In contrast, recent deep matching methods focus on the learning of node/edge features in two graphs respectively. We also show how to extend our network to hypergraph matching, and matching of multiple graphs. Experimental results on both synthetic graphs and real-world images show its effectiveness. For pure QAP tasks on synthetic data and QAPLIB benchmark, our method can perform competitively and even surpass state-of-the-art graph matching and QAP solvers with notable less time cost. We provide a project homepage at http://thinklab.sjtu.edu.cn/project/NGM/index.html.

1 INTRODUCTION AND PRELIMINARIES

The paper formulates graph matching as Lawler’s QAP and introduces a neural network that learns directly from the affinity matrix by embedding its association graph for constrained vertex classification. The framework extends to hypergraph and multiple-graph matching, with experiments showing competitive effectiveness on synthetic, real-world, and QAPLIB tasks.

  • Graph matching establishes node correspondences using node-to-node and edge-to-edge affinities and is NP-complete in general.
  • Lawler’s QAP represents two-graph matching with a quadratic objective over a partial permutation matrix and an affinity matrix whose entries encode node and edge affinities.The affinity matrix is equivalently treated as an association graph for learning.
  • The pipeline combines optional CNN and spline-convolution feature extraction, affinity metric learning, association-graph embedding, Sinkhorn normalization, and cross-entropy training.Sinkhorn operations also introduce matching constraints within the embedding module.
  • The framework extends graph matching to higher-order hypergraph matching through an association hypergraph and to multiple-graph matching through differentiable spectral multi-matching.The hypergraph extension explicitly treats hyperedges, while the multiple-graph extension uses spectral synchronization.
  • The proposed network directly learns Lawler’s QAP by embedding the association graph with a graph neural network and classifying its vertices under matching-aware constraints.Unlike methods that learn from separate graph features, the network accepts the pairwise affinity matrix as its raw input.
  • Experiments on synthetic and real-world data show competitive performance, while the method can directly evaluate Lawler’s QAP on QAPLIB because competing graph-matching networks cannot take the general QAP as input.The network supports supervised training with correspondence labels and unsupervised training from final matching scores.

2 RELATED WORK

Prior work formulates graph matching as QAP and extends affinity modeling through hypergraphs, multiple graphs, and learned methods. Existing deep matching networks generally do not directly handle the most general Lawler's QAP, motivating a network that learns from affinity matrices.

  • Hypergraph matching methods: Hypergraph matching captures higher-order affinities through tensors, improving noise robustness at exponentially increased time and space complexity.
  • Multiple-graph matching methods: Multiple-graph matching aims to fuse information across graphs to improve robustness against local noise and ambiguity.
  • Learning-based methods: Learning methods seek more adaptive affinity models or neural solvers instead of relying only on lifted affinity order or consistency regularization.
  • Motivation for NGM: Existing graph matching networks cannot directly handle the most general Lawler's QAP, whereas the proposed method works directly with affinity matrices and extends to hypergraph and multiple-graph matching.

3 PROPOSED APPROACHES

The paper introduces neural methods for two-graph Lawler's QAP, hypergraph matching, and multiple-graph matching. These settings had been rarely addressed by neural networks in the authors' assessment.

  • The proposed approaches include NGM for two-graph Lawler's QAP, NHGM for hypergraph matching, and NMGM for multiple-graph matching.

3.1 Preliminaries

The paper represents graph matching through an affinity matrix and an association graph whose vertices encode candidate correspondences. Matching then becomes selecting compatible association-graph vertices under one-to-one constraints.

  • The model represents graphs with inliers and optional outliers, while relaxing Lawler's QAP using a partial doubly-stochastic matching matrix.
  • Affinity-matrix diagonal elements encode node similarities, while off-diagonal elements encode edge similarities.
  • Association-graph vertices represent candidate node correspondences, and its edges represent agreement between correspondence pairs.
  • Graph matching becomes vertex classification on the association graph, with links excluded when they violate one-to-one matching constraints.
  • Connectivity matrices encode directed edge starts and ends, while the incidence matrix uses -1 for starts and 1 for ends.

3.2 NGM: Neural Graph Matching for QAP

NGM solves relaxed Lawler's QAP by classifying vertices in an affinity-induced association graph, then applying Sinkhorn normalization to enforce matching constraints. Its differentiable pipeline supports affinity matrices or optional image features and includes matching-aware embeddings, unequal graph sizes, and end-to-end training.

  • NGM applies GCN-based vertex classification with matching-aware embeddings to the association graph induced by the affinity matrix, followed by a Sinkhorn operator.
  • The network can accept affinity matrices directly or use optional CNN processing for image inputs.
  • Affinity matrix construction: Affinity construction combines node and edge representations with a learnable metric and a factorized QAP affinity matrix.
  • Association-graph embedding: Vertex embeddings start from diagonal affinity values and propagate information through the weighted association graph.
  • Matching-aware embedding: Matching-aware embedding concatenates a Sinkhorn-produced soft permutation with vertex embeddings so assignment information enters each embedding layer.
  • Sinkhorn matching: Sinkhorn normalization pads non-square score matrices with dummy elements, alternates row and column normalization, and discards dummy outputs for unequal graph sizes.
  • End-to-end training: The final doubly-stochastic prediction is trained with binary cross-entropy against the ground-truth correspondence matrix, with all components differentiable.
  • The framework also supports direct optimization of affinity-score objectives for QAPLIB problems.

3.3 NHGM: Neural Hypergraph Matching

NHGM extends NGM to hypergraph matching by replacing pairwise association-graph message passing with higher-order hypergraph aggregation. It limits experiments to third-order hypergraphs for computational tractability while retaining the NGM classifier and loss.

  • NHGM restricts hypergraphs to third-order because computation grows as O((n1n2)^t), while NGM is its order-2 special case.The other modules, including classification and cross-entropy loss, remain identical, and sparsity is used for efficiency.
  • NHGM generalizes the second-order affinity matrix to an order-t affinity tensor for higher-order hypergraph matching.The third-order case is specified for the method’s experiments.
  • Third-order affinity compares node triplets and can preserve scaling and rotation invariance through geometric consistency.
  • The hyper-association graph uses correspondence pairs as vertices and higher-order similarities among correspondence tuples as hyperedges.Its tensor elements provide adjacency weights for hypergraph convolution and vertex classification.
  • NHGM updates vertex embeddings by aggregating information from vertices linked through hyperedges using normalized degree tensors and order-specific message passing.Features from different orders are fused by weighted summation.

3.4 NMGM: Neural Multi-graph Matching

NMGM extends NGM to multiple graphs by fusing pairwise soft matchings under cycle consistency. Differentiable spectral fusion and a final Sinkhorn network keep the multi-graph pipeline trainable, with a numerical bypass for degenerate eigenvalues.

  • NMGM represents cycle consistency as Xij = XikXkj and models each graph’s matching to a shared reference.Pairwise matchings are consequently represented as products of reference matchings.
  • The method assumes all graphs have equal size and uses spectral fusion because it supports end-to-end training.
  • NMGM first obtains pairwise NGM soft matchings and assembles them into a symmetric joint matching matrix S.Each pairwise block is a doubly-stochastic matching matrix.
  • Spectral fusion seeks a cycle-consistent joint matching matrix whose inner product with the initial joint matrix is maximized.The fused matrix must satisfy Ŝij = ŜikŜkj.
  • The fusion uses the top-n eigenvectors of S in a differentiable generalized Rayleigh formulation.Eigenvalue and eigenvector computation is treated as a differentiable component of the learning pipeline.
  • When repeated eigenvalues create numerical instability, NMGM bypasses eigendecomposition when the minimum residual is below δ, such as 10^-4, then applies differentiable Sinkhorn normalization.The bypass is reported to stabilize learning.

3.5 Improved Matching by Enhanced Feature Extractor

The improved v2 models replace the baseline feature extractor while preserving the general Lawler QAP pipeline. They refine image features with SplineConv, construct weighted node and edge affinities, and define hypergraph affinities in feature space.

  • NGM, NHGM, and NMGM-v2 replace the baseline extractor with an enhanced image-matching feature extractor while retaining the general QAP solver pipeline.The replacement yields enhanced models for graph, hypergraph, and multi-graph matching.
  • The enhanced extractor concatenates VGG16 relu4_2 and relu5_1 node features, then refines them with two SplineConv layers.SplineConv encodes geometric features into node features.
  • Edge features are formed from differences between the refined features of connected nodes.
  • A max-pooled relu5_3 branch produces global features that are concatenated and transformed for separate node and edge affinity weighting.Node and edge similarity matrices use weighted inner products.
  • NHGM-v2 defines third-order hypergraph affinity from angle differences in the high-dimensional feature space rather than geometric coordinates.
  • The authors empirically find that cosine performs better than sine for the feature-space angle affinity.

3.6 Further Discussions

The discussion frames the neural solver as learning association-graph structure and reducing QAP matching to vertex classification followed by assignment. It also motivates matching-aware Sinkhorn embeddings and sampling-based optimization extensions.

  • The association graph converts Lawler’s QAP into a structure that a GNN can learn for vertex classification.The resulting scores are converted into a matching through differentiable Sinkhorn optimization.
  • Matching-aware Sinkhorn embedding introduces one-to-one constraints before the output layer rather than only at final normalization.The paper reports notable synthetic-test and real-image ablation improvements, with further gains from multi-head embedding at added cost.
  • Cross-entropy trains the doubly-stochastic matrix as a distribution over permutation matrices, while Hungarian decoding selects the highest-probability permutation.
  • Gumbel-Sinkhorn samples sparse doubly-stochastic matrices, then applies Hungarian discretization and chooses the solution with the best objective score.The number of Gumbel samples balances exploration and speed.

4 EXPERIMENTS

Experiments evaluate NGM and its hypergraph and multi-graph extensions on synthetic matching problems, comparing accuracy, objective quality, and runtime. NGM benefits from matching-aware Sinkhorn embedding and performs competitively with substantially faster GPU execution.

  • Synthetic experiments: Synthetic experiments compare NGM, hypergraph N​​HGM, and multi-graph NMGM against learning-free graph and hypergraph matching solvers under deformation, noise, scaling, and outliers.The evaluation uses affinity matrices or tensors directly and includes runtime comparisons.
  • Matching accuracy: NGM matches state-of-the-art accuracy and can surpass competing solvers under severe random scaling, while NHGM shows strong robustness to noise, scaling, and outliers.NMGM also improves as more graphs are jointly matched.
  • Runtime: NGM, NGM-V, and NGM-MH are among the fastest graph matching algorithms, while GPU-parallelized NHGM is faster than the state-of-the-art BPF solver.Traditional hypergraph matching methods such as RRWHM are reported as much slower than second-order approaches.
  • QAP objective: Learning-based solvers can achieve relatively low QAP objective scores despite noisy affinities, because they learn to ignore misleading patterns in the input affinity matrix.The paper notes that the mathematically optimal QAP solution may diverge from the true matching under noise.
  • Ablation and mechanisms: Matching-aware Sinkhorn embedding improves accuracy over vanilla NGM, and multi-head Sinkhorn embedding provides further gains, especially under random scaling.Without Sinkhorn embedding, NGM-V behaves similarly to spectral matching because it does not enforce assignment constraints during embedding.

4.2 Learning Real-world QAP Instances

The QAPLIB study tests whether NGM can learn directly from real-world Lawler QAP instances and generalize across problem instances and sizes. NGM-G5k achieves the strongest reported coverage while offering a favorable accuracy–speed trade-off, although sparse association graphs remain challenging.

  • Results: NGM-G5k beats RRWM and SM and is competitive with or superior to Sinkhorn-JA on QAPLIB, with category-dependent strengths across the benchmark.Sinkhorn-JA performs better on chr and lipa, whereas NGM is stronger on bur, esc, nug, scr, and tai.
  • Results: NGM-G5k achieves the best solution on 72 of 133 tested instances, compared with 46 instances for Sinkhorn-JA.Gumbel sampling consistently outperforms deterministic NGM, and the sampling count controls the accuracy–runtime trade-off.
  • Generalization: The model generalizes to unseen QAPLIB instances with different problem sizes and achieves the paper’s best reported accuracy–speed trade-off.The generalization study trains and tests on different randomly selected instances.
  • Further discussion: Higher affinity-matrix sparsity significantly challenges both NGM-G5k and Sinkhorn-JA, while higher association-graph degrees also degrade both methods.For NGM-G5k, sparse graphs can block message-passing paths; the authors suggest higher-capacity models and global communication as future directions.

4.3 Real Image for Joint CNN and QAP Learning

Image experiments jointly learn CNN features and QAP solvers for semantic keypoint and multi-graph matching. The proposed variants outperform or match competing methods across Pascal VOC and Willow ObjectClass, while controlled experiments support learning both the feature extractor and solver.

  • Pascal VOC Keypoint: The Pascal VOC Keypoint benchmark contains 20 categories with variable scale, pose, illumination, and 6–23 keypoints per image, making matching challenging.The evaluation uses 7,020 training samples and 1,682 testing samples after filtering poorly annotated images.
  • Pascal VOC Keypoint: Joint CNN and QAP-solver learning lets NGM variants surpass competing methods on most Pascal VOC categories, with NGM-v2 exceeding BBGM in mean accuracy.NGM-v2 and BBGM use the same enhanced feature extractor, but NGM-v2 also learns the graph matching solver.
  • Generalization: NGM and NGM-v2 generalize between visually similar categories, although PCA-GM performs better when accuracy is aggregated across all categories.The confusion matrices compare models trained on selected categories with tests covering all categories.
  • Willow ObjectClass: On Willow ObjectClass, NGM-v2 and NHGM-v2 surpass BBGM, while NMGM-v2 achieves the best performance among the evaluated methods.NMGM achieves higher accuracy than learning-free multi-graph baselines despite jointly matching fewer graphs.
  • Ablation study: A controlled experiment reports 44.0% accuracy for the learned solver with ImageNet CNN features versus 24.0% for RRWM, supporting joint learning of CNN features and the QAP solver.The paper states that the joint CNN–solver method performs best among the tested combinations.

5 CONCLUSION AND OUTLOOK

The network directly learns Lawler’s QAP and extends deep matching to hypergraphs and multiple graphs. Experiments report state-of-the-art performance and cost-efficiency, while large-scale QAP remains an outlook target.

  • The method directly learns Lawler’s QAP, unlike approaches restricted to separate graph inputs.
  • The framework extends deep learning to hypergraph matching with third-order edges and multiple-graph matching.
  • Experiments on synthetic and real-world data report state-of-the-art performance and notable cost-efficiency advantages over learning-free methods.
  • Future work will develop more scalable approaches for large-scale QAP problems and apply the model beyond computer vision.
Loading 1911.11308v3…