論文の概要: Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them

• arxiv url: http://arxiv.org/abs/2605.23446v1
• Date: Fri, 22 May 2026 10:01:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-25 17:29:20.300445
• Title: Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them
• Title（参考訳）: Weisfeiler-Lemanは単純なスペクトルグラフに不完全であるので、正規化のテーマ
• Authors: Snir Hordan, Nadav Dym, Tim Seppelt,
• Abstract要約: PRiSMは単純スペクトル固有分解の最初の証明可能な完全正準化である。 DeepSets や Transformer で合成すると、PRiSM は単純なスペクトルグラフ上での普遍近似を達成する。
• 参考スコア（独自算出の注目度）: 15.442114008064877
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number $k$, the $k$-Weisfeiler-Leman ($k$-WL) test cannot distinguish all non-isomorphic graphs with a simple spectrum. As the WL hierarchy upper-bounds the distinguishing power of widely-used Graph Neural Networks (GNNs), this incompleteness applies to all such GNNs, ruling out completeness for every $k$-WL-aligned GNN family. To close this gap, we introduce PRiSM (Partition, Refine, Solve, Match), the first provably complete canonicalization of simple-spectrum eigendecompositions. PRiSM obtains the completeness guarantee that prior canonicalizations provably lack, and resolves the open problem of achieving complete expressivity on simple-spectrum graphs. When composed with DeepSets or a Transformer, PRiSM achieves universal approximation on simple-spectrum graphs, justifying the use of canonicalized Laplacian positional encodings. Empirically, PRiSM performs comparably to or outperforms existing spectral canonicalizations on graph regression, classification, and expressivity
• Abstract（参考訳）: 単純なスペクトルを持つグラフは3次時間同型テストを認めるが、すべての自然数 $k$ に対して、$k$-Weisfeiler-Leman ($k$-WL) テストは単純なスペクトルを持つすべての非同型グラフを区別できないことを証明している。 WL階層は、広く使われているグラフニューラルネットワーク(GNN)の区別力に上限があるため、このような不完全性はすべてのGNNに適用され、$k$-WL対応のGNNファミリに対して完全性を除外する。 このギャップを埋めるために、単純スペクトル固有分解の最初の証明可能な完全正準化である PRiSM (Partition, Refine, Solve, Match) を導入する。 PRiSMは、先行正準化が証明不可能な完全性を保証するとともに、単純スペクトルグラフ上で完全表現性を達成するというオープンな問題を解決している。 DeepSetsやTransformerと組み合わせると、PRiSMは単純なスペクトルグラフ上で普遍的な近似を達成し、正規化されたラプラシアン位置符号化の使用を正当化する。 経験的に、PRiSMは、グラフ回帰、分類、表現性に関する既存のスペクトル正準化を比較または上回る。

関連論文リスト

• Position: Spectral GNNs Are Neither Spectral Nor Superior for Node Classification [10.36868472818283]
  ノード分類のためのスペクトルグラフニューラルネットワーク(スペクトルGNN)は、グラフ上の周波数領域フィルタリングを約束する。 最近の研究は、グラフラプラシア固有ベクトルが一般に真のフーリエ基底の重要な性質を持たないことを示している。 本稿では、ノード分類において、スペクトルGNNはグラフスペクトルを有意に捉えたり、性能を確実に向上させたりしない。
  論文  参考訳（メタデータ） (2026-03-19T16:17:45Z)
• Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum [17.27380476408333]
  スペクトル機能は、その表現力を改善するために、グラフニューラルネットワーク(GNN)に広く組み込まれている。 簡単なスペクトルグラフ上でSGNNの表現性を向上する手法を提案する。
  論文  参考訳（メタデータ） (2025-06-05T19:26:29Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
  スペクトルグラフニューラルネットワーク(GNN)は、スペクトル領域グラフ畳み込みを通じてグラフ表現を学習する。 本稿では、全ての固有値の集合を効果的に符号化し、スペクトル領域で自己アテンションを行うSpecformerを紹介する。 複数のSpecformerレイヤを積み重ねることで、強力なスペクトルGNNを構築することができる。
  論文  参考訳（メタデータ） (2023-03-02T07:36:23Z)
• 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)

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

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