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

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

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

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

distributedsystems protocols

networking, internet, protocols, distributed systems

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

Yi-Ling Kuo1 , Hao-Yu Tien1 , Shih-Yu Tsai1,* Department of Information Management and Finance, National Yang Ming Chiao Tung University, Hsinchu 30010, Taiwan

arXiv:2605.28155v1 [cs.LG] 27 May 2026

Emails: [email protected] (Y.L. Kuo), [email protected] (H.Y. Tien), [email protected] (S.Y. Tsai) *Corresponding author

Abstract— Predicting Internet round-trip time (RTT) is critical for routing optimization, quality-of-service (QoS) provisioning, and traffic engineering in large-scale networks, yet it remains challenging because RTT depends on a long-term history, follows complex routing dynamics, and exhibits heavy-tailed latency distributions. While Temporal Graph Neural Networks (TGNNs) [1]–[9] have shown promise for modeling evolving network topologies, most existing approaches operate in Euclidean space, which is not well-suited for representing the hierarchical and scale-free structure of Internet routing graphs. In contrast, hyperbolic geometry provides a natural embedding space for such topologies with low distortion in low dimensions [10]. In this work, we propose HERMIT(Hyperbolic Edge-aware RTT modeling via Integrated Topology), a hybrid framework that integrates a hyperbolic manifold-preserving temporal GNN with a tree-based Random Forest regressor for joint link prediction and RTT prediction. Building on HMPTGN [8] as the backbone, we further enhance its temporal graph encoder by introducing RTTaware edge features and a learnable edge encoder, allowing more precise modeling of the link states and evolving routing behavior. We combine the resulting hyperbolic node representations with historical RTT statistics in a Random Forest regressor to model non-linear and heavy-tailed latency patterns. We evaluated HERMIT on a large-scale real Internet dataset spanning 10 years from 2015 to 2024. Our experiments show that HERMIT consistently outperforms a strong Random Forest baseline [11] based solely on historical RTT statistics, achieving a 6% improvement in RMSE and substantially mitigating large errors on heavy-tailed samples. Moreover, HERMIT, with its hyperbolic temporal representations enhanced by RTT-aware edge features, achieves better link prediction than prior hyperbolic TGNN models, including HMPTGN [8] and HTGN [6], highlighting the effectiveness of incorporating RTT-aware edge modeling. Our results suggest that combining hyperbolic temporal graph representations with tree-based regression provides a robust and scalable solution for RTT prediction in the real-world Internet topologies. Index Terms—Hyperbolic Temporal Graph Neural Network, Round-Trip Time prediction, Link prediction, Random Forest, Temporal Graph, Hyperbolic space

I. I NTRODUCTION Round-trip time (RTT) is a fundamental metric for characterizing network performance, measuring the time required for a packet to travel from a source node to a destination and back. RTT directly impacts multiple aspects of network operation: from a user experience perspective, excessive RTT

leads to slow page loads, video conferencing lag, and online gaming delays, severely degrading the usability of interactive applications; from a network engineering perspective, ISPs leverage RTT data to identify high-utilization paths during peak hours, informing decisions on bandwidth upgrades, peering adjustments, or traffic engineering strategies to redistribute load and optimize overall network performance. Accurate RTT prediction is therefore critical for Quality of Service (QoS) guarantees—for instance, CDNs require predictive low-latency path selection, and cloud services need dynamic resource allocation—yet existing methods struggle to maintain stable prediction accuracy under both normal and abnormal RTT conditions. We are going to design a model that can jointly address link prediction and RTT prediction. However, RTT modeling and prediction face fundamental challenges. Prior studies have shown that RTT measurements in the Internet exhibit high variability and heavy-tailed distributions [12], [13]. Our dataset aligns with these observations: RTT values span submillisecond low-latency links to extreme cases approaching 10 seconds. This extreme distributional characteristic introduces two challenges: First, heavy tails cause traditional mean squared error (MSE)-based regression models to be dominated by outliers, degrading prediction accuracy in the common RTT range. Second, RTT is influenced by routing dynamics, congestion states, and topology evolution, exhibiting highly nonlinear and time-varying behavior that is difficult to capture with conventional regression models and static-distance embedding approaches. To address these challenges, early RTT prediction methods primarily relied on geometric coordinate systems, such as the Vivaldi algorithm [14], which embeds nodes into coordinate spaces to approximate latencies, or latent factorization techniques like DMFSGD [15], which captures implicit node-pair relationships through matrix decomposition. These approaches can capture coarse spatial relationships, but they are designed for static or quasi-static environments and struggle to handle dynamic routing changes, transient congestion, and highly non-linear latency dynamics. Recently, machine learning-based approaches have emerged, including a sequence-based model, which is an LSTM architecture that treats dynamic RTT as a time series [16], and a tree-based ensemble model, Random Forest [11].

These methods improve regression accuracy by capturing temporal dependencies as well as non-linear relationships and interactions among handcrafted network features (e.g., historical RTT statistics, path characteristics, and traffic-related attributes). However, they typically treat RTT prediction as a tabular regression problem (i.e., predicting a numerical value given a set of attributes/features), neglecting the underlying network topology; the RTT between the sender nodes and the receiver nodes is actually affected by structural factors such as routing paths, congestion status of intermediate nodes, and topology evolution. This disregard for graph structure limits the models’ ability to generalize to the scenarios of routing changes and emerging connections. In order to effectively utilize this topology information, Jaeger et al. [17] modeled Transmission Control Protocol (TCP) behavior using Graph Neural Networks (GNNs), encoding the network topology as a graph and predicting throughput and RTT simultaneously. Their experimental results show that GNN can demonstrate better generalization capability across different network topologies and TCP congestion control algorithms, and can effectively learn the relationships between TCP performance metrics such as RTT and throughput. However, the above methods mostly treat the network as a static graph and do not explicitly capture how network states evolve over time. Temporal Graph Neural Networks (TGNNs) [1]–[9] have recently attracted increasing attention because they are capable of modeling the temporal dynamics of network performance with better quality. However, we observe that most existing temporal graph neural networks used for network modeling are still designed and implemented in Euclidean space [1]– [5], whereas architectures specifically designed for hyperbolic geometry, which is better suited to represent the topology of the Internet [10], [18]. The Internet topology exhibits both scale-free degree distributions and hierarchical structure. When embedding such graphs in Euclidean space, it often requires high embedding dimensionality or incurs geometric distortion to accommodate the large number of lower-layer nodes. The volume of Euclidean space grows only polynomially with the radius, making it difficult to preserve distances and adjacency relations of large-scale hierarchical networks in low dimensions. With exponential volume growth of hyperbolic geometry, lowdimensional embeddings can naturally accommodate treelike and scale-free structures whose number of nodes grows exponentially with depth [6], [18]. Prior work [7], [19], [20] has shown that embedding hierarchical graphs in hyperbolic space can significantly reduce distortion and preserve both hierarchical relations and long-range relative positions between nodes. Thus, designing temporal graph neural networks in hyperbolic space is more suitable for hierarchical and scalefree network data, such as Internet routing graphs, providing more stable and expressive representations than traditional Euclidean TGNNs in the same dimension. With these observations, in order to get better accuracy and robustness performance on link connection prediction and the corresponding RTT values estimate, we proposed a novel hybrid architecture, called HERMIT, that combines a manifoldpreserving hyperbolic temporal GNN with edge-level feature and a tree-based regression model. Building on HMPTGN [8],

we introduce two key enhancements to the graph encoding module. First, we incorporate explicit edge features that fuse RTT statistics to characterize fine-grained link states. Second, we design a learnable edge encoder that adaptively assigns weights to different links during message passing, thereby emphasizing edges that are more critical, stable, and frequently observed in the topology. With these extensions, our model learns node embeddings that more finely reflect link states and path behavior, and further improves link prediction performance over HMPTGN [8] and HTGN [6]. For the RTT prediction task, we combine information from the learned graph structure and historical RTT statistics. Specifically, the hyperbolic embeddings generated by our hyperbolic temporal encoder are treated as topological features. They are directly concatenated with historical RTT statistics and then fed into a Random Forest regressor to produce RTT estimates. Compared to regression models trained only on historical RTT statistics [11], this hybrid feature design enables the regressor to exploit topology-aware information from hyperbolic graph embeddings, yielding better overall performance in RTT prediction. The hyperbolic temporal encoder captures macro-level network organizations, while the Random Forest exploits micro-level feature interactions, resulting in more accurate and robust RTT predictions than either approach alone. Our main contributions are summarized as follows: We design a reproducible data preprocessing pipeline that transforms raw CAIDA Ark traceroute logs [21] into a sequence of daily weighted graphs with edge-level RTT statistics. The pipeline addresses data inconsistencies and incomplete observations commonly observed in Internet traceroute measurements [22]. • We propose HERMIT, a sate-of the-art RTT prediction framework that combines a hyperbolic manifoldpreserving temporal GNN with a tree-based regressor. We demonstrate that it can handle massive Internet data by evaluating its RTT prediction performace on a largescale, real-world dataset spanning ten years (2015 - 2024) of U.S. Internet measurements from the CAIDA IPv4 Ark project [21]. • For RTT prediction, our model HERMIT combines hyperbolic topology-aware embeddings with historical RTT information and achieves significant improvements in RMSE by 6% compared to a Random Forest model [11] that uses only historical RTT statistics. Specifically, it is by 6.4% on existing links and by 2.3% on new appearing links. • For link prediction, our model (HERMIT) that incorporates explicit edge features and a learnable edge encoder consistently outperforms prior hyperbolic GNN baselines including HMPTGN [8] and HTGN [6], on both existing and new links, achieving AUC and AP scores above 0.99 and demonstrating the effectiveness of the learned hyperbolic temporal representations.

•

Overall, our results demonstrate that combining hyperbolic temporal graph representations with Random Forest regression provides a robust and scalable solution for RTT prediction under real-world, heavy-tailed network latency conditions.

The paper is structured as follows. Section II introduces the problem and introduces the dynamic graph setting and learning tasks. Section III reviews related work. Section IV describes the dataset and preprocessing. Section V presents the proposed HERMIT framework. Section VI details the experimental setup, including dataset splits, baselines, and evaluation metrics. Section VII reports the empirical results on link prediction and RTT prediction. Section VIII discusses the findings. Section IX concludes the paper.

directed edge (u, v) ∈ Et represents a routing connection from u to v at time t. The feature vector for each edge (u, v) ∈ Et is denoted by xuv,t ∈ R3 , which includes the log-transformed mean RTT, log-transformed RTT standard deviation, and the link weight.

C. Link prediction II. N OTATION , P ROBLEM F ORMULATION , AND P RELIMINARIES

The link prediction task aims to infer which node pairs are likely to be connected in the next snapshot based on historical graph structure and edge attributes. Formally, given a sequence of past snapshots {G1 , G2 , . . . , Gt }, the goal is to estimate, for each candidate node pair (u, v) in Vt × Vt where u ̸= v, the probability that an edge euv exists in the future snapshot Gt+1 , i.e., p̂uv,t+1 = Pr (u, v) ∈ Et+1 G1 , . . . , Gt .

In this section, we formally define the dynamic graph setting that is considered and introduce the learning tasks of interest. Specifically, we first describe the representation of the Internet routing network as a sequence of time-ordered graph snapshots with associated edge attributes. We then formulate three core tasks: (1) link prediction, which estimates the likelihood of future connections; (2) new link prediction, which focuses on forecasting previously unseen routing relationships; and (3) RTT prediction, which predicts the future continuous This formulation evaluates the model on all edges that appear in RTT values of network links. These tasks together enable Gt+1 , including both edges that persist from earlier snapshots comprehensive modeling of both structural dynamics and and newly formed connections, providing a measure of the model’s overall predictive capability across the entire network latency evolution in time-varying Internet graphs. topology. A. Notation Scalars (e.g., the time index t, an RTT value y) are denoted by regular letters, and vectors by boldface lowercase letters (e.g., z). A hat indicates a predicted or estimated quantity, for example ŷ denotes the predicted RTT value corresponding to the true RTT value y. For a node u at time t, we write zu (t) for its hyperbolic node embedding at that time, that lies in a d-dimensional hyperbolic space (e.g., the Poincaré ball model), and the detailed hyperbolic configuration setting will be introduced in Section VI.We also use fu and fv to denote the historical RTT feature vectors of nodes u and v, respectively.

D. New Link Prediction New link prediction focuses on edges that appear for the first time in Gt+1 . We define the set of newly formed edges as new new Et+1 = Et+1 \ ∪ti=1 Ei . For each (u, v) ∈ Et+1 , we estimate: p̂new / Et , G1 , . . . , Gt . uv,t+1 = Pr (u, v) ∈ Et+1 (u, v) ∈ This formulation measures the model’s generalization ability to predict emerging connections, rather than memorize recurring ones.

B. Definition of Dynamic Graph

E. RTT prediction

A dynamic graph is a graph whose structure and attributes evolve over time. In our work, we adopt a discrete-time snapshot formulation, where the dynamic graph is represented as a sequence of graph snapshots {G1 , G2 , . . . , GT }. Each snapshot at time t

RTT prediction aims to predict a real-valued RTT for a given network edge. Given past snapshots {G1 , G2 , . . . , Gt } and a target node pair (u, v), the goal is to estimate the RTT value in the next snapshot Gt+1 , denoted by

Gt = (Vt , Et , Xt ) consists of a set of nodes Vt , a set of directed edges Et ⊆ Vt × Vt , and associated edge features Xt . In particular, Xt contains link-level measurements (e.g., RTT and other metrics) observed at time t for every edge in Et , so that each snapshot represents the Internet routing topology together with RTT and related link-level metrics collected during a given time window. In our setting, both the edge set Et and the edge features Xt may change over time as routes appear, disappear, or vary in performance, and the node set Vt can also differ across snapshots. For any two distinct nodes u, v ∈ Vt with u ̸= v, a

ŷuv,t+1 , capturing the conditional expectation of RTT given the historical graph and measurements. This task models the temporal dynamics of latency on both existing and newly appearing routing links. III. R ELATED W ORK This section reviews the evolution of two distinct research domains, dynamic graph representation learning and network latency prediction, that form the foundation of our work.

fully exploit the properties of hyperbolic geometry [8], [28]. To address this limitation, Le et al. proposed HyDynamic graph representation learning [23], [24] focuses perbolic Manifold-Preserving Temporal Graph Networks on modeling networks that evolve over time by learning (HMPTGN) [8] in 2024, which perform message passing embeddings for nodes or edges. Given a sequence of graph directly on the hyperbolic manifold. By avoiding intermediate snapshots, the objective is to capture both the structural patterns projections to tangent space, HMPTGN reduces geometric and their temporal changes, enabling the learned representations distortion and provides a more faithful representation of spatioto be used in downstream tasks such as link prediction and temporal dependencies in hierarchical networks. RTT prediction. Early approaches treated dynamic graphs as a Building upon this line of work, our approach further extends sequence of independent static snapshots and learned Euclidean hyperbolic temporal graph modeling toward Internet routing embeddings for each snapshot separately. In 2014, Perozzi et al. topologies and RTT prediction tasks. proposed DeepWalk [25] ,which introduced random-walk-based representation learning, which was later extended in 2017 by GraphSAGE [26] proposed by Hamilton et al., to neighborhood B. Network Latency and RTT Prediction aggregation methods. These methods were applied to each timeClassical TCP packet measurement implementation methods stamped graph to learn node embeddings for temporal link can be dated back to the 1980s, Jacobson estimated RTT using prediction. While these snapshot-based Euclidean models are the Jacobson-style exponentially weighted moving average simple and scalable, they often overlook temporal dependencies (EWMA) [29]. In the early 2000s, RTT prediction methods and smooth temporal transitions. primarily relied on Euclidean coordinate systems [14] or latent As temporal modeling became more important in the early factorization techniques [15], which capture coarse spatial 2020s, prior work incorporated explicit temporal modeling into relationships (i.e., approximate distances between network Euclidean embedding frameworks [1], [3]. In particular, as nodes). However, these approaches struggle to model the nonsurveyed in [1], early approaches leveraged dynamic matrix linear and transient variations that characterize modern internet factorization and recurrent architectures (e.g., RNNs and latency dynamics. GRUs) to enforce temporal consistency in node representations. Motivated by these limitations, data-driven deep learning Building on these ideas, representative dynamic GNNs such methods were introduced to capture temporal patterns in RTT as EvolveGCN [4], TGAT [27], and Roland [2] combine sequences. In 2019, Hagos et al. [16] proposed an LSTMgraph neural networks with recurrent or attention-based mech- based dynamic passive RTT prediction model for TCP and anisms to model structural and temporal dependencies. On showed that they can closely track end-to-end RTT in real the other hand, event-based methods model dynamic graphs time, achieving low prediction error in their experimental TCP as continuous-time interaction streams. In 2020, Rossi et traffic scenarios. al. proposed Temporal Graph Networks (TGN) [3] update Recent work on RTT prediction using classical machine node embeddings upon each observed event, providing finer learning models highlights tree-based ensembles as strong temporal resolution and strong performance on dynamic link baseline models. In particular, in 2025, Stepanov et al. [11] prediction. However, these methods are often computationally empirically demonstrate that Random Forests outperform expensive for long-term, large-scale data, making snapshot- regularized linear models (e.g., ElasticNet [30]), Jacobson’s based approaches more suitable for our setting. EWMA-based RTT estimator, and recurrent neural networks Despite these advances, Euclidean embeddings struggle (RNN, LSTM, GRU) in terms of MSE, MAE, and MAPE to represent networks with strong hierarchical or tree-like across diverse traffic scenarios, including heavy-tailed RTT structures, such as Internet routing topologies, often leading to distributions. distorted distances or requiring high-dimensional representaHowever, these sequence-based models remain constrained tions. This limitation has motivated the adoption of hyperbolic due to their end-to-end formulation. Specifically, treating RTT geometry, which can embed such structures more effectively prediction as an isolated temporal regression task means these with lower dimensionality while preserving hierarchical rela- models ignore how the underlying network topology and tionships [6], [7]. routing paths influence latency. Existing approaches partially Building on these insights, Yang et al. introduced Hyperbolic address these aspects but remain incomplete. Hyperbolic Temporal Graph Networks (HTGN) [28] in 2021, one of temporal GNNs (e.g., HTGN [28] and HMPTGN [8]) capture the first frameworks to incorporate hyperbolic geometry into hierarchical structure and dynamic connectivity, yet do not temporal graph modeling. HTGN maps temporal graphs into explicitly model fine-grained RTT variations. On the other hand, a hyperbolic latent space and combines hyperbolic graph state-of-the-art RTT predictors (e.g., sequence models [16] and neural networks with hyperbolic recurrent units to capture tree-based ensembles [11]) focus on temporal patterns while both temporal dynamics and underlying hierarchical structures, overlooking the underlying network geometry. demonstrating strong performance on temporal link prediction Therefore, it motivates us to propose the HERMIT frametasks. work, which bridges hyperbolic graph learning and latency However, HTGN still relies on operations in the tangent (Eu- prediction. By jointly modeling topological evolution and clidean) space, requiring frequent mappings between Euclidean temporal delay dynamics on the hyperbolic manifold, HERMIT and hyperbolic spaces. This back-and-forth transformation can leverages the geometric hierarchy of Internet networks to introduce geometric distortion and limit the model’s ability to produce more accurate and reliable RTT estimates. A. Dynamic Graph Representation Learning

IV. DATASET In this section, we show how we create our dataset. The utilized dataset originates from the CAIDA IPv4 Ark Project [21], specifically from the probe data operated by Team-1. The temporal scope of the dataset is from 2015 to 2024, focusing primarily on probing activities within the United States. The raw dataset comprises active traceroute measurements stored in the binary .warts format. In order to analyze, we parse the traces and convert them into a JSON file to facilitate feature extraction and temporal graph construction. The parsed dataset contains various attributes for each trace path from a source probe (src) to a destination address (dst). In fact, we only care about key attributes for our analysis, as shown in Table I. The remaining extracted attributes can be classified into two categories: metadata and topology data. Metadata includes start and stop_reason. The start field records the precise timestamp of when each traceroute probe is initiated, enabling temporal alignment across measurements. The stop_reason (e.g., COMPLETED, LOOP, UNREACH) indicates the termination status of each trace. Topology data includes hop_count and the hops array. The hop_count records the total number of hops traversed in the path. The hops array contains an ordered sequence of intermediate routers traversed during the traceroute process. Each element in the hops array represents a hop, and in each hop, it has the visited router’s IP address (addr) and the corresponding roundtrip time (rtt). Thereby, it provides the essential information for constructing nodes, edges, and latency measurements in the network graph. Importantly, this hop sequence is inherently ordered, reflecting the step-by-step propagation of packets along the network path from source to destination. TABLE I D ESCRIPTION OF K EY F IELDS IN THE CAIDA A RK DATASET

most connected nodes. Specifically, the top 5% of nodes ranked by degree were selected, which collectively accounted for approximately 90% of the overall connection volume. This pruning step preserves the core backbone structure while discarding low-active nodes that contribute little to the aggregate dynamics. Even after this pruning reduction, our temporal dataset led to excessive computational overhead and GPU memory exhaustion during model training (we use a NVIDIA GeForce RTX 4090 GPU with 24 GB of memory) In order to maintain computational feasibility and temporal variability of the dataset at the same time, we adopt a rolling weekly sampling strategy. Instead of using all the daily data, we sample three days per week. It contains two weekdays and one weekend day for each week. The specific sampling days were alternated based on the week number. That is Monday, Wednesday, and Saturday in odd-numbered weeks; Tuesday, Friday, and Sunday in evennumbered weeks. This provides a balanced and reasonable subset that covers both typical weekday behavior and weekend traffic patterns. This scheme reduces the original dataset, which consists of 3,415 temporal snapshots to 1,456 snapshots (a 42.6% reduction), while still maintaining both consistent weekly coverage and representative diurnal traffic patterns. After preprocessing and aggregation, we get our final input data structured into six key fields as detailed in Table II. The data encapsulates traceroute measurements collected within the United States from 2015 to 2024, capturing the daily dynamics of network-level interactions, as detailed in Table II.

TABLE II D ESCRIPTION OF THE P REPROCESSED DATASET F IELDS Field

Type

Description Anonymized ID representing the starting node of a network hop. Anonymized ID representing the destination node of the hop. Discrete timestamp index in the sequence of sampled snapshots. Aggregated frequency count of the link observed on that given day. Average Round-Trip Time (ms) of the link for the day, indicating latency. Standard deviation of RTT (ms), capturing the stability of the link.

Field Name

Data Type

Description

source

Integer

src / dst

String

The IPv4 addresses of the source probe and the destination target.

target

Integer

start

Object

Contains the measurement timestamp (sec), used to construct temporal graph snapshots.

time

Integer

weight

Integer

avg_rtt

Float

std_rtt

Float

stop_reason

String

Indicates the termination status of the trace (e.g., COMPLETED, LOOP, UNREACH).

hop_count

Integer

The total number of hops traversed in the path.

hops

Array

A sequential list of intermediate routers. Each element contains: • addr: Router IP address (Node). • rtt: Round-Trip Time.

Next, we clean and organize the raw dataset into temporal graphs for model training and evaluation. To handle the large volume of raw data, an initial preprocessing step was applied to remove incomplete traces. We only retain measurement of probes whose stop_reason is labeled as ”completed”, ensuring that the inferred network topology data is based on valid paths where the traceroute reached its destination. To mitigate the highly skewed degree distribution characteristic of network topologies, the analysis was restricted to the

We construct a sequence of temporal graphs {Gt }Tt=1 , where each daily snapshot Gt = (Vt , Et , Xt ) represents the Internet topology and latency statistics on day t. For each day t, the node set Vt consists of all source and target IDs observed on that day, and the edge set Et contains a directed edge (u, v) if at least one measurement with source = u, target = v, and time = t is observed. The edge attributes Xt include the aggregated frequency weight, the daily average RTT avg_rtt, and the RTT standard deviation std_rtt. The model takes as input a sequence of daily snapshots {G1 . . . , GT }, where each Gt encodes both the routing topology and historical RTT statistics for day t.

Fig. 1. Overview of the proposed HERMIT architecture. Based on HMPTGN, our hyperbolic temporal encoder incorporates edge-level features through a learnable edge encoder. The resulting hyperbolic embeddings are jointly utilized for link prediction and RTT prediction via Random Forest regression.

V. M ETHODOLOGY We propose HERMIT, a hybrid architecture that extends HMPTGN [8] with a learnable edge encoder and Random Forest for joint link and RTT prediction. The key design principle is to preserve the hierarchical structure of Internet topology in hyperbolic space while incorporating explicit edge features, and to leverage the robustness of Random Forest for handling heavy-tailed RTT distributions. As illustrated in Fig. 1, HERMIT performs this joint prediction task on sequences of daily network snapshots. The HMPTGN is selected as the backbone architecture due to its superior geometric stability and enhanced feature representation capabilities compared to the baseline HTGN, which are critical for accurately modeling the highly dynamic and hierarchical Internet topology. The primary distinction between these two models lies in HMPTGN’s manifoldpreserving design, which utilizes native hyperbolic operations such as Möbius addition and Poincaré linear transformations to minimize geometric distortion and ensure critical structural information is accurately preserved. Furthermore, HMPTGN enhances stability by applying orthogonal weight matrices, which constrain node embeddings within the Poincaré ball during their mathematical operations, effectively mitigating numerical instability observed under aggressive optimization settings. Conversely, the baseline HTGN model relies on tangent space approximation, projecting embeddings onto a local Euclidean tangent plane, an approach that introduces significant geometric distortion and allows the resulting error to accumulate linearly across time steps, leading to numerical instability. Following the original HMPTGN architecture, node features are initialized as learnable embeddings of dimension 128 that are jointly optimized with the model parameters to adaptively capture the topological structure without manual feature engineering. To more comprehensively represent the

TABLE III N ODE AND E DGE F EATURE E NGINEERING AND P REPROCESSING P IPELINE Feature

Dim

Content

Preprocessing Pipeline

Node Feature

128

Learnable node embedding

Jointly learned during training

Edge Feature

Log-normalized RTT, log-normalized RTT standard deviation, constant weight

Log transform → global min–max normalization (scaled to [0, 1])

Edge Encoder

3→1

Linear transformation + sigmoid

Xavier initialization → jointly optimized during training

network dynamics, this node-centric approach is extended by incorporating edge features, which explicitly encode the link quality by incorporating the log-normalized metrics of RTT mean and standard deviation, along with the link weight. (Note that these edge features are scaled into [0, 1] via global Min-Max normalization to preserve the absolute scale of RTT across all temporal snapshots.) To effectively integrate these three-dimensional edge features, we employ a learnable linear transformation from R3 to R1 followed by a sigmoid activation to enable learnable attention weights. This edge encoder acts as an edge-level attention mechanism, compressing the threedimensional edge attributes into a scalar weight in [0, 1], which is used to adjust the message passing in the HERMIT layers. The overall feature engineering and preprocessing pipeline for nodes and edges is summarized in Table III. As illustrated in Fig. 2(a), the RTT values in our dataset exhibit a heavy-tailed distribution, with most falling below 200 ms and only a small fraction exceeding 1000ms. Since a standard MSE objective is highly sensitive to these extreme outliers, it often degrades prediction accuracy for typical shortRTT connections. As in Fontugne et al. [12], who model

Min-Max transformation and exponentiates them to recover the predicted RTT value ŷuv,t+1 in milliseconds. Our model jointly exploits the hyperbolic network topology and the temporal RTT dynamics. To jointly optimize topology learning and latency prediction, we train the hyperbolic encoder with a combined objective L that balances link prediction and RTT prediction: L = Llink + λ LRTT , (1)

Fig. 2. (a) RTT distributions on a linear scale show heavy-tailed characteristics with most values below 200ms but outliers extending beyond 1000ms. (b) The Gaussian like log-transformed RTT distribution exhibits more symmetric and concentrated characteristics suitable for regression.

RTTs in the log-domain to handle heavy-tailed behavior, we apply a logarithmic transformation log(RTT + 1) followed by min–max normalization to compress outliers and obtain a more symmetric distribution, as illustrated in Fig. 2(b). Using log(RTT + 1) ensures that the transformed values are positive and avoids extreme negatives from near-zero RTTs, which stabilizes normalization and model training. Our model is trained to predict the RTT values in this normalized logarithmic space. At evaluation time, we perform an inverse Min-Max transformation and exponentiate the predictions to report RMSE and MAE on the original millisecond scale. As Fig. 1 shows, our framework consists of a hyperbolic temporal encoder and an RTT prediction module that regresses continuous RTT values from hyperbolic node embeddings and historical latency statistics, in addition to the link probability used in the original decoder. The encoder first maps graph snapshots into the Poincaré ball, then performs edge-aware hyperbolic message passing to aggregate neighbor features, followed by a GRU to capture temporal dynamics. At each timestamp t, it produces hyperbolic node embeddings zu (t) for all nodes u that preserve the hierarchical structure of Internet topology. As illustrated in Fig. 3(a), for each candidate edge (u, v) at timestamp t, we compute the Poincaré squared distance between node embeddings zu (t) and zv (t). The distance is then mapped to its link existence probability p̂uv,t+1 for the next timestamp through the Fermi-Dirac activation function, which converts hyperbolic distances into probabilities. For its prediction of RTT (Fig. 3(b)), our model extracts the embeddings of its endpoints with node-level historical RTT statistics. The hyperbolic node embeddings zu (t) and zv (t) are concatenated with historical RTT statistics fu and fv (aggregated from past snapshots G1 , · · · Gt ) to form an edge-level feature vector: Huv,t = [ zu (t) ∥ zv (t) ∥ fu ∥ fv ]. The historical statistics in fu and fv are indeed the mean and standard deviation of log-transformed RTT values from all past links in which nodes u and v appear, either as source or target, respectively. A Random Forest regressor takes Huv,t as input to predict log-RTT targets that are globally normalized over the training set. Finally, the model performs an inverse

where Llink is the binary cross-entropy loss for link prediction, LRTT is the MSE loss on the normalized RTT values, and λ is a weighting hyperparameter. We set λ = 10 after exhaustively exploring different values to balance these two objectives. Here, our model minimizes this overall loss L using the Riemannian Adam (RAdam) optimizer [31]. The link prediction loss Llink is the binary cross-entropy between the predicted link probabilities p̂uv,t+1 (from the Fermi-Dirac decoder) and the ground-truth labels. X h 1 ℓuv,t+1 log p̂uv,t+1 Llink = − |St+1 | (u,v)∈St+1 (2) i + (1 − ℓuv,t+1 ) log(1 − p̂uv,t+1 )

where St+1 denotes the set of sampled node pairs (with some specific sampling method that will be mentioned later, St+1 includes both positive edges that exist and negative samples that do not), and ℓuv,t+1 ∈ {0, 1} is the binary label indicating whether edge (u, v) exists at time t + 1. During the training phase, our model uses an auxiliary 2-layer MLP with hidden dimension 32 that takes the concatenated hyperbolic node embeddings zuv (t) = [zu (t)∥zv (t)] at time t as input to predict future RTT values at t + 1, and optimizes the MSE loss LRTT , which is defined as follows X 2 1 MLP LRTT = yuv,t+1 − ŷuv,t+1 (3) |Et+1 | (u,v)∈Et+1

where Et+1 denotes the set of directed edges with RTT values that occurs at time t + 1, yuv,t+1 ∈ [0, 1] is the ground-truth MLP RTT that in the normalized logarithmic form, and ŷuv,t+1 ∈ [0, 1] is the MLP prediction passed through a sigmoid output layer, which is also in the same form. This auxiliary task ensures that the node embeddings capture latency dynamics alongside network topology. During training, we process the network snapshots sequentially to optimize the overall objective L defined in equation (1). For each snapshot Gt , we use all observed links Et as positive edges and construct an equal number of negative edges (1:1 ratio) by uniformly sampling unconnected node pairs from Vt × Vt \ Et . Our model then computes the link prediction loss Llink and the auxiliary RTT prediction loss LRTT in parallel. We split the dynamic graph into 85% training, 5% validation, and 10% test snapshots in strict temporal order. To prevent data leakage, historical node-level RTT statistics are computed exclusively from the training set. During inference, we keep the model parameters fixed, but sequentially update the temporal encoder’s hidden states over the validation and test snapshots to capture the latest network dynamics from the incoming snapshots. For link prediction, our results are evaluated using

Fig. 3. (a) Link prediction pipeline. Hyperbolic node embeddings are evaluated using the Poincaré squared distance, then mapped to link existence probabilities via Fermi-Dirac activation. (b) RTT prediction pipeline. Hyperbolic node embeddings and historical statistics are concatenated and processed by Random Forest to predict RTT values. Since the model is trained on normalized log-RTT targets, the output is subsequently denormalized via an inverse Min-Max transformation and exponentiated to recover the actual RTT in milliseconds.

AUC and AP, whereas for RTT prediction, they are evaluated using RMSE and MAE on the original latency scale.

dimensions to one with sigmoid activation. During training, the auxiliary head is a two-layer MLP with 32 hidden units, ReLU activation, a dropout rate of 0.2, and a sigmoid output layer, which is used to calculate LRTT . We use a learning rate VI. E XPERIMENT of 0.0001 and set the RTT weight in loss (λ) to 10.0. For the All experiments are conducted on a Linux server equipped final RTT prediction, the Random Forest component uses 120 with an NVIDIA GeForce RTX 4090 GPU (24 GB) and an decision trees with maximum depth 30 and maximum features Intel Core i9-14900KF CPU. The models are implemented 0.8, optimized via grid search on the validation set, and it in Python 3.9 with PyTorch 2.x. We use a random seed of takes concatenated hyperbolic embeddings (that are projected 1024 to ensure reproducibility. We evaluate our method on to tangent space) and tabular features (historical RTT statistics) the CAIDA IPv4 Ark Project dataset that spans 2015 to as input. 2024. After the sampling in Section IV, we obtain 1,456 Models are trained for up to 50 epochs with early stopping daily snapshots, each representing the network routing and the based on validation performance. We evaluate link prediction corresponding RTT measurements on a specific date. To handle using Area Under the ROC Curve (AUC), which measures the heavy-tailed RTT distribution, we apply a logarithmic how well the model separates existing from non-existent links, transformation followed by min-max normalization to [0, 1]. We and New AUC, computed only on edges appearing for the adopt an 85%/5%/10% data split, resulting in 1,241 snapshots first time in test snapshots to assess generalization to unseen for training, 70 for validation, and 145 for testing, ensuring links. For RTT prediction, we report Root Mean Squared Error temporal integrity and preventing information leakage. (RMSE) and Mean Absolute Error (MAE). RMSE penalizes We compare HERMIT against baselines in two categories. large errors heavily and is sensitive to outliers, while MAE For link prediction, we evaluate against HTGN [28], which reflects typical accuracy under normal conditions. Together, integrates hyperbolic graph convolution with gated recurrent they capture both average performance and robustness under units, and HMPTGN [8], our base encoder that performs high-variance network conditions. manifold-preserving message passing but lacks the edge encoder and hybrid RTT prediction components proposed in VII. R ESULTS this work. For RTT prediction, we compare against Random Forest trained on tabular features only [11], whereas our We evaluate the link prediction performance of HERMIT HERMIT enhances the Random Forest regressor with additional against two baselines: HTGN and HMPTGN. Table IV shows hyperbolic embeddings that encode network topology. that our model achieves an AUC of 99.53% and AP of The hyperbolic embedding of our HERMIT model is 99.56% on the test set, outperforming HTGN (96.28% AUC, implemented using a Poincaré ball manifold with curvature 96.47% AP) and HMPTGN (97.13% AUC, 97.58% AP). c = 1.0. Edge features are 3-dimensional vectors that consist For new link prediction, HERMIT attains a new AUC of of the log-RTT mean, the log-RTT standard deviation, and the 99.32% and new AP of 99.38% (Table IV), demonstrating link connection count (link weight). The edge encoder then strong generalization to previously unseen connections. The applies a linear transformation on these edge features from three performance improvement can be attributed to the incorporation

of edge-level features, which enable the model to capture fine-grained temporal dynamics and link quality information. Table V compares the RTT prediction performance between HERMIT and Random Forest trained only on tabular features (historical RTT statistics). On the complete test set, HERMIT achieves an MAE of 5.35 ms and RMSE of 20.85 ms, representing improvements of 1.3% and 6.4% over the baseline, respectively. The larger RMSE improvement indicates the model is particularly effective at reducing large prediction errors. For new links that are unseen during training, HERMIT maintains its advantage with MAE of 6.85 ms compared to 6.94 ms (1.3% improvement), demonstrating that hyperbolic embeddings provide generalizable structural information for previously unseen connections. TABLE IV L INK PREDICTION AND NEW LINK PREDICTION PERFORMANCE ON CAIDA DATASET

Metric

HTGN

HMPTGN

HERMIT

AUC AP New AUC New AP

0.9628 0.9647 0.9517 0.9548

0.9713 0.9758 0.9654 0.9705

0.9953 0.9956 0.9932 0.9938

TABLE V RTT P REDICTION P ERFORMANCE C OMPARISON (T EST S ET )