在圖表示學習中，Graph Transformer通過位置編碼對圖結構信息進行編碼，相比GNN，可以捕獲長距離依賴，減輕過平滑現象。本文介紹Graph Transformer的兩篇近期工作。

[ICML 2022] Structure-Aware Transformer for Graph Representation Learning

本文分析了Transformer的位置編碼，認為使用位置編碼的Transformer生成的節點表示不一定捕獲它們之間的結構相似性。為了解決這個問題，提出了結構感知Transformer，通過設計新的自注意機制，使其能夠捕獲到結構信息。新的注意力機制通過在計算注意力得分之前，提取每個節點的子圖表示，并將結構信息合并到原始的自注意機制中。本文提出了幾種自動生成子圖表示的方法，并從理論上表明，生成的表示至少與子圖表示具有相同的表達能力。該方法在五個圖預測基準上達到了最先進的性能，可以利用任何現有的GNN來提取子圖表示。它系統地提高了相對于基本GNN模型的性能，成功地結合了GNN和Transformer。

方法

本文提出了一個將圖結構編碼到注意力機制中的模型。首先，通過Structure extractor抽取節點的子圖結構，進行子圖結構的注意力計算。其次，遵循Transformer的結構進行計算。

Structure-Aware Self-Attention

Transformer原始結構的注意力機制可以被重寫為一個核平滑器： 其中， 是一個線性函數。 是 空間中，由 和 參數化的（非對稱）指數核： 是定義在節點特征上的可訓練指數核函數，這就帶來了一個問題：當節點特征相似時，結構信息無法被識別并編碼。為了同時考慮節點之間的結構相似性，我們考慮了一個更一般化的核函數，額外考慮了每個節點周圍的局部子結構。通過引入以每個節點為中心的一組子圖，定義結構感知注意力如下： 其中， 是節點 在圖 中的子圖，與節點特征 相關， 是可以是任意比較一對子圖的核函數。該自注意函數不僅考慮了節點特征的相似度，而且考慮了子圖之間的結構相似度。因此，它生成了比原始的自我關注更有表現力的節點表示。定義如下形式的: 其中 是一個結構提取器，它提取以 為中心、具有節點特征 的子圖的向量表示。結構感知自我注意力十分靈活，可以與任何生成子圖表示的模型結合，包括GNN和圖核函數。在自注意計算中并不考慮邊緣屬性，而是將其合并到結構感知節點表示中。文章提出兩種生成子圖的方法：k-subtree GNN extractor 和 k-subgraph GNN extractor，并進行相關實驗。

實驗

下圖是模型在圖回歸和圖分類任務上的效果。 使用GNN抽取結構信息后，再用Transformer學習特征，由下圖可以看出，Transformer可以增強GNN的性能。

[NIPS 2022] Recipe for a General, Powerful, Scalable Graph Transformer

本文首先總結了不同類型的編碼，并對其進行了更清晰的定義，將其分為局部編碼、全局編碼和相對編碼。其次，提出了模塊化框架GraphGPS，支持多種類型的編碼，在小圖和大圖中提供效率和可伸縮性。框架由位置/結構編碼、局部消息傳遞機制、全局注意機制三個部分組成。該架構在所有基準測試中顯示了極具競爭力的結果，展示了模塊化和不同策略組合所獲得的經驗好處。

方法

在相關工作中，位置/結構編碼是影響Graph Transformer性能的最重要因素之一。因此，更好地理解和組織位置/結構編碼將有助于構建更加模塊化的體系結構，并指導未來的研究。本文將位置/結構編碼分成三類：局部編碼、全局編碼和相對編碼。各類編碼的含義和示例如下表所示。 現有的MPNN+Transformer混合模型往往是MPNN層和Transformer層逐層堆疊，由于MPNN固有結構帶來的過平滑問題，導致這樣的混合模型的性能也會受到影響。因此，本文提出新的混合架構，使MPNN和Transformer的計算相互獨立，獲得更好的性能。具體框架如圖所示。

框架主要由位置/結構編碼、局部消息傳遞機制（MPNN）、全局注意機制（Self Attention）三部分組成。根據不同的需求設計位置/結構編碼，與輸入特征相加，然后分別輸入到MPNN和Transformer模型中進行訓練，再對兩個模型的結果相加，最后經過一個2層MLP將輸出結果更好的融合，得到最終的輸出。更新公式如下：

實驗

在圖級別的任務上，效果超越主流方法：

通過消融實驗，研究框架中各個結構的作用，可以看到，MPNN和位置/結構編碼模塊對Transformer的效果均有提升作用。

總結

兩篇文章都有一個共同特點，就是采用了GNN+Transformer混合的模型設計，結合二者的優勢，以不同的方式對兩種模型進行融合，GNN學習到圖結構信息，然后在Transformer的計算中起到提供結構信息的作用。在未來的研究工作中，如何設計更加合理的模型，也是一個值得探討的問題。 本期責任編輯：楊成本期編輯：劉佳瑋

Transformer架構最近在圖表示學習中獲得了越來越多的關注，因為它通過避免圖神經網絡(GNN)的嚴格結構歸納偏差，而只通過位置編碼對圖結構進行編碼，從而自然地克服了圖神經網絡(GNN)的一些限制。在這里，我們展示了使用位置編碼的Transformer生成的節點表示不一定捕獲它們之間的結構相似性。為了解決這個問題，我們提出了結構感知Transformer (Structure-Aware Transformer)，這是一類建立在一種新的自注意力機制上的簡單而靈活的圖Transformer。這種新的自注意在計算自注意之前，通過提取基于每個節點的子圖表示，將結構信息融入到原始自注意中。我們提出了幾種自動生成子圖表示的方法，并從理論上表明，生成的表示至少與子圖表示一樣具有表現力。從經驗上講，我們的方法在5個圖預測基準上達到了最先進的性能。我們的結構感知框架可以利用任何現有的GNN來提取子圖表示，我們表明，相對于基本GNN模型，它系統地提高了性能，成功地結合了GNN和transformer的優勢。我們的代碼可以在這個 https: //github.com/BorgwardtLab/SAT. 中找到。

近年來，Transformer架構和變體在許多機器學習任務中取得了顯著的成功。這種成功本質上與處理長序列的能力以及注意力機制中上下文相關的權重的存在有關。我們認為這些能力符合元強化學習算法的核心作用。事實上，元強化學習代理需要從一系列軌跡推斷任務。此外，它需要一個快速適應策略來適應新的任務，這可以通過使用自我注意機制來實現。在這項工作中，我們提出了TrMRL(transformer 元強化學習)，一個元強化學習l代理，模仿記憶恢復機制使用transformer 架構。它將最近過去的工作記憶聯系起來，遞歸地通過transformer層建立情景記憶。我們展示了自注意力計算出一種共識表示，在每一層將貝葉斯風險降到最低，并提供了有意義的特征來計算最佳行動。我們在運動和靈巧操作的高維連續控制環境中進行了實驗。結果表明，在這些環境中，與基線相比，TrMRL具有可比或更好的漸近性能、樣本效率和分布外泛化。

//www.zhuanzhi.ai/paper/1a6668cdd5003fa2b3f7803489661a0d

用于文本圖表示學習的 GNN 嵌套 Transformer 模型：GraphFormers

GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph

論文摘要：文本圖的表示學習是基于單個文本特征和鄰域信息為節點生成低維嵌入。現有的工作主要依賴于級聯模型結構：首先通過語言模型對節點的文本特征進行獨立編碼；然后通過圖神經網絡對文本嵌入進行聚合。然而這種文本特征獨立建模的結構限制了模型的效果。故本文提出了 GraphFormers ——將 GNN 組件嵌套在 Transformer 語言模型的一種新架構。在該架構中，文本編碼和圖聚合融合為一個迭代工作流，使得每個節點的語義都能從全局角度準確理解。此外，還引入了一種漸進式學習策略，該策略在操作數據和原始數據上連續訓練模型，以增強其在圖形上整合信息的能力。實驗證明，本文提出的架構在 3 個數據集上都取得了最好結果。

//www.zhuanzhi.ai/paper/fe680cfb84881e3cd10ad6cb93a66978

本文將圖上定義的神經網絡轉換為消息傳遞神經網絡(MPNNs)，以研究這類模型的不同分類的區分能力。我們感興趣的是某些架構何時能夠根據作為圖輸入的特征標簽區分頂點。我們考慮了兩種不同的MPNNs: 匿名MPNNs，其消息函數只依賴于所涉及的頂點的標簽; 以及程度感知的MPNNs，其消息函數可以額外使用關于頂點度數的信息。前一類涵蓋了流行的圖神經網絡(GNN)形式，其優異的能力是已知的。后者包括Kipf和Welling提出的圖卷積網絡(GCNs)，其區分能力未知。利用Weisfeiler-Lehman (WL)算法的辨識能力，得到了(匿名和程度感知)多神經網絡辨識能力的上界和下界。我們的主要結果表明: (1) GCNs的分辨能力受到WL算法的限制，但它們可能領先一步; (ii) WL算法不能用普通的GCNs模擬，但通過在頂點和其鄰居的特征之間添加一個權衡參數(Kipf和Welling提出的)可以解決這個問題。

//proceedings.mlr.press/v139/geerts21a

由于消息傳遞—圖神經網絡（MPNN）應用在稀疏圖時相對于節點數量具有線性復雜性，因此它們已被廣泛使用， 不過它們的理論表達能力bounded by一階 Weisfeiler-Lehman 檢驗 (1-WL)。

在本文中，我們表明，如果自定義特征值相關的非線性函數設計圖卷積supports并使用任意大的感受野進行掩蔽，則 MPNN 在理論上比 1-WL 測試更強大。實驗表明該方法與3-WL 同樣強大，同時能夠保持空間局部化(spatially localized)。此外，通過設計自定義濾波器函數，輸出可以具有各種頻率分量，從而允許卷積過程學習給定輸入圖信號與其相關屬性的不同關系。

目前，最好的 3-WL 等效圖神經網絡的計算復雜度為 O(n^3 )，內存使用量為 O(n^2 )，考慮非局部更新機制，并且不提供輸出的頻譜。但是本文所提出的方法克服了所有上述問題，并在許多下游任務中達到了最先進的結果。

//honeine.fr/paul/publi/21.icml.gnn.pdf

圖神經網絡(GNN)中缺乏各向異性核極大地限制了其表達能力，導致了一些眾所周知的問題，如過度平滑。為了克服這個限制，我們提出了第一個全局一致的各向異性核GNN，允許根據拓撲導出的方向流定義圖卷積。首先，通過在圖中定義矢量場，我們提出了一種方法應用方向導數和平滑投影節點特定的信息到場。然后，我們提出用拉普拉斯特征向量作為這種向量場。在Weisfeiler-Lehman 1-WL檢驗方面，我們證明了該方法可以在n維網格上泛化CNN，并證明比標準的GNN更有分辨力。我們在不同的標準基準上評估了我們的方法，發現在CIFAR10圖數據集上相對誤差減少了8%，在分子鋅數據集上相對誤差減少了11%到32%，在MolPCBA數據集上相對精度提高了1.6%。這項工作的重要成果是，它使圖網能夠以一種無監督的方式嵌入方向，從而能夠更好地表示不同物理或生物問題中的各向異性特征。

//www.zhuanzhi.ai/paper/f415f74f0c50433285945af702223eaf

圖神經網絡（GNN）已經成為圖表示學習的事實標準，它通過遞歸地聚集圖鄰域的信息來獲得有效的節點表示。盡管 GNN 可以從頭開始訓練，但近來一些研究表明：對 GNN 進行預訓練以學習可用于下游任務的可遷移知識能夠提升 SOTA 性能。但是，傳統的 GNN 預訓練方法遵循以下兩個步驟：

在大量未標注數據上進行預訓練； 在下游標注數據上進行模型微調。 由于這兩個步驟的優化目標不同，因此二者存在很大的差距。

在本文中，我們分析了預訓練和微調之間的差異，并為了緩解這種分歧，我們提出了一種用于GNNs的自監督預訓練策略L2P-GNN。方法的關鍵是L2P-GNN試圖以可轉移的先驗知識的形式學習如何在預訓練過程中進行微調。為了將局部信息和全局信息都編碼到先驗信息中，我們在節點級和圖級設計了一種雙重自適應機制。最后，我們對不同GNN模型的預訓練進行了系統的實證研究，使用了一個蛋白質數據集和一個文獻引用數據集進行了預訓練。實驗結果表明，L2P-GNN能夠學習有效且可轉移的先驗知識，為后續任務提供好的表示信息。我們在//github.com/rootlu/L2P-GNN公開了模型代碼，同時開源了一個大規模圖數據集，可用于GNN預訓練或圖分類等。

總體來說，本文的貢獻如下：

• 首次探索學習預訓練 GNNs，緩解了預訓練與微調目標之間的差異，并為預訓練 GNN 提供了新的研究思路。
• 針對節點與圖級表示，該研究提出完全自監督的 GNN 預訓練策略。
• 針對預訓練 GNN，該研究建立了一個新型大規模書目圖數據，并且在兩個不同領域的數據集上進行了大量實驗。實驗表明，該研究提出的方法顯著優于 SOTA 方法。