33. BI - Graph Embedding 回顾以及 GCN 算法介绍

本文为「茶桁的 AI 秘籍 - BI 篇第 33 篇」

文章目录

- 回顾 Graph Embedding
- 什么是 GCN
- GCN 算法

Hi，你好。我是茶桁。

咱们终于进入核心 BI 课程的最后一部分内容了，之前咱们的重心一直都是在特征选取上，如何获得更好的特征是重中之重，但是并不代表机器学习就不重要。所以这最后一部分，理所当然的，咱们来谈谈强化学习。

除此之外呢，咱们还会讲讲关于图的部分，就是 GCN。虽然大模型 LLM 最近一年十分火爆，但是其实很多时候，我们还是需要从底层去理解 AI 的内容，那 GCN 就是绕不过过去的内容。也就是在前两年，2021 年左右，GCN 是非常火热的技术。所以我们需要对它的原理和工具有一些了解，这个就是属于深度学习的相关内容了。

「GCN」，这里的 G 就是 Graph，CN 基本上就是 CNN 差不多，是卷积神经网络。其实从名字上分析，我们知道它应该是「图卷积神经网络」。

图卷积神经网络是在图的基础上做了特征的提取，这个特征提取能力对于图的特征提取来说是非常强大的一个武器，把特征提取完以后就可以用于后续的分类任务。

回顾 Graph Embedding

GCN 在推荐系统里应用的比较多，强化学习也是重要的一个研究方向。

还是以美国大学生足球队为例，之前的很多课程都是用的这个数据，大家应该都看过很多次了，没看过之前课程的同学也没关系，咱们再来稍微介绍一下。

数据文件是 football.gml，这是一个图数据，gml 文件，一共包括 115 支球队，被分成了 12 个联盟。球队和球队之间会参加一些比赛，我们会把它设成一条边。简单的介绍就是如此，那详细的内容，大家可以回头去看看《28. BI - 图论工具的作用》这一课。

20240225144425

原始数据是比赛的一些行为，看过之前课程的同学可以回忆一下，最开始的时候给大家讲过，上图是一个足球队的比赛图，是一个graph。要在图上进行学习最早的开山之作应该是 DeepWalk。

2014年 KDD 的一篇论文，创造性地把 Word Embedding 和 Random Walk 做了一个结合。Embedding 最早的技术是对单词做一个嵌入的学习，单词就是一条线。那怎么样让它转换成为一个序列？需要给它构造，所以加了个转换器，这个转换器就是 Random Walk。

之前的课程也给大家说了，DeepWalk 可以用于推荐系统的场景。每个人都会有点击的一些序列，一个人可能会有多个序列，采集的样本只是现实中的一种可能性，其实还有更多种可能性。我们可以用图来构造出来，这些就是属于商品之间的流转关系。

20240113230642

如果从 A 到 B 有连接是先后顺序，我们就加一条边做一个指向。所以第一步先构造图，构造图是指存储它各种可能的直达关系。紧接着通过 Random Walk 做一些采样，因为最终你要学习内容，肯定还是要把它转化成一条直线。所以是在图上面采用了 Random Walk 这个技术，最后再基于它来去做一个 Word Embedding，就是使用了 Google 的 Word2Vec 这个工具。

这样我们就会自动的从图上面学习出来更多的一些内容，可以把每个商品 item 求出来它的 Embedding。

Embedding 就是特征提取，它是嵌入到一个固定的向量空间中。有了 Item Embedding，每个商品都有一个维度的向量，后面就可以有各种各样的任务。

一般最常见的任务，假设把淘宝上百万商品每一个的特征都学出来了，下一步可以怎么样去利用特征去做一些业务场景呢？最经典的业务场景应该是推荐。就是基于你点击了这个商品，给你推荐相似的商品。所以相似商品的计算逻辑实际上是计算 Embedding 的 Similarity，就是找相似，只要去找相似的商品就可以了，找相似商品的前一步就是要对每个商品的特征要了解。

其实不光是商品的相似度，找人的相似度也是同样的应用场景。将人做一个 Embedding，可以称为 User Embedding。如果你关注了一个大V，比如说赵丽颖，那跟赵丽颖相关的还有哪些 User Embedding 是类似的，就也会给你做推荐。

除了开山之作 DeepWalk 之外，事隔两年，同样在 2016 年的 KDD 上又提出来一种新的方法，之前咱们也讲过，不知道有没有人可以回忆起来，就是 Node2Vec。

这个新的方法改进其实并不大，只是做了一些很巧妙的方式。DeepWalk 之所以能成名，就是因为它巧妙的加入了一种采样的方式：随机采样，这种随机采样可以看成一种样本采样的策略。

那问题来了，Random 作为策略是好策略吗？如果把策略用随机的方式来进行生成会不会它比较随机？它并不是一个优质的策略。所以 Node2Vec 就会希望能得到一些目的性而不是纯随机，因此它加入了两种游走的方法，一种是 BFS，一种是 DFS。

20240115131108

这一部分内容，咱们在《31. BI - 从原理到实例，详解 Node2Vec 算法》中就有详细的讲到过。

预测结果其实用随机的方式也能得出一个答案，但一般来说是属于中等的，不是那么好，如果要更好需要给他一些智能。所以 BFS 和 DFS 就是它的智能。

实际上就像是一个船长一样，他开船是有方向的，要不就是发现新大陆，像哥伦布一样越走越远，这是蓝色线条，这个就是深度优先 DFS。要不就是在周边进行游走，红色的部分，就是广度优先 BFS。仅仅是加了这么一个小的策略，咱们回忆一下之前的案例，它特征提取的能力比 DeepWalk 更好。

在作者的论文中告诉我们，Node2Vec 可以达到的上限是最优的，对比其他 Graph Embedding 模型来说。

什么是 GCN

回顾了之前所讲的 Graph Embedding 之后，今天要去进行介绍的是另辟蹊径，并没有沿用 DeepWalk 的游走策略，而是沿着神经网络的策略，我们称呼这种方式叫做GCN：Graph Convolutional Networks.

GCN 这种方式现在已经在各个领域里面普遍在应用，包括计算机视觉 CV，自然语言处理 NLP 以及大家熟知的推荐系统 RS，这三个层面都会有很多的应用。

近期非常流行的 YOLO（You Only Look Once）在网络结构上就是采用了卷积神经网络（CNN）作为主干网络，结合了单个前向传递来实现端到端的目标检测。

一般来说，看到 GCN 的时候通常都会想到 CNN。CNN 咱们在《核心能力基础》中有详细的讲解过，忘记或者没看过的可以看一下相关的《29. 深度学习进阶 - 卷积的原理》，咱们在这里稍微的讲解一下。

alt text

CNN 一般是在图像里面去运用的，图像里面的 CNN 的逻辑如上图，其模型用于提取图片特征。CNN 处理的图像或者视频中像素点（pixel）是排列成很整齐的矩阵。CNN 的核心在于它的 Kernel，我们称之为卷积核，这个卷积核就是一个个小窗口，在图片上平移，通过卷积的方式来提取特征。

关键点是在于图片结构上的平移不变性，即一个小窗口无论移动到图片的哪一个位置，其内部的结构都是一模一样的，因此 CNN 可以实现参数共享。

实际上它本身是一个 filter 过滤器，它做的是一个函数的计算，也就说我们把图像的某一个区域做了一个特征的计算。提取出来这个特征可以用于后续的预测，所以 CNN 本身就是一种函数。

CNN 一般作用于欧式空间，无法作用于非欧式空间，具有几个特点：

权重共享：同一个卷积核可以作用于不同的位置
局部性：欧式空间可以简洁的支持卷积核（直接根据卷积公式计算卷积结果即可），卷积核的大小一般远小于输入信号的大小
多尺度：CNN 往往包含下采样，可以减少参数，并获得更大的感受野（receptive field）

回到咱们的 GCN，可以把它理解成也是一种 filter，也是一种函数，做了特征提取。区别在于，以前是在图像 image 上做特征提取
，而现在在 Graph 上。所以从本质上来说，它是针对 Graph 做了一种特征提取。

GCN 可以在图像里面使用，也可以在文本领域去使用，如果你能把它看成文本之间的一张图的关系。

20240226112857

如上图，文本和文本之间可以构造一张图。回想一下之前给大家讲过的 TextRank，应该是在[[27. BI - PageRank相关算法]] 中详细的讲解过。文本和文本如果在共同的一个窗口里面，我们会给它连一条边，从整体上来看的话它本身是一张图。在图上进行学习提取特征就可以用 GCN，GCN 解决的就是可以用于单词的特征提取，最终可以用于 Text Classification，文本的分类。所以 GCN 是可以用于文本分类的，而文本分类又属于 NLP 里面一个很重要的任务，所以 GCN 跟 NLP也是有关系的。https://arxiv.org/abs/1809.05679

那 GCN 到底是什么？它叫做图卷机神经网络，本质是个特征提取器，只不过现在变成了Graph 来进行特征提取。

Graph，之前的课程里给大家介绍过，如果去看图的定义实际上两个组成部分，第一个是 node，第二个就是 edge，节点和连线。咱们看一下 gml 里面，它的定义就是这两个部分的定义。所以一个图就是顶点和边的关系。

特征提取其实也是利用顶点和边，因为它只有这两个部分。《Semi-Supervised Classification with Graph Convolutional Networks, 2017》这篇论文发表在 2017 年：https://arxiv.org/abs/1609.02907。相对于原来传统的深度学习来说它实际上是挖掘关系，因为它是在图上面，而图这种结构比较百搭。

比如说商品之间可以看成图，语意的分析可以是一个图，交通网络、社交关系、金融链流转的关系、资金链的关系等等这些都可以看成图。图上的学习要采用的就是 GCN 这个方法。

GCN 算法

接下来咱们就看看，GCN 到底是怎么去利用顶点和边去做特能提取的。

20240226132817

一张图的定义是由顶点和边组成的，比如上面这张图，就是一张图有6个顶点和它相关的一些边，这样的一个图的结构应该是非欧几里得数据。

每一个顶点连接的边的数量有可能是不等的，非欧基里德数据直接学习不好学，那该怎么去转换呢？第一个思路是把非欧的数据要变成欧式数据，非欧就是不规则，不规则的要变成规则，矩阵算不算规则？

图像就是规则的，图像本质上就是一个矩阵的表达。所以能不能把原来的 Graph 表达的方式看成一个矩阵？如何去定义这个矩阵？我们要表达顶点和边的关系。

$\begin{align*} \begin{bmatrix} 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} \end{align*}$

上面这个矩阵是一个邻接矩阵，它存储的是顶点和顶点之间的连通性。一共是6个顶点，矩阵一共有 6 行，还有 6 列。如果跟其他顶点之间有边就写为 1，没有边就为0。以第一个为例，1 跟 2 跟 5 有边，其他都没有边。以 2 为例，2 跟 1、3、5 有边，所以为 1，其他都为 0。

这种矩阵的表达方式称为邻接矩阵，它保存的是邻居之间的一些特征，把这个连贯性给保存起来了。

上面的图和下面的邻接矩阵，图只要确定下来了，那跟邻居之间的联通性就确定下来了，连通性确定下来以后邻接矩阵应该就是唯一确定的，反推也是一样，邻接矩阵确定下来以后图的连通性也是确定的。

所以第一步就需要把它用邻接矩阵表保存起来，它存储的是一个边的连通的关系。

再想一想，图上还有哪些重要的特征？我们知道非欧基里德的这个数据，它的一个关键点是在于每个顶点的连接边数有可能是不等的，这个是属于一个重要特征，再回到上面那张图：

20240226132817

6 的连接的点的边数就为 1， 2 的连接点就为3，1 这个顶点就为2。所以每个顶点连通的个数有可能是不一样的，这个也算一个重要特征。所以也用一个矩阵叫做度矩阵：

$\begin{align*} \begin{bmatrix} 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \end{align*}$

「度」这个词之前给大家讲过，顶点连接边的个数就是度。这个度矩阵把它跟邻居之间的连通的个数给写下来，最终把它保存到了对角线里面去。因为原来的邻接矩阵对角线都为0，自己和自己的连通性就不记了，只记录跟别人的连通性，在对角线上正好空缺了一个位置。度矩阵也只需要一个位置就行了，所以度矩阵就是在对角线上把度写出来。

这个特征还是挺重要的，可以看到 4 这个顶点的连通性还是非常多的，四通八达，跟其他的顶点之间都有连通性。而 6 就比较偏了，只跟一个顶点有连通性。所以由原来的原始数据可以看到两种特征，第一，连通性的特征，第二，连通性强度的特征。这两个特征都可以从原始的输入数据中来进行提取。

接下来就需要思考，我们用了两种特征，能不能够得到一种新的特征，把前面的特征 1 和特征 2 结合起来？比较明显，既然已经把度矩阵放到对角线上了，而且原来的邻接矩阵表对角线上是缺失值，所以可以把它综合起来。

假设前面的邻接矩阵叫做 A，后面这个叫做 D，有两种综合的方式。一种是 $D + A$ ，一种是 $D - A$ ，这两种都可以把两个特征合二为一。
那问题来了，哪种综合的形式会更合理，更有效一些？是第一种把这两个加到一起还是两个做一个减法？

第一种，把对角线做一个相加，原本特征的强度可能已经很大了，再加上一个就变成 double。如果它数量很大，也就相当于说这一条线的量纲有可能很多。夸张一点，比如这个顶点跟100个都有连接，本身连通的数量已经很多了，现在又加了一个100，它连通性其实已经很大，量纲很高，中间可能有个顶点很偏，只跟一个有连接，其本身很小，所以可能上面这个特征如果按量纲来算的话可能是下面的100倍。

为了方便，每个顶点权重都是一样的，如果做了减法，那整个的量纲就统一了。也就说不管某一行还是某一列，它的和都为零。因此就直接可以给它做一个规范化处理，直接用 D 减去 A，把它设为一个新的特征，这个就叫做「拉普拉斯矩阵」：

$\begin{align*} \begin{bmatrix} 2 & -1 & 0 & 0 & -1 & 0 \\ -1 & 3 & -1 & 0 & -1 & 0 \\ 0 & -1 & 2 & -1 & 0 & 0 \\ 0 & 0 & -1 & 3 & -1 & -1 \\ -1 & -1 & 0 & -1 & 3 & 0 \\ 0 & 0 & 0 & -1 & 0 & 1 \end{bmatrix} \end{align*}$

$L = D - A$ , L 为拉普拉斯矩阵， D 为 Graph 中节点的度，A 为图的邻接矩阵。也就是度矩阵减去邻接矩阵。

直接做减法的结果，对角线还是度，然后邻接矩阵有值的地方就变为了 -1，这个特征就合二为一，在图上构造出来了一种结合的特征的方式。可以把它理解成就是一次性的把图上的一些关键点的特征都提取出来了。这种算子叫做拉普拉斯算子。

我们现在只是看到了一种情况，也就是 D - A，这个是为 Combinatorial Laplacian。为什么比加法好，原因是因为它已经做了个规范化的操作，因为每一列每一行和为 0。除了和为 0 是一种规律化的操作，还有其他操作。

其他操作，我们还可以用 A 除上 D，Random walk normalized Laplacian：

$\begin{align*} L^{rw} = D^{-1}A \end{align*}$

-1 代表的是倒数, 也就是 $\frac{1}{D}$ 。原来的矩阵是 A，现在如果除上 D，那原来的 A 就会变成：

$\begin{align*} \begin{bmatrix} 0 & 1/2 & 0 & 0 & 1/2 & 0 \\ 1/3 & 0 & 1/3 & 0 & 1/3 & 0 \\ 0 & 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 0 & 1/3 & 0 & 1/3 & 1/3 \\ 1/3 & 1/3 & 0 & 1/3 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} \end{align*}$

这样再去做累加，就也做了一个规范化的操作。因为都除上了一个度，每一行的和就会等于 1，这个量纲就也统一了。所以拉普拉斯它有两种作用，第一个就是把两个特征合二为一，综合考虑了原始的一些特征。第二个规范化进行操作，因为在神经网络过程中层级有可能会很多层，如果量纲不统一后续会维度爆炸，原来量纲比较大的在后面会越来越大。为了方便可以把它拉回到同样的尺度上面，更好的来进行学习。

除此之外，还有一种平均的功能化操作，就把它变成了 $D^{-\frac{1}{2}}$ 。

$\begin{align*} L^{sys} = D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \end{align*}$

可以把它理解成为新的一种对称型的拉普拉斯，整个拉普拉斯矩阵是有三种计算逻辑。这三种里面的 L 可以理解成 GCN 的特征算子，特征算子就是对原始数据做特征提取的那个函数。把原始数据给到它，它基于特征算子进行特征提取，可以得到一个结果。

如何在图上提取一些特征，这是给大家讲了 3 种特征提取的 function，好不好后面可以评估，至少是一种特征提取的方法。

这个方法怎么去使用在原始的图上呢？咱们一起来看一看它是怎么样去做图的计算的。

原来一张图 G（G=(V, E)）有 n 个顶点，每个顶点都有自己的特征，目标是要学习图上的信号或特征的一个映射。GCN 模型的输入为矩阵 X 和 A，X 是一个原始数据，A 可以把它理解成就是个邻接矩阵，就是这个图的关系：

矩阵 X，表示这些顶点特征， $\times D$ 维矩阵
矩阵 A，表示各个顶点之间的关系， $\times N$ 维矩阵，也称为邻接矩阵（adjacency matrix）

GCN 是一个网络层，神经网络它的层级会很多，前一层的输出会作为下一层的输入，那写出来下一层就是(l+1):

$\begin{align*} H^{l+1} = \sigma \begin{bmatrix} \tilde D^{-\frac{1}{2}} \tilde A \tilde D^{-\frac{1}{2}} H^{(l)}W^{(l)} \end{bmatrix} \end{align*}$

这个公式矩阵内前半部分就是拉普拉斯算子（ $\tilde D^{-\frac{1}{2}} \tilde A \tilde D^{-\frac{1}{2}}$ ），后半部分就是这一层乘上它的权重（ $H^{(l)}W^{(l)}$ ）。其中对原始数据做了一个拉普拉斯算子的一个提取，又乘上了一个 W（它的权重），就等于这一层输出的结果。

$\tilde A = A + I$ , I 是单位矩阵
$\tilde D$ 是 $\tilde A$ 的度矩阵（degree matrix），公式为 $\tilde D_{ii} = \Sigma \tilde A_{ij}$
H 是每一层的特征，对于输入层的话，H 就是 X
$\sigma$ 是非线性激活函数
$\tilde D^{-\frac{1}{2}} \tilde A \tilde D^{-\frac{1}{2}}$ 可以提前算好，固定不变。

输入的是个 X 乘上一个 function，再乘上一个 W，W 是这一层的神经元的系数。输出以后又加了 $\sigma$ ，也就是激活函数，可以用relu，还可以用 Sigmode都可以。激活函数的目的就是把原来的数据变成一种非线性的映射关系，神经网络里面是可以加激活函数的。所以它的传递可以看成实际上就是 CNN，只不过现在不叫 CNN，而是叫做 GCN。

所以呢，GCN 其实也没这么神秘，只是在图的关系上面提取了一个特征。

大家可以看看 GCN 算法的公式解释：https://tkipf.github.io/graph-convolutional-networks/

在 GCN 算法中，每一层 GCN 的输入都是邻接矩阵 A 和 node 的特征 H，如果我们直接做一个内积，乘一个参数矩阵 W，再激活一下，就相当于一个简单的神经网络层：

$\begin{align*} f(H^{l}, A) = \sigma(AH^{(l)}W^{(l)}) \end{align*}$

实验证明，使用这个简单的神经网络层，就已经很强大了。不过这个简单模型有 2 个局限性，一是只是用 A 的话，由于 A 的对角线上都是 0，所以在和特征矩阵 H 相乘的时候，只会计算一个 node 的所有邻居的特征的加权和，该 node 本身的特征会被忽略。

如果在运算过程中只把周边邻居的特点做了一个叠加，下一次运算，自己的特征还存在吗？如果只是提了一个 A，原始数据直接乘上这个值，对角线自己都为 0，所以在下一层的输出的过程中自己会变成邻居了，变成你的邻居那自己的特征就丢掉了。有没有一些可能性，要保留原来自己的这套特征，就是学别人的内容融到自己里是没有问题的，但是原来自己的那套结果也要保留下来。

这里可以做一个小改动，就是给 A 叫上一个单位矩阵 I，这样就让对角线元素变成 1 了。原来是 A，现在加了一个 $\tilde A$ ，之前讲过 $\tilde A = A + I$ ，I 就是一个单位矩阵。

怎么填充？对角线为 1。所以现在这个邻接矩阵加了一个对角线为 1，这个目的就是在特征提取过程中不要把自己忘掉，否则就只有邻居的特征。所以真正去使用的时候使用的是 $\tilde A$ 。

$\tilde A$ 的度，就会把它称为 $\tilde D$ 。所以 D 上面这个小帽子实际上是对 A hat 的一种度矩阵的计算逻辑。

在真正的提取过程中实际上并不是用了一个原始的邻接矩阵，而是用了一个 A hat 和 D hat，用了对称型。

局限 2，A 是没有经过归一化的矩阵，如果 A 与特征矩阵 H 相乘会改变特征原本的分布，产生一些不可预测的问题。

神经网络的计算过程中归一化价值还是非常大的，如果不做归一化，它后续的网络层级会把它放大。所以为了让它标准，量纲统一，做一个规范化的操作。

对 A 做一个标准化处理，首先让 A 的每一行加起来为 1，然后对 A 乘以 $D^{-1}$ ，D 为度矩阵，可以解决局限 2。

进一步把 $D^{-1}$ 拆开与 A 相乘，得到一个对称且归一化的矩阵：

$\begin{align*} D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \end{align*}$

结合这两种改进的方式，最后得到：

$\begin{align*} f(H^{(l)},A) = \sigma \begin{bmatrix} \tilde D^{-\frac{1}{2}} \tilde A \tilde D^{-\frac{1}{2}} H^{(l)}W^{(l)} \end{bmatrix} \end{align*}$