f:id:ssatsuki040508:20181210005017p:plain DSOC研究員の吉村です. 最近はオーザックのバーベキュー味にハマってます. 気づいたら買って食べているので恐ろしい限りです.

今回も引き続き, グラフ構造に関連する機械学習の話をしていきます. まずは, グラフの種類の話から始めて, 次に深層学習に依らない手法に触れていきます. なお, 今回のブログでの記法は基本的に前回のものを踏襲します. 前回のものをまだご覧になっていない方は, まずはこちらをご覧ください.

グラフの種類

グラフには大きく二つの種類があります. 一つが Homogeneous Graph で, もう一つが Heterogeneous Graph です. これらの違いは, 機械学習の問題設定に落とし込む時に適切に考慮することで性能向上に寄与する可能性が高い部分です.

Homogeneous Graph

Homogeneous Graph は, そこに含まれる全てのノードが同様の性質を持っており, 全てのエッジが同じ意味合いの関係を表すグラフです. 例えば, SNS のネットワークなどは Homogeneous Graph の例と考えることができます. (見方によっては, 必ずしもそうとも言い切れないです.)

Heterogeneous Graph

Heterogeneous Graph は, そこに含まれるノードにいくつかの種類があったり, エッジがいくつかの異なる関係を表すグラフです. 例えば, 購買行動のネットワークなどは, ノードについては商品とユーザの二つの異なるノードを考えることになりますし, エッジについてはある商品をユーザが買ったと言う関係や, あるユーザの質問に別のユーザが答えたと言う関係などの意味合いの異なる関係を考えることになります.

グラフ機械学習

グラフ機械学習では, 前回書いたようにノードの分類 (Node Classification) をしたり, エッジの分類 (Edge Classification) をしたり, グラフ自体の分類 (Graph Classification) をしたりと言うタスクが考えられます. 特に, グラフ機械学習のタスクとしてよく知られている, リンク予測 (Link Prediction) は, エッジの分類の特殊な場合 (関係があるかないかの二値分類) と考えることができます. 今回は, 深層学習に依らない手法を概観していきます.

深層学習に依らない手法 (スコアリングやカーネル法)

まずは, 隣接ノードの数 (該当ノードの次数) だけに依存するリンク予測の手法を紹介します. 二つのノード間のなんらかのスコアを定義して, そのスコアがある程度高いものにはエッジを認めるアプローチです. ここでは, Common Neighbor (CN) Score [*1], Adamic-Adar (AA) Score [*2], そして, Resource Allocation (RA) Index [*3] の三つを紹介します. 次に, グラフカーネル [*4]と呼ばれる, グラフ構造に対してカーネル関数を応用することでカーネル法を利用するアプローチを紹介します. グラフカーネルにおける入力は複数のグラフです.

以下では, ノード $i$ の隣接ノードの集合を $\Gamma_i$ で表すことにします.

Common Neighbor (CN) Score

$\displaystyle \lambda_{i,j} = |\Gamma_i \cap \Gamma_j| \tag{1}$

二つのノードが共通の隣接ノードを数多く持っていたら, その二つのノードの間に直接エッジが貼られているだろうと言う仮説を用いており, それがそのまま上記のスコアで表されています.

damic-Adar (AA) Score

$\displaystyle \lambda_{i,j} = \sum_{\gamma \in \Gamma_i \cap \Gamma_j} \frac{1}{\log{|\Gamma_\gamma|}} \tag{2}$

ノードの類似度を元に, 二つのノードが類似していればエッジが貼られているだろうと言う仮説を元にしたスコアです. ここで言っている類似度を表現するために, 共通の隣接ノードを評価しており, 共通の隣接ノードとつながっているノードが少ないほどレアなつながりを共有できていると言うことになるため, それを逆対数を用いて表現しています. これは, 友人の繋がりのネットワークの文脈で提案されています.

Resource Allocation (RA) Index

$\displaystyle \lambda_{i,j} = \sum_{\gamma \in \Gamma_i \cap \Gamma_j} \frac{1}{|\Gamma_\gamma|} \tag{3}$

ほぼ AA と同様ですが, こちらのインデックスでは $\log$ が用いられておりません. このインデックスは, 二つのノード間を隣接ノードを経由して通信することをイメージしており, 類似度を片方のノードからもう片方のノードへ隣接ノードを通って流れ込んでくるリソース量として定義しています. $\log$ を用いていないので, 次数が極端に大きいノードについてはほとんどインデックスからは無視される傾向にあります.

グラフカーネル

グラフカーネルはその名前の通り, カーネル法をグラフに応用する手法です. カーネル法自体については深く立ち入りませんが, カーネル法の利点の一つとして, カーネル関数という特定の性質を満たす関数を二つの構造の間に適切に定義することができれば, どのような構造においても統一的に分類器を作成できるところがあります. そこで, ここではグラフに対するカーネルをどのように定義することができるのかを紹介します. ただし, 数式で書くと複雑になると思うので要点に絞って説明します.

基本的に重要な要素は下記になります.

構造データは, それに含まれる部分構造によって性質が決まると仮定.
全ての共通の部分構造からカーネル関数は定義できる. (畳み込みカーネル)
部分グラフは指数個存在し, 全ての部分グラフを考えるのは非現実的.
グラフの部分構造としてパスを用いることを考える.
カーネル内で数える共通部分はランダムウォークによって生じるパスとする. (ただし無限個ある.)
再起的, かつ, 連立方程式の形に定式化することで効率的に計算が可能.

この手法のターゲットは化合物の物性に関するものなどです. 元の論文では, 化合物を投与した時に変異原性を生じるかどうかなどの実験が行われています.

まとめ

今回はグラフの種類について簡単に触れ, 深層学習に依らない手法についていくつか紹介しました. deep 全盛の時代ですが, 基本を知っておくことで自分なりのアイデアを形にしていけると思います. さて, 次回は現在精力的に研究がなされている, 深層グラフ学習について紹介したのち, グラフの種類ごとにどんなアプローチの違いが出てくるのかを紹介したいと思います. 引き続き, お付き合いください！

▼【ML Tech RPT. 】シリーズ buildersbox.corp-sansan.com

*1:D. Liben-Nowell, and J. Kleinberg, "The link-prediction problem for social networks," JASIST, in 2007.

*2:L. A. Adamic, and E. Adar, "Friends and neighbors on the web," Social networks, in 2003.

*3:T. Zhou, L. Lu, and Y. C. Zhang, "Predicting missing links via local information," EPJ, in 2009.

*4:H. Kashima, K. Tsuda, and A. Inokuchi, "Marginalized kernels between labeled graphs," ICML, in 2003.