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

4324 软件学报 2025 年第 36 卷第 9 期

θ 超过 0.2 以后, 预测性能逐步下降. 这是因为适度地减小历史网络快照的
性能达到较好的效果; 当时间衰减参数
权重有助于提高特征的区分度, 从而提升预测性能; 而时间衰减参数 θ 过大时, 历史网络快照信息会被过度丢弃,
导致模型预测性能下降. 实验结果表明, 时间衰减参数 θ 取值在 0.1–0.2 之间较为合适.

3.6 时间分析
为探讨 SAMG-LP 算法与所有基准算法的训练时间消耗, 我们对所有算法在相同训练样本上的训练时间进行
了对比, 记录 5 次随机实验结果的平均值如表 4 所示, 其中加粗部分表示一类方法中的最佳结果. 从理论分析, 所
O(N ), 但它们具体训练时长却有所不同. 这是因为理论时间复杂度忽略了常数因
2
有算法的时间复杂度几乎都是
子和低阶项的影响, 而这些因素在实际运行时会对性能产生影响. 从实验结果分析, 深度学习链路预测方法所需的
训练成本比矩阵分解方法、相似性指数方法更高. 这是因为在相似性指数方法中, 它们通过梯度提升等算法训练,
甚至不需要训练. 例如, PR-CN 直接根据输入数据预测未来结果; 矩阵分解方法则以梯度下降法来优化矩阵参数,
因其涉及的矩阵参数较少而具有较好的训练速度. 然而, 这两类方法的学习能力有限, 导致其在实际应用中的预测
表现不佳.

表 4 SAMG-LP 和基线方法在 4 个数据集上的训练时间成本 (s)

方法类型 算法 Haggle LH10 LyonSchool workplace 理论时间复杂度
2
PR-CN － － － － O(N )
相似性指数方法
2
NC-LGBM 44.62 281.10 1 096.78 673.88 O(N )
2
MljFE 132.76 413.88 1 369.31 852.23 O(N )
矩阵分解方法
LPANMF 191.99 323.20 1 708.04 904.50 O(N )
2
2
GC-LSTM 246.43 640.56 3 640.91 1 320.94 O(N )
3
SRG 291.85 862.43 5 180.83 2 263.77 O(N )
深度学习方法
2
GCN_MA 259.68 249.19 2 637.50 712.59 O(N )
2
SAMG-LP 235.47 371.39 2 362.52 695.61 O(N )
注: “－”表示方法不适用

在深度学习方法中, SRG 立方级的时间复杂度使其所需训练时长比其他方法更多. 相比之下, GCN_MA 和
GC-LSTM 在训练时间上有所不同. GC-LSTM 将 GCN 嵌入 LSTM 结构中, 由于嵌入后模块的高计算消耗以及需
要逐步处理每一个时间步, 导致训练成本较高. GCN_MA 则通过解耦 GCN、LSTM 和注意力神经网络, 分别学习
社交网络不同层次的时空特征, 从而在训练时间上具有优势. 相比上述模型, SAMG-LP 摒弃了逐步从每个时间步
学习空间特征的思路, 通过结合掩码注意力机制在整个图快照序列中学习网络节点间的连接强度, 进而只需一次
图卷积操作即可完成空间特征的提取. 此外, SAMG-LP 模块之间采用解耦的方式, 确保了单个模块计算的低消耗
性. 综合而言, SAMG-LP 在速度和预测性能方面能够达到更好的平衡.

4 总 结

针对现有链路预测算法仅考虑单一粒度的社交网络快照序列和无法从长期角度考虑节点邻居不同重要程度
等问题, 本文提出一种基于注意力的多粒度链路预测 SAMG-LP 算法. 通过扩展加权移动平均提出图加权移动平
均策略, 用于构建反映短、中、长期变化趋势的不同粒度社交网络时间序列, 并基于多头注意力神经网络从全局
角度依次建模不同粒度社交网络时间序列的时间信息, 然后引入掩码注意力机制自适应地学习社交网络中节点之
间的相互影响关系, 结合图卷积网络构建网络的空间特征, 进一步提出了融合注意力神经网络有效地融合来自不
同粒度的时空上下文, 最后使用稀疏惩罚损失实现更准确可靠的链路预测. 在 4 种真实社交网络数据集上的大量
对比实验和消融实验验证了 SAMG-LP 算法的优越性和有效性. 在未来工作中, 将进一步探索链路预测中的多分
量特征联合建模, 如对网络序列中的高、低频分量联合建模, 或对谱域、空间域分量的联合建模等, 充分利用网络
序列中的多种信息进一步提高模型链路预测的能力.