Subgraph similarity search, one of the core problems in graph search,
concerns whether a target graph approximately contains a query graph. The
problem is recently touched by neural methods. However, current neural methods
do not consider pruning the target graph, though pruning is critically
important in traditional calculations of subgraph similarities. One obstacle to
applying pruning in neural methods is {the discrete property of pruning}. In
this work, we convert graph pruning to a problem of node relabeling and then
relax it to a differentiable problem. Based on this idea, we further design a
novel neural network to approximate a type of subgraph distance: the subgraph
edit distance (SED). {In particular, we construct the pruning component using a
neural structure, and the entire model can be optimized end-to-end.} In the
design of the model, we propose an attention mechanism to leverage the
information about the query graph and guide the pruning of the target graph.
Moreover, we develop a multi-head pruning strategy such that the model can
better explore multiple ways of pruning the target graph. The proposed model
establishes new state-of-the-art results across seven benchmark datasets.
Extensive analysis of the model indicates that the proposed model can
reasonably prune the target graph for SED computation. The implementation of
our algorithm is released at our Github repo:
this https URL.

本研究提出了一种基于神经网络的子图相似性搜索方法，结合了剪枝技术和注意力机制，通过将图剪枝转化为节点重标记的可微分问题，并设计了多头剪枝策略，有效地优化了子图编辑距离计算。在七个基准数据集上实现了最新的最优结果。