AAAI2015で発表した - でかいチーズをベーグルする

AAAI2015で発表してきた。タイトルは"OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation"。必殺チェアーからの質問による時間稼ぎは出ずにちゃんと聞いてくれてる人たちから質問が出たから良かったかな。

今回はソーシャルネットワークにデータを限らずに出来るだけ広範囲のグラフに適用できるアルゴリズムを提案した。話を一般的にしようとすればするほど大変だといういい経験が出来た。ドメインに特化した問題を解くアルゴリズムももちろん重要だけど、やっぱりいろんなデータに対して適用できるアルゴリズムを提案するってのはその分野の発展にも寄与できるしもっと重要だと思う。

OMNI-Prop: Seamless Node Classification on Arbitrary Label Correlation from Yuto Yamaguchi

概要

グラフ上のノード分類問題を解くアルゴリズムを提案した。一部のノードにラベルが付いたグラフを入力として、ラベルがついていないノードのラベルを推定して出力する。ラベルってのは例えばソーシャルネットワークだったらユーザの年齢、性別とか。共著ネットワークだったら著者の研究分野とか。これを解くアルゴリズムはゴマンとあると思うけど、提案手法は 隣接ノード間のラベルの相関がどんなのでも適用可 であるところが新しい。

隣接ノード間のラベル相関としては代表的なものにHomophilyやHeterophilyがある。Homophilyは「類は友を呼ぶ」的な現象で、隣接ノードは同じラベルを持ちやすいという性質。一方Heterophilyはその逆で隣接ノードは別（逆）のラベルを持ちやすいという性質。他にもこの２つが混ざってるグラフとかいろいろある。

既存のアルゴリズムはこのラベル相関の どれか一つ（もしくはいくつか）のみに対してしか適用できない。また、どれにでも適用できるアルゴリズムもあるが、そのアルゴリズムは あらかじめそのグラフにある相関が何であるかをパラメータとして与えなくてはならない。これに対して提案手法は どんなラベル相関にも適用できて、かつ それを指定するパラメータも必要ない という長所がある。

基本アイデア

以下の仮定を置く。

あるノードの隣接ノード集合の大部分が互いに同じラベルを持つならば、残りの隣接ノードも同じラベルを持つ可能性が高い

つまり、あるノードAの隣接ノードB,C,Dのラベルが1だったとき、残りの隣接ノードEのラベルが分からなかったとしても多分同様に1だろうという考え。この考えのいいところはHomophily, Heterophily, これらが混ざってる時のどんな場合でも適用可能なところ。またもう一つのいいところは、隣接ノード集合の大部分が高いに同じラベルを持つという条件が満たされなければ、何もしないという選択ができるところ。

このアイデアをノード間のメッセージパッシングとして定式化した。この例だと、まずB,C,Dが自分の隣接ノードであるAに対して「僕らのラベルは1だよ」というメッセージを送る。そうするとAは「自分の隣接ノードはみんなほとんどラベル1だな」という事がわかり、Eに対して「君も多分ラベル1だよ」というメッセージを送る。

アルゴリズムの詳細に興味があれば是非論文を。

貢献

以下の長所を持つアルゴリズムを提案した。

Seamless and Accurate：任意のラベル相関を持つグラフに適用可能で、高い精度を実現
Fast：アルゴリズムに含まれる反復計算の各ステップは入力グラフサイズに線形。またどんな構造のグラフ上でも収束を保証
Quasi-parameter free：アルゴリズムは一つだけパラメータを持つが、デフォルト１に設定すれば問題なし。つまりパラメータフリーと考えて差し支えない