Joint Inference of Multiple Label Types in Large Network (ICML'14) を読んだ

ICML14から。数式とか書くのはめんどくさいからアイデアを中心に書く。

概要

ネットワーク上の ノード分類 の話で、各ノードは 複数のラベルタイプを持っている という設定。例えば論文中で使われている例だと、Facebookユーザの出身地、現住所、高校、大学、雇い主の５つのラベルタイプを同時に推定する。

アイデア

提案手法は接続されているノードペアの 多くが出来るだけラベルを共有する ようにノードのラベルを決定する。このやり方がうまくいくことを説明するために既存手法（ラベル伝搬法）がうまくいかない例を挙げる。下の図（論文中Fig. 1）に対してラベル伝搬法を適用すると、u のhometownとcurrent cityはそれぞれ多数決により H と C' と推定される。でもこれだと右の方にいる赤いやつらと u がどのタイプのラベルも共有しないため、 なぜ友達なのかが説明されない という状況になる。普通に考えればある人とある人が友達になるにはなにか理由があるはず。つまり なにかしらのラベルを共有するはず。

ラベル伝搬法と違って提案手法は なぜノードが接続されているか を最大限説明しようとするため、u のcurrent cityの推定結果を C' ではなく C であるとする。こうすることによって、左側のノード達はhometownラベルを共有してるから u と友達で、右側のノード達はcurrent cityラベルを共有してるから u と友達だという説明ができる。著者らはこうすることによってノード分類の精度が上がると考え、実際に精度が上がった。

貢献

• ノード分類（ラベル推定）問題を、ノード間にエッジが張られている理由を説明する 問題に変換した。理由を説明するというのは、接続されているノードペアが共有しているラベルを見つけること。
• スケーラブル（分散可）、高精度のノード分類手法を提案。
• 10億ノードくらいのFacebookグラフを使った実験をし、ラベル伝搬法より精度が高いことを示した。

手法

（数式書くのはめんどくさいので概要だけ書いておく）

一言で言えば、ラベルを共有する接続されたノードペアの数を最大にするように、ノードのラベルを決める。

そういうノードペアの数が多いほど大きくなる目的関数を設計し、それを最大化する。目的関数は凸じゃないから最適化がめんどくさいんだけど、ノードごとに見てやると凸になってるので、ノードごとに目的関数を最大化し、その結果を使って別のノードについて最大化するってのをメッセージパッシング的に繰り返す。

実験

ラベル伝搬法と比較。Facebookのデータを使う（著者らはFacebookの人、ずるい！）。大体勝った（そんなに圧勝はしてない）。

感想

ICMLだけど数式こてこてしてないゆるふわな感じの論文だった。アイデアは面白いし手法もシンプルでよかったんだけど実験ではあんまり良い結果にはなってないように見えた。ICMLとかのガチ機械学習系の論文はあまり読むことはないんだけど、問題定義とかすごくシンプルにかかれてて良い。逆にデータマイニング系はまぁしょうがないとは思うんだけど背景から何からイントロでいろいろ説明しようとするからもうイントロ読むだけでお腹いっぱいになる。