Graph Transformer技術與研究進展：從基礎理論到前沿應用

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

關鍵詞：圖神經網絡；Graph Transformer；圖表示學習；節點分類

中圖分類號：TP39"" 文獻標志碼：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］是一種數據結構，最早由數學家歐拉在1736年提出，用于模擬多種類型的關系和過程。在圖論［2］中，圖是由節點（也稱為頂點）和連接這些節點的邊組成的。節點通常代表對象，而邊則表示對象之間的關系或相互作用。圖可以是有向的（邊有方向）或無向的（邊沒有方向），并且可以包含權重（邊或節點的權重反映了連接或節點的強度或容量）。圖是一種常見的數據結構，廣泛應用于各個領域，如社交網絡分析［3］、推薦系統［4］、化學分子結構分析［5］等。

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

其次，圖嵌入理論［9］的發展也對GNN的構思產生了影響。圖嵌入旨在將圖中的節點、邊或子圖表示為低維向量，其中算法如DeepWalk和node2vec［10］利用隨機游走和SkipGram模型［11］來學習節點的低維表示。雖然這些方法在圖數據的表示學習上取得了一定進展，但它們通常缺乏參數共享和泛化能力，不足以適應圖結構的動態變化或新圖的處理需求。

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

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

本綜述探討了Graph Transformer模型在圖數據分析中的應用，評估其性能，并與現有方法進行比較。研究方法包括對Graph Transformer的理論基礎、架構和應用場景進行全面分析，以及在不同數據集上的實驗驗證，展示了其在圖數據分析中的潛在優勢和應用前景。

1 Graph Transformer的理論和方法

1.1 Graph Transformer設計原理

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

b2=∑ia′2，ivi

（1）

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

在Graph Transformer中，圖嵌入是實現圖數據處理的關鍵技術之一。Graph Transformer中的圖嵌入是將圖中的節點、邊以及整個圖結構轉換成低維向量表示的過程。這些向量表示能夠捕獲圖的拓撲結構、節點間的關系以及節點的特征信息。在Graph Transformer框架中，圖嵌入尤其關鍵，因為它直接影響到模型對圖數據的理解和處理能力。

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

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

編碼器部分在Graph Transformer中負責對圖結構數據進行處理和特征提取，其基本結構與傳統Transformer的編碼器相似，包括多層的自注意力機制，全連接前饋網絡等組件。表1展示Graph Transformer中的編碼器塊組件。

總而言之，編碼器塊的設計旨在充分利用圖結構數據的特點，通過圖注意力機制、節點特征更新規則等組件，實現對節點之間復雜關系的建模和全局信息的整合。這些組件共同作用，使得Graph Transformer在處理圖數據任務時能夠更好地捕捉節點之間的關聯關系和特征之間的依賴關系。

1.2 Graph Transformer層介紹

Graph Transformer層將Transformer架構應用于圖結構數據的神經網絡層。它結合了Transformer模型強大的序列建模能力和圖神經網絡［25］處理圖結構數據的能力，旨在提升對復雜圖結構數據的建模效果。Graph Transformer層是圖神經網絡中的一個核心組件，其結構如圖3所示。Graph Transformer層可以使模型能從復雜的圖結構中學習到有效的表示。表2展示了Graph Transformer層的關系和作用。

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

2 Graph Transformer模型應用分類

本章將具體介紹Graph Transformer在處理典型圖數據任務中的應用，Graph Transformer在實現其設計原理時的幾個關鍵優化，包括注意力機制的優化、模塊架構層面的優化，以及處理復雜圖的優化。Graph Transformer的核心優勢在于其自注意力機制的強大能力，通過動態地分配注意力權重，可以捕捉節點和邊之間的復雜關系。GNN模型通常基于固定的鄰居聚合機制，而Graph Transformer則通過自注意力機制自適應地調整不同節點間的依賴關系，使得模型在處理具有不同重要性關系的節點時表現出更強的靈活性。Graph Transformer在模塊架構層面的改進主要體現在其層次化設計和全局信息聚合能力上。與傳統的模型相比，Graph Transformer不僅在單層結構上引入了注意力機制，還通過多層堆疊實現了更深層次的圖結構信息聚合。在處理復雜圖結構（如動態圖、超圖等）時，Graph Transformer的表現尤為出色。其自注意力機制不僅能夠處理靜態圖數據，還可以通過時間維度的擴展，捕捉圖隨時間演變的動態變化。

2.1 Graph Transformer在注意力機制上的優化

注意力機制的優化對模型性能有著顯著的影響。在傳統的Graph Transformer模型中，注意力機制通常是均勻地對所有輸入數據進行處理，這在處理圖結構數據時可能不夠有效，因為圖數據中節點間的關系是不規則且復雜的。通過引入注意力機制，可以更準確地模擬節點間的關系強度，從而更好地捕捉圖中的結構信息。這種針對性的優化不僅提高了模型對圖數據的理解能力，還顯著提升了模型在圖相關任務上的表現，如節點分類、圖分類和鏈接預測等。此外，改進的注意力機制還有助于提高模型的解釋性，使研究人員和實際應用者能更好地理解模型的決策過程。總之，注意力機制的創新是推動Graph Transformer性能提升的關鍵因素之一。

Transformer架構在自然語言處理和計算機視覺領域取得了顯著成功，但在圖表示學習任務中的表現一直不盡如人意。Graphormer ［26］通過有效地編碼圖的結構信息，解決了 Transformer 在圖表示學習中表現不佳的問題。Graphormer是直接基于標準Transformer構建的，通過引入幾種簡單但有效的結構編碼方式來提高處理圖數據的能力。其核心創新在于其結構編碼方法，主要包括中心性編碼、空間編碼和邊編碼。

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

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

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

（2）

其中：h（0）i是節點vi在輸入層的初始表示向量；xi是節點vi的原始特征向量；z－deg（vi）和z+deg（vi）分別表示節點 vi的入度和出度，對應可學習的嵌入向量，這些嵌入向量根據節點的度來分配。

b）空間編碼（spatial encoding）。

對于每個節點對，根據它們的空間關系分配一個可學習的嵌入。有多種測量方式可以用來進行空間編碼，這里以兩節點間最短路徑的距離為例，它會被編碼為 softmax attention 中的偏置項（是個標量），并幫助模型準確地捕獲圖中的空間依賴關系。式（3）對應Transformer的Q乘K并標準化的部分。

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

（3）

其中：Aij表示節點vi和vj之間的注意力分數；hi和hj分別表示節點vi和vj的特征向量；WQ和WK分別是查詢（query）和鍵（key）的投影矩陣；d是特征向量的維度平方根；φ（vi，vj）用于縮放，索引的可學習標量，在所有層中共享。

c）邊編碼（edge encoding）。

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

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

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

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

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

a）圖4（a）強調每個節點與其直接相鄰節點之間的關系。EXPHORMER通過局部領域注意力，確保模型能夠捕捉節點的近鄰特征，這對于理解圖的局部結構是至關重要的。

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

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

d）圖4（d）的結構融合了局部領域、擴展鄰居以及全局注意力，形成了一個多層次的交互圖。EXPHORMER利用這種復雜的組合來綜合不同層面的信息，提供一個全面的圖表示。這對于理解節點的綜合作用和圖中的復雜模式非常關鍵。

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

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

（5）

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

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

NodeFormer模型的基本思路是采用隨機特征映射和Gumbel-Softmax兩種近似策略分別實現可擴展和可微分的目的。從而實現了線性復雜度下的圖結構可學習的大圖Transformer。下面介紹本文核心思路的公式推導。其更新公式為

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層中節點u的表示向量。k（l）u，q（l）u，v（l）u由第l層的特征變換得到（對應Transformer里的key、query、value）。注意力權重通過對query和key的點積進行softmax歸一化得到，表示節點u對v的關注程度。最終的節點表示z（l+1）u是所有v的value向量u（l）v加權求和的結果，加權系數為節點u對v的注意力權重。式（6）可以看作WT 把Transformer定義在圖上，即圖節點組成了很長一個輸入序列。

顯而易見，按照上式的定義，對于任意節點u都需要單獨計算其他N個節點的注意力z（l+1）u，因此更新所有N個節點需要O（N2）的復雜度。為了解決這一困難，對于任意節點u，找到在每一層中一個“最優”的鄰居集合，進行信息傳遞，就可以把N個節點產生的注意力權重視為一個categorical distribution，然后從中采樣得到鄰居集合。盡管采樣的過程不可求導，可以借助Gumbel-Softmax對其進行近似處理，就是把式（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分布中抽樣得到的噪聲；τ是溫度參數，控制softmax的平滑度。

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

2.2 模塊架構層面的優化

Graph Transformer架構采用模塊化設計，易于擴展和優化，如通過引入輕量化架構、結構集成方式等進一步提升模型性能。總體而言，Graph Transformer在準確性和計算效率方面的改進，使其在處理各種圖結構數據任務中表現出色。

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

VCR-Graphormer通過基于結構和內容的超級節點引入多種類型的虛擬連接來重新連接圖，使PPRToken化能夠將局部和全局上下文、長程交互和異質信息編碼到每個節點的Token列表中。總的來說，與以前工作的O（n3）復雜度相比，VCR-Graphormer需要O（m+k log k）的復雜度進行圖Token化。

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

對于目標節點u，根據PPR公式計算其個性化PageRank向量ru。然后從ru中采樣得分最高的前k個節點，記為集合Rku。Rku中的節點及其對應的PPR得分共同構成了節點u的Token列表Tu，如式（8）所示。

（8）

其中：X（i，：）表示節點i的特征向量；ru（i）表示在ru中節點i對應的PPR得分。將其整理成矩陣形式后，即可輸入到標準的自注意力機制以及池化函數［44］中，得到節點的表示向量。

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

圖5（a）展示了結構感知超節點和虛擬連接的概念。可以看到，通過圖分割，不同的節點被分配到了不同的超節點，并通過虛擬連接與它們關聯。這些連接允許信息在圖中以一種高效的方式流動，使得遠距離的節點（例如5跳鄰居）能夠更快地相互影響。圖5（b）展示了內容感知超節點和虛擬連接。在這里，基于節點的標簽或內容，超節點被引入到圖中。每個超節點與具有相同標簽的所有普通節點連接。表格列出了在引入這些超節點后，一些節點對之間距離的變化，其中紅色節點之間的距離有所縮短（見電子版）。這種方法可以增強圖數據在特征豐富度和異質信息編碼方面的表達能力。

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

TransGNN結合了Transformer和GNN的優勢，設計了子模塊：Transformer層，用于處理遠距離依賴關系；GNN層，用于聚合鄰近節點的信息。

Transformer層：使用 Transformer 層來改進 GNN 層，將感受野擴展到更相關的節點，這些節點可能遠離鄰域。

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

（9）

式（9）描述了Transformer層中計算注意力權重和聚合信息的過程。

GNN層：利用 GNN 層融合表示和圖結構，幫助 Transfor-mer 層更好地利用圖結構。

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

式（10）描述了在圖神經網絡層中消息傳遞和節點表示更新的過程。

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

圖7展示了結構感知Transformer如何通過結合Transformer架構與結構感知模塊，有效捕捉圖結構數據的全局和局部信息。通過結構提取器提取子圖并更新節點表示，再通過Transformer層進行進一步處理，實現了對圖數據的高效建模。

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

2.3 Graph Transformer應用于復雜圖的改進優化

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

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

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

圖9概述了一種用于動態圖建模的Transformer架構SimpleDyG。從一個實例動態圖開始，它首先創建了一系列時間自我中心圖，這些圖捕捉了與每個中心節點隨時間發生交互的節點。隨后，引入了時間對齊的概念，使用時間標記將歷史交互分割成連續的時間段，從而對不同節點的交互歷史進行編碼。這些經時間對齊的序列最后輸入到一個標準的Transformer架構中，Transformer利用其多頭注意力和前饋網絡來學習和預測節點隨時間的行為和交互。整個過程強調了時間信息在捕捉動態圖結構變化中的重要性，并展示了如何將動態圖數據轉換為Transformer能有效處理的格式。

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

Transformer-M模型通過將2D和3D結構信息作為偏置項加入到注意力機制中，從而在處理2D和3D分子數據時，能夠捕捉到更加豐富的結構信息。這種設計使得模型可以同時處理和理解不同模態的分子數據。式（11）展示了Transformer-M模型中的注意力矩陣計算公式。

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

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

通過結合Transformer的自注意力機制和多種結構信息編碼方法，Transformer-M模型能夠同時處理和理解2D和3D分子數據，展示了其在廣泛化學任務中的強大性能和廣泛適用性。這為開發通用的分子模型提供了新的途徑，有助于推動化學和材料科學領域的研究和應用。

Transformer在處理復雜圖數據方面展現出獨特的優勢，尤其是其自注意力機制能夠捕獲長距離的節點間依賴，這對于理解圖的深層次結構和動態變化至關重要。無論是靜態圖的結構化特征學習，還是動態圖中隨時間演進的復雜交互模式識別，Transformer都能通過靈活的序列處理能力，提供精確且深入的圖表示，為社交網絡分析、推薦系統、知識圖譜等領域帶來了革命性的影響。其強大的表征學習能力和對時間動態的敏感捕捉，讓Transformer成為了復雜圖數據分析的強有力工具。

3 Graph Transformer性能分析

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

3.1 大規模圖數據性能分析

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

3.2 復雜圖數據性能分析

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

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

在圖12中，對每個Graph Transformer改進模型（BERT4Rec-MB、MB-GCN、NMTR、MB-GMN、MNHT）在各個超圖數據集（Taobao、Retailrocket和IJCAI）中的評估指標進行了描述（其中橫坐標為模型方法，縱坐標為評估指標）。這些評估指標值能夠幫助讀者在今后選擇超圖實驗模型時選擇最優的模型。

3.3 動態圖數據性能分析

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

在圖13中，對每個Graph Transformer改進模型（DyRep、JODIE、TGAT、TGN、TREND、GraphMixer、SimpleDyG）在各個動態圖數據集（UCI、ML-10M、Hepth和MMConv）中的評估指標進行了描述（其中橫坐標為模型方法，縱坐標為評估指標）。這些評估指標值能夠幫助讀者在今后選擇實驗模型時選擇最優的模型。

在動態圖中主要以NDCG@5=DGC@5IDCG@5作為評估推薦系統性能的指標，特別適用于衡量推薦結果的排序質量。

4 Graph Transformer在不同領域的應用分類

Graph Transformer作為一種結合了圖神經網絡和Transformer架構的先進模型，充分利用了圖結構數據的特性。通過在圖節點間動態地計算注意力權重，Graph Transformer能夠有效地處理和解析節點間的復雜關系，這在許多領域中顯示出了巨大的潛力。表7詳細介紹Graph Transformer在多個關鍵領域中的應用，包括生物信息學中的蛋白質結構預測、社交網絡的用戶行為分析、推薦系統的優化、文本生成，以及金融領域的欺詐檢測。通過探索這些應用，不僅能夠看到Graph Transformer技術的強大能力，也能理解它在未來數據科學和人工智能領域中的應用前景。

Graph Transformer技術在多個領域中展示了其強大的應用潛力和靈活性。在化學領域，如MAT和GROVER所示，Graph Transformer被用于分子結構的表征和預測，幫助科學家更好地理解分子間的相互作用和藥物活性。在生物信息學中，如scMoFormer所示，它被用于處理復雜的單細胞數據，提供細胞類型的詳細分類和功能解析。此外，在處理復雜網絡結構的數據分析方面，如HGT和HeGT所示，Graph Transformer能有效地處理和分析異構圖，這對于增強節點和邊的特征學習，提高數據挖掘和知識發現的效率至關重要。總體而言，Graph Transformer為處理結構化數據提供了一種高效和可擴展的方法，廣泛適用于科學研究和工業應用中的多個領域。

5 總結與展望

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

Graph Transformer盡管取得了顯著成就，但在面對極大規模圖數據時的計算效率、長距離依賴和可解釋性方面仍存在挑戰。

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

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

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

Graph Transformer作為圖神經網絡領域的新興方法，具有廣闊的發展前景。以下是一些未來的研究方向和應用前景：

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

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

c）Graph Transformer 的應用前景十分廣泛，尤其在社交網絡分析、推薦系統、生物信息學、金融風控和知識圖譜等領域展現出巨大潛力。憑借其強大的自注意力機制，Graph Transfor-mer 能夠有效捕捉圖中復雜的節點關系和長距離依賴，為用戶提供更準確的預測和個性化推薦。此外，在處理大規模和動態圖數據時，通過優化模型的可擴展性和計算效率，Graph Transformer 有望推動智能城市、智慧醫療等領域的發展。隨著研究的深入和技術的成熟，Graph Transformer 將在實際應用中發揮越來越重要的作用，推動圖數據分析的進步。

參考文獻：

［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.