Common shortest-path algorithms, such as Dijkstra's (SPF), that OSPF uses, provide exact routing solutions but must be recomputed for each network topology, limiting scalability in dynamic or large-scale networks. This paper proposes the GATNextHop model to determine whether a Graph Neural Network, namely the Graph Attention Network, can approximate shortest paths and generalize across topologies. By training on synthetic graphs and evaluating on real-world Internet Service Provider networks from the Internet Topology Zoo, we aim to benchmark our model's ability to learn routing heuristics that transfer across network structures. Performance will be evaluated in terms of accuracy, inference speed, and generalization, comparing the GNN against Dijkstra's algorithm to quantify trade-offs between learned and classical routing approaches.
Figures & tables
Metric
Median
Min
Max
Std
Node count
25.00
4.00
158.00
25.09
Edge count
31.00
4.00
193.00
30.10
Density
0.09
0.02
1.00
0.13
Avg. degree
2.25
1.60
8.00
0.63
Clustering
0.03
0.00
1.00
0.15
Avg. shortest path
3.17
1.00
13.07
2.06
TABLE I: Summary statistics of 180 Internet Topology Zoo graphs.
Fig. 1: GATNextHop GAT Model Architecture
Fig. 2: Radar comparison of Internet Topology Zoo and synthetic graphs
Fig. 3: Boxplots of graph statistics by dataset (Zoo vs synthetic) for each metric.
Metric
Zoo median
Syn. median
Ratio
Realism
Node count
25.00
19.00
0.76
0.81
Edge count
31.00
21.50
0.69
0.78
Density
0.09
0.12
1.24
0.85
Avg degree
2.25
2.00
0.89
0.65
Clustering coeff.
0.03
0.00
—
0.83
Avg shortest path
3.17
3.16
1.00
0.93
TABLE II: Zoo vs synthetic graph statistics (median and ratio).
Fig. 4: Training and validation loss (left) and accuracy (right) early stopped at epoch 78 on synthetic graphs. Validation accuracy surpasses training accuracy throughout, indicating strong generalization within the synthetic distribution.
Metric
Synthetic Validation
Zoo Testing
Accuracy
0.851
0.842
Number of graphs
200
180
TABLE III: Next-hop classification results. Synthetic vs Zoo.
Features
Epoch Stopped
Syn. Val
Zoo Test
Zoo Loss
Clustering only
37
0.649
0.709
0.569
Degree only
55
0.816
0.811
0.446
Degree centr. only
78
0.824
0.818
0.444
Betweenness only
75
0.857
0.846
0.379
All four
77
0.851
0.842
0.386
TABLE IV: Ablation: effect of individual node features on next-hop classification.
SPF (ms)
GAT (ms)
Speedup
All graphs (n=180)
0.01
0.61
0.02
Small ( n<50 )
0.01
0.58
0.02
Medium ( 50≤n<150 )
0.04
1.43
0.02
Large ( n≥150 )
0.08
2.54
0.03
GAT accuracy (%)
—
84.6
—
TABLE V: SPF (Dijkstra) vs GAT next-hop inference on Topology Zoo.
Fig. 5: SPF vs. GAT inference speed and next-hop accuracy on 180 Internet Topology Zoo graphs.