GMTR: Graph Matching Transformers

Jinpei Guo, Shaofeng Zhang, Runzhong Wang, Chang Liu, Junchi Yan

TL;DR

GMTR (Graph Matching TRansformers) introduces an end-to-end transformer-based framework for visual graph matching that overcomes the spatial insensitivity of standard Vision Transformers (ViTs). By combining a keypoint-centered cropping strategy (QueryTrans) with a backend graph transformer solver, GMTR achieves state-of-the-art accuracy on standard matching benchmarks and demonstrates that transformers can successfully solve complex combinatorial optimization problems like the Quadratic Assignment Problem (QAP).

What Problem Does This Paper Address?

Visual graph matching (GM) aims to establish node-to-node correspondences between keypoints across different images. Traditionally, this task relies on Convolutional Neural Networks (CNNs) for feature extraction and Graph Neural Networks (GNNs) to model the relational structures.

While Vision Transformers (ViTs) have revolutionized computer vision due to their superior relational modeling capabilities, adapting them to graph matching introduces a major bottleneck: spatial insensitivity. Standard ViTs divide an image into a rigid grid of patches. This grid-based tokenization completely ignores the precise coordinates of local keypoints, diluting the fine-grained spatial features necessary to match specific landmarks (like the wheel of a bicycle or the eye of a bird) across images.

Methods

GMTR addresses these challenges by splitting the graph matching pipeline into a specialized transformer frontend and backend:

Overview of the GMTR architecture, showing the frontend QueryTrans feature extractor and the backend graph transformer solver.

1. Frontend: Query Transformer (QueryTrans)

To restore spatial awareness to the transformer, the authors propose a dual-patch generation strategy:

  • Raw Patches: The standard rigid image grid used by classic ViTs.
  • Key Patches: Custom region crops centered precisely around each target keypoint, matching the size of the raw patches.

Instead of letting every token attend to every other token blindly, QueryTrans introduces a cross-attention mechanism with a filter module. A localized filter matrix $D$ restricts key patches so they only perform message passing with their immediate neighboring raw patches. This prevents the model from introducing distant spatial bias and keeps keypoint features highly localized.

Illustration of the filter matrix $D$ restricting cross-attention to neighboring patches around a query point.

2. Backend: GM Solver Transformer

Once features are extracted, graph matching is formulated as a Quadratic Assignment Problem (QAP), which is NP-hard. While previous methods used GNNs to solve the QAP via vertex classification, GMTR replaces GNNs with a graph transformer network (TransformerConv). The backend takes the QAP affinity matrix as an input instance, computes node embeddings using multi-head self-attention, and passes the scores through a Sinkhorn network to output the final keypoint matching matrix.

Datasets

The authors evaluated GMTR on two popular visual graph matching benchmarks:

  • Pascal VOC: Annotated with Berkeley keypoints, containing 20 instance classes with 6 to 23 keypoints per image.
  • SPair-71k: A significantly larger and more challenging dataset containing 70,958 image pairs with diverse variations in viewpoint, scale, and occlusion.

Key Insights and Ideas

  • Grid Tokenization is a Graph Matching Bottleneck: Rigid patch grids are excellent for global image classification but terrible for localized keypoint tracking. Hybrid tokenization (combining global grids with keypoint-centered crops) bridges this gap.
  • Constrained Attention Beats Full Attention Here: In QueryTrans, allowing keypoint tokens to attend to the entire image actually hurts performance. Restricting attention to local neighborhoods via the filter matrix $D$ is essential for preserving high-fidelity local context.
  • Transformers as Combinatorial Solvers: The paper provides the first successful application (to the authors' knowledge) of a transformer architecture directly solving Lawler’s QAP independently of the frontend feature extractor, outperforming traditional GNN architectures in capturing mutual graph information.

Key Results

GMTR achieves state-of-the-art (SOTA) or highly competitive results across both datasets:

  • Pascal VOC: GMTR achieves a SOTA accuracy of 83.6%, outperforming the previous best framework by 0.9%.
  • Plug-and-Play Frontend Success: When QueryTrans was plugged into existing popular graph matching frameworks, it yielded massive accuracy boosts. On Pascal VOC, it boosted NGMv2 from 80.1% to 83.3% and BBGM from 79.0% to 84.5%.
Backbone comparison table showing QueryTrans consistently outperforming CNNs and standard ViTs across NGMv2 and BBGM frameworks.
  • SPair-71k: GMTR demonstrates strong performance with an overall accuracy of 83.2%, outperforming most recent peer methods.

Limitations and Future Work

The authors do not explicitly detail limitations within the paper. However, an inherent constraint of the approach is its reliance on pre-defined or pre-detected keypoints, making it less applicable to dense, pixel-to-pixel image matching tasks where explicit graph nodes are not provided. Future work could involve extending this graph transformer architecture to broader combinatorial optimization problems beyond visual graph matching.

Summary updated

Abstract

Vision transformers (ViTs) have recently been used for visual matching beyond object detection and segmentation. However, the original grid dividing strategy of ViTs neglects the spatial information of the keypoints, limiting the sensitivity to local information. Therefore, we propose QueryTrans (Query Transformer), which adopts a cross-attention module and keypoints-based center crop strategy for better spatial information extraction. We further integrate the graph attention module and devise a transformer-based graph matching approach GMTR (Graph Matching TRansformers) whereby the combinatorial nature of GM is addressed by a graph transformer neural GM solver. On standard GM benchmarks, GMTR shows competitive performance against the SOTA frameworks. Specifically, on Pascal VOC, GMTR achieves $\mathbf{83.6\%}$ accuracy, $\mathbf{0.9\%}$ higher than the SOTA framework. On Spair-71k, GMTR shows great potential and outperforms most of the previous works. Meanwhile, on Pascal VOC, QueryTrans improves the accuracy of NGMv2 from $80.1\%$ to $\mathbf{83.3\%}$, and BBGM from $79.0\%$ to $\mathbf{84.5\%}$. On Spair-71k, QueryTrans improves NGMv2 from $80.6\%$ to $\mathbf{82.5\%}$, and BBGM from $82.1\%$ to $\mathbf{83.9\%}$. Source code will be made publicly available.
BibTeX
@inproceedings{guo2024gmtr,
  author = {Jinpei Guo and Shaofeng Zhang and Runzhong Wang and Chang Liu and Junchi Yan},
  title = {{GMTR: Graph Matching Transformers}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2024},
  doi = {10.1109/icassp48485.2024.10448294},
}
Figure