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

发表评论

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

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