search

Shumpei-Kikuta / Papers

Summarizing papers I've already read
0 stars 0 forks source link

node2vec #6

Open Shumpei-Kikuta opened 5 years ago

Shumpei-Kikuta commented 5 years ago

Why

ネットワークのタスク(リンク予測，ラベル分類)を行うために適切な分散表現を得たい．

  1. Surpervised learning base 特徴量エンジニアリングが必要であり，専門的な知識が必要とされる，
  2. Classic decomposition base PCAや特異値分解などのアプローチがあるが，パフォーマンスが低い
  3. Solve the optimization problem(おそらくpersonalized pagerankなどのアプローチ) 目的関数の設定が難しい，計算コストが非常に高い．
  4. Unsupervised learning (node2vecはこれ) ネットワークの構造情報からベクトル表現を得る．適切な特徴量を保存するように埋め込めば，最も有望な方法．

node2vecによって，"homophily", "structual equivalence"を保存したベクトルを得ることができる．

Related Work

skipgramの手法を用いている． NLPでは分布仮説に基づいてベクトル表現を得る．ネットワークにおいて，skipgramの入力とするシーケンスを得る方法は多数考えられる，Deepwalkでは単純なランダムウォークでシーケンスを得たが，structual equivelenceを考えられていない．node2vecにおいては，違った手法でシーケンスを得る．

How

ランダムウォークをする際の代表的な手法を二つ紹介する．

  1. BFS(Breath First Search: 幅優先探索) 始点のノードに近いところを重点的に探索 +ミクロな視点で隣接関係を捉える．ノードのroleを保存する． (近いところを探索すればそのノードがハブなのか，端っこなのかなどの役割がわかる)
    • 一部分しか探索されない
  2. DFS(Depth First Search: 深さ優先探索) 始点から遠いところまで探索
    • マクロな視点で隣接関係を捉えるためコミュニティ構造(homophily)を保存
    • 試行のたびに異なる結果が得られる(分散が大きい)
    • 始点から遠いところまで探索してもさほど意味がない

Biased random walk

一個前にtにいて，今はvにいる，移動する先がx 2018-10-16 14 21 48 2018-10-16 14 22 05 以上のように遷移確率を定義．dtxはtとxの最短経路の大きさ．

直感的意味

p: 大きくなると元のノードに戻りにくくなる． →情報の冗長性をなくす． 小さくすると，元のノードに戻りやすくなる． →localの特徴をしっかり捉えられる．

q: 大きくなると遠くへ行きづらくなる →幅優先的になる 小さくなると遠くへ行きやすい． →深さ優先的になる．

ランダムウォークは時間・空間計算量共に抑えられる方法．

Experiment

Deepwalk LINEより遥かに高いパフォーマンスを出した．

Shumpei-Kikuta commented 5 years ago

ランダムウォークベースの代表格． ランダムウォークの方法を変えるとまた別の特徴を保存したembeddingが得られそう．