Anya Chaturvedi

Devendra Parkar, Anya Chaturvedi, Joshua J. Daymude

We present the first unsupervised learning model for finding Maximum Independent Sets (MaxIS) in dynamic graphs where edges change over time. Our method combines structural learning from graph neural networks (GNNs) with a learned distributed update mechanism that, given an edge addition or deletion event, modifies nodes' internal memories and infers their MaxIS membership in a single, parallel step. We parameterize our model by the update mechanism's radius and investigate the resulting performance-runtime tradeoffs for various dynamic graph topologies. We evaluate our model against a mixed integer programming solver and the state-of-the-art learning-based methods for MaxIS on static graphs (ICML 2020; NeurIPS 2020, 2023). Across synthetic and empirical dynamic graphs of 50-1,000 nodes, our model achieves competitive approximation ratios with excellent scalability; on large graphs, it significantly outperforms the state-of-the-art learning methods in solution quality, runtime, and memory usage. When generalizing to graphs of 10,000 nodes (100x larger than the ones used for training), our model produces MaxIS solutions 1.05-1.18x larger than any other learning method, even while maintaining competitive runtimes.

Anya Chaturvedi, Joshua J. Daymude, Andréa W. Richa

Algorithms for mutual exclusion aim to isolate potentially concurrent accesses to the same shared resources. Motivated by distributed computing research on programmable matter and population protocols where interactions among entities are often assumed to be isolated, Daymude, Richa, and Scheideler (SAND`22) introduced a variant of the local mutual exclusion problem that applies to arbitrary dynamic networks: each node, on issuing a lock request, must acquire exclusive locks on itself and all its persistent neighbors, i.e., the neighbors that remain connected to it over the duration of the lock request. Assuming adversarial edge dynamics, semi-synchronous or asynchronous concurrency, and anonymous nodes communicating via message passing, their randomized algorithm achieves mutual exclusion (non-intersecting lock sets) and lockout freedom (eventual success with probability 1). However, they did not analyze their algorithm's runtime. In this paper, we prove that any node will successfully lock itself and its persistent neighbors within O$(nΔ^3)$ open rounds of its lock request in expectation, where $n$ is the number of nodes in the dynamic network, $Δ$ is the maximum degree of the dynamic network, rounds are normalized to the execution time of the ``slowest'' node, and ``closed'' rounds when some persistent neighbors are already locked by another node are ignored (i.e., only ``open" rounds are considered).