acceptodds
Under review as a conference paper at ICLR 2027

A Pre-Indexing Adversarial Attack on Neural Subgraph Retrievers

10 views

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Neural Subgraph Matching, Graph Adversarial Attacks

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_UBGwOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes QuPAC, a pre-indexing adversarial attack against neural subgraph retrievers (NSRs). Unlike query-specific attacks, QuPAC modifies a limited subset of corpus graphs before indexing, aiming to degrade retrieval performance on future unseen queries. The attack jointly optimizes corpus graph selection and edge perturbations using a historical query workload. The authors formulate this problem as a cardinality-constrained set function optimization and establish conditional monotonicity and approximate submodularity properties. To improve efficiency, they introduce an ANN-based candidate pruning strategy with learned representations and locality-sensitive hashing. Experiments on several graph datasets and NSR architectures demonstrate substantial retrieval performance degradation compared with adapted attack baselines.

Critical strengths
  1. Interesting attack scenario. The paper investigates pre-indexing corpus attacks, which represent a meaningful security concern for neural subgraph retrieval systems. The formulation of a one-time attack that affects multiple future queries is practically relevant.

  2. Reasonably comprehensive evaluation. The experiments cover multiple datasets, victim architectures, and attack settings, including white-box, black-box, and transfer attacks. The reported results demonstrate the effectiveness of the proposed approach under the evaluated conditions.

Critical weaknesses
  1. Insufficient justification of relevance-label preservation for unseen queries. The paper emphasizes that adversarial perturbations should preserve the original relevance labels to ensure attack imperceptibility. However, the non-critical perturbation set in Eq. (2) only guarantees label preservation for the observed query workload. Since subgraph relevance is defined by exact containment, even a single edge modification may change the relevance labels of future unseen queries. This raises a fundamental concern about whether the observed retrieval degradation reflects genuine adversarial misranking or changes in the underlying ground-truth relevance relationships. The paper does not sufficiently investigate this issue, which directly affects the validity of the proposed pre-indexing attack formulation and its evaluation.

  2. The theoretical guarantees are not sufficiently connected to the practical algorithm. The monotonicity and approximate submodularity results in Theorem 1 rely on restrictive assumptions, particularly the non-negativity of query-specific attack scores across admissible perturbations and additional conditions on positive-negative graph pairs. These assumptions may not hold when a corpus graph participates in different queries with conflicting relevance objectives, and their validity is not empirically examined. More importantly, the approximation guarantee applies to greedy optimization over the original ground set, whereas the practical QuPAC algorithm operates on an ANN-pruned candidate set using approximated attack scores. The paper does not establish whether the theoretical properties or approximation guarantees remain meaningful under this pruning procedure, weakening the theoretical justification for the proposed efficient attack.

  3. Insufficient evidence supporting the claimed scalability and computational efficiency. A central motivation for QuPAC is the prohibitive cost of searching over corpus graphs and their possible edge perturbations. However, the proposed ANN-based approach still requires preprocessing candidate perturbations and constructing an index over their representations. As described in Algorithm 3, this process involves potentially quadratic numbers of node-pair modifications for each corpus graph, introducing substantial offline computation and storage requirements. The experiments primarily report retrieval performance degradation, without sufficient end-to-end runtime, memory consumption, or preprocessing cost comparisons. Consequently, it remains unclear whether the proposed approach provides a meaningful computational advantage over direct greedy optimization, particularly for large-scale graph corpora.

Questions for authors
  1. How do the authors ensure that the selected edge perturbations preserve relevance labels for unseen queries? Are ground-truth labels recomputed on the modified corpus when evaluating MAP?

  2. Can the authors empirically examine the assumptions underlying Theorem 1 and clarify whether any approximation guarantees extend to the ANN-pruned optimization used by QuPAC?

  3. Can the authors provide end-to-end runtime and memory comparisons, including candidate perturbation preprocessing, ANN index construction, and greedy optimization, across different corpus sizes?

4 comments
AuthorsOpenReview ↗

Response to reviewer UBGw (1)

We thank the reviewer for their suggestions which will improve the paper. We address the reviewer concerns below and also add the discussion to the paper.

Insufficient justification of relevance-label preservation for unseen queries. … How do the authors ensure that the selected edge perturbations preserve relevance labels for unseen queries? Are ground-truth labels recomputed on the modified corpus when evaluating MAP?

The reviewer has raised an important concern and we clarify this by discussing the evaluation protocol for the victim NSR on the perturbed corpus.

Adjustment of ground truth relevance labels. The adversary computes (S,δc)(S, \\{\delta _c\\}) based on the historic query workload QQ, and applies the same set of perturbations δc\\{\delta _c\\} to the corpus subset SS for all the unseen queries Q∗Q^*. The computed δj∈δc\delta _j \in \\{\delta _c\\} are chosen such that δj∈∩q∈QΓqj\delta _j \in \cap _{q \in Q}\Gamma _{qj}, that is, relevance labels are preserved for perturbed corpus items. However, since Q∗Q^* is not accessible during the computation of (S,δc)(S, \\{\delta _c\\}), we expect to see this label preservation to be violated for some unseen queries, that is, ∃q∈Q∗,δj∉Γqj\exists q \in Q^*, \delta _j \not\in \Gamma _{qj}. To ensure that the victim NSR ranking quality is assessed fairly, we enforce that the evaluation be correct with respect to the perturbed corpus. For this purpose, we recompute the true relevance labels for all corpus items. The updated set of relevance labels is computed as y(Gq,Gˉc) ∣ Gˉc∈GS,δc∣c∈S\\{y(G _q, \bar{G} _c) \ |\ \bar{G} _c \in \mathcal{G} _{S,\\{ \delta _c | c\in S \\}} \\}, and the victim model's ranking quality is evaluated using this set as the ground truth.

We report the shift in relevance ratio for different attack methods in the whitebox setting. The victim model is Isonet++ (Edge). This is computed as 1∣Q∗∣∑q∈Q∗∣∣{Gc⊕∈G ∣ y(Gq,Gc⊕)=+1}∣−∣{Gc⊕∈GS,δc ∣ c∈S ∣ y(Gq,Gc⊕)=+1}∣∣∣G∣.\frac{1}{|Q^*|}\sum _{q \in Q^*}\frac{\bigl| |\{G _{c _\oplus} \in \mathcal{G} \ | \ y(G _q, G _{c _\oplus}) = +1 \}| - |\{G _{c _\oplus} \in \mathcal{G} _{S,\\{\delta _c \ | \ c\in S\\}} \ | \ y(G _q, G _{c _\oplus}) = +1 \}| \bigr|}{|\mathcal{G}|}. The values in the following table are the change in fraction of positive-relevance query-corpus pairs due to perturbations, averaged across the unseen queries Q* and across 5 different query workloads, for 4 datasets (FM, FR, MM, MR) and 2 budgets B∈40,80B \in\\{40, 80\\}.

MethodFM (B=40)FM (B=80)FR (B=40)FR (B=80)MM (B=40)MM (B=80)MR (B=40)MR (B=80)
Nettack0.000 ± 0.0000.001 ± 0.0000.000 ± 0.0000.001 ± 0.0000.000 ± 0.0000.001 ± 0.0000.000 ± 0.0000.001 ± 0.000
GMA0.001 ± 0.0000.002 ± 0.0000.001 ± 0.0000.002 ± 0.0010.001 ± 0.0000.003 ± 0.0000.001 ± 0.0000.002 ± 0.000
RL-Attack0.001 ± 0.0000.001 ± 0.0010.000 ± 0.0000.001 ± 0.0000.000 ± 0.0000.001 ± 0.0010.002 ± 0.0010.005 ± 0.002
AGGD0.001 ± 0.0000.003 ± 0.0000.001 ± 0.0000.002 ± 0.0010.001 ± 0.0000.002 ± 0.0000.001 ± 0.0000.002 ± 0.000
IAP0.002 ± 0.0010.002 ± 0.0010.001 ± 0.0000.003 ± 0.0000.001 ± 0.0000.001 ± 0.0010.002 ± 0.0010.002 ± 0.001
QuPAC (Greedy)0.002 ± 0.0010.005 ± 0.0020.002 ± 0.0010.005 ± 0.0020.002 ± 0.0010.006 ± 0.0020.003 ± 0.0020.007 ± 0.003
QuPAC (ANN)0.003 ± 0.0020.006 ± 0.0040.003 ± 0.0010.005 ± 0.0020.002 ± 0.0000.004 ± 0.0010.003 ± 0.0010.007 ± 0.002

We observe that the shift in the distribution of positive corpus graphs is small. Additionally, we run an experiment where, during query time, we choose to score against the clean graph rather than perturbed, if the underlying perturbation alters the relevance label. This ensures that the ground truth is preserved even for unseen queries. We observe in the following tables that our methods perform better. (Tables below for WB setting, IE++.)

AIDS (MAP: lower is better):

B/|D|→0.0250.1250.250.6251
RL-Attack0.8740.8660.8200.7230.723
QuPAC (ANN)0.8610.8050.7470.5690.486
QuPAC (Greedy)0.8640.8020.7200.5690.486

FM (MAP: lower is better):

B/|D|→0.0250.1250.250.6251
RL-Attack0.8910.8880.8770.7870.787
QuPAC (ANN)0.8700.8210.7670.6360.580
QuPAC (Greedy)0.8670.7990.7400.6350.579

FR (MAP: lower is better):

B/|D|→0.0250.1250.250.6251
RL-Attack0.8760.8690.8460.7730.773
QuPAC (ANN)0.8500.7940.7480.6530.608
QuPAC (Greedy)0.8390.7810.7420.6520.608

MM (MAP: lower is better):

B/|D|→0.0250.1250.250.6251
RL-Attack0.8720.8660.8330.7580.758
QuPAC (ANN)0.8530.7850.7320.6340.560
QuPAC (Greedy)0.8380.7710.7220.6330.559

MR (MAP: lower is better):

B/|D|→0.0250.1250.250.6251
RL-Attack0.8880.8770.8550.8080.808
QuPAC (ANN)0.8840.8400.8080.7360.692
QuPAC (Greedy)0.8700.8330.8010.7360.692
AuthorsOpenReview ↗

Response to reviewer UBGw (2)

The theoretical guarantees are not sufficiently connected to the practical algorithm. The monotonicity and approximate submodularity results in Theorem 1 rely on restrictive assumptions, particularly the non-negativity of query-specific attack scores across admissible perturbations and additional conditions on positive-negative graph pairs. These assumptions may not hold when a corpus graph participates in different queries with conflicting relevance objectives, and their validity is not empirically examined.

Following table reports the fraction of triples (q,c,δc)(q,c,\delta_c) for which Aq(c,δc)≥0A_q(c, \delta_c) \ge 0 is satisfied across the selections made by QuPAC (ANN). The table is for victim IsoNet++ (Edge) with B=800B = 800.

DatasetAcross Γc\Gamma _cQuPAC selections
AIDS0.7110.829
FM0.7200.881
FR0.7210.877
MM0.6930.832
MR0.6770.841

We see that the condition is violated in under 18% of the cases.

Assumption 1 is sufficient to prove alpha-submodularity but not necessary. Even for instances where this assumption does not hold true, alpha-submodularity is still satisfied with the following observed values of α\alpha.

Datasetmin α\alphamedian α\alpha
AIDS0.760.86
FM0.640.80
FR0.760.85
MM0.770.87
MR0.660.86

Even when assumption 1 fails, the objective has α\alpha in range 0.64-0.77, consistent with Theorem 1, indicating β0\beta _0 is conservative in practice.

Assumption 2: This assumption exactly holds by construction for all six NSRs. The relevance distance computed by NSR retrievers is independent across distinct corpus graphs. Correspondingly, the relevance distance computed for perturbed corpus graph is independent of the perturbations of other corpus graphs.

Assumption 3: We show above (in the table) that the empirical α\alpha values are in the range 0.640.64―0.770.77 in practice and that the β\beta condition is a worst case lower bound on α\alpha.

Assumption 4: We compute the fraction of instances for which the standalone gain ΔF(c∣∅,Q)\Delta _F (c | \emptyset, Q) is strictly positive.

DatasetFraction where ΔF(c∣∅,Q)>0\Delta _F(c \mid \emptyset, Q) > 0
AIDS0.994
FM0.998
FR0.998
MM0.995
MR0.989

Clearly, this assumption is almost always satisfied across all datasets.

More importantly, the approximation guarantee applies to greedy optimization over the original ground set, whereas the practical QuPAC algorithm operates on an ANN-pruned candidate set using approximated attack scores. ... clarify whether any approximation guarantees extend to the ANN-pruned optimization used by QuPAC?

Suppose SANNS _{\text{ANN}} is the subset given by ANN and SGreedyS _{\text{Greedy}} is the subset given by the greedy algorithm. Following table shows the approximation ratio in terms of the ratio F(SANN)/F(SGreedy)F(S _{\text{ANN}})/F(S _{\text{Greedy}}), where F is pairwise ranking objective as defined in Eq. (5) in the paper. We observe that the ANN objective is comparable with greedy objective.

DatasetB/|D| = 0.125B/|D| = 0.25B/|D| = 0.625B/|D| = 1.0
AIDS0.7570.8411.0001.000
FM0.6790.8261.0001.000
FR0.7360.8131.0001.000
MM0.6960.8151.0001.000
MR0.7540.9171.0001.000
AuthorsOpenReview ↗

Response to reviewer UBGw (3)

Insufficient evidence supporting the claimed scalability and computational efficiency. A central motivation for QuPAC is the prohibitive cost of searching over corpus graphs and their possible edge perturbations. However, the proposed ANN-based approach still requires preprocessing candidate perturbations and constructing an index over their representations. As described in Algorithm 3, this process involves potentially quadratic numbers of node-pair modifications for each corpus graph, introducing substantial offline computation and storage requirements. The experiments primarily report retrieval performance degradation, without sufficient end-to-end runtime, memory consumption, or preprocessing cost comparisons. Consequently, it remains unclear whether the proposed approach provides a meaningful computational advantage over direct greedy optimization, particularly for large-scale graph corpora.

Can the authors provide end-to-end runtime and memory comparisons, including candidate perturbation preprocessing, ANN index construction, and greedy optimization, across different corpus sizes?

We compare the end-to-end running time of the greedy algorithm of QuPAC (ANN) and QuPAC (Greedy) across all datasets. We report the time (in hours) required to compute the attacked set S,δcS, \\{\delta _c \\} for corpus of size 100k, IsoNet++ (Edge) victim on budgets B∈1000,2000,5000,10000B \in \\{ 1000, 2000, 5000, 10000\\}. A runtime is reported as DNF if it did not finish within 24 hours.

AIDSB=1000B=2000B=5000B=10000
QuPAC(ANN)0.702.408.3820.28
QuPAC(Greedy)7.10DNFDNFDNF
FMB=1000B=2000B=5000B=10000
QuPAC(ANN)0.852.8712.3822.83
QuPAC(Greedy)7.57DNFDNFDNF
FRB=1000B=2000B=5000B=10000
QuPAC(ANN)1.102.5612.6719.40
QuPAC(Greedy)7.14DNFDNFDNF
MMB=1000B=2000B=5000B=10000
QuPAC(ANN)0.702.489.7719.64
QuPAC(Greedy)5.7510.46DNFDNF
MRB=1000B=2000B=5000B=10000
QuPAC(ANN)0.612.218.5718.15
QuPAC(Greedy)5.299.61DNFDNF

We observe that: (1) QuPAC (ANN) is significantly faster than QuPAC (Greedy), about 6-10x faster for B=1000B=1000 across all datasets while the speedup remains around 4x for B=2000B=2000. This highlights the benefit of the ANN in QuPAC. (2) QUPAC (Greedy) does not finish in a reasonable time for the remaining budgets in case of AIDS, FM and FR datasets.

For indexing 100K corpus, our method took ≈100\approx 100 seconds and requires ≈13\approx 13GB (similar to raw dataset size) of space on disk with a preprocessing time of ≈50\approx 50 minutes.

Reviewer_UBGwOpenReview ↗

Official Comment by reviewer UBGw

Thanks for the detailed rebuttal. I am now more confident in the paper's merits and have decided to raise my rating.

Reviewer_fvEUOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes QUPAC, a pre-indexing adversarial attack on neural subgraph retrievers (NSRs), which rank corpus graphs by how well a query fits inside them. The threat is a compromised corpus vendor which uses only a log of past queries and perturbs a small subset of corpus graphs once (one edge each) before indexing so that the retrieval quality drops on all future queries. The attack is cast as a budget-constrained set-function maximization over the subset and its edge flips. Because the greedy search is costly, the authors prune the candidate set once with approximate nearest neighbor (ANN) search. They first define an "attack score" that approximates how much each candidate graph-and-edit would degrade retrieval. They then rewrite the retriever's relevance distance so this score fits a standard inner-product index, which makes the search fast. Finally, they train a neural surrogate of the score with a min–max objective, so the selected perturbations stay effective on unseen queries rather than only on the past query log.

Critical strengths
  1. The formulation is clean. The attack is a size-budgeted set-function maximization, with a proof of monotonicity and approximate submodularity and a greedy guarantee.
  2. The proposed scalability method cuts a costly greedy scan over the full corpus down to a fast ANN lookup. An attack score approximates each candidate's marginal gain, the relevance distance is rewritten into an inner-product form an ANN index can use, and a min–max step keeps the selection effective on unseen queries. Approximation results support each step.
Critical weaknesses
  1. The threat model is not well presented.
  2. The effect of the attack is modest for such a strong adversary. The adversary has corpus write access, a subgraph solver, and a query log, yet mean average precision drops only about 17 percent. The bar for a successful attack should be higher given this power.
  3. The scalability claim is not tested at scale. The selling point is efficiency on large corpora, but the datasets are small molecular graphs. The ANN benefit is not shown where it would matter.
Questions for authors
  1. How does your set-function formulation and greedy guarantee differ from prior and concurrent NSR corpus attacks that use the same monotone, approximately-submodular framing? What remains new beyond the pre-indexing framing and the ANN step?
  2. Can you report/comment on the runtime and attack quality on a large corpus?
  3. How does the proposed attack compare with other simple baselines such as corrupting the highest-degree or highest-relevance corpus graphs?
5 comments
AuthorsOpenReview ↗

Response to reviewer fvEU (1)

We thank the reviewer for their suggestions which will improve the paper. We address the reviewer concerns below and also add the discussion to the paper.

The threat model is not well presented.

Sorry for this. We discuss it as follows. We analyze threat model in terms of access to the victim NSR, access to historic query workload and pre-indexing attack scheme. We provide more details of the adversary threat model below:

(1) Global attack: The adversary attacks the corpus based on a query workload, unlike a targeted attack where the objective is to degrade the performance on a single query. Hence the adversary aims to degrade the victim's ranking performance on future queries Q∗Q^* anticipated to be drawn from the same distribution as the workload sample. The ideal adversarial objective is

min⁡S,δc1∣Q∗∣∑q∈Q∗APθ∗(Gq,GS,δc).\min_{S, \\{ \delta_c \\} } \frac{1}{|Q^*|} \sum_{q \in Q^*} AP_{\theta^*} (G_q, \mathcal{G}_{S, \\{ \delta_c \\}}).

Since Q∗Q^* is unobserved, the true victim NSR θ∗\theta^* is unavailable and AP is a non-differentiable objective, the adversary optimizes the surrogate in Eqs. (3)-(4) in the paper, pairwise ranking loss computed over the substitute dθd_\theta aggregated over the observed workload QQ.

(2) Adversary's knowledge: The adversary has access to the clean corpus Gc:c∈C\\{ G_c : c \in C \\}, historical query workload QQ which is distinct from the future query workload Q∗Q^*, combinatorial subgraph matching solver for computing true relevance relation y(Gq,Gc)y(G_q, G_c). In the whitebox setting, adversary has access to the victim parameters θ∗\theta^*.

(3) Imperceptibility: The adversary is restricted in the scale of change it can cause to the corpus. The adversary restricts itself to non critical perturbations δc∈Γc=⋂q∈QΓqc\delta_c \in \Gamma_c = \bigcap_{q \in Q} \Gamma_{qc} of the query workload and hence preserves the ground truth relevance y(Gq,Gc)y(G_q, G_c) for every workload query. Moreover, the adversary operates under a budget restriction of perturbing at most BB node pairs in the corpus and at most one node pair edited per corpus graph.

The effect of the attack is modest for such a strong adversary. The adversary has corpus write access, a subgraph solver, and a query log, yet mean average precision drops only about 17 percent. The bar for a successful attack should be higher given this power.

The number 17% is the minimum MAP drop across all possible datasets for the late interaction model family (IsoNet (Node) for example). Over all models, the performance degradation is much larger (as large as > 50% in some cases). Following tables show MAP drop in percentages.

Victim: GEN (%drop in MAP: higher is better)

DatasetB/∥D∥=0.25B/\|D\|=0.25B/∥D∥=0.625B/\|D\|=0.625B/∥D∥=1.0B/\|D\|=1.0
AIDS40.955.860.5
FM41.959.765.1
FR39.256.961.7
MM41.859.162.9
MR43.761.465.6

Victim: GMN (%drop in MAP: higher is better)

DatasetB/∥D∥=0.25B/\|D\|=0.25B/∥D∥=0.625B/\|D\|=0.625B/∥D∥=1.0B/\|D\|=1.0
AIDS29.649.055.9
FM20.733.642.3
FR20.835.240.9
MM28.044.549.2
MR22.340.648.5

Victim: IsoNet (Edge) (%drop in MAP: higher is better)

DatasetB/∥D∥=0.25B/\|D\|=0.25B/∥D∥=0.625B/\|D\|=0.625B/∥D∥=1.0B/\|D\|=1.0
AIDS27.644.951.4
FM22.639.544.4
FR21.936.943.7
MM29.743.245.2
MR18.232.138.1

Victim: IsoNet (Node) (%drop in MAP: higher is better)

DatasetB/∥D∥=0.25B/\|D\|=0.25B/∥D∥=0.625B/\|D\|=0.625B/∥D∥=1.0B/\|D\|=1.0
AIDS29.545.951.5
FM27.146.550.0
FR18.030.439.9
MM25.945.849.8
MR28.446.951.9

Victim: IsoNet++ (Edge) (%drop in MAP: higher is better)

DatasetB/∥D∥=0.25B/\|D\|=0.25B/∥D∥=0.625B/\|D\|=0.625B/∥D∥=1.0B/\|D\|=1.0
AIDS12.830.638.0
FM13.826.632.0
FR14.124.829.6
MM15.725.632.3
MR9.016.921.1

Victim: IsoNet++ (Node) (%drop in MAP: higher is better)

DatasetB/∥D∥=0.25B/\|D\|=0.25B/∥D∥=0.625B/\|D\|=0.625B/∥D∥=1.0B/\|D\|=1.0
AIDS18.236.341.9
FM18.630.934.9
FR13.124.130.1
MM17.427.132.2
MR13.623.429.2
AuthorsOpenReview ↗

Response to reviewer fvEU (2)

The scalability claim is not tested at scale Can you report/comment on the runtime and attack quality on a large corpus?

We generated 100K corpus graphs by sampling graphs with replacement from the original corpora, which resulted in a large corpus. Then we run greedy algorithm which did not finish (DNF) before 24 hours in majority of the cases. Following tables show the time in hours.

AIDSB=1000B=2000B=5000B=10000
QuPAC(ANN)0.702.408.3820.28
QuPAC(Greedy)7.10DNFDNFDNF
FMB=1000B=2000B=5000B=10000
QuPAC(ANN)0.852.8712.3822.83
QuPAC(Greedy)7.57DNFDNFDNF
FRB=1000B=2000B=5000B=10000
QuPAC(ANN)1.102.5612.6719.40
QuPAC(Greedy)7.14DNFDNFDNF
MMB=1000B=2000B=5000B=10000
QuPAC(ANN)0.702.489.7719.64
QuPAC(Greedy)5.7510.46DNFDNF
MRB=1000B=2000B=5000B=10000
QuPAC(ANN)0.612.218.5718.15
QuPAC(Greedy)5.299.61DNFDNF

We observe that: (1) QuPAC (ANN) is significantly faster than QuPAC (Greedy), about 6-10x faster for B=1000B=1000 across all datasets while the speedup remains around 4x for B=2000B=2000. This highlights the benefit of the ANN in QuPAC. (2) QUPAC (Greedy) does not finish in a reasonable time for the remaining budgets in case of AIDS, FM and FR datasets.

We also experiment with a new dataset with moderately larger corpus (2000 graphs) with larger graph size. Following table shows MAP, which reveals that ANN performs comparably with greedy algorithm.

COX2B/|D| = 0.1B/|D| = 0.25B/|D| = 0.5B/|D| = 1
QuPAC(ANN)0.80940.70730.57070.4431
QuPAC(Greedy)0.79970.70220.57030.4431

We see that QuPAC (ANN) and QuPAC (Greedy) show near-equivalent MAP degradation.

How does your set-function formulation and greedy guarantee differ from prior and concurrent NSR corpus attacks

We assume you are comparing the scenario of a query-time attack tailored to a query, against our submission that attacks the corpus prior to indexing, without knowledge of specific queries when deployed. Our submission establishes that "the pre-indexing framing" introduces substantial new technical difficulties. Perturbation δc\delta_c for corpus graph GcG_c must now be chosen based on, and budgeted across, a query workload. The adaptation of ANN search to reducing the ground set is also novel, to our knowledge, as is the technique to improve attack robustness to unseen queries. Without these innovations, a per-query deployment-time attacker (a substantially easier problem with very easy attack objective) could simply not succeed with an offline pre-indexing attack setup.

How does the proposed attack compare with other simple baselines such as corrupting the highest-degree or highest-relevance corpus graphs?

We report the adversarial performance of these methods (namely Top-Degree(B) and Top+(B)) and compare them to QuPAC (ANN) across all datasets and budgets. We observe that we perform better.

AIDS (WB, IE++, MAP: lower is better):

B/|D|→0.0250.050.06250.10.1250.250.6251
Top-Degree(B)0.870.870.870.870.870.860.830.81
Top(+)B0.870.860.860.850.850.810.630.60
QuPAC (ANN)0.860.850.840.820.810.760.610.54

FM (WB, IE++, MAP: lower is better):

B/|D|→0.0250.050.06250.10.1250.250.6251
Top-Degree(B)0.890.880.880.870.870.860.830.82
Top+(B)0.880.870.860.850.850.800.700.70
QuPAC (ANN)0.870.860.850.830.820.770.650.61

FR (WB, IE++, MAP: lower is better):

B/|D|→0.0250.050.06250.10.1250.250.6251
Top-Degree(B)0.880.880.880.870.870.860.830.83
Top+(B)0.870.860.860.850.850.820.740.74
QuPAC (ANN)0.850.830.820.810.800.750.660.62

MM (WB, IE++, MAP: lower is better):

B/|D|→0.0250.050.06250.10.1250.250.6251
Top-Degree(B)0.870.870.870.870.860.840.800.79
Top+(B)0.860.850.850.840.830.800.750.74
QuPAC (ANN)0.850.830.820.800.790.740.650.59

MR (WB, IE++, MAP: lower is better):

B/|D|→0.0250.050.06250.10.1250.250.6251
Top-Degree(B)0.890.890.890.880.880.870.860.85
Top+(B)0.880.880.880.870.860.840.770.76
QuPAC (ANN)0.880.870.870.860.840.810.740.70
AuthorsOpenReview ↗

Additional results for degree based and relevance score based baselines

In addition to the datasets above, we compare our method against top degree based Top-Degree(B) and high relevance score based Top+(B) baselines on more challenging COX2 dataset. Below, we present results. We observe that QuPAC (ANN) significantly outperforms the baselines. Top+(B) yields stronger ranking degradation compared to Top-Degree(B).

COX2 (WB, IE++, MAP; lower is better)

MethodB/|D| = 0.1B/|D| = 0.25B/|D| = 0.5B/|D| = 1
Top-Degree(B)0.89030.88600.87190.8338
Top+(B)0.85950.80790.71070.6478
QuPAC(ANN)0.80940.70730.57070.4431
Reviewer_rnvGOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a new and practically motivated threat model for neural subgraph retrievers (NSRs): a one-time, pre-indexing, universal corpus poisoning attack by a third-party vendor with read/write access to the corpus and a sample of historical (workload) queries. The proposed method, QUPAC, jointly selects a small subset of corpus graphs and a single imperceptible (single-edge) perturbation per selected graph to maximize a workload-aggregated pairwise ranking loss, while preserving ground-truth relevance labels on the observed workload. The joint selection is cast as a cardinality-constrained set function maximization shown to be monotone and approximately submodular, enabling a greedy algorithm; to scale, QUPAC introduces an ANN-backed pruning strategy based on a query-specific attack score that approximates greedy marginal gain via randomized hinge-to-dot-product embeddings and a robustness-enhancing representation trained with min–max parameter perturbations. Experiments on multiple TUDatasets and several NSR models show consistent MAP degradation, outperforming adapted baselines in white-, black-box, and transfer settings.

Critical strengths
  1. The pre-indexing, universal poisoning setting for NSR retrieval is novel and practically relevant, distinct from per-query evasion or training-time poisoning.

  2. Evaluations cover multiple datasets, several NSR architectures (IsoNet, IsoNet++, GMN), and three threat regimes (white-box, black-box, transfer), with consistent improvements over adapted baselines.

  3. Highlights an underexplored but realistic attack surface in graph retrieval systems with split ownership over corpus maintenance vs. indexing/search.

Critical weaknesses
  1. Theoretical guarantees rely on assumptions that are strong or opaque in practice (e.g., A_q(c, δ) ≥ 0 for all δ ∈ Γc and a β0-margin condition), and it is unclear when these hold for realistic NSR distances and corpora.

  2. Evaluation focuses on MAP; other retrieval metrics (e.g., Recall@K, nDCG@K, Precision@K) and top-K analysis more aligned with practical NSR use are missing.

Questions for authors
  1. How often is the assumption A_q(c, δ) ≥ 0 satisfied in practice for δ ∈ Γc? Can you report empirical frequencies and the effect of removing this assumption on Theorem 1’s monotonicity/submodularity claims?

  2. Can you quantify the submodularity ratio and curvature of F(S, Q) empirically on your datasets to complement the β0-condition, and compare greedy against stochastic/lazier greedy variants?

5 comments
AuthorsOpenReview ↗

Response to reviewer rnvG (1)

We thank the reviewer for their suggestions which will improve the paper. We here address the reviewer concerns below and also added the discussions to the paper.

assumptions that are strong or opaque.. it is unclear when these hold for realistic NSR distances and corpora. … How often is the assumption A_q(c, δ) ≥ 0 satisfied in practice for δ ∈ Γc?

Following table reports the fraction of triples (q,c,δc)(q,c,\delta_c) for which Aq(c,δc)≥0A_q(c, \delta_c) \ge 0 is satisfied across the selections made by QuPAC (ANN). The table is for victim IsoNet++ (Edge) with B=800B = 800.

DatasetAcross Γc\Gamma_cQuPAC selections
AIDS0.7110.829
FM0.7200.881
FR0.7210.877
MM0.6930.832
MR0.6770.841

We see that the condition is violated in under 18% of the cases across the QuPAC (ANN) selections.

Can you report empirical frequencies and the effect of removing this assumption on Theorem 1’s monotonicity/submodularity claims?

Assumption 1 is sufficient to prove alpha-submodularity but not necessary. Even for instances where this assumption does not hold true, alpha-submodularity is still satisfied with the following observed values of α\alpha.

Datasetmin α\alphamedian α\alpha
AIDS0.760.86
FM0.640.80
FR0.760.85
MM0.770.87
MR0.660.86

Even when assumption 1 fails, the objective has α\alpha in range 0.64-0.77, consistent with Theorem 1, indicating β0\beta_0 is conservative in practice.

Assumption 2: This assumption exactly holds by construction for all six NSRs. The relevance distance computed by NSR retrievers is independent across distinct corpus graphs. Correspondingly, the relevance distance computed for perturbed corpus graph is independent of the perturbations of other corpus graphs.

Assumption 3: We show above (in the table) that the empirical α\alpha values are in the range 0.640.64―0.770.77 in practice and that the β0\beta_0 condition is a worst case lower bound on α\alpha.

Assumption 4: We compute the fraction of instances for which the standalone gain ΔF(c∣∅,Q)\Delta_F (c | \emptyset, Q) is strictly positive.

DatasetFraction where ΔF(c∣∅,Q)>0\Delta_F(c \mid \emptyset, Q) > 0
AIDS0.994
FM0.998
FR0.998
MM0.995
MR0.989

Clearly, this assumption is almost always satisfied across all datasets.

Can you quantify the submodularity ratio and curvature of F(S, Q) empirically on your datasets...

We empirically measure the submodularity ratio for different datasets. Following table reports results for substitute NSR IsoNet++ (Edge). We observe that the values of submodularity ratio are moderate to high.

Datasetmin α\alphamedian α\alpha
AIDS0.760.86
FM0.640.80
FR0.760.85
MM0.770.87
MR0.660.86

Below, we report the max and median curvature across all datasets and for substitute NSR IsoNet++ (Edge).

Datasetmax curvaturemedian curvature
AIDS0.110.07
FM0.140.09
FR0.160.10
MM0.180.07
MR0.200.14

We see that the curvature remains lower than 0.20.2 with the median remaining ≤0.14\le 0.14.

Compare greedy against stochastic/lazier greedy variants?

Following table shows results for our method, stochastic and lazier greedy variant, which shows that we perform better in all except MR dataset.

AIDS (White Box, IE++, MAP: lower is better):

AIDSB=1000B=2000B=5000B=10000
Lazy greedy0.8680.8610.8420.812
Stochastic greedy0.8680.8610.8430.812
QuPAC (ANN)0.8680.8620.8400.803

FM (White Box, IE++, MAP: lower is better):

FMB=1000B=2000B=5000B=10000
Lazy greedy0.8840.8770.8570.830
Stochastic greedy0.8840.8770.8580.830
QuPAC (ANN)0.8790.8690.8520.828

FR (White Box, IE++, MAP: lower is better):

FRB=1000B=2000B=5000B=10000
Lazy greedy0.8680.8610.8410.815
Stochastic greedy0.8680.8610.8420.814
QuPAC (ANN)0.8490.8490.8180.799

MM (White Box, IE++, MAP: lower is better):

MMB=1000B=2000B=5000B=10000
Lazy greedy0.8650.8580.8380.807
Stochastic greedy0.8650.8580.8370.806
QuPAC (ANN)0.8650.8560.8210.787

MR (White Box, IE++, MAP: lower is better):

MRB=1000B=2000B=5000B=10000
Lazy greedy0.8840.8800.8680.850
Stochastic greedy0.8840.8800.8680.850
QuPAC (ANN)0.8850.8820.8710.850
AuthorsOpenReview ↗

Response to reviewer rnvG (2)

other retrieval metrics (e.g., Recall@K, nDCG@K, Precision@K) .

We compare the adversarial performance of QuPAC (ANN) with other baselines in White Box setting on IsoNet++ (Edge), across all datasets in terms of NDCG@40, Recall@40, Precision@40. We observe that we perform better.

NDCG@40:

AIDS (WB, IE++, NDCG@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.930.930.930.920.81
GMA0.930.930.930.930.93
RL-Attack0.930.930.920.880.88
AGGD0.930.930.930.930.93
IAP0.930.930.930.930.93
QuPAC (ANN)0.900.890.870.750.68

FM (WB, IE++, NDCG@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.960.960.960.930.86
GMA0.960.960.960.940.94
RL-Attack0.960.960.950.920.92
AGGD0.960.960.960.950.95
IAP0.950.950.950.960.95
QuPAC (ANN)0.920.920.890.790.73

FR (WB, IE++, NDCG@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.950.950.950.940.91
GMA0.950.950.950.940.95
RL-Attack0.950.950.930.910.91
AGGD0.950.950.950.950.95
IAP0.950.950.950.950.95
QuPAC (ANN)0.870.870.840.790.77

MM (WB, IE++, NDCG@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.960.960.960.950.90
GMA0.960.960.960.950.96
RL-Attack0.960.960.950.910.91
AGGD0.960.960.960.960.96
IAP0.960.960.960.960.96
QuPAC (ANN)0.900.890.850.800.73

MR (WB, IE++, NDCG@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.950.950.950.940.91
GMA0.950.950.950.950.95
RL-Attack0.950.950.940.950.95
AGGD0.950.950.950.950.95
IAP0.950.950.950.950.94
QuPAC (ANN)0.930.900.890.850.82

Precision@40:

AIDS (WB, IE++, Precision@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.920.920.920.900.79
GMA0.920.920.920.910.91
RL-Attack0.920.920.900.870.87
AGGD0.920.920.920.920.92
IAP0.920.920.920.920.92
QuPAC (ANN)0.890.880.860.730.66

FM (WB, IE++, Precision@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.950.950.950.920.84
GMA0.950.950.950.930.93
RL-Attack0.950.950.950.910.91
AGGD0.950.950.950.940.95
IAP0.950.950.950.950.94
QuPAC (ANN)0.910.900.870.760.72

FR (WB, IE++, Precision@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.930.930.930.920.89
GMA0.930.930.930.930.93
RL-Attack0.930.930.910.890.89
AGGD0.930.930.930.930.93
IAP0.930.930.930.930.93
QuPAC (ANN)0.860.860.830.770.75

MM (WB, IE++, Precision@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.940.940.940.930.88
GMA0.940.940.940.940.95
RL-Attack0.940.950.930.890.89
AGGD0.940.940.940.940.94
IAP0.940.940.940.940.94
QuPAC (ANN)0.870.870.840.790.72

MR (WB, IE++, Precision@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.940.940.940.930.90
GMA0.940.940.940.940.94
RL-Attack0.940.940.930.940.94
AGGD0.940.940.940.940.94
IAP0.940.940.940.940.94
QuPAC (ANN)0.920.890.870.830.80

Recall@40:

AIDS (WB, IE++, Recall@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.290.300.310.330.27
GMA0.300.300.310.340.34
RL-Attack0.290.290.280.250.25
AGGD0.290.290.280.270.26
IAP0.290.290.290.290.29
QuPAC (ANN)0.270.270.250.190.15

FM (WB, IE++, Recall@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.330.330.340.350.32
GMA0.330.330.340.370.38
RL-Attack0.330.330.320.290.29
AGGD0.320.320.320.300.29
IAP0.320.320.320.320.32
QuPAC (ANN)0.310.300.280.220.20

FR (WB, IE++, Recall@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.320.320.330.380.37
GMA0.320.330.330.370.38
RL-Attack0.320.310.300.270.27
AGGD0.320.320.320.320.32
IAP0.320.320.320.320.32
QuPAC (ANN)0.290.290.270.230.21

MM (WB, IE++, Recall@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.300.300.300.320.31
GMA0.300.300.310.340.35
RL-Attack0.290.290.280.250.25
AGGD0.290.290.290.280.27
IAP0.290.290.290.290.29
QuPAC (ANN)0.260.260.240.200.17

MR (WB, IE++, Recall@40: lower is better):

B/|D|→0.10.1250.250.6251
Nettack0.320.320.320.360.35
GMA0.320.320.330.360.37
RL-Attack0.310.310.300.280.28
AGGD0.310.310.310.300.29
IAP0.310.310.300.300.30
QuPAC (ANN)0.300.290.280.240.22
AuthorsOpenReview ↗

Other metrics on new dataset

We provide additional results on the COX2 dataset, which has larger corpus (2000 graphs) and larger graphs. We compare QuPAC with the best performing baseline (RL-Attack) on this dataset in the following tables. We present results across B/∣D∣∈0.1,0.25,0.5,1.0B/|D| \in \\{ 0.1, 0.25, 0.5, 1.0 \\}, victim NSR IsoNet++ (Edge) and in terms of MAP, NDCG @40, Precision@40 and Recall@40. We see that QuPAC outperforms RL-Attack with a significant margin and achieves strong ranking degradation at full budget.

COX2 (WB, IE++, MAP; lower is better)

MethodB/|D|=0.1B/|D|=0.25B/|D|=0.5B/|D|=1
RL_Attack0.82020.76950.72040.7029
QuPAC(ANN)0.80940.70730.57070.4431
QuPAC(Greedy)0.79970.70220.57030.4431

COX2 (WB, IE++, NDCG@40; lower is better)

MethodB/|D|=0.1B/|D|=0.25B/|D|=0.5B/|D|=1
RL_Attack0.83250.80640.80210.7981
QuPAC(ANN)0.81580.73780.65130.5748
QuPAC(Greedy)0.78360.72720.65440.5748

COX2 (WB, IE++, Precision@40; lower is better)

MethodB/|D|=0.1B/|D|=0.25B/|D|=0.5B/|D|=1
RL_Attack0.83460.80710.80130.7963
QuPAC(ANN)0.83210.74370.64790.5592
QuPAC(Greedy)0.80250.73420.65040.5592

COX2 (WB, IE++, Recall@40; lower is better)

MethodB/|D|=0.1B/|D|=0.25B/|D|=0.5B/|D|=1
RL_Attack0.08550.08290.08250.0818
QuPAC(ANN)0.08720.07800.06880.0609
QuPAC(Greedy)0.08420.07730.06930.0609

Comments on the paper

6 comments
AuthorsOpenReview ↗

Requesting the reviewers to acknowledge our rebuttal

Dear Reviewers,

We attempted to address all your concerns and added those discussions to the paper.
Could you please let us know if you have any remaining concerns? This will allow sufficient time to address them.

Best,

Authors

AuthorsOpenReview ↗

Requesting the reviewers to respond

We believe we have adequately responded to the questions raised by the reviewers with clarifications and additional experimental observations they asked for. Our scores have not changed, and they do not appear in consonance with the general tone of the reviews. We request the reviewers to come forward with responses to our rebuttal and any remaining concerns soon, so that they can be addressed within the deadline.

We thank reviewer rnvG for getting back. We would request the reviewers fvEU and UBGW to kindly let us know if our rebuttal addresses their concerns. We would be more than be happy to answer any remaining questions or concerns.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.