SDM2011でwavelet木を用いた大規模グラフデータベースの高速類似度検索手法について発表しました

4月28日から4月30日に開催されたデーターマイニングの国際会議 SIAM Conference on Data Mining (SDM2011)にてwavelet木を用いた大規模グラフデータベースの高速類似度検索手法について発表してきました。

Yasuo Tabei and Koji Tsuda: Kernel-based Similarity Search in Massive Graph Databases with Wavelet Trees, Eleventh SIAM International Conference on Data Mining (SDM), Arizona, USA, 2011. Link to the paper

本研究では大規模グラフデーターの索引による高速な類似度検索手法を提案しました。近年、グラフデータベースに登録されているグラフの数は大規模化しています。例えば、化合物データーベースには、2千5百万以上の化合物が登録されていて、その数は今も増え続けています。これまでに多くのグラフ類似度検索手法が提案されていますが数百万規模のグラフに応用可能な手法はありませんでした。一方、近年、大規模なグラフを扱う手法はいくつか提案されており、例えば、カーネル法の分野ではグラフをbag-of-wordsに変換するための手法 Weisfeiler-Lehman手続き[1]が提案されています*1。Weisfeiler-Lehman手続きを用いるとグラフ１つあたりノードの個数の線形時間でグラフをbag-of-wordsに変換することができます。提案手法では、Weisfeiler-Lehman手続きを用いてグラフをbag-of-wordsに変換した後で、転置索引に基づくwavelet木により索引付けを行います。クエリーのグラフを検索する場合は、同様にグラフをbag-of-wordsに変換した後で、wavelet木上でクエリーグラフのbag-of-wordsとの共通するワードがある個数以上のグラフをデーターベースから求める問題(semi-conjunctive query)を解くことにより効率よく類似グラフを検索することができます。このsemi-conjunctive queryは、wavelet木の操作であるset intersectionの応用として解くことができ、wavelet木を用いると、各ノードでの操作が集合の要素の総和によらず、集合の個数の線形時間で行うことができ、効率よく木をトラバースすることができす。さらに、我々の手法では検索の効率を上げるために、クエリーグラフに対する類似度の評価式を導出することにより探索空間を枝刈りする工夫も行っています。
詳しくは、論文と下の発表資料を参照してください。

Gwt sdm public

View more presentations from Yasuo Tabei

参考文献
[1] N. Shervashidze and K. M. Borgwardt. Fast subtree kernels on graphs. In Advances in Neural Information Processing Systems, 2010.
[2] S. Hido and H. Kashima. A linear-time graph kernel. In Proc. of the Nineth IEEE International Conference on Data Mining (ICDM2009), pages-179-188 2009
[3] X. Wang, A. Smalter, J. Huan, and G.H. Lushington. G-Hash: Towards Fast Kernel-based Similarity Search in Large Graph Databases. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, pages 472-480. ACM, 2009.

*1:同時期にほぼ同じアイディアでHido and Kashimaの手法[2]とWang et al.,の手法[3]も提案されています。