# 紹介: LINE: Large-scale Information Network Embedding Navigation: [[index]] | [[wiki/sources/@2015__WWW__LINE - Large-scale Information Network Embedding|LINE (WWW2015)(source)]] 対応する source ページの配布用紹介文。Slack 等へ貼るための圧縮であり、source 本文の再要約ではない。 ## 紹介文 - 数百万ノード規模の実世界ネットワークを埋め込みたいが、既存手法は計算量が頂点数に対して重すぎてスケールしない。 - 重み付きエッジで素直に SGD を回すと勾配が発散し、大規模な学習自体が破綻する。 - LINE は、直接つながりの強さを表す一次近接性と、周辺構造の似方を表す二次近接性を別々の目的関数で保存する。 - 勾配発散を避けるため、辺の重みに比例した確率でサンプリングしてから二値辺として扱う edge-sampling 法を導入し、alias table で O(1) サンプリングを実現する。 - 単一マシン(メモリ 1TB・40 コア)上で、Wikipedia 共起・Flickr・Youtube・DBLP 著者/論文引用という最大 10 億エッジ級の 5 ネットワークで検証した。 - 比較対象は graph factorization・DeepWalk・SkipGram で、word analogy やマルチラベル分類の Micro/Macro-F1 で評価した。 - LINE は数百万ノード・数十億エッジのネットワークを数時間で学習でき、DeepWalk より 5 倍以上速い。 - 一次・二次近接性を連結した LINE(1st+2nd) は多くのタスクで DeepWalk や graph factorization を上回った。 - 密なネットワークでは二次近接性が、疎なネットワークでは一次近接性が有利という傾向が一貫して見られる。 - 疎な頂点に二次近傍を補って再構成する工夫が、疎ネットワークでの性能改善に効いている。 --- Jian Tang et al. (Microsoft Research Asia; Peking University), "LINE: Large-scale Information Network Embedding," WWW:2015, 2015. https://arxiv.org/abs/1503.03578 ## 出典 - [[wiki/sources/@2015__WWW__LINE - Large-scale Information Network Embedding|LINE (WWW2015)]]