A Solver-Efficient Neural Adversarial Attack on Subgraph Matching Models

Neural subgraph matching (NSGM) models are widely used for graph retrieval, where relevance labels for query–corpus pairs are determined by whether the query graph is a subgraph of the corpus graph. Despite widespread applications, the adversarial robustness of such models remains underexplored. In principle, adversarial attacks should induce minimal shift of the instance distribution and the target labels. However, in NSGM, a single edge insertion or deletion can flip relevance labels. Detecting or controlling label flips requires repeated calls to potentially expensive combinatorial solvers. Responding to this challenge, we propose SEAGRAM, a solver-efficient adversarial attack method. It learns to detect non-critical node pairs whose perturbations will likely preserve relevance labels, thereby avoiding solver calls during test time. We further employ an active learning strategy, which reduces the solver calls also during training. Experiments show that SEAGRAM significantly worsens the performance of existing models.