Graph Transformer技術(shù)與研究進(jìn)展：從基礎(chǔ)理論到前沿應(yīng)用

摘 要：圖數(shù)據(jù)處理是一種用于分析和操作圖結(jié)構(gòu)數(shù)據(jù)的方法，廣泛應(yīng)用于各個領(lǐng)域。Graph Transformer作為一種直接學(xué)習(xí)圖結(jié)構(gòu)數(shù)據(jù)的模型框架，結(jié)合了Transformer的自注意力機(jī)制和圖神經(jīng)網(wǎng)絡(luò)的方法，是一種新型模型。通過捕捉節(jié)點(diǎn)間的全局依賴關(guān)系和精確編碼圖的拓?fù)浣Y(jié)構(gòu)，Graph Transformer在節(jié)點(diǎn)分類、鏈接預(yù)測和圖生成等任務(wù)中展現(xiàn)出卓越的性能和準(zhǔn)確性。通過引入自注意力機(jī)制，Graph Transformer能夠有效捕捉節(jié)點(diǎn)和邊的局部及全局信息，顯著提升模型效率和性能。深入探討Graph Transformer模型，涵蓋其發(fā)展背景、基本原理和詳細(xì)結(jié)構(gòu)，并從注意力機(jī)制、模塊架構(gòu)和復(fù)雜圖處理能力（包括超圖、動態(tài)圖）三個角度進(jìn)行細(xì)分分析。全面介紹Graph Transformer的應(yīng)用現(xiàn)狀和未來發(fā)展趨勢，并探討其存在的問題和挑戰(zhàn)，提出可能的改進(jìn)方法和思路，以推動該領(lǐng)域的研究和應(yīng)用進(jìn)一步發(fā)展。

關(guān)鍵詞：圖神經(jīng)網(wǎng)絡(luò)；Graph Transformer；圖表示學(xué)習(xí)；節(jié)點(diǎn)分類

中圖分類號：TP39"" 文獻(xiàn)標(biāo)志碼：A""" 文章編號：1001-3695（2025）04-002-0975-12

doi： 10.19734/j.issn.1001-3695.2024.08.0291

Graph Transformer technology and research progress： fromfundamental theory to cutting-edge applications

You Hao， Ding Cangfeng， Ma Lerong， Yan Zhaoyao， Cao Lu

（College of Mathematics amp; Computer Science， Yan’an University， Yan’an Shaanxi 716000， China）

Abstract：Graph data processing is a method used for analyzing and manipulating graph-structured data， which is widely applied across various domains. The Graph Transformer， as a model framework directly learning from graph-structured data， combines the self-attention mechanism of the Transformer and methods from graph neural networks， making it a novel model. By capturing global dependencies between nodes and accurately encoding the topology of graphs， the Graph Transformer exhi-bits outstanding performance and accuracy in tasks such as node classification， link prediction， and graph generation. With the introduction of the self-attention mechanism， the Graph Transformer effectively captures both local and global information of nodes and edges， significantly enhancing model efficiency and performance. This paper delved into the Graph Transformer model， covering its development background， fundamental principles， and detailed structure， and analyzed it from three perspectives： attention mechanisms， modular architecture， and complex graph processing capabilities （including hypergraphs and dynamic graphs）. It comprehensively introduced the current application status and future development trends of the Graph Transformer， discussed existing issues and challenges， and proposed possible improvements and ideas to further advance research and applications in this field.

Key words：graph neural network（GNN）; Graph Transformer; graph representation learning; node classification

0 引言

圖（graph）［1］是一種數(shù)據(jù)結(jié)構(gòu)，最早由數(shù)學(xué)家歐拉在1736年提出，用于模擬多種類型的關(guān)系和過程。在圖論［2］中，圖是由節(jié)點(diǎn)（也稱為頂點(diǎn)）和連接這些節(jié)點(diǎn)的邊組成的。節(jié)點(diǎn)通常代表對象，而邊則表示對象之間的關(guān)系或相互作用。圖可以是有向的（邊有方向）或無向的（邊沒有方向），并且可以包含權(quán)重（邊或節(jié)點(diǎn)的權(quán)重反映了連接或節(jié)點(diǎn)的強(qiáng)度或容量）。圖是一種常見的數(shù)據(jù)結(jié)構(gòu)，廣泛應(yīng)用于各個領(lǐng)域，如社交網(wǎng)絡(luò)分析［3］、推薦系統(tǒng)［4］、化學(xué)分子結(jié)構(gòu)分析［5］等。

圖神經(jīng)網(wǎng)絡(luò)（graph neural network，GNN）［6］是一類深度學(xué)習(xí)模型，專門用于分析和處理圖形結(jié)構(gòu)數(shù)據(jù)。這些網(wǎng)絡(luò)的設(shè)計(jì)初衷受到了兩個關(guān)鍵領(lǐng)域的影響。首先，卷積神經(jīng)網(wǎng)絡(luò)（con-volutional neural network，CNN）［7］在圖像和文本處理領(lǐng)域的卓越成就為GNN的開發(fā)提供了重要啟發(fā)。CNN通過提取局部空間特征以及利用局部連接、權(quán)重共享和多層架構(gòu)等機(jī)制，有效地處理了規(guī)則化的數(shù)據(jù)結(jié)構(gòu)。由于圖數(shù)據(jù)也呈現(xiàn)出明顯的局部連接性，這些機(jī)制被借鑒并適應(yīng)于圖結(jié)構(gòu)的處理，促成了圖卷積網(wǎng)絡(luò)（graph convolutional network， GCN）［8］模型的誕生。

其次，圖嵌入理論［9］的發(fā)展也對GNN的構(gòu)思產(chǎn)生了影響。圖嵌入旨在將圖中的節(jié)點(diǎn)、邊或子圖表示為低維向量，其中算法如DeepWalk和node2vec［10］利用隨機(jī)游走和SkipGram模型［11］來學(xué)習(xí)節(jié)點(diǎn)的低維表示。雖然這些方法在圖數(shù)據(jù)的表示學(xué)習(xí)上取得了一定進(jìn)展，但它們通常缺乏參數(shù)共享和泛化能力，不足以適應(yīng)圖結(jié)構(gòu)的動態(tài)變化或新圖的處理需求。

經(jīng)過多年的研究與發(fā)展，研究者們逐步將Transformer模型［12］的應(yīng)用拓展至圖數(shù)據(jù)處理領(lǐng)域。Transformer模型憑借其自注意力機(jī)制和多頭注意力機(jī)制，能夠有效捕捉輸入序列中的長距離依賴關(guān)系，顯著提高了模型的效率和性能。在此基礎(chǔ)上，研究者們創(chuàng)新性地設(shè)計(jì)了Graph Transformer模型［13］，專注于處理圖結(jié)構(gòu)數(shù)據(jù)。該模型融合了Transformer的自注意力機(jī)制和圖神經(jīng)網(wǎng)絡(luò)的特點(diǎn)，其工作原理是通過自注意力機(jī)制計(jì)算節(jié)點(diǎn)間的關(guān)系，使得每個節(jié)點(diǎn)能夠關(guān)注到鄰居節(jié)點(diǎn)的信息，從而有效捕捉長距離依賴和圖的結(jié)構(gòu)特性。該方法使得Graph Transformer在社交網(wǎng)絡(luò)分析、推薦系統(tǒng)和藥物發(fā)現(xiàn)等多個領(lǐng)域表現(xiàn)卓越，能更高效地處理復(fù)雜的圖數(shù)據(jù)。具體來說，CoAtGIN［14］、MAT［15］和GROVER［16］在分子預(yù)測領(lǐng)域表現(xiàn)出色，scMoFormer［17］在單細(xì)胞多模態(tài)分析中得到應(yīng)用，HGT［18］在圖到序列學(xué)習(xí)方面具有優(yōu)勢，HetGT［19］用于文本生成，DGTR［20］在謠言檢測中表現(xiàn)突出，而kgTransformer［21］則在知識圖譜推理中展現(xiàn)了其強(qiáng)大的應(yīng)用潛力。這些模型為處理社交網(wǎng)絡(luò)、生物信息學(xué)和推薦系統(tǒng)等圖數(shù)據(jù)任務(wù)提供了新的思路，開辟了深度學(xué)習(xí)在圖數(shù)據(jù)領(lǐng)域的廣泛應(yīng)用可能性。

總之，Graph Transformer模型通過利用自注意力機(jī)制，在圖數(shù)據(jù)處理上實(shí)現(xiàn)了質(zhì)的飛躍，不僅提高了處理效率，還擴(kuò)展了模型的應(yīng)用范圍，為各種復(fù)雜的圖分析任務(wù)提供了支持。Graph Transformer能夠精確學(xué)習(xí)和表示節(jié)點(diǎn)間的關(guān)系，生成全面的全局圖表示。相比傳統(tǒng)圖處理技術(shù)，Graph Transformer展示了顯著的優(yōu)勢。它具備強(qiáng)大的全局信息建模能力，能夠理解和建模圖中跨越遠(yuǎn)距離和多個連接的復(fù)雜依存關(guān)系，從而全面理解圖的整體結(jié)構(gòu)。同時(shí)，Graph Transformer優(yōu)化了處理大規(guī)模圖數(shù)據(jù)的能力，高效擴(kuò)展至包含成千上萬節(jié)點(diǎn)和邊的大圖，而計(jì)算負(fù)擔(dān)沒有顯著增加。此外，Graph Transformer在社交網(wǎng)絡(luò)分析、推薦系統(tǒng)和化學(xué)分子結(jié)構(gòu)分析等多個領(lǐng)域展現(xiàn)出高度的應(yīng)用靈活性和較高的預(yù)測精度。本文旨在全面介紹Graph Transformer模型在圖數(shù)據(jù)處理領(lǐng)域的研究進(jìn)展和應(yīng)用，深入探討Graph Transformer模型，包括其發(fā)展背景、基本原理和詳細(xì)結(jié)構(gòu)，特別從注意力機(jī)制、模塊架構(gòu)層面以及復(fù)雜圖處理能力三個分類角度進(jìn)行細(xì)分（如圖1所示）。本綜述希望能夠?yàn)檠芯空吆蛷臉I(yè)人員提供有價(jià)值的參考，促進(jìn)Graph Transformer模型在圖數(shù)據(jù)處理領(lǐng)域的進(jìn)一步發(fā)展和應(yīng)用。

本綜述探討了Graph Transformer模型在圖數(shù)據(jù)分析中的應(yīng)用，評估其性能，并與現(xiàn)有方法進(jìn)行比較。研究方法包括對Graph Transformer的理論基礎(chǔ)、架構(gòu)和應(yīng)用場景進(jìn)行全面分析，以及在不同數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證，展示了其在圖數(shù)據(jù)分析中的潛在優(yōu)勢和應(yīng)用前景。

1 Graph Transformer的理論和方法

1.1 Graph Transformer設(shè)計(jì)原理

Graph Transformer結(jié)合了圖神經(jīng)網(wǎng)絡(luò)和Transformer的優(yōu)勢，通過自注意力機(jī)制在圖中捕捉節(jié)點(diǎn)之間的關(guān)系。它使用圖嵌入將節(jié)點(diǎn)特征映射到高維空間，并引入基于圖拓?fù)浣Y(jié)構(gòu)的位置編碼，以保留節(jié)點(diǎn)的結(jié)構(gòu)信息。編碼器塊則由多個自注意力層和前饋神經(jīng)網(wǎng)絡(luò)組成，逐層提取圖的高階特征，增強(qiáng)了圖表示的表達(dá)能力。接下來介紹幾個關(guān)鍵組件，以實(shí)現(xiàn)Graph Transformer的設(shè)計(jì)原理。自注意力機(jī)制［22］是Graph Transfor-mer架構(gòu)的核心，允許圖中的每個節(jié)點(diǎn)考慮來自圖中任何其他節(jié)點(diǎn)的信息，這有助于捕獲圖結(jié)構(gòu)內(nèi)的長距離依賴關(guān)系。式（1）是計(jì)算第二個輸出向量的過程。此過程涉及所有輸入元素的查詢、鍵和值向量。圖2是自注意力機(jī)制計(jì)算過程的圖解介紹。

b2=∑ia′2，ivi

（1）

其中：查詢（query）向量用于衡量每個輸入元素與其他所有元素的相關(guān)性；鍵（key）向量與查詢向量配對計(jì)算注意力得分；值（value）向量則根據(jù)注意力得分被加權(quán)求和，形成輸出向量。注意力權(quán)重是通過查詢向量和鍵向量的點(diǎn)積，經(jīng)softmax函數(shù)歸一化后的權(quán)重，表示每個值向量對輸出向量的貢獻(xiàn)大小。

在Graph Transformer中，圖嵌入是實(shí)現(xiàn)圖數(shù)據(jù)處理的關(guān)鍵技術(shù)之一。Graph Transformer中的圖嵌入是將圖中的節(jié)點(diǎn)、邊以及整個圖結(jié)構(gòu)轉(zhuǎn)換成低維向量表示的過程。這些向量表示能夠捕獲圖的拓?fù)浣Y(jié)構(gòu)、節(jié)點(diǎn)間的關(guān)系以及節(jié)點(diǎn)的特征信息。在Graph Transformer框架中，圖嵌入尤其關(guān)鍵，因?yàn)樗苯佑绊懙侥Ｐ蛯D數(shù)據(jù)的理解和處理能力。

Graph Transformer通過圖嵌入技術(shù)，可以廣泛應(yīng)用于各種圖數(shù)據(jù)處理任務(wù)［23］，如：節(jié)點(diǎn)分類、鏈接預(yù)測、圖分類及聚類、圖生成。Graph Transformer通過圖嵌入技術(shù)，為處理復(fù)雜的圖結(jié)構(gòu)數(shù)據(jù)提供了一種強(qiáng)大且靈活的工具，使得深度學(xué)習(xí)模型能夠更好地理解和利用圖數(shù)據(jù)的豐富信息。在Graph Transformer中，圖的位置編碼（graph positional encoding）［24］是一種特殊的技術(shù)，旨在向模型提供圖中節(jié)點(diǎn)的位置或結(jié)構(gòu)上下文信息，幫助模型理解節(jié)點(diǎn)在圖中的相對或絕對位置。

在傳統(tǒng)的Transformer模型中，通常包括編碼器（encoder）和解碼器（decoder）兩個部分。然而，在Graph Transformer中，并不像序列到序列的任務(wù)那樣需要解碼器，因此通常將其稱為Graph Transformer的編碼器部分。

編碼器部分在Graph Transformer中負(fù)責(zé)對圖結(jié)構(gòu)數(shù)據(jù)進(jìn)行處理和特征提取，其基本結(jié)構(gòu)與傳統(tǒng)Transformer的編碼器相似，包括多層的自注意力機(jī)制，全連接前饋網(wǎng)絡(luò)等組件。表1展示Graph Transformer中的編碼器塊組件。

總而言之，編碼器塊的設(shè)計(jì)旨在充分利用圖結(jié)構(gòu)數(shù)據(jù)的特點(diǎn)，通過圖注意力機(jī)制、節(jié)點(diǎn)特征更新規(guī)則等組件，實(shí)現(xiàn)對節(jié)點(diǎn)之間復(fù)雜關(guān)系的建模和全局信息的整合。這些組件共同作用，使得Graph Transformer在處理圖數(shù)據(jù)任務(wù)時(shí)能夠更好地捕捉節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系和特征之間的依賴關(guān)系。

1.2 Graph Transformer層介紹

Graph Transformer層將Transformer架構(gòu)應(yīng)用于圖結(jié)構(gòu)數(shù)據(jù)的神經(jīng)網(wǎng)絡(luò)層。它結(jié)合了Transformer模型強(qiáng)大的序列建模能力和圖神經(jīng)網(wǎng)絡(luò)［25］處理圖結(jié)構(gòu)數(shù)據(jù)的能力，旨在提升對復(fù)雜圖結(jié)構(gòu)數(shù)據(jù)的建模效果。Graph Transformer層是圖神經(jīng)網(wǎng)絡(luò)中的一個核心組件，其結(jié)構(gòu)如圖3所示。Graph Transformer層可以使模型能從復(fù)雜的圖結(jié)構(gòu)中學(xué)習(xí)到有效的表示。表2展示了Graph Transformer層的關(guān)系和作用。

在整個Graph Transformer模型中，類似這樣的層可以被多次使用或與其他類型的圖處理層相結(jié)合，以解決特定的圖數(shù)據(jù)分析任務(wù)，如節(jié)點(diǎn)分類、鏈接預(yù)測或圖分類。這種模型架構(gòu)特別適合處理不同類型的節(jié)點(diǎn)和邊混合在一起的復(fù)雜圖結(jié)構(gòu)，如社交網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)或推薦系統(tǒng)中的用戶-物品交互網(wǎng)絡(luò)。

2 Graph Transformer模型應(yīng)用分類

本章將具體介紹Graph Transformer在處理典型圖數(shù)據(jù)任務(wù)中的應(yīng)用，Graph Transformer在實(shí)現(xiàn)其設(shè)計(jì)原理時(shí)的幾個關(guān)鍵優(yōu)化，包括注意力機(jī)制的優(yōu)化、模塊架構(gòu)層面的優(yōu)化，以及處理復(fù)雜圖的優(yōu)化。Graph Transformer的核心優(yōu)勢在于其自注意力機(jī)制的強(qiáng)大能力，通過動態(tài)地分配注意力權(quán)重，可以捕捉節(jié)點(diǎn)和邊之間的復(fù)雜關(guān)系。GNN模型通?；诠潭ǖ泥従泳酆蠙C(jī)制，而Graph Transformer則通過自注意力機(jī)制自適應(yīng)地調(diào)整不同節(jié)點(diǎn)間的依賴關(guān)系，使得模型在處理具有不同重要性關(guān)系的節(jié)點(diǎn)時(shí)表現(xiàn)出更強(qiáng)的靈活性。Graph Transformer在模塊架構(gòu)層面的改進(jìn)主要體現(xiàn)在其層次化設(shè)計(jì)和全局信息聚合能力上。與傳統(tǒng)的模型相比，Graph Transformer不僅在單層結(jié)構(gòu)上引入了注意力機(jī)制，還通過多層堆疊實(shí)現(xiàn)了更深層次的圖結(jié)構(gòu)信息聚合。在處理復(fù)雜圖結(jié)構(gòu)（如動態(tài)圖、超圖等）時(shí)，Graph Transformer的表現(xiàn)尤為出色。其自注意力機(jī)制不僅能夠處理靜態(tài)圖數(shù)據(jù)，還可以通過時(shí)間維度的擴(kuò)展，捕捉圖隨時(shí)間演變的動態(tài)變化。

2.1 Graph Transformer在注意力機(jī)制上的優(yōu)化

注意力機(jī)制的優(yōu)化對模型性能有著顯著的影響。在傳統(tǒng)的Graph Transformer模型中，注意力機(jī)制通常是均勻地對所有輸入數(shù)據(jù)進(jìn)行處理，這在處理圖結(jié)構(gòu)數(shù)據(jù)時(shí)可能不夠有效，因?yàn)閳D數(shù)據(jù)中節(jié)點(diǎn)間的關(guān)系是不規(guī)則且復(fù)雜的。通過引入注意力機(jī)制，可以更準(zhǔn)確地模擬節(jié)點(diǎn)間的關(guān)系強(qiáng)度，從而更好地捕捉圖中的結(jié)構(gòu)信息。這種針對性的優(yōu)化不僅提高了模型對圖數(shù)據(jù)的理解能力，還顯著提升了模型在圖相關(guān)任務(wù)上的表現(xiàn)，如節(jié)點(diǎn)分類、圖分類和鏈接預(yù)測等。此外，改進(jìn)的注意力機(jī)制還有助于提高模型的解釋性，使研究人員和實(shí)際應(yīng)用者能更好地理解模型的決策過程?？傊?，注意力機(jī)制的創(chuàng)新是推動Graph Transformer性能提升的關(guān)鍵因素之一。

Transformer架構(gòu)在自然語言處理和計(jì)算機(jī)視覺領(lǐng)域取得了顯著成功，但在圖表示學(xué)習(xí)任務(wù)中的表現(xiàn)一直不盡如人意。Graphormer ［26］通過有效地編碼圖的結(jié)構(gòu)信息，解決了 Transformer 在圖表示學(xué)習(xí)中表現(xiàn)不佳的問題。Graphormer是直接基于標(biāo)準(zhǔn)Transformer構(gòu)建的，通過引入幾種簡單但有效的結(jié)構(gòu)編碼方式來提高處理圖數(shù)據(jù)的能力。其核心創(chuàng)新在于其結(jié)構(gòu)編碼方法，主要包括中心性編碼、空間編碼和邊編碼。

a）中心性編碼（centrality encoding）。

用來捕捉圖中的節(jié)點(diǎn)重要性。利用度（degree）的中心性（centrality）來為每個節(jié)點(diǎn)編碼。每個節(jié)點(diǎn)會按照度的大小分配一個可學(xué)習(xí)的向量，并且向量會被加入到輸入層的節(jié)點(diǎn)特征中，式（2）則展示了此操作。

h（0）i=xi+z－deg－（vi）+z+deg+（vi）

（2）

其中：h（0）i是節(jié)點(diǎn)vi在輸入層的初始表示向量；xi是節(jié)點(diǎn)vi的原始特征向量；z－deg（vi）和z+deg（vi）分別表示節(jié)點(diǎn) vi的入度和出度，對應(yīng)可學(xué)習(xí)的嵌入向量，這些嵌入向量根據(jù)節(jié)點(diǎn)的度來分配。

b）空間編碼（spatial encoding）。

對于每個節(jié)點(diǎn)對，根據(jù)它們的空間關(guān)系分配一個可學(xué)習(xí)的嵌入。有多種測量方式可以用來進(jìn)行空間編碼，這里以兩節(jié)點(diǎn)間最短路徑的距離為例，它會被編碼為 softmax attention 中的偏置項(xiàng)（是個標(biāo)量），并幫助模型準(zhǔn)確地捕獲圖中的空間依賴關(guān)系。式（3）對應(yīng)Transformer的Q乘K并標(biāo)準(zhǔn)化的部分。

Aij=（hiWQ）（hjWK）Td+bφ（vi，vj）

（3）

其中：Aij表示節(jié)點(diǎn)vi和vj之間的注意力分?jǐn)?shù)；hi和hj分別表示節(jié)點(diǎn)vi和vj的特征向量；WQ和WK分別是查詢（query）和鍵（key）的投影矩陣；d是特征向量的維度平方根；φ（vi，vj）用于縮放，索引的可學(xué)習(xí)標(biāo)量，在所有層中共享。

c）邊編碼（edge encoding）。

在許多圖任務(wù)中，邊也具有結(jié)構(gòu)特征。Graphormer提出一種新的邊編碼方法，式（4）將邊的特征通過注意力機(jī)制整合進(jìn)模型，以提升對圖整體結(jié)構(gòu)的表示能力。

Aij=（hiWQ）（hjWK）Td+bφ（vi，vj）+cij，where，cij=1N∑Nn=1xen（wEn）T（4）

其中：Aij表示節(jié)點(diǎn)vi和vj之間的注意力分?jǐn)?shù)；cij是映入邊特征后的附加項(xiàng)；xen是最短路徑第n條邊的特征向量en；wEn是第n條邊的權(quán)重嵌入向量；dE是邊特征維度；N是最短路徑的邊數(shù)量。Graphormer通過引入中心性編碼、空間編碼和邊編碼，將圖的結(jié)構(gòu)信息有效地嵌入到Transformer模型中，在多個圖表示學(xué)習(xí)基準(zhǔn)任務(wù)中表現(xiàn)出色，顯著超過了主流的GNN變體，展示了Transformer架構(gòu)在圖表示學(xué)習(xí)任務(wù)中的巨大潛力。Graphormer和Rampáek等人［27］提出的GraphGPS都是專為圖結(jié)構(gòu)數(shù)據(jù)設(shè)計(jì)的高效Graph Transformer模型。然而，在處理大規(guī)模圖結(jié)構(gòu)時(shí)，GraphGPS展示了其獨(dú)特的優(yōu)勢。特別是，GraphGPS通過采用線性全局注意力機(jī)制［28］（如 Performer 或 BigBird［29］），有效地降低了計(jì)算復(fù)雜度。這種線性注意力機(jī)制與Graphormer通常使用的二次計(jì)算復(fù)雜度［30］的全連接注意力機(jī)制相比，大大減少了資源消耗和處理時(shí)間。因此，GraphGPS能夠擴(kuò)展到包含數(shù)千個節(jié)點(diǎn)的大圖，這種計(jì)算上的優(yōu)化使GraphGPS在實(shí)際應(yīng)用中，尤其是在需要處理大規(guī)模圖數(shù)據(jù)的領(lǐng)域（如社交網(wǎng)絡(luò)分析、大規(guī)模知識圖譜等），展現(xiàn)出更大的潛力和應(yīng)用價(jià)值。

在選擇模型時(shí)，如果是處理非常大的圖數(shù)據(jù)且主要關(guān)注計(jì)算效率，GraphGPS 的線性全局注意力提供了一個有效的解決方案。而如果應(yīng)用場景需要深入理解和分析圖中的復(fù)雜結(jié)構(gòu)和多層次關(guān)系，Shirzad等人［31］提出的EXPHORMER的表達(dá)式增強(qiáng)注意力機(jī)制則顯示出其在表達(dá)能力和模型精度上的明顯優(yōu)勢。

EXPHORMER通過引入一種專門為圖數(shù)據(jù)設(shè)計(jì)的Transformers框架，解決了傳統(tǒng)圖神經(jīng)網(wǎng)絡(luò)在可擴(kuò)展性方面的挑戰(zhàn)。其核心思想是利用擴(kuò)展圖［32］的概念，結(jié)合稀疏注意力機(jī)制［33］，以有效處理大規(guī)模和復(fù)雜的圖結(jié)構(gòu)。EXPHORMER的稀疏注意力框架針對圖中的關(guān)鍵連接和結(jié)構(gòu)模式，動態(tài)調(diào)整注意力分配，從而減少不必要的計(jì)算并優(yōu)化性能。這種方法不僅提高了模型的運(yùn)行效率，還保持了對圖的深層結(jié)構(gòu)和特征的敏感性，使得EXPHORMER能夠在保證高效處理的同時(shí)，更準(zhǔn)確地捕捉和理解圖中的復(fù)雜關(guān)系和動態(tài)變化。這一創(chuàng)新策略使得EXPHORMER在圖神經(jīng)網(wǎng)絡(luò)領(lǐng)域中，尤其是在處理規(guī)模龐大的圖數(shù)據(jù)時(shí)，展示顯著的優(yōu)勢和應(yīng)用潛力。圖4 EXPHORMER的稀疏注意力機(jī)制構(gòu)建了一個由三種類型的邊組成的交互圖。

a）圖4（a）強(qiáng)調(diào)每個節(jié)點(diǎn)與其直接相鄰節(jié)點(diǎn)之間的關(guān)系。EXPHORMER通過局部領(lǐng)域注意力，確保模型能夠捕捉節(jié)點(diǎn)的近鄰特征，這對于理解圖的局部結(jié)構(gòu)是至關(guān)重要的。

b）圖4（b）展示了節(jié)點(diǎn)之間更遠(yuǎn)距離的連接，用于編碼節(jié)點(diǎn)之間的間接關(guān)系。這種擴(kuò)展的鄰居注意力有助于模型理解圖中的路徑依賴性和節(jié)點(diǎn)間的遠(yuǎn)距離交互。

c）圖4（c）的中心節(jié)點(diǎn)與所有其他節(jié)點(diǎn)之間的直接連接表示全局注意力的結(jié)構(gòu)，這種注意力可能被用于衡量單個節(jié)點(diǎn)對整個圖的全局影響，有助于捕捉關(guān)鍵節(jié)點(diǎn)或樞紐節(jié)點(diǎn)的特性。

d）圖4（d）的結(jié)構(gòu)融合了局部領(lǐng)域、擴(kuò)展鄰居以及全局注意力，形成了一個多層次的交互圖。EXPHORMER利用這種復(fù)雜的組合來綜合不同層面的信息，提供一個全面的圖表示。這對于理解節(jié)點(diǎn)的綜合作用和圖中的復(fù)雜模式非常關(guān)鍵。

式（5）描述了EXPHORMER的注意力機(jī)制是如何計(jì)算節(jié)點(diǎn)的輸出特征向量的。具體來說，公式表示了如何將節(jié)點(diǎn)的自身特征與其鄰居節(jié)點(diǎn)的信息進(jìn)行整合，以生成新的節(jié)點(diǎn)特征。

ATTNH（X）：，i=xi+∑hj=1WjOWjVXNH（i）·σ（（WjEENH（i）WjKENH（i））T（WjQxi））

（5）

其中：ATTNH（X）：，i表示節(jié)點(diǎn)i的注意力機(jī)制的輸出；xi是節(jié)點(diǎn)i的輸入特征向量；h是注意力頭的數(shù)量；WjO、WjV、WjK、WjQ和WjE分別是輸出、值（value）、鍵（key）、查詢（query）和邊特征的權(quán)重矩陣；X是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)的特征矩陣；E是節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)的邊特征矩陣；表示元素逐個相乘（Hadamard積）；σ是激活函數(shù)（通常是softmax函數(shù)）。

Wu等人［34］提出的Nodeformer模型中介紹了基于Gumbel-Softmax操作［35］的核化方法，成功地將NodeFormer模型的算法復(fù)雜度從傳統(tǒng)的二次方復(fù)雜度降低至與節(jié)點(diǎn)數(shù)線性相關(guān)。這一突破性的改進(jìn)顯著提高了模型處理大規(guī)模圖數(shù)據(jù)的能力。該方法通過引入隨機(jī)特征映射［36］和近似采樣策略［37］，使得潛在的圖結(jié)構(gòu)學(xué)習(xí)可以通過梯度下降的方式進(jìn)行優(yōu)化，確保了學(xué)習(xí)過程的連續(xù)性和可微分性。這種核化Gumbel-Softmax操作不僅在數(shù)學(xué)上是合理的，還大幅度降低了計(jì)算資源的需求。因此，這種方法對于NodeFormer模型的影響是深遠(yuǎn)的，它不僅提升了模型在處理復(fù)雜圖結(jié)構(gòu)時(shí)的效率，而且也拓展了模型在實(shí)際應(yīng)用中的適用范圍。

NodeFormer模型的基本思路是采用隨機(jī)特征映射和Gumbel-Softmax兩種近似策略分別實(shí)現(xiàn)可擴(kuò)展和可微分的目的。從而實(shí)現(xiàn)了線性復(fù)雜度下的圖結(jié)構(gòu)可學(xué)習(xí)的大圖Transformer。下面介紹本文核心思路的公式推導(dǎo)。其更新公式為

z（l+1）u=∑Nu=1exp（（q（l）u）Τk（l）u）∑Nw=1exp（（q（l）u）Τk（l）w）·v（l）u

（6）

其中：z（l+1）u表示第l+1層中節(jié)點(diǎn)u的表示向量。k（l）u，q（l）u，v（l）u由第l層的特征變換得到（對應(yīng)Transformer里的key、query、value）。注意力權(quán)重通過對query和key的點(diǎn)積進(jìn)行softmax歸一化得到，表示節(jié)點(diǎn)u對v的關(guān)注程度。最終的節(jié)點(diǎn)表示z（l+1）u是所有v的value向量u（l）v加權(quán)求和的結(jié)果，加權(quán)系數(shù)為節(jié)點(diǎn)u對v的注意力權(quán)重。式（6）可以看作WT 把Transformer定義在圖上，即圖節(jié)點(diǎn)組成了很長一個輸入序列。

顯而易見，按照上式的定義，對于任意節(jié)點(diǎn)u都需要單獨(dú)計(jì)算其他N個節(jié)點(diǎn)的注意力z（l+1）u，因此更新所有N個節(jié)點(diǎn)需要O（N2）的復(fù)雜度。為了解決這一困難，對于任意節(jié)點(diǎn)u，找到在每一層中一個“最優(yōu)”的鄰居集合，進(jìn)行信息傳遞，就可以把N個節(jié)點(diǎn)產(chǎn)生的注意力權(quán)重視為一個categorical distribution，然后從中采樣得到鄰居集合。盡管采樣的過程不可求導(dǎo)，可以借助Gumbel-Softmax對其進(jìn)行近似處理，就是把式（6）中的Softmax替換為Gumbel-Softmax。具體操作為

z（l+1）u=∑Nu=1exp（（qΤuku+gv）/τ）∑Nw=1exp（（qΤukw+gw）/τ）·vu，gu～Gumbel（0，1）（7）

其中：gu～Gumbel（0，1）表示從Gumbel分布中抽樣得到的噪聲；τ是溫度參數(shù)，控制softmax的平滑度。

式（7）展示了一種通過全對消息傳遞機(jī)制實(shí)現(xiàn)高效節(jié)點(diǎn)表示更新的方法，通過引入Gumbel-Softmax重新參數(shù)化，能夠在保持連續(xù)近似的同時(shí)實(shí)現(xiàn)端到端的反向傳播，從而解決了在大規(guī)模圖中計(jì)算復(fù)雜度高和梯度消失的問題。Gumbel-Softmax重新參數(shù)化通過引入隨機(jī)噪聲，使得在訓(xùn)練過程中可以進(jìn)行有效的梯度優(yōu)化，同時(shí)保留了離散采樣的特性。優(yōu)化注意力機(jī)制顯著提升了模型在處理圖數(shù)據(jù)時(shí)的性能，尤其是在大規(guī)模圖上的節(jié)點(diǎn)分類任務(wù)中。通過引入全局自注意力、稀疏注意力和核化Gumbel-Softmax操作等方法，這些模型能夠有效降低計(jì)算復(fù)雜度，同時(shí)保持甚至增強(qiáng)了對圖結(jié)構(gòu)特征的敏感度。這種改進(jìn)的注意力機(jī)制不僅提高了模型對長距離依賴和復(fù)雜圖模式的捕捉能力，還使得模型更適合大規(guī)模和復(fù)雜的數(shù)據(jù)環(huán)境，極大地增強(qiáng)了圖神經(jīng)網(wǎng)絡(luò)的可擴(kuò)展性和魯棒性。

2.2 模塊架構(gòu)層面的優(yōu)化

Graph Transformer架構(gòu)采用模塊化設(shè)計(jì)，易于擴(kuò)展和優(yōu)化，如通過引入輕量化架構(gòu)、結(jié)構(gòu)集成方式等進(jìn)一步提升模型性能?？傮w而言，Graph Transformer在準(zhǔn)確性和計(jì)算效率方面的改進(jìn)，使其在處理各種圖結(jié)構(gòu)數(shù)據(jù)任務(wù)中表現(xiàn)出色。

Fu等人［39］提出的VCR-Graphormer的創(chuàng)新主要在于架構(gòu)層面，尤其是在高效小批量訓(xùn)練［40］的能力上作出了重大改進(jìn)。它通過結(jié)構(gòu)感知和內(nèi)容感知的虛擬連接，改進(jìn)了個性化Page-Rank［41］標(biāo)記化的圖Transformer框架。這種架構(gòu)允許VCR-Graphormer以遠(yuǎn)低于標(biāo)準(zhǔn)圖轉(zhuǎn)換器的計(jì)算復(fù)雜度處理大規(guī)模圖數(shù)據(jù)。具體來說，VCR-Graphormer 解決了以往圖轉(zhuǎn)換器在擴(kuò)展性和處理長距離交互［42］上的限制，引入了一種新的圖重連［43］方式，通過虛擬連接對圖進(jìn)行改造，以便在小批量訓(xùn)練中有效地編碼和利用節(jié)點(diǎn)的局部、全局、長距離和異質(zhì)性信息。

VCR-Graphormer通過基于結(jié)構(gòu)和內(nèi)容的超級節(jié)點(diǎn)引入多種類型的虛擬連接來重新連接圖，使PPRToken化能夠?qū)⒕植亢腿稚舷挛摹㈤L程交互和異質(zhì)信息編碼到每個節(jié)點(diǎn)的Token列表中?？偟膩碚f，與以前工作的O（n3）復(fù)雜度相比，VCR-Graphormer需要O（m+k log k）的復(fù)雜度進(jìn)行圖Token化。

VCR-Graphormer主要包括基于個性化PageRank（PPR）的圖Token化和基于虛擬連接的圖重連兩個關(guān)鍵技術(shù)。

對于目標(biāo)節(jié)點(diǎn)u，根據(jù)PPR公式計(jì)算其個性化PageRank向量ru。然后從ru中采樣得分最高的前k個節(jié)點(diǎn)，記為集合Rku。Rku中的節(jié)點(diǎn)及其對應(yīng)的PPR得分共同構(gòu)成了節(jié)點(diǎn)u的Token列表Tu，如式（8）所示。

（8）

其中：X（i，：）表示節(jié)點(diǎn)i的特征向量；ru（i）表示在ru中節(jié)點(diǎn)i對應(yīng)的PPR得分。將其整理成矩陣形式后，即可輸入到標(biāo)準(zhǔn)的自注意力機(jī)制以及池化函數(shù)［44］中，得到節(jié)點(diǎn)的表示向量。

為了將更多全局信息編碼到Token列表中，作者提出通過插入虛擬超級節(jié)點(diǎn)的方式來重新連接原圖，具體分為結(jié)構(gòu)感知型虛擬連接和內(nèi)容感知型虛擬連接兩類，如圖5所示。

圖5（a）展示了結(jié)構(gòu)感知超節(jié)點(diǎn)和虛擬連接的概念?？梢钥吹?，通過圖分割，不同的節(jié)點(diǎn)被分配到了不同的超節(jié)點(diǎn)，并通過虛擬連接與它們關(guān)聯(lián)。這些連接允許信息在圖中以一種高效的方式流動，使得遠(yuǎn)距離的節(jié)點(diǎn)（例如5跳鄰居）能夠更快地相互影響。圖5（b）展示了內(nèi)容感知超節(jié)點(diǎn)和虛擬連接。在這里，基于節(jié)點(diǎn)的標(biāo)簽或內(nèi)容，超節(jié)點(diǎn)被引入到圖中。每個超節(jié)點(diǎn)與具有相同標(biāo)簽的所有普通節(jié)點(diǎn)連接。表格列出了在引入這些超節(jié)點(diǎn)后，一些節(jié)點(diǎn)對之間距離的變化，其中紅色節(jié)點(diǎn)之間的距離有所縮短（見電子版）。這種方法可以增強(qiáng)圖數(shù)據(jù)在特征豐富度和異質(zhì)信息編碼方面的表達(dá)能力。

VCR-Graphormer通過虛擬連接和基于個性化PageRank的節(jié)點(diǎn)標(biāo)記列表，優(yōu)化了圖的小批量訓(xùn)練，能夠在批次中高效編碼節(jié)點(diǎn)表示，降低了傳統(tǒng)圖轉(zhuǎn)換器的計(jì)算復(fù)雜度。Wu等人［45］提出的SGFormer模型通過采用單層的簡單全局注意力機(jī)制［46］，在保持必要表現(xiàn)力的同時(shí)顯著降低了計(jì)算復(fù)雜度，實(shí)現(xiàn)了對大規(guī)模圖數(shù)據(jù)的高效處理。這種輕量化設(shè)計(jì)不需要位置編碼、額外的特征預(yù)處理或損失函數(shù)，使得SGFormer在各種節(jié)點(diǎn)屬性預(yù)測任務(wù)上表現(xiàn)出色，并能夠順利擴(kuò)展到擁有上億節(jié)點(diǎn)的圖，展示了其在處理大型圖結(jié)構(gòu)數(shù)據(jù)時(shí)的優(yōu)越性能和泛化能力［47］。VCR-Graphormer、SGformer都是針對處理大規(guī)模圖數(shù)據(jù)的Graph Transformer模型，它們通過不同的架構(gòu)創(chuàng)新來提高性能和擴(kuò)展性。Zhang等人［48］提出的TransGNN特別地結(jié)合了Transformer的全局信息聚合能力［49］和GNN的結(jié)構(gòu)感知能力［50］，通過交替使用這兩種層來增強(qiáng)模型的接收范圍和信息整合效率。這種集成方法使TransGNN在處理復(fù)雜的用戶-項(xiàng)目交互圖時(shí)，能夠有效地?cái)U(kuò)展傳統(tǒng)GNN模型的局限，提供更深入的結(jié)構(gòu)分析和更高的預(yù)測精度。TransGNN的主要優(yōu)點(diǎn)在于擴(kuò)大了GNN的接收域［51］，使得模型能從更遠(yuǎn)距離的節(jié)點(diǎn)聚集信息，從而提高信息的全局視野和相關(guān)性。此外，通過精心設(shè)計(jì)的位置編碼和節(jié)點(diǎn)采樣策略，TransGNN有效降低了計(jì)算復(fù)雜度，同時(shí)過濾掉噪聲和不相關(guān)的信息。這些創(chuàng)新使得TransGNN在多個公開數(shù)據(jù)集上顯示出顯著的性能提升，尤其是在節(jié)點(diǎn)分類和推薦任務(wù)中，展示其在處理大規(guī)模和結(jié)構(gòu)復(fù)雜的圖數(shù)據(jù)方面的出色能力和高效性。圖6展示了TransGNN的模型框架。

TransGNN結(jié)合了Transformer和GNN的優(yōu)勢，設(shè)計(jì)了子模塊：Transformer層，用于處理遠(yuǎn)距離依賴關(guān)系；GNN層，用于聚合鄰近節(jié)點(diǎn)的信息。

Transformer層：使用 Transformer 層來改進(jìn) GNN 層，將感受野擴(kuò)展到更相關(guān)的節(jié)點(diǎn)，這些節(jié)點(diǎn)可能遠(yuǎn)離鄰域。

q=hiWq，K=HSmpiWkV=HSmpiWv，at=qKTdout， hi=softmax（at）V

（9）

式（9）描述了Transformer層中計(jì)算注意力權(quán)重和聚合信息的過程。

GNN層：利用 GNN 層融合表示和圖結(jié)構(gòu)，幫助 Transfor-mer 層更好地利用圖結(jié)構(gòu)。

hM（vi）Message（hk，vk∈N（vi））， hi=Combine（hi，hM（vi））（10）

式（10）描述了在圖神經(jīng)網(wǎng)絡(luò)層中消息傳遞和節(jié)點(diǎn)表示更新的過程。

在TransGNN模型中，通過注意力機(jī)制計(jì)算中心節(jié)點(diǎn)與其注意力樣本節(jié)點(diǎn)的相關(guān)性，從而聚合最相關(guān)的節(jié)點(diǎn)信息來更新中心節(jié)點(diǎn)的表示；公式描述了在GNN層中，通過從鄰居節(jié)點(diǎn)聚合消息并結(jié)合中心節(jié)點(diǎn)當(dāng)前表示，進(jìn)一步更新節(jié)點(diǎn)表示。通過交替使用Transformer層和GNN層，TransGNN能夠有效地?cái)U(kuò)展接收域，捕捉到更全局和更局部的圖結(jié)構(gòu)信息，從而提升推薦系統(tǒng)的性能。在TransGNN模型中，通過交替整合Transfor-mer層和GNN層，實(shí)現(xiàn)了兩者的協(xié)同增強(qiáng)。與TransGNN相似的是，Chen等人［52］提出的結(jié)構(gòu)感知Transformer模型是將Transformer架構(gòu)與結(jié)構(gòu)感知模塊相結(jié)合的一種創(chuàng)新圖表示學(xué)習(xí)方法。該模型通過引入新的自注意力機(jī)制，將圖的結(jié)構(gòu)信息顯式地整合到Transformer中，以克服傳統(tǒng)GNN的局限性。具體來說，結(jié)構(gòu)感知Transformer在計(jì)算注意力之前，提取每個節(jié)點(diǎn)為根的子圖表示，這樣不僅保留了Transformer靈活處理節(jié)點(diǎn)間交互信息的優(yōu)勢，還增強(qiáng)了其對圖結(jié)構(gòu)的捕捉能力。通過這種結(jié)構(gòu)感知的自注意力機(jī)制，結(jié)構(gòu)感知Transformer在多個圖預(yù)測任務(wù)［53］中實(shí)現(xiàn)了性能的顯著提升，充分展示了將GNN的結(jié)構(gòu)表示能力與Transformer的全局注意力機(jī)制相結(jié)合的強(qiáng)大潛力。圖7描述了結(jié)構(gòu)感知Transformer（structure-aware Transformer， SAT）的整體架構(gòu)，并展示了其工作流程。圖中分為三個主要部分，依次為輸入圖、結(jié)構(gòu)提取器和Transformer層。

圖7展示了結(jié)構(gòu)感知Transformer如何通過結(jié)合Transformer架構(gòu)與結(jié)構(gòu)感知模塊，有效捕捉圖結(jié)構(gòu)數(shù)據(jù)的全局和局部信息。通過結(jié)構(gòu)提取器提取子圖并更新節(jié)點(diǎn)表示，再通過Transformer層進(jìn)行進(jìn)一步處理，實(shí)現(xiàn)了對圖數(shù)據(jù)的高效建模。

Graph Transformer的模塊架構(gòu)優(yōu)化顯著提升了模型在處理圖數(shù)據(jù)時(shí)的性能，尤其是在大規(guī)模圖上的推薦系統(tǒng)任務(wù)中。通過引入高效小批量訓(xùn)練、簡化全局注意力層和融合Transformer與GNN等方法，能夠有效降低計(jì)算復(fù)雜度，同時(shí)保持甚至增強(qiáng)了對圖結(jié)構(gòu)特征的敏感度。這種改進(jìn)的注意力機(jī)制不僅提高了模型對長距離依賴和復(fù)雜圖模式的捕捉能力，還使得模型更適合大規(guī)模和復(fù)雜的數(shù)據(jù)環(huán)境。

2.3 Graph Transformer應(yīng)用于復(fù)雜圖的改進(jìn)優(yōu)化

Graph Transformer在應(yīng)用于復(fù)雜圖［54］方面具有顯著優(yōu)勢。其核心在于自注意力機(jī)制，能夠在節(jié)點(diǎn)間靈活傳遞信息，捕捉到復(fù)雜圖結(jié)構(gòu)中的長距離依賴關(guān)系。這使得Graph Transformer在處理高維、非歐幾里德空間數(shù)據(jù)［55］時(shí)表現(xiàn)尤為出色。通過多頭注意力機(jī)制和位置編碼，模型可以更精確地理解圖節(jié)點(diǎn)和邊之間的關(guān)系。此外，其模塊化設(shè)計(jì)便于集成不同的圖卷積和聚合操作，從而提升處理能力和效率。Graph Transformer在處理復(fù)雜圖結(jié)構(gòu)時(shí)，具有出色的性能和適應(yīng)性。

超圖［56］是一種數(shù)學(xué)結(jié)構(gòu)，它擴(kuò)展了傳統(tǒng)圖的概念，允許一條邊連接兩個以上的頂點(diǎn)，這種邊被稱為超邊。這種結(jié)構(gòu)使得超圖非常適合表達(dá)多對多的關(guān)系，比如在一個網(wǎng)絡(luò)中表示多個人共同參與多個項(xiàng)目。超圖的這一特性使其在數(shù)據(jù)分析、網(wǎng)絡(luò)科學(xué)、組合優(yōu)化等領(lǐng)域有著廣泛的應(yīng)用，特別是在需要處理復(fù)雜關(guān)聯(lián)和群組交互的場景中，超圖能提供比傳統(tǒng)圖更豐富和靈活的表達(dá)能力。圖8展示了一個超圖，包含多個超邊和超節(jié)點(diǎn)（見電子版）。在圖8中，顏色區(qū)域表示不同的超邊，每個超邊覆蓋了其包含的超節(jié)點(diǎn)。具體來說，黃色區(qū)域代表超邊e1（覆蓋節(jié)點(diǎn)v1和v2），紅色區(qū)域代表超邊e2（覆蓋節(jié)點(diǎn)v2和v3），綠色區(qū)域代表超邊e3（覆蓋節(jié)點(diǎn)v3、v5和v6），藍(lán)色區(qū)域代表超邊e4（覆蓋節(jié)點(diǎn)v4）。超節(jié)點(diǎn)v7沒有被任何超邊覆蓋。該超圖示例展示了如何通過超邊連接多個節(jié)點(diǎn)，從而揭示節(jié)點(diǎn)之間復(fù)雜的高階關(guān)系。

Yang等人［57］提出了一個多行為超圖增強(qiáng)的Transformer框架（MBHT），專門用于序列推薦系統(tǒng)［58］。該模型主要針對在線平臺用戶交互行為的動態(tài)和多樣性，通過超圖和Transformer的結(jié)合來捕獲用戶與項(xiàng)目間的復(fù)雜關(guān)系。具體來說，MBHT通過多尺度Transformer［59］來編碼細(xì)粒度和粗粒度的序列模式，并利用超圖神經(jīng)網(wǎng)絡(luò)架構(gòu)來建模全局的多行為依賴關(guān)系，這樣可以有效地學(xué)習(xí)長期和跨類型的項(xiàng)目相關(guān)性。此外，該框架還引入了低秩自注意力機(jī)制［60］來提高序列模式編碼的效率。實(shí)驗(yàn)表明，MBHT在多個公開數(shù)據(jù)集上相比于其他先進(jìn)的推薦系統(tǒng)方法表現(xiàn)出優(yōu)越的性能，驗(yàn)證了其在處理復(fù)雜用戶行為動態(tài)方面的有效性。動態(tài)圖［61］的建模關(guān)鍵在于捕捉圖結(jié)構(gòu)隨時(shí)間的演變，這對于理解社交網(wǎng)絡(luò)的擴(kuò)展、推薦系統(tǒng)的適時(shí)響應(yīng)等應(yīng)用至關(guān)重要。在這一背景下，Wu等人［62］提出的SimpleDyG模型提供了一種簡化的解決方案，它通過原生的Transformer架構(gòu)，不需要額外的復(fù)雜修改就能有效地處理動態(tài)圖數(shù)據(jù)。SimpleDyG通過將動態(tài)圖視為序列建模問題，并引入時(shí)間對齊技術(shù)［63］，實(shí)現(xiàn)了對動態(tài)圖中時(shí)間演變模式的有效捕捉。這種方法不僅簡化了動態(tài)圖的處理流程，還提高了模型在多個真實(shí)世界動態(tài)圖數(shù)據(jù)集上的性能，展示了其在動態(tài)網(wǎng)絡(luò)分析領(lǐng)域的應(yīng)用潛力。其模型框架如圖9所示。

圖9概述了一種用于動態(tài)圖建模的Transformer架構(gòu)SimpleDyG。從一個實(shí)例動態(tài)圖開始，它首先創(chuàng)建了一系列時(shí)間自我中心圖，這些圖捕捉了與每個中心節(jié)點(diǎn)隨時(shí)間發(fā)生交互的節(jié)點(diǎn)。隨后，引入了時(shí)間對齊的概念，使用時(shí)間標(biāo)記將歷史交互分割成連續(xù)的時(shí)間段，從而對不同節(jié)點(diǎn)的交互歷史進(jìn)行編碼。這些經(jīng)時(shí)間對齊的序列最后輸入到一個標(biāo)準(zhǔn)的Transformer架構(gòu)中，Transformer利用其多頭注意力和前饋網(wǎng)絡(luò)來學(xué)習(xí)和預(yù)測節(jié)點(diǎn)隨時(shí)間的行為和交互。整個過程強(qiáng)調(diào)了時(shí)間信息在捕捉動態(tài)圖結(jié)構(gòu)變化中的重要性，并展示了如何將動態(tài)圖數(shù)據(jù)轉(zhuǎn)換為Transformer能有效處理的格式。

分子圖［64］是一種用圖的形式來表示分子結(jié)構(gòu)的方法，其中節(jié)點(diǎn)代表原子，邊代表原子間的化學(xué)鍵。傳統(tǒng)的分子表示方法通常只針對特定的數(shù)據(jù)格式（如2D或3D結(jié)構(gòu)）進(jìn)行設(shè)計(jì)，無法在不同數(shù)據(jù)格式之間通用。為克服這一限制，Luo等人［65］提出了Transformer-M模型，這是一種基于Transformer的通用分子模型，通過設(shè)計(jì)獨(dú)立的通道分別編碼2D和3D結(jié)構(gòu)信息，并結(jié)合原子特征，使其能夠同時(shí)處理和理解2D和3D形式的分子數(shù)據(jù)。其模型架構(gòu)如圖10所示。

Transformer-M模型通過將2D和3D結(jié)構(gòu)信息作為偏置項(xiàng)加入到注意力機(jī)制中，從而在處理2D和3D分子數(shù)據(jù)時(shí)，能夠捕捉到更加豐富的結(jié)構(gòu)信息。這種設(shè)計(jì)使得模型可以同時(shí)處理和理解不同模態(tài)的分子數(shù)據(jù)。式（11）展示了Transformer-M模型中的注意力矩陣計(jì)算公式。

A（X）=softmax（XWQ（XWK）Td+φSPD+φEdge+φ3D distance）（11）

其中：X表示輸入特征矩陣；WQ和WK是用于計(jì)算查詢（query）和鍵（key）的權(quán)重矩陣；d是特征維度；φSPD表示最短路徑距離編碼（shortest path distance encoding），用于2D分子圖結(jié)構(gòu)；φEdge表示邊編碼（edge encoding），用于2D分子圖結(jié)構(gòu)；φ3D distance表示3D距離編碼（3D distance encoding），用于3D分子幾何結(jié)構(gòu)。

通過結(jié)合Transformer的自注意力機(jī)制和多種結(jié)構(gòu)信息編碼方法，Transformer-M模型能夠同時(shí)處理和理解2D和3D分子數(shù)據(jù)，展示了其在廣泛化學(xué)任務(wù)中的強(qiáng)大性能和廣泛適用性。這為開發(fā)通用的分子模型提供了新的途徑，有助于推動化學(xué)和材料科學(xué)領(lǐng)域的研究和應(yīng)用。

Transformer在處理復(fù)雜圖數(shù)據(jù)方面展現(xiàn)出獨(dú)特的優(yōu)勢，尤其是其自注意力機(jī)制能夠捕獲長距離的節(jié)點(diǎn)間依賴，這對于理解圖的深層次結(jié)構(gòu)和動態(tài)變化至關(guān)重要。無論是靜態(tài)圖的結(jié)構(gòu)化特征學(xué)習(xí)，還是動態(tài)圖中隨時(shí)間演進(jìn)的復(fù)雜交互模式識別，Transformer都能通過靈活的序列處理能力，提供精確且深入的圖表示，為社交網(wǎng)絡(luò)分析、推薦系統(tǒng)、知識圖譜等領(lǐng)域帶來了革命性的影響。其強(qiáng)大的表征學(xué)習(xí)能力和對時(shí)間動態(tài)的敏感捕捉，讓Transformer成為了復(fù)雜圖數(shù)據(jù)分析的強(qiáng)有力工具。

3 Graph Transformer性能分析

本章介紹了Graph Transformer模型在大型圖、復(fù)雜圖上的性能分析。需要說明的是，在不同類型圖數(shù)據(jù)的性能評估中，模型指標(biāo)均來自現(xiàn)有論文，考慮到不同方法在圖結(jié)構(gòu)捕捉、節(jié)點(diǎn)關(guān)系建模以及長距離依賴關(guān)系處理等方面存在差異，因此評估分析中的數(shù)據(jù)不完全適用于不同類型方法之間的性能優(yōu)劣比較。Graph Transformer通過自注意力機(jī)制、多頭注意力和位置編碼等設(shè)計(jì)，在處理大型圖和復(fù)雜圖時(shí)展現(xiàn)出顯著的優(yōu)勢，尤其在捕捉長距離依賴關(guān)系和復(fù)雜結(jié)構(gòu)信息方面表現(xiàn)突出。

3.1 大規(guī)模圖數(shù)據(jù)性能分析

大型圖［66］指的是包含大量節(jié)點(diǎn)和邊的圖結(jié)構(gòu)數(shù)據(jù)，這些數(shù)據(jù)常見于各種復(fù)雜網(wǎng)絡(luò)中，如社交網(wǎng)絡(luò)、知識圖譜、生物分子網(wǎng)絡(luò)和金融交易網(wǎng)絡(luò)。大型圖的特點(diǎn)在于節(jié)點(diǎn)數(shù)目龐大、連接關(guān)系復(fù)雜、數(shù)據(jù)維度高，因此在信息存儲、傳遞和計(jì)算過程中面臨著顯著的挑戰(zhàn)。Graph Transformer在大型圖上的應(yīng)用相對于傳統(tǒng)方法具有顯著優(yōu)勢，其自注意力機(jī)制能夠有效捕捉節(jié)點(diǎn)間的長距離依賴關(guān)系和復(fù)雜連接結(jié)構(gòu)。在大型圖的實(shí)驗(yàn)中，主要在六個廣泛使用的數(shù)據(jù)集上評估模型的性能。這些數(shù)據(jù)集包括PubMed［67］、CoraFull、Computer、Photo、CS和Physics，它們分別涵蓋了生物醫(yī)學(xué)文獻(xiàn)、計(jì)算機(jī)科學(xué)文獻(xiàn)、圖像數(shù)據(jù)以及物理學(xué)文獻(xiàn)。這些數(shù)據(jù)集廣泛應(yīng)用于自然語言處理和圖神經(jīng)網(wǎng)絡(luò)研究中，用于訓(xùn)練和評估各種機(jī)器學(xué)習(xí)模型。表3概述了大型圖數(shù)據(jù)集。圖11對每個Graph Transformer改進(jìn)模型（GT、SAN、GraphGPS、NAGphormer、Exphormer、VCR-Graphormer）在各個數(shù)據(jù)集中的評估指標(biāo)進(jìn)行了描述（其中橫坐標(biāo)為模型方法，縱坐標(biāo)為評估指標(biāo)）。這些評估指標(biāo)值能夠幫助讀者在今后選擇實(shí)驗(yàn)?zāi)Ｐ蜁r(shí)選擇最優(yōu)的模型。

3.2 復(fù)雜圖數(shù)據(jù)性能分析

Graph Transformer通過自注意力機(jī)制提供了強(qiáng)大的全局信息聚合能力、并行計(jì)算效率和靈活的建模能力，使其在處理復(fù)雜的超圖結(jié)構(gòu)時(shí)具有顯著優(yōu)勢。在超圖的實(shí)驗(yàn)中，主要在三個廣泛使用的數(shù)據(jù)集上評估模型的性能。這些數(shù)據(jù)集包括Taobao、Retailrocket和IJCAI，它們分別用于評估推薦系統(tǒng)的性能。Taobao數(shù)據(jù)集來源于阿里巴巴的電商平臺，包含用戶的點(diǎn)擊、購買和評價(jià)行為。Retailrocket數(shù)據(jù)集來源于Retailrocket平臺，記錄了用戶的瀏覽、點(diǎn)擊和購買行為。IJCAI數(shù)據(jù)集則是國際人工智能聯(lián)合會議發(fā)布的，用于各種人工智能任務(wù)的競賽數(shù)據(jù)。這些數(shù)據(jù)集通過HR@5、NDCG@5、HR@10、NDCG@10和MRR等指標(biāo)來評估推薦系統(tǒng)的效果和準(zhǔn)確性，表4解釋了性能指標(biāo)，表5概述了超圖數(shù)據(jù)集。

表4中DGC@5=∑5i－1relilog2（i+1），DGC@10=∑10i－1relilog2（i+1），IDCG為理想DCG的值。

在圖12中，對每個Graph Transformer改進(jìn)模型（BERT4Rec-MB、MB-GCN、NMTR、MB-GMN、MNHT）在各個超圖數(shù)據(jù)集（Taobao、Retailrocket和IJCAI）中的評估指標(biāo)進(jìn)行了描述（其中橫坐標(biāo)為模型方法，縱坐標(biāo)為評估指標(biāo)）。這些評估指標(biāo)值能夠幫助讀者在今后選擇超圖實(shí)驗(yàn)?zāi)Ｐ蜁r(shí)選擇最優(yōu)的模型。

3.3 動態(tài)圖數(shù)據(jù)性能分析

Graph Transformer通過自注意力機(jī)制可以捕捉節(jié)點(diǎn)之間復(fù)雜的全局依賴關(guān)系，而不僅僅局限于局部鄰居信息，從而在動態(tài)圖中更準(zhǔn)確地反映節(jié)點(diǎn)狀態(tài)的動態(tài)變化。在動態(tài)圖的實(shí)驗(yàn)中，主要在四個廣泛使用的數(shù)據(jù)集上評估模型的性能。這些數(shù)據(jù)集包括UCI、ML-10M、Hepth和MMConv，各自用于不同的研究領(lǐng)域。UCI數(shù)據(jù)集來自加利福尼亞大學(xué)歐文分校的機(jī)器學(xué)習(xí)庫，涵蓋多種任務(wù)如分類、回歸和聚類；ML-10M是Movie-Lens的一個子集，包含用戶對電影的評分記錄，主要用于推薦系統(tǒng)研究；Hepth數(shù)據(jù)集用于社交網(wǎng)絡(luò)分析，包含科學(xué)合作網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊信息；MMConv數(shù)據(jù)集是多模態(tài)對話數(shù)據(jù)集，包含對話內(nèi)容和多模態(tài)信息，用于研究多模態(tài)對話系統(tǒng)，表6概述了動態(tài)圖數(shù)據(jù)集。

在圖13中，對每個Graph Transformer改進(jìn)模型（DyRep、JODIE、TGAT、TGN、TREND、GraphMixer、SimpleDyG）在各個動態(tài)圖數(shù)據(jù)集（UCI、ML-10M、Hepth和MMConv）中的評估指標(biāo)進(jìn)行了描述（其中橫坐標(biāo)為模型方法，縱坐標(biāo)為評估指標(biāo)）。這些評估指標(biāo)值能夠幫助讀者在今后選擇實(shí)驗(yàn)?zāi)Ｐ蜁r(shí)選擇最優(yōu)的模型。

在動態(tài)圖中主要以NDCG@5=DGC@5IDCG@5作為評估推薦系統(tǒng)性能的指標(biāo)，特別適用于衡量推薦結(jié)果的排序質(zhì)量。

4 Graph Transformer在不同領(lǐng)域的應(yīng)用分類

Graph Transformer作為一種結(jié)合了圖神經(jīng)網(wǎng)絡(luò)和Transformer架構(gòu)的先進(jìn)模型，充分利用了圖結(jié)構(gòu)數(shù)據(jù)的特性。通過在圖節(jié)點(diǎn)間動態(tài)地計(jì)算注意力權(quán)重，Graph Transformer能夠有效地處理和解析節(jié)點(diǎn)間的復(fù)雜關(guān)系，這在許多領(lǐng)域中顯示出了巨大的潛力。表7詳細(xì)介紹Graph Transformer在多個關(guān)鍵領(lǐng)域中的應(yīng)用，包括生物信息學(xué)中的蛋白質(zhì)結(jié)構(gòu)預(yù)測、社交網(wǎng)絡(luò)的用戶行為分析、推薦系統(tǒng)的優(yōu)化、文本生成，以及金融領(lǐng)域的欺詐檢測。通過探索這些應(yīng)用，不僅能夠看到Graph Transformer技術(shù)的強(qiáng)大能力，也能理解它在未來數(shù)據(jù)科學(xué)和人工智能領(lǐng)域中的應(yīng)用前景。

Graph Transformer技術(shù)在多個領(lǐng)域中展示了其強(qiáng)大的應(yīng)用潛力和靈活性。在化學(xué)領(lǐng)域，如MAT和GROVER所示，Graph Transformer被用于分子結(jié)構(gòu)的表征和預(yù)測，幫助科學(xué)家更好地理解分子間的相互作用和藥物活性。在生物信息學(xué)中，如scMoFormer所示，它被用于處理復(fù)雜的單細(xì)胞數(shù)據(jù)，提供細(xì)胞類型的詳細(xì)分類和功能解析。此外，在處理復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)的數(shù)據(jù)分析方面，如HGT和HeGT所示，Graph Transformer能有效地處理和分析異構(gòu)圖，這對于增強(qiáng)節(jié)點(diǎn)和邊的特征學(xué)習(xí)，提高數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的效率至關(guān)重要?？傮w而言，Graph Transformer為處理結(jié)構(gòu)化數(shù)據(jù)提供了一種高效和可擴(kuò)展的方法，廣泛適用于科學(xué)研究和工業(yè)應(yīng)用中的多個領(lǐng)域。

5 總結(jié)與展望

Graph Transformer模型是一種專門用于處理圖結(jié)構(gòu)數(shù)據(jù)的深度學(xué)習(xí)架構(gòu)。通過將Transformer模型的自注意力機(jī)制引入圖數(shù)據(jù)處理領(lǐng)域，Graph Transformer在社交網(wǎng)絡(luò)分析、分子建模、知識圖譜等方面展示了其強(qiáng)大的功能和優(yōu)勢。其基本原理是通過將Transformer模型的自注意力機(jī)制應(yīng)用于圖數(shù)據(jù)，使每個節(jié)點(diǎn)在計(jì)算表示時(shí)能夠關(guān)注整個圖的所有節(jié)點(diǎn)。其詳細(xì)結(jié)構(gòu)包括輸入層接收節(jié)點(diǎn)和邊特征，自注意力層利用多頭注意力機(jī)制更新節(jié)點(diǎn)表示，位置編碼層融入圖結(jié)構(gòu)信息，最終通過輸出層完成特定任務(wù)如節(jié)點(diǎn)分類和圖分類。本文深入探討了Graph Transformer模型的發(fā)展背景、基本原理及其詳細(xì)結(jié)構(gòu)。表8～10對這些方法的優(yōu)缺點(diǎn)進(jìn)行了總結(jié)和歸納。

Graph Transformer盡管取得了顯著成就，但在面對極大規(guī)模圖數(shù)據(jù)時(shí)的計(jì)算效率、長距離依賴和可解釋性方面仍存在挑戰(zhàn)。

a）Graph Transformer 模型在處理大規(guī)模圖數(shù)據(jù)時(shí)常面臨計(jì)算復(fù)雜性問題，主要體現(xiàn)在自注意力機(jī)制的時(shí)間和空間復(fù)雜度上。具體而言，傳統(tǒng)的自注意力機(jī)制的計(jì)算復(fù)雜度為O（N2·d），其中N是節(jié)點(diǎn)數(shù)量，d是節(jié)點(diǎn)特征維度。這意味著隨著節(jié)點(diǎn)數(shù)量的增加，計(jì)算和存儲需求迅速增加，限制了模型的可擴(kuò)展性。為了解決這一問題，可以采用稀疏注意力機(jī)制、局部上下文建?；驁D采樣技術(shù)，減少計(jì)算負(fù)擔(dān)，從而在保持模型性能的同時(shí)，顯著提高效率。這些方法通過限制注意力計(jì)算的范圍或選擇重要的子圖來降低復(fù)雜性，使得 Graph Transformer 能夠更有效地處理大規(guī)模圖數(shù)據(jù)。

b）長距離依賴問題，盡管Transformer在處理序列數(shù)據(jù)時(shí)表現(xiàn)良好，但在圖數(shù)據(jù)中，由于節(jié)點(diǎn)之間的連接可能是稀疏的，如何捕捉長范圍依賴關(guān)系仍然是一個難題。解決 Graph Transformer 中的長距離依賴問題可以通過引入全局信息傳播機(jī)制和改進(jìn)的注意力機(jī)制。盡管圖中的節(jié)點(diǎn)連接可能稀疏，但可以通過添加跨圖注意力機(jī)制，允許節(jié)點(diǎn)在計(jì)算時(shí)關(guān)注非直接鄰居，從而捕捉更遠(yuǎn)的依賴關(guān)系。此外，結(jié)合圖卷積網(wǎng)絡(luò)或基于池化的結(jié)構(gòu)，可以在多個層次上聚合信息，使得節(jié)點(diǎn)不僅依賴于直接鄰居，還能整合更遠(yuǎn)節(jié)點(diǎn)的特征。這種多層次的信息傳播方式有助于有效捕捉長距離依賴，提升模型在復(fù)雜圖數(shù)據(jù)上的表現(xiàn)。

c）Graph Transformer的可解釋性問題主要在于其復(fù)雜的自注意力機(jī)制使得很難直觀理解模型如何作出特定的預(yù)測。為了提升模型的解釋性，可以采用幾種策略：首先，引入注意力可視化技術(shù)，通過分析注意力權(quán)重來識別模型在決策過程中關(guān)注的節(jié)點(diǎn)和邊；其次，結(jié)合圖卷積網(wǎng)絡(luò)等結(jié)構(gòu)，利用局部特征聚合的方式使模型更加透明；此外，應(yīng)用特征重要性評分方法［68］（如 SHAP 或 LIME），幫助量化各特征對最終預(yù)測的貢獻(xiàn)。這些方法能夠提供對 Graph Transformer 決策過程的洞察，增強(qiáng)模型的可解釋性，從而提高用戶對其預(yù)測結(jié)果的信任度。

Graph Transformer作為圖神經(jīng)網(wǎng)絡(luò)領(lǐng)域的新興方法，具有廣闊的發(fā)展前景。以下是一些未來的研究方向和應(yīng)用前景：

a）Graph Transformer在模型優(yōu)化方向的研究正迅速成為一個重要領(lǐng)域。其自注意力機(jī)制能夠靈活捕捉節(jié)點(diǎn)間的長距離依賴關(guān)系，通過進(jìn)一步優(yōu)化模型結(jié)構(gòu)，如引入稀疏注意力和圖卷積融合，Graph Transformer 可以在保持高準(zhǔn)確性的同時(shí)顯著提高計(jì)算效率和可擴(kuò)展性。此外，針對特定任務(wù)進(jìn)行微調(diào)和自適應(yīng)學(xué)習(xí)，也為其在實(shí)際應(yīng)用中提供了更多靈活性和適應(yīng)性。這些優(yōu)勢使得 Graph Transformer 在圖數(shù)據(jù)處理和理解上具有重要的研究價(jià)值和商業(yè)應(yīng)用潛力。

b）Graph Transformer 與其他技術(shù)的結(jié)合（CNN、Mamba［69］等技術(shù)）正迅速成為一個重要領(lǐng)域，尤其是在提升模型性能和應(yīng)用范圍方面。通過將 Graph Transformer 與卷積神經(jīng)網(wǎng)絡(luò)相結(jié)合，可以利用 CNN 的局部特征提取能力，同時(shí)保持圖數(shù)據(jù)的結(jié)構(gòu)信息。此外，與 Mamba 技術(shù)相結(jié)合，Graph Transformer 可以通過 Mamba 的高效并行計(jì)算和低延遲通信機(jī)制，顯著提升大規(guī)模圖數(shù)據(jù)處理的計(jì)算速度和效率。通過這些跨學(xué)科的技術(shù)融合，Graph Transformer 有望在處理復(fù)雜圖數(shù)據(jù)的任務(wù)中展現(xiàn)出更高的靈活性和效率，推動各類應(yīng)用的創(chuàng)新發(fā)展。

c）Graph Transformer 的應(yīng)用前景十分廣泛，尤其在社交網(wǎng)絡(luò)分析、推薦系統(tǒng)、生物信息學(xué)、金融風(fēng)控和知識圖譜等領(lǐng)域展現(xiàn)出巨大潛力。憑借其強(qiáng)大的自注意力機(jī)制，Graph Transfor-mer 能夠有效捕捉圖中復(fù)雜的節(jié)點(diǎn)關(guān)系和長距離依賴，為用戶提供更準(zhǔn)確的預(yù)測和個性化推薦。此外，在處理大規(guī)模和動態(tài)圖數(shù)據(jù)時(shí)，通過優(yōu)化模型的可擴(kuò)展性和計(jì)算效率，Graph Transformer 有望推動智能城市、智慧醫(yī)療等領(lǐng)域的發(fā)展。隨著研究的深入和技術(shù)的成熟，Graph Transformer 將在實(shí)際應(yīng)用中發(fā)揮越來越重要的作用，推動圖數(shù)據(jù)分析的進(jìn)步。

參考文獻(xiàn)：

［1］Diestel R. Graph theory［M］. Berlin：Springer， 2024.

［2］Wang Junjie， Gao Hao， Han Yu，et al. MAGUS： machine learning and graph theory assisted universal structure searcher ［J］. National Science Review， 2023， 10（7）： nwad128.

［3］Zhang Wei， Zhang Mingyang， Yuan Ling，et al. Social network analysis and public policy： what’s new？ ［J］. Journal of Asian Public Policy， 2023， 16（2）： 115-145.

［4］Vullam N， Vellela S S， Reddy V，et al. Multi-agent personalized re-commendation system in e-commerce based on user［C］// Proc of the 2nd International Conference on Applied Artificial Intelligence and Computing. Piscataway，NJ：IEEE Press， 2023： 1194-1199.

［5］He Shufei， Feng Likui， Zhao Weixin，et al. Composition and molecular structure analysis of hydrophilic/hydrophobic extracellular polymeric substances （EPS） with impacts on sludge dewaterability ［J］. Chemical Engineering Journal， 2023， 462： 142234.

［6］Wu Zonghan， Pan Shirui， Chen Fengwen，et al. A comprehensive survey on graph neural networks ［J］. IEEE Trans on Neural Networks and Learning Systems， 2020， 32（1）： 4-24.

［7］Li Zewen， Yang Wenjie， Peng Shouheng，et al. A survey of convolutional neural networks： analysis， applications， and prospects ［J］. IEEE Trans on Neural Networks and Learning Systems， 2021， 33（12）： 6999-7019.

［8］Yao Liang， Mao Chengsheng， Luo Yuan. Graph convolutional networks for text classification［C］// Proc of AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2019： 7370-7377.

［9］Zhang Shijie， Yin Hongzhi， Chen Tong，et al. Graph embedding for recommendation against attribute inference attacks［C］// Proc of Web Conference. 2021： 3002-3014.

［10］Zhang Yichi， Tang M. A theoretical analysis of DeepWalk and node2vec for exact recovery of community structures in stochastic blockmodels ［J］. IEEE Trans on Pattern Analysis and Machine Intelligence， 2023，46（2）： 1065-1078.

［11］Xiao Fang， Yu Siyuan， Li Yuze. Efficient large-capacity caching in cloud storage using skip-gram-based file correlation analysis ［J］. IEEE Access， 2023， 11： 111265-111273.

［12］Han Kai， Xiao An， Wu Enhua，et al. Transformer in Transformer［C］// Advances in Neural Information Processing Systems. 2021： 15908-15919.

［13］Yun S， Jeong M， Kim R，et al. Graph Transformer networks［C］// Advances in Neural Information Processing Systems. 2019.

［14］Zhang Xuan， Chen Cheng， Meng Zhaoxu，et al. CoAtGIN： marrying convolution and attention for graph-based molecule property prediction［C］// Proc of IEEE International Conference on Bioinformatics and Biomedicine. Piscataway，NJ：IEEE Press， 2022： 374-379.

［15］Li Wenbo， Lin Zhe， Zhou Kun，et al. MAT： mask-aware Transformer for large hole image inpainting［C］// Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022： 10758-10768.

［16］Yu Rong， Bian Yatao， Xu Tingyang，et al. Self-supervised graph Transformer on large-scale molecular data［C］// Advances in Neural Information Processing Systems. 2020： 12559-12571.

［17］Tang Wenzhuo， Wen Hongzhi， Liu Renming，et al. Single-cell multimodal prediction via Transformers［C］// Proc of the 32nd ACM International Conference on Information and Knowledge Management. New York：ACM Press，2023： 2422-2431.

［18］Hu Ziniu， Dong Yuxiao， Wang Kuansan，et al. Heterogeneous graph Transformer［C］// Proc of Web Conference. 2020： 2704-2710.

［19］Yao Shaowei， Wang Tianming， Wan Xiaojun. Heterogeneous graph Transformer for graph-to-sequence learning［C］// Proc of the 58th Annual Meeting of the Association for Computational Linguistics. 2020： 7145-7154.

［20］Wei Siqi， Wu Bin， Xiang Aoxue，et al. DGTR： dynamic graph Transformer for rumor detection ［J］. Frontiers in Research Metrics and Analytics， 2023， 7： 1055348.

［21］Liu Xiao， Zhao Shiyu， Su Kai，et al. Mask and reason： pre-training knowledge graph Transformers for complex logical queries［C］// Proc of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York：ACM Press， 2022： 1120-1130.

［22］Vaswani A， Shazeer N， Parmar N，et al. Attention is all you need［C］// Advances in Neural Information Processing Systems. 2017.

［23］Rodrigues M， Santos M Y， Bernardino J. Big data processing tools：an experimental performance evaluation ［J］. Wiley Interdisciplinary Reviews： Data Mining and Knowledge Discovery， 2019， 9（2）： e1297.

［24］Park W， Chang W， Lee D， et al. GRPE： relative positional encoding for graph Transformer ［EB/OL］. （2022）.https：//arxiv.org/abs/2201. 12787.

［25］Zhou Jie， Cui Ganqu， Hu Shengding，et al. Graph neural networks： a review of methods and applications ［J］. AI Open， 2020， 1： 57-81.

［26］Ying Chengxuan， Cai Tianle， Luo Shengjie，et al. Do Transformers really perform badly for graph representation？［C］// Advances in Neural Information Processing Systems. 2021： 28877-28888.

［27］Rampáek L， Galkin M， Dwivedi V P，et al. Recipe for a general， powerful， scalable Graph Transformer［C］// Advances in Neural Information Processing Systems. 2022： 14501-14515.

［28］Li Rui， Su Jianlin， Duan Chenxi，et al. Linear attention mechanism： an efficient attention for semantic segmentation ［EB/OL］. （2020）. https：//arxiv.org/abs/2007.14902.

［29］Zaheer M， Guruganesh G， Dubey K A，et al. Big bird： Transformers for longer sequences［C］// Advances in Neural Information Processing Systems. 2020： 17283-17297.

［30］Nguyen P Q， Stehlé D. An LLL algorithm with quadratic complexity ［J］. SIAM Journal on Computing， 2009， 39（3）： 874-903.

［31］Shirzad H， Velingker A， Venkatachalam B，et al. Exphormer： sparse Transformers for graphs［C］//Proc of International Conference on Machine Learning. 2023： 31613-31632.

［32］Khler E， Langkau K， Skutella M. Time-expanded graphs for flow-dependent transit times［C］//Proc of the 10th Annual European Symposium on Algorithms. Berlin： Springer， 2002： 599-611.

［33］Martins A， Farinhas A， Treviso M，et al. Sparse and continuous attention mechanisms［C］// Advances in Neural Information Processing Systems. 2020： 20989-21001.

［34］Wu Qitian， Zhao Wentao， Li Zenan，et al. Nodeformer： a scalable graph structure learning Transformer for node classification［C］// Advances in Neural Information Processing Systems. 2022： 27387-27401.

［35］Jang E， Gu Shixiang， Poole B. Categorical reparameterization with gumbel-softmax ［EB/OL］. （2016）.https：//arxiv.org/abs/1611. 01144.

［36］Hamid R，Xiao Ying， Gittens A， et al. Compact random feature maps［C］//Proc of International Conference on Machine Learning. 2014： 19-27.

［37］Chaudhuri S， Das G， Narasayya V. Optimized stratified sampling for approximate query processing ［J］. ACM Trans on Database Systems， 2007， 32（2）： 9-es.

［38］Yang YaoYuan， Rashtchian C， Zhang Hongyang，et al. A closer look at accuracy vs. robustness［C］// Advances in Neural Information Processing Systems. 2020： 8588-8601.

［39］Fu Dongqi， Hua Zhigang， Xie Yan，et al. VCR-Graphormer： a mini-batch graph Transformer via virtual connections ［EB/OL］. （2024）.https：//arxiv.org/abs/ 2403. 16030.

［40］Li Mu， Zhang Tong， Chen Yuqiang，et al. Efficient mini-batch trai-ning for stochastic optimization［C］// Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York：ACM Press，2014： 661-670.

［41］Bahmani B， Chowdhury A， Goel A. Fast incremental and persona-lized PageRank ［EB/OL］. （2010）.https：//arxiv.org/abs/ 1006. 2880.

［42］Trang T N A， Ngo K N， Sonnery H，et al. Scalable hierarchical self-attention with learnable hierarchy for long-range interactions ［EB/OL］. （2024-04-12）. https：//openreview.net/forum？id=qH4YFMyhce.

［43］Bi Wendong， Du Lun， Fu Qiang，et al. Make heterophily graphs better fit GNN： a graph rewiring approach ［EB/OL］. （2022）. https：//arxiv.org/abs/ 2209. 08264.

［44］Lee C Y， Gallagher P W， Tu Z. Generalizing pooling functions in convolutional neural networks：mixed， gated， and tree［M］// Artificial Intelligence and Statistics. 2016： 464-472.

［45］Wu Qitian， Zhao Wentao， Yang Chenxiao，et al. Simplifying and empowering Transformers for large-graph representations［C］// Advances in Neural Information Processing Systems.2024.

［46］Niu Zhaoyang， Zhong Guoqiang， Yu Hui. A review on the attention mechanism of deep learning ［J］. Neurocomputing， 2021， 452： 48-62.

［47］Henaff M， Bruna J， LeCun Y. Deep convolutional networks on graph-structured data ［EB/OL］. （2015）.https：//arxiv.org/abs/ 1506. 05163.

［48］Zhang Peiyan， Yan Yuchen， Li Chaozhuo，et al. Can Transformer and GNN help each other？ ［EB/OL］. （2023）. https：//arxiv.org/abs/ 2308. 14355.

［49］Schulz S， Blochinger W， Hannak H. Capability-aware information aggregation in peer-to-peer grids： methods， architecture， and implementation ［J］. Journal of Grid Computing， 2009， 7： 135-167.

［50］Zhu Yanqiao， Xu Weizhi， Zhang Jinghao，et al. Deep graph structure learning for robust representations： a survey ［EB/OL］. （2021）. https：//arxiv.org/abs/ 2103. 03036.

［51］Ma Xiaojun， Wang Junshan， Chen Hanyue，et al. Improving graph neural networks with structural adaptive receptive fields［C］// Proc of Web Conference. 2021： 2438-2447.

［52］Chen Dexiong， O’Bray L， Borgwardt K. Structure-aware Transformer for graph representation learning［C］//Proc of International Confe-rence on Machine Learning. 2022： 3469-3489.

［53］Ke Jintao， Feng Siyuan， Zhu Zheng，et al. Joint predictions of multi-modal ride-hailing demands： a deep multi-task multi-graph learning-based approach ［J］. Transportation Research Part C： Emerging Technologies， 2021， 127： 103063.

［54］Alam M T， Roy A， Ahmed C F，et al. UGMINE： utility-based graph mining ［J］. Applied Intelligence， 2023， 53 （1）： 49-68.

［55］Kiran R， Kumar P， Bhasker B. DNNRec：a novel deep learning based hybrid recommender system ［J］. Expert Systems with Applications， 2020， 144： 113054.

［56］Bretto A. Hypergraph theory： an introduction［M］. Cham： Springer， 2013.

［57］Yang Yuhao， Huang Chao， Xia Lianghao，et al. Multi-behavior hypergraph-enhanced Transformer for sequential recommendation［C］// Proc of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York：ACM Press， 2022： 2263-2274.

［58］Loukili M， Messaoudi F， El Ghazi M. Machine learning based re-commender system for e-commerce ［J］. IAES International Journal of Artificial Intelligence， 2023， 12（4）： 1803-1811.

［59］Fan Haoqi， Xiong Bo， Mangalam K， et al. Multiscale vision Transformers［C］// Proc of IEEE/CVF International Conference on Computer Vision. 2021： 6824-6835.

［60］Fan Xinyan， Liu Zheng， Lian Jianxun，et al. Lighter and better： low-rank decomposed self-attention networks for next-item recommendation［C］// Proc of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York：ACM Press， 2021： 1733-1737.

［61］Lowe R， Boucheix J M. Dynamic diagrams：a composition alternative［C］//Proc of the 7th International Conference on Diagrammatic Representation and Inference. Berlin： Springer， 2012： 233-240.

［62］Wu Yuxia， Fang Yuan， Liao Lizi. On the feasibility of simple Transformer for dynamic graph modeling［C］// Proc of ACM on Web Conference. New York：ACM Press， 2024： 870-880.

［63］Kook Y J， Li J， Lee B，et al. Low-power and high-speed pipelined ADC using time-aligned CDS technique［C］// Proc of IEEE Custom Integrated Circuits Conference. Piscataway，NJ：IEEE Press， 2007： 321-324.

［64］Zang Xuan， Zhao Xianbing， Tang Buzhou. Hierarchical molecular graph self-supervised learning for property prediction ［J］. Communications Chemistry， 2023， 6（1）： 34.

［65］Luo Shengjie， Chen Tianlang， Xu Yixian，et al. One Transformer can understand both 2D amp; 3D molecular data［C］//Proc of the 11th International Conference on Learning Representations. 2022.

［66］Jin Bowen， Liu Gang， Han Chi， et al. Large language models on graphs： a comprehensive survey ［EB/OL］. （2023-12-05）. https：//arxiv.org/abs/2312.02783.

［67］Goeckenjan G， Sitter H， Thomas M，et al. PubMed results ［J］. Pneumologie， 2011， 65（8）： e51-e75.

［68］Htun H H， Biehl M， Petkov N. Survey of feature selection and extraction techniques for stock market prediction ［J］. Financial Innovation， 2023， 9（1）： 26.

［69］Zhang Hanwei， Zhu Ying， Wang Dan，et al. A survey on visual Mamba ［J］. Applied Sciences， 2024， 14（13）： 5683.