An Approximation Method for Querying Similar Large Graphs
Zhou Huang, Feng Zhou · 2022 IEEE International Conference on Big Data (Big Data) · 2022
Searching similar graphs in graph databases for a query graph has attracted extensive attention recently. However, existing works face many challenges in the context of big data. For example, the time and space complexity of completing queries in multiple large graphs is too high to be done on a single machine. This undoubtedly increases the hardware cost of large graph similarity calculation. Moreover, calculating accurate graph similarity is an NP-hard problem. To solve these problems, in this paper, we propose a novel approximation method for searching similar graphs among multiple large graphs for a query graph. Firstly, we propose a graph database tensor (GDT) to unify the representation of various graphs and reduce space complexity. Secondly, we propose an approximation method through several sampling operations on the GDT to obtain a limited set of graphs that are with a high probability similar to the query graph, which avoids a lot of futile similarity calculations and significantly reduces time complexity. Thirdly, we design a fast method to more precisely estimate similarities between the query graph with the ones in the similar graph set obtained. The results showed our method is efficient and feasible.