使用這些基本 REST API 最佳實踐構(gòu)建出色的 API
圖神經(jīng)網(wǎng)絡（GNN）是深度學習領域的一個重要模型，已廣泛應用于推薦系統(tǒng)、計算機視覺、自然語言處理、分子分析、數(shù)據(jù)挖掘和異常檢測等現(xiàn)實場景。GNN在從圖形數(shù)據(jù)中學習方面表現(xiàn)出優(yōu)越的能力，其變體已被廣泛應用。
GNN的表達能力包括特征嵌入能力和拓撲表示能力兩個方面。影響GNN表達能力的因素包括特征和拓撲，其中GNN在學習和保持圖拓撲方面的缺陷是限制表達的主要因素。提高GNN表達能力的現(xiàn)有工作可分為圖特征增強、圖拓撲增強和GNN架構(gòu)增強三類。
圖(Graph)一般定義為節(jié)點（v）、邊（e）的集合，可用于表示實體之間的復雜關系，并使用鄰接矩陣和節(jié)點特征來表示。節(jié)點是圖中的基本單元，邊表示節(jié)點之間的關系。鄰居節(jié)點是指與某個節(jié)點相鄰接的節(jié)點。鄰接矩陣是一個n×n的矩陣，其中n是節(jié)點的數(shù)量，矩陣中的元素表示節(jié)點之間是否存在邊。節(jié)點特征是指每個節(jié)點的屬性或特征向量。節(jié)點特征可以是任何類型的數(shù)據(jù)，如數(shù)字、文本或圖像。
GNN是一種深度學習模型，用于學習圖的表示。GNN的基本思想是通過迭代地聚合節(jié)點的鄰居節(jié)點來更新每個節(jié)點的表示。本文介紹了一些基本的GNN模型，如Graph Convolutional Networks（GCNs）和Graph Attention Networks（GATs），以及一些增強GNN表達能力的模型，如Graph Isomorphism Networks（GINs）和Message Passing Neural Networks（MPNNs）。
圖同構(gòu)性是指兩個圖在節(jié)點和邊的結(jié)構(gòu)上完全相同，但節(jié)點和邊的標簽可以不同。在圖神經(jīng)網(wǎng)絡中，圖同構(gòu)性是一個重要的概念，因為它可以幫助我們判斷兩個圖是否相同，從而避免重復計算。GNNs可以通過學習圖的特征來解決圖同構(gòu)問題。
Weisfeiler-Lehman測試（WL測試）是一種解決圖同構(gòu)問題的有效算法，也稱為顏色細化算法。圖1展示了WL測試的聚合和更新過程。(a)給定兩個沒有特征的圖，并為所有節(jié)點添加顏色標簽。(b)在第一次迭代中，節(jié)點聚合的不同信息被映射到新的顏色標簽中，然后這些新標簽被重新分配給節(jié)點，并在分配后計算標簽數(shù)量。在第一次迭代后，G1和G2具有相同的顏色分布，以確定它們是否同構(gòu)，并進行下一次迭代。(c)再次執(zhí)行節(jié)點鄰居聚合和顏色標簽重新分配步驟，并獲得G1和G2的不同顏色分布，此時可以確定它們不同構(gòu)。圖2展示了WL測試無法區(qū)分的非同構(gòu)圖。k-WL也是一種用于解決圖同構(gòu)問題的算法。
圖1 WL測試的聚合和更新過程
圖2：一些WL測試無法區(qū)分的非同構(gòu)圖
機器學習模型的表現(xiàn)取決于其表達能力，神經(jīng)網(wǎng)絡的表達能力通常強于GNN。然而，在某些節(jié)點分類問題中，圖增強多層感知器（MLP）的表現(xiàn)優(yōu)于GNN。這表明僅使用每個節(jié)點的信息計算節(jié)點特征嵌入的MLP可以超越使用全局信息聚合鄰居節(jié)點特征嵌入的GNN。GNN的卓越性能關鍵在于其拓撲表示能力，為了評估和設計更有效的GNN模型，需要深入研究它們?nèi)绾卫脠D的拓撲結(jié)構(gòu)進行信息傳播和節(jié)點更新，并開發(fā)一套新的理論工具來描述GNN的拓撲表示能力。
圖3說明了不同模型的表達能力：
a)部分說明機器學習問題的目標是基于多個觀察到的例子來學習從特征空間到目標空間的映射。
b)部分說明神經(jīng)網(wǎng)絡的表達能力指的是空間F和F’之間的差距。雖然神經(jīng)網(wǎng)絡具有表達能力（F’在F中密集），但基于神經(jīng)網(wǎng)絡的學習模型f’可能與f*存在顯著差異，因為它們過度擬合了有限的觀察數(shù)據(jù)。
圖 3：神經(jīng)網(wǎng)絡的表達能力及其對學習模型性能的影響。**
**
GNN的表達能力與其特征嵌入能力和拓撲表示能力密切相關。作為神經(jīng)網(wǎng)絡的一種，GNN具有強大的特征嵌入能力，可以學習圖中節(jié)點和邊的表示，反映了具有不同特征的節(jié)點可以得到不同的節(jié)點嵌入。拓撲表示能力是GNN的獨特能力，使其不同于其他機器學習模型，它使GNN能夠捕捉圖的結(jié)構(gòu)信息并學習節(jié)點之間的連接模式，反映了具有不同拓撲位置的節(jié)點可以得到不同的節(jié)點嵌入。
特征嵌入能力和拓撲表示能力共同構(gòu)成了GNN的表達能力，如圖4所示：
a) GNN 的特征嵌入能力與神經(jīng)網(wǎng)絡相同，都是通過 f 將特征空間 X 中的觀察到的示例映射到目標空間 Y。 特征嵌入能力的強弱是通過f的值域空間F的大小來衡量的。
b）GNN的拓撲表示能力是通過f將特征空間中觀察到的實例映射到目標空間并保留實例之間的原始拓撲來實現(xiàn)的。 能力的強弱是通過值域空間F′（X = 1）的大小來衡量的。
c) GNN 的表達能力由特征嵌入能力和拓撲表示能力的組合組成，通過 F 和 F′ 的交集大小（其中 X = 隨機）來衡量。
圖 4：GNN表達能力的示意圖
目前GNN表達能力研究中的幾種主流觀點分別將表達能力描述為近似能力、分離能力和子圖計數(shù)能力。圖 5為不同表達能力表示下 GNN 模型的輸入和輸出。當使用近似能力來描述GNN的表達能力時，模型的輸入是一組圖形，輸出是圖形嵌入。當使用分離能力時，輸入是一對圖形，輸出是圖形嵌入。當使用子圖計數(shù)能力時，輸入是單個圖形，輸出是節(jié)點（集合）嵌入。
圖 5：不同表達能力表示下 GNN 模型的輸入和輸出
GNN 具有執(zhí)行特征嵌入和拓撲表示的能力，這使得它們能夠捕獲圖的局部和全局結(jié)構(gòu)信息。 這種能力使 GNN 能夠在圖的拓撲上傳播和聚合信息，這對于節(jié)點分類、鏈接預測和圖分類等任務至關重要。 GNN 在這些任務中表現(xiàn)出了顯著的成功，這表明了其卓越的表達能力。
GNN的表達能力強于表達圖特征和圖拓撲結(jié)構(gòu)，因此圖特征嵌入和圖拓撲表示的效果將影響GNN的表達。節(jié)點特征和全局圖特征都具有判別能力，GNN可以區(qū)分不同節(jié)點特征或全局圖特征的圖。然而，GNN的表達能力受到排列不變聚合函數(shù)的限制，這種函數(shù)忽略了相鄰節(jié)點之間的關系，導致GNN在拓撲表示中丟失上下文的拓撲結(jié)構(gòu)，從而無法學習圖的基本拓撲屬性。
提高圖神經(jīng)網(wǎng)絡表達能力的三種方法：圖特征增強、圖拓撲增強和GNN架構(gòu)增強。圖特征增強是通過增強特征嵌入效果來提高表達能力，圖拓撲增強則是尋求更有效地表示圖拓撲以捕獲更復雜的圖拓撲信息。GNN架構(gòu)增強包括改進限制GNN表達能力的排列不變聚合函數(shù)和其他評估指標。這些方法可以提高特征嵌入效果和改善拓撲表示效果，從而增強GNN模型的表達能力。
表1對近年來更強大的表達性GNN進行了檢查和系統(tǒng)分類，根據(jù)其采用的設計方法進行分類。
表 1：強大模型的總結(jié)
圖特征增強，旨在提高圖特征的嵌入效率。其中一種方法是提取特征之間的依賴關系，以增加特征的信息量，另一種方法是提高特征的利用率。圖7詳細描述了這種提升特征嵌入效果的方法。
圖7：圖特征增強的方法
我們還提供了使用這些方法的GNN模型的示例，例如自適應多通道圖卷積網(wǎng)絡（AM-GCN）、CL-GNN和ACR-GNN。圖8展示了AM-GCN架構(gòu)中信息通過三圖卷積的傳播過程。左邊部分顯示了通過為原始圖中的每個節(jié)點選擇 k 個最相似的鄰居來獲得 k-NN 圖的過程。右半部分展示了k-NN圖、原始圖和常見卷積過程上的卷積。
圖8：AM-GCN架構(gòu)中信息通過三圖卷積的傳播過程
圖拓撲增強，旨在直接編碼學習到的拓撲信息。其中一種方法是手動添加額外的拓撲相關節(jié)點特征，另一種方法是直接編碼圖中固有的拓撲信息。根據(jù)編碼的不同拓撲信息，后一種方法可以進一步分為：編碼微觀拓撲（如距離、位置和其他拓撲信息）、編碼局部拓撲（主要基于子圖拓撲的局部拓撲信息）和編碼全局拓撲。圖9展示了圖拓撲增強方法的詳細描述。圖10示例了P-GNN 的更新策略，a)是不同大小的錨節(jié)點集，b)是v1嵌入到第l層的過程。
圖 9：圖拓撲增強的方法
圖10：P-GNN 的更新策略
GNN 架構(gòu)增強。GNN架構(gòu)增強是提高GNN表達能力的另一種方法，例如使用注意力機制、增加層數(shù)、使用多頭注意力機制等方法可以提高GNNs的表達能力和性能。圖11展示了GNN 架構(gòu)增強的方法。
圖11：GNN 架構(gòu)增強的方法
GNN 研究的主要挑戰(zhàn)之一是缺乏可靠的真實數(shù)據(jù)集、明確的基準和合理的評估指標，這使得比較不同模型的性能并評估其有效性變得困難。另一個挑戰(zhàn)是 GNN 模型的可擴展性較差。為了應對這些挑戰(zhàn)，我們需要更全面和多樣化的現(xiàn)實世界數(shù)據(jù)集，以提供更可信的模型評估。 此外，我們需要為 GNN 的表達能力建立明確的基準和評估指標，并利用新的模型和技術來提高 GNN 的可擴展性和表達能力。
參考文獻：《A Survey on The Expressive Power of Graph Neural Networks》https://arxiv.org/abs/2003.04078
文章轉(zhuǎn)自微信公眾號@算法進階