Data Science and Engineering (DSE)是由中国计算机学会(CCF)主办，数据库专业委员会承办，施普林格·自然(Springer Nature)集团出版的开放获取(OA)期刊。本篇文章精选自DSE最新一期发文，得到中新赛克赞助文章处理费。

文章介绍

基于图的关键词搜索是图数据挖掘领域的一个重要任务，它指的是在给定的图数据中，找出覆盖给定查询关键词集合的最优子图结构。随着互联网和在线服务的普及，产生了大量的可供挖掘的图数据，关键词搜索被广泛应用在POIs(Point of Interests)推荐、网页查询等实际设施中。

本文从关键词的不同搜索语义出发，对现有基于图的关键词搜索的相关工作进行系统的归纳分类、分析总结，旨在为科研人员全面了解该领域的现有工作和研究进展提供方便。如图1所示，图关键词搜索的语义主要分为四种类型：基于子树结构的语义、基于最邻近邻居的语义、基于子图结构的语义以及其它语义。

图 1. 关键词搜索的语义分类

类型1：基于子树结构语义的关键词搜索

本文将子树结构关键词搜索分类为斯坦纳树和相异根树两种不同语义：

斯坦纳树语义的搜索目标是找到覆盖关键词集合的最优子树，使得该子树的边权重和最小。该语义下的现有工作，主要分为后向搜索算法、动态规划算法、基于索引的算法三种类型：后向搜索算法即从关键词匹配顶点出发，不断反向扩展，直到搜索到一个公共的根节点，能够达到所有的关键词匹配顶点；动态规划算法将关键词搜索问题转化为多阶段决策问题，它将一颗树的根顶点和其关键词覆盖集视为一个状态，对于同一个状态中的所有树，取其中边权重和最小的树，作为该状态对应的解答树；基于索引的算法利用最短路径的两跳标签索引(2-hop Label)技术，对于一个指定的根顶点，直接利用两跳标签去计算距离该顶点最近的各类关键词匹配顶点，然后将它们之间对应的最短路径组合成一颗解答树。

相异根语义的搜索目标是找到覆盖关键词集合的最优子树，使得该子树的根顶点(不同)到各关键词匹配顶点(叶子节点)的最短路径的和最小。该语义下的现有工作，分为双向搜索算法、两层索引算法、图概要算法三种：双向搜索算法在后向搜索算法的基础上增加了从潜在根节点向关键词节点前向扩展过程，以提高算法搜索效率；两层索引算法先将原图分块，分别构建块内最短路径索引和块间门户顶点间最短路径索引来减少空间开销；图概要算法设计图总结策略，将原图顶点和边合成超顶点和超边，以减少搜索空间。

类型2：基于最近邻语义的关键词搜索

本文将最近邻语义的关键词搜索分类为Top-K最近邻关键词搜索和Top-K最相关关键词搜索。其中Top-K最近邻关键词搜索指的是给定查询顶点，找到地理位置(图路径)上距离其最近的前K个关键词匹配顶点，根据查询要求不同，匹配顶点可分为全关键词覆盖和单一覆盖两种类型。该语义下的工作，主要目标就是通过建立索引来加快顶点对之间的最短路径距离查询的计算。目前主要技术有对图随机选择顶点以其为距离原点进行划分、建立最短路径树索引、建立两跳最短路径标签索引这三种。Top-K最相关关键词搜索指的是给定查询顶点，找到在地理位置(图路径)距离和顶点文本标签这两方面综合分数最高的前K个关键词匹配顶点。该语义比之前的语义的搜索难度更高，需要综合考虑顶点距离和文本相关性两部分，因此该语义下的工作的核心就是高效计算查询顶点和其它顶点之间的综合相关性。目前的主要技术有基于迪杰斯特拉(Dijkstra)的图搜索方法、建立图分块的关键词信息聚合的分块索引树方法(G-tree)、关键词信息分离的图索引方法三种主要技术。

类型3：基于子图结构语义的关键词搜索

本文将子图结构语义的关键词搜索分类为r-半径的斯坦纳树、多中心社区子图、r-团、强关联子图、稠密子图五种类型。其中r-半径的斯坦纳树指的是返回一个半径不超过r的子图，子图中的顶点由关键词匹配顶点和它们的最短路径上的顶点组成；多中心社区子图指的是找到有多个中心点的社区子图，其中每个中心点到任意关键词匹配点的距离不超过指定半径R，并且它们的距离和越小，则该子图分数越高；r-团(clique)指的是找到一组关键词匹配顶点，刚好覆盖查询关键词，并且任意关键词匹配点对之间的最短路径不超过r，所有关键词点对的距离之和越小，则该结果越好；强关联子图指的是找到一个覆盖所有关键词的子图，并且使得关键词匹配点对之间的随机游走分数之和越大越好；稠密子图指的是找到一个覆盖所有关键词的子图，并且该子图同时需要满足子图结构强关联，子图结构联度量一般引入社区稠密度的衡量指标，例如k-truss、k-core等。

类型4：基于其它语义的关键词搜索

除了上述几类主要语义之外，本文还介绍了其它的图关键词搜索语义，如基于本体的通用索引框架、路网上空间关键词搜索、路网上关键词路径等相关工作。其中基本本体的通用索引框架使用本体图迭代的对原数据图进行压缩和索引，去生成一个分层次的索引结构图，它是一个关键词搜索的通用框架；路网上的空间关键词搜索有两种不同的搜索目标，找到一组关键词的匹配顶点，第一种目标是查询顶点与匹配顶点之间的相关性和匹配顶点对之间多样性的综合分数最大，第二种目标是查询顶点与匹配顶点之间的最大距离以及匹配顶点对之间的最大距离的综合距离最小；路网上关键词路径指的是在给定不超过约束开销上限的条件下，在源点和终点之间，找到一条覆盖所有关键词的且使得路径最小的路径。

展望

本文归纳了图关键词搜索的一些有潜力的未来研究方向，例如其它具有本身特点的类型图上的关键词搜索，包括知识图谱、公-私网络、不确定图等；利用图嵌入技术结合图神经网络(GNN)进行图表征学习等现有深度学习技术来加速和扩展图关键词搜索任务；其次针对大规模真实数据模式，设计高效的图流数据上关键词搜索算法或者多机组的分布式关键词搜索技术也是一个新的发展方向。

作者简介

杨建业，湖南大学计算机科学系副教授，博士，博士生导师，香江学者。主要研究方向包括大数据分析，近年来在数据库及数据挖掘领域顶级期刊和会议上发表10余篇论文，其中包括VLDBJ、ICDE、TKDE、KAIS、WWWJ等中国计算机学会（CCF）推荐期刊和会议论文。主持国家自然科学基金青年项目一项。担任TKDE、VLDB、ICDE、ICDM、AAAI、KAIS、CIKM等多个国际权威期刊和会议审稿人，并受邀担任VLDB、CIKM、PAKDD等国际会议的程序委员会委员。

姚务，湖南大学计算机系硕士研究生，主要研究方向为图数据处理和图查询。

期刊简介

Data Science and Engineering（DSE）是由中国计算机学会（CCF）主办、数据库专业委员会承办、施普林格 自然（Springer Nature）出版的Open Access期刊。为了迎合相关领域的快速发展需求，DSE致力于出版所有和数据科学与工程领域相关的关键科学问题与前沿研究热点，以大数据作为研究重点，征稿范畴主要包括4方面：（1）数据本身，（2）数据信息提取方法，（3）数据计算理论，和（4）用来分析与管理数据的技术和系统。

目前期刊已被ESCI与SCOPUS收录，CiteScore2020为4.9，在Computer Science Applications领域排名#181/693（73^rd Percentile）。稿件处理费由赞助商中新赛克（Sinovatio）承担，欢迎大家免费下载阅读期刊全文，并积极投稿。

原文链接：https://link.springer.com/article/10.1007/s41019-021-00154-4