GHashing: Semantic Graph Hashing for Approximate Similarity Search in Graph Databases
GHashing: Semantic Graph Hashing for Approximate Similarity Search in Graph Databases
复制标题
DOI：
10.1145/3394486.3403257
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Zongyue Qin;Yunsheng Bai;Yizhou Sun
中科院分区：
文献类型：
--
作者：
Zongyue Qin;Yunsheng Bai;Yizhou Sun
图相似性搜索的目的是在图数据库中找到与查询最相似的图，根据给定的邻近度量，例如图编辑距离（GED）。这是一个被广泛研究但仍然具有挑战性的问题。大多数的研究都是基于剪枝-验证框架，该框架首先对非前景图进行剪枝，然后对小的候选集进行验证。现有的方法能够管理具有数千或数万个图的数据库，但由于其精确的修剪策略，无法扩展到更大的数据库。受最近基于深度学习的语义哈希在图像和文档检索中的成功启发，我们提出了一种新的基于图神经网络（GNN）的语义哈希，即GHashing，用于近似修剪。我们首先用地面真实的GED结果训练GNN，以便它学习生成嵌入和哈希码，以保持图之间的GED。然后构建散列索引以在恒定时间内启用图查找。为了回答查询，我们使用哈希码和连续嵌入作为两级修剪来检索最有希望的候选者，这些候选者被发送到精确求解器进行最终验证。由于我们的图哈希技术利用了近似修剪策略，与最先进的方法相比，我们的方法在保持高召回率的同时实现了更快的查询时间。实验表明，我们的方法平均比唯一的基线，工作在百万级数据库，这表明GHashing成功地为解决大规模图数据库的图搜索问题提供了一个新的方向快20倍。
Graph similarity search aims to find the most similar graphs to a query in a graph database in terms of a given proximity measure, say Graph Edit Distance (GED). It is a widely studied yet still challenging problem. Most of the studies are based on the pruning-verification framework, which first prunes non-promising graphs and then conducts verification on the small candidate set. Existing methods are capable of managing databases with thousands or tens of thousands of graphs, but fail to scale to even larger database, due to their exact pruning strategy. Inspired by the recent success of deep-learning-based semantic hashing in image and document retrieval, we propose a novel graph neural network (GNN) based semantic hashing, i.e. GHashing, for approximate pruning. We first train a GNN with ground-truth GED results so that it learns to generate embeddings and hash codes that preserve GED between graphs. Then a hash index is built to enable graph lookup in constant time. To answer a query, we use the hash codes and the continuous embeddings as two-level pruning to retrieve the most promising candidates, which are sent to the exact solver for final verification. Due to the approximate pruning strategy leveraged by our graph hashing technique, our approach achieves significantly faster query time compared to state-of-the-art methods while maintaining a high recall. Experiments show that our approach is on average 20x faster than the only baseline that works on million-scale databases, which demonstrates GHashing successfully provides a new direction in addressing graph search problem for large-scale graph databases.