arXiv cs.LGは6月11日(現地時間)、グラフニューラルネットワーク (GNNs) の性能向上に用いられる位置エンコーディング (PEs) に関する研究成果を発表しました。実務で一般的に採用される「切り詰められた (truncated)」PEの理論的特性について深く掘り下げたもので、完全なPEが理論上同等の表現力を持つとされるのに対し、切り詰められたPEではその表現力に根本的な差異があることが示されました。また、切り詰められたスペクトルPEは1-WLテストよりも強力ではない点も指摘されています。
本研究は、James Flora氏、Mitchell Black氏、Weng-Keen Wong氏、Amir Nayyeri氏らが執筆した論文Understanding Truncated Positional Encodings for Graph Neural Networksの中で明らかにされました。
これまで、スペクトルPEs (Laplacian eigenspacesやeffective resistanceなど) とウォークベースPEs (adjacency matrixの多項式) の二つの主要な位置エンコーディングは、理論上は同等の表現力を持ち、1-WLテストと3-WLテスト間の表現力を有するとされてきました。しかし、この同等性は、グラフニューラルネットワークが計算および空間複雑性においてO(n^3)を要する「完全な」PEsを使用することを前提としています。
実務では、計算コストを理由に最初のk個の固有空間やadjacency matrixの累乗といった「切り詰められた」PEsが一般的に用いられてきましたが、その理論的特性は不明瞭でした。今回の研究は、この切り詰められたPEsの体系的な研究を開始するものです。
理論的な分析の結果、切り詰められた条件下では、いくつかのPEs族が表現力において根本的に異なることが結論付けられました。特に、切り詰められたスペクトルPEsはもはや1-WLテストよりも強力ではないことが示されています。さらに、k-harmonic distancesと呼ばれるスペクトルPEs族を研究することで、密接に関連する切り詰められたPEs間の表現力の違いが強調されています。
実験結果からは、実世界のデータセットにおいては、単一のPEs族を用いるよりも、切り詰められたPEsの組み合わせが好ましいことが示唆されています。本研究はICML 2026で発表される予定です。
参考: arXiv cs.LG — 2026年6月12日 02:58 (JST)