Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917411008020480 |
|---|---|
| author | Parkar, Devendra Chaturvedi, Anya Daymude, Joshua J. |
| author_facet | Parkar, Devendra Chaturvedi, Anya Daymude, Joshua J. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_13754 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs Parkar, Devendra Chaturvedi, Anya Daymude, Joshua J. Machine Learning Social and Information Networks 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. |
| title | Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs |
| topic | Machine Learning Social and Information Networks |
| url | https://arxiv.org/abs/2505.13754 |