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

钱忠胜 等: 利用伪重叠判定机制的多层循环 GCN 跨域推荐 4345

表 6). 下面对本文模型及部分具有代表性的对比模型就其时间复杂度进行分析.
1) 就本文模型 PO-CDRec 而言, 其时间复杂度主要表现在伪重叠判定机制用户聚类与多层循环 GCN 偏好学
习两个部分. 伪重叠判定机制用户聚类部分主要利用社区聚类算法. 在局部优化阶段, 每个节点均需计算其加入相
邻节点所在社区后的模块度变化, 并选择最优的社区进行合并, 时间复杂度为 O(NM), 其中 N 是用户数, M 是邻居
节点数. 经过局部优化后, 每个社区被视为一个新的超节点, 形成新的简化网络, 新网络的节点数减少为原网络的
社区数, 这通常显著小于 N. 因网络规模在每次合并后缩小, 故社区合并阶段的迭代次数在最坏情况下为 O(logN).
可知, 伪重叠判定机制用户聚类部分的时间复杂度大致为 O(NMlogN). 对于多层循环 GCN 部分, 其运算代价主要
体现在图卷积操作中. 单层图卷积操作的时间复杂度为 O(FEd), 其中 F 为每层的节点数, 每个节点的平均邻居数
为 E, d 是每个节点的特征维度, 对于每一层的图卷积操作需遍历每个节点及其邻居, 并进行相应运算. 可知, 整个
多层循环 GCN 部分的时间复杂度为 O(KFEd), K 为嵌入传播深度. 因此, 本文模型的时间复杂度大致为 O(NMlogN
+ KFEd).

7.48 8.00 9.48 14.00
7.10 7.00 9.10 12.00
6.72
6.00
8.72
10.00
MRR 值 6.34 5.00 NDCG@10 值 MRR 值 8.34 8.00 NDCG@10 值
7.96
6.00
4.00
5.96
5.58 3.00 7.58 4.00
5.20 2.00 7.20 2.00
0.005 0.01 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.005 0.01 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
重叠用户影响权重 重叠用户影响权重
(a) 重叠用户影响权重对 Music→Movie 的影响 (b) 重叠用户影响权重对 Phone→Elec 的影响
6.88 8.00 7.00 8.00
6.60 7.00 6.00 7.00
6.32
6.00
5.00
6.00
MRR 值 6.04 5.00 NDCG@10 值 MRR 值 4.00 5.00 NDCG@10 值
4.00
3.00
4.00
5.76
5.48 3.00 2.00 3.00
5.20 2.00 1.00 2.00
0.005 0.01 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.005 0.01 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5
重叠用户影响权重 重叠用户影响权重
(c) 重叠用户影响权重对 Cloth→Sport 的影响 (d) 重叠用户影响权重对 Game→Video 的影响
MRR NDCG@10
图 5 重叠用户影响权重的影响

2) 就对比模型 HCCDR (相对较新的改进聚类算法的跨域推荐模型) 的时间复杂度来说, 其时间主要消耗在软聚
类分配节点上, 时间复杂度大致为 O(LNId), L 为平均聚类簇数, I 为训练轮数. 与模型 HCCDR 相比, 本文模型 PO-
CDRec 的复杂度虽有所增加, 但模型 HCCDR 仅侧重用户聚类, 导致模型适应性不足. 且就目前大多数 GPU/CPU 来
说, 本文模型的计算任务并不算大. 特别地, 从推荐效果来看, 所提模型 PO-CDRec 比 HCCDR 的性能有所提升.
3) 就对比模型 FPPDM (在仅改进聚类算法的跨域推荐模型中表现最优) 的时间复杂度来说, 其时间主要消耗
在单域建模、全局聚合以及紧致性联合聚类上, 时间复杂度大致为 O(IEd+cgN+LNId), 其中 c 表示参与联邦学习
的客户端数量, g 表示全局聚合轮数. 相较于本文模型而言, FPPDM 模型使用联邦学习涉及多个本地域之间的模
型参数传输和聚合, 更侧重于隐私保护, 需消耗更多的时间和计算资源, 导致其时间复杂度较高.
2
4) 就对比模型 I RCDR (相对较新的基于 GCN 的跨域推荐模型) 的时间复杂度来说, 其时间主要消耗在图卷
积网络上, 时间复杂度大致为 O(IFEd). 模型 I RCDR 针对重叠用户的跨域场景, 更侧重于用户关系的挖掘, 忽视了
2
2
非重叠用户场景, 导致用户相似度迁移不准确. 与模型 I RCDR 相比, 本文模型 PO-CDRec 的复杂度虽有所增加,
但换来了较大的性能提升.
5) 就对比模型 GLOU (在对比模型中平均性能最佳) 的时间复杂度来说, 其时间主要由图卷积网络的计算决
定, 时间复杂度大致为 O(NMI+LFEd). 该模型根据偏好对用户分组并利用 GCN 挖掘不同用户组图中的节点高阶
关系. 因在通常情况下, 平均聚类簇数 L 远大于嵌入传播深度 K, 故本文模型 PO-CDRec 的复杂度通常会低于对比