图神经网络：图的向量化-点头深度学习网站

引言

图神经网络（Graph Neural Networks，GNNs）是一种专门用于处理图形数据的神经网络架构。图形数据是一种非欧几里得数据，其中主要包括节点（vertices）和边（edges），节点代表实体，边表示实体间的关系。图的向量化（也称为图嵌入）是指将图形数据转换成低维度的向量表示，这样就可以用于各种机器学习任务，如分类、聚类和推荐系统等。接下来介绍的就是常见的向量化方法。

节点的向量化

独热编码的方法就是用一个长度为节点数量的向量来表示节点信息，这个向量绝大部分元素都是零，只有一个位置是1，所以称为独热编码，如图9-23所示。

图片[1]-图神经网络：图的向量化-点头深度学习网站 — 图9-23 One-Hot Embedding

这种表示方式虽然可以保证每个节点对应不同的向量，但是却有两个致命的缺点。

（1）稀疏性，向量中绝大部分元素都是0。而且随着图大小的增加，稀疏性会跟着增加。

（2）独热编码的形式不能抓取节点中的相关性，比如节点刘备跟其它五个节点都相连，但这个关系在独热编码的形式上是体现不出来的。

为了解决这些缺点，随机游走（Random Walk）算法被提出。首先，一个合理的向量化应该考虑相似性，即在图中相互临近的节点经过向量化后得到的向量也应该是相似的。也就是说，希望向量化之后的节点向量点乘之后的值接近于原图中的节点相似度，原图的相似度可以采用是否节点相连、是否有相同的邻居节点等方式来定义。

$$
{similarity}(u, v)=z_v^T z_u
$$

根据上面的内容, 生成节点向量定义分为三个步骤:
(1) 定义生成节点向量的编码器;
(2) 定义一个节点相似度的计算函数;
(3) 优化编码器的参数, 让其点乘后的结果约等于相似度。

一种简单的向量化方法采用类型 word embdding 的方式, 定义一个 embdding lookup 矩阵 ${encoder}(v)=Z v$, 其中 $Z$ 是嵌入矩阵, $v$ 是节点的 one-hot 表示方式, 如图 9-24 所示。

图片[2]-图神经网络：图的向量化-点头深度学习网站 — 图
9-24 embdding lookup matrix

接下来考虑第二步，怎么来定义原图的相似度呢？随机游走的输入是给定一个图和一个起始节点，然后按照一定概率随机选择一个邻居节点，走到该处后再随机选择一个邻居，重复length次。length是一个超参数，是指随机游走的长度，如图9-25所示。

图片[3]-图神经网络：图的向量化-点头深度学习网站 — 图9-25 Random Walk

使用随机游走从起始节点到终止节点的概率值, 实际上就可以用来表示相似度, 也就是说, 从 $u$ 节点到 $v$ 节点的概率值, 应该正比于 $u$ 节点与 $v$ 节点向量化之后的点乘结果, 即如果从节点 $u$ 开始的随机游走以高概率访问 $v$ ，则 $u$ 和 $v$ 相似。公式如下:
$$
\boldsymbol{z}_v^T \boldsymbol{z}_u \propto P(v \mid u)
$$

其中, $\boldsymbol{z}_v^T \boldsymbol{z}_u \approx$ 点 $u$ 和 $v$ 在一次随机游走中同时出现 (点 $v$ 在以 $u$ 为起点的随机游走中出现)的概率。
这种方法有两个优点:
(1) 相似度的定义结合了图的局部信息。
(2)只需要考虑随机游走的节点, 不需要考虑全局信息, 节省计算复杂度, 效率高。
接下来是第三步: 编码器的参数优化, 给定图 $G=(V, E)$, 定义 $N_R(u)$ 表示采用策略 $\mathrm{R}$得到的邻居节点, 此时的目标就是学习映射关系 $z: u \rightarrow R^d$ 。用对数似然函数表示为:

$$
\max \sum_{u \in V} \log P\left(N_R(u) \mid \boldsymbol{z}_u\right)
$$

即希望, 当给定 $u$ 的节点向量 $\boldsymbol{z}_u$ 时, 其邻居节点出现的概率最大, 这是最大似然函数的思想。最终损失函数可以表示为:
$$
L=\sum_{u \in V} \sum_{v \in N_r(u)}-\log \left(P\left(v \mid \boldsymbol{z}_u\right)\right)
$$

上述公式中的负号是把求似然函数最大值变成求最小值。目的是做优化时可以使用梯度下降算法。第一个求和公式针对的是图中所有的节点; 第二个求和公式是针对某节点随机游走轨迹上经过的所有节点。其中:
$$
P\left(v \mid \boldsymbol{z}_u\right)=\frac{\exp \left(\boldsymbol{z}_{u}^T \boldsymbol{z}_v\right)}{\sum_{n \in V} \exp \left(\boldsymbol{z}_{l l}^T \boldsymbol{z}_n\right)}
$$

这里经过了 softmax 公式的映射, softmax 会将一组数据归一化为和为 1 的形式, 最大值的结果会几乎为 1 。 sigmoid 会将实数归一化到 $(0,1)$ 上, 此时可以表征概率。

到了这一步, 就可以采用 SGD 等方法来优化参数了。但是, 如果读者仔细看损失函数,可以发现损失的计算复杂度是很高的, 因为其外面嵌套了两层的求和, 因此时间复杂度是 $|V|^2$, 为了简化该过程, 使用类似 word $2 \mathrm{vec}$ 中的负采样, 只采样 $k$ 个负样本, 公式如下:

$$
\log \left(\frac{\exp \left(\boldsymbol{z}_v^T \boldsymbol{z}_u\right)}{\sum_{u \in V} \exp \left(\boldsymbol{z}_v^T \boldsymbol{z}_n\right)}\right)=\log \left(\sigma\left(\boldsymbol{z}_v^T \boldsymbol{z}_u\right)\right)-\sum_{i=1}^k \log \left(\sigma\left(\boldsymbol{z}_v^T \boldsymbol{z}_n\right)\right)
$$

其中 $k$ 是一个超参数, $k$ 越高表示负样本的偏见越高, 较高的 $k$ 能得到更可靠的估计结果。

random walk的每一步都是无偏游走，也就是说走到下一个邻居节点的概率都相同的，那么游走的结果可能会只关注局部信息，类似宽度优先搜索（甚至是两个节点来回跳）；或者只关注全局信息，类似深度优先搜索。

那么有没有什么方法能控制其游走的策略呢？node2ve算法提出了一种游走的策略，该策略包含两个参数。

（1）p参数：用来控制返回上一个节点的概率。

（2）q参数：用来控制远离上一个节点的概率。该参数也可以理解为采用宽度优先搜索还是深度优先搜索的一个比例值。q值大，更偏向深度优先搜索，q值小，更偏向广度优先搜索。

剩下的操作与随机游走类似，定义node2vec的损失函数，并采用SGD进行参数优化即可。

图全局信息的向量化

图全局信息的向量化就是考虑怎么把整个图的信息，或子图的信息映射成一个图向量。

聚合是最简单的得到图向量的方法。就是简单的对图中所有的节点向量求和或求平均，并将这个结果作为图向量。这个方法虽然简单，但实际操作时，效果还是很好的。另一种方法是在整个图的基础上，创造一个虚拟节点（virtual node），用这个节点向量来作为图向量，如图9-26所示。这个虚拟节点与全图所有节点相连。在图模型的训练阶段，这个虚拟节点会与全图的节点进行信息的交互，因此，它可以表征全图信息。

图片[4]-图神经网络：图的向量化-点头深度学习网站 — 图9-26 虚拟全局节点

边的向量化

至于边的向量化，其实比较简单。可以简单的将该边相连的两个节点向量做聚合即可。

除此之外，边的向量化也可以具体问题具体对待。举例：如果图结构表示的是一个分子，其中边表示两个原子是否相连。此时边的性质包括是否是双键、是否是环结构、是否是共价键、相连的原子是否是碳原子等等。那么可以用一个长度是四维的相连来表示这个边。例如 [1, 0, 0, 1] 可以表示这个边是一个连接碳原子的双键。

小结

“图的向量化”是一种将图形数据（包含节点和边的结构）转换为数值向量表示的过程。这个过程关键在于将图的结构性质和节点间的复杂关系编码到低维空间中的向量中，使得这些向量可以用于机器学习和数据分析任务。图的向量化涉及到不同的层面，包括节点嵌入、边嵌入以及整个图的嵌入，各有不同的方法和技术。以下是图的向量化的几个关键点总结：