論文読み.7 Deep Variational Network Embedding in Wasserstein Space (KDD 2018)

## はじめに
　`Deep Variational Network Embedding in Wasserstein Space`という論文を読んだのでまとめていきます。

## 1. 対象とするトピック
### 1.1 キーワード
　`Network Embedding`, `Wasserstein Space` [論文](http://pengcui.thumedialab.com/papers/NE-DeepVariational.pdf)

### 1.2 Abstract
> Network embedding, aiming to embed a network into a low dimensional vector space while preserving the inherent structural properties of the network, has attracted considerable attentions recently. Most of the existing embedding methods embed nodes as point vectors in a low-dimensional continuous space. In this way, the formation of the edge is deterministic and only determined by the positions of the nodes. However, the formation and evolution of real-world networks are full of uncertainties, which makes these methods not optimal. To address the problem, we
propose a novel Deep Variational Network Embedding in Wasserstein Space (DVNE) in this paper. The proposed method learns a Gaussian distribution in the Wasserstein space as the latent representation of each node, which can simultaneously preserve the network structure and model the uncertainty of nodes. Specifically, we use 2-Wasserstein distance as the similarity measure between the distributions, which can well preserve the transitivity in the network with a linear computational cost. Moreover, our method implies the mathematical relevance of mean and variance by the deep variational model, which can well capture the position of the node by the mean vectors and the uncertainties of nodes by the variance. Additionally, our method captures both the local and global network structure by preserving the first-order and second-order proximity in the network. Our experimental results demonstrate that our method can effectively model the uncertainty of nodes in networks, and show a substantial gain on real-world applications such as link prediction and multi-label classification compared with the state-of-the-art methods.

## 2. 理論
### 2.1 概要
　自然言語処理と同様に、ガウス分布を用いてネットワークを空間に埋め込むことを考えます。ただし、`KL divergence`を用いている既存の手法とは異なり、`Wasserstein distance`を空間の距離に用います。これにより、`KL divergence`を用いることで失われてしまう`transitivity`を保持しようと試みます。

### 2.2 Notations
　記号は以下のように定義されています。
<img width="533" alt="スクリーンショット 2020-04-14 15.58.22.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/ebf3f388-d7c9-9629-d480-0a5c41176af0.png">
<img width="538" alt="スクリーンショット 2020-04-14 15.58.48.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/f821d989-6e44-691f-6d2e-bfa5efea0dc1.png">


### 2.3 Problem Definition
　3つの問題設定を行なっています。なお、`proximity`についての記述は以下の通りです。
<img width="497" alt="スクリーンショット 2020-04-14 16.24.48.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/9bb6d29d-3c09-3869-eea2-5f60243e4424.png">


#### 2.3.1 First-Order Proximity
<img width="529" alt="スクリーンショット 2020-04-14 16.25.25.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/f3608791-116e-592f-9eb6-c08e68066eea.png">

　`first-order proximity`の解釈は以下の通りです。レコメンデーションと同様に、得られるデータがスパースであることが機能的な制約となっています。
<img width="538" alt="スクリーンショット 2020-04-14 16.28.16.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/596b44d0-6725-c610-fa39-f900d07fc968.png">


#### 2.3.2 Second-Order Proximity
<img width="532" alt="スクリーンショット 2020-04-14 16.25.44.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/16f08c03-4cbc-f57c-4caf-cf96b670da98.png">
　友達の友達は友達みたいな関係ですね。`first-order`だとデータがスパースなのでより拡張した範囲までノード間の類似度計算に利用しているようですね。

#### 2.3.3 Gaussian-Based Network Embedding
<img width="539" alt="スクリーンショット 2020-04-14 16.26.14.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/f60dd817-2e0d-1c35-3b19-a6063621c06f.png">

### 2.4 DEEP VARIATIONAL NETWORK EMBEDDING
#### 2.4.1 Framework
<img width="564" alt="スクリーンショット 2020-04-14 16.33.24.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/7a9a83eb-ebb4-5a50-bed4-90a3f0e00965.png">

#### 2.4.2 Similarity Measure
　`transitivity`を保持した状態で分布間の距離を計算するために`Wasserstein distance`を利用します。一般式（`p-Wasserstein distance`）は以下の通りです。
<img width="589" alt="スクリーンショット 2020-04-14 16.40.13.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/52cd6723-e9b9-c38c-24d1-1ed10baf3d8b.png">
　この値を直接計算すると計算時間が大きく実用的でないので回避します。そこで今回は計算時間を短縮可能だと既に判明している`2-th Wasserstein distance`($W_2$)を用います。すると、以下のようにガウス分布間の距離を計算できます。
<img width="530" alt="スクリーンショット 2020-04-14 16.45.44.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/c4faad9f-4846-7e86-4bbc-07c31a049b44.png">

　更に、今回対象とする対角共分散を用いた場合は式(2)が以下のように簡略化されます。
<img width="569" alt="スクリーンショット 2020-04-14 16.47.24.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/abbe6543-ed32-2042-4c04-eab92c774b26.png">

#### 2.4.3 Loss Function
　`first-order proximity`と`second-order proximity`を保持するように損失関数を設計します。
　`first-order proximity`についての記述は以下の通りです。入力の組の近さが$W_2$の大小として表現されています。その後エネルギー関数を用いて損失を定義しています。最終的には`first-order proximity`を有する組の類似度が大きくなります。
<img width="594" alt="スクリーンショット 2020-04-14 16.50.30.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/0d5bb5d5-76bc-2370-051c-e81bb1d0644d.png">

　`second-order proximity`についての記述は以下の通りです。序盤は`Wasserstein Auto-Encoders
(WAE)`について記述しています。
<img width="558" alt="スクリーンショット 2020-04-14 16.56.25.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/cb22edcd-32fe-0d68-9ce7-6e23b9b2eec1.png">

　なお、全体の損失関数は以下の通りです。
<img width="383" alt="スクリーンショット 2020-04-14 17.02.15.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/927205a6-6c4f-7f5d-f646-10f76ada5bb4.png">

## 3. 実験
　
### 3.1 Dataset

- Cora
- Facebook
- BlogCatalog
- Flicker
<img width="611" alt="スクリーンショット 2020-04-14 17.03.49.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/16ce6702-efcc-17a8-c7d3-21d9c44e2f9b.png">


### 3.2 Network Reconstruction
　`AUC`での評価結果は以下の通りです。
<img width="531" alt="スクリーンショット 2020-04-14 17.25.06.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/985fae61-6a03-518c-d793-6581ba286330.png">

### 3.3 Link Prediction
<img width="557" alt="スクリーンショット 2020-04-14 17.26.15.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/eea286b4-d6fa-ff2b-480a-e163999cc565.png">

### 3.4 Embedding Uncertainty
　分布での埋め込みによってノードの不確実性を捉えられているか評価します。まずスパースなネットワークほど分散が大きくなるという直感を検証します。手順は以下の通りです。
<img width="617" alt="スクリーンショット 2020-04-14 17.34.01.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/4f5da815-eaca-5eb1-8e3b-c9196d77b457.png">
　図4(a)から、学習した分散がネットワークの密度を反映していることがわかりました。更に追加の実験として、ノイズへの対処に分散が有用であるか検証します。手順は以下の通りです。
<img width="626" alt="スクリーンショット 2020-04-14 17.39.10.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/f56e78ed-db09-1eba-6b26-45d49edf9b40.png">
　提案手法（`DVNE`）が最も`AUC`の減衰を低く抑えていることが分かります。

<img width="524" alt="スクリーンショット 2020-04-14 17.27.15.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/426293/b7fc3273-7ef2-2882-18f6-3b4efa86818a.png">


## 参考文献

- Dingyuan Zhu, Peng Cui, Daixin Wang, Wenwu Zhu (2018). Deep Variational Network Embedding in Wasserstein Space, http://pengcui.thumedialab.com/papers/NE-DeepVariational.pdf