---
title: "Constraint-Based Question Answering with Knowledge Graph"
description: "First, they release ComplexQuestions, a dataset of 2,100 multi-constraint question–answer… 42.33 F1. 29 references, cited by 70 papers here."
authors: ["Junwei Bao", "Nan Duan", "Zhao Yan", "Ming Zhou", "Tiejun Zhao"]
year: 2016
venue: "Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers"
source: "https://aclanthology.org/C16-1236/"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/bao-2016-constraint-based-question-answering-knowledge/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/bao-2016-constraint-based-question-answering-knowledge/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2016](https://md.research.elamur.ai/free/en/papers/2016/page/2/) / Constraint-Based Question Answering with Knowledge Graph

# Constraint-Based Question Answering with Knowledge Graph

**Authors:** Junwei Bao, [Nan Duan](https://md.research.elamur.ai/free/en/authors/nan-duan/), [Zhao Yan](https://md.research.elamur.ai/free/en/authors/zhao-yan/), [Ming Zhou](https://md.research.elamur.ai/free/en/authors/ming-zhou/) and [Tiejun Zhao](https://md.research.elamur.ai/free/en/authors/tiejun-zhao/) · **Year:** 2016 · **Venue:** [Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers](https://md.research.elamur.ai/free/en/venues/coling/) ([COLING 2016](https://md.research.elamur.ai/free/en/venues/coling/2016/)) · **Publisher:** [International Committee on Computational Linguistics (ICCL)](https://md.research.elamur.ai/free/en/publishers/international-committee-on-computational-linguistics-iccl/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/C16-1236/) · [PDF](https://aclanthology.org/C16-1236.pdf) · [OpenAlex](https://openalex.org/W2572289264)

**Citations:** 158 citations (OpenAlex, 2026-10-14) · [70](https://md.research.elamur.ai/free/en/papers/bao-2016-constraint-based-question-answering-knowledge/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
Popular KBQA benchmarks such as WebQuestions and SimpleQuestions consist mostly of questions answerable through a single Freebase relation. They therefore reveal little about how systems handle questions with several restrictions on the answer. Bao et al. address this gap in two ways.

First, they release ComplexQuestions, a dataset of 2,100 multi-constraint question–answer pairs. It combines filtered search-engine queries, existing resources and manual labeling. Second, they propose a systematic KBQA approach. A question is mapped to a multi-constraint query graph (MulCG): a basic subject–path–answer graph is extended step by step with an ordered sequence of constraints. These constraints are expressed through relational edges and functional predicates such as comparison, ranking and counting, and the graph is then executed against Freebase.

Compared with a re-implemented STAGG baseline, the method gains roughly 4 F1 points on ComplexQuestions and stays on par on WebQuestions. It also performs reasonably on SimpleQuestions. The work matters because it gives the field both a benchmark and a structured method for compositional questions beyond single-relation lookup.

## Key points
- The paper defines six constraint categories, with these frequencies in web queries: multi-entity (30.6%), type (38.8%), explicit temporal (10.4%), implicit temporal (3.5%), ordinal (5.1%) and aggregation (1.2%).
- ComplexQuestions has 2,100 QA pairs, split into 1,300 train and 800 test. Its sources are:
  - 596 training and 326 test pairs from WebQuestions,
  - 300 pairs from Yin et al. (2015),
  - 878 newly hand-labeled pairs drawn from a three-month 2015 search log of about 21M distinct 5W1H questions.
- Functional predicates in the query graph include Equal, \<, >, MaxAtN, MinAtN and Count. Each is triggered by cues such as "before/after", WordNet superlatives or "how many".
- On ComplexQuestions, the best setting reaches 42.33 F1 versus 37.69 for STAGG. Removing constraints costs about 10.5 points.
- On WebQuestions the method scores 54.36 average F1 (STAGG re-implementation: 54.30). On SimpleQuestions it reaches 72.78 accuracy using a dictionary-based entity linker.

## Interesting ideas
- **Building a "hard" benchmark by mining logs with cheap heuristics.** The authors filter real queries with simple rules before annotation: length limits, no pronouns, a detected entity, vocabulary overlap with the training data, and category triggers. This keeps human effort focused on relevant candidates and could be reused to build challenge sets for low-resource languages.
- **Sampling annotation candidates by the observed distribution of phenomena.** The selected candidates mirror the observed frequency of each constraint type. As a result, the benchmark reflects what users actually ask rather than what is easy to generate.
- **Composing a query incrementally.** The query starts from a simple core graph, and constraints are attached one at a time in a fixed order. This modular design lets new constraint types (e.g., temporal or ordinal) be added without redesigning the whole parser.
- **Rewriting implicit time as explicit time.** Clauses like "when the Civil War started" are first resolved to a concrete date and then treated as a normal temporal comparison. Reducing a hard case to an already solved one is a reusable trick for temporal QA.
- **Ablating constraints and training-data mixtures separately.** The authors measure the effect of adding constraints independently from the effect of enlarging CNN training data with other datasets. This clarifies where the gains actually come from, which is a good evaluation practice for any pipeline.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Microsoft](https://md.research.elamur.ai/free/en/companies/microsoft/) — Company, Redmond, United States · 240 works · 123,537 citations
- [Harbin Institute of Technology](https://md.research.elamur.ai/free/en/universities/harbin-institute-of-technology/) — University, Harbin, China · 76 works · 27,918 citations
- [Beihang University](https://md.research.elamur.ai/free/en/universities/beihang-university/) — University, Beijing, China · 27 works · 8,089 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works

🧭 Topics (2): [❓ Question answering](https://md.research.elamur.ai/free/en/topics/question-answering/) · 243 works · [🕸️ Knowledge graphs & ontologies](https://md.research.elamur.ai/free/en/topics/knowledge-graphs/) · 103 works

## Cite

Cite as: Junwei Bao, Nan Duan, Zhao Yan, Ming Zhou and Tiejun Zhao. 2016. Constraint-Based Question Answering with Knowledge Graph. Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{bao2016constraint,
  title = {{Constraint-Based Question Answering with Knowledge Graph}},
  author = {Junwei Bao, Nan Duan, Zhao Yan, Ming Zhou and Tiejun Zhao},
  booktitle = {Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers},
  year = {2016},
  url = {https://aclanthology.org/C16-1236/}
}
```

- [← previous Overview for the Second Shared Task on Language Identification in Code-Switched Data](https://md.research.elamur.ai/free/en/papers/molina-2016-overview-second-shared-task-language/)
- [next → A Language-Independent Neural Network for Event Detection](https://md.research.elamur.ai/free/en/papers/feng-2016-language-independent-neural-network-event/)
- [↑ back to papers of 2016](https://md.research.elamur.ai/free/en/papers/2016/page/2/)

## References

29 references, 8 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Junwei Bao, Nan Duan, Ming Zhou, and Tiejun Zhao. 2014. Knowledge-based question answering as machine translation. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 967–976, Baltimore, Maryland, June. Association for Computation… [find](https://scholar.google.com/scholar?q=Junwei+Bao%2C+Nan+Duan%2C+Ming+Zhou%2C+and+Tiejun+Zhao%2E+2014%2E+Knowledge%2Dbased+question+answering+as+machine+translation%2E+In+Proceedings+of+the+52nd+Annual+Meeting+of+the+Association+for+Computational+Lingui)
2. Jonathan Berant and Percy Liang. 2014. [Semantic parsing via paraphrasing](https://md.research.elamur.ai/free/en/papers/berant-2014-semantic-parsing-paraphrasing/). In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA, Volume 1: Long Papers, pages 1415–1425.
3. Jonathan Berant and Percy Liang. 2015. Imitation learning of agenda-based semantic parsers. Transactions of the Association for Computational Linguistics, 3:545–558. [find](https://scholar.google.com/scholar?q=Jonathan+Berant+and+Percy+Liang%2E+2015%2E+Imitation+learning+of+agenda%2Dbased+semantic+parsers%2E+Transactions+of+the+Association+for+Computational+Linguistics%2C+3%3A545%E2%80%93558%2E)
4. Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. 2013. [Semantic parsing on Freebase from question-answer pairs](https://md.research.elamur.ai/free/en/papers/berant-2013-semantic-parsing-freebase-question-answer/). In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1533–1544, Seattle, Washington, USA, October. Association for Computational Ling…
5. Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 1247–1250. ACM. [find](https://scholar.google.com/scholar?q=Kurt+Bollacker%2C+Colin+Evans%2C+Praveen+Paritosh%2C+Tim+Sturge%2C+and+Jamie+Taylor%2E+2008%2E+Freebase%3A+a+collaboratively+created+graph+database+for+structuring+human+knowledge%2E+In+Proceedings+of+the+2008+ACM+SI)
6. Antoine Bordes, Sumit Chopra, and Jason Weston. 2014a. Question answering with subgraph embeddings. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, a Special Interest Group of the ACL, pages… [find](https://scholar.google.com/scholar?q=Antoine+Bordes%2C+Sumit+Chopra%2C+and+Jason+Weston%2E+2014a%2E+Question+answering+with+subgraph+embeddings%2E+In+Proceedings+of+the+2014+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+EMNLP+201)
7. Antoine Bordes, Jason Weston, and Nicolas Usunier. 2014b. Open question answering with weakly supervised embedding models. In Machine Learning and Knowledge Discovery in Databases, pages 165–180. Springer. [find](https://scholar.google.com/scholar?q=Antoine+Bordes%2C+Jason+Weston%2C+and+Nicolas+Usunier%2E+2014b%2E+Open+question+answering+with+weakly+supervised+embedding+models%2E+In+Machine+Learning+and+Knowledge+Discovery+in+Databases%2C+pages+165%E2%80%93180%2E+Spri)
8. Antoine Bordes, Nicolas Usunier, Sumit Chopra, and Jason Weston. 2015. Large-scale simple question answering with memory networks. arXiv preprint arXiv:1506.02075. [find](https://scholar.google.com/scholar?q=Antoine+Bordes%2C+Nicolas+Usunier%2C+Sumit+Chopra%2C+and+Jason+Weston%2E+2015%2E+Large%2Dscale+simple+question+answering+with+memory+networks%2E+arXiv+preprint+arXiv%3A1506%2E02075%2E)
9. Christopher JC Burges. 2010. From ranknet to lambdarank to lambdamart: An overview. Learning, 11:23–581. [find](https://scholar.google.com/scholar?q=Christopher+JC+Burges%2E+2010%2E+From+ranknet+to+lambdarank+to+lambdamart%3A+An+overview%2E+Learning%2C+11%3A23%E2%80%93581%2E)
10. Marie-Catherine De Marneffe, Bill MacCartney, Christopher D Manning, et al. 2006. [Generating typed dependency parses from phrase structure parses](https://md.research.elamur.ai/free/en/papers/marneffe-2006-generating-typed-dependency-parses-phrase/). In Proceedings of LREC, volume 6, pages 449–454.
11. Li Dong, Furu Wei, Ming Zhou, and Ke Xu. 2015. Question answering over freebase with multi-column convolutional neural networks. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volum… [find](https://scholar.google.com/scholar?q=Li+Dong%2C+Furu+Wei%2C+Ming+Zhou%2C+and+Ke+Xu%2E+2015%2E+Question+answering+over+freebase+with+multi%2Dcolumn+convolutional+neural+networks%2E+In+Proceedings+of+the+53rd+Annual+Meeting+of+the+Association+for+Comput)
12. Anthony Fader, Luke Zettlemoyer, and Oren Etzioni. 2014. Open question answering over curated and extracted knowledge bases. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1156–1165. ACM. [find](https://scholar.google.com/scholar?q=Anthony+Fader%2C+Luke+Zettlemoyer%2C+and+Oren+Etzioni%2E+2014%2E+Open+question+answering+over+curated+and+extracted+knowledge+bases%2E+In+Proceedings+of+the+20th+ACM+SIGKDD+international+conference+on+Knowledge)
13. Jenny Rose Finkel, Trond Grenager, and Christopher Manning. 2005. [Incorporating non-local information into information extraction systems by gibbs sampling](https://md.research.elamur.ai/free/en/papers/finkel-2005-incorporating-non-local-information-into/). In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, pages 363–370. Association for Computational Linguistic…
14. Jianfeng Gao, Li Deng, Michael Gamon, Xiaodong He, and Patrick Pantel. 2015. Modeling interestingness with deep neural networks, December 17. US Patent 20,150,363,688. [find](https://scholar.google.com/scholar?q=Jianfeng+Gao%2C+Li+Deng%2C+Michael+Gamon%2C+Xiaodong+He%2C+and+Patrick+Pantel%2E+2015%2E+Modeling+interestingness+with+deep+neural+networks%2C+December+17%2E+US+Patent+20%2C150%2C363%2C688%2E)
15. George A Miller. 1995. [Wordnet: a lexical database for english](https://md.research.elamur.ai/free/en/papers/miller-1994-wordnet/). Communications of the ACM, 38(11):39–41.
16. Siva Reddy, Mirella Lapata, and Mark Steedman. 2014. Large-scale semantic parsing without question-answer pairs. Transactions of the Association for Computational Linguistics, 2:377–392. [find](https://scholar.google.com/scholar?q=Siva+Reddy%2C+Mirella+Lapata%2C+and+Mark+Steedman%2E+2014%2E+Large%2Dscale+semantic+parsing+without+question%2Danswer+pairs%2E+Transactions+of+the+Association+for+Computational+Linguistics%2C+2%3A377%E2%80%93392%2E)
17. Siva Reddy, Oscar Täckström, Michael Collins, Tom Kwiatkowski, Dipanjan Das, Mark Steedman, and Mirella Lapata. 2016. Transforming dependency structures to logical forms for semantic parsing. Transactions of the Association for Computational Linguistics, 4:127–140. [find](https://scholar.google.com/scholar?q=Siva+Reddy%2C+Oscar+Ta%CC%88ckstro%CC%88m%2C+Michael+Collins%2C+Tom+Kwiatkowski%2C+Dipanjan+Das%2C+Mark+Steedman%2C+and+Mirella+Lapata%2E+2016%2E+Transforming+dependency+structures+to+logical+forms+for+semantic+parsing%2E+Transa)
18. Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil. 2014a. A latent semantic model with convolutional-pooling structure for information retrieval. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pages 101–110. ACM. [find](https://scholar.google.com/scholar?q=Yelong+Shen%2C+Xiaodong+He%2C+Jianfeng+Gao%2C+Li+Deng%2C+and+Gre%CC%81goire+Mesnil%2E+2014a%2E+A+latent+semantic+model+with+convolutional%2Dpooling+structure+for+information+retrieval%2E+In+Proceedings+of+the+23rd+ACM+Int)
19. Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil. 2014b. Learning semantic representations using convolutional neural networks for web search. In Proceedings of the companion publication of the 23rd international conference on World wide web companion, pages 373–374. Internation… [find](https://scholar.google.com/scholar?q=Yelong+Shen%2C+Xiaodong+He%2C+Jianfeng+Gao%2C+Li+Deng%2C+and+Gre%CC%81goire+Mesnil%2E+2014b%2E+Learning+semantic+representations+using+convolutional+neural+networks+for+web+search%2E+In+Proceedings+of+the+companion+publ)
20. Zhenghao Wang, Shengquan Yan, Huaming Wang, and Xuedong Huang. 2014. An overview of microsoft deep qa system on stanford webquestions benchmark. Technical report, Technical report, Microsoft Research. [find](https://scholar.google.com/scholar?q=Zhenghao+Wang%2C+Shengquan+Yan%2C+Huaming+Wang%2C+and+Xuedong+Huang%2E+2014%2E+An+overview+of+microsoft+deep+qa+system+on+stanford+webquestions+benchmark%2E+Technical+report%2C+Technical+report%2C+Microsoft+Research%2E)
21. Kun Xu, Siva Reddy, Yansong Feng, Songfang Huang, and Dongyan Zhao. 2016. [Question answering on freebase via relation extraction and textual evidence](https://md.research.elamur.ai/free/en/papers/xu-2016-question-answering-freebase-relation-extraction/). In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2326–2336, Berlin, Germany,…
22. Yi Yang and Ming-Wei Chang. 2015. S-mart: Novel tree-based structured learning algorithms applied to tweet entity linking. [find](https://scholar.google.com/scholar?q=Yi+Yang+and+Ming%2DWei+Chang%2E+2015%2E+S%2Dmart%3A+Novel+tree%2Dbased+structured+learning+algorithms+applied+to+tweet+entity+linking%2E)
23. Min-Chul Yang, Nan Duan, Ming Zhou, and Hae-Chang Rim. 2014. Joint relational embeddings for knowledge-based question answering. In EMNLP, pages 645–650. [find](https://scholar.google.com/scholar?q=Min%2DChul+Yang%2C+Nan+Duan%2C+Ming+Zhou%2C+and+Hae%2DChang+Rim%2E+2014%2E+Joint+relational+embeddings+for+knowledge%2Dbased+question+answering%2E+In+EMNLP%2C+pages+645%E2%80%93650%2E)
24. Xuchen Yao and Benjamin Van Durme. 2014. Information extraction over structured data: Question answering with freebase. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA, Volume 1: Long Papers, pages 956–966. [find](https://scholar.google.com/scholar?q=Xuchen+Yao+and+Benjamin+Van+Durme%2E+2014%2E+Information+extraction+over+structured+data%3A+Question+answering+with+freebase%2E+In+Proceedings+of+the+52nd+Annual+Meeting+of+the+Association+for+Computational+L)
25. Xuchen Yao. 2015. Lean question answering over freebase from scratch. In Proceedings of NAACL-HLT, pages 66–70. [find](https://scholar.google.com/scholar?q=Xuchen+Yao%2E+2015%2E+Lean+question+answering+over+freebase+from+scratch%2E+In+Proceedings+of+NAACL%2DHLT%2C+pages+66%E2%80%9370%2E)
26. Wen-tau Yih, Xiaodong He, and Christopher Meek. 2014. [Semantic parsing for single-relation question answering](https://md.research.elamur.ai/free/en/papers/yih-2014-semantic-parsing-single-relation-question/). In ACL (2), pages 643–648. Citeseer.
27. Wen-tau Yih, Ming-Wei Chang, Xiaodong He, and Jianfeng Gao. 2015. [Semantic parsing via staged query graph generation: Question answering with knowledge base](https://md.research.elamur.ai/free/en/papers/yih-2015-semantic-parsing-staged-query-graph/). In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natur…
28. Pengcheng Yin, Nan Duan, Ben Kao, Junwei Bao, and Ming Zhou. 2015. Answering questions with complex semantic constraints on open knowledge bases. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pages 1301–1310. ACM. [find](https://scholar.google.com/scholar?q=Pengcheng+Yin%2C+Nan+Duan%2C+Ben+Kao%2C+Junwei+Bao%2C+and+Ming+Zhou%2E+2015%2E+Answering+questions+with+complex+semantic+constraints+on+open+knowledge+bases%2E+In+Proceedings+of+the+24th+ACM+International+on+Confer)
29. Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Proceedings of the Conference, 19-24 June, 2011, Portland, Oregon, USA - Short Papers, pages 1… [find](https://scholar.google.com/scholar?q=Yue+Zhang+and+Joakim+Nivre%2E+2011%2E+Transition%2Dbased+dependency+parsing+with+rich+non%2Dlocal+features%2E+In+The+49th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%3A+Human+Language+Technolo)

*Updated 24 October 2026*