详解图嵌入Graph Embedding之 社交网络应用

社交网络推荐是图嵌入(Graph Embedding)的经典应用场景。这篇文章会介绍图嵌入具体到社交网络问题中,派生出的解决算法。

研究问题

协同过滤

协同过滤(Collaborative Filtering)算法在给定用户(user)对于物品(item)的评分矩阵R后,将用户和物品都投影到同样的低维空间中,而用户对于物品的期望评分应该可以用双方在低维空间投影向量的相似度刻画。[1]

社交网络推荐

社交网络推荐(Social Recommendation)着重研究的是在社交网络中特有的性质——节点蕴含的信息可以通过社交网络的邻居进行扩散。在社交网络的邻居倾向于拥有相同的偏好。[1]

社交网络的特点

数据稀疏

社交网络的一大特点是稀疏性[1],不仅一个节点的邻居非常稀疏,而且通常来说用户的反馈也是稀疏的。社交网络推荐系统的典型应用就是通过少数用户的标签推测出其他用户的标签,这种场景下可见的标签必然是及其稀疏的。

属性多元性

相比于其它问题中,图的节点信息较少。在社交网络图结构中,一个节点(用户)拥有非常多的属性,如年龄、性别、地域、经历等等。[1] 同时,两个节点的联系也存在不同的属性,他们可能是亲属、同事、同学,或者仅仅是兴趣相同的线上朋友。这意味着图中的连边并不一定意味着相同的兴趣爱好(相同的标签)[2]。

小世界现象

小世界现象(Small World Phenomenon)说的是在一个比较大的人口集合中,选取任意两个人作为起点终点,计算从起点到终点的“认识链”(即链上的人依次互相认识),这个链长平均为5.7。该现象暗示社交网络图的直径非常小,而且信息扩散是指数级别的,而一般来说社交网络中的“局部”指的是从起点开始1到2跳形成的邻域。[2]

节点度数分布

节点度数的规模无关现象(Scale-free property)说的是在社交网络图里面,节点的度数基本上是与社交网络规模无关的(具体来说应该是O(loglogn))的关系。[3]

引用

[1] Wu, L., Sun, P., Hong, R., Fu, Y., Wang, X., & Wang, M. (2018). SocialGCN: An Efficient Graph Convolutional Network based Model for Social Recommendation. arXiv preprint arXiv:1811.02815.Chicago

[2] Travers, J., & Milgram, S. (1977). An experimental study of the small world problem. In Social Networks (pp. 179-197). Academic Press.

[3] Chakrabarti, D., & Faloutsos, C. (2006). Graph mining: Laws, generators, and algorithms. ACM computing surveys (CSUR)38(1), 2.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据