PathSim（異種分野混合グラフで、「他のオブジェクトに与える影響度」と「オブジェクト間の経路数」を考慮した類似度指標）

書誌情報

この論文でやっていること

異なる分野のオブジェクトがノードになっているグラフ空間で、クエリと類似したオブジェクトを探索

類似度を計算するために、「他のオブジェクトに与える影響度」と「オブジェクト間の経路数」を計算

この論文から分かること

「他のオブジェクトに与える影響度」と「オブジェクト間の経路数」の両者が必要

経路が長すぎると効果が機能しない

シナリオ）自分と似た人をフォローしたい！

SNSで自分と似た人をフォローしたい！

だけど、自分と共通のフォロワーを調べてもなんか違うな...

→ 共通点だけでは、自分と似た人は探せない！

共通点と、他の人たちへの影響度を考慮した類似度指標PathSimを提案

お互いの知名度を考慮して、自分と他の人との類似度指標を提案。

「知名度が同程度で、共通点が多いオブジェクト同士は似ている」という考え

$ \text{(2つのオブジェクトの類似度)} = \frac{\text{(共通点の多さ)}}{\text{(知名度の平均)}}

具体例

table: 例

似ている 「王貞治」と「松井秀喜」 同じぐらい有名で、共通点が多い

似ていない 「王貞治」と「中野暁登」 共通点は多いが、知名度の差が大きい

既存の類似度指標の問題点

隣接ノードが多いノードが似ていると判定されてしまう（クエリからのたどり着きやすさや、経路数）

隣接ノードの隣接ノードが少ないと、似ていると判定されてしまう（それぞれが辿り着きやすいノードの共通度合い）

計算式

知名度: 他のノードからの辿り着きやすさ

$ \text{(2つのオブジェクトの類似度)} = \frac{\text{(オブジェクト同士を繋ぐ経路数)}}{\text{(それぞれが自身に戻ってくる経路数の平均)}}

似たオブジェクトを見つけるために、全通りの類似度を算出するのは大変すぎる...

事前に計算するにしても、組み合わせが膨大すぎて、管理できない！

計算時間を短縮する工夫

短いパスを計算しておいて、長いパスは短いパスを繋げて計算する（隣接行列をパスの長さだけ乗算する）

枝刈り

見込みのない候補オブジェクトを除外

ノードの出ノードと入ノードが似ているもの同士が一緒のクラスタになるようにクラスタリングして、明らかに似ていないクラスタは要素ごと飛ばす

実験

項目

ケーススタディで定性評価

ランキングの品質評価

クラスタリングの評価

比較手法

Personalized PageRank: クエリから近くて辿り着きやすいノードの類似度が高くなる

SimRank: それぞれの隣接ノードが似ていると、類似度が高くなる

Random Walk: クエリから辿り着きやすいノードが類似度が高くなる

Pairwise Random Walk: 辿り着きやすいノードを共有しているほど類似度が高くなる

実験① 類似性検索の評価

タスク①: ケーススタディで定性評価

論文、研究者、学会等のデータセット(DBLP dataset)で、ある研究者と似ている研究者を発見できるかを検証

結果

table: 結果

比較手法 大御所研究者（誰にとっても類似する）やマイナー研究者（特定の小規模会議で共通しているだけ）を返す

提案手法 論文数が同じぐらいで、共通点の多い研究者を返す

→ 同程度の目立ち度の研究者を見つけることができた

タスク②: ランキングの品質評価

実験①と同じデータセットで、ある学会と似た学会を発見できるかを検証

正解のランキングの準備

15の学会の全てのペアが、類似しているかを3段階で人手でラベリング

評価指標

nDCG: ランキングが正しい順番になっているか

結果

table: 結果

比較手法 権威的な会議が上位に来る場合や、マイナーな会議が上位にきて、nDCGスコアは低い

提案手法 人間の直感に合致した似た会議を上位で返せて、nDCGスコアが高い

→ ランキング性能も提案手法が最も高い

実験②: クラスタリング性能の評価

タスク①: 経路の種類間で違いの評価

クラスタリングの正解があるデータセット(4-area dataset)で、研究者経由の会議クラスタリングと会議経由の研究者のクラスタリングができるかを検証

評価指標

NMI(Normalized Mutual Information): クラスタリングの評価で、予測クラスターと正解クラスターの情報量の一致度

結果

経路長が短い場合（2ホップ）は提案手法の性能が最高だが、経路長が長くなるにつれて悪化する

→ 経路長が長い（共通点が薄い）場合、隣接ノードが多い（権威性の高い）ノードに依存する

タスク②: 複数種類の経路を組み合わせて評価

クラスタリングの正解があるデータセット(4-area dataset)で、研究者経由と用語経由の組み合わせなどの異なる種類のノード経由を組み合わせた時にクラスタリングができるかを検証

結果

単一経路よりも組み合わせた方がクラスタリング性能がよかった

→ 複数種類の経路を組み合わせ方が、類似オブジェクトを発見可能

他のドメインのデータセットでも実験

タスク

画像・ユーザ・タグのデータセットで、類似画像を検索できるか

結果

類似画像を検索できた

→ 提案手法はドメインに依存せず、類似オブジェクトを検索可能