Deep Learning

GraphGAN是一种结合了图神经网络和生成对抗网络（GAN）概念的机器学习模型。它旨在通过对抗学习框架解决图数据中的节点分类和链接预测问题，特别是在缺少标签数据的情况下。GraphGAN通过结合生成器和判别器两个主要组件来学习图中节点的有效表示。 GraphGAN的框架如下：设\(G=(V,\mathcal{E})\)为一个给定的图，其中\(V=\begin{Bmatrix}v_1,\ldots,v_V\end{Bmatrix}\)代表顶点的集合，而$\mathcal{E} = \left\{ e_{ij} \right\}_{i,j=1}^{V}$代表边的集合。对于给定的顶点\(\nu_{c}\)，定义\(\mathcal{N}\left(\nu_{c}\right)\)为直接连接到\(\nu_{c}\)的顶点集，也就是顶点\(\nu_{c}\)的1-hop邻居。我们将顶点\(\nu_{c}\)的真实连通性分布表示为条件概率\(p_{\mathrm{true}}\left(\nu|\nu_{c}\right)\)，它反映了\(\nu_{c}\)的连通性偏好和它所连接顶点的类型。从这个视角来看，\(\mathcal{N}\left(\nu_{c}\right)\)可以被看作是从\(p_{\mathrm{true}}\left(\nu|\nu_{c}\right)\)抽取的一组观察样本。给定图\(\mathrm{G}\)，GraphGAN旨在学习以下两个模型： 生成器\(\mathrm{G}\)和判别器\(\mathrm{D}\)作为两个对手: 生成器\(\mathrm{G}\)将试图完美地匹配\(p_{\mathrm{true}}\left(\nu|\nu_{c}\right)\)并生成类似于\(\nu_{c}\)的真实直接邻居的相关顶点以欺骗判别器。而判别器\(\mathrm{D}\)则相反，会尝试检测这些顶点是\(\nu_{c}\)的真实邻居还是由其对手\(\mathrm{G}\)生成的。形式上， \(\mathrm{G}\)和\(\mathrm{D}\)在一个有以下价值函数\(V(G,D)\)的双人博弈中进行对抗： \(\min_{\theta_G}\max_{\theta_D}V(G,D)=\sum_{c=1}^V\left(\mathbb{E}_{\nu\sim p_{\mathbf{tne}}(\nu|\nu_c)}\left[\log D(\nu,\nu_c;\theta_D)\right]+\mathbb{E}_{\nu\sim p_G(\nu|\nu_c;\theta_G)}\left[\log\left(1-D(\nu,\nu_c;\theta_D)\right)\right]\right)\)       （1） 上式描述的最小最大（Minimax）博弈公式是生成对抗网络的核心。在图生成对抗网络（GraphGAN）的上下文中，生成器\(\mathrm{G}\)的目标是生成看起来像真实数据的样本。在GraphGAN的情境下，生成器试图生成看似是\(\nu_{c}\)的1-hop邻居的顶点。而鉴别器\(\mathrm{D}\)的目标是区分输入样本是来自于真实数据还是生成器生成的假数据。在GraphGAN中，它试图区分一个顶点对\((\nu,\nu_{c})\)是否是真实的1-hop邻点对。这个公式包含了两个期望（Expectations）： 第一部分为真实数据的期望\(E_{v\sim p_{\mathrm{true}}\left(v\mid v_{c}\right)}\left[\log

Deep Graph Infomax（DGI）是一种基于图的无监督学习方法，其主要目标是学习图中节点的有效表示，即图数据的Embedding。DGI由Petar Veličković等人在2019年的论文中提出，这种方法通过最大化局部图结构（节点）和全局图结构（整个图）之间的互信息来学习节点表示，DGI整体的模型计算流程如图1所示。 从图1可以看出，第一步，算法需要一个正常图\((X,A)\)的扰动版本\((\widetilde{X},\widetilde{A})\)，扰动版本通过负样本操作\(\mathrm{C}\)来实现。负样本操作可以通过多种方式实现，本质是一个函数。这个函数会接受图的节点特征\(\mathbf{X}\)和邻接矩阵\(\mathrm{A}\)作为输入，然后对原图结构进行变换，比如随机打乱节点的特征，或者在邻接矩阵中随机重排列边。目的是创建一个与原始图在统计特性上有显著区别的样本，这个负样本在后续步骤中用来帮助判别器学习如何区分图的正样本表示和与图不相关的表示。 第二步使用编码器函数\(\varepsilon(X,A)\)处理原始图的每个节点，从而得到每个节点的向量表示。这里的编码器\(\mathcal{E}\)通常是一个图神经网络（如GCN），它能够考虑节点的特征以及节点之间的连接（通过邻接矩阵\(\mathrm{A}\)）来产生一个低维而信息丰富的特征向量\(\boldsymbol{h}_i\)。编码器的目的是捕获节点的局部图结构和节点特征，生成的集合\((H,A)=h_1,h_2,\cdots,h_n\)包含了输入图所有节点的这些表示。同理，在上一步中采样的负样本也需要经过编码器\(\boldsymbol{\varepsilon}\)的处理得到对应的\((\widetilde{H},\widetilde{A})\)。 第三步，算法需要从整个输入图的节点表示中提取一个单一的图级别的表示\(\mathbf{s}\)。这通常通过一个汇总函数\(R\left(\boldsymbol{H},A\right)\)完成，它可以是简单的平均节点表示，或者一个更复杂的结构，如基于注意力的汇总方法。这个图级别的表示\(\mathbf{s}\)应该捕获整个图的全局性质，它将在损失函数中用于比较正样本和负样本的节点表示。 最后一步是模型学习的关键。在这一步中，通过梯度下降来更新编码器\(\boldsymbol{\varepsilon}\)、汇总函数\(\text{R}\)以及判别器\(\text{D}\)的参数。判别器也是一个图神经网络，其任务是根据节点表示（\(h_{i}\)或\(h_{j}\)）和图表示来判断节点是否属于该图。损失函数\(\text{L}\)在正样本的情况下鼓励判别器给出高的得分，而在负样本的情况下给出低的得分。通过最大化损失函数中定义的互信息量，模型能够训练出区分原始图节点和负样本节点表示的能力。 这个训练过程的目标是调整模型的参数，使得从正样本图中提取的节点表示与图的全局表示尽可能接近，而从负样本图中提取的节点表示则与图的全局表示尽可能远。即最大化节点表示和对应图级表示的互信息。这种方法认为，如果节点表示能够捕捉到与整个图表示高度相关的信息，那么这些节点表示就是有用的。这便完成了DGI的主要目标：学习图中节点的有效表示，即图数据的Embedding。 随机游走算法的目的也是学习图中节点的有效表示，且与DGI同属无监督学习方法，但在方法和理念上存在显著差异。随机游走侧重于通过模拟从一个节点开始的随机路径来捕捉图中节点的局部连接模式，以探索和利用图的局部结构特性。这种方法通过观察节点间的“游走”行为，直接反映了节点的邻近关系。相比之下，DGI采用基于互信息最大化的策略，通过学习节点表示和全局图表示之间的互信息来提取特征，不仅考虑了局部结构，还尝试捕捉整个图的全局上下文。DGI通常使用图神经网络如图卷积网络（GCN）作为编码器，更侧重于深度学习技术。总体而言，随机游走方法更加直观和简单，适用于图的局部特征学习；而DGI则是一种更复杂的深度学习方法，能够综合局部与全局信息，适合于需要深层特征提取的复杂图形任务。 此外，DGI（Deep Graph Infomax）和GAN（生成对抗网络）虽然都涉及到一个判别器组件，但它们的目标和训练过程有本质的不同。GAN由两个模型组成：生成器（Generator）和判别器（Discriminator）。生成器的目标是创建尽可能接近真实数据的新数据实例，而判别器则试图区分真实数据和生成器创建的伪造数据。这两个模型在训练过程中相互竞争，生成器不断改进其生成的数据质量以试图“欺骗”判别器，而判别器也不断改进其识别真伪数据的能力。这种对抗性的训练过程导致了生成器学会生成高质量的数据。DGI的目的不是生成新的数据，而是从图数据中学习有用的节点表示。在DGI中，判别器的作用不是与编码器对抗，而是帮助编码器学习生成高质量的节点嵌入。DGI使用一个非对抗的信息最大化原则，这个原则指导编码器生成的节点表示要包含足够的信息以便判别器可以准确区分节点是来自原始图还是扰动后的图（即正样本或负样本）。换句话说，判别器用于指导编码器捕捉到有意义的特征——使得这些特征对于区分不同图结构是有信息的。DGI的目标是通过这种方式提升表示的质量，而不是在编码器和判别器之间创建对抗。

对比GCN讲解RGCN的基本思想。GCN通过将图的邻接矩阵与节点特征结合，利用统一的权重矩阵\(\mathrm{W}\)来更新节点的特征，从而捕获图中的拓扑结构信息。这种方法在处理同质图时非常有效，即所有节点和边被假定具有相同的类型和属性。然而，GCN不直接处理图中的异质性或复杂的关系类型。 与GCN不同，RGCN（Relational Graph Convolutional Neural Network）被设计用来处理具有多种关系的异构图。此时，节点或边的种类有很多种情况，每种类型可能有其特定的属性和语义。例如，在生物医学的异构图中，不同类型的节点（如药物分子、疾病名称、蛋白质名称、生物通路等）和边（如促进、抑制、治疗、包含等）包含丰富的语义信息。RGNN能够对这些不同类型的实体和关系分别学习表示，这样能够更好地理解它们各自以及它们之间的复杂关系。用公式表示为： \(G=(V,E,R,T)\) 其中\(\text{V}\)为节点集，每个节点在下文表示为\(\nu_{i}\)；\(\text{E}\)为边集，边\((\nu_{i},r,\nu_{j})\in E\)；\(T(\nu_{i})\)为节点类型；\(\mathrm{R}\)为边类型集合，\(r_{i}\)在下文表示每个边的属性。 【例1】边有三种不同的类型\((r_1,r_2,r_3)\)，分别用三种不同的线段格式表示，如图1所示。例如，节点A通过类型为\(r_{1}\) 的边与节点B和D相连，通过类型为\(r_{2}\) 的边与节点C相连等等。图1中也展示了关系图卷积网络（RGCN）的一个关键特点：不同类型的边使用不同的权重矩阵\((W_{_{r1}},W_{_{r2}},W_{_{r3}})\)来处理信息。这意味着，当更新一个节点的特征时，RGCN 会根据边的类型使用不同的权重矩阵。值得注意的是，在这个例子中，\(r_{1}\) 有三种类型，但这并不意味着要维护三个独立的神经网络。实际上，\(W_{_{r1}},W_{_{r2}},W_{_{r3}}\)可以共同组成一层神经网络的参数。假设用于更新边信息的神经网络输入输出都是由12个神经元组成的网络层，那么第1-3个神经元可以用于更新第一种边类型；第4-6个神经元用于更新第二种边类型；第7-9个神经元用于更新第三种边类型。 RGCN为每种类型的边引入了不同的权重矩阵，以此来捕获不同关系类型之间的细微差异。每一种关系类型的权重矩阵负责编码特定类型的边对节点特征更新的贡献。这样，RGCN能够综合节点的特征以及与其相连的各种类型边的信息，生成更丰富的节点表征。实际上，RGNN更像是一种思想，而不是固定的模型，它可以扩展到其它GNN模型上，如GraphSAGE、RGAT等。节点\(\mathrm{i}\)的特征更新规则在RGCN中可以表示为： \(\boldsymbol{h}_i^{(l+1)}=\sigma\left(\sum_{r\in R}\sum_{j\in N_r(i)}\frac{1}{c_{i,r}}\boldsymbol{W}_r^{(l)}\boldsymbol{h}_j^{(l)}\right)\) 其中： 在每一层中，对于每种类型的关系\(\mathrm{r}\)，我们首先使用权重矩阵\(W_{r}^{(l)}\)来转换与节点\(\mathrm{i}\)相连的每个邻居节点\(\mathrm{j}\)的特征。然后，我们将所有这些转换后的特征进行加权求和，其中每个邻居的特征向量除以归一化常数\(c_{i,r}\)，以避免不同数量的邻居对聚合结果的不均衡影响。最终，我们对所有关系类型的累加结果应用非线性激活函数，以得到节点\(\mathrm{i}\)在下一层的新特征向量\(h_i^{(l+1)}\)。这种机制允许RGCN分别学习不同类型的关系如何影响节点特征，而不是像GCN那样对所有边一视同仁，或者像GraphSAGE那样只是简单地聚合邻居节点的特征。

Gated GCN 结合了GCNs的空间聚合能力和LSTM中的门控机制。这种结构设计旨在解决传统GCN在处理复杂图数据时面临的信息过载和信息损失问题。每个节点的状态更新不仅依赖于其邻居的信息，还受到门控机制的控制。这种操作使得网络可以在每一层学习到如何最有效地聚合邻近节点的信息，同时根据任务的需要丢弃无关信息，使其能够适应不同的图结构和动态变化的图数据，提供了更精细的信息处理能力。Gated GCN的模型设计如图1所示。 从图1中可以看到节点特征向量\(h_{i}\)和边特征向量\(e_{ij}\)的具体数据更新流程。首先每个节点\(\mathrm{i}\)在每一层\(\mathrm{l}\)有一个特征表示\(h_i^l\)，节点\(\mathrm{i}\)邻居节点的特征向量集合为\(\begin{Bmatrix}h_j^l\end{Bmatrix}\)。每条边\((i,j)\)在每一层\(\mathrm{l}\)也有一个特征表示\(\boldsymbol{e}_{ij}\)。节点特征\(h_{i}^{l}\)通过矩阵\(U^{l}\)和\(A^{l}\)转换。相邻节点的特征\(\begin{Bmatrix}h_j^l\end{Bmatrix}\)通过矩阵\(V^{l}\)和\(B^{l}\)转换。边特征\(\begin{Bmatrix}e_{ij}^l\end{Bmatrix}\)通过矩阵\(C^{l}\)转换，这里的矩阵实际上是神经网络层中的参数矩阵。节点特征\(h_{i}^{l}\)、邻居节点的特征\(\begin{Bmatrix}h_j^l\end{Bmatrix}\)和边特征\(\begin{Bmatrix}e_{ij}^l\end{Bmatrix}\)分别经过\(A^{l}\)、\(B^{l}\)和\(C^{l}\)映射后的新特征表示将进行求和（Sum）操作，这一步的含义是进行边特征与节点特征的信息交互和融合，求和后的结果会经过激活函数ReLU的处理。处理后的结果一方面作为更新后的边特征\(\begin{Bmatrix}\boldsymbol{e}_{ij}^{l+1}\end{Bmatrix}\)；另一方面将经过Sigmoid函数\(\sigma\)的处理产生一个门控信号，这个门控信号与相邻节点特征的加权（经过\(V^{l}\)变换后的\(h_{j}^{l}\)）和相乘，实际上是对每个邻居节点的贡献进行缩放。这就是门控机制，它控制着信息的流向，与LSTM中的门控机制类似。最终，门控后的信息被累加到当前节点特征上 （经\(U^{l}\)变换后的\(h_{i}^{l}\)），通过一个求和（Sum）操作。结果再次通过ReLU激活函数得到当前层的输出结果。 经过上述处理后得到的结果\(\boldsymbol{h}_i^{l+1}\)是节点\(\mathrm{i}\)在下一层\(\mathrm{l+1}\)的新特征表示。同时，边的特征也更新为\(e_{ij}^{l+1}\)。这个过程体现了Gated GCN在图卷积中加入门控机制的重要性。通过调节门控信号，模型能够控制每个节点在其邻居之间传递的信息量，这样就可以捕捉到图中更加复杂的结构模式，同时减少不必要的信息传递，提高了模型的泛化能力和处理大规模图数据的效率。

在讲解Graph Isomorphism Network（GIN）之前，有必要先学习了解一下GNN模型的表达能力（Expressive Power），即GNN将不同图数据表示为不同嵌入向量的能力。这里会涉及一个被称为计算图的概念，图神经网络（GNN）的计算图是一种数据结构，它表示图中的节点以及它们之间的连接关系，用于有效地实施图数据上的学习算法。在这种结构中，每个节点聚合其邻居节点的信息，通过多次迭代更新其状态，从而捕捉和利用图的局部连接性质。为了研究GNN模型的表达能力，先来了解一下图数据的局部信息结构，如图1所示。 考虑图1两跳（2-hop）范围内计算图的几个特殊情况： （1）节点1和节点4，具有相同度数，但到其两跳（2-hop）邻居的信息上度数不同，导致计算图结构不同，因此可以区分这两个节点，如图2所示。 （2）节点1和节点5，因其自身度数不同而具有不同的局部结构信息，如图3所示。 （3）节点1和节点2，具有相同度数，也具有相同的邻居结构，在两跳邻居上，都具有相同的局部结构，如图4所示。 在图4的情况下，假设所有节点的初始化特征向量相同，且聚合节点信息时仅考虑两跳范围内的信息，那么节点1和节点2将被嵌入到同一个表示向量，GNN无法区分这两个节点。相比之下节点3、4、5由于计算图不同，理论上是可能由GNN区分开的。GNN模型应该有将不同的计算图映射到不同的节点向量的能力。想要区分不同的计算图，聚合的方式是关键，聚合函数表达能力越强，GNN表达能力越强。 然而，不管是求和、求平均，还是求最大值这些广泛被使用的聚合方式，都不是最佳的选择，如图5所示，两种图数据的计算图是不同的。但针对图5 (a)的初始化节点向量，求平均和求最大值的聚合方式都不能有效的区分出不同的计算图。类似的，对于图5(b)的初始化节点向量，求和的聚合方式也不能有效区分这两种计算图。这是因为图通过聚合节点向量后却得到了相同的新的节点向量。 从数学的角度上来讲，希望GNN的聚合函数是一种单射函数（Injective Function），即可把不同的元素映射成不同输出。换句话说，希望GNN的聚合函数能把不同的计算图映射生成不同的节点向量。显然，求和函数、求平均函数、求最大值函数都不是单射函数。根据Xu et al. 在论文Graph Wavelet Neural Network中得到定理可知：任一单射函数都可以表示为： \(\phi(\sum_{x\in