文献

J-GLOBAL ID：202102259408356257   整理番号：21A0220409

グラフ上の組合せ最適化問題に対するアルゴリズムへのGraph Neural Networksを用いた枝刈りの導入

Introduction of Pruning Using Graph Neural Networks to Algorithms for Combinatorial Optimization Problems on Graphs

著者 (5件)： 中野裕太 (北大 大学院情報科学院) ,  吉岡真治 (北大 大学院情報科学院) ,  吉岡真治 (北大 大学院情報科学研究院) ,  吉岡真治 (北大 国際連携研究教育局 ビッグデータ・サイバーセキュリティグローバルステーション) ,  吉岡真治 (北大 創成研究機構 化学反応創成研究拠点)
資料名： 人工知能学会人工知能基本問題研究会資料  (SIG-FPAI-C)
巻： 111th  ページ： 23-28  発行年： 2020年01月20日 
JST資料番号： X0830A  ISSN： 2436-4584  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ・グラフ上の組合せ最適化問題である部分集合に関する問題を例に,Graph Neural Networks(GNN)モデルによる予測値を利用した枝刈りを導入することで近似解を求める手法を提案。
・GNNモデルに枝刈りを導入する利点を述べ,最大クリーク問題と本稿で用いるGNNであるGraph Isomorphism Network(GIN)について説明。
・GINの学習と枝刈り方法の検証に用いるデータセットの生成方法について説明し,GINを最大クリーク問題の解の値を回帰するように学習させた結果を提示。
・提案した枝刈り方法の有効性を計算機実験によって検証した結果として,枝刈りで関数呼び出し回数が減少,解の近似精度が向上等について報告。

シソーラス用語： 組合せ最適化問題 ,  *ニューラルネットワーク ,  データ構造 ,  *グラフ ,  部分集合 ,  アルゴリズム ,  *最大化問題 ,  ベクトル ,  回帰モデル ,  *機械学習 ,  計算機シミュレーション
準シソーラス用語： *グラフニューラルネットワーク ,  グラフ構造 ,  *枝刈りアルゴリズム ,  ニューラルネットワークモデル ,  *最大クリーク問題 ,  特徴ベクトル ,  有効性確認 ,  検証実験 ,  計算機実験

分類 (2件)： 人工知能  (JE08000Z) ,  グラフ理論基礎  (IA02020S)

引用文献 (20件)：

• Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In KDD'19, pp. 2623-2631, 2019.
• Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d'horizon. In CoRR, 2018.
• P Erdös and A Rényi. On random graphs, i. Q Publicationes Math ematicae Debrecen, Vol. 6, p.290, 1959.
• Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010.
• Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems 32, pp. 15554-15566, 2019.

タイトルに関連する用語 (4件)： グラフ ,  組合せ最適化問題 ,  アルゴリズム ,  枝刈り