基于圖濾波器的符號屬性圖鏈路關系預測算法

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

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

0 引 言

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

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

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

1 符號屬性圖的鏈路關系預測問題

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

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

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

圖1 符號圖上的鏈路關系預測問題

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

2 相關工作

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

與這些淺層模型相比,圖深度學習方法構建了聯合求解圖節點嵌入及下游任務的端到端學習框架,能實現更好的預測效果。GNNs是當前流行的用于圖結構數據分析的深度學習方法。該類方法能較好地利用節點特征與網絡結構,是端到端訓練模型,且擁有成熟的訓練工具箱[16]。

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

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

3 基于ASGFCN的符號屬性圖節點嵌入

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

圖2 基于圖濾波器的符號圖卷積網絡

3.1 基于帶通濾波器的符號圖神經網絡

3.1.1 GCN以及其GSP視角

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

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

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

(1)

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

(2)

3.1.2 基于帶通濾波器的符號圖神經網絡

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

(3)

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

(4)

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

(5)

3.2 基于屬性相似性圖的節點嵌入

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

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

(6)

3.3 基于注意力機制的節點嵌入融合

對ZA與ZAF進行加權求和,將兩者融合:

Z=αAZA+αAFZAF

(7)

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

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

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

(8)

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

(9)

同理:

αAFi=softmax(WAFi)

(10)

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

4 基于ASGFCN的鏈路預測算法

本節提出了基于ASGFCN的端到端鏈路關系預測算法,并將其應用于藥物網絡鏈路預測問題中。

(11)

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

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

圖3 算法流程

5 實驗設計與分析

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

5.1 數據集

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

表1 實驗使用的數據集

5.2 實驗設置

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

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

所有算法都基于PyTorch實現,且均使用兩個網絡層和一個學習率為0.01的Adam優化器。為了保證帶通濾波器同等考慮低通與高通信號,式(4)的k_l與k_h皆設為K/2。使用不同的迭代次數訓練模型,發現迭代1 000次足以獲得良好的結果。

5.3 實驗結果和分析

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

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

實驗設置文中所提方法在三個數據集上與其他基線的對比,得到表2的統計結果。表2中指標縱向對比,較大者以粗體突出表示。從表中可以看出,SSE的指標在三個數據集上最低,ASGFCN的指標在兩個數據集上明顯高于其它基線。在D-548上與SGFCN和SGCN幾乎相當。通過分析實驗結果,發現ASGFCN性能顯著,在多個數據集上都優于基線。具體而言,在AUC指標上優于基線11.19%,在F1指標上優于基線12.11%。在D-548上,ASGFCN與SGFCN和SGCN效果幾乎相當,這是由于D-548數據集本身未統計多樣化屬性。SSE效果最差,這是其本身未利用網絡結構所導致的。

表2 ASGFCN與基線對比結果

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

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

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

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

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

表4 屬性相似性圖的影響

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

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

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

圖4 不同傅里葉基數量的影響

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

6 結束語

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