ネットワーク埋め込み — Node2Vec, DeepWalk, LINE
- 年
- 2014 (DeepWalk); 2016 (Node2Vec)
- 種類
- Representation learning / unsupervised network method
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
ネットワーク埋め込みは、グラフの各ノードを、ネットワークの構造的特性を保持しながら、密で低次元のベクトルにマッピングする表現学習手法の一群である。このアプローチは、Perozzi, Al-Rfou, Skiena による DeepWalk (2014) によってソーシャルネットワークデータに対して形式化され、グラフ上のランダムウォークに Word2Vec の skip-gram モデルを適用した。さらに Grover と Leskovec によって Node2Vec (2016) として拡張され、広域優先探索と深さ優先探索のバランスをとるバイアス付きランダムウォークが導入された。これらの埋め込みは、関係データを標準的な機械学習分類器やクラスタリングアルゴリズムが直接消費できる特徴ベクトルに変換する。
手法の背後にある直感
グラフはノードとエッジで構成されるが、ほとんどの機械学習アルゴリズムは数値のテーブルを期待する。ネットワーク埋め込みはこの変換問題を解決する。Word2Vec が文中でどの単語が互いに近くに出現するかを見ることで単語の意味を学習するのと同様に、DeepWalk はグラフ全体でのランダムウォーク中にどのノードが互いに近くに出現するかを見ることでノードの意味を学習する。その結果はベクトル空間内の座標となり、構造的に類似しているか頻繁に共起するノードは互いに近くに配置される。すべてのノードがベクトルを持つようになれば、グラフ固有のコードを書くことなく、それらのベクトルを分類器に投入したり、k-means でクラスタリングしたり、UMAP で可視化したりできる。
歴史学
Word2Vec をグラフ構造データに適用するというアイデアは、Perozzi, Al-Rfou, および Skiena によって DeepWalk (KDD 2014) で導入された。これは、ソーシャルグラフ上のランダムウォークがノード分類のための手作業で作成された特徴量を置き換えることができることを示した。Grover と Leskovec は、p と q でパラメータ化された二次バイアス付きランダムウォークを導入した Node2Vec (KDD 2016) でこれを拡張し、ホモフィリーベースの近傍探索と構造的等価性ベースの近傍探索のトレードオフを明示的に制御できるようにした。同時期に Tang ら は LINE (WWW 2015) を提案した。これは、ランダムウォークではなく、直接第1級および第2級近傍の目的関数を最適化することで埋め込みを学習するため、非常に大規模なグラフに適している。これら3つの手法は、ネットワーク表現学習の分野を確立し、その後のグラフニューラルネットワークアーキテクチャに影響を与えた。
使うべき場面
ネットワーク埋め込みは、少なくとも50ノードのグラフがあり、ノード分類、リンク予測、またはノードクラスタリングなどの下流タスクに連続的なベクトル特徴が必要な場合に適切である。この手法は、重みなしグラフと重み付きグラフの両方に適しており、有向または無向の構造を処理できる。単純で均一なランダムウォークベースラインで十分な場合は DeepWalk を選択する。p および q パラメータを通じてホモフィリーと構造的等価性のバランスを調整したい場合は Node2Vec を選択する。推論時に再学習なしで新しい、以前に seen されなかったノードを埋め込む必要がある場合は、GraphSAGE のような帰納的手法を優先する。標準的な形式のネットワーク埋め込みは帰納的(transductive)である。この手法は、ノード属性が正規分布に従うことを必要としない。
限界と注意点
- 帰納的(Transductive):モデルは、完全な再学習なしではトレーニング中に存在しなかったノードを埋め込むことができない。
- ハイパーパラメータ感度:埋め込み次元、ウォーク長、ウォーク数、ウィンドウサイズ、p、および q はすべて埋め込み品質に影響を与え、調整が必要である。
- ランダムウォークは、拡張なしでは高次のグラフ構造(例:ハイパーエッジまたは多関係エッジ)を捉えることができない。
- パフォーマンスは、ウォークコーパスが信頼できる統計を学習するにはあまりにも疎である非常に小さなグラフ(50ノード未満)で低下する。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 関係グラフデータを、標準的な機械学習パイプラインと互換性のある固定長ベクトルに変換する。
- Node2Vec の p および q パラメータにより、分析者はコミュニティに敏感な埋め込みと役割に敏感な埋め込みのバランスを調整できる。
- エッジの重みはウォーク確率に組み込むことができ、追加のモデリングステップなしで関係の強度を捉える。
- 効率的なランダムウォークサンプリングと skip-gram トレーニング手順により、大規模グラフにスケールする。
応用
- 引用ネットワーク、ソーシャルプラットフォーム、または生物学的相互作用グラフにおけるノード分類。
- リンク予測 — ノード埋め込みの類似性を比較することによる、欠落または将来のエッジの特定。
- k-means または階層的手法によるノードベクトルのクラスタリングによるコミュニティ検出。
- 異常検出 — ベクトル空間で外れ値となる埋め込みを持つノードは、異常な構造的役割を表す可能性がある。
- ユーザーとアイテムが二部グラフまたは多重グラフの相互作用グラフのノードである推薦システム。
使い方
使い方
プロセスは、ノードがエンティティであり、エッジが関係を表すグラフ G から始まる。エッジは有向または無向であり、後にトラバーサルの確率に影響を与える重みを持つことがある。エッジの重みが存在する場合、それらはウォーク確率に含まれる。存在しない場合は、すべてのエッジに等しい重みが与えられる。この段階で、分析者はアルゴリズムのバリアントも選択する。均一なランダムウォークには DeepWalk、パラメータ p (return) と q (in-out) によって制御されるバイアス付きウォークには Node2Vec、または第1級および第2級近傍の近接性を別々に学習する必要がある場合は LINE を選択する。Node2Vec のパラメータ設定間の選択は、期待されるネットワーク特性、すなわちホモフィリー(類似ノードが接続するため、広域優先探索が好ましい、q < 1)または構造的等価性(類似の役割を持つノードは離れている可能性があるため、深さ優先探索が好ましい、p < 1)によって導かれる。
各ノードから開始して、アルゴリズムは固定長のランダムウォーク(通常30ステップ)のシリーズをシミュレートし、それを何度も(通常ノードあたり200回のウォーク)繰り返す。各ウォークは、単語のシーケンスに類似したノード識別子のシーケンスを生成する。DeepWalk では、次のノードは近傍から一様に選択される。Node2Vec では、次のノードは p と q によってバイアスされた遷移確率に従って選択される。前のノードに戻ることは 1/p でペナルティが課され、同じ距離にとどまることは 1 に維持され、より遠くへ移動することは 1/q によって制御される。すべてのウォークのコレクションは、グラフのトポロジーをエンコードするノードシーケンスのコーパスを形成する。
ノードシーケンスのコーパスは、skip-gram モデル(Word2Vec と同じアーキテクチャ)に投入される。ウォーク内の各ノードについて、モデルはウィンドウ(通常10ステップ)内の周囲のコンテキストノードを予測する。確率的勾配降下法を通じて、モデルは、ウォークで共起するノードが類似したベクトルを持つように、固定次元(一般的には64または128)の密なベクトル表現をすべてのノードに対して学習する。次元はハイパーパラメータであり、より大きな次元はより多くの構造を捉えるが、計算が増加し、小さなグラフでの過学習のリスクが高まる。
学習後、モデルはノードごとに1つの埋め込みベクトルを提供する。これらのベクトルは、ノード分類(ロジスティック回帰またはニューラル分類器に投入)、リンク予測(候補ノードペアのベクトルの比較)、またはコミュニティ検出(ベクトルのクラスタリング)の特徴として使用される。埋め込みは帰納的(transductive)である。つまり、学習中に seen されたノードに対して固定される。学習後に新しいノードを埋め込む必要がある場合、標準的な Node2Vec または DeepWalk モデルは再学習なしでは unseen ノードに一般化できないため、GraphSAGE のような帰納的(inductive)手法を使用する必要がある。
よくある落とし穴
- Node2Vec モデルをトレーニンググラフに含まれていなかった新しいノードに適用する — モデルにはそれらのノードのベクトルがない。帰納的埋め込みが許容されない場合は、帰納的手法(例:GraphSAGE)を使用する。
- デフォルトの p=1, q=1(DeepWalk と同等)を、ネットワークがホモフィリーまたは構造的等価性のパターンに従っているかどうかを調べずに使用する — 期待されるパターンに p と q を調整することで、下流タスクのパフォーマンスが大幅に向上する可能性がある。
- 埋め込み次元を固定定数として扱う:小さなグラフでは、次元64または128は過学習する可能性がある。より低い値から始めて、下流タスクで検証する。
- 最小サンプル要件を無視する:50ノード未満のグラフは、信頼できる埋め込みを学習するには薄すぎるウォークコーパスを生成する。
よくある質問
DeepWalk, Node2Vec, および LINE の違いは何ですか?
DeepWalk は均一なランダムウォークと Word2Vec の skip-gram モデルを使用する — 最も単純なベースラインである。Node2Vec は p と q によって制御されるバイアス付きランダムウォークを追加し、分析者がウォークが広域優先探索(ホモフィリー)のように探索するか、深さ優先探索(構造的等価性)のように探索するかを調整できるようにする。LINE はランダムウォークを全く使用しない。エッジリスト上で直接第1級および第2級近傍の目的関数を最適化するため、非常に大規模なグラフにスケールしやすいが、ウォークベースの近傍信号は犠牲になる。
Node2Vec の p と q パラメータをどのように選択しますか?
p は前のノードに戻る確率を制御する(低い p = バックトラッキングが少ない)、q は探索半径を制御する(q < 1 は外向き探索を好む、q > 1 はウォークを開始ノードの近くに保つ)。同じコミュニティ内のノードが類似している(ホモフィリー)と予想される場合は、ウォークが外向きに広がるように q < 1 を設定する。離れていても同じ構造的役割を持つノードが類似していると予想される場合は、深さ優先探索を促進するために p < 1 を設定する。両方のレジームを下流タスクで検証する。
トレーニング後に新しいノードを再トレーニングなしで埋め込むことはできますか?
標準的な Node2Vec および DeepWalk は帰納的(transductive)である。埋め込み行列は、トレーニング中に seen されたノードのみをカバーする。新しい、以前に seen されなかったノードへの帰納的(inductive)一般化には、推論時に任意のノードに適用できるノード近傍の集約関数を学習する GraphSAGE のような帰納的グラフニューラルネットワーク手法を使用する。
埋め込みにいくつの次元を使用すべきですか?
最も一般的な選択肢は64と128であり、これらは中規模から大規模なグラフでうまく機能する。小さなグラフ(50〜200ノード)の場合は、過学習を避けるために低い次元(16または32)から始め、再構築誤差だけでなく下流タスクのパフォーマンス(例:ノード分類精度)を測定することで埋め込み品質を評価する。
関連する手法
参考文献
Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.
DOI 文献を開くコピーしました。Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.
DOI 文献を開くコピーしました。