TeGraph: A Novel General-Purpose Temporal Graph Computing Engine

Temporal graphs attach time information to edges and are commonly used for implementing time-critical applications that can not be effectively processed by traditional static and dynamic graph processing engines. State-of-the-art solutions that target temporal path problems remain ad-hoc and often suboptimal. A unified and high-performance solution that could efficiently process general temporal path problems via a universal optimization strategy and relieve practitioners from heavy optimization efforts is in urgent demand. In this paper, we make two key observations: (1) temporal path problems can be described as topological-optimum problems and solved by a universal single scan execution model; and (2) data redundancy commonly occurs in the native format of the transformed temporal graphs, which is unnecessary for information propagation and can be eliminated for better memory utilization and execution efficiency. Based on these core insights, we propose TEGRAPH, the first general-purpose temporal graph computing engine to provide a unified optimization strategy and execution model for general temporal path problems and their applications. TEGRAPH not only presents temporal information-aware graph representation that naturally fits temporal graphs but also offers general systemlevel supports such as out-of-core execution. Extensive evaluation reveals that TEGRAPH can achieve significant speedups over the state-of-the-art designs with up to two orders of magnitude (241×) with the throughput of two hundred million edges per second.

Index Terms-Graph algorithm, temporal graphs.

Temporal graphs, which label the edges with time intervals, can provide additional capabilities to describe time-critical applications that can not be otherwise captured by traditional static graph computing engines [1]-[14]. In reality, many important applications are based on temporal graphs [15]-[31] such as aviation networks [32], e-commerce [33], and realtime epidemiology analysis (e.g., Influenza and COVID-19 outbreaks [34]). Social media graphs [35], [36] are also with a period of friending as the edge labels. Additionally, in the era of deep learning-based big data analytics, effectively extracting essential information from large and complex temporal graphs becomes increasingly critical for everyday life [33], [36]-[39].