无需标注数据，实时更新图结构求解最大独立集。
Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs
- 用图神经网络+可学习的分布式更新机制，动态响应边增删事件。
- 在200-1000节点图上逼近比率达顶尖水平，速度提升1.91至6.70倍。
- 适用于大规模动态图推理，适合追求高效部署的优化场景。
我们提出首个针对动态图中最大独立集（MaxIS）问题的无监督学习模型。该方法结合图神经网络的结构学习能力与可学习的分布式更新机制，能够在边增删事件发生时，通过单步并行计算更新节点内部记忆，并推断其是否属于最大独立集。我们在包含200至1000个节点的动态图上，将本模型与混合整数规划求解器及多种静态图上的无监督和有监督学习模型进行对比。结果表明，本模型在逼近比率上达到当前最先进水平，且运行速度提升1.91至6.70倍。当推广到训练规模100倍以上的图时，本模型生成的解比所有其他无监督模型大1.00至1.18倍，但仍逊于最先进的有监督模型。这些结果表明，基于更新机制的新型无监督学习方法，能够有效利用时间信息，在动态组合优化中成为替代静态模型重算的可行方案。
原文摘要 · Abstract (English)
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. We evaluate our model against a mixed integer programming solver and a breadth of unsupervised and supervised learning models for combinatorial optimization on static graphs. Across dynamic graphs of 200-1,000 nodes, our model achieves approximation ratios that are competitive with the state-of-the-art models while running 1.91-6.70x faster. When generalizing to graphs with 100x more nodes than those used for training, our model produces MaxIS solutions 1.00-1.18x larger than all other unsupervised models, but is outperformed by the state-of-the-art supervised model. These results demonstrate that this novel, unsupervised, update-based learning approach to dynamic combinatorial optimization is a viable alternative to the naïve reapplication of analogous models for static graphs, leveraging temporal information to improve neural methods for combinatorial optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。