作者 | Jiawei Zhang、Haopeng Zhang、Congying Xia、Li Sun
譯者 | 凱隱
編輯 | Jane
出品 | AI科技大本營（ID：rgznai100）
【導讀】本文提出了一種全新的圖神經網絡 Graph-Bert，僅僅基於 Attention 機制而不依賴任何類卷積或聚合操作即可學習圖的表示，並且完全不考慮節點之間的連接信息。通過將原始圖分解為以每個節點為中心的多個子圖來學習每個節點的表徵信息，這不僅能解決圖模型的預訓練問題，還能通過並行處理還提高效率。
論文地址：
https://arxiv.org/abs/2001.05140
簡介
傳統的圖神經網絡存在許多嚴重影響模型性能的問題，例如模型假死和過於平滑問題。模型假死和過於平滑都可以歸結於傳統 GNN 的類卷積特徵學習方式以及基於聚合操作（mean，max，sum）的信息更新方式，這會導致隨著模型層數加深，模型會逐漸喪失對輸入的響應，因此一般GNN都是只堆疊不超過兩層。同時，模型學習到的不同節點的表徵信息也會愈發相似，從而變得無法區分。此外，由於傳統GNN都考慮圖中的固有內在連接（即邊），因此無法對圖數據進行並行化處理。
為了解決以上問題，本文提出了Graph-Bert，Bert 是一個用於NLP的模型，其核心在於 attention 機制，將這種機制拓展到圖結構數據上，便是 Graph-Bert。Graph-Bert 將原始圖採樣為多個子圖，並且只利用attention機制在子圖上進行表徵學習，而不考慮子圖中的邊信息。因此Graph-Bert可以解決上面提到的傳統GNN具有的性能問題和效率問題。
此外，傳統 GNN 受限於圖結構的多樣性，無法進行跨任務的預訓練，而 Graph-Bert 由於不考慮圖中的邊信息，因此並不受限於圖結構，可以很好地進行預訓練和遷移學習。
模型結構介紹
Graph-Bert 主要由四部分組成：
1、將原始圖分解為無邊子圖（不考慮子圖中的邊信息）
2、節點輸入特徵的嵌入表示
3、基於圖transformer的節點表徵學習編碼器，編碼器的輸出作為學習到的節點特徵表示。
4、基於圖transformer的解碼器
（一）無邊子圖分解
這部分對應上圖中的step1，主要將原始輸入圖分解為多個子圖，每個子圖都包含一個中心節點和固定數量的鄰居節點，鄰居節點就代表了中心節點的上下文信息，因此如何為中心節點選取鄰居節點是這一步的關鍵。方法有很多種，本文採用的是top-K關係值方法，類似於KNN算法，計算每個節點與其他所有節點的關聯（intimacy）程度，然後選取關係值最大的前K個點作為鄰接節點。關係矩陣的計算方法採用pagerank算法：
表示列歸一化（隨機遊走歸一化）的鄰接矩陣A，即
，D 是度矩陣，注意A和D都是相對於輸入圖而言的。給定圖G以及該圖的關係矩陣S，那麼就可以得到圖中任意節點vi的上下文信息：
這裡節點vi的鄰居節點vj既可以是距離較近的，也可以是距離較遠的，並不局限於邊連接。
（二）節點輸入特徵嵌入表示
節點的排序不同於圖片像素和句子中的詞，圖的節點並沒有明確的順序，理論上我們在表示節點特徵時，交換任何兩個節點在矩陣中的順序都不應該影響最終結果（置換不變性），然而在用矩陣表示節點特徵信息時，矩陣的行/列必須和權重矩陣（例如FC層）列/行進行對應，否則即便是同一特徵矩陣，在不同的行排列下也會得到不同的計算結果，這顯然是不合理的。因此還是需要按照一定的順序來對每個子圖的輸入節點特徵向量（矩陣）進行排序，從而得到特徵矩陣（張量）。這裡按照前面計算得到的關聯值由大到小進行排序。
特徵向量嵌入表示通過四種方法來逐步得到每個節點特徵向量的嵌入表示：
1、原始特徵向量嵌入
這一步主要將原始特徵嵌入到一個新的特徵空間，對於不同類型的輸入數據可以使用不同的Embed函數，例如對於圖片可以使用CNN，對於序列信息則可以使用LSTM。
2、Weisfeiler-Lehman 絕對角色嵌入
這一步學習每個節點在全局圖（即輸入圖）中的唯一表示，通過WL算法完成。WL算法根據節點在圖中的結構位置來標記節點，結構位置相同的節點會得到相同的標記，這裡的結構位置是指節點在完整圖（而不是子圖）中的位置，因此與子圖無關。節點的WL絕對角色嵌入向量計算方法為：
這一步主要是獲取節點全局位置的信息，詳細細節可以參考原文。
3、基於關聯值的相對位置嵌入
相較於上一步基於WL的全局位置嵌入，這一步主要是獲取節點在子圖中的局部信息：
P是一個位置函數，對於中心節點vi，P(vi)=1，對於其他的周圍節點vj，和vi關聯值越大，P(vj)越小。
4、基於節點距離的相對距離嵌入
這一步主要是平衡上面兩步的嵌入值，通過計算兩個節點在原始圖（考慮邊）中的相隔的邊距離來計算嵌入值：
由於這一步是基於全局圖的，因此不同子圖中的相同節點之間得到的H值是相同的。
（三）基於編碼-解碼器的圖Transformer
谷歌提出的Transformer模型是一種基於全attention的sequence to sequence模型，在NLP任務上取得了比LSTM更好的成績。這裡將Transformer方法推廣到了圖結構數據。首先將上面計算到的四種嵌入表示聚合，以作為編碼器的輸入：
聚合方法可以有多種，例如max, sum, mean等。之後通過多層attention操作來逐步更新節點的表示：
QKV都是輸入特徵矩陣H(l-1)的複製，這裡額外添加了一個mask矩陣M，可以學習到子圖的上下文信息。
整個Transoformer包含2K層，前K層是編碼器，後K層是解碼器，通過自回歸來監督訓練，最終編碼器的輸出即為學習到的節點特徵表示zi。此外還在編碼器輸入和輸入之間添加了res連接。
Graph-Bert預訓練與微調
主要介紹 Graph-Bert 在圖表徵學習任務中的預訓練和微調，對於預訓練，主要考慮節點屬性重建以及圖結構恢復任務，對於表徵學習相關應用，主要考慮節點分類和圖聚類任務。
（一）模型預訓練1、節點原始特徵重建
如何從學習到的節點特徵表示中還原原始輸入特徵是採用預訓練模型時需要關注的點：
在監督時自然採用和編碼-解碼器相同的監督方式：
考慮到節點的特徵可能非常稀疏，這裡額外加入了一個Mask矩陣：
2、圖結構重建
通過圖結構重建來保證模型能學習到圖的結構信息，該任務依然是作為預訓練任務。圖的結構可以用一個標籤向量y來表示，yij表示節點i和j之間的連接關係，包含兩個值（i->j, j->i），因此我們需要預測的是：
損失函數採用多類交叉熵損失函數即可：
考慮到圖比較稀疏時，大部分節點之間都沒有連接（例如對於一個總節點數為100，平均1階鄰居節點數為5的圖，其鄰接矩陣就有95%的地方為0），需要對負例（即無連接的節點對）進行採樣來保證正負例平衡。
通過將上述兩種不同的學習任務與變量正則化項結合，我們可以定義正式訓練前的目標函數。通過優化該目標函數將有助於對Graph-Bert進行有效的預訓練。
（二）模型遷移與微調
在將Graph-Bert應用在新任務中時，既可以直接使用模型學習到的圖特徵表示，也可以根據實際情況做一些必要的調整。這裡主要考慮節點分類和圖聚類任務，其中圖聚類任務可以直接使用學習到的特徵表示，而節點分類還需要做一些調整。
1、節點分類
通過額外添加FC層和softmax來進行節點分類：
相應的損失函數為：
因此額外需要訓練的就是FC層，通過將FC層和原來的Graph-Bert結合，並重新訓練，就可以完成節點分類的任務。
2、圖聚類
圖聚類主要是將圖中的節點分為多類，由於聚類屬於非監督的無參算法，因此不需要額外添加權重，直接在學習到的節點特徵上進行聚類即可，使用諸如K-means的算法就可以完成，需要優化的目標函數為：
該函數中仍然包含了一些變量，可以用EM算法來高效地學習，而不是反向傳播。
總結
本文提出的Graph-Bert模型屬於Bert模型在圖結構數據上的拓展，在一定程度上降低了對節點間固有連接的依賴，使得模型可以更好的進行預訓練和並行計算。筆者個人認為這種思想和點雲很相似，具體區別還有待探究。
（*本文為AI科技大本營翻譯文章，轉載請微信聯繫 1092722531）
1、評選進行中，參與投票即有機會參與抽獎，60+公開課免費學習
疫情嚴重，潛伏期也有傳染性？科技公司在行動召喚超參調優開源新神器：集XGBoost、TensorFlow、PyTorch、MXNet等十大模塊於一身5個可以幫助你提高工作效率的新AI工具亞馬遜機器學習服務：深入研究AWS SageMaker從4個月到7天，Netflix開源Python框架Metaflow有何提升性能的魔法？管理7k+工作流，月運行超10000萬次，Lyft開源的Flyte平臺意味著什麼？伯克利新無監督強化學習方法：減少混沌所產生的突現行為機器推理文本+視覺，跨模態預訓練新進展