Deep Learning of Partial Graph Matching via Differentiable Top-K

Graph matching (GM) aims at discovering node matching between graphs, by maximizing the node-and edgewise affinities between the matched elements. As an NP-hard problem, its challenge is further pronounced in the existence of outlier nodes in both graphs which is ubiquitous in practice, especially for vision problems. However, popular affinity-maximization-based paradigms often lack a principled scheme to suppress the false matching and resort to handcrafted thresholding to dismiss the outliers. This limitation is also inherited by the neural GM solvers though they have shown superior performance in the ideal no-outlier setting. In this paper, we propose to formulate the partial GM problem as the top-k selection task with a given/estimated number of inliers k. Specifically, we devise a differentiable top-k module that enables effective gradient descent over the optimal-transport layer, which can be readily plugged into SOTA deep GM pipelines including the quadratic matching network NGMv2 as well as the linear matching network GCAN. Meanwhile, the attention-fused aggregation layers are developed to estimate k to enable automatic outlier-robust matching in the wild. Last but not least, we remake and release a new benchmark called IMC-PT-SparseGM, originating from the IMC-PT stereomatching dataset. The new benchmark involves more scale-varying graphs and partial matching instances from the real world. Experiments show that our methods outperform other partial matching schemes on popular benchmarks.

1. Introduction

The importance of graph matching (GM) is recognized by its successful applications in machine learning [26], molecule matching [47], and various vision tasks [15], [30], [49]. Existing GM methods mainly follow the optimization formulation by maximizing the node-wise and edgewise affinities of the matched elements, yielding an NP-hard problem known as Quadratic Assignment Problem [22]. Figure 1.

Illustrative comparison of injective graph matching (left) and partial graph matching (right) on our remade and released benchmark: imc-pt-sparsegm (originated from imc-pt [18], see sec. 4 for details). Green for correct matches, red for wrong matches. Without partial matching, the gm solver greedily matches all nodes, leading to inferior accuracy. This paper presents a general learning method to mitigate this issue.