一文详解图神经网络(sa)

5.2 《Semi-Supervised Classification with Graph Convolutional Networks》

这篇论文受到谱图卷积的局部一阶近似可以用于对局部图结构与节点的特征进行编码从而确定卷积网络结构的启发，提出了一种可扩展的图卷积的实现方法，可用于具有图结构数据的半监督学习

5.2.1 GCN定义

按照图傅里叶变换的性质，可以得到如下图卷积的定义：

其中：

• 对于图的傅里叶变换为的傅里叶变换为的傅里叶变换为
• 对于卷积核的图傅里叶变换：其中,按照矩阵形式就是
• 对两者的傅里叶变换向量和求element-wise乘积，等价于将组织成对角矩阵，即，然后再求和矩阵乘法
• 求上述结果的傅里叶逆变换，即左乘

深度学习中的卷积就是要设计trainable的卷积核，从上式可以看出，就是要设计，由此，可以直接将其变为卷积核，而不需要再将卷积核进行傅里叶变换，由此，相当于直接将变换后的参量进行学习

第一代GCN

其中，就是graph上对应每个节点的feature构成的向量，，这里暂时对每个节点都使用标量，然后经过激活之后，得到输出，之后传入下一层

一些缺点：

• 需要对拉普拉斯矩阵进行谱分解来求，在graph很大的时候复杂度很高。另外，还需要计算矩阵乘积，复杂度为
• 卷积核参数为，当graph很大的时候，会很大
• 卷积核的spatial localization不好

第二代GCN

图傅里叶变换是关于特征值(相当于普通傅里叶变换的频率)的函数，也就是，即，因此，将卷积核写成，然后，将定义为如下k阶多项式：

将卷积公式带入，可以得到：

这一代的GCN不需要做特征分解，可以直接对Laplacian矩阵做变换，通过事先将Laplacian矩阵求出来，以及求出来，前向传播的时候，可以直接使用，复杂度为

对于每一次Laplacian矩阵和相乘，对于节点，相当于从邻居节点传递一次信息给节点，由于连续乘以了次Laplacian矩阵，那么相当于n节点的k-hop之内的节点能够传递信息给，因此，实际上只利用了节点的K-Localized信息

另外，可以使用切比雪夫展开式来近似，任何k次多项式都可以使用切比雪夫展开式来近似，由此，引入切比雪夫多项式的阶截断获得近似，从而获得对的近似

其中，，为切比雪夫向量，为第个分量，切比雪夫多项式使用递归的方式进行定义：，其中，，此时，带入到卷积公式：

其中，，因此，可以得到输出为：

第三代GCN

直接取切比雪夫多项式中，此时模型是1阶近似，将，带入可以得到：

其中，归一化拉普拉斯矩阵。为了进一步简化，令，此时只含有一个参数

由于的谱半径太大，使用归一化的trick：

其中，，

由此，带入卷积公式

如果推广到多通道，相当于每一个节点的信息是向量

其中，是节点数量，是通道数，或者称作表示节点的信息维度数。是节点的特征矩阵。相应的卷积核参数变化：

其中，为卷积核数量，那么卷积结果写成矩阵形式为：

上述操作可以叠加多层，对上述输出激活一下，就可以作为下一层节点的特征矩阵

一些特点：

• 取，相当于直接取邻域信息，类似于的卷积核
• 由于卷积核宽度减小，可以通过增加卷积层数来扩大感受野，从而增强网络的表达能力
• 增加了参数约束，比如，引入归一化操作

5.2.2 论文模型

论文采用两层的GCN，用来在graph上进行半监督的节点分类任务，邻接矩阵为，首先计算出，由此，前向网络模型形式如下：

其中，为输入层到隐藏层的权重矩阵，隐藏层的特征维度为，为隐藏层到输出层的权重矩阵，softmax激活函数定义为，，相当于对每一列做softmax，由此得到交叉熵损失函数为：

其中，为带有标签的节点集合

5.2.3 代码实现

import torch_geometric.nn as gnn
class GCN(nn.Module):
    def __init__(self, config, in_channels, out_channels):
        '''
            in_channels : num of node features
            out_channels: num of class
        '''
        super().__init__()
        self.config = config
        self.hidden_dim = config.hidden_dim
        self.dropout_rate = config.dropout_rate
        self.conv1 = gnn.GCNConv(in_channels, self.hidden_dim, improved = False, cached=True, bias=True, normalize=True)
        self.conv2 = gnn.GCNConv(self.hidden_dim, out_channels, improved = False, cached=True, bias=True, normalize=True)
    def forward(self, data):
        x, edge_index = data.x, data.edge_index
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        #x = F.dropout(x, p=self.dropout_rate) # If no drop out, accuracy 0.75 --> 0.80
        x = self.conv2(x, edge_index)
        #x = F.dropout(x, p=self.dropout_rate) # there are two dropout.. But performance bad.
        return x  

5.3 《Diffusion-Convolutional Neural Networks》

该模型对每一个节点(或边、或图)采用H个hop的矩阵进行表示，每一个hop都表示该邻近范围的邻近信息，由此，对于局部信息的获取效果比较好，得到的节点的representation的表示能力很强

5.3.1 任务定义

• 一个graph数据集
• graph定义为，其中，为节点集合，为边集合
• 所有节点的特征矩阵定义为，大小为，其中，为图的节点个数，为节点特征维度
• 边信息定义为的邻接矩阵，由此可以计算出节点度(degree)归一化的转移概率矩阵，表示从节点转移到节点的概率

模型的目标为预测，也就是预测每一个图的节点标签，或者边的标签，或者每一个图的标签，在每一种情况中，模型输入部分带有标签的数据集合，然后预测剩下的数据的标签。DCNN模型输入图，返回硬分类预测值或者条件分布概率。该模型将每一个预测的目标对象(节点、边或图)转化为一个diffusion-convolutional representation，大小为，表示扩散的hops，表示为

• 对于节点分类任务，表示为为大小为的矩阵
• 对于图分类任务，张量为大小为的矩阵
• 对于边分类任务，张量为大小为的矩阵
  
  

5.3.2 论文模型

1. 对于节点分类任务，假设为的power series，大小为，那么对于图的节点，第个hop，第维特征值计算公式为：
   
   使用矩阵表示为：
   
   其中表示element-wise multiplication，由于模型只考虑跳的参数，即参数量为，使得diffusion-convolutional representation不受输入大小的限制

   在计算出之后，过一层全连接得到输出，使用表示硬分类预测结果，使用表示预测概率，计算方式如下：
   

2. 对于图分类任务，直接采用所有节点表示的均值作为graph的representation
   
   其中，是全为1的的向量

3. 对于边分类任务，通过将每一条边转化为一个节点来进行训练和预测，这个节点与原来的边对应的首尾节点相连，转化后的图的邻接矩阵可以直接从原来的邻接矩阵增加一个incidence matrix得到：
   
   之后，使用来计算，并用来替换来进行分类，对于模型训练，使用梯度下降法，并采用early-stop方式得到最终模型

5.3.3 代码实现

import lasagne
import lasagne.layers
import theano
import theano.tensor as T
import numpy as np
class DCNNLayer(lasagne.layers.MergeLayer):
    """A node-level DCNN layer.
    This class contains the (symbolic) Lasagne internals for a node-level DCNN layer.  This class should
    be used in conjunction with a user-facing model class.
    """
    def __init__(self, incomings, parameters, layer_num,
                 W=lasagne.init.Normal(0.01),
                 num_features=None,
                 **kwargs):
        super(DCNNLayer, self).__init__(incomings, **kwargs)
        self.parameters = parameters
        if num_features is None:
            self.num_features = self.parameters.num_features
        else:
            self.num_features = num_features
        self.W = T.addbroadcast(
            self.add_param(W,
                           (1, parameters.num_hops + 1, self.num_features), name='DCNN_W_%d' % layer_num), 0)
        self.nonlinearity = params.nonlinearity_map[self.parameters.dcnn_nonlinearity]
    def get_output_for(self, inputs, **kwargs):
        """Compute diffusion convolutional activation of inputs."""
        Apow = inputs[0]
        X = inputs[1]
        Apow_dot_X = T.dot(Apow, X)
        Apow_dot_X_times_W = Apow_dot_X * self.W
        out = self.nonlinearity(Apow_dot_X_times_W)
        return out
    def get_output_shape_for(self, input_shapes):
        """Return the layer output shape."""
        shape = (None, self.parameters.num_hops + 1, self.num_features)
        return shape

5.4 《Improved Semantic Representations From Tree-Structured Long Short-Term Memory Networks》

将序列型的LSTM模型扩展到树型的LSTM模型，简称Tree-LSTM，并根据孩子节点是否有序，论文提出了两个模型变体，Child-Sum Tree-LSTM模型和N-ary Tree-LSTM模型。和序列型的LSTM模型的主要不同点在于，序列型的LSTM从前一时刻获取隐藏状态，而树型的LSTM从其所有的孩子节点获取隐藏状态

5.4.1 论文模型

Tree-LSTM模型对于每一个孩子节点都会产生一个遗忘门￥f_{jk}￥，这个使得模型能够从所有的孩子节点选择性地获取信息和结合信息

1. Child-Sum Tree-LSTMs
   该模型的更新方程如下：
   
   其中，表示节点的邻居节点的个数，表示节点的隐藏状态，表示节点的输入门，表示节点的邻居节点的遗忘门，表示节点的输出门

   这里的关键点在于第三个公式的，这个模型对节点的每个邻居节点都计算了对应的遗忘门向量，然后在第六行中计算时对邻居节点的信息进行遗忘和组合

   由于该模型是对所有的孩子节点求和，所以这个模型对于节点顺序不敏感的，适合于孩子节点无序的情况

2. N-ary Tree-LSTMs
   假如一个树的最大分支数为(即孩子节点最多为个)，而且孩子节点是有序的，对于节点，对于该节点的第个孩子节点的隐藏状态和记忆单元分别用和表示，模型的方程如下：
   
   该模型为每个孩子节点都单独地设置了参数

5.4.2 训练策略

• 分类任务：

分类任务定义为在类别集中预测出正确的标签，对于每一个节点，使用一个softmax分类器来预测节点标签，分类器取每个节点的隐藏状态作为输入：

损失函数使用negative log-likelihood：

其中，是带有标签的节点数量，是是正则化超参

• 语义相关性任务：

该任务给定一个句子对(sentence pair)，模型需要预测出一个范围在之间的实数值，这个值越高，表示相似度越高。首先对每一个句子产生一个representation，两个句子的表示分别用和

表示，得到这两个representation之后，从distance和angle两个方面考虑，使用神经网络来得到相似度：

其中，，模型期望根据训练得到的参数得到的结果：。由此，定义一个目标分布：

其中，，损失函数为和之间的KL散度：

5.4.3 代码实现

class TreeLSTM(torch.nn.Module):
    '''PyTorch TreeLSTM model that implements efficient batching.
    '''
    def __init__(self, in_features, out_features):
        '''TreeLSTM class initializer
        Takes in int sizes of in_features and out_features and sets up model Linear network layers.
        '''
        super().__init__()
        self.in_features = in_features
        self.out_features = out_features
        # bias terms are only on the W layers for efficiency
        self.W_iou = torch.nn.Linear(self.in_features, 3 * self.out_features)
        self.U_iou = torch.nn.Linear(self.out_features, 3 * self.out_features, bias=False)
        # f terms are maintained seperate from the iou terms because they involve sums over child nodes
        # while the iou terms do not
        self.W_f = torch.nn.Linear(self.in_features, self.out_features)
        self.U_f = torch.nn.Linear(self.out_features, self.out_features, bias=False)
    def forward(self, features, node_order, adjacency_list, edge_order):
        '''Run TreeLSTM model on a tree data structure with node features
        Takes Tensors encoding node features, a tree node adjacency_list, and the order in which 
        the tree processing should proceed in node_order and edge_order.
        '''
        # Total number of nodes in every tree in the batch
        batch_size = node_order.shape[0]
        # Retrive device the model is currently loaded on to generate h, c, and h_sum result buffers
        device = next(self.parameters()).device
        # h and c states for every node in the batch
        h = torch.zeros(batch_size, self.out_features, device=device)
        c = torch.zeros(batch_size, self.out_features, device=device)
        # populate the h and c states respecting computation order
        for n in range(node_order.max() + 1):
            self._run_lstm(n, h, c, features, node_order, adjacency_list, edge_order)
        return h, c
    def _run_lstm(self, iteration, h, c, features, node_order, adjacency_list, edge_order):
        '''Helper function to evaluate all tree nodes currently able to be evaluated.
        '''
        # N is the number of nodes in the tree
        # n is the number of nodes to be evaluated on in the current iteration
        # E is the number of edges in the tree
        # e is the number of edges to be evaluated on in the current iteration
        # F is the number of features in each node
        # M is the number of hidden neurons in the network
        # node_order is a tensor of size N x 1
        # edge_order is a tensor of size E x 1
        # features is a tensor of size N x F
        # adjacency_list is a tensor of size E x 2
        # node_mask is a tensor of size N x 1
        node_mask = node_order == iteration
        # edge_mask is a tensor of size E x 1
        edge_mask = edge_order == iteration
        # x is a tensor of size n x F
        x = features[node_mask, :]
        # At iteration 0 none of the nodes should have children
        # Otherwise, select the child nodes needed for current iteration
        # and sum over their hidden states
        if iteration == 0:
            iou = self.W_iou(x)
        else:
            # adjacency_list is a tensor of size e x 2
            adjacency_list = adjacency_list[edge_mask, :]
            # parent_indexes and child_indexes are tensors of size e x 1
            # parent_indexes and child_indexes contain the integer indexes needed to index into
            # the feature and hidden state arrays to retrieve the data for those parent/child nodes.
            parent_indexes = adjacency_list[:, 0]
            child_indexes = adjacency_list[:, 1]
            # child_h and child_c are tensors of size e x 1
            child_h = h[child_indexes, :]
            child_c = c[child_indexes, :]
            # Add child hidden states to parent offset locations
            _, child_counts = torch.unique_consecutive(parent_indexes, return_counts=True)
            child_counts = tuple(child_counts)
            parent_children = torch.split(child_h, child_counts)
            parent_list = [item.sum(0) for item in parent_children]
            h_sum = torch.stack(parent_list)
            iou = self.W_iou(x) + self.U_iou(h_sum)
        # i, o and u are tensors of size n x M
        i, o, u = torch.split(iou, iou.size(1) // 3, dim=1)
        i = torch.sigmoid(i)
        o = torch.sigmoid(o)
        u = torch.tanh(u)
        # At iteration 0 none of the nodes should have children
        # Otherwise, calculate the forget states for each parent node and child node
        # and sum over the child memory cell states
        if iteration == 0:
            c[node_mask, :] = i * u
        else:
            # f is a tensor of size e x M
            f = self.W_f(features[parent_indexes, :]) + self.U_f(child_h)
            f = torch.sigmoid(f)
            # fc is a tensor of size e x M
            fc = f * child_c
            # Add the calculated f values to the parent's memory cell state
            parent_children = torch.split(fc, child_counts)
            parent_list = [item.sum(0) for item in parent_children]
            c_sum = torch.stack(parent_list)
            c[node_mask, :] = i * u + c_sum
        h[node_mask, :] = o * torch.tanh(c[node_mask])