论文标题：A subgraph matching algorithm based on subgraph index for knowledge graph (面向知识图谱的子图索引驱动的子图匹配算法)

期刊：Frontiers of Computer Science

作者：Yunhao SUN , Guanyu LI , Jingjing DU , Bo NING1, Heng CHEN

发表时间：18 Sep 2021

DOI：10.1007/s11704-020-0360-y

微信链接：点击此处阅读微信文章

导读

子图匹配问题是图搜索研究领域内的一个基本问题，它是 NP 完全问题。子图匹配问题最近已经成为知识图谱分析研究领域内一个热门的研究课题，并被广泛地应用在查询应答和语义搜索的场景中。在本文中，我们对面向知识图谱子图匹配问题进行了研究。具体地讲，给定一个查询图 q 和一个数据图 G，子图匹配问题指的是获取 G 中所有同构于 q 的数据子图。知识图谱被形式化地定义为一个有向的标签多图。由于知识图谱中任一节点对中可能包含多条边，因此，较于一般图而言，知识图谱具有更加稠密的语义和结构特征。为了提高知识图谱上的子图匹配的时间效率，我们提出了一种面向知识图谱的子图索引驱动的自图图匹配算法，被称之为 FGqT-Match。我们的子图匹配算法主要包括两个主要的设计。第一个设计是模式驱动的流图索引结构（FGqT），其用于事先地裁剪冗余的计算。第二个设计是多标签的权重矩阵，用于评估能够最小化中间结果的近似最优的匹配树。受益于我们这两个核心的设计，仅仅对 FGqT 进行遍历就可以得出所有的子图通过的答案。在真实和综合的数据集上大量实验评估表明，我们的技术优于最先进的算法。

文章精要

摘要

The problem of subgraph matching is one fundamental issue in graph search, which is NP-Complete problem. Recently, subgraph matching has become a popular research topic in the field of knowledge graph analysis, which has a wide range of applications including question answering and semantic search. In this paper, we study the problem of subgraph matching on knowledge graph. Specifically, given a query graph q and a data graph G, the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of q on G. Knowledge graph is formed as a directed labeled multi-graph having multiple edges between a pair of vertices and it has more dense semantic and structural features than general graph. To accelerate subgraph matching on knowledge graph, we propose a novel subgraph matching algorithm based on subgraph index for knowledge graph, called as FGqT-Match. The subgraph matching algorithm consists of two key designs. One design is a subgraph index of matching-driven flow graph ( FGqT), which reduces redundant calculations in advance. Another design is a multi-label weight matrix, which evaluates a near-optimal matching tree for minimizing the intermediate candidates. With the aid of these two key designs, all subgraph isomorphic mappings are quickly conducted only by traversing FGqT. Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.

相关内容推荐：

基于用户行为学习的个性化轨迹推荐 2022 16(3): 163610

EcoVis：工业级用电量时空相关性的可视分析 2022 16(2): 162604

流处理系统容错技术综述 2022 16(2): 162603

基于生成对抗网络的癌症分类研究 2022 16(2): 162601

基于城市公开数据的动态犯罪风险预测 2022 16(1): 161609

基于图应用特征的高效内存数据布局策略 2022 16(1): 161607

误差约束条件下的差分隐私优化发布机制 2022 16(1): 161608

基于RDMA和SkipList 的高效范围查询键值存储 2021 15(6): 156617

基于异构属性信息增强的网络表征深层框架 2021 15(6): 156616

数据库中平均开心率最大化加速算法 2021 15(6): 156618

一种面向物联网再制造的PCB产品质量状态编码方案 2021 15(5): 155615

VColor*：一种实用的大图着色方法 2021 15(4): 154610

基于多任务协调的信息网络融合 2021 15(4): 154608

分布式日志存储结构中的增量连接视图维护 2021 15(4): 154607

基于内容和协同过滤的时间感知混合推荐方案 2021 15(4): 154613

基于kNN的最优位置查询算法 2021 15(2): 152606

如何进行精准高效日志修复？一文阐述日志修复算法 2021 15(2): 152605

【FCS 信息系统专栏】一种基于RkNN的空间位置影响力评价与查询算法 2021 15(2): 152604

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、生命科学、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中13种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn