October 10, 2022

图神经网络学习

图神经网络从入门到入土

啊啊啊啊啊啊啊啊啊啊啊看不懂看不懂看不懂看不懂看不懂
不你可以看懂你可以看懂你可以看懂你可以看懂你可以看懂

一些概念

又要开始递归学习了……………………

卷积

如何通俗易懂地解释卷积？这篇文章讲的很清楚。

$$f(x)*g(x) = \displaystyle \int^{\infty}_{-\infty}f(\tau)g(x-\tau)d\tau$$

卷积的物理意义大概可以理解为：系统某一时刻的输出是由多个输入共同作用（叠加）的结果。
对图而言，用到的都是离散卷积。而离散卷积简单来讲本质上就是一种加权求和。

二维离散卷积的定义：
$$(f*g)(m,n)= \sum_i \sum_j f(i,j)g(m-i,n-j)$$

不同的图像处理函数（矩阵g）决定了输出图像（g与原始图像卷积之后的图像）是变得模糊还是锐利。
实际计算时会计算采用g翻转（上下左右翻转后）的矩阵与原图像的内积（对应点相乘相加）。

以前学信号的时候觉得这定义好抽象，根本不能理解，现在看了别人的解释感觉确实每一个公式都有它的来源……

神经网络

神经网络时由具有适应性的简单单元组成的广泛并进行互连的网络，它的组织能够模拟生物神经系统对真实世界物体所作出的交互反应。

M-P神经元模型

神经元接收到来自n个其他神经元传递过来的输入信号，这些输入信号通过带权链接进行传递，神经元接受到的总输入值将与神经元的阈值进行比较，然后通过激活函数（亦称响应函数）处理以产生神经元的输出。

理想中的激活函数是阶跃函数，它将输入映射为0或1。但是由于阶跃函数不连续、不光滑，因此常用的激活函数是Sigmoid函数。

把许多个这样的神经元按一定的层次结构连接起来，就得到了神经网络。

事实上，我们只需要知道，神经网络是一个包含了许多参数的数学模型，这个模型是若干函数，例如$y_i=f(\sum_i w_ix_i - \theta_j)$相互（嵌套）带入而得。

CNN(Convolutional Neural Network 卷积神经网络)

对于卷积公式 $$f(x)*g(x) = \displaystyle \int^{\infty}_{-\infty}f(\tau)g(x-\tau)d\tau$$
在图像分析中， $f(x)$ 是 原始像素点(source pixel) ，$g(x)$是作用点，所有作用点合起来称为 卷积核(Convolution kernel) ，二者的卷积结果称为 目标像素(destination pixel) 。

CNN的核心在于它的kernel，kernel是一个个小窗口，在图片上平移，通过卷积的方式来提取特征。这里的关键在于图片结构上的平移不变性：一个小窗口无论移动到图片的哪一个位置，其内部的结构都是一模一样的，因此CNN可以实现参数共享。

CNN中的卷积本质上就是利用一个共享参数的过滤器（kernel），通过计算中心像素点以及相邻像素点的加权和来构成feature map实现空间特征的提取，加权系数就是卷积核的权重系数。

那么卷积核的系数如何确定的呢？是随机化初值，然后根据误差函数通过反向传播梯度下降进行迭代优化。这是一个关键点，卷积核的参数通过优化求出才能实现特征提取的作用，GCN的理论很大一部分工作就是为了引入可以优化的卷积参数。

Graph embedding（图嵌入）

图分析任务

说明

真实的图（网络）往往是高维、难以处理的，为了将高维的图放到低维中去研究，图嵌入算法应运而生。
简而言之，图嵌入算法是为了降低高维图的维度，即降维技术。
首先根据实际问题构造一个D维空间中的图，然后将图的节点嵌入到d（d<<D）维向量空间中。嵌入的思想是在向量空间中保持连接的节点彼此靠近。

图嵌入的挑战

一些线代定义

度矩阵(degree matrix)

度矩阵是对角阵，对角上的元素为各个顶点的度。

邻接矩阵(adjacent matrix)

邻接矩阵表示顶点间关系。
行数和列数对应坐标写入两个节点的权重。
$A=D^{-1}S$，其中$D$是度矩阵，$S$是邻接矩阵。

特征矩阵

给定$A \in F^{n \times n}$，称多项式矩阵
$ \lambda E-A$为A的特征矩阵

其中$\lambda$是$A$的特征值：
若存在$\lambda$和非零$n$维向量$x$，使得$Ax= \lambda x$，则称$\lambda$为$A$的特征值，向量$x$称为$A$的对应于特征值$\lambda$的特征向量。

拉普拉斯矩阵

归一化

使得预处理的数据被限定在一定的范围内，从而消除奇异样本数据导致的不良影响。

何时使用？

几个学习概念

理解：用一堆数据来训练模型，全部不给标签，让模型自己分类，这是无监督学习；给一部分标签，这是半监督学习；标签全给了，这是监督学习。当有一些新的数据需要得到它们的标签的时候，我得把这些新的数据并入原来的数据，整个重新训练模型，这是直推学习；可以根据原来的模型来预测这些数据的标签时，这是归纳学习。

换言之，监督不监督关注的是训练数据有没有标签，直推和归纳关注的是出现新数据时是需要并入旧数据重新训练模型还是根据原来的模型来预测这些数据的标签

为什么直推学习是半监督学习：原来的数据（一部分有标签或者全都有标签），新数据没有标签，新数据并入原来的数据后，一定会造成所有数据变成一部分有标签而一部分没有标签，这就是半监督学习。

那如果原来的数据全没有标签？为什么不能是无监督学习？

纯半监督学习：对于新数据不再重新训练模型，而是直接预测。（这是属于归纳学习吧

经过学长提醒才关注这几个概念并且搞清楚的呜呜呜呜呜

GCN(Graph Convolutional Network 图卷积网络)

来源

为什么要研究GCN？因为CNN无法处理拓扑图，因为CNN只能处理图像那样规整的矩阵，无法卷积一个拓扑图。而我们又希望在拓扑图上有效地提取空间特征来进行机器学习，就需要研究GCN。

提取拓扑图的空间特征，在vertex domain(spatial domain)（空间维度）和spectral domain（图谱维度）实现目标是两种主流的方式，而后者就是GCN的理论基础。

Spatial domain

提取拓扑图上的空间特征，那么就把每个顶点相邻的neighbors找出来。

这种方法的主要缺点：

Spectral domain

这是借助图谱的理论来实现拓扑图上的卷积操作。图谱维度将问题转换为频域分析，不再需要node-wise的处理。

简单理解

0x00 定义

大多数图神经网络模型都有一个共同的通用架构，这些模型称为GCN。

对于这些模型，目标是学习一个图（$G=(V,E)$）上的信号/特征函数，这个图有以下输入：

生成一个输出$Z$（一个$N \times F$特征矩阵，其中$F$是每个节点的输出特征值）。

每个神经网络层都可以写成非线性函数 $H^{(l+1)}=f(H^{(l)},A)$
其中$H^{(0)}=X,H^{(L)}=Z$，$L$是层数。具体模型的不同仅取决于$f(·,·)$如何选择。

0x01 举个例子

考虑下面这个简单的逐层传播规则形式：
$$f(H^{(l)},A)= \sigma \big (AH^{(l)}W^{(l)}\big )$$
$W^{(l)}$是第$l$层神经网络层的系数矩阵，$\sigma(·)$是一个非线性激活函数（如$ReLU$）。虽然这个模型很简单，但它已经很强大。

当然，这个模型有几个局限性：

基于上述改进，我们得到了最终的层特征传播公式：$f(H^{(l)},A)= \sigma \big (\hat{D}^{- \frac{1}{2}}\hat{A}\hat{D}^{- \frac{1}{2}}H^{(l)}W^{(l)}\big )$

其中$\hat{A}=A+I$，$I$是单位矩阵，$\hat{D}$是$\hat{A}$的对角节点度矩阵。
$H^{(l)}W^{(l)}$相当于给$l$层的所有节点的embedding做了一次线性变换。
左乘以邻接矩阵表示对每个节点来说，该节点的特征表示为邻居节点特征相加之后的结果。

点形式：$h_v^{k+1}=f \Big ( \displaystyle \frac{1}{|N(v)|}\sum_{u \in N(v)}W^k h^k_u+b^k \Big )$，即聚合邻居节点的特征然后做一个线性变换。

0x10 空手道俱乐部的embedding

这里的embedding我暂且理解为空间特征（不知道对不对，没找到解释这是什么意思）

图和视频在GRAPH CONVOLUTIONAL NETWORKS，我就不抄过来了（doge

采用一个随机的系数矩阵，甚至在训练权重之前我们只需要插入图形的邻接矩阵，然后让$X=I$（即单位矩阵，因为我们没有任何节点特征），以这些作为模型输入。后面看原文吧，怎么翻都感觉很奇怪啊啊啊 The 3-layer GCN now performs three propagation steps during the forward pass and effectively convolves the 3rd-order neighborhood（3阶邻域） of every node (all nodes up to 3 “hops”（跃点） away). Remarkably, the model produces an embedding of these nodes that closely resembles the community-structure of the graph (see Figure below). Remember that we have initialized the weights completely at random and have not yet performed any training updates (so far)!

GCN为什么这么强？
我们可以通过将GCN模型解释为一个在图上的广义可微的Weisfeiler-Lehman算法来阐明这一点。

对于所有节点$v_i \in G$：

重复上述步骤$k$次或直到收敛。

在实践中，Weisfeiler-Lehman算法为大多数图形分配了一组独特的特征。这意味着每个节点都分配有一个特征，该特征唯一地描述了它在图形中的角色。例外情况是高度规则的图形，如网格，链等。对于大多数不规则图，此特征分配可以用作图同构的检查（即两个图是否相同，直到节点的排列）。

回到我们的图卷积逐层传播规则（为向量形式）：
$$h_{v_i}^{(l+1)}= \sigma \bigg( \displaystyle \sum_{j} \frac{1}{c_{ij}} h^{(l)}_{v_j}W^{(l)} \bigg)$$

$j$是节点$v_i$的邻居节点的索引，$c_{ij}$是边$\big (v_i,v_j\big )$的归一化常量，它源于我们在GCN模型中使用的对称归一化邻接矩阵$D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$。我们现在看到，这个传播规则可以被解释为可微分和参数化的（因为$W^{(l)}$是原始Weisfeiler-Lehman算法中使用的哈希函数的变体）。如果我们现在选择一个适当的非线性并初始化随机权重矩阵，使其正交，则这个规则会在实践中变得更稳定（也要归功于$c_{ij}$）。

0x11 半监督学习

由于模型中的所有内容都是可微分和参数化的，因此我们可以添加一些标签，训练模型并观察嵌入如何反应。
我们只需要为每个类标记一个节点，并开始训练几次迭代。（看原文视频）

缺陷

GraphSAGE

来源

GCN输入了整个图，训练节点收集邻居节点信息的时候，用到了测试和验证集的样本，我们把这个称为Transductive learning。
然而，我们所处理的大多数的机器学习问题都是Inductive learning，因为我们刻意的将样本集分为训练/验证/测试，并且训练的时候只用训练样本。这样对图来说有个好处，可以处理图中新来的节点，可以利用已知节点的信息为未知节点生成embedding，GraphSAGE就是这么干的。

总的来说，GraphSAGE用于归纳节点的embedding，它利用节点特征来学习泛化到未知节点的embedding函数。当然，GraphSAGE也可以用于没有节点特征的图，只利用图的结构特征（如节点度数）。
GraphSAGE的关键思想在于如何从节点的本地邻域（如邻居节点的度数或文本属性）聚合特征信息。

简单理解

GraphSAGE是一个Inductive Learning框架，具体实现中，训练时它仅仅保留训练样本到训练样本的边，然后包含Sample和Aggregate两大步骤

下图展示了GraphSAGE学习的一个过程

  1. 对邻居采样
  2. 采样后的邻居embedding传到节点上来，并使用一个聚合函数聚合这些邻居信息以更新节点的embedding
  3. 根据更新后的embedding预测节点的标签

下图详细说明了一个训练好的GrpahSAGE是如何给一个新的节点生成embedding的（即一个前向传播的过程），如下算法图：

首先，(line1)算法首先初始化输入的图中所有节点的特征向量，(line3)对于每个节点$v$，拿到它采样后的邻居节点$N(v)$后，(line4)利用聚合函数聚合邻居节点的信息，(line5)并结合自身embedding通过一个非线性变换更新自身的embedding表示。

注意到算法里面的$K$，它是指聚合器的数量，也是指权重矩阵的数量，还是网络的层数，这是因为每一层网络中聚合器和权重矩阵是共享的。网络的层数可以理解为需要最大访问的邻居的跳数(hops)。

给定一组输入节点，首先对所需的邻域进行向前采样（直到深度K），然后运行内部循环（line3），而不是迭代所有节点。

GraphSAGE Sample

采用定长抽样的方法。
具体来说，定义需要的邻居个数$S$，然后采用有放回的重采样/负采样方法达到$S$。保证每个节点（采样后的）邻居个数一致，这样是为了把多个节点以及它们的邻居拼接成Tensor送到GPU中进行批训练。

聚合器

图的邻居节点是没有自然顺序的，因此，聚合函数必须对一组无序的向量进行操作。
理想情况下，聚合函数是对称的（即输入的排列不变），同时仍可训练并保持高表示能力。
对称性可以确保我们的神经网络模型可以被训练并应用于任意排序的邻居节点特征集。

Mean Aggregator

$h_v^k \leftarrow \sigma(W·MEAN({h_v^{k-1}} \cup {h_u^{k-1}, \forall u \in N(v)}))$
和GCN做法基本一致

LSTM Aggregator

Applies LSTM to a random permutation of neighbors.
本质上是不对称的。

Pooling Aggregator

$AGGREGATE_k^{pool}=max({ \sigma (W_{pool}h_{u_i}^k +b) })$
原则上，任何对称向量函数（如逐元素均值）都可以用来代替最大算子。开发测试中发现最大和平均没有显著差异。

总结

优点

缺点

GAT

来源

为了解决GNN聚合邻居节点的时候没有考虑到不同的邻居节点重要性不同的问题，GAT借鉴了Transformer的idea，引入masked self-attention机制，在计算图中的每个节点的表示的时候，会根据邻居节点特征的不同来为其分配不同的权值。

简单理解

对于输入的图，一个graph attention layer如图所示

Input features: $h={ \vec{h_1}, \vec{h_2} ,…,\vec{h_N} }$
Importance of $v_i$ to $v_i$: $e_{ij}=a(W \vec{h}_i,W \vec{h}_j)$

其中$\alpha$采用了单层的前馈神经网络实现，计算过程如下（注意权重矩阵$W$对于所有的节点是共享的）：

$$\alpha_{ij}= \displaystyle \frac{exp \Big (LeakyReLU \Big ( \vec{a}^T[W \vec{h}_i] |W \vec{h}j \Big ) \Big )}{\sum{k \in N_i}exp \Big (LeakyReLU \Big ( \vec{a}^T[W \vec{h}_i] | W \vec{h}_k \Big ) \Big )}$$

计算完attention之后，就可以得到某个节点聚合其邻居节点信息的新的表示，计算过程如下：

$$ \vec{h}i’= \sigma \Big ( \displaystyle \sum{j \in N_i}{\alpha_{ij}W \vec{h}_j} \Big )$$

为了提高模型的拟合能力，还引入了multi-attention机制，即同时使用多个$W^k$计算self-attention，然后将计算的结果合并（连接或者求和）：

此外，由于GAT结构的特性，GAT无需使用预先构建好的图，因此GAT既适用于Transductive Learning，又适用于Inductive Learning。

优点

参考链接：
https://zhuanlan.zhihu.com/p/30994790
http://tkipf.github.io/graph-convolutional-networks/
https://blog.csdn.net/qq_42189083/article/details/103407753
https://zhuanlan.zhihu.com/p/136521625
https://zhuanlan.zhihu.com/p/62629465
《机器学习》，周志华
https://proceedings.neurips.cc/paper/2017/file/5dd9db5e033da9c6fb5ba83c7a7ebea9-Paper.pdf
https://zhuanlan.zhihu.com/p/136521625
https://arxiv.org/pdf/1710.10903.pdf

https://github.com/thunlp/GNNPapers/blob/master/README.md

关于本文

本文作者 云之君, 许可由 CC BY-NC 4.0.