岁岁无虞，长安长乐

原文链接：A Gentle Introduction to Graph Neural Networks

什么是图

图是用来表示一些实体之间的关系。

• 实体：点
• 关系：边

V ：顶点属性

E ：边属性和方向

U ：表示全局信息，代表整个图

attribute ：表示每个顶点，每条边和整个图表示的信息。这些信息是我们所关心的内容。

为了进一步描述每个节点、边或整个图，我们可以在图的每个部分中存储信息。

顶点：可以使用向量来表示。图中顶点有6个值，高矮代表大小。

边：可以使用不同的向量来表示。图中边使用一个长度为8的向量表示。

全局信息：使用一个长度为5的向量表示。

图神经网络的核心：

• 我们怎么样把我们想要的信息表示成这些向量。
• 这些向量是否能够通过数据来学到。

图可以分为有向图和无方向的图。

• 有向图：github的Follow关系。
• 无向图：微信好友关系。

数据是如何表示成图的

图片如何表示成图

假设我们有一张图(244x244x3)，一般我们会把它表示为一个三个维度的Tensor。

从另一个维度来看，我们将把它视作一张图，每个像素就是一个点，如果像素之间是邻接关系则连接一条边。

• 左侧：图像像素
• 中间：邻接矩阵
• 右侧：图

文本如何表示成图

文本可以认为是一条序列，我们可以把每一个词当作一个顶点。一个词和下一个词之间，有一条有向边。

广阔的图数据世界

除了上述列出的两种数据可以表示为图，还有很多别的数据可以表示为图。

分子表示为图

把每一个原子作为一个顶点，而分子间的共价键作为边。

社交网络

社交网络是研究个人、机构和组织集体行为模式的工具。我们可以构建一个图来表示人群，将个体建模为节点，将个体之间的关系建模为边。

引用网络图

科学家在发表论文时经常引用其他科学家的工作。我们可以将这些引用网络可视化为一个图，其中每篇论文都是一个节点，每个有向边是一篇论文与另一篇论文之间的引用。

图结构化适用的问题

图级别任务

在图级别任务中，我们的目标是预测整个图的属性。例如，对于一个用图表示的分子，我们可能想要预测该分子的气味，或者它是否会与某种疾病相关的受体结合。

这是一个简单的图分类，按照图中环的数量进行分类

顶点层面的任务

顶点级任务关注的是预测图中每个节点的身份或角色。

在训练道场的两个老师决裂了，所有的学生必须要选择一个老师进行跟随。

通过学生和老师之间的比赛图，判断学生会跟随老师A还是老师B

边级别上的任务

边级问题是指以图中两个节点之间的关系或连接为研究对象的预测任务。

给出一个确定的图，来预测边上的属性。

机器学习运用在图上的挑战

如何将图表示为与神经网络兼容的格式

在图中，我们需要利用四种类型的信息来进行预测：节点(Nodes)、边(Edges)、全局上下文(Global-context)和连通性(Connectivity)。

前三者相对容易处理：例如，对于节点，我们可以给每个节点分配一个索引$i$，并将节点$i$的特征存储在矩阵$N$中，从而形成节点特征矩阵$N$。尽管这些矩阵的样本数量是可变的，但它们不需要特殊技术即可直接处理。

而图的连接性要复杂的多：

1. 空间效率低下(稀疏性问题)

   最显而易见的选择是使用 邻接矩阵（Adjacency Matrix） ，因为它易于张量化（Tensorisable）。但这种表示方法存在明显的弊端。稀疏矩阵不利于在GPU上计算，在GPU上计算稀疏矩阵一直是一个比较难的技术问题。

2. 置换不变性挑战

   另一个问题是， 同一种连通结构可以由多种不同的邻接矩阵来编码 。我们无法保证深度神经网络对这些不同的矩阵输入能产生相同的结果（也就是说，它们不具备置换不变性）。

   学习“置换不变操作”是近年来的研究热点。

   

随意的交换邻接矩阵的行和列，都不会影响图的含义。

标准的表示形式

在该图中，顶点和边的属性都适用标量来表示，也可以使用向量。

• Adjacency Lsit：邻接列表
  • 邻接列表长度与图的边数相等
  • 它的第$i$项表示第$i$条边连接的哪两个节点

该表示方法的优势：

• 存储高效
• 顺序无关

Graph Neural Networks