详解图嵌入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之 相关文献综述》有一个想法

发表评论

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

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