Proxy Graph Matching with Proximal Matching Networks

Hao-Ru Tan, Chuang Wang, Si-Tong Wu, Tie-Qiang Wang, Xu-Yao Zhang, Cheng-Lin LiuAAAI 2021 · OpenReview

Abstract

Estimating feature point correspondence is a common technique in computer vision. A line of recent data-driven approaches utilizing the graph neural networks improved the matching accuracy by a large margin. However, these learning-based methods require a lot of labeled training data, which are expensive to collect. Moreover, we find most methods are sensitive to global transforms, for example, a random rotation. On the contrary, classical geometric approaches are immune to rotational transformation though their performance is generally inferior. To tackle these issues, we propose a new learning-based matching framework, which is designed to be rotationally invariant. The model only takes geometric information as input. It consists of three parts: a graph neural network to generate a high-level local feature, an attention-based module to normalize the rotational transform, and a global feature matching module based on proximal optimization. To justify our approach, we provide a convergence guarantee for the proximal method for graph matching. The overall performance is validated by numerical experiments. In particular, our approach is trained on the synthetic random graphs and then applied to several real-world datasets. The experimental results demonstrate that our method is robust to rotational transform and highlights its strong performance of matching accuracy.

Introduction

Graph Matching (GM) is a fundamental problem in computer vision, involving the identification of correspondences between two sets of points based on their spatial relationships and features. While critical for applications such as object recognition and tracking, current methodologies face a significant trade-off between accuracy and robustness. Traditional geometric methods are inherently robust to global transformations like rotation but often lack the accuracy of modern data-driven approaches. Conversely, state-of-the-art Graph Neural Networks (GNNs) achieve high accuracy on aligned data but are notoriously "brittle," with performance collapsing under global rotations. Furthermore, these models typically require extensive human-labeled datasets, which are costly to produce.

This paper addresses these challenges by proposing a rotation-invariant GNN framework that can be trained exclusively on synthetic data, bridging the gap between the robustness of classical methods and the accuracy of deep learning.

Methodology

The proposed framework integrates three key components into a unified, differentiable architecture:

  1. High-order Local Feature Extractor: A GNN that processes 2D coordinates to generate high-dimensional local feature vectors. This allows the model to capture the structural context of each node within its local neighborhood.
  2. Differentiable Proximal Graph Matching (DPGM): To solve the NP-hard quadratic assignment problem efficiently, the authors relax it into a continuous version. This is solved using a proximal method with Kullback-Leibler (KL) divergence, decomposing the problem into convex subproblems solvable via the Sinkhorn-Knopp transform. This module is fully differentiable, enabling end-to-end training.
  3. Global Rotational Calibration Module (GRCM): This module employs a "search-and-align" strategy. It samples multiple rotation angles, creates proxy graphs, and uses an attention mechanism to identify the optimal alignment, ensuring the matching process is invariant to initial orientation.

Notably, the model is trained using only synthetic random graphs. By generating reference graphs and applying noise and outliers, the model learns to find correspondences without ever seeing a real-world image during training.

Experimental Results

The model was evaluated against several benchmarks, including Willow-Object, PASCAL-PF, and the CMU House Sequence.

Robustness to Rotation

A key highlight of the research is the model's performance on the PASCAL-PF dataset under random rotations. While previous state-of-the-art neural methods like DGMC saw accuracy drop from 95.7% to 24.5% when data was rotated, the proposed method maintained a high accuracy of 90.0%.

Figure 5: Comparison of matching accuracy across traditional and neural methods on original and rotated datasets. Our method demonstrates superior robustness to rotation compared to other learning-based approaches.

Performance on Sequences and Outliers

The CMU House Sequence was used to evaluate the model's robustness to varying frame gaps and outlier ratios. As shown in the results, the proposed method consistently outperforms or matches the performance of existing methods, maintaining high accuracy even as the complexity of the matching task increases with larger frame gaps and more outliers.

Figure 6: Accuracy vs. frame gap on the CMU House Sequence for different inlier-to-outlier ratios. Our method (red) shows strong stability and high accuracy across increasing gaps.

Conclusion

This work demonstrates that embedding classical optimization principles—specifically proximal methods—into a GNN architecture provides a powerful inductive bias for graph matching. By decoupling rotation through a calibration module and training on purely synthetic data, the proposed framework achieves a rare combination of high accuracy and extreme robustness. The theoretical convergence guarantees and strong empirical results on real-world datasets suggest that synthetic-only training is a viable path for complex geometric matching tasks.

Summary updated

Abstract

Estimating feature point correspondence is a common technique in computer vision. A line of recent data-driven approaches utilizing the graph neural networks improved the matching accuracy by a large margin. However, these learning-based methods require a lot of labeled training data, which are expensive to collect. Moreover, we find most methods are sensitive to global transforms, for example, a random rotation. On the contrary, classical geometric approaches are immune to rotational transformation though their performance is generally inferior. To tackle these issues, we propose a new learning-based matching framework, which is designed to be rotationally invariant. The model only takes geometric information as input. It consists of three parts: a graph neural network to generate a high-level local feature, an attention-based module to normalize the rotational transform, and a global feature matching module based on proximal optimization. To justify our approach, we provide a convergence guarantee for the proximal method for graph matching. The overall performance is validated by numerical experiments. In particular, our approach is trained on the synthetic random graphs and then applied to several real-world datasets. The experimental results demonstrate that our method is robust to rotational transform and highlights its strong performance of matching accuracy.
BibTeX
@inproceedings{tan2021proxy,
  author = {Hao-Ru Tan and Chuang Wang and Si-Tong Wu and Tie-Qiang Wang and Xu-Yao Zhang and Cheng-Lin Liu},
  title = {{Proxy Graph Matching with Proximal Matching Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=7TH4sFUYHp},
}
Figure