論文の概要: Learning from A Single Graph is All You Need for Near-Shortest Path
Routing in Wireless Networks
- arxiv url: http://arxiv.org/abs/2308.09829v1
- Date: Fri, 18 Aug 2023 21:35:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-22 19:51:39.501118
- Title: Learning from A Single Graph is All You Need for Near-Shortest Path
Routing in Wireless Networks
- Title（参考訳）: シングルグラフからの学習は、無線ネットワークにおける近距離経路ルーティングに必要なもの
- Authors: Yung-Fu Chen, Sen Lin, Anish Arora
- Abstract要約: 無線ネットワークの標準モデルにおいて,任意のランダムグラフに一般化しながら,単一のグラフから得られるデータサンプルを数個だけ必要とするような局所ルーティングポリシーの学習アルゴリズムを提案する。
そこで我々はディープニューラルネットワーク(DNN)を訓練し、局所的なルーティングポリシーを効率的に学習することで、全ペアに近い経路問題を解決する。
- 参考スコア（独自算出の注目度）: 8.22181379329857
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a learning algorithm for local routing policies that needs only a
few data samples obtained from a single graph while generalizing to all random
graphs in a standard model of wireless networks. We thus solve the all-pairs
near-shortest path problem by training deep neural networks (DNNs) that
efficiently and scalably learn routing policies that are local, i.e., they only
consider node states and the states of neighboring nodes. Remarkably, one of
these DNNs we train learns a policy that exactly matches the performance of
greedy forwarding; another generally outperforms greedy forwarding. Our
algorithm design exploits network domain knowledge in several ways: First, in
the selection of input features and, second, in the selection of a ``seed
graph'' and subsamples from its shortest paths. The leverage of domain
knowledge provides theoretical explainability of why the seed graph and node
subsampling suffice for learning that is efficient, scalable, and
generalizable. Simulation-based results on uniform random graphs with diverse
sizes and densities empirically corroborate that using samples generated from a
few routing paths in a modest-sized seed graph quickly learns a model that is
generalizable across (almost) all random graphs in the wireless network model.
- Abstract（参考訳）: 無線ネットワークの標準モデルにおいて,任意のランダムグラフに一般化しながら,単一のグラフから得られたデータサンプルを数個だけ必要な局所ルーティングポリシーの学習アルゴリズムを提案する。
そこで本研究では,ディープニューラルネットワーク(dnn)を訓練し,局所的なルーティングポリシ,すなわちノード状態と隣接ノードの状態のみを効率的に学習することで,最短経路問題を解く。
注目すべきは、私たちがトレーニングしているこれらのDNNの1つは、欲張りの転送のパフォーマンスと正確に一致するポリシーを学びます。
第1に,入力特徴の選択,第2に ``seed graph'' の選択,第2に,最短経路からサブサンプリングを行う。
ドメイン知識の活用は、なぜシードグラフとノードサブサンプリングが効率的でスケーラブルで一般化可能な学習に十分かを理論的に説明できる。
様々な大きさと密度のランダムグラフに関するシミュレーションに基づく結果は、モデストサイズのシードグラフにおけるいくつかのルーティングパスから生成されたサンプルを用いて、無線ネットワークモデル内の(ほぼ)ランダムグラフ全体にわたって一般化可能なモデルを素早く学習する、経験的に相関する。
関連論文リスト
- A Local Graph Limits Perspective on Sampling-Based GNNs [7.601210044390688]
本稿では,グラフニューラルネットワーク(GNN)を大規模入力グラフ上で学習するための理論的枠組みを提案する。
大規模な入力グラフの小さなサンプルを用いてサンプリングベースGNNのトレーニングから得られたパラメータが、グラフ全体において同じアーキテクチャをトレーニングした結果の$epsilon$近傍にあることを証明した。
論文 参考訳（メタデータ） (2023-10-17T02:58:49Z) - GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks [2.4175455407547015]
グラフニューラルネットワークは、隣人からの情報を集約することでノードを表現することを学ぶ。
いくつかの既存手法では、ノードの小さなサブセットをサンプリングし、GNNをもっと大きなグラフにスケールすることで、この問題に対処している。
本稿では,GNNのトレーニングに不可欠なノードの集合を識別する適応サンプリング手法であるGRAPESを紹介する。
論文 参考訳（メタデータ） (2023-10-05T09:08:47Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - A Robust Stacking Framework for Training Deep Graph Models with
Multifaceted Node Features [61.92791503017341]
数値ノード特徴とグラフ構造を入力とするグラフニューラルネットワーク(GNN)は,グラフデータを用いた各種教師付き学習タスクにおいて,優れた性能を示した。
IID(non-graph)データをGNNに簡単に組み込むことはできない。
本稿では、グラフ認識の伝播をIDデータに意図した任意のモデルで融合するロバストな積み重ねフレームワークを提案する。
論文 参考訳（メタデータ） (2022-06-16T22:46:33Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。
GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。
提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
論文 参考訳（メタデータ） (2022-03-03T09:53:53Z) - RaWaNet: Enriching Graph Neural Network Input via Random Walks on Graphs [0.0]
グラフニューラルネットワーク(GNN)の人気が高まっており、グラフで表されるデータに対して非常に有望な結果を示している。
本稿では,3つの選択された長さに基づいて,グラフのランダムなウォークデータ処理を提案する。すなわち,グラフ上の局所的および大域的ダイナミクスを捉えるために,長さ1,2の(正規)ウォークと長さ0,1$の分節ウォークを提案する。
本手法は, 処理ノードの特徴をネットワークに渡すことによって, 様々な分子データセット上で検証し, 分類および回帰処理を行う。
論文 参考訳（メタデータ） (2021-09-15T20:04:01Z) - Scalable Graph Neural Network Training: The Case for Sampling [4.9201378771958675]
グラフニューラルネットワーク(Graph Neural Networks、GNN)は、グラフ上で学習を行うディープニューラルネットワークアーキテクチャの新しい、ますます普及しているファミリです。
グラフデータの不規則性から、効率的にトレーニングすることは難しい。
文献には、全グラフとサンプルベースのトレーニングという2つの異なるアプローチが登場した。
論文 参考訳（メタデータ） (2021-05-05T20:44:10Z) - Learning Graph Neural Networks with Positive and Unlabeled Nodes [34.903471348798725]
グラフニューラルネットワーク(GNN)は、グラフのノード分類など、トランスダクティブな学習タスクのための重要なツールです。
ほとんどのGNNモデルは、各ラウンドで短い距離から情報を集約し、グラフで長距離関係をキャプチャできません。
本論文では,これらの制限を克服するために,新しいグラフニューラルネットワークフレームワーク,LSDAN(Long-Short distance aggregation Network)を提案する。
論文 参考訳（メタデータ） (2021-03-08T11:43:37Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z) - Analyzing Neural Networks Based on Random Graphs [77.34726150561087]
様々なタイプのランダムグラフに対応するアーキテクチャを用いて,ニューラルネットワークの大規模評価を行う。
古典的な数値グラフ不変量は、それ自体が最良のネットワークを選び出すことができない。
また、主に短距離接続を持つネットワークは、多くの長距離接続が可能なネットワークよりも性能が良いことも見出した。
論文 参考訳（メタデータ） (2020-02-19T11:04:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。