Optimizing the Interval-centric Distributed Computing Model for Temporal Graph Algorithms

Abstract

Graphs with temporal characteristics are increasingly becoming prominent. Their vertices, edges and attributes are annotated with a lifespan, allowing one to add or remove vertices and edges. Such graphs can grow to millions of vertices, billions of edges, and have months or years of data. Time-dependent algorithms such as temporal reachability and shortest paths are designed over such materialised graphs. These algorithms find important use-cases in digital contact tracing, optimising transit routes, and analysing information diffusion over temporal graphs.

Interval-centric Computing Model (ICM) is a recent abstraction over temporal graphs, enabling intuitive development of temporal graph algorithms while ensuring efficient computation and communication. It uses a bulk-synchronous parallel model of execution with data-parallel computation on interval-vertices and message passing at superstep boundaries. To ease the design of temporal algorithms, ICM introduces a novel TimeWarp phase for temporally aligning messages and grouping them against vertex states. However, this warp operator is super-linear in time complexity with the number of messages received at a vertex. It also has additional overheads in the form of message replications. Further, in pipelining the computation and communication phases, ICM may create stale or redundant messages. This thesis primarily attempts to design techniques to mitigate these performance limitations of ICM, and also extends ICM toward incremental graph processing.

We propose three different techniques to accelerate the execution model of ICM: Local Warp Unrolling (LU), Deferred Message Scatter (DS) and Windowed ICM (WICM). LU unrolls the messages processed in the TimeWarp phase to reduce the time complexity of the warp operator. DS results in lazy scatter operations that reduce redundant calls to messaging. WICM partitions the temporal graph along the temporal dimension and processes the sub-interval graphs in parts, ensuring proper carryover of vertex states. While LU and DS apply locally to each vertex, WICM is applicable at the global interval graph level and can be coupled with the other two techniques.

While developing these techniques, we identify necessary constraints identifying the algorithms that can be modelled using the optimisations. Further, we also prove the equivalence of the new execution model to ICM's execution for a large class of temporal traversal algorithms. For WICM, not all temporal partitioning strategies give the same execution performance. Hence, we also develop heuristics that use statistics on the global graph topology with an analytical modelling of TimeWarp to determine the interval partitioning used with WICM.

We extensively evaluate these optimisations for six large temporal graphs with up to 133M vertices, 5.5B edges and 365 snapshots, and six graph algorithms on an 10-node commodity cluster. LU+DS reduce the runtime of ICM by an average of 56%; WICM reduces the runtime by 48% on average over native ICM, and combining these techniques offers an average reduction of 61%. We also conduct experiments to confirm the effectiveness of the heuristic partitioning technique. We also present preliminary results on extending the WICM model to operate over a graph that arrives incrementally, by batching the incoming updates and forming a window out of them to be executed using the WICM. This also has the benefit of reducing the memory footprint since the entire historic graph does not need to be retained in memory.