- 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
-
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.
-
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
-
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.
-
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.
-
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
-
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?
-
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?
-
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
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 for which is satisfied across the selections made by QuPAC (ANN). The table is for victim IsoNet++ (Edge) with .
| Dataset | Across | QuPAC selections |
|---|---|---|
| AIDS | 0.711 | 0.829 |
| FM | 0.720 | 0.881 |
| FR | 0.721 | 0.877 |
| MM | 0.693 | 0.832 |
| MR | 0.677 | 0.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 .
| Dataset | min | median |
|---|---|---|
| AIDS | 0.76 | 0.86 |
| FM | 0.64 | 0.80 |
| FR | 0.76 | 0.85 |
| MM | 0.77 | 0.87 |
| MR | 0.66 | 0.86 |
Even when assumption 1 fails, the objective has in range 0.64-0.77, consistent with Theorem 1, indicating 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 values are in the range ― in practice and that the condition is a worst case lower bound on .
Assumption 4: We compute the fraction of instances for which the standalone gain is strictly positive.
| Dataset | Fraction where |
|---|---|
| AIDS | 0.994 |
| FM | 0.998 |
| FR | 0.998 |
| MM | 0.995 |
| MR | 0.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 is the subset given by ANN and is the subset given by the greedy algorithm. Following table shows the approximation ratio in terms of the ratio , 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.
| Dataset | B/|D| = 0.125 | B/|D| = 0.25 | B/|D| = 0.625 | B/|D| = 1.0 |
|---|---|---|---|---|
| AIDS | 0.757 | 0.841 | 1.000 | 1.000 |
| FM | 0.679 | 0.826 | 1.000 | 1.000 |
| FR | 0.736 | 0.813 | 1.000 | 1.000 |
| MM | 0.696 | 0.815 | 1.000 | 1.000 |
| MR | 0.754 | 0.917 | 1.000 | 1.000 |
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 for corpus of size 100k, IsoNet++ (Edge) victim on budgets . A runtime is reported as DNF if it did not finish within 24 hours.
| AIDS | B=1000 | B=2000 | B=5000 | B=10000 |
|---|---|---|---|---|
| QuPAC(ANN) | 0.70 | 2.40 | 8.38 | 20.28 |
| QuPAC(Greedy) | 7.10 | DNF | DNF | DNF |
| FM | B=1000 | B=2000 | B=5000 | B=10000 |
|---|---|---|---|---|
| QuPAC(ANN) | 0.85 | 2.87 | 12.38 | 22.83 |
| QuPAC(Greedy) | 7.57 | DNF | DNF | DNF |
| FR | B=1000 | B=2000 | B=5000 | B=10000 |
|---|---|---|---|---|
| QuPAC(ANN) | 1.10 | 2.56 | 12.67 | 19.40 |
| QuPAC(Greedy) | 7.14 | DNF | DNF | DNF |
| MM | B=1000 | B=2000 | B=5000 | B=10000 |
|---|---|---|---|---|
| QuPAC(ANN) | 0.70 | 2.48 | 9.77 | 19.64 |
| QuPAC(Greedy) | 5.75 | 10.46 | DNF | DNF |
| MR | B=1000 | B=2000 | B=5000 | B=10000 |
|---|---|---|---|---|
| QuPAC(ANN) | 0.61 | 2.21 | 8.57 | 18.15 |
| QuPAC(Greedy) | 5.29 | 9.61 | DNF | DNF |
We observe that: (1) QuPAC (ANN) is significantly faster than QuPAC (Greedy), about 6-10x faster for across all datasets while the speedup remains around 4x for . 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 seconds and requires GB (similar to raw dataset size) of space on disk with a preprocessing time of minutes.
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.
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.
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) based on the historic query workload Q, and applies the same set of perturbations δc to the corpus subset S for all the unseen queries Q∗. The computed δj∈δc are chosen such that δj∈∩q∈QΓqj, that is, relevance labels are preserved for perturbed corpus items. However, since Q∗ is not accessible during the computation of (S,δc), we expect to see this label preservation to be violated for some unseen queries, that is, ∃q∈Q∗,δj∈Γ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, 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 ∣Q∗∣1∑q∈Q∗∣G∣∣{Gc⊕∈G ∣ y(Gq,Gc⊕)=+1}∣−∣{Gc⊕∈GS,δc ∣ c∈S ∣ y(Gq,Gc⊕)=+1}∣. 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,80.
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):
FM (MAP: lower is better):
FR (MAP: lower is better):
MM (MAP: lower is better):
MR (MAP: lower is better):