Jure Leskovec的《Graph Representation Learning》可能是迄今（2019年10月）为止最容易理解的图神经网络分享。它提出并回答了为什么要进行图表示，如何进行图表示等一系列根本性问题，而图神经网络仅仅是图表示学习的高阶版本。

这里我就复刻一下Leskovec的素材及思路，再增加一些解读及实现细节，汇成一个系列教程。

目录
为什么要研究图（graph）
针对图结构的机器学习任务
特征表示的难点
特征表示的解决思路
讨论：何谓Embedding
总结
参考文献

为什么要研究图（graph）

很多数据都是图结构，例如社交网络、经济网络、生物医学网络、信息网络（互联网网站、学术引用）、互联网、神经网络。而网络是它们的通用语言，因此具备极大的研究价值。

1im1.png

​ 图1.图结构的举例（source）

针对图结构的机器学习任务

一旦我们拥有了图结构的数据，就可以做一下潜在的机器学习任务，例如：

• 节点分类 ——预测一个给定节点的类型
• 链接预测 ——预测两个节点是否连接
• 社群检测 ——识别密集连接的节点群
• 网络相似度 ——两个子网络有多相似

等等。

然而，正如我们所熟知的，机器学习任务的基本流程如下所示：

1im2.png

​ 图2.机器学习任务的基本流程（source）

可见，第一步的特征工程即需要把每条样本表示为向量，即特征向量。不论输入是非数值类型（图片、语音、文字、逻辑表示等），或者本身就是数值类型，我们都需要将输入数字化为特征向量。

而且，因为特征工程决定着算法上限。所以我们不仅要转为特征向量，而且希望转成的特征向量也足够好。因此，基于自动编码器（Auto-encoder）和词嵌入（Word-Embedding）的启发，我们期望转换后的特征向量（或者叫Embedding），能够自带节点信息（例如在特征空间上，相似的节点会离得特别近），这将非常有利于机器学习的任务。

那么，如何把网络中的节点转化为特征向量？

1im3.png

​ 图3.节点需要映射为特征向量（source）

特征表示的难点

不幸的是，这非常难。

我们可以考察一下常见的非数值类型的输入，是如何转换的。

• 图片（images）

  有固定的2维结构，可以定义CNN。

1im4.png

​ 图4.图片（image）拥有固定的2维结构（source）

• 文本（text）、语音（speech）

  都有固定的线性1维结构，可以定义滑动窗口。

1im5.png

​ 图5.文本、语音拥有固定的1维结构（source）

然而，图（graph）是非欧几里得结构。表现在：

• 图的结构可以任意变化

  一个图可以具备各种形状，尽管它们的节点位置不一样，但是连接关系没变，所以图完全一样。

• 节点也可以以任意顺序标记

  同样一个5个节点的图，节点可以标记为1、2、3、4、5，也可以标记为4、2、1、3、5，节点编号变了，尽管图完全没变。

特征表示的解决思路

怎么办？

他山之石，可以攻玉，基于上面我们对一维序列结构和二维图（image）结构的处理方法的总结，至少可以启发出以下两类套路：

线性化思路

通过图（graph）结构里的遍历，生成节点的序列，来创造“句子”语料，然后再使用Word2Vec的思想。如 Node2Vec。

常见的线性化方法如下所示。

1im6.png

​ 图6.线性化常见做法（source）

图神经网络

用周围节点来编码中心节点，相当于通过训练一个虚拟网络（Network），把每个节点周围的结构信息储存在了这个虚拟网络（Network）里，而输入周围节点后这个网络输出的向量，正是这个中心节点的embedding。

常见的图神经网络如下所示，后面章节将详细讨论，拨开它的神秘面纱。

1im7.png

​ 图7.图神经网络常见做法（source）

讨论：何谓Embedding

2013年Word2Vec（尽管Word2Vec的idea诞生多年，但直到2013年才因为训练技巧的加持而得以解除封印）显著效果兴起了一股风潮：即根据环境上下文的固有结构，用每个元素与上下文的元素之间构造“feature-target”这样的训练数据，自动化地训练浅层神经网络（一般只有一个隐层，一个输出层）。

狭义

某个元素狭义的Embedding即该元素传播到隐藏层计算出的向量。基于一个训练好的浅层网络，每个元素都可以由自己的one-hot表示传播到隐层后，抽出隐层向量作为自己的Embedding。

正是因为这个特征向量是“嵌入”在网络中间的隐层，所以叫嵌入（即Embedding）。

由于相似的元素的Embedding也相似，所以是非常理想的特征表示法。（作为对比，元素也可one-hot，但one-hot向量除了表征元素间的差异，完全没有其他信息，极大限制了机器学习模型的发挥）

广义

一个样本的特征向量，不管它是否来自一个训练的网络，或是来自其他方法的构造，我们都可称之为Embedding。因为我们的最终目标是迭代出最优的特征向量，蕴含相似度信息，所以我们把这种特征向量也称之为Embedding。这是本文所使用的Embedding意义。

总结

• 用图结构数据进行机器学习具有巨大价值，然而抽取特征却是图结构数据的难点。
• 受图像（image）、文本（text）的特征抽取的启发，产生两大类思路。

本文举例是按节点，也可以是边，甚至是子图，根据具体的机器学习任务而定。

参考文献

[1] Jure Leskovec, 《Graph Representation Learning》

[2] Jure Leskovec, 《Representation Learning on Networks》 http://snap.stanford.edu/proj/embeddings-www/