Scalable kernels for graphs with continuous attributes (NIPS'13)

田部井さんのスライドを見ればだいたい分かる http://www.slideshare.net/tbyasu/nips2013-scalable-kernels-for-graphs-with-continuous-attributes

  • 問題
    • グラフ同士のカーネル
    • しかもグラフの頂点には連続値ベクトルの属性がついている
    • 辺には重み(長さ)が付いている
  • 既存手法は O(n^4) のなんか微妙そうなやつ
    • 頂点対の対を全通り考える
  • 提案手法 GraphHopper
    • 同じ長さ(頂点数)の最短路同士で類似度を考える
    • 各頂点について長さ k のパスの i 番目に出てくる回数みたいなのが求められればあとは重み付き和になって O(n^2) で求まるようになってる