圖計算

出自 MBA智库百科(https://wiki.mbalib.com/)

圖計算（Graph Processing）

　　圖計算（Graph Processing）是一類在實際應用中非常常見的計算類型。許多大數據都是以大規模圖或網路的形式呈現，如社交網路、傳染病傳播途徑、交通事故對路網的影響許多非圖結構的大數據，也常常會被轉換為圖模型後進行分析。圖數據結構很好地表達了數據之間的關聯性。要處理規模巨大的圖數據，傳統的單機處理方式已經無力處理，必須採用大規模機器集群構成的並行資料庫^[1]。。

　　圖計算，簡而言之就是將數據按照圖的方式建模，以獲得用扁平化的視角很難得到的結果，更適合海量數據的數字化時代。目前，包括華為、螞蟻、AWS等公有雲、資料庫領域的巨頭，都在大步推進圖計算的商業化與應用場景探索。最近一段時間，一級市場也掀起了一股圖計算的創業與投資熱潮，冒出了Ultipa、創鄰科技等多家創業企業。

　　2022世界人工智慧大會論壇上，世界“最快”的圖資料庫TuGraph宣佈開源。據悉，TuGraph由螞蟻集團和清華大學共同研發，是圖資料庫權威測試世界紀錄保持者，也是世界上有測試紀錄的“最快”圖資料庫。開源技術指導委員會也同時成立，以共同建設圖資料庫應用生態。

　　螞蟻集團圖資料庫負責人洪春濤介紹，這是一套分散式圖資料庫系統，可以支持萬億級邊上的實時查詢。此次開源的TuGraph單機版，具備完備的圖資料庫基礎功能和成熟的產品設計，“相較於市場上常見的開源產品，TuGraph單機版的性能高10倍以上”。因此，它可以輕鬆支持TB級別數據和百億級別大圖，足以滿足大多數業務場景需求。隨著TuGraph的開源，開發者可以聚焦應用層，打造屬於自己的圖數據，從而提升行業整體技術應用水平^[2]。

　　相關基礎知識：GAS 編程模型、BSP 模型、節點為中心編程模型、計算範型。

　　業界常見框架：Pregel、GraphChi、Spark GraphX、PowerGrah、Apache Giraph、Apache Hama。

　　伴隨著元宇宙、人工智慧、雲計算、大數據等前沿科技的興起，支撐這類概念的一系列“黑科技”也正在加速佈局，圖計算正是其中之一。

　　圖計算這項技術在學術理論發展史上可追溯至18世紀，發展至今已然成為支撐未來科技發展不可缺席的技術力量。進入21世紀，隨著大數據、元宇宙、人工智慧等前沿科技的興起和迅速發展，圖計算在多個領域廣泛應用。

　　與此同時，與之相關的學術科研、相關產業佈局、資本賽道等方方面面熱度均在提升，“黑科技”的神秘面紗正逐漸被揭開。

　　某種意義上來說，圖計算並不算是新近建立的學科理論。圖計算可以溯源至18世紀，學術界普遍認為，著名數學家歐拉對哥尼斯堡七橋問題的研究是這項技術的起源。

　　七橋問題是一道頗具趣味性的數學題，即如何能夠在不走重覆路的情況下，走遍哥尼斯堡一個公園裡連接4塊陸地的7座橋，形式上與益智小游戲中的一筆畫游戲類似。數學家歐拉在解決這個問題的同時，將其發展成為數學中的圖論。

　　其後，圖計算在圖論的理論基礎上發展延伸。在圖論中，圖被定義為一個由“頂點”和“邊”組成的多元組，若幹頂點由邊連接，表達之間的關聯和交互，形成“圖”。在數據視域下，將數據按照圖的方式建模，以此來表達問題並予以解決的過程即為圖計算。

　　“以圖之名，鏈接萬物。”研究機構CB Insights中國以此概括圖計算的應用前景。據其近期發佈的《2022中國圖計算技術及應用發展研究報告》中信息顯示，近年來圖計算學術研究領域發展迅速，從2014年到2021年間，圖計算領域論文數量呈現翻倍增長趨勢，其中以中美兩國學者為首。

　　清華大學、北京大學、中國科學院以及華中科技大學等高校及研究機構是國內的圖計算領域研究主力，主要研究領域涵蓋了圖數據、操作系統、人工智慧、大數據、分散式系統等多個方向。

　　科研學術力量的重點聚焦促進了圖計算在產業市場層面的落地，如今國內已悄然形成巨頭與垂直企業併進的市場格局。具體佈局此類業務的企業中，螞蟻、阿裡、騰訊等互聯網巨頭，以及海致星圖、歐拉智能等頭部垂直初創企業，成為這兩種不同類型市場參與者的典型代表。

　　“小到社交圈，大到元宇宙”，圖計算一度成為各種科技論壇的熱議話題，公眾對其在應用層面的價值尤為關註，目前圖計算的應用主要集中在金融、能源、政企、社交網路、搜索引擎、推薦系統等方面。

　　國內的新冠肺炎疫情防控工作中，各地衛健委通過大數據手段對部分病例、密接者活動軌跡進行精確追蹤和分析最為公眾所熟知，這其中也使用了圖計算技術。

　　圖計算技術在此項應用中，能夠直觀展示出相關人員的地理位置、活動軌跡等相關情況的數據。各個實體相當於圖計算理論中的“點”，其相互之間的傳播關係、關聯關係，可以利用“圖”的手段呈現出來，疫情的傳播路徑也在這一基礎上得到準確繪製。

　　2020年的武漢疫情防控中，圖計算技術被應用到大數據平臺中，海致研發的知識圖譜和數據中台為當地群體流調提供了便利。

　　海致集團總裁楊娟告訴《中國經濟周刊》記者：“防疫科技人員可以在圖之上進行計算、分析和挖掘，包括關係的發現、群體的識別、個體的更高維度分析、事件的傳導和隱性知識的推理，幫助用戶實現最快、最準、最全關係挖掘，以及知識推理、事件溯源。”

　　在元宇宙、人工智慧等前沿科技成為科技領域熱點的背景下，圖計算技術在這些領域中的綜合應用也成為學術討論中的焦點。

　　“元宇宙的落地，有著不同的階段和不同的路徑，現在正在進行的是物理世界的數智化，圖計算在其中發揮重要作用。”楊娟說，“在這個過程中，我們把萬事萬物，包括房屋、設備、人員、手機賬戶、車流、物流、行業知識融匯在一起做知識的提取和構建，形成能夠映射真實物理世界的圖譜，這些圖譜之間相互交織連接在一起，在上面涌現出各種各樣的業務場景、產業場景、生活場景、文旅場景、金融場景、政府場景等，從而將物理世界數字化和智能化。”

　　“圖計算在元宇宙中的另一重要應用體現在數字人這一關鍵單元上。”楊娟說，“數字人是元宇宙中基礎的交互單元，近年來數字人在視覺與語音、形象模擬、動作捕捉、場景渲染等方面的技術發展迅猛，但是數字人的互動、認知相關的部分，則仍然處於較為早期的階段，很大程度上取決於我們能不能構建出足夠豐富、足夠延展、足夠準確關聯的超大規模知識圖譜，讓數字人真正擁有智慧和靈魂。”

　　中國工程院院士、清華大學電腦科學與技術系教授、海致科技首席科學家鄭緯民在談到人工智慧的發展時表示，圖計算是人工智慧應用中認知智能的基石，“過去大數據處理都用SPARK，但是SPARK這個軟體機損比較慢，還費記憶體，用圖計算辦法來處理複雜的問題，處理速度會比較快”。

　　鄭緯民認為，更大規模、更複雜的數據實時進行計算是圖計算的技術優勢，高性能圖計算是人工智慧的核心。“圖計算規模不斷增長，比如說我們用導航的道路圖很大，社交網路更大，Web圖也很大，人的腦子更大，這都可以用圖計算來解決問題。”

　　資本涌入“賽道”，圖計算領域需要實質性的突破

　　“突破全記憶體高速數據引擎、高可靠數據存儲引擎、分散式數據處理與任務調度架構、大規模並行圖數據處理等關鍵技術，推動高性能資料庫在金融、電信、能源等重點行業關鍵業務系統應用。”2021年11月，工信部發佈了《“十四五”軟體和信息技術服務業發展規劃》，指示在資料庫領域，應關註大規模並行圖數據處理等資料庫關鍵技術的突破。

　　政策的引導下，圖計算在行業中的佈局動作也吸引了資本的關註。

　　公開數據顯示，2021年6月，國際知名的圖資料庫公司Neo4j完成由Eurazeo 領投、GV（原 Google Ventures）參投的 3.25億美元F輪股權融資，創下圖資料庫與圖計算賽道的最大單筆股權融資紀錄。此次“破紀錄”的投資事件引發業界一片熱議。

　　視線轉回國內，資本對圖計算領域追捧與國外相比不遑多讓。據CB insights中國觀察，近3年中，國內圖計算企業融資主要集中在pre-A至C輪，參與的投資方包括騰訊、高瓴創投、紅點創投等多家機構，單筆投資額集中在數千萬至數億元左右。

　　據不完全信息顯示，今年以來，國內圖計算領域多家垂直企業獲得大額融資。其中，年初海致科技完成超過5億元的D輪融資，該輪融資由中國互聯網投資基金領投，上海人工智慧產業投資基金、高瓴創投、君聯資本、微村智科、一村資本、億宸資本、禾其資本跟投；2月，歐拉認知獲GFC、啟迪之星、方信資本數千萬元人民幣Pre-A輪融資；5月，淵亭科技獲得達晨財智億元人民幣B輪融資。

　　“賽道”已然形成，如何在圖計算領域實現真正的突破？

　　鄭緯民著文分析，首先要堅持走自主創新之路，確保每一行代碼都是安全可靠的；同時，政府部門的產業、稅收政策和資金支持，要和社會資金、人力資源的投入共同發力，形成百花齊放春滿園的局面；再者，要堅持應用拉動與創新驅動並重，走產學研結合的協同創新之路。通過應用引導學術研究的方向，確保科研成果快速轉化為生產力；通過創新驅動完成技術的預研儲備，培育並形成新的市場發展方向，確保技術的引領性和產品的競爭力。

　　網頁排序

　　將網頁作為頂點，網頁之間的超鏈接作為邊，整個互聯網可以建模成一個非常巨大的圖（十萬億級邊）。搜索引擎在返回結果時，除了需要考慮網頁內容與關鍵詞的相關程度，還需要考慮網頁本身的質量。

　　PageRank是最早Google用於對網頁進行排序的演算法，通過將鏈接看成投票來指示網頁的重要程度。PageRank的計算過程並不複雜：在首輪迭代開始前，所有頂點將自己的PageRank值設為1；每輪迭代中，每個頂點向所有鄰居貢獻自己當前PageRank值除以出邊數作為投票，然後將收到的所有來自鄰居的投票累加起來作為新的PageRank值；如此往複，直到所有頂點的PageRank值在相鄰兩輪之間的變化達到某個閾值為止。

　　社區發現

　　社交網路也是一種典型的圖數據：頂點表示人，邊表示人際關係；更廣義的社交網路可以將與人有關的實體也納入進來，例如手機、地址、公司等。社區發現是社交網路分析的一個經典應用：將圖分成若幹社區，每個社區內部的頂點之間具有相比社區外部更緊密的連接關係。社區發現有非常廣泛的用途，在金融風控、國家安全、公共衛生等大量場景都有相關的應用。

　　標簽傳播是一種常用的社區發現演算法：每個頂點的標簽即為自己的社區，初始化時設置自己的頂點編號；在隨後的每一輪迭代中，每個頂點將鄰居中出現最頻繁的標簽設置為自己新的標簽；當所有頂點相鄰兩輪之間的標簽變化少於某個閾值時則停止迭代。

　　最短路徑

　　在圖上發現頂點與頂點之間的最短路徑是一類很常見的圖計算任務，根據起始頂點與目標頂點集合的大小，又可分為單對單（一個頂點到一個頂點）、多對多（多個頂點到多個頂點）、單源（一個頂點到所有其它頂點）、多源（多個頂點到所有其它頂點）、所有點對（所有頂點到其它所有頂點）等。對於無權圖，通常使用基於BFS的演算法；對於有權圖，比較常見的有SPFA演算法、Bellman-Ford演算法等。

　　最短路徑的用途十分廣泛：在知識圖譜中經常需要尋找兩個實體之間的最短關聯路徑；基於黑名單和實體之間的關聯可以發現其它頂點與黑名單之間的距離；而所有點對的最短路徑可以幫助衡量各個頂點在整個圖的拓撲結構所處的位置（中心程度）。

　　如：利用圖計算在微信支付負責風控和異常識別，通過圖演算法和關係網路識別資金異常行為，保障微信支付用戶的資金安全^[4]。

• 流式計算
• 即席分析