論文の概要: How hard is to distinguish graphs with graph neural networks?

• arxiv url: http://arxiv.org/abs/2005.06649v2
• Date: Fri, 16 Oct 2020 12:48:57 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-03 12:49:06.939310
• Title: How hard is to distinguish graphs with graph neural networks?
• Title（参考訳）: グラフニューラルネットワークによるグラフの識別はどの程度難しいか?
• Authors: Andreas Loukas
• Abstract要約: 本研究では,メッセージパッシングモデル(MPNN)におけるグラフアイソモーフィズムの分類変種に対する硬度結果の導出を行う。 MPNNは、今日のグラフニューラルネットワークの大部分を包含しており、ノードにユニークな特徴が与えられた場合、普遍的である。 12のグラフ分類タスクと420のネットワークを含む実証的研究は、実際の性能と理論的予測の間に強い整合性を示す。
• 参考スコア（独自算出の注目度）: 32.09819774228997
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A hallmark of graph neural networks is their ability to distinguish the isomorphism class of their inputs. This study derives hardness results for the classification variant of graph isomorphism in the message-passing model (MPNN). MPNN encompasses the majority of graph neural networks used today and is universal when nodes are given unique features. The analysis relies on the introduced measure of communication capacity. Capacity measures how much information the nodes of a network can exchange during the forward pass and depends on the depth, message-size, global state, and width of the architecture. It is shown that the capacity of MPNN needs to grow linearly with the number of nodes so that a network can distinguish trees and quadratically for general connected graphs. The derived bounds concern both worst- and average-case behavior and apply to networks with/without unique features and adaptive architecture -- they are also up to two orders of magnitude tighter than those given by simpler arguments. An empirical study involving 12 graph classification tasks and 420 networks reveals strong alignment between actual performance and theoretical predictions.
• Abstract（参考訳）: グラフニューラルネットワークの特徴は、入力の同型クラスを識別する能力である。 本研究では,メッセージパッシングモデル(MPNN)におけるグラフ同型分類の難易度を導出する。 MPNNは、今日使用されているグラフニューラルネットワークの大部分を含み、ノードにユニークな特徴が与えられると普遍的になる。 この分析は、導入された通信容量の尺度に依存する。 容量は、ネットワークのノードがフォワードパス中にどれだけの情報を交換できるかを測定し、深さ、メッセージサイズ、グローバル状態、アーキテクチャの幅に依存する。 ネットワークが木を区別し,一般連結グラフに対して二次的に区別できるように,MPNNの容量はノード数とともに線形に増大する必要がある。 導出された境界は、最悪の場合と平均的な場合の両方に関係し、ユニークな特徴と適応アーキテクチャを持たないネットワークにも適用される。 12のグラフ分類タスクと420のネットワークを含む実証的研究は、実際の性能と理論的予測の間に強い整合性を示す。

関連論文リスト

• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Knowledge Enhanced Graph Neural Networks for Graph Completion [0.0]
  Knowledge Enhanced Graph Neural Networks (KeGNN)は、グラフ補完のためのニューラルシンボリックなフレームワークである。 KeGNNは、知識強化レイヤを積み重ねた基盤としてグラフニューラルネットワークで構成されている。 我々はKeGNNを、最先端のグラフニューラルネットワーク、グラフ畳み込みネットワーク、グラフ注意ネットワークの2つと組み合わせてインスタンス化する。
  論文  参考訳（メタデータ） (2023-03-27T07:53:43Z)
• Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representations [26.77596449192451]
  グラフニューラルネットワーク(GNN)は、グラフ上の機械学習問題を解決するための有望なツールとして登場した。 本論文では,Weisfeiler-Leman(WL)アルゴリズムによって生成される階層に基づいて,ノード間の距離関数を定義する。 本稿では,ノード間の距離を保存する表現を学習するモデルを提案する。
  論文  参考訳（メタデータ） (2022-11-04T15:03:41Z)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。 最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。 科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
  論文  参考訳（メタデータ） (2022-05-15T11:38:14Z)
• Graph Neural Networks with Learnable Structural and Positional Representations [83.24058411666483]
  任意のグラフの大きな問題は、ノードの標準位置情報の欠如である。 ノードの位置ノード(PE)を導入し、Transformerのように入力層に注入する。 両方のGNNクラスで学習可能なPEを考えると、分子データセットのパフォーマンスは2.87%から64.14%に向上する。
  論文  参考訳（メタデータ） (2021-10-15T05:59:15Z)
• CopulaGNN: Towards Integrating Representational and Correlational Roles of Graphs in Graph Neural Networks [23.115288017590093]
  グラフニューラルネットワーク(GNN)モデルが両タイプの情報を効果的に活用する方法について検討する。 提案したCopula Graph Neural Network (CopulaGNN)は、幅広いGNNモデルをベースモデルとして扱うことができる。
  論文  参考訳（メタデータ） (2020-10-05T15:20:04Z)
• Graph Structure of Neural Networks [104.33754950606298]
  ニューラルネットワークのグラフ構造が予測性能にどのように影響するかを示す。 リレーショナルグラフの"スイートスポット"は、予測性能を大幅に改善したニューラルネットワークにつながる。 トップパフォーマンスニューラルネットワークは、実際の生物学的ニューラルネットワークと驚くほどよく似たグラフ構造を持つ。
  論文  参考訳（メタデータ） (2020-07-13T17:59:31Z)
• Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks [183.97265247061847]
  我々はグラフ信号処理を活用してグラフニューラルネットワーク(GNN)の表現空間を特徴付ける。 GNNにおけるグラフ畳み込みフィルタの役割について議論し、そのようなフィルタで構築されたアーキテクチャは、置換同値の基本的な性質と位相変化に対する安定性を持つことを示す。 また,ロボット群に対するリコメンデータシステムや分散型コントローラの学習におけるGNNの利用について検討した。
  論文  参考訳（メタデータ） (2020-03-08T13:02:15Z)
• Analyzing Neural Networks Based on Random Graphs [77.34726150561087]
  様々なタイプのランダムグラフに対応するアーキテクチャを用いて,ニューラルネットワークの大規模評価を行う。 古典的な数値グラフ不変量は、それ自体が最良のネットワークを選び出すことができない。 また、主に短距離接続を持つネットワークは、多くの長距離接続が可能なネットワークよりも性能が良いことも見出した。
  論文  参考訳（メタデータ） (2020-02-19T11:04:49Z)

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

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