SAGA: State-Aware Graph Analytics for Combinatorial Optimization on Dynamic Graphs
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.