論文の概要: Nested Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2110.13197v1
• Date: Mon, 25 Oct 2021 18:22:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-27 15:24:53.249068
• Title: Nested Graph Neural Networks
• Title（参考訳）: ネストグラフニューラルネットワーク
• Authors: Muhan Zhang, Pan Li
• Abstract要約: グラフニューラルネットワーク(GNN)のグラフ分類における成功は、Weisfeiler-Lehman (1-WL)アルゴリズムと密接に関連している。 そこで我々は,Nested Graph Neural Networks (NGNN) を提案する。
• 参考スコア（独自算出の注目度）: 20.28732862748783
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural network (GNN)'s success in graph classification is closely related to the Weisfeiler-Lehman (1-WL) algorithm. By iteratively aggregating neighboring node features to a center node, both 1-WL and GNN obtain a node representation that encodes a rooted subtree around the center node. These rooted subtree representations are then pooled into a single representation to represent the whole graph. However, rooted subtrees are of limited expressiveness to represent a non-tree graph. To address it, we propose Nested Graph Neural Networks (NGNNs). NGNN represents a graph with rooted subgraphs instead of rooted subtrees, so that two graphs sharing many identical subgraphs (rather than subtrees) tend to have similar representations. The key is to make each node representation encode a subgraph around it more than a subtree. To achieve this, NGNN extracts a local subgraph around each node and applies a base GNN to each subgraph to learn a subgraph representation. The whole-graph representation is then obtained by pooling these subgraph representations. We provide a rigorous theoretical analysis showing that NGNN is strictly more powerful than 1-WL. In particular, we proved that NGNN can discriminate almost all r-regular graphs, where 1-WL always fails. Moreover, unlike other more powerful GNNs, NGNN only introduces a constant-factor higher time complexity than standard GNNs. NGNN is a plug-and-play framework that can be combined with various base GNNs. We test NGNN with different base GNNs on several benchmark datasets. NGNN uniformly improves their performance and shows highly competitive performance on all datasets.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)のグラフ分類における成功は、Weisfeiler-Lehman (1-WL)アルゴリズムと密接に関連している。 隣接ノードの機能を中心ノードに繰り返し集約することにより、1-WLとGNNは、中心ノードの周囲にルート付きサブツリーをエンコードするノード表現を得る。 これらのルート木表現は、グラフ全体を表現するために単一の表現にプールされる。 しかし、根付き部分木は非木グラフを表すために限定表現性を持つ。 そこで我々はNested Graph Neural Networks (NGNN)を提案する。 NGNNは、ルート付き部分木の代わりにルート付き部分グラフを持つグラフを表すため、多くの同一部分木を共有する2つのグラフは、同じ表現を持つ傾向がある。 鍵となるのは、各ノードの表現がサブツリーよりもその周りのサブグラフをエンコードすることだ。 これを実現するため、NGNNは各ノードの周囲の局所部分グラフを抽出し、各サブグラフにベースGNNを適用してサブグラフ表現を学習する。 グラフ全体の表現は、これらのサブグラフ表現をプールすることで得られる。 NGNNが1-WLよりも強力であることを示す厳密な理論解析を行った。 特に、NGNNは1-WLが常に失敗するほとんどすべてのr-正則グラフを識別できることを示した。 さらに、他の強力なGNNとは異なり、NGNNは標準のGNNよりも一定の時間的複雑さを導入するのみである。 NGNNは様々なベースGNNと組み合わせることができるプラグイン・アンド・プレイフレームワークである。 いくつかのベンチマークデータセットで異なるベースGNNでNGNNをテストする。 NGNNは、そのパフォーマンスを均一に改善し、すべてのデータセットで高い競争性能を示す。

関連論文リスト

• Boosting the Cycle Counting Power of Graph Neural Networks with I$^2$-GNNs [9.806910643086043]
  本稿では,各サブグラフ内のルートノードとその隣人に異なる識別子を割り当てることで,サブグラフMPNNを拡張するための2$-GNNを提案する。 2$-GNNsの識別力は、サブグラフMPNNよりも強く、3WLテストより部分的に強いことが示されている。 我々の知る限りでは、理論的な保証とともに6サイクルを数えられる最初の線形時間GNNモデルである。
  論文  参考訳（メタデータ） (2022-10-22T09:40:00Z)
• Geodesic Graph Neural Network for Efficient Graph Representation Learning [34.047527874184134]
  我々はGeodesic GNN(GDGNN)と呼ばれる効率的なGNNフレームワークを提案する。 ラベル付けなしでノード間の条件付き関係をモデルに注入する。 ジオデシック表現を前提としたGDGNNは、通常のGNNよりもはるかにリッチな構造情報を持つノード、リンク、グラフ表現を生成することができる。
  論文  参考訳（メタデータ） (2022-10-06T02:02:35Z)
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness [23.279464786779787]
  私たちはMPNNをより表現力のあるものにするための一般的なフレームワークを導入します。 私たちのフレームワークは1&2-WLよりも強力で、3WLよりも強力です。 本手法は,いくつかのよく知られたグラフMLタスクに対して,新たな最先端性能を大きなマージンで設定する。
  論文  参考訳（メタデータ） (2021-10-07T19:08:08Z)
• Identity-aware Graph Neural Networks [63.6952975763946]
  グラフニューラルネットワーク(ID-GNN)を1-WLテストよりも表現力の高いメッセージクラスを開発しています。 ID-GNNは、メッセージパッシング中にノードのIDを誘導的に考慮することにより、既存のGNNアーキテクチャを拡張します。 既存のGNNをID-GNNに変換すると、挑戦ノード、エッジ、グラフプロパティ予測タスクの平均40%の精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-01-25T18:59:01Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
  グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。 これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
  論文  参考訳（メタデータ） (2020-08-04T18:57:36Z)
• Graphon Neural Networks and the Transferability of Graph Neural Networks [125.71771240180654]
  グラフニューラルネットワーク(GNN)は、ネットワークデータから局所的な特徴を抽出するためにグラフ畳み込みに依存する。 我々は,GNNのリミットオブジェクトとしてグラフオンNNを導入し,GNNの出力とそのリミットグラフオン-NNとの差を証明した。 これにより、GNNの識別可能性と転送可能性のトレードオフが確立される。
  論文  参考訳（メタデータ） (2020-06-05T16:41:08Z)
• Bilinear Graph Neural Network with Neighbor Interactions [106.80781016591577]
  グラフニューラルネットワーク(GNN)は,グラフデータ上で表現を学習し,予測を行う強力なモデルである。 本稿では,グラフ畳み込み演算子を提案し,隣接するノードの表現の対の相互作用で重み付け和を増大させる。 このフレームワークをBGNN(Bilinear Graph Neural Network)と呼び、隣ノード間の双方向相互作用によるGNN表現能力を向上させる。
  論文  参考訳（メタデータ） (2020-02-10T06:43:38Z)

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

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