无监督学习方法——Node Embedding
| 原始网络 | 嵌入空间 | |
|---|---|---|
| 度量标准 | $similarity(u,v)$ | $z_{v}^{T}z_{u}$ |
Embedding-lookup
其实就是一个哈希表，key为节点，value为节点的embedding。
今天的课程都是这种look-up性质的Embedding，它是静态的，在之后的downstream任务中是不会改变的。
Step 1：定义Similarity
Random Walk Approaches to Node Embedding
本小节讲解的是下面两篇论文：
- Perozzi et al. 2014. DeepWalk: Online Learning of Social Representations. KDD.
- Grover et al. 2016. node2vec: Scalable Feature Learning for Networks. KDD.
Random Walk
- random walk是一个名词，它是图上的一个节点序列；
- random walk的长度是一个自定义的参数，需要根据不同的应用场景进行选择；
你可能会想，我明明在学习Node Embedding，为什么要给我讲Random Walk呢？难道Random Walk可以帮助我们来设计学习Node Embedding的算法？
修改random walk的类型，那么我们就能定义不同的相似性，比如neighborhood，structural role等等。
基于random-walk的embedding的思想是：
为什么固定为dot product为$cos(\theta)$呢？
因为概率的大小是介于[0,1]之间的。
选择random walks作为similarity的原因
表达性：采用不同的random walk机制，能够获取到局部和全局的信息。
高效性：Node Embedding算法要优化是$z_{v}^{T}z_{u}$，如果考虑所有的$(src，dst)$对，那么计算量将会是巨大的。在random walk中，我们只考虑出现在同一random walk中的$(v,u)$对，这无疑减少了计算量。（Scalable）
这一点在图变得越来越大的时候，尤其的重要！
对于基于Random Walk的Node Embedding算法来说，random walk的采集策略是非常重要的，可以说绝大部分的算法都是在对这个策略进行创新。不同的策略将会产生不同的$N_{R}(u)$。
- 这个式子有点极大似然估计的味道；
- ==为什么要使用Log-likelihood作为目标函数？==
- 对于概率$P(N_R(u)|z_u)$，我们知道它是一个介于[0,1]之间的数字，是非常小的。老师说小的数字将会在训练过程中引发numerical instability；
- 而且，使用它并不会改变我们的直观感受。
算法流程
$P(N_R(u)|z_u)$依然很抽象，我们没有定义它的计算方式，接下来我们定义一下：
同时，我们书写出我们的loss function：
需要注意的是这里计算了$V$中的所有顶点$v$！！！
我们的Loss Function的时间复杂度在$O(|V^2|)$，这是非常大的。
需要解决这些问题，我们就需要来拆解$O(|V^2|)$，首先对于第一个$V$，我们无法减小，因为我们一定需要对于每一个节点都要求和的。所以我们要从第二个$V$减小，或者说是approximate it。
解决的办法就是Negative Sampling——
Negative Sampling
noise contrastive estimation
噪声对比评估
- quadratic
- linear
关于负采样中需要采集的样本数$k$，它需要正比于节点的度。（没听懂）
node2vec
DeepWalk的similarity的定义方式太狭隘了，它只是考虑了连接。但是如果我们想要抽取structure role这样的相似性，那么它就显然不适用了，因此需要修改。
node2vec实现了local和global的一个平衡。
DeepWalk做的工作一直是local，现在我们考虑一下global的。
interpolating：插值
为什么称为是2nd-order，因为我们保留了prev_node。
p,q是超参数，需要进行学习。将BFS的概率设置为1，是为了减少参数的数量。
How to Use Embeddings？
既然要结合$z_i$和$z_j$就需要结合函数，有以下几种：
根据不同的任务使用不同的embedding方法
Translating Embeddings for Modeling Multi-relational Data
在知识图谱上我们经常做一个KG Completion的任务
还要知道link的type是什么？
两个蓝色节点应该越来越近，两个蓝色节点都有the genre edge指向fantasy，那么这两个蓝色节点应该越来越近才是。
translate：平移
