Abstract
Graph matching involves combinatorial optimization based on edge-to-edgeaffinity matrix, which can be generally formulated as Lawler's QuadraticAssignment Problem (QAP). This paper presents a QAP network directly learningwith the affinity matrix (equivalently the association graph) whereby thematching problem is translated into a vertex classification task. Theassociation graph is learned by an embedding network for vertex classification,followed by Sinkhorn normalization and a cross-entropy loss for end-to-endlearning. We further improve the embedding model on association graph byintroducing Sinkhorn based matching-aware constraint, as well as dummy nodes todeal with unequal sizes of graphs. To our best knowledge, this is the firstnetwork to directly learn with the general Lawler's QAP. In contrast, recentdeep matching methods focus on the learning of node and edge features in twographs respectively. We also show how to extend our network to hypergraphmatching, and matching of multiple graphs. Experimental results on bothsynthetic graphs and real-world images show its effectiveness. For pure QAPtasks on synthetic data and QAPLIB benchmark, our method can performcompetitively and even surpass state-of-the-art graph matching and QAP solverswith notable less time cost. Source code will be made public athttps://github.com/Thinklab-SJTU/