【CS224W课程笔记】Graph Neural Networks

Limitation of ‘Shallow Encoders’

在Graph Repretention Learning一课中，我们已经学习了如何基于shallow encoders（基于Embedding Lookup将节点映射为向量）表示一个图，但其存在以下限制：

节点间的参数无法共享，每个节点的嵌入都是独一无二的。
无法未训练时没有见过的节点生成嵌入。
没有考虑节点自身的特性。

而今天将要学习的Graph Neural Networks可以解决上述限制，其基本思想在于基于图结构进行多层非线性变换对节点进行编码。现代深度学习工具基本是为简单的序列和网格来设计的，将其用于网络/图的难点在于：

网络/图具有任意的大小和复杂的拓扑结构，即不同于网格那样的空间局限性；
网络/图没有固定的节点顺序或参考点
网络/图通常是动态的且具有多模态的特征

Graph Convolutional Networks (GCN)

Setup

给定一个图 $G=(V, A, X)$ ，其中 $V$ 为节点（vertex）集合， $A$ 表示邻接矩阵， $X \in \mathbb{R}^{m \times |V|}$ 表示节点特征矩阵。

Computational Graph and Generalized Convolution:

aggregate neighbors

给定上图左侧的图 $G$ ，我们的目标是基于 $G$ 定义GCN的计算图，这一计算图需要保留 $G$ 的结构，同时合并节点的相邻特性，例如节点 $A$ 的嵌入尤其邻居 $\{B,C,D\}$ 组成，但不取决于 $\{B,C,D\}$ 这样的顺序。一个简单的方法就是取 $\{B,C,D\}$ 特征向量的平均。一般而言，聚合方程（上图右侧部分的灰盒）应是顺序无关的（order invariant，如max、average等操作）。带有两层的基于 $G$ 的计算图形式如下：

computation graph

图中的每个节点都基于其邻居定义了计算图，例如节点 $A$ 的计算图如下，其中Layer-0，即第0层为输入层，其输入为各节点的特征向量。

computation graph for a

Deep Encoders

基于上述思想，使用平均聚合方程给出每层节点 $v$ 的数学表达式如下：

在第0层， $h_v^0 = x _v$ ，即节点特征；
在第k层， $h_v^k = \sigma (W_k \sum_{u \in N(v)} \frac{h_u^{k-1}}{|N(v)|}), \forall{k \in \{1,\dots,K\}}$
在输出层，假设经过 $K$ 层，最终得到的embedding为 $z_v = h_v^K$

其中 $|N(v)|$ 表示节点 $v$ 的邻居数量； $\sum_{u \in N(v)} \frac{h_u^{k-1}}{|N(v)|}$ 的目的在于聚合节点 $v$ 的邻居在上一层的特征； $\sigma$ 表示激活函数（如ReLU）用于引入非线性； $W_k \text{和} B_k$ 均为需要训练的参数。

等价的，以上计算可以基于整个图写成矩阵相乘的形式如下：
$H^l = {[{h_1^l}^\top, \dots, {h_N^l}^\top]}^\top \\ H^{l+1} = \sigma (H^l W_0^l + \tilde{A} H^l W_1^l) \\ \text{其中，}\tilde{A} = D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \\$

Training the Model

接下来就可以将这些embeddings送入任意损失函数并经由随机梯度下降训练参数。例如，对于一个二分类任务，可以将损失函数定义如下：
$L = \sum_{v \in V} y_v log(\sigma (z_v^\top \theta)) + (1-y_v)log(1-\sigma(z_v^\top \theta))$
其中， $y_v \in \{0, 1\}$ 为节点的类别标签； $z_v$ 为encoder的输出； $\theta$ 为分类权重； $\sigma$ 可以是sigmoid函数； $\sigma(z_v^\top \theta)$ 代表节点 $v$ 的预测概率。因此，公式的前半部分将在 $y_v=1$ 时起到作用，而当 $y_v=0$ 时，则是式子的后半部分起作用。
此外，还可以通过random walk、graph factorization、node proximity等方式以无监督的形式训练模型。

Inductive Capability

GCN可泛化到图中未曾见过的节点。例如，假设一个模型是通过节点 $A,B,C$ 训练的，由于所有节点之间的参数是共享的，新加入的节点 $D,E,F$ 同样可以参与运算。

GraphSAGE

上述介绍的是一种简单的邻居聚合方法，我们还可以以下形式概括性地表示聚合方法：
$h_v^K = \sigma ([W_k AGG({h_u^{k-1}, \forall u \in N(v)}), B_k h_v^{k-1}])$
即对于节点 $v$ 。我们可以采用不同的方法聚合其邻居，然后再将其与自身特征拼接。常用的聚合方法有以下几种：

Mean：计算所有邻居特征的加权平均。
$AGG=\sum_{u \in N(v)} \frac{h_u^{k-1}}{|N(v)|}$
Pooling：对邻居向量进行转换并运用对称向量函数（式中的 $\gamma$ 可以是element-wise mean或max）。
$AGG=\gamma (\{Q h_u^{k-1}, \forall u \in N(v) \})$
LSTM：
$AGG = LSTM(\{h_u^{k-1}, \forall u \in \pi (N(v))\})$

Graph Attention Networks

考虑到部分节点携带的信息比其它节点重要的情况，可以采用attention机制对不同的邻居节点分配不同的权重。
令 $\alpha_{vu}$ 代表节点 $u$ 要传递给节点 $v$ 的信息的权重因子（重要性）。在上述平均聚合方案中，我们定义 $\alpha = \frac{1}{|N(v)|}$ ，此时我们可以根据图的结构属性明确定义 $\alpha$ 。

Attention Mechanism

节点 $u,v$ 的注意力得分基于其携带的信息计算如下：
$e_{vu} = a(W_k h_u^{k-1}, W_k h_v^{k-1})$
其中 $a$ 表示任意注意力计算方式， $e_{vu}$ 表示了节点 $u$ 要传递给节点 $v$ 的信息的重要性。
接下来使用softmax进行归一化处理以比较不同邻居之间的重要性：
$\alpha_{vu}=\frac{exp(e_{vu})}{\sum_{k \in N(v)} exp(e_{vk})}$
继而可以计算得到：
$h_v^k = \sigma(\sum_{u \in N(v)} \alpha_{vu} W_k h_u^{k-1})$