A novel subgraph querying method based on paths and spectra

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

来源：Neural Computing & Applications, 2019, 31(9): 5671-5678.

DOI：10.1007/s00521-018-3837-y

• 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.

• 出版日期2019-9
• 单位西安理工大学