A novel subgraph querying method based on paths and spectra

作     者：Zhu, Lei Yao, Yanni Wang, Yichuan Hei, Xinhong Zhao, Qin Ji, Wenjiang Yao, Quanzhu 

作者机构：Xian Univ Technol 5 Jinhua South Rd Xian Shaanxi Peoples R China 

出 版 物：《NEURAL COMPUTING & APPLICATIONS》 (神经网络计算与应用)

年 卷 期：2019年第31卷第9期

页      面：5671-5678页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [61602374, 61602376, 61702411] Natural Science Foundation of Shaanxi Province [2016JQ6041, 2017JQ6020] Natural Science Foundation of Shaanxi Provincial Department of Education [16JK1552, 16JK1573] Foundation of Xi'an University of Technology [112-451115002] 

主　　题：Subgraph querying Filtering-and-verification framework Two-step filtering strategy Shortest path 

摘      要：Graph and graph database are widely used in many domains, and the graph querying attracts more and more attentions. Among these querying problems, subgraph querying is the most compelling one, since it contains very expensive subgraph isomorphism. The paper proposes a novel subgraph querying method PLGCoding, which use some information of shortest paths and Laplacian spectra to filter out false positives. Specifically, we first extract some features, including some information of vertices, edges, the shortest paths and Laplacian spectra, and encode extracted features. An index PLGCode-Tree is built based on codes to shrink the candidate set. Then, we propose two-step filtering strategy to implement the filtering-and-verification framework and thus generate the answer set. Compared with competing methods on real dataset, experimental results show PLGCoding can improve the querying efficiency.