Hatena::ブログ(Diary)

(iwi)の日記

2014-11-11

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

14:30 |  AAAI'15 論文採択:Top-k 最短経路クエリとネットワーク構造予測への応用を含むブックマーク  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 論文などでも扱ってきたように,最短経路・距離の計算は大規模なグラフでも非常に高速に行えるようになってきています.

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

f:id:iwiwi:20141111142907p:image

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


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

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

f:id:iwiwi:20141111142908p:image:w400

ここで "関連度" とダブルクオーテーションで囲っているのは,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 最短経路の長さを計算する提案手法は,簡単に利用して頂ける形のソフトウェアとして近日公開する予定です.グラフ上の頂点ペアを扱う様々な応用で利用して頂けるのではないかと期待しています.是非使ってみて下さい.

2014-10-26

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

13:03 |  ALENEX'15 論文採択:指数時間 Branch-and-Reduce アルゴリズムの実性能を含むブックマーク  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 先生達です.交通ネットワークにおける最短経路クエリヒューリスティクスを理論的に解析する枠組み,コンピュータビジョン系のインスタンスに特化した最大流アルゴリズムの理論的解析など,とても面白い研究をなさっているので,興味がある方はそちらも是非見てみて下さい.

2014-09-22

Microsoft Research Silicon Valley 最後の日を見て

14:44 |  Microsoft Research Silicon Valley 最後の日を見てを含むブックマーク  Microsoft Research Silicon Valley 最後の日を見てのブックマークコメント

f:id:iwiwi:20140823230954j:image:w550

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

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

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

続きを読む

TakagawaU16TakagawaU16 2014/09/23 09:59 MSR SVCは、"高名な"研究者を集め自由な空気で活動させてきたが、際だった成果も無く閉鎖論は以前からあったがBill Gatesの肝いりで開設されたことから、閉鎖の英断が出来なかっただけかと。長く所長を務めて来たGordon Bellも高齢のためか研究心は失せていたように思います。一方、Google X Labは実業に結びつく成果を出し続け、最近では別の研究コンセプトで長期的研究を行うGoogle Y Labまで新設するに至っています。何れも、即戦力となる研究者集団であり、インターンはいなかったと思います。企業研究所という点で見ると、NTTの研究所もMSR SCVと同じように実業に反映する成果を出せていませんから同じ運命を.....かも知れません。

2014-09-03

ICFP Programming Contest 2014 準優勝

02:56 | ICFP Programming Contest 2014 準優勝を含むブックマーク ICFP Programming Contest 2014 準優勝のブックマークコメント

f:id:iwiwi:20140903104903j:image:w400

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

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


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

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

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

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


追記

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

2014-06-21

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

21:35 |  DEIM フォーラム 2014 最優秀論文賞:2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化を含むブックマーク  DEIM フォーラム 2014 最優秀論文賞:2-Hop ラベルの直接的な計算によるグラフ最短経路クエリ処理の効率化のブックマークコメント

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

f:id:iwiwi:20140621202847j:image:w450

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

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

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

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

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