🤖 machine learning

Temporal Hyperbolic Graph Representation Learning for Scale-Free Internet Routing and Delay Prediction

The paper proposes HERMIT, a hybrid framework that combines hyperbolic temporal graph neural networks with Random Forest regression to effectively model the scale-free Internet topology and significantly improve round-trip time prediction accuracy compared to existing Euclidean and hyperbolic baselines.

Original authors: Yi-Ling Kuo, Hao-Yu Tien, Shih-Yu Tsai

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yi-Ling Kuo, Hao-Yu Tien, Shih-Yu Tsai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the Internet not as a web of cables, but as a giant, living city where millions of roads (data paths) connect millions of buildings (computers). Every time you send a message, it's like a delivery truck trying to get from Point A to Point B. The time it takes for that truck to go there and come back is called RTT (Round-Trip Time).

The problem is that this city is chaotic. Traffic jams appear out of nowhere, new roads open up, and some routes are incredibly fast while others take forever. Predicting exactly how long a trip will take is like trying to guess the weather in a city where the rules of physics change every day.

Here is how the paper "HERMIT" solves this puzzle, explained simply:

1. The Problem: The Wrong Map

Most computer models try to map this Internet city using a flat, 2D sheet of paper (Euclidean space). But the Internet isn't flat; it's like a giant, branching tree or a pyramid with a massive base and a tiny top.

The Analogy: Imagine trying to draw a massive family tree on a flat piece of paper. As the family grows, the branches get so crowded that you have to squish them together, distorting the relationships. To fit everyone, you'd need a huge piece of paper.
The Paper's Insight: The authors say, "Let's stop using flat paper." Instead, they use Hyperbolic Geometry. Think of this like a saddle shape or a pringle chip. On a Pringle, you can fit a huge, branching tree without it getting crowded. This allows the computer to understand the Internet's "hierarchical" structure (big hubs connecting to smaller local networks) much better than flat maps can.

2. The Solution: The "HERMIT" Framework

The authors built a new model called HERMIT. It's a hybrid team of two specialists working together:

Specialist A: The Hyperbolic Time-Traveler (The Encoder)
This part looks at the Internet's map over time. It doesn't just look at where the roads are; it looks at how the roads change.
- The Twist: Previous models only looked at the "nodes" (the cities). HERMIT also looks at the "edges" (the roads themselves). It pays attention to the specific quality of each road: Is it usually fast? Is it shaky? How often is it used?
- The Analogy: Imagine a GPS that doesn't just know the map, but also knows that "Main Street" is usually a smooth ride, while "Back Alley" is full of potholes. It learns these details by "reading" the history of every single road.
Specialist B: The Weather Forecaster (The Random Forest)
Once Specialist A creates a perfect 3D map of the Internet's structure, it hands that map to Specialist B.
- The Job: Specialist B is a "Random Forest," which is like a committee of 120 different decision-makers (trees). They look at the map plus the historical weather reports (past traffic times) to make a final guess.
- Why it works: The "trees" are great at handling messy, unpredictable data (like a sudden traffic jam that makes a trip take 10 seconds instead of 1). They combine the structural map with the raw numbers to make a very safe, accurate prediction.

3. The Training: Learning from the Past

The team trained this model using a massive dataset: 10 years of real Internet data (from 2015 to 2024) collected from probes across the United States.

They cleaned the data to remove broken paths (like a truck that never reached its destination).
They handled the "heavy tails" of the data. In plain English: Most trips are fast (under 200ms), but a few are incredibly slow (seconds). Standard math gets confused by these slow outliers. HERMIT uses a special "logarithmic" trick to flatten these extreme numbers so the model doesn't get distracted by the rare, crazy delays.

4. The Results: Who Won the Race?

The authors tested HERMIT against other smart models and found:

Link Prediction (Guessing new roads): HERMIT was incredibly accurate (over 99% accuracy) at predicting which new connections would appear in the Internet. It was better than previous models because it paid attention to the specific quality of the roads, not just the cities.
RTT Prediction (Guessing travel time): HERMIT beat the standard "Random Forest" model (which only looked at past numbers without the map) by about 6%.
- The Big Win: It was especially good at predicting the long trips. While other models made huge mistakes when traffic was bad, HERMIT stayed steady.

Summary

Think of HERMIT as a super-smart logistics manager.

It uses a special curved map (Hyperbolic space) to understand the complex shape of the Internet.
It studies the history of every single road (Edge features) to know which ones are reliable.
It hands this knowledge to a committee of experts (Random Forest) who combine the map with past traffic data to predict exactly how long a delivery will take.

The paper claims this is a robust way to predict Internet speed and find new connections, making the network faster and more reliable for everyone.

Technical Summary: HERMIT – Temporal Hyperbolic Graph Representation Learning for Scale-Free Internet Routing and Delay Prediction

Problem Statement
Accurately predicting Internet Round-Trip Time (RTT) is essential for routing optimization, Quality of Service (QoS), and traffic engineering. However, RTT prediction faces three primary challenges:

Heavy-Tailed Distributions: RTT data exhibits extreme variability, ranging from sub-millisecond to several seconds, causing traditional Mean Squared Error (MSE)-based regression models to be dominated by outliers and degrade performance on common latency ranges.
Dynamic Topology: RTT is influenced by evolving routing paths, congestion states, and network topology changes, which are difficult to capture with static distance embeddings or conventional regression models.
Structural Mismatch: Most existing Temporal Graph Neural Networks (TGNNs) operate in Euclidean space. This is ill-suited for Internet routing graphs, which possess hierarchical and scale-free structures. Euclidean embeddings often require high dimensions or incur geometric distortion to represent these topologies, whereas hyperbolic geometry naturally accommodates such structures with low distortion in low dimensions.

Methodology: The HERMIT Framework
The authors propose HERMIT (Hyperbolic Edge-aware RTT modeling via Integrated Topology), a hybrid framework designed to jointly perform link prediction and RTT prediction. The architecture integrates a hyperbolic manifold-preserving temporal GNN with a tree-based Random Forest regressor.

Data Preprocessing: The model utilizes a 10-year dataset (2015–2024) from the CAIDA IPv4 Ark project. Raw traceroute logs are cleaned (retaining only "completed" traces), pruned to the top 5% of nodes by degree to focus on the network backbone, and sampled via a rolling weekly strategy (3 days/week) to manage computational load. The resulting data is structured as a sequence of daily weighted graphs with edge features including log-transformed mean RTT, RTT standard deviation, and link weight.
Hyperbolic Temporal Encoder: Building upon the HMPTGN backbone, HERMIT introduces two key enhancements:
1. RTT-Aware Edge Features: Explicit edge features (log-RTT mean, std, and weight) are incorporated to characterize fine-grained link states.
2. Learnable Edge Encoder: A linear transformation followed by a sigmoid activation compresses the 3D edge features into a scalar weight. This acts as an attention mechanism, adaptively weighting edges during message passing to emphasize critical and stable links.
3. Manifold Preservation: The encoder performs message passing directly on the Poincaré ball manifold (curvature $c=1.0$ ) using Möbius addition and Poincaré linear transformations, avoiding the geometric distortion associated with tangent space projections used in models like HTGN.
Joint Prediction Tasks:
- Link Prediction: The model computes the Poincaré squared distance between node embeddings and maps it to link existence probabilities using a Fermi-Dirac activation function.
- RTT Prediction: The hyperbolic node embeddings ( $z_u, z_v$ ) are concatenated with historical RTT statistics ( $f_u, f_v$ ) for the edge endpoints. This combined feature vector is fed into a Random Forest regressor to predict the RTT. The model is trained on log-transformed and min-max normalized RTT values to handle heavy tails, with predictions inverse-transformed to the millisecond scale for evaluation.
Training Objective: The model is optimized using a combined loss function $L = L_{link} + \lambda L_{RTT}$ , where $L_{link}$ is binary cross-entropy and $L_{RTT}$ is MSE on normalized values. The weighting hyperparameter $\lambda$ is set to 10.

Key Contributions

Reproducible Pipeline: A data preprocessing pipeline that transforms raw CAIDA Ark logs into a sequence of daily weighted graphs with edge-level RTT statistics, addressing data inconsistencies common in traceroute measurements.
Hybrid Architecture (HERMIT): A novel framework combining a hyperbolic temporal GNN with a Random Forest regressor. It is evaluated on a massive, real-world dataset spanning a decade.
Performance Improvements:
- RTT Prediction: HERMIT achieves a 6% improvement in RMSE compared to a strong Random Forest baseline using only historical statistics. Specifically, it improves RMSE by 6.4% on existing links and 2.3% on new appearing links.
- Link Prediction: By incorporating explicit edge features and a learnable edge encoder, HERMIT outperforms prior hyperbolic TGNN baselines (HMPTGN and HTGN), achieving AUC and AP scores above 0.99 on both existing and new links.
Scalability: The approach demonstrates that 16-dimensional hyperbolic embeddings can efficiently encode hierarchical routing structures, offering a scalable solution for large-scale networks.

Results and Significance
The paper claims that HERMIT provides a robust and scalable solution for RTT prediction under real-world, heavy-tailed network latency conditions. The experimental results on the CAIDA dataset demonstrate that:

Handling Heavy Tails: The hybrid design effectively mitigates large errors on heavy-tailed samples, outperforming models that rely solely on historical statistics or Euclidean embeddings.
Generalization: The model shows strong generalization to previously unseen connections (new links), suggesting that the learned hyperbolic temporal representations capture latent hierarchical structures that aid in inferring emerging network connections.
Synergy: The combination of macro-level network organization (captured by the hyperbolic encoder) and micro-level feature interactions (exploited by the Random Forest) yields more accurate and robust predictions than either approach alone.

The authors conclude that incorporating RTT-aware edge modeling into hyperbolic temporal graphs significantly enhances both link and latency prediction, offering a practical pathway for latency-aware traffic engineering and proactive performance monitoring.