A Pre-Indexing Adversarial Attack on Neural Subgraph Retrievers

Given a query graph, a neural subgraph retriever (NSR) returns Top-K relevant graphs from a corpus of graphs, where the underlying learned relevance approximates combinatorial subgraph matches. In practice, corpus maintenance is often delegated to a third party vendor, who has read/write access to the corpus and possibly historic query workload.Such a vendor can turn adversarial and corrupt the corpus. Motivated by this threat, we propose QUPAC, a query workload-guided universal corpus attack, where the adversary perturbs a small subset of corpus graphs once, before the NSR indexes and uses the corrupted corpus for future queries. We formulate the adversary's strategy as worst-case maximization of a ranking loss, jointly over the attacked corpus subset and label-preserving node-pair perturbations on selected victim graphs. We show that this can be cast as a cardinality-constrained set function optimization, which can be approximately solved using a greedy algorithm. However, this requires an exhaustive search over all possible perturbations of the entire corpus. To make the attack scalable, the adversary prunes the ground set using a novel application of approximate nearest neighbor (ANN) search. It first computes a query-specific attack score approximating marginal gain, converts it into an ANN-compatible form and then make the index robust to possible future queries. Experiments across multiple datasets show that QUPAC reduces retrieval quality and outperforms existing attack baselines.