Knowledge Base Question Answering by Case-based Reasoning over Subgraphs

Rajarshi DasAmeya GodboleAnkita NaikElliot TowerManzil ZaheerHannaneh HajishirziRobin JiaAndrew McCallum

article2022ICML70 citations

Presents a semiparametric case-based reasoning framework that scales knowledge base question answering to billion-fact graphs by retrieving similar training queries and transferring their subgraph reasoning patterns to target questions without requiring annotated logical forms.

Listen

Organizations increasingly rely on large knowledge bases to store vast amounts of structured facts. However, querying these repositories using natural language remains difficult because answering diverse questions requires complex, joint reasoning across multiple connections in the graph rather than simple path-following. Manually labeling these intricate reasoning patterns is labor-intensive and impossible to scale. At the same time, standard machine learning models struggle to memorize rare query patterns, generalize poorly to newly added entities, and generate overly large subgraphs from massive databases that exceed hardware compute limits.

To resolve these challenges, the article evaluates a case-based reasoning framework called CBR-SUBG. The model is designed to demonstrate that complex reasoning patterns can be resolved without labeled training paths by retrieving dynamically similar past questions and applying structural similarities across local subgraphs. The framework combines a nonparametric retrieval module—which finds similar training queries and adaptively extracts compact, query-specific subgraphs—with a parametric graph neural network trained via contrastive learning to match the structural neighborhood of target answer nodes to those in retrieved cases.

The authors tested CBR-SUBG on synthetic controlled environments featuring unseen entities and on real-world benchmarks, including FreebaseQA, WebQuestionsSP, and MetaQA, scaling up to the full Freebase knowledge graph containing over 45 million entities and 3 billion facts. The evaluation produced four key findings. First, CBR-SUBG effectively identified complex, unannotated graph structures, achieving an 85.68% average strict accuracy across diverse pattern shapes and outperforming standard parametric baseline models by approximately 13 percentage points. Second, the adaptive subgraph collection method reduced subgraph sizes by 55.07% on WebQuestionsSP and 92.07% on MetaQA while increasing answer coverage recall by 4.85% and 0.91%, respectively. Third, CBR-SUBG delivered superior performance on standard benchmarks, notably scoring 52.07% on FreebaseQA to outperform the strongest pure knowledge base baseline by 14.45 percentage points and achieving 99.3% on MetaQA 3-hop questions. Fourth, the model demonstrated an ability to improve performance as more nearest-neighbor evidence was provided at inference time, provided the training case base was sufficiently large.

These findings indicate that semiparametric case-based reasoning offers a practical and computationally efficient path for enterprise knowledge base question answering. By employing sparse entity representations based on outgoing relation types rather than fixed entity embeddings, the system readily incorporates newly added entities and evolving facts without requiring full model retraining. Furthermore, generating smaller, highly focused subgraphs directly reduces hardware memory requirements and compute costs while simultaneously improving answer precision and recall.

Organizations developing automated reasoning and question-answering systems over large-scale knowledge graphs should consider adopting semiparametric, case-based architectures. The article recommends deploying dynamic case retrieval and adaptive subgraph pruning rather than naive neighborhood extraction. Prior to production rollout, teams must evaluate the depth and quality of their historical case repositories, as the system relies on retrieving truly relevant cases to prevent performance degradation caused by noisy context. Future developmental initiatives should explore incorporating large language models into the parametric reasoning component and establishing continuous learning pipelines that automatically ingest newly discovered facts.

Google University of Massachusetts Amherst University of Southern California University of Washington cbr k-nearest neighbors knowledge base knowledge base question answering case-based reasoning subgraphs

arXiv: 2202.10610 rajarshd/CBR-SUBG

Paper: Case-Based Reasoning, J. Kolodner (1988). This paper establishes the foundational principles and four-step reasoning cycle of case-based reasoning that CBR-SUBG adapts for knowledge base question answering.
Paper: Modeling Relational Data with Graph Convolutional Networks, Michael Schlichtkrull et al. (2018). It introduces relational graph convolutional networks for multi-relational graphs, providing essential background for neural representation and structural matching over graph neighborhoods.
Paper: A Review of Relational Machine Learning for Knowledge Graphs, Maximilian Nickel et al. (2015). This survey outlines statistical relational learning and graph feature models for large-scale knowledge bases like Freebase, foundational to the knowledge graph reasoning tasks addressed in the source.
Paper: Semantic Parsing on Freebase from Question-Answer Pairs, Jonathan Berant et al. (2013). It establishes question answering and semantic parsing benchmarks over Freebase without full logical form supervision, directly preceding the unannotated knowledge base QA paradigm used in the source.
Paper: Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks, Patrick Lewis et al. (2020). This work introduces modern retrieval-augmented generation paradigms that combine nonparametric retrieval with parametric neural reasoning.
Paper: Representation Learning on Graphs: Methods and Applications, William L. Hamilton et al. (2017). It provides a comprehensive conceptual framework for node and subgraph representation learning using graph neural network encoders.
Paper: Memory Networks, Jason Weston et al. (2014). It introduces memory networks for knowledge base question answering, formalizing how external memory stores can be queried during neural reasoning.

Paper: NodePiece: Compositional and Parameter-Efficient Representations of Large Knowledge Graphs, Mikhail Galkin et al. (2022). It proposes an inductive, anchor-and-relation-based tokenization method for scaling knowledge graph representations to millions of entities without storing individual entity embeddings.
Paper: Plan-on-Graph: Self-Correcting Adaptive Planning of Large Language Model on Knowledge Graphs, Liyi Chen et al. (2024). This paper extends graph reasoning on Freebase by integrating adaptive planning and dynamic path exploration directly into large language models.
Paper: StructGPT: A General Framework for Large Language Model to Reason over Structured Data, Jinhao Jiang et al. (2023). It generalizes multi-hop question answering over knowledge graphs to an iterative reading-then-reasoning framework for large language models.
Paper: Unifying Large Language Models and Knowledge Graphs: A Roadmap, Shirui Pan et al. (2023). This roadmap provides a broader perspective on unifying structured knowledge graphs with neural language models for bidirectional reasoning.
Paper: Improving Time Sensitivity for Question Answering over Temporal Knowledge Graphs, Chao Shang et al. (2022). It extends subgraph-based question answering strategies to temporal knowledge graphs requiring chronological constraints and time estimation.
Paper: From Local to Global: A Graph RAG Approach to Query-Focused Summarization, Darren Edge et al. (2024). It scales graph-based retrieval-augmented reasoning from local subgraphs to hierarchical, query-focused community summarization.
Paper: Mitigating Large Language Model Hallucinations via Autonomous Knowledge Graph-Based Retrofitting, Xinyan Guan et al. (2024). It applies local knowledge graph subgraph retrieval to autonomously detect and retrofit intermediate reasoning hallucinations in language models.

Cover for Knowledge Base Question Answering by Case-based Reasoning over Subgraphs

Abstract

Question answering (QA) over knowledge bases (KBs) is challenging because of the diverse, essentially unbounded, types of reasoning patterns needed. However, we hypothesize in a large KB, reasoning patterns required to answer a query type reoccur for various entities in their respective subgraph neighborhoods. Leveraging this structural similarity between local neighborhoods of different subgraphs, we introduce a semiparametric model (CBR-SUBG) with (i) a nonparametric component that for each query, dynamically retrieves other similar k-nearest neighbor (KNN) training queries along with query-specific subgraphs and (ii) a parametric component that is trained to identify the (latent) reasoning patterns from the subgraphs of KNN queries and then apply them to the subgraph of the target query. We also propose an adaptive subgraph collection strategy to select a query-specific compact subgraph, allowing us to scale to full Freebase KB containing billions of facts. We show that CBR-SUBG can answer queries requiring subgraph reasoning patterns and performs competitively with the best models on several KBQA benchmarks. Our subgraph collection strategy also produces more compact subgraphs (e.g. 55% reduction in size for WebQSP while increasing answer recall by 4.85%)1.

Topics

cbr k-nearest neighbors knowledge base question answering reasoning bipartite graphs induced subgraphs

Keywords

knowledge base question answering case-based reasoning subgraphs subgraph reasoning patterns relational similarity relation detection semantic parsing FreebaseQA dataset

1. Introduction
2. Related Work
3. Model
3.1. Retrieval of Similar Cases
3.2. Query-subgraph Selection
3.3. Reasoning over Multiple Subgraphs
4. Experiments
4.1. Reasoning over Complex Patterns
4.2. Performance on benchmark datasets
4.3. Analysis
5. Conclusion
Acknowledgments
References
A. Hyperparameters
B. Generating synthetic data for control experiments
C. Dataset details and statistics
D. Retrieving cases by masking query entities
E. Adaptive subgraph collection tailors subgraphs to the query
F. Further Related Work

Knowls

Knowl 1 — CBR-SUBG Semiparametric Case-Based Reasoning Framework
model/method
CBR-SUBG is a semiparametric model for weakly supervised question answering over knowledge bases (KBQA) that does not require annotated logical forms or reasoning paths during training. A case is defined as a natural language query $q$ paired with its set of answer entities $A$ in a symbolic knowledge graph $\mathcal{K}$ .

The framework operates under the hypothesis that queries with similar relational intent require reasoning patterns $P_q$ (subgraphs of facts in $\mathcal{K}$ ) whose abstract type structure $T(P_q)$ —obtained by replacing entities with free variables—reoccurs in the local neighborhoods of similar queries. CBR-SUBG combines:
1. A nonparametric component that retrieves $k$ -nearest neighbor (kNN) query-answer cases $\text{kNN}_q = \{(q_j, A_j)\}_{j=1}^k$ from a training case-base $\mathcal{D}$ and extracts compact, query-specific subgraphs $G_{q_i}$ for $q$ and each retrieved neighbor $q_j$ .
2. A parametric component comprising a multi-relational graph neural network (GNN) trained via contrastive learning to map local graph topologies to node representations such that target answer nodes in $G_q$ exhibit high representational similarity to the known answer nodes in the retrieved subgraphs $G_{q_j}$ .
Knowl 2 — Nonparametric Adaptive Subgraph Collection Algorithm
algorithm
To construct a compact, query-specific subgraph $G_q$ around query entities $E_q$ without traversing full multi-hop neighborhoods or suffering from hub-node combinatorial explosion in large knowledge graphs $\mathcal{K}$ , CBR-SUBG employs an adaptive path-grounding procedure guided by retrieved cases.
Input: Target query $q$ with entities $E_q$ , retrieved cases $\text{kNN}_q = \{(q_j, A_j, E_{q_j})\}_{j=1}^k$ , Knowledge Graph $\mathcal{K}$
Output: Query subgraph $G_q = (V_q, E_q)$
Initialize relation path collection $\mathcal{P} \leftarrow \emptyset$
Initialize graph edge set $E_q \leftarrow \emptyset$
for each retrieved case $(q_j, A_j, E_{q_j}) \in \text{kNN}_q$ do
    for each query entity $e_{\text{src}} \in E_{q_j}$ and answer entity $a \in A_j$ do
        Execute depth-first search in $\mathcal{K}$ to find paths connecting $e_{\text{src}}$ to $a$
        for each path $p = (e_0, r_1, e_1, r_2, \dots, r_m, e_m)$ do
            Extract relation sequence $\pi = (r_1, r_2, \dots, r_m)$
             $\mathcal{P} \leftarrow \mathcal{P} \cup \{\pi\}$
        end for
    end for
end for
for each relation path $\pi = (r_1, r_2, \dots, r_m) \in \mathcal{P}$ do
    for each target entity $e \in E_q$ do
        Traverse $\mathcal{K}$ starting at $e$ along sequence $\pi$
        Add all traversed nodes and edges that exist in $\mathcal{K}$ to $G_q$
    end for
end for
return $G_q$
Because the collected paths explicitly link questions to answers in similar training queries, this method selectively gathers relevant structural evidence while discarding irrelevant or disconnected multi-hop paths.
Knowl 3 — Multi-Relational Graph Neural Network and Contrastive Loss in CBR-SUBG
model/method
CBR-SUBG encodes query-specific subgraphs using a multi-relational Graph Convolutional Network (R-GCN). For a node $v$ in subgraph $G$ , the $l$ -th message-passing layer updates representations via:

$a_v^l = \sum_{r=1}^{|\mathcal{R}|} \sum_{s \in \mathcal{N}_r(v)} \frac{1}{|\mathcal{N}_r(v)|} W_r^l h_s^{l-1}$

$h_v^l = \text{ReLU}\left(W_{\text{self}}^l h_v^{l-1} + a_v^l\right)$

where $\mathcal{R}$ is the set of relation types, $\mathcal{N}_r(v)$ denotes neighbors of $v$ connected via relation $r$ , $W_r^l$ and $W_{\text{self}}^l$ are learnable weight matrices, and $h_v^0 = x_v$ is the initial node feature vector.

Given the final layer representation $h_v^L$ , the cosine similarity between node $a_i$ in query subgraph $G_{q_i}$ and node $a_j$ in retrieved subgraph $G_{q_j}$ is defined as:

$\text{sim}(a_i, a_j) = \frac{a_i^\top a_j}{\|a_i\|_2 \|a_j\|_2}$

For a target query $q_i$ with true answer set $A_i$ and a retrieved query $q_j \in \text{kNN}_{q_i}$ with answer set $A_j$ , the score between node $a_i$ and $A_j$ is the mean similarity $\text{sim}(a_i, A_j) = \frac{1}{|A_j|} \sum_{a_j \in A_j} \text{sim}(a_i, a_j)$ . The parametric model is trained with an extended normalized temperature-scaled cross-entropy (NT-Xent) loss over all nodes $x_i \in V(G_{q_i})$ :

$\mathcal{L} = - \log \frac{\sum_{a_i \in A_i} \exp\left(\sum_{q_j \in \text{kNN}_{q_i}} \text{sim}(a_i, A_j) / \tau\right)}{\sum_{x_i \in V(G_{q_i})} \exp\left(\sum_{q_j \in \text{kNN}_{q_i}} \text{sim}(x_i, A_j) / \tau\right)}$

where $\tau > 0$ is a learnable or tuned temperature hyperparameter.
Knowl 4 — Inductive Entity Node Representations and Relative Distance Embeddings
model/method
To achieve fully inductive reasoning over unseen entities and dynamic knowledge bases without maintaining a fixed entity embedding lookup table, CBR-SUBG defines initial input features $X_v$ for each node $v$ in a query subgraph $G_q$ using structural properties:
1. Sparse Outgoing Relation Vector: Node $v$ is represented by a binary vector $x_v \in \{0, 1\}^{|\mathcal{R}|}$ , where $\mathcal{R}$ is the relation vocabulary of the knowledge base. If entity $v$ possesses at least one outgoing edge of type $r$ , the dimension corresponding to $r$ is set to 1, and 0 otherwise. This allows newly added entities to be instantly represented.
2. Relative Distance Embedding: Because reasoning patterns originate from query entities, query entities are designated as center entities. Every node $v \in V(G_q)$ is assigned a one-hot distance vector $x_d \in \{0, 1\}^d$ denoting its shortest path hop distance to the nearest query entity (typically evaluated up to $d=4$ hops for subgraphs up to 3 hops).
The final initial node feature vector is the concatenation of the structural feature and distance embedding: $X_v = [x_v; x_d]$ .
Knowl 5 — Answer Node Selection Algorithm via kNN Subgraph Similarity
algorithm
At inference time, CBR-SUBG determines the answer entity for an input query by finding the node in the query subgraph whose local structural representation is most similar to the answer nodes across the retrieved nearest-neighbor subgraphs.
Input: Target query subgraph $G_{q_i} = (V_{q_i}, E_{q_i})$ , retrieved subgraphs $\{G_{q_j}\}_{q_j \in \text{kNN}_{q_i}}$ with known answer sets $\{A_j\}$ , trained R-GCN model
Output: Predicted answer node $a_i^* \in V_{q_i}$
Run message passing on $G_{q_i}$ and all retrieved subgraphs $\{G_{q_j}\}$ to obtain node representations
for each candidate node $x_i \in V_{q_i}$ do
    Initialize cumulative similarity score $S(x_i) \leftarrow 0$
    for each neighbor query $q_j \in \text{kNN}_{q_i}$ do
        Compute mean cosine similarity $\text{sim}(x_i, A_j) \leftarrow \frac{1}{|A_j|} \sum_{a_j \in A_j} \frac{h_{x_i}^\top h_{a_j}}{\|h_{x_i}\|_2 \|h_{a_j}\|_2}$
         $S(x_i) \leftarrow S(x_i) + \text{sim}(x_i, A_j)$
    end for
end for
$a_i^* \leftarrow \arg\max_{x_i \in V_{q_i}} \sum_{x_i \in V_{q_i}} \exp\left(S(x_i)\right)$
return $a_i^*$
Knowl 6 — Entity-Masked Query Representation for Case-Base Retrieval
model/method
To retrieve training cases based on relational structure rather than entity topicality, query entities in natural language queries are replaced with a special [MASK] token (for example, transforming "Who played Natalie Portman in Star Wars?" into "Who played [MASK] in [MASK]?").

Each masked question is encoded independently using a pretrained RoBERTa-base model, and a dense sentence vector is generated by mean pooling token representations. The similarity between an input query $q$ and a stored case $q_j \in \mathcal{D}$ is computed as the cosine similarity (inner product between $\ell_2$ -normalized representations) of their vectors. Nearest-neighbor queries are retrieved via maximum inner product search over precomputed representations in the case-base.

Knowl 7 — Evaluation on Latent Subgraph Patterns in Synthetic Graphs

data/table

To evaluate the inductive capacity of models to identify latent subgraph reasoning patterns without annotated logical forms, models were tested on synthetic graphs across five pattern topologies: 2-hop chain (2p), 3-hop chain (3p), 2-hop intersection (2i), intersection-path (ip), and path-intersection (pi). Performance is evaluated using Strict Hits@1 (%)—requiring all ground-truth answer nodes to be ranked above all other 120 nodes in the graph (random guessing achieves $1/120 \approx 0.83\%$ ).

Model	2p	3p	2i	ip	pi	Avg.
CBR-SUBG (NT)	68.56	84.35	23.00	34.85	35.35	47.28
GNN + TransE	80.03	74.49	80.00	52.67	81.53	72.69
CBR-path	69.71	54.39	100.00	69.12	51.24	71.09
CBR-SUBG	96.64	88.43	90.46	70.02	86.81	85.68

CBR-SUBG with randomly initialized weights (NT, No Training) achieves 47.28% average Strict Hits@1, demonstrating an inherent structural inductive bias. Trained CBR-SUBG outperforms the inductive parametric GNN + TransE baseline by 12.99 points on average and exceeds the path-based CBR baseline (CBR-path) by 14.59 points, indicating that joint subgraph message passing is substantially more effective than independent relational path combination for composite reasoning structures.

Knowl 8 — Synthetic Benchmark Setup for Inductive KB Subgraph Reasoning
experimental setup
The controlled synthetic evaluation environment generates heterogeneous random graphs extending the Erd\H{o}s-R'enyi model:
1. Type System: A schema containing 16 entity types and 74 allowed directed relation types is constructed with edge probability $p=0.3$ between entity types.
2. Pattern Grounding: Grounded reasoning patterns are generated from 5 topological shapes (2p, 3p, 2i, ip, pi). Query entities, relation edges, and target answer nodes are assigned types complying with the schema.
3. Graph Construction: For each instance, an empty graph with 120 entities is instantiated, each node assigned one of the 16 types. Edges are sampled with probability $p=0.4$ between allowed types up to 3 hops from query entities, and grounded pattern edges are inserted.
4. Data Splits: 200 distinct pattern types are generated across 1,000 graphs per split (train, validation, test), with 15 graphs per pattern type (5 train, 5 validation, 5 test). Graphs in different splits have completely disjoint entity sets, enforcing strict inductive reasoning on unseen entities.

Knowl 9 — Empirical KBQA Performance on MetaQA, WebQSP, and FreebaseQA Benchmarks

data/table

CBR-SUBG was evaluated on standard KBQA benchmarks including MetaQA (1-hop, 2-hop, 3-hop partitions), WebQSP (evaluated against the full Freebase KB of over 45M entities and 3B facts), and FreebaseQA (trivia questions over full Freebase).

Model	MetaQA			WebQSP
	1-hop	2-hop	3-hop
KVMemNN	95.8	25.1	10.1	46.7
GraftNet	97.0	94.8	77.7	66.4
PullNet	97.0	99.9	91.4	68.1
SRN	97.0	95.1	75.2	-
ReifKB	96.2	81.1	72.3	52.7
EmbedKGQA	97.5	98.8	94.8	66.6
NSM	97.2	99.9	98.9	74.3
CBR-SUBG (Ours)	97.1	99.8	99.3	72.1

Model	FreebaseQA Accuracy (%)
KB-only models
HR-BiLSTM	28.40
KBQA-Adapter	28.78
KEQA	28.73
FOFE	37.00
BuboQA	38.25
CBR-SUBG (Ours)	52.07
LM pre-training + KB
EAE	53.40
FAE	63.30

On MetaQA 3-hop, CBR-SUBG achieves 99.3% accuracy, outperforming GraftNet (77.7%) and PullNet (91.4%). On FreebaseQA, CBR-SUBG achieves 52.07% accuracy, outperforming the best KB-only baseline (BuboQA at 38.25%) by 13.82 percentage points and approaching the performance of large language model pre-trained hybrid architectures (EAE at 53.40%).

Knowl 10 — Compactness, Coverage, and Accuracy of Adaptive Subgraph Collection

data/table

The nonparametric adaptive subgraph collection strategy was compared to GraftNet's personalized PageRank subgraph extraction on WebQSP and MetaQA-2 in terms of average edges, relations, entities, and answer coverage (recall).

Dataset / Subgraph	#Edges	#Relations	#Entities	Coverage (%)
WebQSP
GraftNet	4306.00	294.69	1447.68	89.93%
CBR-SUBG	1934.65	36.42	1403.87	94.30%
Relative Difference	-55.07%	-87.64%	-3.02%	+4.85%
MetaQA-2
GraftNet	1126.00	18.00	468.00	99.00%
CBR-SUBG	89.21	4.72	77.52	99.90%
Relative Difference	-92.07%	-73.78%	-83.43%	+0.91%

When training and evaluating CBR-SUBG using the different subgraphs, the adaptive subgraph collection improves accuracy on WebQSP from 65.61% (using GraftNet subgraphs) to 72.10% (using adaptive subgraphs), and on MetaQA-3 from 96.90% to 99.30%.

Knowl 11 — Effects of Retrieved Case Count and Relative Distance Embeddings on Accuracy
empirical result
Analysis of CBR-SUBG across hyperparameters and architecture ablations shows:
1. Number of Retrieved Neighbors ( $k$ ): On MetaQA (1-hop, 2-hop, and 3-hop), Hits@1 increases sharply as test-time neighbors increase from $k=1$ to $k=7$ , leveling off and converging near $k=10$ . On the smaller WebQSP dataset, test accuracy peaks at $k=5$ (72.11%) and declines as $k$ increases further ( $k=1$ : 69.06%, $k=2$ : 70.28%, $k=3$ : 71.20%, $k=7$ : 71.14%, $k=10$ : 70.71%, $k=20$ : 69.12%) due to noisy, irrelevant questions being retrieved from a limited case-base.
2. Relative Distance Embeddings: Ablating distance embeddings causes Hits@1 performance drops across all MetaQA subsets: MetaQA 1-hop drops from 97.1% to 94.6%, MetaQA 2-hop drops from 99.8% to 96.1%, and MetaQA 3-hop drops from 99.3% to 94.8%.

Coverage note — Omitted hyperparameter details (optimizer betas, exact learning rates, epochs from Appendix A) and qualitative relation distribution plots (Appendix Figures 7-9) as they are standard implementation choices and visual illustrations rather than core scientific contributions.

References

1.Berant, J., Chou, A., Frostig, R., and Liang, P. Semantic parsing on freebase from question-answer pairs. In EMNLP, 2013.
2.Bollacker, K., Evans, C., Paritosh, P., Sturge, T., and Taylor, J. Freebase: A collaboratively created graph database for structuring human knowledge. In ICDM, 2008.
3.Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., and Yakhnenko, O. Translating embeddings for modeling multi-relational data. In Neurips, 2013.
4.Chen, D., Fisch, A., Weston, J., and Bordes, A. Reading wikipedia to answer open-domain questions. In ACL, 2017.
5.Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. A simple framework for contrastive learning of visual representations. In ICML, 2020.
6.Chopra, S., Hadsell, R., and LeCun, Y. Learning a similarity metric discriminatively, with application to face verification. In CVPR, 2005.
7.Cohen, W. W., Sun, H., Hofer, R. A., and Siegler, M. Scalable neural methods for reasoning with a symbolic knowledge base. arXiv preprint arXiv:2002.06115, 2020.
8.Das, R., Dhuliawala, S., Zaheer, M., Vilnis, L., Durugkar, I., Krishnamurthy, A., Smola, A., and McCallum, A. Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In ICLR, 2018.
9.Das, R., Godbole, A., Dhuliawala, S., Zaheer, M., and McCallum, A. A simple approach to case-based reasoning in knowledge bases. In AKBC, 2020a.
10.Das, R., Godbole, A., Monath, N., Zaheer, M., and McCallum, A. Probabilistic case-based reasoning for openworld knowledge graph completion. In Findings of EMNLP, 2020b.
11.Das, R., Zaheer, M., Thai, D., Godbole, A., Perez, E., Lee, J.-Y., Tan, L., Polymenakos, L., and McCallum, A. Casebased reasoning for natural language queries over knowledge bases. In EMNLP, 2021.
12.Duvenaud, D., Maclaurin, D., Aguilera-Iparraguirre, J., Gomez-Bombarelli, R., Hirzel, T., Aspuru-Guzik, A., and Adams, R. P. Convolutional networks on graphs for learning molecular fingerprints. arXiv preprint arXiv:1509.09292, 2015.
13.Erdos, P., Renyi, A., et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 1960.
14.Févry, T., Soares, L. B., FitzGerald, N., Choi, E., and Kwiatkowski, T. Entities as experts: Sparse memory access with entity supervision. In EMNLP, 2020.
15.Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In ICML, 2017.
16.Gu, J., Wang, Y., Cho, K., and Li, V. O. Search engine guided neural machine translation. In AAAI, 2018.
17.Gutmann, M. and Hyvärinen, A. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In AIStats, 2010.
18.Han, N., Topic, G., Noji, H., Takamura, H., and Miyao, Y. An empirical analysis of existing systems and datasets toward general simple question answering. In CoNLL, 2020.
19.Hashimoto, T. B., Guu, K., Oren, Y., and Liang, P. A retrieve-and-edit framework for predicting structured outputs. In Neurips, 2018.
20.Hassani, K. and Khasahmadi, A. H. Contrastive multi-view representation learning on graphs. In ICML, 2020.
21.He, G., Lan, Y., Jiang, J., Zhao, W. X., and Wen, J.-R. Improving multi-hop knowledge base question answering by learning intermediate supervision signals. In WSDM, 2021.
22.Huang, X., Zhang, J., Li, D., and Li, P. Knowledge graph embedding based question answering. In WSDM, 2019.
23.Jiang, K., Wu, D., and Jiang, H. Freebaseqa: a new factoid qa data set matching trivia-style question-answer pairs with freebase. In NAACL, 2019.
24.Karpukhin, V., Oğuz, B., Min, S., Wu, L., Edunov, S., Chen, D., and Yih, W.-t. Dense passage retrieval for opendomain question answering. In EMNLP, 2020.
25.Khandelwal, U., Levy, O., Jurafsky, D., Zettlemoyer, L., and Lewis, M. Generalization through memorization: Nearest neighbor language models. In ICLR, 2020.
26.Khandelwal, U., Fan, A., Jurafsky, D., Zettlemoyer, L., and Lewis, M. Nearest neighbor machine translation. In ICLR, 2021.
27.Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
28.Kwiatkowski, T., Choi, E., Artzi, Y., and Zettlemoyer, L. Scaling semantic parsers with on-the-fly ontology matching. In EMNLP, 2013.
29.Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, V. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692, 2019.
30.Miller, A., Fisch, A., Dodge, J., Karimi, A.-H., Bordes, A., and Weston, J. Key-value memory networks for directly reading documents. In EMNLP, 2016.
31.Mohammed, S., Shi, P., and Lin, J. Strong baselines for simple question answering over knowledge graphs with and without neural networks. In NAACL, 2018.
32.Neelakantan, A., Roth, B., and McCallum, A. Compositional vector space models for knowledge base completion. In ACL, 2015.
33.Qiu, J., Chen, Q., Dong, Y., Zhang, J., Yang, H., Ding, M., Wang, K., and Tang, J. Gcc: Graph contrastive coding for graph neural network pre-training. In KDD, 2020a.
34.Qiu, Y., Wang, Y., Jin, X., and Zhang, K. Stepwise reasoning for multi-relation question answering over knowledge graph with weak supervision. In WSDM, 2020b.
35.Ren, H., Hu, W., and Leskovec, J. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In ICLR, 2020.
36.Saxena, A., Tripathi, A., and Talukdar, P. Improving multihop question answering over knowledge graphs using knowledge base embeddings. In ACL, 2020.
37.Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, G. The graph neural network model. IEEE transactions on neural networks, 2008.
38.Schank, R. C. Dynamic memory: A theory of reminding and learning in computers and people. cambridge university press, 1982.
39.Schlichtkrull, M., Kipf, T. N., Bloem, P., Van Den Berg, R., Titov, I., and Welling, M. Modeling relational data with graph convolutional networks. In ESWC, 2018.
40.Soares, L. B., FitzGerald, N., Ling, J., and Kwiatkowski, T. Matching the blanks: Distributional similarity for relation learning. In ACL, 2019.
41.Sun, F.-Y., Hoffmann, J., Verma, V., and Tang, J. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. In ICLR, 2020.
42.Sun, H., Dhingra, B., Zaheer, M., Mazaitis, K., Salakhutdinov, R., and Cohen, W. W. Open domain question answering using early fusion of knowledge bases and text. In EMNLP, 2018.
43.Sun, H., Bedrax-Weiss, T., and Cohen, W. W. Pullnet: Open domain question answering with iterative retrieval on knowledge bases and text. In EMNLP, 2019a.
44.Sun, Z., Deng, Z.-H., Nie, J.-Y., and Tang, J. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019b.
45.Teru, K., Denis, E., and Hamilton, W. Inductive relation prediction by subgraph reasoning. In ICML, 2020.
46.Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. In ICLR, 2018.
47.Verga, P., Sun, H., Soares, L. B., and Cohen, W. W. Facts as experts: Adaptable and interpretable neural memory over symbolic knowledge. arXiv preprint arXiv:2007.00849, 2020.
48.Wu, P., Huang, S., Weng, R., Zheng, Z., Zhang, J., Yan, X., and Chen, J. Learning representation mapping for relation detection in knowledge base question answering. In ACL, 2019.
49.Xiong, W., Hoang, T., and Wang, W. Y. Deeppath: A reinforcement learning method for knowledge graph reasoning. In EMNLP, 2017.
50.Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In ICLR, 2019.
51.Yang, B., Yih, W.-t., He, X., Gao, J., and Deng, L. Embedding entities and relations for learning and inference in knowledge bases. In ICLR, 2015.
52.Yih, W.-t., Richardson, M., Meek, C., Chang, M.-W., and Suh, J. The value of semantic parse labeling for knowledge base question answering. In ACL, 2016.
53.You, Y., Chen, T., Sui, Y., Chen, T., Wang, Z., and Shen, Y. Graph contrastive learning with augmentations. Neurips, 2020.
54.Yu, M., Yin, W., Hasan, K. S., Santos, C. d., Xiang, B., and Zhou, B. Improved neural relation detection for knowledge base question answering. In ACL, 2017.
55.Zelle, J. M. and Mooney, R. J. Learning to parse database queries using inductive logic programming. In NCAI, 1996.
56.Zettlemoyer, L. and Collins, M. Online learning of relaxed ccg grammars for parsing to logical form. In EMNLP, 2007.
57.Zettlemoyer, L. S. and Collins, M. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In UAI, 2005.
58.Zhang, M. and Chen, Y. Link prediction based on graph neural networks. In Neurips, 2018.
59.Zhang, Y., Dai, H., Kozareva, Z., Smola, A. J., and Song, L. Variational reasoning for question answering with knowledge graph. In AAAI, 2018.
60.Zhu, Y., Xu, Y., Yu, F., Liu, Q., Wu, S., and Wang, L. Deep graph contrastive representation learning. arXiv preprint arXiv:2006.04131, 2020.

Citation

MLA

Das, R., et al. “Knowledge Base Question Answering by Case-based Reasoning over Subgraphs”. International Conference on Machine Learning, vol. 162, 2022, pp. 4777–93, https://proceedings.mlr.press/v162/das22a.html.

APA

Das, R., Godbole, A., Naik, A., Tower, E., Zaheer, M., Hajishirzi, H., Jia, R., & Mccallum, A. (2022). Knowledge Base Question Answering by Case-based Reasoning over Subgraphs. International Conference on Machine Learning, 162, 4777–4793. https://proceedings.mlr.press/v162/das22a.html

Chicago

Das, R., A. Godbole, A. Naik, et al. 2022. “Knowledge Base Question Answering by Case-based Reasoning over Subgraphs”. International Conference on Machine Learning 162: 4777–93. https://proceedings.mlr.press/v162/das22a.html.

Harvard

Das, R. et al. (2022) “Knowledge Base Question Answering by Case-based Reasoning over Subgraphs”, International Conference on Machine Learning. PMLR, pp. 4777–4793. Available at: https://proceedings.mlr.press/v162/das22a.html.

Vancouver

1. Das R, Godbole A, Naik A, Tower E, Zaheer M, Hajishirzi H, Jia R, Mccallum A (2022) Knowledge Base Question Answering by Case-based Reasoning over Subgraphs. In: International Conference on Machine Learning. PMLR, pp 4777–4793

BibTeX

@InProceedings{pmlr-v162-das22a,
  title = 	 {Knowledge Base Question Answering by Case-based Reasoning over Subgraphs},
  author =       {Das, Rajarshi and Godbole, Ameya and Naik, Ankita and Tower, Elliot and Zaheer, Manzil and Hajishirzi, Hannaneh and Jia, Robin and Mccallum, Andrew},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {4777--4793},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/das22a/das22a.pdf},
  url = 	 {https://proceedings.mlr.press/v162/das22a.html},
  abstract = 	 {Question answering (QA) over knowledge bases (KBs) is challenging because of the diverse, essentially unbounded, types of reasoning patterns needed. However, we hypothesize in a large KB, reasoning patterns required to answer a query type reoccur for various entities in their respective subgraph neighborhoods. Leveraging this structural similarity between local neighborhoods of different subgraphs, we introduce a semiparametric model (CBR-SUBG) with (i) a nonparametric component that for each query, dynamically retrieves other similar $k$-nearest neighbor (KNN) training queries along with query-specific subgraphs and (ii) a parametric component that is trained to identify the (latent) reasoning patterns from the subgraphs of KNN queries and then apply them to the subgraph of the target query. We also propose an adaptive subgraph collection strategy to select a query-specific compact subgraph, allowing us to scale to full Freebase KB containing billions of facts. We show that CBR-SUBG can answer queries requiring subgraph reasoning patterns and performs competitively with the best models on several KBQA benchmarks. Our subgraph collection strategy also produces more compact subgraphs (e.g. 55% reduction in size for WebQSP while increasing answer recall by 4.85%)\footnote{Code, model, and subgraphs are available at \url{https://github.com/rajarshd/CBR-SUBG}}.}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Knowledge Base Question Answering by Case-based Reasoning over Subgraphs

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — CBR-SUBG Semiparametric Case-Based Reasoning Framework

Knowl 2 — Nonparametric Adaptive Subgraph Collection Algorithm

Knowl 3 — Multi-Relational Graph Neural Network and Contrastive Loss in CBR-SUBG

Knowl 4 — Inductive Entity Node Representations and Relative Distance Embeddings

Knowl 5 — Answer Node Selection Algorithm via kNN Subgraph Similarity

Knowl 6 — Entity-Masked Query Representation for Case-Base Retrieval

Knowl 7 — Evaluation on Latent Subgraph Patterns in Synthetic Graphs

Knowl 8 — Synthetic Benchmark Setup for Inductive KB Subgraph Reasoning

Knowl 9 — Empirical KBQA Performance on MetaQA, WebQSP, and FreebaseQA Benchmarks

Knowl 10 — Compactness, Coverage, and Accuracy of Adaptive Subgraph Collection

Knowl 11 — Effects of Retrieved Case Count and Relative Distance Embeddings on Accuracy

References

Citation

BibTeX

Source Code

Access the Paper