笔记︱基于网络节点的node2vec、论文、算法python实现

2017-01-13 11:33:52来源:CSDN作者:sinat_26917383人点击

看到一个很有意思的算法,而且腾讯朋友圈lookalike一文中也有提及到,于是蹭一波热点,学习一下。论文是也发KDD2016
.
.

一、主要论文:node2vec: Scalable Feature Learning for Networks

本节引用自
a、微博洪亮劼 :【论文每日读】node2vec: Scalable Feature Learning for Networks

b、简书:node2vec: Scalable Feature Learning for Networks

本文的特征抽取方式类似于聚类分析的非监督方法,本质上都是利用相邻节点之间的联系。文中提到了网络中的节点一般有两种相似度量:1.内容相似性,2.结构相似性。其中内容相似性主要是相邻节点之间的相似性,而结构上相似的的点并不一定是相邻的,可能隔得很远,这也是文中为何要把BFS和DFS相结合来选择邻居节点的原因。

文章的主要想法就是,利用SkipGram的方法,来为Networks抽取Representation。那么,自然,根据SkipGram的思路,最重要的就是定义这个Context,或者说是Neighborhood。​从文本的角度来说,这个Neighborhood当然就是当前Word周围的字,这个定义非常自然。但是对于Graph或者Network来说就来得没那么容易了。

文章阐述了一般所采用Depth-First Search或者是Breadth-First Search来Sample一个Node的周边Node的问题。简单来说,BFS比较容易有一个Microscopic的View而DFS容易有一个Macro-view,两者都有Representative的问题。

文章的核心思想是采用Random Walk来代替DFS或者BFS。文章定义了一种二阶的Random Walk,拥有两个参数,来控制多大的概率反复经过一些Node和控制所谓的Inward和Outward。总之,整个Random Walk的目的就是在DFS和BFS之间采取某种平衡。

文章虽然提出的是关于Node Feature提取的算法,但是Edge Feature也可以很容易从Node Feature导出。

总体感觉是,硬要用SkipGram或者WordVec的想法在Networks上做,还显得比较牵强。因为有这个Neighborhood的概念,在Graph上,反而不是那么直观得定义,因此所有类似的工作都显得比较别扭。当然,这篇文章也不失为一种不错的Heuristic。​
这里写图片描述

这里写图片描述

.
.
.

二、python实现

github网址

案例:
To run node2vec on Zachary’s karate club network, execute the following command from the project home directory:

python src/main.py --input graph/karate.edgelist --output emb/karate.emd

Options

You can check out the other options available to use with node2vec using:

python src/main.py --help

Input

The supported input format is an edgelist:

node1_id_int node2_id_int <weight_float, optional>

The graph is assumed to be undirected and unweighted by default. These options can be changed by setting the appropriate flags.

Output

The output file has n+1 lines for a graph with n vertices. The first line has the following format:

num_of_nodes dim_of_representation

The next n lines are as follows:

node_id dim1 dim2 ... dimd

where dim1, … , dimd is the d-dimensional representation learned by node2vec.
.
.
.

三、腾讯对node2vec的应用

微信公众号infoQ:当机器学习遇上复杂网络:解析微信朋友圈 Lookalike 算法

这个横轴是与广告进行互动的好友个数,纵轴是用户对广告的关注率(包括查看,点赞或者评论),我们发现这个关注率会随着好友数的增加而上升。这个数据拐点差不多是3到5个好友。
这里写图片描述

重点会挖掘这两个价值,就是社交同质性和社交影响力。
实际上在一个社交网络的节点也是这样的,我们经常会存在一些大的节点,他会有非常多的好友,有的人好友就达不到那么多。所以说其实在社交网络里面的一个节点的分布也是幂律分布。如何把Wodrd2Vec迁移到node2vec,这个时候就要产生一个节点的序列,它对应到了自然语言处理的一条句子,图结构里面的节点相当于NLP的一个单词。

所以在图网络上按照一个搜索的方法生成节点序列,这个节点的序列可以对应到自然语言的一个句子,后面我们通过Wodrd2Vec的框架,将节点embedding为一个向量。所以对于做network embedding的时候,这个生成节点序列的搜索策略非常重要。最简单的一个方法,就是随机游走,随机游走一方面生成节点序列,另一方面也是对图的一种采样,降低了计算量。

这里写图片描述

比如说我们的一个社交网络,我的同学会形成一个社团,设计这个P往回走,就更容易走到我这个群体。当P越大,它会越能体现同质性。Q越大的时候,它其实能够体现这种结构的相似性,不同的节点有不同的作用。比如说F节点和E节点它是连接这两个社团的桥接点。当Q大的时候,它体现的是网络结构的相似性。这时候我们怎么选P和Q?这个可以根据实际任务进行半监督的学习。

这里写图片描述

给大家看一下node2vec的结果,先给大家看这个算法的输出。这里有一个简单的图,做embedding之后的结果,1和2的节点向量是一样的,它会是重叠的一个向量,3、4、5、6也是一个重合的节点,它表达的是什么呢?为什么1和2完全重叠?其实1和2的网络环境是一模一样的,这个embedding的结果表达是是节点的社交网络环境,也就是我们说的拓扑特征。
对社交相似性的学习框架,大家可以看下面的图。 我们建立一个回归的model。现在做的是SVR模型。输入好友网络,沟通网络、文章的转发阅读网络等等,进行embedding得到特征向量表达,通过SVR模型,学习到这些特征和广告相似度的函数关系。这个函数关系计算出好友相似度,可以对好友进行排序。

这里写图片描述

我们看一下算法的效果。我们评估算法的效果,最直接的就是说我有多个算法,广告主需要100万的用户,我这几个算法都给出100万用户,然后看一下这100万的用户点击量是怎么样的,我们叫Lift值。其他的算法跟它进行对比,看一下它的效果有没有提升。那我们的算法相比直接的二分类模型有2倍-3倍的lift。

这里写图片描述

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台