Active Corpus Selection for Training Subgraph Retrievers Using OOD Queries

Neural subgraph retrieval (NSR) models degrade under query distribution shifts, and retraining for each new distribution requires collecting fresh ground-truth labels, each of which entails an NP-hard subgraph-matching instance across a large corpus—making repeated label collection computationally prohibitive. We introduce ACROSS, an active corpus selection framework that, under a fixed solver budget, selects a small corpus subset per out-of-distribution query whose labels suffice for effective NSR training. We prove that allocating the entire budget to retrieving positives is optimal given extreme class imbalance. To enable efficient positive retrieval across arbitrary query distributions, we linearize corpus embeddings around a base model, apply randomized projections to eliminate hinge nonlinearities, and train distribution-shift-tolerant representations via adversarial parameter perturbation. The resulting corpus index is built once and reused across all distributions. Experiments on four molecular graph datasets show ACROSS consistently outperforms six baselines in downstream retrieval accuracy.