Linear Graph Miner: 線形グラフのマイニングアルゴリズム

機械学習

データマイニングの国際会議 PAKDD2011に線形グラフのマイニングアルゴリズムに関する論文がアクセプトされました。本研究は、PFIの岡野原さん(@hillbig)、産総研の廣瀬さん、津田さん(@kojitsuda)との共同研究です。
論文をarxiv.orgにアップしました。

LGM: Mining Frequent Subgraphs from Linear Graphs, Yasuo Tabei, Daisuke Okanohara, Shuichi Hirose, Koji Tsuda, The 15th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD2011), link to the paper

線形グラフ(Linear Graph)とは、通常のグラフの頂点に順序がついたグラフです(下図)。自然言語における依存構造関係(Predicate Argument Structure)やタンパク質のコンタクトマップなどさまざまな対象が線形グラフとして表現することができます。

今回はこのグラフのクラスに対して、逆探索法(Reverse Search)[1]を適応することにより列挙アルゴリズムを設計しました。
逆探索法とはマイニングアルゴリズム設計技法の一つで、逆探索法を用いることによりさまざまな対象に対してマイニングアルゴリズムを比較的容易に設計することができます。実験では、設計したアルゴリズムの有効性を示しています。

2011年2月26日 昨年、講演をさせていただいたときの資料を追加しました。

Lgm saarbrucken
View more presentations from Yasuo Tabei.

参考文献
[1] D. Avis and K. Fukuda. Reverse search for enumeration. Discrete Appl. Math., 65:21–46, 1996.