楠姐技術漫話：圖計算的那些事 | 京東雲技術團隊
不知道大家在平時的工作中
有沒有聽說過「圖計算」這個名詞
但大家一定在各工作彙報，技術分享中聽說過「智慧化」，「人工智慧」這樣的字眼
而我們今天要嘮的這個圖計算
就是人工智慧領域內近幾年炙手可熱的前沿寵兒
也是我們風控反欺詐中常用的「大殺器」
在瞭解圖計算之前
首先得了解什麼是「圖」
我們今天所說的圖
其實是用於表示物件之間關聯關係的一種資料結構
具有很強的抽象性和靈活性
在結構和語意等方面具有很強的表示能力
正是由於圖結構豐富的表現力
在現實生活中有很多可以表示為「圖」的例子
例如社群網路、道路網、金融交易等
研發或者演演算法相關的小夥伴們都知道
我們常用的機器學習和深度學習演演算法
大多都是用於處理一些規整、有序，或者結構化的資料
比如矩陣、圖片、文字、序列等
且所處理的資料都是被假設是獨立同分布的
然而圖上的節點都是自然相連
這也就表明節點之間不是獨立的
此時，今天我們要提的圖計算就來了
它的核心正是為了將資料建模為圖結構
並解決如何將問題解法轉化為圖結構上的計算問題
當演演算法任務涉及到多個體之間關聯分析時
圖計算往往能夠使得問題能很自然地表示為一系列對圖結構的操作和計算
但是圖計算所需要解決的問題多種多樣
難以使用一套計算模式解決所有的問題
接下來我們就來系統地盤一盤
關於圖計算的那些事兒
---★---
比如，藉助邊是否有方向
圖可以分為有向圖和無向圖
藉助邊是否有權重
圖還能分為有權圖和無權圖
藉助圖中的點和邊是否具有多種型別
圖又能分為同構圖和異構圖
還有，藉助圖結構和圖資訊是否隨時間變化
圖能分為靜態圖和動態圖
「度」和「鄰居」
是涉及圖節點的兩個重要概念
節點的「度」是指的與之相連的節點個數
如果是有向圖，還會區分「入度」、「出度」
節點的「鄰居」則是指與之相連的其他節點
關於圖的表示
還有幾個基礎概念是不得不提的
一個是「鄰接矩陣」
用於量化表示節點之間的邊關係
還有就是「節點特徵」和「邊特徵」
用於表徵節點和邊的特有數值屬性
無論多麼複雜的圖演演算法模型
都是基於這些基本概念進行的
提一個關於圖的最基本的問題——節點表徵問題
就是如何基於以上的圖的資訊和屬性
對圖中的節點或者邊進行量化表示
在CV和NLP任務中
我們會設計CNN和RNN模組
來建模影象畫素點和文字文字表徵的資訊
在圖的表徵學習中也是一樣的思路
有了合理的節點向量表示
我們就可以探索各類下游任務
比如進行節點分類
找出那些擁有特殊表現或屬性的節點
或者進行社群劃分
找出那些聚集性最強、相似性最高的節點集合
另外，還可以進行連結預測、子圖劃分等各種下游任務
想借助圖計算做什麼
完全取決於你的實際需求
看到這裡
就可以恭喜你
你已經入門圖計算了
---★★---
圖計算其實並不是新興的演演算法
對它進行歷史溯源的話
尤拉被認為是人類歷史上最偉大的數學家之一
由於他對哥尼斯堡七孔橋問題的描述
圖論學科便繼而產生
在哥尼斯堡的一個公園裡
有七座橋將普雷格爾河中兩個島與河岸連線起來
尤拉於1736年研究並證明了此問題
他把問題歸結為「一筆畫」問題
並證明一筆畫的走法是不可能的
在他的研究過程中
就把問題中的陸地與橋分別抽象為點和邊
並形成了一個簡單的拓撲圖
引出了關於圖的基礎概念
在那之後，出現了圖論的一個早期應用——地區渲染（染色）
隨著15—17世紀大航海時代的到來
以及法國大革命之後民族國家概念的興起
世界各國都開始繪製更高精度的地圖
而繪圖中如何用最少的顏色來保證相鄰的兩個區域（國家、州、省）
用不同的顏色區別開來的問題就是個經典的圖論問題
19世紀中葉，數學家們以手工計算的方式證明了「五色地圖」的問題
而直到整整一個世紀之後的1976年
才在計算機的算力的幫助下初步證明了「四色地圖」的可行性
並通過圖計算優化後
以四色圖取代了五色圖
以上地圖上色問題是數學中典型的NP完全問題
例如導航、資源排程、搜尋和推薦引擎
然而這些場景所對應的巨量資料框架及解決方案
在最開始
並沒有真正意義上使用原生化的圖儲存與計算模式
換句話說，人們依然在用列資料庫
甚至檔案資料庫來解決圖論問題
低效低維的工具被用來強行解決複雜高維的問題
那麼它的使用者體驗可能很差或者是投入產出比極為糟糕
最近幾年，隨著網際網路的發展
知識圖譜逐步深入人心
圖計算和圖資料庫的發展才開始重新受到重視
近半個世紀，也有很多圖計算的演演算法問世
包括1956年出現的知名Dijkstra演演算法
研究解決了圖的最短路徑問題
更復雜的各類社群發現演演算法也應運而生
用於檢測社群、客群、嫌疑人之間的關聯
就是將圖中的每一個頂點都表示成一個低維向量
並使該向量能夠儘可能多的儲存圖的結構和內容資訊
並可以作為特徵用於後續的學習任務
如節點分類、連結預測等
這些工作針對同構圖、異構圖、屬性圖、動態圖等不同型別的資料
提出了各式各樣的方案
包括經典演演算法DeepWalk、LINE、Node2Vec
這些演演算法的基本思路是基於隨機遊走生成資料
然後通過訓練優化引數
產生概率模型
將經典神經網路模型如 RNN、CNN等擴充套件到了圖資料上
與圖表徵學習試圖學習出每個點的向量不同
圖神經網路的目的其實是學習出聚合函數
所有點通過同一個函數就可以利用區域性資訊計算出自身的表徵
即使是圖結構發生變化，甚至是完全新的圖
也能用原來的函數計算出有意義的結果
有關圖神經網路，也已經誕生了一系列經典演演算法
---★★★---
最後，說些關於圖計算的實際應用吧
當下許多大型網際網路企業、金融科技公司
其實都離不開圖計算技術
Google創始人Larry Page在20世紀末發明的PageRank
這是一種大規模頁面、連結排序的演演算法
可以說，早期谷歌的核心技術就是一種淺層的並行圖計算技術
還有Facebook，它的技術框架的核心是它的Social Graph
即朋友關聯朋友再關聯朋友
由此臉書建立了強大的社交關係網路
臉書開源了很多東西
但是這個核心的圖計算引擎與架構從未開源過
如果你能回憶起2007-2008年爆發的世界金融危機
萊曼兄弟公司破產
當時高盛集團能全身而退
背後的真實原因是應用了強有力的圖資料庫系統——SecDB
而對於所有技術驅動的新型網際網路公司
比如Paypal、易趣和許多我們國內的金融和電子商務公司
圖計算也並不罕見
圖的核心競爭力可以幫助他們揭示出資料的內部關聯
最近十年以來
隨著以深度學習為代表的人工智慧技術廣泛應用
圖學習逐漸成為了一個熱點話題
也在因果關係、可解釋性方面取得了突破進展
現在，圖學習也已進一步擴充套件應用
比如廣告、金融風控、智慧交通、醫療、智慧城市等各個領域
那就最後再說些金融反欺詐中的圖計算應用例子
在金融、電商等涉及金錢交易的領域
總是不乏活躍在其中以謀取非法利益的黑產
比如薅羊毛、刷單、套現、虛假交易等
相比起個別使用者自身偶發的套利行為
那些以團伙為單位在各業務場景下聚集操作作案的黑產團伙
他們的行為會對平臺造成更大更嚴重的經濟損失
而圖計算正是識別團伙性案件的良方妙藥
通過將萬千使用者、商戶、裝置、網路環境等作為節點
將使用、交易等資訊作為關聯資訊建邊
即可形成一個覆蓋範圍極廣的異構圖
再結合不同的應用背景確定識別目標
並挑選圖計算模型、樣本、標籤等
即可進行一次有監督學習的圖訓練
最終在推理階段對圖中的節點或邊進行其風險水平的概率輸出
那就會有小夥伴說了
風控場景高質量樣本標籤太少了
問題不大，也有很多圖模型可用於無監督學習
比如社群發現，就不需要任何標籤資訊
即可將關聯最緊密的節點集合進行聚類
在我們的經驗裡
是識別黑產團伙最好用的圖演演算法之一
再比如近幾年熱門的自監督學習、對比學習
應用於圖計算領域則可以對圖進行無監督預訓練
從圖結構、圖屬性自身的性質出發
為圖節點學到具有良好表徵能力的向量
可用於下游的各類風控智慧模型中
---★★★★---
隨著近期AIGC大模型的爆火出圈
人工智慧又迎來了新一波浪潮
相比生成式的語言和視覺模型
圖計算確實顯得冷門一些
但楠姐相信好飯不怕晚
沒有發光的日子都是在為發光做準備
也許會有一天，圖計算也能迎來自己的熱搜
----寫在最後----
★本篇文章圖片構思、創意、整體結構、後期修改，全部版權歸京東楠姐所有，素材生成均源自於Midjourney以及楠姐原創提示詞生成。楠姐出圖不易，且並非完美，請勿未經允許用於其他場合及目的
★本篇文章圖片創意均只為了說明及示意，且帶有一定誇張和幽默元素，切勿對號入座哦如有雷同，純屬巧合無意冒犯~
★本篇文章文字均根據以下參考文獻彙總撰寫：
[1]. 馬耀，湯繼良. 圖深度學習[M].電子工業出版社.
[2]. 張長水，唐傑，邱錫鵬[M]. 圖神經網路導論[M].人民郵電出版社.
[3]. 知乎. 圖計算髮展簡史[EB/OL].
https://zhuanlan.zhihu.com/p/562893366
[4]. 百度. 巨量資料的基礎——圖計算的發展歷程[EB/OL].
https://baijiahao.baidu.com/s?id=1743913772591545506&wfr=spider&for=p
作者：京東科技 丁楠
內容來源：京東雲開發者社群（未經授權請勿轉載）