Semi-Supervised Feature Selection for Graph Classification - todo314 @ ウィキ

Semi-Supervised Feature Selection for Graph Classification

• Xiangnan Kong, Philip S. Yu
• KDD 2010

概要

• タイトルのまんま、半教師有りで特徴選択
• ラベル無しグラフも与えられるときに3つの原則に従って、良い部分グラフを選ぶ（探索する）
• 簡単な実験をするとラベル無しグラフを入れることにも意味が有るとわかったよ

提案基準 gSemi

• ラベル(±1)有り・無しグラフがもらえる
• 部分グラフ（パターン）を選んだら、各グラフに対応する出現ベクトル$$x_i$$が得られる

1. Cannot-link: $$ y_i \neq y_j $$なら$$x_i$$と$$x_j$$は*離れて*欲しい
2. Must-link: $$ y_i = y_j $$なら$$x_i$$と$$x_j$$は*近づいて*欲しい
3. Separability: ラベル無し同士なら$$x_i$$と$$x_j$$は*離れて*欲しい

• 結局Laplacianっぽくかけて、
• $$ \max_{\mathcal{T}} \sum_{g_k \in \mathcal{T}} h(g_k, L) $$
  • $$ h(g, L) = f_{g}^\top L f_{g} $$ （f_gは#グラフ次元のgの出現するベクトル）
• 和なので、hの大きい順に取ればOK

提案手法 gSSC

• 頑張りました感：

1. グラフマイニングのよくある探索手法
2. gSemiを元に最適な部分グラフパターンを見つける
3. gSemiの上限を計算して探索空間を削る

実験

• データセット：化合物の抗がん作用（乳・肺・卵巣）、家具物の発がん性（対□□ちゃん）
• 比較手法：提案手法、教師有り（information gain基準）、教師無し（上位k頻出）
• グラフ分類性能
  • 1-NN 分類器、ラベル無しがあると何か改善しましたよ
  • α=β=1でだいたい良さげ
• 探索手法の効率の調査もしてる

まとめ

• 1-NNでいいのかしら…

KDD グラフ分類 特徴選択 頻出部分グラフ

2017/06/18