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