拡散カーネル

拡散カーネル (diffusion kernel) †

グラフのノード間の類似度を表すカーネル．

無向グラフ場合，負のLaplacianは，頂点 \(v_i\) と \(v_j\) の間を要素 \(h_{ij}\) とする 行列 \(H\)：

• 非対角要素では，間に辺があれば \(h_{ij}=1\)，なければ\(h_{ij}=1\)
• 対角要素では，頂点の度数 (連結している辺の数) を \(d_i\) としたとき，\(h_{ij}=-d_i\) この行列を generator という．

このとき，頂点間の類似度を次のGram行列で表すのが拡散カーネル． \[exp(\beta H)=\lim_{n\rightarrow\infty} \sum_{i=0}^n \frac{(\beta H)^i}{i!}\] \(\beta\) は実数でbandwidthパラメータ．

--しましま

関連項目 †

• diffusion kernel
   
• カーネル
• 正定値カーネル
• グラフ
   
• 検索:拡散カーネル

リンク集 †

関連文献 †

• 基本文献
  Risi Kondor and John Lafferty. Diffusion kernels on graphs and other discrete structures. In Proc. 19th Intl. Conf. on Machine Learning, pp.315–322 (2002)
  GoogleScholarAll:Diffusion kernels on graphs and other discrete structures
• Book/学習システムの理論と実現 3.7.3節