基于二部图网络的电商平台智能化推送算法研究

Research on Intelligent Push Algorithm of E-Commerce Platform Based on Bipartite Graph Network

摘要: 在电商平台领域，大多数推荐算法都是基于用户–物品二部图网络(BGN)。但是这种推荐算法在准确性和多样性上严重不足。本文提出了一种基于BGN链接预测的电子商务推荐算法。首先，将所有用户项数据导入距离公式，计算属性之间的相似度；然后，将BGN投影到单模网络(SMN)中，提高了从BGN中提取潜在链路的效率。在此基础上，根据相似性对潜在链接进行预测。通过在真实电子商务数据集上的实验，证明了我们的算法比典型的推荐算法具有更高的准确率和覆盖率。

Abstract: In the field of e-commerce platform, most recommendation algorithms are based on user-item bipartite graph network (BGN). However, this recommendation algorithm is seriously insufficient in accuracy and diversity. In this paper, we propose an e-commerce recommendation algorithm based on BGN link prediction. Firstly, all user item data were imported into the distance formula to calculate the similarity between attributes. Then, the BGN was projected into a single mode network (SMN), which improved the efficiency of extracting potential links from the BGN. On this basis, the potential links are predicted based on the similarity. Through experiments on real e-commerce data sets, it is proved that our algorithm has higher accuracy and coverage than typical recommendation algorithms.

1. 引言

电子商务的繁荣带来了大量的网上购物数据。然而，这些数据大多是高度冗余的，从而降低了用户的检索效率。这不仅抑制了用户的满意度，也给电子商务网站带来了巨大的负担。传统的推荐算法已被亚马逊和淘宝等电商巨头广泛采用。然而，传统推荐系统中的大多数推荐算法面临两个问题：(1) 用户之间的独立性假设忽略了用户之间的现实社会关系；(2) 算法虽然具有较高的精度，但不能输出足够多样化的解，也不能克服冷启动问题的约束。

许多现实世界的问题都可以被建模为一个复杂的网络 [1] ，其中每个节点代表问题的一个实体，每个链路代表两个实体之间的关系。复杂和大规模的问题可以用二分图网络(bipartite graph network, BGN)来描述 [2] 。即顶点集可以划分为两个不相交的子集，图中每条边上的两个顶点都属于这两个不相交的子集，并且这两个子集中的顶点不相邻。因此，BGN极大地扩展了描述复杂网络模型的构建能力及应用场景。在某些特殊情况下，如果我们需要研究二部图中同类节点之间的连接关系，最常用的方法是投影法，它将二部图网络中的一种节点投影到另一种节点上。

目前最流行的推荐算法主要有协同过滤推荐算法 [3] [4] 、基于内容的推荐算法 [5] [6] 、组合推荐算法 [7] [8] 和基于网络的推荐算法 [9] [10] [11] 。协同过滤推荐算法在大型稀疏数据集上表现不佳。为了解决这一问题，Yu等 [12] 提出了一种概率矩阵分解模型，该模型仅基于现有的用户–物品矩阵评分数据来预测未知物品的用户评分。Cui等 [13] 提出了一种新的奇异值分解(SVD)模型，降低了用户项矩阵的稀疏性。Jiao等 [14] 加入隐式反馈来改进SVD模型，并将用户浏览、用户评分、商品浏览、商品评分的历史数据作为新的参数处理。但是，以上方法都假设用户是相互独立的，没有考虑到用户之间的社会关系。因此，利用用户之间的社会关系来提高推荐系统的质量对推荐算法来说是非常重要的。Belkhadir等 [15] 通过概率矩阵分解提出了一种通过共享的用户潜在特征空间将社交网络与用户–物品评分矩阵连接起来的推荐算法，并通过实验证明了该算法在用户评分很少或没有评分的情况下比流行的推荐算法效率更高。Bin等 [16] 将社交网络中的多重关系集成到协同过滤推荐算法中，大大提高了推荐的准确率。为了克服数据稀疏性，Wu等 [17] 提出了一种概率因子分析框架，通过一个社会参数集将每个用户的偏好与其朋友的偏好融合在一起。受传播理论的启发，Tian等 [18] 在BGN中设计了一种基于质量扩散的智能推荐算法，并证明了该算法具有较高的推荐准确率和多样性。

基于BGN的推荐算法将项目和用户组建模为节点，将项目–用户关系视为链接，并在现有的基础上预测网络的潜在链接。潜在链接是用户可能感兴趣的项目。大多数基于BGN的推荐算法向用户推荐流行的商品，但没有向用户推荐足够多的不流行的商品。因此，该建议严重缺乏多样性。这是因为基于BGN的推荐算法只考虑数据集中的强关系，而不关注弱关系或隐藏信息。

组合推荐算法一般是将两种互补的推荐算法组合在一起，提高了推荐系统的推荐精度和覆盖率，但组合推荐算法的计算效率较低，数据推送的实时性不足。为了解决上述问题，本文将BGN投射到一个单模网络(SMN)。SMN的链路中保留了BGN的强弱关系，同时考虑了相邻节点的数量、共同相邻节点的程度和节点的程度。然后，利用增强加权SMN对原始数据集的冗余信息进行过滤。过滤减少了SMN中的信息量，提高了链路预测的效率。

2. 二部图BGN算法

2.1. BGN算法概述

BGN能够被描述为 $G_b=\left(U,I,E\right)$ ，其中U，I是两组不相交的节点， $E⊑\left|U\right|\times \left|I\right|$ 是链接的集合。 $u\in U$ 节点和 $i\in I$ 节点之间存在链路，但是同一节点集中的节点之间没有链路。此外，I中节点相邻节点集通常表示为N(I)。BGN也可以表示为矩阵 $\left|U\right|\times \left|I\right|$ 。假设n和m分别为集合U和集合I中的节点数。则矩阵G_b可以表示为一个 $m\times n$ 维邻接矩阵。BGN的G_b的矩阵元素 $a_{ij}$ 和对角矩阵 $\hat{A}$ 可以分别定义为如下所示：

$a_{ij}=\{\begin{array}{l}1,\text{if}\left(u_i,v_i\right)\in E\\ 0,\text{otherwise}\end{array}$ (1)

$\hat{A}=\left[\begin{array}{cc}{0}_{m\times n}& A_{m\times n}\\ A_{m\times n}^{\text{T}}& 0_{n\times m}\end{array}\right]$ (2)

公式中 $0_{m\times n}$ 和 $0_{n\times m}$ 分别为 $n\times n$ 和 $m\times n$ 的全零矩阵， $a_{n\times m}$ 是一个非零矩阵。这意味着邻接矩阵是对称的。因此BGN的G_b可以用 $A_{n\times m}$ 来进行描述，U集合的每一行和每一列表示集合I的一个节点。

2.2. BGN投影

BGN链路预测的目的是发现网络中不存在但将来会出现的链路。假设 $G_b=\left(U,I,E\right)$ 是时刻t的一个BGN，那么，链路预测的任务就是预测时刻 $t+1$ 时网络中的一条新链路。现有的BGN链路预测算法首先将二部图映射为单部图，然后定义潜在边的概念。预测算法的复杂度较高。本文定义了潜在链路所覆盖的模式和模式的权值，计算了潜在链路所覆盖模式的权值对潜在链路的可信度，并将其作为实际链路在潜在边上的得分，使得二元网络链路的预测只在选定的潜在边上进行，大大降低了预测算法的复杂度。BGN分析的一般做法是通过投影将网络转换为SMN。投影网络具有典型的SMN结构。为了预测BGN的潜在联系，本文首先将BGN投影到两个SMN中。SMN的定义如下。

假设 $G_b=\left(U,I,E\right)$ 为BGN，同时 $\left|U\left(G\right)\right|=m$ ， $\left|I\left(G\right)\right|=n$ 。然后将BGN的两个节点集合U和I转换为两个SMN，即SMN的 $G_u=\left(U,E_u\right)$ 和 $G_v=\left(I,E_v\right)$ 可以表示为如下公式：

$\begin{array}{l}{E}_u=\left\{\left(u_i,u_j\right)|u_i,u_j\in U,|\exists v_i\in I,v_i\in \Gamma \left(u_i\right)\cap \Gamma \left(u_j\right)\right\}\\ E_v=\left\{\left(v_i,v_j\right)|v_i,v_j\in I,|\exists u_i\in U,u_i\in \Gamma \left(v_i\right)\cap \Gamma \left(v_j\right)\right\}\end{array}$ (3)

这种转换可能会牺牲原有网络的一些拓扑信息。为了防止信息丢失，本文设计了加权BGN，并通过加权SMN投影将其转化为加权SMN。在加权SMN中，每条链路的权值代表共同相邻节点的个数。

对于BGN的 $G_b=\left(U,I,E\right)$ ，每个 $E_u$ 或者 $E_v$ 环节用函数W加权：

$\begin{array}{l}{E}_u=\left\{\left(u_i,u_j\right)|u_i,u_j\in U,|\exists v_i,v_i\in \Gamma \left(u_i\right)\cap \Gamma \left(u_j\right)\right\}\\ W:\left(u_i,u_j\right)\to \left|\Gamma \left(u_i\right)\cap \Gamma \left(u_j\right)\right|\\ E_v=\left\{\left(v_i,v_j\right)|v_i,v_j\in I,|\exists u_i,u_i\in \Gamma \left(v_i\right)\cap \Gamma \left(v_j\right)\right\}\\ W:\left(v_i,v_j\right)\to \left|\Gamma \left(v_i\right)\cap \Gamma \left(v_j\right)\right|\end{array}$ (4)

其中， $W\left(u_i,u_j\right)$ 表示第i个节点与第j个节点之间的权值。对于SMN， $W\left(u_i,u_j\right)$ 可以定义为 $\Gamma \left(u_i\right)\cap \Gamma \left(u_j\right)$ 的公共相邻节点数。由于SMN是由真实数据构建的，因此每个SMN都包含大量冗余信息，这对潜在链路的预测有不利影响。因此，有必要通过过滤冗余链路来简化网络并提高预测质量。设计了一种骨干网提取算法，将加权SMN转换为增强SMN。增强的SMN可以定义如下描述。

对于 $G_b=\left(U,I,E\right)$ ，两个SMNs的 $G_u=\left(U,E_u\right)$ 和 $G_v=\left(I,E_v\right)$ 。若权重 $W\left(a,b\right)$ 大于a和b之间的链接，则链接 $\left(a,b\right)$ 应保留在加强后的网络中；否则链路将被过滤为冗余信息。

2.3. BGN链路预测

本研究的关键工作是从由物品、用户和评分组成的BGN中提取基本信息。具体来说，利用一个大型真实数据集构建了一个复杂的BGN，并为该网络设计了链路预测方案。所提方法流程图如图1所示，其中包括基本信息提取模型。当前BGN的潜在链路预测是另一项关键任务。该方法首先从网络数据库中提取二部图的补充属性信息，然后建立二部图的网络拓扑结构，并对其进行训练和测试。最后，利用二部图的加权投影构造了链路预测算法。

Figure 1. Flow diagram of the proposed method

图1. 本文方法流程图

通过增强BGN投影，提取BGN的潜在链接，并基于相似度对潜在链接进行预测。首先，通过挖掘电子商务大数据建立BGN。然后，将BGN转换为加权的SMN。最后，将每个SMN转换为增强的网络 $E{N}^t$ 。

在每个SMN中，检测一个具有内部节点对属性的节点对，以预测潜在的链路 [17] 。该方法可以减少预测链接的数量，提高预测质量。如果BGN G_b中的两个节点相互作用，则它们之间可能存在潜在的链接;如果两个节点没有共同的相邻节点，它们之间就不太可能存在潜在的链接。

对于BGN的 $G_b=\left(U,I,E\right)$ ，两个投影SMNs可以描述为 $G_u^t=\left(U,E_u^t\right)$ 和 $G_v^t=\left(I,E_v^{\alpha }\right)$ 。如果 $a\in U$ 是SMN $G_u^t=\left(U,E_u^t\right)$ 的节点，则节点a存在潜在链路的概率表示为如下所示。

$P{L}_a=\{N\left\{{\left({\Gamma }_a\right)}_{\text{train}}\right\},N=\Gamma \left(N_1\right)\cup \Gamma \left(N_2\right)\cup \cdots \cup \Gamma \left(N_n\right)$ (5)

其中，N代表训练后的BGN中节点 ${\Gamma }_a^{\alpha }$ 的相邻节点。其次，节点a是SMN $G_u^t$ 的一部分， $\Gamma \left(N_n\right)$ 是节点 $N_n$ 在BGN中邻近节点。 $P{L}_a=\left\{p|p\in N\wedge p\notin {\Gamma }_A,\left(a,p\right)\right\}$ ； $PL=P{L}_a\cup P{L}_b\cup \cdots \cup P{L}_m$ 代表预测的潜在节点，具有潜在链接的节点必须满足：

${\Gamma }_U\left(a\right)\cap \Gamma \left(p_i\right)\ne \varnothing \text{and}{}_i\notin \Gamma \left(a\right)$ (6)

在公式10中， $a\in U$ 和 $p_i\in I$ 是两个节点，且 $\left(a,p_i\right)\notin E$ 。

假设 $G_{\text{train}}$ 是一个训练好的BGN， $G_u^t$ 是一个SMN的u投影。对于每个潜在链接 $q\in {\left({\Gamma }_U\left(a\right)\right)}_{\text{train}}\cap \Gamma \left(p_i\right)$ 是潜在链接覆盖的模式。潜在链接所覆盖的模式数量越多，潜在链接成为真实链接的概率就越高。因此，潜在链接所覆盖的模式的数量可以衡量潜在链接的概率。潜在链路覆盖模式越多，网络中潜在链路覆盖的各链路权重越重要。设 $G_u=\left(U,E_u\right)$ 是BGN $G_b=\left(U,I,E\right)$ 在G_u和 $\left(a,b\right)\in E_u$ 之间链接投影到SMN上的权重。然后权重 $w\left(a,b\right)$ 能够被计算为如下所示：

$w\left(a,b\right)=\frac{2}{D_a+D_b}{\displaystyle {\sum }_{\tau \in \Gamma \left(a\right)\cap \Gamma \left(b\right)}\frac{1}{D_c}}$ (7)

其中D_a，D_b和D_c分别为节点a，b，c在BGN G_b中的度； $\Gamma \left(a\right)$ 和 $\Gamma \left(b\right)$ 是BGN中节点a和节点b的相邻集合。可以看出节点a和b的共邻度越小，则该模式的权重越大。

2.4. BGN总评价计算

每个模式元素被潜在链接覆盖的概率等于被潜在链接覆盖的模式的总权重。由此，最终总评价潜在环节 $\left(a,p_i\right)$ 可以通过以下方式计算：

$S\left(a,p_i\right)={\displaystyle {\sum }_{a,b\in \Gamma \left(a,p_i\right)}w\left(a,b\right)}$ (8)

公式12中，a，b表示网络中的节点。由上式可知，高权重模式的潜在链接数与链接预测概率呈正相关。因此，潜在链路覆盖率的模式权重之和就是潜在链路预测的最终值。综上所述，该方法的实现过程如下：从原始数据集中获得包含弱关系的投影SMN，滤除冗余信息，提取骨干网络。然后，根据初始化单模SMN中的高频链路权重，根据预定义的阈值对骨干网进行增强。该方法有效地对潜在链路集进行缩放，减少了总体计算时间，并维护了具有强关系的节点。

3. 实验环境与结果分析

3.1. 实验环境与评价指标

本文在一台Intel(R) Core(TM) i7-11700kF CPU、RTX 3080 GPU、Ubuntu18.0操作系统的计算机上进行实验。本文的实验使用了两个数据集：FilmTrust和Epinions [19] 。这是两个标准化的推荐系统测试数据集。FilmTrust是来自FilmTrust网站的用户–项目评分的集合，涉及35,497个评分，1642个用户和2071部电影。评分在0.5到4之间。Epinions是来自Epinions.com的用户项目评级的集合。该数据集涵盖40,290个用户和139,728个项目。评分标准为5分。在这里，从Epinions数据集中随机选择6000个用户和12,000个项目作为测试集。两个数据集的基本信息如表1所示。

Table 1. Basic information of FilmTrust and Epinions datasets

表1. FilmTrust和Epinions数据集基本信息

采用平均绝对偏差(MAE)衡量推荐准确率：

$\text{MAE}=\frac{{\displaystyle {\sum }_{i=1}^W\left|c_i-c_p\right|}}{W}$ (9)

在公式7中c_p表示第i项的预测评分；c_i为第i项的实际评分，W是数据集中的评级数。MAE越小，推荐准确率越高。

推荐覆盖率是很亮推荐算法性能的另一个重要指标，可以通过以下方式进行计算：

$R_C=N/\left|Q\right|$ (10)

在公式14中，N代表预测评分个数， $\left|Q\right|$ 是数据集中评级的总数。R_C值越高，推荐算法的性能越好。推荐算法的整体性能可以用指标F1来评价，其公式如下所示：

$\text{F}1=\frac{2\times \text{precision}\times R_C}{\text{precision}+R_C}$ (11)

其中，precision的定位为： $\text{precision}=1-\text{MAE}/\left(c_{\max }-c_{\min }\right)$ ，c_max和c_min分别死推荐算法中的最高平分和最低平分。

3.2. 实验部分

Figure 2. MAEs of different algorithms on Epinions dataset

图2. 不同算法在Epinios数据集上的MAE值

Figure 3. RC values of different algorithms Epinions dataset

图3. 不同算法在Epinios数据集上的RC值

Figure 4. F1 values of different algorithms on Epinions dataset

图4. 不同算法在Epinios数据集上的F1值

在本文的实验中，将提出的算法与不同类型的推荐算法进行了比较：协同过滤推荐算法(CF) [20] 、基于信任的推荐算法(MT) [21] 、基于内容的推荐算法(TCF) [5] 、CF-社会关系合并推荐算法(Merge) [22] 。此外，本文还选择了两种基于BGN的推荐算法作为对比方法：实时构建全加权二部(RTCF) [23] 和多视图二部网络(MV) [24] 。图2~4比较了不同算法在Epinions数据集上的性能。

以上结果表明，该算法在大数据集上的推荐准确率和覆盖率都高于其他类型的推荐算法，也超过了其他基于BGN的推荐算法。相比之下，基于BGN的算法优于其他类型的算法。主要原因是RTCF、MV和本文提出的算法建立了一个全面的BGN，保留了大量数据集的信息。然而，在其他类型的算法中，为了提高计算效率，数据集的很多信息都是通过预处理过滤掉的。

图5~7比较了不同算法在FilmTrust数据集上的性能。以上结果表明，本文提出的算法在推荐准确率和覆盖率上都优于其他类型的算法，并且也比另一种基于BGN的算法MV实现了更好的性能。在相同的硬件条件下，该算法所需的时间比RTCF和MV算法减少了约15%。

对比上述两组实验结果，本文算法在小数据集上比在大数据集上准确率更高。这是因为我们的算法在提取BGN投影的骨干网时过滤了冗余信息。如果原始数据集很大，过滤操作需要去除过多的冗余信息，这些信息可能会影响链路预测的准确性。当然，在大数据集上，我们的算法仍然比其他推荐算法更准确。

Figure 5. MAEs of different algorithms on FilmTrust dataset

图5. 不同算法在FilmTrust数据集上的MAE值

Figure 6. RC values of different algorithms on FilmTrust dataset

图6. 不同算法在FilmTrust数据集上的RC值

Figure 7. F1values of different algorithms on FilmTrust dataset

图7. 不同算法在FilmTrust数据集上的F1值

4. 总结

当推荐系统处理大数据时，大多数推荐算法只考虑数据集中的强关系，而不能识别弱关系或隐藏信息。这种策略确实可以提高推荐的准确性。但推荐结果将缺乏多样性。为了解决这一问题，本文提出了一种基于BGN投影的增强加权SMN来提取骨干网，过滤原始数据集的冗余信息，并保留强弱关系。通过在两个真实数据集上的实验，证明了该算法在大小数据集上都优于其他类型的推荐算法和其他基于BGN的推荐算法。在未来的研究中，将更加注重提高推荐的准确性和多样性。