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

Abstract

Dynamic link prediction aims to predict whether two nodes will interact at a future time point in a dynamic graph based on their historical interactions. Existing sampling based methods, which can be considered as a compressor, generally select a subset of one-hop neighbors from the entire interaction sequence for efficiency. It inevitably makes them lose rich context such as high order structural information and temporal patterns, and often underperform on nodes with sparse historical interaction with other nodes. To this aim, we propose a novel context construction based approach named PeNS that adopts Pseudo Neighbor Augmentation Sampling Strategy for more accurate dynamic link prediction. Specifically, PeNS tries to augment neighbor sequences with three complementary types of pseudo neighbors, injecting structural and temporal cues to provide rich context information especially in sparse neighbor scenarios. We further introduce a Streaming Neighbor Memory Module for efficient pseudo neighbor construction and a dual-stream fusion mechanism for robust representation learning. Extensive experiments demonstrate the effectiveness and generalizability of PeNS.