圖神經網絡(GNN)主要是利用神經網絡處理復雜的圖數據，它將圖數據轉換到低維空間，同時最大限度保留結構和屬性信息，并構造一個用于訓練和推理的神經網絡。在實際應用中，為了加速GNN訓練和新算法的快速迭代，設計一套統一的圖計算框架面臨著巨大的挑戰。近日，阿里巴巴在阿里云峰會北京站上重磅推出了大規模圖神經網絡平臺AliGraph，本文是AI前線第74篇論文導讀，我們將深入了解阿里圖神經網絡庫AliGraph背后的系統架構細節和內部自研的GNN算法原理。

介紹

圖作為一種復雜的模型，已廣泛應用于各種現實應用中的建模和管理數據。典型的例子包括社交網絡、物理系統、生物網絡和知識圖譜等。圖分析探索隱藏在圖數據中的潛在洞察，在過去的十年，引起了人們極大的關注。它們在許多領域發揮了重要的作用，如節點分類、鏈接預測、圖聚類和推薦系統等。

由于傳統的圖分析任務經常面臨著高額的計算和空間成本，一種稱為圖嵌入（GE）的新范式為解決此類問題提供了一種高效的方法。具體地說，圖嵌入（GE）是將圖數據轉換為低維空間，以最大程度保留圖中結構和內容信息。之后，生成的嵌入作為特征輸入到下游機器學習任務中。此外，結合深度學習技術，通過將圖嵌入（GE）與卷積神經網絡（CNN）相結合，提出了圖神經網絡（GNN）。在CNN中，采用共享權重和多層結構來增強其學習能力。圖是最典型的局部連接結構，共享權值以降低計算成本，多層結構是處理層次模式的關鍵同時可以捕獲各種變化尺寸的特征。GNN是CNN在圖上的一種推廣。因此，GNN不但擁有圖嵌入（GE）的靈活性，而且在有效性和魯棒性兩個方面展示了其優越性。

GNN面臨的挑戰

當前已有大量論文貢獻了大量精力在開發圖嵌入（GE）和GNN算法方面上，這些工作主要集中在沒有或者有少量輔助信息的簡單圖上。然而，大數據和復雜系統的興起揭示了圖數據上的新洞察。這是一種共識，絕大多數與現實商業場景相關的圖數據表現出四個特點，即大規模、異構、屬性化和動態。例如，現在的電商的圖通常包含數十億個頂點和邊，這些頂點和邊具有各種類型和豐富的屬性，并且會隨著時間的推移快速演變。這些特性為嵌入和表征圖數據帶來了巨大的挑戰，如下所示：

GNN的核心步驟特別針對網格結構（grid structures）進行了優化，但不適用于不規則歐幾里得空間中的圖。因此，現有的GNN方法無法在具有極大尺寸的真實圖上進行縮放。第一個問題是如何提高大規模圖上GNN的時間和空間效率？

不同類型的對象從不同的視角描述數據。它們提供了豐富的信息，但是增加了將圖信息映射到單個空間的難度。因此，第二個問題是如何將異構信息優雅地集成到一個統一的嵌入結果中？

屬性信息可以進一步增強嵌入結果的能力并且使圖嵌入規約成為可能。在不考慮屬性信息的情況下，這些算法只能直推學習，而忽略了預測未知實例的必要性。然而，拓撲結構信息和非結構屬性信息通常呈現在兩個不同的空間中。因此，第三個問題是如何統一保存和定義它們的信息？

由于GNN的效率較低，從零開始更新結構和上下文信息，然后重新計算圖嵌入結果非常昂貴。因此，第四個問題是如何設計動態的有效增量GNN方法？

論文貢獻

為了應對上述挑戰，大量的研究工作致力于設計高效并且有效的GNN方法。在表1中，基于不同工作的關注點以及我們內部開發的模型（黃色陰影部分），我們對一系列流行的GE和GNN模型進行了分類。

如圖所示，大多數現有方法同時集中在一個或兩個屬性上。然而，現實世界中的商業數據通常面臨更多的挑戰。為了緩解這種情況，在本文中，我們提出了一個全面而系統的GNN解決方案。我們設計并實現了一個名為AliGraph的圖神經網絡平臺，它提供了一套對應的系統和算法來解決更實際的問題，以更好地支持各種GNN方法和應用。

AliGraph的主要貢獻包括：

系統

在Aligraph的基礎組件中，我們構建了一個支持GNN算法和應用的系統。系統結構是從通用GNN方法中抽象出來的，它由存儲層、采樣層和操作層組成。具體來說，存儲層應用了三種新技術，即結構化和屬性化的特定存儲，圖劃分和緩存一些重要頂點的領域，來存儲大規模的原始數據以滿足高級操作和算法的快速數據訪問要求。

采樣層優化了GNN方法中的關鍵采樣操作。我們將抽樣方法分為三類，即橫向抽樣（TRAVERSE）、領域抽樣（NEIGHBORHOOD）和反向抽樣（NEGATIVE），并提出了在分布式環境下進行采樣操作的無鎖方法。

操作層提供了GNN算法中兩個常用的應用操作的優化實現，即聚合（AGGREGATE）和組合(COMBINE)。我們應用緩存策略來存儲中間結果，以加速計算過程。這些組件是共同設計和共同優化的，以使整個系統有效和可擴展。

算法

系統提供了一個靈活的接口來設計GNN算法。我們的研究結果表明，所有現有的GNN方法都可以很容易地在我們系統上實現。此外，我們內部還為實際需求開發了幾個新的GNN算法。如表1所示，我們內部開發的方法用黃色陰影表示，每種方法在處理實際問題時都更加靈活和實用。

AliGraph平臺已經在阿里巴巴公司內部實際部署。實驗結果從系統和算法兩方面驗證了其有效性和效率。如圖1所示，我們內部在AliGraph平臺上開發的GNN模型，將標準化評估指標提高了4.12%-17.19%。其中數據來自阿里巴巴的電商平臺淘寶，我們會將此數據集（預計在2019年5月）貢獻給社區，以推動該領域進一步發展。

預備知識

在本節中，表2總結了本文中常見的符號和標記。

屬性異構圖

為了全面描述現實世界中的商業數據，實際圖往往包含豐富的內容信息，如頂點的多種類型、邊的多種類型和屬性等，因此我們進一步定義屬性異構圖（AHG）。AHG是一個元組(V,ε,W，TV,TE,AV,AE)，其中V,ε和W跟簡單圖具有相同的含義。T(V)：V–\u0026gt;F(V)和T(E)：ε–\u0026gt;F(E)表示頂點類型和邊類型的映射函數。為了確保異構性，我們要求|FV|大于等于2和（或）|FE|大于等于2。A(v)和A(E)兩個函數，為每個頂點v和每個邊e分配一些表征其屬性的特征向量。我們將頂點v和邊e的第i個特征向量分別表示為x(v,i)和w(e,i)。AHG的一個例子如圖2所示，它包含兩種類型的頂點，即user和item，以及連接它們的四種類型的邊。

動態圖

現實世界中圖通常隨著時間而演化。給定一個時間間隔[1,T]，動態圖是一個系列的圖G(1),G(2),…,G(T)。對于每個t大于等于1并且小于等于T，G(T)是一個簡單圖或者一個AHG。為了便于記憶，我們添加一個上標t來表示時間戳t處對象的對應狀態。例如，V(t) 和E(t)分別表示圖G(t)的頂點集和邊集合。

問題定義

給定一個輸入圖G，它是一個簡單的圖或者AHG，預先定義一個嵌入維度d ∈ N，其中d \u0026lt;\u0026lt; |V|，在盡可能保留圖性質的前提下，嵌入問題是將圖G轉換到d維空間。GNN是一種特殊的圖嵌入方法，它將神經網絡應用在圖上，學習嵌入結果。注意，在本文中，我們主要關注頂點級別的嵌入。也就是說，對于每個頂點v，嵌入輸出結果是一個d維度的向量h(v)。我們在第7節中討論未來工作中，我們還將考慮邊的嵌入、子圖嵌入甚至是整個圖的嵌入。

AliGraph系統詳解

Aligraph平臺架構如圖3所示，我們設計并實現了一個底層系統（用淺藍色方塊標記），以更好地支持高級別的GNN算法和應用。本節將介紹該系統的詳細信息，在第3.1節中，我們抽象了一個GNN的通用框架來解釋為什么我們的系統是這樣設計的；第3.2至3.5介紹了系統中每個關鍵組件的設計和實現細節。

3.1 GNN算法框架

在本小節中，我們將為GNN算法抽象為一個通用框架。一系列經典的GNN，如?Structure2Vec，GCN，FastGCN，AS-GCN和GraphSAGE?可以通過在框架中實例化操作器來描述。GNN框架的輸入包含一個圖G，嵌入維度d ∈ N，每個頂點 v ∈ V的頂點特征x(v)，鄰居的最大跳數k(max)。對于每個頂點?v ∈ V，GNN的輸出是一個嵌入向量h(v)，將被送入下游機器學習任務，如分類、鏈接預測等。

算法1是對GNN框架的描述。在最開始，頂點v的嵌入向量h(v)(0)被初始化為等于輸入屬性向量x(v)。然后，在每個k處，每個頂點v聚合其鄰居頂點的嵌入向量，以更新自身的嵌入向量。具體地說，我們應用樣本函數在頂點v的領域集Nb(v) 的基礎上提取一個頂點的子集S，用聚合函數對所有頂點u ∈ S的嵌入進行聚合，得到一個向量 h^(v)，并將h^(v)與 h(v)(k-1) 通過組合函數生成嵌入向量h(v)(k) 。在處理完所有的頂點后，嵌入向量被歸一化。最后，經過k(max) 跳后，
h(v)(k(max)) 作為頂點v的嵌入結果 h(v)返回。

基于上面描述的GNN框架，我們構建了AliGraph平臺的系統架構，如上一節圖3所示。平臺總體由五層組成，其中三個底層構成了系統以支持算法層和應用層。在系統內部，存儲層對不同類型的原始數據進行組織和存儲，以滿足高級操作和算法的快速數據訪問要求。

在此基礎上，通過算法1，我們發現三個主要的算子在各種GNN算法中起著重要的作用，即采樣、聚合和組合。其中，采樣操作為聚合和組合操作奠定了基礎，因為它直接控制了要處理的信息范圍。因此，我們設計了采樣層來訪問存儲，以便快速準確地生成訓練樣本。在此之上，操作層專門優化聚合和組合函數。在系統的基礎上，可以在算法層構建GNN算法，為應用層的實際任務提供服務。

3.2 存儲

在本小節中，我們將討論如何存儲和組織原始數據。存儲現實世界的圖的空間成本非常大，常見的電子商務圖可以包含數百億個節點和數百億個邊，存儲成本很容易超過10TB。圖的大尺寸給有效訪問帶來了巨大的挑戰，特別是在集群的分布式環境中。為了更好地支持高級運算操作和算法，我們在AliGraph的存儲層中應用了以下三種策略。

圖分區

Aligraph平臺建立在一個分布式環境中，因此整個圖被切分并分別存儲在不同的work節點。圖分區的目標是最小化交叉邊（crossing edges）的數量，其的端點（endpoints）分布在不同的work節點上。為此，文獻工作中提出一系列算法。

我們實現了四個內置的圖分區算法：（1）METIS；（2）頂點切割和邊切割分區；（3）2-D分區；（4）流式分區策略，這四種算法適用于不同的環境。簡而言之，METIS專門處理稀疏圖；頂點切割和邊切割分區在稠密圖上表現更好；在woker數量固定時，通常使用2-D分區；而流式分區方法通常應用于邊更新頻繁的圖上。用戶可以根據自己的需要選擇最佳的分區策略，此外，他們還可以將其他圖分區算法實現為系統中的插件。

在算法2中，第1-4行給出了圖分區的界面。對于每個邊e，第4行中的通用ASSIGN函數將根據它的端點（endpoint）計算出e在哪個woker節點中。

單獨存儲屬性

對于AHG，我們需要在每個work節點中存儲分區圖的結構和屬性。圖的結構信息可以簡單地用鄰接表存儲。也就是說，對于每個頂點v，我們存儲它的鄰居集Nb(v)。然而，對于兩個頂點的屬性和邊，不建議將它們存儲在鄰接表中。原因有兩方面：

屬性通常需要更多的空間。例如，存儲頂點id的空間成本最多為8字節，而頂點上的屬性可能在0.1KB到1KB之間。

不同頂點和邊之間的屬性有很大的重疊。例如，許多頂點可能具有相同的標記”man“，表示其性別。因此，單獨存儲屬性更為合理。

在我們的系統中，我們通過構建兩個索引I(v)和I(e)分別在頂點和邊上存儲屬性。如圖4所示，在鄰接表中，對于每個頂點u，我們將屬性Av(u)的索引存儲在I(v)中。對于每個邊（u,v），我們也將屬性Ae(u,v)存儲在I(e)中。假設N(D)和N(L)分別是鄰居數量的平均值和屬性長度的平均值。設N(D)為頂點和邊上不同屬性的數目。顯然，我們單獨存儲策略將空間成本從O(n*ND*NL)降低到O(n*ND+NA*NL)。

緩存重要頂點的鄰居

在每個work節點，我們進一步提出了一種局部緩存重要頂點的鄰居的方法，以降低通信成本。如果一個頂點v經常被其他頂點訪問，我們可以在它發生的每個分區中存儲它的外部鄰居。這樣做可以大大降低其他頂點通過v訪問相鄰頂點的開銷。但是，如果v的鄰居數目很大，存儲v的鄰居的多個副本也會產生巨大的存儲空間成本。為了更好地權衡，我們定義了一個度量來評估每個頂點的重要性，決定一個頂點是否值得緩存。

假設Di(v)(k)和Do(v)(k)分別表示頂點v的k-hop 入和出的鄰居的數目。那么Di(v)(k)和Do(v)(k)就可以衡量緩存頂點v的外部鄰居的收益和成本。因此，頂點v第k重要性表示為Imp(v)(k)，定義如下：

在算法2中，第5-9行給出了緩存重要頂點的鄰居的過程。假設h表示鄰居的最大深度。對于每個頂點v，我們緩存頂點v的1到k-hop的外部鄰居頂點，在Imp(v)(k)大于等于τk的條件下。其中，τk是用戶指定的閾值。注意，將h設置為一個小數字（通常為2）就足夠支持一系列實際的GNN算法。實際上，我們發現τk不是一個敏感參數。通過實驗評估，將τk設置為0.2左右可以在緩存成本和收益之間進行最佳的權衡。

有趣的是，我們發現要緩存的頂點只是整個圖的一小部分。Di(v)(1)和Do(v)(1)在實際圖中經常服從冪律分布。也就是說，在圖中只有很少的頂點具有較大的出入度。基于此，我們得到了以下兩個定理。

定理2表明圖中只有極少數頂點是重要級別比較高的，這意味著，我們只需緩存少量重要頂點就可以顯著降低圖遍歷的成本。

3.3 采樣

回想一下，GNN算法依靠聚合鄰居信息來生成每個頂點的嵌入。然而，現實世界圖的度的分布往往是偏度的，這使得卷積運算難以操作。為了解決這個問題，現有的GNN通常采用各種抽樣策略來對大小一致的鄰居子集進行抽樣。由于它的重要性，我們在AliGraph中抽象了一個特定的采樣層來優化采樣策略。

概要

形式上，采樣函數接受一個頂點子集V(T)的輸入，抽取一個小的子集V(S)，|V(S)|\u0026lt;\u0026lt;|V(T)|。通過對現有GNN模型的調研，我們抽象出三種不同的采樣器，即遍歷、鄰域、負采樣。

• 遍歷（TRAVERSE）：用于從整個分區圖中，采樣一批頂點或邊。

• 鄰域（NEIGHBORHOOD）：將生成頂點的上下文。該頂點的上下文可以是一個或多個hop鄰居，用于對該頂點進行編碼。

• 負采樣（NEGATIV）：用于生成負樣本以加速訓練過程的收斂。

實現

在文獻中，抽樣方法對提高GNN算法的效率和準確性起著重要的作用。在我們的系統中，采樣器都以插件的形式存在。這三種采樣器可以實現如下：

• 對于遍歷采樣器，他們從局部圖中獲取數據。

• 對于領域采樣器，他們可以從本地存儲獲取一跳（one-hop）鄰居，也可以從本地緩存獲取多跳（multi-hop）鄰居。如果沒有緩存頂點的鄰居，則需要從遠程圖服務器調用。當獲取一批頂點的上下文時，我們首先將頂點劃分為子批，并從相應的圖服務器上獲得返回結果后，每個子批的上下文將被拼接在一起。

• 負采樣器通常從本地圖服務器生成樣本。對于某些特殊情況，可能需要從其他圖服務器進行負采樣。負采樣在算法上是靈活的，我們不需要批量調用所有的圖服務器。

總之，一個典型的采樣階段可以實現為如圖5所示。

我們可以通過采用動態權重的幾種有效采樣策略來加速訓練。我們在采樣器的反向計算中實現更新操作，就像反向傳播的運算一樣。所以，當需要更新時，我們應該做的是為采樣器注冊一個梯度函數。更新模式是同步還是異步，由訓練算法決定。

到目前為止，讀取和更新都將在內存中的圖存儲上進行，這可能導致性能下降。根據鄰居需要，該圖由源頂點分割。在此基礎上，我們將圖服務器上的頂點分組。每個組都將與一個請求流桶相關，其中的操作（包括讀取和更新）都與該組中的頂點有關。桶是一個無鎖隊列，如圖6所示，我們將每個bucket綁定到一個CPU內核，然后，桶中的每個操作都按順序處理，不加鎖進一步提高了系統的效率。

3.4 運算符

概要

采樣后，輸出的數據被對齊，處理起來就會容易很多。在采樣器上，我們需要一些類似GNN的運算符來使用它們。在我們的系統中，我們抽象了兩種運算符，即聚合和組合。他們的作用如下：

• 聚合：收集每個頂點的鄰居信息以生成統一的結果。例如，算法1中的聚合算法將一系列向量h(u)映射到單個向量h^(v)，其中u屬于v的采樣鄰居節點。h^(v)是一個中間結果為了進一步生成h(k)(v)。聚合函數從周圍鄰居收集信息，它可以用作卷積操作。各種聚合方法被應用在不同的GNN中，例如，元素平均值、最大池化神經網絡和LSTM。

• 組合： 負責如何使用頂點的鄰居來描述頂點。在算法1中，組合函數映射兩個向量h(v)(k-1)和h^(v)為一個向量h(v)(k)。組合函數可以將前一跳和領域的信息集成到一個統一的空間中。通常，現有的GNN方法中，h(v)(k-1)和h^(u)求和然后輸入到神經網絡中。

實現

采樣器和類似GNN的運算符不僅可以前向運算，還可以反向運算，以便更新參數，使整個模型成為端到端的訓練網絡。考慮到圖數據的特點，為了獲得更好的性能，可以考慮大量的優化。一個典型的運算符由前向和后向的運算組成，以便參與到深層網絡的訓練中。用戶可以在基于運算符的基礎上，快速構建GNN算法。

為了進一步加速這兩個算子的運算，我們通過應用策略將中間結果向量h(v)(k)緩存。在訓練過程中的每個mini-batch中，所有頂點我們可以共享采樣鄰居集合。同樣，在同一個mini-batch中，對于所有的k\u0026gt;=1且k\u0026lt;=k(max)，我們也可以共享向量h(v)(k)。為此，我們將k(max)個h^v(1)、h^v(2)、…h^v(kmax)向量存儲為mini-batch中所有頂點的最新向量。在聚合函數中，我們利用向量h^v(1)、h^v(2)、…h^v(kmax)來獲取h^(v)。然后，我們通過應用組合函數計算h^(v)和h(v)(k-1)來獲得h^(v)(k)。最后，存儲的向量h^(k)通過h^(v)(k)更新。通過這種策略，運算符的計算成本可以大大減小。

方法論

在系統的基礎上，我們來討論算法的設計。我們的研究結果表明，現有的GNN在AliGraph上非常容易創建。此外，我們還提出了一系列新的GNN算法，以解決第1節中總結的真實世界的圖數據嵌入的四個新挑戰。它們在AliGraph平臺算法層以插件形式供用戶使用。

4.1 GNN最佳實踐

由于AliGraph平臺是基于通用GNN算法抽象出來的，因此現有的GNN可以很容易地在這個平臺上實現。具體來說，表1中列出的GNN都可以按照算法1中的框架構建在AliGraph中。這里我們以GraphSAGE為例進行簡要介紹，其他GNN也可以用類似的方式實現。對于GraphSAGE，它應用簡單的逐節點采樣，從每個頂點的相鄰集中提取一個子集。顯然，這一采樣策略通過我們的采樣運算符很容易就能實現。然后，我們需要在算法1中實例化聚合和組合函數。GraphSAGE可以在第4行的聚合函數中應用加權元素平均。此外，也可以使用其他更復雜的函數，如maxpooling 神經網絡和LSTM神經網絡。在其他的GNN方法中，如GCN、FastGCN和AS-GCN，我們可以在抽樣、聚合和組合上替換不同的策略。

4.2 阿里內部開發的GNNs

我們內部開發的GNN專注于不同方面，例如：采樣（AHEP）、復合邊（GATNE）、多模態（Mixture GNN）、層次（Hierarchical GNN）、動態（Evolving GNN）和多源信息（Bayesian GNN）。

AHEP算法

該算法是為了減輕傳統嵌入傳播（EP）算法在異構網絡（HEP）上的繁重計算和存儲成本而設計的。HEP遵循GNN的總體框架，對AHG進行了細微修改。

在HEP中，所有的頂點嵌入都是以迭代的方式生成的。在第k次hop中，對于每個頂點v和每個節點類型c，c中v的所有鄰居u，傳播其嵌入h(u,c)給v來重構一個h^(v,c)嵌入。然后，跨所有節點類型連接h^(v,c)嵌入來更新v的嵌入。但是，在AHEP（HEP用自適應抽樣）中，我們只對重要的鄰居進行抽樣，而不考慮所有鄰居。

我們設計了一個度量，通過結合每個頂點的結構信息和特征來評估其重要性。之后，根據相應的概率分布，分別對不同類型的所有鄰居進行采樣。我們仔細設計了概率分布，以最小化抽樣方差。在特定任務中，為了優化AHEP算法，損失函數一般可以描述為：

其中，L(SL)是批處理中監督學習的損失，L(EP)是批處理采樣時的嵌入傳播損失，Ω(Θ)是所有可訓練參數的正則化，α, β是兩個超參數。根據第5節的實驗結果驗證，AHEP的運行速度比HEP快得多，同時達到了相當的精度。

GATNE算法

該算法用于處理頂點和邊上具有異構和屬性信息的圖。為了解決上述問題，我們提出了一種既能捕獲豐富屬性信息，又能利用不同節點類型的多重拓撲結構新方法，即通用的屬性多重異構網絡嵌入，簡稱GATNE。

每個頂點的整體嵌入結果由三部分組成：通用嵌入、特定嵌入和屬性嵌入，分別對應描述結構信息、異構信息和屬性信息。對于每個頂點v和任何節點類型c，通用的嵌入b(v)和屬性嵌入f(v)保持相同。設t為可調超參數，當1 ≤ t^ ≤ t時 g(v,t^)是元-特定嵌入。特定嵌入是通過連接所有的g(v,t^)得到。然后，對于每種類型c，所有的h(v,c)嵌入如下：

其中，α?和β?是反映特定嵌入和屬性嵌入重要性的兩個可調參數；利用注意力機制計算系數矩陣a?；M? and D是兩個可訓練的變化矩陣。最終嵌入結果h(v)可以通過連接所有的h(v,c)。

嵌入可以應用類似于隨機游走的方法學習。具體來說，在隨機游走中給定c類型的頂點v和窗口大小p，設v(-p),v(-p+1),…v,v(1),…v§表示其上下文。我們需要最小化negative log-likelihood：

Mixture GNN算法

該模型是一個混合的GNN模型，用于處理多模態的異構圖。在這個模型中，我們擴展了異構圖上的skip-gram模型，以適應異構圖上的多義場景。在傳統的skip-gram模型中，我們試圖尋找參數為θ的圖嵌入，通過最大化似然函數：

其中，Nb(v)表示v的鄰居，Prθ(u|v)表示softmax函數，在我們對異構圖上的設置中，每個節點有多感知。為了區分它們，假設P是節點感知的已知分布。我們將目標函數改寫為：

此時，很難結合負采樣方法直接優化等式（6）。或者，我們推導出一個新的方程（6）的下界L(low)，并嘗試最大化L(low)。我們發現下界L(low)可以用負采樣近似。因此，在現有的工作中，如Deepwalk和node2vec中，通過稍微修改采樣過程，可以很容易地實現訓練過程。

層次GNN算法

當前的GNN方法本質上是扁平的，并不學習圖的層次表征。這個限制對于明確研究不同類型用戶行為的相似性問題時尤其明顯。層次GNN算法模型組合了層次結構，增強了GNN的表達能力。

假設H(k)表示在GNN的k步之后，計算節點的嵌入矩陣。A是圖G的鄰接矩陣，在算法1中，傳統的GNN迭代學習H(k)通過組合H(k-1)、A和一些可訓練的參數θ(k)。開始，我們設置H(0)=X，其中X表示節點特征的矩陣。在我們的層次GNN中，我們以層級方式學習嵌入結果。具體來說，讓A(l)和X(l)分別表示第l層中的鄰接矩陣和節點特征矩陣。通過輸入A(l)和X(l)到單層GNN來學習第l層的節點嵌入向量結果矩陣Z(l)。

在此之后，我們對圖中的一些頂點進行聚類，并將鄰接矩陣A(l)更新為A(l+1)。設S(l)表示在第l層中的可學習的賦值矩陣。S(l)中的每一行和每一列分別對應第l層和(l+1)層中的一個聚類。S(l)可以通過在另外一個pooling GNN的A(l)和X(l)上應用softmax函數獲得。利用Z(l)和S(l)，我們可以為第l+1層獲得一個新的粗粒度鄰接矩陣A(l+1)=S(l)(T)*A(l)*S(l)和一個新的特征矩陣X(l+1)=S(l)(T)*Z(l)。如第5節所驗證的，多層的層次GNN比單層傳統GNN更有效。

動態演化的（Evolving）GNN算法

這個模型用于在動態網絡設置中的頂點嵌入。我們的目標是學習圖序列（G(1),G(2),G(3),…G(T)）中頂點的表征。

為了捕獲動態圖的演化性質，我們將演化鏈接分為兩種類型：（1）正常演化代表邊的大部分合理的變化；（2）突發鏈接代表稀有和異常的邊演化。

在此基礎上，以交錯方式學習動態圖中的所有頂點的嵌入。在時間戳t處，圖G(t)上找到的正常和突發的鏈接與GraphSAGE模型集成，以生成G(t)中每個頂點v的嵌入結果h(v)。然后，我們利用變分自動編碼器和RNN模型對圖G(t+1)上的正常和突發信息進行預測。該過程在迭代中執行，以在每個時間戳t輸出每個頂點v的嵌入結果。

貝葉斯GNN算法

該模型通過貝葉斯框架集成了兩種信息源，即知識圖譜嵌入或行為圖嵌入。它模擬了認知科學中人類的理解過程，在這個過程中，每一種認知都是通過調整特定任務下的先驗知識來驅動的。具體來說，給定一個知識圖G和G中的一個實體（頂點）v，它的基礎嵌入h(v)是通過純粹考慮G本身來學習的，它描述了G中的先驗知識，然后根據hv生成一個特定任務下的嵌入z(v)，并對該任務生成一個修正項δv，也就是：

其中，f是一個非線性函數。注意，學習精確的δv和f似乎是不可行的，因為實體v有不同的δv，f函數非常復雜。為了處理這個函數，通過考慮二階信息，我們應用生成模型從h(v)到z(v)。具體地說，對于每個實體v，我們從一個高斯分布N(0,s(v)(2))中采樣出修正變量δv。其中，s(v)由h(v)的相關系數決定。然后，對于每個v1和v2實體對，我們從另外一個高斯分布中采樣z(v1)-z(v2)：

其中，φ表示函數f可訓練的參數。δv的后驗均值是u^(v)，φ^是結果參數。我們應用h(v)+u^(v)作為修正的知識圖譜的嵌入，fφ(h(v)+u^(v))作為修正的特定任務的嵌入。

實驗

5.1 系統評估

在本小節中，我們從存儲、采樣、運算的角度評估AliGraph平臺中底層系統的性能（圖構建和緩存鄰居節點）。所有實驗都在兩個數據集上進行的，如表3所示，Taobao-small和Taobao-large，后者的存儲容量是前者的六倍之大。它們都代表了淘寶電子商務平臺中用戶和物品的子圖。

圖構建

圖構建的性能在圖計算平臺中起著核心作用。AliGraph支持多種來自不同文件系統的各種原始數據，無論是否分區。圖7顯示了在兩個數據集上worker節點構建圖所消耗的時間成本。我們觀察到以下兩個結果：（1）隨著woker節點數量增加，構建圖的時間明顯縮短了；（2）AliGraph可以在幾分鐘內構建大型圖，如：Taobao-large花費5分鐘。這比通常需要幾個小時（比如，PowerGraph）構建圖的大多數技術高效得多。

緩存鄰居的有效性

我們研究了緩存重要頂點的k跳（k-hop）鄰居的效果。在我們的緩存算法中，為了分析Di(k)和Dv(k)，我們為方程1中的Imp(v)設置閾值。在實驗中，我們局部緩存所有頂點的一跳（1-hop）鄰居，并改變控制緩存二跳（2-hop）鄰居的閾值。我們逐漸將閾值從0.05增加到0.45，以測試其敏感性和有效性。

圖8說明了緩存頂點百分比和閾值的情況。當閾值小于0.2時，緩存頂點百分比急劇下降，之后變得相對穩定。這是因為頂點的重要性服從冪率分布，正如我們定理2中證明那樣。為了在緩存成本和收益之前進行良好的權衡，我們根據圖9將閾值設置為0.2，并且只需要緩存大約20%的額外頂點。

我們還比較了基于重要性的緩存策略和另外兩種策略，即隨機策略（緩存隨機選擇一小部分頂點的鄰居）和LRU替換策略。圖9說明了時間成本和緩存頂點百分比的關系。實驗結果表明我們的隨機策略方法節省了大約40%-50%的時間成本，LRU替換策略節省了大約50%-60%的時間成本。這僅僅是因為：（1）隨機選擇的頂點不太可能被訪問；（2）LRU策略由于經常替換緩存頂點而增加了額外的成本。然而，我們基于重要性的緩存頂點更容易被其他頂點訪問。

抽樣的影響

我們測試了采樣優化實現的影響。表4顯示了三種抽樣方法的時間成本，其中批處理大小512、緩存率為20%。我們發現：（1）采樣方法非常有效，完成時間在幾毫秒到不到60毫秒之間；（2）采樣時間隨著圖大小緩慢增長，雖然Taobao-large是Taobao-small的六倍，但是兩個數據集的采樣時間卻相當接近。這些觀察結果驗證了我們的采樣方法的實現是有效且可擴展的。

算子的影響

我們進一步研究了我們在聚合、組合算子上實現的影響。表5顯示了這兩個運算符的時間成本，在我們提出的實現中，時間成本可以加快一個數量級。這是因為我們應用了緩存策略來消除中間嵌入向量的冗余計算，這再次證明了AliGraph平臺的優點。

5.2 算法評估

5.2.1實驗設置

數據集

我們在實驗中使用了兩個數據集，包括一個來自Amazon和Taobao-small的公共數據集。

數據集的統計數據匯總在表6中，他們兩個都是AHG。Amazon公共數據集是從亞馬遜電子產品類別下的產品元數據抽取的。在這個圖中，每個頂點代表一個具有屬性的產品，每個邊連接兩個由同一個用戶共同查看或者共同購買的產品。它有兩個頂點，即user和item，以及user和item之間的四種邊類型，即點擊、添加到preference、添加到購物車和購買行為。

算法

我們實現了所有在本文中提出的算法。為了進行比較，我們還實現了一些不同類別的有代表性的圖嵌入算法，如下所示：

• C1：Homogeneous GE 方法。比較的方法包括：DeepWalk、LINE和Node2Vec。這些方法只能應用于純結構信息的普通圖。

• C2：帶屬性的GE方法。 比較方法包括ANRL，它可以生成嵌入捕獲結構和屬性信息。

• C3：異構（Heterogeneous）的GE方法。比較方法包括Methpath2Vec、PMNE、MVE和MNE。MethPath2Vec只能處理具有多種類型頂點的圖，而其他三種方法只能處理具有多種類型邊的圖。PMNE包括三種不同的方法來擴展Node2Vec方法，分別表示為PMNE-n，PMNE-r和PMNE-c。

• C4：基于GNN的方法。比較方法包括Structural2Vec、GCN、Fast-GCN、AS-GCN、GraphSAGE和HEP。

為了公平起見，所有的算法都通過在我們的系統上應用優化的運算符來實現。如果一個方法不能處理屬性或多個類型的頂點，我們在嵌入過程中會忽略這些信息。我們為具有相同邊類型的每個子圖生成嵌入，并將它們連接在一起作為基于異構的GNN的最終結果。請注意，在我們的檢查中，我們不會比較我們提出的每個GNN算法。因為每個算法設計的側重點不同。我們將詳細介紹每個GNN算法的競爭對手，報告其實驗結果。

指標

我們評估了所提出方法的效率和有效性。該算法的執行時間可以用于簡單地衡量效率。為了測量有效性，我們將算法應用于廣泛采用的鏈接預測任務，在推薦等現實場景中發揮著重要作用。我們隨機抽取一部分數據作為訓練集，其余部分作為測試集。為了測量結果的質量，我們使用了四個常用的指標，即ROC曲線下的面積（ROC-AUC）、PR曲線（PR-AUC）、F1分數和命中召回率（HR Rate）。值得注意的是，每個度量在不同類型的邊之間取平均值。

參數

對于所有的算法，我們設置嵌入向量的維度d為20。

5.2.1 實驗結果

AHEP算法

AHEP算法的目標是快速獲得嵌入結果同時不會犧牲太多的精度。在表7中，我們展示了在Taobao-small數據集上，AHEP算法和其他算法比較的結果。在圖10中，我們說明了不同算法的時間和空間成本。

顯然，我們有以下觀察：（1）在Taobao-small數據集上，HEP和AHEP是唯一兩種能夠在合理的時間和空間限制下產生結果的算法。然而，AHEP比HEP快2-3倍，而且比HEP占用的內存要小的多。（2）在結果質量方面，AHEP的ROC-AUC和F1評分與HEP相當。實驗結果表明，利用最短的時間和空間，AHEP可以產生與HEP相似的結果。

GATNE算法

GATNE的目標是處理具有頂點和邊的異構和屬性信息的圖。我們將GATNE算法以及其競爭對手的比較結果顯示在表8中。

顯然，我們發現GATNE在所有度量指標方面都優于現有的方法。例如，在Taobao-small數據集上，GATNE將ROC-AUC、PR-AUC和F1得分分別提高了4.6%、1.84%和5.08%。這僅僅是因為GATNE同時捕獲頂點和邊的異構信息以及屬性信息。同時，我們發現GATNE的訓練時間與woker節點數呈現線性關系。GATNE模型收斂在不到兩個小時內，在150個節點的分布式環境下。驗證了GATNE方法的高效性和可擴展性。

Mixture GNN

我們比較了Mixture GNN、DAE和β*-VAE方法。將嵌入結果應用于推薦任務的命中率如表9所示。注意，通過應用我們的模型，命中率提高了2%左右。同樣，這種改進也在大型網絡中有重要貢獻。

層次GNN

我們比較了層次GNN和GraphSAGE。結果如表10所示。分數顯著提高7.5%左右。這表明我們的層次GNN可以產生更具前景的嵌入結果。

Evolving GNN

我們比較了在多分類鏈接預測任務中Evolving GNN和其他方法。競爭對手包括具有代表性的DeepWalk、DANE 、DNE 、TNE和GraphSAGE。這些競爭算法無法處理動態圖，因此我們在動態圖的每個快照上運行該算法，并報告所有時間戳的平均性能。Taobao-small數據集的比較結果如表11所示。

我們很容易發現，在所有的度量上，Evolving GNN優于所有其他方法。例如，在劇烈演變情況下，Evolving GNN將微觀（micro）和宏觀(macro)F1得分提高了4.2%和3.6%。這僅僅是因為我們提出的方法能夠更好地捕獲真實網絡的動態變化，從而產生更具前景的結果。

貝葉斯GNN

該模型的目標是將貝葉斯方法和傳統GNN模型相結合。我們使用GraphSAGE作為基準線，并將結果與包含和不包含貝葉斯模型的結果進行比較。表12中給出了推薦結果的命中率。注意，我們同時考慮商品品牌和類別的粒度。顯然，在應用貝葉斯模型時，命中召回率分別增加了1%到3%。請注意，這種改進可以為我們包含900萬個item的網絡帶來顯著的好處。

相關工作

在本節中，我們簡要回顧了GE和GNN方法的最佳性能。根據第1節總結的四個挑戰，我們將現有方法分類如下。

同質性

DeepWalk首先通過隨機游走在圖上生成一個語料庫，然后，在語料庫上訓練一個skip-gram 模型。LINE通過保留一階和二階近鄰來學習節點的表征。NetMF是一個統一的矩陣因式分解框架，用于理論上理解和改進DeepWalk和LINE。Node2Vec增加了兩個參數來控制隨機游走過程，而SDNE則提出了一種structure-preserving的嵌入方法。GCN使用卷積運算合并鄰居的特征表征。GraphSAGE提供一種將結構特征信息與節點特征相結合的歸納方法。

異構性

對于具有多種頂點和（或）邊的圖，PMNE提出了三種方法將復合邊網絡投影到連續向量空間。MVE使用注意力機制將具有多視圖的網絡嵌入到協同后的單個向量表征中。MNE為每個節點使用一個通用嵌入和多個不同邊類型的附加嵌入，這些嵌入由統一的網絡嵌入模型共同學習。Mvn2Vec通過同時保存和協作建模來探索嵌入結果。HNE將內容和拓撲結構共同考慮為統一的向量表征。PTE利用標記信息構建大規模異構文本網絡，并將其嵌入低位空間。Metapath2Vec和HERec將基于元路徑的隨機游走形式化，以構造節點的異構領域，然后利用skip-gram模型進行節點嵌入。

屬性

屬性網絡嵌入的目的是尋找低維向量表征，以 保留拓撲和屬性信息。TADW通過矩陣分解將頂點的文本特征融入到網絡表征學習中。LANE在保留相關性的同時，平穩地將標簽信息整合到屬性網絡潛入中。AANE使聯合學習過程能夠以分布式方式完成，從而加速屬性網絡嵌入。SNE提出了一種通過捕獲結構鄰近度和屬性鄰近度來嵌入社交網絡的通用框架。DANE可以捕獲高的非線性，并在拓撲結構和節點屬性中保留各種近似性。ANRL使用鄰居增強自編碼器對節點屬性信息進行建模，并使用skip-gram模型捕獲網絡結構。

動態的

實際上，一些靜態方法也可以通過基于靜態嵌入更新新的頂點來處理動態網絡。考慮到新的頂點對原始網絡的影響，擴展了skip-gram方法來更新原始頂點的嵌入。“Dynamic network embedding by modeling triadic closure process”重點捕獲學習網絡嵌入的三元結構屬性。考慮網絡結構和節點屬性，“Attributed network embedding for learning in a dynamic
environment”著重于更新streaming網絡的特征向量和特征值。

結論

我們從目前實際的圖數據問題中總結出了四個挑戰，即大規模、異構、屬性和動態。基于這些挑戰，我們設計并實現了AliGraph平臺，它為解決更多實際問題提供了系統和算法。今后，我們重點關注但不限于以下幾個方面：

邊級別和子圖級別嵌入的GNN；

更多的執行優化，例如，將計算變量與圖數據在GNN中共同定位以減少跨網絡流量，引入新的梯度優化方法，利用GNN的特點加速分布式訓練，而不造成精度損失，在多GPU架構中更好地分配work節點；

Early-stop機制，有助于在沒有預期結果的情況下，提前終止訓練任務；

Auto-ML，有助于從各種GNN中選擇最佳方法。

論文原文鏈接：https://arxiv.org/pdf/1902.08730.pdf

公開數據集平臺：https://tianchi.aliyun.com/dataset/dataDetail?dataId=9716

更多內容，請關注AI前線

總結

以上是生活随笔為你收集整理的阿里重磅发布大规模图神经网络平台AliGraph，架构算法解读的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。