The problem of subgraph matching is one funda-mental 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 sub-graph 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 know-ledge 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.

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

[1]Yunhao SUN;Guanyu LI;Jingjing DU;Bo NING;Heng CHEN-.A subgraph matching algorithm based on subgraph index for knowledge graph)[J].计算机科学前沿,2022(03):119-136

FGqT

subgraph,matching,knowledge,problem,one,funda,mental,issue,which,NP,Complete,Recently,has,become,popular,research,topic,field,analysis,wide,range,applications,including,question,answering,semantic,In,this,paper,study,Specifically,given,query,data,possible,isomorphic,mappings,Knowledge,formed,directed,labeled,having,multiple,edges,between,pair,vertices,more,dense,structural,features,than,general,To,accelerate,propose,novel,called,Match,consists,two,key,designs,One,driven,flow,reduces,redundant,calculations,advance,Another,weight,matrix,evaluates,near,optimal,tree,minimizing,intermediate,candidates,With,aid,these,are,quickly,conducted,only,by,traversing,Extensive,empirical,studies,real,synthetic,graphs,demonstrate,that,our,techniques,outperform,state,art,algorithms

0.492225