论文笔记-Deep Learning on Graphs: A

2021-12-18 本文已影响0人升不上三段的大鱼

论文链接：https://arxiv.org/pdf/1812.04202.pdf

关于图卷积：论文笔记-Deep Learning on Graphs: A Survey（上）

4.2 读出操作

使用图卷积操作，可以学习有用的节点特征来解决许多以节点为中心的任务。然而，为了解决以图为中心的任务，需要聚合节点信息以形成图级表示。在文献中，这种程序通常称为读出操作（readout operation）。

读出操作也与图的粗化（graph coarsening）有关，（将一个较大的图缩小为一个较小的图），因为可以通过将图粗化为单个节点来获得图形级表示。

CNN可以进行多级卷积或池运算，降低分辨率。但图缺乏网格结构，无法直接使用。

图读出操作的一个关键要求，该操作应该对节点顺序保持不变，即，如果我们使用两个节点集之间的双射函数更改节点和边的索引，则整个图的表示不应改变。

4.2.1 统计学

最简单的顺序不变的操作就是统计运算，比如求和、求平均或者 max-pooling。

另一种聚合节点表示的常用方法是添加一个全连接（FC）层作为最终层。这种方法的优点是模型可以为不同的节点学习不同的权重；然而，这种方法无法保证顺序不变性。

4.2.2 层次聚类

除了节点和图级结构之外，图还表现出丰富的层次结构，可以通过层次聚类方法进行探索。例如，基于密度的 agglomerative clustering，multi-resolution spectral clustering。 Cheb-Net 和 MoNet 采用了另一种贪心分层聚类算法 Graclus ，一次合并两个节点，并采用快速池化方法将节点重新排列为平衡二叉树。 ECC 通过特征分解进行分层聚类。然而，这些层次聚类方法都独立于图卷积（即，它们可以作为预处理步骤执行，而不是以端到端的方式进行训练）。

DiffPool 提出了一种与图卷积联合训练的可微层次聚类算法，作者提出使用隐藏表示来学习每一层的 soft cluster assignment matrix:
$S^l = f(A^l, H^l) \tag{30}$
这个“粗化”图的节点表示和新的邻接矩阵可以通过根据 $S^l$ 取平均获得:
$H^{l+1} = (S^l)^T \hat{H}^{l+1}, A^{l+1}=(S^l)^TA^lS^l \tag{31}$
其中 $\hat{H}^{l+1}$ 是通过对 $H^l$ 图卷积得到的。初始节点数 $N_0=N$ ，最后一层 $N_L=1$ ，即单个节点代表整个图。

由于集群分配操作是软的，集群之间的连接不是稀疏的；因此，该方法的时间复杂度原则上为 O（N2）。

什么是 soft clustering？
传统的聚类算法会将一个点分配到一个聚类，这种分配是一种硬分配（hard assignment），如果一个点到第一个聚类中心和到第二个聚类中心的距离一样，但是被分配到了第一个聚类，那么它就不会出现在第二个聚类里。
而软聚类（soft assignment）为每个点分配一个概率向量，而不是一个固定的标签。向量的长度等于找到的聚类数。向量的第 i个概率值是该点属于第 i 个集群成员的概率。

简而言之，平均或求和等统计数据是最简单的读出操作，而与图卷积联合训练的层次聚类算法更先进，但也更复杂。还有一些其他方法，例如添加伪节点或强加节点顺序等。

4.3 改进方法

4.3.1 Attention 机制

在GCN中，节点邻域以相等或预定义的权重聚集。然而，邻居的影响可能会有很大差异。受 Attention 机制的启发，GAT （graph attention networ）通过修改式（13）中的卷积运算，将注意机制引入GCN，如下：
$h_i^{l+1} = \rho (\sum_{j \in N(i)} \alpha_{i,j}^l h_j^l \Theta^l) \tag{32}$

其中 $\alpha_{i,j}^l$ 是在第 l 层的节点 $v_i$ 对节点 $v_j$ 的attention：

$\alpha_{i,j}' = \frac{exp(LeakyReLU(F(h_i^l \Theta ^l)))}{\sum_{k \in N(i) } exp(LeakyReLU(F(h_i^l \Theta^l, h_k^l \Theta^l)))} \tag{33}$

这里的 $F()$ 是另一个需要学习的函数，比如多层感知器（MLP）。为了提高模型的容量和稳定性，作者还建议使用多个独立注意并连接结果，即多头注意机制，如下图。

GAT 中提出的多头部注意机制。每种颜色表示一个独立的 attention 向量

HAN 为异构图提出了一种两级注意机制，即节点级和语义级注意机制。具体来说，节点级注意力机制类似于 GAT，但也考虑了节点类型；因此，它可以为聚合基于元路径（meta-path）的邻居分配不同的权重。然后语义级注意力学习不同元路径的重要性并输出最终结果。

4.3.2 Residual 与Jumping

许多研究观察到，现有 GCN 最合适的深度通常非常有限，例如 2 层或 3 层。这个问题可能是由于训练深度 GCN 所涉及的实际困难或过度平滑问题，即更深层中的所有节点具有相同的表示。为了解决这个问题，可以将类似于 ResNet 的残差连接添加到 GCN，通过实验表明，添加残差连接可以让网络的深度增加，这与 ResNet 的结果类似：
$H^{l+1}=\rho (\tilde{D} ^{- \frac{1}{2}} \tilde{A} \tilde{D}^{- \frac{1}{2} }H^l \Theta^l) + H^l \tag{34}$

Column network（CLN）采用了类似的思想，使用了以下具有可学习权重的残差连接：
$h_i^{l+1} = \alpha_i^l \odot \tilde{h}_i^{l+1} + (1-\alpha_i^l) \odot h_i^l \tag{35}$

受个性化 PageRank 的启发，PPNP 定义了具有连接到初始层的图卷积：
$H_{l+1}= (1−α) \tilde{D}^{−1/2 } \tilde{A } \tilde{D}^{−1/2}H^l+αH^0,\tag{37}$
其中 $H_0=F_θ(F^V)$ 和 $α$ 是一个超参数。所有参数都在 $F_θ(·)$ 中，而不是在图卷积中。

Jumping knowledge networks（JK-Nets）提出了另一种架构，将网络的最后一层与所有之前的隐藏层连接，将所有的表示“跳转”到最终的输出，通过这种方式，模型可以学习选择性地利用来自不同层的信息。JK-Nets 的公式如下：
$h_ i^{final} = AGGREGATE(h_i^0, h_i^1, \cdots, h_i^L) \tag{38}$

JK-Nets使用了三个与 GraphSAGE 类似的聚合函数：concatenation、max-pooling 和 LSTM attention。实验结果表明，增加 jumping connection 可以提高多个GCN的性能。

4.3.3 Edge Features

对于具有离散值的简单边缘特征，如 edge type，一种简单的方法是针对不同的边缘类型训练不同的参数并聚合结果。

DCNN 提出了另一种方法，将每个边转换为连接到该边的头和尾节点的节点。经过这种转换，边特征可以被视为节点特征。

LGCN 构建了一个线图以结合边的特征。线图中的节点是原始图中的有向边，如果信息可以通过原始图中相应的边流动，则线图中的两个节点是连接的。然后，LGCN采用了两个GCN：一个在原始图上，一个在线图上。