# LINE: Large-scale Information Network Embedding > [!abstract] 概要 > 本論文は、可視化・ノード分類・リンク予測などに有用な、超大規模情報ネットワークを低次元ベクトル空間へ埋め込む問題を研究する。既存のグラフ埋め込み手法の大半は、数百万ノードを含む実世界の情報ネットワークに対してスケールしない。本論文は、無向・有向・重み付きのいずれの種類の情報ネットワークにも適用できる新しいネットワーク埋め込み手法「LINE」を提案する。この手法は、ネットワークの局所構造と大域構造の両方を保存するように注意深く設計された目的関数を最適化する。古典的な確率的勾配降下法の限界に対処し、推論の有効性と効率の両方を改善する edge-sampling アルゴリズムを提案する。実証実験により、言語ネットワーク・社会ネットワーク・引用ネットワークを含む様々な実世界の情報ネットワーク上で LINE の有効性が証明される。このアルゴリズムは非常に効率的で、典型的な単一マシン上で数時間のうちに、数百万の頂点と数十億のエッジを持つネットワークの埋め込みを学習できる。LINE のソースコードはオンラインで公開されている。 ## 論文情報 - タイトル: LINE: Large-scale Information Network Embedding - 著者: Jian Tang([[Microsoft Research Asia]])、Meng Qu・Mingzhe Wang・Ming Zhang(北京大学 EECS、[[Peking University]])、Jun Yan([[Microsoft Research Asia]])、Qiaozhu Mei([[University of Michigan]] School of Information) - 媒体: WWW 2015(International World Wide Web Conference, 2015 年 5 月 18〜22 日, フィレンツェ)。DOI 10.1145/2736277.2741093 - arXiv: 1503.03578(2015 年 3 月 12 日投稿) - コード: https://github.com/tangjianpku/LINE(論文中に記載) ## 概要 LINE は、数百万ノード・数十億エッジ規模の実世界情報ネットワークを低次元ベクトル空間へ埋め込む手法である。ノード間の局所的な結びつきを表す一次近接性と、隣接構造の類似性を表す二次近接性という 2 種類の近接性を、それぞれ専用の目的関数で保存する。重み付きエッジによる勾配の発散を避けるため、辺の重みに比例した確率で辺をサンプリングしてから二値辺として扱う edge-sampling 法を用いて非同期 SGD(ASGD)で最適化する。言語ネットワーク・社会ネットワーク・引用ネットワークでの実験により、DeepWalk やグラフ因子分解(graph factorization)より高い有効性と効率を示す。 ## 問題設定 情報ネットワークは $G = (V, E)$ として定義され、各エッジ $e = (u, v) \in E$ は関係の強さを表す重み $w_{uv} > 0$ を持つ。無向グラフでは $(u, v) \equiv (v, u)$、有向グラフでは $(u, v) \not\equiv (v, u)$ である。 論文は 2 種類の近接性を定義する。 - **一次近接性(first-order proximity)**: 頂点対 $(u, v)$ 間の局所的な対関係で、観測された辺の重み $w_{uv}$ そのものが一次近接性を表す。辺が観測されなければ一次近接性は 0 になる。無向グラフにのみ適用可能。 - **二次近接性(second-order proximity)**: 頂点 $u$, $v$ の近傍構造の類似度で決まる近接性。$p_u = (w_{u,1}, \dots, w_{u,|V|})$ を頂点 $u$ の一次近接性ベクトルとすると、$u$ と $v$ の二次近接性は $p_u$ と $p_v$ の類似度で定まる。有向・無向の両方に適用可能。 **Figure 1: トイネットワークの例** ![[_attachments/arxiv-1503.03578/fig01-toy-network.png]] (Figure 1. 頂点 6 と 7 は重みの大きい辺で直接結ばれており高い一次近接性を持つため低次元空間で近くに配置されるべきである。頂点 5 と 6 の間には辺は無いが共通の近傍(頂点 1〜4)を多く共有しており高い二次近接性を持つため、これも近くに配置されるべきである。) 現実のネットワークでは正当なリンクの多くが観測されないため一次近接性だけでは大域構造を保存するのに不十分であり、二次近接性がその疎性を補完する。社会学の「友人関係の重なりの度合いは結びつきの強さと相関する」という知見や言語学の「同じ文脈で使われる語は似た意味を持つ(distributional hypothesis)」という知見が、この直感を支持する。 **問題定義**: 大規模ネットワーク $G = (V, E)$ が与えられたとき、各頂点 $v \in V$ を低次元空間 $\mathbb{R}^d$($d \ll |V|$)へ写す関数 $f_G: V \to \mathbb{R}^d$ を学習し、一次近接性と二次近接性の両方を $\mathbb{R}^d$ 上で保存する。 ## 提案手法 ### 一次近接性を保存する LINE 無向エッジ $(i, j)$ について、頂点 $v_i$, $v_j$ 間の結合確率を $p_1(v_i, v_j) = \frac{1}{1 + \exp(-\vec{u}_i^\top \cdot \vec{u}_j)}$ と定義する($\vec{u}_i \in \mathbb{R}^d$ は頂点 $v_i$ の低次元表現)。経験分布は $\hat{p}_1(i,j) = w_{ij} / W$($W = \sum_{(i,j) \in E} w_{ij}$)で与えられ、KL ダイバージェンスを距離関数として目的関数を $O_1 = -\sum_{(i,j) \in E} w_{ij} \log p_1(v_i, v_j)$ と定める。一次近接性は無向グラフにのみ適用できる。 ### 二次近接性を保存する LINE 各頂点 $v_i$ に「頂点としての表現」$\vec{u}_i$ と「コンテキストとしての表現」$\vec{u}_i'$ の 2 つのベクトルを与える。有向エッジ $(i, j)$ について、頂点 $v_i$ から「コンテキスト」$v_j$ が生成される条件付き確率を $p_2(v_j \mid v_i) = \frac{\exp(\vec{u}_j'^\top \cdot \vec{u}_i)}{\sum_{k=1}^{|V|} \exp(\vec{u}_k'^\top \cdot \vec{u}_i)}$ と定義し、頂点の重要度 $\lambda_i$(本論文では次数 $d_i$ とする)で重み付けた目的関数 $O_2 = -\sum_{(i,j) \in E} w_{ij} \log p_2(v_j \mid v_i)$ を最小化する。二次近接性は有向・無向の両方のグラフに適用できる。 ### 一次近接性と二次近接性の結合 論文が実用上採る方法は、一次近接性と二次近接性をそれぞれ別個に学習した LINE(1st) と LINE(2nd) の埋め込みベクトルを連結する簡便な方法である(教師あり学習では次元の重み付けを学習データから決められるため LINE(1st+2nd) として利用可能。教師なしタスクでは重み付けが難しいため、この結合は教師あり評価にのみ適用する)。2 つの目的関数を同時学習するより原理的な結合方法は将来課題として残されている。 ### モデル最適化と edge-sampling アルゴリズム $O_2$ の最適化は頂点全体にわたる正規化項の計算が必要で計算コストが高いため、negative sampling を採用し、各エッジ $(i,j)$ について $\log \sigma(\vec{u}_j'^\top \cdot \vec{u}_i) + \sum_{n=1}^{K} \mathbb{E}_{v_n \sim P_n(v)}[\log \sigma(-\vec{u}_n'^\top \cdot \vec{u}_i)]$ を目的関数とする($\sigma$ はシグモイド関数、$K$ は負例数、$P_n(v) \propto d_v^{3/4}$)。$O_1$ の自明解($u_{ik} = \infty$)を避けるため、同じ negative sampling の枠組みで $\vec{u}_j'$ を $\vec{u}_j$ に置き換えて用いる。最適化には非同期 SGD(ASGD, Hogwild!)を用いる。 エッジ $(i,j)$ がサンプルされたときの勾配 $\frac{\partial O_2}{\partial \vec{u}_i} = w_{ij} \cdot \frac{\partial \log p_2(v_j \mid v_i)}{\partial \vec{u}_i}$ には辺の重み $w_{ij}$ が直接乗じられるため、重みの分散が大きいネットワーク(語共起ネットワークでは 1 から数万まで分布)では、学習率をどう選んでも勾配が発散するか小さすぎるかのいずれかになり最適化が破綻する。 この問題を解決するため **edge-sampling アルゴリズム**を提案する。重み $w$ の辺を $w$ 本の二値辺に展開すればこの問題は解けるがメモリ消費が増大するため、代わりに重みに比例した確率で元の辺をサンプリングし、サンプルされた辺を二値辺として扱ってモデルを更新する。この操作は目的関数自体を変えず、辺サンプリングを alias table 法によって $O(1)$ で行う(重み総和からの累積区間探索が $O(|E|)$ かかるのに対し、alias table は繰り返しサンプリングを高速化する)。1 ステップ当たり $O(dK)$ 時間で、ステップ数はエッジ数 $|E|$ に比例することが実験的に分かっているため、LINE 全体の時間複雑度は $O(dK|E|)$ となり、頂点数 $|V|$ に依存しない。 ### 実装上の工夫 - **低次数頂点の扱い**: 次数の小さい頂点は近傍数が少なく、特に二次近接性ベースの手法では表現の推定が難しい。本論文は二次近傍(隣接ノードの隣接ノード)を追加してネットワークを再構成する対処を提案する。頂点 $i$ とその二次近傍 $j$ の間の重みは $w_{ij} = \sum_{k \in N(i)} w_{ik} \frac{w_{kj}}{d_k}$ とし、実用上は $w_{ij}$ が大きい上位の部分集合だけを追加する。 - **新規頂点への対応**: 新しい頂点 $i$ が既存頂点との接続を持つ場合、既存頂点の埋め込みを固定して $-\sum_{j \in N(i)} w_{ji} \log p_1(v_j, v_i)$(または $p_2$)を最小化することで新頂点の埋め込みを得られる。接続が全く観測されない場合はテキスト情報等の他の手掛かりが必要で、将来課題として残されている。 ## 新規性 古典的なグラフ埋め込み手法(MDS・IsoMap・Laplacian eigenmap 等)は親和行列の固有ベクトル計算に依拠し計算量が頂点数に対して少なくとも二乗のため大規模ネットワークに使えない。graph factorization(GF)は SGD で最適化する行列分解によりスケールするが、目的関数がネットワーク専用に設計されておらず無向グラフにしか使えない。最も近い先行研究である DeepWalk は truncated random walk により深さ優先探索的に頂点の近傍を拡張するが、どのネットワーク性質を保存するかを明示する目的関数を持たず、二値辺のネットワークにしか適用できない。 これに対し LINE は、(1) 一次近接性と二次近接性を明示的に保存する目的関数を持つ、(2) 有向・無向・重み付き・二値のいずれの型のネットワークにも適用できる、(3) edge-sampling により重み付きエッジでの SGD の発散問題を解決しつつ $O(|E|)$ の線形時間複雑度を保つ、という 3 点で既存手法と異なる。DeepWalk が深さ優先的に近傍を拡張するのに対し、LINE の二次近接性は幅優先探索的な近傍拡張に対応するという整理がなされている。 ## 実験設定 - **実験環境**: 1 台の単一マシン(メモリ 1TB、40 CPU コア、2.0GHz、16 スレッド使用)。 - **データセット**: 5 種類の実世界ネットワーク。 **Table 1: 実世界情報ネットワークの統計量** | | Wikipedia(言語) | Flickr(社会) | Youtube(社会) | DBLP(著者引用) | DBLP(論文引用) | |---|---|---|---|---|---| | 型 | 無向・重み付き | 無向・二値 | 無向・二値 | 有向・重み付き | 有向・二値 | | \|V\| | 1,985,098 | 1,715,256 | 1,138,499 | 524,061 | 781,109 | | \|E\| | 1,000,924,086 | 22,613,981 | 2,990,443 | 20,580,238 | 4,191,677 | | 平均次数 | 504.22 | 26.37 | 5.25 | 78.54 | 10.73 | | ラベル数 | 7 | 5 | 47 | 7 | 7 | | 訓練数 | 70,000 | 75,958 | 31,703 | 20,684 | 10,398 | - 言語ネットワークは英語版 Wikipedia 全体から 5 語のスライディングウィンドウ内の共起関係で構築(頻度 5 未満の語は除外)。 - 社会ネットワークは Flickr(密)と Youtube(疎、DeepWalk と同一データ)。 - 引用ネットワークは DBLP データセットから著者間・論文間それぞれの引用関係を構築。 - **比較対象**: graph factorization(GF, [1])、DeepWalk([16])、SkipGram([12]、言語ネットワークのみ)、LINE-SGD(edge-sampling なしで直接 SGD 最適化した LINE、比較用のアブレーション)。MDS・IsoMap・Laplacian eigenmap は大規模ネットワークを扱えないため比較対象から除外。 - **パラメータ設定**: ミニバッチサイズ 1。学習率は $\rho_t = \rho_0 (1 - t/T)$、$\rho_0 = 0.025$。言語ネットワークの次元は 200(word embedding の慣例に合わせる)、他は 128(DeepWalk の慣例)。負例数 $K=5$。LINE・LINE-SGD の総サンプル数 $T=10$ billion、GF は $T=20$ billion。DeepWalk はウィンドウサイズ 10、ウォーク長 40、頂点当たりウォーク数 40。全埋め込みベクトルは最終的に $\|\vec{w}\|_2 = 1$ に正規化。 - **評価指標**: 言語ネットワークでは word analogy(Semantic / Syntactic / Overall の正解率)と Wikipedia ページ分類(Micro-F1 / Macro-F1)。社会・引用ネットワークではマルチラベル分類の Micro-F1 / Macro-F1。 ## 実験結果 ### 言語ネットワーク **Table 2: Wikipedia データでの word analogy 結果** | Algorithm | Semantic (%) | Syntactic (%) | Overall (%) | 実行時間 | |---|---|---|---|---| | GF | 61.38 | 44.08 | 51.93 | 2.96h | | DeepWalk | 50.79 | 37.70 | 43.65 | 16.64h | | SkipGram | 69.14 | 57.94 | 63.02 | 2.82h | | LINE-SGD(1st) | 9.72 | 7.48 | 8.50 | 3.83h | | LINE-SGD(2nd) | 20.42 | 9.56 | 14.49 | 3.94h | | LINE(1st) | 58.08 | 49.42 | 53.35 | 2.44h | | **LINE(2nd)** | **73.79** | **59.72** | **66.10** | 2.55h | LINE(2nd) は SkipGram を含む全手法を上回った。これは、単語の共起そのものより「同じ文脈の語を共有すること」を捉える二次近接性が、より強い意味的類似性の指標になるためと考察されている。LINE-SGD 系は重みの分散が大きい言語ネットワークで SGD が発散し性能が著しく劣化するが、edge-sampling を適用した LINE は同じ一次/二次近接性を使いながら大幅に性能が改善する。LINE(1st)・LINE(2nd) は 2 百万ノード・10 億エッジのネットワークを 3 時間未満で処理でき、GF より 10% 以上速く、DeepWalk より 5 倍以上高速である(DeepWalk はウォークに基づき重みを無視するため学習には不利)。 **Table 3: Wikipedia ページ分類結果(Micro-F1、抜粋)** | Algorithm | 10% | 50% | 90% | |---|---|---|---| | GF | 79.63 | 81.38 | 81.78 | | DeepWalk | 78.89 | 80.92 | 81.42 | | SkipGram | 79.84 | 81.71 | 82.09 | | LINE(1st) | 79.67 | 81.40 | 81.67 | | LINE(2nd) | 79.93 | 81.80 | 82.17 | | **LINE(1st+2nd)** | **81.04**\*\* | **83.16**\*\* | **83.74**\*\* | (\*\* は GF に対し 0.01 水準で有意に優れることを示す paired t-test の結果。Macro-F1 でも同様の傾向。)LINE(1st+2nd) は一次・二次近接性を連結した表現が単独の LINE(1st)・LINE(2nd) より一貫して優れることを示し、両近接性が相補的であることを確認している。 **Table 4: 一次/二次近接性による類似語比較** | 単語 | 近接性 | 類似語トップ | |---|---|---| | good | 1st | luck, bad, faith, assume, nice | | good | 2nd | decent, bad, excellent, lousy, reasonable | | information | 1st | provide, provides, detailed, facts, verifiable | | information | 2nd | infomation, informaiton, informations, nonspammy, animecons | | graph | 1st | graphs, algebraic, finite, symmetric, topology | | graph | 2nd | graphs, subgraph, matroid, hypergraph, undirected | | learn | 1st | teach, learned, inform, educate, how | | learn | 2nd | learned, teach, relearn, learnt, understand | 二次近接性による類似語は語義的に強く関連する語(同義語・上位語)に集中するのに対し、一次近接性による類似語は構文的・意味的な語が混在する傾向が見られる。 ### 社会ネットワーク **Table 5: Flickr ネットワークでのマルチラベル分類(Micro-F1、抜粋)** | Algorithm | 10% | 50% | 90% | |---|---|---|---| | GF | 53.23 | 54.32 | 54.48 | | DeepWalk | 60.38 | 61.13 | 61.22 | | LINE(1st) | 63.27 | 63.96 | 64.10 | | LINE(2nd) | 62.83 | 63.55 | 63.69 | | **LINE(1st+2nd)** | **63.20**\*\* | **64.53**\*\* | **64.74**\*\* | Flickr(比較的密なネットワーク)では LINE(1st) が LINE(2nd) をやや上回る。これは、社会ネットワークでは強い結びつき(一次近接性)がより重要であること、平均近傍数が小さいほど二次近接性の推定が不正確になりやすいことの 2 点によると説明される。 **Table 6: Youtube ネットワーク(次数平均 5.25 の極めて疎なネットワーク)でのマルチラベル分類(抜粋、括弧内は二次近傍を加えた再構成後)** | Algorithm | Micro-F1 (1%) | Micro-F1 (10%) | |---|---|---| | GF | 25.43 | 28.51 (29.63) | | DeepWalk | 39.68 | 45.23 | | LINE(1st) | 35.43 | 42.21 (42.73) | | LINE(2nd) | 32.98 | 43.34 (45.67) | | **LINE(1st+2nd)** | 39.01\* | **46.08**\*\* (**46.43**\*\*) | Youtube では疎性のため LINE(2nd) が単体では DeepWalk に劣るが、次数の小さい頂点に二次近傍を加えてネットワークを再構成すると LINE(2nd) の性能が大きく改善し、LINE(1st+2nd) は再構成後に DeepWalk を上回る。これは低次数頂点への対処(実装上の工夫)の有効性を示す実験結果である。 **Figure 2: 共著者ネットワークの可視化** (a) GF ![[_attachments/arxiv-1503.03578/fig02a-gf-visualization.png]] (b) DeepWalk ![[_attachments/arxiv-1503.03578/fig02b-deepwalk-visualization.png]] (c) LINE(2nd) ![[_attachments/arxiv-1503.03578/fig02c-line2nd-visualization.png]] (Figure 2. WWW・KDD(データマイニング、赤)、NIPS・ICML(機械学習、青)、CVPR・ICCV(コンピュータビジョン、緑)から抽出した 18,561 著者・207,074 辺の共著者ネットワークを t-SNE で 2 次元に写像。GF による可視化は同一コミュニティの著者がまとまらず意味のある配置になっていない。DeepWalk はより良好だが、多くの著者(特に高次数頂点)がランダムウォークのノイズにより中心付近に密集して混ざる。LINE(2nd) は同色のノードが近くに配置され、最も意味のある層構造を生成する。) ### 引用ネットワーク 引用ネットワークは有向グラフのため一次近接性を使う GF・LINE(1st) は比較対象から外し、DeepWalk と LINE(2nd) のみを比較する。分類ラベルは AAAI・CIKM・ICML・KDD・NIPS・SIGIR・WWW の 7 会議。 **Table 7: DBLP(著者引用)ネットワークでのマルチラベル分類(Micro-F1、抜粋)** | Algorithm | 10% | 50% | 90% | |---|---|---|---| | DeepWalk | 63.98 | 64.92 | 64.90 | | LINE-SGD(2nd) | 56.64 | 60.44 | 60.59 | | LINE(2nd) | 62.49 | 63.84 | 63.77 | | LINE(2nd), 再構成後 | **64.69**\* | **66.19**\*\* | **66.05**\*\* | このネットワークも疎なため、再構成前は DeepWalk が LINE(2nd) を上回るが、次数 500 未満の頂点に二次近傍を加えて再構成すると LINE(2nd) が DeepWalk を上回る。 **Table 8: DBLP(論文引用)ネットワークでのマルチラベル分類(Micro-F1、抜粋)** | Algorithm | 10% | 50% | 90% | |---|---|---|---| | DeepWalk | 52.83 | 55.07 | 55.90 | | LINE(2nd) | 58.42 | 60.94 | 61.79 | | LINE(2nd), 再構成後 | **60.10**\*\* | **61.85**\*\* | **62.80**\*\* | 論文引用ネットワークでは再構成前から LINE(2nd) が DeepWalk を上回る。ランダムウォークは引用パスに沿ってしか到達できず(常に古い論文へ向かう)、被引用側の参照を捉えにくいのに対し、LINE(2nd) は各論文をその参照集合で表現するため、より合理的に構造を捉えられると説明されている。 ### ネットワークの疎性・パラメータ感度・スケーラビリティ **Figure 3: ネットワーク疎性に対する性能** ![[_attachments/arxiv-1503.03578/fig03-sparsity-sensitivity.png]] (Figure 3. (a) Flickr ネットワークからサンプルした辺の割合を変えたときの Micro-F1。辺が少ない(疎な)うちは LINE(1st) が LINE(2nd) を上回るが、辺の割合が増えるほど LINE(2nd) が LINE(1st) を上回るようになる。(b) Youtube ネットワークの頂点を次数でグループ化した性能。元のネットワークでは最低次数グループを除き LINE(2nd) が LINE(1st) を上回るが、再構成(二次近傍の追加)後はすべての次数グループで LINE(2nd) が DeepWalk を上回る。) **Figure 4: 次元数・サンプル数に対する感度** ![[_attachments/arxiv-1503.03578/fig04-dimension-samples.png]] (Figure 4. (a) 埋め込み次元 $d$ を大きくしすぎると LINE(1st)・LINE(2nd) の性能はむしろ低下する。(b) サンプル数(最適化ステップ数)に対する収束の速さでは LINE(2nd) が LINE(1st) と DeepWalk を一貫して上回り、両 LINE モデルとも DeepWalk よりずっと速く収束する。) **Figure 5: スレッド数に対するスケーラビリティ** ![[_attachments/arxiv-1503.03578/fig05-threads-speedup.png]] (Figure 5. (a) Youtube データでのスレッド数に対する高速化率はほぼ線形。(b) スレッド数を増やしても分類性能(Micro-F1)は安定しており、非同期 SGD による並列化が推論の質を損なわないことを示す。) ## 考察 - edge-sampling は、重み付きエッジの分散が大きい実世界ネットワークで SGD が抱える勾配発散の問題を、目的関数を変えずに解くという点で本論文の核心的な工夫である。LINE-SGD と LINE の比較(Table 2・7)は、この工夫単体の効果を分離して示している。 - 一次近接性と二次近接性のどちらが有効かはネットワークの密度に依存する。疎なネットワークでは一次近接性が、密なネットワークや低次数頂点を補完した後では二次近接性が優位になる傾向が、言語・社会・引用ネットワークの全実験で一貫して観察される。 - 低次数頂点への二次近傍の追加(ネットワーク再構成)は疎なネットワークでの二次近接性ベース手法(LINE(2nd))の性能を大きく改善し、DeepWalk のようなランダムウォークに基づく近傍拡張よりも直接的な効果を持つ。 ## 強み・弱点・課題 **強み** - 有向・無向・重み付き・二値のあらゆる型の情報ネットワークに適用できる汎用性。 - edge-sampling により $O(|E|)$ の線形時間複雑度を保ちながら重み付きエッジでの SGD の発散問題を解決する。 - 数百万ノード・数十億エッジ規模のネットワークを単一マシンで数時間で学習できる実用的なスケーラビリティ。 **弱点・課題(論文が明示的に述べるもの)** - 一次近接性と二次近接性を同時に学習する原理的な結合方法は本論文では実現されておらず、将来課題として残されている(現状は学習済み埋め込みの単純な連結)。 - 一次近接性と二次近接性を超える高次の近接性の考慮は将来課題。 - 頂点が複数の型を持つヘテロジニアスな情報ネットワークへの拡張は将来課題。 - 既存頂点との接続が一切観測されない新規頂点への対応(テキスト情報等の追加手掛かりの活用)は未解決のまま将来課題とされている。