論文の概要: Flood and Echo: Algorithmic Alignment of GNNs with Distributed Computing
- arxiv url: http://arxiv.org/abs/2310.06970v2
- Date: Thu, 12 Oct 2023 14:21:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-13 11:22:08.115492
- Title: Flood and Echo: Algorithmic Alignment of GNNs with Distributed Computing
- Title(参考訳): Flood and Echo: 分散コンピューティングによるGNNのアルゴリズムアライメント
- Authors: Jo\"el Mathys, Florian Gr\"otschla, Kalyan Varma Nadimpalli, Roger
Wattenhofer
- Abstract要約: グラフニューラルネットワークは、学習アルゴリズムに自然に適合する。
抽象的だが汎用的なグラフ構造を通じてタスクを直接表現し、異なるサイズの入力を処理することができる。
これにより、アルゴリズムの最も重要な利点の1つである大きなグラフへのスケーリングと外挿の可能性が開ける。
分散アルゴリズムの設計原理にインスパイアされた新しい実行フレームワークであるFloodとEcho Netを提案する。
- 参考スコア(独自算出の注目度): 20.706469085872516
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Graph Neural Networks are a natural fit for learning algorithms. They can
directly represent tasks through an abstract but versatile graph structure and
handle inputs of different sizes. This opens up the possibility for scaling and
extrapolation to larger graphs, one of the most important advantages of an
algorithm. However, this raises two core questions i) How can we enable nodes
to gather the required information in a given graph ($\textit{information
exchange}$), even if is far away and ii) How can we design an execution
framework which enables this information exchange for extrapolation to larger
graph sizes ($\textit{algorithmic alignment for extrapolation}$). We propose a
new execution framework that is inspired by the design principles of
distributed algorithms: Flood and Echo Net. It propagates messages through the
entire graph in a wave like activation pattern, which naturally generalizes to
larger instances. Through its sparse but parallel activations it is provably
more efficient in terms of message complexity. We study the proposed model and
provide both empirical evidence and theoretical insights in terms of its
expressiveness, efficiency, information exchange and ability to extrapolate.
- Abstract(参考訳): グラフニューラルネットワークは、学習アルゴリズムに自然に適合する。
抽象的だが多彩なグラフ構造を通じてタスクを直接表現し、さまざまなサイズの入力を処理することができる。
これにより、大きなグラフへのスケーリングと外挿が可能となり、アルゴリズムの最も重要な利点の1つである。
しかし、これは2つの疑問を提起する。
i) たとえ遠くにいても,ノードが所定のグラフ(\textit{information exchange}$)で必要な情報を収集できるようにするには,どのようにすればよいか。
ii) より大きなグラフサイズへの外挿に関するこの情報交換を可能にする実行フレームワークをどのように設計すればよいか(\textit{algorithmic alignment for extrapolation}$)。
分散アルゴリズムの設計原理にインスパイアされた新しい実行フレームワークであるFloodとEcho Netを提案する。
アクティベーションパターンのようなウェーブで、グラフ全体を通してメッセージを伝搬し、自然により大きなインスタンスに一般化する。
スパースだが並列なアクティベーションにより、メッセージの複雑さの点で、明らかに効率が良い。
提案モデルについて検討し,その表現性,効率性,情報交換能力,外挿能力の両面から,実証的証拠と理論的知見を提供する。
関連論文リスト
- NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Learning Strong Graph Neural Networks with Weak Information [64.64996100343602]
我々は、弱い情報(GLWI)を用いたグラフ学習問題に対する原則的アプローチを開発する。
非完全構造を持つ入力グラフ上で長距離情報伝搬を行うデュアルチャネルGNNフレームワークであるD$2$PTを提案するが、グローバルな意味的類似性を符号化するグローバルグラフも提案する。
論文 参考訳(メタデータ) (2023-05-29T04:51:09Z) - You Only Transfer What You Share: Intersection-Induced Graph Transfer
Learning for Link Prediction [79.15394378571132]
従来見過ごされていた現象を調査し、多くの場合、元のグラフに対して密に連結された補グラフを見つけることができる。
より密度の高いグラフは、選択的で有意義な知識を伝達するための自然なブリッジを提供する元のグラフとノードを共有することができる。
この設定をグラフインターセクション誘導トランスファーラーニング(GITL)とみなし,eコマースや学術共同オーサシップ予測の実践的応用に動機づけられた。
論文 参考訳(メタデータ) (2023-02-27T22:56:06Z) - Learning Graph Algorithms With Recurrent Graph Neural Networks [8.873449722727026]
我々は、単純なグラフ問題を末尾から末尾まで小さなグラフで学習し、より大きなインスタンスに拡張する、反復的なアーキテクチャ設計に重点を置いている。
We use (i) skip connection, (ii) state regularization, and (iii) edge convolutions to guide GNNs to extrapolation。
論文 参考訳(メタデータ) (2022-12-09T15:42:22Z) - Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。
GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。
提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
論文 参考訳(メタデータ) (2022-03-03T09:53:53Z) - Inferential SIR-GN: Scalable Graph Representation Learning [0.4699313647907615]
グラフ表現学習法は、ネットワーク内のノードの数値ベクトル表現を生成する。
本研究では,ランダムグラフ上で事前学習されたモデルであるInferential SIR-GNを提案し,ノード表現を高速に計算する。
このモデルではノードの構造的役割情報を捉えることができ、ノードやグラフの分類タスクにおいて、目に見えないネットワーク上で優れた性能を示すことができる。
論文 参考訳(メタデータ) (2021-11-08T20:56:37Z) - Self-Supervised Deep Graph Embedding with High-Order Information Fusion
for Community Discovery [3.6002285517472767]
提案アルゴリズムは,複数の深部グラフ畳み込みニューラルネットワークを学習するために,自己教師機構とグラフの高次情報を用いている。
複数のグラフ畳み込みニューラルネットワークの出力を融合して、グラフの属性と構造情報を含むノードの表現を抽出する。
論文 参考訳(メタデータ) (2021-02-05T17:22:28Z) - Towards Efficient Scene Understanding via Squeeze Reasoning [71.1139549949694]
我々はSqueeze Reasoningと呼ばれる新しいフレームワークを提案する。
空間地図上の情報を伝播するのではなく、まず入力特徴をチャネルワイドなグローバルベクトルに絞ることを学ぶ。
提案手法はエンドツーエンドのトレーニングブロックとしてモジュール化可能であり,既存のネットワークに簡単に接続可能であることを示す。
論文 参考訳(メタデータ) (2020-11-06T12:17:01Z) - Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
グラフ埋め込みは、高次元および非ユークリッド特徴空間でデータ構造を変換しエンコードする方法である。
CensNetは一般的なグラフ埋め込みフレームワークで、ノードとエッジの両方を潜在機能空間に埋め込む。
提案手法は,4つのグラフ学習課題における最先端のパフォーマンスを達成または一致させる。
論文 参考訳(メタデータ) (2020-10-25T22:39:31Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳(メタデータ) (2020-08-31T23:15:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。