# LINE ## 定義 LINE(Large-scale Information Network Embedding)は、[[ネットワーク埋め込み]]の一手法であり、無向・有向・重み付き・二値のいずれの型の情報ネットワークにも適用できる。一次近接性(局所的な結びつき)と二次近接性(近傍構造の類似度)をそれぞれ専用の目的関数(KL ダイバージェンスに基づく $O_1$、negative sampling を用いる $O_2$)で保存し、学習済みの一次・二次埋め込みベクトルを連結して最終的な表現を得る。重み付きエッジで確率的勾配降下法(SGD)を直接使うと辺の重みの分散が大きいネットワークで勾配が発散する問題があり、これを辺の重みに比例した確率で辺をサンプリングして二値辺として扱う edge-sampling アルゴリズム(alias table 法による $O(1)$ サンプリング)で解決する。全体の時間複雑度は $O(dK|E|)$ で頂点数 $|V|$ に依存しない。(Source: [[@2015__WWW__LINE - Large-scale Information Network Embedding]]) DeepWalk が truncated random walk による深さ優先探索的な近傍拡張で二次近接性相当の情報を暗黙に捉えるのに対し、LINE は幅優先探索的な近傍拡張に相当する二次近接性を明示的な目的関数で保存する点、およびエッジの重みを直接扱える点で異なる。(Source: [[@2015__WWW__LINE - Large-scale Information Network Embedding]]) ## 未解決の問い - 一次近接性と二次近接性を、学習後の埋め込みベクトルの連結ではなく単一の目的関数として同時に学習する原理的な方法は何か。 - 既存頂点との接続が一切観測されない新規頂点(コールドスタート)の埋め込みを、テキスト情報などの追加手掛かりを使ってどう求めるか。 - LINE をヘテロジニアスな情報ネットワーク(頂点が複数の型を持つネットワーク)へどう拡張できるか。 ## 未編纂の観察 - ## 関連 - [[ネットワーク埋め込み]](親概念) - [[@2015__WWW__LINE - Large-scale Information Network Embedding]] ## 出典 - [[@2015__WWW__LINE - Large-scale Information Network Embedding]]