本文总结一些基于传统的w2v改进的图网络相关的论文，这个是前期的一些工作，到现在为止主线是Phrase Extraction，同时兼顾Phrase Ranking和Embedding。因此目前对Embedding的总结也是和Phrase Extraction，Phrase Embedding比较相关的。
SurfKEy
由Learning Feature Representations for Keyphrase Extraction引出我对Graph Embedding的兴趣的，下面简单说一下这篇文章做的工作。
Graph Construction：对于单篇文档而言，首先去除停用词（对于中文，需要先分词），将剩下的词设置窗口大小，窗口内的词定义为共现。节点为词，边的权重为两个词共现的次数。（注意，是单文档构建，这样就要求单文档比较长）
Learning Feature Representations：无向图构建后，我们使用有偏随机游走采样固定数量长度为l的walks，当上一个节点是$v_{i_{j-1}}=y$时，下一个节点$v_{i_{j}}=x$的转移概率如下：
其中$w_{xy}$是边(x,y)的权重，$T$为图中所有边的权重和（这里我觉得应该是与接点$v_{i_{j-1}}$相连的节点之间的权重和）,然后将游走的walks放到w2v中训练词向量作为特征向量。
Candidate Phrases： 候选词如果在文档中是连续出现的，我们将其连接作为短语，其向量表示等于词的向量表示的均值
Train：使用贝叶斯分类器来为词向量训练得分（二分类），然后设置一个阈值，挑选出高于该阈值的作为候选短语。。。
BiasedWalk
BiasedWalk: Biased Sampling for Representation Learning on Graphs于2018年发表，这篇论文提供了源码，使用python的networkx实现的，skip-gram+negative sampling 使用gensim库，但是这种方法对于大数据量来说不可行，也就跑跑几百几千个节点还好，百万千万级别的节点就很不好搞了，因为每次选择当前节点的下一个节点时，都要将当前节点的所有邻边节点的累积因子求和$S$，然后产生一个在$S$范围内的随机数，看该随机数在哪个节点范围内就选该节点（类似于负采样），这个非常耗时。
构建图的方法上面提到了，至于有偏随机游走获取序列该论文提供了两种方案，如下图所示：
一种是DFS，即偏向于选择当前节点的邻边节点中被游走过的节点作为邻边节点次数少的节点，如左图蓝色线所示。一种是BFS，即偏向于选择当前节点的邻边节点中被游走过的节点作为邻边节点次数多的节点，如左图红色线所示。再看右图，第一个节点是1号节点，同时对应的邻边节点会被加上累积因子$α^k$，$k$等于当前节点为整个序列中第几个节点，当走到7号节点时，如果是DFS方式，相对于5号，4号节点而言，9号，8号节点会更大概率被访问。
具体算法如下所示：
核心算法如下所示：
#有偏游走，默认使用DFS方式
def simulate_walks(nx_G,num_walks,walk_length,i_value):
walks=[]
nodes = list(nx_G.nodes())
adds=[1.0]
for i in range(walk_length):adds.append(i_value*adds[i])
out_adj = {}
for node in nodes:
out_adj[node]=list(nx_G.neighbors(node))
random.shuffle(nodes)
for i in range(num_walks):
print("Step:", i+1, "/", num_walks)
for node in nodes:
tau={}
walk=[node]
l=0
while(l<walk_length-1):
u=walk[l]
for w in out_adj[u]:
if w not in tau:tau[w]=adds[l]
else:tau[w]=tau[w]+adds[l]
total=0.0
r=random.random()
summ=0.0
for v in out_adj[u]:
total=total + np.reciprocal(tau[v])*nx_G[u][v]['weight']
for v in out_adj[u]:
summ = summ + np.reciprocal(tau[v])*nx_G[u][v]['weight']
if (summ/total > r):
break
walk.append(v)
l=l+1
walks.append(walk)
return walks使用该算法小批量做了测试，选取一篇文章下的全部评论作为一篇文档，来训练该文档对应的短语的Embedding，构建图的时候，该文档作为一个窗口，因此该文档中的短语之间都是共边的（我们的直观理解是一篇文章下面的评论都是在讲一个话题），万级节点(3万多)，百万级边(150万)，每个节点走4条walk，每条walk长度为5（这里原论文中设置的是walk=10，length=80，太慢根本训练不出来），使用gensim训练，选取指定短语对应的前10个最相似的短语罗列如下：
此处为了证明我们选取的文档对应的短语序列确实能够学习到相似信息，我们直接用文档对应的短语按顺序作为一个序列训练word2vec，结果如下：
相比之下，使用BiasedWalk的方法差于直接训练的方法（当然从另一个角度来说，BiasedWalk的泛化能力要比直接训好），下面的DeepWalk则要差很多。
DeepWalk
DeepWalk: Online Learning of Social Representations于14年发表在KDD上，最早提出graph Embedding???，提供了源码。DeepWalk和BiasedWalk的不同之处在于DeepWalk在选取当前节点的下一个节点时，是随机选取的，也就是说DeepWalk构建的图的边是没有权重的。
本论文解释了为什么从图中得到的序列可以使用NLP的word2vec方式来求解Embedding，论文中对YouTube社交网络图生成walks对应的节点频率分析，和对Wikipedia的文本词频统计分析，符合power-law 分布(幂率分布，此处对应的是Zipf定律，即一个单词出现的频率与它在频率表中的排名成反比)，如下图所示：
同上小批量测试：3万节点，一百多万条边，维度64维，每个节点游走10条路径(使用默认参数)，运行半小时，结果如下：
这个结果真的是啥也没学到，可能是我调参问题??? 说一下个人理解：论文中也提到了说语言模型就是通过前面的词(节点)来预测下一个词(节点)，那么w2v学习到的就是相同上下文的词有相同的表示，对应到图中，就是节点周围的节点，而论文中生成序列时，对当前节点随机选择下一个邻边节点，而这种随机性能够学习到图的网络结构，理应可以学习到相似的节点表示啊，不知道为什么。。。拿到没有学到图的结构信息？？？
【图嵌入，即用一个低维，稠密的向量去表示图中的点，该向量表示能反映图中的结构，本质上就是说，两个点其共享的（n阶）邻近点越多，即两个点的上下文越相似，两个对应向量距离越近。而图嵌入的最大好处自然是得到的向量表示可以输入任何的机器学习模型去解决具体面对的问题。】
node2vec
node2vec: Scalable Feature Learning for Networks于16年发表在KDD上，源码python2实现，内部使用networkx和gensim库，同上样本量，跑了一下午都没有跑出来，可以说非常慢了(也有可能是我使用不当。。。)
类似于上面的构造方法，本论文中学习节点的两个特征：
（1）学习该节点周围节点的特征（相似上下文的节点相似）
（2）学习和该节点的网络结构（相似网络结构的节点相似）
和前面几种方法主要的区别是随机游走上，如下图所示：
给定一个源节点，模拟一条长度为$l$的随机路径，假定$c_i$是路径的第$i$个节点，那么其被生成服从如下分布：
其中$Z$是归一化常量，$π_{vx}$是在节点$v$和$x$之间的转移概率，为$π_{vx}=\alpha_{pq}(t,x) \cdot w_{vx}$，其中$\alpha_{pq}(t,x)$由如下式子定义：
其中$d_{tx}$表示节点$t$和节点$x$之间在图中的最短路径长度(当前节点的上一节点和下一节点之间的距离只可能是0，1，2三种情况)，比如上图所示，路径的当前节点为$v$，路径的上一个节点是$t$，那么在选择下一个节点$x$时对应的$\alpha_{pq}(t,x)$由上述指定。
参数$p>1$时，采样的时候回更少的采样已经访问过的节点，关注多条信息；$p<1$时，采样趋向于当前节点周围的节点。
参数$q>1$时，采样更偏向近的节点，类似BFS；$q<1$时，偏向于远的节点，类似于DFS
LINE
LINE: Large-scale Information Network Embedding于15年发表，源码是C++写的，需要下载gsl，没跑。。。
Line适合于大规模节点网络学习(百万节点以上，10亿边)，该算法定义了两种相似性，1阶相似度和2阶相似性，并提出了一种边采样算法来优化目标函数。
一阶相似性：定义网络中的节点连接关系(局部特征)，两节点之间的相似性正比于两节点的连接边权重的大小，如果节点之间没有连接，其一阶相似性等于0。对于一个无向边$edge(i,j)$，定义节点$v_i$和节点$v_j$之间的连接概率如下：
其中$\vec{u_i} ∈ R^d$是节点$v_i$的低维度向量表示，即两个向量越相似，那么它们的连接概率越接近1，这里只是将余弦相似度变为sigmoid了。两个节点对应的经验概率定义为：
最小化如下损失函数来定义一阶相似性：
$d(.)$表示的是这两种分布的距离，选择KL散度来表示$d(.)$，如下所示(忽略了常数分母$W$)：
注意一阶相似性只能用在无向图上。(为什么呢???，我的理解是一阶相似性拟合边权重，仅仅能够表示两个节点之间的相关性，相关性强则两节点越相似，有向图加了方向，不能简单这样做???)
【这里这个$E$表示的是全部的边，在论文中的定义里写了】
【再说一下对公式(3)的理解：让目标函数最小，也就是趋向于0，而$w_{ij}$为定值，那么相应的$w_{ij}$越大，对应的$log p_1(v_i,v_j)$越小，才能让乘积变小，而且该乘积越小，对整个目标函数的优化就越明显，就是说目标函数的训练结果是$w_{ij}$越大，$v_i$和$v_j$两向量就越相似】
二阶相似性：作为一阶相似性的补充，如下图所示，节点6和节点7之间存在很强的一阶相似性(线越粗权重越大，按一阶相似性定义，则两节点越相似)，节点5和节点6之间虽然没有边连接，但是由于它们之间有很多相同的邻边节点，因此也应该是相似的。即二阶相似性的定义是指两个节点之间的相似性和它们之间的邻边网络结构的相似性有关的。
二阶相似性即适合有向图也适合无向图，对于边$edge(i,j)$，定义节点$v_i$生成上下文$v_j$的概率定义如下：
其中$|V|$表示节点$v_i$的邻边节点的个数，注意$u'$是节点上下文的向量表示，而$u$是节点本身的向量表示，也就是说每个节点有两个向量表示，一个是作为节点本身使用，一个是作为其他节点的上下文使用。同上，对应的经验概率为：
$N(i)$表示$v_i$的邻边集(有向图指的是出度)
最小化如下损失函数：
$λ_i$表示上下文节点相对于当前节点的重要度，可以使用PageRank来测得，设置$λ_i=d_i$并去掉常数项，得到：
上面这个结果有些模糊，查一下KL散度（一种量化两种概率分布P和Q之间差异的方式），其中$Q(i)$表示理论分布，$P(i)$表示真实分布，当$D_{KL}$等于0时，两个分布完全重合,将这个转化过程罗列出来：
再看上面的公式(4)，计算的是全部的邻边节点，然后看论文中写的是用负采样优化，如下所示：
然后又说公式(3)也可以换成公式(7)的形式，只不过将$u'$换成$u$即可。
最后一个点是边采样，说边权重差异较大，在梯度训练时很难去选择好一个学习率，然后通过负采样的思想来采样，而去掉权重。
这篇文章的表述比较难于理解，看到后面我就觉得是带权重的word2vec，然后变成带权重的负采样，而一阶和二阶在最后公式(7)训练时本质区别是一个用上下文向量，一个不用上下文向量。
注意：一阶只使用了一个矩阵，二阶使用了两个矩阵(节点矩阵，上下文矩阵)，但是word2vec中使用的是两个矩阵(输入矩阵和输出矩阵)，所以说本论文和普通w2v的区别是一阶相似性??? 我的理解
我想验证一下上面这个结论，于是粗略看了一下源码，下面这个部分代码是负采样过程，可以看到一阶和二阶的区别确实在于其上下文向量的使用：
// NEGATIVE SAMPLING
for (int d = 0; d != num_negative + 1; d++)
{
if (d == 0)
{
target = v;
label = 1;
}
else
{
target = neg_table[Rand(seed)];
label = 0;
}
lv = target * dim;
if (order == 1) Update(&emb_vertex[lu], &emb_vertex[lv], vec_error, label);
if (order == 2) Update(&emb_vertex[lu], &emb_context[lv], vec_error, label);
}代码中v表示的是与u相连的正样本，这里lu是源节点，lv是目的节点和负采样的节点集合，乘以dim是因为源码中用一维数组来存储矩阵。下面是更新过程：
/* Update embeddings */
void Update(real *vec_u, real *vec_v, real *vec_error, int label)
{
real x = 0, g;
for (int c = 0; c != dim; c++) x += vec_u[c] * vec_v[c];
g = (label - FastSigmoid(x)) * rho;
for (int c = 0; c != dim; c++) vec_error[c] += g * vec_v[c];
for (int c = 0; c != dim; c++) vec_v[c] += g * vec_u[c];
}说白了LINE就是按权重采样，当然我们没有按权重采样，只是简单的将边权重小于某一阈值的过滤掉，然后将节点对pair作为序列放到word2vec中，训练结果如下，应该是最好的了：
SDNE
Structural Deep Network Embedding这篇论文于2016年发表在KDD上。论文中提到大多数的图网络都是浅层网络，很难捕捉高度非线性网络结构，因此提出SDNE，探索联合一阶相似性和二阶相似性来保留网络结构，一阶相似性保留局部结构，二阶相似性保留全局结构。这篇论文和LINE比较像，同时在实验中有对比的对象DeepWalk和LINE。实验包括Network Reconstruction，Multi-label Classification，Link Prediction，Visualization。
整个结构如下图所示：
包括一阶相似性(local structure preserved cost)和二阶相似性(global structure preserved cost)，节点$i$和节点$j$是有边相连的两个节点，$y_i^{(K)}$是节点$i$的向量表示，$y_j^{(K)}$是节点$j$的向量表示，二阶相似性的直观意义是全局结构的保留，即当前的向量表示能够恢复整个网络结构，如图所示，$x_i$是长度为n的01向量，n表示所有节点的个数，对应的如果和该节点有边相连则为1，否则为0，$\hat x_i$表示最终为1或0的概率，中间层以及损失函数如下所示：
这里因为网络的稀疏性，添加常量向量$b_i=\{b_{i,j}\}_{j=1}^{n}$，对应的如果边$s_{i,j}=0,b_{i,j}=1$，否则$b_{i,j}=β >1$。如下所示：
⊙为点集(就是对应位置相乘)。【不太清楚为什么要乘以B，暂时放一下】
再看这个一阶相似性，建立在拉普拉斯特征映射(Laplacian Eigenmaps)，意思就是说如果两个数据实例i和j很相似，那么i和j在降维后目标子空间中应该尽量接近，如下所示：
问题讨论
1.为什么LINE在公式(1)中提到说两个向量是否相似使用sigmoid来判断，这里是否可以使用余弦相似度来评判？
2.word2vec中将输入矩阵作为word的embedding，是否可以将输出矩阵作为word的embedding呢？
参考
[1]幂律分布背后的数学逻辑，了解一下？
[2]Graph Embedding：从DeepWalk到SDNE
[3]论文快读 - LINE: Large-scale Information Network Embedding
[4] word2vec中的两个矩阵(https://www.zhihu.com/question/278791534)
暂无评论