Fugu-MT 論文翻訳(概要): Expander Graph Propagation

論文の概要: Expander Graph Propagation

arxiv url: http://arxiv.org/abs/2210.02997v1
Date: Thu, 6 Oct 2022 15:36:37 GMT
ステータス: 処理完了
システム内更新日: 2022-10-07 15:17:48.369378
Title: Expander Graph Propagation
Title（参考訳）: 展開グラフの伝播
Authors: Andreea Deac, Marc Lackenby, Petar Veli\v{c}kovi\'c
Abstract要約: 本稿では,拡張グラフ上での情報伝達に基づくエレガントなアプローチを提案する。 EGPは、セットアップに最小限の労力を要しながら、上記の懸念に対処できることを示します。我々の分析は、GNNの過剰な監視に対処する、スケーラブルな方法の新たなクラスへの道を開くものだと信じています。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Deploying graph neural networks (GNNs) on whole-graph classification or regression tasks is known to be challenging: it often requires computing node features that are mindful of both local interactions in their neighbourhood and the global context of the graph structure. GNN architectures that navigate this space need to avoid pathological behaviours, such as bottlenecks and oversquashing, while ideally having linear time and space complexity requirements. In this work, we propose an elegant approach based on propagating information over expander graphs. We provide an efficient method for constructing expander graphs of a given size, and use this insight to propose the EGP model. We show that EGP is able to address all of the above concerns, while requiring minimal effort to set up, and provide evidence of its empirical utility on relevant datasets and baselines in the Open Graph Benchmark. Importantly, using expander graphs as a template for message passing necessarily gives rise to negative curvature. While this appears to be counterintuitive in light of recent related work on oversquashing, we theoretically demonstrate that negatively curved edges are likely to be required to obtain scalable message passing without bottlenecks. To the best of our knowledge, this is a previously unstudied result in the context of graph representation learning, and we believe our analysis paves the way to a novel class of scalable methods to counter oversquashing in GNNs.
Abstract（参考訳）: グラフニューラルネットワーク(GNN)をグラフ全体の分類や回帰タスクにデプロイすることは困難であることが知られている。この空間をナビゲートするGNNアーキテクチャは、時間と空間の複雑さを理想的に要求しながら、ボトルネックやオーバーシャッシングといった病理学的な振る舞いを避ける必要がある。本研究では,拡張グラフ上での情報伝達に基づくエレガントなアプローチを提案する。与えられた大きさの拡張グラフを構築するための効率的な方法を提案し、この知見を用いてEGPモデルを提案する。 EGPは上記のすべての懸念に対処できるが、セットアップには最小限の労力が必要であり、Open Graph Benchmarkの関連するデータセットやベースラインにその経験的有用性を示す証拠を提供する。重要なことに、メッセージパッシングのテンプレートとしてexpander graphsを使用することは、必ずしも負の曲率をもたらす。オーバースカッシングに関する最近の研究からすると、これは直感的とは思えないが、ボトルネックを伴わずにスケーラブルなメッセージパッシングを得るためには、負の湾曲したエッジが必要であることが理論的に証明されている。我々の知る限りでは、これはグラフ表現学習の文脈における未研究の結果であり、我々の分析は、GNNのオーバーカッシングに対処するための、新しいスケーラブルな方法のクラスへの道を開くものだと考えている。

関連論文リスト

Implicit Graph Neural Diffusion Networks: Convergence, Generalization, and Over-Smoothing [7.984586585987328]
Inlicit Graph Neural Networks (GNN)は、グラフ学習問題に対処する上で大きな成功を収めた。パラメータ化グラフラプラシアン演算子に基づく暗黙グラフ拡散層を設計するための幾何学的枠組みを提案する。ディリクレエネルギー最小化問題の固定点方程式として, 暗黙のGNN層がどう見えるかを示す。
論文参考訳（メタデータ） (2023-08-07T05:22:33Z)
GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks [72.01829954658889]
本稿では,この新たな問題設定の数学的定義を紹介する。一つのグラフ共有構造学習者と複数のグラフ固有GNNを協調する一般的なフレームワークを考案する。十分に訓練された構造学習者は、微調整なしで、目に見えない対象グラフの適応的な構造を直接生成することができる。
論文参考訳（メタデータ） (2023-06-20T03:33:22Z)
NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文参考訳（メタデータ） (2023-06-14T09:21:15Z)
FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
論文参考訳（メタデータ） (2022-10-21T07:58:03Z)
Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
論文参考訳（メタデータ） (2022-07-18T14:23:31Z)
Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。 GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
論文参考訳（メタデータ） (2022-03-03T09:53:53Z)
LSP : Acceleration and Regularization of Graph Neural Networks via Locality Sensitive Pruning of Graphs [2.4250821950628234]
グラフニューラルネットワーク(GNN)は、グラフ関連のタスクのための非常に成功したツールとして登場した。大きなグラフは、性能を損なうことなく取り除くことができる多くの冗長なコンポーネントを含むことが多い。そこで我々はLocality-Sensitive Hashingに基づくグラフプルーニングのためのLocality-Sensitive Pruning(LSP)という体系的手法を提案する。
論文参考訳（メタデータ） (2021-11-10T14:12:28Z)
GNNAutoScale: Scalable and Expressive Graph Neural Networks via Historical Embeddings [51.82434518719011]
GNNAutoScale(GAS)は、任意のメッセージパスGNNを大規模グラフにスケールするためのフレームワークである。ガスは、前回のトレーニングの繰り返しから過去の埋め込みを利用して計算グラフのサブツリー全体を掘り起こします。ガスは大規模グラフ上で最先端のパフォーマンスに達する。
論文参考訳（メタデータ） (2021-06-10T09:26:56Z)
GraphMI: Extracting Private Graph Data from Graph Neural Networks [59.05178231559796]
GNNを反転させてトレーニンググラフのプライベートグラフデータを抽出することを目的とした textbfGraph textbfModel textbfInversion attack (GraphMI) を提案する。具体的には,グラフ特徴の空間性と滑らかさを保ちながら,グラフエッジの離散性に対処する勾配モジュールを提案する。エッジ推論のためのグラフトポロジ、ノード属性、ターゲットモデルパラメータを効率的に活用するグラフ自動エンコーダモジュールを設計する。
論文参考訳（メタデータ） (2021-06-05T07:07:52Z)
Graph Networks with Spectral Message Passing [1.0742675209112622]
本稿では,空間領域とスペクトル領域の両方にメッセージパッシングを適用するSpectral Graph Networkを紹介する。その結果,spectrum gnは効率のよいトレーニングを促進し,より多くのパラメータを持つにもかかわらず,少ないトレーニングイテレーションで高いパフォーマンスを達成できることがわかった。
論文参考訳（メタデータ） (2020-12-31T21:33:17Z)

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

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