Graph Neural Network（GraphSAGE，GAT）

Graph图论问题。如生成树算法，最短路径算法，BFS，DFS。概率图模型。将条件概率表达为图结构，如马尔可夫链，条件随机场。图神经网络。结合深度学习，如博主已经整理过的Graph Embedding，Graph LSTM/CNN等结合。基本上Graph+Neural Network，即使用了深度学习技术解决图问题就都是GNN的范畴了。而GNN主要是为了解决Non-Euclidean结构的...

上杉翔二

5582人浏览 · 2020-01-09 15:48:44

上杉翔二 · 2020-01-09 15:48:44 发布

Graph

图论问题。如生成树算法，最短路径算法，BFS，DFS。
概率图模型。将条件概率表达为图结构，如马尔可夫链，条件随机场。
图神经网络。结合深度学习，如博主已经整理过的Graph Embedding，Graph LSTM/CNN等结合。基本上Graph+Neural Network，即使用了深度学习技术解决图问题就都是GNN的范畴了。而GNN主要是为了解决Non-Euclidean结构的特征向量学习，即学习一个包含每个节点的邻域信息的状态嵌入。

GraphSAGE
上图出自2017的《Inductive representation learning on large graphs》。首先GNN的学习方法可以分为两种：

直推式学习（transductive）：直接学到每个节点的一个唯一确定的embedding向量。但一旦graph结构变化了，所有特征向量是需要重新学习的，所以无法直接泛化新节点(unseen node)。博主已经整理过的Graph Embedding，还有GCN都是代表，输入往往为一个矩阵，也是基于矩阵进行学习，无法应对transductive的问题。
归纳式学习（inductive）：从特殊到一般，node embedding，根据node的邻居关系的变化而变化的。即学习节点之间的聚合模式，就可以利用节点邻域的聚合模型直接学习出新节点的嵌入特征，而无需额外训练过程。

而GraphSAGE则是归纳式学习的一个代表，不学习每个节点的固定表示，而是学习节点之间的聚合函数，即节点的信息是通过其邻居节点的特征聚合而来的，所以仅需邻域即可处理新节点了。那么如何学习聚合函数？

先对邻节点随机采样，因为每个节点的度是不一致的，为了计算高效，为每个节点分层(K层)采样固定数量的邻居。采样分一跳采样数和二跳采样数（与之前的一阶和二阶是一样的概念，邻居和邻居的邻居），如图中的K=1，和K=2
聚合采样到的邻居特征，更新当前节点的特征。首先聚合最远跳的结点特征，如第 2 跳结点特征。由第二跳能得到第一跳结点的特征，再聚合第一跳邻居特征，就得到当前节点的嵌入特征了，此时的特征包含着一跳和二跳的节点信息（每一层的node的表示都是由上一层生成的，跟本层的其他节点无关），此时可以有多种聚合的方式。
无监督训练：节点与邻居的向量应该相似： $J=-log(\sigma(z_u^Tz_v))-Q \cdot E_{v_n}[log(\sigma(z_u^Tz_{v_n}))]$ 其中vn是负采样随机游走到的邻居节点，z是特征。
有监督训练：再使用全连接层，预测目标节点的标签以监督模型。损失函数可以为交叉熵等适合特定目标的loss，然后梯度下降。

多种聚合方式：

Mean aggregator。对邻居向量的每个维度取平均，然后与自己拼接再非线性。 $h^k_{N(v)}=mean({h^{k-1}_u,u\in N(v)})$ $h^k_v=\sigma(W^k \cdot CONCAT(h^{k-1}_v,h^{k-1}_{N(v)}))$
GCN aggregator。和平均很像，只是它是对当前节点和所有邻居 emebdding 中每个维度取平均（这不就是GCN的计算方法了。。。是的） $h^k_v=\sigma(W^k \cdot mean(所有邻居特征))$
LSTM aggregator。邻居节点应该符合“排序不变量”的性质，所以采样的node先随机排序shuffle后再算特征
pooling。按维度 max/mean pooling

其实集中图神经网络的不同关键在于聚合方式，表现在两个方面，一个是邻居节点的聚合（mean，norm，plain），一个是本身和聚合邻居节点的聚合（加法，拼接，点乘）。比如GCN采用本身的表达（自环）加上邻居节点的聚合表达，GraphSage则采用拼接的方式，而接来下要介绍的GAT则是使用一种类似于自注意力机制的表达。

#作者实验中 K=2，即聚合两跳内邻居特征；一跳采样邻居数S1=25，二跳采样邻居S2=10个节点：采样随机游走步长为 5 的且50 次，
负采样采样 20 个。
def aggregate(self, samples, input_features, dims, num_samples, support_sizes, batch_size=None,
            aggregators=None, name=None, concat=False, model_size="small"):
        if batch_size is None:
            batch_size = self.batch_size
            
        hidden = [tf.nn.embedding_lookup(input_features, node_samples) for node_samples in samples]
        new_agg = aggregators is None
        if new_agg:
            aggregators = []
        for layer in range(len(num_samples)):
            if new_agg:
                dim_mult = 2 if concat and (layer != 0) else 1
                #聚合当前层
                if layer == len(num_samples) - 1:
                    aggregator = self.aggregator_cls(dim_mult*dims[layer], dims[layer+1], act=lambda x : x,
                            dropout=self.placeholders['dropout'], 
                            name=name, concat=concat, model_size=model_size)
                else:
                    aggregator = self.aggregator_cls(dim_mult*dims[layer], dims[layer+1],
                            dropout=self.placeholders['dropout'], 
                            name=name, concat=concat, model_size=model_size)
                aggregators.append(aggregator)
            else:
                aggregator = aggregators[layer]
            #多跳
            next_hidden = []
            #层数增加，采样邻居数逐渐减少
            for hop in range(len(num_samples) - layer):
                dim_mult = 2 if concat and (layer != 0) else 1
                #support邻居
                neigh_dims = [batch_size * support_sizes[hop], 
                              num_samples[len(num_samples) - hop - 1], 
                              dim_mult*dims[layer]]
                h = aggregator((hidden[hop],
                                tf.reshape(hidden[hop + 1], neigh_dims)))
                next_hidden.append(h)
            #下一跳
            hidden = next_hidden
        return hidden[0], aggregators

完整的细节源代码逐行中文注释：https://github.com/nakaizura/Source-Code-Notebook/tree/master/GraphSAGE

GraphSAGE的优点

归纳式。学习节点特征的映射，泛化性更强。
采样。使用minibatch批训练，复杂度降低泛化提高。
多样的聚合函数。多种聚合可自由选择。

采样数大于邻居数怎么办？
一般是采用无放回的抽象，但如果采样数大了，可以采用有放回的抽样方法直到采完K个节点。同时原文用的是uniform均匀采样的，其实用像PinSage那种按重要性采结果也不错。

哪种聚合函数好？
LSTM>pooling>mean

怎么用在有向图中？
只要采样的时候考虑到方向性就行了。

怎么用在无监督学习中？
让“近”的节点的表示相似，“远”的节点表示尽可能可被区分。所以可以用负采样的方法，把近的节点做正样本，远的节点是负样本，然后Word2vec。至于这个“近”的定义可以是从某节点能够随机游走到的节点，其他不能游走到的则认为是远的节点。

GraphSAGE的缺点是什么？
采样会随着阶数深度增加而指数增加。
在这里插入图片描述
GAT
Bengio ICLR2018年的《Graph Attention Network 》。按照Transductive learning的方式，需要对所有节点得到结果，所以训练好的GCN是无法用在不一样的图结构上的。GAT是另一种解决方案，即Attention。一般来说GCN分为两大类，一种是谱图卷积，是在傅里叶域进行卷积变换;另一种是非谱图卷积(也叫做“空间域卷积”)，是直接在Graph上进行卷积，GAT就属于空间域卷积，而且放松了邻点个数和边的权重这两个限制条件图。

Attention的特点是自适应，所以即便图结构不一样，度数不相同，也可以通过动态计算邻域节点和该节点的强度关系weight来适应，所以GAT可移植到其他的图结构上，不需要与训练集完全相同。

对于节点特征向量 $h=\{h_1,h_2...h_n\}$ ，最后需要更新得到 $h'=\{h'_1,h'_2...h'_n\}$ 。计算领域Attention使用MLP方法，即公式为： $e_{ij}=a^T[Wh_i||Wh_j]$ $\alpha_{ij}=softmax(e_{ij})$ 该式计算，节点 j 对于节点 i 的重要性，a是MLP的权重，W是所有节点之间的权值（抽象特征，从h到h’的线性转换）。由上图左边就是W和a权重的区别和Attention的计算过程，清晰易懂。

由于使用的是masked attention，即只算邻居向量，所以不会关心整个图的结构问题，也就解决了问题（同时也是缺点）。最后乘以权重得到结果：
$h'_i=\sigma(\sum \alpha_{ij}Wh_j)$

multi-head attention。上图右侧是使用了多个注意力呗，只需要concat/avg K个注意力的结果再更新h’就行了。（作者建议对中间层使用拼接对最后一层使用求平均）

def attn_head(seq, out_sz, bias_mat, activation, in_drop=0.0, coef_drop=0.0, residual=False):
    with tf.name_scope('my_attn'):
        if in_drop != 0.0:
            seq = tf.nn.dropout(seq, 1.0 - in_drop)#seq是原始的节点

        seq_fts = tf.layers.conv1d(seq, out_sz, 1, use_bias=False)#一维卷积模拟nn投影

        #自注意力self-attention
        f_1 = tf.layers.conv1d(seq_fts, 1, 1) #Wh，一维卷积模拟投影
        f_2 = tf.layers.conv1d(seq_fts, 1, 1) #Wh
        logits = f_1 + tf.transpose(f_2, [0, 2, 1]) #拼接，注意力矩阵
        #bias_mat是邻居mask矩阵，不是邻居的会有无限小（exp时就为0）mask
        coefs = tf.nn.softmax(tf.nn.leaky_relu(logits) + bias_mat) #softmax分配权重

        if coef_drop != 0.0:
            coefs = tf.nn.dropout(coefs, 1.0 - coef_drop)
        if in_drop != 0.0:
            seq_fts = tf.nn.dropout(seq_fts, 1.0 - in_drop)

        vals = tf.matmul(coefs, seq_fts) #分配值
        ret = tf.contrib.layers.bias_add(vals)

        # residual connection，残差连接保持特征一定的不变性
        if residual:
            if seq.shape[-1] != ret.shape[-1]: #维度不等就再投影一下
                ret = ret + conv1d(seq, ret.shape[-1], 1) # activation
            else:
                ret = ret + seq #相加

        return activation(ret)  # activation

完整的细节源代码逐行中文注释：https://github.com/nakaizura/Source-Code-Notebook/tree/master/GAT

非对称的注意权重
比较以下两个注意力权重公式。
$e_{ij}=a(Wh_i,Wh_j)$ $e_{ij}=a^T[Wh_i||Wh_j]$ 这里我之间奇怪了好久，为什么不直接算相似度计算注意力呢？非要拼接之后计算e。理由是这里拼接导致 $e_{ij}$ 和 $e_{ij}$ 是不等的，也就是说注意力值是非对称的！非对称的有点在于，我与大佬和大佬看我是完全不一样的东西，本来这种相互关系就是不对等。

LeakyReLU
这里同样也是为了非对称！首先按公式，拼接的部分是可以拆开的：
$exp(a^T[Wh_i || Wh_j])=exp(a_1^TWh_i)exp(a_2^TWh_j)$ 那么如果不用LeakyReLU激活，直接softmax归一化话：
$\alpha=\frac{exp(a_1^TWh_i)exp(a_2^TWh_j)}{\sum_{k \in N_i} exp(a_1^TWh_i)exp(a_2^TWh_k)}=\frac{exp(a_2^TWh_j)}{\sum_{k \in N_i} exp(a_2^TWh_k)}$ 可以看到a1被约掉了。节点(i,j)之间的注意力权重都将不会考虑节点i的表示，所以LeakyReLU这也为了防止被约掉。

如何理解attention？
其实GCN版已经不算是很正统的谱域方法了，它也是直接把节点拿出来然后做特征变换再聚合，而且在“卷积”上GCN也并没有真的卷积，是借助拉普拉斯矩阵完成的。所以GAT认为还是需要一个卷积核比较好，所以公式中的a实际上就是这个功能。

谱方法与空间方法
区别在于：谱方法需要显式的定义卷积核，比如傅里叶那就是会投影到拉普拉斯的那个空间，小波变换就是小波变换的基函数了，即需要显式的定义。而近些年的空间方法不需要，只需要一个核函数就可以了，至于什么空间管他呢。这里可以联想到以前SVM需要显式的定义核，而监督学习方法出来之后只需要给一个loss就可以了。所以谱方法实际上是空间方法的一种特例，一种需要显式定义基空间的特例。

Transformer 与 GAT
两者都是用了self-attention，都是找关联，算注意力权重，再通过对上下文或者节点邻居聚合，最后得到节点or词的表示。嘛，虽然说Transformer其实是隐式图的暴力解，还是会有一点点不同：