图注：网络传播图解
作者 | Remy Lau
编译 | 琰琰
我们知道，图卷积（graph convolution ）是AI算法中主流的网络学习方法，而网络传播（network propagation）是计算生物学中的主流方法，那么，二者有何密切联系和区别？在这篇文章中，作者通过深入研究网络传播背后的理论机制，发现网络传播其实是图卷积的一个特例。
本文要点：
- 网络传播是计算生物学中基于GBA原理的一种主流方法。
- 网络传播方式的两种不同观点：随机游走（random walk）与扩散（ diffusion），后者以HotNet2为例进行了介绍。
- 网络传播是图卷积的特例。
1
计算生物学中的网络传播
网络来源于现实世界的大量数据，比如社交网络、交通网络、生物网络等等。网络结构蕴含了网络中每个独立个体的丰富信息。
在蛋白质交互（PPI）网络中，节点表示蛋白质，边缘表示两种蛋白质相互作用的可能性。计算生物学中已经证明，这种网络结构在生物重建过程中非常有用，甚至可能揭示疾病基因。
重建过程主要是通过直接观察目标蛋白的相邻蛋白质是否是生物疾病的一部分。这种通过邻近蛋白质推断蛋白质性质的过程称为“网络传播”。在下一节中，我们将着重介绍实现网络传播背后的数学公式，但在此之前，我们要思考一个问题：为什么这样一个简单的方法是有效的？
图注：酵母PPI中的蛋白质复合物
这要归结于关联内疚（Guilt By Association ，GBA）原则，它表示通过物理相互作用或基因共表达等其他相似性度量，相邻或密切相关的蛋白质很可能参与相同的生物过程或路径。
GBA原则源于研究人员观察到许多蛋白质复合物（例如酵母中的SAGA/TFIID复合物）会出现在内聚网络模块中。类似地，在人类疾病基因网络中，我们可以看到，与耳、鼻、喉疾病或血液学疾病相关的疾病基因出现在网络模块中。
注意：在这篇文章中，蛋白质和基因这两个词可以互换使用。
图注：人类疾病基因网络
2
网络传播的数学表述：两种不同的观点
符号（Notations）
给定一个图 G=（V，E，w），其中V由n个顶点组成，E代表边集，w代表权重函数。设A是相应的n-n维相邻矩阵，如下图：
利用对角度矩阵D（其对角项是对应节点的度），我们可以在行或列两个方向上对一个矩阵进行规范化，并得到两个新矩阵P和W。
p0代表一个独热码标签（one-hot encoded label）向量，其中p0对应正标签节点时为1，其它为0。
观点 1：随机游走
在网络上，我们可以通过随机游走（random walk）的方式进行网络传播，但在这种情况，我们要解决一个关键问题：
通过1-hop传播，从目标节点开始最终到达任何一个正标签节点的概率是多少？
在数学上，此操作对应于P和p0之间的矩阵向量相乘，从而产生预测得分向量y
我们先来看一个例子，在由基因g1、g2、g3和g4构成的子网络中，假设g2和g3被标记为一种疾病，g1和g4没有被标注为这种疾病（注意：这并不意味着它们对该疾病没有影响，而是目前还不知道它们与该疾病有关）。
图注：随机游走网络传播实例
为了确定g1是否与疾病有关，我们可以设计一个从g1开始的1-hop随机游走，看看它落在疾病基因（g2或g3）上的概率有多大。经过计算，最终预测得分为2/3，这个分数是相当高的。这在一定程度上验证了GBA原理，因为g1的三个相邻基因中有两个与该病有关，根据GBA原理，g1很可能与该病有关。
观点 2：扩散
网络传播的另一种观点是通过网络进行扩散。在这里我们要提出的关键问题是：
有多少“热量”被扩散到目标节点？或者换言之，从带有正标签的节点开始，通过1-hop传播到达目标节点的概率是多少？
在数学上，此操作对应于P和p0~之间的矩阵向量相乘，产生预测得分向量y~。
注：p0的标准化确保了从概率分布到概率分布的映射，即y~的总和为1。
现在回到上面通过网络传播预测疾病基因的例子。这一次，我们要执行标签传播作为扩散。由于两个标注的疾病基因产生的大部分（5/12）总“热量”由g1收集，因此g1极有可能与该疾病有关。
图注：基于扩散的网络传播
不止1-hop传播
1-hop传播的方法是简单有效的。然而，当标记数据较少时（这种情况在计算生物学中经常出现），1-hop传播方法只能计算与疾病基因直接相邻的基因的预测分数。鉴于人类基因组中有2万多个基因，这显然导致了次优预测。因此，我们可以扩展到2-hop，3-hop，甚至更多......而不是局限于1-hop。下图说明了从k=1到k=2的k-hop传播。
图注：multi-hop 传播
HotNet2扩散
有许多不同的变体来执行多跳扩散或随机游走。在这里，我们介绍一个具体的例子HotNet2。与上面介绍的扩散类似，HotNet2算法迭代更新初始“热量”分布，如下所示：
其中，β值从0到1代表将“热量”带回其源头的“重启概率”。关于“重启概率”有以下几点原因：首先，扩散算子的先前定义给出了当前节点具有的所有“热量”，而在步骤t时，所有先前的扩散信息丢失，β在每个步骤中有效地保留了一些热量。因此在步骤t中，分布包含了前面步骤中的所有信息。其次，β参数保证了t趋于无穷大时热分布的收敛性，从而给出了t处热分布的闭式解（ closed-form solution）
最后，相关研究已经证明，与1-hop网络传播相比，这种HotNet2扩散方法在生物路径重建、疾病基因预测等方面可以产生更精确的预测结果。
3
与图卷积的关系
图卷积网络遵循如下逐层传播的规则：
图注：GCN 传播
其中，H(l) 是第l层的隐藏特征，W(l)是可学习参数，非线性sigma(DAD) 中的前导部分是具有自连接（self-connections）的谱归一化邻接矩阵。自连接的作用类似于重启概率，用于保留当前迭代的一些信息。
通过以下替换，我们可以将标签传播完全重构为图卷积的特例。
- 用行规范化（P）或列规范化（W）的形式替换谱规范化的自连接邻接矩阵
- 用p（l）代替H（l）
- 用恒等式替换非线性和W（l）
请注意，第一次替换不会改变图形频谱，因此仍将执行相同的卷积运算，所以！网络传播成了图卷积的特例！
4
结论
由于细胞组织的模块化，网络传播在计算生物学中被广泛应用于疾病基因预测等各种任务。因此，基于GBA原理，我们深入研究了网络传播的两种观点及其与图卷积的关系。
原文链接：
https://towardsdatascience.com/network-learning-from-network-propagation-to-graph-convolution-eb3c62d09de8
