智源社區 & AI科技評論
作者 | 周寅張皓
小到分子相互作用，物質結構，大至氣候變化，星系模型，很多自然界和社會生活中的現象都能用圖結構描述。而如何將神經網絡應用到圖網絡中進行計算，在幾年前卻是懸而未決的難題。
現今，我們提到的圖神經網絡，往往指圖的卷積，那麼，卷積是如何應用在圖的非歐結構上的？帶著這個問題，我們一起走進10月30日，中科院計算所研究員沈華偉在CCL2020「圖卷積神經網絡」的報告，報告中沈華偉介紹了卷積應用於圖模型的思想起源、譜域方法和空間方法的發展，探討了其表達性能，並對未來發展方向進行思考。
沈華偉，博士，中國科學院計算技術研究所研究員，中國中文信息學會社會媒體處理專委會副主任。研究方向為網絡科學和社會計算。先後獲得過CCF優博、中科院優博、首屆UCAS-Springer優博、中科院院長特別獎、入選首屆中科院青年創新促進會、中科院計算所「學術百星」。2013年在美國東北大學進行學術訪問。2015年被評為中國科學院優秀青年促進會會員（中科院優青）。獲得國家科技進步二等獎、北京市科學技術二等獎、中國電子學會科學技術一等獎、中國中文信息學會錢偉長中文信息處理科學技術一等獎。出版個人專/譯著3部，在網絡社區發現、信息傳播預測、群體行為分析、學術評價等方面取得了系列研究成果，在Science、PNAS等期刊和WWW、SIGIR、CIKM、WSDM、AAAI、IJCAI等會議上發表論文60餘篇，引用1700餘次。擔任PNAS、IEEE TKDE、ACM TKDD等10餘個學術期刊審稿人和WWW、CIKM、WSDM等20餘個學術會議的程序委員會委員。
1
非歐空間的卷積
卷積，在泛函中，指使用一個算符(函數)，與另一個函數運算產生新的函數。若對連續函數f(x)，g(x)使用該運算，可以使用積分公式。直觀上看，卷積可以看作是一個函數對另外一個函數的平均。
沈華偉指出，神經網絡的卷積通常是對歐式空間數據的操作。例如圖片數據，可以看作是在固定形狀的矩陣通道上取不同的值。將卷積操作拓展於離散數據，就成了使用固定的卷積核(函數f(x))對固定通道（函數g(x)）進行相乘求和(積分)。然而在圖結構中，通道往往各不相同，即每張圖都有其特殊結構，無法固定卷積的函數，相對於矩陣這種在歐氏空間的數據，圖的非歐性質使其很難找到有效的方法應用卷積。
圖1：函數的卷積
2
從譜域到空間域
2.1 譜域
1. Yann LeCun的方法
面對以上問題，卷積神經網絡的提出者LeCun，提出了譜域(spectral)和空間域(spatial)兩種方法。在"Spectral Networks and Deep Locally Connected Networks on Graphs"中，作者提出將圖的Laplacian矩陣的特徵向量作為基底，將樣本投影到該空間後，進行卷積操作。採用超參控制每次選擇的相鄰節點的數量，對變化後的樣本做filter和求加，再將輸出結果進行拉普拉斯的逆變換，並輸出非線性化後的結果。
圖2：節點選擇
該方法展示了在譜域進行卷積操作的可能性，並為後續的一系列圖網絡奠定了基礎，但該方法仍存在一些問題，沈華偉指出，該方法依賴於矩陣的特徵分解，且投影計算和逆變換的開銷為O(n)，計算開銷過大。另外，該方法並不是在局部空間上操作的，這讓這種方法失去了直觀上的意義。這些問題也給未來的工作提供了一系列改進的空間。
2. ChebNet
17年的「ChebNet: Efficient and Stable Constructions of Deep Neural Networks with Rectified Power Units using Chebyshev Approximations」使用切比雪夫多項式近似。該方法一次性解決了譜域方法中存在的三個問題。
沈華偉表示，該方法避免了分解Laplacian矩陣，而是採用特徵值對角矩陣作為基底。避免了使用過多自由參數導致的學習困難，同時代入計算公式減少了對特徵向量矩陣U的依賴。研究證明了該方法與譜方法有同樣的誤差上界，且計算複雜度降低到了O(|E|)，極大改善了譜方法圖卷積的性能，同時啟發了空間方法GCN，作為該方法的一階近似。
3. Graph Wavelet Nerual Network(GWNN)
沈華偉發現，ChebNet在使用多項式近似時限制了卷積操作的自由度，使得該模型在實際使用中並不能有很好的效果。因此採用圖的小波基作為基底U。由於小波變換的性質，U為一個稀疏矩陣，降低了計算開銷，同時，其局部性質也使得GWNN在實際應用中展現出不錯的效果。
2.2 空間域
1. 工程思維的啟發
2016年「Learning Convolutional Nerual Networks in Graph」引起了人們對於空間方法的關注。文中方法思路簡潔：對於一個結點進行卷積操作時，固定該點並將該點的固定鄰域節點排序，採用加權平均的方式得到節點值。
該方法固定了每次卷積操作使用的節點個數，採用非常工程化的思維，實現了權重值的共享。其中，該工作採用了對於節點相似度的度量確定鄰接節點的選擇，這啟發了後續的一系列工作。例如在GraphSAGE中，作者採用聚合函數，通過對訪問節點進行隨機遍歷，相當於對所求節點的鄰接節點進行聚合，避免了權重共享的問題。
2. GCN
在先前工作的基礎上，GCN對節點的一階鄰近節點進行訪問，通過一階層次化的堆疊，可以實現對二階、三階信息的獲取。但進一步的分析發現，該方法在計算中並未使卷積操作參數化而共享，其共享的參數是實現特徵變換的W，這使得該方法本質上是對鄰接節點的加權聚合，使用鄰居信息來平滑自身，可以在很多任務中表現出不錯的效果，但表達能力受限。因此，後續工作諸如Graph Attention Network 採用self-attention來控制自身信息與鄰接節點信息的表達，實現了卷積操作的參數化。
圖3：GCN模型
2.3 融合
《MoNet：A General Framework for Spatial Methods》給予圖卷積方法一種規範化的描述。文中指出，圖卷積的實質是使用參數化的權重對定義的距離矩陣加權聚合。這個框架同時給予譜方法一種新的解釋，沈華偉說，相較於空間方法在原始空間定義聚合函數，譜方法在規範後實質上是對變換到新的空間中的樣本進行卷積。因此譜方法可以被看作是變換空間後的空間方法，其從屬於空間方法這一類別。
圖4：譜方法和空間方法的關係
3
圖的表達能力
近年來，圖卷積網絡的一系列應用展現出其在特定任務上的優越性能，在節點分類、預測中得到了很好的效果。在量子化學的應用中，它能在給定物質結構的基礎上，精確的預測物質具有的性能，且精度達到了化學精度，相較於傳統的泛函分析，大大節省了計算開銷和時間。
沈華偉指出，與一般的卷積神經網絡類似，圖的卷積使用加權聚合和空間變換等操作實現了參數共享，使得模型的參數量得到下降，在一定程度上，降低了模型訓練的難度，因此在一些節點預測和分類等任務上取得了不錯的成果，但這依賴於對領域知識的利用，其表達性同樣不如常規的神經網絡。簡單的分析可以證明其性能上的缺陷，例如在一般的分類中，通過增加網絡層數，獲取二階、三階等信息，能夠區分一些一般的圖結構，但對於一些相似結構的特例，GNN並不能有效區分。
圖5：無法分辨的節點
WL test提供了GNN表達能力上界的解釋。與神經網絡不同，GNN對於節點的運算採用聚合操作，無論是加權平均、求和，或是求均值、求Max，輸入輸出並不能保證單射的性質，因而限制了網絡的表達能力。例如，採用均值的情況下，樣本（2，4）和（1，5）可以有相同的均值，同理，在圖網絡上，如果採樣的節點具有相似的結構，且採樣順序相同時，在進行平均聚合運算後會產生相似的結果，導致網絡無法區分。
4
未來的方向
與神經網絡類似，GNN的設計很大程度上依賴於啟發式的設計，缺乏對其理論和性能上的認識。在一些圖網絡性能研究工作中已有進展，但仍待更深入的研究，以幫助進一步理解圖卷積網絡。
報告最後，沈華偉介紹了目前圖卷積網絡研究中的問題和未來的推進方向。
1. 圖網絡的學習性能：是否真正學到結構化的信息。
2. 解決訓練導致的過平滑問題：由於圖卷積實質是利用周圍節點平滑所求節點信息，當網絡深度增加時，容易導致過渡平滑。
3. 圖的預訓練模型。
4. 對抗攻擊: 一些研究表明，圖卷積網絡在一定程度上受限於穩定性問題，需要設計出更加穩定的網絡。
5. 擴展應用領域。