ICLR 2017(reject)，两个模型，第一个是将数据扔到Defferrard的图卷积里面，然后将输出扔到LSTM里面。第二个模型是将RNN中的矩阵乘法换成了图卷积操作，最后对动态的mnist进行了识别。原文链接：Structured Sequence Modeling With Graph Convolutional Recurrent Networks

摘要

GCRN(Graph Convolutional Recurrent Network)，一个可以预测结构化序列数据的深度学习模型。GCRN是传统的循环神经网络的在任意的图结构上的一种泛化形式。这样的结构化数据可以表示成视频中的一系列帧，检测器组成的网络监测到的时空监测值，或是用于自然语言建模的词网中的随机游走。我们提出的模型合并了图上的CNN来辨识空间结构，RNN寻找动态模型。我们研究了两种GCRN，对Penn Treebank数据集进行建模。实验显示同时挖掘图的空间与动态信息可以同时提升precision和学习速度。

1 Introduction

很多工作，Donahue et al. 2015; Karpathy & Fei-Fei 2015; Vinyals et al. 2015，利用CNN和RNN的组合来挖掘时空规律性。这些模型那个处理时间变化的视觉输入来做变长的预测。这些网络架构由视觉特征提取的CNN，和一个在CNN后面，用于序列学习的RNN组成。这样的架构成功地用于视频活动识别，图像注释生成以及视频描述。

最近，大家开始对时空序列建模时融合CNN和RNN感兴趣。受到语言模型的启发，Ranzato et al. 2014提出了通过发现时空相关性的能表示复杂变形和动作模式的模型。他们的实验表明在通过quantizing the image patches获得到的visual words上，使用RNN建模，可以很好的预测视频的下一帧以及中间帧。他们的表现最好的模型是recursive CNN(rCNN)，对输入和状态同时使用卷积。Shi et al. 2015之后提出了卷积LSTM(convLSTM)，一个使用2D卷积利用输入数据的空间相关性，用于时空序列建模的RNN模型。他们成功的对降雨临近预报的雷达回波图的演化进行了预测。

很多重要问题中，空间结构不是简单的网格状。气象站就不是网格状。而且空间结构不一定是空间上的，如社交网络或生物网络。最后，Mikolov et al. 2013等人认为，句子可以解释成在词网上的随机游走，使得我们转向了分析图结构的句子建模问题。

我们的工作利用了近期的模型——Defferrard et al. 2016; Ranzato et al. 2014; Shi et al. 2015——来设计GCRN模型对时间变化的图结构数据建模和预测。核心思想是融合图结构上的CNN和RNN来同时辨识空间结构和动态模式。图1给出了GCRN的架构。

2 Preliminaries

2.1 Structured Sequence Modeling

$x_t \in \mathbf{D}$是时间$t$的观测值，$\mathbf{D}$表示观测到的特征的域。原型应用是$n-\mathrm{gram}$模型$(n = J + 1)$，$P(x_{t+1} \mid x_{t-J+1},…,x_t)$对在句子中给定过去$J$个词时$x_{t+1}$出现的概率进行建模。

我们感兴趣的是特别的结构化的句子，也就是句子中$x_t$的特征不是相互独立的，而是有着两两相连的关系。这样的关系广义上通过带权图建模。

$x_t$可以看作是一个图信号，也就是一个定义在无向带权图$\mathcal{G} = ( \mathcal{V}, \Large{\varepsilon}, \normalsize{A )}$，其中$\mathcal{V}$是$\vert \mathcal{V} \vert = n$个顶点的有限集，$\Large{\varepsilon}$是边集，$A \in \mathbb{R}^{n \times n}$是带权邻接矩阵，编码了两个顶点之间的连接权重。定义在图的顶点上的信号$x_t: \mathcal{V} \rightarrow \mathbb{R}^{d_x}$可以当作是一个矩阵$x_t \in \mathbb{R}^{n \times d_x}$，列$i$是$d_x$维向量，表示$x_t$在第$i$个顶点的值。尽管自由变量的数量在长度为$K$的结构化序列中本质上是$\mathcal{O}(n^K{d_x}^K)$，我们仍然试图去挖掘可能的预测结果的空间结构以减少维度，来使这些问题变得容易解决。

2.2 Long Short-Term Memory

其中$\odot$表示Hadamard product，$\sigma(\cdot)$表示sigmoid function $\sigma(x) = 1/(1+e^{-x})$，$i,f,o \in [0, 1]^{d_h}$是输入门，遗忘门，输出门。权重$W_{x\cdot} \in \mathbb{R}^{d_h \times d_x}$，$W_{h\cdot} \in \mathbb{R}^{d_h \times d_h}$，$w_{c\cdot} \in \mathbb{R}^{d_h}$，偏置$b_i,b_f,b_c,b_o \in \mathbb{R}^{d_h}$是模型参数。这个模型之所以称为全连接是因为$W_{x\cdot}$和$W_{h\cdot}$与$x$和$h$所有分量进行线性组合。由Gers & Schmidhuber 2000引入可选的peephole connections $w_{c\cdot} \odot c_t$，在某些特定任务上可以提升性能。

2.3 Convolutional Neural Networks On Graphs

$T_0 = 1$，$T_1 = x$，$T_k(x) = 2xT_{k-1}(x)-T_{k-2}(x)$，时间复杂度是$\mathcal{O}(K \vert \Large{\varepsilon} \normalsize \vert)$，也就是和边数相关。这个图卷积是$K$阶局部化的。

3 Related Works

卷积核$W_h \in \mathbb{R}^{d_h \times d_h}$受限到$1 \times 1$的大小。

观察到自然语言表示出语法性质，自然的将词融入短语中，Tai et al. 2015提出了一个处理树结构的模型，每个LSTM可以获取他们的孩子的状态。他们在semantic relatedness and sentiment classification上获得了state-of-the-art的结果。Liang et al. 2016在之后提出了在图上的变体。他们复杂的网络结构在4个数据集上获得了semantic object parsing的state-of-the-art结果。这些模型中，状态通过一个可训练的权重矩阵的带权加和从邻居上聚集。然而这些权重并不在图上共享，否则需要对顶点排序，就像其他图卷积的空间定义一样。此外，他们的公式受限于当前顶点的一阶邻居，给其他的邻居相同的权重。

受到如人体动作和物体交互等时空任务的启发，Jain et al 2016提出了一个方法将时空图看作是一个富RNN的混合，本质上是将一个RNN连接到每个顶点与每条边上。同样的，通信受限于直接连接的顶点与边。

和我们的工作最相关的模型可能是Li et al 2015提出的模型，在program verification上表现出了最好的结果。尽管他们使用Scarselli et al. 2009提出的GNN，以迭代的步骤传播顶点的表示，直到收敛，我们使用的是Defferrard et al. 2016提出的GCN在顶点间扩散信息。尽管他们的动机和我们很不一样，这些模型的关联是使用$K$阶多项式定义的谱滤波器可以实现成一个$K$层的GNN。

4 Proposed GCRN Models

我们提出了两种GCRN架构

我们简单地写成$x^{\mathrm{CNN}}_t = W^{\mathrm{CNN}} \ast_\mathcal{G} x_t$，其中$W^{\mathrm{CNN}} \in \mathbb{R}^{K \times d_x \times d_x}$是切比雪夫系数。Peepholes由$w_{c\cdot} \in \mathbb{R}^{n \times d_h}$控制。这样的架构可能足以捕获数据的分布，通过挖掘局部静止性以及性质的组合性，还有动态属性。

5 Experiments

数据集是moving-MNIST(Shi et al., 2015)。