---
title: "Structured Relation Discovery using Generative Models (2011)"
description: "The authors propose three topic-model-style generative models in which the latent \"topic\" is a relation… 29 references, cited by 71 papers here."
authors: ["Limin Yao", "Aria Haghighi", "Sebastian Riedel", "Andrew McCallum"]
year: 2011
venue: "Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing"
source: "https://aclanthology.org/D11-1135/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/yao-2011-structured-relation-discovery-generative-models/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/yao-2011-structured-relation-discovery-generative-models/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2011](https://md.research.elamur.ai/free/en/papers/2011/) / Structured Relation Discovery using Generative Models

# Structured Relation Discovery using Generative Models

**Authors:** Limin Yao, [Aria Haghighi](https://md.research.elamur.ai/free/en/authors/aria-haghighi/), [Sebastian Riedel](https://md.research.elamur.ai/free/en/authors/sebastian-riedel/) and [Andrew McCallum](https://md.research.elamur.ai/free/en/authors/andrew-mccallum/) · **Year:** 2011 · **Venue:** [Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing](https://md.research.elamur.ai/free/en/venues/emnlp/) ([EMNLP 2011](https://md.research.elamur.ai/free/en/venues/emnlp/2011/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/D11-1135/) · [PDF](https://aclanthology.org/D11-1135.pdf) · [OpenAlex](https://openalex.org/W115166160)

**Citations:** 145 citations (OpenAlex, 2026-10-14) · [71](https://md.research.elamur.ai/free/en/papers/yao-2011-structured-relation-discovery-generative-models/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
The paper tackles unsupervised relation discovery between pairs of named entities. The set of relation types is not fixed in advance but induced from unlabeled text. Each document is treated as a bag of tuples: a dependency path plus its source and destination entity mentions. The authors propose three topic-model-style generative models in which the latent "topic" is a relation type rather than a word theme:
- **Rel-LDA** generates only the three tuple components.
- **Rel-LDA1** adds richer lexical, syntactic and entity-tag features.
- **Type-LDA** also infers latent entity types for both arguments, so relation and entity clusters are learned jointly.

The models are evaluated in two ways. Intrinsically, induced clusters are compared against Freebase relations. Extrinsically, the clusters serve as features in a distant supervision relation extractor. There they give a 12% error reduction in precision over a strong weakly supervised baseline and find more facts without a notable accuracy drop. The approach also scales better than USP and beats DIRT and USP at equal data sizes, which makes open-domain relation induction practical on large corpora.

## Key points
- **Tuple representation.** Each observation is (source NE, dependency path, destination NE). For example, "John Lennon was born in Liverpool" yields a path through nsubjpass, *born* and *in*.
- **Rel-LDA1 features:** path, source, destination, trigger words (non-stopword path words), lexical pattern, POS pattern, NER tag pair and syntactic category pair.
- **Type-LDA structure:** it draws a relation plus two hidden entity types per tuple, and argument features are generated from those types.
- **Scalability of USP.** Training the public USP code on only 1,000 documents needed about 45 GB of JVM heap, which shows why it is hard to scale.
- **Manual evaluation.** Top-50 precision was checked for frequent relations (e.g., worksFor, containedBy, bornIn, founder) across the distant supervision baseline, Rel-LDA1 and Type-LDA features. For containedBy, extracted instances rose from 670 to 714 to 804.
- **Metric mismatch.** Clustering quality against Freebase did not consistently predict downstream distant supervision performance.

## Interesting ideas
- **Swap the unit of observation in a topic model.** Replacing words with structured tuples of independent features turns LDA into a relation clusterer. The same trick could cluster other structured events, such as trade records or place descriptions.
- **Curriculum-style feature introduction.** Training starts with only the core features and adds one new feature type every 10 iterations, in a fixed order. This stabilizes EM-like learning and could help any feature-rich unsupervised model avoid poor early solutions.
- **Entity-type pairs as a splitting signal.** Adding NER pairs like PER-LOC versus ORG-LOC breaks apart clusters that mix relations with similar wording but different argument types. This is a cheap way to enforce selectional constraints.
- **Joint induction of relation and argument types.** Type-LDA learns entity clusters as a byproduct of relation clustering. This is useful when no fine-grained entity typing exists, for example in a lower-resource language.
- **Pair intrinsic with extrinsic evaluation.** Using induced clusters as features for a distantly supervised extractor gives a task-based check. Since the two measures disagreed here, relying on only one of them can be misleading.

*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

- [Massachusetts Institute of Technology](https://md.research.elamur.ai/free/en/universities/massachusetts-institute-of-technology/) — University, Cambridge, United States · 159 works · 65,157 citations
- [University of Massachusetts Amherst](https://md.research.elamur.ai/free/en/universities/university-of-massachusetts-amherst/) — University, Amherst Center, United States · 67 works · 64,591 citations
- [MIT Computer Science and Artificial Intelligence Laboratory](https://md.research.elamur.ai/free/en/labs/mit-computer-science-and-artificial-intelligence-laboratory/) — Research institute, Cambridge, United States · 54 works · 29,441 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 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

## Cite

Cite as: Limin Yao, Aria Haghighi, Sebastian Riedel and Andrew McCallum. 2011. Structured Relation Discovery using Generative Models. Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing.

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

```bibtex
@inproceedings{yao2011structured,
  title = {{Structured Relation Discovery using Generative Models}},
  author = {Limin Yao, Aria Haghighi, Sebastian Riedel and Andrew McCallum},
  booktitle = {Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing},
  year = {2011},
  url = {https://aclanthology.org/D11-1135/}
}
```

- [← previous Automatically Evaluating Text Coherence Using Discourse Relations](https://md.research.elamur.ai/free/en/papers/lin-2011-automatically-evaluating-text-coherence-discourse/)
- [next → READ–IT: Assessing Readability of Italian Texts with a View to Text Simplification](https://md.research.elamur.ai/free/en/papers/orletta-2011-read-it-assessing-readability-italian/)
- [↑ back to papers of 2011](https://md.research.elamur.ai/free/en/papers/2011/)

## References

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

1. Michele Banko and Oren Etzioni. 2008. The tradeoffs between open and traditional relation extraction. In Proceedings of ACL-08: HLT. [find](https://scholar.google.com/scholar?q=Michele+Banko+and+Oren+Etzioni%2E+2008%2E+The+tradeoffs+between+open+and+traditional+relation+extraction%2E+In+Proceedings+of+ACL%2D08%3A+HLT%2E)
2. Michele Banko, Michael J Cafarella, Stephen Soderland, Matt Broadhead, and Oren Etzioni. 2007. [Open information extraction from the web](https://md.research.elamur.ai/free/en/papers/banko-2007-open-information-extraction-web/). In Proceedings of IJCAI2007.
3. David Blei, Andrew Ng, and Michael Jordan. 2003. [Latent Dirichlet allocation](https://md.research.elamur.ai/free/en/papers/blei-2003-latent-dirichlet-allocation/). Journal of Machine Learning Research, 3:993–1022, January.
4. Danushka Bollegala, Yutaka Matsuo, and Mitsuru Ishizuka. 2010. Relational duality: Unsupervised extraction of semantic relations between entities on the web. In Proceedings of WWW. [find](https://scholar.google.com/scholar?q=Danushka+Bollegala%2C+Yutaka+Matsuo%2C+and+Mitsuru+Ishizuka%2E+2010%2E+Relational+duality%3A+Unsupervised+extraction+of+semantic+relations+between+entities+on+the+web%2E+In+Proceedings+of+WWW%2E)
5. Sergey Brin. 1998. Extracting patterns and relations from the world wide web. In Proc. of WebDB Workshop at 6th International Conference on Extending Database Technology. [find](https://scholar.google.com/scholar?q=Sergey+Brin%2E+1998%2E+Extracting+patterns+and+relations+from+the+world+wide+web%2E+In+Proc%2E+of+WebDB+Workshop+at+6th+International+Conference+on+Extending+Database+Technology%2E)
6. Razvan C. Bunescu and Raymond J. Mooney. 2007. [Learning to extract relations from the web using minimal supervision](https://md.research.elamur.ai/free/en/papers/bunescu-2007-learning-extract-relations-web-minimal/). In Proceedings of the 45rd Annual Meeting of the Association for Computational Linguistics (ACL ’07).
7. Eugene Charniak and Micha Elsner. 2009. [Em works for pronoun anaphora resolution](https://md.research.elamur.ai/free/en/papers/charniak-2009-em-works-pronoun-anaphora-resolution/). In Proceedings of ACL.
8. Harr Chen, Edward Benson, Tahira Naseem, and Regina Barzilay. 2011. In-domain relation discovery with meta-constraints via posterior regularization. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Harr+Chen%2C+Edward+Benson%2C+Tahira+Naseem%2C+and+Regina+Barzilay%2E+2011%2E+In%2Ddomain+relation+discovery+with+meta%2Dconstraints+via+posterior+regularization%2E+In+Proceedings+of+ACL%2E)
9. Aron Culotta and Jeffery Sorensen. 2004. [Dependency tree kernels for relation extraction](https://md.research.elamur.ai/free/en/papers/culotta-2004-dependency-tree-kernels-relation-extraction/). In 42nd Annual Meeting of the Association for Computational Linguistics, Barcelona, Spain.
10. 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 of the Association for Computational Linguistics (ACL ’05), pages 363–370, June.
11. Benjamin Hachey. 2009. Towards Generic Relation Extraction. Ph.D. thesis, University of Edinburgh. [find](https://scholar.google.com/scholar?q=Benjamin+Hachey%2E+2009%2E+Towards+Generic+Relation+Extraction%2E+Ph%2ED%2E+thesis%2C+University+of+Edinburgh%2E)
12. Aria Haghighi and Dan Klein. 2010. [Coreference resolution in a modular, entity-centered model](https://md.research.elamur.ai/free/en/papers/haghighi-2010-coreference-resolution-modular-entity-centered/). In Proceedings of HLT-NAACL.
13. Takaaki Hasegawa, Satoshi Sekine, and Ralph Grishman. 2004. [Discovering relations among named entities from large corpora](https://md.research.elamur.ai/free/en/papers/hasegawa-2004-discovering-relations-among-named-entities/). In ACL.
14. Nanda Kambhatla. 2004. Combining lexical, syntactic, and semantic features with maximum entropy models for extracting relations. In Proceedings of ACL. [find](https://scholar.google.com/scholar?q=Nanda+Kambhatla%2E+2004%2E+Combining+lexical%2C+syntactic%2C+and+semantic+features+with+maximum+entropy+models+for+extracting+relations%2E+In+Proceedings+of+ACL%2E)
15. Zornitsa Kozareva and Eduard Hovy. 2010. Learning arguments and supertypes of semantic relations using recursive patterns. In Proceedings of ACL 10. [find](https://scholar.google.com/scholar?q=Zornitsa+Kozareva+and+Eduard+Hovy%2E+2010%2E+Learning+arguments+and+supertypes+of+semantic+relations+using+recursive+patterns%2E+In+Proceedings+of+ACL+10%2E)
16. Dekang Lin and Patrick Pantel. 2001. Dirt - discovery of inference rules from text. In Proceedings of KDD. [find](https://scholar.google.com/scholar?q=Dekang+Lin+and+Patrick+Pantel%2E+2001%2E+Dirt+%2D+discovery+of+inference+rules+from+text%2E+In+Proceedings+of+KDD%2E)
17. Dekang Lin. 1998. Dependency-based evaluation of minipar. In Proceedings of the Workshop on the Evaluation of Parsing Systems. [find](https://scholar.google.com/scholar?q=Dekang+Lin%2E+1998%2E+Dependency%2Dbased+evaluation+of+minipar%2E+In+Proceedings+of+the+Workshop+on+the+Evaluation+of+Parsing+Systems%2E)
18. Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky. 2009. Distant supervision for relation extraction without labeled data. In ACL-IJCNLP. [find](https://scholar.google.com/scholar?q=Mike+Mintz%2C+Steven+Bills%2C+Rion+Snow%2C+and+Dan+Jurafsky%2E+2009%2E+Distant+supervision+for+relation+extraction+without+labeled+data%2E+In+ACL%2DIJCNLP%2E)
19. J. Nivre, J. Hall, and J. Nilsson. 2004. [Memory-based dependency parsing](https://md.research.elamur.ai/free/en/papers/nivre-2004-memory-based-dependency-parsing/). In Proceedings of CoNLL, pages 49–56.
20. Hoifung Poon and Pedro Domingos. 2008. [Unsupervised semantic parsing](https://md.research.elamur.ai/free/en/papers/poon-2009-unsupervised-semantic-parsing/). In Proceedings of the Conference on Empirical methods in natural language processing (EMNLP).
21. Deepak Ravichandran and Eduard Hovy. 2002. [Learning surface text patterns for a question answering system](https://md.research.elamur.ai/free/en/papers/ravichandran-2002-learning-surface-text-patterns-question/). In Proceedings of ACL.
22. Sebastian Riedel, Limin Yao, and Andrew McCallum. 2010. Modeling relations and their mentions without labeled text. In Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD ’10). [find](https://scholar.google.com/scholar?q=Sebastian+Riedel%2C+Limin+Yao%2C+and+Andrew+McCallum%2E+2010%2E+Modeling+relations+and+their+mentions+without+labeled+text%2E+In+Proceedings+of+the+European+Conference+on+Machine+Learning+and+Knowledge+Discover)
23. Alan Ritter, Mausam, and Oren Etzioni. 2010. A latent dirichlet allocation method for selectional preferences. In Proceedings of ACL10. [find](https://scholar.google.com/scholar?q=Alan+Ritter%2C+Mausam%2C+and+Oren+Etzioni%2E+2010%2E+A+latent+dirichlet+allocation+method+for+selectional+preferences%2E+In+Proceedings+of+ACL10%2E)
24. Dan Roth and Wen tau Yih. 2002. Probabilistic reasoning for entity and relation recognition. In Proceedings of Coling. [find](https://scholar.google.com/scholar?q=Dan+Roth+and+Wen+tau+Yih%2E+2002%2E+Probabilistic+reasoning+for+entity+and+relation+recognition%2E+In+Proceedings+of+Coling%2E)
25. Evan Sandhaus, 2008. The New York Times Annotated Corpus. Linguistic Data Consortium, Philadelphia. [find](https://scholar.google.com/scholar?q=Evan+Sandhaus%2C+2008%2E+The+New+York+Times+Annotated+Corpus%2E+Linguistic+Data+Consortium%2C+Philadelphia%2E)
26. Diarmuid O Seaghdha. 2010. Latent variable models of selectional preference. In Proceedings of ACL 10. [find](https://scholar.google.com/scholar?q=Diarmuid+O+Seaghdha%2E+2010%2E+Latent+variable+models+of+selectional+preference%2E+In+Proceedings+of+ACL+10%2E)
27. Kristina Toutanova, Dan Klein, Christopher Manning, and Yoram Singer. 2003. [Feature-rich part-of-speech tagging with a cyclic dependency network](https://md.research.elamur.ai/free/en/papers/toutanova-2003-feature-rich-part-speech-tagging/). In HLT-NAACL, pages 252–259.
28. Limin Yao, Sebastian Riedel, and Andrew McCallum. 2010. Collective cross-document relation extraction without labelled data. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1013–1023, Cambridge, MA, October. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Limin+Yao%2C+Sebastian+Riedel%2C+and+Andrew+McCallum%2E+2010%2E+Collective+cross%2Ddocument+relation+extraction+without+labelled+data%2E+In+Proceedings+of+the+2010+Conference+on+Empirical+Methods+in+Natural+Langu)
29. Alexander Yates and Oren Etzioni. 2009. Unsupervised methods for determining object and relation synonyms on the web. Journal of Artificial Intelligence Research, 34:255–296. [find](https://scholar.google.com/scholar?q=Alexander+Yates+and+Oren+Etzioni%2E+2009%2E+Unsupervised+methods+for+determining+object+and+relation+synonyms+on+the+web%2E+Journal+of+Artificial+Intelligence+Research%2C+34%3A255%E2%80%93296%2E)

*Updated 24 October 2026*