論文の概要: Weisfeiler--Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs

• arxiv url: http://arxiv.org/abs/2210.03990v1
• Date: Sat, 8 Oct 2022 10:14:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-11 15:07:35.812803
• Title: Weisfeiler--Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs
• Title（参考訳）: Weisfeiler--Lehmanがダイナミックに: 分散グラフと動的グラフのためのグラフニューラルネットワークの表現力の分析
• Authors: Silvia Beddar-Wiesing, Giuseppe Alessio D'Inverno, Caterina Graziani, Veronica Lachi, Alice Moallemy-Oureh, Franco Scarselli, Josephine Maria Thomas
• Abstract要約: グラフニューラルネットワーク(GNN)は、グラフ処理のための大規模なリレーショナルモデルである。 GNNの表現力に関する最近の研究は2つの問題に焦点を当てている。 本研究は汎用GNNモデルを考察し,これらの領域に対して適切な1-WLテストを提案する。
• 参考スコア（独自算出の注目度）: 1.1083289076967897
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs) are a large class of relational models for graph processing. Recent theoretical studies on the expressive power of GNNs have focused on two issues. On the one hand, it has been proven that GNNs are as powerful as the Weisfeiler-Lehman test (1-WL) in their ability to distinguish graphs. Moreover, it has been shown that the equivalence enforced by 1-WL equals unfolding equivalence. On the other hand, GNNs turned out to be universal approximators on graphs modulo the constraints enforced by 1-WL/unfolding equivalence. However, these results only apply to Static Undirected Homogeneous Graphs with node attributes. In contrast, real-life applications often involve a variety of graph properties, such as, e.g., dynamics or node and edge attributes. In this paper, we conduct a theoretical analysis of the expressive power of GNNs for these two graph types that are particularly of interest. Dynamic graphs are widely used in modern applications, and its theoretical analysis requires new approaches. The attributed type acts as a standard form for all graph types since it has been shown that all graph types can be transformed without loss to Static Undirected Homogeneous Graphs with attributes on nodes and edges (SAUHG). The study considers generic GNN models and proposes appropriate 1-WL tests for those domains. Then, the results on the expressive power of GNNs are extended by proving that GNNs have the same capability as the 1-WL test in distinguishing dynamic and attributed graphs, the 1-WL equivalence equals unfolding equivalence and that GNNs are universal approximators modulo 1-WL/unfolding equivalence. Moreover, the proof of the approximation capability holds for SAUHGs, which include most of those used in practical applications, and it is constructive in nature allowing to deduce hints on the architecture of GNNs that can achieve the desired accuracy.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフ処理のための大規模な関係モデルである。 GNNの表現力に関する最近の理論的研究は2つの問題に焦点を当てている。 一方、GNNはグラフを識別する能力においてWeisfeiler-Lehmanテスト(1-WL)と同じくらい強力であることが証明されている。 さらに、1-WL による同値性は展開同値性に等しいことが示されている。 一方、GNNは1-WL/展開同値の制約を変調するグラフ上の普遍近似器であることが判明した。 しかし、これらの結果はノード属性を持つ静的無向等質グラフにのみ適用される。 対照的に、現実のアプリケーションは、動的やノード、エッジ属性など、様々なグラフ特性を含むことが多い。 本稿では,特に関心のある2種類のグラフに対して,GNNの表現力に関する理論的解析を行う。 動的グラフは現代の応用で広く使われており、理論解析には新しいアプローチが必要である。 属性型は全てのグラフ型の標準形式として機能するが、これは全てのグラフ型がノードとエッジ(SAUHG)の属性を持つ静的無方向性ホモジニアスグラフに失われることなく変換可能であることが示されている。 本研究は汎用GNNモデルを考察し,これらの領域に対して適切な1-WLテストを提案する。 そして、GNNの表現力に関する結果は、動的および属性グラフを区別する1-WLテストと同じ能力を持つこと、GNNが1-WL/アンフォールディング同値であり、GNNが1-WL/アンフォールディング同値であることを示すことによって拡張される。 さらに,SAUHGの近似能力の証明は実用的応用のほとんどを含むものであり,望まれる精度を達成できるGNNのアーキテクチャ上のヒントを導出することができる構造的である。

関連論文リスト

• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Generalization Limits of Graph Neural Networks in Identity Effects Learning [12.302336258860116]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフドメインでデータ駆動学習を行う強力なツールとして登場した。 我々は、いわゆるアイデンティティ効果の学習において、GNNの新たな一般化特性と基本的限界を確立する。 我々の研究は、単純な認知タスクを行う際に、GNNの能力を理解する必要性によって動機付けられている。
  論文  参考訳（メタデータ） (2023-06-30T20:56:38Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  グラフネットワーク(GNN)は本質的に表現力に制限がある。 本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。 これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
  論文  参考訳（メタデータ） (2023-02-22T18:53:38Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Graph Neural Networks for Graphs with Heterophily: A Survey [98.45621222357397]
  異種グラフに対するグラフニューラルネットワーク(GNN)の総合的なレビューを提供する。 具体的には,既存の異好性GNNモデルを本質的に支配する系統分類法を提案する。 グラフヘテロフィリーと様々なグラフ研究領域の相関を議論し、より効果的なGNNの開発を促進することを目的とした。
  論文  参考訳（メタデータ） (2022-02-14T23:07:47Z)
• On the approximation capability of GNNs in node classification/regression tasks [4.141514895639094]
  グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。 GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
  論文  参考訳（メタデータ） (2021-06-16T17:46:51Z)
• 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)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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