PaperlayerView exact revision on arXiv

Source-linked AI summary

GATNextHop: A GAT for Shortest Path Routing with Cross-Topology Generalization

Chia-Hong Chou, Katerina Potika

arXiv:2608.23917v1cs.LG

TL;DR

Dynamic network topologies make exact shortest-path routing costly because Dijkstra’s algorithm must be rerun for each topology. The paper develops GATNextHop, trains it on synthetic graphs, and evaluates transfer to unseen real-world ISP topologies, achieving 84.2% accuracy and 84.6% with betweenness alone.

  • Problem

    Dynamic topologies make efficient optimal routing challenging because exact OSPF/SPF routing must be recomputed for each topology.

  • Method

    GATNextHop uses a Graph Attention Network with structural node features and edge weights, deriving next-hop labels from Dijkstra-based shortest-path ground truth and transferring from synthetic to ISP topologies.

  • Results

    84.2% accuracy was achieved on unseen Internet Topology Zoo topologies, increasing to 84.6% when betweenness centrality was used alone.

  • Takeaways & Limitations

    The results demonstrate potential for GATs to transfer structural knowledge from synthetic graphs to shortest-path prediction in real-world ISP networks.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper investigates whether a GAT can approximate shortest-path next hops and transfer structural knowledge from synthetic graphs to unseen ISP topologies. It contrasts this learned approach with exact but repeatedly recomputed shortest-path routing.

  • Motivation: Dynamic topologies make exact OSPF/SPF routing difficult to maintain because Dijkstra’s algorithm must be rerun for each topology.The stated focus is generalization under uncertainty, including dynamic and partial graphs, rather than computational competition.
  • Motivation: Prior work suggests GNN-based routing can adapt to changing or complex environments, motivating investigation of a Graph Attention Network for next-hop prediction.The paper specifically follows evidence that GNN routing methods can outperform Dijkstra’s in dynamic or complex settings.
  • Approach: The study analyzes Internet Topology Zoo networks, curates 1,000 structurally similar synthetic graphs, and trains a GAT using node and edge features.The synthetic data are split into training and validation sets using an 80–20 split.
  • Contributions: GATNextHop achieves 85.1% accuracy on synthetic graphs and 84.2% on unseen Internet Topology Zoo topologies.The study also benchmarks SPF and GAT inference speed across graph sizes using 180 real-world ISP topologies.

II. RELATED WORK

Related work applies GNNs to routing optimization, prediction, and reinforcement-learning policies for dynamic or unseen topologies. This paper differentiates its approach by using GAT attention to assign different importance to neighbors, while acknowledging a static-topology scope.

  • Prior GNN routing work: Earlier studies combined GNNs with deep reinforcement learning to learn routing policies that generalize to unseen topologies.Other systems used GNNs to predict path delay and loss or improve load-balanced routing in ISP networks.
  • Positioning: Most prior methods use GCNs or MPNNs with uniform or degree-normalized neighbor weights.This provides the comparison point for the paper’s use of neighbor-specific attention.
  • Positioning: GAT introduces masked self-attention, allowing the model to assign different importance to each neighbor when encoding structural patterns.The paper links this design to the next-hop task, which requires distinguishing among candidate neighbors.
  • Scope: The authors limit the present use case to static environments and do not analyze dynamic topology configurations.The study instead tests transfer from seen synthetic structures to route prediction on unseen topologies.
  • Evaluation setting: The evaluation targets 180 processed Internet Topology Zoo graphs and synthetic training graphs calibrated to their observed structural statistics.The Zoo graphs are converted to undirected simple graphs and reduced to their largest connected components before analysis.

2) Weight Assignment:

Because the Internet Topology Zoo lacks edge weights, the study assigns random weights before computing shortest-path ground truth. Synthetic graphs are then calibrated to Zoo statistics for training.

  • 2) Weight Assignment:: Each edge in the real-world graphs receives a uniform random real-valued weight from 1 to 100.The weights use 64-bit precision because the source graphs do not provide edge weights.
  • 2) Weight Assignment:: All-pairs shortest paths are computed with Dijkstra and stored as ground truth for deriving next-hop labels.A neighbor is labeled correct when its edge weight plus its remaining distance equals the source-to-destination shortest-path distance.
  • 2) Weight Assignment:: Statistics from 180 processed Internet Topology Zoo graphs are summarized by medians to define targets for synthetic graph generation.The profiling includes graph characteristics used to shape the synthetic training set.
  • 2) Weight Assignment:: The synthetic dataset contains 1,000 graphs generated from ER, BA, WS, SBM, and Waxman models calibrated to Zoo medians.The parameters were selected to make the synthetic graphs resemble the Zoo set, and the graphs were split into 800 training and 200 validation examples.

C. GNN Model Design

GATNextHop formulates routing as predicting the neighbor that lies on the shortest path from a source to a destination. It uses attention to prioritize structurally relevant neighbors.

  • Task formulation: Given graph G, source s, and destination t, the model classifies which neighbor w of s is the shortest-path next hop.The candidate set is N(s), and the ground-truth condition is dist(s,t) = weight(s,w) + dist(w,t), verified with tolerance 1e-5.
  • Model choice: GATNextHop uses Graph Attention Network attention to upweight neighbors oriented toward shortest paths and downweight other neighbors.This neighbor-dependent weighting matches the adaptive decision required by next-hop selection.

2) Feature Selection:

GATNextHop encodes graph structure with normalized node and edge features, then scores candidate neighbors to predict the next hop.

  • Feature Selection: The model uses four normalized node features: degree, weighted betweenness centrality, clustering coefficient, and degree centrality.Each feature is scaled to [0, 1] by dividing by its maximum value.
  • Feature Selection: A one-dimensional edge feature represents the edge weight used alongside node features.
  • Architecture: Three GATConv layers use 64 hidden units and four attention heads, producing 256-dimensional outputs per layer.
  • Architecture: Edge-aware attention uses edge_dim=1 with self-loops, ReLU activation, and 0.1 dropout after each layer.
  • Prediction Head: For each source, destination, and candidate neighbor, concatenated embeddings are passed through a two-layer MLP to produce a candidate score.The concatenated embedding has dimension 768, and invalid padded candidates are masked before softmax.
  • Optimization: The model is trained with cross-entropy over candidate logits.

4) Training Details:

Training uses synthetic graphs with validation monitoring and evaluates transfer to unseen Internet Topology Zoo graphs.

  • Training Details: Training used Adam with LR = 1e−3, ReduceLROnPlateau scheduling, early stopping, and a batch size of 16 graphs.The scheduler halves the learning rate after five validation-accuracy patience epochs; training ran for up to 100 epochs.
  • Dataset Characterization: Synthetic graphs are compared with Zoo graphs using eight structural metrics, median ratios, and a realism score based on 1 − D.D is the Kolmogorov-Smirnov distance between the Zoo and synthetic distributions, so realism ranges from 0.0 to 1.0.
  • Data Split: The dataset contains 1,000 synthetic graphs, split into 800 training graphs and 200 validation graphs.The model never sees Internet Topology Zoo graphs during training.

3) Ablation Study:

The comparison examines feature contributions and synthetic-to-real graph similarity, identifying both matched structural properties and a realism-related limitation.

  • Ablation Study: The ablation study evaluates degree-only, betweenness-only, clustering-coefficient-only, and degree-centrality-only feature sets.Each variant includes only one of the four node features to isolate its contribution to next-hop prediction.
  • Inference Speed: The timing comparison measures Dijkstra wall-clock time against GAT single-query inference across small, medium, and large graph-size buckets.Median timing uses 200 source-destination pairs per graph and three warm-up rounds.
  • Synthetic–Zoo Comparison: The SBM model has a clustering coefficient five times the Zoo median, while Waxman has density around 3.5 times the Zoo median.The WS model over-represents diameter and average shortest path, producing a sparser training set.
  • Synthetic–Zoo Comparison: Synthetic and Zoo graph medians are similar, but their outliers differ across the plotted statistics.This comparison is used to test generalization from synthetic training graphs to real-data evaluation.
  • Synthetic–Zoo Comparison: Diameter and average shortest path each have a 1.00 ratio, with realism scores of 0.96 and 0.93, respectively.Edge count, assortativity, and average degree show larger mismatches; the passage links lower realism to potentially weaker clustering-coefficient ablation results.
  • Limitation: Better realism across the graph metrics could produce stronger ablation results for different node-level features.

B. Model Evaluation

GATNextHop maintains similar next-hop accuracy when transferred from synthetic validation graphs to unseen Internet Topology Zoo topologies. Ablation results indicate that betweenness centrality is the most informative individual node feature.

  • Validation accuracy remained higher than training accuracy throughout training, with early stopping at epoch 78 and no observed overfitting.The passage attributes lower validation loss to regularization.
  • 85.1% synthetic validation accuracy compared with 84.2% on the Zoo test set indicates a small cross-topology performance gap.The model was evaluated on unseen Internet Topology Zoo topologies.
  • Betweenness centrality was the most helpful individual node feature for predicting the next hop.It measures how often a node lies on shortest paths, matching the next-hop task.
  • 84.6% Zoo-test accuracy using betweenness alone exceeded the full-feature model’s 84.2%, suggesting the other features add little or may introduce noise.The comparison concerns degree, degree centrality, and clustering coefficient as additional features.

D. SPF vs GAT benchmark

The benchmark compares single-source Dijkstra/SPF wall-clock time with GAT single-query inference across 180 Internet Topology Zoo graphs. GAT is slower for a single query, but the gap narrows as graph size increases and repeated queries can amortize its fixed topology cost.

  • Across 180 graphs, SPF had a median inference time of 0.01 ms, while GAT took 0.61 ms for a single query.The measurements were collected on a MacBook Pro M2 Max CPU.
  • Dijkstra’s O((V + E) log V) cost increases with graph size, whereas GAT has a comparatively constant inference overhead.This overhead is a bottleneck for small graphs.
  • Speedup increased from 0.02 for graphs with n < 50 to 0.03 as graph size grew, indicating a narrowing performance gap.Speedup is defined as SPF time divided by GAT time; values below 1.0 mean GAT is slower.
  • GAT’s topology encoding can be reused across queries, leaving only another MLP forward pass for each additional source–destination pair.This can amortize the fixed inference cost over many queries on the same topology.

V. CONCLUSION AND FUTURE WORK

GATNextHop transfers routing heuristics from synthetic graphs to real-world ISP topologies, achieving about 84% next-hop accuracy. However, Dijkstra remains faster for static single-source routing, while several larger-scale and dynamic settings remain future work.

  • Betweenness centrality was the most effective node-level feature for shortest-path next-hop prediction.
  • Dijkstra was 50 times faster than GAT inference for single-source queries.
  • In static settings with the graph loaded in memory, Dijkstra remains faster and GAT overhead is not justified.
  • Future work includes evaluating topology changes and failures, larger-network adaptation, amortized latency with cached embeddings, and comparisons with other GNN paradigms.
Loading 2608.23917v1…