图神经网络

2021-10-05

1. 图的基本概念

连通图：对于一个无向图，如果任意的结点i能够通过一些结点边到达结点j，称之为连通图
非连通图：对于一个无向图，如果任意的结点i不能够通过一些结点边到达结点j，称之为非连通图
连通分量：无向图G的一个极大连通子图称为G的一个连通分量。连通图只有一个连通分量，即其自身，非连通图有多个连通分量。
强连通图：给定有向图G(V,E)，并且给定该图G中的任意两个结点u和v，如果结点u和结点v互相可达，那么就称该有向图G是强连通图。
弱连通图：若至少有一对结点不满足单向连通，但去掉边的方向后从无向图的观点看是连通图，则D称为弱连通图。
图直径：图中两两结点的最短路径的最大值。

2. Graph Embedding

2.1 deepwalk算法

deepwalk的方法是参考了word2vec的思路的，将一个图作为输入，并产生一个潜在的表示(将图中的每个节点表示为一个向量)作为输出。对于图结构来说，算法设计要满足以下几个要求： 1.适应性：社交网络是不断变化的，当网络发生变化不能对整个网络重新进行计算 2.社区意识：节点的潜在表示对应着维度空间中的距离，应该表示网络中对应的成员的相似度，以保证网络的同质性 3.低维：当被标记的成员很少时，低维的模型一般表现得更好，并且收敛性和推理速度更快 4.连续性：需要通过图的潜在表示对连续空间中的部分社区成员进行建模。除了提供对社区成员资格的细微视图之外，连续表示还可以使社区之间的决策界限平滑，从而实现更强大的分类

算法的流程： 1.展示用户行为序列 2.基于这些用户行为序列构建了物品相关图，图中的边是由用户行为产生的 3.采用随机游走的方式随机游走的方式随机选择起始点，产生局部物品序列 4.将这些物品序列当做初始句子进行word2vec建模，生成最终的物品embedding向量

random walk是从截断的随机游走序列中得到的网络局部信息，并以此来学习节点的向量表示。借助语言模型word2vec中的skip-gram模型来学习节点的向量表示。将网络中的结点作为语言模型中的单词，而结点的序列(随机游走得到)模拟为语言中的句子，作为skip-gram的输入。

优点： 1.并行性：同时进行多个随机游走 2.适应性：当图变化时，不需要全局重新计算，可以迭代的更新学习模型，适合online learning

deepwalk算法架构

SkipGram是一个语言模型，用于最大化句子中出现在窗口w内的单词之间的共现概率。使用独立性假设，最后条件概率为：

对序列中的每个顶点，计算条件概率，即该结点出现的情况下序列中其他节点出现的概率的log值，借助随机梯度下降算法更新该结点的向量表示：

2.2 line算法

Line的原理介绍

这里与deepwalk不一样的方法是作者考虑了两个方面：一阶相似性和二阶相似性。LINE可以看作是一种基于BFS构造邻域的算法。 (1) 一阶相似性一阶相似性就是指图中两个结点有边相连接，边的权重衡量的就是两个结点的相似程度。有边相连接边权值为两个顶点的相似度，无边相连时相似度为1.假设我们定义两个结点的联合概率是: 而又知道其对应的经验概率是：

优化的目标为：\(O_1=d(\hat p_1(.,.),p_1(.,.))\)

利用KL散度的公式并且忽略掉一些常数之后，可以定义一阶相似性的损失函数为：

一阶相似性只能用于无向图中，

二阶相似性

每个节点维护两个embedding向量，一个是该顶点本身的表示向量，一个是该点作为其他顶点的上下文时的表示向量。假如两个结点他们的邻居很相似，我们则称这两个结点二阶相似。定义两个节点的条件概率是：要对比两个结点的二阶相似性，其实对比的就是两个结点的条件概率分布的相似性。只要能够保证所有结点的条件概率和经验条件概率一致，那么这个embedding就可以很好地保存这两个结点的二阶相似性。λ表示控制节点的重要性因子，可以通过节点的度数或者PageRank来估计得到。

经验分布定义为：\(\hat p_2(v_j|v_i)=w_{i,j}/d_i\)，其中\(w_{i,j}\)是边\((i,j)\)的边权重，\(d_i\)是顶点\(v_i\)的出度，对于带权图，\(d_{i}=\sum_{k \in N(I)} W_{i k}\)

得到二阶的损失函数为：在现实中，一般采用负采样的方法进行训练，即：

(3)结合一阶相似性和二阶相似性将一阶相似性训练得到的embedding和二阶相似性训练得到的embedding拼接起来，就是最终的embedding形式。

模型优化

我们会可以看到不管是一阶还是二阶的时候，损失函数每条边都有个weight，为了加速模型收敛，训练的时候可以对边采取抽样的方式生成训练样本，每条边被抽中的概率为边的权重。
对于邻居很少的结点，我们可以将结点邻居的邻居作为该结点的邻居，对应的权重为：然后将结点的权重进行排序，取出topN。

2.3 node2vec算法

要设计的网络表示学习算法的目标必须满足以下两点： 1.同一个社区内的结点表示类似 2.拥有类似结构特征的结点表示相似

算法流程

该方法的损失函数是：为了让结果更容易计算，引入了skip-gram中的两个假设：

条件独立，即采样每个邻居是相互独立的，所以如果要计算采样所有邻居的概率只需要将采样每个邻居的概率相乘就好了，公式化表达就是：
特征空间的对称性。假设一条边连接了a和b，那么映射到特征空间时，a对b的影响和b对a的影响是一样的。用一个模型来表示一个(结点，邻居)对：将上面的三个公式结合起来得到最终的优化结果：注意： 1.Zu直接计算特别费时，本文使用的是负采样的方式 2.Ns(u)未必是u的直接邻居，只是用s方法采样得到的邻居，跟具体的采样方法有关

复杂网络处理的任务其实离不开两种特性，一种是同质性也就是社区，另一种是结构相似性。结构相似的两个点未必相连，可以是相距很远的两个结点。深度优先游走(DFS)和广度优先游走(BFS)是两种随机游走的方式。BFS倾向于在结点的初始结点的周围游走，可以反映出一个结点的邻居的微观特性；而DFS一般会跑的离初始结点越来越远，可以反映出一个结点邻居的宏观特性。 node2vec的随机游走产生的方式是：对于一个随机游走，如果已经采样了(t,v)，也就是说现在停留在结点v上，那么下一个要采样的结点是哪个？作者定义了一个概率分布，也就是一个结点到它不同邻居结点的转移概率：

如果t和x相等，那么采样x的概率系数是1/p
如果t和x相连，那么采样x的概率系数是1
如果t和x不相连，那么采样x的概率系数是1/q

参数p、q的意义分别如下：返回概率p：

如果p > max(q,1)，那么采样会尽量不往回走，对应上图的情况，就是下一个节点不太可能是上一个访问的结点t
如果p < min(q,1)，那么采样会更倾向于返回上一个结点，这样会一直在起始点周围某些结点来回转来转去。出入参数：
如果q > 1，那么游走会倾向于在起始点周围的结点之间跑，可以反映一个结点的BFS特征。
如果q < 1，那么游走会倾向于往远处跑，反映出DFS特性。当 p = 1 , q = 1 时，游走方式就等同于DeepWalk中的随机游走。 q是用来控制模型是DFS还是BFS

node2vec算法流程

根据p、q和之前的公式计算一个结点到它邻居的转移概率
将这个转移概率加到图G中形成G'
walks用来存储随机游走，先初始化为空
外循环r次表示每个节点作为初始结点要生成r个随机游走
然后对图中每个节点
生成一条随机游走walk
将walk添加到walks中保存
然后使用SGD方法对walks进行训练

第6步中一条walk的生成方式如下：

将初始节点u添加进去
walk的长度与为l，因此还要再循环添加l-1个结点

2.4 重启随机游走算法

重启随机游走是对随机游走的改进，从图中的某一个节点出发，每一步面临两个选择，随机选择相邻节点或者返回开始节点。算法包含一个参数a为重启概率，1-a表示移动到相邻节点的概率，经过迭代到达平稳，平稳后得到的概率分布可以被看作是受开始节点影响的分布。重启随机游走可以捕捉两个节点之间多方面的关系，捕捉图的整体结构信息。

RWR最初是为图像分割而提出的一个算法，它反复的探究一个网络的总体结构去估计两个节点之间的亲和力程度，这个算法只考虑一个参数，也就是重启概率。这个反复迭代进行下去直到走遍所有的节点，此时得到的概率向量包含所有节点与起点的亲和力分数。另外，RWR的起点也可以选择一个起点集合(多个起点组成的集合)

2.5 SDNE

SDNE使用一个自编码器来同时优化1阶和2阶相似度，相当于LINE的扩展，LINE是分别优化一阶和二阶相似度的。相似度的定义也是一样的，一阶相似度衡量的是相邻两个顶点对之间相似性。2阶衡量的是两个顶点他们的邻居集合的相似程度。

二阶相似度：\(L_{2 n d}=\sum_{i=1}^{n}\left\|\hat{x}_{i}-x_{i}\right\|_{2}^{2}\),输入使用的是图的邻接矩阵，对于第i个顶点有\(x_i=s_i\)，每个\(s_i\)都包含了顶点i的邻居结构信息，这样的重构过程能够使得结构相似的顶点具有相似的embedding表示向量。由于图是有稀疏性的，邻接矩阵S中的非零元素远小于零元素，对于神经网络来说全部输入0也有不错的效果，这显然不合理。

SDNE的一个做法是使用带权的损失函数，对于非零元素具有更高的惩罚系数。修正后的损失函数为：\(L_{2 n d}=\sum_{i=1}^{n}\left\|\left(\hat{x}_{i}-x_{i}\right) \odot \mathbf{b}_{\mathbf{i}}\right\|_{2}^{2}=\|(\hat{X}-X) \odot B\|_{F}^{2}\)

其中\(b_i= \left\{b_{i,j}\right\}^n_{j=1}\),若\(s_{i,j}=0,则b_{i,j}=1,else b_{i,j}=β>1\)

对于一阶相似度，损失函数定义为：

\(L_{1 s t}=\sum_{i, j=1}^{n} s_{i, j}\left\|\mathbf{y}_{\mathbf{i}}^{(K)}-\mathbf{y}_{\mathbf{j}}^{(K)}\right\|_{2}^{2}=\sum_{i, j=1}^{n} s_{i, j}\left\|\mathbf{y}_{\mathbf{i}}-\mathbf{y}_{\mathbf{j}}\right\|_{2}^{2}\)

该损失函数可以让图中相邻的两个顶点的embedding vector在隐藏空间接近。

此式子可以写为：

\(L_{1 s t}=\sum_{i, j=1}^{n}\left\|\mathbf{y}_{i}-\mathbf{y}_{j}\right\|_{2}^{2}=2 \operatorname{tr}\left(Y^{T} L Y\right)\)

其中L图对应的拉普拉斯矩阵，L=D-S，D是度矩阵，S是邻接矩阵。

联合优化损失函数为：\(L_{m i x}=L_{2 n d}+\alpha L_{1 s t}+\nu L_{r e g}\)

\(L_{reg}\)是正则化项，α为控制1阶的损失函数，v为控制正则化的参数。

模型图如下：

二阶相似度学习：

左半部分：

输入是\(x_i\)，输出是\(\hat x_i\)，这是一种自编码器\(f(x)≈x\)，自编码器没有标签数据，所以是一种非监督学习，前半部分为编码器，后半部分为解码器。在实际中通常会用到自编码器的前半部分，即输入\(x_i\)得到\(y_i^{K}\)的部分，此部分的公式为：

其中，\(x_i\)为输入值，本质上是节点i的邻接矩阵。\(y_i^{(k)}\)为第k层的第i个节点的输出值，而\(W^{k}\)是第k层的参数矩阵，\(b^k\)为第k层的偏置项。最终经过编码得到节点的embedding向量\(y_i^{(k)}\)之后，再经过与编码器对称的网络结构得到输出值\(\hat x_i\)。

自编码器的目标是最小化输入与输出的重构误差\(L_{2 n d}=\sum_{i=1}^{n}\left\|\hat{x}_{i}-x_{i}\right\|_{2}^{2}\)

之后考虑稀疏性得到的损失函数跟上述的一致。输入的数据就是\(x_i\)表示邻接矩阵集合\(S=\left\{s_1,s_2,...,s_n\right\}\)
一阶相似度：

模型两侧的输入是有边相连接的节点i，j的信息，可以学习全局特征。相连的两个节点具有一阶相似性，i和j有相似的向量表示。利用拉普拉斯特征映射的思想（图中相连的点，在降维后的空间尽可能地靠近）。

\(L_{1 s t}=\sum_{i, j=1}^{n} s_{i, j}\left\|\mathbf{y}_{\mathbf{i}}^{(K)}-\mathbf{y}_{\mathbf{j}}^{(K)}\right\|_{2}^{2}=\sum_{i, j=1}^{n} s_{i, j}\left\|\mathbf{y}_{\mathbf{i}}-\mathbf{y}_{\mathbf{j}}\right\|_{2}^{2}\)

3. 图神经网络

对称归一化拉普拉斯矩阵

GCN中会对邻接矩阵进行归一化的拉普拉斯标准化。

A1=A/np.sqrt(A.sum(axis=1))
A2=A1.T/np.sqrt(A.sum(axis=0))
A2=A2.T
A2

本质上来说就是对邻接矩阵进行横向和纵向的标准化，只是多了个根号。

横向标准化的含义是：因为在graph中，不同的节点之间的边的权重差异可能很大，对于金融中通过user之间的交易关系来构建的图尤其如此，交易的金额作为weights，则不同用户之间的交易权重差异可能非常的大。这对于nn训练的难度比较大。

纵向标准化的含义：希望将节点的邻接节点对其的贡献进行标准化。比方说微博上的关注关系就是一个同构图，如果想要判断一个人是不是喜欢足球的东西，假设该用户A关注了一百个体育的博主，那么这些足球博主对用户的类别的判定的贡献是很小的，因为体育博主可能会关注足球篮球等等。而若体育粉丝B来说，如果他只跟A有关联，那么B对A的忠诚关联度是很高的，B的节点特征以及B和A的关联关系对A进行节点分类来说是重要的。而对称归一化拉普拉斯矩阵，实际上是横纵向标准化之后又开了根号，开根号不影响计算结果的相对大小，不改变实际的物理意义。