要約
グラフニューラルネットワーク（GNN）はグラフ学習分野において著しい成果を上げているが、従来のGNNは、GNNの伝搬パラダイムが1次Weisfeiler-Leman（1-WL）グラフ同型性判定アルゴリズムと一貫しているため、1-WLの表現力の上限を突破することができないという課題を抱えている。本研究では、元のグラフを部分グラフによってより容易に区別できるという知見に基づき、構造認識能力を向上させるための新規なニューラルネットワーク枠組み「部分構造感知型グラフニューラルネットワーク（Substructure Aware Graph Neural Networks: SAGNN）」を提案する。まず、元のグラフから辺を連続的かつ選択的に削除することで得られる「カット部分グラフ（Cut subgraph）」を定義する。次に、ランダムウォークによる符号化パラダイムを拡張し、部分グラフにおける根付きノードの帰還確率を用いて構造情報を捉え、これをノード特徴として用いることで、GNNの表現力を強化する。理論的に、本フレームワークが1-WLよりも強力であり、構造認識能力に優れていることを証明した。広範な実験により、本フレームワークの有効性を実証し、既存の代表的なグラフタスクにおいて最先端の性能を達成した。特に、3-WLテストで失敗するグラフにおいても、本フレームワークを搭載したGNNは著しく優れた性能を発揮した。具体的には、ベースラインモデルと比較して最大83%、従来の最先端手法と比較して最大32%の性能向上を達成した。