论文标题
Sigma：一种结构上的不一致，减少了匹配算法的图形
SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm
论文作者
论文摘要
图形匹配发现了两个相关图的节点的对应关系，并且位于许多应用程序的核心。当图侧信息不可用时，节点对应关系将根据网络拓扑的唯一估算。在本文中，我们提出了一个新的标准，以测量图形匹配的精度，结构上不一致（SI），该标准是根据网络拓扑结构定义的。具体而言，SI结合了热扩散小波，以适应图的多跳结构。基于SI，我们提出了一个结构上的不一致匹配算法（Sigma）的结构上的不一致，该算法（Sigma）改善了每次迭代中SI值较低的节点对的比对分数。在合适的假设下，Sigma可以降低真实对应物的Si值。此外，我们证明可以通过使用镜下下降方法来衍生Sigma，以基于K-Hop结构的新型匹配成本来解决Gromov-Wasserstein距离。广泛的实验表明，我们的方法优于最先进的方法。
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.
