論文の概要: Finding Hamiltonian cycles with graph neural networks

• arxiv url: http://arxiv.org/abs/2306.06523v1
• Date: Sat, 10 Jun 2023 21:18:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-13 18:23:33.561771
• Title: Finding Hamiltonian cycles with graph neural networks
• Title（参考訳）: グラフニューラルネットワークによるハミルトニアンサイクルの探索
• Authors: Filip Bosni\'c, Mile \v{S}iki\'c
• Abstract要約: 我々は、ErdHos-Rnyiのランダムグラフ上でハミルトン周期を予測するために、小さなメッセージパスグラフニューラルネットワークを訓練する。 このモデルは、より大きなグラフサイズによく一般化され、元の8倍の大きさのグラフでも妥当な性能を維持する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We train a small message-passing graph neural network to predict Hamiltonian cycles on Erd\H{o}s-R\'enyi random graphs in a critical regime. It outperforms existing hand-crafted heuristics after about 2.5 hours of training on a single GPU. Our findings encourage an alternative approach to solving computationally demanding (NP-hard) problems arising in practice. Instead of devising a heuristic by hand, one can train it end-to-end using a neural network. This has several advantages. Firstly, it is relatively quick and requires little problem-specific knowledge. Secondly, the network can adjust to the distribution of training samples, improving the performance on the most relevant problem instances. The model is trained using supervised learning on artificially created problem instances; this training procedure does not use an existing solver to produce the supervised signal. Finally, the model generalizes well to larger graph sizes and retains reasonable performance even on graphs eight times the original size.
• Abstract（参考訳）: 我々は、臨界状態におけるErd\H{o}s-R\enyiランダムグラフ上のハミルトン周期を予測するために、小さなメッセージパスグラフニューラルネットワークを訓練する。 1つのGPUで約2.5時間トレーニングした後、既存の手作りヒューリスティックよりも優れています。 本研究は,計算要求問題(np-hard)を実際に解くための代替手法を提案する。 手動でヒューリスティックを設計する代わりに、ニューラルネットワークを使ってエンドツーエンドにトレーニングすることができる。 これにはいくつかの利点がある。 まず、比較的速く、問題固有の知識はほとんど必要ありません。 第二に、ネットワークはトレーニングサンプルの分布に適応でき、最も関連する問題インスタンスのパフォーマンスを向上させることができる。 モデルは人工的に生成された問題インスタンス上で教師あり学習を用いて訓練されるが、この訓練手順では教師あり信号を生成するために既存の解決器を使用しない。 最後に、モデルはより大きなグラフサイズにうまく一般化し、元の8倍のグラフでも妥当なパフォーマンスを保ちます。

関連論文リスト

• Algebraic Representations for Faster Predictions in Convolutional Neural Networks [0.0]
  畳み込みニューラルネットワーク(CNN)は、コンピュータビジョンにおけるタスクのモデルとして一般的な選択肢である。 より簡単な勾配最適化問題を作成するために、スキップ接続を追加することもできる。 スキップ接続を持つ任意の複雑で訓練された線形CNNは単層モデルに単純化可能であることを示す。
  論文  参考訳（メタデータ） (2024-08-14T21:10:05Z)
• Unlearning Graph Classifiers with Limited Data Resources [39.29148804411811]
  制御されたデータ削除は、データに敏感なWebアプリケーションのための機械学習モデルの重要機能になりつつある。 グラフニューラルネットワーク(GNN)の効率的な機械学習を実現する方法はまだほとんど知られていない。 我々の主な貢献は GST に基づく非線形近似グラフアンラーニング法である。 第2の貢献は、提案した未学習機構の計算複雑性の理論解析である。 第3のコントリビューションは広範囲なシミュレーションの結果であり、削除要求毎のGNNの完全再トレーニングと比較して、新しいGSTベースのアプローチは平均10.38倍のスピードアップを提供する。
  論文  参考訳（メタデータ） (2022-11-06T20:46:50Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。 GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。 提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
  論文  参考訳（メタデータ） (2022-03-03T09:53:53Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  グラフ構造化データに対する半教師付き学習(SSL)は、多くのネットワークサイエンスアプリケーションに現れる。 グラフ上の学習を効率的に管理するために,近年,グラフニューラルネットワーク(GNN)の変種が開発されている。 実際に成功したにも拘わらず、既存の手法のほとんどは、不確実な結節属性を持つグラフを扱うことができない。 ノイズ測定によって得られたデータに関連する分布の不確実性によっても問題が発生する。 分散ロバストな学習フレームワークを開発し,摂動に対する定量的ロバスト性を示すモデルを訓練する。
  論文  参考訳（メタデータ） (2021-10-20T14:23:54Z)
• Training Graph Neural Networks by Graphon Estimation [2.5997274006052544]
  本稿では,基礎となるネットワークデータから得られたグラフトン推定値から再サンプリングすることで,グラフニューラルネットワークをトレーニングする。 我々のアプローチは競争力があり、多くの場合、他の過度にスムースなGNNトレーニング手法よりも優れています。
  論文  参考訳（メタデータ） (2021-09-04T19:21:48Z)
• Very Deep Graph Neural Networks Via Noise Regularisation [57.450532911995516]
  グラフニューラルネットワーク(GNN)は、入力グラフを介して学習されたメッセージパッシングを実行する。 最大100のメッセージパッシングステップを持つディープGNNをトレーニングし、いくつかの最先端の結果を得る。
  論文  参考訳（メタデータ） (2021-06-15T08:50:10Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。 これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-07T15:05:59Z)
• Scalable Graph Neural Network Training: The Case for Sampling [4.9201378771958675]
  グラフニューラルネットワーク(Graph Neural Networks、GNN)は、グラフ上で学習を行うディープニューラルネットワークアーキテクチャの新しい、ますます普及しているファミリです。 グラフデータの不規則性から、効率的にトレーニングすることは難しい。 文献には、全グラフとサンプルベースのトレーニングという2つの異なるアプローチが登場した。
  論文  参考訳（メタデータ） (2021-05-05T20:44:10Z)
• Binary Graph Neural Networks [69.51765073772226]
  グラフニューラルネットワーク(gnns)は、不規則データに対する表現学習のための強力で柔軟なフレームワークとして登場した。 本稿では,グラフニューラルネットワークのバイナライゼーションのための異なる戦略を提示し,評価する。 モデルの慎重な設計とトレーニングプロセスの制御によって、バイナリグラフニューラルネットワークは、挑戦的なベンチマークの精度において、適度なコストでトレーニングできることを示しています。
  論文  参考訳（メタデータ） (2020-12-31T18:48:58Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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