《Graph Learning》| 第一章：繽紛的圖世界

9 人贊了文章

通過前文《淺析圖卷積神經網路》的介紹，相信大家對於圖學習有了一個初步的認識，接下來我們將更加細緻的解析圖學習的相關知識。

開啟圖學習演算法的第一步：理解什麼是圖

在數學上，圖（Graph）是表示對象與對象之間關係的方法。從定義上可以看出，圖有兩個要素：

1、對象又稱節點（Node）、頂點（Vertex）、實體（Entity），它描述的是具體的一件事物。

2、關係又稱邊（edge）它描述的對象之間的關係。

我們一般用這樣的形式來表示一張圖：G=(V, E), V表示節點的集合，E表示邊集合；

V={V0,V1,V2,V3}、E={V0V1,V0V2,V1V2,V2V3}

圖的另一種表達方式是鄰接矩陣（Adjacent matrix）

Aij(鄰接矩陣的第i行第j列)的取值表示的是第i個節點與第j個節點之間是否有邊，取值為1表示有邊，取值為0表示無邊。鄰接矩陣刻畫的是圖的結構信息，給定一個鄰接矩陣，相應的圖就可以畫出來。

另外在實際研究中，節點與邊都有特定的類型，比如連接「用戶」與「商品」節點的邊，很可能就是「購買」的類型關係。像這樣，在構建一個具體業務場景的圖時，標識上節點類型與邊的類型，這樣的圖我們稱之為圖的結構表示（Graph Schema），它反應出來的是一種業務上的邏輯抽取。後面我們會結合各類現實場景中的Graph Schema來說說我們關注的一些學習任務。

青睞有加，理解圖的優勢

圖做為一種廣泛應用的數據結構，其優勢主要表現在兩點：

一是順藤摸瓜，給定一個節點，順著其邊的信息，能夠快速的找到它的鄰居節點。換言之，在圖裡面查詢信息很容易。

二是拉幫結派，由於圖的傳播性強（鄰居的鄰居也跟自己關係緊密），相互之間聯繫緊密的節點可以構成一個子圖（或子團）。

上圖中可以明顯看到有a、b兩個子圖，一般像這樣在圖中尋找子團的任務稱為社群檢測（Community Detection ）或者叫作高密子圖挖掘（Dense Subgraph Mining）。

現實場景下繽紛的圖世界

社交網路

利用社交網路圖可以實現以下任務：

1、推薦用戶可能感興趣的人；

2、推薦用戶可能感興趣的帖子或者內容；

3、社群發現（通過用戶社交關係網路挖掘群體結構）；

4、用戶畫像（地點、興趣、關係網路）；

搜索排名

圖在網頁排名中的應用，根據各網頁的鏈接關係網來確定各網頁的排名，又叫做PageRank演算法。其基本思路是被引用越多的網頁重要性越高；被重要性高的網頁鏈接的網頁重要性越高。

評分系統

用戶-產品的評分圖

通過上述的圖可以分析比如哪些用戶可能對啤酒感興趣，哪些用戶可能對尿布感興趣，從而實現商品推薦。還可以實現評分清洗，建模用戶的公平度、商品的良心度、評分的可信度，按照一定的規則迭代更新這三個值，從而分析商品的優劣或者區分惡意用戶。例如上圖中的用戶f，很大可能就是惡意評價用戶。

推薦系統

用戶與歌曲的關係圖譜，可以實現可解釋的推薦和精細化推薦。

比如沿著用戶-歌曲-曲風-歌曲這個路徑是推薦用戶喜歡的曲風下的其他歌曲；沿著用戶-年代-歌曲-歌手是推薦活躍在用戶出生年代的歌手的歌曲（可能是用戶小時候聽過的歌，俗稱回憶殺系列），這些就是可解釋的推薦。

小思考：沿著用戶-歌曲-年代-用戶-歌曲的意義是什麼呢？

關於精細化推薦，從圖中挖掘有很多條路徑，很多種理由去推薦，每個用戶對具體路徑的偏好不一，我們還可以根據歷史偏好信息對用戶做更精細化的推薦。

知識圖譜（關聯圖譜）

知識圖譜通常是指從文本中分解實體及其關係，導入到圖中，便於查詢及推理。簡單介紹兩個很簡單的知識圖譜應用。

?知識圖譜應用之知識推理：

基於規則「爸爸的爸爸是爺爺」可以推理出康熙是乾隆的爺爺。

?知識圖譜應用之語義理解（智能問答）：

通過對「北京」和「博物館」兩個信息的綜合，機器可以得出結論該地方很有可能是指故宮。

風險控制

圖在風控中的應用很廣泛，很多風控的策略邏輯可以轉化為圖裡面的一些具體問題來思考。比如下面涉及到的幾種思路方法，包括像關聯識別、聚類識別、推導識別、異構識別、碰撞識別等一系列應用。

?風險控制之關聯識別

通過強標識性節點的關聯信息來做Identity recognition。比如關聯到相同設備指紋與IP節點的用戶可視為同一用戶。

短時間內關聯到同一設備節點的用戶節點數目異常可考慮為撞庫行為。

同一設備關聯的用戶數目異常

撞庫原理

?風險控制之聚類識別

通過節點關聯信息來挖掘子圖結構，而這種緻密的結構通常會被判定為異常的風險關係。

圖中可以看出，用戶1、用戶2、用戶3和帖子1、帖子2形成了高密子圖

?風險控制之推導識別

順藤摸瓜，找到與異常節點相關聯的節點進行風險排查。

?風險控制之異構識別：

用戶關聯的信息發生較大變化，潛在被盜號風險。

?風險控制之碰撞識別：

節點之間的對應關係出現碰撞矛盾。

公司G同時存在兩個地址，出現數據碰撞，那麼就可能有風險。

歸納總結：圖的學習任務分類

上面和大家介紹的是一些常見場景下的圖結構以及相關任務，總的來說，我們可以從節點、邊、圖三個方面對圖學習任務進行分類。

1、節點上的任務：利用圖中節點的關係可以做包括分類（比如風險識別、價值排名等任務）、聚類（社群檢測、用戶畫像等任務）。

2、邊上的任務：通過圖中節點之間是否有邊可以做比如推薦、知識推理等任務。

3、圖上的任務：圖可以做像高分子分類、3D視覺分類等任務。

在後期專欄中將會對各種任務進行更加細緻的探討。圖在各種場景數據中都有著廣泛的適用性。但是實際應用上，圖的學習一直停留在「規則引擎」、「圖計算」這樣的淺層層面上，本專欄旨在通過梳理 Graph learning的方方面面，和大家一起打開思路，探討真正的 Learning on graph。

更多交流分享可以加入我們的AI交流群geetest_1024

推薦閱讀：