Learning deep graph matching with channel-independent embedding and Hungarian attention

Graph matching aims to establishing node-wise correspondence between two graphs, which is a classic combinatorial problem and in general NP-complete. Until very recently, deep graph matching methods start to resort to deep networks to achieve unprecedented matching accuracy. Along this direction, this paper makes two complementary contributions which can also be reused as plugin in existing works: i) a novel node and edge embedding strategy which stimulates the multihead strategy in attention models and allows the information in each channel to be merged independently. In contrast, only node embedding is accounted in previous works; ii) a general masking mechanism over the loss function is devised to improve the smoothness of objective learning for graph matching. Using Hungarian algorithm, it dynamically constructs a structured and sparsely connected layer, taking into account the most contributing matching pairs as hard attention. Our approach performs competitively, and can also improve state-of-the-art methods as plugin, regarding with matching accuracy on three public benchmarks. Recently, the seminal work namely deep graph matching (DGM) (Zanfir & Sminchisescu, 2018 ) is proposed to exploit the high capacity of deep networks for graph matching, which achieves stateof-the-art performance. This is in contrast to some early works which incorporate learning strategy 1 We assume graphs are of equal size for narrative simplicity. One can easily handle unbalanced graph size by adding dummy nodes as a common protocol in graph matching literature (Cho et al., 2010) . 2 A ia:jb typically encodes the affinity between pair (i, j) and (a, b) where node i, j ∈ G1 and a, b ∈ G2.