Scalable Distributed Frameworks for Temporal Analysis and Partitioning of Streaming Graphs

Abstract

The analysis of graph-structured data has become increasingly important as networks in various domains, including science, engineering, and business, grow in size, complexity, and dynamism. While static graph analysis has been well-explored, there is now a shift towards understanding how networks evolve over time due to changes in vertices and edges. These evolving networks are termed temporal graphs, and they require new methods to study their dynamic properties. However, there is limited research on distributed programming frameworks and scalable platforms for designing and executing incremental algorithms on such time-varying graphs, especially those updated at high rates in applications like social networks and financial systems. In response to the challenges of processing dynamic temporal graphs, we introduce TARIS, a distributed platform designed to execute time-respecting algorithms on large-scale, evolving networks. TARIS extends prior work on Windowed Interval-centric Computing Model (WICM) by enabling it to perform incremental computation, making it suitable for continuous graph updates. We formalize the properties of temporal algorithms and prove that our model of incremental computing over streaming updates is equivalent to recomputing from scratch. This helps reduce runtime by multiple orders of magnitude. TARIS uses optimized data structures to reduce memory access and enhance locality during graph updates. We also propose scheduling strategies to pipeline updates and computations, and streaming strategies to adapt the execution window to variable input rates. Related to this is the need to partitioning large evolving graphs whose edges stream in incrementally. Traditional partitioning methods prioritize balancing edge counts and minimizing vertex replication but overlook the community structure inherent in many graphs. We leverage prior work that proposed a novel optimization function to preserves local triangle counts within a partition, and formalize its benefits for conserving the graph’s community structure. We further evaluate its scalable distributed runtime design. Our results report significantly improved triangle count metrics while maintaining edge balance and vertex replication efficiency and achieving scalability.