CSM-TopK: Continuous Subgraph Matching with TopK Density Constraints

Continuous subgraph matching (CSM) is an important problem of graph analysis over dynamic graphs. Given a query graph, existing CSM efforts return numerous matches, which may overwhelm analysts. In addition, they do not consider weighted graphs that are ubiquitous in many real-world applications, such as payment networks where each edge has a weight to represent a transaction amount. Over these weighted graphs, matches of the given query graph have diverse priorities for analysis if they own different densities. In this paper, we propose a new problem of CSM-TopK to compute
$k$
matches of a given query graph with the highest densities over a dynamic weighted graph and prove it to be NP-hard. To compute the CSM-TopK effectively, we first define a star-structured subquery, based on which we design two lightweight indexes, called global and local MWstar, respectively. In particular, the global MWstar maintains the maximum weights of all partial matches of each specific star-structured subquery. Differently, the local MW star is designed based on the corresponding maximum weight distribution for each specific data vertex. Additionally, a query-dependent graph compacted technique is introduced to further improve the performance on both time and space. Extensive experiments over real-world datasets show that our MW star- based approaches surpass the comparative ones by at least two orders of magnitude.