Supergraph Topology Feature Index for Personalized Interesting Subgraph Query in Large Labeled Graphs
Interesting subgraph query aims to find subgraphs that are isomorphic to the given query graph from a data graph and rank the subgraphs according to their interestingness scores. However, the existing subgraph query approaches are inefficient when dealing with large-scale labeled data graph. This is...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2021/9274429 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832548964973412352 |
|---|---|
| author | Xiaohuan Shan Haihai Li Chunjie Jia Dong Li Baoyan Song |
| author_facet | Xiaohuan Shan Haihai Li Chunjie Jia Dong Li Baoyan Song |
| author_sort | Xiaohuan Shan |
| collection | DOAJ |
| description | Interesting subgraph query aims to find subgraphs that are isomorphic to the given query graph from a data graph and rank the subgraphs according to their interestingness scores. However, the existing subgraph query approaches are inefficient when dealing with large-scale labeled data graph. This is caused by the following problems: (i) the existing work mainly focuses on unweighted query graphs, while ignoring the impact of query constraints on query results. (ii) Excessive number of subgraph candidates or complex joins between nodes in the subgraph candidates reduce the query efficiency. To solve these problems, this paper proposes an intelligent solution. Firstly, an Isotype Structure Graph Compression (ISGC) strategy is proposed to compress similar nodes in a graph to reduce the size of the graph and avoid unnecessary matching. Then, an auxiliary data structure Supergraph Topology Feature Index (STFIndex) is designed to replace the storage of the original data graph and improve the efficiency of an online query. After that, a partition method based on Edge Label Step Value (ELSV) is proposed to partition the index logically. In addition, a novel Top-K interest subgraph query approach is proposed, which consists of the multidimensional filtering (MDF) strategy, upper bound value (UBV) (Size-c) matching, and the optimizational join (QJ) method to filter out as many false subgraph candidates as possible to achieve fast joins. We conduct experiments on real and synthetic datasets. Experimental results show that the average performance of our approach is 1.35 higher than that of the state-of-the-art approaches when the query graph is unweighted, and the average performance of our approach is 2.88 higher than that of the state-of-the-art approaches when the query graph is weighted. |
| format | Article |
| id | doaj-art-9dd047e7c9114efbba63c325546dd1d2 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-9dd047e7c9114efbba63c325546dd1d22025-02-03T06:12:31ZengWileyComplexity1076-27871099-05262021-01-01202110.1155/2021/92744299274429Supergraph Topology Feature Index for Personalized Interesting Subgraph Query in Large Labeled GraphsXiaohuan Shan0Haihai Li1Chunjie Jia2Dong Li3Baoyan Song4College of Information, Liaoning University, Shenyang 110036, ChinaCollege of Information, Liaoning University, Shenyang 110036, ChinaCollege of Information, Liaoning University, Shenyang 110036, ChinaCollege of Information, Liaoning University, Shenyang 110036, ChinaCollege of Information, Liaoning University, Shenyang 110036, ChinaInteresting subgraph query aims to find subgraphs that are isomorphic to the given query graph from a data graph and rank the subgraphs according to their interestingness scores. However, the existing subgraph query approaches are inefficient when dealing with large-scale labeled data graph. This is caused by the following problems: (i) the existing work mainly focuses on unweighted query graphs, while ignoring the impact of query constraints on query results. (ii) Excessive number of subgraph candidates or complex joins between nodes in the subgraph candidates reduce the query efficiency. To solve these problems, this paper proposes an intelligent solution. Firstly, an Isotype Structure Graph Compression (ISGC) strategy is proposed to compress similar nodes in a graph to reduce the size of the graph and avoid unnecessary matching. Then, an auxiliary data structure Supergraph Topology Feature Index (STFIndex) is designed to replace the storage of the original data graph and improve the efficiency of an online query. After that, a partition method based on Edge Label Step Value (ELSV) is proposed to partition the index logically. In addition, a novel Top-K interest subgraph query approach is proposed, which consists of the multidimensional filtering (MDF) strategy, upper bound value (UBV) (Size-c) matching, and the optimizational join (QJ) method to filter out as many false subgraph candidates as possible to achieve fast joins. We conduct experiments on real and synthetic datasets. Experimental results show that the average performance of our approach is 1.35 higher than that of the state-of-the-art approaches when the query graph is unweighted, and the average performance of our approach is 2.88 higher than that of the state-of-the-art approaches when the query graph is weighted.http://dx.doi.org/10.1155/2021/9274429 |
| spellingShingle | Xiaohuan Shan Haihai Li Chunjie Jia Dong Li Baoyan Song Supergraph Topology Feature Index for Personalized Interesting Subgraph Query in Large Labeled Graphs Complexity |
| title | Supergraph Topology Feature Index for Personalized Interesting Subgraph Query in Large Labeled Graphs |
| title_full | Supergraph Topology Feature Index for Personalized Interesting Subgraph Query in Large Labeled Graphs |
| title_fullStr | Supergraph Topology Feature Index for Personalized Interesting Subgraph Query in Large Labeled Graphs |
| title_full_unstemmed | Supergraph Topology Feature Index for Personalized Interesting Subgraph Query in Large Labeled Graphs |
| title_short | Supergraph Topology Feature Index for Personalized Interesting Subgraph Query in Large Labeled Graphs |
| title_sort | supergraph topology feature index for personalized interesting subgraph query in large labeled graphs |
| url | http://dx.doi.org/10.1155/2021/9274429 |
| work_keys_str_mv | AT xiaohuanshan supergraphtopologyfeatureindexforpersonalizedinterestingsubgraphqueryinlargelabeledgraphs AT haihaili supergraphtopologyfeatureindexforpersonalizedinterestingsubgraphqueryinlargelabeledgraphs AT chunjiejia supergraphtopologyfeatureindexforpersonalizedinterestingsubgraphqueryinlargelabeledgraphs AT dongli supergraphtopologyfeatureindexforpersonalizedinterestingsubgraphqueryinlargelabeledgraphs AT baoyansong supergraphtopologyfeatureindexforpersonalizedinterestingsubgraphqueryinlargelabeledgraphs |