Periodic Subgraph Matching on Temporal Graphs

Periodicity is a frequent phenomenon on temporal graphs. Seeking periodic subgraph patterns is essential to understand the insights into the structure and behavior of the graph. Unfortunately, most previous studies for subgraph matching ignore the periodic feature of query patterns. In this paper, we study a new problem of periodic subgraph matching on temporal graphs, which finds all subgraphs in the temporal graph that not only match the given query graph but also appear periodically. To solve this problem, we propose a two-phase subgraph matching approach. In the offline phase, we develop an effective graph reduction technique to significantly prune the temporal graph. In the online phase, we propose a novel auxiliary data structure to further prune the search space and support periodic subgraph matching. We conduct extensive experiments on several real-life datasets and the results demonstrate the efficiency and effectiveness of our approach.