グローバル・リードアウトによるGNNの表現力理解に向けて

arXiv cs.LG / 2026/4/28

💬 オピニオンIdeas & Deep AnalysisModels & Research

共有:

要点

この論文は、メッセージパッシング型の集約・合成・リードアウト（ACR）グラフニューラルネットワークの表現力を解析し、表現できる一階（FO）性質に焦点を当てています。
和（sum）集約とグローバル・リードアウトを用いることで、ACR-GNNが論理フレームワークC2では表現できないFO性質まで捉えられることを示し、2026年の既知結果を強化します。
C2に対する厳密な論理的特徴付けを回復するための2つの方策として、ローカル集約を制限する（グローバル・リードアウトは制限しない）方法と、次数を有界にする（グラフサイズは無制限）方法を提案しています。
いずれの場合も、ACR-GNNが捉えるFO性質は「グローバルなカウントモダリティを伴う次数付きモーダル論理」で定義できるものとちょうど一致すると結論づけています。
総じて本研究は、GNNの表現力とC2断片の関係について下限・上限を与え、集約とグローバル・リードアウトの無制限な相互作用がC2を超える表現力を生む、という見取り図を提示しています。