AI RESEARCH
Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs
arXiv CS.LG
•
ArXi:2505.13754v3 Announce Type: replace We present the first unsupervised learning model for Maximum-Independent-Set (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.