时空图神经网络（ST-GNN）

1. 文章信息

文章题为《SPACE-TIME GRAPH NEURAL NETWORKS》，提出了一种新颖的图网络结构。

2. 摘要

文章介绍了时空图神经网络（ST-GNN），这是一种新的GNN结构，专门用于联合处理时变网络数据的基本时空拓扑。文章提出的体系结构由时间和图卷积滤波器组成，以及逐点非线性激活函数。文章首先介绍了卷积算子的一般定义，它模拟信号在其底层支持上的扩散过程。在这个定义的基础上提出时空图卷积，它是建立在时间和图移位操作符的组合上的。文章证明具有多元积分Lipschitz滤波器的ST-GNN对基础图中的小扰动以及时间扭曲引起的时域小扰动是稳定的。此外分析表明，网络拓扑和系统时间演化的微小变化不会显著影响ST-GNNs的性能。用分散控制系统进行的数值实验表明了所提出的ST-GNNs的有效性和稳定性。

本文的贡献包括两点：首先介绍了一种新的时变图信号卷积结构，然后证明了其稳定性。

3. 时空图神经网络

首先，文章给出齐次扩散方程的定义：（定义1）

其中，x(t)是输入信号，是Laplacian微分算子。

1.卷积：

首先文章给出了卷积算子的一般定义，定义式如下：

其中，*D表示应用于底层架构为D的信号的卷积算子。该定义为各类卷积类型的基础。基于此，文章进一步提出了时间卷积和图卷积，定义如下。

时间卷积：给定一个连续时间信号，并且该信号属于一维二次可积的。为给出传统的时间卷积定义，文章选择微分算子作为时间移位算子（TSO）。依据泛函分析知识以及泰勒展开，可以得到下式：

进一步，可以由定义1推导出时间卷积定义式，如下所示：

值得注意的是，对于所选的微分算子，其特征向量为，特征值为。

图卷积：给定图信号x，且该图信号属于N维二次可积空间，N表示节点的个数。图移位算子S（GSO）是一个N×N的矩阵，该矩阵反映了图信号的稀疏性。将GSO作用于图信号x，其结果为信号Sx，结果信号携带着所有节点之间的聚合信息。值得注意的是，图卷积处理的是离散信号，因此，有时将图上的扩散过程离散化更为常见，定义式如下：

其中hk表示滤波器的参数，K表示滤波器中的tap参数。等式左侧的参数h指有限脉冲响应（FIR）滤波器。

2.时空卷积以及图滤波器

时空卷积的输入为，是一组时变的图信号。时空移位算子（STSO）是一个线性算子，该算子能够协同地在时空上移动输入信号。文章选择GSO和TSO地线性组合作为STSO，即，

由此，文章给出时空卷积的定义式，以及滤波器的频域相应：

3.时空卷积图神经网络（ST-GNN）

由于学习无线脉冲响应（IIR）是不实际的，文章应用FIR时空图滤波器。ST-GNN由L层组成，每层都包含一组时空图滤波器以及逐点非线性激活函数。第l层的输入为前一层的输出，第l层的输出定义如下

其中，表示第l层输出中的特征个数。值得注意的是，上式处理的时变图信号在时间上是连续的，但学习的是有限的参数。此外，ST-GNN是因果结构，节点无法访问那些该节点无法获取的信息。

4. 稳定性分析

1.扰动模型

图扰动模模型，定义如下：

其中，等号左侧的表示扰动后的GSO，E表示误差矩阵，P₀是置换矩阵。上式反映随着误差矩阵E的模的逐渐增加，扰动后的GSO与原始的GSO的差别逐渐变大，SE+ES计算了二者的区别，因此若所考虑图中节点的度越大，对应扰动也就越大。

此外，由于大多数研究都只考虑图扰动，而未考虑时间扰动。文章提出了一种新的时间扰动模型。由于在采样过程中，采样不总是平均间隔的，文章发现离散信号总是在时间被采集，其中z是一个可微函数。文章考虑扰动时间线并观测信号，由此可推导出在扰动时间线上，输入信号的扩散过程。

进一步，令扰动的TSO可表示为下式：

时间扰动的效应由空值，随着其模的增加，原始TSO与扰动TSO的差异随之增大，由此也表明时间扰动模型与偏移时间的变化率有关。利用扰动的TSO可以给出时间卷积的定义：

2.距离模协同算子（Joint operator-distance modulo）

为进行稳定性分析，需要用于计算扰动效应的算子。对于图扰动而言，对于两个图算子，其距离模定义如下：

该矩阵用于计算算子与其扰动版本之间的距离。

对于时间算子而言，文章创新地提出如下计算方式。给定算子，其距离模计算公式如下：

代入扰动的TSO以及原始地TSO，上式进一步表示如下。

依据上述两个定义，文章给出距离模协同运算公式，表示如下：

3.时空滤波器的稳定性

首先文章给出多元积分Lipschitz滤波器。

对于微分滤波器，上式可简化表达为：

依据上述定义，当时空图滤波器满足下述条件时，该滤波器是Lipschitz滤波器。

该条件表明，对于一个积分Lipschitz时空图滤波器而言，其频域响应在接近0 的低频下会迅速变化，因此在低频附近的信号可以被滤波器区分，然和高频部分较为平坦，难以区分。

文章给出如下命题，用于分析图扰动以及时间扰动的稳定性。

命题1阐明，时空图滤波器对于满足特定条件的图扰动是稳定的，且扰动的GSO与原始GSO的差异与特征值和特征向量的差异相关。命题2同样阐明对于满足特定条件的时间扰动，时空图滤波器是稳定的，此外，扰动的TSO与原始的TSO的差异仅与特征值的差异相关。进一步，文章提出下述定义，同时考虑图和时间扰动，用于表征STSO中的滤波器的差异。

上述定义表明，时空图滤波器在低频时是稳定的且可区别的，但在高频时不能同时满足稳定性和可区别性。

4.时空图神经网络的稳定性

关于时空图神经网络的稳定性定理如下：

上述定理表明，ST-GNN的稳定性与层数L以及影响时空滤波器稳定性的因素相关。此外，与时空图滤波器相比，ST-GNN不论在高频还是低频条件下，都能满足稳定性和可区分性。

5. 数值实验

文章进行了两个数值实验：模拟群体行为以及运动规划。对于两个实验，其目标函数定义如下：

实验A：1、设立100个点在网络网格中，遵循一定的规则，但每个点不允许移动，即图是静态的；2、允许50个点进行移动，并形成关联网络即随着其运动而改变，即图是动态的。实验结果如下：

实验B：无标记的运动规划。此任务的目标是将N个未标记的点分配给N个目标位置。实验结果如下：

6. 结论

本文开发了一种新的ST-GNN体系结构，该体系结构专门针对图形上支持的时变信号。本文证明了在一定条件下，该结构在图扰动和时间扰动下都是稳定的。此外，本文条件是实用的，并为如何设计时空石墨过滤器以实现理想的稳定性提供了指导。本文的理论分析得到了强有力的实验结果的支持。对模拟群体行为和无标记运动规划任务的仿真验证了本文的理论结果，并证明了所提出的ST-GNN体系结构的有效性。

Attention

欢迎关注微信公众号《当交通遇上机器学习》！如果你和我一样是轨道交通、道路交通、城市规划相关领域的，也可以加微信：Dr_JinleiZhang，备注“进群”，加入交通大数据交流群！希望我们共同进步！