Graph Representation Learning

所谓的Graph Representation Learning可以看成是Graph的Embedding而已，也就是如何将Graph之中的节点转换成为Low Dimension Representation。总体的想法在昨天的论文之中自己好像也写了个大概，今天再把算法的细节给完善一些吧。

Basic Version

假设我们有一个Graph记作是$G $,其节点的集合是$V$,其邻接矩阵是$A$，在这个版本之下我们并不利用其它的Information。

那么现在的目标就是希望在Embedding空间之中接近的向量，在Graph之中也有相似的性质。将$u,v$的Embedding记作是$z_{u},z_{v}$.

我们希望$z_{u}\cdot z_{v} \simeq Similarity (u,v)$.为了达成这样的目标我们需要定义一个Encoder，也就是将Node Map into the Embedding Space.同时我们需要定义一个计量原网络之中节点相似度的Function，然后不断的优化参数使得这两个的相似度接近。那么任务就很简单了，First Step我们寻找一个Encoding的函数

最简单的方法就是直接在词典之中Look Up就完了，即

$$Encoder( v ) = Z v$$

其中的$Z$是一个Embedding Matrix，其中的$v$则是一个Onehot 向量，仅仅代表着其对应的节点的所在的位置信息。

通过上面这样的简单的Look up就可以对于每一个Node都获得了Embedding的信息。但是如何构建上面的Embedding Matrix呢？有非常多的算法就是干这个的比如说,DeepWalk,Node2Vec,TransE，还有阿里爸爸的那个。

我们先看看Deepwalk是怎么搞的

首先在图之中选一个Start Point，然后从他的Neighbor之中随机选择一个点，然后就Move to 这个随机选择的点，然后循环往复下去。那么这个选择的走过的Path就是一个Random Walk。用数学化的语言进行表示的话，在给定$G = (V,E)$的情况下，最大化

$$\max_{z} \sum_{u\in V} \log P(N_{R}(u) | z_{u})$$

其中的$N_{R}(u)$就是其Neighbor，大家如果学过NLP相关的内容可以发现这个就是Skipgram模型。如果对于网络之中的所有的节点都考虑进来，那么可以使用一个Likelihood表示

$$L = \sum_{u\in V}\sum_{v\in N_{R}(u)} -\log P(N_{R}(u) | z_{u})$$

那么接下来要考虑的问题是这里的概率用什么函数来进行表达，一般碰见了概率这种东西，我们很直接的想法就是使用Softmax函数

$$p(v|z_{u}) = \frac{\exp(z_{u}^{T} z_{v})}{\sum_{n\in V}\exp(z_{u}^{T} z_{v})}$$

那么最后的形式就可以得到了

对于所有的节点计算在其Random Walk之中所得到的Similarity。但是如果这样话计算的开销有点大，因为每算一轮的话，其计算的复杂度是$O(|V|^2)$.

所以我们寻找到一个其他的方法来很好的近似，这里的近似的方法也是如SkipGram之中的一样，通过Negative Sampling进行实现。

对于上面的

$$\log (\frac{\exp(z_{u}^{T} z_{v})}{\sum_{n\in V}\exp(z_{u}^{T} z_{v})})$$

可以近似成为

$$\log (\sigma (z_{u}^{T}z_{v})) – \sum_{i=1}^{k} \log (\sigma(z_{u}^{T}z_{n_{i}}))$$

其中的$n_{i}$是从原来的数据之中随机的采样得到的结果。这个采样就是所谓的负采样，因为其采样的范围不属于Neighbor，而是除了Neighbor之外的那些Node并且和他们计算相似度。

当然这个属于比较Basic的Version，我们应该如何的改进呢？

Node2Vec

在Node2Vec之中提出了两种策略分别是BDS策略以及DFS策略，两种策略分别是侧重于搜索当前的节点的周围的Neighbor还是搜索更遥远的Neighbor，有点像是玩文明先把周围给摸清楚还是探索未知的远方。

其中的BFS可以看成是优先搜索周围的点，也被称为是广度优先，而其中的DFS是优先搜索更远的点，被称为是深度优先。那么直观上很好理解，但是在数学上怎么处理呢？

假设上一个节点是从$s_{1}$，现在到了$w$，那么$w$面临三种选择，第一种选择是往回走，第二种选择是走向与$s_1$相连的$s_2$，第三种选择是走向与$s_1$不相连的$s_3,s_4$,他们的概率分别是

$$\begin{cases} \frac{1}{p} & dt =0 \\ 1 & dt =1 \\ \frac{1}{q} & dt =2\end{cases}$$

其中的$dt$表示的是与$s_1$的距离，如果是0就是返回自身，如果是1就是在$s_1$周围直接相连，如果是$2$就代表与$w$直接相连。通过这样的方式就可以控制是BFS还是DFS的强弱。

TransE

但是需要注意的是，上述的算法都完全没有考虑到节点直接的关系的多样性，可能是因为大家都是默认是节点直接是Contact就可以了，但是具体的Connect的方式却没有考虑进来，而这个关系在知识图谱之中至关重要。

在知识图谱之中，往往数据被记录为一个三元组的形式以(head entity , relation , tail entity)的形式进行储存。记作是

$$(h,l,t)$$

所以我们希望通过Embedding之后的结果可以达成一个下面的情况就是

$$h + l  = t$$

Head Entity加上了Relation就可以变成Tail Entity。下面的是训练的算法

输入了数据集之后首先对于关系和实体都进行初始化,而初始化的方法就是从Uniform Distribution之中采样作为随机初始化。做完这些之后，选择大小为 $b$的正样本Minibatch，再对于每一个Relation选择负样本集合。

选择完数据之后我们的目标是达成上面的那个目标，所以最小化正样本

$$||s+r-o||$$

而最大化负样本距离

$$||s’+r-o’||$$

用SGD直到Converge。还是很直观的一个方法

Graph Embedding

上述是对于节点进行Embedding，但是如果是针对一个图来说，怎么把整个Graph都进行Embedding呢？一个非常非常直接的方法就是把所有的节点的值都加起来，这个也是在NLP之中经常使用的技巧。

或者还有一个方法就是在里面创造一个Virtual Node代表整个图，或者是子图，再进行Embedding

还有一种方法叫做是Anonymous Walk Embedding，这个方法与上面的Random Walk不大一样，在对于Path记顺序的时候并非是以具体的节点为Record，而是以他的Relative Index作为Record

对于上面的所有的Possible的Walks进行Count，然后可以认为图就是一个Walks的概率的分布。

然后有了这个之后，其目标函数就可以写成是

$$P(w_{t}^{u} | w_{t-\Delta}^{u},\cdots ,w_{t}^{u} ) = f(z)$$

也就更好的利用到了Walk的Sequence的信息。这个模型也就像是从SkipGram这种Bag of Words模型变成了RNN这种Sequence的模型。不过我感觉这个东西还是非常的不Make Sense也没那么Elegant。持保留意见，以后看他的原Paper看看能不能改观。