SHOT: Structured Hierarchical Optimal Transport for Robust Graph Matching

Graph matching aims to find node correspondences across different graphs, with wide applications in knowledge engineering and data science, e.g., entity alignment across knowledge graphs. However, existing graph matching methods often suffer from robustness issues when graphs are highly noisy or cross domains. In this study, we propose a novel Structured Hierarchical Optimal Transport (SHOT) framework that leverages advanced computational Optimal Transport (OT) techniques to achieve robust graph matching with a mild computational cost. Given two graphs, SHOT first extracts multi-layer node embeddings via a pretrained or predefined graph neural network. Then, it aligns their node embeddings within the same layer and across different layers, respectively, and infers the node correspondences by learning the weighted average of the alignments of all layer pairs, yielding a Hierarchical Optimal Transport (HOT) between the two graphs. For each layer pair, SHOT enables different alignments to share the same structure, resulting in an efficient algorithmic implementation. In theory, we establish the connection between SHOT and existing OT-based graph matching methods, demonstrating its advantages. Experiments on various graph matching tasks demonstrate the superiority and robustness of our method compared to state-of-the-art approaches.