计算路网中两点间的最短路径距离是路网应用场景中的核心问题，在地图服务和导航系统中有着广泛的应用。例如，打车软件需要快速准确地为用户匹配最近的车辆，从而减少用户等待时间。最短路径距离的计算方法可分为准确计算^[1-4]和估计计算^[5-14]2种。其中，估计计算方法计算速度快效率高，能够为用户提供更为高效的即时反馈。并且，在大多数情况下采用估计计算方法并不会影响最终结果的准确性。

近年来，一些研究者提出了基于图嵌入^[11-14]的路网最短路径距离估计方法。这些方法运用深度学习技术构建最短路径距离计算的索引，核心思想是运用图嵌入方法对路网中的每个顶点进行嵌入处理，使得每个顶点嵌入到欧氏^[15]或双曲^[16]空间获得嵌入向量表示，然后通过计算顶点向量之间的相似距离来估计顶点之间的最短路径距离。然而，现有基于深度学习的估计方法采用随机游走^[11]或权重矩阵相乘^[14]的方法对顶点进行嵌入处理，没有充分考虑路网的结构信息，并且使用路网中所有顶点对作为训练数据，在估计准确度和模型训练代价方面仍有较大提升空间。文献[17]对路网最短路径距离估计任务的前沿方法进行了详细的介绍和实验评估，并着重分析了不同算法的优劣。文献[18-20]扩展了基于嵌入方法的应用场景，为农业和路由规划任务提供技术支持。

图神经网络（graph neural networks, GNN）是一种用于处理图结构数据的深度学习模型。路网的本质是图结构数据，图神经网络为路网场景下的最短路径距离估计任务提供了新的研究视角。图卷积网络（graph convolutional networks, GCN）^[21]是近几年图神经网络的代表之一，基本思想是利用图的结构信息和顶点的特征信息，通过卷积操作来更新顶点的嵌入向量表示，提取图的深层次特征和捕获图的空间关键信息。因此，本文基于GCN构建了一种适用于路网的嵌入方法，用来提取路网中顶点和边的关联模式。

本文贡献主要包括以下4个方面：

1）对基于嵌入方法的核心部分进行分析，提出了路网最短路径距离估计编码器−解码器（road shortest distance estimation encoder-decoder framework, RSDE）框架，提炼了路网最短路径距离估计任务的核心过程。

2）在上述贡献的基础上，针对路网场景，提出了一种基于图卷积神经网络的路网最短路径距离估计嵌入方法。

3）在模型的训练样本采样方面，提出了一种基于图逻辑分区的三阶段采样方法。

4）将所提模型RGCNdist2vec在4个真实路网上进行实验验证，结果表明该模型具有显著的效果和性能提升。

1.   相关工作

1.1   最短路径距离的计算方法

路网最短路径距离的经典计算方法包括Dijkstra^[1]、Floyd^[2]等。由于这些方法需要访问终点到起点路径范围内所有的点，计算复杂度高。为了降低计算复杂性，Robert等^[3]提出了缩短层次网络(contraction hierarchies, CH)方法，该方法通过计算图中某些重要顶点间的最短距离来加速计算和查询。Ouyang等^[4]提出了H2H方法，该方法通过为每个顶点分配距离标签来提高计算效率。然而，上述方法都需要大量的预处理时间构建索引，不能适用于大规模道路网络。

为了适用于大规模路网数据场景，估计方法被提出用来解决上述问题。基于地标的方法^[8-10]是一类典型的估计路网最短路径距离的方法，该类方法的基本思想是从图中选择部分顶点作为地标顶点，然后为每个顶点分配距离标签存储该顶点到所有地标顶点的距离。当计算图中任意2点的最短路径距离时，可用2个顶点与同一路标顶点的最小距离之和作为结果。虽然基于地标的方法能够降低内存开销，但由于选择地标顶点是一个NP-hard（non-deterministic polynomial hard）问题，所以这类方法的计算准确度无法保证。基于嵌入的方法是对地标方法的一种突破，该类方法的基本思想是结合图嵌入技术估计大规模路网的最短路径距离。Rizi等^[11]最早提出运用深度学习技术对图顶点进行嵌入处理，从而逼近大规模图中的最短路径距离。该方法使用node2vec^[22]和Poincare^[23]作为嵌入方法，在社交网络图上取得了很好的效果，并在实验中验证node2vec不适用于路网结构。Qi等^[12]提出了一种基于学习的方法来估计路网最短路径距离，该方法虽然有较高的估计准确度，但其选取图中所有顶点对作为训练数据，导致模型训练时间较长。Chen等^[14]提出了一种基于地标和学习的估计方法，该模型直接对路网顶点进行编码，然后运用MLP（multilayer perceptron）进行训练，虽然该模型通过减少部分训练轮次的训练数据从而降低了训练时间，但没有考虑路网结构信息，并且基于地标的采样具有较大随机性，进而使得训练结果的估计准确度无法保证。

1.2   图神经网络

近年来，大量的图神经网络模型被提出，主要包括图卷积神经网络^[21]、图注意力网络^[24]等。大部分图神经网络方法都遵循Gilmer等 ^[25]提出的神经信息传递（neural message passing）框架。文献[26-27]详细阐述了GNN领域近年来的重要研究成果。Kipf等^[21]提出了GCN模型，该模型是一种直推式学习，通过聚合邻居顶点信息产生顶点的嵌入向量表示。Hamilton等^[28]提出了GraphSAGE模型，该模型是一种利用顶点的属性信息来高效产生未知顶点嵌入的归纳式学习框架，其核心思想是通过学习一个聚合邻居顶点的表示函数来产生目标顶点的嵌入向量。由于GraphSAGE在融合邻居信息时，将各个邻居以同等权重看待，Veličković等^[24]提出GAT模型，通过添加自注意力机制（self-attention）实现了对不同邻居的权重自适应配置。目前，已有众多现实应用任务采用图神经网络的相关方法，本文提出一个新的视角，将图神经网络方法运用到路网最短路径距离估计任务上，作为提取路网结构的嵌入方法。

2.   相关定义与解决方案

2.1   相关定义

定义1（路网）　路网表示为带权无向图G=(V, E, W)，其中V是顶点集合，$ {{v}}_{{i}} \in {V} $ 为图中的一个顶点；E是边集合，$ {{e}}_{{{v}}_{{i}}{,}{{v}}_{{j}}} \in {E} $为顶点v_i到顶点v_j的边，$ {{w}}_{{{v}}_{{i}}{,}{{v}}_{{j}}}\in {W}{} $为边$ {{e}}_{{{v}}_{{i}}{,}{{v}}_{{j}}} $的权重。

图1为路网结构的一个示例，其中有13个顶点，16条边，顶点v₀到v₁的权重为2。

图  1  路网结构示例

Fig.  1  An example of road network structure

下载: 全尺寸图片

定义2（路网最短路径距离计算）　给定路网中的任意2个顶点v_i和v_j，计算它们之间准确距离的方法为$ \varphi {(}{{v}}_{{i}}{,}{{v}}_{{j}}{)}{=}{w}_{{{v}}_{{i}}{,}{{v}}_{{u}}}{+}{{w}}_{{{v}}_{{u}}{,}{{v}}_{{n}}}{+}{{w}}_{{{v}}_{{n}}{,}{{v}}_{{j}}} $，其中，v_u和v_n为路径上的顶点。

例如，图1中标粗线条为v₀到v₆的最短路径，最短路径距离为7。

定义3（路网最短路径距离估计计算）　给定路网G=(V, E, W)，将每个顶点$ {v_i} \in V $嵌入到 d 维空间中，获得其嵌入向量$ {{{\boldsymbol{v}}}}^{{(}{i}{)}} $，$ \boldsymbol{H}=\left\{\boldsymbol{v}^{(1)}, \boldsymbol{v}^{(2)}, \cdots, \boldsymbol{v}^{(i)}\right\} $为嵌入矩阵。给定任意顶点v_i和v_j，估计距离的计算方法为

定义4（邻接矩阵）　A_v$ \in \bf{R} $^|V|×|V|为路网G的邻接矩阵，其中A_v(i , j)表示v_i到v_j的连接性。如果图G是无权图且v_i和v_j有边相连，则A_v(i , j) = 1；否则A_v(i , j)=0；如果图G是有权图且v_i和v_j有边相连，则${\boldsymbol{A}}_v^w $(i , j) = $ {{w}}_{{{v}}_{{i}}{,}{{v}}_{{j}}} $，否则${\boldsymbol{A}}_v^w $(i , j) = 0。

定义5（划分图）　给定图G，使用集合∆(G)={G₁,G₂,…,G_n}表示图G的划分结果。将图G划分为n个子图，则∆(G)中的元素为G_i = (V_i, E_i, W_i) , (i$ \in $[1, n])。每个子图满足以下3个条件：1）V=U_i∈[1,n]V_i；2）如果 i$ \ne $j,V_i∩V_j=$ {\varnothing } $；3）每个子图G_i为G的诱导子图，即子图G_i的属性与G一致。

给定图G和区域阈值$ {{k}}_{{{\mathrm{f}}}} $，经过划分后，图G被划分为近似大小的$ {{k}}_{{{\mathrm{f}}}} $个子图（$ \left|{{V}}_{{1}}\right|\approx \left|{{V}}_{{2}}\right|\approx \dots \approx \left|{{V}}_{{{\mathrm{kf}}}}\right| $）。本文采用多层图划分框架METIS^[29]，目的是将图划分为$ {{k}}_{{{\mathrm{f}}}} $个顶点个数相近的子图。

如图2所示，图G被分为4个子图∆(G)={G₁, G₂, G₃, G₄}，区域阈值$ {{k}}_{{{\mathrm{f}}}}=4 $。

图  2  图G的划分结果

Fig.  2  Partition results for G

下载: 全尺寸图片

定义6（顶点的度）　图顶点的度表示依附于某个顶点的边的数目，用D(v_i)表示v_i的度。如图2所示，D(v₃)=3。

定义7（边界）　给定图G = (V, E, W)，令G_x = (V_x, E_x, W_x)为图G的一个子图，如果存在一条边$ {{e}}_{{{v}}_{{i}}{,}{{v}}_{{j}}}\in {E} $但$ {{e}}_{{{v}}_{{i}}{,}{{v}}_{{j}}}\in {E}_{x} $，则这样的边称为子图的边界，该边所连接的点是子图的边界点。B(G_x)定义为G_x的边界点，则图2中B(G₂)={v₂, v₅} , B(G₃)={v₆}。

2.2   解决方案

对现有的基于图嵌入的路网最短路径距离估计方法进行分析和归纳，可将其核心过程概括为3部分：1）以某种方式进行采样，并使用传统方法计算所采样数据的最短路径距离，与采样顶点对拼接作为训练数据；2）使用图嵌入方法对路网顶点进行嵌入处理，获得顶点嵌入表示向量。3）选用恰当的度量方式/函数（范数或神经网络等）训练模型来优化顶点的向量表示并输出顶点特征矩阵。

基于上述分析，本文提出了路网最短路径距离估计编码器解码器框架(RSDE framework)，该框架组织和提炼了基于嵌入方法中的核心思想和步骤，方便后续改进和理解各部分的作用。RSDE框架如图3所示，该框架分为2部分，RSDE−编码器和RSDE−解码器，解码器层又进一步细分为样本选择过程和图嵌入过程。下文将在此框架的基础上具体阐述各部分的改进策略，以提升路网最短路径距离估计的准确性和效率。

图  3  RSDE框架结构

Fig.  3  Overall frame structure of RSDE

下载: 全尺寸图片

3.   RGCNdist2vec模型

3.1   模型总体框架

RGCNdist2vec模型结构如图4所示，主要包括2个部分：1）RGCNdist2vec−编码器层：构建路网图卷积网络（road graph convolutional networks, RGCN），通过融合路网权重和结构信息，获得每个顶点的嵌入向量；2）RGCNdist2vec−解码器层：接收编码器层的输出和训练数据，选择合适的度量方式和损失函数优化编码器层中的可学习权重矩阵，获得最优的嵌入矩阵，用于计算路网2点间的最短路径距离。

图  4  RGCNdist2vec模型结构

Fig.  4  Architecture of RGCNdist2vec

下载: 全尺寸图片

3.2   RGCNdist2vec编码器

图嵌入的作用是整合路网中的信息，为路网中的每个顶点生成低维嵌入向量表示，这是RGCNdist2vec模型的核心部分。路网被建模为带权无向图，图信息主要保存在边集合上。而现有嵌入方法并没有充分考虑顶点的邻域信息，不能为每个顶点学习更丰富的向量表示，进而影响最终的估计准确性。而GCN在提取图空间特征方面具有独特优势，通过卷积操作提取顶点和邻居之间的关联模型，从而优化顶点的嵌入表达，因此本文将其作为最短路径距离估计任务的嵌入方法，GCN的消息传递计算方法为

式中：$ \tilde{\boldsymbol{A}}=\boldsymbol{A}_v+\boldsymbol{I}_{|V|} $是附加自连接的邻接矩阵，I_|V|是大小为|V|的单位矩阵，$ {\tilde{{{\boldsymbol{D}}}}}_{{ii}}{=}\displaystyle\sum _{{j}}{\tilde{{{\boldsymbol{A}}}}}_{{ij}} $为度矩阵，$ {{{\boldsymbol{W}}}}^{{(}{l}{)}} $为第l层的可学习权重矩阵，R为第l层的顶点特征矩阵，$ {\sigma }{(}{\cdot}{)} $为ReLU激活函数。

由于路网的邻居顶点之间存在连接权值，而GCN融合邻居和自身的顶点信息是无偏好的，所以仅采用GCN从路网邻域关系的角度考虑并不合理。为此，提出了RGCN模型，主要由2部分组成：一是使用路网带权邻接矩阵替换无权邻接矩阵，以路网的权重信息为评分，不同偏好的融合邻域信息；二是选用邻域均值作为顶点的自连接性，因为邻域均值不仅与邻居权重在同一个值域区间，而且能够反映一组数据的集中水平。综上，RGCN的消息传递规则计算方法为

式中：$ {\tilde{{{\boldsymbol{A}}}}}_{{ij}}^{{{\mathrm{r}}}}{=} {\boldsymbol{A}}_v^w + {\mathrm{eye}} $ (mean($ {{w}}_{{{v}}_{{i}}{,}{{v}}_{{j}}} $))为经过权重均值自连接后的邻接矩阵，eye(mean($ {{w}}_{{{v}}_{{i}}{,}{{v}}_{{j}}} $)), $ {{w}}_{{{v}}_{{i}}{,}{{v}}_{{j}}} $∈W表示邻居权重均值对角矩阵；$ {\tilde{{{\boldsymbol{D}}}}}_{{ii}}{=}\displaystyle\sum _{{j}}{\tilde{{{\boldsymbol{A}}}}}_{{ij}}^{{{\mathrm{r}}}} $为度矩阵；$ {{{\boldsymbol{W}}}}_{{{\mathrm{r}}}}^{{(}{l}{)}} $表示第l层可学习的权重矩阵；$ {{\sigma}}_{{1}}{(}{\cdot}{)} $为激活函数LeakyReLU(·)，用来表示路网最短路径距离和嵌入向量之间的非线性关系。

随着消息传递阶数的增加，GCN会存在过平滑的问题。这是因为GCN可看作一个低通滤波器，其特性会使信号变得平滑，多次进行消息传递会使得信号趋于一致，导致顶点失去表示的多样性。考虑到RGCN的底层原理与GCN一致，所以RGCN采用2阶消息传递机制。

3.3   RGCNdist2vec解码器

解码器层首先接收编码器层的输出，即嵌入矩阵$ {{{\boldsymbol{H}}}}^{{(}{2}{)}} $和训练数据[(v_s,v_e), $ \varphi {(}{{v}}_{{{\mathrm{s}}}}{,}{{v}}_{{{\mathrm{e}}}}{)} $]。然后，通过计算式（1），迭代更新权重矩阵来优化模型的表达能力。顶点嵌入向量度量方式的选取对模型的训练结果有很大影响，本文选用L₁-norm作为其度量方式，文献[13]给出了选择L₁-norm的原因以及相关证明。在训练过程中，采用SmoothL1Loss作为损失函数评估回归任务的精度，损失函数是L1Loss和L2Loss的结合，如式（4）所示，其同时拥有两者的优点，当预测值和真实值之间的绝对值之差小于1时，选用L2Loss，此时有助于模型收敛；反之则选用L1Loss，由于L1Loss对异常值不敏感，因此容易控制梯度的量级，从而达到更好的训练效果。实验采用Adam优化器来训练模型参数，该优化器可以在训练中自动更新学习率，使得模型的收敛速度更快。

3.4   数据采样方案

训练数据的选择对于学习路网中各顶点的嵌入向量表示至关重要，文献[12]选择图中所有顶点对（包含n(n−1)个顶点对，n为顶点个数）进行训练，文献[14]在首轮训练过程中选择所有顶点对，其余轮次根据地标选择l(n−l)，l=(15~20)%n，其中l为地标顶点个数，n为路网的顶点个数。如果训练数据量过大，训练数据构造和模型训练的时间都会变长。其次，如果在路网中进行随机采样，样本的选择概率和选择范围将是不确定的，这种方式也会因随机性而导致模型训练结果变差。

为了兼顾模型训练开销和估计准确性，设计了一种基于图逻辑分区的三阶段采样方法。该采样方式分为3个层次：子图内采样、子图间采样和全图内采样。

1）子图内采样方式：对路网顶点进行划分，得到顶点个数相对均匀的子图；如果计算属于2个不同子图的2点之间的距离，那么对应子图的边界点是必经之点。

证明 1　使用反证法。给定来自不同子图的2个顶点u∈B(G₁)和v∈B(G₂), u到v的最短路径为p = uv₁v₂…v_xv。假定v₁，v₂, …,v_x并不是B(G₂)中的边界点。如果v_x$ \notin $G₂，那么v一定是边界点，这与假设相互矛盾。如果v_x∈G₂，那么找到G₂中下标最大的点（如v_i）。这样，v_i−1$ \notin $G₂ (v₀ = u)。基于边界点的定义，v_i是一个边界点，这也与假设相矛盾。因此，引理得证。

图中顶点的度是用来描述图中心性的一项重要指标。因此，以子图中度值较大的点和子图的边界点为切入点对其进行采样。如果采取确定的图划分方法，则子图边界点是固定且已知的，将其称为边界点集合，用Set(B_n)表示子图G_n的边界点集合。然而，对于图中度值较大顶点的选择是不确定的。将度值较大的顶点集合简称为度集合，用Set(D_n)表示子图G_n的度集合。为了选取恰当的度集合，本文对多个真实路网数据集的顶点度值进行了正态性检验，发现顶点的度值存在尖峰分布现象，为保证采样数据的数量，将峰值对应的度值作为度集合采样的阈值。

子图的顶点集Set(G_n)被划分成3部分，即Set(E_n)= Set(G_n) − Set(B_n) − Set(D_n)、Set(B_n)和Set(D_n)。首先，选择v_i∈Set(E_n) 和 v_j∈Set(D_n)∪Set(B_n)；其次，再分别选择v_i∈Set(D_n)和v_j∈Set(B_n)。最后，将所选数据进行拼接构成子图G_n采样结果。

假设子图G₂的度集合阈值为3，图5为子图G₂的图内采样过程。

图  5  子图内采样过程

Fig.  5  Process of intra-subgraph sampling

下载: 全尺寸图片

2）子图间采样方式：对于每个子图边界点，选取其到除自身以外其他子图的边界点。图6给出了子图G₂的边界点v₂的采样过程。上述方法是针对子图和子图间的采样，目的是学习子图细粒度的结构信息。

图  6  子图间采样过程

Fig.  6  Process of inter-subgraph samplings

下载: 全尺寸图片

3）全图内采样方式：全图内采样是针对整个图层次的采样，目的是学习图的全局信息（即粗粒度学习）。根据第1阶段和第2阶段可知，已对图中顶点的所属子图进行采样，对于其余子图，每个顶点随机选取除自身子图以外其他子图顶点数的10%~15%。

4.   实验及结果分析

4.1   数据集及实验环境

为了验证RGCNdist2vec模型的有效性，本文在4个不同规模的路网数据集上对所提模型的效果和性能进行评估。在预处理阶段，提取路网的最大连通分量输入到模型中。表1为所选路网的具体信息，属性分别为顶点数量、边数量、顶点度值、平均权重。图7是4个路网数据集的可视化结果。

图  7  数据集的可视化结果

Fig.  7  Visualization results of the datasets

下载: 全尺寸图片

RGCNdist2vec模型使用Python语言进行开发，深度学习框架选择PyTorch，所有训练与测试实验的模型均运行在2张RTX2080Ti、12 GB显卡、操作系统为Ubuntu 16.04、运行内存32 GB的主机上。

4.2   评价指标

本文采用平均绝对误差E_MA（MAE）和平均相对误差E_RE（MRE）衡量估计距离($ \hat{\varphi }{(}{{v}}_{{i}}{,}{{v}}_{{j}}{)} $)与真实距离($ \varphi {(}{{v}}_{{i}}{,}{{v}}_{{j}}{)} $)之间的误差，误差越小则表示模型效果越好，MAE和MRE的定义分别为

式中N表示验证数据的数量。训练时间（precomputation/training time，PT）和查询时间（query time，QT）用来衡量模型的训练与查询效率。

4.3   参数设置

对于本文提出的RGCNdist2vec模型，在实验过程中采用2阶消息传递，其共有4个超参数，分别为1阶消息传递中的隐藏层维度hid、模型的嵌入维度d、学习率l_r、训练轮次epoch。为了获得更好的训练效果，不同的路网设置不同的超参数值。模型最优情况下的参数值设置如下：对于数据集SU和DG，设置隐藏层维度为512，嵌入维度为32，学习率为0.05；而对于数据集HA和AH，设置隐藏层维度为1024，嵌入维度为64，学习率为0.05。对于所有实验（除对比模型），将三阶段采样方法获得的训练数据打乱后输入到网络，验证数据由路网中随机选取的10⁶个顶点对构成。路网顶点的初始特征采用one-hot编码构建。

4.4   消融实验

为了测试RGCNdist2vec模型中各个模块对模型整体估计准确度的影响，通过选取最优嵌入维度及参数设置，对采样方法和嵌入方法的组合选择进行了模型的自对比。

4.4.1   分区阈值k_f的设置策略与采样方法的影响

该实验的目的是通过对三阶段采样方法中的分区阈值k_f取不同值，来观察分区阈值k_f如何影响训练数据质量，进而影响模型的估计准确度。实验策略为，调整分区阈值k_f在[2,10]范围内以1为步长进行变化，在SU数据集和DG数据集上的开展实验，实验结果如图8和图9所示。

图  8  SU数据集分区阈值变化下的效果对比

Fig.  8  Performance comparison under the change of k_f of SU dataset

下载: 全尺寸图片

图  9  DG数据集分区阈值变化下的效果对比

Fig.  9  Performance comparison under the change of k_f of DG dataset

下载: 全尺寸图片

从实验结果来看，不同路网结构的最优结果处的分区阈值k_f不同。为使模型的估计准确度最佳，本文采用一种自适应优化算法获得不同数据集的最优分区阈值k_f^[30]，该优化算法结合了模拟退火算法和粒子群优化算法，旨在为不同优化任务寻取最优解。表2为本文所用数据集的最优阈值。

图8和图9也显示了在SU数据集和DG数据集上基于地标采样与三阶段采样的对比结果。实验结果表明，在不同的分区阈值k_f下，三阶段采样方法的估计准确度均优于基于地标采样的估计结果。这是由于三阶段采样方法偏向于选取路网中重要的顶点对构成训练数据，相较于基于地标的采样对路网结构和权重的学习更有针对性。

4.4.2   消息传递阶数对模型估计准确度的影响

该实验目的是验证RGCN是否存在由于过深的消息传递阶数产生过平滑问题，在此分别对RGCN设置2、3、4阶消息传递，用来评估消息传递阶数对模型准确度的影响。实验结果如图10。

图  10  不同消息传递阶数的效果对比(SU)

Fig.  10  Performance comparison of different messaging stages (SU)

下载: 全尺寸图片

从实验结果可以看出，在2阶消息传递变换到3、4阶消息传递的过程中，模型的平均相对误差出现了大幅度上升，由此可见，RGCN和GCN相同，不适合过深阶的消息传递。

4.5   效果实验

为了评估RGCNdist2vec模型的估计准确度，使用以下几种主流模型进行对比实验。

1）ndist2vec^[14]：该模型通过深度优先算法选取一定比例的顶点构成地标顶点，从地标顶点和其余顶点中采样获得训练数据，从而训练神经网络模型逼近两顶点间的最短路径距离。

2）vdist2vec-S^[12]：该模型通过运用权重矩阵嵌入图顶点，然后再训练多层感知机逼近路网最短距离，模型的训练采用路网所有顶点对作为训练数据。

3）node2vec-Sg^[11]：运用node2vec^[22]或Poincare^[23]作为嵌入方法，通过训练神经网络用于预测社交网络的最短距离。在此，将其用于路网场景以对比模型性能。

通过对上述基线方法的介绍可知，ndist2vec和vdist2vec-S是基于多层感知机的估计计算方法，二者的区别主要在于采样方案的不同，前者根据地标采样，后者是进行全图采样。node2vec-Sg是一种主要用于无权图的估计方法。上述方法均没有充分考虑路网的拓扑结构。而RGCNdist2vec分别在采样方案和嵌入方法2个层次进行了创新，对路网结构进行了细化分析并融合了权重信息，进一步提升了最短路径距离估计任务的估计效果和效率。

4.5.1   与基线算法在估计准确度方面的对比结果

通过设置最优的参数对比4个模型在4个真实路网数据集上的估计准确度。表3为4个模型在估计准确度方面的实验结果。图11为实验结果的可视化分析。

图  11  不同模型的效果对比

Fig.  11  Comparison on effects of different models

下载: 全尺寸图片

由对比结果可知，在3个不同规模的真实路网上（除了HA），本文所提模型RGCNdist2vec的MAE和MRE均优于其他3个模型。这是由于其他模型的图嵌入方法采用基于随机游走(node2vec)或简单与权重矩阵相乘的方法，相较于本文所提的图嵌入方法，不能很好地学习路网的结构和权重信息。对于HA数据集来说，RGCNdist2vec的准确率略低于vdist2vec-S，但高于ndist2vec和node2vec-Sg。通过分析Harbin数据集的可视化结果(图7)，发现HA相较于其他3个数据集分布稀疏且权重差距较大，会削弱模型融入邻居特征的能力。

4.5.2   不同嵌入方法在估计准确度方面的对比结果

为了验证GCN的不同改进策略对模型估计准确度的影响，本文针对图嵌入方法进行模型自对比（如图12所示）。在对RGCN改进策略的不同组合下，进行效果对比实验。GCN、GCN-1和GCN-2分别对应了GCN、GCN将自连接矩阵更改为邻域权重均值自连接矩阵和GCN将无权邻接矩阵更改为带权邻接矩阵。

图  12  不同嵌入组合下的效果对比（SU）

Fig.  12  Performance comparison under different embedding combinations (SU)

下载: 全尺寸图片

从表4可以看出，在SU数据集中，RGCN模型相较于3个组合模型平均绝对百分比误差（mean absolute percentage error，MAPE）降低了约1.2百分点，这说明RGCN的改进方案对估计结果起到了促进作用。MAPE的定义为

综上，对GCN进行改进使其根据邻居权重融合邻域信息是有效的。

4.6   效率实验

表5为RGCNdist2vec模型与基线模型在效率方面的对比实验结果。通过对实验结果进行分析，本文所提RGCNdist2vec模型最大的优势体现在PT指标上，其在4个数据集上均优于对比模型。虽然基于嵌入的方法相较于传统的方法在训练时间方面已经有明显的提升，但图神经网络的相关方法对比于该任务以往方法具有更快的训练速度。同时，RGCNdist2vec模型在训练时并没有选取路网中所有顶点对作为训练数据，这也会使训练时间大幅减少。对于查询时间QT，通过计算路网n(n−1)对顶点对的查询均值来获得，实验结果表明查询时间和路网嵌入维度成正比关系。对于数据集SU和DG，本文所提模型RGCNdist2vec设置d=32，ndist2vec设置d=50，vdist2vec-S和node2vec-Sg分别设置d为0.02n和128。因RGCNdist2vec模型设置的维度均小于其余3个模型，所以查询时间最短。而对于数据集HA和AH，由于RGCNdist2vec模型设d=64，其余模型的设置值不变，则查询时间略高于ndist2vec，而低于vdist2vec和node2vec-Sg。基于嵌入类的方法均可在线性时间复杂度内获得查询结果，这也是该类方法的优点之一，能够满足数百万查询同时发起时的及时反馈^[31]。

5.   结束语

为了兼顾路网最短路径距离估计任务的估计准确性和训练时间，本文通过分析图神经网络的相关方法，提出了路网最短路径距离估计编码器−解码器框架。其次，改进图卷积神经网络将其运用到路网场景上，作为路网最短路径距离估计的嵌入方法，捕获顶点的邻域关系。同时，为了进一步提高训练效率，本文对路网分区处理，设计了一种基于图逻辑分区的三阶段采样方法，用于选取优质训练样本。最后，在4个真实的数据集上开展实验，表明所提方法在估计准确度和训练效率上均有显著的效果。在路网场景中，有向的距离计算、路网顶点嵌入的可扩展性以及路网最短路径恢复工作也非常的重要和有意义，在接下来的研究中，将进一步开展上述研究工作。