REVIEW 2 major objections 5 minor 55 references
Message Passing for Complex Question Answering over Knowledge Graphs
T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Complex knowledge-graph questions can be answered by propagating confidence scores through the graph, without translating the question into a formal query.
desk verdict A genuinely useful KGQA paper whose core reasoning is sound, but the abstract's 'always correct' guarantee is false on the paper's own benchmark and the headline baseline comparison is not apples-to-apples. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the message-passing update in Algorithm 1: a sparse matrix multiplication routine that mimics joins over small local subgraphs. For each matched property reference, the adjacency matrices of candidate property URIs are weighted by property confidence and summed; entity confidence scores are then propagated over the combined matrix; and the final score of an entity is a normalized combination of the propagated activation sum and the number of entity and property references that activated it. The same update runs hop by hop, so the answer set of one hop seeds the next. The algorithm's symmetry—all adjacency matrices are symmetric—is what makes the propagation order-independent, and it is also the point where the undirected-edge assumption enters.
What would settle it
Take a pair of questions that differ only by reversing a directed relation, for example asking for the doctoral advisor versus the doctoral student of the same person, and feed both with the correct entity and property matches at confidence 1. The symmetric adjacency matrices used in Algorithm 1 cannot distinguish the two directions, so any such pair with a unique answer would violate the claim that correct interpretation always yields a correct answer ranking.
Extended reading notes
Core claim
QAmp's central discovery is that answer inference for complex KGQA can be a deterministic, unsupervised diffusion over the local subgraph rather than a learned or templated query-construction process. The paper models a question as a sequence of hops, where each hop contributes entity, property, and class references with confidence scores. Inference then builds symmetric adjacency matrices for the matched properties, propagates the entity and property confidences through those matrices, and combines summed activations with counts of non-zero references to score every candidate answer. Because every adjacency matrix is symmetric, the algorithm deliberately treats edges as undirected; the paper reports that only 5% of questions in its benchmark require edge direction. Given that relaxation, the paper argues that a correct relevance score distribution always yields a correct answer ranking, so the residual end-to-end error is attributable to parsing and matching, with predicate matching as the weakest component.
Load-bearing premise
The method assumes edge direction in the knowledge graph does not matter, so a question whose answer depends on direction—like doctoral advisor versus doctoral student—can get the wrong answer even with perfect interpretation.
Editorial extensions
If this is right
- Given a correct relevance-score distribution, the paper's inference procedure is guaranteed to rank correct answers first, so no supervised ranking or query-generation model is needed at answer time.
- Multi-hop compound questions are answered by chaining hops: each hop's answer activations seed the next hop, all within the same matrix-algebra framework.
- The approach runs on a billion-triple knowledge graph in about 0.72 seconds per question on average, roughly twice as fast as the SPARQL-based baseline.
- End-to-end accuracy is capped by term matching, especially predicate matching, so better relation linking is the highest-leverage improvement.
- Because inference is not tied to template queries, the system can surface correct answers that the benchmark's single-URI gold standard missed.
Reading between the lines
- The paper's own 5% directionality figure suggests a modest extension: keep the message-passing core but make messages direction-aware, perhaps through two symmetric matrices per relation encoding subject and object roles; the guarantee would then hold on directed questions without a full supervised direction predictor.
- The aggregation formula in Algorithm 1 is heuristic; replacing it with calibrated sum-product updates could yield confidence scores that are comparable across questions, at the cost of the paper's closed-form efficiency.
- Because inference is independent of the linker, QAmp could be used as a measurement instrument: swap different entity and predicate matchers into the same inference code to attribute end-to-end errors cleanly.
- The false-negative cases suggest that precision numbers on this benchmark are inflated and recall numbers underestimated; a canonicalized answer set would re-rank all systems.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents QAmp, a question-answering system over knowledge graphs that separates question interpretation from answer inference. The interpretation phase identifies question type and extracts entity, predicate, and class mentions using supervised sequence labeling, then matches them to KG terms via BM25 and FastText embeddings. The answer inference phase performs unsupervised message passing over the subgraph induced by the matched terms, implemented as sparse matrix multiplications, optionally constrained by class filters and question-type aggregation. The authors evaluate QAmp on the LC-QuAD benchmark, reporting an F-measure of 0.33 compared with 0.28 for the WDAqua baseline, and provide an ablation study and error analysis. The central formal claim is that, given a correct relevance score distribution over terms, the message-passing answer inference always produces a correct ranking.
Significance. If properly qualified, this is a useful contribution: it provides a scalable, open-sourced, unsupervised alternative to SPARQL-query-building for complex KGQA, with a clean separation between interpretation and reasoning. The ablation study is informative, clearly identifying predicate matching as the main bottleneck, and the error analysis gives concrete evidence of benchmark and KG inconsistencies. The claim of a guaranteed correct ranking under perfect interpretation is important for the paper's narrative, but as written it is contradicted by the authors' own Setup 1 results, which show residual errors including directionality-sensitive cases. With an explicit qualifier (e.g., invariance under edge reversal), the formal claim becomes defensible for the vast majority of LC-QuAD questions. The end-to-end comparison to WDAqua is also not fully controlled, so the state-of-the-art claim needs to be moderated.
major comments (2)
- [Abstract; Section 5.1, Table 3] The abstract's claim that 'given a correct relevance score distribution, our approach always produces a correct answer ranking' is contradicted by the paper's own Setup 1 ablation. When the answer inference module receives all ground-truth entity, property, and class URIs plus the gold question type, Table 3 still reports errors on 9% of test questions, with 53 questions (5%) requiring modeling of exact subject-object order, e.g., dbp:doctoralStudents versus dbp:doctoralAdvisor. Because Algorithm 1 constructs symmetric adjacency matrices and explicitly treats the graph as undirected (Section 3.2), the guarantee can hold at most for questions whose answers are invariant under edge reversal or where the KG encodes both directions. The unconditional 'always' statement must be qualified to this setting, and the corresponding sentence should be revised in the abstract, introduction, and Section 5.1.
- [Section 4, Table 2] The claim of outperforming the state of the art is not supported by a controlled comparison. The WDAqua numbers are taken from the published results of Diefenbach et al. rather than re-run under the same evaluation harness, and the WDAqua precision is estimated from the reported precision for answered questions only (footnote in Table 2). Differences in metric computation, answer post-processing, and timeout handling can materially change P, R, and F. The paper should either re-run the baseline with the exact same evaluation script or clearly state that the comparison is indicative, not a controlled benchmark, and soften the 'outperforms the state-of-the-art' phrasing accordingly.
minor comments (5)
- [Section 5.1] The text first says 53 test questions (5%) require directionality but later mentions only 35 questions (3.5%) of the LC-QuAD test split use relations of this type. These numbers should be reconciled or the definitions clarified.
- [Algorithm 1] The notation is under-specified: the symbol ⊗ for the combination of the 3-dimensional tensor S with property activations is not defined, and the update in line 3 mixes a loop over Pj with the tensor S in a way that is hard to follow. A brief textual explanation of the tensor dimensions and operations would improve reproducibility.
- [Section 3.2] The assumption that all edges are treated as undirected is stated in Algorithm 1's adjacency matrix definition but is only given a detailed motivation in Section 6. Consider stating the assumption and its implications prominently in Section 3.2, since it is central to the method.
- [Section 5.1, row 4] The sentence 'In this setup, all correct answers according to the benchmark were ranked at the top' is stronger than the reported metrics (P=0.89, R=0.92) justify. The authors should either specify that this holds for a subset of questions or rephrase to 'the correct answers were normally ranked at the top'.
- [Throughout] The paper contains several typos and formatting issues (e.g., 'embedded' for 'embedded' in Section 4.2, unbalanced parentheses in the Algorithm 1 description). A careful proofreading pass is recommended.
Circularity Check
No significant circularity: QAmp's oracle 'GT' runs are standard upper bounds, and the 'always correct ranking' claim is an overclaim contradicted by the paper's own directionality results, not a fitted or self-referential derivation.
full rationale
QAmp's answer inference (Algorithm 1) is a fixed, unsupervised aggregation rule; no parameter is fitted to LC-QuAD test answers, and the ablation's oracle setups ('Question model* GT', 'GT span+') are standard upper-bound experiments that feed ground-truth term URIs into the inference module rather than predicting them from fitted values. The paper does not rename a fitted parameter as a prediction. The headline claim that a correct relevance score distribution 'always produces a correct answer ranking' is an overstatement: the paper's own Setup 1 reports 9% errors, with 53 test questions (5%) requiring edge directionality (Section 5.1), and Section 6 concedes directionality as future work. This is a correctness or robustness defect, not a circular reduction; the claim is empirically falsified by the paper's own controlled setup rather than being true by construction. There is no load-bearing self-citation: the HDT and DBpedia infrastructure references are external tooling, and no uniqueness theorem or ansatz is imported from the authors' prior work. Therefore no circularity step is established.
Assumptions & free parameters
free parameters (4)
- answer confidence threshold =
not specified
- BM25 top-k for entity matching =
500
- FastText top-k for predicate matching =
50
- Aggregation weights in Algorithm 1 =
equal weights, W scaled by 2/(l+m)
assumptions (4)
- domain assumption Edges in the knowledge graph can be treated as undirected for the target questions.
- domain assumption Complex questions can be decomposed into a sequence of hops, each with entity, property and class references.
- domain assumption The LC-QuAD benchmark is a valid measure of complex KGQA performance.
- domain assumption RDF literals other than rdfs:labels can be ignored.
Cite this review
Pith. "Pith review of Message Passing for Complex Question Answering over Knowledge Graphs." pith.science (2026). https://pith.science/paper/OG42RQ3V
@misc{pith2026190806917,
author = {Pith},
title = {Pith review of: Message Passing for Complex Question Answering over Knowledge Graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/OG42RQ3V}},
note = {Machine review of arXiv:1908.06917}
}
read the original abstract
Question answering over knowledge graphs (KGQA) has evolved from simple single-fact questions to complex questions that require graph traversal and aggregation. We propose a novel approach for complex KGQA that uses unsupervised message passing, which propagates confidence scores obtained by parsing an input question and matching terms in the knowledge graph to a set of possible answers. First, we identify entity, relationship, and class names mentioned in a natural language question, and map these to their counterparts in the graph. Then, the confidence scores of these mappings propagate through the graph structure to locate the answer entities. Finally, these are aggregated depending on the identified question type. This approach can be efficiently implemented as a series of sparse matrix multiplications mimicking joins over small local subgraphs. Our evaluation results show that the proposed approach outperforms the state-of-the-art on the LC-QuAD benchmark. Moreover, we show that the performance of the approach depends only on the quality of the question interpretation results, i.e., given a correct relevance score distribution, our approach always produces a correct answer ranking. Our error analysis reveals correct answers missing from the benchmark dataset and inconsistencies in the DBpedia knowledge graph. Finally, we provide a comprehensive evaluation of the proposed approach accompanied with an ablation study and an error analysis, which showcase the pitfalls for each of the question answering components in more detail.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Jun-Wei Bao, Nan Duan, Zhao Yan, Ming Zhou, and Tiejun Zhao. 2016. Constraint- Based Question Answering with Knowledge Graph. In COLING 2016. 2503–2514
work page 2016
-
[2]
Peter W. Battaglia, Jessica B. Hamrick, et al. 2018. Relational inductive biases, deep learning, and graph networks.CoRR abs/1806.01261 (2018). arXiv:1806.01261
arXiv 2018
-
[3]
Piotr Bojanowski, Edouard Grave, Armand Joulin, and Tomas Mikolov. 2017. En- riching Word Vectors with Subword Information. Transactions of the Association for Computational Linguistics 5 (2017), 135–146
2017
-
[4]
Piero Andrea Bonatti, Stefan Decker, Axel Polleres, and Valentina Presutti. 2018. Knowledge Graphs: New Directions for Knowledge Representation on the Se- mantic Web (Dagstuhl Seminar 18371). Dagstuhl Reports 8, 9 (2018), 29–111
work page 2018
-
[5]
Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. 2015. Large- scale Simple Question Answering with Memory Networks. CoRR abs/1506.02075 (2015). arXiv:1506.02075
arXiv 2015
-
[6]
Wim Bronnenberg, Harry Bunt, Jan Landsbergen, Remko Scha, Wijnand Schoen- makers, and Eric van Utteren. 1980. The question answering system Phliqa1. In Natural Language Question Answering Systems, L. Bolc (Ed.). MacMillan, 217–305
work page 1980
-
[7]
de Faria, Ricardo Usbeck, Alessio Sarullo, Tingting Mu, and André Freitas
Fabrício F. de Faria, Ricardo Usbeck, Alessio Sarullo, Tingting Mu, and André Freitas. 2018. Question Answering Mediated by Visual Clues and Knowledge Graphs. In WWW. 1937–1939
work page 2018
-
[8]
Dennis Diefenbach, Andreas Both, Kamal Deep Singh, and Pierre Maret. 2018. To- wards a Question Answering System over the Semantic Web.CoRR abs/1803.00832 (2018). arXiv:1803.00832
work page Pith review arXiv 2018
Show all 55 references
-
[9]
Mohnish Dubey, Debayan Banerjee, Debanjan Chaudhuri, and Jens Lehmann
-
[10]
Fernández, Miguel A
Javier D. Fernández, Miguel A. Martínez-Prieto, Claudio Gutiérrez, Axel Polleres, and Mario Arias. 2013. Binary RDF Representation for Publication and Exchange (HDT). J. Web Semant. 19 (2013), 22–41
2013
-
[11]
Óscar Ferrández, Christian Spurk, Milen Kouylekov, Iustin Dornescu, Sergio Ferrández, Matteo Negri, Rubén Izquierdo, David Tomás, Constantin Orasan, Guenter Neumann, Bernardo Magnini, and José Luis Vicedo González. 2011. The QALL-ME Framework: A specifiable-domain multilingual...
2011
-
[12]
André Freitas, Edward Curry, João Gabriel Oliveira, and Seán O’Riain. 2012. Querying Heterogeneous Datasets on the Linked Data Web: Challenges, Ap- proaches, and Trends. IEEE Internet Computing 16, 1 (2012), 24–33
2012
-
[13]
André Freitas, João Gabriel Oliveira, Seán O’Riain, João Carlos Pereira da Silva, and Edward Curry. 2013. Querying linked data graphs using semantic relatedness: A vocabulary independent approach. Data Knowl. Eng. 88 (2013), 126–141
2013
-
[14]
Amir Gandomi and Murtaza Haider. 2015. Beyond the hype: Big data concepts, methods, and analytics. International journal of information management 35, 2 (2015), 137–144
2015
-
[15]
Schoenholz, Patrick F
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, et al. 2017. Neural Message Passing for Quantum Chemistry. In ICML 2017. 1263–1272
2017
-
[16]
Yash Goyal, Tejas Khot, et al. 2017. Making the V in VQA Matter: Elevating the Role of Image Understanding in Visual Question Answering. In CVPR 2017
2017
-
[17]
Green, Alice K
Bert F. Green, Alice K. Wolf, Carol Chomsky, and Kenneth Laughery. 1963. Base- ball: An automatic question answerer. In Computers and Thought. McGraw-Hill, 219–224
1963
-
[18]
Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec
William L. Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. 2018. Embedding Logical Queries on Knowledge Graphs. In NeurIPS. 2030–2041
2018
-
[19]
Steve Harris and Andy Seaborne. 2013. SPARQL 1.1 Query Language. W3C Recommendation. (March 2013)
2013
-
[20]
Gary G Hendrix. 1982. Natural-language interface. Computational Linguistics 8, 2 (1982), 56–61
1982
-
[21]
Fuad Jamour, Ibrahim Abdelaziz, and Panos Kalnis. 2018. A demonstration of MAGiQ: matrix algebra approach for solving RDF graph queries. Proc. the VLDB Endowment 11, 12 (2018), 1978–1981
2018
-
[22]
Esther Kaufmann and Abraham Bernstein. 2007. How Useful Are Natural Lan- guage Interfaces to the Semantic Web for Casual End-Users?. In ISWC. 281–294
2007
-
[23]
Bader, Aydin Buluç, Franz Franchetti, John R
Jeremy Kepner, Peter Aaltonen, David A. Bader, Aydin Buluç, Franz Franchetti, John R. Gilbert, Dylan Hutchison, Manoj Kumar, Andrew Lumsdaine, Henning Meyerhenke, Scott McMillan, Carl Yang, John D. Owens, Marcin Zalewski, Tim- othy G. Mattson, and José E. Moreira. 2016. Mathem...
2016
-
[24]
Jin-Dong Kim, Christina Unger, Axel-Cyrille Ngonga Ngomo, André Freitas, YoungGyun Hahm, Jiseong Kim, Gyu-Hyun Choi, Jeonguk Kim, Ricardo Usbeck, Myoung-Gu Kang, and Key-Sun Choi. 2017. OKBQA: an Open Collaboration Framework for Development of Natural Language Question-Answeri...
2017
-
[25]
Daphne Koller, Nir Friedman, and Francis Bach. 2009. Probabilistic Graphical Models: Principles and Techniques. MIT press
2009
-
[26]
Lafferty, Andrew McCallum, and Fernando C
John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001. Condi- tional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In ICML 2001. 282–289
2001
-
[27]
Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, et al. 2015. DBpedia - A large-scale, multilingual knowledge base extracted from Wikipedia. Semantic Web 6, 2 (2015), 167–195
2015
-
[29]
Gaurav Maheshwari, Priyansh Trivedi, Denis Lukovnikov, Nilesh Chakraborty, Asja Fischer, and Jens Lehmann. 2018. Learning to Rank Query Graphs for Complex Question Answering over Knowledge Graphs. arXiv preprint arXiv:1811.01118 (2018)
2018 arXiv
-
[30]
Christopher Manning, Prabhakar Raghavan, and Hinrich Schütze. 2010. Intro- duction to information retrieval. Natural Language Engineering 16, 1 (2010), 100–103
2010
-
[31]
Miguel A Martínez-Prieto, Mario Arias Gallego, and Javier D Fernández. 2012. Exchange and consumption of huge RDF data. In ESWC. 437–452
2012
-
[32]
András Micsik, Sándor Turbucz, and Attila Györök. 2014. LODmilla: a Linked Data Browser for All. In Posters&Demos SEMANTiCS 2014 , Sack Harald, Filipowska Agata, Lehmann Jens, and Hellmann Sebastian (Eds.). CEUR-WS.org, 31–34
2014
-
[33]
Giulio Napolitano, Ricardo Usbeck, and Axel-Cyrille Ngonga Ngomo. 2018. The Scalable Question Answering Over Linked Data (SQA) Challenge 2018. InSemWe- bEval Challenge at ESWC. 69–75
2018
-
[34]
Ajay Patel, Alexander Sands, Chris Callison-Burch, and Marianna Apidianaki
-
[35]
Judea Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc
1988
-
[36]
In EMNLP 2018
Magnitude: A Fast, Efficient Universal Vector Embedding Utility Package. In EMNLP 2018. 120–126
2018
-
[37]
Michael Petrochuk and Luke Zettlemoyer. 2018. SimpleQuestions Nearly Solved: A New Upperbound and Baseline Approach. In EMNLP 2018. 554–558
2018
-
[38]
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global Vectors for Word Representation. InEMNLP 2014. 1532–1543
2014
-
[39]
Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling
Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018. In ESWC. 593–607
2018
-
[40]
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016. SQuAD: 100, 000+ Questions for Machine Comprehension of Text. In EMNLP
2016
-
[41]
Kuldeep Singh, Andreas Both, Arun Sethupat Radhakrishna, and Saeedeh Shekar- pour. 2018. Frankenstein: A Platform Enabling Reuse of Question Answering Components. In ESWC. 624–638
2018
-
[42]
Guus Schreiber and Yves Raimond. 2014. RDF 1.1 Primer. W3C Note. (June 2014)
2014
-
[43]
Kuldeep Singh, Arun Sethupat Radhakrishna, Andreas Both, Saeedeh Shekarpour, Ioanna Lytra, Ricardo Usbeck, Akhilesh Vyas, Akmal Khikmatullaev, Dharmen Punjani, Christoph Lange, Maria-Esther Vidal, Jens Lehmann, and Sören Auer
-
[44]
Kuldeep Singh, Ioanna Lytra, Arun Sethupat Radhakrishna, Saeedeh Shekarpour, Maria-Esther Vidal, and Jens Lehmann. 2018. No One is Perfect: Analysing the Performance of Question Answering Components over the DBpedia Knowledge Graph. CoRR abs/1809.10044 (2018)
2018 arXiv
-
[45]
Priyansh Trivedi, Gaurav Maheshwari, Mohnish Dubey, and Jens Lehmann. 2017. LC-QuAD: A Corpus for Complex Question Answering over Knowledge Graphs. In ISWC. 210–218
2017
-
[46]
Why Reinvent the Wheel: Let’s Build Question Answering Systems To- gether. In WWW. 1247–1256
-
[47]
Daniil Sorokin and Iryna Gurevych. 2018. Modeling Semantics with Gated Graph Neural Networks for Knowledge Base Question Answering. In COLING 2018. 3306–3317
2018
-
[48]
Denny Vrandecic and Markus Krötzsch. 2014. Wikidata: a free collaborative knowledgebase. Commun. ACM 57, 10 (2014), 78–85
2014
-
[49]
Christina Unger, André Freitas, and Philipp Cimiano. 2014. An Introduction to Question Answering over Linked Data. In Reasoning Web. 100–140
2014
-
[50]
Ricardo Usbeck, Ria Hari Gusmita, Axel-Cyrille Ngonga Ngomo, and Muhammad Saleem. 2018. 9th Challenge on Question Answering over Linked Data. In QALD at ISWC. 58–64
2018
-
[51]
William Aaron Woods. 1977. Lunar rocks in natural English: Explorations in nat- ural language question answering. In Linguistic Structures Processing, A. Zampoli (Ed.). Elsevier North-Holland, 521–569
1977
-
[52]
Meng Wang, Ruijie Wang, Jun Liu, Yihe Chen, Lei Zhang, and Guilin Qi. 2018. Towards Empty Answers in SPARQL: Approximating Querying with RDF Em- bedding. In ISWC. 513–529
2018
-
[53]
Xander Wilcke, Peter Bloem, and Victor De Boer. 2017. The knowledge graph as the default data model for learning on heterogeneous knowledge. Data Science (2017), 1–19
2017
-
[55]
Hamid Zafar, Giulio Napolitano, and Jens Lehmann. 2018. Formal Query Genera- tion for Question Answering over Knowledge Bases. In ESWC. 714–728
2018
-
[56]
Lei Zou, Ruizhe Huang, Haixun Wang, Jeffrey Xu Yu, Wenqiang He, and Dongyan Zhao. 2014. Natural language question answering over RDF: a graph data driven approach. In SIGMOD 2014. 313–324
2014
-
[2018]
In ISWC 2018
EARL: Joint Entity and Relation Linking for Question Answering over Knowledge Graphs. In ISWC 2018. 108–126
2018
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.