Graph Poisoning for Node Rank Manipulation

Graph-based retrieval systems rely heavily on structural dependencies, making them vulnerable to adversarial manipulation. We present a black-box graph poisoning attack that degrades a target node's ranking using only edge deletions, without access to model parameters, gradients, or retraining. Prior heuristic methods treat edge influence as a static property and fail to capture how an edge's impact varies with local neighborhood structure. We address this limitation by modeling edge influence as context-dependent. Our method samples multiple ego-networks around a target node, measures empirical utility changes from edge ablations, and trains a local scorer to predict context-sensitive edge effects. At inference, predictions are aggregated across sampled subgraphs to yield stable deletion decisions. Experiments on standard benchmarks show that this approach consistently outperforms existing black-box and white-box baselines across perturbation budgets while remaining model-agnostic.