Scalable Top-k Query on Information Networks with Hierarchical Inheritance Relations
Scalable Top-k Query on Information Networks with Hierarchical Inheritance Relations
复制标题
DOI：
10.1007/s10619-023-07432-2
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Fubao Wu;Lixin Gao
中科院分区：
文献类型：
--
作者：
Fubao Wu;Lixin Gao
在大规模异构信息网络中，图查询、模式挖掘和知识发现成为一个具有挑战性的问题。涉及路径传播的最新技术主要集中在节点标签和邻域结构的推断上。然而，真实的世界中的实体链接也包含着丰富的层次继承关系。例如，产品版本的漏洞可能是从其旧版本继承而来的。利用层次继承可以潜在地提高查询结果的质量。基于此，我们探讨了实体之间的层次继承关系，并提出了层次继承关系的HIN上的图查询问题。我们提出了一个图查询搜索算法，通过分解原始查询图成多个星星查询和应用一个星星查询算法，每个星星查询。然后，为原始查询的最终前k个查询答案构造来自每个星星查询结果的候选。为了有效地从大规模HIN中获得图查询结果，我们设计了一种基于边界的剪枝技术，通过使用均匀代价搜索来修剪搜索空间。我们在Spark GraphX中实现了我们的算法，以测试合成和真实世界数据集的有效性和效率。与两种最先进的图查询算法相比，我们的算法可以有效地获得更准确的结果和竞争力的性能。
Graph query, pattern mining and knowledge discovery become challenging on large-scale heterogeneous information networks (HINs). State-of-the-art techniques involving path propagation mainly focus on the inference of node labels, and neighborhood structures. However, entity links in the real world also contain rich hierarchical inheritance relations. For example, the vulnerability of a product version is likely to be inherited from its older versions. Taking advantage of the hierarchical inheritances can potentially improve the quality of query results. Motivated by this, we explore hierarchical inheritance relations between entities and formulate the problem of graph query on HINs with hierarchical inheritance relations. We propose a graph query search algorithm by decomposing the original query graph into multiple star queries and applying a star query algorithm to each star query. Candidates from each star query result are then constructed for the final top-kquery answer to the original query. To efficiently obtain the graph query result from a large-scale HIN, we design a bound-based pruning technique by using the uniform cost search to prune the search spaces. We implement our algorithm in Spark GraphX to test the effectiveness and efficiency on synthetic and real-world datasets. Compared with two state-of-the-art graph query algorithms, our algorithm can effectively obtain more accurate results and competitive performance.