# metapath2vec

###### tags: `GNN`, `autoglab`

## Introduction
同質圖有多種 embedding 方法，如 **node2vec**, **LINE**, **DeepWalk** 等，然而，這些方法很難直接應用在異質圖上，因為異質圖中不同類型 (type) 的 node 數量往往差異懸殊。**metapath2vec** 引進 **metapath** 機制能有效解決上述問題，學習到異質圖上語意與結構的關係。


## Preliminary
1. 異質圖 $G = (V, E, T)$ 包含 node 與 edge 的映射函數 $\phi(v): V \rightarrow T_V$, $\varphi(e): E \rightarrow T_E$，分別將 node 與 edge 映射到不同的**類型**與**關係**，並滿足 $|T_V| + |T_E| > 2$。

2. 異質圖 $G = (V, E, T)$ 的 embedding 任務

學習 node 的 embedding $X \in \mathbb{R}^{|V| \times d}$, 其中 $d \ll |V|$，捕捉 node 的**結構**與**語意**關係。

3. **meta-path scheme** $\mathcal{P}$

一系列**關係**所連起來的路徑

$$
v_1 \xrightarrow{R_1} v_2 \xrightarrow{R_2} \cdot \cdot \cdot v_t \xrightarrow{R_t} v_{t+1} \cdot \cdot \cdot \xrightarrow{R_{l-1}} v_{l}
$$

其中 $v_i$ 為 $i$ 類型的 node，$R_i$ 為異質圖上的某種關係。

<center>
<img src=https://i.imgur.com/S2wpqei.png
width=400>
</center>

## Model

1. **Objective Function**
+ **同質圖**：

$$
\arg\max_{\theta}
\prod_{v \in V} \prod_{c \in N(v)} p(c|v; \theta)
$$

其中，$N(v)$ 為 $v$ 的 neighborhood。

+ **異質圖**：

$$
\arg\max_{\theta} \prod_{v \in V} \ \prod_{t \in T_v} \prod_{c \in N(v)} p(c_t|v; \theta)
$$

其中，$N_t(v)$ 為 node $v$ 所有類型為 $t$-th 的 neighborhood。

2. **Transition Probability (產生文本)**:
> Sun et al. demonstrated that heterogeneous random walks are biased to highly visible types of nodes—those with a dominant number of paths—and concentrated nodes—those with a governing percentage of paths pointing to a small set of nodes
>
> The meta-path-based random walk strategy ensures that the semantic relationships between different types of nodes can be properly incorporated into skip-gram.

\begin{align}
p(v^{i+1}|v^i_t, \mathcal{P})
= \begin{cases}
\frac{1}{|N_{t+1}(v^i_t)|}
\;\;\;
(v^{i+1}, v^i_t) \in E,
\phi(v^{i+1}) = t+1
\\
0
\;\;\;\;\;\;\;\;\;\;\;\;\;
(v^{i+1}, v^i_t) \in E,
\phi(v^{i+1}) \neq t+1
\\
0
\;\;\;\;\;\;\;\;\;\;\;\;\;
(v^{i+1}, v^i_t) \notin E
\end{cases}
\end{align}

其中 $N_{t+1}(v^i_t)$ 為 node $v^i_t$ 所有 node type 為 $(t+1)$-th 的 neighborhood，換句話說，$v^{i+1} \in V_{t+1} \; \forall v^{i+1} \in N_{t+1}(v^i_t)$。只有在給定的 meta-path $\mathcal{P}$，才有不為 $0$ 的 transition probability。

3. **metapath2vec**

同 DeepWalk 與 node2vec，我們使用 **skip-gram** 方法訓練 embedding，藉由中心詞來預測上下文，定義條件機率函數

$$
p(c_t|v; \theta)
= \frac{e^{X_{c_t} \cdot X_v}}{\sum_{u \in V} e^{X_u \cdot X_v}}.
$$

為了緩解計算複雜度，我們使用負採樣 (**negative sampling**) 並重新定義條件機率 $p(c|v; \theta) = \sigma(X_u \cdot X_c)$，對應的目標函數為

$$
\mathcal{O}(X) = \log \sigma(X_{c} \cdot X_{v}) + \sum_{m=1}^{M} \mathbb{E}_{u^m \sim P_c(u)}[\log \sigma(-X_{u^m} \cdot X_v)]
$$

其中 $\sigma(x) = 1/(1+e^{-x})$，$u^m$ 為從分佈 $P_c(u)$ 中採樣出來的負樣本 node。

最大化目標函數，相當於在同一 meta-path 的 nodes 有相近的 embedding，並分離不在同一 meta-path 的 node embeddings，如此一來，能捕捉 meta-path 的語意。

<center>
<img src=https://i.imgur.com/XhWJ6Zr.png
width=400>
</center>

然而，metapath2vec 的負採樣是沒有考慮到 node type，所有 node type 均一視同仁。

2. **metapath2vec++**

metapath2vec++ 對**不同類型**的 node type 做**負採樣**，預測函數為

\begin{align}
p(c_t|v;\theta)
= \frac{e^{X_{c_t} \cdot X_v}}
{\sum_{u_t \in V_t} e^{X_{u_t}\cdot X_v}}
\end{align}

目標函數為

$$
\mathcal{O}(X) = \log \sigma(X_{c_t} \cdot X_{v}) + \sum_{m=1}^{M} \mathbb{E}_{u_t^m \sim P_t(u_t)}[\log \sigma(-X_{u_t^m} \cdot X_v)]
$$

梯度分別為

\begin{align}
&\frac{\partial\mathcal{O}(X)}
{\partial X_{u_t^m}}
= (\sigma(X_{u_t^m} \cdot X_v - \mathbb{I_{c_t}[u_t^m]}))X_v,
\\
&\frac{\partial\mathcal{O}(X)}{\partial X_{v}}
= \sum_{m=0}^M (\sigma(X_{u_t^m} \cdot X_v - \mathbb{I_{c_t}[u_t^m]}))X_{u_t^m}.
\end{align}

其中 $\mathbb{I}_{c_t}[u^m_t]$ 為 indicator 函數，當 $u^m_t$ 為 neighborhood context node $c_t$ 時為 $1$。當 $m=0$ 時 $u^0_t=c_t$。

如下圖所示，metapath2vec++ 輸出 4 個 node type 的輸出。
<center>
<img src=https://i.imgur.com/TAMKo1s.png
width=400>
</center>

## Algorithm

<center>
<img src=https://i.imgur.com/CtRvkuQ.png =600x700
width=400>
</center>

## Results

### Datasets

兩種異質圖 datasets：

1. AMiner Computer Science (CS) dataset
2. Database and Infor- mation Systems (DBIS) dataset

### Tasks

1. Multi-class node classification

將有 label 的 node embedding 拿去訓練 logistic regression classifier。在不同的 training set 比例 5%-90% 下進行實驗。

2. Node clustering

用 k-means 將所學習到的 node embeddings 做分群，並用 normalized mutual information (NMI) 作為 metric。

3. Similarity search

### Setting

1. The number of walks per node $w = 1000$
2. The walk length $l = 100$
3. The vector dimension $d = 128$
4. The neighborhood size $k = 7$
5. The size of negative samples $M = 5$
6. Meta-path scheme $\mathcal{P} = \{APVPA\}$

### Experiment Results

1. Multi-class node classification

<center>
<img src=https://i.imgur.com/NliLF7w.png>
</center>
<center>
<img src=https://i.imgur.com/KscW5TP.png>
</center>

實驗結果顯示 metapath2vec 與 metapath2vec++ 差異不大，前者略佳。與既有方法相比，均有相當大的進步，反映出 metapath2vec 與 metapath2vec++ 良好的 embedding 品質能幫助 classifier 做分類。

下圖為針對 hyper-parameters 做 parameter-sensitivity 實驗，結果顯示 number of walk $w$ 與 walk lenght $l$ 對 performance 有正向幫助，embedding dimension $d$ 與 neighborhood size $k$ 則影響較不明顯。然而，越小的 $k$ 越能區分 authors。


2. Node Clustering

<center>
<img src=https://i.imgur.com/va8xMEP.png
width=400>
</center>

上表顯示 metapath2vec 與 metapath2vec++ 均能為不同類型的 node 取得更好的 embedding 品質 (NMI 值越高越好)。


Parameter sensitivity 實驗與 multi-class node classification 差不多。

3. Similarity Search

Pass

4. Visualization

將學習到的 node embeddings 投影到二維空間做視覺化。

<center>
<img src=https://i.imgur.com/ObFKBdj.png
width=400>
</center>

上圖 (d) 顯示 metapath2vec++ 將相同類型的 nodes 集中成一排，並且有著相當類似的 author-venue 箭頭，這表示 metapath2vec 可能學習到內在的關聯。

然而 (c) 顯示 metapath2vec 傾向於集中 venue 與 author。同時也傾向集中類似的領域，如 Core CS cluster 的 OSDI、SIGCOMM、S&P、ISCA，以及 Big AI cluster 的 KDD、SIGIR、AI、NIPS、ACL、CVPR。

<center>
<img src=https://i.imgur.com/XuU9Ytp.png
width=400>
</center>

上圖顯示 metapath2vec++ 傾向來自相同領域的 conferences 聚集成一群，並分離不同領域的 conferences。

從 Figure 1 與 Figure 5 展示出 metapath2vec++ 有能力發現、建模並捕捉不同類型 nodes 之間的隱藏結構與語意關係。

5. Scalability

<center>
<img src=https://i.imgur.com/cCcH5zC.png
width=400>
</center>

隨著 thread 數量的增加，metapath2vec 與 metapath2vec++ 大致呈現線性加速。

## Code

> code: [metapath2vec.py](https://github.com/pyg-team/pytorch_geometric/blob/master/torch_geometric/nn/models/metapath2vec.py)

1. `MetaPath2Vec(edge_index_dict: Dict[Tuple[str, str, str], torch.Tensor], embedding_dim: int, metapath: List[Tuple[str, str, str]], walk_length: int, context_size: int, walks_per_node: int = 1, num_negative_samples: int = 1, num_nodes_dict: Optional[Dict[str, int]] = None, sparse: bool = False)`
+ `edge_index_dict`
+ `embedding_dim`
+ `metapath`
+ `walk_length`: 採樣序列的長度
+ `context_size`: 提取上下文範圍
+ `walks_per_node`
+ `num_negative_samples`

## Reference

1. https://ericdongyx.github.io/papers/KDD17-dong-chawla-swami-metapath2vec.pdf
2. https://pytorch-geometric.readthedocs.io/en/latest/_modules/torch_geometric/nn/models/metapath2vec.html