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: https://github.com/tufts-ml/Prune4SED.

翻译：子线相似性搜索是图形搜索的核心问题之一,它关系到目标图是否包含一个查询图。 这个问题最近被神经方法所触及。 但是, 当前神经方法并不考虑调整目标图, 尽管在传统计算子线相似性时, 修剪是极为重要的。 在神经方法中应用修剪的一个障碍是 { 修剪的离散属性} 模型的设计中, 我们建议一个关注机制来利用关于查询图的信息, 并指导目标图的修剪。 此外, 我们根据这个想法, 进一步设计一个新的神经网络, 以近似一个子图类型的距离: 子图编辑距离 。 { 特别是, 我们用一个神经结构构建修剪裁部分, 整个模型可以优化尾端 } 在模型的设计中, 我们建议一个关注机制来利用关于查询图的信息, 并指导目标图的修剪裁。 此外, 我们开发了一个多头运行策略, 以便模型可以更好地探索目标图的多种方法: 底线编辑方式编辑距离 。 特别是, 我们用一个直径图的模型, 将显示我们所拟议的直径直径基图的模型 。 。