Robust Influence Maximization (He-Kempe)

Robust Influence Maximization

  • Xinran He, David Kempe
  • KDD 2016

概要

  • 様々な要因で影響関数が沢山ある
  • min f(S)/f(S*) を最大化し、同時に良い近似を達成したい
  • *対数因子を許すと1-1/e近似
  • 実験したら実はヒューリスティクスも良い

動機づけ

  • Q.何で影響最大化? A.大人気だから
  • 不確実性・雑音の原因
    1. 定義・基準が一杯
    2. モデルは近似でしかない(?)
    3. 人間行動に関して無数の変数がある
    4. データが不完全(API制限・匿名化)
    5. パラメタ推定
  • というわけで、「第一目標として頑健性に注目する事は研究コミュニティにとって必須」

定式化

  • 目的関数 $$ \rho(S) := \min_{\sigma \in \Sigma} \frac{\sigma(S)}{\sigma(S^*_\sigma)} $$
    • ∑: 影響関数の集合(有限/無限)
    • 各影響関数σは単調劣モジュラ
    • $$ S^*_\sigma $$: サイズkのσのマキシマイザ
  • アドバーサリがσを∑から選ぶと思ってもOK
  • 例: Perturbation Interval (摂動区間)
    • $$ p_e \in [l_e, r_e] $$だから∑は非可算無限
    • 実は、任意のSについて、比が最悪となるσは各辺eの確率をl_eかr_eにすると得られる
      • 2^mパタン考えれば良い
  • 確率的 vs. アドバーサリアル
    • 例えば摂動区間で考えると、結局期待値の話になる。あまり意味がない。

近似算法と困難性

  • 定理2 (困難性)
  • $$ (1-\delta)\ln |\Sigma| \cdot k $$頂点で(非自明な)近似比$$ \Omega(1/n^{1-\epsilon}) $$を達成するのは無理 (unless P=NP)
  • 定理3 (近似算法)
  • $$ \beta = 1+\ln |\Sigma|+\ln \frac{3}{\gamma} $$とし、$$ \textsf{Saturate Greedy} $$はサイズ$$ \beta k $$以下の頂点集合$$ \hat{S} $$を見つけ、$$ \rho(\hat{S}) \geq (1-1/e)\rho(S^*) - \gamma $$

ρの計算

  • そもそも比の計算が難しい(>-<)
  • (分母に使う)最適解の代わりに貪欲解を使う
    • $$ (1-1/e)\rho^g(S) \leq \rho(S) \leq \rho^g(S) $$ こんな感じ

$$ \textsf{Saturate Greedy} $$

  • 主戦略: minの最大化→二分探索(二分法)!
  • $$ h^{(c)}_\sigma(S) := \min(c, \frac{\sigma(S)}{\sigma(S^g_\sigma)}), H^{(c)}(S) := \sum_{\sigma \in \Sigma}h^{(c)}_\sigma(S) $$
  • $$ \rho^g(S)\geq c \iff H^{(c)}(S) \geq |\Sigma| \cdot c $$
    • あたり前田のクラッカー
  • $$ H^{(c)} $$は単調劣モジュラ関数なので、$$ \ln|\Sigma| $$-近似の貪欲算法を適用!
  • 実際には、貪欲もc|∑|-εに達したらreturn、二分法の上限-下限<εで打ち切り

ヒューリスティクス

  • $$ \textsf{Single Greedy} $$
    • ρ^gで貪欲…劣モジュラ関数達のminなので保証は無し
  • $$ \textsf{All Greedy} $$
    • $$ S^g_\sigma $$の中で$$ \rho^g $$最大のものを返す
  • どちらも近似比がやばくなる入力を作れる

実験

  • データセット: Twitter・MemeTracker
    • カテゴリ・各月のデータでグラフを作り、辺確率を決め打ち
  • 1.5k頂点(k=10,20,50,100)も選べば、目的関数値≧1になる
  • 可視化してみる…提案手法はまばらな感じで選ぶ
  • 摂動区間で実験すると、不確実性が大きい方が提案手法が優位…せやな
    • こちらは目的関数値が計算大変なので、10サンプルとかで近似

まとめ

  • 手法自体は簡単
  • 問題自体が一定の新規性と影響力を持っているのかな
  • 相手(アドバーサリ)が強いので、複数シード集合選んでも良くないすか?
  • 摂動区間モデルでの目的関数値の効率的な計算(とそうなる最悪時影響関数)がOPEN PROBLEM

KDD 影響最大化 情報拡散 頑健性

2016/12/08

最終更新:2016年12月08日 03:32