-
摘要:
基于本地差分隐私的图聚类工作成为近年来的一个研究热点. 已有工作主要针对的是无向图，且大多利用位向量技术通过模块化聚合实现. 由于噪声量与向量维度成线性关系，使得聚类质量和隐私性难以很好地兼顾. 此外，针对无向图中边的有/无设计的2元扰动机制在面对有向图时，因无法对边的方向性进行处理而无法适用. 针对上述问题，提出一种基于本地边差分隐私（edge local differential privacy, Edge-LDP）的有向图聚类算法DGC-LDP (directed graph clustering under LDP）. 具体来说，为了降低噪音量同时适用于有向图，基于直接编码方式设计了一种适用于有向星型图的动态扰动机制，通过自适应添加噪声来平衡隐私性和统计效用. 在此基础上，在终端和收集者之间构建迭代机制. 收集者依据终端上传的噪声数据提取节点间的相似性信息，并设计基于轮廓系数测量模型的节点聚合算法，通过迭代机制不断地优化节点聚合形式形成高质量簇. 理论分析和实验结果表明，所提算法在满足Edge-LDP 的同时能够有效兼顾聚类精度.
Abstract:Graph clustering based on local differential privacy has become a hot research topic in recent years. Most existing solutions are mainly realized through modular aggregation using bit vector technology. The linear relationship between the amount of noise and the vector dimension makes balancing clustering quality and privacy challenges. Aiming at the above problems, a directed graph clustering algorithm, DGC-LDP (directed graph clustering under LDP), is proposed based on edge local differential privacy (Edge-LDP). Concretely, the direct encoding method replaces the bit vector encoding method to reduce the amount of data in privacy processing. Meanwhile, a dynamic perturbation mechanism is designed based on the graph structure to balance privacy and statistical utility by adaptively adding noise. Then, according to the individual information uploaded by the terminal, the collector extracts the similarity information between nodes and designs a node aggregation algorithm based on the silhouette coefficient measurement model to generate clusters. Finally, an iterative mechanism is built between the terminal and the collector, and the collector iteratively optimizes the node aggregation form based on the statistical information fed back by the mechanism to achieve high-quality clustering. Theoretical analysis and experimentation on real-world datasets demonstrate that our proposed algorithm can obtain desirable clustering results while satisfying Edge-LDP.
-
Keywords:
- privacy-preserving /
- local differential privacy /
- graph clustering /
- random response /
- similarity
-
在序列推荐[1-4]中根据用户的交互序列预测下一时刻用户将要交互的物品，已经引起了大量的关注，序列推荐的核心挑战是如何从用户的复杂行为中准确建模用户的偏好.
在早期工作中，通过马尔可夫链（Markov chain， MC）[5-6]或者分解机[7-8]来建模序列物品之间的低阶关系，但是用户的交互序列往往比较长，这类方法难以捕获序列间的高阶依赖信息. 因此研究者们开始用高阶马尔可夫链模型和递归神经网络(recursive neural network，RNN)[9-11]来解决高阶依赖的问题，但是高阶马尔可夫模型的模型参数量随阶次指数增长，而RNN方法中具有较强的顺序依赖的假设在用户交互具有灵活顺序的序列中难以应用. 随着注意力机制和图神经网络模型成为热点，研究者们[12-15]也将其引入了序列推荐中建模用户偏好，但是这些方法通常将用户的偏好表示为单一向量，在较长的交互序列中往往存在多个用户的偏好. 此外，这些方法没有充分考虑用户交互序列中时间间隔分布不均匀的问题. 图1展示了电商数据集中2个用户的交互序列. 从图1中可以看出：用户u1和u2的序列中均存在3个主要的兴趣点，因此将用户的偏好表示为单一向量，不能准确地区分这3种不同的兴趣点. 为了解决这个问题，研究者们提出了一些多兴趣建模的方法，通常的做法是根据用户行为序列中的物品依赖关系对多个兴趣进行显式建模. 如MGNM模型[16]利用图卷积神经网络迭代学习物品的嵌入以捕获不同层次的复杂偏好，然后通过序列胶囊网络学习用户的多兴趣嵌入. 但是该方法仅考虑了用户自己交互的历史序列，只能准确建模用户交互序列中的局部偏好，难以学习相似用户行为之间的潜在关联关系（如用户u1和用户u2均对毛绒玩具感兴趣）. 此外用户的偏好随着时间的变化在发生漂移，如果忽略时间属性，会影响偏好的准确性.
![]()
图 1 不同时间间隔的用户交互序列Figure 1. The sequence of user interactions at different time intervals一些基于时间的推荐方法侧重于对绝对时间戳进行建模，以捕获用户和物品的时间动态. 如文献[17]将自激励点过程和低秩模型连接起来，以捕获大量用户物品对中反复出现的时间模式. 文献[7]通过静态视图和动态视图相结合的方式，将时间预测任务和因式分解机结合起来. 考虑到用户的兴趣随着时间的变化发生漂移，文献[18]基于Transformer预训练模型将下一个时间步长的物品作为当前时间步的兴趣标记，从而得到每个时间步长的兴趣. 还有一些研究没有局限于将时间信息作为模型输入，而是从绝对时间和相对时间2方面分析用户行为的时间模式. 如TiSASRec模型[19]对物品之间的相对时间间隔和绝对位置进行建模，以预测未来的相互作用. 文献[20]在建模用户的长短期偏好时，引入时间自注意力机制提高模型的性能. 文献[18-20]所述的方法将时间作为边信息来增强推荐，没有分析和处理序列中时间间隔分布对于用户偏好学习的影响. 从图1中可以直观地发现2个现象：1）在交互序列中，时间间隔越大的地方用户越容易发生兴趣漂移； 2）用户u1交互序列中时间间隔的标准差小于用户u2的交互序列中时间间隔的标准差，标准差越小，表示序列中时间分布越均匀，用户的兴趣分布越集中，模型能够更准确地学习到用户的多个兴趣. 而在u2的序列中，用户在时刻t−5和时刻t具有相同的兴趣（毛绒玩具），但是由于存在较长的时间间隔，模型倾向于将其视为2个兴趣点进行学习. Dang等人[21]证明了时间间隔均匀分布的序列比时间间隔变化较大的序列更有利于性能的提高.
因此，本文提出了基于对比学习的多兴趣感知序列推荐模型MIRec，在用户交互序列中学习用户的局部偏好和全局偏好，并且从中挖掘用户的多个兴趣点；同时考虑时间间隔分布对偏好建模的影响，对用户的序列进行了数据增强，采用对比学习机制使历史交互序列和增强交互序列互相靠近.
本文的创新点可以总结为3点：
1） 提出了多粒度用户偏好挖掘模块，通过Transformer的编码器结构学习用户物品序列内的依赖关系，建模细粒度的局部用户偏好，并通过图神经网络方法学习用户与其相似用户之间的潜在偏好，建模粗粒度的全局用户偏好.
2） 设计了多兴趣表示和对比学习机制，先利用胶囊网络学习融合了用户局部偏好和全局偏好的表示中潜在的用户多兴趣嵌入，同时采用相似度替换方式进行数据增强，并引入对比学习进一步精准学习用户的偏好.
3） 将本文方法MIRec在2个公开数据集上进行了广泛的实验，验证了本文方法的有效性.
1. 相关工作
根据本文的工作，此节首先介绍常见的序列推荐方法，然后介绍考虑用户交互序列中多兴趣的序列推荐方法.
1.1 常见序列推荐方法
与传统推荐方法[22-24]相比，序列推荐方法考虑了交互序列中物品的顺序. 早期的方法利用马尔可夫链中下一个动作依赖于前序动作的特性，提出了很多基于马尔可夫链的序列推荐模型，如Rendle等人[5]结合矩阵分解和马尔可夫链方法，为每个用户使用单独的转换矩阵. 早期的基于一阶马尔可夫链的方法具有较强的下一个动作依赖于上一个行为的假设，建模用户长期兴趣的能力有限. 为了解决这个问题，在Fossil模型[6]中提出了利用高阶马尔可夫链来学习更多的信息，并结合相似性模型解决序列推荐中的稀疏性问题. 随着马尔可夫链的阶次的提升，参数量也在逐渐增长.
后来研究者们发现RNN模型既能学到类似于马尔可夫链的转移信息，也能通过增加门控机制等方式学习序列中的长短期偏好. 具有代表性的方法是GRU4Rec[25]对基于RNN的方法进行了部分优化，提出了会话（session）并行的概念、负采样方法等，并根据任务改进损失函数. 为了更好地建模序列的整体信息，研究者们也引入了基于CNN的方法，如Caser模型[26]和HierTCN[27]等，但是这些方法只能捕获从局部到整体的卷积信息，忽略了交互序列之间的关联性.
随着注意力机制和图神经网络（GNN）技术的发展，基于Transformer的方法和图神经网络的方法成为了近年的一个研究热点. Kang等人[15]提出的SASRec模型是较早时期的尝试，对整个用户序列进行建模，不进行任何循环和卷积操作，通过注意力机制自适应学习交互序列的特征进而预测下一时刻交互的物品.Sun等人[28]提出的BERT4Rec模型采用深度双向自注意力机制建模用户行为序列. Wu等人[29]提出的SSE-PT模型考虑用户嵌入在序列模型中的重要性，并提出了随机共享嵌入的方法来提升性能. 由于图神经网络方法在图上的优秀建模能力，Wu等人[30]提出了基于GNN的方法SR-GNN，首先将用户的序列转换为图结构，然后使用注意力网络将每个会话表示为全局偏好和该会话当前兴趣的组合. 图神经网络和注意力相结合的工作有利于提取更多一致性[31]或邻接性的特征. Fan等人[32]提出的TGSRec模型将图信息和时间信息相结合，提高了模型的性能. Chang等人[33]提出的SURGE通过考虑隐式信号行为和快速变化的偏好，利用图神经网络从嘈杂的用户行为序列中动态融合和提取用户的核心兴趣.
最近结合注意力网络和图神经网络的方法进一步提升了模型的性能，能够更准确地挖掘用户的兴趣，但是这些方法中仅考虑了交互序列中的单一兴趣. 实际上在用户的交互序列中会存在多个不同的用户兴趣. 此外，这些方法旨在从用户自身交互的序列内挖掘用户的偏好，忽略了具有相似特征的用户之间的潜在关联.
1.2 多兴趣序列推荐方法
为了能够学习用户交互序列中的复杂行为，研究者们开始研究基于多兴趣的序列推荐模型. Li等人[18]提出的模型MIND中设计了一个具有可变动态路由的多兴趣提取层来提取用户的不同兴趣，然后使用一种新颖的标签感知注意力方案对这些兴趣进行训练. Pi等人[34]借鉴神经图灵机（neural turing machine，NTM）的思想，提出了多通道用户兴趣存储网络模型MIMN，该模型包括基本的存储单元和多通道门控循环单元（gate recurrent unit，GRU）的内存槽存储和学习用户的多兴趣. Li等人[35]提出了由兴趣提取层、兴趣聚合层和注意力融合结构组成的多分辨率兴趣融合模型，解决不同时间范围内用户偏好的提取和组合问题. Cen等人[36]提出了一种新的可控多兴趣框架（ComiRec）用于序列推荐，使用多兴趣提取模块生成多个用户兴趣，并使用聚合模块获得总体排名前N的物品. ComiRec和MIMN侧重于通过聚类等方法来提取用户的不同兴趣，图卷积的方法可以建模基于历史交互物品中的多层次关联来细化用户的偏好. Tian等人[16]将多兴趣学习和图卷积聚合结合起来，提出了MGNM模型，通过多层图卷积神经网络和胶囊网络学习用户的多个兴趣.
考虑交互序列中的多兴趣能够更准确地捕获用户的实际偏好，但是目前的多兴趣学习方法中没有考虑用户间的全局偏好和研究用户交互序列中时间间隔分布的影响. 因此在本文中，我们考虑用户的局部偏好和全局偏好2个方面，同时基于交互物品的时间间隔，对用户的交互序列进行了数据增强，在训练过程中通过对比损失为模型提供更多的监督信号.
2. 问题定义
序列推荐系统根据用户带有时序信息的历史交互序列，预测用户在下一刻要交互的物品. V={x1，x2，…，xM}表示所有的物品集合，U={u1，u2，…，uN}表示所有的用户集合，用户与物品的交互序列表示为{su}NM. 对于每个用户u，用户交互的有序序列su={x1，x2，…，xt}，交互的时间序列表示为Tu={1，2，…，t}，基于时刻t的交互序列预测用户在时刻t+1交互的物品xt+1. 形式化定义为:
argmaxxi∈V(xt+1=xi|su). (1) 3. 模 型
本节详细介绍我们提出的基于对比学习的多兴趣感知序列推荐模型，模型主要包括多粒度用户偏好挖掘模块和多兴趣表示学习2个部分. 其中的多粒度用户偏好挖掘模块用于学习用户的细粒度的局部偏好和粗粒度的全局偏好，进而在融合局部偏好和全局偏好的用户表示中学习用户的多兴趣表示. 为了缓解用户交互序列中时间间隔分布不均匀影响模型性能的问题，对用户的交互序列进行了数据增强，在模型训练中引入更多监督信号，通过对比学习使模型更准确地学习间隔较大的用户的相同兴趣. 模型整体结构如图2所示.
3.1 多粒度用户偏好模块
多粒度用户偏好模块中主要包括学习细粒度用户偏好的序列编码模型和学习粗粒度用户偏好的图神经网络模型.
3.1.1 局部偏好模块
用户的历史交互序列中，物品之间存在一定的时间依赖关系和顺序依赖关系，我们首先采用Tansformer的编码器结构来学习交互序列中的物品之间的长期和短期依赖关系.
{\boldsymbol{h}}_{i}={\boldsymbol{e}}_{i}+{\boldsymbol{p}}_{i}， (2) 其中， {\boldsymbol{e}}_{i}\in {\mathbb{R}}^{d} 表示初始的物品嵌入， {\boldsymbol{p}}_{i}\in {\mathbb{R}}^{d} 表示物品i的位置嵌入，可以区分不同交互物品的时间顺序和位置信息，加入位置信息的物品嵌入矩阵表示为 \boldsymbol{H}\in {\mathbb{R}}^{M\times d}，M 表示物品的数量.
Transformer编码器由多层多头注意力和残差连接堆叠而成，在第l层中经过多头注意力模块得到的矩阵表示为 {\hat{\boldsymbol{H}}}^{l} ：
{\hat{\boldsymbol{H}}}^{l}={{softmax}}\left(\frac{{\boldsymbol{W}}^{1}{\boldsymbol{H}}^{l}{({\boldsymbol{W}}^{2}{{{\boldsymbol{H}}}}^{l})}^{\mathrm{T}}}{\sqrt{d}}\right){\boldsymbol{W}}^{3}{\boldsymbol{H}}^{l}， (3) 其中， {\boldsymbol{W}}^{1}，{\boldsymbol{W}}^{2}，{\boldsymbol{W}}^{3} 表示可学习的嵌入变换矩阵，d表示嵌入向量的维度.
由于用户交互序列的长度具有差异性，且层归一化方法可以稳定前向输入分布、加快收敛速度，因此在注意力层后应用层归一化方法对用户的交互序列进行操作：
{{\tilde{\boldsymbol{H}}}^{l}}_{\mathrm{t}\mathrm{m}\mathrm{p}}={\hat{\boldsymbol{H}}}^{l-1}+LN({\boldsymbol{W}}{\hat{\boldsymbol{H}}}^{l})， (4) 其中， LN（\boldsymbol{x}）=\left[\dfrac{\boldsymbol{x}-\mu }{\sqrt{\delta +\varepsilon}}\right]+\beta ，\mu 表示经过线性层后的嵌入的均值， \delta 表示方差. \varepsilon 和 \beta 表示2个可训练的参数，弥补归一化过程中损失掉的信息. 同时引入前馈神经网络建模嵌入中的非线性关系，得到第l层编码输出 {\tilde{\boldsymbol{H}}}^{l} ：
{\tilde{\boldsymbol{H}}}^{l}={{\tilde{\boldsymbol{H}}}^{l}}_{\mathrm{t}\mathrm{m}\mathrm{p}}+FFN(LN({{\tilde{\boldsymbol{H}}}^{l}}_{\mathrm{t}\mathrm{m}\mathrm{p}}))， (5) 其中， {\tilde{\boldsymbol{H}}}^{l} 中学习了用户交互序列中的物品依赖关系和位置依赖等信息，一些研究中用嵌入 {\tilde{\boldsymbol{H}}}^{l} 做预测，由于只学习了序列中的局部偏好，会导致模型次优.
3.1.2 全局偏好模块
在全局偏好模块中，我们主要关注与用户具有相似兴趣的其他用户的交互物品，采用以用户为中心的物品交互图，为学习交互序列中的用户表示提供全局上下文信息，在一定程度上减弱序列数据中噪声信息的影响.
为了缓解用户交互序列中的时间间隔对于用户偏好的影响，在建立用户物品交互图之前，我们对原始的交互序列采用最大相似度替换的方式进行数据增强. 通过计算相邻物品的时间间隔，将时间间隔最大的物品替换为与之最相似但用户未交互过的物品. 时间间隔差计算为
TD= \underset{i\in \{1，2,…,t-1\}}{\mathrm{arg}\;\mathrm{max}}\left|{x}_{i+1}-{x}_{i}\right|. (6) 交互序列中替换物品的数量计算为
TN=\mathrm{max}(int(\lambda \left|{s}_{u}\right|),1), (7) 其中 \lambda 是一个超参数.
在计算好时间间隔和替换物品的数量后，选取与待替换物品最相似的物品进行替换，物品的相似度计算为
{w}_{ij}=\frac{\displaystyle\sum _{u\in N(i)\cap N(j)}\dfrac{1}{\mathrm{log}(1+\left|N(u)\right|)}}{\sqrt{\left|N(i)\right|\times\left|N(j)\right|}}， (8) 其中， N（u） 表示用户 u 交互的物品集合， |N（i）| 表示与物品i交互的用户数量， |N（j）| 表示与物品j交互的用户数量，进行替换操作后原始交互序列 {s}_{u} 表示为 {\bar{s}}_{u} .
基于用户交互行为，我们构建一个以用户为中心的全局交互图 G ，即用户节点和物品节点作为图的顶点，用户与物品交互作为图的边.
由协同过滤方法可知，推荐点击同一物品的其他用户喜欢的物品有更高的点击率，因此本文中也考虑了此类特征，通过图卷积网络的方法获取与用户偏好相关的全局特征. 在图 G 和 \bar{G} 上进行的卷积操作如式（9）所示：
{\boldsymbol{E}}^{l+1}=\sigma \left({\boldsymbol{D}}^{-\tfrac{1}{2}}{\boldsymbol{A}}_{\mathrm{S}}{\boldsymbol{D}}^{\tfrac{1}{2}}{\boldsymbol{E}}^{l}\right), (9) 其中， {\boldsymbol{E}}^{l} 表示经过第l层聚合后的物品嵌入矩阵， {\boldsymbol{A}}_{\mathrm{S}} 表示未经处理的原始数据集合中用户物品的邻接矩阵， \boldsymbol{D} 表示邻接矩阵 {\boldsymbol{A}}_{\mathrm{S}} 的度矩阵，初始化的嵌入矩阵 {\boldsymbol{E}}^{0}\in {\mathbb{R}}^{（M+N）\times T} ，T表示嵌入维度. 在经过图卷积操作后得到的物品嵌入矩阵中，可以查找原始交互序列 {s}_{u} 和数据增强交互序列 {\bar{s}}_{u} 中物品的嵌入，分别表示为 {\boldsymbol{e}}_{u} 和 {\bar{\boldsymbol{e}}}_{u} .
3.2 多兴趣表示模块
通过局部偏好模块和全局偏好模块得到用户交互序列中的物品表示后，借鉴Tian等人[16]的思想，利用胶囊网络将融合全局偏好和局部偏好的嵌入生成用户的多个兴趣表示，多兴趣表示模块如图3所示.
胶囊网络通过内置的动态路由机制将每个兴趣表示组合起来，每个胶囊的输出表示为用户的一个兴趣，为了保证序列推荐中的交互序列的顺序特性不被忽略，在进行动态路由之前对融合全局偏好和局部偏好的用户嵌入进行线性映射，具体为
{\boldsymbol{z}}_{u}={\boldsymbol{w}}_{u}({\tilde{\boldsymbol{h}}}_{u}+{\boldsymbol{e}}_{u}), (10) 其中， {\tilde{\boldsymbol{h}}}_{u} 表示从局部偏好矩阵 {\tilde{\boldsymbol{H}}}^{l} 中得到的用户u的局部偏好， {\boldsymbol{e}}_{u} 表示从原始交互序列中学习的用户全局偏好， {\boldsymbol{w}}_{u} 是一个可训练的参数.
为了捕获长短期偏好，我们引入双向LSTM结构对用户嵌入进行编码，并与原始嵌入进行加和，表示为
{\boldsymbol{z}}_{u}={\boldsymbol{z}}_{u}+BiLSTM({\boldsymbol{z}}_{u}). (11) 在胶囊网络的更新过程中采用动态路由更新，动态路由耦合系数表示为
{\boldsymbol{c}}={{softmax}}({\boldsymbol{g}}), (12) 其中， \boldsymbol{g}=({\boldsymbol{g}}_{1}，{\boldsymbol{g}}_{2}，… ，{\boldsymbol{g}}_{m}) 随机初始化为符合截断正态分布的参数， {\boldsymbol{g}}_{m} 表示物品 {x}_{i} 与上层高级胶囊耦合的先验概率. 将耦合系数 \boldsymbol{c}=({\boldsymbol{c}}_1,{\boldsymbol{c}}_2,…,{\boldsymbol{c}}_m) 与输入表示 {\boldsymbol{z}}_{u} 加权求和后表示为
{\boldsymbol{r}}_{u}=\sum _{i=1}^{m}{\boldsymbol{c}}_{i}{\boldsymbol{z}}_{u}. (13) 然后使用squash方法将向量进行压缩，使其长度在0~1之间并且保持方向不变，如式（14）所示：
{\boldsymbol{o}}_{u}=\frac{{\left|\left|{\boldsymbol{r}}_{u}\right|\right|}^{2}}{{\left|\left|{\boldsymbol{r}}_{u}\right|\right|}^{2}+1}\frac{{\boldsymbol{r}}_{u}}{\left|\left|{\boldsymbol{r}}_{u}\right|\right|}. (14) 耦合系数中的元素的更新方式如式（15）所示：
{\boldsymbol{g}}_{m}={\boldsymbol{g}}_{m}+{{\boldsymbol{o}}_{u}}^{\mathrm{T}}{\boldsymbol{z}}_{u}. (15) 在后续的胶囊网络层中，重复式（12）~（15）的路由过程进一步学习用户的多兴趣表示，将胶囊网络最后一层的输出表示为用户u的多兴趣表示 {\boldsymbol{o}}_{u} ，假设用户的兴趣数量为K，通过胶囊网络后， {\boldsymbol{o}}_{u}=({\boldsymbol{o}}_{u}^{1}， {\boldsymbol{o}}_{u}^{2},… ，{\boldsymbol{o}}_{u}^{K}) .
数据增强的交互序列经过胶囊网络，得到增强交互序列中融合用户全局偏好和局部偏好的K个兴趣表示，即 {{\boldsymbol{o}}_{u}}'=({{\boldsymbol{o}}_{u}^{1}}'，{{\boldsymbol{o}}_{u}^{2}}'，…，{{\boldsymbol{o}}_{u}^{K}}' ), 在本文中我们为每个交互序列进行2次数据增强后得到2个增强序列,第2个增强序列表示得到的多兴趣表示为 {{{\boldsymbol{o}}}_{u}}''=({{{\boldsymbol{o}}}_{u}^{1}}''， {{{\boldsymbol{o}}}_{u}^{2}}''，… ，{{{\boldsymbol{o}}}_{u}^{K}}'' ).
3.3 模型预测和优化
3.3.1 模型预测
给定候选物品 {x}_{t+1} ，首先对用户的第k个兴趣表达 {\boldsymbol{o}}_{u}^{k} 与候选物品的嵌入 {\boldsymbol{e}}_{t+1} 进行注意力计算，如式（16）（17）所示：
{\boldsymbol{o}}_{u}^{k}={\alpha }_{k}{\boldsymbol{o}}_{u}^{k}， (16) {\alpha }_{k}=\frac{\mathrm{e}\mathrm{x}\mathrm{p}({{\boldsymbol{o}}_{u}^{k}}^{\mathrm{T}}{\boldsymbol{e}}_{t+1})}{\displaystyle\sum\limits _{k=1}^{K}{{\boldsymbol{o}}_{u}^{k}}^{\mathrm{T}}{\boldsymbol{e}}_{t+1}}, (17) 其中 {\alpha }_{k} 表示用户的第k个兴趣的注意力权重，然后通过计算内积的方式得到用户的兴趣表示与目标物品的分数，如式（18）所示：
{\hat{y}}_{ui}=\underset{k\in \left\{1，2,…,K\right\}}{\mathrm{arg}\;\mathrm{max}}{\boldsymbol{o}}_{u}^{k}{\boldsymbol{e}}_{t+1}. (18) 3.3.2 模型优化
本文采用交叉熵函数来更新模型，交叉熵损失如式（19）所示：
{\mathcal{L}}_{\mathrm{c}\mathrm{e}}=-\sum _{u,i}\left[{y}_{ui}\mathrm{log}\left({\hat{y}}_{ui}\right)+\left(1-{y}_{ui}\right)\mathrm{log}\left(1-{\hat{y}}_{ui}\right)\right]， (19) 其中， {y}_{ui} 表示用户u和物品 {x}_{t+1} 的真实标签， {\hat{y}}_{ui} 为预测标签.
序列中的时间间隔会影响用户的偏好挖掘，我们没有显式利用交互序列的时间信息，而是通过隐式计算时间间隔，并基于时间间隔得到增强的序列. 因此与原始交互相比，在时间间隔较大的交互物品处，模型能够有更多可学习的监督信号，使其能够更准确地学习用户的多兴趣. 我们为每个交互序列进行2次数据增强后得到2个增强序列，通过数据增强和对比训练，可以更准确地建模用户的兴趣. 在每个batch中，相对应位置的交互序列与数据增强序列中的偏好数据互为正样本，其余的数据为负样本，对比损失计算如式（20）~（23）所示：
{\mathcal{L}}_{\mathrm{c}\mathrm{l}}^{1}=-\mathrm{l}\mathrm{o}\mathrm{g}\frac{\mathrm{e}\mathrm{x}\mathrm{p}(sim({\boldsymbol{o}}_{u}^{k},{{\boldsymbol{o}}_{u}^{k}}'))}{\displaystyle\sum _{j\ne k}\mathrm{e}\mathrm{x}\mathrm{p}(sim({\boldsymbol{o}}_{u}^{k},{{\boldsymbol{o}}_{u}^{j}}'))}， (20) {\mathcal{L}}_{\mathrm{c}\mathrm{l}}^{2}=-\mathrm{l}\mathrm{o}\mathrm{g}\frac{\mathrm{exp}(sim({\boldsymbol{o}}_{u}^{k},{{\boldsymbol{o}}_{u}^{k}}''))}{\displaystyle\sum_{j\ne k}\mathrm{exp}(sim({\boldsymbol{o}}_{u}^{k},{{\boldsymbol{o}}_{u}^{j}}''))}， (21) {\mathcal{L}}_{\mathrm{c}\mathrm{l}}^{3}=-\mathrm{l}\mathrm{o}\mathrm{g}\frac{\mathrm{exp}(sim({{\boldsymbol{o}}_{u}^{k}}',{{\boldsymbol{o}}_{u}^{k}}''))}{\displaystyle\sum _{j\ne k}\mathrm{exp}(sim({{\boldsymbol{o}}_{u}^{k}}',{{\boldsymbol{o}}_{u}^{j}}''))}， (22) {\mathcal{L}}_{\mathrm{c}\mathrm{l}}={(\mathcal{L}}_{\mathrm{c}\mathrm{l}}^{1}+{\mathcal{L}}_{\mathrm{c}\mathrm{l}}^{2}+{\mathcal{L}}_{\mathrm{c}\mathrm{l}}^{3})/3. (23) 其中， sim（） 表示相似度计算，采用简单的内积计算方式.
为了增强数据的自监督信号增强序列推荐的性能，将序列推荐任务和对比学习任务进行联合训练，节点损失为线性加权和，计算为
L={\mathcal{L}}_{\mathrm{c}\mathrm{e}}+\beta {\mathcal{L}}_{\mathrm{c}\mathrm{l}}， (24) 其中 \beta 是控制对比损失权重的超参数.
4. 实 验
在本节中，我们通过大量的实验验证本文模型的性能，实验中主要验证3个研究问题RQ1，RQ2和RQ3.其中，RQ1：与当前考虑用户多兴趣的模型相比，本文模型的性能是否最优.RQ2：本文模型的各个部分的组件对模型的性能有什么影响.RQ3：本文模型的参数对性能的影响.
4.1 实验设置
4.1.1 数据集描述
我们使用亚马逊数据集Musical Instruments和Toys and Games来验证本文模型的性能，在数据集中，将评分大于2的交互物品作为正例，将所有数据拆分为训练集、验证集和测试集来训练和验证模型，在测试集上与基线模型进行比较，表1是预处理后的数据集的统计结果.
表 1 数据集统计Table 1. The Statistics of Datasets数据集 用户数量 物品数量 交互数量 Musical Instruments 60739 56301 133189 Toys and Games 313557 241657 784844 4.1.2 评价指标
在本文中与大多数推荐方法相同，我们采用常用的评价指标HR@K，NDCG@K，MRR@K来评价模型性能，其中K=5，采用交叉验证的方式验证模型性能，实验的结果为测试集中所有用户的平均指标.
4.1.3 基 线
我们将本文方法与以下最先进的序列推荐方法进行比较.
1）GRU4Rec[25]. 利用门控递归单元建模推荐中的会话序列信息.
2）Caser[26]. 是一种基于CNN的模型，应用水平和垂直卷积过滤器来捕获短期会话序列中的信息.
3）MIMN[34]. 利用多通道记忆网络学习序列行为中的用户多兴趣表征.
4）MIND[18]. 是一个利用胶囊网络捕获用户不同兴趣的多兴趣学习模型.
5）ComiRec[36]. 设计了胶囊网络和自注意力2种机制来提取用户的多兴趣特征.
6）SURGE[33]. 是序列推荐中的图神经网络模型，通过集群感知和查询图传播，从行为序列中融合用户的当前核心兴趣.
7）TGSRec[32]. 是一个考虑时序模式内时间动态的图神经网络模型.
8）MGNM[16]. 利用多层级图卷积神经网络和胶囊网络学习用户的多兴趣特征.
此外，我们还与本文模型的2个变体进行了比较来验证全局偏好模块和对比学习对模型性能的影响.
1）MIRec w/o global. 去除了用户偏好挖掘中的全局偏好的影响，仅利用局部视图进行对比学习.
2）MIRec w/o cl. 去除了对比学习任务，利用原始交互序列中的局部偏好和全局偏好信息进行推荐.
4.1.4 参数设置
为了公平比较，对比方法中的参数都与原论文的参数保持一致，并且取对比算法复现结果和原论文中效果最好的值. 本实验中， 在Musical Instruments数据集上学习率设置为0.005，Batchsize的值设为256. 在Toys and Games数据集上学习率设置为0.001，Batchsize的值为1024，嵌入大小 d 为16.
4.2 性能比较（针对RQ1）
我们在2个数据集上验证了本文模型的性能，实验结果如表2所示.
表 2 模型的整体性能比较Table 2. Overall Performance of the Models模型 Musical Instruments Toys and Games NDCG@5 HR@5 MRR@5 NDCG@5 HR@5 MRR@5 GRU4Rec 0.0619 0.1049 0.0478 0.0840 0.1278 0.0697 Caser 0.0955 0.1178 0.0883 0.0679 0.1012 0.0569 MIMN 0.0955 0.1509 0.0750 0.1158 0.1676 0.0988 MIND 0.1040 0.1422 0.0898 0.1015 0.1510 0.0824 ComiRec-DR 0.1091 0.1541 0.0943 0.1131 0.1597 0.0978 ComiRec-SA 0.0820 0.1204 0.0694 0.0665 0.0977 0.0563 SURGE 0.1056 0.1494 0.0913 0.0930 0.1353 0.0791 TGSRec 0.0946 0.1653 0.0729 0.1410 0.2027 0.1164 MGNM 0.1057 0.1658 0.1021 0.1611 0.2231 0.1408 MIRec（本文） 0.1377 0.1911 0.1201 0.1602 0.2236 0.1394 注：黑体数值表示本文模型达到最好的实验结果. 从表2可以看出，传统的递归神经网络方法GRU4Rec和卷积神经网络方法Caser在提取交互序列中的用户兴趣整体性能上表现较差. 考虑交互序列中具有多个兴趣的特点，通过胶囊网络、注意力机制等捕获多兴趣特征的方法，性能得到了明显的提升. 随着图神经网络的发展，在序列推荐中应用图神经网络方法使模型在性能上有了更显著的提升. 但是在MGNM方法提出之前，用户多兴趣学习的研究和图聚合方式的研究互相独立，MGNM将多兴趣研究和图神经网络结合起来，因此MGNM在所有指标上优于所有的传统序列推荐方法和基于图聚合的方法.
与MGNM相比，本文方法在学习用户的多兴趣时考虑了用户的序列内的局部偏好和用户间的全局偏好，并且考虑了序列间的时间间隔对模型性能的影响，实验结果表明，模型在Musical Instruments数据集上提升更为显著，优于所有基线模型. 在Toys and Games数据集上与MGNM相比，在HR@5指标上有微小提升，其余2个指标相差不大，而与其他多兴趣模型MIMN、MIND和图神经网络方法TGSRec相比，本文模型具有较大的提升，说明本文模型是有效的. 本文模型在2个数据集模型的性能具有一定的差异，主要是因为Toys and Games数据集中的物品和用户数量更大，而交互数量有限、数据更为稀疏，本文模型在处理稀疏数据集的方面还有一定提升空间.
4.3 消融实验（针对RQ2）
在本节中，我们探讨MIRec模型的全局偏好抽取模块对性能的影响和数据增强对模型性能的影响.
为了探究全局偏好抽取模块和对比学习损失的有效性，我们仅学习用户交互序列间的局部偏好信息，在2个数据集上的实验结果如表3所示.
表 3 各个模块的模型性能的影响Table 3. Effect of Each Module on Model Performance数据集 Musical Instruments Toys and Games NDCG@5 HR@5 MRR@5 NDCG@5 HR@5 MRR@5 MIRec 0.1377 0.1911 0.1201 0.1602 0.2236 0.1394 MIRec w/o global 0.1303 0.1812 0.1135 0.1548 0.2177 0.1341 MIRec w/o cl 0.1273 0.1768 0.1111 0.1296 0.1859 0.1112 注：MIRec w/o global表示去除全局信息模块；MIRec w/o cl表示去除对比学习任务. 从表3可以看出，当去除对比学习任务后，模型性能在各个指标上下降更为明显，在Musical Instruments数据集上下降约7.5个百分点，在Toys and Games数据集上下降16.8~20.2个百分点，说明本文提出的数据增强方法和对比学习机制能够缓解交互序列中时间间隔分布不均匀对建模用户兴趣的影响. 去除全局信息模块后，模型性能在Musical Instruments数据集上各个指标下降5.1~5.3个百分点，在Toys and Games数据集上各个指标下降2.6~3.3个百分点. 因此本文中提出的全局偏好模块和对比学习损失对模型性能均有效. 而去除全局信息模块后，在Toys and Games数据集上的影响不是特别明显的原因是该数据集的用户数量和物品数量更大，图卷积的邻接矩阵稀疏度更大，在聚合信息的过程中获取的有效信息较少，因此去除全局偏好模块后，对模型的性能影响没有那么明显.
4.4 模型的参数分析（针对RQ3）
在本节中，我们首先验证了用户交互序列中的兴趣数量对用户模型性能的影响，实验结果如图4所示，折线图中每个点对应的用户兴趣数量分别为I=2，I=3，I=4，I=5时NDCG@5，HR@5，MRR@5的值，条形图为不同序列长度分布的比例. 从图4中可以看出在2个数据集上都有相似的趋势，当用户兴趣数量I=4时，模型性能最好. 这是由于文中对于不同长度的交互序列的兴趣数量统一，当用户兴趣数量较小时，不能充分学习到长序列中的多个真实兴趣，当兴趣数量较大时，反而会影响短序列中的用户兴趣，用户兴趣较小或较大都会影响模型的性能，因此在本文中统一取I=4.
![]()
图 4 不同用户兴趣数量对模型性能的影响Figure 4. Impact of different numbers of user interest on the performance of models此外我们还从序列中物品替换的比例和对用户序列增强的比例2个方面来验证统一数据增强对模型性能的影响. 首先我们将序列中的物品按照 \mathrm{m}\mathrm{a}\mathrm{x}（int（\lambda \left|{s}_{u}\right|），1） 的比例来对序列中的物品进行替换， \lambda 表示替换率，实验结果如图5和图 6所示.
![]()
图 5 Musical Instruments数据集上 \lambda 对模型性能的影响Figure 5. Impact of \lambda on the performance of models on the Musical Instruments dataset从图5和图 6可以看出，在2个数据集上当 \lambda =0.1时，模型的性能最差，这是因为按照替换比例计算公式，对于小于20的序列数据中的替换数量均为1.而实际上，序列长度越长，交互序列中存在的较大时间间隔的概率越大，越有必要进行数据增强，而没有对交互序列中的数据进行充分处理会导致性能不佳；随着替换率 \lambda 的变化（\lambda 为0.2~0.7），与 \lambda =0.1时相比有了明显提升，且 \lambda =0.2 时模型表现最好，这时交互序列中长度小于10的序列数据替换数量为1，长度大于10的序列替换数量为2，说明这种数据增强方式符合大部分数据序列的分布. 当 \lambda > 0.2 时，模型的性能呈现波动，这是由于数据分布中（如图4中的直方图所示），约40%的交互序列的长度小于等于4，由公式计算的替换物品的数量皆为1，因此随着\lambda 的增加，在短序列中替换的物品数量没有变化. 随着\lambda 的增加，长序列的数据增强引起了性能的差异. 整体而言，无论以多少比例进行数据增强，实验结果均比去除对比学习模块的性能优越，因此进一步验证了对比学习模块的有效性.
![]()
图 6 Toys and Games数据集上 \lambda 对模型性能的影响Figure 6. Impact of \lambda on the performance of models on the Toys and Games dataset5. 结 论
本文提出了一个基于对比学习的多兴趣感知序列推荐模型，从序列内的局部偏好和序列间的全局偏好出发，通过对比学习机制更精准地获取用户的偏好信息，进而进行更精准的推荐. 通过消融实验验证了全局偏好模块和对比学习对于模型性能的有效性. 此外，利用胶囊网络学习融合用户全局偏好和局部偏好嵌入中的多兴趣表示，可以准确建模用户序列中的不同兴趣. 但是在本文中，用户交互序列中的兴趣数量是一个可训练的超参数，在未来将继续研究如何自适应交互序列中的兴趣数量以及模型在稀疏数据集上的扩展性.
作者贡献声明：赵容梅提出创新点，负责方法实现和论文写作；孙思雨辅助实验；鄢凡力负责文献调查和辅助写作；彭舰参与方法分析和论文修改；琚生根参与实验分析和论文修改.
-
表 1 常用符号
Table 1 Common Symbols
符号 说明 G 任意一张图或网络 E 图G中的边集 V 图G中的节点集 {G_{{v_i}}} 以节点vi为中心的星型图 {E_{{v_i}}} 图 {G_{{v_i}}} 中的边集 {V_{{v_i}}} 图 {G_{{v_i}}} 中的节点集 {e_{{v_i},{v_j}}} 从节点vi出发到vj的边 si,j 节点vi和vj间的相似度 V * 节点集 p1~p6 扰动概率 L1 数据截断长度 SN 相似度集合 Ti1, Ti2 用户i的部分边数据集合 {{\boldsymbol{B}}_{{v_i}}} 用户i的邻接位向量 cc 单个簇 δ 阈值 α 隐私预算分割比例 
下载: 导出CSV
表 2 计算代价
Table 2 Computation Cost
min 算法 数据集 Fediverse Government LastFm LF-GDPR-D 2.88 3.49 15.22 LDPGen 2.06 2.77 5.77 LDPCD 6.17 4.84 28.49 DGC-LDP（本文） 6.88 5.32 26.77
下载: 导出CSV
-
[1] Duchi J C, Jordan M I, Wainwright M J. Local privacy and statistical minimax rates[C] // Proc of the 54th IEEE Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2013: 429−438
[2] 叶青青,孟小峰,朱敏杰,等. 本地化差分隐私研究综述[J]. 软件学报,2017,29(7):1981−2005 Ye Qingqing, Meng Xiaofeng, Zhu Minjie, et al. Survey on local differential privacy[J]. Journal of Software, 2017, 29(7): 1981−2005 (in Chinese)
[3] Li Weiqing, Chen Hongyu, Zhao Ruifeng, et al. A federated recommendation system based on local differential privacy clustering[C] // Proc of the 7th IEEE Smart World, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Int of People and Smart City Innovation. Piscataway, NJ: IEEE, 2021: 364−369
[4] Liu Gaoyuan, Tang Peng, Hu Chengyu, et al. Multi-dimensional data publishing with local differential privacy[C] //Proc of the 26th Int Conf on Extending Database Technology. Berlin: Springer, 2023: 183−194
[5] 张少波,原刘杰,毛新军,等. 基于本地差分隐私的K-modes聚类数据隐私保护方法[J]. 电子学报,2022,50(9):2181−2188 Zhang Shaobo, Yuan Liujie, Mao Xinjun, et al. Privacy protection method for K-modes clustering data with local differential privacy[J]. Journal of Acta Electronica Sinica, 2022, 50(9): 2181−2188 (in Chinese)
[6] 朱素霞 ,王蕾 ,孙广路 . 满足本地差分隐私的分类变换扰动机制[J]. 计算机研究与发展,2022,59(2):430-439 Zhu Suxia, Wang Lei, Sun Guanglu. A perturbation mechanism for classified transformation satisfying local differential privacy [J]. Journal of Computer Research and Development, 2022, 59(2): 430−439 (in Chinese)
[7] Dwork C. Differential privacy[C] // Proc of the 33rd Int Colloquium on Automata, Languages, and Programming. Berlin: Springer, 2006: 1−12
[8] Ye Qingqing, Hu Haibo, Au M H, et al. Towards locally differentially private generic graph metric estimation[C] // Proc of the 36th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2020: 1922−1925
[9] Qin Zhan, Yu Ting, Yang Yin, et al. Generating synthetic decentralized social graphs with local differential privacy[C] //Proc of the 24th ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2017: 425−438
[10] Zhang Yuxuan, Wei Jianghong, Zhang Xiaojian, et al. A two-phase algorithm for generating synthetic graph under local differential privacy[C] //Proc of the 8th Int Conf on Communication and Network Security. New York: ACM, 2018: 84−89
[11] Wei Chengkun, Ji Shouling, Liu Changchang, et al. AsgLDP: Collecting and generating decentralized attributed graphs with local differential privacy[J]. IEEE Transactions on Information Forensics and Security, 2020, 15: 3239−3254 doi: 10.1109/TIFS.2020.2985524
[12] Yang Jingyu, Ma Xuebin, Bai Xiangyu, et al. Graph publishing with local differential privacy for hierarchical social networks[C] // Proc of the 10th IEEE Int Conf on Electronics Information and Emergency Communication (ICEIEC). Piscataway, NJ: IEEE, 2020: 123−126
[13] Sun Haipei, Xiao Xiaokui, Khalil I, et al. Analyzing subgraph statistics from extended local views with decentralized differential privacy[C] //Proc of the 26th ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2019: 703−717
[14] Imola J, Murakami T, Chaudhuri K, Locally differentially private analysis of graph statistics[C] // Proc of the 30th USENIX Security Symp. Berkeley, CA: USENIX Association, 2021: 983−1000
[15] Liu Zichun, Huang Liusheng, Xu Hongli, et al. PrivAG: Analyzing attributed graph data with local differential privacy[C] // Proc of the 26th IEEE Int Conf on Parallel and Distributed Systems (ICPADS). Piscataway, NJ: IEEE, 2020: 422−429
[16] Zhang Zhejian. LDPCD: A novel method for locally differentially private community detection [J]. Computational Intelligence and Neuroscience 2022, 2022: 4080047
[17] Fu Nan, Ni Weiwei, Zhang Sen, et al. GC-NLDP: A graph clustering algorithm with local differential privacy[J]. Computers & Security, 2023, 124: 102967
[18] Hou Lihe, Ni Weiwei, Zhang Sen, et al. Wdt-SCAN: Clustering decentralized social graphs with local differential privacy[J]. Computers & Security, 2023, 125: 103036
[19] Shamir A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612−613 doi: 10.1145/359168.359176
[20] Warner S L. Randomized response: A survey technique for eliminating evasive answer bias[J]. Journal of the American Statistical Association, 1965, 60(309): 63−69 doi: 10.1080/01621459.1965.10480775
[21] Wang Teng, Zhang Xuefeng, Feng Jingyu, et al. A comprehensive survey on local differential privacy toward data statistics and analysis[J]. Sensors, 2020, 20(24): 7030 doi: 10.3390/s20247030
[22] Yang Mengmeng, Lyu Lingjuan, Zhao Jun, et at. Local differential privacy and its applications: A comprehensive survey [J]. arXiv preprint, arXiv: 2008.03686, 2020
[23] Wang Tianhao, Blocki J, Li Ninghui, et al. Locally differentially private protocols for frequency estimation[C] //Proc of the 26th USENIX Security Symp. Berkeley, CA: USENIX Association, 2017: 729−745
[24] Erlingsson Ú, Pihur V, Korolova A. Rappor: Randomized aggregatable privacy-preserving ordinal response[C] //Proc of the 21st ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2014: 1054−1067
[25] Zhang Jun, Xiao Xiaokui, Xie Xing. PrivTree: A differentially private algorithm for hierarchical decompositions [C] //Proc of the 2016 ACM Int Conf on Management of Data. New York: ACM, 2016: 155−170
[26] Liu Shang, Cao Yang, Murakami T, et al. A crypto-assisted approach for publishing graph statistics with node local differential privacy [J]. arXiv preprint, arXiv: 2209.02231, 2022
[27] Kairouz P, Bonawitz K, Ramage D. Discrete distribution estimation under local privacy[C] //Proc of the 33rd Int Conf on Machine Learning. New York: ACM, 2016: 2436−2444
[28] Allard A, Serrano M, Boguñá M. Geometric description of clustering in directed networks [J]. arXiv preprint, arXiv: 2302.09055, 2023
[29] Rand W M. Objective criteria for the evaluation of clustering methods [J]. Journal of the American Statistical Association, 1971, 66(336): 846−850
[30] Vinh N X, Epps J, Bailey J. Information theoretic measures for clusterings comparison: Variants, properties, aormalization and correction for chance[J]. Journal of Machine Learning Research, 2010, 11: 2837−2854
计量
- 文章访问数: 184
- HTML全文浏览量: 35
- PDF下载量: 80
