Alternately Optimized Graph Neural Networks(ICML 2023)

Author

Haoyu Hanらのグループ

Link

icml.cc

メモ書き

  • GNNモデルは以下の二つのアルゴリズムからなる
  • 特徴変換…入力特徴を低次元空間に写像するもの。学習可能なパラメタを持つ

  • 特徴伝搬…グラフ構造を利用して情報を伝搬するもの。the message passing scheme を利用するのが多いらしい。

  • 後者はback-propagationを用いるため計算コストが大きい、なんとかしたい

  • 多くの既存研究では学習において二段階の最適化問題を解いている

\begin{align} \rm{min}_{\Theta, \Phi} &{||f_{\Theta}(\mathbf{F}_{L}) - \mathbf{Y}_{L}||}_{F}^{2}, \nonumber \\ \rm{s.t.} \quad \mathbf{F} = \rm{argmin} &{|| g_{\Phi}(\mathbf{X}) - \mathbf{F}||}_{F}^{2} + \lambda \rm{tr} (\mathbf{F}^{\rm{T}}\mathbf{L}\mathbf{F}) \end{align}
  • 本研究では誤差関数を一つに統一し、最適化すべきパラメタ \Thetaと \mathbf{F}のそれぞれについてiterativeに最適化することを提案(ALT-OPT):
\begin{align} \mathcal{L} = \lambda_{1} {||\rm{MLP}(\mathbf{X};\Theta) - \mathbf{F}||}_{F}^{2} + \rm{tr} (\mathbf{F}^{\rm{T}}\tilde{\mathbf{L}}\mathbf{F}) + \lambda_{2}{||\mathbf{F}_{L} - \mathbf{Y}_{L}||}_{F}^{2} \end{align}

  • 左辺第一項はノード特徴 \mathbf{X}をノード表現(潜在変数) \mathbf{F}に写像すること、第二項は \mathbf{F}に拘束条件を課すこと、第三項は \mathbf{F}_{L}と \mathbf{Y}_{L}との間に関係性を持たせること(ふんわりした説明だな！)を目的としている　なおMLPはおそらく多層パーセプトロンのこと。

  • まず \mathbf{F}について最適化(特徴伝搬に相当?)、その後 \Thetaについて最適化(情報変換に相当?)、これを繰り返す。

  • 前者の最適化は依然としてback-propagationを利用するためコストが大きいが、後者の最適化が頑張るためそこまで回数こなさなくても良いらしく、結果として計算コスト改善につながるらしい。

  • 提案誤差関数第二項の \tilde{\mathbf{L}}は正則化グラフラプラシアンだが、これはローパスフィルタとして機能しており、homophily graphなら有用だがheterophilyでは高周波信号が破棄されるため性能が悪くなる恐れがある

  • これに対する対策として、ALT-OPT-Hを提案:

\begin{align} \mathcal{L} = \lambda_{1} {||\rm{MLP}(\mathbf{X};\Theta) - \mathbf{F}||}_{F}^{2} + \rm{tr} (\mathbf{F}^{\rm{T}}{\tilde{\mathbf{L}}}^{2}\mathbf{F}) + \lambda_{2}{||\mathbf{F}_{L} - \mathbf{Y}_{L}||}_{F}^{2} \end{align}

  • 第二項をいじることで高周波成分も通すようになるらしい。最適化手法は前のものと同じ。

  • 結果、計算効率、メモリ効率ともに良いことが理論的に示され、また実験によりラベリング率が低いノード分類問題において有効な性能を示すことが検証された。

感想

  • 最適化問題における誤差関数を一つに統一したのは面白いが、ハイパーパラメタが増えるという欠点がある。うまい設定ならともかく、まずい設定の場合ではどうなのかを知りたい。

  • どこの研究もGraph Transformerに対抗して計算量の削減を頑張っているんだな、と思った。

参考文献