Graph similarity computation aims to predict a similarity score between one pair of graphs to facilitate downstream applications, such as finding the most similar chemical compounds similar to a query compound or Fewshot 3D Action Recognition. Recently, some graph similarity computation models based on neural networks have been proposed, which are either based on graph-level interaction or node-level comparison. However, when the number of nodes in the graph increases, it will inevitably bring about reduced representation ability or high computation cost. Motivated by this observation, we propose a graph partitioning and graph neural network-based model, called PSimGNN, to effectively resolve this issue. Specifically, each of the input graphs is partitioned into a set of subgraphs to extract the local structural features directly. Next, a novel graph neural network with an attention mechanism is designed to map each subgraph into an embedding vector. Some of these subgraph pairs are automatically selected for node-level comparison to supplement the subgraph-level embedding with fine-grained information. Finally, coarse-grained interaction information among subgraphs and fine-grained comparison information among nodes in different subgraphs are integrated to predict the final similarity score. Experimental results on graph datasets with different graph sizes demonstrate that PSimGNN outperforms state-of-the-art methods in graph similarity computation tasks using approximate Graph Edit Distance (GED) as the graph similarity metric.
翻译:图形相似性计算旨在预测一对图表之间的相似性分数,以便利下游应用,例如找到类似于查询化合物或微小截图 3D 行动识别的最为相似的化学化合物。最近,根据神经网络提出了一些基于神经网络的图形相似性计算模型,这些模型以图形层面的互动或节点层面的比较为基础。然而,当图形中节点的数量增加时,它必然带来代表能力下降或高计算成本。根据这一观察,我们提议了一个图形分区和图形神经网络模型,称为PSimGNN,以有效解决这一问题。具体地说,每个输入图表被分割成一组子图,以直接提取本地结构特征。接下来,设计了一个具有关注机制的新图形神经网络,将每个子图绘制成嵌入矢量。一些子图配将自动选择为无偏度的比较,以精细度信息来补充子绘图级嵌入的神经网络网络模式。最后,子图配有子图和精度直径直径直径直径直径直径图形的对比信息,在不同的亚级图表中不使用不同的缩缩缩缩缩缩缩缩缩缩缩缩缩缩图的图表中,从而显示不同的细度预测。