論文の概要: Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum

• arxiv url: http://arxiv.org/abs/2506.05530v1
• Date: Thu, 05 Jun 2025 19:26:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-09 17:28:43.206626
• Title: Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum
• Title（参考訳）: 単純なスペクトルを持つグラフ上でのスペクトルグラフニューラルネットワークの不完全性
• Authors: Snir Hordan, Maya Bechler-Speicher, Gur Lifshitz, Nadav Dym,
• Abstract要約: スペクトル機能は、その表現力を改善するために、グラフニューラルネットワーク(GNN)に広く組み込まれている。 簡単なスペクトルグラフ上でSGNNの表現性を向上する手法を提案する。
• 参考スコア（独自算出の注目度）: 2.916558661202724
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Spectral features are widely incorporated within Graph Neural Networks (GNNs) to improve their expressive power, or their ability to distinguish among non-isomorphic graphs. One popular example is the usage of graph Laplacian eigenvectors for positional encoding in MPNNs and Graph Transformers. The expressive power of such Spectrally-enhanced GNNs (SGNNs) is usually evaluated via the k-WL graph isomorphism test hierarchy and homomorphism counting. Yet, these frameworks align poorly with the graph spectra, yielding limited insight into SGNNs' expressive power. We leverage a well-studied paradigm of classifying graphs by their largest eigenvalue multiplicity to introduce an expressivity hierarchy for SGNNs. We then prove that many SGNNs are incomplete even on graphs with distinct eigenvalues. To mitigate this deficiency, we adapt rotation equivariant neural networks to the graph spectra setting to propose a method to provably improve SGNNs' expressivity on simple spectrum graphs. We empirically verify our theoretical claims via an image classification experiment on the MNIST Superpixel dataset and eigenvector canonicalization on graphs from ZINC.
• Abstract（参考訳）: スペクトル機能は、表現力を改善するためにグラフニューラルネットワーク(GNN)に広く組み込まれている。 人気のある例としては、MPNNやグラフ変換器における位置符号化にグラフラプラシア固有ベクトルを用いることがある。 このようなスペクトル強化GNN(SGNN)の表現力は通常、k-WLグラフ同型テスト階層と準同型カウントによって評価される。 しかし、これらのフレームワークはグラフスペクトルとうまく一致せず、SGNNの表現力について限られた洞察を与える。 我々は,SGNNの表現性階層を導入するために,グラフを最大固有値乗法で分類するよく研究されたパラダイムを活用する。 すると、多くのSGNNが異なる固有値を持つグラフでさえ不完全であることを示す。 この欠損を緩和するために、回転同変ニューラルネットワークをグラフスペクトル設定に適用し、単純なスペクトルグラフ上でSGNNの表現性を向上させる方法を提案する。 我々は、MNISTスーパーピクセルデータセット上の画像分類実験とZINCのグラフ上の固有ベクトル正準化により、我々の理論的主張を実証的に検証する。

関連論文リスト

• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Permutation-Invariant Graph Partitioning:How Graph Neural Networks Capture Structural Interactions? [2.7398542529968477]
  グラフニューラルネットワーク(GNN)は、グラフ関連学習タスクの基盤となるための道を開いた。 しかし、グラフ内の構造的相互作用を捕捉するGNNの能力は、まだ解明されていない。 構造的相互作用の学習において,GNNの表現力を効率的に向上する新しいアーキテクチャであるグラフ分割ニューラルネットワーク(GPNN)を提案する。
  論文  参考訳（メタデータ） (2023-12-14T06:08:35Z)
• Spectral Heterogeneous Graph Convolutions via Positive Noncommutative Polynomials [34.74726720818622]
  正のスペクトル不均一グラフ畳み込みネットワーク(PSHGCN)を提案する。 PSHGCNは、有効なヘテロジニアスグラフフィルタを学習するための、単純かつ効果的な方法を提供する。 PSHGCNは目覚ましいスケーラビリティを示し、数百万のノードとエッジからなる大規模な実世界のグラフを効率的に処理する。
  論文  参考訳（メタデータ） (2023-05-31T14:09:42Z)
• Stable and Transferable Hyper-Graph Neural Networks [95.07035704188984]
  グラフニューラルネットワーク(GNN)を用いたハイパーグラフでサポートする信号処理アーキテクチャを提案する。 スペクトル類似性により任意のグラフにまたがってGNNの安定性と転送可能性の誤差をバウンドするフレームワークを提供する。
  論文  参考訳（メタデータ） (2022-11-11T23:44:20Z)
• A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs [13.954735096637298]
  そこで我々は,グラフスペクトルの空間分布がグラフスペクトルに与える影響を解析し,グラフニューラルネットワーク(GNN)の高密度グラフとスパースグラフのノード分類における性能について検討した。 GNNはスパースグラフのスペクトル法よりも優れており、これらの結果を合成グラフと実グラフの両方で数値例で示すことができる。
  論文  参考訳（メタデータ） (2022-11-06T22:38:13Z)
• 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)
• Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs [6.018995094882323]
  グラフニューラルネットワーク(GNN)は、グラフ上の予測タスクのために広く研究されている。 ほとんどのGNNは、局所的ホモフィリー、すなわち地域住民の強い類似性を仮定している。 基本となるホモフィリーによって制限されることなく、任意のグラフを扱うことができる柔軟なGNNモデルを提案する。
  論文  参考訳（メタデータ） (2021-03-26T00:35:36Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs)は、まずグラフ上の特定のマルチホップ演算子でノード機能を拡張する。 我々は,GA-MLPとGNNの表現力の分離を証明し,指数関数的に成長することを示す。
  論文  参考訳（メタデータ） (2020-10-28T17:59:59Z)
• Graphon Pooling in Graph Neural Networks [169.09536309161314]
  グラフニューラルネットワーク(GNN)は、グラフによってモデル化された不規則構造上の信号の処理を含む様々なアプリケーションで効果的に使用されている。 本稿では,グラフのスペクトル特性を保存したグラフオンを用いて,GNNのプールとサンプリングを行う新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-03-03T21:04:20Z)

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

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