TeMotif: An Efficient Approach to Temporal Motif Matching
Yingjian Fu, Jianqiang Huang · 2024
Temporal graph mining has a wide range of applications in various domains, and temporal motif matching is the core processing method of temporal graph mining and can provide support for different downstream tasks. As the size of temporal graph data grows and the mining performance requirements increase, researchers are focus on performance improvement of temporal motif matching. Temporal motif matching is aims to discover motif that obey the specified structural and temporal order constraints in temporal graph. Despite previous efforts, temporal motif matching implements is suboptimize and cannot leverage code generation technology to automatically generate optimized execution code. To address these challenges, we propose a new method for temporal motif matching that can execute optimized algorithmic schedules for arbitrary motifs just like static graph mining system. We propose a new vertex-centric method for mining temporal motifs, which combines the generation of vertex schedules and code generation techniques to break through the limitations of previous generic temporal motif matching algorithms that are limited by the matching order according to the incremental size of the timestamps on the temporal edges of the temporal motif. In addition, we propose optimizations for the algorithm's multi-way join with storing hash-indexed temporal graph data structures additionally and redundantly. Evaluation on multiple query motifs show that, using proposed optimizations, our system in stand-alone 128-core outperforms the state-of-the-art algorithm implementation by 14×, on average.