KDD'16 論文採択:省メモリなグラフスケッチのデータ構造

国際学会 KDD 2016 に論文が採択されました.KDDデータマイニング分野の最も有名な会議です.発表は 8 月にサンフランシスコです.オーラル発表有りの採択です.

今回の論文は "Compact and Scalable Graph Neighborhood Sketching" というタイトルで,私が主著であり,研究室で特任技術専門員としてお手伝いしてもらっていた矢野さんとの共著です.内容はグラフ向けデータ構造 All-Distances Sketches の実用上の問題点である空間使用量を大幅に削減するための新しいデータ構造の提案です.以前に「大規模グラフのコンパクトでスケーラブルな全距離スケッチ」というタイトルで人工知能学会の人工知能基本問題研究会にて議論させて頂いていたものです.

背景:All-Distances Sketches とは?

All-Distances Sketches (ADS) は Min-Hash に基づくグラフ向けの乱択スケッチのデータ構造です.グラフ向けのデータ構造は私がずっと注力してきた分野ですが,ADS は数年前に浮上してきて以来ずっと注目してきた技術です.ADS は以下の魅了的な性質を取り揃えています.これらを満たすものはこれまで他にほぼ存在しませんでした.

  • 二点間距離,近接中心性,近接関連性など,様々な指標の推定を行うことができる
  • しかも,かなりの指標の推定において,推定精度に保証がつく
  • 理論的には,空間や構築時間がグラフのサイズにほぼ線形である

詳しくは,IBIS 2014 で講演した際の以下のスライドをご覧下さい.


背景:ADS の問題点

ADS のこれらの魅了的な性質を知った当時の僕は,我先にと飛びついて実装をして試していたのですが,理論的にはほぼ線形であっても,実際にはスケーラビリティがあまり高くないという問題を発見しました.ほぼ線形というのは精度パラメータである k を定数だと考えた場合ですが,実用的には k も無視できない大きさを持つ,などが理由です.

これは実際に IBIS 2014 の講演でも最後のスライドで課題として取り上げています.この頃からずっと問題意識を持っていたんですね.

f:id:iwiwi:20160512142343p:plain


提案手法:Sketch Retrieval Shortcuts

誰かがすぐ解決しそうだと思っていたのですが,意外となかなかいい手法が出てこず,結局僕がやった,というのが今回の研究になります.実際,ADS は繰り返しが少なく切れ目の多いデータ構造なので,汎用の圧縮技術ではほとんど性能が出ませんでした.

そこで我々は,Sketch Retrieval Shortcuts (SRS) というデータ構造を提案しています.SRS は ADS の部分集合ですが,SRS を覚えておけば,1 頂点を指定された時,その頂点の ADS を瞬時に復元できるようになっています.復元した ADS は,オリジナルの ADS と全く同じく推定に使えますので,ADS の持つ推定能力をそのまま引き継ぐことになります.

実験では,数億辺規模のウェブグラフやソーシャルグラフにて性能を確認しています.サイズは数倍〜10倍程度小さく,数ミリ秒で ADS が復元できています.

感想など

ADS は近年浮上してきてから大変注目していた技術だったものの,なかなか自分が研究成果でそこに食い込んでいくことができていなかったので,ようやく ADS に関連した研究を発表できることとなり,とても嬉しいです.現在,他にも ADS に関連した別方面の研究も進めているので,そっちも早くお披露目できるといいなと思っています.