Seonho Lee  Kunsoo Park

10.5626/JOK.2024.51.2.103

subgraph matching diversity coverage backtracking

Subgraph matching is a core and important problem in graph analysis. The subgraph matching problem is to find all embeddings of the query graph in the data graph. However, the output results from previously proposed algorithms often overlap with each other, and thus interesting results are often missed. For this purpose, the diversified top-k subgraph querying problem is proposed. The diversified top-k subgraph querying problem is to find k embeddings that have the highest coverage among embeddings of the query graph in the data graph. In this paper, we present an algorithm for the diversified top-k subgraph querying problem and demonstrate that it finds diversified top-k results efficiently compared to existing algorithms.