圖注：網絡傳播圖解
作者 | 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