A subgraph matching algorithm based on subgraph index for knowledge graph

doi:10.1007/s11704-020-0360-y

Frontiers of Computer Science

2022, Vol. 16

Issue (3): 163606 https://doi.org/10.1007/s11704-020-0360-y

本期目录

A subgraph matching algorithm based on subgraph index for knowledge graph

Yunhao SUN¹, Guanyu LI¹(

), Jingjing DU¹, Bo NING¹, Heng CHEN^1,²

¹. Faculty of Information Science and Technology, Dalian Maritime University, Liaoning 116026, China
². Faculty of Software, Dalian University of Foreign Languages, Liaoning 116044, China

全文: PDF(12660 KB) HTML

Abstract：

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 $F G q T$ -Match. The subgraph matching algorithm consists of two key designs. One design is a subgraph index of matching-driven flow graph ( $F G q T$ ), 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 $F G q T$ . Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.

Key words： knowledge graph subgraph matching subgraph index matching tree

收稿日期: 2020-07-22 出版日期: 2021-09-18

Corresponding Author(s): Guanyu LI

引用本文:

. [J]. Frontiers of Computer Science, 2022, 16(3): 163606.
Yunhao SUN, Guanyu LI, Jingjing DU, Bo NING, Heng CHEN. A subgraph matching algorithm based on subgraph index for knowledge graph. Front. Comput. Sci., 2022, 16(3): 163606.

链接本文:

https://academic.hep.com.cn/fcs/CN/10.1007/s11704-020-0360-y
https://academic.hep.com.cn/fcs/CN/Y2022/V16/I3/163606

Fig.1

Fig.2

Fig.3

Fig.4

Notations	Meanings
$q$ $=$ ( $V q$ , $E q$ , $L$ )	a directed query multi-graph with $V q$ , edge set $E q$ and labeling function $L$
$G$ $=$ ( $V$ , $E$ , $L$ )	a directed data multi-graph with vertex set $V$ , edge set $E$ and labeling function $L$
$q T$ $=$ ( $V T$ , $E T$ )	a matching tree of $q$ with node set $V T$ and edge set $E T$
$F G q T$ $=$ ( $r$ , $V F$ , $E F$ , $L F$ )	a matching-driven flow graph of $q$ on $G$ with a root $r$ , vertex set $V F$ , edge set $E F$ and labeling function $L F$
$? v, u ?$	a query-data vertex pair with $v ∈ V$ and $u ∈ V q$
$M$	a subgraph isomorphic mapping of $q$ on $G$ ,
	$M$ $=$ ${? v 1, u 1 ?, ? v 2, u 2 ?, …, ? v n, u n ?}$
$M ~ i$	a partial subgraph isomorphic mapping
	$M ~ i =$ ${? v 1, u 1 ?, ? v 2, u 2 ?, …, ? v i, u i ?}$ , $M ~ i$ $?$ $M$
$M$	a set of subgraph isomorphic mappings $M$ s of $q$ on $G$
$C (u)$	a candidate set of $u$ , $u$ $∈$ $V q$
$C R (u, v)$	a candidate region of $u$ and adjacent to $v$ , $u$ $∈$ $V q$ , $v$ $∈$ $V$

Tab.1

Fig.5

Semantic Dictionary		Data Dictionary of $G$
University	$A$	$U 1$	$v 1$
GraduatedStudent	$B$	$P 1$	$v 2$
Student	$C$	Data Storage of Vertices
hasName	$D$	$v 1$	${A}$
GraduatedFrom	$a$	$v 2$	${$ $B$ , $C$ $}$ , ${$ $? D, “ L i l y ” ?$ $}$
Data Storage of Edges
$e$	( $v 2$ , $v 1$ )		$a$

Tab.2

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Fig.14

Fig.15

Fig.16

Fig.17

Fig.18

Fig.19

Fig.20

Methods	Index Structures	Matching Order
TurboHOM	Adjacency List	Infrequent Node First
CFLMatch	Compact Path Index	Infrequent Path First
$F G q T$ -Match	Subgraph Index	Cost-Balanced Matching Tree

Tab.3

Parameters	Dimensions
Query Size	$10$	$15$	$20$	$25$	$30$
Data Size	$104$	$5 × 104$	$105$	$5 × 105$	$106$
Density	$0.01$	$0.1$	$1$	$10.0$	$100$

Tab.4

Fig.21

Fig.22

Fig.23

Fig.24

Fig.25

Fig.26

1	S Hu , L Zou , J X Yu , H Wang , D Zhao . Answering natural language questions by subgraph matching over knowledge graphs. IEEE Transactions on Knowledge and Data Engineering, 2018, 30( 5): 824– 837
2	Xu Q, Wang X, Li J, Gan Y, Chai L, Wang J. StarMR: an efficient star-decomposition based query processor for SPARQL basic graph patterns using MapReduce. In: proceedings of Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint International Conference on Web and Big Data. 2018, 415-430
3	T Cai , J Li , A S Mian , T Sellis , J X Yu . Target-aware holistic influence maximization in spatial social networks. IEEE Transactions on Knowledge and Data Engineering, 2020,
4	Shekhar S, Xiong H, Zhou X. Encyclopedia of GIS: Resource Description Framework(RDF). 1st ed. Cham: Springer International Publishing, 2017
5	Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. 1st ed. New York: W. H. Freeman, 1979
6	J Kim , H Shin , W H Han , S Hong , H Chafi . Taming subgraph isomorphism for RDF query processing. Proceedings of the VLDB Endowment, 2015, 8( 11): 1238– 1249
7	Ingalalli V, Ienco D, Poncelet P, Villata S. Querying RDF data using a multigraph-based approach. In: Proceedings of the 19th International Conference on Extending Database Technology. 2016, 245-256
8	H Ma , M A Langouri , Y Wu , F Chiang , J Pi . Ontology-based entity matching in attributed graphs. Proceedings of the VLDB Endowment, 2019, 12( 10): 1195– 1207
9	L P Cordella , P Foggia , C Sansone , M Vento . A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 26( 10): 1367– 1372
10	He H, Singh A K. Graphs-at-a-time: query language and accessmethods for graph databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2008, 405-418
11	P Zhao , J Han . On graph query optimization in large networks. Proceedings of the VLDB Endowment, 2010, 3( 1): 340– 351
12	Han W, Lee J, Lee J H. Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2013, 337–348
13	Bi F, Chang L, Lin X, Qin L, Zhang W. Efficient subgraph matching by postponing cartesian products. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2016, 1199−1214
14	H Shang , Y Zhang , X Lin , J X Yu . Taming verification hardness: an efficient algorithm for testing subgraph isomorphism. Proceedings of the VLDB Endowment, 2008, 1( 1): 364– 375
15	Kim K, Seo I, Han W S, Hong S, Chafi H, Shin H, Jeong G. Turboflux: A fast continuous subgraph matching system for streaming graph data. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2018, 411-426
16	J R Ullmann . An algorithm for subgraph isomorphism. Journal of the ACM, 1976, 23( 1): 31– 42
17	Jin X, Lai L. MPMatch: A Multi-core Parallel Subgraph Matching Algorithm. In: Proceedings of IEEE 35th International Conference on Data Engineering Workshops. 2019, 241−248
18	Bhattarai B, Liu H, Huang H. CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2019, 1447−1462
19	P Peng , L Zou , Z Du , D Zhao . Using partial evaluation in holistic subgraph search. Frontiers of Computer Science, 2017, 12( 5): 966– 983
20	Y Ma , Y Yuan , M Liu , G Wang , Y Wang . Graph simulation on large scale temporal graphs. GeoInformatica, 2020, 24( 1): 199– 220
21	P Lin , Q Song , Y Wu . Fact checking in knowledge graphs with ontological subgraph patterns. Data Science and Engineering, 2018, 3 : 341– 358
22	Xu Y, Tong Y, Shi Y, Tao Q, Xu Ke, Li W. An Efficient Insertion Operator in Dynamic RideSharing Services. In: Proceedings of IEEE 35th International Conference on Data Engineering. 2019, 1022−1033
23	L Zou , M T Özsu , L Chen , X Shen , R Huang , D Zhao . gStore: a graph-based SPARQL query engine. The VLDB Journal, 2014, 23( 4): 565– 590
24	L Zeng , L Zou . Redesign of the gStore system. Frontiers of Computer science, 2018, 12( 4): 1– 19
25	X Wang , Le Chai , Q Xu , Y Yang , J Li , J Wang , Y Chai . Efficient subgraph matching on large RDF graphs using MapReduce. Data Science and Engineering, 2019, 4 : 24– 43
26	Q Xu , X Wang , J Li , Q Zhang , L Chai . Distributed subgraph matching on big knowledge graphs using pregel. IEEE Access, 2019, 7 : 116453– 116464
27	Malewicz G, Austern M H, Bik, A J C, Dehnert J C. Pregel: A system for large-scale graph processing. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. 2010, 135−146
28	J Li , T Cai , K Deng , X Wang , T Sellis , F Xia . Community-diversified influence maximization in social networks. Information Systems, 2020, 92 : 101522–
29	Y Ma , Y Yuan , G Wang , X Bi , Z Wang , Y Wang . Rising star evaluation based on extreme learning machine in geo-social networks. Cognitive Computation, 2020, 12( 1): 296– 308
30	Wang Y, Tong Y, Long C, Xu P, Xu K, Lv W. Adaptive dynamic bipartite graph matching: a reinforcement learning approach. In: Proceedings of IEEE 35th International Conference on Data Engineering, 2019, 1478−1489
31	W Zheng , L Zou , W Peng , X Yan , S Song , D Zhao . Semantic SPARQL similarity search over RDF knowledge graphs. Proceedings of the VLDB Endowment, 2016, 9( 11): 840– 851

[1]

Highlights

Download

Viewed

Full text

Abstract

Cited

Shared

Discussed