PReP（異種情報グラフ内で、共通点の相乗効果を考慮したノード関連度指標）

書誌情報

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

グラフ上でノードペアの関係の強さを計算するために、「共通点間の相関関係」を考慮した関連度指標を提案

この論文から分かること

2つのノードの「知名度」、「メタパスの意外さ」、「経路の相関関係」からノードの関連度を算出

教師なしで、グラフからノード間の関連を学習

「研究者の名寄せ」、「SNS上の友達発見」で指標が有効

シナリオ） SNSで気が合う人と繋がりたい！

SNSで自分と気の合う人をフォローしたい！同じハッシュタグを付けたことのある人で探してみよう！

でもそれだと、投稿数が多い人とか、似たような共通点でしか関連していない人が出てくる...

→ 共通点の数だけで気が合う人を探すことはできない！

ペアの知名度、共通点の意外さ、共通点間の相関関係を考慮した関連度指標PRePを提案

$ \text{(ペアの関連度)} = \frac{\text{(メタパスの意外さ)}}{{\text{(ペアの知名度)}}×{\text{(共通点間の相関関係)}}}

table: 例

ペア 共通点 理由

似ている 「北川景子」と「イモトアヤコ」 「ドラマ 家売るオンナ」、「母」 共通点どうしが独立していて、共通点が多いほど関係が強くなっている

似ていない 「千鳥・ノブ」と「千鳥・大悟」 「千鳥」、「漫才」、「吉本」 「千鳥」に依存する、「漫才」や「吉本」の共通点をいくら持っても関係は強くならない

両者とも有名すぎず、意外な共通点を持っていて、独立した共通点を多く持つペアの関連度が高くなるような関連度指標

ペアの関連度を求めるために、経路別で関連度を求める

先に経路別（「千鳥・大悟」-「漫才」-「千鳥・ノブ」）で、　”経路の関連度”を求めて、最後に合算することで"ペアの関連度"を求める

共通点間の相乗効果

$ \text{(共通点間の相乗効果)} = {{\text{(メタパスの少なさ)}}×{\text{(メタパス内の経路の少なさ)}}}

例）共通点「千鳥」の相乗効果

「千鳥・ノブ」と「千鳥・大悟」には、他に似た共通点である「漫才」を持つため、「千鳥」は意外ではない

他の指標

知名度

$ \text{(ペアの知名度)} = {{\text{(一方の知名度)}}×{\text{(他方の知名度)}}}

例）「千鳥・ノブ」と「千鳥・大悟」

「千鳥・ノブ」の知名度と「千鳥・大悟」の知名度を掛け合わせる。どちらからメジャーだと、ペアの知名度は小さくなる

共通点の意外さ

$ \text{(メタパスの意外さ)} = \frac{\text{(実際のメタパス数)}}{{\text{(他2つの指標から計算されるメタパスの期待値)}}}

期待値は、他の指標を計算すると勝手に求めることができます。

関連度を最適化するためにグラフから学習

「ペアの知名度」、「共通点の意外さ」、「共通点間の相乗効果」のそれぞれのパラメータを1つずつ調整します。

具体的には、1つのパラメータを調整するために、他のパラメータを固定した状態で更新します。

実験

タスク

SNS上で本当の友達を発見できるか

異なる分野の研究データセットで、同じ研究者を発見できるか

ベースライン

table: ベースライン

PathCount(VLDB 2011) ペアの共通点の個数のみ使用

PathSim(VLDB 2011) 「ペアの共通点の個数」と「ペアの知名度の平均」で算出

JoinSim(VLDB 2014) 「ペアの共通点の個数」と「ペアの知名度の積」で算出

SimRank(SIGKDD 2002) ペアの各オブジェクトが持つタグの類似度で算出

提案手法のバリエーション

ペアの知名度なし提案手法

共通点の意外度なし提案手法

共通点間の相関関係なしの提案手法

フルバージョンの提案手法

実験① SNS上で本当の友達を発見できるか

人同士の関連度が算出できるか

データセット: FaceBookデータセット

FaceBookのアカウントデータ

ユーザ、専攻、学校名等11種類の属性がある

→ 「ユーザ-何か-ユーザ」の10種類のメタパスを作成

評価指標

ROC-AUC: 正解を正解とできていて、正解を誤って正解としていないか

AUPRC: RecallとPrecisionが両方とも高いか

結果

ROC-AUC、AUPRCともに提案手法がベースラインを上回った

全ての提案手法のバリエーションで、提案手法が上回った

→ 3つの指標が関連度の算出にプラスの影響

実験② 異なる分野の研究データセットで、同じ研究者を発見できるか

正解が1つしかないデータで正解を当てられるか

データセット: DBLPデータセット

コンピュータサイエンスの研究者や論文のデータセット

研究者、論文、学会名等の属性がある

→「研究者-論文-学会名-論文-研究者」をメタパスで実験

評価指標

MRR: 正解ペアを、関連度指標ランキングの上位にできたか

結果

提案手法がベースラインを上回った

ほとんどの提案手法のバリエーションで提案手法が上回ったが、「パスの意外性なし」だけが上回った

→ 教示なし学習では「パスの意外性」の影響が弱い可能性