从三篇经典论文看时空数据挖掘任务中的自适应图学习

©PaperWeekly 原创 · 作者 | 西南交一枝花

单位 | 西南交通大学CCIT实验室

研究方向 | NLP、时空数据挖掘

想介绍此类相关的方法已有一段时间，最近整理论文工作，借此机会，分享一下。

引言

目前图神经网络在时空数据挖掘领域取得了突出表现，主要得力于捕获空间依赖能力的增强。一句话可以总结为：将时空任务中的空间依赖建模为图结构（如，在交通流预测任务中，将传感器视为图中节点，不同节点之间的路网连接关系视为图中边），然后基于图神经网络计算节点之间的空间关联表示，再通过捕获时序依赖（如，循环神经网络、膨胀卷积等），完成时空任务建模。目前，该任务的研究热点主要在图结构表示以及空间依赖捕获。

动机

图结构表示，如邻接矩阵，可以表示节点之间的相邻关系。在时空挖掘场景中，如交通流任务中可以通过路网拓扑表示传感器之间的相邻关系，可以通过欧氏距离度量；地铁交通流任务中可以通过地铁线路图表示站点之间的相邻关系。此类图结构表示可以看作是预定义图（Pre-defined graph）或者说固定图（Fixed graph），即通过先验知识定义的图结构或者说是既定图结构。

但是，在某些研究任务中没有预定的图结构，或者说此类预定义图结构无法完全表示节点之间的相邻关系。为解决上述问题，有学者提出自适应图结构学习，即构造一个参数化的邻接矩阵，在随机梯度优化过程中不断地调整邻接矩阵。

方法

本小节将着重介绍模型如何通过端到端方式学习邻接矩阵。目前常用的方法可以概括为：初始化的节点嵌入表示，通过节点之间向量计算表示节点之间的关联关系，得到一个参数化后的邻接 矩阵，基于梯度下降优化在后向传播中不断“调整”节点表示，进而改变邻接矩阵，最终使其收敛到稳定状态。

首先，由于现有工作将自适应图学习与图卷积联系地较为“紧密”，往往不是单一地只对自适应图学习做改进，同时还对图卷积操作做了修改。因此，在本文介绍中将自适应图学习以及单层图卷积一起给出。

给出论文【Kipf GCN】GCN 的计算方式：

其中邻接矩阵表示 A，加上自环后的邻接矩阵可以表示为 ， 表示度矩阵，为加强网络学习时的数值稳定性，计算归一化拉普拉斯矩阵 ， 表示对图信号矩阵做两次仿射变换。从中可以看出，邻接矩阵是计算的关键。

之后，分别介绍【Wu, 2019 IJCAI】、【Bai, 2020 NeurIPS】、【Wu, 2020 KDD】三篇工作中的自适应图学习方法。

3.1 Graph WaveNet 2019 IJCAI

其中 可以看作源节点嵌入表示， 看作目标节点嵌入表示，单个节点维度为 。

为何 可以表示节点之间的联系？可以这样理解，该自适应图学习到的是有向图表示，常用的方法是为每一个节点初始化两个嵌入表示，然后二者做计算，这个和 word2vec 有相似的思想。我们可以按矩阵乘法的单个元素计算来看， 表示源节点 i 的向量表示， 表示目标节点 j 的向量表示， 与 的点积计算从源节点到目标节点的关联度，可以表示节点之间的关系，ReLU 用于保持邻接矩阵的非负性，softmax 用于归一化。这样得到的 是非对称的，可以用于表示节点之间的有向关系。

3.2 AGCRN 2020 NeurIPS

与 GraphWaveNet 不同，作者只是用了单个节点嵌入表示，具体计算如下：

通过该计算 是一个无向图表示，为对称矩阵。另外，该论文还提及了 GraphWaveNet 自适应图，原文是这样介绍：

Comparing with the self-adaptive adjacent matrix in [5], DAGG module is simpler and the learned EA has better interpret-ability. AGCRN unifies all the embedding matrix to be E instead of learning separate node embedding matrix in different NAPL-GCN layers and DAGG. This gives a strong regularizer to ensure the nodes embedding consistent among all GCN blocks and gives our model better interpretability.

文中提及了 AGCRN 的可解释能力，但是阅读了全文，关于可解释性的解释，笔者并未看到，作者好像并未对此进一步解释。如果读者有看明白的，可以在评论中指出。此外，在邻接矩阵和 GRU 结合计算的地方，也并未使用上述的 中节点自环，上下文有不对应的问题。

3.3 MTGNN 2020 KDD

作者对自适应图进一步进行了“升级”（单向图）。主要是作者考虑了节点之间的单向关系，单向不同于有向，举个例子说明：有向图中 A 到 B 有边 A→B，B 可以到 A 有边。但是在单向图中，A→B，不存在 B→A。提出单向关系，原文作者的解释为多变量预测中一个变量状态变化引起另一个变量状态变化，但笔者认为这个解释不足以说明单向关系必要性，因为有向图也可以表示这种变化关系。

笔者的理解是交通流中存在单向通行路段，传感器 A 所在道路状况会传递给传感器 B 所在道路状况，同时 B 的状态变化不会影响 A，因此二者之间的关系是单向的。在后续图卷积操作时，作者还传入了 ，可以表示入度（inflow）和出度（outflow）。

x = gconv1(x, adp)+gconv2(x, adp^{T})

图学习层的具体计算如下：

其中 tanh 表示双曲正切函数， 和 为随机初始化的节点嵌入矩阵表示，比较有意思的是通过上述计算得到的 M 是一个反对称矩阵，该矩阵主对角线上的元素全为零，且 ，这样通过 ReLU 激活函数后 非主对角线元素一半为 0，这样 中元素 ，表示节点的 i 和 j 的单向关系。 

结语

本文回顾了三篇基于图神经网络的时空预测工作，他们都采用自适应图学习方法。具体地，不使用预定义图结构，通过节点嵌入计算图中节点之间的关联关系，用于表示图结构，基于预测目标的损失后向传播优化节点表示，进而改变图结构，实现基于数据驱动的图结构定义。 

参考文献

[Kipf GCN] Semi-supervised classification with graph convolutional networks

[Wu, Graph WaveNet, 2019 IJCAI] Graph WaveNet for Deep Spatial-Temporal Graph Modeling 

[Bai, AGCRN, 2020 NeurIPS] Adaptive Graph Convolutional Recurrent Network for Traffic Forecasting 

[Wu, MTGNN, 2020 KDD] Connecting the Dots Multivariate Time Series Forecasting with Graph Neural Networks 

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·