面向图相似性搜索的高效图编辑距离算法

在图相似性搜索问题中，图编辑距离是较为普遍的度量方法，其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题，提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分，以此计算映射编码来判断等价映射；然后定义映射完整性更新等价映射优先级，选出主映射参与扩展；其次，设计高效的启发式函数，提出基于映射编码的下界计算方法，快速得到最优映射。最后，将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明，该算法具有更好的搜索性能，在搜索空间上最大可降低49%，速度提升了约29%。

Efficient graph edit distance algorithm for graph similarity search

In graph similarity search, the graph edit distance algorithm is a common measurement method and its performance largely determines the graph similarity search performance. Aiming at the low performance of the traditional graph edit distance algorithm, such as many redundant mappings and large search space, this paper proposed an improved graph edit distance algorithm. Firstly, it divided all the vertices in the graph into several equivalent classes, by computing mapping encoding to judge equivalent mapping. Then it defined the mapping integrity to update the priority of equivalent mapping and selected main mapping to extend. Secondly, in order to quickly obtain the optimal mapping, it proposed a lower bound computation method based on the mapping encoding and designed an effective heuristic function. Finally, it applied the improved graph edit distance algorithm to graph similarity search. Experimental results show that the proposed algorithm has better search performance on multiple datasets, which can decrease the search space up to 49% and the speed increases about 29%.