論文の概要: Brain-inspired Chaotic Graph Backpropagation for Large-scale Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2412.09860v1
• Date: Fri, 13 Dec 2024 05:00:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-16 15:04:29.611021
• Title: Brain-inspired Chaotic Graph Backpropagation for Large-scale Combinatorial Optimization
• Title（参考訳）: 大規模組合せ最適化のためのブレインインスパイアされたカオスグラフバックプロパゲーション
• Authors: Peng Tao, Kazuyuki Aihara, Luonan Chen,
• Abstract要約: 教師なし学習を伴うグラフニューラルネットワーク(GNN)は、効率的な時間複雑性で大規模最適化問題(COP)を解決することができる。 しかし、現在の主流のバックプロパゲーションベースのトレーニングアルゴリズムは、ローカルなミニマに陥りがちである。 カオスグラフバックプロパゲーション(CGBP)というカオス学習アルゴリズムを導入し,カオスだけではなく,高い効率でトレーニングを行う。
• 参考スコア（独自算出の注目度）: 3.97492577026225
• License:
• Abstract: Graph neural networks (GNNs) with unsupervised learning can solve large-scale combinatorial optimization problems (COPs) with efficient time complexity, making them versatile for various applications. However, since this method maps the combinatorial optimization problem to the training process of a graph neural network, and the current mainstream backpropagation-based training algorithms are prone to fall into local minima, the optimization performance is still inferior to the current state-of-the-art (SOTA) COP methods. To address this issue, inspired by possibly chaotic dynamics of real brain learning, we introduce a chaotic training algorithm, i.e. chaotic graph backpropagation (CGBP), which introduces a local loss function in GNN that makes the training process not only chaotic but also highly efficient. Different from existing methods, we show that the global ergodicity and pseudo-randomness of such chaotic dynamics enable CGBP to learn each optimal GNN effectively and globally, thus solving the COP efficiently. We have applied CGBP to solve various COPs, such as the maximum independent set, maximum cut, and graph coloring. Results on several large-scale benchmark datasets showcase that CGBP can outperform not only existing GNN algorithms but also SOTA methods. In addition to solving large-scale COPs, CGBP as a universal learning algorithm for GNNs, i.e. as a plug-in unit, can be easily integrated into any existing method for improving the performance.
• Abstract（参考訳）: 教師なし学習を伴うグラフニューラルネットワーク(GNN)は、効率的な時間複雑性で大規模な組合せ最適化問題(COP)を解くことができ、様々なアプリケーションに汎用性を持たせることができる。 しかし、この手法は組合せ最適化問題をグラフニューラルネットワークのトレーニングプロセスにマッピングし、現在の主流のバックプロパゲーションベースのトレーニングアルゴリズムは局所的なミニマに陥りやすいため、最適化性能は現在のSOTA(State-of-the-art)COP法よりも劣っている。 この問題を解決するために、実際の脳学習のカオス力学にインスパイアされたカオス学習アルゴリズム、すなわちカオスグラフバックプロパゲーション(CGBP)を導入する。 従来の手法と異なり、このようなカオス力学のグローバルなエルゴード性や擬似ランダム性は、CGBPが各最適GNNを効果的かつグローバルに学習し、COPを効率的に解けることを示す。 我々はCGBPを用いて、最大独立集合、最大カット、グラフカラー化などの様々なCOPを解く。 いくつかの大規模ベンチマークデータセットの結果は、CGBPが既存のGNNアルゴリズムだけでなくSOTAメソッドよりも優れていることを示している。 大規模COPの解決に加えて、プラグインユニットであるGNNの普遍的な学習アルゴリズムであるCGBPは、パフォーマンス向上のための既存の方法に容易に統合できる。

関連論文リスト

• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• Training Artificial Neural Networks by Coordinate Search Algorithm [0.20971479389679332]
  本稿では、ニューラルネットワークのトレーニングのための勾配自由座標探索(CS)アルゴリズムの効率的なバージョンを提案する。 提案アルゴリズムは、微分不可能なアクティベーション関数で使用することができ、多目的/マルチロス問題に適合する。 ANNの重みに対する最適値を求めることは、大規模な最適化問題である。
  論文  参考訳（メタデータ） (2024-02-20T01:47:25Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。 実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-10-05T02:58:29Z)
• Layer-wise training for self-supervised learning on graphs [0.0]
  大規模グラフ上でのグラフニューラルネットワーク(GNN)のエンドツーエンドトレーニングは、いくつかのメモリと計算上の課題を示す。 本稿では,GNN層を自己教師型で学習するアルゴリズムであるレイヤワイズ正規化グラフInfomaxを提案する。
  論文  参考訳（メタデータ） (2023-09-04T10:23:39Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である 本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。 提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
  論文  参考訳（メタデータ） (2022-10-14T03:43:05Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• Alternately Optimized Graph Neural Networks [33.98939289745346]
  グラフ上の半教師付き学習のための新しい最適化フレームワークを提案する。 提案手法は交互最適化アルゴリズムにより便利に解けるので,効率は大幅に向上する。
  論文  参考訳（メタデータ） (2022-06-08T01:50:08Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Gradient Centralization: A New Optimization Technique for Deep Neural Networks [74.935141515523]
  勾配集中(GC)は、勾配ベクトルをゼロ平均とする集中化によって、勾配を直接操作する。 GCは、制約された損失関数を持つ射影勾配降下法とみなすことができる。 GCは実装が非常に簡単で、1行のコードだけで既存のグラデーションベースのDNNに簡単に組み込める。
  論文  参考訳（メタデータ） (2020-04-03T10:25:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。