Collective Prediction of Multiple Types of Links in Heterogeneous Information Networks (ICDM'14) を読んだ

ICDM14が始まったので興味ありそうな論文をいくつか読んでみようと思う。

概要

色んな種類のノード、エッジがあるネットワーク（Heterogeneous networks）においてリンク予測をする。

論文中で例に挙げられてたネットワークのスキーマ（論文中Fig.2を引用）はこんな感じで、遺伝子とか病気とかの関係が複雑に表されてる。例えばこのネットワークにおいてGeneからDiseaseへのリンクを予測するとかいうタスク。

f:id:yamaguchiyuto:20141217015145p:plain

貢献

Heterogeneous networkにおけるノード間の類似度（RM）を提案
Co-trainingをベースとしたリンク予測手法（HCLP）を提案

手法

ノーテーションが複雑すぎて詳細を理解するのが相当面倒くさいんだけど、概念的にはすごく単純なので概念だけ説明する。

Metapath

あるノードタイプからあるノードタイプへのパスの種類。例えば上の図を使って説明すると "Gene -> Tissue -> Gene" というパスは、始点のGeneと終点のGeneが同じTissueを共有するという意味になる。また、 "Gene -> Disease -> Gene" というパスは始点のGeneと終点のGeneが同じ病気の原因となるという意味になる。これを使うと、同じTissueを共有している遺伝子同士は類似している可能性大だし、さらに同じ病気の原因にもなっている遺伝子同士はもっと類似しているよねということが言える。つまり何が言いたいかというと遺伝子同士（だけでなく同じタイプのノード）のいろんな種類の関係を使ってノード間の類似度を計算したいねということ。

Relatedness Measure (RM)

あるGene AとあるDesease B間のリンクを予測したいとする。この時、いろいろなMetapathを使ってAと類似するGeneの集合SAと、Bと類似するDeseaseの集合SBを見つける。そんでSAのノードからSBのノードへどれくらいの割合でリンクが張られているかを計算する。それがAとBの類似度となる。すごくシンプル。

論文中ではこういうふうに書いてある

PRINCIPLE 1. (Linkage Homophily Principle) Two nodes are more likely to be directly linked if most of their respective similar nodes are linked.

Iterative Framework

あとはもうほぼCo-Trainingやって終わり。簡単。

全てのノードペアについて上記のRMを計算し、それを使ってリンク予測をするSVMを作る
作ったSVMを使って、予測の対象とするノードペアの集合に対してそれぞれリンクがあるかどうか予測する
SVMによる出力値が閾値以上（つまり確信度の高い）のノードペアにはリンクが有ると見なして再度SVMを作る
2-3を決められた回数だけ繰り返す
最終的に出来たSVMによって予測の対象とするノードペアの集合に対してそれぞれリンクがあるかどうか予測、出力

手法のパラメータ多すぎ。

実験

上の図に示した遺伝子やら何やらのデータセット（SLAP*1）を使ったよ
提案した類似度（RM）と他の単純な類似度を比較したよ
提案したリンク予測手法を（HCLP）と、Co-trainingのようにIterationを回さない1-stepの手法を比較したよ
もちろん提案手法が勝ったよ

感想

出たなMetapath！という感じしかしない。このグループの論文はMetapathを使ったいろんな手法を提案しまくってるけどどうもいいイメージがない。アイデアは面白いと思うけど、よく使われてるアルゴリズムとの比較はないし、ノーテーションが複雑すぎて理解するのが面倒くさい。で、何が新しかったんだろうとかんがえると結局Metapathを使ってるだけじゃんとなる（個人の感想です）。

パラメータ多すぎてどう使えばいいのかわからないし、いろんな要因が重なり合っててどこが効いていい結果が出てるのか分からない。最近良く思うことだけど、こういうアドホックな手法（ぱっと見新しくてすごそう）提案しっぱなしの論文は読者に何も知見を与えないと思う。もっとインクリメンタルでいいから一つ一つ検証していきましょうよ。

*1:B. Chen et al., Assesing drug target association using semantic linked data. PLOS Computational Biology, 8, 2012.