论文标题
NASS：一种新的图形相似性搜索方法
Nass: A New Approach to Graph Similarity Search
论文作者
论文摘要
在本文中，我们研究了图形编辑距离（GED）约束的图形相似性搜索问题。由于GED计算的NP硬度，该问题的现有解决方案采用过滤和验证框架，主要关注过滤阶段，以生成少量的候选图。但是，他们有一个限制，即随着GED阈值的增加，候选人的数量非常迅速。为了解决限制，我们提出了一种利用GED计算的新方法来生成候选图。主要思想是，每当我们识别查询的结果图时，我们就会使用类似于确定的结果图的预计图的子集立即再生候选图。为了加快GED计算，我们还开发了一种新型的GED计算算法。所提出的算法通过利用一系列过滤技术来减少GED计算的搜索空间，这些技术已用于在现有解决方案中生成候选者。实际数据集的实验结果表明，所提出的方法的表现明显优于最先进的技术。
In this paper, we study the problem of graph similarity search with graph edit distance (GED) constraints. Due to the NP-hardness of GED computation, existing solutions to this problem adopt the filtering-and-verification framework with a main focus on the filtering phase to generate a small number of candidate graphs. However, they have a limitation that the number of candidates grows extremely rapidly as a GED threshold increases. To address the limitation, we propose a new approach that utilizes GED computation results in generating candidate graphs. The main idea is that whenever we identify a result graph of the query, we immediately regenerate candidate graphs using a subset of pre-computed graphs similar to the identified result graph. To speed up GED computation, we also develop a novel GED computation algorithm. The proposed algorithm reduces the search space for GED computation by utilizing a series of filtering techniques, which have been used to generate candidates in existing solutions. Experimental results on real datasets demonstrate the proposed approach significantly outperforms the state-of-the art techniques.
