@TOC

简介

Hello！
非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～
 
ଘ(੭ˊᵕˋ)੭
昵称：海轰
标签：程序猿｜C++选手｜学生
简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研
学习经验：扎实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！
 
唯有努力💪
 
【每日一读】每天浅读一篇论文，了解专业前沿知识，培养阅读习惯（阅读记录 仅供参考）

论文简介

原文链接：https://dl.acm.org/doi/10.1145/3394486.3403043

会议：KDD '20: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining （CCF A类）

年度：2020年8月20日（发表日期）

ABSTRACT

路网是城市交通的核心组成部分，广泛应用于各种交通相关的系统和应用中。由于其重要作用，开发通用、有效和鲁棒的道路网络表示模型至关重要。尽管已经朝着这个方向做出了一些努力，但它们无法完全捕捉到道路网络的复杂特征。

在本文中，我们提出了一种新的分层道路网络表示模型，命名为 HRNR，通过构建一个三级神经架构，分别对应于“功能区”、“结构区域”和“路段”。

为了关联这三种节点，我们引入了两个由概率分布组成的矩阵，用于对段到区域的分配或区域到区域的分配进行建模。

基于这两个分配矩阵，我们精心设计了两个重建任务，要么基于网络结构，要么基于人类运动模式。通过这种方式，我们的节点表示能够捕捉结构和功能特征。

最后，我们设计了一个三级分层更新机制，用于通过整个网络学习节点嵌入

针对四个任务的三个真实数据集的广泛实验结果表明了所提出模型的有效性。

1 INTRODUCTION

如今，智能交通系统通过提供与交通相关的应用程序在日常生活中变得越来越重要，例如路线规划[2、6、24、28、31]、到达时间估计[10、11]和下一个位置预测[4 , 14 , 29]。这种系统的核心组件是道路网络，它由相互连接的路段网络组成，以适应车辆和行人的交通[6, 12]。道路网络通常构成城市地区最基本的交通基础设施。它在各种与交通相关的系统和应用程序中广泛有用 [12, 20 – 22, 36, 39]。

由于其重要作用，必须开发合适的方法来有效地表征和建模道路网络，特别是以一般方式。早期的研究主要将道路网络视为约束，并采用标准的图数据结构来开发其算法[29, 38]。最近，深度学习揭示了道路网络的建模。最近的几项研究开始利用网络或图形表示学习来获取道路网络上的节点表示 [5, 24, 25]。通过这种方式，可以提取和利用路网的底层特征，有望提高下游应用程序的性能。

然而，道路网络是一个相当复杂的系统，设计有效的表示学习方法并不容易。

至少有三个主要问题需要解决，这是以前的工作没有研究过的。

• 一是路网不平坦。它自然地将交通单元组织为“集群”，无论是结构性的（例如交通枢纽）还是功能性的（例如商业区）。此外，一些交通单位更重要，通过路网承担着更重要的交通任务。而以往的研究[5,24,25]通常采用标准的图神经网络，将节点平等对待，不能表征层次结构。
• 其次，道路网络可能不是“小世界”，往往具有较长的平均路径。例如，主干道的长度通常会随着城市地区的增长而增加。然而，在典型的图神经网络 [5, 7, 19] 中，仅聚合来自附近节点的消息，无法有效捕获节点之间的长期依赖关系。
• 第三，道路网络主要反映结构特征，而其他方面的信息可能无法通过网络结构获得。例如，通常很难仅根据其道路连接来确定交通单元的功能角色（例如，购物中心）。

为了解决这些问题，本文的重点是为各种下游应用设计一种通用、有效和鲁棒的道路网络表示方法。我们的关键思想是开发用于学习此类表示的分层图神经网络。通过分层组织，我们可以通过聚合细粒度的单元，在不同层次上编码有用的特征，逐渐形成更抽象的集群。特别是，我们期望分层组织可以对应于道路网络中交通单元的实际聚合，例如上述结构或功能集群。为此，我们将两种虚拟节点合并到层次结构中，即结构区域和功能区域。结构区域主要用于表征空间连接的路段，充当一些交通角色，例如立交桥和十字路口。此外，功能区是在结构区域之上形成的，为交通用户提供某种功能，例如购物区。有了这样的三级组织，我们可以缓解与远程节点依赖相关的问题，因为我们可以先在高层执行消息共享，然后将信息传播到低层节点。对于第三个问题，我们考虑结合用户的真实轨迹数据来补充结构信息。如先前的研究 [23, 36, 40] 所示，用户的轨迹数据可用于发现潜在的功能或生活方式相关模式。

为此，在本文中，我们提出了一种新颖的分层道路网络表示模型，名为 HRNR。我们按照层次结构“功能区”→“结构区域”→“路段”构建了一个三级神经架构

• 我们首先应用光谱聚类通过聚合空间连接的路段来构建结构区域。
• 此外，我们通过组合功能相关的结构区域来形成功能区。为了关联这三种节点，我们引入了两个分配矩阵，建模段到区域或区域到区域的成员资格。这两个矩阵分别表征结构区域中路段的概率分布和功能区中结构区域的概率分布。基于这两个分配矩阵，我们精心设计了两个重建任务，要么基于网络结构，要么基于人类运动模式。通过这种方式，我们可以驱动学习的节点嵌入来捕捉结构和功能特征。
• 最后，我们设计了一个三级分层更新机制，用于通过整个网络学习节点嵌入。

据我们所知，这是第一次使用分层图神经网络学习道路网络表示，同时捕获结构和功能特征。我们的模型能够自然地模拟道路网络上远程节点之间的远程依赖关系，并利用轨迹数据来提取功能特征。我们的模型为各种与下游流量相关的应用程序提供了一种通用的表示学习方法。我们使用三个真实世界的数据集对四个典型的应用任务进行了广泛的实验。实验结果证明了所提出模型的有效性。

2 RELATED WORK

我们的工作与以下研究方向有关。

建模道路网络。由于道路网络是交通系统的基本组成部分，因此各种应用程序都将其用于开发算法，例如下一位置预测 [4、14、29]、路线规划 [2、6、24、28]、到达时间估计[10, 11]和目的地预测[8, 32, 33]。为了利用道路网络信息，早期的研究主要集中在设计启发式约束[6、42]或在道路网络上构建基于图的算法[30、37、38]。后来，诸如隐马尔可夫模型之类的统计模型已被用于对道路网络上的位置转换进行建模[15、17]。随着深度学习技术的快速发展，一些研究试图从道路网络中学习有效的节点表示，包括基于 RNN 的模型 [29]、图卷积网络 [5]、图注意力网络 [24] 和其他类型的网络 [25] ]。尽管这些研究通过增强的数据表示提高了应用程序的性能，但它们缺乏对第 1 节中提出的问题的全面考虑。特别是，这些方法通常专注于一些特定的任务，不能灵活地适应其他任务。

图表示学习。近年来，深度学习在图数据建模方面取得了成功。具体而言，图神经网络 (GNN) 已被广泛用于对复杂图数据进行建模以学习有效的节点特征。两个经典模型是图卷积网络 (GCN) [7] 和图注意力网络 (GAT) [19]。基本过程是执行消息传递并聚合来自邻居的消息。基于这样的核心架构，已经提出了各种变体来改进原始网络 [24]。特别是，建模层次或结构特征的工作与我们的工作非常相关，包括可微图池化 [35]、几何聚合方案 [18] 以及异构或元路径驱动的注意力聚合 [27, 41]。然而，所有这些研究都不是针对道路网络的。将这些研究直接应用于道路网络模型是不合适的。

我们的工作基于对基于流量的应用程序任务的广泛研究[10,11,29]。我们没有专注于某些特定任务，而是设计了一个通用的、有能力的、鲁棒的道路网络表示学习模型，以便它可以为各种下游应用程序提供有效的表示。据我们所知，这是第一次提出基于层次图神经网络的道路网络综合表示模型。

3 PRELIMINARIES

在本节中，我们将介绍整篇论文中使用的符号并正式定义我们的任务。

定义 1. 路段。路段 s ∈ S 是在交通[26]中单独标识的统一路段，通常与一些侧面特征（例如，经度和纬度、路段类型和长度）相关联。

定义 2. 道路网络。道路网络的特征是有向图 G = ⟨S, AS ⟩，其中 S 是 kS 个路段的顶点集，AS ∈ RkS ×kS 是邻接矩阵。每个entryAS [si , sj ] 是一个二进制值，指示是否存在从路段si 到路段sj 的有向链路。

在这里，我们遵循广泛采用的设置 [5, 11, 24]，将路段视为顶点。将位置（例如 POI 或位置单元）定义为顶点同样可行。对于双向路段，我们只需通过反转它们的开始和结束顶点来添加两个有向链接。如第 1 节所述，我们的目标是结合层次结构以更好地组织道路网络上的顶点。我们想捕捉和学习一个三层的层次结构，即功能区→结构区→路段。接下来，我们定义这两个新概念。

定义 3. 结构区域。结构区域 r ∈ R 由一组空间连接的路段 [40] 组成，充当一些交通角色，例如立交桥和十字路口。

定义 4. 功能区。功能区 z ∈ Z 由多个结构区域组成，提供某种交通功能 [36, 40]，例如购物区和交通枢纽。

我们假设有 kR 个结构区域和 kZ 个功能区，分别用区域集 R 和区域集 Z 表示。在整篇论文中，我们使用小写字母 s、r 和 z 分别表示路段、结构区域和功能区，它们的大写字母 S、R 和 Z 表示聚合数据的索引类型。为方便起见，在明确的情况下，我们可以简称为段、区域和区域。我们进一步利用这种层次结构来组织道路网络。

定义 5. 分层道路网络。分层道路网络正式描述为 H = ⟨V, E⟩，其中 V = S ∪ R ∪ Z 由路段、结构区域和功能区组成，E = {AS , AR , AZ , AS R , ARZ } , 其中五个矩阵AS ∈ RkS ×kS , AR ∈ RkR ×kR , AZ ∈ RkZ ×kZ , AS R ∈ RkS ×kR 和ARZ ∈ RkR ×kZ 表示（加权或二进制）邻接矩阵，用于捕获（1）两个之间的链接段节点，（2）两个区域节点，（3）两个区域节点，（4）段节点和区域节点，以及（5）区域节点和区域节点。

不同于路段，结构区域和功能区是虚拟节点。因此，AR 、 AZ 、AS R 和 ARZ 是需要学习的未知参数。我们还分别称 AS R 和 ARZ 段到区域和区域到区域分配矩阵，用于将段与区域关联或将区域与区域关联。我们为图 1 中的分层道路网络提供了一个说明性示例。现在，我们准备好定义我们的任务。

定义 6. 道路网络的表征学习。给定道路网络 G，我们的目标是构建相应的分层道路网络 H，同时为 H 上的每个顶点推导出 d 维表示 nm ∈ Rd，其中 d ≪ |V | andm 是 V 中一个顶点的占位符。

对于这三种节点，我们可以将它们的嵌入聚合为矩阵形式，即 NS ∈ RkS ×d ， NR ∈ RkR ×d 和 NZ ∈ RkZ ×d ，分别表示片段、区域和区域嵌入矩阵。我们的任务变成了如何形成虚拟区域和区域节点并学习嵌入矩阵（NS、NR、NZ）和邻接矩阵（AR、AZ、AS R、ARZ）。

4 MODEL

在本节中，我们介绍了提出的分层道路网络表示 (HRNR) 模型。我们的核心思想是通过表征三级层次结构来扩展用于道路网络表示学习的图神经网络。

所提出模型的整体架构如图 1 所示。

我们从位置段的上下文嵌入开始，然后介绍如何对结构区域和功能区进行建模，最后讨论如何更新层次模型和训练整个网络。

4.1 Contextual Embedding for Road Segments

正如我们在第 3 节中介绍的那样，路段与一组有用的上下文特征相关联。在这里，我们嵌入这些辅助信息并学习路段的上下文嵌入。

与使用链接信息（即 nli ）的节点表示不同，我们使用 vli ∈ Rd 来表示使用自身侧面特征的上下文嵌入。给定路段 si ，我们考虑五种特征用于上下文嵌入，即路段 ID、道路类型 (RT)、车道编号 (LN)、路段长度 (SL) 和经纬度 (LL)。对于连续特征，我们将整个取值范围划分为几个连续的 bin，并利用 bin 编号进行特征编码。这样，我们为每个离散值（或 bin 编号）设置一个唯一的嵌入向量，然后将关联的向量连接起来作为上下文嵌入：

其中“∥”是向量连接操作，v(·)表示某种上下文特征的嵌入向量。

这种简单的方法可以灵活地包含更多的侧面特征。我们采用它来初始化图节点嵌入：

其中 V 是所有路段的上下文嵌入的聚合矩阵。

4.2 Modeling Structural Regions

在我们的模型中，结构区域主要用于表征某些交通目的的局部连接模式。我们假设一个路段属于一个单一的区域，不同的路段对应一个区域内不同的重要性级别。接下来，我们介绍如何对结构区域进行建模

4.2.1 Constructing Structural Regions by Spectral Clustering

我们采用经典的谱聚类算法 [16] 来推导结构区域。它通过拆分弱链接来进行图切割视图，从而使产生的集群达到更紧密的连接状态。这种聚类算法特别适合我们的任务，因为我们的目标是寻找紧密相连的路段。形式上，给定路段的邻接矩阵 AS，我们首先通过减去对角矩阵 DS 得到其图拉普拉斯 LS，因此我们有 LS = DS - AS。通过计算拉普拉斯矩阵 LS 的第一个 d ′ 特征向量 su1, …, uk ，我们得到由 d ′ 个特征向量组成的矩阵 U ∈ RkS ×d′。通过在矩阵 U 上运行标准 K-means 算法，我们可以获得从位置到集群（即结构区域）的硬映射。我们合并了一个隶属度矩阵 M1 ∈ RkS ×kR ，其中每个条目定义为

4.2.2 Learning Region Representations with Assignment Matrix

由于集群中不同路段的重要性不同，我们采用图注意网络（GAT）[19]对路段重要性得分进行建模，如下所示：

其中 GAT(·,·) 是补充文档中详述的 [19] 的标准实现，V 是上下文嵌入矩阵（等式 1），AS 是路段的邻接矩阵，W1 ∈ RkS ×kR 是学习输出通过 GAT。在这里，我们将 W1 的列号设置为 kR（即结构区域的数量），并将每个潜在维度与唯一的结构区域相关联。 W1 中的列向量测量路段 w.r.t 的重要性级别。某个地区。由于我们之前已经获得了一个硬位置区域映射矩阵 M1（等式 3），我们进一步将这两个矩阵相乘，并推导出结构区域中路段的软分配：

其中“⊙”表示基于矩阵的元素乘积，softmax(·) 是用于列归一化的标准 softmax 函数。每个条目 AS R [s, r ] 确实模拟了结构区域 r 中路段 s 的条件概率

我们进一步利用 AS R 将区域表示与段表示相关联：

其中 NS ∈ RkS ×d 是路段的表示矩阵，NR ∈ RkR ×d 是结构区域的表示矩阵。可以看出，nr = Ís ∈r Pr(s |r )ns 。我们可以进一步得到区域节点的加权邻接矩阵 AR ∈ RkR ×kR：

这样的公式可以解释为：

4.2.3 Learning the Assignment Matrix by Network Reconstruction

分配矩阵 AS R 在将片段表示 NS 与区域表示 NR 相关联中起关键作用。这种方式类似于 DP-GCN [35] 中具有分配矩阵的分层池技术。然而，如果没有适合我们任务的监督信号，很难直接学习 AS R，因为道路网络有其独特的特征。以上，我们采用谱聚类来预先构建区域节点。在这里，我们进一步提出了一种基于网络重建的增强学习方法。我们的核心思想是利用区域表示来拟合基于分配矩阵的路段表示，并用近似的路段表示重建道路网络。形式上，我们如下获得拟合段表示 NS：

我们可以用向量形式重写上面的方程： ns = Pr(s |rs )nr ，其中 rs 是段 s 的分配区域。此外，^NS 用于重建原始邻接矩阵 AS ：

其中 sigmoid 函数适用于每个矩阵元素，用于将值转换为区间 (0, 1)。此外，使用交叉熵函数来计算重建损失：

这种网络重建的一个主要优点是它迫使 AS R 和 NR 从原始道路网络结构中学习有效特征，并增强区域和路段之间的关联。

4.3 Modeling Functional Zones

在这一部分中，我们研究如何对功能区进行建模。功能区是在功能相关的结构区域之上构建的。它旨在捕捉重要的功能特征，即使对于不连贯或遥远的区域也是如此。

4.3.1 Learning Zone Representations with Assignment Matrix

我们在第 4.2.2 节（等式 7）中采用了类似的策略，使用区域表示的线性组合来学习功能区域表示。给定区域到区域分配矩阵 ARZ ∈ RkR ×kZ ，每个条目 ARZ [r, z] 表示区域 z 中区域的条件概率。通过将潜在维度与区域对齐，我们利用 GAT 网络推导出 ARZ：

其中 M2 ∈ RkR ×kZ 表示区域到区域的映射，我们按列执行 softmax 函数以导出区域到区域的概率矩阵 ARZ。这样，我们可以将区域表示设置为区域表示的线性组合：

使用 NZ ，我们进一步推导出区域节点的邻接矩阵：

其中 AZ 是区域节点的计算加权邻接矩阵，σ 是设置为 0.5 的缩放参数。

4.3.2 Capturing Functional Characteristics with Trajectory Data

路网本身主要体现结构特征，包含的功能信息非常有限。因此，我们考虑使用真实轨迹数据来捕捉功能特征。先前关于轨迹数据挖掘的研究 [36, 40] 表明，轨迹行为可以对应于基础道路网络单元的重要功能模式。我们收集真实用户的轨迹序列数据，这是一个用户访问的按时间顺序排列的路段序列。为了利用轨迹数据，我们构造了一个路段过渡矩阵 T (λ) ∈ RkS ×kS ，其中条目 T (λ)[si , sj ] 表示 si 以步长 λ 达到 sj 的频率轨迹序列。有了 T (λ)，我们可以得到一个更新后的连接矩阵 C ∈ RkS ×kS ：

其中 C 考虑道路网络结构和人类移动行为的连通性，λ 是在这项工作中设置为 5 的可调参数。此外，我们对 C 执行基于行的归一化。然后，我们遵循方程式中的类似方式。 10 根据区域表示拟合段表示：

其中 AS R 和 ARZ 分别是段到区域或区域到区域的分配矩阵。这可以用向量形式来解释：ns = Pr(s |rs ) Íz ∈Z Pr(rs |z)nz ，这是一个两步拟合过程。类似于方程式。 11，我们将矩阵 C 重构为：

我们没有在 ^C 上使用 sigmoid 函数来推导概率，而是从轨迹数据中保留原始可达度。我们使用均方误差 (MSE) 来测量真实矩阵和重构矩阵之间的差异：

其中 C 是方程中估计的连通性矩阵。 19.

4.4 Hierarchical Update Mechanism

上面，我们已经讨论了如何学习将区域与区域关联或将位置与区域关联的两个分配矩阵。接下来，我们假设这两个矩阵是固定的，并讨论如何通过设计分层更新机制来更新节点表示。

4.4.1 Zone-level Update

我们首先执行区域级更新。在这个级别，我们更新区域表示并准备它们以将消息传递到下一个级别。我们采用标准的图卷积网络 (GCN) [7] 来更新区域嵌入：

其中 AZ 是等式中区域节点的计算加权邻接矩阵。 16、由于AZ不是二元矩阵，所以这里我们不采用GAT，GCN的细节可以在补充文档中找到。然后，它将区域嵌入发送到下一个级别以更新区域嵌入：

其中 äZ R 是控制从区域传递到区域的信息的门向量，w1 是要学习的参数向量。

4.4.2 Region-level Update

在区域级别，它首先通过采用标准 GCN 来更新自己的嵌入表示：

其中 AR 是等式中的加权邻接矩阵。 8. 然后，我们将区域嵌入转发到下一个级别以更新段表示：

其中 äRS 是控制从区域到片段传递的信息的门向量，w2 是要学习的参数向量。

4.4.3 Segment-level Update

最后，我们使用 Graph Attention Network [19] (GAT) 对段节点之间的关系进行建模，如下所示

其中 AS 是分段节点的二进制邻接矩阵。

4.5 Learning and Discussion

在我们的模型中，各种节点嵌入（NS、NR、NZ）、分配矩阵（AS R、ARZ）和涉及的组件参数是模型参数。请注意，每个 GAT 或 GCN 组件都对应一个唯一的参数集。

在每次迭代中，我们首先学习分配矩阵 AS Rand ARZ。为此，我们优化了 Loss1 (Eq. 12) 中的损失来学习 AS R，然后联合优化 Loss1 (Eq. 12) 和 Loss2 (Eq. 20) 来学习 ARZ。然后，分配矩阵AS R 和ARZ 被提供给分层更新算法。最后，我们将第 4.4 节中的分层更新机制应用于学习节点嵌入。我们在补充材料中详细描述了算法流程、时间复杂度和训练方法。

一旦学习了我们的模型，我们就可以将节点嵌入应用到各种下游应用程序中。有趣的是，根据某些下游应用程序添加新的特定于任务的损失很简单。这样，我们可以重新调整参数以获得最佳性能。与之前关于图表示学习 [7, 18, 19] 或道路网络表示 [5, 25] 的研究相比，我们设计了一个三层层次结构，用于从三种节点（即段、区域和区域）学习有效表示。我们的模型可以通过利用道路网络结构和人类运动轨迹数据来学习结构和功能特征。

5 EXPERIMENTS

6 CONCLUSIONS

在本文中，我们研究了如何有效地表示道路网络，以便在智能交通系统中通用。我们通过描述层次结构“功能区”→“结构区域”→“路段”，提出了一个层次图神经网络。我们精心设计了两个有用的重建损失函数来捕捉结构和功能特征。还提供了针对我们的网络架构量身定制的分层更新机制。针对四个任务的三个真实数据集的广泛实验结果证明了所提出模型的有效性和稳健性。

通常，道路网络可能会随着时间而改变。作为未来的工作，我们将考虑扩展我们的模型以学习时变表示。目前，我们利用轨迹数据作为网络重建的监督信号。我们将研究如何在表示模型中明确地结合轨迹数据。

结语

文章仅作为个人学习笔记记录，记录从0到1的一个过程

希望对您有一点点帮助，如有错误欢迎小伙伴指正