论文背景
本文提出了一种名为Swing的新算法，可以利用用户-商品行为图的内部结构（Swing）来构建替代产品图。Swing是一种准局部结构，设计得比传统的协同过滤方法中使用的单个边更加稳定。它在用户-商品二分图上提供了更可靠的计算传播，并有助于减少嘈杂的用户行为数据的影响。然后，文章提出了一种名为Surprise的新算法来构建互补产品图。Surprise算法通过利用产品的类别信息和基于Swing算法构建的产品簇来解决用户共购图的稀疏性问题。此外，它考虑了共购产品的时间敏感性和时间顺序。这两种方法都可以与常用的大规模分布式计算框架（如MapReduce或Spark）并行运行，因此可扩展性不是一个问题。基于此在淘宝上构建产品替代图和产品互补图，为进一步的推荐排序模块生成候选产品提供基本索引服务。
相关性产品索引主要包含两部分：替代性产品和互补性产品。不同种类的衬衫构成了替代关系，而衬衫和风衣裤子等构成了互补关系。用户通常希望在完成购买行为之前尽可能看更多的衬衫，而用户购买过衬衫之后更希望看到与之搭配的单品而不是其他衬衫了。
传统相似度度量方法的不足
考虑余弦相似度与杰卡德相似度，具体计算公式不再赘述。
在余弦相似度与Jaccard相似度中，分子表示共同点击了商品i与商品j的用户集合，越多用户共同点击了这两个商品，则在某种程度上，这两个商品的相似度越高。分母表示对点击的用户数量进行惩罚，越多用户点击了商品i，说明商品i的热度越高，所以分母可以防止热门商品都非常相似。
考虑下面这个图（来源于论文）：
下图展示了点击商品h的用户集合，以及这些用户点击的其他商品，大写字母代表用户，小写字母表示商品，图中的边表示点击关系。其中=5，
分别表示共有5个用户点击了商品h，15个用户点击了商品t，以此类推。
根据余弦相似度的计算公式，我们可以得到各个商品与商品h的相似度排序为：t>z>p>q。然而我们可以比较清晰的看到，只有一个用户A共同点击了商品h和z，所以其实商品z和商品h并不是很相似。这是由于点击商品z的用户较少，所以其分母的点击惩罚较小。也就是说在某些情况下，余弦相似度并无法很好地评价商品之间的相似度。
基于余弦相似度，杰卡德，皮尔逊相关系数等的协同过滤算法在计算关联强度的时候只关注于Item-based（因为item相比于用户变化的慢，且新Item特征比较容易获得），一般只关注于Item-User-Item的路径，而忽略了User-Item交互中的大量噪声，推荐精度存在局限性。
并且，存在对互补性产品建模不足的问题，可能导致用户购买手机以后还继续推荐手机，但是用户短时间内不会再继续购买手机，产生了无效曝光的问题。
Swing算法
Swing通过利用User-Item-User路径中所包含的信息，考虑User-Item二部图中的鲁棒内部子结构计算相似性。例如参考下图：
图中红色四边形就是一种Swing子结构，这种子结构可以作为给王五推荐尿布的依据。
Swing结构
在使用传统相似度度量方法计算两个商品之间的相似度的时候，本质上是基于以下假设：当一个用户共同点击商品 与商品
的时候，就可以认为这两个商品间存在一定的相似性。 这其实是在使用一种item-User-item的结构来计算相似度。
Swing论文作者认为上述约束条件还不够强烈，于是提出了另外的一种假设：当两个用户共同点击商品 i 和商品 j 时，判断这两个商品相似的置信度更高。
Swing算法中，作者关注的是两个用户和两个商品形成的四边形结构，如上上图中的节点h，A，B，p构成了一个四边形，作者认为这种四边形结构能够更好地刻画两个商品的相似度，并且关系更加稳固，受到点击噪音的干扰更加小。
为了计算种子商品（上上图中的h）与其他商品的相似度，作者首先找出所有点击过种子商品的用户，并且找出这些用户点击过的其他商品，构建二部图。实际上，Swing结构是一种user-item-user结构，对于用户B和用户C，他们都共同点击了种子商品h，并且还点击了商品p，则B、p、C三者构成了一个swing结构<B,p,C>。基于上述四边形的假设，我们可以合理地认为商品h和商品p之间是存在一定的相似关系。如果在二部图中，商品p存在越多这种swing结构，则说明越多用户共同点击了h和p这两个商品，它们之间的相似关系就越牢固。
Swing结构的通俗解释：
若用户 u 和用户 v 之间除了购买过i外，还购买过商品 j ，则认为两件商品是具有某种程度上的相似的。也就是说，商品与商品之间的相似关系，是通过用户关系来传递的。为了衡量物品 i 和 j 的相似性，比较同时购买了物品 i 和 j 的用户 u 和用户 v， 如果这两个用户共同购买的物品越少，即这两个用户原始兴趣不相似，但仍同时购买了两个相同的物品 i 和 j， 则物品 i 和 j 的相似性越高。
Swing权重
如果仅仅直接计算二部图中包含商品p的swing结构数量作为商品h与商品p的相似度，这样是直接将所有swing结构的权重置为1，显然是不合理的，我们需要对swing里面的用户共同点击行为进行惩罚。
例如对于swing结构<B,p,C>，如果除了商品p外，用户B和用户C还共同点击了非常多其他的商品，我们有理由认为这两个用户的点击意图不是非常明确，swing结构<B,p,C>就不能很好地刻画h和p之间的相似度，这个swing权重就应该低一些。
除此之外，如果商品h和p都是热门商品，则共同点击这两个商品的用户就会非常多，此时二部图中包含商品p的swing结构的数量就会非常多。如果不对swing的权重进行惩罚，就会导致热门商品的相似度都非常高，这显然是不合理的。
因此，考虑以上因素，需要对swing结构的权重进行动态计算，对于上述二部图中的swing结构<B,p,C>，其权重计算公式为：
当用户B和用户C共同点击的商品数量越小，则点击目的越明确，swing结构的权重就越大。这就缓解了用户随意点击，或者无目的点击热门商品带来的噪声干扰。
Swing相似度
对于商品i与商品j，只需要将所有swing结构的权重求和就得到了i与j之间的相似度得分，公式如下：
其中，表示点击过商品i的用户集合，
表示用户u点击过的商品集合，
表示平滑因子。这个公式本质上是在计算点击过商品i与商品j的所有用户对的swing结构的权重之和。
在上述相似度的基础上，还可以对活跃用户进行惩罚，本质上就是对用户的点击次数进行惩罚，作者认为：用户点击次数越多，其目的就越不明确。最终Swing相似度计算公式如下：
其中：
Surprise算法
Swing算法主要用于寻找可替代产品，Surprise算法主要用于通过挖掘用户购买数据以寻找互补产品。为了寻找互补关系，利用采购数据寻找候选产品，为此需要考虑产品的时间敏感性以及数据稀疏性问题。
首先在行为相关性中引入连续时间衰减因子，然后引入了一种基于用户点击数据的聚类方法来解决数据稀疏性问题，而不是使用存在于高维空间且不同类别之间差异很大的内容信息。
需要注意的是，尽管用户购买数据是稀疏的，但是用户点击等隐式反馈数据并不是那么稀疏。
类别级别的相关
为了找到与用户购买的种子商品相关度最高的产品，
首先尝试在产品分类中找到相关度最高的类别，这种方法通常用于电子商务系统。这就排除了绝大多数源自用户购买行为的案例。
通过将每个条目映射到它的类别，我们得到一个用户类别矩阵。然后使用标准的协同过滤技术来计算类别之间的相关性。cj是ci的一个相关范畴的概率定义如下:
是购买过i后购买j类的数量，
为购买j类的数量。
由于类别之间的差异很大，计算每个类别的相对下降分数：
选择在最大相对落点之前排名的类别作为的top-related类别。
例如图(a)中T恤的相关类选择前八个，图(b)中手机的相关类选择前三个。
商品级别的相关
商品层面的相关性挖掘主要有两个关键性设计：
1）商品的购买顺序是需要被考虑的，例如在用户购买手机后推荐充电宝是合适的，但是在用户购买充电宝后推荐手机是不合理的。
2）两个商品购买的时间间隔也需要被考虑在内，时间间隔越短，表明两个商品之间互补关系越强。
最终商品层面的互补相关性被定义为：
式中，是
的相关类别（从类别级别的相关中得到的），且
，也就是说
的购买时间要晚于
的购买时间。
聚类层面的相关
即使在用户购买i后继续购买了j，假设仍不能确定j与i很匹配。而如果几个用户都出现了相同的购买行为，那么对j与i相关的确信度会大大提高。
在选择候选item时，作者还引入了（i，j）共现数的阈值。
例如，在购买物品i后进行推荐时选择 的候选物品。但是这种约束会进一步带来数据稀疏性的问题。
考虑另一种情况，Bob在i之后买了j, David在i之后买了k，同时物品j和物品k非常相似，例如它们都是蓝色的levis牛仔裤。这种共同购买是关于产品关系的信息。这也促使我们在聚类层面计算物品的相关分数，这有助于缓解物品层面共同采购的数据稀疏性问题。
标签传播聚类算法：
传统的聚类算法（基于密度或者k-means）在数十亿产品规模下的淘宝场景中是不可行的，所以作者采用了标签传播算法。
对于每个item，通过Swing算法计算得到的顶部相似的item被添加为该item的邻居，并使用一个从相似item指向种子item的定向链接。将边的权值设置为相似度得分.
最初将每个项目节点的标签设置为其节点id,p(.)表示当前邻居节点对应标签所属的概率。对于每个项目节点，在基于边权值更新标签概率时考虑其所有邻居，然后基于一定的概率为项目节点选择概率值最大的标签。
聚类层级的相关性计算：
其中，s1按前面描述的公式计算。也就是说计算了一个相关性分数，即购买项目簇L(j)发生在项目簇L(i)之后。
在得到两个相关分数之后，将它们进行线性组合得到最后的相关分数：
其中=0.8是作者设置的权重超参数.
Surprise算法通过利用类别信息和标签传播技术解决了用户共同购买图上的稀疏性问题。