Optimizing the interval-centric distributed computing model for temporal graph algorithms

Temporal graphs assign lifespans to their vertices, edges and attributes. Large temporal graphs are common for finding the shortest paths in transit networks and contact tracing for COVID-19. Graph programming abstractions like Interval-centric Computing Model (ICM) extend Google's Pregel model to intuitively compose and execute time-dependent graph algorithms in a distributed environment. However, the benefits of easier algorithmic design in ICM are offset by performance bottlenecks in its TimeWarp shuffle and messaging phases. Here, we design several optimizations to ICM to reduce these overheads. We propose local optimizations within a vertex execution by unrolling messages before TimeWarp (LU), and deferring messaging till all local computations complete (DS). We also temporally partition the interval graph into windows (WICM) to flatten the execution load. We offer a proof of equivalence between ICM and these techniques. Our detailed empirical evaluation for six real-world graphs with up to 133M vertices, 5.5B edges and 365 time-points, for six temporal traversal algorithms executing on a commodity cluster with 8 nodes, shows that LU, DS and WICM together significantly reduce the average algorithm runtime by ≈ 61% (≈ 15 mins) over ICM, and reduce message communication by ≈ 38%(≈ 3.2B) on average.