图神经网络

发布日期: 2021-01-25

图网络总结

第一个问题什么是图神经网络，他的优势干什么的，他有哪些种类

1.类似于离散数学中的图和点的关系，我们是通过分析点与线之间的关系，来对这个神经网络进行研究

2.优点在于处理点与线的关系，找到关联性，或者进行推测，并且可以获得较为深度的意义

3.主要分为GNN,GCN,Graph Embedding

预备知识的通俗解释

图的定义 G=（V，E）V为节点，边为E，分为有向图和无向图，图与矩阵之间的联系和离散数学中一致

傅里叶变换：将一个时域非周期的连续信号，转换为一个在频域非周期的连续信号，说白了就是时间与空间之间存在的一种关系

图神经网络主要任务：节点层面，边层面，图层面

这里我们认为图的每一个节点都有一组n维的特征值向量，可以想成一组信号

拉普拉斯矩阵(L)，邻接矩阵(A)，度数矩阵(D)：L=D-A

我们的训练目的：

GCN(Spectral)

主要操作：傅里叶变换在卷积然后再傅里叶逆变换

这个是傅里叶系数公式：$f=\sum_{i=0}^{N-1} \hat{f}{i} \cdot u{i}$ 可以看成是一组n维的向量的线性组合，一个时间单位的时域信号，在 $x(t)=\int_{-\infty}^{\infty} x(\tau) \delta(t-\tau) d \tau$ 体现出了时间对总体积分影响

这幅图片表明该图的每一个节点上有一个函数表述他的信号，或者说叫特征向量

这是一个矩阵变换的内容：$L=U \Lambda U^{T}$ 其中 $\Lambda$ 是指特征值，线代内容，在这里我们认为 $\lambda$ 是frequency，而U则是basis

这里值得注意的的是 $\lambda$ 的值是frequency，然后当frequency有不同的的值对于u1，u2…也会有不同的值，以上图为例，在每一个不同的维度下，即 $\lambda$ =0，1，3…会得出不同的u矩阵，这是表示该frequency下不同的信号。可以预见的是当 $\lambda$ 越大相邻两点u的变化越大，可以理解为频率变化来类比。

我们来将特征值反映进图中 $L f=(D-A) f=D f-A f$

推出以下公式含义：$f^{\mathrm{T}} L f$=$=\frac{1}{2} \sum_{v_{i} \in V} \sum_{v_{j} \in V} w_{i, j}\left(f\left(v_{i}\right)-f\left(v_{j}\right)\right)^{2}$

这个公式表示节点 i 和节点 j 之间的能量差异

该公式用于估计不同频域成分的大小不同 $\hat{x}=U^{T} x$ （傅里叶变换）$x=U \hat{x}$ （这个是傅里叶逆变换）

步骤：傅里叶变换->Filtering->傅里叶逆变换

这里涉及到一个频率响应函数（应该这么叫）

$\hat{y}=g_{\theta}(\Lambda) \quad U^{\mathrm{T}} \quad x$ y = $\begin{array}{llllll}U&\hat{y} & = &U& g_{\theta}(\Lambda) & U^{\mathrm{T}} & x\end{array}$

化简为 y=$=g_{\theta}\left(U \Lambda U^{\mathrm{T}}\right) x$ —> $y=g_{\theta}(L) x$

解释一下：首先y是我们最终的期望输出，而我们要学习的参数是 $g_{\theta}(\Lambda)$ ，这里就涉及到一个问题，这个参数取决于我们模型图像的大小，不同的数据我们要设置 $g_{\theta}(\Lambda)$ 不同的大小

然后我们对 $g_{\theta}(\Lambda)$ 做级数展开为N次方时，虽然能保证纵观全图，但是表明了这个模型不是localized

ChebNet

优点：快，并且可以localized，而且可以避免N维度对参数的影响

重要公式 $\mathrm{g}{\theta}(L)=\sum{k=0}^{K} \theta_{k} L^{k}$ 通过选择K来确定想要看到K-localized，$\theta_{k}$ 而这个是要学的参数

理论上的公式：$y=U \mathrm{~g}{\theta}(\Lambda) U^{T} x=U\left(\sum{k=0}^{K} \theta_{k} \Lambda^{k}\right) U^{T} x$ 但是时间复杂度会 $O\left(N^{2}\right)$ 不方便计算

Chebyshev polynomial

$T_{0}(\widetilde{\Lambda})=\mathrm{I}, T_{1}(\widetilde{\Lambda})=\widetilde{\Lambda}, T_{k}(\widetilde{\Lambda})=2 \widetilde{\Lambda} T_{k-1}(\widetilde{\Lambda})-T_{k-2}(\widetilde{\Lambda})$
$\widetilde{\Lambda}=\frac{2 \Lambda}{\lambda_{\max }}-\mathrm{I}, \quad \tilde{\lambda} \in[-1,1]$

通过这个变换我们要学的多项式变成了 $g_{\theta^{\prime}}(\widetilde{\Lambda})=\sum_{k=0}^{K} \theta_{k}^{\prime} T_{k}(\widetilde{\Lambda})$

为什么我们要用这个方法：可以理解为做这个变换主要是方便计算，让式子计算难度下降，有点点像多项式转变成多项式的平方和

该式子推导如下

$\begin{aligned} y=g_{\theta^{\prime}}(L) x &=\sum_{k=0}^{K} \theta_{k}^{\prime} T_{k}(\tilde{L}) x \ &=\theta_{0}^{\prime} T_{0}(\tilde{L}) x+\theta_{1}^{\prime} T_{1}(\tilde{L}) x+\theta_{2}^{\prime} T_{2}(\tilde{L}) x+\cdots+\theta_{K}^{\prime} T_{K}(\tilde{L}) x \ &=\theta_{0}^{\prime} \bar{x}{0}+\theta{1}^{\prime} \bar{x}{1}+\theta{2}^{\prime} \bar{x}{2}+\cdots+\theta{K}^{\prime} \bar{x}{K} \ &=\left[\begin{array}{llll}\bar{x}{0} & \bar{x}{1} & \ldots & \bar{x}{K}\end{array}\right]\left[\begin{array}{lll}\theta_{0}^{\prime} & \theta_{1}^{\prime} & \ldots & \theta_{K}^{\prime}\end{array}\right] \end{aligned}$

在这种情况下他的计算难度只有$O(K E)$

GCN

推导过程略：

renormalization trick: $I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \rightarrow \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$
$$
H^{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)
$$
可以写成核心公式：$h_{v}=f\left(\frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} W x_{u}+b\right)$

$\sum_{u \in \mathcal{N}(v)}$ 表示所有的相关节点加起来，包括自己， $W$ 表示傅里叶变换， $|\mathcal{N}(v)|$ 表示取平均，

Filter

Filter in GraphSAGE

对于每个点 $v_{i},$ 其生成新feature的过程如下：先从 $\mathcal{N}\left(v_{i}\right)$ 中选出 $S$ 个点 (记相应集合为 $\left.\mathcal{N}{\mathcal{S}}\left(v{i}\right)\right),$ 再把这 $S$ 个点的所有feature (用某种AGG函数) 合起来, 再将其与 $v_{i}$ 的feature $F_{i}$ 组合, 乘以某个矩阵后再经过一个激活函数得到 $v_{i}$ 的新feature。

Filter in GAT

GAT-Filter具体操作中对于点 $v_{i}, \quad \mathcal{N}\left(v_{i}\right) \cup v_{i}$ 中点 $v_{j}$ 对 $v_{i}$ 的importance score为 $v_{i}, \quad \mathcal{N}\left(v_{i}\right) \cup v_{i}$ 中点 $v_{j}$ 对 $v_{i}$ 的importance score为 $e_{i, j}:=\alpha\left(F_{i} \theta, F_{j} \theta\right):=\operatorname{LeakyReLU}\left(a^{T}\left[F_{i} \theta, F_{j} \theta\right]\right),$ 其中 $[\cdot, \cdot]$ 其中 $[\cdot, \cdot]$ 为连接操作, $\quad \alpha$
为一共同attention function, $\theta$ 为某参数化矩阵, $a$ 为某参数化向量 (要理解 $e_{i, j}$ 的定义需要从形式上看: 这里只涉及两个点, 所以定义里面只有两个feature, 通过某种 $\theta$ 作用后再连接起来, 再用 $a^{T}$ 乘以后转换信息, 最后经过 LeakyReLU (为了使不同点生成的score不同我们不能用 $\operatorname{Re} L U$ )生成大小 $) ，$ 我们接下来将其用 Softmax 函数规范化得到 $\alpha_{i, j} ，$ 那么很显然地, $v_{i}$ 新生成的feature就是$F_{i}^{\prime}=\sum_{v_{j} \in \mathcal{N}\left(v_{i}\right) \cup v_{i}} \alpha_{i, j} F_{j} \theta($ 这里面可以增加激活函数）了。以上具体操作中仅仅训练出了一个 $\theta$ ，可能导致训练效果不太稳定。我们可以将上述操作重复 $M$ 次得到 $\theta^{1} \sim \theta^{M},$ 最后取 $F_{i}^{\prime}=|{m=1}^{M} \sum{v_{j} \in \mathcal{N}\left(v_{i}\right) \cup v_{i}} \alpha_{i, j}^{m} F_{j} \theta^{m},$ 其中 $|$ 代表连接。

Filter in MPNN

首先来看下消息函数, 可以以 GG-NN 中使用的消息函数开始, GG-NN 用的是矩阵乘法：
$$
M\left(h_{v}, h_{w}, e_{v w}\right)=A_{e_{v w}} h_{w}
$$
为了兼容边特征，作者提出了新的消息函数：
$$
M\left(h_{v}, h_{w}, e_{v w}\right)=A\left(e_{v w}\right) h_{w}
$$
其中, $A\left(e_{v w}\right)$ 是将边的向量 $e_{v w}$ 映射到 $d \times d$ 维矩阵的神经网络。
矩阵乘法有一个特点, 从节点 w 到节点 $v$ 的函数仅与隐藏层状态 $h_{w}$ 和边向量 $e_{v w}$ 有关，而和隐藏状态 $h_{v}^{t}$ 无关。理论上来说, 如果节点消息同时依赖于源节点 $\mathrm{w}$ 和目标节点 $\vee$ 的话, 网络的消息通道将会得到更有效的利用。所以也可以尝试去使用一种消息函数的变种：
$$
m_{v w}=f\left(h_{w}^{t}, h_{v}^{t}, e_{v w}\right)
$$
其中，f为神经网络。

Graph Pooling Operation

池化分为哪几种：Hard rule hard rule很简单，因为Graph structure是已知的，可以预先规定池化节点，Graph coarsening图粗略化是先对节点进行聚类，然后合成一个超级节点，以达到池化效果，Node selection节点选择就是选择一些重要节点去代替原图，类似于分析节点的重要性，方法类似节点分类的操作。

gPool

选择一些重要节点去代替原图，类似于分析节点的重要，计算证明过程略

DiffPool

先对节点进行聚类，然后合成一个超级节点，计算证明过程略

Eigenpooling

解决了面对层次化聚类过程中，如何将合并成一个超级节点的子图的结构信息保留下来的问题，相当于是对DiffPool的改进版，EigenPool算法分为两部分，1）图坍缩，将图分为一组子图，并通过将子图视为超节点来形成粗化图； 2）使用EigenPooling将原始图信号转换为在粗化图上定义的信号。

GNN的鲁棒性

攻击种类

攻击已经训练好的GNN，攻击可重训练的GNN。这两种攻击可定义为：基于投影梯度下降（PGD）的拓扑攻击和min-max拓扑攻击。可以粗略理解为攻击点，攻击线，和非直观攻击。

GradArgmax ：修改了点，线和边缘，在每一个步骤中选取干扰最大的扰动

Nettack：干扰网络本身，但是需要知道模型参数才能攻击

GF-Attack ：破坏模型输出的图嵌入向量的质量，从而降低利用图嵌入进行的下游任务的性能

ReWatt ：通过改变线的分布，改变度数，该方法以较小的改变去干扰结果

防御方法

对抗训练：通过输入对抗数据，和一般的对抗训练意义相同

清洗图像：通过预处理，清洗掉错误的数据，例如边或点，Pro-GNN

注意机制：减少对边缘的权值，边缘的降低影响，RGCN，对被攻击的节点降低关注度，PA-GNN,我们要使用clean graphs来学习

图网络的自监督学习

SSL（半监督学习）

基本概念不做赘述，这里遮住或者生成高斯噪声，在特征层面干扰，通过增加或者减少点，线，子样本，和扩充矩阵，来对结构层面干扰，通过强制判别器来输出类别标签。在一个数据集上训练一个生成器 G 以及一个判别器 D，输入是N类当中的一个。在训练的时候，D被用于预测输入是属于 N+1的哪一个，这个+1是对应了G的输出。这种方法可以用于创造更加有效的分类器，并且可以比普通的GAN 产生更加高质量的样本。

这种训练方式可以改进大多数的GNN模型：

对节点分类任务的优点：该任务是去更正错误标签

1.使用相邻的标签也能提高准确率

2.标签矫正确实能帮助任务

3.样本较小也没有关系

FastGCN

作者假设图是无限大的, 即当前的图只是无限大图的一个子图，因此对于一个无限大图来说就可以写成积分的形式:
$$
\tilde{h}^{(l+1)}(v)=\int \hat{A}(v, u) h^{(l)}(u) W^{(l)} d P(u), h^{(l+1)}=\sigma\left(\tilde{h}^{(l+1)}(v)\right)
$$
其中 $P(u)$ 是节点的概率分布，这里作者假设了每个节点是一个 iid 样本(独立同分布)，其实并不会真正去求这个积分，表达成积分的形式主要是为了用蒙特卡罗法((Monte Carlo)。

利用蒙特卡罗法，对每一层采样 $t_{l}$ 个顶点 $u_{1}^{(l)}, u_{2}^{(l)}, \cdots, u_{t_{l}}^{(l)} \sim P$ 来近似积分:
$$
\tilde{h}^{(l+1)}(v)=\frac{1}{t_{l}} \sum_{j=1}^{t_{l}} \hat{A}\left(v, u_{j}^{(l)}\right) h^{(l)}\left(u_{j}^{(l)}\right) W^{(l)}, h^{(l+1)}=\sigma\left(\tilde{h}^{(l+1)}(v)\right)
$$
同时为了减小估计方差(VARIANCE REDUCTION)，作者提出利用重要性采样，每个顶点根据以下概率分布进行采样: $q(u)=\frac{|\hat{A}(:, u)|^{2}}{\sum_{u^{\prime} \in V}\left|\hat{A}\left(:, u^{\prime}\right)\right|^{2}}$

通俗来说其实 FastGCN 就是在每一层根据顶点的度采样t_个顶点。 FastGCN 采用的是一种 layer-wise 的采样方式, 即对每一层 layer 进行采样，FastGCN 就不会有邻域指数扩散的问题，不过也存在一种可能,对于一个很大且十分稀疏的图来说， FastGCN 很可能刚好采样到一批跟需要嵌入节点没有任何关联(即没有连接)的节点或者连接很稀疏，此时对于当前这批 mini-batch 就无法进行信息传播聚合，网络便无法学习。

GraphSAGE

其运行流程如上图所示，可以分为三个步骤对图中每个顶点邻居顶点进行采样，根据聚合函数聚合邻居顶点蕴含的信息，得到图中各顶点的向量表示供下游任务使用

1.采样邻居顶点

出于对计算效率的考虑，对每个顶点采样一定数量的邻居顶点作为待聚合信息的顶点。设采样数量为k，若顶点邻居数少于k,则采用有放回的抽样方法，直到采样出k个顶点。若顶点邻居数大于k，则采用无放回的抽样。

2.聚合函数的选取

我们希望选出来的函数对称
$$
h_{v}^{k} \leftarrow \sigma\left(\boldsymbol{W} \cdot \operatorname{MEAN}\left(\left{h_{v}^{k-1}\right} \cup\left{h_{u}^{k-1}, \forall u \in N(v)\right}\right)\right.
$$
mean aggregator将目标页点和邻居顶点的第k-1层向量拼接起来, 然后对向量的每个维度进行求均值的操作, 将得到的结果做一次非线性变换产生目标页点的第k层表示向量。
$$
A G G R E G A T E^{p o o l} k=\max \left(\left{\sigma\left(\boldsymbol{W} \operatorname{poolh}{u{i}}^{k}+b\right), \forall u_{i} \in N(v)\right}\right)
$$
Pooling aggregator 先对目标页点的邻接点表示向量进行一次非线性变换, 之后进行一次 pooling操作(maxpooling or meanpooling), 将得到结果与目标顶点的表示向量拼接, 最后再经过一次非线性变换得到目标顶点的第k层表示向量。
LSTM相比简单的求平均操作具有更强的表达能力，然而由于LSTM函数不是关于输入对称的，所以在使用时需要对顶点的邻居进行一次乱序操作。

对于结果的节点分类依旧缺乏明确的分析证明过程