A Structural Smoothing Framework For Robust Graph-Comparison - todo314 @ ウィキ

A Structural Smoothing Framework For Robust Graph-Comparison

• Pinar Yanardag, S. V. N. Vishwanathan
• NIPS 2015

概要だけ

• R-convolutionの問題
  1. 特徴空間がデカイと、自分以外とは類似しにくい（対角優位問題）
  2. 低次数部分構造（ちっちゃい部分グラフ）が分布を占めてしまう
  3. 部分構造は互いに関連しているけど、R-convolutionはEXACTを要求するので微妙
     • Deep Graph Kernelとはここが違うらしい
• 解決法
  • 頻度ベクトルを平滑化する
  • 色んな部分グラフを層っぽい感じに捉えて、関連性で平滑化
• アイデア: Maximum Likelihood Estimateと平滑化
  • p1,p2,…pnみたいな確率分布を見積もりたい場合は、普通はCOUNTINGをする
  • ゼロだらけでやばお
  • Absolute discounting・Interpolated Kneser-Neyなる平滑化手法があるらしい
• これを構造的な部分グラフに頑張って適用する
• 部分グラフをノードとするDAGを作る
  • Graphlet、Weisfeiler-Lehmen、Shortest-Pathについてそれぞれ頑張る
  • 実際は高級そうな事をしている
• 実験
  • 生物学系のデータセットで平滑化するとちょっと良くなった！

まとめ

• 最近のグラフカーネルでこんななのか

NIPS グラフカーネル

2016/12/25