High-Order Relation Construction and Mining for Graph Matching
This addresses the challenge of capturing structural similarity in large-scale graphs for applications like network alignment or bioinformatics, representing a novel method for a known bottleneck.
The paper tackles the problem of graph matching by incorporating high-order information using iterated line graphs, resulting in a method called HGMN that achieves more accurate matching results than state-of-the-art methods.
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.