MENU

GNN详解

February 14, 2021 • Read: 343 • Deep Learning阅读设置

Introduction

既然你点进了这篇博客,我就默认你了解图的最基本概念,包括但不限于有向图、无向图的定义,这里我不再多做赘述,下面我只阐述一些比较重要的部分

图神经网络是一种直接对图结构进行操作的神经网络。GNN的一个典型应用是节点分类。本质上,图中的每一个节点都与一个标签相关联。如下图所示,a节点的向量表示为[0.3, 0.02, 7, 4, ...],将该向量送入下游继续做分类即可得到a节点的类别

a节点的向量表示究竟是如何得到的,等会儿我会详细阐述,不过在这我们可以简单的思考一下,a节点的向量表示一定应该与其相邻节点相邻边有关系,假设每个节点$v$的one-hot向量表示为$X_v$,则

$$ h_v=f(X_v, X_{co[v]}, h_{ne[v]},X_{ne[v]}) $$

其中$X_{co[v]}$表示与$v$相连边的one-hot表示,$h_{ne[v]}$表示与$v$相邻节点的embedding,$X_{ne[v]}$表示与$v$相邻节点的one-hot表示。最终再将$h_v$向量和真实标签计算loss,不过也有的地方是将$h_v$向量和$X_v$经过一轮融合之后再计算loss,例如

$$ \begin{aligned} O_v&=g(h_v,X_v)\\ loss &= \sum_{i=1}^p (t_i-o_i) \end{aligned} $$

上述公式以及符号可能不好理解,这里其实可以类比Word2Vec。在Word2Vec中,输入的是每个词对应的one-hot,即$X_v$。输出的是这个词对应的embedding,即$h_v$

DeepWalk:第一个无监督学习节点嵌入的算法

DeepWalk用一句话概述就是:随机生成图节点序列,然后对该序列进行Word2Vec

具体来说,给定一个图,我们随机选择一个节点作为起始,然后随机"步行"到邻居节点,直到节点序列的长度达到给定的最大值。例如下图,分别选择d,e,f作为起点进行游走,得到三条节点序列

在这种情况下,我们可以将节点和节点序列分别看作是"单词"和"句子",然后利用skip-gram或者cbow算法训练得到每个节点的embedding

node2vec:bias random walk

一般的随机游走公式

$$ {P}\left(c_{i}=x \mid c_{i-1}=v\right)=\left\{\begin{array}{cc} \frac{1}{|N(v)|}, & \text { if }(v, x) \in E \\ 0, & \text { otherwise } \end{array}\right. $$

其中,$|N(v)|$表示$v$节点的邻居节点数量,$c_{i-1}$表示当前节点,$c_i$表示下一个选择的节点

一般的随机游走存在以下几个问题:

  1. 如果是带权图,没考虑到边权值的影响
  2. 太过于随机,不能由模型自行学习以何种方式游走更好

实际上图的游走分两大类,即DFS和BFS

为了引入边权,以及依概率选择DFS或BFS,我们首先要将一般的随机游走公式进行修改

$$ {P}\left(c_{i}=x \mid c_{i-1}=v\right)=\left\{\begin{array}{cc} \frac{\pi_{vx}}{Z}, & \text { if }(v, x) \in E \\ 0, & \text { otherwise } \end{array}\right. $$

其中,$\frac{\pi_{vx}}{Z}$在值上与$\frac{1}{|N(v)|}$是相等的,$Z$可以理解为归一化的缩放因子

设节点$v$和$x$之间的边权为$w_{vx}$,则可以将$\pi_{vx}$改写为$\alpha_{pq}(t,x)\cdot w_{vx}$

$$ \alpha_{{pq}}(t, x)=\left\{\begin{array}{l} \frac{1}{p}, &\quad{ \text { if } d_{t x}=0} \\ 1, &\quad{\text { if } d_{t x}=1} \\ \frac{1}{q}, &\quad{ \text { if } d_{t x}=2} \end{array}\right. $$

其中,$d_{tx}$表示当前节点$v$的一阶邻居节点到节点$t$的距离

  • $p$:控制随机游走以多大的概率"回头"
  • $q$:控制随机游走偏向DFS还是BFS

    • $q$较大时$(q>1)$,倾向于BFS
    • $q$较小时$(q<1)$,倾向于DFS
  • $p=q=1$时,$\pi_{vx}=w_{vx}$

到此为止,GNN中节点Embedding算法我就不再多叙述,其实还有很多更好的算法,例如LINE,Struct2vec等,不过我个人感觉这些embedding算法并不重要,或者说它们并不是GNN的核心部分,只要当作工具来用就行了,类比Transformer中Word Embedding的地位

References

Last Modified: March 1, 2021
Archives Tip
QR Code for this page
Tipping QR Code