[4E3-GS-2] Machine learning: graph structure

[4E3-GS-2-03] Jumping Graph Attention Neural Network for Combinatorial Optimization

〇NGUYEN HUU BAO LONG¹, Tohgoroh Matsui^2,3, Kensuke Hara⁴ (1. Department of Computer Science, Graduate School of Engineering, Chubu University, 2. Department of Clinical Engineering, College of Life and Health Sciences, Chubu University, 3. Department of Computer Science, College of Engineering, Chubu University, 4. BRAIS Promotion Office, Seino Information Service Co., Ltd.)

Keywords:GNN, TSP, Reinforcement Learning

For the traveling salesman problem (TSP), graph neural networks do not have the generalization ability to predict large TSP.
We propose a graph attention (GAT) neural network with a jumping knowledge network (JKN) structure and a node relationship parameter matrix.
We trained a model with small graphs TSP20-50 and evaluated with large graphs TSP100, TSP1000, and TSP10000, and so forth.
The experimental results show that our new method outperforms the existing GAT neural network method.
Besides we applied this method to actual data of a transportation company to evaluate the practicability.