Deep Graph Representation Learning and Optimization for Influence Maximization(ICML 2023)

Author

Chen Lingらのチーム

Link

icml.cc

メモ書き

  • 影響力最大化(Influence Maximization)について
  • 影響力最大化とは、以下を満たす \tilde{\mathbf{x}} \subseteq Vを探すこと。
\tilde{\mathbf{x}} = \rm{argmin}_{|\mathbf{x}| \leq k} M \left( \mathbf{x}, G; \theta \right)

ここで、 Mは影響拡散モデルであり、 \mathbf{x}を感染させた時にどれぐらいその感染が広がるかを示す。要するに、 k個以下のノードを感染させて感染を広げる時、感染したノード数を最大にする初期ノード集合tex: \tilde{\mathbf{x}} \subseteq Vはどれか？という問題。

  • 従来手法は大きく分けて二つ。非学習ベース(生成モデル系?)と学習ベース。

  • 非学習ベースは明示的に影響拡散モデル Mを定めている。現実世界ではそう単純なモデルで拡散過程が表現できるとは限らない。

  • 学習ベースは与えられたデータから Mを推定する。が、いろいろ制約や限界があるらしい、というよりは結局ヒューリスティックな解法に頼らざるを得ないようだ。

  • 提案手法は、学習フェーズと推論フェーズの二つのフェーズに分けられる。

  • 学習フェーズでは、tex: p(\mathbf{x})を直接学習することは困難なので、代わりに潜在変数 zを用いて p(\mathbf{x}|z)を用いることを提案している。この時、以下のようなオートエンコーダ( \mathbf{x}から zへエンコード、そしてまた \mathbf{x}へデコード)の最適化問題を解いて zを学習する:

\rm{max}_{\phi, \psi} = \mathbb{E} \left[ p_{\phi}(z | \mathbf{x}) p_{\psi}(\mathbf{x} | z) \right ]
  • さらに、影響拡散モデル Mの学習も行う。提案手法では、以下のようにモデルを二つの関数に分解している:
M = g_{r} \circ g_{u} \left( \mathbf{x}, G; \theta \right)

二つの関数[tex: g{r}, g{u}]はそれぞれaggregationとnormalizationを担当しており、出力 yは最終的な情報の拡散を表現する、らしい。

  • 推論フェーズでは、「連続性」と「完全性」という二つの仮定を置いてから潜在変数 zを用いた推論を行う。

  • 連続性…潜在空間上で近い2点は離散空間上でも性質が近い

  • 完全性…潜在空間上でサンプリングされた点はデコードされた時に「意味がある」内容を含む(?)

結局、推論の場を離散空間 \mathbf{x}から連続空間 zに移しただけである。

  • 残念ながらこの手法ではまだまだオーバーヘッドが大きかったらしく、本研究ではさらに「知識蒸留」(Knowledge Distillation)を導入している

  • 知識蒸留とは、スケールの大きなモデル(教師モデル)の持つ情報を比較的小さなモデル(生徒モデル)に伝達する技術のこと。要するに入出力をできるだけ変えないままスケールの小さなモデルに置き換えること

  • これにより、1) \mathbf{x}のエンコード 2)潜在変数 zを拡散モデル内部でaggregate 3)normalizeの3ステップで行なっていた計算を、生徒モデル M_{s}(z; \lambda)により軽量化できる(グラフ情報とかを破棄することで軽量化している)

  • 実験の結果、汎化性能に問題のあるOIMや、スケーラビリティに問題のあるIMINFECTORなどを抑えて優れた成績を発揮した。

感想

  • テーマとしては面白いが、ユースケースが不明だった。マーケティングにおいて影響力のあるノードに広告を打つなどの例が挙げられていたが、そういった人たちは概して案件で宣伝しているし、そもそもグラフ構造と全てのノードの情報が閲覧できる権限を持ちつつ限られたノードにしか広告を掲載できないという状況とは一体…
  • 申し訳ないが個人的には知識蒸留の方が興味が向いた。よりシンプルなモデルで再学習を行うことで、計算量を改善できるのは単純だが面白い。
  • 推論フェーズの「意味のある」内容では何をもって意味としているのだろうか？