  Graph matching refers to finding node correspondence between graphs, such
that the corresponding node and edge's affinity can be maximized. In addition
with its NP-completeness nature, another important challenge is effective
modeling of the node-wise and structure-wise affinity across graphs and the
resulting objective, to guide the matching procedure effectively finding the
true matching against noises. To this end, this paper devises an end-to-end
differentiable deep network pipeline to learn the affinity for graph matching.
It involves a supervised permutation loss regarding with node correspondence to
capture the combinatorial nature for graph matching. Meanwhile deep graph
embedding models are adopted to parameterize both intra-graph and cross-graph
affinity functions, instead of the traditional shallow and simple parametric
forms e.g. a Gaussian kernel. The embedding can also effectively capture the
higher-order structure beyond second-order edges. The permutation loss model is
agnostic to the number of nodes, and the embedding model is shared among nodes
such that the network allows for varying numbers of nodes in graphs for
training and inference. Moreover, our network is class-agnostic with some
generalization capability across different categories. All these features are
welcomed for real-world applications. Experiments show its superiority against
state-of-the-art graph matching learning methods.
