PSEALP: patch-based structural external attention with node memory for dynamic link prediction

Abstract

Dynamic link prediction on temporal graphs is fundamental to many applications such as recommendation, knowledge base completion, and user–item interaction modeling. Most existing dynamic graph neural networks (DGNNs), including memory-based and attention-based models, operate on node-level embeddings and local temporal neighborhoods, making it difficult to explicitly encode ego-centric subgraph structures or share structural patterns across events. In this paper, we propose PSEALP, a patch-based framework that combines structural subgraph modeling with external attention and node memory for dynamic link prediction. For each temporal interaction, we construct a k-hop ego-subgraph around the target node pair and partition its nodes into a small number of structural patches (e.g., center nodes, one-hop neighbors, and others), which are aggregated into patch embeddings. We then apply Structural External Attention (SEA) to map each patch embedding to a shared global structural memory, so that reusable structural motifs are represented as memory slots and reused across ego-subgraphs, with complexity linear in the number of patches. To capture temporal evolution, we maintain a lightweight node memory that is updated using SEA-enhanced subgraph representations of incident events, and design a symmetric scoring function based on the sum and absolute difference of node representations together with a subgraph-level representation, ensuring consistency with undirected link prediction. We conduct experiments on static citation networks and temporally evolving interaction graphs, comparing against GCN-based and TGN-style baselines under a leakage-free temporal evaluation protocol. The results show that the proposed patch+SEA+memory framework yields competitive dynamic link prediction performance while providing an explicit and interpretable structural modeling mechanism that bridges subgraph-based methods and dynamic GNNs.