論文の概要: Understanding Truncated Positional Encodings for Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2606.13671v1
• Date: Thu, 11 Jun 2026 17:58:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-12 15:55:27.98061
• Title: Understanding Truncated Positional Encodings for Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークにおける整合位置符号化の理解
• Authors: James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri,
• Abstract要約: 位置符号化(PE)はグラフニューラルネットワーク(GNN)のパワーを高める 切断下では、PEのいくつかのファミリーは表現力において根本的に異なる。 提案手法は,実世界のデータセットにおいて,任意の家族に対して,混在したPEが好ましいことを示すものである。
• 参考スコア（独自算出の注目度）: 6.537174583219785
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Positional encodings (PEs) enhance the power of graph neural networks (GNNs), both theoretically and empirically. Two of the most popular families of PEs - spectral (e.g., Laplacian eigenspaces, effective resistance) and walk-based (polynomials of the adjacency matrix) - are theoretically equivalent in expressive power, with expressivity between the 1-WL and 3-WL tests. However, this equivalence assumes the GNN uses the "complete" version of these PEs, which requires $O(n^3)$ time and space complexity. Instead, practitioners commonly use truncated variants of these encodings, such as the first $k$ eigenspaces or powers of the adjacency matrix. However, the theoretical properties of these truncated PEs are unknown. In this work, we initiate the study of these truncated PEs. Theoretically, we show that, under truncation, several families of PEs are fundamentally different in expressive power. As a corollary, we show that truncated spectral PEs are no longer stronger than the 1-WL test. We also study a family of spectral PEs, the $k$-harmonic distances, to highlight the differences in expressive power of even closely related truncated PEs. Finally, we experimentally show that a mix of truncated PEs is preferable to any single family on real-world datasets.
• Abstract（参考訳）: 位置エンコーディング(PE)は、理論上も経験的にも、グラフニューラルネットワーク(GNN)のパワーを高める。 PEの最も一般的な2つのファミリー(例えば、ラプラシア固有空間、有効抵抗)とウォークベース(隣接行列のポリノミアル)は、理論上は1-WLテストと3-WLテストの間の表現力で等価である。 しかし、この同値性は、GNNがこれらのPEの「完全」バージョンを使っていると仮定し、時間と空間の複雑さは$O(n^3)である。 代わりに、実践者は一般に、最初の$k$固有空間や隣接行列の力など、これらの符号化の切り詰められた変種を使用する。 しかし、これらの歪んだPEの理論的性質は分かっていない。 本研究では,これらの乱れたPEの研究を開始する。 理論的には、トランジケーションの下では、PEのいくつかのファミリーは、表現力において根本的に異なることが示される。 その結果,スペクトルPEは1-WL試験よりは強くないことがわかった。 また、スペクトルPE群($k$-harmonic distances)も研究し、より密接な絡み合ったPEの表現力の違いを明らかにする。 最後に,実世界のデータセット上では,どのファミリーよりも混在したPEの方が好ましいことを示す。

関連論文リスト

• Transformers Provably Learn to Internalize Chain-of-Thought [65.41010769606844]
  Implicit Chain-of-Thought (ICoT) は、隠れた状態の中で中間段階を内部化するモデルを訓練する。 Log-ICoTはシンキングトークンを一度に削除し、$k$のリニアから対数へのステージ数を削減します。 多層変圧器の実験により理論が確認され、より深い層に段階的に推論がどのように吸収されるかが可視化される。
  論文  参考訳（メタデータ） (2026-05-27T15:17:06Z)
• Analyzing the Effect of Embedding Norms and Singular Values to Oversmoothing in Graph Neural Networks [12.876488159688506]
  深部グラフニューラルネット(GNN)における過密効果に寄与する要因について検討する。 MASED$は、大域的な上と下の境界を得るために集約される。 深層ネットワークにおける過度なスムース化を減らすことで,浅層ネットワークよりも優れた結果が得られることを示す。
  論文  参考訳（メタデータ） (2025-10-07T15:55:28Z)
• Look Within or Look Beyond? A Theoretical Comparison Between Parameter-Efficient and Full Fine-Tuning [50.05207363001145]
  フルファインチューニング(FFT)に匹敵する性能を実現するPEFT法 最適化理論に基づく表現能力とロバスト性の観点から,PEFTとFFTの特性を比較した。 分類,生成,推論,微調整タスクを含む15のデータセットの実験と,11の逆検定セットによる理論の検証を行った。
  論文  参考訳（メタデータ） (2025-05-28T13:35:12Z)
• Learning Efficient Positional Encodings with Graph Neural Networks [109.8653020407373]
  グラフのための学習可能なPEの新しいフレームワークであるPEARLを紹介する。 PEARL は線形複雑性を持つ固有ベクトルの同変関数を近似し、その安定性と高表現力を厳密に確立する。 解析の結果、PEARLは線形複雑度を持つ固有ベクトルの同変関数を近似し、その安定性と高表現能を厳密に確立することを示した。
  論文  参考訳（メタデータ） (2025-02-03T07:28:53Z)
• Learning interpretable positional encodings in transformers depends on initialization [14.732076081683418]
  位置符号化(PE)は、シーケンス内のトークンの位置と順序を区別する重要な情報を提供する。 学習可能なPEの選択は、解釈可能なPEを学習する能力に大きな影響を及ぼすことを示す。 極小分布から学習したPEは、複数の次元で真実の位置を反映する解釈可能なPEを発見できる。
  論文  参考訳（メタデータ） (2024-06-12T14:37:29Z)
• Hamiltonian Mechanics of Feature Learning: Bottleneck Structure in Leaky ResNets [58.460298576330835]
  ResNets と Fully-Connected Nets を相互接続する Leaky ResNets について「有効深度」に依存して検討する。 この直感を利用して、以前の研究で見られるように、ボトルネック構造の出現を説明する。
  論文  参考訳（メタデータ） (2024-05-27T18:15:05Z)
• Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction [55.57072563835959]
  本稿では,繰り返し入力される固有値の制約からフィルタを解放する固有値補正手法を提案する。 具体的には、提案した固有値補正戦略により、固有値の均一分布が向上し、フィルタの適合能力と表現力が向上する。
  論文  参考訳（メタデータ） (2024-01-28T08:12:00Z)
• How Powerful are Spectral Graph Neural Networks [9.594432031144715]
  スペクトルグラフニューラルネットワーク(Spectral Graph Neural Network)は、グラフ信号フィルタに基づくグラフニューラルネットワークの一種である。 まず、非線形性のないスペクトルGNNでさえ任意のグラフ信号を生成することを証明した。 また、スペクトルGNNの表現力とグラフアイソモーフィズム(GI)テストの関連性を確立する。
  論文  参考訳（メタデータ） (2022-05-23T10:22:12Z)
• Breaking the Limits of Message Passing Graph Neural Networks [6.175401630947573]
  グラフニューラルネットワーク(MPNN)は、スパースグラフに適用する場合のノード数に関して線形複雑である。 本稿では, 固有値の非線形なカスタム関数により, グラフ畳み込みサポートがスペクトル領域で設計されている場合, MPNNは1-WLテストよりも理論的に強力であることを示す。
  論文  参考訳（メタデータ） (2021-06-08T13:26:56Z)

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

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