文章目录
- 前言
- 一、为什么要选择图进行机器学习？（起源）
- 1.现代深度学习工具的不足
- 二、图神经网络定义
- 1.有监督机器学习全流程图
- 2.图表示机器学习
- 三、图机器学习的应用
- 四、图表示的选择
- 1.图的组成部分
- 2.一些图表示的方式
- 1.有向图VS无向图
- 图的度数
- 2.异构图
- 3.二部图
- 4.图的表示
- 4.1邻接矩阵
- 4.2 边序列
- 4.3 邻接表
- 4.4 边有权重或无权重
- 4.5 联通性
- 总结
前言
本章主要介绍了图神经网络的起源、定义、应用与总结。
课程建议先修知识点： 1.机器学习、2.算法与图论、3.概率论与数理统计
一、为什么要选择图进行机器学习？（起源）
图是用于描述并分析有关联/互动的实体的一种普适语言。它不将实体视为一系列孤立的点，而认为其互相之间有关系。它是一种很好的描述领域知识的方式。复杂领域有丰富的关系结构，可以表示为关系图通过显式建模关系，我们实现更好的性能!
1.现代深度学习工具的不足
现代深度学习传统工具目前在图片处理和文本处理（包含语音）中大放异彩，但是其很难用于图的建模，其难点在于网络的复杂，主要体现在：
- 图具有任意大小和复杂的拓扑结构，没有文本或者图片那么规整（如文本、语音等具有线性结构的数据序列sequence；图片具有平移不变性的网格结构，见下图）
- 没有基准点，没有节点固定的顺序。没有那种上下左右的方向
- 经常出现动态的图，而且会有多模态的特征
所以要想让神经网络适用范围更加广泛，我们需要开始引入图神经网络的学习。
二、图神经网络定义
下图是图神经网络流程图，我们可以看到输入网络，经过图卷积、激活、正则…，最后得到节点的标签、新的连接、生成新图和子图。
1.有监督机器学习全流程图
我们从上图可以看出，图机器学习相比较之前的有监督机器学习来说，少了特征工程（比如手动提取特征等），取而代之的是图表示学习（自动地学习特征）。（个人感觉方便多了，这也是图机器学习相比较传统机器学习的有优势的地方）
2.图表示机器学习
大致来说就是将原始的节点（或链接、或图）表示为向量嵌入（embedding），图中相似的节点会被embed得靠近（指同一实体，在节点空间上相似，在向量空间上就也应当相似）
接下来就是课程安排了，在此不再赘叙。
三、图机器学习的应用
图机器学习的应用可以分为以下四类，见下图
- 图级别，包括预测任务（graph-level prediction）和图生成任务（graph generation）
- 节点级别（node level）
- 社区 / 子图级别 （community(subgraph) level）
- 边级别 （edge level）
下面都是他举出的图机器学习应用的例子，有解决蛋白质折叠问题——AlphaFold，PinSage：基于图的推荐系统，以及应用到医学或物理问题求解等，可以看出图机器学习的应用具有很高的应用价值。
四、图表示的选择
1.图的组成部分
从上图我们可以看到，一个图是由三部分组成的。
- 节点（N或V）
- 链接 / 边（E）
- 网络 / 图（G）
图是一种解决关系问题时的通用语言，各种情况下的统一数学表示。将问题抽象成图，可以用同一种机器学习算法解决所有问题。接着作者开始举例，比如把工作的同事们连接起来，你将会得到一个工作网…但不是所有的连接都是有意义的。
所以，为问题选择合适的表示方法是个很难的任务。你将考虑不同的情况： - 在某些情况下，只有一个独特的、明确的图表示方式
- 在某些情况下，图表示方式不是唯一的
- 分配边的方式将决定图可以学习的问题的性质
2.一些图表示的方式
1.有向图VS无向图
图的度数
- 有向图：分成 in-degree 和 out-degree ，(total) degree是二者之和
- 无向图：Avg. degree:
k
‾
=
<
k
>
=
1
N
∑
k
=
1
N
k
i
=
2
E
N
\overline{k}=<k>=\frac{1}{N}\sum_{k=1}^N k_i=\frac{2E}{N}
k=<k>=N1∑k=1Nki=N2E
判断是否是有向或者无向图时候，可以根据度数来判定。
2.异构图
下面的图是异构图的例子：
3.二部图
二部图是一个图，它的节点可以分成两个不相交的集合U和V，使U中的一个节点与V中的一个节点相连接;也就是说，U和V是独立集。如下图所示。
下面是折叠/映射二部图。
4.图的表示
4.1邻接矩阵
每一行/列代表一个节点，如果节点之间有边就是1，没有就是0。下图是无向图和有向图的邻接矩阵。
可以看到，无向图的邻接矩阵天然对称和网络的邻接矩阵往往是稀疏矩阵。
4.2 边序列
用一系列边来表示图
这种方式常用于深度学习框架中，因为可以将图直接表示成一个二维矩阵。这种表示方法的问题在于很难进行图的操作和分析，比如说计算图中点的度数都会很难。
4.3 邻接表
如果网络很大或者稀疏（或两者兼有时候）比较方便，它允许我们快速检索给定节点的所有邻居。
4.4 边有权重或无权重
下面是自循环或者多图。
4.5 联通性
- 无向图的联通性
联通的：任意两个节点都有路径相通
非联通的：由2至多个联通部分构成最大的子连接图
- 有向图的联通性
**强连通有向图:**从每个节点到每个其他节点都有一条路径，反之亦然(如a - b路径和B-A路径)
**弱连通有向图:**在不考虑边方向的情况下是连通的
- 强连通分量
强连通分量可以被识别，但不是每个节点都是一个强连通分量的部件。
总结
