WWW'14 に論文採択
論文が国際学会 WWW'14 (23rd International World Wide Web Conference) に採択されました！ WWW はその名の通りウェブに関するトップ学会で，比較的新しいものの最近ではかなりの人気を誇る学会だと思います．
WWW の最近の人気は，例えば Microsoft Academic Search の学会ランキングで伺うことができます．最近 5 年に限定すると，なんとコンピュータ科学の全分野合わせても 2 位*1，最近 10 年にしても 3 位ということで，かなり順位が高いです．その分もちろん競争も激しく，採択率は 84/650 = 12.9% だそうです． 所属する河原林グラフ ERATO からもかなりの本数が提出されたようですが，知る限り残ったのは僕の論文だけのようです．
論文タイトルは "Dynamic and Historical Shortest-Path Distance Queries on Large Evolving Networks by Pruned Landmark Labeling" というもので，またもや研究室同期の岩田と NII の吉田さんとの共著になっています．
内容について
論文タイトルからわかるとおり，これまた SIGMOD'13，CIKM'13，ALENEX'14 と出してきた最短路クエリの論文の続きの新編です．今回も対象は大規模なソーシャルネットワークやウェブグラフです．そして，論文タイトルの冒頭になっているとおり，今回は Dynamic と Historical というのが新しい点です．この論文の貢献は主に 2 つあります．
貢献 1: Dynamic Update
今までの最短路クエリではグラフは静的であることを仮定し，グラフの変更を反映するには前計算をしなおす必要がありました．しかし，今回提案する動的更新アルゴリズムを組み込むと，なんとグラフの変更を即座に反映することができるようになります． ちなみに 1 本の枝に対する処理は数ミリ秒で終わります．
ただし，対応しているグラフの変更は今の所残念ながら辺の追加のみです．しかし，現実のネットワークでは辺の追加の方が削除よりも遥かに多いため，実用的にはそれでもかなり価値があるという事を主張しています．今までは再構築をするまで反映されなかった変更が，追加だけとはいえ即座に追加されるのは有用であると思います．
貢献 2: Historical Queries
さらに，データ構造にもう少し情報を入れることにより，最新の状態での距離だけでなく，「昔，時間 t の頃の距離はいくつだったか？」や「距離が変化したのはいつか？」というような質問に答えることができるということを提案しています．
これを使うと，辺に時間の入った大規模なグラフデータにおいて，距離を使った指標がどのように時間経過と共に変化していくかを観察できるようになります．下図はその例です．
(Fig.3 は平均距離と有効直径の変化，Fig.4 は近接中心性の変化，Fig.5 は temporal hop plot です．）
論文採択について
今回の論文も，実は最初に VLDB に投稿して落とされていて，その次で WWW に投稿しました．
この論文に限らず，VLDB では，正直毎回かなり納得の行かない査読コメントと共に落とされています．かなり頭に来たので，今回は DB 分野はもういいかなということで思い切って WWW に投稿するという判断をしました．これは，どうやら正解だったようです．同等の競争率のはずですが，かなり高い評価と共に論文は採択されました．
とはいえもちろん，VLDB に出した原稿をただ WWW に再提出して採択されたわけではなく，かなり念入りに修正をしています．特に，WWW の査読でウケるように，「何ができるか」に重点を起き，上で示した例などを追加しました．また，VLDB で納得してもらえなかった点の議論の防御を強めました．
特に今回は，「更新で削除が対応していない」という点がかなりきつい防御ポイントで，VLDB で落とされたのもその点の影響も大きかったと思います． 「WWW に 5 年で 6 本」で有名な松尾先生も仰っている通り，論文を通すためには失点を少なくすることが重要であり，こういう大きな突っ込まれ得るポイントがあると，例え面白くても「論文を通す」という観点からは結構厳しいです．そのような部分を今回は議論で押し切ることができたというのは少し自信につながり嬉しいです．
*1:1 位は納得の CVPR ですね． その次という順位は結構すごいように思います．このランク付けがどれだけ意味のあるものかという議論の余地は当然ありますが，少なくともこの指標ではこの順位だということに一定の意味はあると思います．
