說明：本文僅供學(xué)習(xí)，未經(jīng)同意請勿轉(zhuǎn)載
筆記時間：2022年08月
博客公開時間：2023年3月2日

前情回顧

前面我們大致的了解了Graph Transformer是什么，以及它與GNN、Transformer的差別，關(guān)聯(lián)。如果對這方面不是很熟悉的朋友可以看一下【圖-注意力筆記，篇章1】一份PPT帶你快速了解Graph Transformer：包括Graph Transformer 的簡要回顧且其與GNN、Transformer的關(guān)聯(lián)

在大致的了解Graph Transformer之后，筆者在篇章2中將介紹一下兩篇筆者自身認(rèn)為必看的經(jīng)典Graph Transformer的文章——Graphormer和GraphFormers。

別看這兩個名字有點像，但是它們的做法是不一樣得。在篇章1中，我們可以知道Graph Transformer實際上就是GNN和Transformer的結(jié)合。根據(jù)筆者我閱讀的文獻來看，我大致地將后面改進方向粗略地分成四個（ps:當(dāng)然本人看的文獻有限，存在缺漏，有不對的或者其他更加有趣的點，歡迎學(xué)習(xí)交流!）：

1. 怎么設(shè)置位置編碼，也就是PE。常見的PE編碼設(shè)置有很多，比如Local PE, Global PE和Relative PE。PE的方式很多，而且很多來源于Transformer的文章，這里我就不找對應(yīng)的論文來介紹了。在篇章1中，我們知道論文GraphTrans中并沒有采用PE，而是采用像VIT一樣的[CLS]，這樣子的[CLS]處理方式可以實現(xiàn)：在聚合信息時，可以實現(xiàn)排列不變性，也就是在不考慮節(jié)點重要性的情況下，屬于同一類型同一階的鄰居節(jié)點沒有優(yōu)先級的區(qū)分。
2. 怎么融入拓撲結(jié)構(gòu)信息。拓撲結(jié)構(gòu)信息是指邊的屬性/特征，圖路徑的屬性/特征，拓撲空間的屬性，或者圖的頻譜性等。在多數(shù)論文中，常見的就有將邊的特征（也就是邊的權(quán)重矩陣）添加至attetion里面，還有的就是利用結(jié)構(gòu)編碼SE實現(xiàn)結(jié)構(gòu)信息的融入，或者是先通過學(xué)習(xí)子圖結(jié)構(gòu)的信息，再進Transformer機制。對于SE，同樣常見的也有Local SE, Global SE和Relative SE。最后，還有的論文是把空間上的拓撲特征也添加至attention里面。比如說這里我要講的第一篇論文Graphormer。
3. 怎么考慮更復(fù)雜的圖屬性/結(jié)構(gòu)。要知道在現(xiàn)實中，圖多數(shù)是異質(zhì)圖，包含多種類型的邊/路徑，而且不同的節(jié)點之間的重要性應(yīng)該是不一樣的。所以，針對多關(guān)系的局限，有的研究會考慮關(guān)系編碼RE或者邊類型編碼（這個我也把它稱之為RE，因為邊本身也可以看出一種關(guān)系）。針對節(jié)點類型/重要性，有的研究會添加類型編碼，重要性編碼來解決。其中，重要性編碼同樣在Graphormer中也有應(yīng)用。
4. 怎么結(jié)合GNN和Transformer。早期多數(shù)的研究都是直接GNN拼接Transformer。其實還有更多結(jié)合的方式，這也是本博文想要介紹GraphFormer論文的原因。

基于上面的介紹，其實我想分享的這兩篇論文的理由也十分清晰了。后面就來看看這兩篇文獻吧。

論文信息概覽

在介紹之前，我們先概覽一下這兩篇文章的信息。

可以發(fā)現(xiàn)這兩篇文獻都是NeurlPS 2021的文章，但它們的驅(qū)動任務(wù)是不同的。Graphormer是在化學(xué)分子評分的場景下提出，主要做的是圖層面的回歸任務(wù)，而GraphFormer則是邊層面上的任務(wù)，做的是邊預(yù)測，主要應(yīng)用在文本場景中。在下面的筆記中，筆者我只介紹和概括筆者認(rèn)為比較重要的內(nèi)容，對于細節(jié)部分，大家感興趣的話，建議直接看原論文。

Graphormer

論文信息概覽

• paper name:《Do Transformers Really Perform Bad for Graph Representation?》

• 原文鏈接：https://proceedings.neurips.cc/paper/2021/file/f1c1592588411002af340cbaedd6fc33-Paper.pdf

• 源碼鏈接：https://github.com/Microsoft/Graphormer.

• 來源：大連科大, NeurIPS

• 數(shù)據(jù)背景：Kaggle比賽，化學(xué)分子評分背景

• 年限：2021

論文核心要點介紹

Graphormer論文不得不夸一下這篇論文的圖??，屬于那種看圖就知道文章在做什么了。

三大編碼的介紹

從上面的圖，我們可以快速的知道，Graphormer模型的核心內(nèi)容就是中引入了三種編碼方式，分別是Centrality Encoding（中心性編碼）, Edge Encoding （邊特征編碼）和Spatial Encoding（空間位置編碼）。其中：

Centrality Encoding

Centrality Encoding從名字看就知道作者計算了節(jié)點的中心性。在圖論中，節(jié)點的中心性代表這節(jié)點的重要性。節(jié)點中心性有很多種，比如特征向量中心性(Eigenvector Centrality)， 介數(shù)中心性(Betweenness Centrality)，接近中心性（Closeness Centrality），PageRank中心性和這里的度中心性等。這些都是圖論中比較基礎(chǔ)的概念了，如果不了解，建議自己去看一下這些。

在Graphormer論文中（看PPT上面右下角第一行的藍色標(biāo)記），作者主要采用的是度中心性。因此，Centrality Encoding考慮了節(jié)點的重要性。而且從PPT里面我框的紅色公式來看，這里的節(jié)點度的計算包括出度$de{g}^{?}(v_i)$和入度$de{g}^{+}(v_i)$，考慮了邊的方向。所以進入Transformer之前，節(jié)點的特征$h_i^{(0)}$是原本節(jié)點的特征$x_i$加上節(jié)點入度的線性變換特征$z_{de{g}^{+}(v_i)}^{+}$和節(jié)點出度的線性變換特征$z_{de{g}^{?}(v_i)}^{?}$。

Spatial Encoding

Spatial Encoding同樣非常清晰，空間編碼。類似于相對編碼。我們知道Transformer主要是關(guān)注全局信息，對圖的局部拓撲屬性的捕捉差。因此，才會有結(jié)構(gòu)編碼或者子圖結(jié)構(gòu)編碼的相關(guān)研究。這里, Graphormer論文為了融入圖空間上的拓撲結(jié)構(gòu)屬性的話，引入了空間編碼。那么這個空間編碼具體是怎么做呢？可以看到PPT右下角紅色框的那部分，Graphormer作者在這里利用弗洛伊德算法計算兩個節(jié)點之間的最短路徑距離（shortest path distance, SPD)，以此編碼空間屬性。那可能有的人就會有“為什么SPD可以表征空間屬性"這個疑問。這是因為我們計算了每個節(jié)點之間最短路徑距離的時候，就可以知道原來有節(jié)點與節(jié)點之間隔了多少條邊，節(jié)點與節(jié)點之間的連接狀態(tài)大概是怎么樣的。因此，最短路徑可以用來捕獲圖的非歐式空間的拓撲結(jié)構(gòu)屬性。

同時，作者考慮不可達的情況，將不可達之間節(jié)點的距離定義為-1。因此，到這里，我們應(yīng)該知道SPD是可以用來捕獲空間屬性的，而且由于是最短路徑SP，所以它獲取的是局部信息的空間屬性。在論文中Spatial Encoding，也就是最短路徑距離$?(v_i,v_j)$主要是加在注意力機制$A$的偏置$b$上，也就是上面PPT右上藍色框的部分，因此attention $A_{ij}$就變成:
$$A_{ij}=\frac{(h_i{W}_Q)(h_i{W}_K{)}^T}{\sqrt{d}}+b_{?(v_i,v_j)}$$
注意，這里跟節(jié)點度中心性一樣，也對屬性進行線性變換。 相當(dāng)于使用一個可學(xué)習(xí)縮放函數(shù)$b$對我們原始計算的SPD進行縮放編碼。這樣子做可以讓圖自適應(yīng)地調(diào)整不同距離的節(jié)點重要性。一般來說$b$應(yīng)該是一個相對最短路徑距離$?(v_i,v_j)$的遞減函數(shù)，因為模型認(rèn)為，隨著距離$?(v_i,v_j)$增加，節(jié)點重要性會逐漸降低。因此，Spatial Encoding實際上也可以看出節(jié)點重要性的間接表達。這里還需要注意的是，$b$在不同層之間是共享的，因為最短的路徑距離$?(v_i,v_j)$對于這里的Graph來說是固定, Graphormer本身并不會改變圖的連接（指0-1連接）狀態(tài)，因此，每一層的對SPD的縮放$?(v_i,v_j)$應(yīng)該是一致的。

Edge Encoding

Edge Encoding也是非常清晰，作者引入了邊特征的編碼。前面篇章1中我們也講過邊特征編碼的引入，那么在以往邊特征的引入有以下三種方法：

1. 將邊緣特征添加到關(guān)聯(lián)節(jié)點的特征中；
2. 對于每個節(jié)點，其相關(guān)邊的特征將與聚合中的節(jié)點特征一起使用；
3. 直接將邊的連接權(quán)重矩陣進行線性變換后添加至于attention中。

其中，前兩種方法是GNN中常見的做法，尤其在有帶邊的特征的圖中應(yīng)用廣泛，而第三種方法則是早期Graph Transformer進階2中常見的方式。（這里可以跳轉(zhuǎn)至【圖-注意力筆記，篇章1】看一下）。然而，前兩種做法僅將邊信息傳播到其關(guān)聯(lián)的節(jié)點，無法利用邊的特征信息來表達整個圖的復(fù)雜連接轉(zhuǎn)態(tài)，無法從更加全局的角度看待邊特征與節(jié)點的關(guān)聯(lián)；而第三種做法的話，則無法捕獲邊連接的局部拓撲屬性。

那么針對上面的局限呢，在Graphormer中，作者通過計算節(jié)點之間的最短路徑SP上所有邊特征的加權(quán)平均值來得到Edge Encoding, 具體的做法如下面PPT中綠色框的$c_{ij}=\frac{1}{N}{\sum }_{n=1}^N{x}_{e_n}(w_n^E{)}^T$。其中$e_n$為邊特征，$w_n^E$為可學(xué)習(xí)權(quán)重。

與空間編碼相似，作者這里同樣將邊特征編碼$c_{ij}$添加至注意力機制$A$的偏置上。因此，Graphormer最后的attention $A_{ij}$就變成:
$$A_{ij}=\frac{(h_i{W}_Q)(h_i{W}_K{)}^T}{\sqrt{d}}+b_{?(v_i,v_j)}+c_{ij},where:c_{ij}=\frac{1}{N}\sum _{n=1}^N{x}_{e_n}(w_n^E{)}^T$$

其他一些需要注意的點

1. 多頭注意力機制的計算
   Graphormer中多頭注意力機制的計算如下：
   $$\begin{gathered} h^{\prime (l)}=MHA(LN(h^{(l?1)}))+h^{(l?1)} \\ {h}^{(l)}=FFN(LN(h^{\prime (l)}))+h^{\prime (l)} \end{gathered}$$
   這里跟大多數(shù)Transformer層的做法是一樣的。
2. 全連接節(jié)點 [VNode] 的引入
   在Graphormer中，作者向圖中添加了一個名為 [VNode] 的特殊虛擬節(jié)點 Virtual Node，這個節(jié)點與其他所有節(jié)點相連。因此，這里我稱 [VNode] 為全連接節(jié)點?；诖?，在信息聚合時，[VNode] 就可以聚集所有的節(jié)點表示，它的節(jié)點特征實際上就是整個圖的嵌入。實際上，這里的 [VNode] 有點像BERT模型里的[CLS]。 因此，最終圖表示的結(jié)果就是這個虛擬節(jié)點 [VNode] 的嵌入表示。
   根據(jù)上面的介紹，既然 [VNode] 為全連接節(jié)點，那么它與其他節(jié)點的最短路徑距離SPD$?(v_i,[VNode])$就都是1。同時作者考慮到 [VNode] 與其他節(jié)點的連接是我們假定連接的（也就是虛擬的），而不是現(xiàn)實存在的。因此，為了區(qū)分現(xiàn)實存在的邊，也就是Graph的物理連接，與虛擬連接之間的區(qū)別，作者在空間編碼時，將[VNode]與其他節(jié)點的連接看成一種特殊的存在，單獨為其設(shè)置不同的$b$，即為$?(v_i,[VNode])$和的所有空間編碼$b_{?(v_i,[VNode])}$和重置為一個不同的可學(xué)習(xí)標(biāo)量。

結(jié)果概覽及分析

這里我只截取了我比較關(guān)注的結(jié)果，更多結(jié)果請移步至原論文中查閱。首先從驅(qū)動任務(wù)出發(fā)，Graphormer來源于Kaggle比賽，是化學(xué)分子評分背景。在論文中，主要做了三個化學(xué)分子圖數(shù)據(jù)集：

• PCQM4M-LSC
• OGBG-MolPCBA
• OGBG-MolHIV

這里筆者只拿其中一個數(shù)據(jù)集得結(jié)果來分析。

PCQM4M-LSC數(shù)據(jù)集是量子化學(xué)數(shù)據(jù)集，里面是化學(xué)分子，對應(yīng)得任務(wù)是預(yù)測給定分子的重要特性HOMO-LUMO間隙，這里不用管這種特性是什么東西，我們只需要知道我們是對這種化學(xué)分子進行這種特征的評分就好了。因此，這是一個整個圖層面的回歸問題。

因此，上面 [VNode] 的設(shè)計就非常好，因為它實際上就先當(dāng)于一個ReadOut層，無需像以往部分研究那樣子為了實現(xiàn)圖層面任務(wù)而添加一個ReadOut層來獲取整個圖的表征。

再回到這里的實驗，根據(jù)數(shù)據(jù)集的統(tǒng)計結(jié)果（上面PPT右層）來看，這些化學(xué)分子是小圖，平均每個圖有14個節(jié)點，但數(shù)據(jù)集中包含很多個小圖。因此，這個數(shù)據(jù)集屬于小圖大數(shù)據(jù)集。

• 從消融實驗結(jié)果來看空間編碼： 這里的空間編碼比Graph上的拉普拉斯位置編碼（Laplacian PE)具有更好的性能（MAE:0.1427vs0.1483)。實際上，我們知道空間編碼的最短路徑實際上就可以通過鄰接矩陣來直接計算。雖然這篇論文中沒有這方面的對比，但筆者看到下面這位博主自己做的實驗：
  注，來源于：Graphormer實驗與刷榜

  可以看到，SPD換成鄰接矩陣Adj.好像差的不是很大。去掉Spatial Encoding效果居然還要好一點。筆者認(rèn)為對于這種小圖來說，復(fù)雜的空間編碼計算不如帶權(quán)鄰接矩陣來得直接，簡單。對小圖來說，可能更加簡單得編碼會更加合適。

• 從消融實驗結(jié)果來看節(jié)點重要性： 從實驗結(jié)果來看效果還不錯（MAE:0.1427vs0.1396）。筆者這里同樣也為節(jié)點的重要性一般來說對圖學(xué)習(xí)很重要性（主要看圖任務(wù)哈），因為很多GNN研究也會像這樣子把節(jié)點的各種中心性加入節(jié)點的特征中，此外，還有加入其他節(jié)點屬性特征的，比如節(jié)點的局部連接屬性，這里建議看一下圖論中節(jié)點的屬性。

• 從消融實驗結(jié)果來看邊特征引入方式： 可以看出，將邊特征編碼加入偏置中，對atttion具有更好的性能。為什么好呢，這里上面筆者將邊特征編碼的時候已經(jīng)介紹了，這里就不在贅述了。

GraphFormer

論文信息概覽

• paper name:《GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph》

• 原文鏈接：https://proceedings.neurips.cc/paper/2021/file/f18a6d1cde4b205199de8729a6637b42-Paper.pdf

• 源碼鏈接：https://github.com/microsoft/GraphFormers

• 來源：中科大, 微軟亞洲研究院, NeurIPS

• 數(shù)據(jù)背景：邊預(yù)測場景（主要在文本）

• 年限：2021

論文核心要點介紹

背景的了解

GraphFormer的驅(qū)動背景是文本圖的表示學(xué)習(xí)（Textual Graph Representation）。那么什么是文本圖表示學(xué)習(xí)呢？文本圖的表示學(xué)習(xí)是基于單個文本特征和鄰域信息為節(jié)點生成低維嵌入。文本圖的表示學(xué)習(xí)在推薦系統(tǒng)、文本檢索中的應(yīng)用廣泛。目前，對文本圖的表征學(xué)習(xí)的主要處理方式為：（1）首先通過預(yù)訓(xùn)練語言模型（PLM: Pretrained Language Model）對節(jié)點的文本特征進行獨立編碼； （2）然后通過圖神經(jīng)網(wǎng)絡(luò)GNN對文本嵌入進行聚合。因此，PLM與GNN的結(jié)合是生成高質(zhì)量文本圖表示的主流方法。

那前面我們也介紹了Transformer最初提出的場景是NLP場景。因此，這里的PLM模型也通常采用Transformer來實現(xiàn)。因此，怎么結(jié)合Transformer(也就是指這里的PLM)與GNN實現(xiàn)更好的效果? 這也是這篇論文主要的核心點。

要點介紹

在以往的文本圖表征研究中，通常借助先幾層PLM后GNN的級聯(lián)架構(gòu)，如PPT中Figure1中的（A)， 即先由 PLM（比如 BERT，Transformer的前身）生成各個節(jié)點的文本表示，再借助 GNN（比如 GraphSage）來融合中心節(jié)點與鄰域的語義。但GraphFormer作者認(rèn)為這種級聯(lián)架構(gòu)是一種相對低效的整合模式。因為在 PLM（Transformer） 的編碼階段，每個節(jié)點無法考慮其他鄰居節(jié)點的信息（文本圖領(lǐng)域指語義信息），因此，不利于生成高質(zhì)量的文本表示。
為此，GraphFormer作者采取了層級化的 PLM-GNN 整合方式，也就是將將 GNN 組件嵌套在 Transformer 語言模型中。如上面PPT中Figure1中的（B)。具體的流程如上面PPT下面的彩圖，也就是：

• Transformer層編碼獲取全局信息：首先，在每一層中，每個節(jié)點先由各自的 Transformer Block 進行獨立的語義編碼，編碼結(jié)果匯總為該層的特征向量（默認(rèn)由 CLS 所關(guān)聯(lián)的 hidden state 來表征）；
• GNN層獲取局部/鄰居信息：其次，各節(jié)點的特征向量匯集到該層的 GNN 模塊進行信息整合；之后信息整合的結(jié)果會被編碼至對應(yīng)各個節(jié)點的圖增廣（graph augmented）特征向量中，并分發(fā)至各個節(jié)點；
• 層疊Transformer&GNN：然后，各節(jié)點會依照圖增廣特征向量再進行下一層級的編碼，以此層疊。

比前面直接拼接的方式相比，GraphFormers 在 PLM （如Transformer）編碼階段充分考慮了來自GNN中的鄰域信息。筆者認(rèn)為這種結(jié)構(gòu)在文本領(lǐng)域可以更好的融合局部信息和全局信息。

結(jié)果概覽及分析

因為核心內(nèi)容主要就是采用層級嵌套的結(jié)構(gòu)，所以下面我們直接看結(jié)果吧。這里同樣我只放我關(guān)注的實驗結(jié)果。（論文中做的數(shù)據(jù)集實驗主要是“邊預(yù)測任務(wù)“上三個大規(guī)模的文本圖數(shù)據(jù)集，因此，這里與前面Graphormer的小圖數(shù)據(jù)集不同是大規(guī)模文本數(shù)據(jù)集）
從上面PPT右層的實驗結(jié)果來看，層級的結(jié)構(gòu)具有更好性能。而且可以發(fā)現(xiàn)PLM+Max是次優(yōu)的，可能數(shù)據(jù)中Max的影響比較大，或者有部分噪聲?

總結(jié)

下期預(yù)告

為了跟上面Graph Transformer的模型做對比，筆者下期將公開自己的另外一篇筆記《GATNE的論文筆記》，而不是圖注意力筆記篇章。文章來源地址http://www.zghlxwxcb.cn/news/detail-424918.html

到了這里，關(guān)于【圖-注意力筆記，篇章2】Graphormer 和 GraphFormers論文筆記之兩篇經(jīng)典Graph Transformer來入門的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！