LazyGNN: Large-Scale Graph Neural Networks via Lazy Propagation(ICML 2023)

Author

Rui Xueらのチーム

Link

icml.cc

メモ書き

  • 長距離関係(離れた位置にあるノード同士の関係性のこと?)を捉えることによって性能向上が見られる
  • 従来の手法では、GNNを深層化することによってこれに対処しようとしたが、グラフが大きくなるにつれて計算量が爆発してしまう問題(neighborhood explosion problem)があった
  • これに対する対策はまだまだ制約のあるものが多かった(メモリコスト、性能、サーバ同士の通信確保などなど)
  • 本研究ではそもそも深層化をやめ、浅いGNNのまま長距離依存性を捉えることを目的とする(LazyGNN)
  • 従来のモデルのk番目のiterationにおける初期化/更新式:
\begin{align} \mathbf{X}_{\rm{in}}^{k} &= f\left( \mathbf{X}_{\rm{fea}}, \Theta^{k} \right) \\ \mathbf{X}_{0}^{k} &= \mathbf{X}_{\rm{in}}^{k} \\ \mathbf{X}_{l+1}^{k} &= (1 - \alpha) \tilde{\mathbf{A}}\mathbf{X}_{l}^{k-1} + \alpha \mathbf{X}_{\rm{in}}^{k} \\ \end{align}

に対する検証で、隠れ特徴量 \mathbf{X}_{l}^{k}がすぐに収束しiterationによってほぼ変化していないことがわかった

  • なので、LazyGNNでは真ん中の初期化式を以下のように変更する:
\mathbf{X}_{0}^{k} = (1 - \alpha) \tilde{\mathbf{A}}\mathbf{X}_{L}^{k} + \alpha \mathbf{X}_{\rm{in}}^{k}

  • これにより、前のiterationにおける情報をある程度保持しながら勾配計算を行うことができ、長距離依存性を捉えることができるらしい。

  • backward計算においては、各層の特徴量を保存する必要がなく(従来法ではある)、結果メモリコストの改善につながっている

  • さらにミニバッチ学習(ターゲットノードを中心としたサブグラフによるサンプリング)を導入することによって計算/メモリコストを改善することができる

  • 実験により、LazyGNNは期待通りコストを削減しつつ、他のモデルと比較しても遜色ない予測性能を実現　またミニバッチ学習は予測性能に大きく影響しないことがわかった。

感想

  • 提案手法における初期化の式から長距離依存性を捉えることが本当にできているのか自明ではないなと感じた。第 L層における特徴量には遠距離にいるノードの情報が含まれている、ということだろうか