Adversarial graph learning has emerged as a critical field for assessing the robustness of deep link prediction models. However, contemporary attack methodologies are frequently bottlenecked by prohibitive computational overhead, rendering them impractical for large-scale social networks. Moreover, many existing strategies lack a principled mechanism to optimize the perturbation budget. To overcome these challenges, this work introduces a Local Perturbation algorithm leveraging Integrated Gradients (LPIG). Unlike global attack paradigms, LPIG strategically confines gradient estimation to a localized structural subgraph encompassing the target edge, significantly mitigating the gradient-scaling problem in sparse graphs. By employing integrated gradients as a sensitivity metric, the algorithm identifies and prioritizes the most influential candidate links for perturbation. A key innovation of our approach is the integration of a dynamic convergence criterion, which adaptively terminates the attack based on the real-time misprediction state of the target link, thereby ensuring maximum stealthiness with a minimal perturbation footprint. Extensive experiments on large-scale benchmarks demonstrate that LPIG not only achieves superior computational efficiency but also exhibits high transferability across both similarity-based and neural-based link prediction heuristics.
HAN et al. (Thu,) studied this question.