PaperlayerView exact revision on arXiv

Source-linked AI summary

Query-Side Attacks on GNN-Based KGQA: Tracing Failures from Entity Linking to Answer Generation

Pankaj Kumar, Subhankar Mishra

arXiv:2608.25922v1cs.CLcs.AIcs.IR

TL;DR

GNN-based KGQA robustness metrics usually collapse failures across entity linking, retrieval, reasoning, and generation, making the failing stage unclear. This paper isolates stages with answer-preserving query attacks and finds that CR failures arise chiefly from subgraph construction, not GNN reasoning. The results distinguish answer presence from reachability and motivate retrieval-focused defenses.

  • Problem

    Standard end-to-end robustness metrics do not identify which KGQA pipeline stage fails under adversarial question perturbations.

  • Method

    The paper introduces stage isolation with answer-preserving Compositional Restructuring and Relation Synonym Swap attacks verified against the knowledge graph.

  • Results

    52.08 pp of the 52.22 pp total CR CWQ drop is attributed to subgraph topology failure, while intact-subgraph reasoning reaches 52.76% CWQ EM.

  • Takeaways & Limitations

    Answer presence does not ensure answer reachability, so mitigation should target question-conditioned subgraph construction rather than the reasoning model.

  • Takeaways & Limitations

    Reported attack severities are conservative lower bounds because validity filters discard candidate rewrites, and the framework is an offline diagnostic stress test.

Abstract

from arXiv · show

GNN-based Knowledge Graph Question Answering (KGQA) pipelines process queries through four discrete stages: entity linking, subgraph retrieval, GNN reasoning, and answer generation. Standard robustness evaluations conflate stage-level failures into a single end-to-end metric, obscuring both the source of brittleness and the appropriate mitigation target. We ask which stage fails, and why, when the pipeline is subjected to adversarial perturbations on the input question. We introduce a stage-isolation protocol with two answer-preserving adversarial perturbations verified against the knowledge graph: Compositional Restructuring (CR) and Relation Synonym Swap (RS) target distinct stages while leaving entity seeds intact. Evaluated across ComplexWebQuestions and WebQSP, the results run counter to prevailing assumptions: the GNN reasoning stage retains near-baseline accuracy when the subgraph is intact, while subgraph construction accounts for over 99\% of the end-to-end collapse under CR, occurring even when the gold answer is present in 74\% of retrieved subgraphs. This exposes a fundamental distinction between answer presence and answer reachability that end-to-end metrics cannot detect, and places the mitigation target firmly at the subgraph construction stage rather than the reasoning model. Perturbed datasets and evaluation infrastructure are released at https://anonymous.4open.science/r/atkgrag-E85C .

1 Introduction

This paper studies query-side adversarial failures in four-stage GNN-based KGQA pipelines and introduces stage-isolated, answer-preserving perturbations. Results identify subgraph construction as the main bottleneck under compositional restructuring, while reasoning remains robust when the subgraph is intact.

  • Motivation: GNN-based KGQA passes questions through entity linking, subgraph retrieval, GNN reasoning, and answer generation, allowing failures to propagate across stages.Each stage can independently corrupt outputs consumed downstream.
  • Method: The stage-isolation protocol fixes upstream outputs and measures per-stage degradation under Compositional Restructuring (CR) and Relation Synonym Swap (RS).CR preserves entity mentions and SPARQL answers while restructuring composition; RS changes predicate surface forms while preserving entities.
  • Findings: 74% answer presence under CR yields only 0.68% CWQ EM because PPR retrieval remains anchored to the original reasoning chain.GraftNet reaches 29.82% EM at 63.3% answer coverage by aligning PPR topology with the restructured chain.
  • Findings: 52.08 percentage points of the 52.22 pp total CR CWQ drop come from subgraph topology failure, while intact-subgraph reasoning reaches 52.76% CWQ EM.This isolates subgraph construction as the dominant source of end-to-end collapse.
  • Mitigation: Inference-time relation-path injection recovers 51.4% CWQ EM under CR without fine-tuning.The recovery matches or exceeds relation-path-augmented fine-tuning.

2 Related Work

Prior KGQA methods use semantic parsing, dense retrieval, or PPR-based GNN-RAG, while robustness studies have largely examined surface perturbations or corpus-side attacks. The paper fills a gap by resolving which pipeline stage fails under query-only attacks.

  • KGQA Approaches: Semantic parsing converts questions into SPARQL, embedding-based methods retrieve answers by dense similarity, and GNN-RAG combines PPR subgraphs with a GAT reasoner.GNN-RAG uses ELQ for entity linking and creates a cascading failure structure under query perturbation.
  • Robustness Threats: Existing robustness work often poisons retrieval corpora, injects adversarial passages, or manipulates retrieved context, requiring corpus or KG access.These capabilities differ from the query-only threat model studied here.
  • Research Gap: Prior KGQA robustness studies examined entity surface-form noise and relation paraphrases but did not measure first-failing stages or downstream propagation.The stage-isolation protocol addresses this measurement gap.
  • Positioning: For CR and RS, entity linking remains intact with a SeedHit drop of at most 0.3 pp, making subgraph topology the bottleneck rather than the linker.This finding distinguishes the paper’s structural diagnosis from linker-focused alternatives.

3 Methodology

The methodology models GNN-RAG as a four-stage pipeline and evaluates two answer-preserving query attacks under a query-only black-box threat model. Perturbations are certified for semantic preservation and applied while holding the GNN checkpoint fixed.

  • Pipeline: The modeled pipeline maps a question through entity linking, subgraph retrieval, GNN reasoning, and answer generation to a generated answer.In GNN-RAG, these components are ELQ, personalized PageRank, a three-layer GAT, and fine-tuned Llama-2-7B.
  • Threat Model: The adversary submits a perturbed question and observes the answer without accessing model parameters or intermediate states.Local perturbation generation and SPARQL verification are used for certification, not attacker access.
  • Validation: Perturbations pass perplexity, BERTScore, and SPARQL-denotation filters, with manual inspection validating naturalness and answer preservation.The reported filter pass rates are 92.4% for the first two criteria and 94.1% for denotation checking.
  • Perturbations: CR performs one KG-safe structural operation, preserving entity mentions and SPARQL denotation while targeting retrieval and multi-hop traversal.Operations include hop-order reversal, distractor constraint injection, and intermediate-entity alias substitution.
  • Perturbations: RS replaces a predicate phrase with a synonym preserving the Freebase relation, leaving entity mentions and PPR walks unchanged.Its resulting ELQ EM measures GNN instruction-decoder sensitivity in near-isolation.
  • Experimental Control: All variants use the same GNN-RAG ReaRev checkpoint, changing only the retrieved subgraph to isolate retrieval quality from GNN model quality.This controls the reasoning model while varying subgraph construction.

4 Stage-Wise Evaluation Framework

The evaluation tracks failure across pipeline stages using answer presence and structural overlap, then isolates subgraph and decoder contributions by freezing upstream outputs.

  • Per-stage metrics: Triple-level Jaccard measures structural drift between retrieved subgraphs, complementing αpert’s answer-presence measure.
  • Per-stage metrics: αpert measures whether the gold answer is present in the perturbed subgraph and serves as a direct measure of subgraph construction quality.
  • Per-stage metrics: ∆AG is defined as EMclean − EMpert, with positive values reported as degradation in percentage points.
  • Metric conventions: The evaluation uses MID-based Hit@1, which coincides with gold-MID EM for GNN-RAG and EPR-KGQA.
  • Stage isolation: The protocol compares clean, fully perturbed, and clean-subgraph configurations to separate total, subgraph-attributable, and decoder-attributable failures.

5 Experiments

Experiments evaluate GNN-RAG across CWQ and WebQSP using CR and RS attacks, retrieval variants, stage-isolated decoder tests, and inference-time path injection.

  • Datasets and setup: The experiments use 3,531 CWQ and 1,639 WebQSP test questions, with CWQ requiring 2–4 hops and WebQSP requiring 1–2.
  • Main results: CR causes ELQ EM to collapse to 0.68% on CWQ and 0.49% on WebQSP despite intact entity seeds.
  • Subgraph variants: Under CR, GraftNet reaches 29.82% CWQ EM at 63.3% answer coverage, while NSM reaches 5.81% at 29.5% coverage.
  • Decoder isolation: With a clean subgraph, ReaRev achieves 52.76% CWQ EMfast under CR, compared with 0.68% for the full-pipeline ELQ configuration.
  • LLM reasoning: Path injection reaches 51.43% CWQ Hit@1 under CR without task-specific fine-tuning and matches the path-augmented model within 1 pp across benchmarks and attacks.

6 Analysis

Analysis shows that CR primarily breaks retrieval topology rather than entity linking or GNN reasoning, while RS is more resilient when the ELQ subgraph remains structurally unchanged.

  • Answer reachability: 74.0% CR ELQ answer presence yields only 0.68% CWQ EM, with 73.3% of questions present-but-unreachable because connecting paths are missing.
  • Subgraph quality: αpert correlates with EM at Spearman ρ = 0.91 (p < 10^-9) across 24 ablation cells, but fails as a predictor when topology remains anchored to the original chain.
  • Attack asymmetry: RS retains 20.3% CWQ and 50.9% WebQSP ELQ EM, while clean-subgraph EMfast remains 51.69% and 70.59%, respectively.
  • Attack asymmetry: Identical 74.0% answer coverage produces 20.31% EM under RS but 0.68% under CR, showing that coverage alone does not determine accuracy.
  • Architectural controls: Single-shot pattern-matching retains 59.2% CWQ Hit@1 under CR, whereas iterative ExplaiGNN falls from 33.9% clean P@1 to 9.8%.
  • Cross-knowledge-base control: MetaQA’s worst-case drops are 13.1 pp under relation paraphrase and 6.9 pp under CR, versus 52.2 pp for CWQ CR.

7 Conclusion

The paper’s stage-isolation evaluation identifies subgraph construction as the primary performance ceiling under query-side attacks, while showing robust decoding when the subgraph remains intact. It releases datasets and infrastructure and highlights retrieval designs that avoid fixed PPR bottlenecks.

  • Conclusion: Stage-isolation attributes 52.08 pp of the 52.22 pp CWQ CR drop to subgraph topology failure.The GNN instruction decoder remains robust with an intact subgraph, achieving 52.76% CWQ EM on the clean subgraph and perturbed question.
  • Conclusion: Under CR, 74% answer presence in ELQ subgraphs still produces only 0.68% CWQ EM because PPR remains anchored to the original reasoning chain.This separates answer presence from answer reachability.
  • Conclusion: GraftNet’s question-embedding-weighted PPR reaches 29.82% CWQ EM with GEM seeds, while the deployment-realistic ELQ+cosine configuration reaches 14.98%.Inference-time path injection separately recovers 51.4% CWQ EM without task-specific fine-tuning.
  • Conclusion: The released perturbed datasets and evaluation infrastructure are intended to facilitate future robustness work.
  • Conclusion: The vulnerability is specific to PPR-seeded pipelines, whereas EPR-KGQA and GMT-KBQA are substantially more robust.The paper identifies bypassing fixed PPR subgraph retrieval as the key architectural defense and proposes question-conditioned retrieval or relational-path search.

Limitations

The study’s main boundaries are its limited system and benchmark coverage, conservative attack-severity estimates, incomplete cross-knowledge-graph replication, and deployment-inaccessible gold seeds in one comparison.

  • Scope: All primary results use one GNN-RAG system across two Freebase-based benchmarks, although the decoder finding also holds for ReaRev and NSM.UniKGQA is excluded because no public inference checkpoint is available.
  • Attack evaluation: Validity-filtered perturbations fall back to original questions, making reported attack severity a conservative lower bound.Joint pass rates are 86.6% for CWQ CR, 96.6% for CWQ RS, 90.7% for WebQSP CR, and 95.0% for WebQSP RS.
  • Knowledge-graph coverage: The core GNN-RAG CR/RS findings lack a full Wikidata replication, although MetaQA replication and partial Wikidata evidence support transfer beyond Freebase.ConvMix/Wikidata shows more than 70% relative P@1 collapse under CR and RS.
  • Retrieval comparison: GEM-seeded GraftNet uses gold SPARQL entity MIDs unavailable at deployment, limiting the direct deployability of its 29.82% CWQ CR result.The deployment-realistic ELQ+cosine configuration reaches 14.98%, with seed quality identified as the binding constraint.
  • Threat model: The certification setup requires a rewriting model and local SPARQL endpoint, whereas an attacker seeking degradation alone requires neither.The framework is therefore characterized as an offline diagnostic stress test rather than a resource-constrained attacker model.

Ethical Considerations

The study frames query-side attacks as dual-use research on published benchmark systems, releasing perturbations, infrastructure, and defenses while noting important scope boundaries.

  • Ethical Considerations: The attacks target published benchmark systems rather than commercial deployments and are released under a research-use license with two concrete defenses.The defenses are question-embedding-weighted PPR and inference-time path injection.
  • Scope: The evaluation is limited to Freebase-based CWQ and WebQSP with Western, English-language entity coverage.Perturbations were generated with Llama-3.3-70B-Instruct, filtered, and verified against Freebase denotations.
  • Experimental Setting: The study uses the published GNN-RAG ReaRev checkpoint without modification and keeps the model fixed across variants.Only the retrieved-question input changes in the stated fixed-checkpoint setup.
  • Ethical Considerations: CR and RS reduce ELQ SeedHit by at most 0.3 percentage points, indicating that entity linking is not the failure mode for these attacks.The result supports focusing mitigation on downstream subgraph construction rather than the linker.

D ES Diagnostic: Entity Swap

Entity Swap is a diagnostic, not an answer-preserving attack: it changes the topic entity and gold answer to expose entity-linker brittleness and separate it from downstream effects.

  • Diagnostic Design: Entity Swap replaces the topic entity with another same-domain Freebase entity, creating a new MID and gold answer.Because the correct answer changes by design, ES is excluded from the paper’s adversarial-attack definition.
  • Entity-Linker Brittleness: ELQ any-GT hit rate falls from 57.4% to 23.1% on CWQ and from 68.3% to 14.1% on WebQSP under ES.The resulting 34.3- and 54.2-percentage-point drops propagate to near-zero EM.
  • Answerability: 45.6% of CWQ ES questions are structurally unanswerable because the substituted entity has no Freebase path matching the relation chain.CR and RS are at least 99.8% answerable, so ES has an additional answerability confound.
  • Oracle Diagnostic: GraftNet-BFS with oracle substituted-entity MIDs recovers 8.2% CWQ and 44.6% WebQSP overall EM, rising to 14.1% and 51.4% on answerable subsets.This is an upper bound unavailable at deployment, not a deployable defense.
  • Stage Attribution: With clean subgraphs, perturbed-question CR reaches 52.76% CWQ EM versus the 52.9% clean baseline, attributing 52.08 of the 52.22-point drop to subgraph construction.NSM shows similarly small decoder drops under CR and RS, though WebQSP CR is more sensitive.

J.1 Failure Case Examples

Failure cases distinguish retrieval failure from reasoning failure: the gold answer may be absent, or present and reachable yet ranked below an incorrect entity.

  • Failure Mechanisms: RS failures include both absent-answer cases and cases where the answer is reachable but the GNN selects an incorrect entity.This separates subgraph coverage failure from GNN decision failure.
  • Answer Absence: When the gold answer MID is absent from the perturbed subgraph, correct GNN reasoning cannot recover it because it is not among the candidates.The failure is therefore determined before the reasoning stage can choose an answer.
  • Perturbation Templates: The perturbation templates distinguish CR’s KG-safe structural operations from RS’s predicate synonym paraphrase while preserving the intended answer for the primary attacks.CR operations include hop-order reversal, distractor constraint injection, and intermediate alias substitution.
  • Answer Reachability: Even when αpert = 1, the GNN can fail if the perturbed topology provides insufficient message-passing support for the answer node.Answer presence therefore does not guarantee answer reachability.
  • CR Visualization: Figure 5 visualizes CR topology anchoring with PPR mass, ELQ-linked seeds, and gold-answer nodes across clean and hop-reversed neighborhoods.The comparison focuses on whether the reversed path receives enough retrieval emphasis for GNN traversal.

K.2 Subgraph Component Ablation: Seeds × PPR

The ablation identifies seed quality as the main determinant of CR recovery, while retrieval architecture explains robustness differences across systems and task settings.

  • Seeds × PPR: GEM seeds account for approximately 15 percentage points of CR improvement regardless of PPR type.This separates seed quality from the choice between cosine-weighted and flat PPR.
  • Seeds × PPR: The deployment-realistic ELQ-seed plus cosine-PPR configuration reaches 14.98% CWQ CR, below the GEM-seeded 29.82% upper bound.The gap indicates that oracle seed quality is unavailable in deployment.
  • PPR Flavor: On CWQ CR, GEM plus cosine and GEM plus flat PPR differ by only 0.46 points and are statistically indistinguishable; on WebQSP, cosine is 5.6 points higher.The reported CWQ values are 29.79% versus 30.25%, while WebQSP values are 31.18% versus 25.56%.
  • Architectural Controls: GMT-KBQA loses at most 5 points under structural and paraphrase perturbations, but entity-related perturbations cause 18–26-point degradation.Its direct S-expression generation bypasses the EL-then-subgraph-retrieval pipeline.
  • Architectural Controls: EPR-KGQA retains 59.22% CWQ and 64.25% WebQSP Hit@1 under CR, unlike GNN-RAG ELQ’s 0.68% and 0.49%.Its atomic, single-shot retrieval avoids the multi-turn error propagation seen in iterative retrieval.
  • Architectural Controls: ExplaiGNN drops from 33.9% clean P@1 to 9.8% under CR and 10.2% under RS, consistent with vulnerability in iterative turn-dependent retrieval.The comparison is qualitative because ExplaiGNN uses different KG, benchmark, task, and metric settings.

L MetaQA: Stage-Isolation Results

On MetaQA, the stage-isolation protocol tests whether the Freebase failure is schema-specific by replacing both the knowledge base and retrieval topology. The results show no comparable collapse, supporting retrieval construction—not GNN reasoning—as the key boundary for this failure mode.

  • Setup: MetaQA replaces Freebase with WikiMovies and uses seed-neighbourhood expansion instead of PPR-weighted subgraph construction.The setup tests whether topology anchoring belongs to the retrieval algorithm or the underlying knowledge graph.
  • Setup: 95.88% and 99.74% are the clean Hit@1 baselines for MetaQA 3-hop and 2-hop splits, respectively.The evaluation covers complete test sets of 14,274 3-hop and 14,872 2-hop questions.
  • Stage-Isolation Results: The most damaging MetaQA attack is S1, costing 13.09 percentage points on 3-hop and 12.97 points on 2-hop.Every other perturbation remains within 7.2 percentage points of the clean baseline.
  • Stage-Isolation Results: CR costs only 6.91 points on MetaQA-3 and 0.11 points on MetaQA-2, versus a 52.22-point CWQ collapse from 52.9% to 0.68% EM.With perturbation generation, validity filters, and GNN architecture fixed, the contrast is attributed to retrieval construction.
  • Stage-Isolation Results: Under end-to-end re-execution, ES improves by 11.3 points while CR changes by only −0.5 points, localising ES to linking and CR to neither retrieval nor decoding on MetaQA.Re-execution recomputes linking, retrieval, and GNN inference, unlike the fixed-subgraph condition.
  • Scope: Absolute end-to-end accuracies depend on the reference linker and retriever, so only within-condition deltas should be compared across rows.Gold-seeded 3-hop Hit@1 is 30.69% end-to-end, versus 95.88% with the shipped subgraphs.
Loading 2608.25922v1…