[ 文献阅读·综述 ] Deep Learning on Graphs: A Survey [1]
推荐理由：图神经网络的survey paper，在很多的领域展现出了独特的作用力，分别通过GRAPH RNN（图循环网络）、GCN（图卷积）、GRAPH AUTOENCODERS（图自编码器）、GRAPH REINFORCEMENT LEARNING（图强化学习模型）、GRAPH ADVERSARIAL METHODS（图对抗模型）等五个类型的模型进行阐述，可以让大家对图神经网络有一个整体的认识。
5.图自动编码器
自动编码器（AE）及其变体广泛应用于无监督学习任务中，适合于学习图的节点表示。隐含的假设是，图有一个内在的，潜在的非线性低秩结构。在这一节中，本文首先阐述了图自动编码器，然后介绍了图变分自动编码器和其他改进。下表总结了GAE的主要特征：
5.1.自动编码器
- 图的自动编码器的使用起源于稀疏自动编码器（SAE）。其基本思想是，通过将邻接矩阵或其变化作为节点的原始特征，AEs可以作为一种降维技术来学习低维节点表示。具体而言，SAE采用了以下L2-reconstruction loss：
min Θ L 2 = ∑ i = 1 N ∥ P ( i , : ) − P ^ ( i , : ) ∥ 2 P ^ ( i , : ) = G ( h i ) , h i = F ( P ( i , : ) ) (43) \begin{gathered} \min _{\boldsymbol{\Theta}} \mathcal{L}_{2}=\sum_{i=1}^{N}\|\mathbf{P}(i,:)-\hat{\mathbf{P}}(i,:)\|_{2} \\ \hat{\mathbf{P}}(i,:)=\mathcal{G}\left(\mathbf{h}_{i}\right), \mathbf{h}_{i}=\mathcal{F}(\mathbf{P}(i,:)) \end{gathered}\tag{43} ΘminL2=i=1∑N∥P(i,:)−P^(i,:)∥2P^(i,:)=G(hi),hi=F(P(i,:))(43) - 然而，SAE是建立在错误的理论分析基础上的，其有效性的机制尚不清楚。
- Structure deep network embedding（SDNE）填补了这一难题，它表明等式（43）中的L2重建损失实际上对应于节点之间的二阶接近度，即如果两个节点具有相似的邻域，则它们共享相似的latten表示，这是网络科学中一个被广泛研究的概念，被称为协同过滤或三角闭包。由于网络嵌入方法表明一阶邻近性也很重要，SDNE通过添加另一个拉普拉斯特征映射项修改了目标函数：
- min Θ L 2 + α ∑ i , j = 1 N A ( i , j ) ∥ h i − h j ∥ 2 (44) \min _{\boldsymbol{\Theta}} \mathcal{L}_{2}+\alpha \sum_{i, j=1}^{N} \mathbf{A}(i, j)\left\|\mathbf{h}_{i}-\mathbf{h}_{j}\right\|_{2}\tag{44} ΘminL2+αi,j=1∑NA(i,j)∥hi−hj∥2(44)
- 例如，如果两个节点直接相连，它们也共享相似的潜在表示。作者还通过使用邻接矩阵并为零和非零元素分配不同的权重来修改L2重建损失：
- L 2 = ∑ i = 1 N ∥ ( A ( i , : ) − G ( h i ) ) ⊙ b i ∥ 2 (45) \mathcal{L}_{2}=\sum_{i=1}^{N}\left\|\left(\mathbf{A}(i,:)-\mathcal{G}\left(\mathbf{h}_{i}\right)\right) \odot \mathbf{b}_{i}\right\|_{2}\tag{45} L2=i=1∑N∥(A(i,:)−G(hi))⊙bi∥2(45)
- GC-MC采用了不同的方法，使用Kipf和Welling提出的GCN作为编码器：
H = G C N ( F V , A ) (46) \mathbf{H}=G C N\left(\mathbf{F}^{V}, \mathbf{A}\right)\tag{46} H=GCN(FV,A)(46)
其使用简单的双线性函数作为解码器：
A ^ ( i , j ) = H ( i , : ) Θ d e H ( j , : ) T (47) \hat{\mathbf{A}}(i, j)=\mathbf{H}(i,:) \Theta_{d e} \mathbf{H}(j,:)^{T}\tag{47} A^(i,j)=H(i,:)ΘdeH(j,:)T(47) - DRNE没有重建邻接矩阵或其变体，而是提出了另一种改进方法，通过使用LSTM聚集邻域信息来直接重建低维节点向量。具体而言，DRNE采用了以下目标函数：
L = ∑ i = 1 N ∥ h i − LSTM ( { h j ∣ j ∈ N ( i ) } ) ∥ (48) \mathcal{L}=\sum_{i=1}^{N}\left\|\mathbf{h}_{i}-\operatorname{LSTM}\left(\left\{\mathbf{h}_{j} \mid j \in \mathcal{N}(i)\right\}\right)\right\|\tag{48} L=i=1∑N∥hi−LSTM({hj∣j∈N(i)})∥(48) - Graph2Gauss (G2G)将每个节点编码为高斯分布
h
i
=
N
(
M
(
i
,
:
)
,
diag
(
Σ
(
i
,
:
)
)
)
\mathbf{h}_{i}=\mathcal{N}(\mathbf{M}(i,:), \operatorname{diag}(\Sigma(i,:)))
hi=N(M(i,:),diag(Σ(i,:)))来获得节点的不确定性。具体而言，作者使用从节点属性到高斯分布均值和方差的深度映射作为编码器：
M ( i , : ) = F M ( F V ( i , : ) ) , Σ ( i , : ) = F Σ ( F V ( i , : ) ) (49) \mathbf{M}(i,:)=\mathcal{F}_{\mathbf{M}}\left(\mathbf{F}^{V}(i,:)\right), \mathbf{\Sigma}(i,:)=\mathcal{F}_{\mathbf{\Sigma}}\left(\mathbf{F}^{V}(i,:)\right)\tag{49} M(i,:)=FM(FV(i,:)),Σ(i,:)=FΣ(FV(i,:))(49) - 他们不使用显式解码器函数，而是使用成对约束来学习模型：
- K L ( h j ∥ h i ) < K L ( h j ′ ∥ h i ) ∀ i , ∀ j , ∀ j ′ s.t. d ( i , j ) < d ( i , j ′ ) (50) \begin{array}{r} \mathrm{KL}\left(\mathbf{h}_{j} \| \mathbf{h}_{i}\right)<\mathrm{KL}\left(\mathbf{h}_{j^{\prime}} \| \mathbf{h}_{i}\right) \\ \forall i, \forall j, \forall j^{\prime} \text { s.t. } d(i, j)<d\left(i, j^{\prime}\right) \end{array}\tag{50} KL(hj∥hi)<KL(hj′∥hi)∀i,∀j,∀j′ s.t. d(i,j)<d(i,j′)(50)
- 换句话说，这些约束确保节点表示之间的KL散度与图距离具有相同的相对顺序。然而，由于式（50）难以优化，因此采用基于能量的损耗作为松弛：
- L = ∑ ( i , j , j ′ ) ∈ D ( E i j 2 + exp − E i j ′ ) (51) \mathcal{L}=\sum_{\left(i, j, j^{\prime}\right) \in \mathcal{D}}\left(E_{i j}^{2}+\exp ^{-E_{i j^{\prime}}}\right)\tag{51} L=(i,j,j′)∈D∑(Eij2+exp−Eij′)(51)
5.2.变分自动编码器
- 与前面提到的自动编码器不同，变分自动编码器（VAEs）是另一种将降维与生成模型相结合的深度学习方法。它的潜在好处包括容忍噪音和学习平滑表示。VAE首先在VGAE中引入图形数据，其中解码器是一个简单的线性积：
p ( A ∣ H ) = ∏ i , j = 1 N σ ( h i h j T ) (52) p(\mathbf{A} \mid \mathbf{H})=\prod_{i, j=1}^{N} \sigma\left(\mathbf{h}_{i} \mathbf{h}_{j}^{T}\right)\tag{52} p(A∣H)=i,j=1∏Nσ(hihjT)(52)
其中，节点表示被假定为服从高斯分布， q ( h i ∣ M , Σ ) = N ( h i ∣ M ( i , : ) , diag ( Σ ( i , : ) ) ) q\left(\mathbf{h}_{i} \mid \mathbf{M}, \mathbf{\Sigma}\right)=\mathcal{N}\left(\mathbf{h}_{i} \mid \mathbf{M}(i,:), \operatorname{diag}(\boldsymbol{\Sigma}(i,:))\right) q(hi∣M,Σ)=N(hi∣M(i,:),diag(Σ(i,:)))。对于均值和方差矩阵的编码器，作者还采用了Kipf和Welling提出的GCN：
M = G C N M ( F V , A ) , log Σ = G C N Σ ( F V , A ) (53) \mathbf{M}=G C N_{\mathrm{M}}\left(\mathbf{F}^{V}, \mathbf{A}\right), \log \mathbf{\Sigma}=G C N_{\Sigma}\left(\mathbf{F}^{V}, \mathbf{A}\right)\tag{53} M=GCNM(FV,A),logΣ=GCNΣ(FV,A)(53)
然后，通过最小化变分下界来学习模型参数：
L = E q ( H ∣ F V , A ) [ log p ( A ∣ H ) ] − K L ( q ( H ∣ F V , A ) ∥ p ( H ) ) (54) \mathcal{L}=\mathbb{E}_{q\left(\mathbf{H} \mid \mathbf{F}^{V}, \mathbf{A}\right)}[\log p(\mathbf{A} \mid \mathbf{H})]-\mathrm{KL}\left(q\left(\mathbf{H} \mid \mathbf{F}^{V}, \mathbf{A}\right) \| p(\mathbf{H})\right)\tag{54} L=Eq(H∣FV,A)[logp(A∣H)]−KL(q(H∣FV,A)∥p(H))(54)
然而，由于这种方法需要重建完整的图形，其时间复杂度为 O ( N 2 ) O\left(N^{2}\right) O(N2)。 - 在SDNE和G2G的启发下，DVNE提出了另一种图数据VAE，它也将每个节点表示为高斯分布。与已有的采用kl散度作为度量的方法不同，DVNE采用Wasserstein距离来保持节点相似度的传递性。与SDNE和G2G类似，DVNE在其目标函数中也保留了一阶和二阶邻近性：
min Θ ∑ ( i , j , j ′ ) ∈ D ( E i j 2 + exp − E i j ′ ) + α L 2 (55) \min _{\boldsymbol{\Theta}} \sum_{\left(i, j, j^{\prime}\right) \in \mathcal{D}}\left(E_{i j}^{2}+\exp ^{-E_{i j^{\prime}}}\right)+\alpha \mathcal{L}_{2}\tag{55} Θmin(i,j,j′)∈D∑(Eij2+exp−Eij′)+αL2(55)
其中， E i j = W 2 ( h j ∥ h i ) E_{i j}=W_{2}\left(\mathbf{h}_{j} \| \mathbf{h}_{i}\right) Eij=W2(hj∥hi)是高斯分布 h j \mathbf{h}_{j} hj和 h i \mathbf{h}_{i} hi二阶Wasserstein距离，且 D = { ( i , j , j ′ ) ∣ j ∈ N ( i ) , j ′ ∉ N ( i ) } \mathcal{D}=\left\{\left(i, j, j^{\prime}\right) \mid j \in \mathcal{N}(i), j^{\prime} \notin \mathcal{N}(i)\right\} D={(i,j,j′)∣j∈N(i),j′∈/N(i)}是一组三元组，对应于一阶邻近度的排名损失。重建损失定义如下：
L 2 = inf q ( Z ∣ P ) E p ( P ) E q ( Z ∣ P ) ∥ P ⊙ ( P − G ( Z ) ) ∥ 2 2 (56) \mathcal{L}_{2}=\inf _{q(\mathbf{Z} \mid \mathbf{P})} \mathbb{E}_{p(\mathbf{P})} \mathbb{E}_{q(\mathbf{Z} \mid \mathbf{P})}\|\mathbf{P} \odot(\mathbf{P}-\mathcal{G}(\mathbf{Z}))\|_{2}^{2}\tag{56} L2=q(Z∣P)infEp(P)Eq(Z∣P)∥P⊙(P−G(Z))∥22(56)
其中P是转移矩阵，Z表示从H中提取的样本。该框架如图9所示。使用这种方法，目标函数可以最小化，就像使用重参数化技巧的常规VAE一样。
5.3.改进和讨论
5.3.1.对抗训练
- GAEs引入一种对抗性的训练方案，作为ARGA中的一个额外的正则化项。总体架构如图10所示。具体而言，GAEs的编码器用作生成器，而鉴别器旨在区分潜在表示是来自生成器还是来自先验分布。通过这种方式，自动编码器*匹配先验分布作为正则化。目标函数是：
min Θ L 2 + α L G A N (57) \min _{\boldsymbol{\Theta}} \mathcal{L}_{2}+\alpha \mathcal{L}_{G A N}\tag{57} ΘminL2+αLGAN(57)
其中 L 2 \mathcal{L}_{2} L2是GAEs的重建损失，而 L G A N \mathcal{L}_{G A N} LGAN如下：
min G max D E h ∼ p h [ log D ( h ) ] + E z ∼ G ( F V , A ) [ log ( 1 − D ( z ) ) ] (58) \min _{\mathcal{G}} \max _{\mathcal{D}} \mathbb{E}_{\mathbf{h} \sim p_{\mathbf{h}}}[\log \mathcal{D}(\mathbf{h})]+\mathbb{E}_{\mathbf{z} \sim \mathcal{G}\left(\mathbf{F}^{V}, \mathbf{A}\right)}[\log (1-\mathcal{D}(\mathbf{z}))]\tag{58} GminDmaxEh∼ph[logD(h)]+Ez∼G(FV,A)[log(1−D(z))](58)
其中， G ( F V , A ) \mathcal{G}\left(\mathbf{F}^{V}, \mathbf{A}\right) G(FV,A)是使用等式（53）中的图形卷积编码器的生成器， D ( ⋅ ) \mathcal{D}(\cdot) D(⋅)是基于交叉熵损失的鉴别器，ph是先验分布。研究采用简单的高斯先验，实验结果验证了对抗训练方案的有效性。 - 同时，NetRA还提出了使用生成对抗网络（GAN）来增强图自动编码器的泛化能力。具体而言，作者使用了以下目标函数：
min Θ L 2 + α 1 L L E + α 2 L G A N (59) \min _{\Theta} \mathcal{L}_{2}+\alpha_{1} \mathcal{L}_{L E}+\alpha_{2} \mathcal{L}_{G A N}\tag{59} ΘminL2+α1LLE+α2LGAN(59)
其中， L L E \mathcal{L}_{L E} LLE是拉普拉斯特征映射目标函数，如式（44）所示。此外，作者采用LSTM作为编码器来聚集来自类似于等式（48）的邻域的信息。在DRNE中，作者使用随机游动来生成输入序列，而不是像DRNE那样只对近邻进行采样并使用度对节点进行排序。与ARGA不同的是，NetRA将GAEs中的表示作为基本真值，并采用随机高斯噪声和MLP作为发生器。
5.3.2.归纳学习
- 与GCNs类似，如果编码器中包含节点属性，则GAEs可应用于归纳学习设置。这可以通过使用GCN作为编码器来实现，例如在GC-MC、VGAE和VGAE中，或者通过直接从G2G中的节点特征学习映射函数来实现。由于只在学习参数时利用边缘信息，因此该模型也可以应用于训练过程中看不见的节点。这些工作还表明，虽然GCNs和gae基于不同的体系结构，但是可以联合使用，这是一个很有前途的方向。
5.3.3. 相似性度量
- GAEs中采用了许多相似性度量，如图AEs的L2重构损失、Laplacian特征映射和排序损失，图VAEs的KL散度和Wasserstein距离。尽管这些相似性度量基于不同的动机，但是如何为给定的任务和模型体系结构选择合适的相似性度量仍然没有研究。需要更多的研究来理解这些指标之间的潜在差异。
参考文献
[1] Zhang Z, Cui P, Zhu W. Deep learning on graphs: A survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2020.