基于圖濾波器的符號屬性圖鏈路關(guān)系預(yù)測算法

馬 華,姜 偉,陳 明,鐘世杰

(湖南師范大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長沙 410081)

0 引 言

帶屬性的符號網(wǎng)絡(luò)(或稱符號屬性圖)是指節(jié)點含有屬性信息,且邊權(quán)帶正、負符號的一類網(wǎng)絡(luò)。鏈路與符號預(yù)測是這類網(wǎng)絡(luò)上的熱點問題,在許多領(lǐng)域中均有應(yīng)用,如在醫(yī)學(xué)領(lǐng)域中的藥物互作用關(guān)系預(yù)測、蛋白質(zhì)復(fù)合物檢測。圖神經(jīng)網(wǎng)絡(luò)(graph neural network,GNN)與圖信號處理(graph signal processing,GSP)是當前流行的圖數(shù)據(jù)挖掘技術(shù)。傳統(tǒng)的非圖深度學(xué)習(xí)方法,例如,隨機游走、張量分解、標簽傳播和符號譜嵌入(signed spectral embedding,SSE)等,與GNN與GSP相比,GNN與GSP具備充分的整合圖結(jié)構(gòu)和節(jié)點特征的強大能力[1]。GNN具有端對端的學(xué)習(xí)框架、隨機梯度優(yōu)化等集成優(yōu)化器和API庫等優(yōu)勢,加速了其在圖數(shù)據(jù)挖掘中的成功[2]。GSP將節(jié)點信息視為圖上的信號,利用圖論和信號處理理論,融合圖結(jié)構(gòu)對信號進行變換與分析[3]。典型的圖卷積網(wǎng)絡(luò)[4](graph convolutional networks,GCN)可以解釋為GSP和卷積網(wǎng)絡(luò)的結(jié)合體。GSP的迅速發(fā)展,為GNN這類深度學(xué)習(xí)技術(shù)提供了強大的理論支撐。

這些技術(shù)在符號圖上有相應(yīng)的延伸,如符號圖卷積網(wǎng)絡(luò)[5](signed graph convolutional networks,SGCN)及在基礎(chǔ)上改進的符號圖注意網(wǎng)絡(luò)[6](signed graph attention networks,SiGAT)、符號圖擴散網(wǎng)絡(luò)[7](signed graph diffusion network,SGDNET)等[8]。但是,它們大多是GNN與社會平衡理論結(jié)合的產(chǎn)物,用于解決符號圖上節(jié)點信息的聚合與傳播問題。平衡性的判斷建立于邊符號的累計奇偶性,其使用場景有限,且并未考慮邊的權(quán)重屬性。這些模型的測試案例通常不存在節(jié)點屬性,因而,不能很好地適用于帶節(jié)點屬性的應(yīng)用場景。事實上,節(jié)點屬性(圖信號)可能是影響形成圖拓撲結(jié)構(gòu)的關(guān)鍵因素。

針對上述問題,該文提出基于圖濾波器的符號屬性圖卷積網(wǎng)絡(luò)模型(graph filtering-based convolutional network for attributed and signed graphs,ASGFCN)用于鏈路符號預(yù)測。首先,提出基于帶通濾波器的符號圖卷積網(wǎng)絡(luò),利用帶通濾波器在譜域上實現(xiàn)符號圖上節(jié)點信息的聚合與傳播,用于獲得基于符號圖拓撲的節(jié)點嵌入。在設(shè)計符號圖濾波器時,同時考慮了低頻與高頻信號,并通過參數(shù)化頻率響應(yīng)函數(shù),提高了模型的自適應(yīng)學(xué)習(xí)能力。其次,考慮到節(jié)點屬性可能是圖拓撲的關(guān)鍵來源,構(gòu)造屬性相似性圖并利用圖卷積網(wǎng)絡(luò)得到另一種節(jié)點表達。最終利用注意力機制融合這兩種表達,將其輸入符號判別器,通過Adam優(yōu)化器訓(xùn)練模型。在多個數(shù)據(jù)集上與基線方法進行的對比分析表明,基于ASGFCN的鏈路預(yù)測算法具有更好的性能,其AUC與F1指標分別比最好的基線方法提升了8.68%與10.04%。

1 符號屬性圖的鏈路關(guān)系預(yù)測問題

用G={V,E,X}表達符號屬性圖,其中,V={v1,v2,…,vn}是由n個節(jié)點組成的集合;E表示邊集,連接節(jié)點vi,vj∈V的邊記為eij,且eij∈{+,-};X∈Rn×d為節(jié)點的特征矩陣,其中n表示特征維度。由邊集E可以得到鄰接矩陣A,矩陣元素Aij表示節(jié)點對vi和vj的帶符號邊權(quán)。

該文考慮以下應(yīng)用場景中的符號圖鏈路或符號預(yù)測問題:藥物相互作用(drug-drug interactions,DDIs)符號預(yù)測與藥物副作用識別預(yù)測。

(1)符號DDIs預(yù)測。已知一批藥物以及它們之間的一些積極或消極關(guān)系,對于關(guān)系未知的藥物對,確定其鏈接關(guān)系。如圖1所示,?∈{+,-,0},正號和負號分別表示兩種藥物組合時的積極或消極作用。

圖1 符號圖上的鏈路關(guān)系預(yù)測問題

(2)藥物副作用識別。已知一批藥物以及它們之間的副作用,對于關(guān)系未知的藥物對,確定藥物節(jié)點之間是否存在副作用,如圖1所示,?∈{-,0}。

2 相關(guān)工作

符號屬性圖上的鏈路預(yù)測方法一般可以分為基于圖深度學(xué)習(xí)的方法和基于非圖深度學(xué)習(xí)的方法。近十年來,符號屬性圖上的鏈路預(yù)測方法主要以非圖深度學(xué)習(xí)方法(特別是譜方法)為主導(dǎo),如符號拉普拉斯矩陣方法[9]及其變式[10]、平衡正則割[11]與SSE[12]和一些其他的方法[13～15]。這些方法通常是二階段式的:首先抽取特征,然后是關(guān)系判別。

與這些淺層模型相比,圖深度學(xué)習(xí)方法構(gòu)建了聯(lián)合求解圖節(jié)點嵌入及下游任務(wù)的端到端學(xué)習(xí)框架,能實現(xiàn)更好的預(yù)測效果。GNNs是當前流行的用于圖結(jié)構(gòu)數(shù)據(jù)分析的深度學(xué)習(xí)方法。該類方法能較好地利用節(jié)點特征與網(wǎng)絡(luò)結(jié)構(gòu),是端到端訓(xùn)練模型,且擁有成熟的訓(xùn)練工具箱[16]。

當前一些GNNs在符號圖上進行了擴展,它多為現(xiàn)有模型與社會平衡理論的結(jié)合。例如,SGCN[5]基于社會平衡理論提出一種新的符號圖節(jié)點嵌入方法,符號圖注意力網(wǎng)絡(luò)[6](signed graph attention network,SiGAT)與基于注意力的符號網(wǎng)絡(luò)嵌入[17](signed network embedding based on attention,SNEA)也是在SGCN基礎(chǔ)上基于平衡理論所提出的方法。另一類模型則通過擴展符號圖GSP理論獲得啟發(fā)。例如,Chen等人提出以基于圖濾波的符號卷積網(wǎng)絡(luò)(signed graph filtering-based convolutional network,SGFCN)來表示藥物[18-19],節(jié)點特征被視為圖信號通過專門的譜濾波器進行傳遞和聚合,該圖濾波器可捕捉藥物對的同配性和異配性。

相較非深度學(xué)習(xí)方法而言,符號圖GNNs方法集成了節(jié)點特征與網(wǎng)絡(luò)結(jié)構(gòu),且是端到端模型,因此對符號圖數(shù)據(jù)的挖掘能力有較大提升。但仍具備一些不足:(1)它們所基于的平衡理論在許多場景中并不適用,且該理論并未考慮邊的權(quán)重屬性。(2)這些模型的測試場景并未考慮到節(jié)點的多通道屬性,對節(jié)點屬性的利用程度有限。事實上,節(jié)點屬性(圖信號)可能是邊的符號屬性的關(guān)鍵性潛在影響因素。

3 基于ASGFCN的符號屬性圖節(jié)點嵌入

針對符號屬性圖上的鏈接預(yù)測任務(wù)所提出的ASGFCN,其整體流程見圖2。分別在符號拓撲圖與屬性相似圖上進行節(jié)點嵌入,引用注意力機制將兩者融合用于下游鏈路預(yù)測。針對符號圖節(jié)點嵌入,設(shè)計了基于帶通濾波器的符號圖神經(jīng)網(wǎng)絡(luò),并討論低高頻的作用。對于節(jié)點屬性,構(gòu)建相似性網(wǎng)絡(luò),利用GCN節(jié)點嵌入。下面分別闡述節(jié)點嵌入過程與鏈路關(guān)系預(yù)測。

圖2 基于圖濾波器的符號圖卷積網(wǎng)絡(luò)

3.1 基于帶通濾波器的符號圖神經(jīng)網(wǎng)絡(luò)

3.1.1 GCN以及其GSP視角

GNN通過多層疊加得到節(jié)點嵌入結(jié)果,每層包含特征轉(zhuǎn)換、消息聚合兩個算子。不同的GNN模型采用不同的聚合操作。

圖G上的消息聚合過程可視為對圖信號的濾波操作。用H表示圖濾波器,y=Hx將定義在n個節(jié)點上的圖信號x∈Rn變換為另一個圖信號。H可通過在整個圖的譜域內(nèi)調(diào)整頻率強度得到。首先,選擇一個圖矩陣進行譜特征分解。設(shè)M∈Rn×n是定義在G上的實對稱半正定矩陣,對其進行分解:M=Udiag(λ1,λ2,…,λn)UT,特征值λi≥0被稱為圖頻率,U={U1,U2,…,Un}包含相應(yīng)的特征向量作為列。在GSP中U用作傅里葉基,將一個頂點域圖信號映射至譜域。UT則用于重建信號。然后,定義以下的圖濾波器:

H=Udiag(h(λ1),…,h(λn))UT

(1)

這里需選擇頻率響應(yīng)函數(shù)h(λ),調(diào)整譜域信號。以GCN為例,每層的計算方法為:

(2)

3.1.2 基于帶通濾波器的符號圖神經(jīng)網(wǎng)絡(luò)

無符號圖的譜域分析已被廣泛用于開發(fā)GNN體系結(jié)構(gòu)。許多眾所周知的GNN,如GCN、適應(yīng)性圖卷積神經(jīng)網(wǎng)絡(luò)[20](adaptive graph convolutional neural networks,AGCN)等,都依賴于譜域分析。這些設(shè)計基于從規(guī)范化無符號圖拉普拉斯特征分解得出的頻率解釋。然而,將現(xiàn)有的譜域GNN設(shè)計直接應(yīng)用于符號圖存在局限性,主要包括:(1)度矩陣中可能的零對角項使得拉普拉斯函數(shù)的規(guī)范化變得不可行。(2)圖拉普拉斯可能出現(xiàn)負特征值,使得頻率排序時難以準確決定將特征值的最小負值、最小正值或最小絕對值視為低頻值。

(3)

無符號圖上較大特征值對應(yīng)的特征向量為高頻信號,在節(jié)點嵌入時也能發(fā)揮作用,用于獲取異質(zhì)關(guān)系所隱含的信息[21]。在后面的實驗中嘗試同時考慮低頻與高頻信號的組合。用以下函數(shù)來表示這種帶通濾波器:

(4)

將節(jié)點原始矩陣X視為廣義圖信號,堆疊兩層GNN得到符號拓撲圖節(jié)點嵌入結(jié)果,計算方法為:

(5)

3.2 基于屬性相似性圖的節(jié)點嵌入

符號屬性圖上的節(jié)點可能具有多樣化屬性,如藥物互作用網(wǎng)絡(luò)上藥物節(jié)點具有蛋白質(zhì)靶標特征與副作用特征等多種屬性。這些節(jié)點屬性是產(chǎn)生鏈接關(guān)系的潛在因素。為了挖掘節(jié)點屬性的潛力,通過計算節(jié)點間的特征相似性來構(gòu)造屬性相似性圖,利用GCN產(chǎn)生一個輔助的節(jié)點嵌入結(jié)果。

首先,采用藥物網(wǎng)絡(luò)中常用的杰卡德系數(shù)產(chǎn)生一個相似性圖,計算節(jié)點i與節(jié)點j間的特征相似性得分Sij。然后,保留閾值μ之上的連邊。最后,對相似性矩陣S采用GCN,堆疊兩層得到無符號的屬性相似圖節(jié)點嵌入結(jié)果,方法如下:

(6)

3.3 基于注意力機制的節(jié)點嵌入融合

對ZA與ZAF進行加權(quán)求和,將兩者融合:

Z=αAZA+αAFZAF

(7)

其中,αA,αAF∈Rn×1為對應(yīng)于ZA和ZAF的注意力系數(shù)。節(jié)點i在ZA的嵌入結(jié)果為ZAi。首先通過一層神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)ZAi初始注意力,然后使用共享的注意力向量q∈Rp×1獲得注意力值WAi,計算方法如下:

WAi=qT?tanh(θATT?(ZAi)T+bA)

上周本刊記者探訪時，新東站還是熱火朝天的施工現(xiàn)場，如今卻已姿態(tài)煥然。從早上七點半開始，新東站南廣場上，行色匆匆的人們總要暫做停留，將“濟南東站”的招牌收入鏡頭中。

(8)

其中,θATT為權(quán)重矩陣,bA為對應(yīng)ZA的偏置向量。同理可得ZAF對應(yīng)節(jié)點i的注意力值WAFi。然后,使用softmax函數(shù)將注意力值WAi和WAFi整合獲得最終權(quán)重,方法如下:

(9)

同理:

αAFi=softmax(WAFi)

(10)

最后,將式(9)與式(10)推廣至任意節(jié)點即得式(7)。

4 基于ASGFCN的鏈路預(yù)測算法

本節(jié)提出了基于ASGFCN的端到端鏈路關(guān)系預(yù)測算法,并將其應(yīng)用于藥物網(wǎng)絡(luò)鏈路預(yù)測問題中。

(11)

其中,θCij表示與連邊類型tij相關(guān)聯(lián)的權(quán)重,如果給定的預(yù)測為真,則(?)返回1,其余則返回0。

對第2節(jié)介紹的兩個預(yù)測問題,T的設(shè)定不同。對DDIs符號預(yù)測任務(wù),使用“0”邊作為負樣本訓(xùn)練模型,T∈{+,-,0}。對第2節(jié)介紹的藥物副作用判別任務(wù),使用“+”邊作為負樣本,T∈{-,0}。所提算法流程如圖3所示。

圖3 算法流程

5 實驗設(shè)計與分析

將所提算法與多個基線進行了對比分析。

5.1 數(shù)據(jù)集

使用了3種數(shù)據(jù)集,如表1所示。數(shù)據(jù)集簡介如下:(1)D-1562。Shi等人[22]從DrugBank V4數(shù)據(jù)庫收集得到。包括180 576個已知的DDIs,其中包含125 298個正鏈接和55 278個負鏈接。連邊的符號是根據(jù)DrugBank數(shù)據(jù)庫中的語義描述來劃分的。藥物自身屬性特征包含藥物結(jié)合蛋白和化學(xué)結(jié)構(gòu)。(2)D-548。藥物副作用數(shù)據(jù)集,由Liu等人[23]收集。它包括548種藥物,只有化學(xué)結(jié)構(gòu)屬性。其中48 584種藥物副作用(負連接)是從TWOSIDES得到的,僅表示兩種藥物間是否存在副作用,其8 299種正連接是通過特征相似性計算得到。(3)D-597。該數(shù)據(jù)集的提取方式與D-1562相同,但來自于DrugBank V5。其原始數(shù)據(jù)包括Wang等人[24]收集的614種小分子藥物。刪除了幾個孤立的無鄰居節(jié)點藥物,得到了包含597個藥物的數(shù)據(jù)集。

表1 實驗使用的數(shù)據(jù)集

5.2 實驗設(shè)置

每次實驗運行都采用5折交叉驗證,所有結(jié)果為5次運行的平均值,并選取兩種常用的評價指標受試者工作特性曲線(AUC)下面積和F1度量,值越大,說明模型性能表現(xiàn)越好。

設(shè)定的基線方法如下:(1)SGCN[5],它是一種基于社會平衡理論的符號圖節(jié)點嵌入方法。(2)SGFCN[18-19],它將藥物關(guān)系網(wǎng)絡(luò)看作是同配圖和異配圖的重疊,節(jié)點特征被當作圖信號通過專門的譜濾波器進行傳遞和聚合。(3)SSE[12],它是用于符號網(wǎng)絡(luò)嵌入問題的基線方法,它將符號網(wǎng)絡(luò)映射到一個由符號圖拉普拉斯特征向量組成的空間中,它僅集成了網(wǎng)絡(luò)結(jié)構(gòu),且是二階段式。(4)A-LHW-C。它是ASGFCN的變體,與ASGFCN相比,它僅利用單通道化學(xué)結(jié)構(gòu)特征構(gòu)成屬性相似性圖。(5)A-L。ASGFCN的變體,它僅考慮低頻信號。(6)A-LH。ASGFCN的變體,它同時考慮低頻與高頻信號。

所有算法都基于PyTorch實現(xiàn),且均使用兩個網(wǎng)絡(luò)層和一個學(xué)習(xí)率為0.01的Adam優(yōu)化器。為了保證帶通濾波器同等考慮低通與高通信號,式(4)的k_l與k_h皆設(shè)為K/2。使用不同的迭代次數(shù)訓(xùn)練模型,發(fā)現(xiàn)迭代1 000次足以獲得良好的結(jié)果。

5.3 實驗結(jié)果和分析

本節(jié)旨在回答四個關(guān)鍵問題:(1)ASGFCN與基線方法對比結(jié)果;(2)高頻信號是否影響模型預(yù)測效果;(3)屬性相似性圖的作用;(4)帶通濾波器中傅里葉基數(shù)量是否影響ASGFCN性能。具體內(nèi)容如下:

(1)ASGFCN與基線對比實驗。

實驗設(shè)置文中所提方法在三個數(shù)據(jù)集上與其他基線的對比,得到表2的統(tǒng)計結(jié)果。表2中指標縱向?qū)Ρ?較大者以粗體突出表示。從表中可以看出,SSE的指標在三個數(shù)據(jù)集上最低,ASGFCN的指標在兩個數(shù)據(jù)集上明顯高于其它基線。在D-548上與SGFCN和SGCN幾乎相當。通過分析實驗結(jié)果,發(fā)現(xiàn)ASGFCN性能顯著,在多個數(shù)據(jù)集上都優(yōu)于基線。具體而言,在AUC指標上優(yōu)于基線11.19%,在F1指標上優(yōu)于基線12.11%。在D-548上,ASGFCN與SGFCN和SGCN效果幾乎相當,這是由于D-548數(shù)據(jù)集本身未統(tǒng)計多樣化屬性。SSE效果最差,這是其本身未利用網(wǎng)絡(luò)結(jié)構(gòu)所導(dǎo)致的。

表2 ASGFCN與基線對比結(jié)果

(2)ASGFCN變體A-L與變體A-LH對比實驗。

實驗設(shè)置基于ASGFCN變體A-L或A-LH的鏈路預(yù)測算法在三個數(shù)據(jù)集的性能比較,A-L僅考慮低頻信號,A-LH考慮低頻與高頻信號。統(tǒng)計結(jié)果如表3所示。表3展示了基于A-L或A-LH的鏈路預(yù)測算法的AUC指標與F1指標在三個數(shù)據(jù)集對比情況。通過分析實驗結(jié)果,發(fā)現(xiàn)額外考慮高頻信號的A-LH與A-L相比,有更好的性能。A-LH與A-L之間的效果差距在D-548達到最大,D-1562次之,D-597差距最小。對D-548數(shù)據(jù)集,A-LH的AUC指標優(yōu)于A-L 1.32%,F1指標則優(yōu)于A-L 1.80%。對D-597數(shù)據(jù)集,A-LH的AUC指標相對A-L也達到了0.53%的提升,F1指標上A-LH也有1.05%的提升。這表明在無符號圖中表征節(jié)點間差異性的高頻信號在符號圖中仍可表征節(jié)點間某種特殊關(guān)系,且此關(guān)系影響信號在符號圖上的傳播。

表3 基線對比結(jié)果高頻信號對ASGFCN的影響

(3)ASGFCN與變體A-LHW-C對比實驗。

實驗比較所提方法與A-LHW-C在兩個數(shù)據(jù)集的性能,結(jié)果如表4所示。A-LHW-C與所提方法相比,僅考慮單通道化學(xué)結(jié)構(gòu)特征構(gòu)成屬性相似性圖。

表4 屬性相似性圖的影響

表4展示了所提方法與A-LHW-C的AUC指標與F1指標在兩個數(shù)據(jù)集的對比情況,由于D-548無多樣化屬性,故不將其加入對比。從表中可以看出,該文提出的算法在兩個數(shù)據(jù)集上指標都明顯大于對比的變體,在AUC指標上,ASGFCN比僅利用化學(xué)結(jié)構(gòu)作為特征屬性的A-LHW-C提高了5.65%。通過分析實驗結(jié)果,發(fā)現(xiàn)利用多通道節(jié)點屬性的ASGFCN在性能上明顯優(yōu)于僅利用單通道節(jié)點屬性的A-LHW-C。這表明節(jié)點屬性會影響邊的符號屬性,而ASGFCN模型更好地利用了節(jié)點多通道屬性,也就捕獲到了邊符號屬性的影響因素。

(4)ASGFCN的帶通濾波器中K取值對比實驗。

將D-1562作為圖數(shù)據(jù)放入基于ASGFCN的鏈路預(yù)測框架,決定傅里葉基數(shù)量的K值分別取值為{8,16,32,64,128},設(shè)置對比實驗,結(jié)果如圖4所示。

圖4 不同傅里葉基數(shù)量的影響

圖4表示基于ASGFCN模型的鏈路預(yù)測算法性能隨帶通濾波器傅里葉基數(shù)量變化的結(jié)果折線圖。實線與虛線分別代表AUC指標與F1指標。從圖中可以看出折線總體波動情況不大,呈現(xiàn)先上升后緩慢下降的趨勢,K=32時,折線處于最高點。分析實驗結(jié)果得到ASGFCN帶通濾波器中傅里葉基數(shù)量對模型性能影響較小的結(jié)論。為了充分發(fā)揮ASGFCN性能,ASGFCN模型及變體設(shè)定K=32。

6 結(jié)束語

針對現(xiàn)有的符號圖神經(jīng)網(wǎng)絡(luò)模型主要基于社會平衡理論且未充分利用節(jié)點屬性的問題,提出一種基于圖濾波器的符號屬性圖鏈路預(yù)測算法。從新的視角設(shè)計了兼顧低高頻信號的符號圖濾波器,并通過參數(shù)化頻率響應(yīng)函數(shù),提高了ASGFCN模型的自適應(yīng)學(xué)習(xí)能力。構(gòu)造屬性相似性圖并利用圖卷積網(wǎng)絡(luò)得到另一種節(jié)點表達,并通過注意力機制融合符號拓撲圖與屬性相似性圖節(jié)點嵌入,進一步挖掘節(jié)點屬性所蘊涵的信息。基于多個數(shù)據(jù)集的對比實驗驗證了ASGFCN鏈路預(yù)測算法具有良好的性能。未來將進一步嘗試合適的符號圖拉普拉矩陣,為符號屬性圖定制圖譜濾波器,并豐富實驗集種類。