引言
圖資料廣泛存在于我們生活中，社交網絡、網際網路、交通網等等都是天然的圖資料。在阿裡内部場景，使用者物品的互動資料，安全風控領域的使用者、評論、交易等都構成圖，圖可以說是資料最為廣泛的存在形式。
深度學習在文本，語音，圖像等資料上取得了很大成功，GNNs(圖神經網絡)是深度學習在圖結構資料上的應用。對于圖這一非歐空間的資料，如何将它和深度學習結合起來是GNNs首先要解決的問題。GNNs早期的研究主要集中在Spectral-based 方法上，這種方法理論比較充分，但是難以用于大規模場景。近些年以GraphSage[1]為代表的Spatial-based方法在性能，泛化性，靈活性等方面均展現出了優勢。GraphSage通過采樣子圖進行按批次訓練的方式在Pinterest推薦場景進行了實際應用，并取得了很好的效果[2]。此外，像DeepWalk等Graph embedding算法和TransE等知識圖譜模型的訓練都是基于采樣的方法進行設計和訓練。
阿裡很多場景的資料都是十億級别節點，百億邊的規模，針對阿裡衆多場景的實際需求和特點，我們設計開發了一個簡潔易用，高性能的工業級大規模圖學習系統graph-learn（
https://github.com/alibaba/graph-learn）。Graph-learn主要面向spatial-based的GNNs算法，同時支援graph embedding, 知識圖譜等常見圖學習算法。我們将GNNs算法抽象為一個統一的算法架構。包括采樣，聚合，組合，如Algorithm 1所示[3]。
采樣一方面解決了大規模訓練的問題，另一方面是進行深度學習批次訓練的必要前提。采樣向下對接圖存儲系統，向上對接算法模型，是以是整個graph-learn中的基礎功能。
大規模采樣的實作
采樣和查詢是graph-learn圖引擎部分對外提供服務的基本接口，采樣和查詢建構于分布式圖存儲之上，以Python API的形式對外提供，如圖1所示。查詢包括圖的節點和邊的周遊，節點和邊的屬性、權重、标簽等查詢。采樣分為鄰居采樣和負采樣，鄰居采樣提供采樣子圖的功能，負采樣主要面向非監督學習場景，系統直接提供采樣負樣本的功能，不需要使用者額外産生負樣本。
基于阿裡内部大量業務場景的需求總結和實際應用，系統內建了若幹種常用的采樣和負采樣方法(Built-in Samplers)。雖然這些采樣方法基本覆寫了大部分需求，但是因為采樣方法和算法效果關系密切，甚至直接關系到模型的成敗，是以，開放采樣程式設計接口，友善使用者進行其他自定義采樣方法(Custom Sampler)的探索是我們系統的一個重要功能以及GNN創新的一大方向。
圖 1. graph-learn圖引擎部分示意圖
Graph-learn的圖引擎是CS架構，具體的采樣實作流程如圖2所示：給定一批需要采樣的源節點，首先通過Partitioner去查詢包含這些源節點的子圖在哪個server上，圖中src id為1，3的被partition到了server 1上，2，4被partition到了server 2上。然後，将這些src ids發送到對應的server上，查詢子圖，并調用本地采樣方法去執行采樣操作。目前系統內建了若幹種常見的采樣算子，也可以支援使用者自定義自己的采樣算子。本地采樣結束後，需要将采樣後的結果按照原始src ids的順序進行拼接傳回。Partition目前使用系統内置的hash劃分方法，将來我們會支援不同的Partition政策來進行更加高效的圖劃分，提高采樣和計算性能。
圖 2. graph-learn采樣流程示意圖
對于負采樣來說，沒有partition和stitch過程，一個batch的輸入資料，會随機或者按照分布選擇一個server，然後在這個標明server上進行負采樣，這樣可以做到全局負采樣的效果[5]。
我們底層的資料結構使用Tensor的形式實作，支援常見數值類型和string類型的Tensor。基于Tensor這種規整的格式，系統可以将采樣的Partition，Stitch和分布式執行過程自動化，是以，新增一個采樣算子時隻需要寫具體的本地采樣邏輯即可。
Graph-learn采用了分布式圖存儲和采樣，使得規模可以輕松擴充到上百台機器，支撐起十億節點，百億邊的日常任務。此外，針對不同的采樣政策，我們采用了熱點緩存，慢機遷移等衆多優化，使得在規模提升的同時，能夠保持高性能地采樣。
采樣算法介紹
鄰居采樣
Graph-learn支援異構圖，同構圖是異構圖的一種特例，是以圖采樣需要指定meta path，系統按照指定的meta path采樣得到多跳鄰居，不同的采樣算子按照不同算法來傳回鄰居。目前built-in的采樣算子包括以下幾種：
• random：随機采樣鄰居，每次在給定節點的所有鄰居裡随機選擇一個鄰居。
• edge_weight：按照邊的權重為機率分布進行采樣。
• topk：以edge_weight為大小對鄰居進行排序，并傳回topk個。鄰居數不足要求個數會循環填充。
• in_degree：按照鄰居的入度大小為機率分布進行采樣。
• full neighbor: 傳回給定點的所有鄰居。
圖3. （a)原始圖；（b)目的節點的id對應的edge weight和in-degree統計表。
前四種采樣都需要指定meta path，并且需要指定需要采的鄰居個數，采樣結果以dense的形式傳回，這是由于采樣後按batch訓練的時候需要樣本對齊。當然對于原始GCN[4]等需要擷取源節點的所有鄰居的算法，我們支援采樣傳回節點的所有鄰居，而不做上采樣/下采樣，我們稱這種采樣為full neighbor采樣，采樣後的結果會以sparse的形式傳回。
以圖3為例，假設需要采樣src id為1的節點的鄰居，指定的鄰居個數是2。那麼random會從[2, 3, 4, 5]裡随機采樣兩個；edge_weight以邊權重為機率分布傳回兩個；in_degree采樣以入度為機率分布傳回兩個；topk會傳回邊權重最大的兩個，即[5, 4]。如果指定采樣個數為6，則topk會做循環填充，傳回結果為[5, 4, 3, 2, 5, 4]；full neighbor采樣的話則會傳回實際個數的全部鄰居[2, 3, 4, 5]。
以上采樣算法裡按機率分布的采樣均采用了AliasMethod[5]實作，是以複雜度都是常數時間。單機在512 batch size、采樣10個1hop、15個2hop鄰居id的情況下，耗時在毫秒級别。此外針對不同的政策系統有不同的優化，比如對于topk，我們在構圖時就會預先按照edge weight為大小對底層存儲表進行排序。
上面介紹的算法以node-wise(layer sampling)采樣為主，node-wise采樣随着采樣的跳數增加，鄰居數目會急劇上升，在多跳(>2)情況下尤其明顯，是以近年來layer-wise的采樣也被應用于不同GNN算法，如上圖GCN算法所示[6]，我們也正在探索開發layer-wise(graph sampling)的采樣，希望在多跳場景下帶來進一步的性能優化和記憶體節省。
負采樣
負采樣就是給定源節點，傳回和它不相連的目标節點。負采樣同時支援本地和全局負采樣，對于一個batch的樣本要采樣其負樣本時，可以按照一定的機率分布選擇一個server，然後在該server上采樣。如果選擇本地負采樣，則隻在本機進行負采樣。目前built-in的負采樣算子包括以下幾種：
• random：随機采樣和給定源節點不相連的目的節點。
• in_degree：按照目的節點的入度分布，傳回與源節點不相連的目的節點。
按照入度分布的in_degree負采樣實作上采用AliasMethod[5]，會在首次采樣前提前建構好Alias Table，是以采樣是常數時間複雜度。此外負采樣我們預設是嚴格負采樣，但是出于性能和極端情形的考慮，我們支援使用者端設定一個門檻值來控制嚴格程度。負采樣可能對算法效果也會産生很大影響，是以負采樣算子如何和圖劃分結合，如何高效負采樣，以及按何種分布負采樣都是值得探索和研究的地方。
自定義采樣
上面介紹了graph-learn開發過程中，結合實際業務場景需求系統已經內建的鄰居采樣和負采樣算子。雖然這些built-in的采樣算子滿足了大部分GNNs和其他圖學習算法的需求，但是，考慮到每個具體業務場景的采樣、負采樣需求不同，而且采樣、負采樣政策對算法的建構和效果有着重要影響，是以我們也允許使用者自定義采樣算子。自定義采樣算子主要流程包括：
a）在C++檔案中注冊并實作新Sampler
class MySampler : public Operator {
public:
Status Process(const OpRequest* req, OpResponse* res) override {
//TODO
}
};
REGISTER_OPERATOR("my_sampler", MySampler); b）在Python端調用已注冊的算子
g.sample(count).by("my_sampler")... 應用場景
采樣作為graph-learn的核心功能，在所有使用graph-learn的作業中都起着非常重要的作用。常見的用法是周遊圖的點或者邊産生正樣本，然後采樣給定節點的n-hop鄰居對節點進行編碼，對于非監督學習場景使用負采樣來得到負樣本并對負樣本做類似的鄰居編碼。最後對采樣後的結果進行特征的組合和reshape等處理成batch的資料，接入頂層算法模型。基于這一流程graph-learn目前支援GCN(包括采樣版實作), GAT(包括采樣版實作), GraphSage, 二部圖GraphSage, DeepWalk, LINE, TransE等算法，并且可以友善擴充實作其他的圖學習模型。
在阿裡内部，graph-learn支撐了推薦，安全風控等衆多業務場景，不同場景下有個位到十位數百分點的提升。此外，由于樣本生産組裝過程和訓練同時進行，相比之前的離線處理完樣本後再訓練的流程，存儲和訓練時間也得到了很大節省。
總結和展望
本文對graph-learn的采樣實作和各個采樣算子做了簡單介紹，采樣在GNNs中起着重要作用，并已經在很多場景得到了實際應用。采樣和算法效果以及模型設計息息相關，是GNNs探索創新的一個重要方向，目前的采樣算子都是基于統計靜态特征，後面我們會在采樣和訓練結合方面做一些探索。此外，将Graph Partitioning和采樣，負采樣一起考慮和優化也是系統發展的一個重要方向。
參考文獻
[1] Inductive Representation Learning on Large Graphs. NIPS, 2017.
[2] Graph Convolutional Neural Networks for Web-Scale Recommender Systems. KDD, 2018.
[3] AliGraph: A Comprehensive Graph Neural Network Platform. VLDB, 2019.
[4] Semi-Supervised Classification with Graph Convolutional Networks. ICLR, 2017.
[5] Distributed negative sampling for word embeddings. AAAI, 2017.
[6] Accurate, Efficient and Scalable Graph Embedding. IPDPS，2019.
開源項目位址：
歡迎對圖學習算法和系統感興趣的同學加入我們 [email protected]
本文作者：艾寶樂