图机器学习——2.3 整图嵌入

图机器学习——2.3 整图嵌入 整图嵌入

整图嵌入的想法是将一个完整的图结构嵌入为一个向量。通常有如下三种做法：

1）节点嵌入求和

一种非常简洁且有效的图嵌入方式是将图所有节点的嵌入结果进行求和或平均（Duvenaud et al., 2016）：
z G = ∑ v ∈ G z v boldsymbol{z}_{boldsymbol{G}}=sum_{v in G} boldsymbol{z}_{v} zG​=v∈G∑​zv​

2）虚拟节点

另一种比较简单的想法是将一个子图结构作为一个虚拟节点，而后运行前文叙述的标准节点嵌入算法（Proposed by Li et al., 2016）

3）匿名随机游走嵌入（anonymous walk embeddings）

匿名漫步中的状态（标签）对应于我们在随机游走中第一次访问该节点的索引。以下图为例：

有一个由A-F标签组成的图结构，我们分别在这个图上进行随机游走（随机选择初始节点）。

• 第一次游走的顺序为：A-B-C-B-C，对此序列进行编码，在此序列中第一次遇到的状态记为一个新的索引。因此上述序列对应的索引为 1-2-3-2-3；
• 第二次游走的顺序为：C-D-B-D-B，同样进行编码，也是1-2-3-2-3；
• 第三次游走的顺序为：A-B-A-B-D，编码为：1-2-1-2-3；
• 以此类推。

当给定的随机游走长度为2时，编码有两种情况：
w 1 = 11 , w 2 = 12 w_1=11, w_2=12 w1​=11,w2​=12

随机游走长度为3时，可行的编码共5种：
w 1 = 111 , w 2 = 112 , w 3 = 121 , w 4 = 122 , w 5 = 123 w_{1}=111, w_{2}=112, w_{3}=121, w_{4}=122, w_{5}=123 w1​=111,w2​=112,w3​=121,w4​=122,w5​=123

游走长度与编码个数的对应关系如下图所示：

可以看出，匿名游走的种类个数随着游走长度指数增长。接着我们可以按照匿名游走的不同种类，构建嵌入向量 z G mathbf{z}_{G} zG​：

z G [ i ] =  匿名游走  w i 在图  G 中出现的概率  mathbf{z}_{G}[i]=text { 匿名游走 } w_{i} text {在图 } G text {中出现的概率 } zG​[i]= 匿名游走 wi​在图 G中出现的概率 

也即数出现的次数，再除以游走的总数即可。关于训练时需要抽样游走的总数可以利用下式进行计算：

m = [ 2 ε 2 ( log ⁡ ( 2 η − 2 ) − log ⁡ ( δ ) ) ] m=left[frac{2}{varepsilon^{2}}left(log left(2^{eta}-2right)-log (delta)right) right] m=[ε22​(log(2η−2)−log(δ))]

其中，我们分布的误差大于 ε varepsilon ε的概率小于 δ delta δ， l l l为游走的长度， η eta η为游走的种类数（如，按照前面的对应关系 l l l取7， η eta η就为877）。我们就可以计算出对应需要的抽样个数了。

但上面简单计算出现次数百分比不是一个很好的表示策略，这里引入一个更好的嵌入训练策略。

我们首先定义一个全图的嵌入： z G mathbf{z}_{G} zG​，接着再为每一种游走定义一个嵌入方法： Z = { z i : i = 1 … η } boldsymbol{Z}=left{mathbf{z}_{boldsymbol{i}}: i=1 ldots etaright} Z={zi​:i=1…η}， η eta η为游走的种类数。下面我们计划通过当前 Δ Delta Δ期的嵌入以及全图的嵌入，预测下一次游走的嵌入情况。目标函数定义为：

max ⁡ z G ∑ t = Δ + 1 T log ⁡ P ( w t ∣ w t − Δ , … , w t − 1 , z G ) max _{z_{G}} sum_{t=Delta+1}^{T} log Pleft(w_{t} mid w_{t-Delta}, ldots, w_{t-1}, mathbf{z}_{G}right) zG​max​t=Δ+1∑T​logP(wt​∣wt−Δ​,…,wt−1​,zG​)

T T T为不同随机游走的个数，以下图为例：

若 Δ = 3 Delta=3 Δ=3，则我们需要用 w 1 , w 2 , w 3 w_1, w_2, w_3 w1​,w2​,w3​以及全图的嵌入信息 z G mathbf{z}_{G} zG​来预测 w 4 w_{4} w4​。由于实际上每一个游走的嵌入 z i mathbf{z}_{i} zi​ 也需要进行训练得到，因此优化目标为：

max ⁡ z i , z G 1 T ∑ t = Δ T log ⁡ P ( w t ∣ { w t − Δ , … , w t − 1 , z G } ) max _{z_{i}, z_{G}} frac{1}{T} sum_{t=Delta}^{T} log Pleft(w_{t} midleft{w_{t-Delta}, ldots, w_{t-1}, mathbf{z}_{boldsymbol{G}}right}right) zi​,zG​max​T1​t=Δ∑T​logP(wt​∣{wt−Δ​,…,wt−1​,zG​})

其中：
P ( w t ∣ { w t − Δ , … , w t − 1 , z G } ) = exp ⁡ ( y ( w t ) ) ∑ i = 1 η exp ⁡ ( y ( w i ) ) , Pleft(w_{t} midleft{w_{t-Delta, ldots}, w_{t-1}, mathbf{z}_{G}right}right)=frac{exp left(yleft(w_{t}right)right)}{sum_{i=1}^{eta} exp left(yleft(w_{i}right)right)}, P(wt​∣{wt−Δ,…​,wt−1​,zG​})=∑i=1η​exp(y(wi​))exp(y(wt​))​,

y ( w t ) = b + U ⋅ ( cat ⁡ ( 1 Δ ∑ i = 1 Δ z t − i , z G ) ) . yleft(w_{t}right)=b+U cdotleft(operatorname{cat}left(frac{1}{Delta} sum_{i=1}^{Delta} boldsymbol{z}_{t-i}, boldsymbol{z}_{boldsymbol{G}}right)right). y(wt​)=b+U⋅(cat(Δ1​i=1∑Δ​zt−i​,zG​)).

cat是指将两种嵌入进行拼接，一种为前 Δ Delta Δ期的嵌入取平均，另一种为全图的嵌入。 b b b为偏置项， U U U为长度是 z i mathbf{z}_{i} zi​与 z G mathbf{z}_{G} zG​长度相加，两个参数都是可训练的。最终，由于游走的随机性，而全图的嵌入对图中每一种游走的预测都有帮助，因此最终训练出的全图嵌入 z G mathbf{z}_{G} zG​能够尽可能涵盖整个图的信息。整体的训练过程如下：

参考

• CS224W: Machine Learning with Graphs