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.

Centrality measures quantify the importance of vertices in a network and are widely used in domains such as social network analysis and epidemiology. Given the size and evolving nature of real-world networks, there is growing interest in parallel algorithms that efficiently update centrality values in dynamic settings. In this paper, we study the update of the percolation centrality measure in a dynamic graph. We present parallel algorithms to handle changes to the percolation value of a batch of vertices and the addition and deletion of a batch of edges to the graph. We leverage the graphs’ structural properties to improve our algorithms’ performance. To our knowledge, we are the first to propose such algorithms for percolation centrality. We implement and benchmark our algorithms on a server with two AMD EPYC CPUs and an Nvidia A100 GPU. Our experiments on a collection of real-world graphs indicate that our algorithms achieve speedups of 8.79 × and 2.82 × on CPU and GPU, respectively, for edge updates, and 309.44 × and 18.71 × on CPU and GPU, respectively, for vertex percolation updates over state-of-the-art static algorithms for a batch of 10000 edges and vertices, respectively.

In network analysis, Katz centrality is widely used to measure node influence by considering both direct and indirect connections weighted by path length. While numerous studies have examined Katz centrality for static graphs, relatively few address the challenges posed by dynamic graphs. Katz centrality can utilize perturbation theory by exploiting iterative solvers to obtain updated Katz scores in dynamic graphs. However, these methods are limited to handling only small changes, as they generally accept only minor structural updates limited to only edge insertions or removals. Additionally, due to an iterative approach, the solutions can be sequential and provide approximate answers, which may reduce accuracy when the graph undergoes frequent updates over time. This paper introduces a novel algorithm that significantly improves the efficiency of Katz centrality calculations in dynamic graphs. After each update, we identify affected nodes using a Breadth First Search (BFS) frontier and then apply dynamic programming, which allows for both edge/node insertions and deletions. Our parallel implementation on a shared memory platform achieves a 5.29 x speedup on an average over the static version. Our algorithm can update a batch of 1 million edges on an existing graph of 1 billion edges in 24.73 seconds.

Finding the Maximal Independent Set (MIS) in a graph is a well-known problem with applications in resource allocation, load balancing, and routing optimization. This task is particularly challenging for large graphs as it requires multiple iterations over the entire set of vertices. Recently, there has been significant interest in developing techniques to maintain the MIS dynamically in evolving graphs rather than re-computing from scratch. In this paper, we propose new data structures and techniques for computing MIS in parallel on dynamic graphs. We specifically propose techniques to handle insertions and deletions in a batched setting. We conducted detailed experiments on shared memory multicore CPUs using graphs ranging from 50 million to ${1. 2}$ billion edges. Our results show that using our technique for insertions and deletions can provide up to 15.64x and 10.57x speedups on average over comparable baselines. Additionally, the final MIS we produce varies by only about ${0. 1 8 \%}$ in cardinality compared to the existing state-of-the-art.