読者です 読者をやめる 読者になる 読者になる

VLDB'16 論文採択:媒介中心性の動的更新

国際学会 VLDB 2016 に論文が採択されました.VLDB (International Conference on Very Large Data Bases) は SIGMOD と並ぶデータベース分野の最も有名な学会です.学会は来年 9 月にインドのニューデリーです.

今回の論文は "Fully Dynamic Betweenness Centrality Maintenance on Massive Networks" というタイトルで,東大今井研の林くん(主著者),NII の吉田さんとの共著です.我々は DEIM 2015 にて「動的なネットワークにおける媒介中心性の高速計算手法」というタイトルの発表をしており,優秀論文賞を頂くことができました.今回の論文はその論文の続きに相当しますが,いくつかのアイディアの追加により更に大幅に性能が向上しています.

媒介中心性とは?

中心性 (centrality) とは,グラフ上の頂点の重要さを測定する指標のことです.媒介中心性 (betweenness centrality) は最も人気のある中心性の 1 つで,ネットワーク解析を扱う書籍には必ず取り上げられており,実際の解析を行う方々からお話を伺っても,よく話に上がります.コミュニティ検出アルゴリズムの定番である Girvan-Newman アルゴリズムも媒介中心性に基いています.

媒介中心性は,全頂点対の最短経路が通る割合として定義されます(より詳しくは Wikipedia などをご覧下さい).感覚的には,物や情報が「どのぐらいその頂点を通過したいか」で重要度を表す,という気持ちだと思います.実際に実データに適用した際の結果は確かになかなか興味深くて,例えば人間関係のグラフでは,単に友人が多いといよりも,多数のコミュニティに所属するような人物が浮き上がってきます.

媒介中心性に対するアルゴリズム

媒介中心性の厳密な値の計算は,Brandes のアルゴリズムにより O(頂点数 * 枝数) 時間で行うことができ,計算量の意味では,これ以上高速なアルゴリズムは知られていません.(ちなみに,Brandes のアルゴリズムは巧妙な動的計画法に基づく面白いアルゴリズムなので是非調べてみて下さい.)

Brandes のアルゴリズムは,残念ながら,百万頂点を軽く超える現在の大規模なグラフに適用することは困難な計算量を持っています.そこで,大規模グラフでも媒介中心性を使えるようにするため,近年,推定値を高速に計算するアルゴリズムがとても良く研究されてきています.

本論文:動的ネットワークにおける媒介中心性の更新

本論文で扱うのは,動的なグラフにおいて,各頂点の媒介中心性の推定値を更新し続けるという問題です.それを実現する一番単純な方法は,グラフが更新されるたびに,既存の手法で 1 から計算し直す方法ですが,毎回とても時間がかかってしまいます.そこで,グラフに対して付加的なデータ構造を管理しておくことにより,瞬時に媒介中心性の推定値を更新する,というのが本論文で扱うアプローチです.

基本的な考え方としては,グラフの頂点対を幾つかサンプリングし,それらの間の最短経路の DAG による表現を管理します.我々はこれを Hypergraph Sketch と呼んでいます.頂点の追加・削除の際には,一定確率で,偏らせた確率分布を用いてサンプリングを再度行うことにより,サンプルを保ちます.辺の追加・削除の際には,各最短路 DAG を必要に応じて更新します.ただし,最短路 DAG の更新は,それだけを持っている状態では効率的に行うのは難しいです.そこで,両側幅優先探索の途中状態をデータ構造化した Two-Ball Index というデータ構造を別途保っておくことにより,更新が必要な箇所を高速に特定できるようにします.しかし,このデータ構造を用いても,到達不能な頂点対が一定数存在する場合には,とても大きな範囲を無駄に探索することになり性能が著しく低下してしまいます.そこで,大まかに到達可能性を判定できるデータ構造も新たに導入し,それらを組み合わせることにより無駄な探索を抑えています(我々はこれを Special-Purpose Reachability Index と呼んでいます).

我々の実験では,これらのパーツを組み合わせたデータ構造は数十億辺からなるソーシャルグラフやウェブグラフにおいても十分高速に自身のデータ構造と媒介中心性の推定値を更新できました(ただし,性能は要求する精度によります).

感想など

今回作ったデータ構造は,自分の最短経路への愛情をちょっと発揮できた気がして気に入ってます.上述の 3 つのデータ構造は,3 つとも最短路木や最短路 DAG 及びその一部分(+それぞれの付加情報)になってます.最短経路の塊みたいなデータ構造です.

AtCoder 株式会社に入社しました

5 月より AtCoder 株式会社に入社しました.主となる勤務先は国立情報学研究所のままで,兼任としての入社になります.

AtCoder とは?

AtCoderプログラミングコンテストの開催を主な業務とするスタートアップ企業です.設立からそろそろ 3 年で,私を入れてメンバーは現在 3 人になります.社長は書籍「最強最速アルゴリズマー養成講座」などで有名な @chokudai です.ICFP Programming Contest で優勝を果たした際のチームメイトでもあります.

オンラインのコンテスト AtCoder Regular Contest (ARC), AtCoder Beginner Contest (ABC) を土曜日にほぼ毎週開催しています.また,宣伝と採用を兼ねた企業のプログラミングコンテストを,システムのレンタル,問題の作成代行,集客,開催のコンサルティングなどの面でサポートしています(記事1記事2記事3).

また,最近ではエンジニアの採用におけるプログラミング能力の推定と足切りの支援にも取り組んでいます.

なんで AtCoder

プログラミングコンテストは,間違いなく自分の人生に最も大きな影響を与えたものです.プログラミングコンテストで育った者として,今後はコミュニティへの恩返し,即ちコミュニティの活発化や優秀な人材の発掘・育成などの活動を行っていく責務を負っていると考えています.私は,AtCoder との兼任を通じてこれを果たしていきたいと考えています.

私はこれまで,アルバイトやインターンといった立場で,Broadtail, Preferred Infrastructure といった先輩達のスタートアップ企業に関わり,その成長を見てきました.少数精鋭のスタートアップ企業が自ら道を切り拓き世の中にインパクトを与えることに強く魅力を感じています.

AtCoder はまだ小さいチームですが,既にコミュニティ内外に大きな影響をもたらしています.日本語でのプログラミングコンテストの頻繁な開催は,裾野を大きく広げました.また,プログラミングコンテストに興味を持ってくださる企業さんの数も増えており,就職・転職の機会や賞金額といったような状況は数年前と比べ物にならない状況にあります.

ということで,今後とも私と AtCoder をよろしくお願いします.プログラミングコンテストについてのご相談など,是非ご連絡下さい.

1/30 発売!「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」

書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」が近日中に発売される予定です.会津大の渡部先生が著者で,Short Coding 本の Ozy さんと私が協力としての参加です.どうかよろしくお願いします.

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造


本書はアルゴリズムとデータ構造の入門書です.整列,探索,木構造などをはじめとする基礎的なアルゴリズムとデータ構造を初学者向けに説明します.前提とするのは基礎的なプログラミング能力のみです.コード例では C++ を用いています.

これだけだと,よくある本のように思われるかもしれません.しかし,本書は非常にユニークな特徴として,オンラインジャッジシステムとの密な連携をしています.実装を行い,正しさのチェックを受けてから次に進むことで,基礎を着実に身に付けることのできる本になっています.

(Ozy さんのこちらの紹介記事も是非ご覧になって下さい.より簡潔に売りがまとまってます.)

オンラインジャッジシステムとは?

オンラインジャッジシステムとは,元々,プログラミングコンテストの過去問にオンラインで挑戦できるようにしたシステムです.プログラムを提出すると,自動でコンパイルと実行が行われ,テストケースに対する出力により正誤が判定されます.また,実行時間制限があり,正しいだけでなく,要求される効率で処理が行えるプログラムを作成する必要があります.

オンラインジャッジシステムは古くから UVA, POJ, SPOJ など世界中で多くのものが作られ運用されてきました.日本のものでは会津大の Aizu Online Judge (AOJ) が最も大きく有名なオンラインジャッジシステムの 1 つです.AOJ は以下のような特徴を持ち,日本人を中心として人気が高く,日々活発に用いられています.

  • 日本人が作成した問題が重点的に収録されている
  • API が公開されており,サードパーティ製のアプリケーション・サービスが数多く存在
  • コンテストの過去問のみならず,プログラミングやアルゴリズムの初学者向けの基礎問題コースを持つ



(AOJ の画面)

本書のオンラインジャッジシステムとの連携

さて,何を隠そう,本書の主著者は AOJ を作成され管理されている会津大学の渡部先生です.従って,言わずもがなですが,本書では AOJ と連携しています.しかも,AOJ 管理者の先生によって書かれた本ゆえに,非常に密な連携が実現されています.

本書は,前述した AOJ のアルゴリズム初学者向け基礎問題コースに沿っています.アルゴリズムの基礎的な説明と問題の紹介・解説を交互に繰り返して進んでいきます.できれば,AOJ 上で実際に問題を解きながら進めていってもらいたいと考えています.



(AOJ の基礎問題コース)

オンラインジャッジシステムを用いる意義

アルゴリズム入門書がオンラインジャッジシステムと連携する意義は非常に大きいと思います.実装をしてみることは,アルゴリズムをよりよく理解するための近道です.しかし,アルゴリズムやデータ構造の実装は,落とし穴だらけのことも多く,間違った実装で満足してしまう場合もしばしば見受けられます.一方,本書でアルゴリズムの学習を進めていけば,オンラインジャッジシステムとの連携により,正しく実装できたかをチェックしながら進むことができます.

ちなみに,タイトルでは「プログラミングコンテスト攻略のための」ということになっています.プログラミングコンテストでは,アルゴリズムを自在に応用できるよう十分理解すること,そしてアルゴリズムを正しく実装することが重要です.また,一部のアルゴリズムは,コンテスト本番で「ライブラリ」として用いられるように,自分で実装した後で蓄えておけるようなものとなっています.従って,この本はプログラミングコンテストを目指す初心者にお勧めだと思います.一方,個人的には,このブログでここまで紹介してきました通り,プログラミングコンテストには特に興味がないような方にも勧めできる本だと考えています.

目次

既存の本に対する位置づけ

プログラミングコンテストチャレンジブック

拙著「プログラミングコンテストチャレンジブック」はアルゴリズムとデータ構造の入門書ではありません.既存の本で説明されてこなかったプログラミングコンテストにおけるアルゴリズムの設計・活用に重点を置くため,入門書で解説されるような基礎知識の説明は省いていました.従って,アルゴリズムとデータ構造の基礎知識に自信がない方は,プログラミングコンテストチャレンジブックの前に本書を読んでいただけると良いと思います.

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

オンラインジャッジではじめるC/C++プログラミング入門

渡部先生の前著「オンラインジャッジではじめるC/C++プログラミング入門」では,オンラインジャッジを用いた同様のアプローチでプログラミング言語 C/C++ を学ぶことができます.本書はその続編とも言えますが,本書だけで独立して読んでいただけるようになっています.

オンラインジャッジではじめるC/C++プログラミング入門

オンラインジャッジではじめるC/C++プログラミング入門

Short Coding 〜職人達の技法

オンラインジャッジでは,解いた問題数などで努力が可視化されるため,つい競う心が生まれ学習が促進されるという一面があります.一方,本書のもう一人の協力者 Ozy さんの著書「ショートコーディング 職人達の技法」では,オンラインジャッジの変わった楽しみ方として,コードの長さをどれだけ短くできるかの競争を扱っています.

AAAI'15 論文採択:Top-k 最短経路クエリとネットワーク構造予測への応用

国際学会 AAAI 2015 に論文が採択されました.AAAI は人工知能分野の最も有名な会議の 1 つです.発表は来年の 1 月にアメリカのオースティンです.AAAI への論文採択は 2 年連続となります.

今回の論文は "Efficient Top-k Shortest-path Distance Queries on Large Networks by Pruned Landmark Labeling" というタイトルで,研究室後輩の林くん,京大の則さん,研究室同期の岩田,NII の吉田さんとの共著です.内容は,グラフにおける Top-k 最短経路を高速に計算するためのスケーラブルなインデクシング技法の提案,及びそのネットワーク構造予測への応用です.特に,応用面のインパクトを示す試みを論文内に入れることができたのが大変気に入っています.

背景:ネットワーク上の 2 点間の関連度推定に関する課題

グラフにおける 2 頂点間の関連度・類似度の強さを推定することは様々なタスクにおける基礎的な処理です.最も基礎的な関連度指標はグラフ上の距離(最短経路の長さ)です.私の SIGMOD 2013 論文などでも扱ってきたように,最短経路・距離の計算は大規模なグラフでも非常に高速に行えるようになってきています.

しかし,距離は関連度の指標としては構造をいまいち上手く捉えられません.例えば,下図のようなグラフを考えてみましょう.黒い頂点同士の距離は同じですが,直感的には関連度が同じ強さだとは思えません.

そこで,距離よりも構造を把握できる関連度指標として Random Walk with Restart (RWR)SimRank などの指標が提案され使われてきました.しかし,学習や評価のために大量のペアに対する関連度を評価しなければならない場合や,ネットワークを加味した検索サービスの応答のために数多くのペアに対する関連度を瞬時に評価しなければならない場合などを考えた場合,そういった指標に対するアルゴリズムはスケーラビリティ,クエリ応答速度,あるいは精度のいずれかに課題があります.

新たな "関連度" としての Top-k 最短経路

そこで我々は,新たな "関連度" として Top-k 最短経路の長さを用いることを提案します.Top-k 最短経路とは,2 点間のパスのうち短いものから k 本(k はパラメータ)のことです.下表は上図の各グラフに対応しています.Top-k 最短経路の長さが このようなグラフの関連度の違いを識別できることがわかります.

ここで "関連度" とダブルクオーテーションで囲っているのは,Top-k 最短経路の長さは他の指標と異なり 1 つの数ではなく k 個の数のベクトルになるからです.しかし,一部の応用では,これは問題にならず,それどころか有利であると考えています.例えば,機械学習の分類器などの特徴量として用いる場合,特徴ベクトルとして k 個の数を入れれば,その間の調整は問題ごとに分類器に任せることができます.

提案手法:Top-k 最短経路の高速なクエリ応答

上で挙げたような極めて高速な計算が求められる状況でも Top-k 最短経路を用いることができるようにするため,新たなアルゴリズムとデータ構造を提案しています.提案手法は常に正しい Top-k 最短経路を計算します.そして,実験により,千万辺クラスの大規模グラフから索引が構築でき,数十マイクロ秒で 2 点間の Top-k 最短経路が回答できることを示しています(k は数十という想定).

提案手法は SIGMOD 2013 で発表した索引付け手法の拡張になっています.ただし,同じパスを 2 度出してしまわないようにするための工夫やその証明は非自明です.また,安易な拡張を行うと前処理時間や索引サイズが k 倍になってしまうため,それを防ぐための高速化技法複数提案しています.

応用実験:Top-k 最短経路のリンク予測問題における活用

Top-k 最短経路は今までネットワーク上の関連度指標として使われてきませんでした.従って,直感で「実は有用なはずだ」と述べているだけでは説得力は薄いです.そこで,実際のタスクとしてリンク予測問題という有名な問題を取り上げ,Top-k 最短経路の有用性を検証しました.

具体的には,Top-k 最短経路と SVMサポートベクターマシン)を組み合わせたアプローチを他の基礎的なアプローチと比較しました.比較対象として用いたのは,共通近傍数,Jaccard 係数,Adamic-Adar 等の簡単な指標,及びそれらを SVM と組み合わせたものや,SVD (特異値分解), RWR などです.Top-k 最短経路を用いる手法が概ね良好な結果を出すことが確認できました.

感想など

昨年の SIGMOD より続いていた最短経路クエリのシリーズも一応これにて一段落の予定です.感慨深いです.

Top-k 最短経路の長さを計算する提案手法は,簡単に利用して頂ける形のソフトウェアとして近日公開する予定です.グラフ上の頂点ペアを扱う様々な応用で利用して頂けるのではないかと期待しています.是非使ってみて下さい.

ALENEX'15 論文採択:指数時間 Branch-and-Reduce アルゴリズムの実性能

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

今回の論文は "Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover" というタイトルで,研究室同期の岩田との共著です.

背景1:アルゴリズム研究における理論と実性能の乖離

アルゴリズムが好きな人はよく御存知の通り,アルゴリズムの世界には理論(オーダーによる計算量解析)と実性能(実装し実データに適用した際の性能)に大きな乖離があります.これは,理論コミュニティでのアルゴリズムの評価基準が,理論的な計算量の改善を証明できるか否かのみにほぼなっており,本当に実性能が優れているかをほぼ全く考慮しないことによるものです.それ故,「理論的に計算量を改善するアプローチ」と「現実のデータにおける高速化を達成するアプローチ」に大きな違いがある場合も少なくなく,しばしば,理論的なアルゴリズム研究の価値が問われることとなってしまっています.

背景2:厳密指数時間アルゴリズムにおける理論と実性能の乖離

大きな乖離が存在する一つのアルゴリズム研究分野として,探索・最適化のアルゴリズムがあります.

例えば,実際によく用いられている CPLEX や Gurobi などの最適化ソフトウェアは,branch and cut と呼ばれるフレームワークに基づいており,良い cut を導入することによって探索空間を狭めてゆく工夫が中心となっています.一方,理論コミュニティでは branch and cut が扱われることは殆どありません.これは,理論的な計算量の改善を証明することが困難であるからです.

そこで,理論コミュニティでは,計算量の改善が証明可能な異なるアプローチが次々と提案されてきました.その 1 つが,branch and reduce と呼ばれるものです.問題を簡潔化する reduction rule を導入することで,受け取るインスタンスを reduction 済みのものと仮定します.すると,可能性が限定されるため,探索の分岐数を理論的に抑えることができます.例えば,頂点被覆問題では O*(1.212^n) 時間での動作が理論的に保証可能なアルゴリズムがこのアプローチにより提案されています.

(詳しくは岩田のこの資料の P.29 からをどうぞ:指数時間アルゴリズム入門

本論文の内容:branch and reduce アルゴリズムは本当に理論的価値しか持たないのか?

本論文では「こういった branch and reduce のアルゴリズムは本当に理論的価値しか持たないのか?」という疑問に向き合い,そして典型的な予想を裏切るポジティブな結果を提示します.

我々は,頂点被覆問題を例に取り,今まで理論的な価値のみが重視されてきた数々の branch and reduce テクニックを徹底的に盛り込んだ実装を作成しました.そして,様々な現実のインスタンスを用い,branch and cut に基づく CPLEX や branch and bound に基づく MCS アルゴリズム等との比較を行いました.

結果は非常に興味深いもので,インスタンスの種別による得意不得意はあるものの,多くのインスタンスで branch and reduce によるアルゴリズムは(全く cut を用いないにも関わらず)branch and cut に匹敵する性能を達成しました.特に,ソーシャルネットワークやウェブグラフ等の大規模疎グラフにおいては,branch and reduce に基づくアルゴリズムが最も良い性能を示しました.数千万辺・一億辺規模のソーシャルネットワークの最小頂点被覆も厳密に求めることに成功しました.

また,今回の実装は branch and reduce に基づいているため,他の手法と違い,実用上高速なだけでなく理論的に計算量の証明ができることも面白い点です.O*(1.2210^n) 時間で動作することが証明できる他,最良優先探索と組み合わせた場合は O(m 4^k + m√n) 時間で動作することも証明できます(k は integrality gap).

頂点被覆問題が高速に解けて嬉しいのか?

BIP2 と呼ばれるクラスに属する整数計画問題は全て「難しさ」(integrality gap)を保ったまま線形時間で頂点被覆問題に帰着できることが知られています.BIP2 に属する問題は Odd Cycle Transversal, Almost 2-SAT, Split Vertex Deletion, Edge Bipartization, Min SAT, Generalized Vertex Cover, Generalized 2-SAT, ... などなどいっぱい有ります.論文中では Odd Cycle Transversal のインスタンスを用いた実験も行っています.

関連研究・感想など

アルゴリズム研究における理論と実性能の乖離を問題視している研究者は少なくありませんが,その問題に実際に取り組んでいる研究者は残念ながらかなり少ないです.この問題に正面から取り組み成果を挙げているのが,Microsoft Research でお世話になっていた Andrew Goldberg 先生達です.交通ネットワークにおける最短経路クエリのヒューリスティクスを理論的に解析する枠組み,コンピュータビジョン系のインスタンスに特化した最大流アルゴリズムの理論的解析など,とても面白い研究をなさっているので,興味がある方はそちらも是非見てみて下さい.

Microsoft Research Silicon Valley 最後の日を見て

8 月中旬より,インターンとしてマウンテンビューに位置する Microsoft Research Silicon Valley (MSR SVC) に滞在して研究をしていました.期間は 3 ヶ月の予定で,11 月中旬まで居る予定でした.しかし,Microsoft経営判断により MSR SVC の閉鎖が突然決定され,所属チームの方々を含む殆どの研究者は解雇となり,僕の滞在も突如終了になりました.

このショッキングな事件は,英語のみならず日本語のニュースサイトにも取り上げられています.

この異変を偶然にも内側から見た者として,その実態や思ったことについて書いておきたいと思います.ただし,私はあくまでここに 1 ヶ月間滞在していただけの学生に過ぎないことに気をつけていただければと思います.特に,なるべく区別するようにしますが,研究所・会社の考えと私個人の考え・憶測は異なっている可能性があります.

続きを読む

ICFP Programming Contest 2014 準優勝

7 月末に開催された ICFP Programming Contest 2014 の結果がスウェーデンで開催中の学会 ICFP 2014 で発表されたようです.例によって我々は事前にこっそり知らされていましたが,結果は準優勝!

(写真は現地の @esumii 先生にお願いして使わせて頂いています.)


このブログでももう何度か紹介していますが,ICFP-PC は他のプログラミングコンテストよりも圧倒的に「なんでもあり」の世界的なコンテストです.1 つの大きめのタスクにチームで 72 時間取り組み成績を競います.チーム人数,プログラミング言語,計算資源などに一切制限は無く,問題も形式からして毎年大きく異なります.(類似するコンテストとして挙げられるコンテストが皆無で,毎年かなり内容が違うこともあり,人にどのようなコンテストかを説明するのは毎回苦労します.)

今年は,去年優勝を果たした際のチームと同一のメンバーで出場しました.今年もチームの持つ幅広い面での力が発揮でき良かったと思います.チームで良い連携ができると,やっぱり一人でやっているより格段に楽しいです.

「連覇に失敗した」という捉え方をするチームメイトも居ますが,僕は上出来だと思っています.今年の内容は対戦ゲームの AI 作成でした.対戦ゲームはどうしても対戦相手との相性が重要になってくる部分があり,「強い」「弱い」でのランキングというより「多くの AI を倒せる AI」が良い順位を取ることになります.そして勿論その辺まで予測するのは困難ですので,良い順位を取るためには運も必要になってきます.(更に,今年のようなタスクでは評価に用いられるステージの性質も大きく響きますが,今年も評価に使うステージはコンテスト中には公開されませんでした.)

とはいえ,もちろん優勝したかったことには間違いないです.来年がまた楽しみです.

追記

色んなプログラミング言語を使ったのですが,恐らくリポジトリからの統計で,C++ が我々指定の言語という扱いになったようです.というわけで,1 年間 C++ が "a fine tool for many applications" ですのでよろしくお願いします.