Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2501.05845 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929669939396608 |
|---|---|
| author | Loyola, Pablo Hasegawa, Kento Hoyos-Idobro, Andres Ono, Kazuo Suzumura, Toyotaro Hirate, Yu Yamaoka, Masanao |
| author_facet | Loyola, Pablo Hasegawa, Kento Hoyos-Idobro, Andres Ono, Kazuo Suzumura, Toyotaro Hirate, Yu Yamaoka, Masanao |
| contents | While Annealing Machines (AM) have shown increasing capabilities in solving complex combinatorial problems, positioning themselves as a more immediate alternative to the expected advances of future fully quantum solutions, there are still scaling limitations. In parallel, Graph Neural Networks (GNN) have been recently adapted to solve combinatorial problems, showing competitive results and potentially high scalability due to their distributed nature. We propose a merging approach that aims at retaining both the accuracy exhibited by AMs and the representational flexibility and scalability of GNNs. Our model considers a compression step, followed by a supervised interaction where partial solutions obtained from the AM are used to guide local GNNs from where node feature representations are obtained and combined to initialize an additional GNN-based solver that handles the original graph's target problem. Intuitively, the AM can solve the combinatorial problem indirectly by infusing its knowledge into the GNN. Experiments on canonical optimization problems show that the idea is feasible, effectively allowing the AM to solve size problems beyond its original limits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05845 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization Loyola, Pablo Hasegawa, Kento Hoyos-Idobro, Andres Ono, Kazuo Suzumura, Toyotaro Hirate, Yu Yamaoka, Masanao Artificial Intelligence Machine Learning While Annealing Machines (AM) have shown increasing capabilities in solving complex combinatorial problems, positioning themselves as a more immediate alternative to the expected advances of future fully quantum solutions, there are still scaling limitations. In parallel, Graph Neural Networks (GNN) have been recently adapted to solve combinatorial problems, showing competitive results and potentially high scalability due to their distributed nature. We propose a merging approach that aims at retaining both the accuracy exhibited by AMs and the representational flexibility and scalability of GNNs. Our model considers a compression step, followed by a supervised interaction where partial solutions obtained from the AM are used to guide local GNNs from where node feature representations are obtained and combined to initialize an additional GNN-based solver that handles the original graph's target problem. Intuitively, the AM can solve the combinatorial problem indirectly by infusing its knowledge into the GNN. Experiments on canonical optimization problems show that the idea is feasible, effectively allowing the AM to solve size problems beyond its original limits. |
| title | Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization |
| topic | Artificial Intelligence Machine Learning |
| url | https://arxiv.org/abs/2501.05845 |