DEIM フォーラム 2014 最優秀論文賞:2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化

DEIM フォーラム 2014 での発表論文が最優秀論文に選ばれ,本日開催されたソーシャルコンピューティングシンポジウム (SoC 2014) にて行われた授賞式に参加しました.後輩の大坂君との共著論文も優秀論文賞を受賞しました.

このような極めて高い評価を頂けたことは身に余る光栄です.私だけでなく,著者グループ全体で見ても DEIM や関連イベントへの参加・投稿経験を持つ者は居ず,我々のような「新参者」であっても公平に高い評価をしてくださるコミュニティに感謝と敬意を表したいと思います.

元々,私の研究の興味は「アルゴリズムとデータ構造」であり,卒論の頃から,アルゴリズムの研究室(東大今井研)を選びずっと所属しています.しかし,アルゴリズムのコミュニティにて重視されるような漸近的な理論解析よりも,私は大規模データ・実性能・社会へのインパクトなどに興味があり,配属当初は(正確には研究室選びの頃から)価値観の違いに悩んでいました.

そんな時,ふとしたきっかけで見つけ感激したのが,SIGMOD'10 の大規模グラフ上の最短経路クエリに関する論文でした.研究の世界をよく知らなかった当時,データベースといえば本当にデータベース自体についてのみ研究をしているのではないかと思い込んでいましたし,かなり不思議にも思いましたが,この論文は自分の興味・価値観に,ばっちり,これ以上ないほど,合致していました.「こういう研究がしたい!」と思い,卒論ではこの論文に基づいた研究を行いました.

そうしてその後も,このブログでも度々報告している通り,データベース関連の国際学会に少しずつ挑戦し,いくつかの論文がお陰様で採択されてきました.ただ,所属する研究室や近隣研究室ではデータベースのコミュニティへの論文投稿の経験を持つ人は殆ど居なかったため,活動はかなりが手探りでした.実際,僕の今までの共著者は,殆どが理論系のアルゴリズム研究者です.そして,実は心の中では,「自分のような研究内容で,胸を張って参加できる研究コミュニティは存在するのだろうか」というような疑問をずっと持ち続けてきました.なにせ,研究内容はグラフアルゴリズムですが,理論解析での貢献は薄いので,アルゴリズムのコミュニティでは高い評価を受けません.一方,データベースの学会に論文を採択して貰ってはいても,グラフアルゴリズムのようなトピックはとても隅っこの方の存在なのではないか,というようになんとなく感じていました.

従って今回の受賞は,受賞だけでも大変嬉しいのですが,このような背景から「僕のようなトピックでもデータベースコミュニティの一員として認めていただけるんだ」と感じられて,とても喜んでいます.これからも,きっと近いスコープで研究を続けていくと思いますので,まだ未熟者ではありますが,どうかよろしくお願いします.

VLDB'14 論文採択:グラフの構造を活用した Personalized PageRank の高速計算

論文が国際学会 VLDB'14 に採択されました.VLDB (International Conference on Ver Large Data Bases) は SIGMOD と並ぶデータベースの最も有名な学会です.学会は 9 月に中国の杭州です.

今回の論文は "Computing Personalized PageRank Quickly by Exploiting Graph Structures" というタイトルで,NII の前原さん,同じ研究室の岩田, NII の河原林先生との共著です.

内容

この論文は大規模なソーシャルネットワークやウェブグラフにおいて Personalized PageRank を高速に計算する手法を提案する論文です.Personalized PageRank は有名な PageRank の一般化です.PageRank が担っていた重要度の計算の他,関連度としても使われ,幅広い応用を持ちます.

今回の提案手法は,Tree-decomposition を拡張した Core-tree-decomposition を用い,グラフの性質を活用して計算を効率化します.

Core-Tree-Decomposition による Core と Whisker の分離

グラフ理論における有名な概念である tree-decomposition (木分解) を拡張した core-tree-decomposition という道具を用いることにより,グラフを Core 部分と Whisker 部分に分離することができます.Whisker 部分は木に類似した構造を持ち,グラフ理論の言葉を用いて言えば treewidth (木幅) が小さいです.一方,Core 部分は密に絡みあっており,グラフ理論の言葉を用いて言えば expander graph に近いです.

Core-Tree-Decomposition の高速な計算

core-tree-decomposition を利用していくための問題点の 1 つとして,計算コストがありました.そこで本論文では,まず,データ構造の工夫により core-tree-decomposition をより高速かつ省メモリに計算するための新たなアルゴリズムを提案しています.

Whisker 部分の処理: LU 分解による Preconditioning

Personalized PageRank の計算は連立方程式の球解に他なりません.ただし,そのままでは LU 分解のような直接法はスケールせず,一般的には反復法が用いられます.

ただし,上記の通り,Whisker 部分は木幅が小さく,これは,この部分に関しては LU 分解が効率的に動作するということを意味します.従って,Whisker 部分に関しては LU 分解により直接的に解を求め,その解を用いて連立方程式を Core 部分のみの問題に帰着します.

Core 部分の処理: GMRES 法

一方,Core 部分は expander graph に近いため,LU 分解のような直接法の性能は絶望的です.しかし,逆に Core 部分は Core 部分で,expander graph に近いという性質を活用し計算を効率化することができます.

通常の Personalized PageRank の計算では基本的な反復法であるヤコビ法や Gauss–Seidel 法が用いられます.しかし,今回提案しているのは,Core 部分には GMRES 法 (generalized minimal residual method) を用いることです.expander graph から来る性質の良い連立方程式において GMRES が効率的に収束することは,理論的にも実験的にも言うことができます.

ここで面白いのは,Core と Whisker の分離を行わないでそのままの連立方程式に適用した時は,GMRES 法はヤコビ法等よりも低速であるという点です.これは,そのままの問題ではあまり性質が良くなく,GMRES の高い収束性能を発揮できず,反復回数で差をつけることができないため,オーバーヘッドの部分で負けてしまうからです.一方,今回は Core 部分を抽出したことにより,オーバーヘッドを加味してもなお GMRES 法が優位に立ちます.

論文採択について

今まで VLDB はとにかく負け続きだったので,第二著者とはいえ,VLDB への初の論文採択は本当に待ち望んでいたものであり嬉しいです.アルゴリズムが面白いという点が査読者にも気に入ってもらえたのが良かったのだと思います.

乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−

本日,PFI セミナーにて「乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩−」というタイトルで話をさせてもらいました.スライドは以下になります.

Ustream の録画もあります.

内容としては,以下の操作を効率的に行うための集合に関するデータ構造 (Sketch) の最近の進歩を紹介しました.

  • 集合の類似度の推定 (Jaccard 係数)
  • 集合異なり数の推定 (distinct counting)

どちらも重要かつ基礎的な操作で,b-bit MinHashHyperLogLog など,既に実用的な手法が提案されており,実際にも使われています.しかし,2014 年になって,Odd SketchHIP Estimator という,これらをさらに改善する手法が立て続けに発表されました.

今日の発表ではこれを踏まえ,まず MinHash の基礎を復習し,次に今まで最も有力な手法であった b-bit MinHash,HyperLogLog の説明をし,最後にこれらの新しい手法を紹介しました.新しい手法は両方とも,新しいアイディアに基づく本質的な改善ながら,手法自体はかなりシンプルなので,実装も困難ではないと思います.是非使ってみて下さい.

今日の発表は主に以下の 2 つの論文に基づいています.より詳しい情報は論文をご参照下さい.

  • Michael Mitzenmacher, Rasmus Pagh, and Ninh Pham. Efficient estimation for high similarities using odd sketches. In WWW 2014.
  • Edith Cohen. All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis. In PODS 2014.

Cache-Oblivious データ構造入門 @DSIRNLP#5

「データ構造と情報検索と言語処理勉強会」にお邪魔して,「Cache-Oblivious データ構造入門」という発表をさせてもらいました.

実はこういうインターネットから集う感じのいわゆる勉強会に参加するのは初めてでした.発表も初めてなので結構緊張していて大変だったのですが,参加者の皆さんがとても優しくて助かりました.懇親会 (新年会) もとても楽しかったです.主催の overlast さん,会場を提供してくださっていたスマートニュースさん,どうもありがとうございました.


発表の内容は以下のような感じです.

  1. DB の索引としての B 木の利点の復習
  2. Cache-Oblivious の考え方
  3. vEB レイアウト (Cache-Oblivious の例)
  4. 実際の事例紹介 (TokuDB)

ちなみに,実況ツイートをしてくださっていた方々の説明が大変良い要約になっています(僕の舌足らずの説明よりよっぽどわかりやすい,ありがとうございます!).ハッシュタグつきのツイートを適当に引用させてもらいます.一方で,データ構造の説明部分は図を見てもらえば結構一発に近いと思うのでそちらを見てもらえればと思います.

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'13CIKM'13ALENEX'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 ですね. その次という順位は結構すごいように思います.このランク付けがどれだけ意味のあるものかという議論の余地は当然ありますが,少なくともこの指標ではこの順位だということに一定の意味はあると思います.

ALENEX'14 に論文採択

国際学会 ALENEX 2014 に論文が採択されました.ALENEX (Meeting on Algorithm Engineering & Experiments) は SIAM によって開催される実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで,理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます.発表は来年の 1 月にアメリカのオレゴンです.

今回の論文は "Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling" というタイトルで,研究室の後輩の河田君,同期の岩田,NII の河原林先生との共著です.タイトルからご察しの通り,SIGMOD'13 論文から続く最短路クエリの手法 Pruned Landmark Labeling (PLL) のシリーズ 3 作目です(SIGMOD'13, CIKM'13 *1, そして今回 ALENEX'14).

内容

今回の論文の題材は,道路ネットワークにおける最短路クエリのアルゴリズムです.前回の PFI セミナーの後半で扱っていたトピックです.

SIGMOD で発表した最初の PLL の論文では,対象とするネットワークをソーシャルネットワークやウェブグラフのようないわゆる「複雑ネットワーク」とし,それらのネットワークの特徴を活用していました.道路ネットワークは,それらのネットワークに対し性質が随分異なる(例えば,とても次数の高いハブのような頂点が存在しない)ので,そのままでは道路ネットワークで高い性能を出すことができませんでした.

そこで,この論文では,道路ネットワークに特化した手法として "Pruned Highway Labeling" を提案しています.この手法は,以下の点が新しいと思います.

  • まず,データの持ち方が進化しています.詳細は省略しますが,今までは純粋に頂点から頂点への距離を保存していたところを,頂点からパスへの距離をうまく保存するようにすることにより,ネットワークに高速道路のような中心的なパスが存在することを活用できるようにしています.
  • ラベルが頂点ベースからパスベースのものとなっていますが,枝刈り Dijkstraアルゴリズムをパス全体から一気に走らせるアルゴリズムにより,パス 1 本分のラベルを一気に効率的に計算できます.


特徴

この手法は,以下のような点で面白いと思っています.

  • 高速道路の活用:複雑ネットワークでは「中心的な頂点(=ハブ)」を活用していたのに対し,道路ネットワークでは「中心的なパス(=高速道路)」を活用します.最近の道路ネットワークの手法は,高速道路をそこまで陽に活用できていませんでした.
  • Thorup の Distance Oracle との類似性以前の PFI セミナーで紹介した通り,理論コミュニティで純粋な理論的計算量を勝負している手法と,実際に実装された際の性能を勝負している手法は,今までかけ離れていました.しかし,今回の手法は,パスにより平面を分割しパスへの距離を保存してゆくという点で,理論コミュニティでの有名な平面グラフの最短路クエリ手法と似たアプローチになっています.

また,今回の論文で,ついに「複雑ネットワーク上の最短路クエリ」「DAG 上の到達可能性クエリ」「交通ネットワーク上の最短路クエリ」という大規模グラフ上のクエリの中で最もよく研究されてきたと言える 3 種類のクエリの研究の歴史に PLL の名前を刻むことができました.今まで,かなりバラバラな手法がそれぞれに独立に開発されてきていたのに対し,ある程度統一的な手法でそれぞれで良い性能が出るというのは,今までに無かったことだと思います.

*1:ちなみにこのブログはまさに CIKM へ発表に来ているところで書いています

ICFP Programming Contest 2013 優勝!


WINNER: UNAGI--THE SYNTHESIS
 
Java, C#, PHP, Ruby and Haskell
are programming tools of choice for discriminating hackers
 
Takuya Akiba, Yoichi Iwata,
Kentaro Imajo, Toshiki Kataoka,
Naohiro Takahashi, Hiroaki Iwami
 
University of Tokyo, Google, Keio University and AtCoder
Japan

8 月に開催された ICFP Programming Contest 2013 の結果が ICFP 2013 で本日発表され,我々は念願の優勝をついに果たしました.これは嬉しい!(事前に知っていましたが,例によって発表まで秘密にするように言われていました.)

写真は現地の imos のツイートより拝借.

ICFP Programming Contest について

ICFP Programming Contest は「なんでもあり」が特徴の,他とは一線を画す特徴的なプログラミングコンテストです.ACM関数型プログラミング言語の学会 ICFP (International Conference on Functional Programming) に伴って毎年開催されていまして (1) プログラミング言語自由 (2) 計算資源自由 (2) チーム人数制限なし (3) 72 時間勝負 (4) 問題の形式も毎年大きく変化,等の特徴があります.優勝者は「その年のプログラミング言語」を決めることとなっており「その年はその言語の文句は言えない」とか.

チームについて

今年は,以下のメンバーで出場しました.(アルファベット順)

  • chokudai
  • imos
  • iwiwi
  • sulume
  • tos
  • wata

チーム名は "Unagi: The Synthesis" です(何故か運営にいつも ":" を "--" に置換される).一応僕はリーダー的な立場でした(=呼びかけをしたのと雑用を多くしただけ).

このチームは,2 年前に準優勝したチーム "Unagi: The Gathering" をベースとしています.その際,優勝者は 301 点だったのに対し準優勝の我々は 300 点でした.準優勝はとても嬉しくはありましたが,一方で 1 点差にとても悔しい思いをしました.

去年は色々あって(主に僕の都合が悪く)一旦チームが崩壊していましたが,そこから,今年出られるメンバーで再集結&新たなメンバーを勧誘して結成したのが今年のチーム "Unagi: The Synthesis" です.今年も(今年は今まで以上に)勝ちに行くことを強く意識して結成しました.全員が他のプログラミングコンテスト (ICPC, TopCoder 等) のバックグラウンドを色濃く持つ一方で,能力のバランス(アイディア力,アルゴリズム実装力,システム実装力,関数型言語等)を考えながら構成しました.

問題と結果について

今年の問題は,Program Synthesis という研究トピックを題材にした,割と真面目な問題でした.一言で言うと,「向こうが秘密のプログラムを持っていて,入力を渡すと出力を返してくれるので,秘密のプログラムを当てる.どれだけ多くの問題を当てられるか」という問題です.詳細はこちら

我々のソルバーは,特に特別な道具 (SAT/SMT ソルバー等) には頼らず,基本的に枝刈り探索+ヒューリスティクスをひたすらチューニングしてきました.色々なバリエーションを作り,それを Amazon EC2 をふんだんに使って分散実行しました.

普段,ICFP Programming Contest はリバースエンジニアリングやショートコーディング等を伴うもっと奇抜な問題が多いのに対し,かなり純粋な問題だったところも,優勝につながった要因だと思います.また,(2 年前からひきずっている)チームの最大の欠点である,メンバーが使える・使いたいプログラミング言語がバラバラというのが余り問題にならなかったのも助かりました.

皆思い思いのプログラミング言語を使ったので,「今年のプログラミング言語」は「Java, C#, PHP, Ruby and Haskell」ということになりました.(多くてちょっとダサいですが,毎年大抵どの言語を指定するかは使った言語にかかわらず指定できるのに対し,今年はアンケートに書いたプログラミング言語がそのまま使われてしまいました.)今年のプログラミング言語たちをよろしくお願いします.

感想など

ICFP Programming Contest に 2 年前から本気で参加するようになったのは,3 年前に尊敬する先輩たちのチーム Pure Pure Code++ が優勝し,とてつもなくかっこ良く感じたというのがあります.この際の先輩方のチームも,ICPCTopCoder 等で名高い方々で構成されたチームで,そういう方々がそういうコンテストだけでなく色々な要素での総合力勝負でも圧倒したところに憧れ,自分もそうなってみたいと思い真面目に参加するようになりました.憧れの優勝についに手が届き,とても嬉しいです.

もちろん,次の目標は連覇です.今回は比較的問われる能力が純粋だった(総合力勝負性が少し低かった)という点もあり,「また勝つ」ということへのモチベーションは失われていないと思います.簡単なことではないと思いますが,どちらにせよ(順位に関わらず)とても楽しいイベントでもありますので,来年も参加したいと思います.

参加中の風景など


期間中は集まってやってました.


序盤(もちろん全完してない)から「全完した」などと意味不明な情報戦を仕掛ける wata.


ボーナス問題が出現すると共に「再集結」したなどとさらなる大嘘を書く wata.



最後は時間が足りなくなってきたので 4 問同時に見守る.


ちなみに,最終的な得点は 1696 点でした.2 位に 100 点程度差をつけての優勝ということです.


全完とはこういうことだったらしいです.