論文の概要: Homomorphism Expressivity of Spectral Invariant Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2503.00485v1
• Date: Sat, 01 Mar 2025 13:23:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:17:03.385177
• Title: Homomorphism Expressivity of Spectral Invariant Graph Neural Networks
• Title（参考訳）: スペクトル不変グラフニューラルネットワークの準同型表現性
• Authors: Jingchu Gai, Yiheng Du, Bohang Zhang, Haggai Maron, Liwei Wang,
• Abstract要約: スペクトル不変なGNNは、並列木と呼ばれる特定の木のようなグラフのクラスを正確に成すことができることを証明している。 我々の結果はArvind et al. (2024) を著しく拡張し、オープンな疑問を解決した。 我々は解析を高次GNNに一般化し、Zhangらによって提起されたオープンな質問に答える(2024年)。
• 参考スコア（独自算出の注目度）: 25.040557677497745
• License:
• Abstract: Graph spectra are an important class of structural features on graphs that have shown promising results in enhancing Graph Neural Networks (GNNs). Despite their widespread practical use, the theoretical understanding of the power of spectral invariants -- particularly their contribution to GNNs -- remains incomplete. In this paper, we address this fundamental question through the lens of homomorphism expressivity, providing a comprehensive and quantitative analysis of the expressive power of spectral invariants. Specifically, we prove that spectral invariant GNNs can homomorphism-count exactly a class of specific tree-like graphs which we refer to as parallel trees. We highlight the significance of this result in various contexts, including establishing a quantitative expressiveness hierarchy across different architectural variants, offering insights into the impact of GNN depth, and understanding the subgraph counting capabilities of spectral invariant GNNs. In particular, our results significantly extend Arvind et al. (2024) and settle their open questions. Finally, we generalize our analysis to higher-order GNNs and answer an open question raised by Zhang et al. (2024).
• Abstract（参考訳）: グラフスペクトルはグラフ上の重要な構造的特徴のクラスであり、グラフニューラルネットワーク(GNN)の強化に有望な結果を示している。 広く実用化されているにもかかわらず、スペクトル不変量(特にGNNへの貢献)のパワーの理論的理解はいまだ不完全である。 本稿では、スペクトル不変量の表現力を包括的かつ定量的に分析し、同型表現率のレンズを通してこの問題に対処する。 具体的には、スペクトル不変なGNNが、並列木と呼ばれる特定の木のようなグラフのクラスを正確に同型カウントできることを示す。 本稿では,GNN深度の影響を定量的に把握し,スペクトル不変GNNのサブグラフカウント機能を理解することなど,様々な文脈におけるこの結果の重要性を強調した。 特に、我々の結果はArvind et al (2024) を著しく拡張し、オープンな疑問を解決した。 最後に、我々の分析を高階のGNNに一般化し、Zhang et al (2024) が提起したオープンな質問に答える。

関連論文リスト

• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。 我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。 最も重要な観察は、前の結果のようにグラフのサイズに制限されるのではなく、1つの大きなグラフで一般化能力を実現することができることである。
  論文  参考訳（メタデータ） (2024-09-08T18:55:57Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• On the Expressive Power of Spectral Invariant Graph Neural Networks [28.557550571187253]
  Eigenspace Projection GNN(EPNN)と呼ばれるスペクトル不変GNNを設計するための統一メッセージパッシングフレームワークを導入する。 EPNNは、従来のスペクトル不変アーキテクチャをすべて統一し、それらが厳密に表現されにくいか、EPNNと同値であることを示す。 より表現力の高いGNNと組み合わせることで、スペクトル特徴を用いることで表現性が向上するかどうかを論じる。
  論文  参考訳（メタデータ） (2024-06-06T17:59:41Z)
• Generalization of Graph Neural Networks through the Lens of Homomorphism [7.223313563198697]
  本稿では,グラフ・ニューラル・ネットワーク(GNN)の一般化を,グラフ準同型のエントロピー解析という新たな視点で研究することを提案する。 グラフ準同型と情報理論測度を結びつけることにより、グラフ分類とノード分類の両方の一般化境界を導出する。 これらの境界は、パス、サイクル、傾きなど、様々なグラフ構造に固有の微妙さを捉えることができる。
  論文  参考訳（メタデータ） (2024-03-10T03:51:59Z)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness [35.409017863665575]
  準同型表現性は、GNNモデルが準同型の下でグラフを数える能力を測定する。 ケーススタディとして著名なGNNの4つのクラスを調べることで、それらの同型表現の単純で統一的でエレガントな記述を導き出す。 本研究の結果は, 過去の一連の研究に対する新たな洞察を与え, 地域社会における様々なサブアレスの景観を統一し, いくつかのオープンな疑問を解決した。
  論文  参考訳（メタデータ） (2024-01-16T17:23:23Z)
• On the Expressive Power of Graph Neural Networks [0.0]
  グラフニューラルネットワーク(GNN)は、社会科学、化学、医学といった分野における様々なタスクを解くことができる。 ディープラーニングをグラフ構造化データに拡張することにより、GNNは、社会科学、化学、医学といった分野におけるさまざまなタスクを解決できる。
  論文  参考訳（メタデータ） (2024-01-03T08:54:56Z)
• Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All? [61.35457647107439]
  ほとんどの実世界のホモフィルグラフとヘテロフィルグラフは、ホモフィルグラフとヘテロフィルグラフの両方の構造パターンの混合ノードから構成される。 ノード分類におけるグラフニューラルネットワーク (GNN) は, 一般にホモ親和性ノード上で良好に機能することを示す。 次に、GNNに対する厳密で非I.d PAC-Bayesian一般化を提案し、性能格差の理由を明らかにした。
  論文  参考訳（メタデータ） (2023-06-02T07:46:20Z)
• On the Expressiveness and Generalization of Hypergraph Neural Networks [77.65788763444877]
  この拡張抽象化はハイパーグラフニューラルネットワーク(HyperGNN)の表現性、学習、および(構造的)一般化を分析するためのフレームワークを記述する。 具体的には、HyperGNNが有限データセットからどのように学習し、任意の入力サイズのグラフ推論問題に構造的に一般化するかに焦点を当てる。
  論文  参考訳（メタデータ） (2023-03-09T18:42:18Z)
• How Powerful are Spectral Graph Neural Networks [9.594432031144715]
  スペクトルグラフニューラルネットワーク(Spectral Graph Neural Network)は、グラフ信号フィルタに基づくグラフニューラルネットワークの一種である。 まず、非線形性のないスペクトルGNNでさえ任意のグラフ信号を生成することを証明した。 また、スペクトルGNNの表現力とグラフアイソモーフィズム(GI)テストの関連性を確立する。
  論文  参考訳（メタデータ） (2022-05-23T10:22:12Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)

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

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