[4E3-GS-2] 機械学習：グラフ構造データ

[4E3-GS-2-03] 組合せ最適化におけるジャンピングとアテンションを用いたグラフニューラルネットワーク

〇グェンフウ バオロン¹、松井 藤五郎^2,3、原 謙介⁴ (1. 中部大学 大学院 工学研究科 情報工学専攻、2. 中部大学 生命健康科学部 臨床工学科、3. 中部大学 工学部 情報工学科、4. 株式会社セイノー情報サービス BRAIS推進室)

キーワード：グラフニューラルネットワーク、組合せ最適化、強化学習

本研究では、Graph Attention Networks （GAT）と強化学習を活用して組合せ最適化問題を解く手法に対して、Jump Knowledge Network (JKN) を導入することによってより効率的に探索する方法を提案する。従来手法は、隣接するノードの特徴量に重みをかけ、これに距離説明係数をかけてノードの特徴量を更新することでグラフの畳み込みを行う。これに対し、提案手法は、隣接するノードの特徴量に重みをかけた後に、距離説明係数だけではなく関係性を表すパラメータ行列をかけてノード特徴量を更新する。この関係性を表すパラメータ行列は、JKNを用いてすべての中間層から最終層へのジャンプ接続を適応的に選択するもので、MLPを用いて学習する。巡回セールスマン問題 (TSP) を用いた実験により、提案手法は小さいグラフに対しては従来手法よりも少し悪い結果となるが、大きなグラフに対しては効率よく短い経路を学習できることを示す。また、提案手法を物流における配送経路最適化問題に適用した結果を示す。