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

详解图嵌入Graph Embedding之 相关文献综述

详解图嵌入系列传送门:https://mhy12345.xyz/graph-embedding-tutorials/

文献综述

Relational learning via latent social dimensions

在这篇文章之前,图的多标签分类是传统算法的天下。在此之前,甚至人们探讨的都是如何给社交网络划分集群等传统问题。当时人们的思想还是类似于page-rank一样的影响力模型,一个节点的邻居是什么标签,那么这个点也应该是什么标签。

这篇文章提出了先为图中每个节点识别出一个K维向量,然后将图的分类问题转换为向量的分类问题。而这个向量本身,是图的Modularity矩阵的前K大的特征向量。Modularity细节一言难尽,可以参考实际的论文。不过感性上来看,第K个特征向量中1的项暗示了这个节点可以被分到第K类。

这篇文章算是将矩阵、线性代数那一波东西引入图嵌入中比较成功的一个例子。也是图分类从统计学、线性代数等传统方法向深度学习的图嵌入的中间产物。

DeepWalk: Online Learning of Social Representations

这篇文章首先说:“从图中一个指定点出发随机游走较短距离遍历过的点,从频数分布来说与普通英文文章中的词频相似,都符合幂律分布(power-law distribution)。”

社交网络的路径遍历和普通文章的词频相似,因此可能存在共通的分析方法。

接下来,节点的Embedding就变成了将从他开始若干路径视为“句子”,使用NLP中的词嵌入算法生成的Embedding。文章还介绍了一个称之为Hierarchical Softmax的分层求解Softmax的方法。可以使模型更加高效。

Structural Deep Network Embedding

文章首先介绍了一阶相似度(first-order proximity)和二阶相似度(second-order proximity),其中,一阶相似度要求两个节点的编码能够有效的表征其间是否存在连边,而二阶相似度要求两个节点的编码能够有效表征他们的共同邻居的存在。实际上,一个合理的Embedding方式,应该能够同时满足一阶/二阶相似度的关联性。因此我们将一阶/二阶相似度引入到Loss函数中,作为优化的一项参数即可。

SocialGCN: An Efficient Graph Convolutional Netowork based Model for Social Recommendation

文章指出之前的很多文章没有考虑到社交网络中的信息扩散效益,通过K轮迭代的方式,使得图中中每个节点内部的信息(即节点的Embedding)有机会扩展到距离为K的节点中。

GraphGAN: Graph representation learning with generative adversarial nets.

文章指出了图表示学习诸多算法的一种分类方式——基于生成性&判别性分类。并进一步设计了基于图的生成模型算法。具体来说,生成器G尝试拟合节点v_c的真实邻居的概率分布p_{true}(v|v_c)。并从这个分布中采样一部分邻居用以迷惑判别器D。同时判别器D需要判断出某一个节点真的是邻居还是生成器G假装生成的。

比较特别的是,这篇文章由于存在采样,因此使用的是强化学习Policy Gradient中的“随机梯度下降算法(Stochastic gradient descent)”方法进行学习。

参考文献

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

详解图嵌入Graph Embedding之 算法概述

详解图嵌入系列传送门:https://mhy12345.xyz/graph-embedding-tutorials/


算法概述

将深度学习放在图上

深度学习在近十年有着井喷式的突破,随着研究者们在该领域投入大量的人力物力,大量新颖有效的结构被创造了出来,比如能够完成手写数字识别的卷积神经网络CNN,能够提取语句情感色彩的LSTM结构,能够生成图片的对抗神经网络GAN……

CIFAR-10 Samples
CIFAR-10 数据集的分类是机器学习中一个公开的基准测试问题,其任务是对一组32x32RGB的图像进行分类

现有的神经网络大多都是建立在图像和序列上的,还有少量建立在树形结构上。如何将神经网络迁移到图上,成为了很多学者研究的问题,为什么会尝试把神经网络迁移到图上呢?在笔者看来有两个原因——

第一个原因是图结构本身就是所有数据组织结构的大杂烩。我们平常处理的“链式结构”,“树形结构”,“二维网格图”都可以被“图”这样一个概念囊括。如果我们能够提出一个建立在图上面的,足够高效智能的算法,其意义在机器学习问题中不亚于大统一理论在物理中的意义。

图本身就是大量数据结构的抽象化结果,比如计算机视觉中,卷积神经网络处理的二维图像,从某种意义上也是图的一种,研究者们尝试将CNN的模型迁移到图上,就成为了现在的图卷积神经网络GCN。[1]

第二个原因是图上的分类问题,在我们生活中也大有应用。比如基于关注列表的商品推荐、社交网络中的朋友推荐、以及社交网络中的兴趣推荐等等。这些问题的核心都是将用户的关注列表抽象为图结构,并从中提取出有用的信息。

既有实现深度学习大统一的“仰望星空”,又有解决实际问题的“脚踏实地”,基于图的深度学习算法,在近年来逐渐火了起来。

图嵌入识别节点空间结构

相比于传统的深度学习问题,基于图的神经网络不仅需要处理节点自带的若干属性,还需要处理节点在图上的空间结构。

我们将通过社交网络中一类重要的数据集类别“博客”为例,讲解图嵌入的意义。博主通常会为自己的博客添加一些标签作为博客本身的介绍。这些标签同时还可以优化博客的检索与搜索。但是,并不是所有博主都会上传自己博客的标签,甚至有些博主会由于某些因素上传一些不那么准确的标签。这就要求我们的模型能从博客的关注图结构以及部分博客标签中,补全其他节点的标签。[4]

与博客网络相似的还有基于社交网络的广告推荐。不过不同的是,对于广告推荐而言,有效样本占总体数据的比重非常非常的小(毕竟只有很小一拨人会点击广告并被我们的模型捕获)。这也要求模型花更多精力投入到识别图结构本身的特征而非节点上蕴含的信息。后者对标签特征的提取与图本身无关,可以套用传统的深度学习模型,而后者对图特征的提取就需要特殊的算法解决了。而计算节点在图中的空间特征的算法就是图嵌入(Graph Embedding)或网络嵌入(Network Embedding)。

图嵌入的目标是将图中的节点表示为一个低维向量,该向量保留了节点在网络中的拓扑结构以及节点内部信息。通过这个表示向量,其他的经典深度学习算法才得以被应用到图中,最终实现分类、聚类、推荐等问题。[3]

数据集与模型评价

综述文章[3]中有一张很大的表,记录了基于图深度学习文章常用的数据集。包括类别、规模以及引用。本系列的另一篇文章会详细描述我在学习过程中了解过的数据集。

在表中,数据集被分为了引用网络(Citation Network),社交网络(Social Network), 化学/生物的图结构(Chemical/Biological Graphs),去结构化的图(Unstructured Graphs)和其他(Others)。每一种类型都对应了不同的问题,比如社交网络数据集着重于测试模型能否捕获临近节点的信息,以及识别出节点的空间特征,而去结构的图则着重测试模型是否可以成功泛化一些本可以有更强结构信息的图。

在图嵌入这个问题中,节点所处的空间特征很重要,因此相关的论文喜欢用社交网络数据集进行测试。一个最简洁的社交网络数据集有如下组成部分——

  • 节点表:记录了这个图结构所有节点
  • 边表:记录了图中的所有有向边
  • 标签表:记录图中所有节点所述的分类

对于图上的分类算法的测试,我们一般将标签表中一部分点的数据隐藏,让模型试图通过没有隐藏的节点标签推导出这部分隐藏数据,并计算准确率。[4] 由于这是一个多标签分类问题,学术界通常使用Micro-F1和Macro-F1两个指标来衡量模型效果。

当然,对于图嵌入算法来说,模型输出的并不是分类本身,而是一个表征了节点信息的向量。在这样的情境下,我们一般以这个向量为输入,跑一个简单的分类算法。例如文章[5]就使用了一个“一对多的逻辑回归(one-vs-rest logistic regression)”来分类这些节点的embedding。

算法发展

从历史的角度来看图嵌入算法的发展历程,最初这类算法使用传统概率模型,通过类似于page-rank的思路计算出每个节点属于每一类的概率。接下来,在传统领域,有些学者引入了图的拉普拉斯矩阵与模块度矩阵来优化分类效果。这类做法归根结底是使用更为复杂精巧的数学模型解决问题。

当然,随着深度学习的发展,有很多学者使用了诸多深度学习的方法,比如之前所说的图嵌入与图卷积神经网络。这类方法尝试重现深度学习在其他领域的突破性成功。至今为止,start-of-art的模型当然是基于深度学习的。我们可以从paperwithcode网站的排行榜上面看到当前最新的图嵌入算法。

这些基于深度学习的图算法有很多不同的思路,比如是以DeepWalk[5]、SocialGCN[7]为代表算法的通过随机游走、多重迭代等遍历策略来生成的图嵌入算法。另一种是以SDNE[6]为代表,通过设计损失函数引导梯度下降,来保证嵌入向量能够表示某种特定的图结构信息。详细的介绍可以看本系列另一篇文章 详解图嵌入Graph Embedding之 相关文献综述

更多资料

GraphEmbedding复现代码:https://github.com/shenweichen/GraphEmbedding

详解图嵌入系列传送门:https://mhy12345.xyz/graph-embedding-tutorials/

引用

[1] Niepert, M., Ahmed, M., & Kutzkov, K. (2016, June). Learning convolutional neural networks for graphs. In International conference on machine learning (pp. 2014-2023).

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

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

[4] Tang, L., & Liu, H. (2009, June). Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 817-826). ACM.

[5] Perozzi, B., Al-Rfou, R., & Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710). ACM.

[6] Wang, D., Cui, P., & Zhu, W. (2016, August). Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1225-1234). ACM.

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