TEA: A General-Purpose Temporal Graph Random Walk Engine

Many real-world graphs are temporal in nature, where the temporal information indicates when a particular edge is changed (e.g., edge insertion and deletion). Performing random walks on such temporal graphs is of paramount value. The state-of-the-art sampling strategies are tailored for conventional static graphs and thus cannot effectively tackle the dynamic nature of temporal graphs due to several significant efficiency challenges, i.e., high sampling complexity, gigantic index space, and poor programmability.

In this paper, we present TEA, the first highly-efficient general-purpose TEmporal grAph random walk engine. At its core, TEA introduces a new hybrid sampling approach that combines two Monte Carlo sampling methods together to drastically reduce space complexity and achieve high sampling speed. TEA further employs a series of algorithmic and system-level optimizations to remarkably improve the sampling efficiency, as well as provide streaming graph support. Finally, we introduce a temporal-centric programming model to ease the implementation of various random walk algorithms on temporal graphs. Experimental results demonstrate that TEA can achieve up to 3 orders of magnitude speedups over the state-of-the-art random walk engines on large temporal graphs.