一、说明
二、GCN网挑战是什么？
在社交网络中，朋友联系可以通过社交图实现。
在语音识别中，音素Yi和声学模型xi形成HMM（语音识别图）。
即使在CNN上，输入图像也可以建模为图形。例如，下图是 5 × 5 图像的图表。每个节点代表一个像素，对于 3 × 3 滤波器的情况，每个节点都连接到其八个直接邻居。
尽管以这种方式表示图像是矫枉过正的，但很大一部分机器学习 （ML） 问题对于通过图形建模来说是非常自然和有效的。特别是，当相邻节点之间的关系是不规则和高维的时，我们需要明确定义它们才能有效地解决它们。在CNN中，我们在欧几里得空间工作。权重如何与输入要素（像素）相关联已明确定义。
但图表并非如此。例如，下面的图表是相同的，即使它在空间上看起来不同。
通常，神经网络 （NN） 采用输入 x 来预测 z。
这就引出了神经网络如何直接处理图的挑战。
在GCN（图卷积网络）中，NN的输入将是图形。此外，它不是推断单个 z，而是推断图形中每个节点 i 的值 zi。为了对Zi进行预测，GCN在计算中同时利用了Xi及其相邻节点。
让我们更详细一点。
三、图卷积网络 （GCN）
GCN的一般思想是在图上应用卷积。GCN 没有将 2-D 数组作为输入，而是将图形作为输入。
源
下面的第一个图（第一行）是我们所知道的NN，第二个图是GCN，其中包含四个节点作为输入的图形。
在第一个 NN 中，它包含多个密集层（全连接层）。x 是第一层的输入，zi 是第 i 层的输出。对于每一层，我们将z（或第一层的x）与权重矩阵W相乘，并将输出传递给激活函数σ，例如ReLU。GCN非常相似，但σ的输入是ÂHⁱWⁱ而不是Wizi。即 σ（Wizi） v.s. σ（ÂHⁱWⁱ），其中 zi 和 Hⁱ 分别是 NN 和 GCN 最后一个隐藏层的输出向量。但请注意，Wⁱ 和 Wi 是不同的，并且具有不同的尺寸。对于 GCN 中的第一层，X 包含一个节点数组，而不是单个节点 x。X 将被编码为矩阵，每行包含节点的特征。
那么什么是 Â？GCN 引入了邻接矩阵 A。如果节点 i 和 j 连接，则 A 中的元素 Aij 等于 1。否则，它将为零。所以 Â 表示节点的邻居。但我们将再进行一次调整，以表明所有节点都是自连接的。这表明隐藏层中节点的输出取决于其自身及其邻居。因此，我们将 A 的所有对角线元素转换为 1 以形成 Â。 在数学上，Â 等于 A + I。
这就涉及到要σ的隐藏层的输出（ÂHⁱWⁱ）。如果我们忽略W一秒钟，对于隐藏层中的每个节点，ÂHⁱ将每个节点上的特征与其邻居相加。
但是，如果我们对隐藏层输出的范围没有一定的控制，我们可能会在 NN 中面临递减或爆炸问题。具体来说，GCN希望对输出特征向量进行归一化以保持输出特征向量的比例。一种可能性是用 D̂⁻¹ 进行多个 Â，其中 D̂ 是测量每个节点度数的对角线节点度数矩阵。在高层次上，与其将自己与邻居相加，不如将总和乘以反向 D̂⁻¹ 来取平均值。具体来说，D̂ 是一个对角矩阵，每个对角线元素 D̂ii 计算相应节点 i 的边数。每个隐藏层的输出变为σ（D̂⁻¹ÂHⁱWⁱ），而不是σ（ÂHⁱWⁱ）。
让我们在我们的示例中计算 D̂。对于无向图，节点的度数计为边在该节点处终止的次数。因此，自循环将计数两次。在我们的示例中，节点 0 有 2 条连接到其邻居的边和一个自环路。它的度数等于 4（即 2 + 2）。对于节点 3，其度数等于 5 （3 + 2）。
D̂⁻¹ 等于
下图总结了到目前为止讨论的模型。在此示例中，它有 3 个隐藏层，对于每个隐藏层，它将其输出计算为 σ （D̂⁻¹ÂHⁱWⁱ）。用于从最后一层输出计算隐藏层输出的方程称为传播规则。
除了使用σ（D̂⁻¹ÂHⁱWⁱ）之外，还有其他选择。实际上，传播规则可以概括为：
不同的f选择导致模型的不同变体。作为预览，GCN论文应用了下面的传播规则
 和 D̂⁻¹ 的计算方式与以前相同。但是，让我们推迟稍后的讨论，转而使用一个示例。让我们用Zachary的空手道俱乐部网络问题来演示它。
扎卡里的空手道俱乐部
有一个空手道俱乐部有两个主要利益相关者：教练（Hi先生）和管理员。不幸的是，他们之间的争端导致它分裂成两个俱乐部。原始成员需要选择一个方面并选择加入哪一方。他们的决定将基于他们与 Hi 先生或管理员的关系。这还包括他们与与其关联的成员的连接程度。下图是成员之间表示连接的社交图。
来源：维基百科（成员#从1开始）
让我们再组织一下图表，蓝色和红色是会员将加入哪个俱乐部的基本事实（Hi先生的俱乐部在下面用红色标记）。
成员 # 从 0 开始
为了找到俱乐部会员资格，我们在下面应用了两个隐藏层，Hⁱ⁺¹ = σ（D̂⁻¹ÂHⁱWⁱ）。输入将是上面的社交图（没有俱乐部标签），最后一个隐藏层将是输出。
最后一个隐藏层为每个节点输出 2 个标量潜在特征，我们使用这些值来表示一个节点。好的部分是，在这个例子中，即使没有训练，我们也可以仅基于社交图来计算潜在表示。我们使用 W⁰ 运行模型进行一次迭代，W¹ 使用正态分布随机初始化。但是我们不打算执行梯度下降来更新W。对于 X，我们只是使用单位矩阵，因为没有节点特征（因为我们事先不知道这些特征）。
最后，我们使用输出潜在特征作为 x 和 y 坐标绘制每个节点。
此模型使用 σ（D̂⁻¹ÂHⁱWⁱ） 作为传播规则
如图所示，当我们用其基本事实（蓝色表示 Hi 俱乐部，红色表示管理员）为每个节点着色时，生成的潜在特征与一个人属于哪个俱乐部高度相关。简而言之，我们只是在输入社交图谱上应用聚类。直观地说，我们的示例生成了与其相邻特征相似的潜在特征，因为隐藏层正在对其相邻特征进行潜在特征的平均化。该算法通过生成与其邻居相关的潜在因素，设法将邻居聚类在一起。
让我们考虑一个用于分类或聚类的半监督问题，其中每个类或聚类只标记一个数据点。一旦计算出每个节点的潜在特征，我们就可以计算出未标记数据和标记数据之间的距离。然后，我们找到已知标记数据的最近邻居，对未标记的数据进行分类或聚类。
源
到目前为止讨论的所有传播规则都是可微分的。对于半监督或无监督问题，如果需要，我们可以使用反向传播来使用标记数据来训练权重。（对于我们的最后一个示例，即使没有额外的培训，结果也很好。作为演示，下面的 GCN 模型经过 300 次迭代的训练。在此模型中，每个类仅提供一个标签。随着训练的进行，我们看到属于相同真实值类的节点如何开始聚类在一起。
源
四、光谱图卷积
工程问题可以在空间域或频谱域（又称频域）中解决。例如，在信号处理中，我们应用傅里叶变换将音频输入从时域转换为频域，并应用低通滤波器来消除高频噪声。在卷积中，可以使用空间或光谱方法定义这些滤波器。将哪个域用于特定步骤取决于设计过滤器的难易程度以及执行操作的难易程度。
源
在深度学习中，研究人员还从空间或光谱域进行卷积。例如，在上一节中，我们应用了σ（D̂⁻¹ÂHⁱWⁱ）形式的空间图卷积。
源
但GCN实际上是一个频谱图卷积。它是谱图卷积的局部一阶近似，传播规则如下。
导致此新传播规则的过程可能非常漫长。但是彻底理解它以使用它并不是很重要。特别是，新规则与以前的规则非常相似。我们只是添加了更多的数学理由。请随意快速浏览接下来的两个部分。
五、光谱图卷积
但是，它需要一些数学概念，方程和一些研究论文来解释频谱图卷积。由于其复杂性，我们将仅显示高级步骤。
卷积滤波器是平移不变的，允许权重共享（相同的滤波器在输入上滑动）。在空间域中工作时，它可以独立于其空间位置识别相同的要素。图形没有明确的空间概念或空间平移的数学定义。这就引出了关于空间图过滤器所基于的数学基础的问题。
另一方面，频谱图卷积基于频谱图理论。它提供了一个数学框架来设计具有平移不变属性的运算符（过滤器）。这并不意味着空间图过滤器是非科学的。但有时，他们可能会回到经验结果来证明理由。
在高层次上，通过在输入信号x上应用滤波器gθ，在傅里叶域中定义频谱图卷积。
以前，我们使用邻接矩阵 A 对图进行建模，并使用对角节点度矩阵 D 对其进行归一化。在谱图理论下，无向图由归一化图拉普拉斯矩阵L表示，定义为
L 是一个实对称的正半定矩阵。但是对于 N×N 矩阵，如果它是正半定的，则它具有 N 个正交特征向量。（我们将跳过此处的证明。简而言之，这些 N 个独立向量构成了可以对角化矩阵的基础，即 L 可以分解为 L = UΛUT，如下所示，其中 U 包含 L 的特征向量，Λ 是包含相应特征值的对角矩阵。这些特征向量也称为图傅里叶模态，对应的特征值是图的频率。
拉普拉斯量由傅里叶基 U 对角化，谱卷积将定义为具有 U 的线性算子。具体来说，x 上的图傅里叶变换定义为
这里，图卷积算子在傅里叶域中定义。它是图x与傅里叶空间中的滤波器的乘法。即
x *G g 表示使用滤波器 g 对 x 执行频谱卷积。
如果我们将过滤器表示为
那么图卷积可以简化为：
谱卷积神经网络假设滤波器 gθ 是一个充满可学习参数 Θkij 的对角矩阵。Θkij 包含图层 k 的参数，用于将第 i个输入要素映射到第 j个输出要素。对于层 k，隐藏层输出的输出为
这是频谱图卷积的数学框架。
光谱图卷积的不足之处
虽然谱图理论具有具有明确定义的平移属性的运算符，但计算L的特征向量是计算昂贵的。我们希望避免这种情况。另一个缺点是这些过滤器通常没有本地化。我们可能不会只访问每个节点的第 k个最近邻居。它的复杂性随着图形的大小而增加，并且不可扩展。事实上，为了有效地计算节点的输出，我们应该跳过有限数量的邻居，比如从中心节点最多跳 K 个。这导致了将近似应用于频谱图卷积的研究，例如ChebNet和GCN中的卷积，使得过滤器是本地化的。而由于这个问题，空间图卷积近年来也受到了更多的关注。
切博网
那么我们如何在光谱图卷积中找到局部滤波器呢？切比雪夫光谱CNN（ChebNet）使用切比雪夫多项式Tk（x）高达K阶的截断展开来近似滤波器gθ。
具有定义滤波器 gθ 的图 x 的卷积变为：
这是 K 局部的，因为它是拉普拉斯算中的 K 次多项式。它仅取决于距离中心节点最多 K 步的节点（详细信息）。这意味着它位于空间中并且无论图形大小如何都可以很好地缩放。甚至ChebNet和GCN也是从频谱图卷积开始的，它们应用近似，使其滤波器被定位。
因为 Ti（L̂） 可以写成：
卷积变为
因此，我们不需要计算特征向量，它是局部的。
六、GCN模型
GCN通过假设K = 1和λmax = 2来引入ChebNet的一阶近似。等式变为
为了减少自由参数的数量并避免过度拟合，GCN 假设 θ = θ₀= −θ₁，方程变为
但是下面的 L.H.S. 项的特征值在 [0， 2] 范围内，为了避免爆炸/消失问题，应用了一个重整化技巧，导致下面的 R.H.S. 项。
最后，GCN 的传播规则为
（本节中的公式学分：来源 1 和 2。
接下来，我们将进入空间图卷积。
七、空间图卷积
不同的空间图卷积依赖于不同的聚合器来从每个节点的邻居那里收集信息。从概念上讲，我们也可以将其视为消息传递。
如果没有频谱图卷积中的近似值，空间图卷积通常更具可扩展性，因为它们的过滤器是本地化的。主要挑战是定义CNN的局部不变性，这些CNN与具有不同数量邻居的中心节点一起工作。在接下来的几节中，我们将快速概述不同的空间图卷积方法。我们可能会提出有时可能需要您连接点的方程式。但为了不进一步延长文章，请参阅个别论文以了解详细信息。
消息传递神经网络 （MPNN）
MPNN 概述了空间图卷积的通用消息传递框架。它沿边缘将信息（消息）从一个节点传递到另一个节点，并重复 K 步，让信息在图中传播。下面的等式是节点 v 的第 k层的隐藏特征表示。 这取决于 v 及其相邻要素在前一层中的隐藏要素以及与其相邻要素的边要素。 U 和 M 函数的不同选择将导致模型的不同变体。
可以将最后一个隐藏层中节点的潜在表示传递给输出层以执行节点级预测。或者，它可以传递给具有可学习参数的读出函数 R，以执行图形级预测。
例如，在药物发现中，图形表示以原子为节点，化学键为边缘的化合物。我们可能想对这种化合物是否可以阻碍癌细胞的生长或致癌进行分类。因此，我们可以在进行图级预测时用上面的等式进行读数。
扩散卷积神经网络 （DCNN）
DCNN将图卷积视为扩散过程。它将信息从一个节点传输到其邻居之一，概率转换矩阵 P 等于 D⁻¹A。这个过程将重复K次，以便信息分布达到平衡。第 k 步的隐藏表示 H k 将从 Pk 计算，但不是从最后一个隐藏表示计算的。
DCNN 将 H⁽¹⁾、H⁽²⁾、· · ·、H⁽K⁾ 连接在一起，形成最终的模型输出。
图同构网络 （GIN）
然而，GIN声称MPNN方法中的图嵌入无法区分不同的图结构。一个好的方案应该区分不同的图结构，并将它们映射到嵌入空间中的不同潜在特征。为了解决这个问题，GIN引入了一个可学习的参数εk来调整中心节点的权重。
图贤者
社交影响者有很多联系。对于具有许多边的节点的图形，卷积可能无法很好地缩放。GraphSage 使用采样为每个节点获取固定数量的邻居，以便传递消息，而不是所有相邻节点。
源
这是公式：
或者，我们可以先计算邻居的聚合值。例如，我们可以使用 LSTM 聚合器来计算邻居的表示形式。然后我们将值与中心节点连接起来并应用密集层。否则，我们可以将 W 应用于所有邻居，后跟一个激活函数和一个最大池。
源
采样
FastGCN进一步完善了采样算法。FastGCN 不是对每个节点的邻居进行采样，而是使用重要性采样来减少方差。它从反映其与其他节点的连接程度的分布 q 中对节点 （u） 进行采样。然后，应用重要性抽样从u估计节点v的损失梯度。
源
图注意力网络 （GAT）
GAT 使用注意力来学习消息传递中两个连接节点之间的相对权重。首先，GAT 计算节点对 i 和 j 的注意力。得到的向量 Whi（hi 是节点 i 的隐藏表示）和 Whj 被连接起来 （|| 运算符）并与可学习向量 a 相乘。他们的注意力，测量他们之间的连接强度，然后用softmax函数计算。
然后，节点 i 的隐藏表示由计算的注意力α加权，最终结果为
混合模型网络
MoNet 使用节点伪坐标来确定节点与其邻居之间的相对位置。假设节点 y 是节点 x 的邻居。首先，计算伪坐标 u（x， y） 的 d 维向量如下。MoNet论文使用节点的度数（连接数）作为伪坐标，然后用全连接网络进一步变换它们。
Modified from source
一旦计算出两个节点之间的相对位置，权重函数就会将相对位置映射到这两个节点之间的相对权重。该权重函数 w 由可学习参数 θ 参数化，并由 J 个分量组成：
在MoNet中，权重函数定义为：
where μⱼ and Σⱼ are trainable parameters for a Gaussian.
我们来总结一下。图像的坐标系 (x, y) 在欧几里得空间中定义，输出像素值为 f(x, y)。通过 MoNet，上面的权重函数使我们能够将概念扩展到非欧几里得空间，并应用可在不同位置工作的共享过滤器。下面是在 f 上应用卷积滤波器 g 的详细方程。
MoNet 可以通过 u 和权重函数的不同选择进行推广。下图显示了如何使用特定的 u 和 w 将不同的 GNN 视为 MoNet。
源
大规模可学习图卷积网络 （LGCN）
在每个 LGCL 层中，它为中心节点的邻居的每个输入特征通道选择并排序最大的 k 值。具有中心节点的特征，它形成了一个（k+1）×3矩阵。然后应用 CNN 过滤器。在下图中，应用了两个滤波器来创建具有 5 个输出通道的新节点表示。
从源代码修改
LGCN应用多层LGCL，如下图所示。
源
输入节点使用图形嵌入层转换为低维表示。在某些情况下，它可以简单地使用如下所示的线性变换。
然后是两个具有跳过串联连接的LGCL层以产生输出，即LGCL的输入和输出连接在一起。最后，使用全连接层对每个节点进行分类。
八、池化
在下图中，我们应用卷积层和 ReLU 为每个节点生成潜在表示。
源
但在其他应用中，我们感兴趣的是生成图形的表示。例如，考虑一个样本 （G， y），其中 G 是图形，y 是它的类。作为一个分类问题，我们读取 G 并预测 y — 图的表示。在这种情况下，可以应用池化来生成更粗的图形，该图形可以通过读出操作进一步减少。这类似于传统的CNN，我们应用最大池来降低空间分辨率。
源
通常，池化和读数是相似的，在数学上，可以概括为：
源
CNN
如果有一种一致的方法将图中的节点映射到欧几里得空间，那么在应用过滤器时，哪个权重应该与特定节点相关联就不会有歧义。因此，对于空间图卷积，挑战在于如何一致地为节点分配权重。
下面的两个图形在拓扑上相似，但下面的两个红色边除外。如果两个图中的节点具有相似的网络拓扑，我们将它们的颜色相似。例如，节点 D 和 2 都显示为橙色。
当我们应用卷积过滤器时，两个图都应该为相应的节点生成类似的潜在特征。一种方法是按分配的颜色（例如，按 RGB 值）对节点进行排序，并相应地分配相应的权重。
DGCNN解决了如何按顺序读取图形并以一致顺序关联权重的相同问题。因此，它引入了 SortPooling 层，该层按颜色对图形节点进行排序，以便可以在这些有序节点上训练神经网络。
源
通过根据拓扑以一致的方式呈现图形，一维卷积和密集层将更容易训练。例如，下面的图形是同构的，将以相同的方式呈现在 SortPooling 层之后的 NN 中。
源
那么我们如何在DGCNN中为节点着色呢？它使用Weisfeiler-Lehman算法。
源
这个概念与我们第一个针对Zachary空手道俱乐部的聚类示例非常相似。但我们不会在这里详细介绍。请参考DGCNN文件。基本上，它根据网络拓扑学习节点的网络嵌入（签名）。它将节点的颜色与其直接邻居连接起来，然后按字典顺序对其进行排序以分配新颜色。具有相同签名的节点将被分配相同的颜色。重复该过程，直到颜色收敛或 h 次迭代后。最后，具有相同颜色的节点在图形中共享相同的结构角色。然后，最后一个卷积层中的颜色将用于对节点进行排序。因此，对图形节点施加了一致的排序。排序后，DGCNN 会截断或扩展节点数组。这支持具有不同节点数的图形。
差异池
源
DiffPool基于生成粗图的分层概念。它学习一个带有元素 i 的软聚类分配矩阵 Sl，j 包含层 l 中的节点 i 被聚类并分配给粗图中下一个分层层中的节点 j 的概率。
然后，此软赋值可用于计算下一个分层层的新节点嵌入和邻接矩阵。
方程的来源
由 Sl 生成
该模型是可微的，目标是学习生成Z和S的GNN模型。
