エッジ重み付きグラフ畳込みニューラルネットワークを用いた最小コストマルチカットを解くための学習【JST・京大機械翻訳】

Jung Steffen; Keuper Margret

プレプリント

J-GLOBAL ID：202202205902871514 整理番号：22P0324863

エッジ重み付きグラフ畳込みニューラルネットワークを用いた最小コストマルチカットを解くための学習【JST・京大機械翻訳】

Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2022年04月04日プレプリントサーバーでの情報更新日： 2022年04月04日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

最小コストマルチカット問題は,分割の全コストを最小化するように,実数値エッジ加重グラフを分割するNP-ハード/APX-ハードコンビナトリアル最適化問題である。グラフ畳込みニューラルネットワーク(GNN)はコンビナトリアル最適化の文脈で有望であることが証明されているが,それらの大部分は正値エッジ重み,即ち,マルチカット問題の性質に従わないか,あるいはテストされた。そこで筆者らは,実数値エッジコストの効率的符号化を容易にするために,グラフ畳込みネットワーク,署名グラフ畳込みネットワークおよびグラフ同形ネットワークを含む様々なGNNアーキテクチャを適応させた。さらに,スケーラブルな方法で実行可能なマルチカット解を学習できる損失関数として多項式プログラムにマルチカットILP制約の再定式化を採用した。したがって,エンドツーエンド訓練可能マルチカットに向けた最初のアプローチを提供した。著者らの知見は,GNNアプローチが,LPソルバーおよび最適化発見的方法と比較して,特に大きなインスタンスを考慮するとき,低い計算時間を提供し,大幅に改善されたスケーラビリティを提供しながら,実践において良好な解決策を製造できるというサポートをサポートした。【JST・京大機械翻訳】

, , , , , , , , , , , ,
, , 【Automatic Indexing@JST】

グラフ理論基礎

, , ,

前のページに戻る