PAKDD2015で発表し（てもらっ）た

PAKDD2015に論文が通っていたので発表した。タイトルは"SocNL: Bayesian Label Propagation with Confidence"。自分で参加して発表したかったんだけどちょうど同じ日程でWWW2015が開催されていて、そっちでの発表もあったので、PAKDDには参加できなかった。残念。なので共著のFaloutsos教授の知り合いの方にかわりに発表してもらった。大変お世話になりました。

前回のAAAI2015に引き続き、今回の発表もグラフ上でのノード分類アルゴリズムの提案。やっぱりアルゴリズムを考えていろいろ解析するのは楽しい。今後もこういう研究をしていきたい。

SocNL: Bayesian Label Propagation with Confidence from Yuto Yamaguchi

概要

今回の発表はグラフ上でのノード分類アルゴリズムをベイズ推定から導いて、推定結果に確信度を付与するというもの。ノード分類アルゴリズムはたくさんあるんだけど推定結果に確信度を付与できるものは（なぜか？）なかった。

提案したアルゴリズムは全てのラベルなしノードのラベルについて事前分布を仮定して、隣接ノードのラベルを手がかりとして事後分布を推定する。ただ、隣接ノードにもまたラベルなしノードが存在する（ことが多い）ので、事後分布を再帰的に計算する。

結果としてノードのラベルの事後分布を出力する。これを使えば推定結果の確信度を求めることができる。基本的には隣接ノードが多いほど事後分布はシャープな形状になる。なぜなら手がかりが多いから。逆に隣接ノードが一つとかだと手がかりが少なすぎるので分布は平たくなり、確信度は小さい。これは直感にも合っていると思う。

貢献

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

• Confidence: 推定結果に確信度を付与

• Simple: アルゴリズムは簡単な線形システムを解くだけ

• Fast: 必ず収束するし、計算量は入力サイズに線形

結果

アルゴリズムの理論的解析と実験的解析をした。

理論的解析では収束性とか、計算量とか、他のアルゴリズムとの等価性とかを示した。

実験的解析では三つのネットワークデータセットを使ってLabel Propagationと提案アルゴリズムの亜種と比較した。