Page 408 - 《软件学报》2025年第9期

何玉林 等: 基于时空注意力的多粒度链路预测算法 4319

3 ∑
X statt = Attention i (16)
i=1
其中, X statt ∈ R N×d .

最后, 通过多层全连接层将综合时空特征 X statt 转化为节点之间的链接关系, 具体如下所示:

b A l+1 = MLP(X statt ) (17)
其中, b A l+1 ∈ R N×N 表示第 l+1 个时间步社交网络快照 b G l+1 对应的邻接矩阵预测结果. MLP 表示多层全连接层, 除最
后一层使用 Sigmoid 激活函数外, 其余层均采用 ReLU 激活函数.

2.7 模型的训练优化
现实世界中, 社交网络是稀疏的, 社交网络中节点之间的链接相对于可能的全部链接而言是相对较少的, 这导
致网络的链接密度较低. 因此, 设计损失函数时, 需要考虑社交网络的稀疏性. 为了解决社交网络稀疏性的问题, 在
[32]
反向传播中给予存在的链接更多地关注, 本文使用带稀疏惩罚的损失函数 L , 具体如下所示:

2

(18)
L =
P∗( b A l+1 − A l+1 )
F
其中, A l+1 是第 l+1 个时间步真实社交网络快照 G l+1 的邻接矩阵, ∗ 表示逐元素乘法, P 是惩罚矩阵, 具体表示如下式:


β, (A l+1 ) i,j > 0
(19)

P = 
 1, (A l+1 ) i,j = 0
其中, β > 1 为惩罚系数, 对非零元素施加了更多的惩罚来解决社交网络稀疏性问题.
本文提出的 SAMG-LP 算法的训练过程的伪代码如算法 1 所示.
算法 1. 基于注意力的多粒度链路预测 SAMG-LP 算法.
1 1 1 1 G l+1 ;
输入: 社交网络快照序列 G = {G ,G ,...,G } 和未来社交网络快照
1 2 l
输出: 优化后的算法及其参数.
步骤 1. 构建多粒度特征: 对粒度 1 快照序列 G 使用 GWMA 生成粒度 2 快照序列 G , 类似地, 利用粒度 2 快照序
1
2
G 生成粒度 3 G ;
2
3
列 快照序列
步骤 2. 建模时间特征: 对 3 种不同粒度的社交网络快照序列分别使用时间注意力网络提取时间信息, 由公式 (6)
得到时间特征;
步骤 3. 建模空间特征: 由公式 (7)–公式 (10) 自适应构建社交网络的空间拓扑结构, 并由公式 (11) 得到 3 种不同粒
度的社交网络快照序列的时空特征;
步骤 4. 由公式 (15) 从 3 种不同粒度的时空特征分别提取短期、中期和长期信息, 由公式 (16) 完成特征融合, 并由
公式 (17) 将综合时空特征转化为社交网络链路预测结果;
步骤 5. 由公式 (18) 得到损失函数, 并通过梯度下降更新算法的参数.
本文提出的 SAMG-LP 算法时间复杂度主要包括对步骤 2、步骤 3 和步骤 4 共 3 部分的计算. 在步骤 2 中主
要计算量是公式 (6), 其相应的计算复杂度是 O(Nlh d ), 其中 N 是社交网络节点数, 是社交网络快照序列的长度,
2 2
l
k
h 是注意力的头数, d k 是每个注意力头的输出维度. 步骤 3 中主要计算量是公式 (7), 计算复杂度是 O(N D 2 ), 其中
2
2
D 2 是权重参数 W 2 的输出维度. 步骤 4 的主要计算量在公式 (15), 计算复杂度 O(N d), 其中 d 是注意力神经网络的
2
输出维度. 由于真实社交网络中的节点数往往是巨大的, 因此, 算法时间复杂度可简约地表示为 O(N ).

3 实验分析
本节主要在真实数据集上验证本文提出的 SAMG-LP 算法的链路预测效果. 实验主要分成 4 部分: 第 1 部分
是在 4 个真实社交网络数据集上, 通过与基准模型比较, 验证 SAMG-LP 算法在链接预测任务上的优越性; 第 2 部
分是通过消融实验, 分析 SAMG-LP 各个组件对算法性能的影响; 第 3 部分是分析不同参数设置对 SAMG-LP 算