Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs

A team of researchers has introduced the first unsupervised learning model specifically designed for solving the Maximum Independent Set (MaxIS) problem in dynamic graphs, where connections between nodes change over time. The novel approach, detailed in a paper accepted at IJCNN 2026, merges structural learning from Graph Neural Networks (GNNs) with a learned mechanism that updates node memories in a single, parallel step whenever an edge is added or deleted. This allows the model to infer optimal node selections for the MaxIS problem—a classic NP-hard combinatorial optimization challenge—without needing labeled training data or recomputing solutions from scratch for every graph change.

In rigorous testing against a mixed integer programming solver and other unsupervised and supervised models, the new method proved highly efficient. On dynamic graphs ranging from 200 to 1,000 nodes, it achieved approximation ratios competitive with the best existing models while running 1.91 to 6.70 times faster. Perhaps more impressively, when tested on graphs with 100 times more nodes than those seen during training, the unsupervised model produced MaxIS solutions that were 1.00 to 1.18 times larger than all other unsupervised baselines, demonstrating strong generalization. While a state-of-the-art supervised model still outperformed it in solution quality on these massive graphs, this work establishes a new, faster, and data-efficient paradigm for tackling dynamic optimization problems, moving beyond the naive reapplication of static graph models.