详解图嵌入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.

详解图嵌入Graph Embedding之 经典数据集

Yelp数据集

Yelp数据集是由美国最大的点评网站Yelp公开维护的数据集,网站开放了能够做预测的几乎所有数据。包括——

  • [bussiness]餐馆详情:名称、地址、坐标、评分、类别、营业时间、有没有WIFI……
  • [checkin]餐馆的登记时间戳
  • [photo]餐馆上传的室内/室外照片
  • [review]用户对餐厅的评价
  • [tip]大概是用户对餐厅的建议
  • [user]用户信息,历史好评/差评数量,及其好友列表

Yelp还定期举办比赛,看哪个团队的预测结果最准确。写这篇文章的时候,比赛已经进行到了第13轮。一个需要注意的是在数据集下载界面中的“Please sign by entering your initials”是让你输入姓名中姓和名的大写首字母。[1]

Wikipedia数据集

Wikipedia数据集从英文维基百科的存档中截取了1,000,000个字节的数据,并将单词的出现建立成一张图。而单词的词性标注(part-of-speech tags)被看做这个节点的标记。不过由于我不太懂NLP方面的东西,也没有找到具体建图的流程,只在[2]里面看到了一个粗略的介绍,如果有读者知道的话,欢迎留言。一个经过处理后的图数据集可以在这里找到。

BlogCatalog数据集

BlogCatalog3数据集 是从著名博客目录网站BlogCatalog抓取的博客数据集,其中节点代表了每一个用户(博客),而节点的标签则是用户在网站中所属的用户组别,在一定程度上,标签反映了用户本身感兴趣的种类。[3] 数据集包括——

  • [edges] 所有边所连接的端点的表
  • [group-edges] 所有标签对应的节点编号
  • [nodes] 所有的节点编号
  • [groups] 所有的标签编号

引用

[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.

[2] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2019). A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596.

[3] Wang, H., Wang, J., Wang, J., Zhao, M., Zhang, W., Zhang, F., … & Guo, M. (2018, April). Graphgan: Graph representation learning with generative adversarial nets. In Thirty-Second AAAI Conference on Artificial Intelligence.