論文の概要: On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles

• arxiv url: http://arxiv.org/abs/2502.03703v1
• Date: Thu, 06 Feb 2025 01:25:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-07 14:32:07.746102
• Title: On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles
• Title（参考訳）: 境界周期グラフのためのグラフグラフニューラルネットワークの表現力について
• Authors: Ziang Chen, Qiao Zhang, Runzhong Wang,
• Abstract要約: この研究は、最大$k$までの距離を持つ隣人からの情報を集約する$k$-hopサブグラフGNNを調査します。 我々は、$k$ホップ部分グラフ GNN がグラフ上の置換不変/同変連続関数を任意の誤差許容範囲内で2k+1$以上のサイクルなしで近似できることを証明した。
• 参考スコア（独自算出の注目度）: 17.29046077604317
• License:
• Abstract: Graph neural networks (GNNs) have been widely used in graph-related contexts. It is known that the separation power of GNNs is equivalent to that of the Weisfeiler-Lehman (WL) test; hence, GNNs are imperfect at identifying all non-isomorphic graphs, which severely limits their expressive power. This work investigates $k$-hop subgraph GNNs that aggregate information from neighbors with distances up to $k$ and incorporate the subgraph structure. We prove that under appropriate assumptions, the $k$-hop subgraph GNNs can approximate any permutation-invariant/equivariant continuous function over graphs without cycles of length greater than $2k+1$ within any error tolerance. We also provide an extension to $k$-hop GNNs without incorporating the subgraph structure. Our numerical experiments on established benchmarks and novel architectures validate our theory on the relationship between the information aggregation distance and the cycle size.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、グラフ関連の文脈で広く使われている。 GNN の分離パワーはWeisfeiler-Lehman (WL) テストと同値であることが知られているため、GNN はすべての非同型グラフを識別できないため、表現力は著しく制限される。 この研究は、$k$ホップのサブグラフGNNを調査し、最大$k$までの距離を持つ隣人からの情報を集約し、サブグラフ構造を組み込む。 適切な仮定の下では、$k$-hop 部分グラフ GNN はグラフ上の置換不変/同変連続関数を任意の誤差許容範囲内において 2k+1$ 以上の長さのサイクルなしで近似することができることを証明している。 サブグラフ構造を組み込まずに$k$-hop GNNの拡張も提供する。 確立されたベンチマークと新しいアーキテクチャに関する数値実験により,情報集約距離とサイクルサイズとの関係を検証した。

関連論文リスト

• Global Graph Counterfactual Explanation: A Subgraph Mapping Approach [54.42907350881448]
  グラフニューラルネットワーク(GNN)は、様々な現実世界のアプリケーションに広くデプロイされている。 対実的説明は、GNN予測を変える入力グラフ上で最小の摂動を見つけることを目的としている。 我々は,グローバルレベルのグラフ対実的説明法であるGlobalGCEを提案する。
  論文  参考訳（メタデータ） (2024-10-25T21:39:05Z)
• Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information [17.56609419806051]
  K$ホップメッセージパスGNNの表現力を高めるために,テキストサブストラクチャ符号化関数を提案する。 提案手法は,従来の$K$-hopグラフニューラルネットワークや1-WLサブグラフGNNよりも強力である。
  論文  参考訳（メタデータ） (2024-06-27T15:10:56Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• An Efficient Subgraph GNN with Provable Substructure Counting Power [32.44487589958533]
  本稿では,グラフニューラルネットワーク(GNN)のサブストラクチャカウント能力による表現能力の向上について検討する。 近年の進歩では、入力グラフを多数のサブグラフに分割するサブグラフGNNが採用され、グラフ全体の表現を拡大するためにそれぞれにGNNが適用されるようになった。 様々なサブ構造を識別できるにもかかわらず、サブグラフGNNは計算とメモリの大幅なコストによって妨げられる。
  論文  参考訳（メタデータ） (2023-03-19T05:35:59Z)
• From Local to Global: Spectral-Inspired Graph Neural Networks [28.858773653743075]
  グラフニューラルネットワーク(GNN)は、非ユークリッドデータのための強力なディープラーニング手法である。 MPNNは、局所グラフ地区の信号を集約して結合するメッセージパッシングアルゴリズムである。 MPNNは、過密や過密といった問題に悩まされる可能性がある。
  論文  参考訳（メタデータ） (2022-09-24T17:19:00Z)
• $p$-Laplacian Based Graph Neural Networks [27.747195341003263]
  グラフネットワーク(GNN)は、グラフ上の半教師付きノード分類において優れた性能を示す。 我々は、離散正規化フレームワークからメッセージパッシング機構を導出する$p$GNNと呼ばれる新しい$p$LaplacianベースのGNNモデルを提案する。 新たなメッセージパッシング機構は低域通過フィルタと高域通過フィルタを同時に動作させることで,ホモ親和性グラフとヘテロ親和性グラフの両方に対して$p$GNNを有効にすることができることを示す。
  論文  参考訳（メタデータ） (2021-11-14T13:16:28Z)
• Graph Neural Networks with Local Graph Parameters [1.8600631687568656]
  ローカルグラフパラメータは、任意のグラフニューラルネットワーク(GNN)アーキテクチャに追加することができる。 我々の結果は、有限モデル理論と有限変数論理の深い結果とGNNを結びつける。
  論文  参考訳（メタデータ） (2021-06-12T07:43:51Z)
• 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)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
  グラフニューラルネットワーク(GNN)は、隣の情報を集約して組み合わせることでノードの特徴を学習する。 GNNはブラックボックスとして扱われ、人間の知的な説明が欠けている。 我々はモデルレベルでGNNを解釈する新しい手法 XGNN を提案する。
  論文  参考訳（メタデータ） (2020-06-03T23:52:43Z)

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

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