Structural Deep Network Embedding

[Shumpei-Kikuta]

Why and What

Network情報の表現学習として，以下の3つのchallengeがある．

1. High Non-lineality 構造が複雑なため，浅いモデルでは構造を捉えきれない．
2. Structure-Preserving ローカルの特徴とグローバルの特徴を埋め込むのが難しい．
3. Sparse 現存のリンク以外にも繋がりうるリンクは存在するが，実際にはつながっていないsparseなネットワーク．現存のリンクだけで高いパファオーマンスを得るのが難しい．

SDNEは1に対して，DeepLearningを用いて複雑な非線形関数を作る． また，2,3に対して，ローカルな特徴として，ノードの次数を，グローバルな特徴として，隣接ノードの次数を利用し対処する． 半教師あり学習を利用する．1次隣接関係(ノードの次数)は教師あり，2次の隣接関係(隣接ノードの次数)は教師なし学習をする(後述)．

Related Work

1. Deep learning 深層学習は他の分野で複雑な表現を得る手法として利用されている．ネットワークに適用した例は少ないが，適用されていても第一次の隣接関係しか捉えられていない．
2. Network Embedding DeepWalkはネットワークの表現学習に大きなインパクトをもたらしたが，目的関数がネットワークの構造を保存することに特化されていない． つまり，目的関数が最大化された = 構造がしっかり保存されている とは言えない．

How

DeepAutoEncoder

通常の自己符号化器は隠れ層が一層のみであるが，これを多層にしたもの．考え方は同じで，次元圧縮のために用いられる．SDNEではd次元のembeddingを得るために用いられている． 以下のコスト関数を最小化することで適切な埋め込みが得られているか確認する． x_iはi番目のデータのinput ベクトル，x^_iはi番目のデコード後のベクトル(次元圧縮後のベクトル).

Model

DeepAutoEncoderの入力として，隣接行列Sの各ノードの列s_iを与える．すると1次隣接関係を埋め込んだd次元のembeddingが生成される．ここで注意したいのは，ネットワークの特徴はSparceであり，隣接ベクトルの大部分が0であることから，decoderから出力されるベクトルが0ベクトルになりやすいということ．(イメージは0を出力すれば大半が当たる).それゆえ，非0を間違えると，ペナルティを与えるようにする． b_iはs_ijが0であれば1, s以外であれば，β(>1)となる変数．Operationはアダマール積. これによって似た隣接関係を持つノード(隣接ベクトルが似ているノード)は似たembeddingが得られることが保証される，つまり二次隣接関係を保存している． 一次隣接関係の保存には，以下のコスト関数を用いる． つまり．似たエッジが張られていれば(s_ij)，エンベッティング後の距離も近くなるように保存する．したがって，一次隣接関係を保存することを保証している． これらに，正則化項を加えてJoint optimizationを行う．

[Shumpei-Kikuta]

一次，二次隣接関係を保存することにおいて，かなり有効な手段

[Shumpei-Kikuta]

非線形性と，パラメータシェアがDeep Walkなどと比べて優れている．