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.

Property graphs are a common form of linked data, with path queries used to traverse and explore them for enterprise transactions and mining. Temporal property graphs are a recent variant where time is a first-class entity to be queried over, and their properties and structure vary over time. These are seen in social, telecom and transit networks. However, current graph databases and query engines have limited support for temporal relations among graph entities, no support for time-varying entities and/or do not scale on distributed resources. We address this gap by extending a linear path query model over property graphs to include intuitive temporal predicates that operate over temporal graphs. We design a distributed execution model for these temporal path queries using the interval-centric computing model, and develop a novel cost model to select an efficient execution plan from several. We perform detailed experiments of our $\mathcal{G}ranite$ distributed query engine using temporal property graphs as large as 52M vertices, 218M edges and 118M properties, and an 800-query workload, derived from the LDBC benchmark. We offer sub-second query latencies in most cases, which is 149×-1140× faster compared to industry-leading Neo4J shared- memory graph database and the JanusGraph/Spark distributed graph query engine. Further, our cost model selects a query plan that is within 10% of the optimal execution time in 90% of the cases. We also scale well, and complete 100% of the queries for all graphs, compared to only 32-92% by baseline systems.