从图网络表示到图神经网络

人工智能的不同算法围绕不同数据结构展开。数据的本质是一大串互相联系的数字。最简单的情况下， 这串数字是一些只有上下左右相连的，我们称之为像素， 这就是图像。如果数字和数字之间是单向的连接， 而且这个箭头有着单一的指向，那么这个数据类型就是时间序列。而在更一般的情况下， 数字和数字之间，是一个互相联系的复杂网络， 这时候我们用节点和连接它们的边来描述这种数据类型， 这就是我们说的图网络结构。

对于图像CNN是目前深度学习的集大成者， 对于时间序列RNN， transformer是集大成者， 那么对于图结构呢？这就是当下的图神经网络崛起的背景。而事实上， 关于图的研究， 远早于图神经网络已有之， 这个系列， 通过被称为graph embding， 也就是把网络的拓扑结构和节点本质， 通过一定方法压缩到一个向量表示里(正如通过CNN和RNN我们可以得到图像或时间序列的向量表示)。我们在这里展望下都有这个历史门派：

首先， 为什么要研究图网络， 是因为这和machine learning的核心使命， 预测与决策，息息相关。我们有时候要预测同在一个社会网络里的张三和李四是什么关系， 有时候要预测在不同的网络结构 趋向于图中的 A或B， 哪一个是manager， 哪一个是worker， 或者某个网络区域哪一个处在CBD， 哪一个是贫民窟。 根据不同的目标， 我们需要对图进行embedding的方法就不一样。

1 基于图的embedding

那么我们就一步步检测不同的embedding方法的需求是什么。

首先， 如何表示一张图， 图包含节点和连接的信息， 我们用两个矩阵， A和X来表达相邻连接和节点的信息。

然后，我们来看用机器学习研究网络问题的核心方法， 也就是如何把网络核心的信息压缩到机器学习模型里。而你除了A和X不知道网络的任何信息。你可以怎么做呢？

首先这个网络核心信息可以是什么呢？网络由无数同质或异质的节点构成， 而每个节点间均有可能根据一定概率有连接， 在一个社交网络里， 每个个体的位置均由其连接决定， 犹如我们说的一个人的本质是由其社会关系决定的。而如果我们关注连接本身， 我们又会看到网络往往被分成无数子区域。根据我们要研究的问题不同， 这些网络属性均可以被机器学习模型表达 。

如果你了解传统的机器学习， 你一定会知道一个词叫特征工程， 传统机器学习利用特征工程把图像里的信息预处理出来， 比如各种滤镜。而类似的， 在对图结构处理时候， 也有类似方法。

在 表征 学习（深度学习）兴起后， 我们不再依赖特征工程处理图像， 而是让机器自己学习 该 如何提取特征。 类似的， 对于图结构， 在我们有相应的表示学习方法。

基于漫步的图嵌入方法

何为embedding? 所谓嵌入， 就是把一个东西映射到一个低维向量表示里。对于图网络， 嵌入就是把节点和边的信息一起压缩到一个张量， 同时从这里面可以解码边的信息或者节点的信息。

这个解码过程， 本质是最小化重构误差。这个重构误差， 通常体现在压缩后的节点信息， 要尽量保持原先的距离， 通常用向量积来表达。

z 是对v 编码后的结果， 而Dec 代表解码， 这个loss就包含了这个编码和解码的过程。注意这个过程用到监督学习，而监督学习的label样本就是节点和节点的距离。那么如何衡量两个node的距离呢？这个可以由训练者根据目标而定。一种最简单的想法是距离就是连接矩阵本身， 两个节点有连接就是1， 没有就是0， 而另一种想法是，距离是从某个节点A出发，有多么容易到达B 。我们通常用随机游走采样的方法巧妙的寻找这个量， 也就是让一个爬虫从某个节点随机游走一下， 然后看它n步之后到达另一个节点的概率，用以衡量不同节点的距离。任意节点到任意节点的距离构成一个矩阵。

有了label具体到方法层面， 这个编码的方法又可以分为矩阵的分解和deepwalk两大类。

对于matrix factorisation，我们需要直接把这个节点和节点间的距离矩阵分解为因子相乘的形式， 而其中一个相乘的因子矩阵就可以成为节点的向量表达（联想协同过滤）。然后我们可以根据向量点积的大小比较节点的相似度， 背后的画面是， 两个因子越相近， 点积就越接近1， 而这个时候两个节点间相互连接的概率也越大。

而另一个方法deepwalk， 则再次用到了随机游走的思想， 一个agent在图上随机游走，如果把它所经历的节点看成一个序列比如AABA, 这个过程就好像是一个醉汉随机的说出了很多疯言疯语， 而我们把这些语言给保存下来，的确可以用它洞悉语言本身的结构。这个 洞察 的过程， 就类似于word2vec的计算过程。 我们从这些序列里掩盖住一些节点信息， 然后让神经网络去预测这些确实的节点。 最终我们将得到关于每个节点的神经编码， 两个节点间的神经编码做点积算一下距离， 就反应了从一个节点到另一个节点的迁移概率。

graph embdding 又分为浅度和深度的区别 ，而更深层次的还有对整个子网络的embedding。

这些不同的embedding ， 本质上是以不同的计算代价， 将图的拓扑结构的有用信息映射到embedding的向量里。

比如我们可以直接用神经网络的思想， 将图上的信息通过一个图连接矩阵和神经网络的连接矩阵的双重作用， 迭代成为一个 信息 的表征，如此重复数次， 直到节点的数值收敛。 整个过程与RNN的本质有着深刻的联系。

Representation Learning on Graphs: Methods and Applications， William L. Hamilton

基于传播的图嵌入算法

事实上之前介绍的方法都与某种图结构上的随机游走相关，而方法也比较“浅” 。对比机器学习到深度学习， 有没有一个方法， 能够提高这种在图上的“漫步” 的效率，就像CNN处理图象那样并行高效的进行呢？

这种方法再次借鉴了算子的概念，其实复杂网络的本质就是信息传播， 所谓从每个节点向周围节点发送消息（broadcast）， 这个流程的思想又称为neibourhood aggregation。

它的根本思想是传播和迭代， 利用传播算子进行多次信息的整合。

整个流程如图所示：

Representation Learning on Graphs: Methods and Applications， William L. Hamilton

假定最初每个节点上的值均为0， 然后我们给定一个输入x作为每个节点的初始值。然后， 我们开始进行一轮信息的aggregation。在这个过程里， 每个节点会根据一个可微分的aggregation函数向邻居节点发射信息， 最终得到一个被更新的节点信息， 这个信息和之前的旧的节点信息整合 在 一起， 被一个全连接矩阵W处理，这样得到最后的下一轮节点信息。 虽然每一轮的信息整合是根据临近节点， 但是若干 轮 后， 每个节点embedding的信息将包含整个图结构的拓扑和节点信息。 事实上这个过程神似循环神经网络里的LSTM，经过若干时间步， 网络节点的信息是包含了整个动态过程的历史。

图网络 ：

事实上上面的aggregation算法离图网络就是一步之遥。我们把节点间信息互相传播的函数用神经网络来表达， 就直接得到图网络的概念。这里的h代表一个非线性的函数， xi 和 xj 是节点的信息表达， 然后h是网络结合了节点和连接信息的隐状态， 通过多次迭代， 可以生成图网络的最终表示， 然后我们可以再加一个softmax函数预测我们所需要知道的节点和边信息。

这种方法有很多特化， 比如我们可以直接用 gated recurrent network 来代表h。

2 GCN 图卷积网络

一种更有效的处理图神经网络的方法就是图卷积网络。

刚刚说的图神经网络的核心在于可以学习的传播算子。那么在物理里， 什么才是最自然的传播算子呢？我们称之为拉普拉斯算子。在数学上， 它的表示如下 ：

拉普拉斯算子的物理含义非常明显， 它就是有一个物质产生的源头，有一个外周区域， 物质从源头向外周区域扩散， 就形成一个传播的过程。形象的看如下图。

把它和一个时间过程合并起来， 我们得到扩散方程。

好了， 那么我们如何把这种智慧转移到图网络上呢？事实上我们要的是一个图网络上的扩散方程， 我们不难看出这和之前基于随机游走方法的联系， 因为扩散方程的本质可以看成大量物质在随机游走时候自发出现的从高浓度向低浓度的趋势。而使用扩散方程， 我们仿佛拥有了无数这样的漫步者帮我们探索网络空间 。

由于图网络是由连接矩阵和节点描述的， 数学上如果要把扩散过程推倒到这种数据结构里， 我们要借助的就是谱方法。所谓谱，其实就是求矩阵的特征值和特征向量， 然后把它们进行特征分解。也就是求那个三角形的拉普拉斯算子在图网络结构对应的特征向量。推倒相当复杂再此不述。我们来看最终结果的形式， 这个算子非常对称， 中间是连接矩阵A， 两边是度矩阵的开方的倒数。事实上它描述这样一个数学过程， 一些物质从中心节点出发， 沿着度矩阵A达到邻居节点， 这个时候邻居节点会有一个增量产生， 而中心节点则要减去传播出去的物质， 这个减掉的物质的量就是由度矩阵D描述的。这种一增一减的过程在物理对应质量守恒， 而在AI领域，就是normalization

那么何为卷积呢？首先此处的扩散是最简单的一种也就是说对应一般的扩散（identity matrix 对应随机游走）， 而如果要让这个过程变得更高效， 我们就可以让它按照一种特殊的方式扩散， 这在图像识别上就对应滤波，我们通过设定滤波函数， 就可以让图片变得更锐利或更模糊。这个一般的表达，就是在连接矩阵边上在右乘一个一般形式的W。更进一步的， 这个W是可以学习的。我们最终得到GCN的一般表达式：

此处的H是节点特征， 我们看到经过这个可以学习的扩散算子， 再加上一个非线性的sigma函数， 节点特征就被迭代了一轮， 而经过若干 轮 迭代， 就可以得到整合了整个网络信息的节点表示。 类似于图像卷积的， 图卷积网络也可以并行使用不同的滤镜抽取不同的特征， 好比并行的进行很多这种可学习的扩散过程， 是不是比最初的随机游走学习模式高出很多？

图卷积网络的效率之强体现在经过若干次迭代就可以得到一个网络的有效表示， 比如下图的社区网络图：

经过两三轮迭代， 我们把得到的节点表示投影到二维空间， 我们看到， 此时的数据聚类已经和真实的社区表示差不多了：

3 有关图网络学习的更多问题展望：

1， 图网络学习都是已知连接矩阵A， 如果不知道连接矩阵A呢？比如在城市电网或互联网这种非常巨大的难以测量的自发形成的复杂网络里， 上述方法是否依然奏效？

2， 这种方法更多适合于同构图， 也就是节点信息相似的这种图，而如果在图网络结构里节点信息差距巨大不可忽略（异构图）这类方法是否还如此高效， 是否存在更好的方法？

3， 图网络对边的理解依然局限于拓扑的关系， 而如果这些边含有了复杂世界的因果关系呢？是否网络可以学习？

4， 图网络方法目前更多局限于静态的图， 而显示世界的图更多是动态的， 变化的。那么如果有一个机器学习模型可以不停的适应这种动态变化的图， 需要什么样的表示？

5， 说到底， 图网络结构是产生在我们的大脑里。当婴儿探索世界的时候， 他的大脑里没有图的概念， 而是片段的序列信息， 那么这个图的结构是如何从这种片段序列信息里面整合出来的， 这个过程是怎么通过大脑神经网络构建起来的？

这些问题都值得进一步探讨。

涉及的相关论文或博客

1 Hamilton, William L., Rex Ying, and Jure Leskovec. "Representation learning on graphs: Methods and applications." arXiv preprint arXiv:1709.05584 (2017).

2 GRAPH CONVOLUTIONAL NETWORKS, THOMAS KIPF

3 Spectral Graph Convolution Explained and Implemented Step By Step,Boris Knyazev

更多阅读

巡洋舰人工智能资源打开手册

人工智能在电网管理中的应用