Scalable kernels for graphs with continuous attributes - todo314 @ ウィキ

Scalable kernels for graphs with continuous attributes

• ベクトルをノード属性、長さをエッジとして持つグラフのカーネルを提案
• GraphHopper Kernel
  • 同じ長さの最短路のノードの類似度を足し算

• Graph kernel
  • グラフの類似度計算
  • K(G,G') = <φ(G),φ(G')>
  • カーネルトリック！！
• 共通する部分グラフの数をカウントする
  • φ(G) = パス、木、サイクルとかを成分とするベクトル
• 全ての部分グラフをカウントするカーネルはNP-hard
• 色々提案されてる
  • ただし、離散ラベル

• グラフの分類
  • 化合物とか？

• 対象とするグラフ
  • l:E→R+, A:V→R^d
  • 化学・生物学方面に応用

• 既存の
• Shortest path kernel(ICDM 2005)
  • ノード属性の類似度とか何か
• n^4やばい！！！！

• 提案手法
• GraphHopper kernel
• O(n^2m)くらい
• 2つのグラフの同じ長さの最短路上の対応する各ノードのカーネルの和
• 長さjの最短路πでi番目にvが現れる回数、みたいなのとかでエンコード
  • ↑は開始頂点をfixすればてきとーに計算できる

NIPS

2014-01-24 14:18:38 (Fri)