摘要
本文是對兩位機器學習領軍人物的新作Graph Structure of Neural Networks的解析。該論文從神經網絡連接配接關系的視角重新定義了一種圖結構來表達神經網絡模型，并從圖結構本身的屬性來分析什麼樣的神經網絡模型會具有好的預測性能。
本研究由相關領域的頂尖學者發起，并非傳統意義的DNN新方法研究，而是探索了神經網絡性能分析的新的方向。幾位作者開創性的提出用圖結構(graph structure)而非計算結構(computation structure)來分析神經網絡的性能。這項工作可以說是開拓了一個新的研究方向，可能會對DNN的設計、結構優化與提升性能帶來一些全新的思路。它對于DNN結構探索、自動DNN建構等工作也将會起到促進作用。
我們從這項研究本身的内容和所涉及的相關圖理論背景進行了深入了解。因篇幅較長，将介紹分為兩部分：(1)對文章内容的了解；(2)結合圖理論背景知識進一步了解文章的主要概念及重要意義。上一期我們介紹了第一部分，本篇是第二部分。
0 1概述
通過探索不同網絡結構及性能來得到最優的神經網絡模型是目前機器學習的重要探索方向。主流的思路是用大算力暴力探索不同網絡結構組合來達到目标。這對計算資源提出了巨大的挑戰。與這種基于經驗歸納的模式不同，推演模式以一定理論指導通過推導得到最優的模型設計，進而降低計算量的需求。比如，可以找到某種高性能神經網絡模型共有的特性，進而根據該特性來設計DNN模型。
“Graph Structure of Neural Networks”[1]從神經網絡圖結構的角度研究了這一問題。這是ICML2020收錄的一篇文章，由Kaiming He和Jure Leskovec等合作完成。作者提出了”關系圖”(relational graph)的概念來表達層間組合神經元的互動，進而系統性研究了神經網絡結構與性能的關系。如作者指出，文[1]最重要的貢獻是轉換研究思路，從神經網絡圖結構而不是計算架構來分析DNN。通過實驗驗證，他們認為對這一方法更廣泛深入的探索将促進DNN發展。
我們之前已經對文[1]進行了初步解讀。本篇嘗試結合圖理論的知識來深入了解文[1]的相關的概念及内容。
0 2關系圖(relational graph)
Graph Structure of Neural Networks一文定義了關系圖(relational graph)來描述神經網絡的圖結構特征。為避免混淆，下文中我們一般用“圖“來代表圖網絡，以區分神經”網絡“。關系圖中的每一個節點對應神經網絡兩層間的一對輸入與輸出通道/次元，多個節點代表多個通道，如圖1所示。節點間的邊表達了神經元對于其它對之間的資料輸入輸出雙向關系：消息交換(message exchange)。
圖1 關系圖[1]
圖1中關系圖對應的DNN寬度固定，每層輸入輸出次元不變時，關系圖所有節點均與其它節點連結，稱之為完全關系圖。
圖節點與神經網絡通道的一對多映射
需要注意的是關系圖中的節點與神經元并非一一對應。比如圖2的4節點關系圖對應65維MLP。其中三個節點對應16維通道(神經元)，另一節點對應剩餘17維通道。作者采用了一個簡單政策來劃分神經網絡層的節點。假定節點數為n,神經網絡層的次元為m，對于m mod n個數的節點配置設定[m/n]+1維，其餘節點配置設定[m/n]維。相信其它方案也适用于節點劃分。
按照上述操作，即使多層神經網絡的每層次元不同，關系圖節點數也是固定的。關系圖最大可選節點數由DNN模型最窄一層的次元來限制的。當然，由于一對多的映射，圖節點數可以小于DNN的最窄的次元。
圖2 多元神經網絡層與關系圖節點的對應[1]
0 3消息交換
關系圖的一個核心是節點間的消息交換。這個也是“relational”的由來。是以作者将由消息交換為邊特性的圖結構定義為關系圖。更具體的，消息交換有兩個函數組成：message function和aggregation function。Message function的輸入是節點特征，輸出是message，而aggregation function的輸入是一組messages，輸出為更新的節點。很顯然，這一概念與圖神經網絡(GNN)中的消息傳遞機制有類似之處。文[1]中，作者也認為可以把關系圖看作GNN的輸入。
一般地，message function是輸入節點的權積，聚合函數為組合消息的非線性變換，二者合并為消息聚合函數。若第r輪節點特征為
,對于第r+1輪的節點
的特征有：
其中，
是節點v的鄰域，即與其直接相連的節點的集合。
關系圖Round與 神經網絡layer的關系
關系圖的一次消息交換操作代表了NN模型中兩層之間的一次資料傳遞。是以，多層神經網絡并不表達為多層圖結構，而是由相同的一個關系圖來表達，層與層之間的一次資料傳遞是關系圖的一輪(round)消息傳遞。也就是說，多層神經網絡由一個關系圖，多輪資訊交換來表達。需要注意的是，盡管關系圖不變，但每個節點對應的次元及數量在不同的round是可以變化的。
神經網絡對應的圖節點消息函數
不同神經網絡結構的消息函數不同。對于MLP，其消息函數為：
如果關系圖的節點數目與DNN層的次元相同，則上述公式的xj為标量，是以消息函數與MLP單層更新公式一緻。但是如果類似圖2，一個節點代表多個次元，則公式中節點特征是一個代表多個神經元的向量。這種情況下，關系圖消息函數與DNN網絡層更新公式是有差別的。
卷積網絡與關系圖
很顯然，不同神經網絡的消息與聚合函數的定義有所不同。文中表1列出了幾種神經網絡(多層感覺器，Resnet等)的消息與聚合函數的定義。盡管原文沒有直接給出，參照上述定義，我們也可以構造出卷積網絡和關系圖的對應關系。具體例子如下。
對于CNN，卷積層輸入輸出次元分别分組後，每組為一個節點。輸入與上一層的輸出形成關系圖節點(r round節點)。其消息函數可以表達為：
其中，i，j分别代表輸入(r輪)輸出(r+1)輪節點的index。Wj是與輸入輸出對應的部分channel卷積核。
圖3卷積網與關系圖
以圖3為例，卷積核w為4x6x3x3的tensor，input層次元為4，output層次元為6。對應的關系圖有4個節點。節點0是輸入tensor第0通道與輸出tensor第0通道組成的消息對。圖中節點0的鄰域N是節點(1，2，3)，即包括卷積網絡所有輸入通道，是以其權重對應的是卷積核第0輸出通道，即w[0, :, : ,: ]。而對于節點4，其權重對應的是卷積核第4，5輸出通道，w[4:5, :, :, :]。
0 4圖的度量及圖的生成
作者在文[1]提出了産生滿足一定圖特性的神經網絡模型的方法。其中涉及到兩個圖理論中的概念：圖度量，圖生成。
4.1 圖度量
圖度量用來描述一個圖的特性。作者選取全局度量平均路徑長度(average path length)和局域度量聚合系數(clustering efficient)作為關系圖特性的度量。
平均路徑長度(L)：
兩個節點間的路徑長度是連通兩節點的最少邊數。Graph的平均路徑長度是網絡中任意節點間路徑長度的平均值。這是一個全局特征度量。
網絡聚合系數(C)：
一個節點的聚合系數定義為其鄰域節點間的實際邊數與所有可能邊數的比值。網絡的聚合系數則是所有節點聚合系數的均值。它描述了圖網絡的局部特征。
為什麼選取這兩個度量？一方面作者其實也對比了很多其它的度量，最後在正文中選取了這兩個度量。另一方面，本文所用到的圖網絡理論可以歸類到複雜網絡理論的一部分。而平均路徑長度與網絡聚合系數是複雜網絡理論中用來描述圖網絡特性的常用度量。
圖4 幾種神經網絡結構及對應的關系圖[1]
我們用圖4所列出的幾個簡單例子來直覺了解圖度量。
圖ａ的關系圖是節點間完全連接配接，所有節點兩兩相連C=L=1。
圖ｂ左邊的神經網絡對應的關系圖中, 每個節點的平均路徑長度均為(1＋1＋2)／3＝4/3，即整個網絡的Ｌ＝4/3。每個節點的聚合系數為2/3, 是以網絡的平均聚合系數C為2/3。
圖b右邊的神經網絡分為不連通的兩部分，關系圖表現為下對稱兩部分。每個節點聚合系數為1，而整個網絡C=1。記不相連節點長度為0,則單個節點的平均路徑長度為1/3,網絡的平均路徑長度為1/3。注意，如果将圖b右側關系圖中的消息函數用CNN的函數代替，則對應的神經網絡可以了解為類似group CNN的模型。
4.2 圖的生成
文章測試了6種圖生成器來産生滿足度量條件的關系圖，分别是ER，WS，BA, Haray，完全圖，環狀網格圖。其中前四種模型均是圖理論領域學者提出的。它們可以産生滿足某類網絡特性的圖生成模型。
完全圖是所有節點互聯的網絡，圖1(a)的關系圖即為一個完全圖。環狀網格圖是Watts-Strogatz(WS)模型的基礎，其結構類似圖5左側圖。
作者比較了這些生成器後，提出了改進的Watts-Strogatz(WS)-flex圖生成器。Watts-Strogatz模型是心理學家 DuncanJ. Watts和他的導師 StevenStrogatz 1998年在Nature上發表的一篇文章上提出的[2]。在這篇文章中他們提出了小世界網絡概念，用來解釋著名的小世界現象，即六度分隔：世界上任意兩個人從平均意義上都可以通過六個人聯系起來。他們提出小世界網絡是具有聚合系數高，而平均路徑長度短的特點的一種複雜網絡。他們同時提出了生成具有上述特點網絡的模型，即Watts-Strogatz模型，如圖5所示。
WS模型生成模型的大緻步驟是：
1 建構給定節點數目的規則圖。
2 以給定重連機率将節點的邊随機連接配接到其它節點。
圖5 環網格圖與小世界網絡[2]
文[1]提出的WS-flex模型則更進一步規定規則圖中所有節點的degree相同。這樣泛化了模型的生成能力，進而可以産生本文期望的關系網。如文[1]所述，WS-flex生成器有三個參數：節點數n，平均度數k，重連機率p，則要生成的網絡的邊數為e=[n*k/2]。生成器首先産生一個ring網絡，其每個節點連接配接e/n個鄰居節點。然後生成器随機選取e mod n 節點，并将每個選取的節點與最近的一個鄰接節點連接配接。最後以機率p對産生的網絡做随機重連。
用上述方法産生圖，并計算其聚集系數C和最短路徑L。作者發現WS-flex生成的關系圖能夠最大的覆寫C-L度量定義的空間。
0 5實驗結果的了解及思考
通過分析不同C-L組合的神經網絡，文[1]得到一個有趣的結論：在關系圖屬性位于sweet spot (C[0.10，0.50], L[1.82，2.75])的DNN模型預測性能好。相對于實驗設定的64節點網絡設定，這類網絡聚合系數較高，而平均路徑長度短。從前述網絡理論可知，這樣的網絡符合小世界網絡的特征。
有意思的是，作者還對比了貓腦和猴腦皮層神經。無論是度量上還是呈現的圖模式上，這些生物的神經結構都和基于關系圖的最優神經網絡類似 — 這再次驗證了早期學者對神經網絡在生物上的類比描述。
當然，sweet spot的結論僅适用于按照文中方式産生的DNN模型。作者實驗發現，如果不施加圖結構先驗，而是直接通過模型剪枝等方式優化得到的DNN模型，其圖結構與施加先驗的模型并不一緻。如圖6所示。
圖6 不同生成方式得到的最優神經網絡模型([1])
此外，原文關系圖以神經網絡的單層為機關來構造整個DNN網絡，要求每層都可以用相同的圖結構表達。這限制了對一般神經網絡更複雜結構的建構，比如具有hierarchical結構的深度神經網絡。
拓展思考
文[1]是一個開創性的工作，在提出新的思路及方法架構時，也留給我們許多可以深入探讨的地方，比如：
什麼是合适的圖度量
作者嘗試了多種圖度量來表達關系圖結構。如前文介紹，作者在正文中以平均路徑長度和聚合系數為名額來指導關系圖及神經網絡性能，同時也列出了其它圖度量下神經網路的性能變化。盡管大緻趨勢類似，但各度量下的神經網絡性能分布還是有所不同。
平均路徑長度和聚合系數是圖理論中常用的兩個度量。但這種經驗性的選擇是否适合神經網絡的性能表達？是否存在更合适的圖度量組合，甚至可以從理論上證明？這些相關問題或許是下一步研究可以探讨的地方。
可否用于GNN分析
另外一個相關的問題是圖度量在圖神經網絡的拓展。可否借鑒文[1]思路來評價GNN網絡中資料的品質、特性？我們知道GNN的輸入資料表達為圖結構，而其結構特點會影響到實作算法與運算硬體的執行性能。如果能夠确定一組合适的度量來分析資料結構的内在特性，那麼這樣的度量對于确定GNN模型和優化無疑會起到指導作用。
06總結
本篇是對Graph Structure of Neural Networks一文介紹的第二部分，主要是對文章中涉及的圖理論部分内容進行更進一步的了解。期望有助于和大家一起了解幾位作者的思路和把握該項研究的進展，并促進在這個方向的開拓性工作。
本文希望能夠起到抛磚引玉的作用，由于水準有限，文中存在不足的地方，請各位讀者批評指正，也歡迎大家參與我們的讨論。
07參考文獻
[1] Jiaxuan You, Jure Leskovec, Kaiming He and Saining Xie，Graph Structure of Neural Networks，ICML2020
[2] Collective dynamics of ‘small-world’ networks, Duncan J. Watts, StevenH. Strogatz , Nature volume 393, pages440–442(1998)
壁仞科技研究院作為壁仞科技的前沿研究部門，旨在研究新型智能計算系統的關鍵技術，重點關注新型架構，先進編譯技術和設計方法學，并将逐漸拓展研究方向，探索未來智能系統的各種可能。壁仞科技研究院秉持開放的原則，将積極投入各類産學研合作并參與開源社群的建設，為相關領域的技術進步做出自己的貢獻。
掃碼關注我們