CS224W 图机器学习

• 参考视频：

  • 【图机器学习Machine Learning with Graphs】精译【Stanford 公开课 CS224W (Fall 2021)】(中英双语字幕)

• 为什么要写课程笔记？

  • 课程我是全程跟看的，防止看了一遍视频啥都没懂，所以记下笔记让自己有印象
  • 让它变成我的“工具书”，想看的时候随时都可以查阅，而且该课程很经典，值得反复观看

介绍

为什么使用图？

图结构强调的是表征学习 (representation learning)，在处理传统的行数据时，我们需要将数据进行特征工程变换，从而能够应用相关算法；但图数据不需要特征工程，它可以直接通过图的关系结构学习特征

图中的节点被映射为一个 d 维的 embedding 向量，从原图中映射到一个表征空间中，成为一个表征向量

机器学习中图的应用

一个图结构可以被拆分为多个层次，每个层次都有相关的应用可以实现

• 节点分类：用户分类/目标分类
• 链接预测：知识图补全
• 图分类：分子属性预测
• 聚类：社交网络检测
• 图生成：药物检测
• 图进化：物理模拟

Example

AlphaFold 预测蛋白质结构 以 DeepMind 推出的 AlphaFold 为例，AlphaFold 是一个用来预测蛋白质结构的深度学习模型，其中关键的创新点就是使用了空间图结构来进行表征学习； 节点表示蛋白质中的每个氨基酸 边表示蛋白质中的氨基酸序列之间的距离

Example

推荐系统 在推荐系统的图中，节点表示用户和物品，边表示用户和物品之间的互动，例如：评论、点赞等等，目标是给对应的用户推荐喜欢的产品

Example

药物副作用预测 在这个例子中，我们使用图结构去预测多种药物和不同蛋白质之间可能产生的反映，这是一个 semi-supervised learning 任务，因为在这个例子中某些药物之间的副作用是不明确的（我们不能知道所有药物组合的副作用）

Example

交通情况预测 节点表示路段，边表示路段之间的连通性，通过构建这样的图结构预测子图的预计到达时间，虽然在例子中没有介绍具体的实现方法，但我想了一下，可能直接选择子图中的所有节点 embedding，然后做 sum/mean/min/max 操作求得一个最终的向量并做回归预测

Example

药物发现 通过构建分子和分子之间的化学键，可以得到现有药物的所有化学式所表示的图结构集合，放入深度学习模型中可以预测出哪些分子是有治疗效果的，从而让人们减少工作量，只关注重要的分子构成

选择图结构的原因

1.3 - Choice of Graph Representation字幕版_哔哩哔哩_bilibili

在现实生活中，有许多图表示的例子，比如电影中的人物关系、社交网络、蛋白质结构等，都可以被抽象成同一个图结构

但在构建图结构时，需要特别注意节点和边的构建，例如在学术论文分类任务中，如果我们仅仅将论文标题的词作为节点，论文之间的引用关系作为边，显然是错误的，因为同样的标题可能包含的内容完全不一样

无向图和有向图

节点的度

无向图中，节点的度表示该节点所连接边的数量，平均度：$\bar{k}=\frac{2E}{N}$

有向图中，分为入度和出度，例如 C 节点的入度为 2，出度为 1

二部图

二部图只有两种类型的节点，两种类型的节点之间有边相连，但同类型节点之间没有边相连，如图中右侧的二部图所示

应用场景：

• 作者与他们写的文章相连
• 演员与他们参演的电影
• 用户与他们评价的电影
• 配方与配方所包含的配料

投影映射网络

对二部图进行转换可以得到左边或者右边的图，创建方法也很简单：以投影 U 为例，在 V 中的每一个顶点找到与之连接的 U ，表示这些节点存在联系，用边连接起来，得到投影 U

在作者与其撰写的论文二部图中，左侧的节点表示作者，右侧的节点表示文章，投影 U 表示文章的作者之间的关系，共同作者之间会有边连接

图的表示

邻接矩阵

真实世界中的邻接矩阵通常都是一个稀疏矩阵，但这会导致一个很严重的问题，在计算机中的存储效率不高！

对邻接矩阵的列/行求和，就得到了节点的度

边列表

深度学习中常用，但问题是难以对图进行更进一步分析，因为哪怕是计算度都需要一定的时间

邻接列表

邻接列表的好处是可以快速找到节点的度，适用于更大和稀疏的网络

节点和边属性

边的属性可以直接用邻接矩阵表示出来

同时，还可以考虑自循环节点和频率作为权重

图的连通性

无向图

如果图是非连通的，可以在邻接矩阵中看到两个小的对角矩阵

有向图

弱连通图：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图

强连通图：在有向图中, 若对于每一对顶点 v1和 v2, 都存在一条从 v1到 v2和从 v2到 v1的路径,则称此图是强连通图

强连通分量：有向图的极大强连通子图，称为强连通分量

图机器学习中的特征工程

传统的基于特征的方法：节点

在传统的机器学习模型中，我们需要训练一个机器学习模型，这个模型的输入是数据的特征，输出是预测的结果，应用到图中，就是给定图结构的特征，进行预测

但上述方式存在问题，输入特征是模型是否能有较好性能的关键因素，但传统的机器学习方法的输入特征需要进行手动编码

本节中，介绍了几种传统的特征处理方法

节点预测

上图中，绿色节点最少有 2 个度，红色节点只有一个度，为了实现对节点的分类，我们需要建立模型学习节点在图中的位置和结构关系，总结共有 4 种方法：

节点度

第一种方法是通过节点的度进行区分，但问题是有些节点有相同的度，这些节点是没办法区分的

节点度只考虑了邻居节点出现的次数，没有捕捉它们的关键信息，但反映了节点在图中的重要性，节点度越大，说明与其向量的邻居节点越多，在图中的重要性就越大

节点中心度

特征向量中心度

Summary

如果我的朋友很重要，那么我也就很重要，节点的重要性取决于邻居节点的重要性

公式如上图所示，$c_v=\frac{1}{\lambda }\sum _{u\in N(v)}{c}_u$，其中 $\lambda$ 表示一个常量，是一个标准化的操作，$c_u$ 是与节点 $v$ 相邻节点的中心度

从上面的式子来看，如果在一个很大的图谱上做递归运算，且图谱的度数很深，甚至存在环路，则需要非常大的栈内存，同时计算效率也不高。

为了解决上述计算问题，我们提出了如下的方法：

Important

假如 A 是多维(n)矩阵，且有 n 个不同的特征值，那么就可以理解成这个矩阵 A 和一个向量 x 相乘其实就是把向量 x 往 n 个特征向量的方向进行拉伸，拉伸比例是对应的特征值。

Quote

Perron–Frobenius 定理证明了存在一个方阵，如果其行列的元素为正值，则存在最大的特征值 ${\lambda }_{pf}$ ​ ，并且该特征值所对应的特征向量的每个元素都是正数。

从上图中可以看出，$c$ 是矩阵 $A$ 的特征向量，向量中的值表示每个节点的中心度，根据 PF 定理，最大的特征值永远为正且唯一，最大特征值对应的特征向量作为节点的中心度

中介中心度

中介中心度量衡量的是从 s 到 t 节点的最短路径中，有几个包含了节点 c 记录其数量并除以最短路径总数，就得到了中介中心度量的结果

Summary

本质上，给定节点的路径越短，越重要，这种度量方法体现了给定节点的连接性和传输的优劣程度

接近中心度

Summary

如果一个节点到达网络中其他节点的路径和是最短的，那么它是重要的

聚类系数

聚类系数衡量一个人与邻近节点直接的联系程度，式中的分母表示 $C_{k_v}^2$，$k_v$ 表示节点 v 的邻居节点数量，分子表示邻近节点之间边的数量

图元

仔细观察不难发现，edges among neighboring nodes 的数量就是图中三角形（三元组）结构的数量

一个简单的结论：朋友的朋友也是我的朋友，在许多的社交网络中，会有很多的三角结构，而聚类系数是一个非常重要的度量值

上图展示了节点为 2-5 的所有图元，列举了给定节点，节点之间不同连接构成的不同图结构，黑色和白色的节点，表示节点是否同构/异构

GDV 表示基于图元特征的点的集合，从宏观来看，GDV 能够捕捉更多的图中的结构信息

Example

如图中所示，图元中不同的节点共有 $a,b,c,d$ 四个，图元实例共有 $[2,1,0,2]$ 个

如果我们只考虑大小为 2-5 节点的图元，那么我们可以得到任意一个图中节点的长度为 73 的向量，这个向量表示了节点和邻居节点的拓扑结构

传统的基于特征的方法：连接

定义：基于网络中现有的连接，对新的连接做出预测 ，预测的关键是设计一对节点的特征

连接预测的方法：

1. 网络中的连接随机缺失 让网络中的连接随机缺失，然后目标就是预测出它们
2. 按照时间顺序来预测 已知在时间 $t_0\to t_0^{{}^{\prime }}$ 时间段有一个图 $G$，基于 $t_0^{{}^{\prime }}$ 时刻的图结构，输出一个未来可能出现的连接排名列表 $L$，这个列表 $L$ 会在时间 $t_1\to t_1^{{}^{\prime }}$ 中出现 评估方法：已知在未来一个时间段内会生成 $n$ 个边，那么就从连接列表 $L$ 中选择前 $n$ 个作为预测边，并与正确结果进行比较

通用的方法：

1. 设计一个分数函数衡量节点 $x,y$ 之间的分数
2. 按照分数，对所有的这些节点对进行降序排列
3. 把预测的前 $n$ 个节点对作为新的边
4. 把新的边与真实结果做对比，进行评估

基于距离的特征

取两个节点对的最短距离作为其特征

但这种方法效果很差，因为并没有考虑到节点对之间的重叠度，例如在图中，$(B,H)$ 之间有两个共享邻居节点 $C$ 和 $D$

局部邻域重叠

为了解决上述问题，我们需要捕捉两个节点之间的共享近邻节点的关系

1. 计算两个节点的邻居，分别记作 $N(v_1)$ 和 $N(v_2)$，然后取两者的交集的模（即两者中有多少共同的邻居）
2. Jaccard 系数是 1 方法的标准化版本，其分母是两者的并集
3. Adamic-Adar 指数：对节点 $v_1$ 和节点 $v_2$ 共有邻居的度进行求和，然后用 $\frac{1}{\log K_u}$ ，例如在图中，$(A,B)$ 的共享邻居节点是 $C$，其 Adamic-Adar 指数就是 $\frac{1}{log(C_{dgr})}$ 通俗来讲就是：认识一群低节点度的朋友要比认识几个大明星要好，通常在社交网络中很有用

然而这种方法也是存在缺陷的：

如果一个图特别大，连接的两个节点的距离大于 1，那么就会出现一直为 0 的情况，但显然距离大不代表未来不可能有连接

全局邻域重叠

前置概念：

• Katz index：计算一对节点之间不同路径的数量

Important

如何用矩阵表示这一问题？ - 假设图存在邻接矩阵 $A$，那么对于给定长度为 1 的路径数就是 $A$

如何计算高阶次矩阵？

1. 计算节点 u 到 v 之间距离为 1 的路径
2. 对 1 中所有符合条件的路径求和

因此对于更长的路径数量来说，就是求 A 矩阵的高阶次 高阶次的求法就是先求相似对角矩阵，然后利用相似的性质求高阶次 矩阵论中的相似与合同

求出 Katz index 之后，我们需要对所有的长度进行求和得到 $S_{v_1{v}_2}$，并且使用 $\beta$ 参数控制折扣系数

使用矩阵的方式表达就是 $S=(I-\beta A{)}^{-1}-I$

Quote

具体推导如下： $(I-\beta A)(I+S)=(I+\beta A+{\beta }^{2}A+\dots )-(\beta A+{\beta }^{2}A+\dots )=I$，对等式两边进行适当移项就可以得到 $S=(I-\beta A{)}^{-1}-I$

传统的基于特征的方法：图

我们的目标是获取一组特征，能够描述整个图的结构特征

核方法简介

• 核方法在传统的图级别的机器学习预测任务中被广泛应用，方法的关键就是设计一个核函数替代特征向量
• 图 $G$ 和 $G^{{}^{\prime }}$ 之间的核函数 $K(G,G^{{}^{\prime }})$ 返回了一个值，这个值描述了这两个图之间的相似性
• 一个核如果是有效的，那么需要保证核矩阵是一个半正定矩阵，关于正定概念见 这里，半正定就是条件从 $<$ 变为 $\le$
• 存在一个特征表示 $\Phi$ ，满足 $K(G,G^{{}^{\prime }})=\Phi (G{)}^T\Phi (G^{{}^{\prime }})$，这个特征表示是隐含的，不需要显式的表示出来

本章中比较重要的两个核分别是：图元核和 Weisfeiler-Lehman 核

设计核的关键是找到一个合适的特征向量 $\Phi (G)$，例如可以类比 NLP 中词袋的概念，使用所有节点的数量作为特征向量，下面的两个图都包含四个节点，它们的特征向量是相等的

为了更进一步优化，我们可以把不同度的节点看作不同的词，分别统计它们的数量，就得到了如上的两个图的特征向量

图元核

• 图元核的思想：数出图中不同图元的数量

图元核中的图元

• 图元核的图元和节点预测中的图元方法 的区别：
  • 图元核中的图元允许孤立节点
  • 图元核中的图元不是根节点

Example

例子中的图元就是图元核，这些节点不区分根节点，同时允许孤立节点的存在

于是，对于一个图，有一个图元计数向量，定义如下：

Example

图元核定义及计算

• 对于两个图 $G$ 和 $G^{{}^{\prime }}$，图元核的计算公式为：$K(G,G^{{}^{\prime }})=f_G^T{f}_{G^{{}^{\prime }}}$，$f(G)$ 表示图 $G$ 的图元计数向量
• 虽然这种方式想法很好，用核函数来衡量两者之间的相似度，但问题是 $G$ 和 $G^{{}^{\prime }}$ 的大小可能是不同的，例如：一个图很大，图元数量很多，图元计数特征向量的值都比较大，另一个图比较小，图元数量也较小，图元计数特征向量的值都为前面图的 $\frac{1}{2}$，这就会导致 $f_G$ 和 $f_{G^{{}^{\prime }}}$ 的 Scale 是不同的
• 解决方法很简单：为特征向量添加一个标准化方法，除以计数之和，将向量 Scale 到同一个标准下

局限性

• 在一个节点数为 $n$ 的图中，计算大小为 $k$ 的图元需要花费 $n^k$ 的时间
• 上述最坏情况是不可避免的，因为判断一个子图是否是另一个子图的同构问题是一个 NP 难问题
• 如果图中节点度以 $d$ 为界，那么久存在一个 $O(n{d}^{k-1})$ 的算法计算 $k$ 大小的图元 总的来说，计算图中的离散结构是十分费时的，代价极大

Weisfeiler-Lehman 核⭐

• 目标：设计一个有效的图特征，能够描述图 $G$
• 思想：使用邻域结构迭代丰富节点的词汇表
  • 由于节点度是一步邻域信息到多步邻域信息，所以我们对节点度的概念进行扩展
• 实现这一目标的算法叫做 W-L 图同构测试/颜色细化

颜色细化

• 先分配一个初始颜色 $c^{(0)}$，并将初始颜色分配给图中每个节点
• 使用 Hash 散列算法，迭代更新节点颜色，更新节点的颜色是自己之前的颜色和邻近节点颜色串联颜色的散列值
• 在迭代 $K$ 步后，$c^{(K)}(v)$ 总结了 $K$ 跳邻居的结构

WL 核的例子

Example

1. 分配初始颜色，这里的 $1$ 就是颜色的值
2. 聚合邻居的颜色，邻居颜色串联，节点得到一个新的值
3. Hash 算法进行映射
4. 再进行聚合操作
5. 再进行散列映射
6. 计算每个节点被分配颜色的数量，我们只需要统计初始分配的颜色和每次 Hash 操作后的颜色
7. 计算 Weisfeiler-Lehman 核的值，就是对之前的向量做点乘

WL 核的优点

时间计算复杂度是 $O(\#(edges))$，与边呈线性关系，这非常适用于庞大的稀疏图结构

节点嵌入

Node Embedding

在传统的机器学习任务中，特征工程是我们需要重点关注的，我们需要人工为图收集节点、边、图级别的特征，使其能够完成表达图的结构，并利用学习算法进行下游任务

但现在我们想自动获取这些图的结构特征信息，这就叫做表征学习（representation learning）

表征学习的原理是利用高效的任务独立型特征学习方式进行图机器学习，目标是从图中得到一个特征表征向量，这个向量代表了图中节点的嵌入信息

为什么需要嵌入？

• 节点之间的嵌入相似度代表了它们在网络中的相似度，例如它们的相似度很高，很可能它们是连在一起的
• 希望能偶自动编入网络结构信息
• 这些信息能够适用于很多的下游预测任务，多个任务一个模型搞定！

上图是 Deep Walk 算法中的结果，图嵌入结果映射在二维坐标中，可以看到

编码器和解码器

如上图所示，假设有一个图 $G$，$A$ 是这个图的邻接矩阵

目标是对节点进行编码，映射到嵌入空间中，两个节点的距离，表示了它们之间的相似度

更进一步说，目标就是构建一个相似性度量函数，用来准确描述编码后两个节点的相似性

首先我们需要设计一个编码器，将节点映射到对应的嵌入空间，然后通过解码器，将嵌入映射到相似度分数，然后通过优化参数使解码后的相似度尽可能与网络相似度的定义相对应 (上图的解码器就是 $z_v^T{z}_u$)

首先编码器会将数据映射到一个 $d$ 维的低维空间，作为特征嵌入，之后将特征向量放入解码器中，这里的解码器就是相似性度量函数

Example

一个最简单的编码器就是对输入数据的查询，不同的输入数据能够得到不同的查询结果

矩阵论中的坐标变换，v 表示空间中的坐标，Z 表示一组基向量，两者相乘得到一个在空间中的向量 但两者不指代同一个内容

上面的编码器矩阵表示类似于

假设图 G 有 $N$ 个节点，那么 $Z$ 就是一个 $d\times N$ 的矩阵，向量 $v$ 就是一个 one-hot 编码的向量，对应每个节点的查询，这就意味着每个节点都有一个唯一的嵌入向量 缺点：不具有扩展性，如果是一个很大的图，图中节点有很多，那么这个嵌入矩阵可能会非常大

主要的两个嵌入学习算法：DeepWalk 和 node2vec

节点相似度

在定义完编码器和解码器后，我们需要准确度量节点之间的相似度才能通过优化算法学习到嵌入矩阵，考虑两个节点是否使一个相似的嵌入可以从以下问题考虑：

1. 它们是否是连接的
2. 它们是否有共享的邻居
3. 它们是否有相同的结构特征 一个常用的算法就是随机游走（random walks）

• 学习嵌入表示是一个无监督/自监督的任务
• 这些学习到的嵌入是与具体任务无关的，它们能够被用在不同的任务中

嵌入学习算法⭐