Hybrid Dynamic Graph Architecture Enhances Link Prediction Across Sparse Evolving Networks

A research team comprising Nafiseh Sadat Sajadi, Behnam Bahrak, and Mahdi Jafari Siavoshani has introduced TGN-SEAL, a hybrid machine learning framework designed to improve dynamic link prediction in sparse, evolving communication networks. Dynamic link prediction forecasts how relationships between nodes evolve over time as edges and vertices appear, disappear, or update. Conventional Graph Neural Networks are designed for static graphs and struggle to capture continuous temporal dependencies. While snapshot-based discrete-time methods track network evolution across fixed intervals, they regularly suffer from data sparsity and class imbalance, particularly in telecommunication call detail records. By extracting enclosing subgraphs around candidate links and combining them with Temporal Graph Networks, the TGN-SEAL architecture jointly learns localized topological structure and temporal dynamics. Empirical evaluations demonstrate that this hybrid formulation increases average precision by at least two percent over standard Temporal Graph Networks, highlighting the decisive benefit of integrating local topology for dynamic link prediction.

Forecasting connection formation in dynamic graphs carries substantial operational importance across diverse computational and engineering disciplines. Modeling complex systems as graphs provides a unified foundation, where nodes correspond to distinct entities and edges capture relationships between them. In the telecommunications sector, network operators record millions of communication events within call detail records containing caller identities, recipient identifiers, timestamps, and call durations. Predicting future communication events allows telecommunication providers to allocate resources efficiently, suggest customized service packages based on anticipated subscriber requirements, and optimize administrative staffing schedules. Beyond telecommunications, dynamic link prediction is equally essential across commercial and scientific applications. In e-commerce platforms, link prediction underpins recommender systems that suggest relevant products. In bioinformatics, dynamic link prediction models facilitate the identification of emerging protein-protein interactions and accelerate drug discovery pipelines, while in data engineering, related techniques support metabolic network reconstruction, automated knowledge graph completion, and interaction tracking in security monitoring.

To establish the context of their architecture, the researchers reviewed the foundation of link prediction strategies, which divide into heuristic-based approaches and learning-based frameworks. Heuristic methods assign a likelihood score to candidate node pairs based on shared characteristics or graph topology. These heuristics are categorized according to the neighborhood distance required to evaluate potential links. First-order heuristics such as common neighbors and preferential attachment examine direct neighboring nodes, whereas second-order heuristics like the Adamic-Adar index evaluate paths two steps away. Higher-order and global heuristics, including the Katz index, rooted PageRank, and SimRank, capture broader graph connectivity. Although similarity-based heuristics consistently outperform random baselines and capture intuitive tendencies such as homophily in social networks, they depend on rigid assumptions that do not hold across distinct networks. For instance, while nodes sharing more neighbors connect frequently in social graphs, interaction likelihood in protein-protein networks often increases when nodes share fewer common neighbors, demonstrating how rigid heuristics fail across distinct scientific domains.

To overcome the limitations of fixed heuristics, subsequent research framed link prediction as a supervised machine learning task capable of inferring structural patterns directly from data. Early work evaluated topological similarity metrics to rank links, which later researchers expanded by combining network topology with social data and reformulating link prediction as supervised binary classification. In classification models, engineered similarity indices serve as input features for support vector machines and decision trees to distinguish positive from negative links. Methodological taxonomies further categorized techniques into similarity-based methods, computationally inefficient maximum likelihood approaches, and probabilistic relational frameworks, including Probabilistic Relational Models and Graphical Models developed primarily for homogeneous structures. As network scales expanded, latent feature models emerged, projecting relational dependencies into low-dimensional representations. These techniques progressed from node embedding algorithms to modern Graph Neural Networks, which iteratively aggregate local neighborhood features through message passing. However, standard Graph Neural Networks remain restricted to static graphs, lacking mechanisms to model continuous-time dynamic event streams.

The new architecture bridges this gap by integrating two established graph neural network models: Subgraph Embeddings and Attributes for Link prediction (SEAL) and Temporal Graph Networks (TGN). The SEAL framework, developed for static graphs, replaced hand-crafted scoring functions with structure-aware learning by extracting enclosing subgraphs around target node pairs. Supported by the unified gamma-decaying theory, SEAL demonstrated that higher-order heuristics can be approximated using information contained within local enclosing subgraphs, which are processed by graph neural networks such as the Weisfeiler-Lehman Neural Machine to learn topological patterns. Conversely, Temporal Graph Networks were designed specifically for continuous-time dynamic graphs, modeling network activity as ordered streams of time-stamped events rather than static snapshots. Operating within an encoder-decoder structure, TGN assigns each node an evolving memory vector that acts as a compact summary of its historical interactions. Updated node embeddings are dynamically computed by integrating current node memory, recent event attributes, and memories of temporal neighbors, mitigating memory staleness while maintaining strict causal consistency and avoid information leakage from future events.

In standard Temporal Graph Networks, the decoder predicts link formation by concatenating temporal embeddings of two target nodes and feeding them into a multi-layer perceptron. The TGN-SEAL framework replaces this prediction module by redefining link prediction as a graph classification task performed over enclosing subgraphs. At each iteration, the model computes initial temporal embeddings for every node using the TGN embedding module, summarizing recent activity. For each interaction between a source node and a destination node occurring at time t, the architecture extracts an enclosing subgraph induced by the k-hop neighborhood, incorporating exclusively those interactions that transpired prior to time t. Each node within the extracted subgraph is assigned a structural label via Double-Radius Node Labeling (DRNL), which calculates shortest path distances to both target nodes in closed form. These labels are converted into one-hot vectors and concatenated with temporal memory representations. The combined feature matrix and enclosing subgraph are then processed by a Deep Graph Convolutional Neural Network (DGCNN), which generates a scalar probability output between zero and one representing the probability of a link, optimized using binary cross-entropy loss.

Following batch probability estimation, TGN-SEAL initiates a memory update procedure designed to maintain causal validity without information leakage. For each interaction occurring within the batch, messages are generated for participating nodes using their pre-batch memory states, current embeddings derived from the TGN-SEAL module, interaction attributes, and temporal encodings of interaction times. Because individual nodes often engage in multiple interactions within a single batch, the model applies a last-message aggregation strategy for computational efficiency, retaining solely the most recent message in temporal order. The aggregated messages subsequently update node memory states through a Gated Recurrent Unit (GRU) updater. Importantly, memory updates are delayed until all predictions for the current batch have been completed. This delayed execution guarantees that node representations used to predict an interaction at time t depend entirely on information available prior to that timestamp. Because enclosing subgraphs are extracted using exclusively past interactions, this postponed update mechanism preserves causal integrity and inductive validity throughout the continuous learning process.

To assess the generalizability of TGN-SEAL, the researchers conducted experiments across three continuous-time interaction benchmarks characterized by distinct communication behaviors. The Reality Mining dataset captures 87,417 mobile telephone call records among 94 participants over nine months, exhibiting pronounced structural sparsity and transient communication. The Email-Eu-core dataset contains approximately 60,000 email interactions across four distinct departmental subnetworks within a European research institution, reflecting structured institutional communications. The CollegeMsg dataset documents 59,835 private messages exchanged over 193 days within an online university social platform. Across all three datasets, the authors implemented a chronological split allocating seventy percent of interactions to training, fifteen percent to validation, and fifteen percent to testing, ensuring models were evaluated strictly on future temporal connections. Because benchmark nodes lacked intrinsic attributes, the researchers assigned constant zero vectors to all nodes. Consequently, models were forced to rely exclusively on learned structural topologies and temporal interaction histories, with call duration serving as an informative edge feature in the telecommunications data.

The evaluation utilized Mean Average Precision (mAP) as the primary performance metric, chosen for its suitability in dynamic link prediction tasks marked by class imbalance. The researchers benchmarked TGN-SEAL against three dynamic graph networks—JODIE, DyRep, and TGAT—alongside standard TGN and three ablation variants: TGN-no-mem, which removes memory; TGN-id, which uses an identity message mapping; and TGN-time, which isolates temporal encodings. Across transductive and inductive evaluations, TGN-SEAL achieved the best or second-best performance across most datasets. Improvements were especially pronounced on the Reality Mining call network and institutional Email datasets, where recurring interactions and stable structural patterns allowed enclosing subgraphs to supply critical signals beyond temporal dynamics alone. In contrast, on the CollegeMsg online messaging dataset, TGAT and TGN-no-mem achieved top performance, with TGN-SEAL ranking second. This outcome indicated that connection formation in college messaging is driven primarily by immediate temporal activity rather than persistent structural motifs, confirming that the benefit of enclosing subgraphs depends on underlying network characteristics.

An examination of model convergence and efficiency highlighted key operational trade-offs governing the practical deployment of TGN-SEAL. Training curve analyses demonstrated that TGN-SEAL converged in fewer training epochs than baseline TGN architectures on both seen and unseen nodes, although each individual epoch incurred higher computational expenditure due to subgraph extraction and structural aggregation. Comparing neighborhood extraction depths revealed that expanding the enclosing subgraph from a 2-hop radius to a 3-hop radius increased per-epoch execution time by approximately 2.7 times without consistently yielding higher Mean Average Precision. In agreement with the gamma-decaying heuristic theory, the authors noted that predictive structural information is concentrated predominantly within compact local neighborhoods, making a 2-hop radius sufficient for capturing informative topology. To manage scalability across large-scale evolving networks, the framework utilizes temporal neighbor sampling that prioritizes recent interactions, restricting subgraph volume while preserving predictive efficacy. While subgraph extraction overhead represents the primary limitation of TGN-SEAL in dense networks, the configurable neighborhood radius provides an adaptable mechanism to balance computational cost against predictive precision.

Subject of Research: Dynamic graph link prediction combining temporal networks and enclosing subgraphs

Article Title: A hybrid TGN-SEAL model for dynamic graph link prediction

Article References: Sajadi, N. S., Bahrak, B., & Jafari Siavoshani, M. (2026). A hybrid TGN-SEAL model for dynamic graph link prediction. EPJ Data Science, 15(1), Article 69. https://doi.org/10.1140/epjds/s13688-026-00670-1

Image Credits: AI Generated

DOI: 10.1140/epjds/s13688-026-00670-1

Keywords: Dynamic Graphs, Link Prediction, Temporal Graph Networks, Graph Neural Networks, SEAL Framework, Network Science, Call Detail Records, Machine Learning, hybrid, TGN-SEAL, model, dynamic