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

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

0 引 言

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

(a)歐氏空間網(wǎng)格型數(shù)據(jù) (b)非歐空間圖結構數(shù)據(jù)

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

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

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

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

3)所提模型在3個動態(tài)圖公共基準數(shù)據(jù)集上的精度優(yōu)于已有動態(tài)圖表示學習算法,驗證了基于圖框架變換的動態(tài)圖神經(jīng)網(wǎng)絡模型的潛在優(yōu)勢.

1 動態(tài)圖與動態(tài)圖表示學習的定義

1.1 動態(tài)圖

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

(a)離散動態(tài)圖 (b)連續(xù)動態(tài)圖

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

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

圖3 特征演變的動態(tài)圖結構

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

圖4 圖結構演變的動態(tài)圖

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

圖5 特征及結構同時演變的動態(tài)圖

1.2 動態(tài)圖表示學習

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

2 基于圖框架變換的動態(tài)圖神經(jīng)網(wǎng)絡模型

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

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

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

2.1.1 動態(tài)圖信號轉換

圖6 基于圖框架變換的動態(tài)圖神經(jīng)網(wǎng)絡模型框架示意圖

(1)

(2)

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

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

(3)

2.1.2 多尺度圖卷積

綜合上述動態(tài)圖信號轉換知識,為了更好地捕獲動態(tài)圖演變特征,本文將t-1時刻的隱狀態(tài)矩陣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信號壓縮函數(shù);sgn()為符號函數(shù);x為輸入特征;δ作為一個門限值,可以控制信號分量值,進一步壓縮信號.

2.2 長短期記憶網(wǎng)絡(LSTM)

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

(8)

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

3 實 驗

3.1 數(shù)據(jù)集簡介

1)Chickenpox Hungary[22]

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

2)Pedal Me London[22]

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

3)Wikipedia Math[22]

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

3.2 實驗設置

實驗在3個動態(tài)圖數(shù)據(jù)集上采用如下2種不同的訓練方式：

1)Incremental：動態(tài)圖中的每個時序快照都會更新?lián)p失和訓練權重.

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

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

表1 模型超參數(shù)

3.3 評估指標

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

(9)

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

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

(10)

3.4 實驗結果與討論

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

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

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

3.5 消融實驗及激活函數(shù)對比研究

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

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

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

3.6 超參數(shù)敏感性實驗分析

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

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

表4 超參數(shù)δ敏感性分析實驗

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

表5 超參數(shù)r敏感性分析實驗

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

4 結 語

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