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.