AAAI-14に論文採択 - とどの日記

旅先（WWW'14）での投稿なので，帰国後詳細を書きます．→書きました．(2014/04/14)→更に書き足しました．(2014/04/16)

論文がAAAI-14 (Twenty-Eighth Conference on Artificial Intelligence)に採択されました．

タイトルは``Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations''で，秋葉さん(同研究室)，吉田さん(NII)，河原林先生(NII)との共著で，非常にお世話になりました．一人では不可能でした．

AAAIはその名の通りAIに関する会議なのですが，実に非常に多岐に渡る内容をカバーしていると思います．提出論文数1406，採択論文数398，採択率28%という数字からもその多さがわかると思います．

今回の研究のメインはInfluence Maximization（影響最大化）という情報拡散に関する問題です．2003年に問題が定式化されて[KKT03]からしばらくはこの問題の高速化はなされてこなかったのですが，ここ数年（2009年位）から沢山の手法がCIKM,ICDM,ICDE,KDD,WWW等に出てくるようになりました．

今回の研究の貢献は，Influence Maximizationの高速手法で，既存のヒューリスティクスとほぼ同等の速度かつ理論的保証のある高精度の解を出力します．例えば，LiveJournal(|V|=4.8M, |E|=69M)を約10分で処理できます．今回提出した論文の元となる論文はICDE'14に出したのですが落ちてしまったので，再編しての挑戦となりました．2013年の時点で相当数の手法が提案されていたため，既存手法との明確な差別化が求められていました．さらに，非常に最近になってSIGMOD'14にも新しい高速手法が現れたので，この時点で通ってホッとしています．

Influence Maximizationって何？

日本語に直訳すると影響最大化（問題）になりますが，馴染みのある人は少ないと思います．主なモチベーションはバイラル（感染式）マーケティング[DR01,RD02]といって，少数の人に商品の無料サンプルを渡すことで，その（良い）噂が「口コミ」を通して多数の人に伝わっていくことを期待するものです．ソエンド(http://soen.do/contents/)は関連があると思います．また，馴染みのある近い文脈ではTwitter上のRT等があります．

情報拡散をグラフでモデル化すると，頂点が人，辺が人と人の関係を表します．頂点は活性化（影響された，RTした） or 非活性化（影響されてない，RTしてない）の2状態をもちます．非活性化→活性化には遷移しますが，逆は遷移しません．また，人と人の関係の強さというのは色々違ったりするので，各辺eに重み（確率）p_eを割り当てます．
対象となる情報拡散モデルは最も基本的なIndependent Cascade Model（独立カスケードモデル）[KKT03]というモデルです．このモデルは，最初に活性化させる人の集合（シード）を決めた後，次の確率的な情報拡散過程を繰り返します．

0. シードを活性化．
1. 新たに活性化した人は近傍の（非活性な）人を活性化させる試行を行う．この試行は指定された確率p_eで成功するが，失敗したらそれ以降試行しない．
2. 新たに活性化した人がいれば1.に戻る．

各辺を高々一回しか見ないので，↑の処理は有限時間内に終わります．最初に活性化させるターゲットSに対して平均で何人が活性化するかというのが影響力を表す指標としてとても気になるので，これをσ(S)で表し，influence spread（影響拡散）と呼ぶことにます．

最後にInfluence Maximizationを定式化すると，「有向グラフ・辺の確率・ターゲットの人数kが与えられるので，σを最大化するようなk人のシード集合を求めよ」という問題になります．

近似アルゴリズムとヤバい点

悲しいことに，Influence Maximizationは一般にNP-困難であることが証明されています[KKT03]．さらに，目的関数σの値の厳密計算が#P-困難であることも証明されています[CWW10]．しかし，それぞれの困難は貪欲アルゴリズムとMonte-Carloシミュレーションである程度解決できます．

貪欲アルゴリズム

この問題は目的関数が劣モジュラであるので貪欲アルゴリズムで簡単に1-1/e(≒63%)近似解が得られることが証明されています[NWF78]．
劣モジュラ関数とは，以下を満たす関数です．
$S \subseteq T \subseteq \Omega,\; x \in \Omega,\; f(S+x)-f(S) \geq f(T+x)-f(T)$
または，
$S, T \subseteq \Omega,\; f(S)+f(T) \geq f(S \cup T)+f(S \cap T)$
（等）が成り立つ．前者の意味を限界収穫逓減とか言ったりします．
貪欲アルゴリズムは，今の解をS（最初は空集合）とすると，σ(S+v)-σ(S)が最大となるvを取ってきて，Sに加えるという操作をk回繰り返すだけです．しかも，経験的には実際のネットワークではかなり最適解に近い解が計算できます．

Monte-Carloシミュレーション

Monte-Carloシミュレーションは，先の確率過程を沢山シミュレートして活性化した頂点数の平均値を計算し，σの近似値とします．シミュレーション回数をRとするとこの計算コストはO(mR)です．

ヤバい点

貪欲アルゴリズム+Monte-Carloシミュレーションによるアルゴリズムは63%近似解を出力します．これは嬉しい事ですが，貪欲アルゴリズムはσをkn回計算し，一回σを求めるのにO(Rm)くらいの計算コストがいるので，全体の計算コストはO(knmR)となります．

つまりヤバいのは，目的関数の計算コストと計算回数によって，計算量がグラフサイズの自乗以上になるという点にあります．

ですから，多くの既存手法はσの値を求めることに主眼を置いており，σの値を適当に近似するヒューリスティクスか，σの値をMonte-Carloシミュレーションで精度良く求める手法かに二分されてました．前者は速いけど精度が悪い，後者は精度が良いけど遅い，という問題があります．

貢献

今回の論文の手法はシミュレーションベースに相当します．とにかくシミュレーションを高速化，しかも精度を落とさないところがポイントです．

まず，コインフリップテクニックというテクニックを説明します．これはIndependent Cascade Modelのシミュレーションがランダムグラフ上の到達可能性検査に等価であることを示すものです．ラフに言うと，
1. 各辺が確率1-p_eで消えるようなランダムグラフを沢山生成します．
2. 各ランダムグラフにおいて，頂点集合Sから到達可能な頂点数の平均を計算します．BFSとかで．
で計算した値がσ(S)を近似します．

これだけだと，元のシミュレーションベースのアルゴリズムとほとんど変わらないので高速化手法を導入します．元の貪欲アルゴリズムは最悪計算量がO(kmnR)ですが，直感・実験的には，手法1がRの値を10000から100くらいのオーダーに減らし，手法2がmの値を100未満に減らし，手法3がkを10以下にまで抑える感じです．

高速化手法1: 生成する必要のあるグラフ数をbound

先ほどのように事前にランダムグラフを生成しておくと，毎回シミュレーションをするよりも生成すべきグラフ数（上図のパラメータR）を抑えることができます．このテクニックはStaticGreedy[CSH+13]という既存の手法が提案していましたが，今回はそれに理論的保証を与えました．

高速化手法2: 到達可能な頂点数計算の枝刈り

σ({v})を各頂点vについて求めることを考えます．各頂点からBFSをすれば求められますが，合計でn回BFSするので計算コストは最悪でO(n^2)位になります．ソーシャルネットワークでも，数百万頂点とかになると全然終わらないです．高速化手法では，n回のBFSで冗長な部分は省くことで探索頂点を大幅に減らしています．

高速化手法3: 不必要なゲインの再計算の抑制（省略）

こちらも到達可能な頂点数の計算をできるだけ抑制しています．

参考文献

[CWW10] W. Chen, C. Wang and Y. Wang. Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks. In KDD 2010.
[CSH+13] S. Cheng, H. Shen, J. Huang, G. Zhang and X. Cheng. StaticGreedy: Solving the Scalability-Accuracy Dilemma in Influence Maximization. In CIKM 2013.
[DR01] P. Domingos and M. Richardson. Mining the Network Value of Customers. In KDD 2001.
[KKT03] D. Kempe, J. Kleinberg and É. Tardos. Maximizing the Spread of Influence through a Social Network. In KDD 2003.
[NWF78] G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 1978.
[RD02] M. Richardson and P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In KDD 2002.