GATNextHop：一种用于最短路径路由的图注意力网络，具有跨拓扑泛化能力

# 一种用于跨拓扑泛化的最短路径路由图注意力网络
来源：https://arxiv.org/html/2608.23917
## GATNextHop：一种用于跨拓扑泛化的最短路径路由图注意力网络
代码可在以下地址获取：https://github.com/knhn1004/GATNextHop

周家宏
单位：圣何塞州立大学计算机科学系，加利福尼亚州圣何塞
电子邮箱：oliver\.chou@sjsu\.edu
卡捷琳娜·波蒂卡
单位：圣何塞州立大学计算机科学系，加利福尼亚州圣何塞
电子邮箱：katerina\.potika@sjsu\.edu

###### 摘要

常用的最短路径算法（如 OSPF 使用的 Dijkstra \(SPF\) 算法）能提供精确的路由解决方案，但必须为每个网络拓扑重新计算，这限制了其在动态或大规模网络中的可扩展性。本文提出了 GATNextHop 模型，旨在探究图神经网络（具体而言，图注意力网络）能否近似最短路径并实现跨拓扑泛化。通过在合成图上进行训练，并在互联网拓扑库（Internet Topology Zoo）的现实世界互联网服务提供商网络上进行评估，我们旨在评估模型学习能跨网络结构迁移的路由启发式方法的能力。性能将通过准确性、推理速度和泛化能力来评估，并将图神经网络与 Dijkstra 算法进行比较，以量化学习型与经典路由方法之间的权衡。

###### 关键词：

图神经网络，最短路径，路由，拓扑，互联网拓扑库，图注意力网络，随机图

## I 引言

在拓扑结构不断变化的现代网络环境中，如何以最优方式高效地路由数据包颇具挑战。虽然诸如 OSPF\[1 (https://arxiv.org/html/2608.23917#bib.bib2)\] 及其 SPF（Dijkstra）算法等最短路径路由协议可靠且精确，但它们必须在每次拓扑变化时重新运行，这在拓扑频繁变化或传输有限的网络拓扑中显得不足。

图神经网络（GNN）为现有的路由优化研究引入了范式转变。包括 Dijkstra 在内的经典算法保证了在静态拓扑中运行最优的精确解，但难以适应可扩展的动态环境。相反，根据 Jiang 等人 \[2 (https://arxiv.org/html/2608.23917#bib.bib9)\] 的研究，基于 GNN 的方法能够实现变化环境中的优化，并已被应用于解决网络路由问题。

先前的工作探索了使用 GNN 在动态、可扩展的网络拓扑中执行路由优化。研究发现，在动态或复杂的网络环境中，基于 GNN 的路由方法可以优于 Dijkstra 最短路径算法 \[3 (https://arxiv.org/html/2608.23917#bib.bib13)\]。基于这一思路，我们研究了一个 GNN，具体而言是图注意力网络（GAT）\[4 (https://arxiv.org/html/2608.23917#bib.bib4)\]，能否近似预测最可能的下一跳节点，并从合成（随机）图泛化到真实的互联网服务提供商（ISP）拓扑。

首先，我们分析了来自互联网拓扑库 \[5 (https://arxiv.org/html/2608.23917#bib.bib1)\] 数据集的真实世界网络拓扑，并探索了节点和边层面的关键特征，包括度、中心性、权重、介数和聚类系数。然后，基于对真实网络的分析，我们使用 NetworkX 库 \[6 (https://arxiv.org/html/2608.23917#bib.bib14)\] 策划了包含 1000 个合成（随机）图的数据集，其特征与训练集相似。使用训练集，我们进行了 80-20 的测试-验证划分，并训练了一个编码边和节点特征以预测最短距离最佳下一跳节点的 GAT。使用包含 4 个节点特征（归一化度、介数中心性、聚类系数和度中心性）和 1 个边特征（边权重）的 GAT，我们在训练的合成验证集上达到了 85.1% 的准确率，在互联网拓扑库测试集上达到了 84.2% 的准确率。此外，通过仅包含介数中心性作为节点级特征，该模型优于全特征模型，在合成集上达到了 85.7% 的准确率，在测试集上达到了 84.6% 的准确率。这表明，只要训练数据在结构上相似，GAT 有可能从合成数据集中泛化，并估计真实网络拓扑上的最优下一跳。

本文的贡献如下：(i) 设计了 GATNextHop，一个基于 GAT 的下一跳预测模型，在合成图上达到 85.1% 的准确率，在未见过的互联网拓扑库拓扑上达到 84.2% 的准确率，并通过消融研究确定介数中心性是最重要的节点特征；(ii) 使用来自互联网拓扑库数据集的 180 个真实世界 ISP 拓扑，对不同图规模下的 SPF（Dijkstra）与 GAT 推理速度进行了基准测试。

我们方法的目标是处理 Dijkstra 算法假设失效的情况（例如动态和部分图）。我们的重点是在不确定性下的泛化，而非计算竞争。

## II 相关工作

Almasan 等人 \[7 (https://arxiv.org/html/2608.23917#bib.bib7)\] 将 GNN 与深度强化学习（DRL）相结合，学习能够泛化到未见拓扑的路由策略，优于先前的 DRL 和 MLP 方法。Rusek 等人 \[8 (https://arxiv.org/html/2608.23917#bib.bib8)\] 引入了 RouteNet，使用 GNN 预测每条路径的延迟和丢包，并将其应用于软件定义网络（SDN）路由优化。Ferriol-Galmés 等人 \[9 (https://arxiv.org/html/2608.23917#bib.bib6)\] 更进一步，开发了 RouteNet-Fermi，它更精确，并且适用于训练期间未见过的更大网络。He 等人 \[10 (https://arxiv.org/html/2608.23917#bib.bib10)\] 提出了 MPDRL，将 GNN 插入 DRL 代理中，以利用跨拓扑的消息传输，与传统算法相比，改善了 ISP 网络中的负载均衡路由。Zheng 等人 \[11 (https://arxiv.org/html/2608.23917#bib.bib11)\] 提出了用于 SDN 的 GNN-DRL，使用 GNN 状态编码器与 DRL，以最小化最大链路利用率和延迟，在高负载下优于 OSPF、ECMP 和之前的智能路由器（EARS）。

然而，大多数先前的工作使用原始或改进的图卷积网络（GCNs）\[12 (https://arxiv.org/html/2608.23917#bib.bib12)\] 或消息传递神经网络（MPNNs）\[13 (https://arxiv.org/html/2608.23917#bib.bib3)\]，对邻居使用统一或度归一化的权重。另一方面，图注意力网络（GAT）\[4 (https://arxiv.org/html/2608.23917#bib.bib4)\] 引入了掩码自注意力，允许为每个邻居分配不同的重要性。对于我们的问题，使用 GAT 解决下一跳问题是合理的，因为我们的目标是编码结构信息并预测模式。这与 GAT 区别对待每个邻居的理念一致，从而为更好的决策提供了额外的学习机会。诚然，我们的用例局限于静态环境，并未分析动态拓扑配置。尽管如此，本文探索了 GAT 能否从见过的拓扑中学习，并泛化到预测未见拓扑中的路由。

## III 方法论

### III-A 真实世界网络拓扑分析

我们的研究对象是真实世界的互联网拓扑库数据集（Zoo）\[5 (https://arxiv.org/html/2608.23917#bib.bib1)\]（276 个原始拓扑，预处理后为 180 个）。拓扑分析遵循以下步骤：(1) 预处理原始数据，(2) 在图上分配权重，(3) 计算距离矩阵，(4) 描述图统计特征。

#### III-A1 预处理

我们将每个图转换为无向简单图（移除多边和自环），提取最大的连通分量，并将节点重新标记为 0...n。节点数少于三个或解析失败的图被丢弃，最终保留 180 个图。

#### III-A2 权重分配

由于真实图缺少边权重，我们为每条边分配一个在 \[1,...,100\] 范围内的均匀随机实数权重（64 位精度）。

#### III-A3 距离矩阵

我们通过 Dijkstra 算法计算所有点对的最短路径，并将其存储为基本事实。下一跳标签在评估期间得出：对于每个 \((s,t)\)，选择 \(s\) 的邻居 \(w\)，满足 \(dist(s,t)=weight(s,w)+dist(w,t)\)，其中 \(weight(e)\) 是边 \(e\) 的权重，\(dist(s,t)\) 是从节点 \(s\) 到节点 \(t\) 最短路径的权重。

#### III-A4 图特征描述

我们收集了 180 个已处理互联网拓扑库图的统计数据，并取中位数，如表 I (https://arxiv.org/html/2608.23917#S3.T1) 所示。这决定了我们在生成合成训练图时希望达到的目标参数。

表 I：180 个互联网拓扑库图的摘要统计。

### III-B 合成数据集策划

基于图特征描述，我们使用五个模型生成了 1,000 个合成图（每个模型 200 个），包括 Erdős-Rényi（ER）、Barabási-Albert（BA）、Watts-Strogatz（WS）、随机块模型（SBM）和 Waxman，并校准至 Zoo 数据集的中位数。

这些参数经过精心挑选，以使合成数据尽可能接近 Zoo 数据集，遵循早期图特征描述的结果，这些参数为：
- •ER：选择 \(p\) 使得期望度 = 2.3
- •BA：\(m=1\)，因此平均度 ≈ 2
- •WS：\(k=2, p \in [0.1,0.4]\)
- •SBM：内部目标度 2.3，较低的 \(p\_out\)
- •Waxman：较低的 \(\alpha/\beta\) 以获得更稀疏的图

此外，预先计算了所有点对的最短路径值 \(dist(u,v)\)，并将原始的 1,000 个图以随机种子 42 划分为 800 个训练集和 200 个验证集。

### III-C GNN 模型设计

#### III-C1 任务表述与基本事实

形式化地，我们的目标是：给定一个图 \(G\)、源节点 \(s\) 和目标节点 \(t\)，我们希望预测 \(s\) 的哪个邻居 \(w\) 位于 \(s\) 和 \(t\) 之间的最短路径上，本质上就是下一跳节点。这是一个针对候选集 \(N(s)\) 的分类问题。基本事实是邻居 \(w\)，满足 \(dist(s,t)=weight(s,w)+dist(w,t)\)，并使用 \(1e-5\) 的容差进行验证。

我们设计了一个图注意力网络（GAT）\[4 (https://arxiv.org/html/2608.23917#bib.bib4)\]，称为 GATNextHop 模型。我们选择 GAT 是因为其注意力机制可以增加朝向最短路径的邻居的权重，降低其他邻居的权重。GAT 非常适合这种依赖邻居的自适应决策问题。

#### III-C2 特征选择

为了捕获结构信息，我们使用 4 维节点特征，每个特征通过除以最大值归一化到 \([0,1]\)：度、介数中心性（加权）、聚类系数和度中心性。度统计节点的直接连接数，介数中心性衡量节点位于其他节点对最短路径上的频率，聚类系数捕获节点周围三角形的密度，度中心性是归一化的度。此外，它使用 1 维边特征，包含边权重。

#### III-C3 架构（GATNextHop）

参考图 1：GATNextHop GAT 模型架构，如图 1 (https://arxiv.org/html/2608.23917#S3.F1) 所示。
- •GATConv 3 层，每层有 64 个隐藏单元和 4 个注意力头（每层输出维度 = \(64 \times 4 = 256\)）。边感知注意力，使用 \(edge\_dim=1\)。启用自环。ReLU 激活 + 每层后接 dropout（0.1）。
- •对于每个 \((s,t,\text{候选 }w)\) 三元组，将最终的嵌入向量 \([h_s;h_t;h_w]\)（维度 \(3 \times 256 = 768\)）拼接。通过一个 2 层 MLP：Linear(768, 64) → ReLU → Dropout(0.1) → Linear(64, 1)，为每个候选节点产生一个标量分数。
- •无效候选（填充）在 softmax 前被掩码为 -1e9。
- •损失函数：候选节点 logits 上的交叉熵。

#### III-C4 训练细节

我们使用 Adam 优化器，初始学习率 \(LR=1e-3\)。使用 ReduceLROnPlateau 学习率调度器，监测验证准确率，因子为 0.5，耐心值为 5。我们运行了 100 个 epoch（带有早停），批次大小为 16 个图，每个 epoch 从每个图中采样 100 个 \((s,t)\) 对，每个源节点最多有 64 个候选节点。所示结果的模型是在一台 MacBook Pro M2 Max 设备上使用 CPU 训练的，耗时 3 分 27 秒，在第 77 个 epoch 时早停。

### III-D 实验

#### III-D1 差距分析：合成图 vs 互联网拓扑库图

尽管我们尽力创建了一个具有互联网拓扑库特征的合成数据集，但生成的合成图使用了不同的模型，包含不同的属性。认识到这一差距，我们使用中位数、比率和真实感分数比较了 Zoo 和合成图之间的 8 项结构指标（节点数、边数、密度、平均度、聚类系数、平均最短路径、同配性、直径）。对于每个指标，比率计算为（合成图中位数）/（Zoo 中位数），其中 Zoo 中位数 ≠ 0。每个指标的真实感分数计算为 \(1-D\)，其中 \(D \in [0.0,1.0]\) 是 Zoo 和合成分布之间的 Kolmogorov-Smirnov 统计量距离 \[14 (https://arxiv.org/html/2608.23917#bib.bib5)\]，因此 1.0 表示分布完全相同，0.0 表示最大差异。

#### III-D2 主要评估

我们在 800 个合成图上训练 GAT，并在另外 200 个图上进行验证。模型在训练期间从未见过真实的互联网拓扑库图。准确率报告为预测下一跳与基本事实匹配的 \((s, t)\) 对的比例。

#### III-D3 消融研究

为了研究哪些因素有助于下一跳预测，我们进行了一项消融研究，其中仅包含四个节点特征中的每一个，即仅度、仅介数中心性、仅聚类系数和仅度中心性。这让我们更清楚地了解每个节点级特征对下一跳预测的贡献。

#### III-D4 SPF vs GAT 基准测试

我们还想看看 GAT 是否有潜力比 OSPF 使用的最短路径优先算法（SPF）更快，因此我们比较了 Dijkstra 的（类似于 SPF）挂钟时间与 GAT 的单次查询推理时间。我们使用每个图 200 个 \((s, t)\) 对，并按图大小分桶报告中位时间（小型 <50 个节点，中型 50-150，大型 ≥150），计时前有 3 轮预热。

## IV 结果与讨论

### IV-A 合成图与互联网拓扑库图对比

图 2 (https://arxiv.org/html/2608.23917#S4.F2) 将每个合成模型与 Zoo 中位数（归一化为 1.0）进行了比较。SBM 的聚类系数是 Zoo 中位数的五倍，这意味着它比真实世界拓扑更聚集。Waxman 的密度很高（约为 Zoo 中位数的 3.5 倍），表明它比真实集合更密集。WS 模型过度代表了直径和平均最短路径，表示一个更稀疏的训练集。

参考图 2：互联网拓扑库和合成图的雷达图比较
图 3 (https://arxiv.org/html/2608.23917#S4.F3) 中的箱线图显示了合成图与现实 Zoo 集合在六项不同指标上的总体比较：节点数、边数、密度、平均度、聚类系数和平均最短路径。注意，中