系列文章
《Graph Representation Learning》笔记 Chapter2

An Encoder-Decoder Perspective

编码 The Encoder

编码是将节点 $v\in \mathcal{V}$ 映射至向量 embeddings $z_v\in {\mathbb{R}}^d$ 的函数， $d$ 为 embedding 的维数，表示为
$$\begin{gathered} ENC:\mathcal{V}\to {\mathbb{R}}^d \\ ENC(v)=Z[v] \end{gathered}$$
其中 $Z\in {\mathbb{R}}^{|\mathcal{V}|\times d}$ ， $Z[v]$ 代表 $Z$ 的第 $v$ 行。

解码 The Decoder

解码是根据 embeddings 重建图结构。比如，根据 $Z[u]$ 预测相邻节点 $\mathcal{N}(u)$ （邻接矩阵 $A[u]$ ）。标准方法是定义 pairwise decoders，表示为
$$DEC:{\mathbb{R}}^d\times {\mathbb{R}}^d\to {\mathbb{R}}^{+}$$
它可以解释为预测节点对之间的相似性，目标是使重构损失最小
$$DEC(ENC(u),ENC(v))=DEC(z_u,z_v)\approx S[u,v]$$
其中， $S$ 是相似性矩阵（见Chapter2笔记），我们的目的是预测两节点是否相邻，所以 $S\triangleq A$ ，即 $S$ 等价于 $A$ 。

Optimizing an Encoder-Decoder Model

为了实现我们的重构目标（损失最小），标准做法是最小化训练节点对集合 $\mathcal{D}$ 的重构损失
$$\mathcal{L}=\sum _{(u,v)\in \mathcal{D}}l(DEC(z_u,z_v),S[u,v])$$
其中， $l:\mathbb{R}\times \mathbb{R}\to \mathbb{R}$ 是计算解码相似度与真实相似度之间偏差的损失函数。

Factorization-based approaches

Laplacian eigenmaps

定义解码为两节点 embeddings 之间的L2距离
$$DEC(z_u,z_v)=\Vert z_u-z_v{\Vert }_2^2$$
损失函数为解码后的值乘以权重，权重为相似性度量
$$\mathcal{L}=\sum _{(u,v)\in \mathcal{D}}DEC(z_u,z_v)\cdot S[u,v]$$
直观来看，当相似节点的 embeddings 距离过大时，上式会惩罚模型。若构造 $S$ 使其满足邻接矩阵 $A$ 的属性
$$\begin{array}{rl}\mathcal{L}& =\sum _{(u,v)\in \mathcal{D}}\sum _d(z_u[d]-z_v[d]{)}^{2}S[u,v]\\ & =\sum _d\sum _{(u,v)\in \mathcal{D}}{z}_u[d{]}^{2}S[u,v]+z_v[d{]}^{2}S[u,v]-2z_u[d]z_v[d]S[u,v]\\ & =\sum _{d}2(\sum _{u\in \mathcal{D}}{z}_u[d{]}^{2}D[u,u]-\sum _{(u,v)\in \mathcal{D}}{z}_u[d]S[u,v]z_v[d])\\ & =\sum _{d}2(Z^{T}LZ)[d]\end{array}$$
其中 $Z\in {\mathbb{R}}^{|\mathcal{D}|\times d}$ ，最小化 $L$ 与上一节讨论的谱聚类 spectral clustering 的解决方案相同，即选取最小的 $d$ 个 $L$ 的特征值所对应的特征向量郭建 embeddings 。

内积方法 Inner-product method

假定两节点之间的相似性与它们 embeddings 的点积成正比
$$DEC(z_u,z_v)=z_u^T{z}_v$$
采用均方误差
$$\begin{array}{rl}\mathcal{L}& =\sum _{(u,v)\in \mathcal{D}}\Vert DEC(z_u,z_v)-S[u,v]{\Vert }_2^2\\ & =\Vert Z^{T}Z-S{\Vert }_2^2\end{array}$$
GF 方法直接使用 $S\triangleq A$ ，GraRep 方法使用 $A$ 的幂定义 $S$ ，HOPE 方法采用Chapter2中邻域重叠的方法定义 $S$ 。

Rabndom walk embeddings

DeepWalk and node2vec

我们的目标是学习 embeddings ，使其满足
$$DEC(z_u,z_v)\triangleq \frac{e^{z_u^{T}zv}}{{\sum }_{v_k\in \mathcal{V}}{e}^{z_u^T{z}_k}}\approx p_{\mathcal{G},T}(v|u)$$
其中 $p_{\mathcal{G},T}(v|u)$ 是从节点 $u$ 以长度为 T ∈ { 2 , . . . , 10 } T ∈ \{2, ..., 10\} T∈{2,...,10} 的路径到达 $v$ 的概率。
为了训练 embeddings ，需要最小化交叉熵损失
$$\mathcal{L}=\sum _{(u,v)\in \mathcal{D}}-log(DEC(z_u,z_v))$$
node2vec 引入了负样本
$$\mathcal{L}=\sum _{(u,v)\in \mathcal{D}}-log(\sigma (z_u^T{z}_v))-\gamma {\mathbb{E}}_{v_n\sim P_n(\mathcal{V})}[log(-\sigma (z_u^T{z}_{v_n}))]$$
其中， $\sigma$ 代表 logistic 函数，可近似表示 $DEC$ ， $P_n(\mathcal{V})$ 表示负样本（两节点间没有边）集合的分布， $\gamma >0$ 是超参数。

Large-scale information network embeddings(LINE)

LINE结合了两项 encoder-decoder ，第一项目的是编码一阶邻接信息，训练时的相似性度量 $S=A$ ，使用如下解码
$$DEC(z_u,z_v)=\frac{1}{1+e^{-z_u^T{z}_v}}$$
第二项比较像 random walk 方法，解码形式与上式相同，但训练时的相似性度量 $S=A^2$