Graph-based retrieval systems are vulnerable to adversarial edge perturbations that distort embeddings and ranking outcomes. We study adversarial edge removal for graph-based retrieval and show that structural heuristics such as degree and PageRank are unreliable predictors of rank degradation due to multi-hop spectral effects. We then propose a learning-based estimator that maps local edge characteristics to ranking distortion using perturbation–response pairs, enabling efficient edge selection under budget constraints in a gray-box setting. Experiments on benchmark datasets show that our approach achieves stronger and more efficient rank demotion than state-of-the-art baselines.