FCS | 前沿研究：面向知识图谱的子图索引驱动的子图匹配算法
论文标题：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.
相关内容推荐：
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或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。
中国学术前沿期刊网
特别声明：本文转载仅仅是出于传播信息的需要，并不意味着代表本网站观点或证实其内容的真实性；如其他媒体、网站或个人从本网站转载使用，须保留本网站注明的“来源”，并自负版权等法律责任；作者如果不希望被转载或者联系转载稿费等事宜，请与我们接洽。
