Graph圖Transformer前沿進展研究！

圖作為具有高度表達能力的數(shù)據(jù)結(jié)構(gòu)，廣泛用于表示各個領(lǐng)域的復雜數(shù)據(jù)，例如社交媒體、知識圖譜、生物學、化學和交通網(wǎng)絡(luò)[1]。它們從數(shù)據(jù)中捕捉結(jié)構(gòu)和語義信息，促進了推薦系統(tǒng)[2]、問答系統(tǒng)[3]、異常檢測[4]、情感分析[5]、文本生成[6]和信息檢索[7]等任務的發(fā)展。為了有效處理圖結(jié)構(gòu)數(shù)據(jù)，研究人員開發(fā)了各種圖學習模型，例如圖神經(jīng)網(wǎng)絡(luò)（GNN），這些模型可以學習節(jié)點、邊和圖的有意義表示[8]。特別是，遵循消息傳遞框架的GNN通過迭代地聚合鄰居信息并更新節(jié)點表示，在各種基于圖的任務中表現(xiàn)出色[9]。從信息提取到推薦系統(tǒng)等應用都受益于GNN對知識圖譜的建模[10]。

最近，作為新興且強大的圖學習方法，圖Transformer在學術(shù)界和工業(yè)界都引起了極大的關(guān)注[11],[12]。圖Transformer的研究受到了Transformer在自然語言處理（NLP）[13]和計算機視覺（CV）[14]中成功應用的啟發(fā)，并結(jié)合了GNN的價值。圖Transformer結(jié)合了圖歸納偏差（例如，對圖屬性的先驗知識或假設(shè)）來有效處理圖數(shù)據(jù)[15]。此外，它們可以適應動態(tài)和異構(gòu)圖，利用節(jié)點和邊的特征和屬性[16]。圖Transformer的各種改編和擴展在解決圖學習的各種挑戰(zhàn)（如大規(guī)模圖處理）方面表現(xiàn)出優(yōu)越性[17]。此外，圖Transformer已成功應用于各個領(lǐng)域和應用，展示了其有效性和多功能性。

現(xiàn)有的綜述未能充分涵蓋圖Transformer的最新進展和全面應用。此外，大多數(shù)綜述未能提供系統(tǒng)的圖Transformer模型分類。例如，Chen等人[18]主要關(guān)注GNN和圖Transformer在CV中的應用，但未能總結(jié)圖Transformer模型的分類法并忽略了其他領(lǐng)域（如NLP）。同樣，Muller等人[12]概述了圖Transformer及其理論屬性，但未提供現(xiàn)有方法的全面綜述或評估其在各種任務上的表現(xiàn)。最后，Min等人[19]集中于圖Transformer的架構(gòu)設(shè)計方面，系統(tǒng)評估了不同組件在不同圖基準測試中的表現(xiàn)，但未包括圖Transformer的重要應用或討論該領(lǐng)域的開放問題。

為了填補這些空白，本綜述旨在從設(shè)計和應用視角全面系統(tǒng)地回顧圖Transformer研究的最新進展和挑戰(zhàn)。與現(xiàn)有綜述相比，我們的主要貢獻如下：

1. 我們?nèi)婊仡櫫藞DTransformer的設(shè)計視角，包括圖歸納偏差和圖注意力機制。我們將這些技術(shù)分類并討論其優(yōu)缺點。

2. 我們提出了一種基于深度、可擴展性和預訓練策略的圖Transformer新分類法，并提供了選擇不同任務和場景中有效圖Transformer架構(gòu)的指南。

3. 我們回顧了圖Transformer在各種圖學習任務中的應用視角，以及在其他領(lǐng)域（如NLP和CV任務）中的應用場景。

4. 我們確定了圖Transformer研究中的關(guān)鍵開放問題和未來方向，如模型的可擴展性、泛化性、可解釋性、高效的時間圖學習和數(shù)據(jù)相關(guān)問題。

本文的概述如圖1所示。后續(xù)綜述的結(jié)構(gòu)如下：第二節(jié)介紹與圖和Transformer相關(guān)的符號和預備知識。第三節(jié)深入探討包含圖歸納偏差和圖注意力機制的圖Transformer的設(shè)計視角。第四節(jié)提出圖Transformer的分類法，基于其深度、可擴展性和預訓練策略進行分類。此外，還提供了選擇適當圖Transformer模型以應對不同任務和領(lǐng)域的指南。第五節(jié)探討圖Transformer在各種節(jié)點級、邊級和圖級任務中的應用視角，以及其他應用場景。第六節(jié)確定了圖Transformer研究的開放問題和未來方向。最后，第七節(jié)總結(jié)本文并強調(diào)其主要貢獻。

圖Transformer分類法 

近年來，圖Transformer引起了極大的興趣。本節(jié)深入探討當前文獻中的四個主要類別：淺層圖Transformer、深層圖Transformer、可擴展圖Transformer和預訓練圖Transformer。通過分析每個類別中的代表性模型，我們旨在為設(shè)計高效的圖Transformer提供有價值的指導。

A. 淺層圖Transformer 

淺層圖Transformer代表了一類利用自注意力機制從圖結(jié)構(gòu)數(shù)據(jù)中獲取節(jié)點表示的GNN。這些模型受到了Transformer在順序數(shù)據(jù)中通過自注意力有效捕捉長程依賴關(guān)系的啟發(fā)，將這一概念擴展到圖數(shù)據(jù)中，通過基于節(jié)點特征和圖拓撲計算自注意力權(quán)重[94]。淺層圖Transformer的主要目標是在盡量減少計算復雜度和內(nèi)存使用的同時，達到卓越的性能。

淺層圖Transformer可以看作是圖注意力網(wǎng)絡(luò)（GAT）的廣義版本[42]。GAT使用多頭注意力機制來計算節(jié)點嵌入。然而，GAT存在一些局限性，如無法建模邊特征以及注意力頭之間缺乏多樣性[95]。文獻中提出了幾種GAT擴展以解決這些問題。例如，Yun等人[36]提出的GTN引入了邊緣自注意力機制，將邊信息納入節(jié)點嵌入。Ahmad等人[63]提出的圖注意力Transformer編碼器（GATE）應用了掩碼自注意力機制，為不同節(jié)點學習不同的注意模式。GATE還使用了位置前饋網(wǎng)絡(luò)和dropout來增強模型容量和泛化能力。淺層圖Transformer方法的總結(jié)見表II。

淺層圖Transformer高效且適應性強，能夠處理各種圖學習任務和不同類型的圖，但其深度和遞歸的缺乏可能限制其捕捉復雜依賴關(guān)系的能力。其性能還可能受到掩碼矩陣選擇和注意力頭數(shù)量的影響，這表明需要進一步研究其優(yōu)化設(shè)計和正則化。

B. 深層圖Transformer 

深層圖Transformer由多個堆疊在一起的自注意力層組成，層之間可以有可選的跳躍連接、殘差連接或密集連接[102]。它們旨在通過增加模型深度和復雜性來達到更高的性能[103]。深層圖Transformer通過層次化地將自注意力層應用于節(jié)點特征和圖拓撲，擴展了淺層圖Transformer。

然而，深層圖Transformer也面臨需要解決的幾個挑戰(zhàn)。一個挑戰(zhàn)是訓練更深模型的難度，可以通過使用DeeperGCN中引入的PairNorm等技術(shù)來緩解[104]。另一個挑戰(zhàn)是過度平滑問題，可以通過使用門控殘差連接和廣義卷積算子（如DeeperGCN中提出的）來解決。此外，全局注意力能力的消失和注意力頭之間缺乏多樣性也是需要解決的問題，可以通過像DeepGraph[94]這樣的方法來解決。DeepGraph引入了子結(jié)構(gòu)token和局部注意力，以改進全局注意力的焦點和多樣性。

深層圖Transformer雖然復雜，但能夠在各種圖學習任務中取得頂級成績，并適應不同類型的圖和領(lǐng)域。然而，其高計算成本、優(yōu)化難度和對超參數(shù)的敏感性需要進一步研究以優(yōu)化設(shè)計和訓練。深層圖Transformer方法的總結(jié)見表III。

C. 可擴展圖Transformer 

可擴展圖Transformer是一類在將自注意力應用于大規(guī)模圖時應對可擴展性和效率挑戰(zhàn)的圖Transformer[39],[53],[114],[115]。這些Transformer專門設(shè)計用來在保持或提高性能的同時減少計算成本和內(nèi)存使用。為實現(xiàn)這一目標，采用了各種技術(shù)來降低自注意力的復雜性，例如稀疏注意力、局部注意力和低秩近似[12],[115]。可擴展圖Transformer可以看作是深層圖Transformer的增強版，解決了如過度平滑和全局注意力能力有限等挑戰(zhàn)。

提出了幾種可擴展圖Transformer模型，以提高圖Transformer的可擴展性和效率。例如，Rampa?ek等人[39]引入的GPS使用低秩矩陣近似來降低計算復雜性，并在各種基準測試中取得了最先進的結(jié)果。GPS將局部真實邊聚合與全連接Transformer分離，并結(jié)合不同的位置信息和結(jié)構(gòu)編碼來捕捉圖拓撲。它還提供了一個模塊化框架，支持多種編碼類型和局部與全局注意力機制。Cong等人[116]開發(fā)的DyFormer是一種動態(tài)圖Transformer，利用子結(jié)構(gòu)token和局部注意力來增強全局注意力的焦點和多樣性。DyFormer采用時間聯(lián)合圖結(jié)構(gòu)和基于子圖的節(jié)點采樣策略，實現(xiàn)高效和可擴展的訓練。

可擴展圖Transformer是一類創(chuàng)新且高效的圖Transformer，能夠在處理大規(guī)模圖時表現(xiàn)出色，同時盡量減少計算成本和內(nèi)存使用。然而，可擴展圖Transformer也面臨一些局限性，包括可擴展性和表達能力之間的權(quán)衡、選擇最佳超參數(shù)和編碼的挑戰(zhàn)以及缺乏關(guān)于其收斂性和穩(wěn)定性的理論分析。因此，需要進一步研究以探索各種應用中可擴展圖Transformer的最佳設(shè)計和評估?？蓴U展圖Transformer方法的綜合概述見表IV。

D. 預訓練圖Transformer 

預訓練圖Transformer利用大規(guī)模無標簽圖來獲取可轉(zhuǎn)移的節(jié)點嵌入[135]。這些嵌入可以通過微調(diào)用于下游任務，以解決圖學習任務中的數(shù)據(jù)稀缺和領(lǐng)域適應挑戰(zhàn)[136],[137]。這些Transformer類似于預訓練的大型語言模型（LLM），使用自監(jiān)督學習目標在圖數(shù)據(jù)集上進行訓練，例如掩碼節(jié)點預測[138]、邊重建[139]和圖對比學習[140]。這些目標旨在獨立于外部標簽或監(jiān)督捕捉圖數(shù)據(jù)的固有屬性[141]。通過結(jié)合特定任務層或損失函數(shù)并在標簽數(shù)據(jù)上進行優(yōu)化，預訓練模型可以在特定下游任務上進行微調(diào)。這樣，預訓練模型能夠?qū)拇笠?guī)模圖數(shù)據(jù)集中獲得的知識轉(zhuǎn)移到后續(xù)任務，從而獲得比從頭訓練更好的性能[142]。

預訓練圖Transformer面臨一些挑戰(zhàn)，如選擇合適的預訓練任務、領(lǐng)域知識的結(jié)合、異構(gòu)信息的整合和預訓練質(zhì)量的評估[143]。為解決這些問題，提出了KPGT[144]和KGTransformer[145]。KPGT利用額外的領(lǐng)域知識進行預訓練，而KGTransformer作為統(tǒng)一的知識表示和融合（KRF）模塊應用于各種任務中。盡管預訓練圖Transformer功能強大且靈活，但它們也面臨圖數(shù)據(jù)異質(zhì)性和稀疏性、領(lǐng)域適應、模型泛化和性能解釋等問題。預訓練圖Transformer方法的總結(jié)見表V。

E. 高效圖Transformer的設(shè)計指南 

開發(fā)高效的圖Transformer需要仔細注意細節(jié)和周全的考慮。本指南提供了為各種場景和任務設(shè)計圖Transformer的一般原則和提示。

• 根據(jù)圖數(shù)據(jù)和任務的性質(zhì)和復雜性選擇合適的圖Transformer類型。對于簡單和小規(guī)模的圖數(shù)據(jù)，淺層圖Transformer幾層可能就足夠了。對于復雜和大規(guī)模的圖數(shù)據(jù)，深層圖Transformer具有更多層次可以學習更具表現(xiàn)力的表示。對于動態(tài)或流式圖數(shù)據(jù)，可擴展圖Transformer更高效。預訓練圖Transformer更適合稀疏或噪聲圖數(shù)據(jù)。

• 為圖數(shù)據(jù)設(shè)計合適的結(jié)構(gòu)和位置編碼。這些編碼捕捉圖的結(jié)構(gòu)，并在將輸入節(jié)點或邊特征輸入Transformer層之前添加。編碼的選擇取決于圖數(shù)據(jù)的特征，如方向性、權(quán)重和同質(zhì)性。精心設(shè)計這些編碼可以確保它們的信息性。

• 優(yōu)化自注意力機制以適應圖數(shù)據(jù)。自注意力機制在圖中的所有節(jié)點或邊對之間計算注意力分數(shù)，捕捉長程依賴關(guān)系和交互。然而，這引入了計算復雜性、內(nèi)存消耗、過擬合、過度平滑和壓縮等挑戰(zhàn)?？梢圆捎貌蓸?、稀疏化、分區(qū)、哈希、掩碼、正則化和歸一化等技術(shù)來解決這些挑戰(zhàn)，并提高自注意力機制的質(zhì)量和效率。

• 利用預訓練技術(shù)增強圖Transformer的性能。預訓練技術(shù)利用其他領(lǐng)域或任務的預訓練模型或數(shù)據(jù)，將知識或參數(shù)轉(zhuǎn)移到特定的圖學習任務?？梢允褂梦⒄{(diào)、蒸餾和適應等方法來調(diào)整預訓練模型或數(shù)據(jù)。利用預訓練技術(shù)特別有益于擁有大量預訓練數(shù)據(jù)或資源時。

結(jié)論 

圖Transformer是一類新穎且強大的神經(jīng)網(wǎng)絡(luò)模型，能夠有效地編碼和處理圖結(jié)構(gòu)數(shù)據(jù)。本綜述從設(shè)計視角、分類法、應用和開放問題等方面提供了圖Transformer的全面概述。我們首先討論了圖Transformer如何結(jié)合圖歸納偏差，包括節(jié)點位置編碼、邊結(jié)構(gòu)編碼、消息傳遞偏差和注意力偏差，以編碼圖的結(jié)構(gòu)信息。然后，我們介紹了圖注意力機制的設(shè)計，包括全局和局部注意力機制。接著，我們提出了圖Transformer的分類法。本綜述還包括有效圖Transformer的設(shè)計指南，提供了選擇適當組件和超參數(shù)的最佳實踐和建議。此外，我們基于各種圖相關(guān)任務（如節(jié)點級、邊級和圖級任務）以及其他領(lǐng)域的任務，回顧了圖Transformer的應用場景。最后，我們確定了圖Transformer的當前挑戰(zhàn)和未來方向。本綜述旨在為對圖Transformer及其應用感興趣的研究人員和實踐者提供有價值的參考。

鏈接：https://arxiv.org/pdf/2407.09777