Query-Aware Subgraph Packing: A Knapsack Optimization Paradigm for Graph Retrieval-Augmented Generation

W1. Furthermore, the manuscript omits any side‐by‐side qualitative comparison of retrieved subgraphs between GraphPack and GraphRAG (or other graph‐RAG baselines). For example, Table 5 in Section 4.3 illustrates GraphPack’s selected nodes and edges for sample WebQSP and CWQ queries, highlighting how its knapsack‐optimized subgraphs ostensibly capture multi‐hop evidence chains. However, there is no analogous visualization showing what GraphRAG would retrieve given the same query and budget. Without such a qualitative baseline overlay, readers cannot visually verify whether GraphPack’s subgraphs are indeed more coherent, better‐connected, or more semantically focused than those of GraphRAG. Including side‐by‐side subgraph examples would concretely demonstrate how the knapsack formulation improves the relevance and interpretability of retrieved evidence beyond the reported numerical gains.

We appreciate the reviewer’s suggestion to include a qualitative comparison with baseline methods. To address this, we present a representative case study for the query:

"How many teams are there in the NCAA football?"

This query is intentionally broad and non-entity-specific, which poses a challenge for traditional similarity-based retrieval.

Below, we include simplified views of the retrieved subgraphs:

G-Retriever (retrieved subgraph)

• Nodes:

  • national collegiate athletic association
  • miami hurricanes football
  • sports association
  • division i (ncaa)
  • teams
  • m.0p7h36k (non-descriptive entity)

• Edges:

  • association → teams
  • football team → division
  • several indirect or weak links

Observation: The retrieved subgraph is sparse, with limited semantic coverage and minimal direct evidence toward answering the query.

GraphPack (retrieved subgraph)

• Nodes:

  • national collegiate athletic association
  • division i (ncaa)
  • 2014 ncaa division i fbs football season
  • Multiple NCAA football teams:
    • miami hurricanes
    • usc trojans
    • lsu tigers
    • ohio state buckeyes
    • michigan wolverines
    • stanford cardinal

• Edges:

  • football team → division → NCAA
  • team → league → NCAA
  • season → league → NCAA

Observation: GraphPack retrieves a densely connected, semantically coherent subgraph that maintains answer entities and reasoning paths under the same size budget.

This example demonstrates that GraphPack’s knapsack-based retrieval enables more effective structural evidence aggregation than similarity-only retrieval. Additional examples will be included in the revised appendix.

No user study verifies that selected subgraphs align with expert‐annotated evidence chains. Qualitative examples lack ground‐truth rationale coverage metrics (e.g., a concrete clinical use case to validate the learned/retrieved subgraph).

We fully agree with the reviewer on the importance of validating whether the retrieved subgraph aligns with meaningful evidence chains. However, most benchmark datasets used in our experiments (e.g., WebQSP, CWQ, Arxiv) do not provide expert-annotated "gold-standard" reasoning paths. To address this gap, we propose two objective metrics that approximate this alignment:

• Answer Entity Recall: the percentage of ground-truth answer entities contained in the retrieved subgraph.
• Shortest Path Recall: the proportion of minimal reasoning paths (e.g., entity-to-answer paths in the KG) preserved in the retrieved subgraph.

These proxies allow us to evaluate the quality and coherence of the evidence subgraphs. Table 4 below compares GraphPack with the baseline G-Retriever on the WebQSP dataset using these metrics.

Table 4: Comparison of reasoning path metrics on WebQSP

The results demonstrate that GraphPack consistently retrieves more complete reasoning chains and captures more of the correct answer entities, reinforcing its effectiveness bey

Dear Reviewer s988,

I hope this message finds you well. As the discussion period is nearing its end with less than three days remaining, we wanted to ensure that we have addressed all your concerns satisfactorily. If there are any additional points or feedback you would like us to consider, please let us know. Your insights are invaluable, and we are eager to address any remaining issues to further improve our work.

Thank you for your time and effort in reviewing our paper.

Thank you for your feedback and support! We truly appreciate your time and thoughtful comments, and we are happy to address any additional questions or concerns you may have.

Response to Reviewer Ms8M

We thank the reviewer for the positive feedback and thoughtful suggestions. Below, we provide responses to each of the raised concerns.

W1. In addition to formulating the subgraph selection as an optimization problem, the technical contribution of other parts lacks novelty.

We would like to clarify that GraphPack contributes beyond the knapsack-based selection mechanism. Specifically:

• Query-aware graph encoding via FiLM: Unlike existing GraphRAG systems, we introduce a Query-FiLM module that injects query semantics at multiple layers of the GNN encoder. This allows dynamic, fine-grained modulation of node representations across the entire graph structure.

• Rank-decay value modeling: To combat embedding score distribution bias across heterogeneous node types, we propose a ranking-based decay scoring mechanism that normalizes relevance signals before knapsack selection.

• Structure-aware cost modeling: We incorporate hop-based penalties into the weight function to reduce structural redundancy—a design not used in prior work.

Together, these components form a coherent, query-aware GraphRAG framework that addresses both retrieval and encoding stages and generalizes across graph types and tasks.

W2. Motivation and detailed analysis regarding why the retrieved elements are constructed as a coherent subgraph in the proposed way are not clearly presented. Q1. Could the authors provide a more detailed analysis of the subgraph construction phase? Is it possible that the retrieved subgraph is not connected, and if so, will it affect the performance?

GraphPack selects subgraphs from an n-hop expanded, connected candidate graph centered around anchor nodes. However, the knapsack selection may yield partially disconnected subgraphs. To address this, we adopt a prompt-node strategy that encourages inclusion of anchor-centered paths to maintain connectivity.

Ablation results (Table 3) show that when we disable this strategy and allow fully fragmented subgraphs, the performance degrades across both reasoning (WebQSP) and classification (Instagram) tasks. This confirms the importance of cohesive subgraph structure for effective graph message passing.

Table 3: Effect of Subgraph Connectivity

W3. There are some inconsistencies between the evaluation claims and the results shown in the table. For example, in Table 1, the OFA model achieves the best result on the Citeseer dataset, not GraphPack.

Thank you for catching this. We have rechecked our results and confirm that OFA achieves the best score on Citeseer, and its result should have been bolded. We will correct this in the final version. Nonetheless, GraphPack remains the overall top performer across diverse datasets and domains.

Q2. Regarding the results in Table 9 in Appendix D.1: VanillaRAG performs significantly better on the MusiqueQA dataset compared to the proposed method. Could the authors explain why?

MusiqueQA is a benchmark where questions and answers are tightly bound to the original, pre-segmented text.. Both the questions and answers often depend on full-paragraph semantics that can span multiple sentences and entity mentions.

GraphPack, by design, converts text into a graph structure, pre-processes text chunks into entities and relational edges, which can lead to the loss or corruption of original semantics. While this conversion is beneficial for structured reasoning, it may underperform in tasks like MusiqueQA that rely on expert-segmented content.

In contrast, VanillaRAG retrieves entire text blocks, retaining all local context, which gives it a distinct advantage on MusiqueQA. We acknowledge this as a domain-specific tradeoff and will add further discussion in the revised Appendix.

We again thank the reviewer for the insightful feedback and will incorporate all suggested clarifications into the final version of the paper.

Thank you for your feedback and support! We appreciate your time and are happy to address any further questions.

Response to Reviewer jDFx

We thank the reviewer for the thoughtful and detailed feedback. Below, we respond to each of the concerns and questions raised.

W1. GraphPack's performance is contingent on the quality of the initially retrieved "anchor nodes," which are identified using a frozen text encoder. This upstream component could be a bottleneck, as its performance on data with noisy or sparse textual features may limit the effectiveness of the entire pipeline. Q1. How sensitive is the proposed GraphPack to the choice of text encoder for anchor node selection, and how is performance affected by graphs with sparse or less descriptive textual features?

We acknowledge the reviewer's observation and have explicitly noted this limitation in the original submission (see Section 5, Limitations). Specifically, GraphPack currently relies on a frozen text encoder to identify anchor nodes.

That said, our framework is intentionally modular and encoder-agnostic: GraphPack can work with any node representation method, and the downstream knapsack optimization acts as a second-stage filter, discarding irrelevant nodes even when anchor selection is imperfect. This two-stage process helps mitigate some of the risks associated with weak anchors.

We see this as a valuable direction for future work: integrating a jointly trainable or adaptive anchor retriever could further enhance GraphPack's robustness in real-world graphs with low-quality text.

W2. The functions for assigning value and weight are based on simple heuristics. While intuitive, the paper could be strengthened by providing a more thorough justification for these specific design choices over other potential metrics. Q2. Could the authors provide more justification for choosing rank-decay and hop-distance heuristics for the value and weight functions over other potential metrics?

We chose rank-decay and hop-distance for their simplicity, stability, and transferability across graph types. Rank-decay specifically addresses distributional bias in raw similarity scores—in graph structures, textual descriptions of different entities often have varying semantic distributions. This leads to significant differences in the distribution of their embedding vectors. Table 1 shows the superiority of rank-decay over raw similarity.

Table 1: Value Function Comparison

As for weights, we compared hop-distance with an inverse similarity-based function. The former better penalizes distant, redundant nodes.

Table 2: Weight Function Comparison

These results support our design choice: joint optimization of semantic relevance and structural compactness is more effective than semantics alone.

W3. The performance of GraphPack appears sensitive to the knapsack capacity $\mathcal{C}$. According to the ablation study, it requires tuning for optimal performance on a given dataset. This could challenge the method's practicality and generalizability, and the paper does not offer a clear principle for setting this parameter.

We perform an ablation on WebQSP, showing that $\mathcal{C} = 20$ offers the best trade-off. Remarkably, we reuse this setting across all other datasets (e.g., CWQ, Instagram, Wikics) without retuning. This consistency demonstrates the generalizability of GraphPack’s query-aware optimization.

Q3. What node features are fed into the graph encoder, and how is this feature engineering process generalized across different datasets?

We use semantic embeddings of textual node attributes produced by a frozen language model (e.g., RoBERTa). No manual features or graph statistics are injected. This design avoids feature engineering and generalizes well across diverse datasets (citation networks, social graphs, knowledge graphs).

W4. The clarity of the paper could be improved in several areas, such as providing self-contained table captions and clarifying ambiguous notation (detailed in the Questions section). Q4. Please clarify the notation for n, which appears to refer to both the number of items in Algorithm 1 and the hop distance in the subgraph construction.

We appreciate the suggestion and will revise accordingly:

• In Algorithm 1, n refers to the number of candidate elements and is unrelated to n in “n-hop.” We will change it to m for clarity.
• In n-hop, n denotes the expansion radius from anchor nodes.
• Table captions and figure descriptions will be rewritten to be self-contained and independently interpretable.

Q5. Is the pooling operation in Equation (12) performed over the nodes in the full graph or only those in the retrieved subgraph?

Pooling in Equation (12) is applied only over the retrieved subgraph. We will use $\mathcal{G}\^\*=\left( \mathcal{V}\^\*,\mathcal{E}\^\* \right)$ to explicitly denote the retrieved optimal subgraph, where $\mathcal{V}^\*$ and $\mathcal{E}^\*$ represent the node set and edge set of this subgraph, respectively.

Q6. Could the authors elaborate on what is meant by "expressive power" in the context of lines 174-175 and how the described non-linear transformation enhances it?

It refers to the ability of node embeddings to capture rich, query-specific semantics before pooling. GraphPack amplifies node importance through a nonlinear transformation following Query-FiLM conditioning, which helps the LLM better attend to key information. This avoids the equal-weighting limitation of earlier Graph-RAG methods.

Q7. On which specific tasks and objectives was the LLM fine-tuned (lines 293-294)?

To ensure fair and effective comparison, the LLM is fine-tuned using the LoRA method, and in cross-domain settings (e.g., Cora → Instagram, CWQ → Wikics), both the LLM and GraphPack are trained with consistent input texts and supervision labels.

Q8. Could the authors comment on how GraphPack compares against other recent baselines like [1]? Could the author also comment on the performance discrepancy between the reported results on GraphQA tasks?

SubgraphRAG is designed for KGQA and depends on silver-labeled training paths and retriever training. In contrast, the strategy of GraphPack is a training-free, general-purpose method applicable across domains (social, citation, QA, etc.).

In ICL experiments with the same base model (qwen2.5-14b-instruct) in the cross-task setting, GraphPack achieves:

• WebQSP: Hit@1 = 72.4 (vs. SubgraphRAG’s 79.1)
• CWQ: Hit@1 = 48.89 (vs. SubgraphRAG’s 49.21)

Despite not training the retriever, GraphPack remains highly competitive, demonstrating its strong generalization. We will add discussion of this line of work in the revised Related Work section.

[1] Simple is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation. [2] GNN-RAG: Graph Neural Retrieval for Large Language Model Reasoning.

Dear Reviewer jDFx,

I hope this message finds you well. As the discussion period is nearing its end with less than three days remaining, we wanted to ensure that we have addressed all your concerns satisfactorily. If there are any additional points or feedback you would like us to consider, please let us know. Your insights are invaluable, and we are eager to address any remaining issues to further improve our work.

Thank you for your time and effort in reviewing our paper.

Sensitivity and Generalizability (W1, W3 & Q3)

We agree that demonstrating one fixed hyperparameter setting is not sufficient to establish robustness. To address this, we conducted additional sensitivity analyses.

Effect of Capacity $\mathcal{C}$. On the Wikics node classification task (Table 5), performance peaks at $\mathcal{C}=20$ and remains stable over a wide range. Very large capacities introduce noise and redundancy that slightly reduce accuracy, confirming the importance of balancing coverage and compactness.

Table 5: Ablation Study on Capacity $\mathcal{C}$ (Wikics node classification).

Effect of Text Encoder. We evaluated two pre-trained encoders of very different scales—all-MiniLM-L6-v2 (small, efficient) and gte-large-en-v1.5 (larger, stronger)—on WebQSP (Table 6). While the stronger encoder improves scores, GraphPack remains competitive even with the smaller, generic encoder. This shows the retrieval optimization can exploit semantic signals of varying quality without being tied to a specific encoder.

Table 6: Ablation Study on the Effect of the Textual Encoder (WebQSP).

We will include these results in the appendix to strengthen the evidence of robustness and component replaceability.

Baseline Comparison (Q8)

We appreciate the suggestion for a more nuanced discussion of trade-offs. GraphPack is positioned as a general-purpose, query-aware subgraph retrieval framework that can serve diverse graph tasks. In contrast, SubgraphRAG focuses on KGQA with learned, task-specific multi-hop retrievers.

While GraphPack can be paired with LoRA-tuned LLMs for certain tasks, its retrieval stage is training-free, lowering adaptation cost when moving to new domains. The trade-off is that SubgraphRAG may excel in specialized KBQA when retriever training data are abundant, whereas GraphPack offers broader applicability without retriever retraining.

Addressing GraphQA performance discrepancy. To ensure fairness, we re-ran both methods on WebQSP using the same newer base model (Qwen2.5-7B-Instruct). GraphPack matches or exceeds SubgraphRAG in Hit@1 and especially Precision (Table 7), indicating fewer hallucinations.

Table 7: Performance difference between GraphPack and SubgraphRAG (WebQSP, Qwen2.5-7B-Instruct).

In the ICL (training-free) setting, GraphPack also boosts untrained LLM reasoning, reinforcing its generalization ability across usage modes.

We thank the reviewer for these constructive suggestions and will integrate the new analyses and trade-off discussion into the final version. We hope these clarifications have adequately addressed your concerns and enhanced the clarity of our work.

Dear Reviewer jDFx,

I hope this message finds you well. Today is the final day of the rebuttal period. We would like to confirm that our responses have addressed your concerns thoroughly.

Thank you for your time and effort in reviewing our work!

Response to Reviewer 5jJX

We thank the reviewer for their thoughtful and constructive comments. Below, we address each point raised in detail.

The contribution of the paper appears to be an incremental work based on GRAG. The two-MLP subgraph pruning in GRAG is replaced with 0-1 knapsack optimization; the Query-FiLM module is added into GNN-based graph encoder to introduce query-aware conditional modulation.

We would like to clarify that GraphPack represents a fundamentally new paradigm in subgraph retrieval, rather than a component-level refinement over GRAG. The differences are substantive in both retrieval formulation and query interaction:

• (1) Subgraph Retrieval Paradigm
  GRAG constructs a large n-hop candidate subgraph through similarity-based retrieval and subsequently applies post-processing techniques (e.g., MLP-based weighting) to refine the results. This approach is still fundamentally reliant on a flat retrieval strategy. In contrast, GraphPack formulates subgraph selection as a 0-1 knapsack optimization, jointly optimizing for semantic relevance and structural cost, enabling compact, query-focused subgraph construction under a token budget.

• (2) Query-Aware Graph Encoding
  Most prior works (including GRAG and G-Retriever) use the query only during retrieval. Our proposed Query-FiLM module enables layer-wise conditional modulation, allowing the query to dynamically influence GNN message passing at every layer.

These two innovations result in behavioral differences, particularly in multi-hop and noisy settings (e.g., CWQ). Our ablations (Appendix D.4) confirm these components bring consistent improvements. We thus respectfully suggest that GraphPack goes beyond incremental refinement and represents a principled redesign.

The experimental results lack significance testing. For example, in Table 2, the results of GraphPack are quite close to those of the GRAG baseline. The superiority of GraphPack needs to be validated through significance testing.

We agree that statistical significance is important. We have conducted additional paired t-tests (5 runs) comparing GraphPack with GRAG:

• WebQSP: GraphPack > GRAG with p < 0.01
• CWQ: GraphPack > GRAG with p < 0.005

The smaller margin on WebQSP is due to its shallow query structure (≤2 hops), where GRAG’s large subgraphs often contain the answer. However, on complex multi-hop tasks, GRAG must retrieve larger subgraphs (more than 3-hop) to cover the complete path. GRAG suffers from noisy retrieval, while GraphPack performs hard query-aware pruning, offering more robust reasoning. We will include full statistical details in the final version.

The meaning of ‘structural redundancy’ is not that clear. Within a size budget, what is the reason for minimizing structural redundancy? q1. As mentioned in weakness 3., What is the reason for minimizing structural redundancy? Is less structural redundancy better for model performance with a fixed size budget?

In our method, structural redundancy refers to graph elements that are topologically distant or irrelevant to the query. These elements consume token budget but contribute little to reasoning.

We measure the degree of structural redundancy using the graph's structural complexity: elements farther from the anchor node are more likely to introduce noise and irrelevant information, and are therefore assigned higher weights as a penalty. This leads to compact, semantically dense subgraphs. Our ablation confirms the effectiveness of this design:

Table: Effect of Structural Constraints

The paper illustrates that a larger knapsack capacities $\mathcal{C}$ is not necessarily better. However, how to determine the appropriate size of $\mathcal{C}$ remains unclear. q2. For a specific task, how to determine the appropriate size of $\mathcal{C}$?

We treat $\mathcal{C}$ as a hyperparameter selected via validation. On WebQSP, we found that $$\mathcal{C} = 20$$ yields the best performance (Figure 3). Importantly, this value generalizes well across datasets (Instagram, CWQ, Wikics), likely due to GraphPack’s query-aware scoring, which adaptively prioritizes high-value nodes regardless of graph scale.

We will make this selection strategy clearer in the final version and expand the explanation in Appendix.

how does the text input organized? What is the order of the elements?

The textual input to the LLM is organized as follows:
We first serialize the node descriptions along with their unique indices, followed by edge triples, where the head and tail nodes are replaced with their corresponding indices. This formatting is consistent with the baseline method G-Retriever, ensuring fair comparison in both retrieval and encoding strategies.
We will revise the caption of Figure 2 to clarify this.

We appreciate the reviewer’s thoughtful feedback and will incorporate these clarifications and results into the revised version to improve clarity and rigor.

Dear Reviewer 5jJX,

I hope this message finds you well. As the discussion period is nearing its end with less than three days remaining, we wanted to ensure that we have addressed all your concerns satisfactorily. If there are any additional points or feedback you would like us to consider, please let us know. Your insights are invaluable, and we are eager to address any remaining issues to further improve our work.

Thank you for your time and effort in reviewing our paper.

Thank you for your valuable time and thoughtful review. We greatly appreciate your feedback and would like to clarify that GraphPack does not amount to merely replacing components in GRAG; rather, it introduces a fundamentally innovational framework for subgraph retrieval.

We emphasize that GraphPack is not a component-level replacement within the GRAG framework. In fact, GRAG does not propose or formalize a subgraph retrieval strategy in the same optimization-driven manner as our work. GRAG retrieves a broad n-hop neighborhood and applies an MLP-based weighting over node representations during the generation phase, This is an essentially post-processing step.

In contrast, GraphPack introduces a novel retrieval paradigm based on the 0-1 knapsack problem: we formulate subgraph selection as a constrained optimization problem, jointly optimizing for semantic relevance and structural cost under a given resource budget. This is a parameter-free and training-free paradigm, enabling strong generalization across various graph tasks.

We acknowledge that high-level goals are shared across works in GraphRAG domain, such as improving subgraph quality and downstream generation. However, characterizing GraphPack as an incremental extension of GRAG is therefore misleading. We hope this clarification highlights the principled differences in methodology and design.

Thank you once again for your constructive and insightful comments.