SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm
This addresses the challenge of aligning nodes in correlated graphs for applications where topological information is the only available data, representing an incremental improvement over existing methods.
The paper tackles the problem of graph matching without side information by introducing a structural inconsistency (SI) criterion based on heat diffusion wavelets to measure accuracy, and proposes SIGMA, an algorithm that reduces SI to improve alignment, which outperforms state-of-the-art methods in experiments.
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.