要約
近年、Transformerアーキテクチャはグラフ表現学習において注目を集めている。これは、グラフニューラルネットワーク（GNN）が抱えるいくつかの制限を、構造的な誘導バイアス（inductive bias）を厳密に課さず、代わりに位置符号化（positional encoding）によってグラフ構造をのみエンコードすることで自然に克服できる点に起因する。本研究では、位置符号化を用いたTransformerによって生成されるノード表現が、必ずしもノード間の構造的類似性を捉えているわけではないことを示す。この問題に対処するため、新しい自己注意機構（self-attention mechanism）に基づく、シンプルかつ柔軟なグラフTransformer「構造認識型Transformer（Structure-Aware Transformer, SAT）」を提案する。本提案する自己注意機構では、注意計算の前に各ノードを根とする部分グラフの表現を抽出することで、構造情報を元の自己注意機構に組み込む。部分グラフ表現を自動的に生成する複数の手法を提案し、理論的にそれらの表現が部分グラフ表現以上に表現力を持つことを示す。実験的にも、5つのグラフ予測ベンチマークにおいて最先端の性能を達成した。本研究の構造認識フレームワークは、既存の任意のGNNを用いて部分グラフ表現を抽出することができ、ベースとなるGNNモデルと比較して一貫して性能向上を示す。これにより、GNNとTransformerの利点を効果的に統合することに成功した。コードは https://github.com/BorgwardtLab/SAT にて公開されている。