基于圖框架變換的動態圖神經網絡模型

楊圣鵬, 施建棟, 周斯煒, 李 明

(1.浙江師范大學 計算機科學與技術學院,浙江 金華 321004;2.浙江師范大學 浙江省智能教育技術與應用重點實驗室,浙江 金華 321004)

0 引 言

自基于深度學習的數據分析方法在學術界取得系列成果以來,已經有大量的模型應用深度學習技術對各類數據進行分析和處理,并在多個領域取得了廣泛的應用.然而,目前大部分的模型僅適用于處理歐氏空間的網格型數據.Kipf等[1]指出,由于非歐結構的圖數據不具備歐氏空間中的規則性和均勻性,所以傳統的卷積操作無法直接應用于圖數據的特征提取;Bruna等[2]指出,由于圖數據的頻譜特性和傳統信號處理中的頻譜特性存在差異,所以歐氏空間中的頻域處理方法也無法直接應用于非歐結構的圖數據;Hamilton等[3]也明確了由于非歐結構的圖數據具有復雜的連接關系和異構節點屬性,傳統的特征聚合方法無法充分捕捉到圖數據的全局結構和節點之間的復雜交互.而在數據表現形式繁多的大數據時代,非歐結構圖數據的應用背景又非常廣泛.例如,在社交網絡分析領域,通過分析社交網絡中的節點和邊的連接模式,可以揭示社會關系、社交影響力、社區發現等信息,從而實現更精準的個性化推薦和媒體營銷[4].在交通網絡規劃中,通過分析交通網絡中節點和邊的連接關系,可以進行路徑規劃、交通流量預測等工作,有助于改善交通運輸系統[5].此外,圖數據還在知識圖譜、網絡安全、推薦系統等領域得到了廣泛的應用,通過構建和分析圖數據,能夠從復雜的關系中發現隱藏的模式和知識,從而實現智能搜索、語義理解、智能推薦等功能[6].歐氏空間網格型數據與非歐空間圖結構數據特征如圖1所示.

(a)歐氏空間網格型數據 (b)非歐空間圖結構數據

動態圖是非歐空間圖結構數據中一類特殊的數據形式,具有豐富的時間和空間演變特征.在以往的研究中,Wang等[7]提出了通過聚合鄰居節點特征來更新中心節點表示的動態圖卷積模型,并與傳統的靜態圖卷積模型在分類任務和分割任務上進行了實驗對比,發現用圖卷積網絡等靜態圖模型對動態圖進行表示學習會導致信息丟失,使實驗結果變差;Manessi等[8]在靜態圖中引入時間維度,將靜態圖擴展為動態圖并提出了用鄰居節點信息和時間維度的變化更新節點特征的動態圖卷積模型,分別完成了圖分類和圖預測任務,發現靜態圖卷積模型無法處理動態圖數據中節點的新增、刪除和連接關系的變化,無法直接對動態圖數據的時空演變進行建模;Pareja等[9]提出了將RNN[10]和GCN[11]結合使用的動態圖表示學習方法,并指出因為靜態圖模型無法自適應地學習圖結構和特征隨時間變化時的演變特征,所以靜態圖表示學習方法在動態圖中并不適用.因此,動態圖表示學習領域吸引了眾多研究者的關注,提出了各種方法來處理這種動態圖數據.例如,Sankar等[12]在動態圖表示學習中引入注意力機制,構建不同時間下圖演變的時間和空間信息;Liu等[13]在RNN[10]和GCN[11]之中引入Z核結構,進一步考慮了動態圖單個時間戳中的同一局部不同細粒度的相似信息,提高了后續任務的效果;Yu等[14]通過深層自編碼器和圖距離游走方式對動態圖進行重新編碼,實時更新節點狀態并進行圖聚類分析;Liu等[15]綜合考慮動態圖神經網絡在同一時刻的全局信息、局部信息和動態演變信息,在多個動態圖異常檢測基準數據集上取得了最佳效果.

基于上述處理歐氏結構的特征提取方式并不適用于非歐結構,且靜態圖表示學習模型也無法準確捕獲動態圖中的時空演變特征的論述,本文提出一種針對動態圖表示學習的模型,主要創新和貢獻總結如下：

1)將動態圖表示學習與非歐空間圖框架理論結合起來,提出了一種基于圖變換框架的動態圖神經網絡模型,進一步拓展基于譜方法的動態圖表示學習技術;

2)通過兼顧低通濾波器和高通濾波器,所提模型能夠有效地挖掘動態圖的低頻、高頻信息及其演變模式,提升了動態圖神經網絡的表達能力;

3)所提模型在3個動態圖公共基準數據集上的精度優于已有動態圖表示學習算法,驗證了基于圖框架變換的動態圖神經網絡模型的潛在優勢.

1 動態圖與動態圖表示學習的定義

1.1 動態圖

根據數據的時序處理角度可以把動態圖劃分為兩大類：一類是在固定的時間戳中記錄圖數據,稱為離散動態圖,如圖2(a)所示;另一類是記錄連續時間下的圖數據,稱為連續動態圖,如圖2(b)所示.

(a)離散動態圖 (b)連續動態圖

本文基于離散動態圖結構,根據離散動態圖中頂點和邊的動態特性進一步把它劃分為如下3類圖形.

第1類：圖3表示帶有動態特征的靜態圖結構,它是圖矩陣G和節點特征矩陣X的有序集合D={(G,X1),(G,X2),…,(G,XT)},其中節點特征矩陣滿足Xt∈R|V|×d,?t∈{1,2,…,T}為時間序列中單個時間戳,V={v1,v2,v3,…},vi(i=1,2,…)為節點,|V|表示節點數量,d表示特征維度.即在該類動態圖中,節點特征隨著時間的流逝而發生改變,圖形的結構在各個時刻中均不發生改變.

圖3 特征演變的動態圖結構

第2類：圖4表示帶有靜態特征的動態圖結構,它是圖矩陣和節點特征矩陣的有序集合D={(G1,X),(G2,X),…,(GT,X)},其中Gt為t時刻的圖矩陣,節點集合滿足Vt=V,?t∈{1,2,…,T},節點特征矩陣滿足X∈R|V|×d.即在該類動態圖中,節點特征在各個時刻中均不發生改變,圖形的結構隨著時間的流逝而發生改變.

圖4 圖結構演變的動態圖

第3類：圖5表示帶有動態特征的動態圖結構,它是圖矩陣和節點特征矩陣的有序集合D={(G1,X1),(G2,X2),…,(GT,XT)},其中節點集合滿足Vt=V,?t∈{1,2,…,T},節點特征矩陣滿足Xt∈R|V|×d,?t∈{1,2,…,T}.即在該類動態圖中,節點特征和圖形結構在不同時刻均發生改變.

圖5 特征及結構同時演變的動態圖

1.2 動態圖表示學習

動態圖表示學習是指從動態圖數據中學習節點和邊嵌入的任務.給定動態圖=(V,E,T)作為模型輸入,其中E表示邊集合,然后用神經網絡的方法設計一個函數F表示可以映射節點和邊特征的模型,使得在具體的時間戳t下,動態圖中每個節點v∈V和邊e∈E,有hv(t)=F(v,t),he(t)=F(e,t)分別對節點v和邊e進行嵌入,旨在捕捉動態圖中節點和邊在時空演變過程中的關聯性和變化模式,為后續的圖分析、預測和推薦等任務提供有意義的指導.

2 基于圖框架變換的動態圖神經網絡模型

目前大部分的圖神經網絡都是基于空間建模的,如GCN[11],GAT[16]等,這些方法通過空間消息傳遞的方式計算鄰居節點的信息,并通過圖卷積技術將源節點和目標節點的信息匯聚整合,經過多層網絡堆疊訓練,最終實現全圖特征學習.然而,這些基于空域建模的方法存在一些局限性,淺層圖卷積技術無法有效傳播節點標簽,而深層圖卷積堆疊會導致特征過度平滑,難以區分不同類別的節點[6,11].另一種建模方法是通過傅里葉變換把信號傳入譜域,先將空域信號投影到傅里葉基上,以此確定信號在譜圖中的幅值大小,進行系列操作后再通過逆傅里葉變換無差別地將信號傳回空域,這種基于譜域的數據分析和建模方法對于頻率隨著時間發生改變的非平穩信號有著很大的局限性[17].

為了彌補基于空域和譜域建模的缺陷,考慮到小波變換比較適用于處理非平穩過程的信號特點,決定引入小波變換.在現有的研究中,Xu等[18]在傳統的圖卷積神經網絡基礎上引入了小波變換,在不同的頻率尺度上提取圖結構和特征信息,從而實現更全面的圖表示學習,但模型整體結構注重局部鄰域的信息,對全局圖結構表示相對較弱,這導致在一些全局性圖任務學習或者具有長程依賴關系的圖數據上性能受限.Zheng等[19]提出了用小波圖框架來增強圖神經網絡的性能,將信號分解為不同的頻域子空間來更好地表示信號的細節和整體特征,從而提高圖神經網絡對于圖結構的特征提取能力,該模型只考慮了靜態圖結構,并沒有進一步將小波變換用于動態圖結構中.本文受此啟發,首先將空域信號投影到小波基上,然后對低頻信號和高頻信號有區分地進行濾波操作,并在譜空間設計激活函數進行信號壓縮和去噪,從而構建了一個針對動態圖信號提取的譜域卷積模型,再用整個卷積模塊替換長短期記憶神經網絡中的乘積操作,利用長短期神經網絡能夠學習數據中長程依賴關系的特性,捕捉動態圖的演變特征,構建了基于圖卷積框架變換的動態圖神經網絡模型,即dynamic graph neural network model based on graph frameles transform(GFTLSTM),模型結構如圖6所示.

2.1 基于圖框架變換的多尺度圖卷積

2.1.1 動態圖信號轉換

圖6 基于圖框架變換的動態圖神經網絡模型框架示意圖

(1)

(2)

由于深度學習訓練的數據是張量形式,所以式(1)和式(2)在具體實現時將傅里葉變換替換成小波變換后,對于圖信號s的轉換可以通過信號分解矩陣Wr,j(r=0,1,…,n)和信號重構矩陣Br,j來執行[19].由信號分解矩陣可以構成一個長度為nJ+1的矩陣集合Q,如式(3) 所示[20].

Q={Wr,j|r=1,2,…,m;j=1,2,…,J}∪{W0,J}.

(3)

2.1.2 多尺度圖卷積

綜合上述動態圖信號轉換知識,為了更好地捕獲動態圖演變特征,本文將t-1時刻的隱狀態矩陣ht-1與當前時刻的輸入特征矩陣Xt作為卷積模型的輸入特征,卷積計算過程如式(4)和式(5)所示.

(4)

(5)

Ss(x)=sgn(x)(|x|-δ)+;

(6)

Sh(x)=x(|x|-δ).

(7)

式(6)和式(7)中：Ss和Sh分別為Shrinkage-soft和Shrinkage-hard信號壓縮函數;sgn()為符號函數;x為輸入特征;δ作為一個門限值,可以控制信號分量值,進一步壓縮信號.

2.2 長短期記憶網絡(LSTM)

長短期記憶網絡(long short-term memory networks,LSTM)是循環神經網絡中的一種,主要用于解決長序列訓練過程中的梯度消失和梯度爆炸問題[21].本文將圖卷積操作與長短期記憶神經網絡相融合,將長短期記憶網絡中輸入矩陣Xt與上一時刻的外部狀態ht-1同權重矩陣Aξ,Uξ(ξ∈{i,f,c,o})的乘積操作替換成基于圖框架變換的多尺度圖卷積.具體處理過程如式(8)所示.

(8)

式(8)中：*表示基于圖框架變換的多尺度卷積操作;bξ表示偏置矩陣;mρ(ρ∈{i,f,o})表示對角矩陣;ct-1表示上一時刻的內部狀態,記錄了時序中到上一時刻為止的所有歷史信息;輸入門it的作用是對當前輸入數據進行選擇性記憶,減少不重要信息的輸入;遺忘門ft的作用是選擇性地忘記上一時刻的內部狀態信息,刪除不重要的信息;ct表示當前時刻的內部狀態,用于更新需要保留的信息;輸出門ot的作用是控制當前時刻的內部狀態ct有多少信息需要輸出給外部狀態ht.

3 實 驗

3.1 數據集簡介

1)Chickenpox Hungary[22]

匈牙利官方報告的2005—2015年匈牙利每周水痘病例動態圖數據集,節點是縣城,邊表示縣城之間的鄰接關系,預測目標是下一周的患病數量.

2)Pedal Me London[22]

一個描述2020—2021年倫敦貨運自行車物流公司每周交付訂單量的動態圖數據集,節點是地理位置單元,邊描述的是節點的空間連接關系,預測目標是下一周的交貨數量.

3)Wikipedia Math[22]

一個描述2019年3月到2020年3月用戶每天訪問維基百科次數的動態圖數據集,是一個有向加權的動態圖,節點是維基百科中關于數學話題的頁面,邊的權重表示在源維基百科鏈接到目標維基百科的數量,預測目標是下一天的頁面訪問量.

3.2 實驗設置

實驗在3個動態圖數據集上采用如下2種不同的訓練方式：

1)Incremental：動態圖中的每個時序快照都會更新損失和訓練權重.

2)Cumulative：動態圖中的每個時序快照中的損失會被累積后再進行反向傳播.

在Incremental訓練方式上,采用Shrinkage-hard函數,硬性閾值特性能夠將較小的權重壓縮為0,減少舊數據的影響,使得模型更快地適應新的動態圖變化;在Cumulative訓練方式上,采用Shrinkage-soft函數,軟閾值特性可以對權重進行平滑收縮,減少權重的幅度,但不將其直接壓縮為0,有助于保留歷史數據信息,綜合考慮整個動態圖的演變關聯特征.本文模型中的超參數設置見表1.

表1 模型超參數

3.3 評估指標

第1個評估指標是均方誤差(MSE),是指樣本估計值與樣本真實值之差平方的期望值.

(9)

式(9)中：Ly為樣本均方誤差;yi表示真實的樣本值;o={o1,o2,…,oN}表示模型輸出值.

第2個指標是標準差,是用來度量一組數據平均值分散程度的指標,可以反映數據的準確程度.一個較大的標準差,代表大部分數值和其平均值之間差異較大,反之,代表這些數值接近平均值.

(10)

3.4 實驗結果與討論

本文實驗的對比數據和對比模型均引自文獻[22],以監督學習的方式,把動態圖數據集按時序輸入模型中,然后輸出下一時刻的預測結果.每一個數據集在2種不同的訓練方式下重復10次實驗,縱向比較其他模型的預測結果,引入均方誤差來評價模型的性能并計算標準差用于輔助驗證,實驗結果見表2.

從表2數據可見,本文提出的GFTLSTM模型在譜域使用Shrinkage作為激活函數后,無論是以Incremental還是Cumulative方式進行訓練,在處理離散動態圖數據時優于大多數對比模型,這表明本文模型確實可以較好地捕獲動態圖的內部演化和關聯特征,為動態圖表示學習提供進一步參考.然而,在Wikipedia Math數據集中,以Incremental為訓練方式的實驗結果雖然優于絕大多數模型,但并未達到SOTA效果,相比之下,以Cumulative方式進行訓練時,實驗結果遠超其他縱向對比模型.造成這個現象主要有2個原因.首先,Incremental方法是一種基于增量學習的方式,按照時間順序逐漸添加新的動態圖快照進行訓練,能夠及時捕獲圖數據的演變特征,適用于實時數據的變化,側重捕捉數據的動態特性;而Cumulative方法是一種累積式學習方法,將所有動態圖快照同時輸入模型進行訓練,能夠綜合考慮整個動態圖的演變歷史,捕捉更全面的動態圖特征,側重捕捉數據的關聯關系.由于本文模型在譜域進行低通和高通濾波后,會在空域進行再次整合,并使用長短期記憶網絡來捕捉數據中的長程依賴關系,與Cumulative訓練方式更契合,這同時也解釋了為什么在Chickenpox Hungary和Pedal Me London數據集中,以Cumulative訓練方式得到的實驗結果優于Incremental訓練結果的原因.其次,Wikpedia Math數據集規模龐大,包含大量的節點和邊連接關系,因此,在Incremental學習過程中需要處理更大規模的動態數據,每個時序快照中的損失和參數都需要更新,這增加了計算復雜性,加大了模型訓練時間和擬合難度,對模型提出了更高的要求.

表2 算法比較(均方誤差±標準差)

3.5 消融實驗及激活函數對比研究

為了驗證本文模型在譜域空間中引入Shrinkage函數取代空域激活函數ReLU的有效性,進行消融實驗.在實驗中,本文將去除函數Shrinkage后的模型標記為GFTLSTM-S.同時,為了進一步驗證模型在譜域空間使用多頻分析的有效性,在空域中引入了ReLU激活函數,并去除了譜域Shrinkage函數,將該類模型標記為GFTLSTMR.重復進行10次試驗,具體的實驗結果見表3.

表3 消融實驗及激活函數對比實驗(均方誤差±標準差)

根據表3的結果,在譜域空間去除Shrinkage函數后,通過與表2中的GFTLSTM模型相比,實驗結果的均方誤差和標準差均有不同程度的提升,這表明模型的性能下降了,驗證了引入Shrinkage函數對模型的作用.此外,GFTLSTMR在均方誤差或標準差指標上數值都有一定程度的提升,說明實驗結果再次變差.因此,在處理離散動態圖數據集時,在譜域空間中使用Shrinkage函數來代替ReLU作為激活函數得到的效果更好,這驗證了用Shrinkage函數在多頻分析中進行信號壓縮的價值.

3.6 超參數敏感性實驗分析

通過超參數敏感性實驗分析可以系統地評估不同超參數對模型性能的影響,從而找到最優的超參數組合.本文模型中的超參數δ用來控制信號壓縮的程度,原始信號中大于該閾值的數值才會被輸入模型中進行訓練;另一個超參數r表示譜域空間中高通濾波器的數量,它與信號刻畫程度j共同作用,不同的選擇會改變輸入特征的維度.

在超參數δ敏感性分析實驗過程中,取r=2,設置不同閾值δ后得到的均方誤差如表4所示.

表4 超參數δ敏感性分析實驗

在超參數r敏感性分析實驗過程中,取δ=1e-4,設置不同高階濾波器數量r后得到的均方誤差如表5所示.

表5 超參數r敏感性分析實驗

如表4和表5所示,加粗的數值表示不同超參數取值中得到的最優結果.可見在上述2個超參數敏感性實驗中,在給定的實驗條件下,結果呈現一定的波動,沒有明確的最優解,這可能是受到數據集大小、模型的復雜性以及超參數之間的相互影響等因素導致的.在實際應用中,根據具體任務和需求進行超參數的調整更為重要,而不是過于追求單一的最佳設置.

4 結 語

本文提出了一個動態圖表示學習的通用框架,初次嘗試將小波分析理論、多頻分析與動態圖表示學習相結合,并在多個動態圖數據集上驗證了模型的有效性.在未來的工作中,將嘗試把模型用于圖結構演變的動態圖、特征及結構同時演變的動態圖及連續動態圖中,并結合具體的應用場景,進一步驗證模型在不同動態圖表示學習任務中的通用性.