圖計算的學習與思考

好的軟體不是靠程式分析、查錯查出來的，而是由正確的人建構出來的。

圖成為日益重要的運算對象，圖結構是對群體關係的一種抽象，可以描述豐富的對象和關係。圖計算的核心是如何將資料建模為圖結構以及如何將問題的解法轉換為圖結構上的計算問題，當問題涉及關聯分析時，圖計算往往能夠使得問題的解法自然地表示為一系列對圖結構操作和計算的過程。例如，使用基於網頁連結的圖結構的PageRank演算法得到網頁權重，作為搜尋引擎排序的參考，利用圖結構的使用者行為資料來得到精確的群體偏好分析和個人化產品推薦結果。

1.什麼是圖計算？

圖計算是研究人類世界的事物和事物之間的關係，對其進行描述、刻畫、分析和計算的技術。這裡的圖是“graph”，而不是圖“image”，源自於數學中的圖論（graph theory）。

圖是一種最靈活的連結方式，讓實體之間可以不受限制地連結。圖計算不僅只是一個技術，更是一種理解世界的方式。圖數據可以很好地描述事物之間的聯繫，包括描述聯繫的方向和屬性。從資料結構來看，圖是對事物之間關係的一種原生表達。在某種程度上，關係資料庫應該叫表資料庫，而圖資料庫反而應該叫關係資料庫。廣義的圖計算是指基於圖資料來做各種各樣的處理，包括了圖資料庫。

圖表計算技術解決了傳統的計算模式下關聯查詢的效率低、成本高的問題，在問題域中對關係進行了完整的刻畫，並且具有豐富、高效和敏捷的數據分析能力，其特徵有如下：

• 基於圖抽象的資料模型
• 圖資料模型並行抽象
• 圖模型系統最佳化

對於圖計算而言，效能成本、容錯機制以及可拓展性都是非常重要的。

2. 從歷史發展看圖計算

圖計算最早可追溯到20 世紀60 年代面向樹狀結構的資料庫，70-80 年代出現面向屬性圖的模型和技術，如LDM（邏輯資料模型）等。直到2007 年，第一款商用圖資料庫 Neo4j 公司成立，標誌著圖計算進入了發展的階段。

圖表計算研究真正開始的標誌是 2004 年 Google 開發出面向大數據並行處理的計算模型MapReduce，這一模型的推出給大數據並行處理帶來了巨大的革命性影響。隨後，2006 年Apache Hadoop 團隊引進了 Hadoop 分散式檔案系統（HDFS）以及新的 Hadoop MapReduce框架。 2009 年，加州大學柏克萊分校 AMP Lab 開發 Spark 系統。

從2010年開始，大規模分散式架構、多模態支援、圖查詢語言設計等圖計算研究方向逐漸受到關注。 Google 提出了 Pregel，一個針對圖演算法特徵設計的分散式圖計算系統，遵循 BSP 運算模型；之後 CMU Select 實驗室 GraphLab 專案組提出了GAS 運算模型。 。雖然pregel 和GraphLab 都是對於複雜機器學習計算的處理框架，用於迭代型（iteration）計算，但是二者的實現方法卻採取了不同的路徑：Pregel 是基於大塊的消息傳遞機制，GraphLab 是基於記憶體共享機制，對後續其他圖計算系統的設計都產生了深遠的影響。

Google在2012年5月提出了知識圖譜的概念，這是一種資訊間全新的連結方式，其基本組成單位是「實體—關係—實體」三元組，實體之間通過關係相互聯結，構成網狀的知識結構。知識圖譜能夠成立的核心是電腦的知識推理機制，圖計算為其提供了重要的底層技術支援。

2015年隨著資料量級迅速成長，應用市場逐漸打開，對圖運算系統擴展性和效率需求不斷提高。中國圖計算領域學術界和產業界研究開始逐漸發力，發布了自己的圖計算系統和平台 ，例如清華大學的Gemini等等。

近年來，隨著人工智慧技術的發展， 圖神經網路也已經在業界展現身手了。

3.從框架模型看圖運算

圖運算的架構基本上都遵循BSP(Bulk Synchronous Parallell)的運算模式。 BSP模式批量同步(bulk synchrony)機制，其獨特之處在於超步(superstep)概念的引進。一次計算過程由一系列全域超步組成，每一個超步包含並行計算(local computation)、全域通訊(非本地資料通訊)以及柵欄同步(等待通訊行為結束)三個階段。

BSP模式有以下特點：

將運算分割為一個一個的超步(superstep)，有效避免死鎖;

將處理器和路由器分開，強調了計算任務和通訊任務的分離，而路由器僅僅完成點到點的消息傳遞，不提供組裝、複製和廣播等功能，既掩蓋了具體的互連網絡拓撲，又簡化了通信協議；

採用同步方式以硬體實現的全域同步和可控的粗粒度級，執行緊密耦合同步式並行演算法。

一些代表性的圖表計算架構如下：

• Neo4j-APOC ：在圖資料庫的基礎上，支援一些基本圖演算法，分散式版本不開源。
• Pregel ：Google 在 2009 年提出，是圖計算模型的開山祖師，後續許多工作都受到它的思想影響。不開源。
• Giraph ：Facebook 基於 Pregel 思想的開源實作。
• Gemini ：清華大學基於 Pregel 思想進行了多項改進的實現，性能優秀。僅提供免費 Demo，商業版不開源。
• KnightKing ：針對 Walker 遊走演算法專門設計的圖計算框架，不具通用性。
• GraphX ：Apache 基金會基於 Spark 實現的圖運算框架，社群活躍度較高。
• GraphLab（PowerGraph）：商業軟體，不開源。已被蘋果收購。
• Plato ：騰訊基於 Gemini 和 KnightKing 思想的 C 開源實現，是一款高效能、可擴展、易插拔的圖計算框架。

4. 從演算法看圖計算

圖演算法指利用特指的頂點和邊求得答案的一種簡便方法，無向圖、有向圖和網絡能運用很多常用的圖算法。對於圖數據，遍歷演算法（深度/廣度優先）是其它演算法的基礎。典型的圖演算法有 PageRank、最短路徑、連通分支、極大獨立集、最小生成樹以及 Bayesian Belief Propagation 等。圖的最小生成樹在生活中常代表最低的成本或最小的代價，常用 Prim 演算法和 Kruskal 演算法。社群發現、最短路徑、拓樸排序、關鍵路徑也都有對應的演算法。

圖演算法包含了 搜尋、配對、分類、評估等多樣化資料分析技術，從演算法結構維度大約可以分成兩類：以遍歷為中心的演算法和以計算為中心的演算法。以遍歷為中心的演算法，需要以特定方式從特定頂點遍歷圖，存在著大量的隨機存取。以計算為中心的演算法，需要在一個迭代週期中有大量的運算進行，資料局部性相對較好。

5.從電腦體系結構看圖計算

圖計算一般都是資料驅動的計算，計算結構無法在運行前準確地進行預測，形態上沒有明顯規律，難以有效率且優質地進行劃分。現有的快取機制往往只能對局部性好的資料存取提速，大量對資料的存取會使處理器頻繁處於等待I/O的狀態。

圖計算的負載具有複雜性，沒有單一最具代表性的圖計算負載。連接頂點的邊，只是無數可能連結中的一個小子集，存在高度不規則性。在圖計算的過程中，讀寫的時空局部性難以掌握，頻寬佔用情況難以預測。

大多數演算法對記憶體頻寬的佔用可能不到50%，是什麼限制了記憶體頻寬的利用呢？處理器需取得指令， 指令視窗間存在空間，暫存器操作數需要等待，直到操作數可用，相關依賴才會解除。由於指令命中率較高，可能導致記憶體層面的平行度下降，難以充分利用平台的記憶體頻寬。較低的快取資料使用比又意味著應用程式難以從空間局 部性中獲利，資料預取策略會失效。資料預取一般對提升效能有幫助，但也會產生大量無用的預取操作。對於記憶體頻寬或說快取容量有限的應用來說，資料預取可能造成一定資源浪費。在多線程計算的情況下，若觸發延遲較高的遠端記憶體訪問，也會抵消多線程的收益。

圖運算需要怎樣的處理器核心呢？一般地，會採用許多小運算核心加高執行緒數的架構，適合處理傳統多核心處理器所不擅長的大圖運算。在多圖並發計算的時候，有共享分配與獨佔分配兩種策略。共享分配策略指將 m 項請求中的每一項都使用 n 個邏輯核心並行處理，由OS管理不同請求在邏輯核心上的切換。獨佔分配策略指為每項請求指派 n/m 個邏輯核心，使邏輯核心不需要在任務間切換。獨佔分配策略更適合併發圖計算，獨佔通常可減少相同並發請求下整體的運行時間。重新排序快取競爭度低可能是獨佔策略在並發圖計算場景中優於共享策略的原因。

就圖計算產生的耗電量而言，負載變化導致系統功率波動，會出現峰谷交錯的情形。若增加併發任務，會改變峰谷比率並抬升耗電量。一般地，對CPU的功耗而言，以計算為中心的演算法平均每條指令能耗大，以遍歷為中心的演算法則相反；對記憶體的功耗而言，以計算為中心的演算法記憶體的平均能耗小，以遍歷為中心的演算法則相反。

大多基於圖計算的應用程式都是記憶體受限的，但也存在受核心元件限制帶來的記憶體利用率不足。足夠的活躍線 程創造並發訪問，或可提升利用率。更多執行緒是需要的，但由於執行緒間不均衡性，可能使用起來效率不高，需要提供更可擴展的並行策略，來優化多核心處理器的高頻寬記憶體使用。功耗和能耗行為從指令角度和頂點運算角度來看都各有不同，需要精準的功耗管理方法，粗放型調整恐難發揮作用。

6.從系統看圖計算

依據大規模圖計算系統的使用場景以及計算平台架構的不同，可以將其分為單機內存圖計算系統、單機外存圖計算系統、分散式記憶體圖計算系統和分散式外存圖計算系統。

單機記憶體圖處理系統就是圖處理系統運作在單機環境，並且將圖資料全部緩衝到記憶體當中。單機外存圖處理系統是圖處理系統運行在單機環境，並且透過計算將圖資料不斷地與記憶體和磁碟互動的高效圖演算法。分散式記憶體系統就是圖處理系統運行在分散式叢集環境，並且所有的圖資料載入到記憶體當中。分散式外存圖運算系統將單機外存系統（Singlemachine out-of-core systems）拓展為集群，能夠處理邊的數量級為 trillion 的圖。

7. 從AI 看圖計算

AI 和圖計算融合產生的圖神經網路（GNN），是目前正在快速發展且重要的領域。各種實體之間的關係數據，它怎麼和神經網路結合？圖神經網絡，利用了表示學習，透過圖的結構先把每一個節點或邊都用向量來表示特徵，然後再進一步地使用神經網路來處理。這擴展了神經網路使用的範圍，把實體之間的關係也引入 AI 的處理中。

圖神經網路可以看作一個圖特徵的學習過程，例如節點的代表特徵或圖級的代表特徵，一般以圖的屬性和圖的結構作為輸入，輸出一組更新後的節點表示。一般這個過程也稱為圖濾波操作。圖濾波會更新節點特徵但不會改變圖的結構。圖神經網路的發展是從不同的理論動機發展出來的，例如，將GNN看作為非歐距離的捲積推廣，那它是基於圖訊號發展起來的；現在大多的GNN基於神經訊息傳遞方法是透過類比圖模型中機率推理的訊息傳遞演算法提出的。

不管是譜方法還是基於空間的思想，圖神經網路最後都可統一到基於訊息傳遞的框架下。 GNN訊息傳遞框架基本概念是在每次迭代時，每個節點都會聚合其鄰居節點的資訊。隨著迭代次數的增加，每個節點包含圖上更大範圍的資訊。例如，經過k次迭代後，中心節點可以取得其k跳鄰域的資訊。其關鍵思想是基於圖結構和已知的特徵資訊生成節點表示。 GNN利用了圖上的結構和節點特徵訊息，產生深層的嵌入表示，而傳統的圖嵌入方法只利用了圖的結構訊息，透過查表的方式產生層嵌入。

7.1 GNN VS MLP/CNN/RNN

圖資料中結點鄰居有兩個特點，一是數量不定，二是順序不定，因此MLP/ CNN/RNN無法直接處理這樣的非歐式資料而只能用GNN建模。實際上，可以將GNN看做一個更泛化的模型，例如，RNN相當於線性圖上的GNN，而Transformer相當於完全圖上的GNN。

7.2 GNN VS Graph Embedding

在GNN之前已經湧現出很多Graph Embedding方法，並被廣泛應用在搜尋類別服務的向量召回階段，這類方法受Word2vec啟發設計，從最初的Item2Vec到Node2Vec基於平衡同質性和結構性的改進，再到MetaPath2Vec基於對圖的異構性改進，以及引入屬性資料緩解行為資料的稀疏性，這類方法都遵循著Skip-Gram的範式。

相比於這些方法，GNN可以結合目標任務端到端地進行訓練，而Graph Embedding更像是預訓練，其學習到的Embedding不一定與目標任務相關，特別是在樣本規模龐大的業務場景，端到端訓練得到的Embedding比預訓練得到的Embedding更有效。

GNN的層級網路結構方便與其他深度學習技術結合，例如GCN Attentinotallow=GAT。 GNN可以適用Inductive的任務，也就是當圖的結構改變後，加入了一些新的結點，如果是Graph Embedding方法就需要重新訓練模型，而GNN可以使用類似GraphSage Node-Wise Sampling的方式，使用已經訓練好的模型直接對新的結點進行推斷，在訊息傳遞的過程中可以使用多種特徵。

7.3 GNN VS Feature Concat & Collaborative Filtering & Proximity Loss

Feature Concat表示將特徵拼接到一起然後透過特徵交叉可以學習到一階的屬性關聯信息。 Collaborative Filtering也可以透過使用者歷史行為學習到一階的行為關聯資訊。 Proximity Loss表示在損失函數中加入正規項使得相鄰的結點更相似，但是一方面它是一種隱式的方式，另一方面想確保學習到高階的相似關係，就需要加入更複雜的K階正則項，這也是GCN提出時的出發點之一。相較之下這三種方法，GNN可以透過堆疊多層顯示地學習高階的關聯資訊。

圖神經網路的設計中有個關鍵的條件要滿足就是置換不變性或置換等變性，就是設計的函數在處理圖資料時，不受節點順序的影響，或是輸入時的順序變換域輸出的順序一致。

8. 小結

圖是一種最靈活的連結方式，讓實體之間可以不受限制地連結。圖計算是研究在大量數據中如何高效計算、儲存和管理圖數據等問題的領域，可以應用於相當廣泛的業務場景，如資本市場風險管理、生命科學研究、醫療保健交付、監控和應對道路事故、智慧基礎設施管理扽等。高效處理大規模資料的圖計算，能推動社交網路分析、語意 web 分析、生物資訊網路分析、自然語言處理等新興應用領域的發展。

【參考資料】 

“人工智慧之圖計算”，清華大學人工智慧研究院，北京智源人工智慧研究院，清華-工程院知識智能聯合研究中心，2019- 2

#https://www.php.cn/link/c9e5c2b59d98488fe1070e744041ea0e

##https://www.php.cn /link/d40d35b3063c11244fbf38e9b55074be

#https://www.php.cn/link/315f006f691#2e689125614ea2225614ea2261 ://www.php.cn/link/51d1cd3a02276948f566e6ea0a7d78cb

以上是圖計算的學習與思考的詳細內容。更多資訊請關注PHP中文網其他相關文章！