要約
グラフ上のノード分類タスクは、ノードの近傍を多次に集約することによりノード表現の階層構造を学習する完全に訓練された深層メッセージ伝播モデルを通じて解決されます。クラス内エッジの比率が高いグラフでは効果的ですが、逆の場合、つまり異質性（heterophily）がある場合、このアプローチは課題を抱えています。異質性が高く、同じクラスに属するノードが通常より離れているグラフでは、近傍に基づく平滑化表現は畳み込みモデルによって計算されても効果的でなくなります。これまで、メッセージ伝播モデルのアーキテクチャ変更や入力グラフの再配線による長距離メッセージ伝播の改善が提案されてきました。本論文では、Graph Echo State Network (GESN) を用いて異質性のあるグラフのノード分類における課題に対処します。GESN はグラフ用のリザバーコンピューティングモデルであり、ノード埋め込みは未訓練のメッセージ伝播関数によって再帰的に計算されます。実験結果から、リザバーモデルはアーキテクチャバイアスへの個別の変更や入力グラフに対する前処理として再配線を行うほとんどの完全に訓練された深層モデルと比較して同等かそれ以上の精度を達成できることを示しています。また、効率性と精度のトレードオフにおいても改善が見られます。さらに、分析結果からは GESN がグラフノードの構造的な関係を効果的に符号化できることを示しており、再帰的な埋め込み関数の反復回数とグラフ内の最短経路分布との相関性が確認されています。