  Graph matching pairs corresponding nodes across two or more graphs. The
problem is difficult as it is hard to capture the structural similarity across
graphs, especially on large graphs. We propose to incorporate high-order
information for matching large-scale graphs. Iterated line graphs are
introduced for the first time to describe such high-order information, based on
which we present a new graph matching method, called High-order Graph Matching
Network (HGMN), to learn not only the local structural correspondence, but also
the hyperedge relations across graphs. We theoretically prove that iterated
line graphs are more expressive than graph convolution networks in terms of
aligning nodes. By imposing practical constraints, HGMN is made scalable to
large-scale graphs. Experimental results on a variety of settings have shown
that, HGMN acquires more accurate matching results than the state-of-the-art,
verifying our method effectively captures the structural similarity across
different graphs.
