AFLiP: An Access-Recomputation Decoupling Framework for Efficient and Structure-Preserving GNN-based Link Prediction

Abstract

Many GNN-based link prediction models use a shared message-passing encoder to amortize node encoding across edges. However, in practice, neighborhood expansion makes the edge-level mini-batches approach near full-graph computation, weakening this benefit. Existing scalable techniques enable efficient mini-batch training but make recomputation decisions implicitly via structural access, either recomputing all accessed nodes or only the target nodes in the batch. We propose Access-Decoupled Recomputation (ADR), which treats recomputation as an explicit optimization decision while preserving the original graph structure without neighborhood sampling. We realize ADR as AFLiP, an efficient and structure-preserving framework for GNN-based link prediction. Across diverse models and datasets, AFLiP matches or exceeds full-recomputation accuracy, while sampling and static reuse exhibit dataset-dependent degradation. Compared to full recomputation, AFLiP reaches the best checkpoint up to 3.1× faster and scales to web-scale graphs where full recomputation is infeasible, and achieves up to 16× higher throughput than sampling on Friendster.