1. 项目概述为什么我们需要一个新的图学习基准如果你在过去几年里折腾过图神经网络GNN尤其是处理过像社交网络、分子结构或者推荐系统这类图数据那你大概率对“过平滑”Over-smoothing和“过挤压”Over-squashing这两个词不陌生。简单来说过平滑就是消息传递层数堆多了所有节点的特征向量都变得差不多失去了区分度过挤压则是指远距离节点的信息在通过图结构的“瓶颈”比如连接稀疏的路径时被压缩甚至丢失了。这两个问题本质上都指向了GNN的一个核心挑战如何有效地建模和利用节点之间的长程依赖Long-range Dependency。现有的基准测试比如经典的Cora、Citeseer、PubMed或者更大规模的OGB数据集大多侧重于短距离的、同配性Homophily强的任务——也就是相连的节点很可能属于同一类。在这些任务上两三层的GCN或者GraphSAGE往往就能取得不错的效果。但这就引出了一个疑问我们设计的那些号称能捕捉长程交互的深层GNN或者图TransformerGT在现有基准上表现出的性能提升到底是因为它们真的学会了利用远距离信息还是仅仅因为模型容量变大了从而更好地拟合了数据中的短程模式为了回答这个问题社区需要一个新的“考场”——一个任务目标本身就明确要求模型必须理解远距离节点关系的数据集。这就是我们这项工作的出发点。我们不再满足于用社交网络或学术引用网络而是将目光投向了城市道路网络。为什么是路网想象一下一个城市的十字路口节点和道路边。判断一个路口到城市各个区域的“可达性”或者“中心度”绝不仅仅是看它相邻的几个路口而必须考虑整个路网的结构计算它到许多跳之外节点的最短路径或加权旅行时间。这种任务天然地、强制性地要求模型具备处理长程信息的能力。然而仅仅有一个新数据集还不够。我们还需要一把“尺子”来量化模型到底在多大程度上捕捉到了长程依赖。传统做法是看模型深度增加时性能的变化但这把尺子不够精确。我们在这项工作中从理论分析入手揭示了经典GNN中均值聚合Mean Aggregation操作在长程信息传递中的根本缺陷——我们称之为“影响分数稀释”Influence Score Dilution。基于此我们提出了一种新的、更可靠的度量指标总影响力Total Influence。这套“数据集度量方法”的组合旨在为图学习社区提供一个更严谨、更具挑战性的新基准推动下一代GNN/GT架构的发展。2. 核心原理从消息传递到影响分数稀释要理解我们提出的基准和度量首先得深入GNN的核心运作机制并看清经典方法在长程场景下的“阿喀琉斯之踵”。2.1 图神经网络的消息传递范式绝大多数现代GNN都建立在消息传递神经网络MPNN框架之上。对于图中的每个节点v在第l层的更新可以抽象为h_v^{(l)} UPDATE^{(l)}(h_v^{(l-1)}, AGGREGATE^{(l)}({h_u^{(l-1)}: u ∈ N(v)}))其中N(v)是节点v的邻居集合AGGREGATE是聚合函数如求和、均值、注意力加权UPDATE是更新函数通常是一个可学习的神经网络如MLP。对于k层的GNN节点v的最终表示h_v^{(k)}理论上可以接收到k跳k-hop以内所有邻居的信息。这里的“跳数”h定义了信息的传播距离。2.2 影响分数与长程依赖的量化为了量化一个源节点u对目标节点v的最终预测有多大的影响研究者们引入了影响分数的概念。一种经典且可计算的方法是基于雅可比矩阵的影响分数I(v, u)。直观上它衡量了节点u的初始特征x_u发生微小变化时节点v的最终输出h_v^{(k)}的变化率。数学上可以表示为I(v, u) ||∂h_v^{(k)} / ∂x_u||的某种范数。对于一个给定的目标节点v和一个特定的跳数h我们可以定义其h跳邻居集合N_h(v)即所有与v最短路径距离恰好为h的节点。那么来自h跳邻居的总影响力T_h(v)就是所有这些节点影响分数的和T_h(v) I_sum(v, h) Σ_{u: ρ(v,u)h} I(v, u)其中ρ(v, u)是v到u的最短路径距离。而更常见的、在经典GCN等模型中隐式使用的度量是平均影响力I_mean(v, h) (1 / |N_h(v)|) * Σ_{u: ρ(v,u)h} I(v, u)也就是总影响力除以h跳邻居的数量。2.3 影响分数稀释定理均值聚合的“致命伤”我们的核心理论贡献在于严格证明了在网格状图Grid-like Graphs中随着跳数h的增加I_mean(v, h)会不可避免地衰减到0而I_sum(v, h)却能保持一个下界。城市路网正是这种网格状图的典型代表可以近似看作二维平面网格Z^2。定理网格状图中的均值影响力稀释假设图G是一个D维的网格状图例如城市路网对应D2且节点度有界。那么存在正常数C1, C2使得对于足够大的跳数hh跳邻居集合的大小满足C1 * h^{D-1} ≤ |N_h(v)| ≤ C2 * h^{D-1}这意味着在二维网格中h跳邻居的数量大致与h成正比增长|N_h(v)| ~ O(h)。现在考虑一个理想化但能说明问题的场景在h跳邻居中存在一个特定的节点u*它对v有着显著的影响I(v, u*) I* 0而其他所有h跳邻居对v的影响可以忽略不计近似为0。那么总影响力T_h(v) I_sum(v, h) ≥ I*。只要这个关键邻居存在总影响力至少是I*。平均影响力I_mean(v, h) I_sum(v, h) / |N_h(v)| ≤ I* / (C1 * h^{D-1})。对于二维网格D2I_mean(v, h) ~ O(1/h)。当h趋向无穷大时I_mean(v, h)会衰减到0。这就是影响分数稀释即使存在一个强有力的长程信号源u*当使用均值聚合时这个信号会被大量“无关”的h跳邻居所“稀释”最终在平均效应中消失不见。模型根本无法通过观察平均后的节点特征来感知到u*的存在。推论聚合h跳邻域内的更快稀释如果我们考虑从1跳累积到h跳的整个邻域球B_h(v) ∪_{i1}^{h} N_i(v)其大小约为O(h^D)。在同样的假设下平均影响力I_mean(B_h(v))的稀释速度将达到O(1/h^D)对于二维网格就是O(1/h^2)衰减得更快。实操心得这个理论揭示了为什么单纯增加GCN的层数来捕捉长程依赖常常会失败。即使信息在理论上能够传播到通过多层消息传递但默认的均值聚合操作就像在一个嘈杂的房间里试图听清一个远处的声音——如果只是把房间里所有人的声音平均一下那个关键声音早就被淹没了。这从原理上解释了“过平滑”的一种微观机制不是信息没传到而是传到的有效信号在聚合中被稀释了。2.4 我们的解决方案转向总影响力度量上述分析为我们选择度量指标提供了坚实的理论依据。既然I_mean会因邻居数量的增长而被稀释那么它就不是一个衡量长程依赖可靠指标。一个模型可能拥有强大的长程信息传播能力却因为使用均值聚合而在I_mean指标上表现不佳。因此在我们的基准评估中我们主张使用总影响力T_h(v)或其在整个图上的平均值T_h (1/|V|) Σ_{v∈V} T_h(v)作为核心度量。定理保证了只要在每一个h跳邻域内至少存在一个具有正影响(I*)的节点那么平均总影响力T_h就始终不低于I*不会随着h增大而衰减至零。这使得T_h成为一个更稳定、更能真实反映模型长程建模能力的指标。3. 数据集构建City-Networks的诞生与挑战有了理论武器我们需要一个能体现长程依赖本质的数据集。我们构建了City-Networks一个基于真实世界城市路网的大规模图数据集专注于直推式节点分类任务。3.1 数据来源与处理我们选择了四个具有不同规模与拓扑结构的世界级城市巴黎、上海、洛杉矶和伦敦。原始数据来源于OpenStreetMap这是一个由全球志愿者共同维护的开放式地图数据库。我们使用osmnx库来获取每个城市的路网数据其中道路交叉口被抽象为图节点道路段被抽象为无向边。节点特征来源于交叉口的真实属性数值特征纬度、经度、连接道路数量。类别特征土地利用类型如住宅、工业、商业等。边特征来源于道路段的真实属性数值特征道路长度米、限速公里/小时。二元特征是否为单行道、是否在高峰时段有潮汐车道方向可变。类别特征车道数、道路类型如主干道、次干道、支路等。特征工程流程类别特征处理对于土地利用类型、车道数、道路类型这类类别特征每个城市都可能出现上百种小众类别。我们采取了高频类别保留策略对每个特征仅保留出现频率最高的前8个类别其余所有低频类别统一归为“其他”类。实测表明这能覆盖超过90%的节点和边在保证信息量的同时极大降低了特征维度与稀疏性。边特征到节点特征的转换为了适配标准的节点分类任务模型输入通常是节点特征矩阵我们将边特征聚合到了节点上。对于每个节点我们计算其所有关联边的各个特征的平均值然后将这些聚合后的特征与节点原始特征拼接。例如一个路口节点的特征中会包含“相邻道路的平均限速”、“相邻道路中住宅区道路的比例”等衍生信息。这一步非常关键它将道路本身的属性信息融合到了路口节点中。图规范化最终我们将图转换为无向图如果两个节点间存在多条有向边则合并为一条无向边其边特征取所有原始边的平均值。经过处理每个城市的图节点数在2万到10万之间每个节点具有37维的特征。这是一个典型的大规模图。3.2 长程标签生成基于局部偏心率的节点分类数据集的核心在于其节点标签的设计。我们的目标是生成一个与长程拓扑结构强相关的标签。我们摒弃了基于节点自身属性如路口类型或极短程邻域属性如相邻路口平均流量的标签而是引入了“局部偏心率”的概念。定义与计算 对于节点v我们考虑其k跳自我中心网络k-hop ego-network即从v出发在k步内能到达的所有节点及它们之间的边构成的子图。在该子图内我们计算v到所有其他节点的加权最短路径距离其中边的权重w(e)我们初始选用道路长度。这个距离的最大值就被定义为节点v的k跳局部偏心率ê_k(v)ê_k(v) max_{u ∈ N_k(v)} ρ_w(v, u)ρ_w(v, u) min_{π ∈ P(v,u)} Σ_{e∈π} w(e)其中P(v, u)是v到u的所有路径集合。直观理解ê_k(v)可以理解为从路口v出发在只允许走k条街道的限制下最远能到达的距离米。这个指标直接反映了节点在局部路网中的“中心性”或“可达范围”它是一个典型的非局部属性。要准确预测一个路口的ê_k(v)模型必须整合v的k跳邻域内大量的路径信息。标签生成 我们为每个城市网络计算所有节点的ê_k(v)选择k16原因后述然后根据其值的分布将所有节点划分到10个分位数区间中每个区间作为一个类别。这就构成了一个10类的节点分类任务。注意事项这里有一个精妙的平衡。k不能太小比如4或8否则任务可能被浅层GNN解决无法体现长程性。k也不能太大比如接近图的直径否则ê_k(v)会趋近于全局偏心率而全局偏心率在城市这种近似二维网格的结构中与节点的空间坐标经纬度高度相关市中心节点偏心率小郊区大。如果标签只和坐标强相关那么一个简单的多层感知机MLP忽略图结构也能做好这就失去了图学习基准的意义。我们的实验验证了k16是一个甜点既足够长迫使模型需要深层传播又不至于让标签退化为纯空间函数。3.3 计算优化与可行性直接计算全图所有节点对的最短路径例如使用Floyd-Warshall算法复杂度是O(|V|^3)对于十万节点级别的图是不可行的。我们采用局部计算策略为每个节点v提取其k跳自我中心子图。这个子图通常远小于原图。在该子图上使用Dijkstra算法计算v到所有其他节点的加权最短路径。复杂度约为O(|Ê| |V̂| log|V̂|)其中|V̂|和|Ê|是子图的平均规模。并行化处理所有节点。我们在一个72核的CPU集群上计算四个城市k16的局部偏心率耗时在3到23小时之间这在学术研究的数据集预处理阶段是完全可以接受的。4. 基准实验与核心发现我们使用City-Networks数据集对一系列代表性的GNN和GT模型进行了基准测试旨在回答现有模型能否有效学习我们定义的长程依赖信号4.1 实验设置与基线模型任务直推式节点分类10类。评估指标分类准确率Accuracy。对比模型MLP仅使用节点特征完全忽略图结构。这是一个重要的下限基准用于检验任务是否真的需要图结构信息。经典GNNsGCN图卷积网络使用均值聚合。GraphSAGE采样邻居并聚合更具可扩展性。图Transformers (GTs)Exphormer通过扩展器图Expander Graphs近似全局注意力提升效率。SGFormer一种简化且高效的图Transformer架构。关键变量我们系统地改变了模型的层数num_layers从2层一直到32层以观察模型深度即理论感受野对性能的影响。4.2 结果分析深度与长程依赖实验结果以巴黎和上海为例揭示了一些非常有趣且一致的规律MLP性能显著落后在所有城市和所有模型深度下MLP的性能都远低于图模型。这有力地证明了我们生成的节点标签局部偏心率确实依赖于图结构信息而不仅仅是节点的空间坐标或自身特征。即使我们只给MLP提供经纬度坐标其性能也远不足以完成任务。GNN与GT的性能随深增加而提升对于GCN、GraphSAGE、Exphormer等模型随着层数从2增加到16分类准确率呈现持续且显著的上升趋势。这是一个关键信号在传统的同配性社交网络数据上GCN的性能通常在2-3层达到顶峰随后因过平滑而下降。而在我们的City-Networks上性能在更深层如16层仍在提升说明更深层的模型确实捕捉到了更远距离的信息这对于完成基于16跳偏心率的任务是必要的。性能提升的饱和与平台期当层数继续增加到32层时性能提升变得非常缓慢甚至出现平台。这可能有几个原因一是理论感受野已经足够覆盖标签所需的k16跳信息二是过深的网络带来了优化困难或过拟合三是对于GT模型由于全局注意力的O(N^2)复杂度在层数很深时极易出现显存溢出OOM错误限制了其深度探索。不同城市的对比不同拓扑结构的城市网络对模型提出了不同挑战。例如上海的路网可能更规整网格状更强而巴黎的路网可能包含更多不规则和历史形成的结构。模型在不同城市上的绝对性能差异以及达到峰值性能所需的最优深度都为我们理解模型架构与图拓扑的交互提供了丰富信息。4.3 消融实验坐标信息的作用为了进一步剥离空间信息与拓扑信息的作用我们进行了消融实验实验组AGNN/GT模型使用全部37维节点特征包含坐标。实验组BGNN/GT模型使用掩码掉经纬度坐标后的节点特征。对照组MLP模型仅使用经纬度坐标作为特征。结果对于GNN和GT掩码坐标后性能仅有轻微下降例如下降1-3%。而对于MLP仅使用坐标的性能比使用全部特征时暴跌了约50%。这再次确认坐标本身信息不足仅靠地理位置无法准确预测局部偏心率。图模型学会了利用拓扑GNN/GT主要从图结构连接关系和衍生特征如聚合后的道路属性中学习坐标只是辅助信息。即使没有坐标它们依然能通过消息传递理解网络的连通性来推断可达性。5. 影响分数稀释的实证验证与模型设计启示我们的理论分析和实验结果是相互印证的。City-Networks上的实验现象可以从影响分数稀释的角度得到解释。5.1 为什么深层GCN在这里有效在传统同配图任务中深层GCN失效主要是因为过平滑——所有节点特征趋同。但在我们的长程任务中目标信号局部偏心率本身就是一个全局性的节点属性。要预测它节点需要汇聚来自很远距离的信息。虽然均值聚合会导致来自某一跳的单个重要信号被稀释但总影响力T_h(v)是跨所有跳数累积的。一个足够深的GCN其最终节点表示h_v^{(L)}是经历了L次消息传递后的结果它隐式地聚合了从1跳到L跳的所有邻居信息的总和或某种混合。只要这个累积的总影响力足够强模型就能从中提取出用于分类的信号。我们的实验表明在City-Networks上需要大约16层才能较好地捕捉到16跳的信号这与理论是吻合的。5.2 对下一代图模型设计的启示我们的工作为图神经网络特别是旨在解决长程依赖问题的模型提供了明确的评估标准和设计方向超越均值聚合理论明确指出了均值聚合在长程场景的缺陷。未来的模型应探索更鲁棒的聚合机制例如注意力机制像GAT或图Transformer中的注意力可以学习对重要邻居分配更高权重本质上是在计算一个加权和更接近保留“总影响力”而非被“平均影响力”稀释。门控机制或残差连接帮助模型在深层网络中保留和传递来自早期层的关键信息防止其被后续的均值操作淹没。显式的高阶路径编码不局限于1跳邻居的聚合而是直接建模节点间的多跳路径例如通过子图采样或路径编码方法。可扩展的全局感受野City-Networks的规模要求模型必须具有可扩展性。像Vanilla Transformer那样计算全图所有节点对的注意力是不现实的。需要推广像Exphormer、SGFormer这类使用稀疏化、线性化或分层策略的GT以及像GraphSAGE这样基于采样的GNN使它们能够在保持效率的同时有效地整合远距离信息。基准驱动的架构创新City-Networks作为一个新的、具有明确长程语义的基准可以更公平地比较不同架构在长程依赖建模上的能力。以往在短程基准上表现相近的模型可能在这个新基准上拉开显著差距从而催生真正为长程交互设计的创新架构。6. 潜在应用与未来展望这项工作不仅是一个学术基准也具有切实的实际应用潜力。在城市规划与交通分析中的应用我们基于局部偏心率的节点分类任务本质上是在量化城市中不同位置的“可达性”或“中心性”。这种度量对于城市规划者至关重要。例如识别交通瓶颈局部偏心率异常高的区域可能意味着路网连通性差是潜在的交通拥堵点。评估基础设施影响新建一条道路或一座桥梁后重新计算相关区域的局部偏心率可以量化该设施对改善区域连通性的效果。15分钟城市概念评估“15分钟城市”倡导居民在步行或骑行15分钟内获取基本服务。我们的方法可以用于绘制城市中不同点位在特定时间/距离阈值内的服务可达性地图。未来工作方向更真实的边权重目前我们使用道路长度作为边权重来计算加权最短路径。一个自然的扩展是引入旅行时间作为权重这可以通过结合道路长度、限速、甚至历史交通流量数据来估算。这将使我们的标签更贴近真实的交通可达性分析。动态图建模真实的城市路网是动态的交通流量、速度限制如潮汐车道随时间变化。未来可以构建动态图版本的数据集研究时空图神经网络STGNN在长程依赖建模上的表现。面向其他领域的泛化虽然我们聚焦于城市路网但“基于局部偏心率的长程标签生成”思路可以推广到其他具有网格状或类网格结构的领域如电路板布线分析、蛋白质残基接触图、甚至是一些社交网络中的社区结构分析只要其任务本质与节点的全局网络位置相关。构建City-Networks和提出影响分数稀释理论的过程让我深刻体会到一个好的基准不仅能评估现有模型更能揭示其根本局限并指引未来方向。长程依赖是图学习迈向更复杂、更现实应用的必经之路而这条路才刚刚开始。