Parabola JournalMachine Learning

グラフカーネルのメモ

 
Weisfeiler-Lehmanグラフカーネルについてのメモである.特に冒頭のグラフカーネルを俯瞰したイントロあたりを読んで面白かったので力尽きるまで読んだ.あと書いている人はカーネル法の研究者でもなければ,グラフに関した機械学習の研究者でもありませんので,気軽に読んでくださいね(これはいわゆる,マクドナルドで女子高生がXXメソッド).

  • N. Shervashidze et al., Weisfeiler-Lehman Graph Kernels, JMLR, vol. 12, pp. 2539-2561, 2011.

お約束: Preliminary

  • ラベル付きグラフG=(V, E, l),ラベルは自然数とする.
  • N(v)でvの近傍を表す.
  • Walk: edgeの列で,Path: 異なる節点を通るようなWalk(たぶん)
  • 部分木: サイクルを含まない部分グラフ
  • 部分木パターン: 同じ節点を含んでもいいように部分木の概念を拡張したもの(tree-walk)
  • 部分木パターンとは,ある節点からはじめて,その近傍を子に持つように作成した木のこと.しかし,開始地点になったノードも,再び木の下の方に出現する.
  • グラフ同型はラベルを込み込みにした定義とする


主なグラフカーネルの種類へのリンク: Link to Famous Classes of Graph Kernels

注意: 著者の一部変音記号?(アルファベットの上に付くあれ)を省略しました.

Walk Based Graph Kernels
  • H. Kashima, K. Tsuda, A. Inokuchi, Marginalized Kernels Between Labeled Graphs, In Proc. of ICML 2003.
  • T. Gärtner, P. A. Flach, S. Wrobel, On Graph Kernels: Hardness Results and Efficient Alternatives, In Proc. of COLT, 2003.
Path Based Graph Kernels
  • K. M. Borgwardt, H. P. Kriegel, Shortest Path Kernels on Graphs, In Proc. of ICDM 2005.
Limited-size Subgraph Based Graph Kernels
  • T. Horvath, T. Gärtner, S. Wrobel, Cyclic Pattern Kernels for Predictive Graph Mining, In Proc. of KDD 2004.
  • N. Shervashidze, S. V. N. Vishwanathan, T. Petri, K. Mehlhorn, K. M. Borgwardt., Efficient Graphlet Kernels for Large Graph Comparison, In Proc. of AIS, 2009. (GraphletsとはLimited-sizeなサブグラフのこと)
Subtree Patterns Based Graph Kernels
  • J. Ramon, T. Gärtner, Expressivity Versus Efficiency of Graph Kernels, Technical Report of Mining Graphs, Trees, and Sequences, 2003.
  • P. Mahe, J. P. Vert, Graph Kernels Based on Tree Patterns for Molecules, Machine Learning, 2009.

これらのグラフカーネル群の計算コストはいろいろ.

Weisfeiler-Lehman Test of Isomorpshimとは

Weisfeiler-Lehman Kernelの前に,元々Weisfeiler-Lehman Testというものがある.これはNP問題(合ってる?)であるグラフの同型性(同じ構造をしていること)を判定するために大昔の60年代にWeisfeilerとLehmanによって提案された手法である.基本的には,与えられた2つのグラフGとHが同型かどうかを判定するために,それぞれのラベルをひたすら計算し直すような反復を行なって,生成されたラベルの集合が同じものなら同型,そうでなければ同型ではないと返す.この手法は1次元のWeisfeiler-Lahman Testと呼ばれていて,もし同型であればだいたいの場合において正しく動作する,らしい.

基本的な4操作

1. ラベル集合の決定
GとHのすべてのノードvについて,自分自身のラベルl(v)と,その近傍のラベルL(v)={l(u)
u∈N(v)}を集めたもの(多重集合と見なす)を,そのノードのラベルとする.

2. ラベル集合の整列
GとHのすべてのノードvに付けられたラベルの多重集合をソートし,辞書順に小さい順番で並べる.

3. ラベルの圧縮
GとHにおいて今まで出てきていないラベル(まだ使われていない自然数)を付与することで,多重集合に新たな自然数を対応させる.

4. ラベルの付け替え
GとHのすべてのノードvについて,新しく圧縮して作ったラベルを付与する.

この動作を,初期に出現するラベル数|Σ|の半分(n=|Σ|/2)ほど繰り返しても,両方のグラフに新しく作られるラベルの集合が一致していれば,Weisfeiler-Lehman Test of Isomorphismは2つのグラフが(おそらく)同型である,と返し,そうでなければ2つのグラフは同型ではない,と返す.
(非常に簡単な例ながら,下に両方の例を作りました.)

動作例(同型である,と返す)


Wltest 01
2回(=|Σ|/2=4/2)繰り返しても,ラベルの集合は同じなので同型と出力する.

動作例(同型ではない,と返す)


Wltest 02
1回目の手順で,ラベル集合が異なるようになるため,同型ではないと返す.

Weisfeiler-Lehamn Graph Kernelとは

上のWL-Testでやっているラベルの付け替えを与えられたグラフに何度も適用すると,グラフの系列が出来る.もし同型(同じ構造)であれば,同じラベル集合を持つような系列になり,そうでなければラベルの系列も変化していく.このラベルの系列を利用して,WL-Kernelを定義する.

上の一連の操作(手順1~4)をi回繰り返したものをGiと書く.あるグラフGのh-Weisfeiler-Lehman系列を{G0,G1,…,Gh}とする.なお上の2つの例は節点の中にラベルを直接描いているため,この系列の正体は{(V,E,l0), (V,E,l1), …, (V,E,lh)}である.さて,ある既存のグラフカーネルをkとしたとき,Weisfeiler-Lehnman Graph Kernelとは,h-WL系列の各グラフ同士にカーネルを適用したものの和と定義する.

  • k_{WL}^{h,k}(G, H) = k(G0, H0) + k(G1, H1) + … + k(Gh, Hh)
  • よく分からない再生核ヒルベルト空間のお陰で,カーネルの和はカーネルなので,これはカーネル(?論文にはちゃんと定理として解説あります.)
  • 上にリストアップした既存のクラスのグラフカーネルを持ってきて,Weisfeiler-Lehaman Test of Isomorphismと融合したものが,Weisfeiler-Lehaman Grpah Kernelとなる.


おしまい.(論文にはWL-Graph Kernelの具体例が3つ+実験がある).

ところでWeisfeiler-Lehman Kernelというよりも,Weisfeiler-Lehman Test of Isomorphismの解説になってしまってどうしたものか….


あとがきと免責

何か間違っているところ等問題があれば@taki__taki__まで通知してください(修正します).あと勘違いなどしている可能性が高い部分もあるかもしれませんが,責任は負えません,ごめんなさい.

メモ

そのうち続き書く