上海交通大學過敏意：面向城市治理的圖智慧分析框架

作者 | 王曄

編輯 | 青暮

目前，中國新的城市治理體系基本形成。與此同時，伴隨著經濟社會的變革、大數據、互聯網的發展以及人工智慧、雲端運算的興起，城市治理面臨著新要求、新挑戰的同時，也實作了跨越式的發展。

那麽技術的進步為城市治理帶來了哪些進展？又面臨怎樣的瓶頸呢？

不久前，在CCAI 2021 大數據智慧學術論壇上，過敏意教授分享了題為 「面向城市治理的圖智慧分析框架」 的主題報告，分四部份介紹了城市治理方面的內容。

過敏意 歐洲科學院外籍院士、上海交通大學講席教授、IEEE/CCF Fellow

過敏意教授是歐洲科學院外籍院士，上海交通大學致遠講席教授，電子資訊與電氣工程學院電腦學科負責人，國家傑出青年基金獲得者，也是教育部創新團隊學術帶頭人，「973」計劃首席科學家。

他長期從事並列與分布式系統和雲端運算的研究，發表學術論文400多篇，著述英文著作4部，主持多項國家自然基金重點計畫以及國家和省部級計畫，曾獲得國家技術發明二等獎和省部級科技一等獎等多項獎項。

AI科技評論對過敏意教授在CCAI 2021 大數據智慧學術論壇上的報告做了不改變原意的整理：

1

城市治理 與圖結構

我們國家的城市化率現在已經達到了60%以上，隨著城市發展得越來越快，「十四五」計劃提出了80%以上的城市要進行城市精細化治理，實作智慧城市建設。智慧城市建設牽涉到方方面面，從電腦科學的角度來看最重要的是大數據技術、人工智慧技術，以及雲端運算技術的結合，這是支撐城市化治理的基石。

目前為止，我們團隊在「十三五」期間的「973計劃」中，主要面向城市精細化治理的三後設資料的融合及協同計算。我們在做城市化治理時，以數據為中心，原來是人、機、物三元空間的數據。到現在，隨著城市的發展，數據越來越大，城市的精細化治理也不斷發展。

城市精細化治理發展分為四個階段：

1. 從原來的物能說話，以數位化、網路化為代表的城市管理，即智慧城市的初級形態。我們借助網路實作連線使得物與物之間能夠互聯起來。

2. 到後來2.0版，就是物物對話。不僅是互聯網，還有物聯網了。從物聯網在城市治理中的作用來看，運用系統化、程式化、標準化的手段，使城市各單元精確、高效、協同和持續發展，實作萬物互聯。

3. 到了3.0版，即人物協同。以人為本，充分發揮人機協同的作用，透過對城市大數據價值的挖掘，使城市各部份功能最佳化執行 ， 呈現的決策能夠更精準，最大程度地服務市民。

4. 4.0時代，就進入了城市大腦階段，即讓城市自身學會思考，能夠自主整合、引導和分配城市管理資源，具有自我最佳化與前進演化能力，真正智慧化，這是最高版的城市精細化治理。

為了真正讓城市學會思考，實作城市治理智慧化，打造智慧、智慧城市，我們正在實踐城市大腦的理念。「十三五」期間，我們和阿裏及杭州的 「城雲科技「 合作，做了城市的交通管理、智慧停車等工作。

我們將人、機、物三元空間的物理世界、人類社會、資訊社會得到的數據進行融合。結果發現越來越多的數據，呈現出圖化的結構，其實是用圖的形式表示出來的。關於這個問題我們以前都沒有註意到，也沒有處理，但這樣以後很多數據都不能夠精準處理。因此，在城市化治理中，圖化治理場景是一個關鍵挑戰。

五個不同領域的圖化治理場景：

（1） 公共安全分析。 首先，在傳感器網路方面，傳感器網路的互聯結構本身就是一張圖。然後多個傳感器形成了傳感器之間的互聯的圖的分析，比如說一個傳感器到另一個傳感器的路由，實際上就是圖分析的問題。其次，比如說遙感監控，現在我們做了人臉辨識，人臉辨識原來是抓特征，現在我們新的方法可以從圖結構中分析人臉特征，這又是一個圖分析的問題。

（2） 生態環境監測 。2017年波蘭氣象部門從2 000個不同的傳感器節點對臭氧層進行了監控。其中的很多問題也是圖結構的問題，比如一個節點到另一個節點之間臭氧的影響，以及對整個的布局來說，會不會產生時間上和空間上的最佳布局等。還有城市樓宇能耗城市化管控。城市樓宇之間，比如高層和低層電能的管控，這也是一個用圖來表示的問題，因此很多最佳化都離不開城市的圖化分析、查詢等等。

（3） 醫療健康服務 。生命健康基因圖譜的分析，也是圖的重構、圖的叠代、圖的分析。還有人腦網路的功能區域分析，現在腦電采集實際上都可以從圖的結構裏面反映出來，所以有大量的個人化的圖的分析。

（4） 交通出行指導。 道路出行中最短路徑演算法本身就是一個圖問題。但是增加了手機數據、路網數據及工具監控數據等，那麽這些圖就變得越來越復雜。還有充電智慧排程，現在我們新能源的車越來越多，新能源的充電樁以及充電樁的位置等都是圖的查詢和分析問題。

（5） 城市大腦運維。 城市大腦的基礎設施有雲端運算、大數據、大數據平台。這一平台現在用到了雲原生的技術，雲原生的技術就要用到微服務。微服務裏面就有很多排程的問題，實際上微服務本身的聯結就是一張圖結構。要提升系統效能，就要進行圖的分析和精細化查詢。還有硬體資源管理，捕捉資源瓶頸，使用者動態圖的系統變化等，這些都是圖的結構、分解和圖的綜合等，實際上都可以歸納到圖的特征的問題。

因此目前對圖的分析和圖的管理越來越迫切，現在我們國家以及世界上很多科研機構公司等都研發了一些面向圖計算的工具，但還是遇到了問題。

2

應對挑戰的 城市大數據協同計算框架

面對大規模結構化的城市治理任務，現有大數據計算平台存在收斂慢、吞吐低問題，影響城市治理決策。

（1）收斂慢：傳統大數據框架如Spark/MapReduce不適應圖的不規則存取模式。

開發環境未針對圖套用客製化設計，難以高效優質地進行執行階段劃分

我們以前「十三五」期間做的事情，基本上都是用的傳統spark、MapReduce等大數據框架來做的，但是這些問題如果要弄到圖裏面預處理，比如說圖要進行偏好設定、分拆等等，用傳統框架就不適用了，它會非常慢，要迴圈往復來做。

（2） 吞吐低：現有主流圖計算框架如PowerGraph/Ligra不支持高並行請求。

上述框架大都忽略了多使用者請求執行共存的問題

現有主流圖計算框架如PowerGraph/Ligra等框架都是單機、單使用者的圖計算結構，雖然克服了spark、Mapreduce等的缺點，它可以圖分析、圖分解、圖查詢等，但是如果面向城市治理這些就不適用了，因為城市治理是高並行的。也就是說這些框架對高並行的圖的問題，都不太適用，所以就會遇到吞吐根本做不了城市大腦支撐的問題。

要解決上述問題就要做城市大數據協同計算框架。圖計算將成為未來城市大數據協同計算框架中的關鍵一環，能夠支撐大規模高並行場景的圖智慧分析尤其重要。

城市大數據協同計算框架

我們以前做了很多Mapreduce、PowerGraph的處理，但是還缺乏圖請求排程、圖結構分析、圖數據分割、圖查詢、圖生成等面向圖計算的工具。所以 我們就一定要把這些工具給數據融合、數據感知開發出來。如果沒有圖分析、圖查詢、圖管理、圖結構分析等，是沒有辦法支撐整個城市大數據協同平台的。所以我們要在有限的資源下，處理高並行多元圖數據分析的請求，對單使用者的圖計算框架實行高並行多使用者的圖計算框架的轉變。

那麽如何高效執行不同使用者送出的多元化圖計算請求呢？

3

並行圖計算的復雜性 及其瓶頸

並行圖計算可以在有限資源下高效並行處理多元化圖分析請求，或將成為新一代雲端運算中最主要的一類智慧服務。它的三個核心步驟是並行圖程式構建、並行圖數據載入、並行圖執行排程。

目前，我們要做的事情是實作 可延伸和永續 。

擴充套件性需求： 隨著圖規模和圖計算服務的激增，需解決平台峰值負載問題。

永續性需求： 支撐高並行場景的圖計算更符合集約高效、低碳環保的要求。

高並行圖的圖分析、圖查詢也延續到了一些人工智慧演算法，比如說現在做人工智慧的技術處理，如果講大模型，比如說GBT-3 1 751億個參數跑一次訓練，相當於一輛用油汽車跑70萬公裏，那麽這對永續發展、低碳環保非常不利。所以說圖計算也是這樣的，如果不斷地進行圖的叠代往復，如果演算法不好，那麽可延伸、永續都不行，所以現在各大公司和雲商像華為和阿裏都對此非常重視，都自己開發了這方面的工具對圖進行分析。我們有一個課題做國家重點研發計劃現在也是做的圖處理這方面的事情。

但是並行圖計算不同於如今的線上數據密集型計算（如MapReduce)，更不同於以往的高效能數值計算。

對並行圖計算來講，請求間和請求內的協同最佳化變得更重要

比如做平行計算時，以往的傳統的平行計算比較規則，我從一個處理到下一個CPU的處理，通訊是比較規則的。這邊處理好以後，下一個通訊基本上模式是一樣的。但是並行圖不一樣，圖的計算模式是不規則的，這個到下一個的並行處理有可能是A節點到B節點，下一個可能是C節點到D節點，模式是完全不一樣的不規則的。

所以其中通訊、最佳化和它的並行都和原來的高效能計算完全不同，因此比較具有挑戰性。與數據密集型計算不一樣，和高效能計算也不一樣，即與以計算和數據為中心的都不一樣，我們現在要強調 以圖為中心的計算。

並行圖計算 主要 面臨的瓶頸主要有 以 下 三 個 。

（1） 使用者圖計算請求主要有圖管理、圖分析。 在圖管理方面，已有較多並行性最佳化工作，比如說資料倉儲、圖查詢等。但對圖分析方面，比如管理查詢不到結果以後怎麽樣能夠對放到基層單元弄出決策來，這方面還缺乏研究，易成為效能瓶頸，所以說我們要做這方面的事情。

（2） 並行圖分析任務之間的不規則幹擾， 多個圖演算法並行執行時，會在時間與空間兩個維度對處理器和記憶體等資源進行搶占，且幹擾方式不規則，最佳化空間很大。

比如使用者的要求各不相同，使用者提出的請求也各不相同。這些圖請求比如Pagerank、Kmeans等這些都是不一樣的，那麽具體到圖的分割查詢和記憶體的放置都可以以不同方式來進行模組放置，排程也不一樣。所以這裏的最佳化空間非常大，一個是復雜，一個是不規則的幹擾。

（3） 並行圖分析與圖查詢任務間的協同。

請求還存在對同一塊圖數據的存取依賴問題，進一步提升並行圖查詢的效率對於釋放並行圖分析效能也至關重要。比如說有的要查詢邊，有的查詢點，有的要查詢整張圖。對這些分割的任務，也就是並行來的任務，對一些子圖的分割和綜合又是一個非常復雜的問題。

4

對並行圖分析的 初期探索

（一） 工業界計畫概述

現在工業界對於圖的分析、圖的並行、圖的查詢非常重視，但是圖拓撲內容分析現在還不多。Apache 上目前的開源圖計算系統主要以圖資料庫管理為主，面向圖拓撲內容分析的並行圖管理系統還處於萌芽階段。這是我們調查下來整個Apache Graph Systems的列表，大概就是這幾十個：

相關連結：http:// tinkerpop.apache.org/

（二） 學術界研究總覽

早期基本上關註的是圖的請求，焦點主要是圖查詢。到2014年開始有並行圖分析，然後多使用者並行圖比如圖數據共享已經開始關註了；2017年提出多圖多使用者場景，但對圖請求內部缺乏分析；到2018年對請求內部特征最佳化以及圖並行的計算進行考慮。國內主要在做的高校是上海交通大學、華中科技大學、北京大學。

（三）上海交通大學做 的一些工作

（1）圖 化治理任務的並行計算框架

文章先後發表在IEEE ICCD和IEEE TPDS上

我們做的工作就是對圖化治理任務的並行計算做了一個框架，也就是對線下進行繪像線上排程相結合，將訪存特性傳遞給排程器，這樣並行的會比較快，訊息傳遞就會比較快。然後提出架構感知的負載均衡和執行緒排程、最佳化多圖的並行執行的效果請求效能可以提升5.4倍了。實作了一套面向圖化治理任務的冗余操作削除機制，對整個圖存在的冪律分布、縮減操作等都做了分析，然後改進了圖化治理任務流程，使分析提升了很多倍。

（2） 圖化治理任務的高效編程框架

文章先後發表在IPDPS和ACM TACO上

如果將圖放到編程框架裏面進行描述是很方便的。如果變成框架以後，就像人工智慧框架一樣對編程是非常方便的。圖計算原子操作復雜，然後GPU記憶體利用率是不高的。如果要對這些圖利用GPU來說，對於並行是絕對沒有問題的。所以改進數據結構，從圖冪律分布出發削減冗余的計算操作，我們提出統一記憶體利用高效的圖計算原子操作，最佳化多圖資源利用，搞出一個編程框架來對圖的演算法進行精準的描述，就可以比較容易的對圖的性進行提升。

這是我們圖分析框架的編程介面，先把一個問題變成一個圖的結構一個任務，比如說多少頂點多少邊互相怎麽連線，頂點預處理，然後對活躍邊進行更新，頂點生成等等叠代技術處理。經過這一套預備、更新、生成框架以後，整個圖的分析和高並行處理就非常簡單了。

這是效果，實作系統資源高效利用。

5

技術 成果 的 實際套用

（一） 公共衛生治理平台

借助數據泛在發現和最佳化組合，建立起多源異構城市環境氣象數據的跨時空圖結構關聯性。

數據量：共計近千萬條數據 需求方：中國城市治理研究院

這是我們和中國城市治理研究院合作的，他們的需求是對霧霾進行監控，這個有點像對臭氧層的監控一樣的，我們也是布了很多傳感器，然後用圖進行分析，對霧霾進行分析和處理。

第一個是利用空間的關聯分析制定霧霾判斷分析。這是對中國的31個省、市、自治區的霧霾和工業產值的關系的分析，所有的關聯數據都可以給出一個框架和處理，整個過程都有圖的分析和決策在裏面。

（二） 交通客流監控平台

借助城市大數據三元空間群智發現與群智建模，實作了多元多模數據下的多檢視細粒度人群分析。

數據量：共計超過20TB 需求方：深圳市地鐵集團有限公司

這是我們和深圳地鐵集團對城市交通軌域進行了分析。這個數據很簡單，每個地鐵站實際上就是一張圖。

這張圖幹什麽用呢？就是即時監控，比如進站人數，出站人數，在網人數等。然後用不同的顏色標出來，幾號線、哪個站有多少人等。這樣會便利人們的交通出行。比如知道坐哪條線、哪邊換乘。客流預測精準度從87%提高到95%。

（三） 人群密度推演平台

借助城市大數據的深度叠代計算，完成了即時感知與靜態預測的融合，實作城市人口的高效分布推演。

數據量：百萬級車輛千萬級使用者 需求方：深圳市交通運輸委

這個完全就是一張圖：單檢視建模、多檢視建模，對圖的分析。這裏面總共是六維數據。

黑洞表示人口密度超過正常均值的2倍，熱點表示人口密度大超過正常均值

做什麽事呢？人口密集時，有可能會出現危險。人口密度一般來說比較均勻，如果出現紅點了，那麽就是人口密度超過正常均值，我們一般在800×800m的範圍內，比如說2萬人口是正常分布，如果超過兩萬就是熱點，黑洞表示人口密度超過正常均值的2倍，就要警示就是要派警力來疏散人群等等。這完全就是一個圖的分析，利用六維數據對圖進行分析對人口密度進行高度精準的預測。

（四） 城市路況分析平台

借助城市治理任務圖結構化數據的智慧存管，達到復雜城市交通路況的即時處理和分析預測。

數據量：百萬級車輛千萬級使用者 需求方：深圳市交通運輸委

這是路況，也是六維數據。對一條路上有多少人卡車、公交、出租車、私家車等，進行相似度分析、路況預測。下面這是深圳市的地圖，綠色的是貨運車，藍色的是公交車，然後對它們進行精準分析。

這些方面，我們主要是和深圳、杭州，阿裏城市大腦合作，進行大數據的分析，包括人、機、物三元空間分析以及圖分析工具都整合在一個平台系統裏面。前期相關技術套用於阿裏城市大腦、網易數據地圖等關鍵資源密集型套用場景，整體效能提升顯著。去年也拿到了教育部科技進步一等獎。

6

研究展望

（ 一 ） 高並行圖化治理任務的硬體加速

結合並行圖計算任務的多為領域知識特征，研究硬體資源共享利用方式，設計高效能低能耗的並行圖計算協同加速框架。

左為基於FPGA可重構計算的加速系統，右為基於GPU/NVM加速的自適應架構

首先是高並行圖化治理任務的硬體加速。這方面現在還沒有做，我們知道人工智慧硬體加速非常快。我認為硬體加速非常重要，如果有了硬體，那麽我們用傳統的GPU和CPU進行排程會省很多事。針對圖演算法，比如說給它可重構計算加速硬體化，那麽如何對動態參數調節，比如說基於GPU加速的自適應架構等等，也是研究的另外一個課題。

硬體加速，這是一個自適應的。比如說控制部件也可以硬體化。整個的軟硬體協同設計的一個框架必須要做出來。這對整個高並行圖計算的平台會產生非常大的影響。

（二） 圖化治理任務的執行時自主最佳化

研究並行圖計算服務的時空動態特性，建立異構計算環境下開銷可估、精度可控、效能可調的圖計算自主管理最佳化機制。

第二個是執行時自主最佳化。現在使用者請求、請求預處理及特征表示、排程分配等等這一套，還不是在更精準的狀態下可以做到。必須我們事先預知一些演算法，一些統計上的框架來做。今後可能實作自主管理，自主排程。

（三） 智慧城市多元化圖計算服務平台

建立統一的並行圖計算多元支撐平台，制定設計規範和關鍵技術標準，完善接入機制，促進高品質多元化的圖計算服務。

做服務平台，針對面向政務的、面向民生的、面向產業的能不能有一個統一化的平台這個可能就比較大了。比如說現在在做城市特征的一些東西，面向政務的要求可能就會完全不一樣，要做這方面就會遇到很大的挑戰。

（四） 並行圖計算的基準測試評估機制。

需要研究平行導向圖計算的綜合效能評估機制，尤其是開發多程式圖負載。

我認為這方面可以做很多事情，而且必須是要做的。目前對圖的多程式圖負載、圖並行機制的基準測試程式還很少。以及效能評估標準如何制定這一方面，弄出一個benchmark來大家都可以用，我們也正在做這件事。

7

總結

雷峰網雷峰網