ジャーナル投稿から発行までの期間の統計情報

ジャーナルに投稿してから採択され、発行されるまでにどれくらい要するかがよく分からない。 調べてみたら、American Mathematical Society 提供の数学分野のジャーナルに関する統計情報があった。

Backlog of Mathematics Research Journals

色々書いてあるけど、Current Estimate of Waiting Time between Submission and Publication (in Months) を見れば充分。

  • Print: 投稿から(物理的)印刷されるまでの月数
  • Electronic: 投稿から電子的に発行されるまでの月数(こっちの方が基本早い)

例えば、Information Processing Letters(9ページ制限つきの計算機科学のジャーナル)を見ると、 電子的に発行(i.e., ScienceDirect.comで公開)されるまで平均13ヶ月かかるとある。最初13週だと勘違いした;長い。

他には、Journal of Combinatorial Theory, Series B離散数学、特にグラフ理論・マトロイド理論の最高峰のジャーナル)は30ヶ月かかる。やばい。 試しに、河原林先生の論文[Zdeněk-Kawarabayashi. "Packing six T-joins in plane graphs." J. Combin. Theory Ser. B. 116 (2016): 287--305]を見たら、

Received 30 September 2010, Available online 12 September 2015.

だった。これだけ時間がかかるのであれば、ArXivに先に投稿するのも頷けた。

(そういえば、気づいたら、はてなブログに移行していた。)

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]で提案しました。

独立カスケードについて思ったこと

[Kempe-Kleinberg-Tardos. KDD'03]による影響最大化の定式化の際に情報拡散モデルとして独立カスケードと線形閾値モデルが採用・提案された.

インパクトが大きく,扱いやすかったので,特に独立カスケードは拡張・変種が沢山生み出されている.
一方で,拡散の大きさが実際の分布(例えばTwitterリツイートの大きさ)とは違うと指摘されていることもある.具体的には,確率が高いと双峰性っぽい感じになる.
自分の手法[Ohsaka-Akiba-Yoshida-Kawarabayashi. AAAI'14]はこの性質を(部分的に)利用しているのだけれど,ちょっと気になるので調べてみた.

独立カスケード

  • 入力: 辺確率つきグラフG=(V,E,p),シードs∈V
    • 一般にはシード集合S⊆Vで良い
  • 出力: σ({s}) = E[|Rs|]
    • Rs := sをシードとして独立カスケードをシミュレートした時のvの拡散の大きさを表す確率変数
  • 独立カスケードのシミュレーション
    1. キューにsを入れる
    2. キューが非空な限り
      1. キューから頂点uを出す
      2. uの出近傍vについて
      3. 確率p_uvで次を実行
        1. vが未訪問ならvをキューに入れる
  • ポイントは各辺は高々一回しか見ないということ
    • つまり,確辺eを確率p_eで残した時のランダムグラフ上でsから到達可能な頂点集合と等しい

やったこと

  • 各辺確率を色々変えた時のある頂点の影響の広がり|Rv|の分布を見てみる
  • 確率設定
    • UC(P)モデル: p_e = P
      • 一様に設定する簡単なモデル
    • WC(P)モデル: p_uv = P/indeg(v)
      • 入次数が期待値1なので,線形閾値を模擬している(皆大好き)
  • データセット
  • ランダムに選んだ頂点から割りと影響力が高いものを事前に一つ選び,1,000,000回シミュレーションして,Rvの分布をプロットしてみた結果
    • UC(0.01): 確率が小さすぎるので,特に何も起こらない.
    • UC(0.1): パット見べき分布.ちょっとは広がっているけれど,ネットワークの中心部には到達していない.
    • UC(0.2): はっきりと拡散の大きさが二分されている.ネットワークの中心部に到達するか否かが分かれ目.拡散が小さい方はUC0.1に対応していることが分かる.
    • WC(1): UC(0.1)に似てる.中心部にやはり到達していない?
    • WC(2): キモい.UC(0.2)とかに比べたら,ギャップが滑らか.中心部の方が確率が低い(∵高次数)ので,到達すれば「爆発」というわけでもない.
    • WC(4): ※これだけlog-logスケールでない.とってもわかりやすい形.おそらく低次数の部分の確率が十分に高いので,あとは中心部が爆発するか否かだけが支配的.
  • 拡散が凄く大きくてもべき分布っぽくできるかは少し謎(今回の場合10,000オーバー).
  • 与えられた出現頻度を再現する辺確率設定を復元する,とかは頑張れば出来るのでは…?






KDD 2015

  • (Paper ID: 53) Panther: Fast Top-k Similarity Search on Large Networks
    • Jing Zhang, Tsinghua university; Jie Tang*, Tsinghua University; Cong Ma, Tsinghua; Hanghang Tong, ASU; Yu Jing, Tsinghua; Juanzi Li, Tsinghua University
  • (Paper ID: 54) COSNET: Connecting Heterogeneous Social Networks with Local and Global Consistency
    • Yutao Zhang*, Tsinghua University; Jie Tang, Tsinghua University; Zhilin Yang, Tsinghua University; Jian Pei, Simon Fraser University; Philip Yu, UIC
  • (Paper ID: 77) Online Influence Maximization
    • Siyu Lei, The University of Hong Kong; Silviu Maniu, The University of Hong Kong; Luyi Mo, The University of Hong Kong; Reynold Cheng*, ; Pierre Senellart, Telecom ParisTech
  • (Paper ID: 117) Edge-Weighted Personalized PageRank: Breaking A Decade-Old Performance Barrier
    • Wenlei Xie*, Cornell University; David Bindel, Cornell University; Alan Demers, Cornell University; Johannes Gehrke, Cornell University
  • (Paper ID: 127) Adaptive Message Update for Fast Affinity Propagation
    • Yasuhiro Fujiwara*, NTT; Makoto Nakatsuji, NTT; Hiroaki Shiokawa, NTT; Yasutoshi Ida, NTT; Machiko Toyoda, NTT
  • (Paper ID: 163) MASCOT: Memory-efficient and Accurate Sampling for Counting Local Triangles in Graph Streams
    • Yongsub Lim*, KAIST; U Kang, KAIST
  • (Paper ID: 236) Locally Densest Subgraph Discovery
    • Lu Qin*, UTS; Rong-Hua Li, SZU; Lijun Chang, ; Chengqi Zhang,
  • (Paper ID: 316) Network Lasso: Clustering and Optimization in Large-Scale Graphs
  • (Paper ID: 321) Set Cover at Web Scale
    • Stergios Stergiou*, Yahoo! Labs; Kostas Tsioutsiouliklis, Yahoo! Labs
  • (Paper ID: 342) TimeCrunch: Interpretable Dynamic Graph Summarization
    • Neil Shah*, ; Danai Koutra, Carnegie Mellon University; Tianmin Zou, Carnegie Mellon University; Brian Gallagher, Lawrence Livermore; Christos Faloutsos, Carnegie Mellon University
  • (Paper ID: 411) Integrating Vertex-centric Clustering with Edge-centric Clustering for Meta Path Graph Analysis
    • Yang Zhou*, Georgia Institute of Technology; Ling Liu, Georgia Institute of Technology; David Buttler,
  • (Paper ID: 434) An Evaluation of Parallel -- Eccentricity Estimation Algorithms on Real-World Graphs

Julian Shun*, Carnegie Mellon University

  • (Paper ID: 442) Influence at Scale: Distributed Computation of Complex Contagion in Networks
    • Yaron Singer*, Harvard; Joel Oren, University of Toronto; Brendan Lucier, Microsoft Research
  • (Paper ID: 563) Efficient Algorithms for Public-Private Social Networks
    • Flavio Chierichetti, """Sapienza Univ, Rome"""; Alessandro Epasto, Brown University; Ravi Kumar, Google; Silvio Lattanzi*, Google; Vahab Mirrokni, Google
  • (Paper ID: 621) Improved Bounds on the Dot Product under Random Projection and Random Sign Projection
    • Ata Kaban*, University of Birmingham
  • (Paper ID: 720) Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling
    • Michael Mitzenmacher, Harvard University; Jakub Pachocki, Carnegie Mellon University; Richard Peng, MIT; Charalampos (Paper ID: Babis) Tsourakakis*, Harvard University; Shen Xu , Carnegie Mellon University
  • (Paper ID: 754) A Learning-based Framework to handle Multi-round Multi-party influence maximization on social networks
    • Su-Chen Lin*, National Taiwan University; Shou-de Lin, National Taiwan University; Ming-Syan Chen, Academic Sinica
  • (Paper ID: 921) Deep Graph Kernels
    • Pinar Yanardag*, Purdue; S.V.N. Vishwanathan, UC Santa Cruz
  • (Paper ID: 872) Reciprocity in Social Networks with Capacity Constraints
    • Bo Jiang*, University of Massachusetts Am; Zhi-Li Zhang, University of Minnesota; Don Towsley, University of Massachusetts Amherst

ICDE 2015

  • 004 Finding Dense and Connected Subgraphs in Dual Networks

Yubao Wu, Ruoming Jin, Xiaofeng Zhu, Xiang Zhang

  • 050 Multi-Constrained Graph Pattern Matching in Large-Scale Contextual Social Graphs
  • 073 Multicore Triangle Computations Without Tuning
  • 096 Preserving Privacy in Social Networks Against Connection Fingerprint Attacks
  • 098 Real Time Personalized Search on Social Networks
  • 125 Quick-Motif: An Efficient and Scalable Framework for Exact Motif Discovery
  • 131 Size-Constrained Weighted Set Cover
  • 169 The Safest Path via Safe Zones
  • 208 Scalable SimRank Join Algorithm

Takanori Maehara, Mitsuru Kusumoto, Ken-ichi Kawarabayashi

  • 209 Diversified Top-K Clique Search
  • 211 VENUS: Vertex-Centric Streamlined Graph Computation on a Single PC
  • 225 On Random Walk Based Graph Sampling

Rong-Hua Li, Jeffrey Xu Yu, Lu Qin, Rui Mao, Tan Jin

  • 290 Making Pattern Queries Bounded in Big Graphs
  • 310 A Tale of Three Graphs: Sampling Design on Hybrid Social-Affiliation Networks
  • 400 Asymmetric Structure-Preserving Subgraph Queries for Large Graphs
  • 426 Linear Path Skylines in Multicriteria Networks
  • 458 Dynamic Interaction Graphs with Probabilistic Edge Decay
  • 470 HaTen2: Billion-scale Tensor Decompositions

Inah Jeon, Evangelos E. Papalexakis, U Kang, Christos Faloutsos

  • 504 Bump hunting in the dark: Local discrepancy maximization on graphs
  • 516 Network Motif Discovery: A GPU Approach

Wenqing Lin, Xiaokui Xiao, Xing Xie, Xiao-Li Li

  • 605 Convex Risk Minimization to Infer Networks from Probabilistic Diffusion Data At Multiple Scales
  • 609 Mining Maximal Cliques from an Uncertain Graph

IJCAI-15

  • Paper ID: 81 - A Fast Local Search for Mnimum Vertex Cover in Massive Graphs

Shaowei Cai (Chinese Academy of Sciences)

  • Paper ID: 213 - A Scalable Community Detection Algorithm for Large Graphs Using Stochastic Block Models

Chengbin Peng (KAUST); Zhihua Zhang (n/a); Ka-Chun Wong (n/a); Xiangliang Zhang (n/a); David Keyes (n/a);

  • Paper ID: 671 - Non-monotone Adaptive Submodular Maximization

Alkis Gotovos (ETH Zurich); Amin Karbasi (Yale University); Andreas Krause (ETH Zurich)

  • Paper ID: 945 - Scalable Graph Hashing with Feature Transformation

Qing-Yuan Jiang (Department of CS&T, Nanjing University); Wu-Jun Li (Nanjing University)

  • Paper ID: 1073 - Maximizing the Coverage of Information Propagation in Social Networks

Zhefeng Wang (University of Science and Technology of China); Qi Liu (University of Science and Technology of China); Yu Yang (Simon Fraser University); Yong Ge (UNC Charlotte); Enhong Chen (n/a); Biao Chang (University of Science and Technology of China)

  • Paper ID: 1167 - Analysis of Sampling Algorithms for Twitter

Deepan Palguna (Purdue University); Vikas Joshi (IBM India Research Lab); Venkatesan Chakaravarthy (IBM Research - India); Ravi Kothari (IBM India Research Lab); L Venkata Subramaniam (IBM Research)

  • Paper ID: 1491 - Generalized Transitive Distance with Minimum Spanning Random Forest

Zhiding Yu (Carnegie Mellon University); Weiyang Liu (Peking University); Wenbo Liu (Carnegie Mellon University); Xi Peng (Institute for Infocomm Research (I2R), A*STAR); Zhuo Hui (Carnegie Mellon Univeristy); Vijayakumar Bhagavatula (Carnegie Mellon University);