  Graph matching finds the correspondence of nodes across two correlated graphs
and lies at the core of many applications. When graph side information is not
available, the node correspondence is estimated on the sole basis of network
topologies. In this paper, we propose a novel criterion to measure the graph
matching accuracy, structural inconsistency (SI), which is defined based on the
network topological structure. Specifically, SI incorporates the heat diffusion
wavelet to accommodate the multi-hop structure of the graphs. Based on SI, we
propose a Structural Inconsistency reducing Graph Matching Algorithm (SIGMA),
which improves the alignment scores of node pairs that have low SI values in
each iteration. Under suitable assumptions, SIGMA can reduce SI values of true
counterparts. Furthermore, we demonstrate that SIGMA can be derived by using a
mirror descent method to solve the Gromov-Wasserstein distance with a novel
K-hop-structure-based matching costs. Extensive experiments show that our
method outperforms state-of-the-art methods.
