✦

点击蓝字关注我们

编者按：该文是北大人工智能研究院马剑竹课题组发表在Nature Machine Intelligence上的一篇研究论文，属于人工智能与城市科学交叉领域的工作。在城市科学的研究中，路网、航空网、航运网等被看作时空中信息传输的重要载体，与之相关理论有中心地理论、空间句法理论、流空间理论等。近年来随着人工智能领域的快速发展，其应用面越来越广，提出的模型对复杂场景的适应能力也逐渐增强，这其中的代表就有图神经网络。在城市科学中也有不少研究将图神经网络应用于兴趣点推荐、轨迹预测、交通流量预测等场景，但尚未有研究使用图神经网络的方法对不同城市的路网空间同质性进行分析。早期研究路网生成机制的工作可以参考空间句法创始人Bill Hillier的《空间的社会逻辑》一书，该书基于Chomsky的形式语言创建了空间句法，并基于空间句法对路网生成机制进行了深入的研究，该工作也对后续路网生成机制研究起到了很大的影响作用。近年来也有不少研究从复杂网络中的“规模”视角对路网宏观及微观尺度的分布特性进行研究。从机器学习的视角来看，空间句法对路网的研究分析主要是使用特征工程的方法，但是对于路网节点间的复杂链接建模则缺乏一定的有效性，本文则主要针对路网的空间连接特性以及空间分布对空间同质性的影响使用图神经网络的方法进行了探索。

原文链接：

https://www.nature.com/articles/s42256-022-00462-y

代码链接：

https://github.com/jiang719/road-network-predictability.git

Abstract

量化城市道路网络不同部分的拓扑相似性可以帮助我们理解城市的增长模式。虽然传统的统计数据提供了关于单个节点的直接邻近节点或整个网络的特征信息，但考虑到局部间接邻近关系，这种度量无法衡量子网的相似性。该研究提出一种基于图的机器学习方法，应用于全球30个城市的11790个城市道路网络，以衡量城市内部和城市之间道路网络的空间同质性，发现城市内部的空间同质性与社会经济地位(如GDP和人口增长)高度相关。此外，通过将模型在不同城市间的转移得到城市间空间同质性，揭示了城市间网络结构的相似性起源于欧洲，传递至美国和亚洲城市。使用这一方法所揭示的社会经济发展和城市间相似性可以用于理解和转移跨城市的见解，应对城市政策挑战，如：快速城市化地区的网络规划和消除区域不平等。

Introduction

过去几十年，城市道路网络（Urban road network，URN）在社会交流、商品流通中发挥了核心作用，它的一些潜在特征揭示了道路结构和功能的相互作用。许多关于道路网络的度量标准被广泛应用于研究中，表征路网拓扑特征分布，但它们都无法捕获间接邻近节点之间的关系。子图理论和高阶交互作用能够挖掘邻近节点组成的团簇间的结构以及交互模式，但无法对子图相似性直接进行量化。而该研究提出的“空间同质性”（Spatial homogeneity）实现了对子图间相似性的描述，并捕获了间接邻居关系。空间同质性代表了市内不同区域交互的拓扑特征的相似性程度，可以通过从URN中提取多跳邻居节点信息来揭示城市知识，并与社会经济发展相联系。

为了能从URN中得到上述观点，首要任务时定义空间同质性，以捕获现有URN指标中缺失的间接邻居节点关系。由于多跳消息传播机制可以有效捕获URN中的多跳节点关系，该研究采用图神经网络（Graph neural network，GNN）来捕捉URN中的间接邻居节点关系，预测URN上道路链接的存在。该研究使用预测精度指标来定城市内及城际的路网空间同质性，建立城市同质性转移矩阵（City homogeneity transfer matrix，CHTM）来量化城市间的空间同质性。路网空间同质性揭示了已有路网指标不可见的深刻的社会经济发展（以GDP和人口增长为指标）和城市间的相似性模式，高GDP和低人口增长的城市的空间同质性显著高于其他城市。

简而言之，该研究的主要贡献在于使用GNN挖掘细粒度的局部URN信息，并以城市内发展和城市间相似性呈现其联系。该研究的主要目的在于理解基础设施与城市经济过程间的耦合关系。该研究的指标和发现对学界和业界的突出价值具体如下：

市内空间同质性将帮助城市区域及社会科学家实现空间基础设施平等；
城际空间同质性用作路网相似性的定量度量将支持不同跨城市迁移政策（例如，自动驾驶和事故预防相关的政策，尤其是从发达国家借鉴到发展中国家的场景）；
城际urban insights记录了城市的历史模式，对城市考古学有一定帮助。

Results

1. 使用GNN度量了全球30个城市的同质性

首先将URN建模为图，交叉口和路段分别用节点和链接表示。

高空间同质性的URN更有可能包含很多可以被图的其余部分还原（预测）的链路，因此该研究选择通过链路预测问题的F1 score来量化网络的空间同质性。使用图神经网络模型（R-GCN模型），根据两个端点的结构角色的偏置来预测链接是否存在。空间同质性度量是一种捕获了不同现有网络统计指标的复合度量，包括了平均度和中介中心性。实验发现低平均中介中心性和高平均度的城市有更高的空间同质性，可预测性也更强。

将预测结果与现有的路网聚类有关工作相联系。首先，F1 score越高，表明子网络利用全局信息的可预测性越高，但这不足以和现有的城市科学理论相联系。为了探究不同拓扑类型的URN是否会在F1 score上有显著不同，该研究对11790个URN计算11个现有的网络指标，将其编码为11维向量点，使用K-means算法将11790个点聚为四类，即将URN分为以下四类：

Type 1：“Grid”：拥有最大的平均度数以及最大比例的“度数≥4”的节点；
Type 2：“Degree-3”：表现为拥有最大比例的“度数=3”的节点；
Type 3：“Irregular grid”：核心特征为“度数=1”的节点以及“断头路”；
Type 4：“Circuitous”：拥有最大的circuity值（网络距离与直线距离之比）以及“桥”的比例。

可得如下结果：

不同城市具有差异化的F1 score可以使用道路类型来解释；

四种类型各自的F1 score也不尽相同，其中Type 1对应的F1 score值最高；

某城市平均F1 score与Type 1类型占比呈正相关（Pearson相关系数=0.702）。

为了进一步分析空间同质性度量，该文对URN的11维向量表示进行主成分分析(PCA)，第一主成分PC1为网络不规则性（Network irregularity，NI），其与circuity和dendricity("桥"和“断头路”的比例)呈正相关，与平均度呈负相关。研究发现，F1 score与NI负相关。也就是说，越不规则的网络，其F1 score越低，可预测性较弱，空间同质性较低。

2. 空间同质性揭示社会经济发展

路网作为城市空间的骨架，随着经济发展和人口空间集聚的历史进程而演变。研究了城市内部空间同质性与经济、人口增长和城市年龄等社会经济地位之间的相互影响将有助于加深对城市的理解。根据1950-2020年的有关数据，该研究首先将城市按GDP和PG（人口增长）分为四类，分别得到各类的F1 score。结果表明：高GDP &低PG（发达国家的“成熟城市”）预测精度显著高，即空间同质性好，而现有的网络指标并没有类似的显著结果。

之后该研究探索了新指标是否与城市的年龄有关，将城市按历史分为“公元前”、“1-16世纪”、“17-18世纪”和“19-20世纪”四种类型后发现：“17-18世纪”和“19-20世纪”类型的城市F1 score明显高于“公元前”和“1-16世纪”类型的城市，这一结果是合理的，因为年轻城市高速发展时期的城市规划在城市级别必须标准且统一。

该研究进一步分析了F1 score与15个城市因子间的关系，这15个因子被划分为：社会经济因子、路网尺度指标、路网密度指标以及网络拓扑指标。该研究将15个因子作为解释变量，统一城市的average F1 score作为应变量。结果显示，PG相比人口本身与城市空间同质性更相关。GDP和F1 score之间存在关联，GDP越高则空间同质性越显著。空间同质性与路网尺度指标呈现正相关。

3. 迁移学习揭示城市间相似性

为了计算城市间URN的空间同质性，该研究进行了跨城市链接预测(在A市训练模型，在B市测试模型)，并以这些城市的平均F1 score作为训练样本和测试样本，对这些城市进行层次聚类，将测试样本分为“USA”、“Asia(c)”、“Asia(w)”、“Europe”，训练样本分为“高多样性”、“低多样性”两类。

根据F1 score建立城市同质转移矩阵(CHTM)，CHTM(A, B)表示训练于A城市的GNN应用于B城市时的F1 score，如图所示：F1 score高块位于左上角，大多数训练城市为欧洲城市或美国城市，而测试城市主要是美国城市。这一结果与历史上美国城市规划风格受欧洲城市启发的说法相一致。另外，美国的城市是系统规划和建设的，而欧洲和亚洲的城市则由复杂的历史和现代因素所塑造的。此外，将训练数据的城市设置为从米兰到首尔将比其他城市获得更高的F1 score，即这些城市可能拥有更好的路网“多样性”，使得从这些城市识别的拓扑特征可以应用于其他城市。

为了计算城市之间的相似度，该研究将城市编码为16维向量，其中包括：节点数、链路数、链路总长度、中介中心性、总面积等5个指标以及路网聚类中的11个指标（参见Methods），从而对城市路网特征提供全面的描述。使用两个向量的余弦值来计算城市间相似度，分别用最小值和最大值将值线性归一化到0和1以及将值除以最大值来规范化该值，如图所示。

4. 从城际迁移学习进行历史urban insights

该研究降低了分析尺度并研究局部子网上的城际迁移学习的预测效果能否进一步研究历史urban insights。该研究进行了案例分析，当训练城市为芝加哥及纽约，并在洛杉矶上做推理时，洛杉矶西南部的乡村区域相比东北部表现出更好的预测效果，即洛杉矶西南部乡村的路网风格与芝加哥和纽约更加相近。在大阪则发现了相反的结论，研究发现大阪和东京的路网风格相比大阪周边区域更相近。最后一个重要发现是东京回收的土地，研究发现东京湾海岸回收区域的URN的路网模式与芝加哥和纽约以及伦敦和巴黎相比东京其他西部区域更加相近。

Discussion

该研究利用GNN模型，提出了一种空间同质性指标，揭示了深刻的城市发展和城市间相似性模式，但也存在三个局限性：

当GNN加深之后，预测性能会下降，在模型训练过程中会出现梯度消失和过度平滑的问题；
对URNs进行链路预测的可靠性受参数选择的影响，进一步的研究需要综合的参数敏感性试验和针对不同路网的统一的标准；
该研究将城市定义为20km×20km，但更理想的是采用标准来源的边界（MSAs、GHSL）或现有方法定义的边界（CCA）。

该研究对未来城市研究的主要贡献有：

缺失数据补全（人道主义和地图协助）：在路网数据稀疏的区域，使用GNN模型来预测缺失道路，然后与卫星图像等地面真实数据进行对比，验证缺失道路是否存在。
基础设施公平性评价（城市科学与政策）：在快速城市化的城市中，区域和社会科学家利用这一指标来衡量不同地区的路网空间同质性，并做出公平的基础设施和设施政策决策。
定量城市分析（城市考古学）：利用城市间相似性结果，城市考古学家可以更好地以定量的方式跟踪全球道路网络的历史演变和社会经济环境。
迁移学习基准（城市计算）：由于城市间社会经济活动对城市中心网络的依赖性强，衡量城市中心网络的空间同质性有助于评价城市间转移性。
级联故障分析（网络科学）：级联故障在网络中从局部发展到多跳邻居和全局规模。空间同质性可以应用于理解故障的级联动力学，捕获网络中的多跳节点关系。

总之，空间同质性度量量化了分段和整个网络之间的相似性，并提供了广泛的多学科贡献。未来，高精度道路网络和城市交通数据（如道路等级、交通流）将促进交通网络空间同质化的量化。此外，用户友好的空间同质化计算软件库也有利于在实践中提高机器学习的实现效率。

长远影响

该研究提出的空间同质性指标在量化两个子网相似性上有两个主要特征：

使跨城市路网的定量比较成为可能
这种网络无感（network-agnostic）的指标揭示了不同城市规划政策间的可迁移性这两大特性将在城市科学、城市计算以及网络科学等得到广泛应用。

Methods

1. 数据集

利用OSMnx从OpenStreetMap (OSM)下载路网数据，选择30个主要的全球城市作为样本，使样本容纳具有不同历史、地区、位置和发展状况的城市。对每个城市，将研究区域定义为20km×20km的网格区域，其中包含400个1km×1km的URNs，设置了训练和测试样本比例为3:1。同时收集了用于关联分析的社会指标数据（GDP、人口）。

2. GNN 模型

根据URN拓扑来预测缺失的链接，通过添加已知的社会经济因素（如土地使用、人口统计）作为节点和链接特征，将任务制定为多类分类问题来预测其他类型的信息（如道路车道数量、交通流量）。

R-GCN 模型

将来自30个城市的11790个URNs数据输入到R-GCN模型中，为每个节点i生成一个低维表示h_i，它是其上一层邻居表示h_j的非线性聚合：

其中l+1和l为层数，R为关系集，N_rⁱ为节点i在关系r下的邻域节点集，W_r^l 和W₀^l是可学习的参数矩阵。采用双线性投影函数DistMult，将一对节点的表示转换为它们的连接强度：

采用sigmoid函数将连接强度值转换到(0,1)，并设置阈值δ，超过阈值δ，则链路存在：

利用Adam optimizer最小化交叉熵损失，以端到端方式联合训练R-GCN和DistMult中的参数：

其中y=1, y=0分别代表正负链接，ω=5:1为负采样之比，|E|为样本总数。

R-GCN* 模型

R-GCN* 模型在R-GCN模型的基础上增加了两个decoding改进，以避免预测中的交叉链接问题和锐角问题。如图所示，交叉链接问题：网络a中，链接2被预测存在，则与链接2相交的链接3将被预测不存在；锐角问题：网络b中，链接2被预测存在，则与链接2存在锐角的链接3将被预测不存在。

除此之外，为了比较模型性能，还实现了其他5个GNN模型：Node2vec、Struc2vec、GraphSAGE、 spectral GCN、GAT。

3. 模型性能

模型的性能对比如下:

由模型性能对比结果可知，R-GCN* 实现了AUPRC=0.28和F1 score=0.42的预测精度，优于其他模型。通过最大化最佳模型R-GCN* 的F1 score来定义sigmoid连接强度阈值为0.61。如果两个节点的sigmoid连接强度至少为0.61，那么预测它们在现实世界中是由一个路段连接的，因为它们在路网中的结构角色是相似的。

4. 空间同质性量化

空间同质性描述了局部网络和整个网络之间的相似性。由于链路预测利用全局路网信息来预测局部路网中的链路，因此具有高空间同质性的路网具有可预测性。因此，该研究使用预测性能指标F1 score来量化空间同质性：

对于每个路网单元，空间同质性为链路预测下的F1 score。
对于每个城市，空间同质性定义为所有路网单元的平均F1 score。

5. 关联分析

对路网的11个特征进行测量。

并基于此对路网进行聚类，发现当聚类数为4时具有较高的可解释性。

6. 超参设置

在该链路预测任务中，负样本(不存在的链路)的数量远大于正样本(链路)。为了防止GNN模型过分关注负样本，对负样本进行子集采样，使正样本与负样本之比为1:5。层数、迭代轮数、学习率和GNN中的神经元是模型中的超参数。为了确定这些超参数，执行标准的五折交叉验证，并最终设置迭代轮数为10，学习率为0.001，层数为3，神经元数量为50。

| 作者：杨素

| 编校：顾海硕；甄沐华

安全防范与风险评估

重点实验室