马 华,姜 伟,陈 明,钟世杰

(湖南师范大学 信息科学与工程学院,湖南 长沙 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链路预测算法具有良好的性能。未来将进一步尝试合适的符号图拉普拉矩阵,为符号属性图定制图谱滤波器,并丰富实验集种类。