# ネットワーク埋め込み ## 定義 ネットワーク埋め込み(network embedding、グラフ埋め込み)とは、頂点集合 $V$ とエッジ集合 $E$ からなるネットワーク $G = (V, E)$ の各頂点を、可視化・ノード分類・リンク予測などのタスクに使える低次元ベクトル空間 $\mathbb{R}^d$($d \ll |V|$)へ写す学習問題である。MDS・IsoMap・Laplacian eigenmap のような古典的手法は親和行列の固有ベクトル計算に依拠し計算量が頂点数に対して少なくとも二乗のため、数百万頂点・数十億エッジ規模の実世界ネットワークにはスケールしない。(Source: [[@2015__WWW__LINE - Large-scale Information Network Embedding]]) ネットワーク構造を保存する対象は、頂点間の局所的な結びつきを表す一次近接性(first-order proximity、観測された辺の重みそのもの)と、隣接構造の類似度で決まる二次近接性(second-order proximity、共通の近傍を持つ頂点同士が類似するという直感を捉える)に大別できる。実世界ネットワークでは観測される辺(一次近接性)が疎であるため、二次近接性はその疎性を補完する役割を持つ。(Source: [[@2015__WWW__LINE - Large-scale Information Network Embedding]]) ## 子概念 - [[LINE]] — 一次・二次近接性を別個の目的関数で保存し、edge-sampling による最適化で大規模ネットワークにスケールする埋め込み手法。 ## 未解決の問い - 一次近接性と二次近接性を、埋め込み後の連結ではなく単一の目的関数として原理的に同時学習する方法は何か。 - 頂点が複数の型を持つヘテロジニアスな情報ネットワークへ、大規模ネットワーク埋め込み手法をどう拡張できるか。 - 一次・二次近接性を超える高次の近接性は、ネットワーク埋め込みの性能をどの程度改善するか。 ## 未編纂の観察 - ## 関連 - [[@2015__WWW__LINE - Large-scale Information Network Embedding]] ## 出典 - [[@2015__WWW__LINE - Large-scale Information Network Embedding]]