WWW 2017に論文採択 - とどの日記

WWW 2017 (http://www.www2017.com.au/, 26th International World Wide Web Conference) に論文が採択されました。ウェブに関する上位会議として有名であり、投稿論文が966件（昨年比33%増）、採択論文が164件、採択率17%となりました*1。今回の研究はNIIの吉田悠一さんとの共同研究で、タイトルは"Portfolio Optimization for Influence Spread"です。

概要

AAAI'14、NIPS'15、VLDB'16、ECML-PKDD'16に続く影響最大化シリーズですが、今回は期待値最大化では捉えられないリスクの回避が目標です。具体的には、conditional value at risk というリスク尺度を導入し、集合の「ポートフォリオ」を組む問題を定式化しました。さらに、この問題に対し、巧妙な近似アルゴリズムを提案しました。提案手法を用いることで、既存の期待値最大化手法よりもリスクの小さい解が得られます。

期待値最大化のリスク

影響最大化とは、グラフ上の確率的情報拡散モデルにおいて、情報の伝わる人数の期待値が最大となるkシード頂点集合を選択する、という離散最適化問題です。これまで効率的手法が量産されてきたものの*2、「そもそも期待値最大化で良いのか？」という疑問がありました。例えば、期待値的には1,000人に情報が行き渡る戦略があったとしても、もしかしたら、無視できない確率で10人未満にしか情報が行き渡らないかもしれません。論文に載せた以下の図では、拡散サイズが無視できない確率でくすぶってしまう様子が実際に確認できます。

貢献: CVaR最大化問題と近似アルゴリズム

上記の問題を解決するため、本研究は conditional value at risk (CVaR) を最大化することを考えます。CVaRは、金融経済や保険数理の分野で用いられてきたリスク尺度です。直感的には「最悪時α割合の期待値」(今回の設定では、小さい＝悪い)を表します。α=1なら影響最大化と等価です。一般には、影響最大化とは異なり、（集合関数としての）CVaRは単調劣モジュラではありません。また、[Maehara. Operations Research Letters 2015]がCVaR最大化問題に関する厳しい困難性を示しています。（詳しくは前原さんの記事を参照: http://www.maehara-lab.org/?p=561）そこで、単一の集合を選ぶ代わりに、集合の分布を求めるポートフォリオ最適化問題を定式化します。この最適化問題は線形計画として記述できる一方、考えるべき集合の個数が ${|V| \choose k}$ と指数的に大きいため、連続最適化の分野での既存手法は適用できません。これを解決するため、乗算型重み更新法 (multiplicative weights update method) を基にした巧妙な近似アルゴリズムを提案しました。

できたこと

以下は、得られたポートフォリオの情報の伝わる人数（＝カスケードサイズ）の分布図です。Greedy、Degree、Random といった「単一の集合を選ぶ戦略」と比較して、提案手法の分布は集中しており、より望ましいと言えます。実際、CVaRの値が2倍以上改善していることを確認しました。

また、以下のポートフォリオを可視化した図では、コミュニティの中心や周囲に重みを割り振っていることが見てとれます（ $\pi_v$ が単一点からなる集合 $\{v\}$ のポートフォリオ重み）。

*1:8ページ制限になった影響もあると思います。

*2:僕自身も[Ohsaka-Akiba-Yoshida-Kawarabayashi. AAAI'14]で提案しました。