本文作者来自Singapore University of Technology and Design以及Department of Computer Science, University of Rochester。
虽然本文中没有提到图神经网络的概念，但是从其实际操作上还是被归类为图的空间方法的一种。本文为了克服了BiLSTM局限于顺序文本的缺点，提出了新的模型S-LSTM，利用Recurrent steps在单词之间同时执行本地和全局信息交换，而不是对单词序列进行增量读取。换句话说，S-LSTM为LSTM增加了全局结点，并使用与LSTM同样的门规则对全局节点的信息进行更新，全局结点的信息也被用于与句子中的每一个单词结点进行信息交换，最终使得在减少了LSTM的复杂度的同时又提升了性能。
为了更深刻地理解本文，先复习一下LSTM。
LSTM
提到RNN，多数人都会想起来下边这样的图：
这里面的time step是指一句话的长度，每一个单词作为一个X输入，然后RNN的过程就是从头到尾遍历这句话的过程。每一个cell的输出对应X的输出，X+1个单词保留单词X的输出信息，这样就做到了记忆。但是可能由于梯度消失的原因，RNN的比较脑瘫，记忆力并不是很行，所以一个更强的版本LSTM诞生了。By the way，其实LSTM叫做（Long Short-Term Memory）长—短期记忆网络，而不是长短期—记忆网络。就跟北京的“东四-十条”不叫“东-四十条”一样。LSTM示意图如下：
LSTM通过使用gate的机制（遗忘门，更新门，输出门）控制信息的取舍与更新，做到了更长时间的记忆。下面分别介绍这几个门。
遗忘门：ht-1是上一个cell的输出，Ct-1表示上一个cell的状态。门本质上是一些列矩阵的操作，输出ft表示上一个cell的状态到底哪些要记住哪些要忘记。
更新门：决定了需要给本个cell的状态Ct添加哪些信息。
最终Ct由上一个cell的状态Ct-1和更新门的输出共同决定。
输出门：ot同样是一个参数矩阵乘法+bias然后过一个softmax**函数的操作，最终cell的隐状态ht由ot与Ct共同参与决定。
本文Model
可以看到尽管S-LSTM脱胎于LSTM，但是与LSTM还是有一些差别：
- BiLSTM所需要的重复步骤的数量与句子的大小成比例，而S-LSTM所需的时间步是一个预设的参数，可以根据实际的实验进行调整。所以S-LSTM所需要的训练时间要比LSTM短。
- 句子级别结点g的添加。g^t在模型执行的过程中聚合整句话里所有单词结点的信息，并参与到下一层的结点的隐状态的更新的过程中。并且，句子级别的结点也可以被用来进行句子的分类。
- 每一个time step，单词wi都从上下文中聚合邻居单词的信息，这个领域的大小取决于窗口参数的大小，在后文中会对这个参数进行进一步探讨。假定每次传播从w_i-1和w_i+1两个结点聚合新的信息，在第二个time step就可以得到w_i-2和w_i+2的信息，因为w_i+1在第一个time step也从邻居聚合了有用的信息。因此随着time的增加，每个单词所聚合的上下文信息也越来越多，这就使得模型能够接受长距离的记忆。
从模型的实际传播过程也可以看出，S-LSTM尽管作用于一个序列（sentence），但是聚合方式以及全局结点的添加在本质上都属于GNN的基操。因此在清华大学孙茂松组发表的论文中将其归类为处理文本的GNN【1】。
github传送门：https://github.com/leuchine/S-LSTM
形式化描述
接下来就是枯燥的公式了。
第t步的S-LSTM状态可以表示为：
其中，h表示每个单词的隐藏状态表示，为啥有n+2个单词是因为在句首与句尾添加了两个特殊字符 < S>< /S> 表示句子的开始与结束。这两个字符的添加使得原本句子中第一个和最后一个单词也能参与到信息交换之中，因此会稍稍提升一下准确率。这个操作在后文的实验里也有提及。g则表示当前句子级别结点的隐藏信息。
之后句子中单词wi的信息更新的操作被表示为如下一大串公式。但是这些公式都和LSTM里的差不了多少，所以比较好理解：
ξ：一个context window内的三个单词w_i-1,wi,w_i+1的隐状态的拼接。下面的公式都是依照这个ξ进行计算的。
i~：控制从输入xi获取到的信息，xi是单词的特征表示，可以是预训练的词向量。
l~：也就是left的门操作，控制从左侧单词w_i-1的cell接受到的信息
r~：同理，控制从右边的单词收到的信息。
f~：遗忘门，和LSTM中的遗忘门作用相同，控制从上一个时间步ct-1所得到的信息。
o~：输出门，来控制最终的输出。
u~：更新门
softmax：各种不同的门进行normalise
c~：当前节点对应cell的状态，由以上一大堆公式共同决定。
h~：最终的输出，输出还是由cell的状态与输出门共同控制。
然后恭喜你，你了解了文本结点是如何更新的，然后全局结点g还需要另一个cell进行更新。不过这个操作和以上操作差不多，相信你一看就会了：
实验
首先定义一下不同的任务。本文考虑了两种不同的任务：文本分类和序列标注。对于文本分类，可以使用全局结点作为softmax的输入：
最后一层隐藏层的结点信息可以应用在序列标注的任务中。当然，对于序列标注可以在输出层后边增加一层条件随机场（CRF）以提高准确率。
所有的损失函数都使用standard log-likelihood loss并添加L2正则化（正则化参数0.001）。
硬件以及超参数
因为实验中考虑到了模型的执行时间，因此要明确地说明硬件条件：GeForce GTX 1080 GPU with 8GB memory。
超参数上使用了预训练的Glove300，这个可以在Stanford的网站上下载预训练好的模型。Dropout为0.5，所有模型都使用Adam optimizer，初始learning rate为0.001并以0.97的速度进行衰减（0.001*0.97）。batch设置为10，每个sentence需要补全到同样的长度。
分类任务
可变超参数讨论
在MR数据集上进行了不同参数的实验。
句子级别结点数（dummy node）：1个最好。
Hidden Size：300
< S>：需要在句子首位两段添加特殊字符进行标记。
time step：step增加当然会让准确率一直有所提升，直到拟合。
window size：在较小的窗口大小下，可以使用更多的重复步骤来实现远程节点之间的信息交换，而在较大的窗口大小下，可以使用更少的步骤来实现。因此窗口的大小并不是很重要的参数。考虑到效率，剩余的实验选择窗口大小为1。step为9。
与LSTM、CNN以及Transform的比较
CNN的用时是一定最短的，这取决于模型的内部实现。LSTM要比S-LSTM长，这在前文也说了，LSTM需要每次都计算所有结点。在最终聚合w的信息到g的时候添加Attention有助于准确率的提升。
最终所有数据集比较
数据集描述：
在16个数据集上有12个取得了最优的结果。
序列标注任务
使用了POS-tagging（词性标注）以及NER（命名实体识别）两个不同的子任务来验证。
同时也实验了句子长度与准确率、耗时之间的关系：
参考文献
【1】Zhou J, Cui G, Zhang Z, et al. Graph Neural Networks: A Review of Methods and Applications[J]. arXiv: Learning, 2018.