要約
グラフ変換器（Graph Transformers）は、意味のあるアテンションスコアを導出するためには強力な誘導的バイアス（inductive biases）が必要である。しかし、現在の手法は、分子やソーシャルネットワーク、引用ネットワークなど、さまざまなグラフに共通する長距離依存関係、階層構造、コミュニティ構造を十分に捉えられていないことが多い。本論文では、グラフ内のノード間距離を、その多段階的・階層的な性質に着目してモデル化するための、階層的距離構造符号化（Hierarchical Distance Structural Encoding, HDSE）を提案する。さらに、既存のグラフ変換器のアテンション機構にHDSEをシームレスに統合するための新規フレームワークを導入し、他の位置符号化（positional encoding）と併用可能な状態を実現した。大規模グラフへの適用を可能とするため、線形変換器（linear transformers）がグラフの階層構造に適切にバイアスされるよう、高レベルなHDSEをさらに提案する。理論的に、HDSEが最短経路距離よりも表現力および一般化性能において優れていることを証明した。実験的にも、7つのグラフレベルのデータセットにおけるグラフ分類・回帰、および最大10億ノードを有する11の大規模グラフにおけるノード分類において、HDSEを用いたグラフ変換器が優れた性能を示した。