論文の概要: Learning Graph Algorithms With Recurrent Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2212.04934v1
- Date: Fri, 9 Dec 2022 15:42:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-12 14:27:31.120626
- Title: Learning Graph Algorithms With Recurrent Graph Neural Networks
- Title（参考訳）: リカレントグラフニューラルネットワークを用いたグラフアルゴリズムの学習
- Authors: Florian Gr\"otschla, Jo\"el Mathys, Roger Wattenhofer
- Abstract要約: 我々は、単純なグラフ問題を末尾から末尾まで小さなグラフで学習し、より大きなインスタンスに拡張する、反復的なアーキテクチャ設計に重点を置いている。
We use (i) skip connection, (ii) state regularization, and (iii) edge convolutions to guide GNNs to extrapolation。
- 参考スコア（独自算出の注目度）: 8.873449722727026
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Classical graph algorithms work well for combinatorial problems that can be
thoroughly formalized and abstracted. Once the algorithm is derived, it
generalizes to instances of any size. However, developing an algorithm that
handles complex structures and interactions in the real world can be
challenging. Rather than specifying the algorithm, we can try to learn it from
the graph-structured data. Graph Neural Networks (GNNs) are inherently capable
of working on graph structures; however, they struggle to generalize well, and
learning on larger instances is challenging. In order to scale, we focus on a
recurrent architecture design that can learn simple graph problems end to end
on smaller graphs and then extrapolate to larger instances. As our main
contribution, we identify three essential techniques for recurrent GNNs to
scale. By using (i) skip connections, (ii) state regularization, and (iii) edge
convolutions, we can guide GNNs toward extrapolation. This allows us to train
on small graphs and apply the same model to much larger graphs during
inference. Moreover, we empirically validate the extrapolation capabilities of
our GNNs on algorithmic datasets.
- Abstract（参考訳）: 古典グラフアルゴリズムは、完全な形式化と抽象化が可能な組合せ問題に対してうまく機能する。
アルゴリズムが導出されると、任意のサイズのインスタンスに一般化される。
しかし、現実世界の複雑な構造や相互作用を扱うアルゴリズムを開発することは困難である。
アルゴリズムを指定するのではなく、グラフ構造化データから学習することができる。
グラフニューラルネットワーク(GNN)は本質的にグラフ構造に取り組む能力があるが、それらをうまく一般化するのに苦労し、より大きなインスタンスで学ぶことは難しい。
スケールするために私たちは、より小さなグラフに端から端まで単純なグラフの問題を学習し、さらに大きなインスタンスに外挿できる、リカレントなアーキテクチャ設計にフォーカスしています。
本研究の主な貢献として,GNNのスケールアップに要する3つのテクニックを同定した。
利用することで
(i)接続をスキップする。
(ii)状態の正規化、及び
(三)エッジ畳み込みにより、GNNを外挿に導くことができる。
これにより、小さなグラフをトレーニングし、推論中に同じモデルをもっと大きなグラフに適用することができます。
さらに、アルゴリズムデータセット上でGNNの補間能力を実証的に検証する。
関連論文リスト
- Learning on Large Graphs using Intersecting Communities [13.053266613831447]
MPNNは、各ノードの隣人からのメッセージを集約することで、入力グラフ内の各ノードの表現を反復的に更新する。
MPNNは、あまりスパースではないため、すぐに大きなグラフの禁止になるかもしれない。
本稿では,入力グラフを交差するコミュニティグラフ (ICG) として近似することを提案する。
論文 参考訳（メタデータ） (2024-05-31T09:26:26Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳（メタデータ） (2022-10-27T16:00:45Z) - FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。
本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。
提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-10-21T07:58:03Z) - Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。
固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。
GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
論文 参考訳（メタデータ） (2022-05-19T14:08:15Z) - Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。
これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-07T15:05:59Z) - Towards Scale-Invariant Graph-related Problem Solving by Iterative
Homogeneous Graph Neural Networks [39.370875358317946]
現在のグラフニューラルネットワーク(GNN)は、多くのグラフ解析問題を解く際に、スケール(グラフサイズ、グラフ径、エッジウェイトなど)に関する一般化性に欠ける。
まず,グラフサイズに対する共通グラフ理論アルゴリズムの反復回数の依存性に着想を得て,GNNにおけるメッセージパッシングプロセスの終了を,進捗に応じて順応的に学習する。
第二に、多くのグラフ理論アルゴリズムがグラフの重みに関して均一であるという事実に着想を得て、一般のGを変換するために、普遍的同次関数近似器である同次変換層を導入する。
論文 参考訳（メタデータ） (2020-10-26T12:57:28Z) - Graph Contrastive Learning with Augmentations [109.23158429991298]
グラフデータの教師なし表現を学習するためのグラフコントラスト学習(GraphCL)フレームワークを提案する。
我々のフレームワークは、最先端の手法と比較して、類似またはより良い一般化可能性、転送可能性、堅牢性のグラフ表現を作成できることを示す。
論文 参考訳（メタデータ） (2020-10-22T20:13:43Z) - From Local Structures to Size Generalization in Graph Neural Networks [53.3202754533658]
グラフニューラルネットワーク(GNN)は、さまざまなサイズのグラフを処理することができる。
特に小さなグラフから大きなグラフまで、サイズをまたいで一般化する能力は、まだよく理解されていない。
論文 参考訳（メタデータ） (2020-10-17T19:36:54Z) - Lifelong Graph Learning [6.282881904019272]
連続グラフ学習問題を正規グラフ学習問題に変換することにより、グラフ学習と生涯学習を橋渡しする。
機能グラフネットワーク(FGN)は,ウェアラブルデバイスを用いた生涯の人間行動認識と特徴マッチングという2つのアプリケーションにおいて,優れた性能を発揮することを示す。
論文 参考訳（メタデータ） (2020-09-01T18:21:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。