新零售智能引擎事业群出品

背景

图可以用来描述事物之间的普遍关系，并把它们编码在参数化的图结构里（如邻接矩阵）。基于专家的构图方法需要昂贵的人工信息，很难快速部署到广泛的生产生活中，也就推动了基于数据驱动的图生成算法的研究。后者拟构造一张可以最好地描述输入数据产生过程的图，比如推荐场景中，数据可以是用户的购物记录，商品网络图表达物品之间的关系强度。由于基于数据驱动的算法严重依赖数据的条件独立性假设，也即训练场景和测试场景有同样的数据分布，一旦独立性假设遭到破坏，图的表现性能就会大打折扣。然而独立性假设在现实中是十分脆弱的，数据采样的过程也一定存在时间和间的局限性。比如，线上购物的用户中，通常女性比男性比例多，青年人比老年人比例多，那么学出来的图就会产生对年轻女性的偏好，对其他群体则不太友好。所以如何提升图结构的泛化性能是非常有实践意义的课题。

挑战

虽然学习因果图可以直接抓取事物之间的不变的因果关系、带来稳定性，但是学因果图的计算复杂度很大、很难拓展到大规模的网络中，而且因果图自身是有向无环图，也不能描述场景中广泛的有环结构。另一方面，图结构中包含复杂的高阶和非线性关系，直接在原始图结构空间（如邻接矩阵）修正偏差是很困难的，而且用于生成图结构的输入数据（如集合类型）是高维稀疏的。为了学习稳定的一般性图结构，本文提出了一种从多异质环境中学习稳定图结构的方法 SGL。

模型

为了针对更加普遍的场景，我们假设输入数据类型是高维稀疏的集合数据类型。一条集合数据的产生可以理解为从空集开始，一步一步向集合中添加元素，直至集合达到饱和的过程。对第 m 个数据环境，每次添加时，给定当前集合 s，各个元素 IkIk 加入的概率是集合的条件生成概率 p(m)(Ik|s)p(m)(Ik|s)。显然， pm I |s p I |s ( k ) m( k )和 图结构 G(m)G(m) 包含的元素关系有关，可表示成：

由于各个异质环境存在采样偏差，其相应的条件生成概率也是有偏的。假设环境的选择是随机的，那么平均各环境的概率空间就是对无偏环境的估计。

由于图结构中充满了高阶和非线性的关系，直接在图结构的参数空间（邻接矩阵）去偏差是很难的，如果我们可以建立图结构到条件生成概率的映射，通过在生成概率空间平衡偏差，就能间接修正图结构的偏差。
1. 基于图的稀疏集合数据生成
根据以上想法，我们的第一件事就是建立图结构到条件生成概率的映射。已知多个有差异的有偏数据环境，我们首先可以利用基于联合发生频率的方法在各个环境中构建初始的图，每个点表示集合中的元素。SGL 框架由 2 个模块构成，第一个模块是图卷积神经网络，可以把初始图的结构特性嵌入到输出的元素表征中。这样，通过池化一个集合的所有元素表征，我们可以得到对应集合的特征向量。特征向量会经过第二个模块，元素级的变分编码器（E-VAE），重构真实数据的同时，学习集合的生成概率。具体地说，集合的特征向量经过编码器会得到隐空间分布，并能从中采样一个隐向量；隐向量分别和各个元素的表征联合解码，产生该元素被选入集合的强度；把所有元素的强度投影到概率空间，就能输出集合的生成概率。假设输入集合数据是饱和的，我们可以通过尽可能重构原始数据的方式，学习环境中的条件生成概率空间。也就是说，我们希望条件于真实样本的输出概率，采样新元素加入后，集合保持不变，最大化真实样本出现的概率。

考虑到集合数据的稀疏性，我们用 negative log likelihood 目标函数优化模型的学习。

同时，优化 E-VAE 里隐层分布和预定义的正态分布的 KL 散度距离：

2. 学习稳定的图结构
在各个环境中训练一套参数共享的 GCN 和 E-VAE，我们可以得到给定相同输入集合，各个环境不同的条件生成概率。此时，假设有一个无偏数据环境，并初始化其中的图结构。我们能够优化无偏环境的图结构，使得从这张图输出的无偏环境中的生成概率是各个有偏环境的均值，从而得到稳定的图结构。

考虑到各部分之间的相互作用，我们最终联合优化 GCN、E-VAE 和稳定图结构的邻接矩阵。模型通过 SGD 的框架优化，所以对图规模的适用性也比较友好。

实验

为了验证模型的有效性，我们分别在模拟数据和真实数据上进行了实验。模拟实验的部分，我们先利用有偏的随机游走策略在两个环境中产生了数据分布有差异的游 走路径。策略由p0（0 阶关系，如用户的先验偏好）、p1（元素的一阶关系）、p2（元 素的二阶关系）控制两个环境中的差异程度。p0 、 p1 、 p2 的值越大，说明分布差异 越大。然后在各个环境中的训练数据基于联合发生频率建图，可以得到内含关系不同的 2 张图。
除了单一环境的频率图G1、G2，我们的基线模型还有GA = GG 12 + 2 和均匀比例 混合各环境数据构成的频率图GC。基于G1、G2 和训练数据，我们可以学到稳定的图结构GS。
为了测试不同图结构的稳定性，我们设计了集合预测任务：首先把一个测试集合划分成目标元素和剩余已知元素，给定从图结构学出来的元素表征和测试集已知元素，目标是从所有候选节点中选出目标元素，也即选出与集合中剩余元素的距离最近的元素。进一步，我们把两个环境的测试数据以 0:10、1:9、……、10:0 比例混合，可以得到 11 个测试组。统计基于不同图结构学出来的元素表征，用元素表征之间的平均 COS 距离作为测度，在多个数据分布不同的测试组中的预测准确率。为了保证实验的公平性，我们用同一个 GCN 学习不同图中的元素表征。
从以下结果可以看出，单一环境中的图随着另一个环境数据的增加，图中关系的适用性越来越差；简单对各环境的图线性平均，没有考虑到图中的非线性关系；混合各环境数据构图，会存在原始建图方法的模型偏差，也不能解决 0 阶关系，如用户的先验偏好的差异；稳定的图结构可以以最小的预测标准差达到最好的预测准确率，因为它可以平衡不同测试环境中的高阶、非线性的关系偏差。

真实实验上，我们分别对用户群体偏差和商品曝光偏差的场景做了测试。前者是指不同环境中用户成分比例不同，后者是指不同环境中商品的主导成分的热度不同。对于用户群体偏差，我们直接把女性用户和男性用户划分两个环境；对于商品曝光偏差，我们先筛选出热门商品，然后根据一个购物记录中是否热门商品占比超过一半，把所有记录划分到热门主导环境和冷门主导环境。基线模型和预测任务同模拟实验。
实验中观察到，不同环境的预测难度是不同的：女性的购物行为比男性的更容易预测，可能是由于女性更倾向于一次相关性强的商品；热门商品较多的购物记录也更容易预测，可能由于热门商品之间的相关性更强。SGL 依然可以从不同环境中学习更泛化的信息，达到最好的预测率。

总结：

为了从多异质环境中学习稳定的图结构，我们提出了SGL学习框架。框架通过基于图的稀疏数据生成，建立了图结构到生成概率空间的映射，然后在生成概率空间平衡有偏信息，从而能修正图的结构偏差。实验证明，我们提出的方法确实可以提升图结构的稳定性，并在实际问题中起到有效作用。

参考文献：

[1] Lada A Adamic and Eytan Adar. 2003. Friends and neighbors on the web. Social networks 25, 3 (2003), 211–230.
[2] Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. 2018. Netgan: Generating graphs via random walks. arXiv preprint arXiv:1803.00816 (2018).
[3] Peter Bühlmann, Jonas Peters, Jan Ernest, et al. 2014. CAM: Causal additive models, high-dimensional order search and penalized regression. The Annals of Statistics 42, 6 (2014), 2526–2556.
[4] Abhishek Gupta, Coline Devin, YuXuan Liu, Pieter Abbeel, and Sergey Levine. 2017. Learning invariant feature spaces to transfer skills with reinforcement learning. arXiv preprint arXiv:1703.02949 (2017).
[5] Kilol Gupta, Mukund Yelahanka Raghuprasad, and Pankhuri Kumar. [n.d.]. A Hybrid Variational Autoencoder for Collaborative Filtering. ([n. d.]).
[6]Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. 2019. Semi-supervised learning with graph learning-convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 11313–11320.
[7] Diederik P Kingma and Max Welling. 2013. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 (2013).

更多数据挖掘论文查看：《KDD论文精华解读》