干货！基于神经网络的多粒度图表征学习
點擊藍字
關注我們
AI TIME歡迎每一位AI愛好者的加入！
圖是建模實體與實體之間關系的常用數據結構。近年來，圖數據挖掘引起了學術界和工業界廣泛的關注，如分類、聚類等等。然而圖相似度學習這一任務卻未得到充分的研究，如何計算一對圖結構數據之間的相似度？由于圖結構數據的復雜、多樣性，使得圖相似度學習算法的設計充滿了挑戰性與特殊性。為此，本文基于圖神經網絡、圖池化算子以及子圖匹配等模塊，設計了一種超圖匹配框架來高效的進行圖相似度推理。具體來說，本文提出的H2MN框架從超圖的角度出發，將每條超邊作為一個子圖來進行匹配，捕獲到了圖上豐富的子結構相似性。為了降低匹配的時間復雜度，本文還設計了基于超邊的池化算子來將大的超圖轉化為較小的超圖。通過在多個公開數據集包括生物以及社交網絡等類型圖數據上進行驗證，本文提出的方法在圖回歸以及分類任務上均取得了最佳的效果。
AI TIME 特別邀請了新加坡國立大學博士后張震，給大家帶來分享《基于神經網絡的多粒度圖表征學習》。
張震：
新加坡國立大學博士后，2021年畢業于浙江大學計算機科學與技術學院，博士期間主要研究方向為數據挖掘、圖神經網絡與推薦系統，目前已在KDD、WWW、IJCAI、TKDE等國際頂級會議和期刊中發表多篇論文。
01
研究背景與意義
傳統圖挖掘算法示例
（1） 如果節點0、3、6、8標簽已知
（2） 如何預測剩余未知節點的標簽
人工設計特征
（1） 統計每個節點的出入度信息
（2） 計算每個節點到其余節點的最短路徑均值信息
（3） 統計每個節點的子圖信息
缺點：需要相關領域知識人工設計特征、靈活度不高
如何同深度學習一樣去自動的提取圖數據上的特征呢？
給定圖G =（V,E)?其中|V|,|E|代表圖中節點和邊的個數，A表示的是圖中節點邊信息 構建的鄰接矩陣
圖表征學習的目標是通過映射函數學習出節點的表征向量，它可以捕獲到圖中的結 構、節點的屬性以及標簽等信息
圖表征學習任務的難易程度取決于其輸入以及輸出的設置
?（1） 圖數據類型紛繁復雜，如何捕獲不同類型圖數據中的關鍵信息進行表征學習？（可能存在同構圖和異構圖，靜態圖和時序圖）
?（2） 圖挖掘任務錯綜復雜，如何針對相關任務設計不同的圖表征學習模型？（不同的任務，需要我們去捕捉不同的語義信息；對于表征的好壞也有不同的標準）
為了解決上述挑戰，本文主要對輸入以及輸出四種不同粒度的表征學習問題展開了研究
橫軸：模型輸出的節點表征
縱軸：模型輸出的圖數據類型
02
?主要研究工作
屬性圖中節點級表征學習
屬性圖是一種節點富含屬性信息的圖結構，例如社交網絡中往往包含用戶的年齡、 性別等資料信息
節點的屬性信息可以進一步反映出圖中的潛在模式
給定圖G =（V,E,X)其中|V|,|E|代表圖中節點和邊的個數
?（1） A表示的是圖中節點邊信息構建的鄰接矩陣,
?（2） X表示的是圖中節點的屬性信息
捕獲圖的結構以及節點的屬性相似性
現有研究工作
（1） 將屬性信息構建成圖中的節點來建模節點和屬性信息的共現關系
（2） 通過屬性信息計算出節點之間相似度來約束節點的表征
（3） 通過屬性信息計算出節點之間相似度來約束節點的表征
我們提出了一種新穎的無監督節點表征學習框架ANRL
?（1） 該框架充分利用了節點與其鄰居節點信息的相關性和節點屬性信息與其上下文信 息的相關性來學習節點的表征
?（2） 在建模節點屬性信息的時候將節點的結構信息融入進來；反之亦然，在建模節點 結構信息時也巧妙地將節點的屬性信息融入了進來
?（3） 設計了鄰居增強型自編碼器和屬性感知的Skip-gram模塊
?（4） 在6個數據集上進行了鏈接預測和節點分類實驗，驗證了模型的有效性
主要由以前兩個模塊構成：
鄰居增強型自編碼器模塊
?（1） 使用簡單的多層感知器來對節點的屬性信息進行編碼和解碼
（2）優化的損失函數
（3） 目標鄰居節點計算過程
a. 加權平均鄰居
b. 元素中值鄰居
（1） 建模節點屬性信息的同時捕獲到節點的局部結構信息
（2） 重構節點的目標鄰居節點屬性信息，而不是節點自己的屬性信息
左圖中，節點3和5之間雖然沒有邊相連接，但我們可以看出他們共享了許多鄰居節點，因此這兩個節點是有相似性的。
在重構的時候，如果兩個節點具有相同的鄰居節點，那么他們重構之后編碼的表征也會比較相似。
屬性感知的Skip-gram模塊
?（1） 采用隨機游走對圖結構進行線性化操作，對抽樣出的節點序列進行建模
?（2） 具有相似上下文的節點在語義空間中也相似
?（3） 利用Skip-gram建模結構信息的同時融入節點的屬性信息
模型整體框架優化
整個模型框架，輸入先經過一個編碼器模塊，這個模塊有兩個分支：左邊是解碼器模塊，右邊是一個預測context信息的過程；共享編碼器模塊參數，在優化的過程中交替更新彼此的損失函數，以達到整體框架的優化。
數據集統計信息
鏈接預測任務
我們從上圖可以看出，我們的模型相對現有模型是有評價指標提升的。
節點分類任務
（1） 僅使用節點屬性信息（SVM）
（2） 僅使用圖結構信息 （DeepWalk等）
（3）同時使用屬性和結構信息
（4） ANRL模型變體
ANRL模型總結
（1） 屬性圖中的無監督表征學習框架
（2） 深度融合了圖的結構信息和節點的屬性信息
（3） 在6個數據集上進行了鏈接預測和節點分類實驗，驗證了模型的有效性
存在的問題
（1） 該模型僅局限于節點帶屬性信息的靜態圖數據
（2） 隨著時間的推移，圖數據中會有新的節點加入以及生成新的連邊，因此如何對動 態圖建模并捕獲其時序信息？
（3） 很多應用往往涉及到包含多種類型節點的異構圖，例如推薦系統中的``用戶-商品 "交互信息就可以構建成一個異構二部圖，那么如何捕獲異構圖中不同節點的語 義信息
時序異構圖中節點級表征學習
現有的大部分表征學習工作僅僅關注于靜態的同構圖
時序異構圖建模的是不同類型節點之間的時序交互信息，它是一種更加復雜、通用 的數據結構
給定圖G =（U,V,E,T)?其中|U|,|V|代表圖中兩類異構節點的個數，E表示的是圖中兩 類節點之間的交互信息,T表示的是圖中節點交互的時間信息
復雜的圖結構不是一蹴而就形成的
特定時間段內節點交互信息累積的結果
為了降低建模難度，只考慮了兩類節點——用戶節點和物品節點
現有研究工作
（1） 將時序圖劃分為一系列離散的子圖，它們由預定義的時間窗口切分而成，然后再 設計相關算法對該子圖序列進行建模
（2） 無法區分異構節點類型
（3） 無法利用邊上的屬性信息
（4） 模型復雜度與子圖個數及大小成正比
我們提出了基于記憶網絡的表征學習框架TigeCMN
?（1） 該框架利用記憶網絡進行寫入和讀取操作以增強其跟蹤動態信息的能力
?（2） 為每個節點都引入了記憶矩陣來維護其時序交互信息而不是簡單的將其多面性的 交互信息壓縮到單個潛在向量中
?（3） 當模型進行推理時, 基于自注意力機制來動態的讀取記憶矩陣中的相關信息
?（4） 在5個常用公開數據集上進行了三類實驗包括節點分類、時序推薦以及可視化， 實驗結果表明TigeCMN優于一系列的對比算法
TigeCMN整體架構圖
我們由上圖可以看到，當用戶發生交互行為之后，我們便可以通過這個交互信息來進行建模，更新用戶節點和物品節點之間的一個表征。
（1） 邊特征編碼模塊（將用戶前后交互行為的時間差引入）
a. 該編碼模塊可以根據輸入的數據類型進行針對性的設計
b. 為簡單起見，我們使用基于dropout模式的多層前向傳播網絡來對邊特征信息進行編碼
c. 將邊屬性信息，商品表征向量以及距離上次交互的時間間隔拼接后作為輸入
（2） 記憶網絡動態寫模塊
a. 根據權重信息進行擦除以及添加操作
主要分為兩部分：一部分為擦除信息。一部分為擦除后補充新信息
?（1） 記憶網絡動態讀模塊
a. 根據自注意力機制從記憶矩陣中動態的讀取信息
Q=Mut ·?WQ， K=Mut ·?WK， V=Mut ·?WV
數據集統計信息
節點分類任務
Top-N推薦任務
表征可視化
可以看出圖(f)中，我們的模型比其他的分散程度更高，說明我們學習到了還不錯的表征。
TigeCMN模型總結
?（1） 時序異構圖中的節點表征學習框架
?（2） 利用讀寫操作顯示的存儲、更新節點表征
?（3） 在節點分類、Top-N推薦等任務中展現出有效性
存在的問題
?（1） 時序異構二部圖僅僅涉及到兩種類型的節點
?（2） 設計一些自適應采樣策略來促進模型的優化過程
?（3） 如何從節點表征生成整圖級的表征？
多視圖層級圖池化表征學習
場景：計劃進行圖分類
現有的大部分工作僅僅關注于設計有效的圖卷積操作
忽略了圖池化模塊在層級表征學習中的重要性
通過引入池化操作，整個圖結構信息將會逐步縮減為包含層級信息的子圖
給定圖的集合 G = {G1, G2, ?,Gn} 其中Gi=（Vi,Ei,Xi）代表第i個圖，Ai,Ei表示的是圖中節點與邊的信息, 集合中每個圖的節點和邊信息千變萬化。
現有研究工作
（1） 通過對節點聚類進行池化操作
通過對節點采樣進行池化操作
只去保留圖中比較重要的節點，刪掉其他節點；這樣最終，我么能從大圖得到一個小圖，而且不會丟掉太多重要信息
我們提出了一種通用的圖池化框架MVPool
?（1） 根據不同視圖中的上下文信息對節點的重要性進行評估
?（2） 通過注意力機制來促進不同視圖信息之間的融合
?（3） 根據節點的重要性排序來自適應地保留相關節點子集以形成池化后的圖
?（4） 引入了結構學習機制來對每一層池化后的圖結構進行微調
?（5） 在9個常用公開數據集上驗證了模型的有效性，包括節點和整圖的分類、聚類以 及可視化任務
圖神經網絡模型簡介
給定圖G的鄰接矩陣A和節點的表征矩陣H作為輸入，則下一層節點表征的計算過程 如下所示：
其中σ（·）是非線性激活函數，H0=X即節點的初始表征為節點的屬性，A~=A+I是添加自環后的鄰接矩陣，Wk∈Rdk×dk+1是一個可訓練的參數矩。
圖采樣此時產生了問題：什么樣的節點才是重要的節點？在多視圖的情況下，不同視圖下對節點的標準也不一樣。于是我們提出了在不同視圖下計算節點的重要性。
多視圖池化算子
?（1） 視圖一，基于圖結構的度量準則
?（2） 視圖二，基于節點特征的度量準則
（3） 視圖三，基于圖結構和節點特征的度量準
多視圖信息融合
?（1） 由于單個視圖通常會導致評估出現偏差，并且每個視圖的重要性可能會大不相同
?（2）通過促進不同視圖之間的協作來生成更加魯棒的節點排序
節點采樣策略
?（1） 首先根據節點的重要性得分對其進行排序
?（2）然后按照以下方式選擇排名較高的節點子集
每次排序只保留其中最重要的k個節點，其余的節點以及他們之間的連邊都會刪掉，這樣就可以從一個大圖慢慢變成小圖；
不過，也存在可能本來相連的節點因為不斷的抽樣操作而被切斷了聯系，導致會丟失一部分信息。為了解決這個問題，我們設計了下面這個結構學習模塊。
結構學習機制
?（1） 基于采樣的池化操作很有可能會導致高度相關的節點變得彼此無法訪問
?（2） 學習出微調過的圖結構，可以編碼每對節點之間潛在的關系
其中sparsemax用來學習稀疏圖信息，可以使得我們在結構信息上的損失達到最小化。
節點分類模型框架
?（1） 在池化過程中保留了節點的位置信息，然后在上采樣層中使用該位置信息將相應的節點放回它們的原始位置
整個過程類似與一個graph auto encoding，我們首先對輸入的圖數據中節點進行重要性排序，刪除那些不重要的節點；之后在進行結構化的學習，將他們之間可能存在的連接補上。緊接著是類似的解碼過程，也有類似的標簽幫助我們訓練。
整圖分類模型框架
?（1） 設計了一個簡單的讀出函數，它匯總了各層網絡中所有節點的表征
數據集統計信息
?（1） 節點分類數據集信息
（2） 圖分類數據集信息
實驗結果
?（1） 節點分類實驗結果
?（2） 圖分類實驗結果
可視化實驗結果
我們可以看到，池化操作的模型效果更佳。
MVPool模型總結
?（1） 它是一種通用的圖池化框架
?（2） 通過多視圖的方式充分利用圖結構信息以及節點屬性信息
?（3） 提出了結構學習機制來微調池化后的圖結構信息
?（4） 在9個公開數據集上驗證了模型的有效性
存在的問題
?（1） 是否可以設計出無參數的圖池化算子？
?（2） 如何在一對圖數據上進行推理和建模來捕獲其相似度信息？
目前模型僅用于單個圖，是否可以用于更加復雜的圖推理呢？
圖相似度學習
現有大部分工作研究的是單個圖數據上的有效節點表征或者整圖級別的表征
?（1） 該類模型不能很好的解決圖相似度計算問題
?（2） 因為它需要在一對圖結構數據上進行推理和建模
給定一組圖數據對作為輸入 其中每個圖的節點和邊的數量可以是任意的。我們的目標是利用圖神經網絡端到端的學習出 任意一對圖數據之間的相似性，主要研究了兩類基于圖相似度的問題：graph-graph classification和graph-graph regression任務
現有研究工作
?（1） 傳統圖相似度計算方法如A* ，Beam等時間復雜度高
?（2） 很少有模型嘗試用GNN來探索圖相似度學習
?（3） 基于節點匹配的模型無法很好地捕獲其子圖的結構信息
我們提出了一種新穎的圖相似度學習框架H2MN
?（1） 在圖相似度學習的過程中充分考慮兩個圖之間的子圖匹配信息
?（2） 將子圖的匹配問題轉換為超圖之間超邊的匹配問題
?（3） 首次提出了提出了基于超邊的池化算子
?（4） 在5個常用公開數據集上驗證了模型的有效性，包括圖的分類以及回歸任務
超圖構造模塊
?（1） 超圖可以定義為H=（V,ε,X,W）由節點集、超邊集、節點特征矩陣以及邊權對 角矩陣組成；每條超邊可以包含兩個或者更多節點，關聯矩陣H定義如下：(超圖中1條邊可以包含兩個以上的節點）
（2） 超圖構建
a. 隨機游走：將采樣得到的節點序列作為超邊
b. K階鄰居：根據節點的K階鄰居來構建超邊
超圖卷積神經網絡
?（1） 超圖神經網絡（或HGNN）是建模高階節點關系而非成對關系的通用框架
?（2） 以超圖關聯矩陣H和節點表征矩陣X作為輸入：
其中σ（·）是非線性激活函數，Dv，De，W分別表示的是節點的度對角矩陣、超邊的度對角矩陣以及超邊權重矩陣，∈Rdl×dl+1是一個可訓練的參數矩陣。
超邊池化算子
?（1） 圖相似度學習任務中只有有限數量的關鍵子結構在子圖匹配過程中起著重要作用
?（2） 根據重要性保留排名較高的超邊
子圖匹配模塊
?（1） 子圖匹配機制的主要步驟是計算超圖中超邊之間的注意力系數
（2） 對于Hi中每條超邊e1i，計算它與H2中所有超邊的余弦相似度
?（3） 利用這些注意力系數來計算H2基于e1i的全局表征
（4） 多角度匹配函數
模型整體框架
首先我們輸入兩個圖數據對，然后會根據之前定義的兩種方式去生成兩個超圖神經網絡。緊接著我們會去進行池化操作，僅僅保留圖中比較重要的一些信息，再去對這兩個信息進行匹配計算相似度。實際上是對超邊進行匹配，因為超邊其實融合了子圖的信息。子圖之間的比較，因為子圖數量少，建模比較省時；同時子圖之間的匹配，能幫助我們更好的捕獲圖的子結構信息且能更好的計算相似度。
通過類似更新操作之后，我們便能生成一些新的表征。通過不同層次的疊加就能得到一個整圖的表征。兩個圖的表征拼接之后，最后去計算得到他們相似度的信息。
數據集統計信息
Graph-Graph分類任務
現有的幾個做圖相似度計算的模型：
1）我們的模型取得了一定效果的提升
2）圖大小對模型效果的影響：我們的模型比較穩定
Graph-Graph回歸任務
回歸任務：
1）采用A*作為ground truth：可以看到相應的mse為0
2）ρ為全局排序指標
3）p@10為Top k排序指標
圖相似度檢索任務
H2MN模型總結
?（1） 將普通圖轉換為超圖以進行子圖匹配
?（2） 通過執行超圖卷積、超邊池化和多視角子圖匹配等一系列操作來捕獲圖數據對之 間的語義相似性
?（3） 在5個公開數據集上驗證了模型的有效性
存在的問題
?（1） 動態構建超圖子結構信息
?（2） 對異構的知識圖譜進行建模，需要一對一的匹配兩個知識圖譜中共同的實體
03
總結與展望
本文主要從四個不同的粒度對圖表征學習展開了研究，具體包括：
?（1） 屬性圖中節點級表征學習
?（2） 時序異構圖中節點級表征學習
?（3） 多視圖層級圖池化表征學習（節點&整圖）
?（4） 圖相似度學習
重點對不同粒度復雜圖數據以及挖掘任務進行了探索，提出了一系列基于神經網絡 的圖表征學習模型，研究了圖數據中知識的表征、融合以及推理
未來研究計劃
?（1） 在知識圖譜中利用神經網絡進行推理
a. 將模型擴展到跨語言知識圖譜對齊任務中
?（2） 將強化學習融入到圖神經網絡中
a. 通過強化學習模型來確定每層池化操作需要抽樣的節點個數
?（3）設計自監督模型對圖神經網絡進行預訓練
a. 如何在結構化圖數據中設計自監督任務？
論文鏈接：
https://b23.tv/EWBsPTa
點擊“閱讀原文”，即可觀看本場回放
整理：林則
審核：張震
直播預告
3月9日? 14:00-17:40? ?NeurIPS專場六
11位華人學者帶來分享
記得關注直播信息哦！
3月9日? 19:30-20:30? ?青年科學家-23
參數高效遷移學習
期待馬學喆老師為大家帶來精彩分享～
往期精彩文章推薦
記得關注我們呀！每天都有新知識！
?關于AI TIME?
2019年，清華大學人工智能研究院院長張鈸院士、唐杰教授和李涓子教授等人聯合發起“AI TIME science debate”，希望用辯論的形式，探討人工智能和人類未來之間的矛盾，探索人工智能領域的未來。
AI TIME是清華大學計算機系一群關注人工智能發展，并有思想情懷的青年學者創辦的圈子。AI TIME旨在發揚科學思辨精神，邀請各界人士對人工智能理論、算法、場景、應用的本質問題進行探索，加強思想碰撞，鏈接全球AI學者、行業專家與愛好者，打造成為全球AI交流與知識分享的聚集地。
我知道你
在看
哦
~
點擊 閱讀原文?查看回放！
總結
以上是生活随笔為你收集整理的干货！基于神经网络的多粒度图表征学习的全部內容，希望文章能夠幫你解決所遇到的問題。
