10万変数以上の問題に対して計算時間を最大20%短縮、精度を最大35％向上

　日立と楽天グループの研究開発機関である楽天技術研究所(以下、楽天)は、大規模な組合せ最適化問題を高速かつ高精度に解く新たな手法を開発しました。本手法は、日立のCMOSアニーリング技術*1と、楽天のグラフニューラルネットワーク(GNN)技術*2を組み合わせることで、10万変数を超える大規模な問題に対して、GNN技術単体の場合と比較して計算時間を最大20%短縮し、計算精度を最大35%向上させることが可能です。これにより、配送計画の最適化など、多くの分野での応用が期待されます 。

　物流、金融などの多くの分野において、大規模な組合せ最適化問題を効率的に解決することは、サービスの質の向上やコスト削減に繋がることから、企業の競争力を高めるために重要となっています。今回、日立と楽天は、それぞれの技術を組み合わせることで、新たな解決手法を開発しました。
　具体的には、まずメインGNNを圧縮してサイズの異なる複数のサブGNNを順に作成し、それぞれの解をCMOSアニーリング技術で求めます。次に、得られた解を教師データとしてサブGNNに機械学習させ、その結果をメインGNNにフィードバックすることで、計算時間の短縮と計算精度の向上を可能にします(図1)。
　本手法を、ソーシャルネットワークの分析などに応用が期待される最大独立集合問題*3や最大カット問題*4などに適用して検証した結果、GNN技術単体の場合*5と比較して、10万変数以上の問題に対して、計算時間を最大20%短縮し、計算精度を最大35%向上させることを確認しました。

　今後、日立は、本技術を材料開発やレコメンデーションシステム、電力需給関連事業などの分野での応用をめざし、大学やアカデミアを含めたパートナーとの技術連携を進めていきます。
なお、本成果の一部は、2024年12月15日にバンクーバーで開催されたML with New Compute Paradigms (MLNCP) at NeurIPS 2024で発表しました*6。

図1 大規模な組合せ最適化問題を高速かつ高精度に解く新たな手法の概要

*1 CMOSアニーリング技術: イジングモデルの動作を半導体のCMOS回路で擬似的に再現する。この技術を用いたコンピュー　　　タは、組合せ最適化問題の実用解を室温下で、効率良く求めることができる。
*2 グラフニューラルネットワーク(GNN)技術: ネットワーク(グラフ)構造のデータを扱うことができるニューラルネットワークの一種。従来のニューラルネットワークが主に画像やテキストといったデータを対象としているのに対し、GNNはグラフ構造を学習するための機械学習モデル。数百万～数億の頂点と辺を含む問題を取り扱えるスケーラビリティを有する。
*3 最大独立集合問題: グラフ中で互いに隣接しない頂点をできるだけ多く選ぶ問題。
*4 最大カット問題: グラフを2つの頂点集合に別ける際にできるだけ多く辺をカット(切断)する問題。
*5 CMOSアニーリングの解を用いずにサブGNNの教師なし学習を実行し、その結果をメインGNNにフィードバックする。
*6 “Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization” (https://arxiv.org/abs/2501.05845)

■関連情報
・Rakuten and Hitachi Collaborate at NeurIPS 2024 Workshop | News | Rakuten Institute of Technology | 楽天技術研究所
・楽天技術研究所　公式ウェブサイト
・日立の研究開発ウェブサイト

■照会先
株式会社日立製作所 研究開発グループ
問い合わせフォームへ