Graph matching aims to establish node correspondence between two graphs, which has been a fundamental problem for its NP-complete nature. One practical consideration is the effective modeling of the affinity function in the presence of noise, such that the mathematically optimal matching result is also physically meaningful. This paper resorts to deep neural networks to learn the node and edge feature, as well as the affinity model for graph matching in an end-to-end fashion. The learning is supervised by combinatorial permutation loss over nodes. Specifically, the parameters belong to convolutional neural networks for image feature extraction, graph neural networks for node embedding that convert the structural (beyond second-order) information into node-wise features that leads to a linear assignment problem, as well as the affinity kernel between two graphs. Our approach enjoys flexibility in that the permutation loss is agnostic to the number of nodes, and the embedding model is shared among nodes such that the network can deal with varying numbers of nodes for both training and inference. Moreover, our network is class-agnostic. Experimental results on extensive benchmarks show its state-of-the-art performance. It bears some generalization capability across categories and datasets, and is capable for robust matching against outliers.

Permutation loss and Intra-graph Affinity based Graph Matching (PIA-GM) and
Permutation loss and Cross-graph Affinity based Graph Matching (PCA-GM)


Iterative Permutation loss and Cross-graph Affinity based Graph Matching (IPCA-GM)

Visualization result is provided on the testing set of 20 VOC categories.
Keypoints with the same color stands for predicted correspondence. And the white outer color means correct prediction, while the red outer color means incorrect prediction. (Click the image to zoom in)