Triangle Graph Interest Network for Click-through Rate Prediction
三角形图兴趣网络的点击率预测
来源：WSDM 2022
摘要：目前，许多现有的方法都试图从历史上的点击行为序列中提取用户的潜在兴趣，一些研究人员将项目-项目共现图作为一个辅助图。由于用户兴趣的难以确定性，这些工作仍然不能有效地确定用户点击行为的真正动机。此外，这些方法更偏向于流行的或类似的商品，它们缺乏打破多样性限制的有效机制。在本文中，作者提出了一种新的有效的框架：三角图兴趣网络(TGIN)。对于用户行为序列中的每个被点击的项目，作者在项目-项目图的邻域中引入三角结构作为补充。TGIN将这些三角形视为用户感兴趣的基本单位，它为捕捉用户点击一个项目的真正动机提供了线索。通过聚合几个兴趣单元的信息来描述每一个点击行为，可以缓解难以捉摸的动机问题。通过选择多样化的三角结构，TGIN带来了新颖的项目，以扩大用户兴趣的探索范围。在公共和工业数据集上进行的大量实验清楚地验证了我们的框架的有效性。
1 动机
现有的工作强调从历史点击的项目序列中发现用户的兴趣，这导致了难以捉摸的动机问题。一般来说，用户的兴趣是隐含的和难以捉摸的，而每个项目都有多个属性。很难确定用户单击一个项目的真正动机。例如，用户可能会因为裙子的颜色、材质或风格而点击它。然而，相关的工作缺乏一种捕获隐性用户兴趣的有效机制。此外，基于图嵌入的方法试图在项目-项目图中聚合邻域，以丰富项目表示，拓宽探索范围。然而，他们仍然面临着多样性限制的问题。对于一个特定的项目，其在项目-项目图中的大多数邻居都是相似的（如图1所示的情况）。
同时，作者使用阿里巴巴数据集来构建图表，并随机选择10万个项目。对于每个项目，将提取其邻域中的一组三角形。作者比较了每个三角形中涉及的三个项目的多个属性。这些属性包括品牌、卖家、商店、类别、以及关键字、价格、评论、星级和销售。作者计算了有多少个三角结构共享了属性，以及哪些属性被共享了。结果如图2所示。
因此，作者总结了推荐系统的项目共现图中三角形的两个特殊性质。1)三角形内的同质性。三角形中的三个项通常共享一些共同的属性。它可以反映出用户点击这些项目的真正动机。因此，三角形可以被看作是最基本的用户兴趣单元。与单项建模相比，三角形建模更有助于捕捉用户难以捉摸和隐含的兴趣。此外，在现实场景中，项目-项目共现图通常是大规模的，不可避免地有噪声。通过对三角形的建模，我们可以过滤掉孤立的项目，减少噪声，以提高用户兴趣提取的质量。2)三角间的异质性。不同三角形的共享属性是不同的。它们可以反映用户感兴趣的不同方面。各种三角形可以向用户介绍新颖而多样的商品。因此，用户可以获得更多的探索机会，扩大他们的兴趣。
2 定义
在推荐系统中，用户和项目之间通常会有一系列的历史点击。设U表示一组用户，I表示一组项。我们将用户点击表示为R={(𝑢，𝑖，B𝑢，𝑦)|𝑢∈U，𝑖∈I}。这里，B𝑢⊂I表示用户𝑢的历史行为（即交互过的项目列表）。𝑦∈{0,1}是向用户𝑢推荐项目𝑖时的隐式反馈，其中观察到用户𝑢点击项目𝑖时为𝑦=1，否则为𝑦=0。
定义一：（项目-项目共现图）：本文将项目-项目共现图定义为一个无向图G={V，E}，其中V为节点集，E为边集。𝑣∈V中的每个节点都表示一个项目。在实践中，为了构造一个项目-项目共现图，可以设置一个滑动窗口，并在所有用户的行为序列上滑动它。窗口内的每一对项目都通过一条无向边连接起来。每条边的权重被分配为两个连接项在所有用户行为中出现的总次数。
定义二：（三角结构）在项目-项共现图G={V，E}中，对于节点𝑣∈V，我们将其K阶(K>0)邻居节点的集合表示为V𝑣。对于三个节点𝑣0，𝑣1和𝑣2∈V𝑣，只有当（𝑣0，𝑣1），（𝑣0，𝑣2）和（𝑣1，𝑣2）∈E时，将𝑡𝑟=（𝑣0，𝑣1，𝑣2）定义为一个三角结构。此外，对于目标节点，由于不同距离的三角形的影响也不同，我们进一步引入了k阶三角形的定义
定义三：（k阶三角结构）：对于节点𝑣∈V，给定一个三角结构（𝑣0，𝑣1，𝑣2），如果从这三个节点到𝑣的最短距离为𝑘，那么我们将这个三联体定义为𝑣的k阶三角结构。
3 方法
效率
提取三角形是一个耗时的过程，特别是对于大规模的图形数据。然而，CTR预测作为一项实时任务，对效率有很高的要求。根据经验，对于一个特定的项目，在它附近的三角形有更强的影响。因此，论文中三角形只从每个项目的小尺度邻域中提取。以0阶三角形为例，对于共现图中的每个节点，作者对其所有的一阶邻居进行采样。然后，作者检查每对邻居节点是否可以与特定的项目形成一个三角形。也就是说，有必要判断每对之间是否有边缘。作者通过构造一个边的哈希图来解决这个问题，它可以将时间复杂度限制在O（1）。
3.1 三角结构选择策略
作者采用确定点过程(DPP)来建模相关但不同的三角形集的选择概率，该方法可以使得采样的三角结构更加均匀，方便获得更丰富的语义信息。关于DPP的详细原理及证明可以阅读：
通过“行列式点过程”让 GAN 生成更多样化的样本 - 知乎
这里简单说明一下：DPP的关键在于构造一个DPP kernel矩阵。它是一个 N×N（N即为点的总数） 的实对称方阵。 K 的元素 Kij 可以理解为第 i,j 个点之间的相似度，对角线上的元素Kii则表示点i被采样的概率（如果每个点被采样的概率相同，那么对角线上的值都应为1/N）。点i和j被采样的概率如下式所示：可以看出两个点相似度很高时，被采样的概率很小。
在本文中，作者把每个三角结构视为一个节点进行采样，定义,其中
表示该三角结构的特征向量，是通过平均三角形内三个节点的特征来计算得到的,
则表示三角结构的相关性得分，对于该得分，作者引入了三角形的内权和外权。内部权重是其三条边的平均权重。对于外部权值，作者将分母设为从三个内部节点到中心节点的距离之和，并将分子设为连接三个内部节点和中心节点的边权值之和。在此基础上，三角形相关性得分是内部和外部权值乘积的算术平方根。此外，如果特征向量x𝑖归一化，两个三角形之间的余弦相似度可以计算为
,则K矩阵可以被重写为：
作者在此基础上加入了超参数作为采样的核矩阵：
其中，是一个用来权衡相关性和多样性的超参数。
3.2 模型结构
3.2.1 Embedding Layer
在本文中，作者使用了四类特征：用户特征、用户历史行为、上下文和目标项目。它们分别用x𝑢、x𝑏、x𝑐和x𝑡表示。特别是，在用户历史行为中有多个项目。因此，它可以用来表示，其中𝐿是用户行为序列的长度，𝑑是项目嵌入的维数。此外，为了对用户兴趣的动态变化进行建模，作者还考虑了每个项目在用户行为序列中的位置。用户行为位置由
表示，其中pt是第𝑡个条目的位置编码。在三角结构被提取和选择之后，作者为用户行为序列中的所有项生成一组三角形。将节点表示以所有三角形进行叠加。因此，用户行为三角结构被表示为
，其中𝑛是每个item选取的三角形的数量。特别的，作者还为目标项目提取三角结构。目标项目三角结构表示为
。
3.2.2 Intra-triangle Aggregation Layer
作者使用三角结构来表示项目背后的潜在兴趣单位。具体来说，使用一个简单的池化操作来聚合三角结构内部的信息，并生成用户行为序列的表示：
其中，,Average表示平均池化操作。同理，目标项目的表示计算为：
其中，
3.2.3 Inter-triangle Aggregation Layer
在这部分中，作者将描述如何为用户点击的每个项目使用多头自注意聚合多个三角结构。具体来说，headℎ的输出计算如下：
其中，分别是进行查询的第ℎ个头、键和值的投影矩阵。因此，每个head代表一个子空间中的一个潜在的项目表示。然后将不同头部的向量连接起来，产生历史项目表示，可以定义如下：
对于目标项，也需要聚合多个三角结构来得到其表示。同样使用多头自我注意来得到目标项目的表示：
与以前使用单个项目特征的工作不同，作者聚合了多个三角结构来表示每个项目的潜在兴趣。因此，该模型可以确定用户的行为是否与目标项紧密匹配。
3.2.4 Behavior Refiner Layer
在实践中，下游任务受益于高质量的项目表征。因此，在获得项目表示之后，作者将描述如何进一步细化它。作者使用另一个与前一部分相同的多头自我注意来实现多个兴趣之间的互动：
同样，分别是用来查询、键和值的第ℎ个头的投影矩阵。作者将所有输出头向量{(ℎ𝑒𝑎𝑑‘1，head’2，…，head‘ℎ}作为矩阵
。
同时，作者用一个辅助损失用于监督更好的项目表征学习。它使用第（𝑖+1）个用户行为原始项目嵌入作为积极项来监督第𝑖个学习项目表示b𝑖。而消极的示例是从整个项目集中抽取的，不包括用户点击过的项目。在数学上，辅助损失的表述为：
3.2.5 User Behavior Modeling Layer
除此以外，作者从用户行为序列中提取位置特征，以捕捉用户兴趣随时间的转移趋势。提出了一种位置感知注意机制来计算用户在不同位置的行为对用户建模的重要性。具体来说，用户表示的每个用户行为的注意系数计算如下：
其中，为上面得到的目标项目的表示，B为上面得到的用户历史行为的表示，
为位置特征。最终得到的c表示注意系数的一个向量，里面的每一项都对应着一个聚合三角项目的注意力权重。请注意，用户行为中每个项的位置是在它发生时按时间戳排序的反向顺序。
考虑到每个行为的不同重要性，可以获得一个目标项的表示：
其中，b𝑗∈R𝑑为B的第𝑗行，它表示用户行为序列中第𝑙个项的三角结构聚合表示向量。
3.2.6 Multi-Level Interest Fusion Layer
不同阶的三角结构反映了不同的兴趣水平。因此，如前所述，对于用户的历史行为和目标项目，作者提取了多阶三角结构。对于每个阶𝑘，用户行为也可以以上述的方式获得，即记为v𝑘。考虑到它们对用户的不同重要性，作者将多层次的兴趣与注意机制相结合。作者将所有不同阶的用户行为表示堆叠为V。行为表示V对用户的注意系数可以计算为：
在此基础上，最终可以融合对学习表示的多层次兴趣。在数学上，最终表示的计算方法如下：
其中，v𝑘∈R𝑑表示从𝑘阶三角结构中学习到的表示。e𝑘∈R表示表示v𝑘对用户的重要性。
3.3 优化
作者将所有的特征向量连接起来，并输入到MLP层中进行最终预测。由于点击率预测任务是一个二元分类任务，因此选择损失函数作为交叉熵损失，通常定义为：
最终的损失定义为：
为平衡两个损失的超参数。
4 实验
4.1 数据集
前两个数据集为亚马逊数据集的子集。工业数据集为从阿里巴巴在线展示广告系统中收集为期30天的点击日志。
4.2 结果
4.3 消融实验
有三种策略来聚合每个用户的三角形信息和点击行为，包括MeanAgg、权重和注意力系数。它们分别代表平均池化、加权池化和注意力池化。同时还进行了辅助损失的消融实验，如下图所示：
