本文內容來自將門機器學習主題社群

論文作者: Simon S. Du 編譯:T.R

本文為將門好聲音第25 期，也是NeurlPS 2019系列分享第·4·期。

論文作者之一是來自將門機器學習主題社群、普林斯頓高等研究院博士後杜少雷

如果你也想與廣大群友分享自己的研究工作、文章觀點、出坑經驗，點擊“閱讀原文”

雖然圖內核 (graph kernel，GK) 易於訓練並享有可證明的理論保證，但其實際性能受其表達能力的限制，因為內核函數往往依賴於圖的手工組合特性。與圖內核相比，圖神經網絡通常具有更好的實用性能，因為圖神經網絡使用多層結構和非線性激活函數來提取圖的高階信息作為特徵。

然而，由於訓練過程中存在大量的超參數，且訓練過程具有非凸性，使得GNN的訓練更加困難。GNN的理論保障也沒有得到很好的理解。此外，GNN的表達能力隨參數的數量而變化，在計算資源有限的情況下，很難充分利用 GNN的表達能力。

本文提出了一類新的圖內核，即圖神經切線核 (GNTKs)，它對應於通過梯度下降訓練的無限寬的多層 GNN。GNTK充分發揮了GNN的表現力，繼承了GK的優勢。從理論上講，我們展示了GNTK可以在圖上學習一類平滑函數。根據經驗，我們在圖分類數據集上測試GNTK並展示它們實現了強大的性能。

從社交網絡到生物網絡，大量的圖結構數據不斷出現。為了從圖數據中進行學習，需要我們設計有效的方法來探索圖結構。目前用於圖數據學習最主要的兩類方法分別是圖核函數(Graph Kernels,GK)和圖神經網絡(Graph Neural Networks, GNNs)的方法。對於GK方法來說，無論是顯式還是隱式的方法都基於輸入圖的組合特性建立起特徵向量。GK方法具有核函數方法的所有優點，由於其對應著凸優化問題使得基於圖核函數的方法便於訓練。此外核函數方法具有精確的表達，可以利用理論工具進行詳盡的分析和驗證。但圖核函數方法卻受限於其手工特徵的表達能力，對於涉及節點間複雜相互作用的高維特徵捕捉能力還存在很多不足。

而隨著卷積神經網絡的發展，使用多層卷積結構進行局域信息聚合的圖神經網絡方法，無需精確的人工特徵就能從圖中抽取出有效的特徵。其對圖數據的高維特徵抽取能力比核函數方法更為強大，在眾多基於圖結構數據的任務上取得了優異的結果。然而，由於圖卷積網絡的目標函數是非凸的，需要仔細地調節超參數來穩定訓練過程。同時，訓練過程的非凸性質使得任務無法直接分析圖網絡的學習結果，限制了我們對於GNN的理解。此外，GNN的表達能力與參數量直接相關，在計算資源受限的情況下我們很難學習到一個具有強大特徵學習抽取能力的圖神經網絡模型。

核方法和神經網絡方法都各有優勢，那麼能不能通過優勢互補創造出一種既容易訓練又容易解釋並具有強大表達能力的模型呢？

來自普林斯頓高研院、浙江大學、CMU 和MIT的研究人員們在近年研究的啟發下，提出了一種新的圖核函數——圖神經切線核函數(Graph Neural Tangent Kernels, GNTKs)。這種方法等價於利用梯度下降法訓練具有無限寬度的GNNs，其中tangent(切線)的命名主要來源於其訓練方法—梯度下降法。雖然GNTKs是從無限寬的GNN推導而來，但在預測時GNTK僅僅依賴於圖之間的成對的核函數值，可以通過解析式進行高效的計算。這使得GNTK方法同時具有了GNN的強大表達能力和GK核函數容易訓練和分析的優勢。

圖神經網絡

首先我們要回顧一下圖神經網絡GNN，這是一種對於圖數據十分強大的學習框架，它通過多層網絡對相鄰節點表達的轉移與融合來實現局域特徵聚合，隨後通過池化方式得到整個圖結構額表達。基於聚合與池化方式的不同，人們提出了各種各樣的圖神經網絡結構。但在這篇文章中，作者首先將鄰域的聚合過程定義為BLOCK操作，隨後將整個圖數據上的池化定義為READOUT操作。

BLOCK操作主要用於從鄰域中進行特徵聚合，可以使用相加、多層感知機等方式進行非線性聚合、或者利用全連接層和ReLU來實現。在GNN中BLOCK操作等價於圖卷積操作，其主要目的在於對鄰域特徵進行抽取表達，基於網絡層對特徵進行傳遞和聚合。

READOUT操作的目的在於從整個圖的特徵中得到完整圖表示，既可以通過將所有節點的特徵進行疊加，也可以通過更為複雜的方式來得到圖特徵，例如將不同層的特徵進行聚合獲取完整的圖全局特徵。

在BLOCK和READOUT的基礎上，人們就可以構建GNN了。可以通過L個Block操作得到特徵，而後通過READOUT操作得到全局圖特徵。

GNTK

在理解圖神經切線核函數之前需要首先明確神經切線核函數的概念。先前的研究已經證明，人工神經網絡在無窮寬度極限在可以等價為高斯過程，這就將核方法和神經網絡方法銜接了起來。在這樣的情況下，網絡的訓練過程可以用核函數來描述：網絡的參數通過梯度下降法進行更新的時候，網絡代表的映射f(θ)更新方向將會沿著函數損失的核函數梯度，從而可以引出一個新的核函數方法：神經切線核函數(Neural Tangent Kernel, NTK)。

下面我們可以從數學上來進一步理解，首先對通用的網絡模型f(θ,x) 定義損失函數：

但學習率足夠小時，利用參數方程將f(θ(t),x)表達為u(t) 作為網絡的輸出，此時u滿足下面的表達式：

H代表切向核

近年來神經網絡的相關研究顯示，足夠過參數化的網絡中H可以在訓練過程中基本保持不變。此外在參數隨機初始化的情況下，隨機矩陣H(0) 將會以一定概率收斂到確定性的核函數矩陣上，而這一核函數就稱為NTK，其對應著無限寬的神經網絡。

在先前關於神經切線核的啟發下，研究人員將這套理論應用於圖結構數據中，其中f(θ,G)代表了圖神經網絡，在兩個圖數據輸入的情況下需要計算其對應的GNTK值。首先需要計算下式的取值:

但網絡的輸出維度m趨向於無窮時並且θ都是高斯隨機變量，其可以被視為高斯過程。對於GNN中的每一層，可以使用Σ來表示輸出的協方差，Σ來表示對應層協方差的偏導。由於GNN具有多層結構，這些協方差矩陣可以通過動態規劃來進行計算。

在此基礎上，我們針對兩個圖數據輸入G,G’和一個包含L個BLOCK操作，每個操作包含R層全連接和ReLU激活函數的GNN。可以計算出逐對核函數值Θ(G,G′)的GNTK公式。下面的公式分別展示了進行鄰域聚類操作和通過R個全連接層進行轉移操作的協方差和中間核函數值的計算公式。

進行鄰域聚類操作

通過R個全連接層進行轉移操作的協方差和中間核函數值

在利用BLOCK得到中間輸出後，就可以利用下面的公式來得到GNTK的最終結果：

注:如果需要詳細理解推導過程，請參看原文及參考文獻

https://arxiv.org/abs/1905.13192

理論優勢和實驗結果

這種方法對於GNN具有很好的泛化性，下圖顯示瞭如何將GNN轉化為GNTK的方法。其中對應的特徵聚合過程和非線性操作可以通過協方差和核函數值函數進行計算。

同時在這一理論框架下，我們不僅通過分析得到計算過程中的一些解析表達式和取值上界，同時也能從理論上GNTK可以通過多項式樣本學習到圖上的平滑函數。這使得GNTK不僅保留了神經網絡的強大表達能力，同時也具有核函數方法的高效計算訓練特性以及有效的理論支撐。

最後研究人員在圖數據分類任務上對這一新方法進行了實驗。分別在四個生物信息數據三個社交網絡數據集上與常見了GK和GNN方法進行了比較，結果與下圖所示：

實驗顯示在多個數據集上融合GK和GNN的GNTK方法都取得了良好的效果，並在四個數據集上超過了先前的方法。此外在相同架構的情況下，GNTK方法比GNN具有更高的計算效率。

研究人員還對GNTK中的參數進行了研究，下圖展示了兩個數據集上的測試結果隨BLOCK操作中的尺度因子的變化情況。研究人員發現在生物數據上擁有更多層數的GNTK具有更好的表現，針對社交網絡數據加法聚合比平均聚合的效果更好。

最後研究人員還分析了 jumping knowledge network (JK) 對結果的影響。實驗顯示JK與GNN中的結果類似，可以提高網絡的性能。同時增加MLP的層數也能夠提升模型的表現。

GNTK通過結合圖核函數GK和圖卷積GNN的優點，實現了更為有效的圖表示學習，如果想要了解更多的細節，請參看論文和詳細的代碼實現：

Paper:https://papers.nips.cc/paper/8809-graph-neural-tangent-kernel-fusing-graph-neural-networks-with-graph-kernels.pdf

Code:https://github.com/KangchengHou/gntk/blob/master/gntk.py

將門好聲音·NeurlPS系列

ref：

http://simonshaoleidu.com/

https://github.com/KangchengHou/gntk/blob/master/gntk.py

https://papers.nips.cc/paper/8809-graph-neural-tangent-kernel-fusing-graph-neural-networks-with-graph-kernels

組合圖論：http://math.xmu.edu.cn/html/xwgl/xydongtai/5070.html

Weisfeiler-Lehman(WL)算法：

https://zhuanlan.zhihu.com/p/90645716

https://www.slideshare.net/pratikshukla11/graph-kernelpdf

over-paramters:https://www.jiqizhixin.com/articles/2019-06-25-18

Neural Tangent Kernel：https://arxiv.org/pdf/1806.07572.pdf

關於我門

▼

將門是一家以專注於發掘、加速及投資技術驅動型創業公司的新型創投機構，旗下涵蓋

將門創新服務

將門技術社群

專注於幫助技術創新型的創業公司提供來自產、學、研、創領域的核心技術專家的技術分享和學習內容，使創新成為持續的核心競爭力。

專注於投資通過技術創新激活商業場景，實現商業價值的初創企業，關注技術領域包括

在近四年的時間裡，將門創投基金已經投資了包括量化派、碼隆科技、禾賽科技、寬拓科技、杉數科技、迪英加科技等數十傢俱有高成長潛力的技術型創業公司。

如果您是技術領域的初創企業，不僅想獲得投資，還希望獲得一系列持續性、有價值的投後服務，歡迎發送或者推薦項目給我“門”: bp@thejiangmen.com

閱讀更多 將門創投 的文章

關鍵字: 麻省理工學院 人工智能 社交網絡