Adversarial Corpus Selection to Attack Subgraph Matching based Graph Retrieval

Neural subgraph retrieval systems, which retrieve corpus graphs containing a query graph as a subgraph, are used in safety-critical applications such as drug discovery, hardware trojan detection, and molecular similarity search. Despite their importance, the adversarial robustness of these systems remains unstudied. We propose GRAP, the first adversarial attack framework targeting subgraph matching-based graph retrieval. \our jointly selects a budget-constrained subset of corpus graphs and computes per-graph edge perturbations to maximally degrade retrieval quality. We formalize two attack regimes: a ranking attack (with solver access) that corrupts pairwise relevance ordering while preserving relevance labels, and a solver-free top-K attack that directly displaces relevant results from retrieved sets. In both cases, we show that the resulting adversarial set functions are monotone and approximately submodular, enabling greedy subset selection with provable approximation guarantees. Experiments on five benchmark datasets against multiple state-of-the-art victim retrievers demonstrate that our method consistently and significantly outperforms all baselines in both gray-box and black-box settings, with and without solver access.