Robust Influence Maximization (Chen+)

Robust Influence Maximization Chen+

Robust Influence Maximization

  • Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, Xuren Zhou
  • KDD 2016

概要

  • 最悪時比を最大化したい
  • 解依存バウンド
  • パラメタ空間をいい感じに狭めるサンプリング手法提案
  • 実際、パラメタ空間が大きいと解が良くないので提案手法が効果的

問題定式化

  • パラメタ空間 $$ \Theta = \times_{e \in E}[l_e, r_e] $$
  • 頑健比 $$ g(\Theta, S) = \min_{\theta \in \Theta}\frac{\sigma_\theta(S)}{\sigma_\theta(S_\theta^*)} $$
  • 問題 $$ S_\Theta^* = \mathrm{argmax}_{S \subseteq V, |S|=k} g(\Theta, S) $$
  • 信頼区間の解釈に仕方
    • 推定した確率ベクトル$$ \hat{\theta} $$と摂動レベル$$ \delta_e $$がある
    • $$ p_e \in [\hat{p}_e-\delta_e, \hat{p}_e+\delta_e] $$と思う
  • 課題
    • Θ(でかすぎ)をそのまま使うと頑健比が微妙
    • 代わりにΘ'を使って良い感じにしたい
    • サンプリングして(したと思って)$$ \Theta' $$と解$$ S' $$を得る s.t.
      1. $$ \theta \in \Theta $$ w.h.p.: 真値θが含まれやすい
      2. $$ g(\Theta', S') $$大: 頑健比が良い

提案手法

  • θは知らない、とりあえずΘの下で最適化する(サンプリングは後回し)

$$ \textsf{LUGreedy} $$ (Lower-Upper Greedy Algorithm)

  1. $$ \theta^- / \theta^+ $$で貪欲して解を2つ得る
  2. $$ \sigma_{\theta^-}(\cdot) $$で見て良い方を返す
    • 最悪時を良くしたい気持ち
  • 定理2:
    • $$ g(\Theta, S_\Theta^{\textsf{LU}}) \geq \alpha(\Theta)(1-\mathrm{e}^{-1}) $$
    • $$ \alpha(\Theta) := \frac{\sigma_{\theta^-}(S_\Theta^{\textsf{LU}})}{\sigma_{\theta^+}(S_{\theta^+}^g)} $$
      • ギャップ比: α(Θ)=(LUGreedyで最適化した影響力)/(最も高い(と思しき)影響力)
      • こいつの評価は簡単
  • 割とそれっぽい尺度です
  • ただし、最悪時頑健比はマジでやばい(頑張る意味が無いレベル)
  • Θを改良するためサンプリング

頑健比

  • 定理3
    1. 仮定無: 頑健比=O(n/k)
    2. 弱い仮定: 頑健比=O(log n/n)
      • [r_e-l_e]=O(1/n)
    3. 色々仮定: 頑健比の期待値っぽい奴=O(log n/√n)
  • 2つのERグラフからなるグラフだと、どう選んでも死ぬ

サンプリング手法

  • Uniform Sampling $$ \textsf{US-RIM} $$
    • "max|確率の差|<δ→|影響力の差|<mnδ"とかそういう感じの保証
    • 各辺をt回サンプリングして推定した$$ (p_e\pm \delta_e)_e $$でLUGreedy
  • Non-uniform & Adaptive Sampling $$ \textsf{ICS-RIM} $$
    • 大事そうな辺を重点的にサンプリングする
    • 重点的: 今ある解からシミュレートして見た辺

実験

  • US-RIM, ICS-RIM, OES-RIM(シードの出辺だけサンプリング)を比較
  • 頑健比の上限
    • どれかθを(ヒューリスティクスで)決めて、上限をとれる
  • いい感じでしたねー、不確実性が頑健比にクリティカルに影響しますね―等

まとめ

  • こういう解依存のバウンドと、そのパラメタの解析でいい感じに何か出来るんかな

KDD 影響最大化 頑健最適化

2016/12/11

最終更新:2016年12月12日 18:44