From Compression to Construction: Pseudo Neighbor Augmentation Sampling for Dynamic Link Prediction

1 Introduction

Dynamic link prediction aims to model the evolving interaction patterns in dynamic graphs by predicting whether two nodes will interact at time t based on their historical interactions observed before t. This task arises broadly in realworld scenarios such as social networks [Yu et al., 2020], ecommerce platforms [Yin et al., 2025; Liu et al., 2025] and traffic network [Cheng et al., 2025].

In recent years, dynamic graph learning methods based on neighbor interaction sequence [Cong et al., 2023; Zou et al., 2024] have become one of the dominant paradigms for dynamic link prediction. These methods typically retrieve the historical interaction neighbors along with their timestamps for each node at a target time, to form a neighbor sequence, and then learn temporal node representations via a sequence modeling module [Sutskever et al., 2014]. Given the large scale and high interaction frequency of dynamic graphs, directly encoding the full historical neighborhood is costly. Therefore, existing methods [Rossi et al., 2020; Li et al., 2023] generally adopt the compression strategy, namely selecting a subset of the entire historical neighbors or truncating by a time window, to control the size of historical context used for prediction.

∗Corresponding Author.

Figure 1: Illustration of three limitations of existing compression based neighbor sampling strategy for dynamic link prediction.

However, such compression based sampling methods suffers from the following three major limitations: (1) difficult to fully utilize the high order structural information. Since the size of neighborhoods grows exponentially with the increase of hops, multi-hop message passing will introduce prohibitive cost for large graphs. As a result, most existing methods only prune within one-hop historical neighbors, making them difficult to incorporate the high order structure information, as shown in the difficulty ① (upper right) of Figure 1; (2) difficult to fully utilize the temporal pattern information. As shown in the difficulty ② (upper left) of Figure 1, nodes w and u have never interacted, but they exhibit similar temporal interaction patterns at [t1, t3, t5, t7], which may indicate potential future interactions. This intuition is supported by previous studies showing that social network users who are consistently active in the same time period are more likely to become friends in the future [Cho et al., 2011]. However, such temporal patterns are largely ignored by existing methods. (3) difficult to learn the reliable representations for the nodes with sparse neighbors. Since dynamic graphs in real world are typically long tailed and intermittent, many nodes may have scarce or even no historical interactions with other nodes at some time points [Leskovec et al., 2005; Leskovec et al., 2010]. In this case, compression based sampling method often degenerates the input into short sequences or heavy padding, as shown in the difficulty ③ (lower right) of Figure 1. This leaves the model without sufficient context, making it difficult to learn reliable node representations.

To address these limitations, we rethink neighbor sampling from Compression to Context Construction. Specifically, instead of modifying the real neighbor sampling, we try to construct the interaction context with pseudo neighbor augmentation. The augmented pseudo neighbors provide auxiliary structural and temporal cues, and thus help to produce more stable temporal representations, especially for the nodes with scarce historical interaction. However, it is non-trivial to construct such pseudo neighbors due to the following challenges: (1) Limited informativeness. Weakly relevant pseudo neighbors may bring little useful context, leading to little gain or even misleading the model. (2) Efficiency bottleneck. Inefficient pseudo neighbor construction can be time-consuming, substantially increasing the computational cost. (3) Bias issue. Since pseudo and real neighbors differ in generation mechanisms , directly encoding them together may introduce bias, resulting in unreliable node representations.

To address these challenges, we propose a Pseudo Neighbor Augmentation Sampling Strategy based approach named PeNS for dynamic link prediction. Specifically, we first construct three complementary types of pseudo neighbors to inject high order structural (via structural bridge pseudo neighbors and shared hub pseudo neighbors) and temporal pattern (via temporal correlation pseudo neighbors) information into the interaction sequence context without introducing additional multi-hop message passing overhead. To efficiently construct pseudo neighbors, we further propose a Streaming Neighbor Memory Module that only requires a single chronological linear pass over the global edge stream to obtain the historical neighbor sequence at a given timestamp. Finally, we adopt a dual-stream fusion mechanism that encodes real and pseudo sequences separately, with cross attention for adaptive fusion to produce robust node representations. Our main contributions are summarized as follows.

• We present a novel perspective on neighbor sampling from Compression to Context Construction, thus providing richer interaction context for dynamic link prediction even when nodes have sparse interaction neighbors.
• We propose the Pseudo Neighbor Augmentation Sampling Strategy, which is plug-and-play and can be integrated into existing models. Based on this strategy, we further design an approach named PeNS to learn stable temporal representations for dynamic link prediction.
• Extensive experiments on multiple datasets demonstrate the effectiveness of our approach. Moreover, the consistent gains achieved when integrating our strategy into existing approaches further highlight its generalizability.

2 RelatedWork

DynamicGraphLearning. Dynamic graph learningmethods can be broadly categorized into discrete-time dynamic graph (DTDG) methods and continuous-time dynamic graph (CTDG) methods. DTDG methods [Seo et al., 2018; Hajiramezanali et al., 2019; Chen et al., 2022; Pareja et al., 2020; Sankar et al., 2018; Le and Ta, 2024; Yu et al., 2025] treat a dynamic graph as a sequence of static graph snapshots and then learn representations using static graph learning technique [Scarselli et al., 2008; Kipf and Welling, 2017; Veliˇckovi´c et al., 2018; Xu et al., 2019]. However, these methods rely on temporal discretization, which may discard event-level information. In contrast, CTDG methods [Poursafaei et al., 2022; Cong et al., 2023; Yu et al., 2023; Zou et al., 2024; Zhou et al., 2025] directly model on temporal event streams with continuous timestamps, preserving accurate interaction order and time intervals at the event level, thereby modeling dynamic evolution more faithfully.

Neighbor Sampling Strategy. Neighbor sampling strategies [Liu et al., 2021; Chen et al., 2018] aim to reduce the computational complexity by approximating the message passing on the full graph. Existing sampling methods can be categorized into three groups. Early works [Chen et al., 2017; Ying et al., 2018] adopt mini-batch recursive sampling, which first collect neighbors of nodes within a batch, expand layer by layer and then sample the full neighborhood at each layer. Another research line [Chen et al., 2019; Hamilton et al., 2017] focuses on node-wise sampling, which randomly selects at most k neighbors from the neighborhood of each node to approximate the node distribution of the full graph. Recent methods [Abu-El-Haija et al., 2023; Zeng et al., 2020] target at partitioned graphs and discard boundary nodes from other partitions while maintaining the connectivity among nodes within the batch.

3 Preliminaries

In this section, we present the definition of dynamic graphs and the formalization of dynamic link prediction.

Definition 1. Dynamic Graphs. A dynamic graph can be modeled as a time-ordered sequence of interaction events, denoted as G = {(u1, v1, t1), (u2, v2, t2), . . . , (uk, vk, tk)}, where 0 ≤ t1 ≤ t2 ≤ · · · ≤ tk represent the timestamps. Here, ui and vi denote the interaction nodes, indicating that nodes ui and vi interact at time ti. The node set is denoted by N . For each node u ∈ N , the node feature of u is represented as xu ∈ RdN . Moreover, each interaction event (u, v, t) has an edge feature xtu,v ∈ RdE , where dN and dE denote the dimensions of node and edge features, respectively.

Definition 2. Dynamic Link Prediction. Given two nodes u and v, a timestamp t, and the interaction history {(u′ , v′ , t′ ) | t′ < t} before t in a dynamic graph G, the goal of dynamic link prediction is to learn a mapping function f : (u, v, t) → ˆ ytu,v ∈ [0, 1], which estimates the interaction probability ˆ ytu,v and further predicts whether u and v will interact at time t.

4 Methodology

In this section, we illustrate the overall architecture of the proposed PeNS in Figure 2. Firstly, we query and update the Streaming Neighbor Memory Module (Sec 4.1) to obtain the real historical neighbor sequences. Then we augment the sequences to inject rich context via Pseudo Neighbors Augmentation Sampling (Sec 4.2). Next, we adopt Feature Encoding and Alignment (Sec 4.3) for the neighbor sequences to fuse multi-source features. Finally, a Dual-Stream Fusion Transformer (Sec 4.4) is employed to learn robust temporal representations for Dynamic Link Prediction (Sec 4.5).

4.1 Streaming Neighbor MemoryModule

In dynamic link prediction, a model typically needs to quickly retrieve the historical neighbor sequences of nodes u and v before time t when processing a sample (u, v, t), so as to construct the context for temporal encoding. To avoid repeatedly searching over the global edge set, we employ a Streaming Neighbor Memory Module to maintain node interaction histories at a given time, as shown in Figure 2(a). Specifically, for each node u ∈ N , we maintain a deque Du with a maximum capacity of kneigh, where each element stores the interaction information δ = (v, t), including the target node v and the interaction time t. When processing the event (u, v, t), we first query the historical neighbor sequences as follows:

where Read(·) returns a sequence with length at most kneigh. We then update the memory as:

If the sequence length exceeds kneigh, the oldest element is removed to keep the fixed capacity. This ensures that each edge triggers only a constant number of enqueue and dequeue operations, efficiently supporting the real neighbor retrieval and subsequent pseudo neighbor augmentation.

4.2 Pseudo Neighbor Augmentation Sampling

In this part, we design three complementary pseudo neighbor sampling strategies. These strategies can inject high order structural and temporal pattern information into interaction context without introducing additional multi-hop message passing overhead. To control the number of pseudo neighbors in each category, we adopt a Top-k scheme to keep the augmentation budget bounded. Given the real neighbor sequences N tu and N t v for a target sample (u, v, t), we sample pseudo neighbors as follows.

Structural Bridge PseudoNeighbor Sampling. As shown in the upper part of Figure 2(b), structural bridge pseudo neighbors inject cross-neighborhood bridging roles into the sequence. Specifically, for each node a ∈ N t v , we query its historical neighbors N t a from the previous presented Streaming Neighbor Memory Module, and compute the structural bridge score of node a as:

We then select the Top-kb nodes with the highest scores to form the structural bridge pseudo neighbor sequence ˜N tu,bridge . In particular, for attributed graphs, the interaction time and edge feature of a pseudo edge are computed as:

where tu,v denotes the interaction time between nodes u and v, and xtu,v denotes the edge feature of interaction (u, v, t).

The ˜N t v,bridge and its corresponding pseudo edge interaction times and edge features are computed analogously.

SharedHubPseudoNeighbor Sampling. As shown in the middle part of Figure 2(b), shared hub pseudo neighbors select highly connected nodes that are commonly associated with both endpoints, serving as stable contextual anchors especially for sparse interaction nodes. Specifically, for each node a ∈ N, we compute its overlap sizes ru(a) and rv(a) with the neighborhoods of both endpoints u and v as:

and obtain the shared hub score via max normalization as:

where ϵ is a small positive constant to avoid division by zero. For computational simplicity, we restrict a ∈ N tu ∪ N t v .

We then select the Top-kh nodes to form the shared hub pseudo neighbor sequence ˜N tu,v,hub , and append it to both the pseudo neighbor sequences of nodes u and v. In particular, for attributed graphs, the pseudo edge interaction time and edge feature are computed as:

Temporal Correlation Pseudo Neighbor Sampling. As shown in the lower part of Figure 2(b), temporal correlation pseudo neighbors exploit temporal correlations in interaction sequences, enabling the model to observe potentially related interaction partners and thus better capture temporal interaction patterns. Specifically, we denote the historical interaction timestamp sequence of node u at time t as TN tu = (tu,1, tu,2, . . . , tu,m), and construct its adjacentinterval sequence ∆TN tu = (tu,2 - tu,1, . . . , tu,m - tu,m-1), where m ≤ kneigh. For each node a ∈ N, we compute its temporal correlation score with respect to node u as:

where PCC(·) computes the Pearson Correlation Coefficient between two sequences. For computational simplicity, we restrict a ∈ N tu ∪N t v as shared hub pseudo neighbor sampling.

We then select the Top-kc nodes with the highest scores to form the temporal correlation pseudo neighbor sequence ˜N tu,corr . In particular, for attributed graphs, the pseudo edge interaction time and edge feature are computed as:

The ˜N t v,corr and its corresponding pseudo edge interaction times and edge features are computed analogously.

Finally, we concatenate the three types of pseudo neighbors to obtain the final pseudo neighbor sequences as:

4.3 Feature Encoding and Alignment

To uniformly characterize the information carried by real and pseudo neighbors, we construct a joint representation that includes node, edge, time, frequency, and source information, as shown in Figure 2(c).

For each a ∈ N tu , we define the relative time ∆ta = t-tu,a and introduce a source label sa ∈ {real,bridge,hub,corr}. The node feature xa ∈ RdN and the edge feature xtu,a u,a ∈ RdE are obtained from the dynamic graph G. Following [Cong et al., 2023], we derive the time representation by mapping ∆ta into a continuous vector via cosine functions as:

where wi is a fixed node-specific feature and dT denotes the dimension of time encoding.

The frequency feature explicitly models the intensity of repeated interactions. Given the four neighbor sequences, the frequency feature of node a is computed as:

where N tu (a) denotes the number of occurrences of node a in the sequence N tu .

The source feature xta,S indicates whether the neighbor comes from the real sequence or one of three pseudo neighbor types, obtained by one-hot encoding the source label sa.

Finally, we feed these features into separate linear layers to align them to dimension d, and then concatenate them to obtain the neighbor sequence representations Ztu = Xtu,N ||Xtu,E ||Xtu,T ||Xtu,F ||Xtu,S ∈ Rkneigh×5d . Stacking the representations of both endpoints yields the interaction representation Ztu,v = [Ztu ;Ztv ] ∈ R2kneigh×5d . Similarly, we obtain ˜Ztu,v = [ ˜Ztu ; ˜Ztv ] ∈ R2kpseudo×5d , where kpseudo = kb + kh + kc denotes the total number of pseudo neighbors. Positions with insufficient length are padded with zeros for dimensional alignment.

4.4 Dual-StreamFusion Transformer

In our framework, real neighbors provide observed signal while pseudo neighbors act as prior supplements. They differ in their generation mechanisms and noise characteristics. Directly mix and feed them into a single encoder may introduce bias, which can mislead temporal representation learning. Hence, we adopt a Dual-Stream Fusion Transformer as shown in Figure 2(d), where two structurally identical but parameter-independent Transformer [Vaswani et al., 2017] encoders are used to learn the representationsHtu,v and ˜Htu,v of real stream and pseudo stream respectively as follows:

Then, to allow the real interaction to adaptively absorb the structural and temporal priors injected by pseudo neighbors, we perform cross-attention fusion by using the real stream as query and the pseudo stream as key and value, yielding the fused interaction representation matrix as:

The final temporal representations otu and otv of nodes u and v at time t are obtained by averaging their corresponding rows in Otu,v and applying a linear projection as:

whereWout ∈ R5d×dout and bout ∈ Rdout are learnable parameters, and dout denotes the output dimension.

4.5 Dynamic Link Prediction

After obtaining the temporal representations otu and otv and concatenating them, we predict the interaction probability via a multi-layer perceptron (MLP) [Rumelhart et al., 1986] as:

We adopt the binary cross-entropy loss for supervision as:

where E + and E - denote the sets of positive and negative samples, respectively, and N is the total number of samples.

5 Experiments

In this section, extensive experiments are conducted. We report results for various baselines and further demonstrate the generalizability of our sampling strategy by equipping it into existing methods. We then provide an in-depth analysis on the effect of key hyperparameters and components.

5.1 Experimental Settings

Datasets. We evaluate PeNS on 9 real-world dynamic graph datasets (i.e., Wikipedia, Reddit, MOOC, LastFM, Enron, UCI, BITotc, BITalpha, and DBLP) from [Poursafaei et al., 2022; Xu et al., 2023].

Baselines. We compare PeNS against 11 widely used dynamic graph methods, including four memory-based methods (JODIE [Kumar et al., 2019], DyRep [Trivedi et al., 2019], TGN [Rossi et al., 2020], and PANet [Zhou et al., 2025]), a graph convolution-based method (TGAT [Xu et al., 2020]), a random-walk-based method (CAWN [Wang et al., 2021b]), a statistical method (EdgeBank [Poursafaei et al., 2022]), two MLP-based methods (GraphMixer [Cong et al., 2023] and RepeatMixer [Zou et al., 2024]), and two sequence-based methods (TCL [Wang et al., 2021a] and DyGFormer [Yu et al., 2023]).

Evaluation Tasks and Metrics. We consider two settings: (1) transductive dynamic link prediction, which predicts links between nodes observed during training period, and (2) inductive dynamic link prediction, which predicts links involving previously unseen nodes. Negative samples are randomly selected with a 1:1 ratio to positive samples. We report Average Precision (AP) and Area Under the Receiver Operating Characteristic Curve (AUC-ROC) as the main metrics.

Implementation Details. We use the same hyperparameter settings as those in DyGLib [Yu et al., 2023] for fair comparison. Our code is available at https://github.com/CsuYuzhigang/PeNS.

5.2 Performance Comparison

Overall Performance. We report the comparison results for dynamic link prediction in Table 1. Based on the results, we make the following key observations:

(i) Under the transductive setting, PeNS achieves almost consistent SOTA performance across datasets. In terms of AP, PeNS outperforms the strongest baseline by 5.71% on LastFM, 3.31% on UCI and 8.53% on DBLP. Moreover, on datasets that are close to saturation (e.g., Wikipedia and Reddit), PeNS still pushes performance to around 99.9% on top of very strong baselines, demonstrating its effectiveness.

(ii) Under the more challenging inductive setting, the advantages of PeNS become even more pronounced. In terms of AP, PeNS improves upon the strongest baseline by at least 10% on datasets such as BITotc (97.86%), BITalpha (97.29%) and DBLP (93.39%). This suggests that when many unseen nodes appear at test time, conventional methods rely more heavily on retrievable real historical interactions to form representations. In contrast, PeNS leverages the enriched context brought by augmentation to provide more stable signals when real neighbors are insufficient, thereby largely preventing the severe performance drop on nodes with sparse interactions. Although PeNS does not achieve the best result on MOOC, it delivers more stable performance and a higher lower bound on most datasets.

Overall, these results support our core motivation: the key bottleneck in dynamic graph learning is not only the need to compress overly many neighbors, but also the lack of sufficient context. This bottleneck becomes more pronounced in inductive settings or sparse neighbor scenarios. PeNS effectively complements structural and temporal information through pseudo neighbor augmentation and dual-stream fusion, leading to significant and stable performance gains.

Performance under Varying Neighbor Availability. We conduct an evaluation stratified by historical interaction neighbor availability to compare PeNS with existing baselines. The results are shown in Figure 3.

Specifically, we partition the test samples into three groups according to the number of historical neighbors of the anchor node at the target time, and then report the AP of methods across different groups to examine performance differences under varying neighbor availability. The results show that when sufficient historical neighbors are available (neighbors ≥ 10), all four baselines achieve relatively strong performance on both datasets. In contrast, when historical neighbors are extremely sparse (neighbors < 5), the performance of these baselines drops significantly, indicating that the models rely heavily on limited historical interaction information and struggle to construct stable temporal representations in sparse conditions. In contrast, by augmenting with pseudo neighbors, PeNS achieves performance in sparse scenarios that is comparable to that in dense scenarios, while consistently outperforming baselines across all scenarios, indicating the effectiveness and generalizability of our approach.

5.3 Effects of Pseudo Neighbor Augmentation Sampling Strategy

To investigate the impact of our Pseudo Neighbor Augmentation Sampling Strategy, we conduct two experiments from the perspectives of generalizability and effectiveness.

Generalizability of Pseudo Neighbor Augmentation Sampling Strategy. We integrate the proposed sampling strategy into different baselines (DyGFormer, TGAT, and TCL), and report AP results on transductive dynamic link prediction in Figure 4. The results show consistent improvements across four datasets, indicating that neighbor augmentation can provide effective contextual signals without modifying the core modeling components of the baselines, thus yielding broad gains across models and datasets. Moreover, the improvement magnitude is closely related to both the representational capacity of the backbone model and the interaction sparsity of the dataset. The gains are more evident when the original method is more sensitive to context information or more likely to suffer from insufficient historical neighbors.

Comparison with Different Variants. Table 2 compares three variants: using our designed pseudo neighbors (Ours), using random pseudo neighbors (Random), and replacing pseudo neighbors with more real neighbors (Real). The results demonstrate that our carefully designed pseudo neighbors provide informative context and improve temporal representation learning. In contrast, randomly introduced pseudo neighbors tend to inject substantial noise and fail to offer useful complementary signals. Thanks to the dual-stream fusion mechanism, the model adaptively balances real and pseudo neighbors, suppressing irrelevant information and maintaining stable performance. While replacing with more real neighbors avoids random noise, it is still insufficient to compensate for the missing context in sparse neighbor scenarios and mitigate the loss of structural and temporal information.

5.4 Effects of Different Hyperparameters

More specifically, we examine the effects of key hyperparameters on PeNS. Figure 5 reports the results on UCI.

Number of Sampled Neighbors. The left of Figure 5 shows that using few sampled neighbors yields insufficient context and limits the performance. As the number increases, the performance improves rapidly and then reaches its peak. However, further increasing this number leads to a gradual drop in AP, with a more clear degradation under the inductive setting. This suggests that overly long historical neighbor sequences introduce more outdated or weakly related interactions, interfering with temporal modeling, and the effect is more pronounced under inductive settings.

Total Number of Pseudo Neighbors. The right of Figure 5 shows that AP increases as the total number of pseudo neighbors grows, and the gain later plateaus or slightly declines. It indicates that a reasonable amount of pseudo neighbors can continuously provide effective context and improve representation quality, while too many pseudo neighbors increase computational cost and may introduce additional noise.

5.5 Ablation Study

To evaluate the effectiveness of individual components in PeNS, we conduct an ablation study with the following variants: w/o PN removes all pseudo neighbors; w/o SBN, w/o SHN, and w/o TCN remove structural bridge neighbors, shared hub neighbors, and temporal correlation neighbors, respectively; w/o FE removes frequency encoding; and w/o SE removes source encoding.

As shown in Figure 6, all variants perform worse than the full PeNS under both transductive and inductive settings, indicating that all these components work together and achieve the best performance when fully enabled. A closer look shows that removing pseudo neighbors (w/o PN) leads to the most pronounced drop (e.g., 5.07% in BITotc and 13.96% in BITalpha under transductive settings), suggesting that pseudo neighbor augmentation is the primary driver of the overall gains. Meanwhile, removing source encoding (w/o SE) also noticeably degrades performance (e.g., 4.37% drop in BITalpha under transductive settings), implying that explicitly distinguishing real neighbors from different types of pseudo neighbors helps the model utilize the augmented context in a stable and effective manner. Among the three kinds of pseudo neighbors, removing structural bridge neighbors (w/o SBN) or shared hub neighbors (w/o SHN) typically causes larger performance losses, highlighting the dominant role of high order structural information. Removing temporal correlation neighbors (w/o TCN) also yields consistent degradation, indicating that the injected temporal pattern signals complement structural information and remain indispensable. Finally, the results of w/o FE verify that modeling repeated interaction intensity provides additional useful signals for prediction.

6 Conclusion

In this paper, we rethink neighbor sampling from compression to context construction and propose PeNS. Specifically, we design a Pseudo Neighbor Augmentation Sampling Strategy that constructs three complementary types of pseudo neighbors. It can inject high order structural and temporal pattern information into the interaction context without introducing additional multi-hop message passing overhead, and generalize well to sparse neighbor scenarios. A Streaming Neighbor Memory Module is developed to construct pseudo neighbors efficiently. In addition, we adopt a dual-stream fusion mechanism to enable more stable temporal representations for dynamic link prediction. Extensive experiments demonstrate the effectiveness and generalizability of PeNS.

Acknowledgments

This research was funded by the National Natural Science Foundation of China (No.62572489 and No.72571284), Hunan Provincial Fund for Distinguished Young Scholars (No.2025JJ20073), Science and Technology Innovation Program of Hunan Province (No.2023RC3009) and Innovation Research Foundation of National University of Defense Technology (No.JS24-05).