Efficient Subgraph Matching in Large Graph with Partitioning Scheme
Xiaofang Xie, Zhongwei Li, Haiwei Zhang · 2016
Recently, subgraph matching has been implemented in more and more domains, such as social network and semantic web. An approximated solution for subgraph matching named strong simulation has been put forward. Strong Simulation can preserve the topology of data graphs and find a bounded number of matches, but the complexity further holds a cubic-time, so it's yet intractable to deal with large graphs. To solve the problem, this paper focuses on a partition scheme to reduce the search space of subgraph matching algorithm. Firstly, we present a pruning method on data graph based on the connection relationships of nodes and edges in query graph. Secondly, we propose to use a multilevel partitioning algorithm when the subgraphs we get from former step are too large. Thirdly, we propose an algorithm for subgraph matching based on the partitioning scheme, which can preserve the topology of query graph and guarantee the correctness of results. Lastly, we experimentally prove the effectiveness and efficiency of this scheme, both using real-life data and synthetic data. It turns out that our method is quite efficient and the matching results are also satisfactory.