SAGA: State-Aware Graph Analytics for Combinatorial Optimization on Dynamic Graphs
TL;DR
This work presents SAGA, a high-performance framework for real-time combinatorial optimization on dynamic graphs that adopts a state-aware execution model in which each vertex maintains compact local state, enabling incremental and localized updates in response to graph changes.
Abstract
Combinatorial optimization problems on graphs, such as Maximal Independent Set (\(\mathcal {M}\)), Graph Coloring (\(\mathcal {GC}\)), and Maximal Matching (\(\mathcal {MM}\)), are computationally challenging and are significantly harder in dynamic settings where edges and vertices evolve continuously. Maintaining valid solutions under high-rate updates requires more than recomputation or static parallelism. We present SAGA, a high-performance framework for real-time combinatorial optimization on dynamic graphs. SAGA adopts a state-aware execution model in which each vertex maintains compact local state, enabling incremental and localized updates in response to graph changes. By coupling fine-grained task parallelism with data-parallel execution, SAGA minimizes communication overhead through state-aware partitioning and distributed state management. The SAGA compute engine maintains evolving solutions consistently across worker nodes while supporting low-latency queries. We evaluate SAGA on a distributed memory cluster against three state-of-the-art graph frameworks. On streaming instances of \(\mathcal {M}\), \(\mathcal {MM}\), and \(\mathcal {GC}\), SAGA achieves speedups of up to 11.8 × , 6.2 × , and 8.4 × , respectively, sustains up to 7.2M operations per second, and delivers over 10.8 × lower query latency compared to state-of-the-art graph analytics frameworks under concurrent update workloads.