Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs
This addresses the challenge of efficiently solving MaxIS in dynamic graphs for applications like network optimization, though it is incremental as it builds on existing learning-based methods.
The paper tackles the problem of finding Maximum Independent Sets in dynamic graphs with changing edges, achieving competitive approximation ratios and scalability, with solutions 1.05-1.18x larger than other learning methods on graphs up to 10,000 nodes.
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.