Graph Embedding及其在知乎的实践

1 .Graph Embedding及其在知乎的实践 知乎 孙付伟 

2 .目录 • 业务背景 • Graph Embedding 介绍 • Graph Embedding 在知乎的实践 • 总结与未来规划 

3 .业务背景 知乎：可信赖的问答社区 2.2 亿 3000 万 1.3 亿 注册用户数 问题 回答 截止到 2018.11 

4 .业务背景 本质：连接 人 知识 

5 .Graph Embedding 介绍 举例 为什么要用到 Graph Embedding • 在面对图结构的时候，传统的序列 embedding 方法就显得力不从心。对图 结构中间的节点进行表达的 Graph embedding 成为了新的研究方向 知乎用户关系 

6 .Graph Embedding 介绍 DeepWalk • Random Walk 负责对图采样 • 如果是有向有权图，则游走概率可以选择 边的权重占比（非原文） • Skip-gram 借助 Word2Vec 思想对序列训 练每个节点的 Embedding 向量表示 • Hierarchical Softmax *** 该图来自《Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba》 Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '14). ACM, New York, NY, USA, 701- 710. 

7 .Graph Embedding 介绍 LINE • First-order proximity（1 阶相似度）：用于 描述图中成对顶点之间的局部相似度 • Second-order proximity（2 阶相似度）： 用于衡量成对顶点之间的网络结构相似度 Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. LINE: Large-scale Information Network Embedding. In Proceedings of the 24th International Conference on World Wide Web (WWW '15). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, Switzerland, 1067-1077. 

8 .Graph Embedding 介绍 LINE • First-order proximity（1 阶相似度）（只适用于无向图）： • 优化技巧： • 节点相似度（sigmoid）： • 分开训练，可以 concat • Edge Sample（边采样） • 经验概率： • 优化目标 O1： • 低度的顶点的处理（冷启动问题） • 利用3阶来扩充 • Second-order proximity（2 阶相似度） • 节点相似度（softmax）： • 经验概率： • 优化目标 O2： Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. LINE: Large-scale Information Network Embedding. In Proceedings of the 24th International Conference on World Wide Web (WWW '15). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, Switzerland, 1067-1077. 

9 .Graph Embedding 介绍 Node2Vec • DeepWalk： 类似一种 DFS（深度优先搜 索） • Node2Vec： DFS + BFS • 同质性（homophily）： • 距离相近节点的embedding应该尽 量近似，通过 DFS 方式来实现 • 结构性（structural equivalence）： • 结构上相似的节点的embedding应 该尽量接近，通过 BFS 方式来实现 Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '16). ACM, New York, NY, USA, 855-864. 

10 .Graph Embedding 介绍 Node2Vec • 节点间的跳转概率控制 BFS 和 DFS 的倾 向性 • 从节点 V 跳转到下一个节点的 x 的 概率： Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '16). ACM, New York, NY, USA, 855-864. 

11 .Graph Embedding 介绍 • Node2Vec 效果（上图是偏重同质性、下 图偏重结构性） Node2Vec • 优化策略 Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '16). ACM, New York, NY, USA, 855-864. 

12 .Graph Embedding 介绍 SDNE • 是 LINE 的扩展 • 图的网络结构信息分成 local 和 global 的， 就是一阶近邻和二阶近邻的关系。 • 二阶近邻用非监督的autoencoder 去得到， 还原节点的上下文信息 • 一阶近邻用监督的方式去得到，对应监督 样本就是存在直接相连的节点。 • 优化目标 **原图修改 Daixin Wang, Peng Cui, and Wenwu Zhu. 2016. Structural Deep Network Embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '16). ACM, New York, NY, USA, 1225-1234 

13 .Graph Embedding 介绍 SDNE • 应用于阿里打包购商品挖掘系统 https://zhuanlan.zhihu.com/p/33501938 

14 .Graph Embedding 介绍 EGES • 在 DeepWalk 基础之上加入对『冷启动』 商品的处理，从而使得长尾物品也能够获 得合适的 Embedding • 组合表示 item embedding 时，对 item 和 side information（例如 category, brand, price 等）的 embedding 施以不同的权重。 该权重通过模型训练得到 Jizhe Wang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. 2018. Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD '18). ACM, New York, NY, USA, 839-848. 

15 .Graph Embedding 在知乎的实践 用户 Embedding 表示 • 利用 Graph Embedding 模型对用户进行 隐式表示的学习，计算出两个用户之间的 亲密度，以此进行更精准的推荐，让用户 更多地在社区里发生连接 • 主要采用了 DeepWalk 思想 

16 .Graph Embedding 在知乎的实践 在收藏夹数据中的应用 • 知乎收藏夹包含大量有价值内容 • 基于矩阵分解的协同过滤的问题： • 长尾内容无法有效表示，推荐内容不相关 • 无法表达出更强的传播能力，从而覆盖较 弱 

17 .Graph Embedding 在知乎的实践 在收藏夹数据中的应用 • 采用类似 EGES 算法 • 基于收藏夹内容，构建 graph，节 点为内容，同时出现在一个收藏夹 的行为为边， • 使用热门数据降采样及加入 BFS 的 Random Walk 构造序列 • 引入内容的 side information（例如： topic、category 等）的 Embedding 并施以不同的权重 

18 .Graph Embedding 在知乎的实践 在收藏夹数据中的应用 示例 • 训练集：110万节点， 3 亿条边。 • Random walk的长度为 10，每个节点会 进行 10 次 walk，skip-gram 的窗口大小 CF（ALS） EGES 为5 为什么白居易写了《琵琶行》却不娶琵琶女？ 为什么白居易写了《琵琶行》却不娶琵琶女？ • 最终测试集 accuracy = 0.84 有没有一瞬间觉得男女真的不平等？ 有哪些惊艳到你的诗词？ 有哪些很文艺的句子？ 鲁迅先生写过什么值得细品的句子？ 放弃了自己很喜欢的人，会不会后悔？ 有哪些前半句为大众所熟知，后半句却很少有人 知道的诗句（词句）？ 当下中国有哪些审美畸形的现象？ 你见过美得不可方物的别称或雅称是什么？ 有哪些惊艳到你的诗词？ 李白笔下最为动人的六十六句话？ 

19 .总结和未来规划 • 总结 • Graph Embedding 成为推荐系统、计算广告等领域一种新的流行做法 • 目前工业界应用影响还在慢慢放大 • 未来规划 • 更丰富的应用场景 • 会员购买预测、个性化推送召回等等 • 更多的技术尝试 • 引入用户更多 side information（比如用户多种画像信息） 的用户 Embedding 获取 • 尝试将 side information 与 SDNE 结合，更好学习图的结构性 

20 .Q &A