We present TFGM (Training Free Graph Matching), a framework to boost the performance of Graph Neural Networks (GNNs) based graph matching without training. TFGM sidesteps two crucial problems when training GNNs: 1) the limited supervision due to expensive annotation, and 2) training's computational cost. A basic framework, BasicTFGM, is first proposed by adopting the inference stage of graph matching methods. Our analysis shows that the BasicTFGM is a linear relaxation to the quadratic assignment formulation of graph matching. This guarantees the preservation of structure compatibility and an efficient polynomial complexity. Empirically, we further improve the BasicTFGM by handcrafting two types of matching priors into the architecture of GNNs: comparing node neighborhoods of different localities and utilizing annotation data if available. For evaluation, we conduct extensive experiments on a broad set of settings, including supervised keypoint matching between images, semi-supervised entity alignment between knowledge graphs, and unsupervised alignment between protein interaction networks. Applying TFGM on various GNNs shows promising improvements over baselines. Further ablation studies demonstrate the effective and efficient training-free property of TFGM. Our code is available at https://github.com/acharkq/Training-Free-Graph-Matching.

翻译：我们首先提出一个基本框架,即基本TFGM, 采用图形匹配方法的推论阶段。我们的分析表明,基本TFTGM是对图形匹配的二次分配配方的线性放松。这保证了结构的兼容性和高效的多元性复杂性。我们随机地进一步改进基本TFTFGM, 将两种匹配的前身搭进GNNS的架构:比较不同地点的节点区,如果有的话,则使用注解数据。为了评估,我们首先对一系列广泛的环境进行了广泛的实验,包括受监督的图像关键点匹配、知识图表之间半超超标准的实体对齐,以及蛋白质互动网络之间的非超强对齐。在各种GNFS网络上应用GM显示有希望的改进基线。进一步的研究显示,在TFMM/GADR上可有效且高效的培训。