「大規模圖神經網路系統」2022最新綜述:從演算法到系統

語言: CN / TW / HK

↑ 點選 藍字  關注極市平臺

來源丨專知

編輯丨極市平臺

極市導讀

本文首先分析圖神經網路演算法的計算模式,提出大規模圖神經系統訓練存在的挑戰,並對現有系統進行介紹。  然後從系統架構、通訊優化等多個維度對這些系統進行詳細的分析和對比,對圖神經網路系統的不同優化技術進行總結和分析,並對目前已經開源的圖神經網路系統設計實驗,從多個方面測評系統的效能,驗證系統有效性。   >> 加入極市CV技術交流群,走在計算機視覺的最前沿

來自東北大學最新《大規模圖神經網路系統》綜述論文

圖神經網路(GNN)是一類基於深度學習的處理圖域資訊的方法,它通過將圖廣播操作和深度學習演算法結合,可以讓圖的結構資訊和頂點屬性資訊都參與到學習中,在頂點分類、圖分類、連結預測等應用中表現出良好的效果和可解釋性,已成為一種廣泛應用的圖分析方法。然而現有主流的深度學習框架(如TensorFlow、PyTorch等)沒有為圖神經網路計算提供高效的儲存支援和圖上的訊息傳遞支援,這限制了圖神經網路演算法在大規模圖資料上的應用。

目前已有諸多工作針對圖結構的資料特點和圖神經網路的計算特點,探索了大規模圖神經網路系統的設計和實現方案。 首先對圖神經網路的發展進行簡要概述,總結了設計圖神經網路系統需要面對的挑戰;隨後對目前圖神經網路系統的工作進行介紹,從系統架構、程式設計模型、訊息傳遞優化、圖分割槽策略、通訊優化等多個方面對系統進行分析; 最後使用部分已開源的圖神經網路系統進行實驗評估,從精確度、效能、擴充套件性等多個方面驗證這些系統的有效性。

http://www.jos.org.cn/html/2022/1/6311.html

圖神經網路概述

深度學習在物件檢測[1,2]、機器翻譯[3,4]、語音識別[5]、物理系統[6,7]等領域取得了革命性的成功,推動了對模 式識別和資料探勘的研究。現有的深度學習方法能夠處理歐式空間表示下的規則資料,例如影象資料可以表示為 歐幾里得空間中的規則網路,而現實中的很多應用的資料以圖的形式來表示。比如在社交網路[8]中,可以通過圖來 表示物件之間的關聯關係,從而能夠進行社群發現、聚類[9]等演算法。在生物領域[10] ,可以通過圖來表示蛋白質分子 之間的關係,從而能夠對蛋白質進行分類。在引文網路[11]領域,可以用圖來表示論文之間的引用關係,從而能夠對論文按領域進行分組。在電子商務領域,可以用圖來表示使用者和商品之間的互動關係,從而能夠對使用者進行商品的 推薦。由於圖資料的不規則性和稀疏性,每個頂點可能具有不同數量的鄰居,並且圖資料之間具有依賴性,圖中每個頂點的計算依賴於其他的頂點,所以導致很多深度學習方法無法直接應用在圖資料中。例如,卷積只能對影象或文字這樣的歐幾里德資料進行操作,無法直接應用於圖資料,限制了深度學習方法在圖領域的發展。

隨著圖領域深度學習方法逐漸受到廣泛關注,近些年出現了很多圖神經網路演算法,這些方法通過在傳統深度 學習模型中新增圖操作,應用圖的結構資訊和屬性資訊,來處理圖資料的複雜性,成為解決圖學習問題的有效方 法。比較典型的工作有 Structure2Vec[12]、GCN[13]、FastGCN[14]、AS-GCN[15]、GraphSAGE[16]等。

圖神經網路演算法將傳統深度學習的方法,如卷積,擴充套件到了圖資料領域,並結合資料傳播的思想形成了在圖上的深度學習演算法,其 在社交網路、推薦系統[17]、知識圖譜[18]、連結預測[19]等領域都取得了良好的效果。圖神經網路受到廣泛關注的原因如下:首先,現有標準神經網路無法正確處理圖資料的輸入,因為其按照特定 順序處理節點特徵,而圖中的頂點沒有自然順序。圖神經網路演算法採用在頂點上傳播資訊的計算方式,忽略頂點的 輸入順序解決了這個問題。第二,在標準神經網路中,圖中頂點的依賴關係僅能作為頂點特徵輸入,而圖神經網路 演算法根據圖中頂點的依賴關係進行資訊傳播,保留了圖結構的資訊,為下游深度學習任務提供了更加完整的資訊。第三,推理是高階人工智慧的一個重要研究課題,圖神經網路強大的表示能力,為進一步生成強大的神經模型提供了基礎。

現有的深度學習框架如 TensorFlow[20]、PyTorch[21]、MXNet[22]以及 CNTK[23] ,和圖處理框架 PowerLyra[24]、 PowerGraph[25]、Garaph[26]、Pregel[27]、TuX2[28]都不能很好地支援圖神經網路的計算,這阻礙了圖神經網路的進一 步發展,也限制了圖神經網路在大規模資料中的應用。因此突破現有框架限制,開發專用於圖神經網路訓練的系統,對於充分發揮圖神經網路的潛力十分重要。

**本文首先分析圖神經網路演算法的計算模式,提出大規模圖神經系統訓練存在的挑戰,並對現有系統進行介紹。然後從系統架構、通訊優化等多個維度對這些系統進行詳細的分析和對比,對圖神經網路系統的不同優化技術進 行總結和分析,並對目前已經開源的圖神經網路系統設計實驗,從多個方面測評系統的效能,驗證系統有效性。

大規模圖神經網路訓練的挑戰

隨著圖神經網路在不同領域的應用越來越廣,對訓練圖神經網路系統的效能要求也越來越高。結合對圖嵌入[42-44]以及圖神經網路[45,46]的分析,本文對設計開發神經網路訓練系統存在的挑戰進行如下總結。

(1) 現有深度學習系統不能很好地抽象圖傳播過程。現有的深度學習系統處理的是規則資料,規則資料中每個樣本的計算圖是獨立的,與其他樣本無關,而圖神經網路是將深度神經網路和迭代圖傳播結合起來進行計算的,圖資料的每個樣本(即圖頂點)之間具有依賴性,所以現有系統不能自然地表達和有效地支援圖傳播模型。如何突破現有框架的侷限,設計一種適用於圖神經網路的系統架構是發展圖神經網路的重要問題;

(2) 訓練大規模圖神經網路的計算、儲存複雜度高。真實世界中的尺寸都非常大,而且由於頂點之間具有複雜的依賴性,隨著圖神經網路層數的增加,計算成本和記憶體空間需求呈指數級增長。例如Facebook的社交網路圖包含超過20億個頂點和1萬億條邊,這種規模的圖在訓練時可能會產生100 TB的資料。所以針對大圖的訓練,如何設計計算和儲存策略以利用有限的資源來使系統達到理想的效能也是發展圖神經網路系統的一大挑戰;

(3) 圖計算區域性性差導致系統開銷問題。真實世界圖的稀疏性會導致非常差的空間區域性性,在單機系統中這會導致Cache命中率降低。而在分散式系統中,這會導致頻繁的跨節點訪問,進而產生大量的訊息傳遞開銷。所以如何針對圖的特殊性質減少系統開銷是提高系統性能的一大挑戰;

(4) 圖的冪律分佈導致分散式計算負載均衡問題。對於具有數億個頂點的大型圖,通常需要對圖進行分散式處理,圖神經網路演算法不同於傳統的圖演算法,平衡的圖分割槽不僅依賴於分割槽內的頂點數量,還依賴於分割槽內頂點鄰居的數量,多層圖神經網路模型中不同頂點多階鄰居的數量可能相差極大,並且這些分割槽之間需要頻繁的資料交換,如何對圖資料進行合理的分割槽來保證分散式訓練的效能是對於分散式系統的重大挑戰;

(5) 異構計算架構中的任務劃分和負載排程的合理性問題。GPU的廣泛應用為訓練深度學習模型帶來了很多機會和挑戰。在利用GPU加速神經網路的訓練時,通常將資料儲存在主機記憶體中,在計算時需要將資料傳輸到GPU,由於圖神經網路演算法在反向傳播階段的複雜性,需要頻繁的在主機和GPU之間進行資料傳輸,如何設計合理的排程方案來最大程度地減少資料傳輸成本也是提高系統性能的一大挑戰。

為了應對這些挑戰,出現了很多針對圖神經網路的訓練框架,其中單機系統如PyTorch Geomertic、DGL、NeuGraph。圖神經網路通常處理非常大且不規則的圖,這些大圖無法儲存在單個裝置中,因此必須以分散式方式進行分割槽和處理,其中分散式圖神經網路框架如Euler、AliGraph、Roc、AGL。接下來本文將介紹若干典型的單機圖神經網路系統以及分散式圖神經網路系統。

圖神經網路系統介紹

圖神經網路演算法將深度神經網路的運算(如卷積、梯度計算)與迭代圖傳播結合在一起:每個頂點的特徵都是由其鄰居頂點的特徵結合一組深度神經網路來計算。但是,現有的深度學習框架不能擴充套件和執行圖傳播模型,因此缺乏高效訓練圖神經網路的能力,並且現有框架一般採用資料/模型並行來分散式訓練深度神經網路,這種平行計算方法難以直接應用於圖神經網路,因此限制了訓練大規模圖神經網路的能力。而現有的圖處理系統雖然能夠表示迭代圖傳播模型,並能有效支援大規模圖的迭代計算,但是缺乏支援神經網路計算的關鍵能力,如張量抽象、自動微分等。因此,為了支援圖神經網路在大規模圖上的應用,以及對更復雜圖神經網路結構的探索,開發針對圖神經網路的訓練系統是十分有必要的。

目前具有代表性的圖神經網路框架:DGL[47]、PyTorch Geometric[48]、NeuGraph[49]、EnGN[50]、Euler[51]、PSGraph[52]、AliGraph[53]、Roc[54]、AGL[55]、PGL[56]。DGL[47]是易於使用,高效能且可擴充套件的Python庫,用於圖結構的深度學習,能夠與主流的深度學習框架整合,例如Tensorflow[20]、PyTorch[21]、MXNet[22]。PyTorch Geometric[48]是基於PyTorch構建的深度學習庫,用於處理非結構化資料的深度學習。NeuGraph[49]是一種將資料流系統和圖處理系統結合起來訓練圖神經網路的框架,它構建在現有的資料流引擎之上,使用Python和C++作為開發語言。EnGN[50]是一種以邊為中心,專門用於大規模圖神經網路訓練的加速器。Euler[51]與PSGraph[52]是一個與深度學習工具整合的大規模分散式圖學習框架,支援使用者在數十億點數百億邊的圖上進行模型訓練。AliGraph[53]是由阿里巴巴團隊開發的取樣建模訓練一體化的圖神經網路平臺。Roc[54]是一種用於快速圖神經網路訓練的分散式多GPU框架。AGL[55]是用於工業用途圖學習的整合系統,利用傳統基礎架構(MapReduce、引數伺服器[57])實現了容錯性和一致性。PGL (paddle graph learning)[56]是由百度開發的基於PaddlePaddle的高效靈活的圖學習框架。

圖神經網路系統總結和分析

本節從系統架構、處理模型、圖分割槽策略、通訊優化策略、以及社群活躍度與系統易用性方面,對現有圖神經網路系統進行分析和對比,並從多個維度對系統的特點進行總結,以表格的形式清晰的展示系統的共性與不同,來為研究人員提供有效參考。

(1) 系統架構。DGL和PyTorch Geometric都是結合現有的深度學習框架來實現的,並且針對圖神經網路的特點做了多種優化,達到了很好的效能。結合現有深度學習框架來實現的系統,更加方便使用者使用,能夠幫助其更快地實現圖神經網路模型。但結合現有深度學習框架來實現的系統,在針對圖操作的優化上有很多侷限性。NeuGraph採用了一種新的架構,將圖模型和資料流模型結合起來,以支援高效的圖神經網路訓練,這種架構既彌補了現有資料流引擎不能有效地支援圖計算的缺點,又彌補了圖引擎不能支援資料流程式設計模型的缺點。EnGN在統一的處理模型基礎上,開發了一個定製的EnGN加速器,它集成了一個神經圖處理單元(NGPU),可以在統一的體系結構中執行特徵提取,聚合和更新操作。EnGN的專用加速器突破了硬體結構的限制,相比於其他系統配備的多個CPU或GPU,大大降低了成本和能源開銷。AliGraph、Euler和PGL的架構類似,都採用分層架構,構建於現有資料流框架之上,並且都構建在CPU平臺上。Roc將圖神經網路的計算分佈在多個計算節點上,每個計算節點可以包含多個GPU,每個計算節點在子圖上執行圖神經網路的訓練,並與CPU通訊來獲得輸入張量並儲存中間結果。Roc採用分散式多GPU的架構不僅解決了單節點系統對於大規模圖的限制,並且比基於CPU的系統更高效。AGL、PSGraph都是利用現有大資料處理系統和引數伺服器的並行體系結構來組建的基於CPU的分散式圖神經網路訓練框架,這些系統具有良好的容錯性和可伸縮性。

(2) 處理模型。DGL和PyTorch Geometric通過使用面向圖的訊息傳遞介面包裝深度學習系統,來支援針對圖神經網路的程式設計。這種訊息傳遞模型很好地表示了圖上的資料流動,整個模型分為兩步。第1步:“訊息”生成操作,這個操作定義在每個邊上,通過將邊的特徵與兩端頂點特徵組合為每一條邊生成一條“訊息”。第2步:更新操作,定義在每個頂點上,通過彙總頂點入邊傳入的訊息來更新頂點特徵。通過系統提供的訊息傳遞介面,使用者可以快速實現圖神經網路的原型製作。PGL也採用訊息傳遞正規化構建圖神經網路的介面,並提供多種聚合方法,提高了並行處理效率。NeuGraph提出了一種新的處理模型SAGA-NN,提高了在頂點和邊上執行批量操作的靈活性,提供了在圖計算和資料流排程中實現優化的機會,提高了系統性能。EnGN提供一種以邊為中心的處理模型,將圖神經網路的計算抽象為特徵提取,聚合和更新3個階段。EnGN與其他3個系統不同,在處理模型基礎上定製了針對圖神經網路的加速器,不依賴於現有的深度學習系統,並擁有獨特的資料流處理方法。EnGN優化了頂點資料和邊資料移動的記憶體訪問模式。對於大圖中的源頂點資料訪問,採用圖切片技術,並確保對源節點的訪問僅引起對連續記憶體地址的訪問。對於聚合和更新階段中的隨機目標頂點訪問,EnGN利用雜湊邊資料佈局和多級快取方法來避免寫衝突並提高片上緩衝器中的資料命中率。

(3) 圖分割槽策略。平衡的圖分割槽是實現分散式圖神經網路系統的關鍵之一。Euler採用簡單的雜湊方法將圖的頂點進行分片,這種分片方式使各個節點擁有目標頂點的數量基本一致,但是在每個頂點的子圖中擁有的鄰居數量是不同的,所以每個節點的計算負載並不均衡。AliGraph則提供了多種內建的圖分割槽演算法供使用者選擇,比如適合處理稀疏圖的METIS方法,適合稠密圖的點割和邊割方法,這種方法雖然為使用者提供了多種選擇,但需要使用者自己去判斷使用哪種分割槽方式,給使用者造成很大不便。Roc採用一種線上線性迴歸模型來優化圖分割槽。這種基於線性迴歸的圖分割槽方法在圖神經網路系統中能夠達到比傳統分割槽更好的效能。

(4) 通訊優化策略。針對通訊開銷影響分散式系統性能的問題,Euler採用的是快取對應頂點k階內的鄰居頂點資訊,這種方式雖然直接避免了計算節點之間的通訊,但是造成了很嚴重的記憶體浪費,並且在冪律分佈的圖中還會使各個計算節點之間負載不均衡。AGL採用的策略和Euler相同,但是AGL提出了重新索引的策略來均衡負載。AliGraph提出了一種快取重要頂點的鄰居的方法來降低通訊開銷,同時提出了一種對頂點重要性的度量標準,既能有效減低通訊開銷,又防止產生巨大的儲存成本,避免資源浪費。ROC引入了代價模型,可以最大程度地減少CPU和GPU之間的資料傳輸。這種動態的方法突破了手動優化的侷限,將影響通訊的多種因素綜合考慮,從而更好的降低通訊成本,提高系統性能。PGL的分散式引數伺服器提供了一種高效的引數更新策略:GeoSSD,在全非同步的條件下進行引數更新,並重疊模型訓練與節點通訊,在保證模型效果的前提下提升了訓練效率。

(5)社群活躍度與系統易用性。PyTorch Geometric、DGL、AliGraph、Euler、PSGraph、PGL為開源系統,這裡的社群活躍度以GitHub上討論區的數量為標準,這其中最活躍的社群為PyTorch Geometric。在系統易用性方面,從配置檔案的完整度、對其他系統的依賴度、使用者使用的方便度多個角度綜合考量,這其中DGL和PyTorch Geometric的易用性排在前列,而Euler與PSGraph雖然給出了配置檔案,但在配置系統時,需要配置其他多個依賴包,並且資料處理過程繁瑣,不易使用者使用。本文為系統的社群活躍度和易用性給出星級評價,星級越高,系統在這兩方面表現越好,其中空白符號表示系統未開源。

本文對目前的圖神經網路系統從多個維度進行了綜合分析,對這些系統的共同特性進行提取,並總結歸納,見表1。

總結

本文首先簡要介紹了圖神經網路的發展,並對典型的圖神經網路演算法的計算模式進行了介紹,並簡要分析了圖神經網路訓練的難點。然後本文對現有圖神經網路系統做了詳細描述,並對這些系統從系統架構、處理模型以及優化策略和系統易用性等多個角度進行分析和總結,總結了針對圖神經網路系統的多種優化技術,最後使用目前可用的開源系統驗證了現有分散式圖神經網路系統的有效性。經過論文分析與總結,發現現有圖神經網路系統仍存在以下問題,同時也是未來的研究方向:首先,目前系統所採用的架構仍依賴於現有資料流框架,現有資料流框架針對深度神經網路的運算做了一系列優化,但缺少針對圖操作的優化尤其是高效分散式圖操作,與這些框架結合起來搭建系統,制約了分散式圖神經網路系統的進一步發展。第二,目前系統所採用的小批量平行計算方式,並不適用於基於譜方法的圖卷積網路,本文通過實驗發現,採用這種平行計算方式會對基於譜方法圖卷積網路的訓練精度產生影響。第三,圖的分割槽操作和通訊管理是影響系統性能的關鍵因素,儘管目前的系統已經在這兩方面提出多種優化,減少了記憶體消耗和通訊開銷,但這兩者仍存在非常大的優化空間。

參考文獻

[1] Redmon J,Divvala S, Girshick R, Farhadi A. You only look once: Unified, real-time object detection. In: Proc. of the 2016 IEEE Conf. on Computer Vision and Pattern Recognition. Las Vegas: IEEE, 2016. 779–788. [doi: 10.1109/CVPR.2016.91]

[2] Ren SQ, He KM, Girshick R, Sun J. Faster R-CNN: Towards real-time object detection with region proposal networks. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2017, 39(6): 1137-1149. [doi:10.1109/TPAMI.2016.2577031]

[3] Luong MT, Pham H, Manning CD. Effective approaches to attention-based neural machine translation. In: Proc. of the 2015 Conf. on Empirical Methods in Natural Language Processing. Lisbon: Association for Computational Linguistics, 2015. 1412–1421. [doi: 10.18653/v1/D15-1166]

[4] Wu YH, Schuster M, Chen ZF, et al. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv: 1609.08144, 2016.

[5] Hinton G, Deng L, Yu D, Dahl GE, Mohamed AR, Jaitly N, Senior A, Vanhoucke V, Nguyen P, Sainath TN, Kingsbury B. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine, 2012, 29(6): 82-97. [doi:10.1109/MSP.2012.2205597]

[6] Sanchez-Gonzalez A, Heess N, Springenberg JT, Merel J, Riedmiller M, Hadsell R, Battaglia P. Graph networks as learnable physics engines for inference and control. In: Proc. of the 35th Int’l Conf. on Machine Learning. Stockholm: PMLR, 2018. 4470–4479.

[7] Battaglia PW, Pascanu R, Lai M, Rezende DJ, Kavukcuoglu K. Interaction networks for learning about objects, relations and physics. In: Proc. of the 30th Int’l Conf. on Neural Information Processing Systems. Barcelona: NIPS, 2016. 4509–4517. [doi: 10.5555/3157382.3157601]

[8] Hamilton WL, Ying R, Leskovec J. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 2017, 40(1): 52-74. http://arxiv.org/pdf/1709.05584

如果覺得有用,就請分享到朋 友圈吧!

△點選卡片關注極市平臺,獲取 最新CV乾貨

公眾號後臺回覆“ transformer ”獲取最新Transformer綜述論文下載~

極市乾貨

課程/比賽: 珠港澳人工智慧演算法大賽 保姆級零基礎人工智慧教程

演算法trick 目標檢測比賽中的tricks集錦 從39個kaggle競賽中總結出來的影象分割的Tips和Tricks

技術綜述: 一文弄懂各種loss function 工業影象異常檢測最新研究總結(2019-2020)

# CV技術社群邀請函  #

△長按新增極市小助手

新增極市小助手微信 (ID : cvmart4)

備註: 姓名-學校/公司-研究方向-城市(如:小極-北大-目標檢測-深圳)

即可申請加入極市 目標檢測/影象分割/工業檢測/人臉/醫學影像/3D/SLAM/自動駕駛/超解析度/姿態估計/ReID/GAN/影象增強/OCR/影片理解 等技術交流群

每月大咖直播分享、真實專案需求對接、求職內推、演算法競賽、乾貨資訊彙總、與  10000+ 來自港科大、北大、清華、中科院、CMU、騰訊、百度等名校名企視覺開發者互動交流~

覺得有用麻煩給個在看啦~   

「其他文章」