---
title: "Graph-Based Generation of Referring Expressions (2003)"
description: "This paper addresses content determination for referring expressions: choosing which properties and… 37 references, cited by 71 papers here."
authors: ["Emiel Krahmer", "Sebastiaan van Erk", "André Verleg"]
year: 2003
venue: "Computational Linguistics"
source: "https://aclanthology.org/J03-1003/"
doi: "10.1162/089120103321337430"
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/krahmer-2003-graph-based-generation-referring-expressions/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/krahmer-2003-graph-based-generation-referring-expressions/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2003](https://md.research.elamur.ai/free/en/papers/2003/) / Graph-Based Generation of Referring Expressions

# Graph-Based Generation of Referring Expressions

**Authors:** [Emiel Krahmer](https://md.research.elamur.ai/free/en/authors/emiel-krahmer/), Sebastiaan van Erk and André Verleg · **Year:** 2003 · **Venue:** [Computational Linguistics](https://md.research.elamur.ai/free/en/venues/cl/) ([Computational Linguistics 2003](https://md.research.elamur.ai/free/en/venues/cl/2003/)) · **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/J03-1003/) · [PDF](https://aclanthology.org/J03-1003.pdf) · [DOI 10.1162/089120103321337430](https://doi.org/10.1162/089120103321337430) · [OpenAlex](https://openalex.org/W2096646663)

**Citations:** 207 citations (OpenAlex, 2026-10-14) · [71](https://md.research.elamur.ai/free/en/papers/krahmer-2003-graph-based-generation-referring-expressions/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
This paper addresses content determination for referring expressions: choosing which properties and relations of a target object to mention so that a hearer can tell it apart from distractor objects. The authors model a scene (objects, their attributes and the relations between them) as a labeled directed graph. Choosing content then becomes the task of building a subgraph around the target that fits no distractor. A branch and bound search, steered by cost functions, explores candidate subgraphs, and the costs determine which valid description is preferred. Swapping cost functions lets the framework mimic, and in places improve, earlier algorithms such as Dale's full brevity method and Dale and Reiter's incremental algorithm. Because attributes and relations are both just edges, relational descriptions need no special handling, which sidesteps problems in earlier proposals. The approach matters because it links referring-expression generation to established graph theory, puts competing algorithms in one comparable framework, and opens a route to combining rule-based and statistical generation. (The excerpt provided omits the core algorithm and cost-function sections, so their details are not summarized here.)

## Key points
- Published in Computational Linguistics (2003) by Emiel Krahmer, Sebastiaan van Erk and André Verleg (Tilburg University / Eindhoven University of Technology).
- Running example: four animals (three dogs and one cat) differing in size and colour. Full brevity picks {small, dog} for d1. The incremental algorithm with preference order ⟨type, color, size⟩ picks {dog, brown, small}, where brown ends up redundant.
- Full brevity yields minimal descriptions but is NP hard. The incremental algorithm runs in polynomial time because it never backtracks.
- Earlier relational approaches had specific flaws. Dale and Haddock's could recurse endlessly, describing a dog by the doghouse it is in, that doghouse by the dog inside it, and so on without end, which they patched by allowing each property or relation only once. Krahmer and Theune's incremental extension suffers from "forced incrementality" when adding relations.
- A second scene (two dogs and two doghouses) uses the relations left of, right of, contain and in. It shows a case where only a relation can separate one dog from the other. Surface realization is delegated to standard realizers such as KPML or SURGE.

## Interesting ideas
- **Represent everything as graph edges.** Encoding one-place properties as looping edges and relations as edges between nodes means one search procedure covers both. This trick could simplify any system that mixes attributes and relations, such as knowledge-graph querying or entity descriptions in geographic data.
- **Cost functions as a pluggable preference layer.** Separating the search from the scoring lets one engine reproduce several published algorithms by changing only the costs. This makes formal comparison between methods straightforward and is a useful design for benchmarking alternatives in any generation task.
- **Bridge between rules and statistics.** Since preferences live in costs, those costs could be estimated from corpus frequencies rather than set by hand. This offers a clean way to inject data-driven preferences, for example for Ukrainian descriptions, into a symbolic pipeline.
- **Branch and bound over candidate descriptions.** Pruning partial subgraphs once they cost more than the best solution found so far keeps the search for the cheapest distinguishing description manageable. The same pattern suits other "smallest distinguishing set" problems, such as choosing features that uniquely identify a record.

*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

- [Tilburg University](https://md.research.elamur.ai/free/en/universities/tilburg-university/) — University, Tilburg, Netherlands · 40 works · 6,231 citations
- [Eindhoven University of Technology](https://md.research.elamur.ai/free/en/universities/eindhoven-university-of-technology/) — University, Eindhoven, Netherlands · 4 works · 525 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 (1): [✍️ Text generation](https://md.research.elamur.ai/free/en/topics/text-generation/) · 145 works

## Cite

Cite as: Emiel Krahmer, Sebastiaan van Erk and André Verleg. 2003. Graph-Based Generation of Referring Expressions. Computational Linguistics.

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

```bibtex
@article{krahmer2003graph,
  title = {{Graph-Based Generation of Referring Expressions}},
  author = {Emiel Krahmer, Sebastiaan {van Erk} and André Verleg},
  journal = {Computational Linguistics},
  year = {2003},
  doi = {10.1162/089120103321337430},
  url = {https://doi.org/10.1162/089120103321337430}
}
```

- [← previous Sentence Alignment for Monolingual Comparable Corpora](https://md.research.elamur.ai/free/en/papers/barzilay-2003-sentence-alignment-monolingual-comparable-corpora/)
- [next → Fast Methods for Kernel-Based Text Analysis](https://md.research.elamur.ai/free/en/papers/kudo-2003-fast-methods-kernel-based-text/)
- [↑ back to papers of 2003](https://md.research.elamur.ai/free/en/papers/2003/)

## References

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

1. Appelt, Douglas E. 1985. Planning English referring expressions. Artificial Intelligence, 26:1–33. [find](https://scholar.google.com/scholar?q=Appelt%2C+Douglas+E%2E+1985%2E+Planning+English+referring+expressions%2E+Artificial+Intelligence%2C+26%3A1%E2%80%9333%2E)
2. Bateman, John. 1997. Enabling technology for multilingual natural language generation: The KPML development environment. Natural Language Engineering, 3:15–55. [find](https://scholar.google.com/scholar?q=Bateman%2C+John%2E+1997%2E+Enabling+technology+for+multilingual+natural+language+generation%3A+The+KPML+development+environment%2E+Natural+Language+Engineering%2C+3%3A15%E2%80%9355%2E)
3. Bateman, John. 1999. Using aggregation for selecting content when generating referring expressions. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics (ACL’99), University of Maryland. [find](https://scholar.google.com/scholar?q=Bateman%2C+John%2E+1999%2E+Using+aggregation+for+selecting+content+when+generating+referring+expressions%2E+In+Proceedings+of+the+37th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%E2%80%9999%29%2C)
4. Bauckhage, Christian, Jannik Fritsch, Franz Kummert, and Gerhard Sagerer. 1999. Towards a vision system for supervising assembly processes. In Proceedings of the Symposium on Intelligent Robotic Systems (SIRS’99), pages 89–98. [find](https://scholar.google.com/scholar?q=Bauckhage%2C+Christian%2C+Jannik+Fritsch%2C+Franz+Kummert%2C+and+Gerhard+Sagerer%2E+1999%2E+Towards+a+vision+system+for+supervising+assembly+processes%2E+In+Proceedings+of+the+Symposium+on+Intelligent+Robotic+Syste)
5. Berge, Claude. 1985. Graphs. North-Holland, Amsterdam. [find](https://scholar.google.com/scholar?q=Berge%2C+Claude%2E+1985%2E+Graphs%2E+North%2DHolland%2C+Amsterdam%2E)
6. Blackburn, Patrick. 2000. Representation, reasoning, and relational structure: A hybrid logic manifesto. Logic Journal of the IGPL, 8(3):339–365. [find](https://scholar.google.com/scholar?q=Blackburn%2C+Patrick%2E+2000%2E+Representation%2C+reasoning%2C+and+relational+structure%3A+A+hybrid+logic+manifesto%2E+Logic+Journal+of+the+IGPL%2C+8%283%29%3A339%E2%80%93365%2E)
7. Chartrand, Gary and Ortrud Oellermann. 1993. Applied and Algorithmic Graph Theory. McGraw-Hill, New York. [find](https://scholar.google.com/scholar?q=Chartrand%2C+Gary+and+Ortrud+Oellermann%2E+1993%2E+Applied+and+Algorithmic+Graph+Theory%2E+McGraw%2DHill%2C+New+York%2E)
8. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Press, Cambridge. [find](https://scholar.google.com/scholar?q=Cormen%2C+Thomas+H%2E%2C+Charles+E%2E+Leiserson%2C+and+Ronald+L%2E+Rivest%2E+1990%2E+Introduction+to+Algorithms%2E+MIT+Press%2C+Cambridge%2E)
9. Dale, Robert. 1992. Generating Referring Expressions: Constructing Descriptions in a Domain of Objects and Processes. MIT Press, Cambridge. [find](https://scholar.google.com/scholar?q=Dale%2C+Robert%2E+1992%2E+Generating+Referring+Expressions%3A+Constructing+Descriptions+in+a+Domain+of+Objects+and+Processes%2E+MIT+Press%2C+Cambridge%2E)
10. Dale, Robert and Nicholas Haddock. 1991. Generating referring expressions involving relations. In Proceedings of the Fifth Conference of the European Chapter of the Association for Computational Linguistics (EACL’91), pages 161–166, Berlin. [find](https://scholar.google.com/scholar?q=Dale%2C+Robert+and+Nicholas+Haddock%2E+1991%2E+Generating+referring+expressions+involving+relations%2E+In+Proceedings+of+the+Fifth+Conference+of+the+European+Chapter+of+the+Association+for+Computational+Lingu)
11. Dale, Robert and Ehud Reiter. 1995. [Computational interpretations of the Gricean maxims in the generation of referring expressions](https://md.research.elamur.ai/free/en/papers/dale-1995-computational-interpretations-gricean-maxims-generation/). Cognitive Science, 18:233–263.
12. Elhaded, Michael and Jacques Robin. 1997. SURGE : A comprehensive plug-in syntactic realization component for text generation. Technical Report 96-03, Computer Science Department, Ben-Gurion University, Beer Sheva, Israel. [find](https://scholar.google.com/scholar?q=Elhaded%2C+Michael+and+Jacques+Robin%2E+1997%2E+SURGE+%3A+A+comprehensive+plug%2Din+syntactic+realization+component+for+text+generation%2E+Technical+Report+96%2D03%2C+Computer+Science+Department%2C+Ben%2DGurion+Universit)
13. Eppstein, David. 1999. Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications, 3(3):1–27. [find](https://scholar.google.com/scholar?q=Eppstein%2C+David%2E+1999%2E+Subgraph+isomorphism+in+planar+graphs+and+related+problems%2E+Journal+of+Graph+Algorithms+and+Applications%2C+3%283%29%3A1%E2%80%9327%2E)
14. Faugeras, Olivier. 1993. Three-Dimensional Computer Vision. MIT Press, Cambridge. [find](https://scholar.google.com/scholar?q=Faugeras%2C+Olivier%2E+1993%2E+Three%2DDimensional+Computer+Vision%2E+MIT+Press%2C+Cambridge%2E)
15. Garey, Michael R. and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York. [find](https://scholar.google.com/scholar?q=Garey%2C+Michael+R%2E+and+David+S%2E+Johnson%2E+1979%2E+Computers+and+Intractability%3A+A+Guide+to+the+Theory+of+NP%2DCompleteness%2E+W%2EH%2E+Freeman%2C+New+York%2E)
16. Gibbons, Alan M. 1985. Algorithmic Graph Theory. Cambridge University Press, Cambridge. [find](https://scholar.google.com/scholar?q=Gibbons%2C+Alan+M%2E+1985%2E+Algorithmic+Graph+Theory%2E+Cambridge+University+Press%2C+Cambridge%2E)
17. Grosz, Barbara J., Aravind K. Joshi, and Scott Weinstein. 1995. [Centering: A framework for modeling the local coherence of discourse](https://md.research.elamur.ai/free/en/papers/grosz-1995-centering-framework-modeling-local-coherence/). Computational Linguistics, 21(2):203–225.
18. Hajic̆ová, Eva. 1993. Issues of Sentence Structure and Discourse Patterns. Charles University, Prague. [find](https://scholar.google.com/scholar?q=Hajic%CC%86ova%CC%81%2C+Eva%2E+1993%2E+Issues+of+Sentence+Structure+and+Discourse+Patterns%2E+Charles+University%2C+Prague%2E)
19. Hopcroft, John E. and Robert Tarjan. 1974. Efficient planarity testing. Journal of the Association for Computing Machinery, 21:549–568. [find](https://scholar.google.com/scholar?q=Hopcroft%2C+John+E%2E+and+Robert+Tarjan%2E+1974%2E+Efficient+planarity+testing%2E+Journal+of+the+Association+for+Computing+Machinery%2C+21%3A549%E2%80%93568%2E)
20. Horacek, Helmut. 1997. An algorithm for generating referential descriptions with flexible interfaces. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics (ACL’97), pages 206–213, Madrid. [find](https://scholar.google.com/scholar?q=Horacek%2C+Helmut%2E+1997%2E+An+algorithm+for+generating+referential+descriptions+with+flexible+interfaces%2E+In+Proceedings+of+the+35th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%E2%80%9997)
21. Krahmer, Emiel and Mariët Theune. 1998. Context sensitive generation of descriptions. In Proceedings of the Fifth International Conference on Spoken Language Processing (ICSLP’98), pages 1151–1154, Sydney. [find](https://scholar.google.com/scholar?q=Krahmer%2C+Emiel+and+Marie%CC%88t+Theune%2E+1998%2E+Context+sensitive+generation+of+descriptions%2E+In+Proceedings+of+the+Fifth+International+Conference+on+Spoken+Language+Processing+%28ICSLP%E2%80%9998%29%2C+pages+1151%E2%80%931154%2C+S)
22. Krahmer, Emiel and Mariët Theune. 2002. Efficient context-sensitive generation of descriptions. In Kees van Deemter and Rodger Kibble, editors, Information Sharing: Givenness and Newness in Language Processing. CSLI Publications, Stanford, California, pages 223–264. [find](https://scholar.google.com/scholar?q=Krahmer%2C+Emiel+and+Marie%CC%88t+Theune%2E+2002%2E+Efficient+context%2Dsensitive+generation+of+descriptions%2E+In+Kees+van+Deemter+and+Rodger+Kibble%2C+editors%2C+Information+Sharing%3A+Givenness+and+Newness+in+Language+)
23. Krahmer, Emiel, Sebastiaan van Erk, and André Verleg. 2001. A meta-algorithm for the generation of referring expressions. In Proceedings of the Eighth European Workshop on Natural Language Generation (EWNLG’01), Toulouse. [find](https://scholar.google.com/scholar?q=Krahmer%2C+Emiel%2C+Sebastiaan+van+Erk%2C+and+Andre%CC%81+Verleg%2E+2001%2E+A+meta%2Dalgorithm+for+the+generation+of+referring+expressions%2E+In+Proceedings+of+the+Eighth+European+Workshop+on+Natural+Language+Generation)
24. Langkilde, Irene and Kevin Knight. 1998. The practical value of n-grams in generation. In Proceedings of the Ninth International Workshop on Natural Language Generation (INLG’98), pages 248–255, Niagara-on-the-Lake, Ontario. [find](https://scholar.google.com/scholar?q=Langkilde%2C+Irene+and+Kevin+Knight%2E+1998%2E+The+practical+value+of+n%2Dgrams+in+generation%2E+In+Proceedings+of+the+Ninth+International+Workshop+on+Natural+Language+Generation+%28INLG%E2%80%9998%29%2C+pages+248%E2%80%93255%2C+Niaga)
25. Liebers, Annegret. 2001. Planarizing graphs. Journal of Graph Algorithms and Applications, 5(1):1–74. [find](https://scholar.google.com/scholar?q=Liebers%2C+Annegret%2E+2001%2E+Planarizing+graphs%2E+Journal+of+Graph+Algorithms+and+Applications%2C+5%281%29%3A1%E2%80%9374%2E)
26. Malouf, Rob. 2000. The order of prenominal adjectives in natural language generation. In Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics (ACL’00), Hong Kong. [find](https://scholar.google.com/scholar?q=Malouf%2C+Rob%2E+2000%2E+The+order+of+prenominal+adjectives+in+natural+language+generation%2E+In+Proceedings+of+the+38th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%E2%80%9900%29%2C+Hong+Kong%2E)
27. Messmer, Bruno T. and Horst Bunke. 1995. Subgraph isomorphism in polynomial time. Technical Report IAM 95-003, University of Bern, Institute of Computer Science and Applied Mathematics, Bern, Switzerland. [find](https://scholar.google.com/scholar?q=Messmer%2C+Bruno+T%2E+and+Horst+Bunke%2E+1995%2E+Subgraph+isomorphism+in+polynomial+time%2E+Technical+Report+IAM+95%2D003%2C+University+of+Bern%2C+Institute+of+Computer+Science+and+Applied+Mathematics%2C+Bern%2C+Switzerl)
28. Messmer, Bruno T. and Horst Bunke. 1998. A new algorithm for error-tolerant subgraph isomorphism detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 20(5):493–504. [find](https://scholar.google.com/scholar?q=Messmer%2C+Bruno+T%2E+and+Horst+Bunke%2E+1998%2E+A+new+algorithm+for+error%2Dtolerant+subgraph+isomorphism+detection%2E+IEEE+Transactions+on+Pattern+Analysis+and+Machine+Intelligence%2C+20%285%29%3A493%E2%80%93504%2E)
29. Pechmann, Thomas. 1989. Incremental speech production and referential overspecification. Linguistics, 27:98–110. [find](https://scholar.google.com/scholar?q=Pechmann%2C+Thomas%2E+1989%2E+Incremental+speech+production+and+referential+overspecification%2E+Linguistics%2C+27%3A98%E2%80%93110%2E)
30. Read, Ronald C. and Derek G. Corneil. 1977. The graph isomorphism disease. Journal of Graph Theory, 1(1):339–363. [find](https://scholar.google.com/scholar?q=Read%2C+Ronald+C%2E+and+Derek+G%2E+Corneil%2E+1977%2E+The+graph+isomorphism+disease%2E+Journal+of+Graph+Theory%2C+1%281%29%3A339%E2%80%93363%2E)
31. Reiter, Ehud. 1990. [The computational complexity of avoiding conversational implicatures](https://md.research.elamur.ai/free/en/papers/reiter-1990-computational-complexity-avoiding-conversational-implicatures/). In Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics (ACL’90), pages 97–104.
32. Rosch, Eleanor. 1978. Principles of categorization. In E. Rosch and B. Lloyd, editors, Cognition and Categorization. Lawrence Erlbaum, Hillsdale, New Jersey, pages 27–48. [find](https://scholar.google.com/scholar?q=Rosch%2C+Eleanor%2E+1978%2E+Principles+of+categorization%2E+In+E%2E+Rosch+and+B%2E+Lloyd%2C+editors%2C+Cognition+and+Categorization%2E+Lawrence+Erlbaum%2C+Hillsdale%2C+New+Jersey%2C+pages+27%E2%80%9348%2E)
33. Sedgewick, Robert. 1988. Algorithms. Addison-Wesley, Reading, Massachusetts, second edition. [find](https://scholar.google.com/scholar?q=Sedgewick%2C+Robert%2E+1988%2E+Algorithms%2E+Addison%2DWesley%2C+Reading%2C+Massachusetts%2C+second+edition%2E)
34. Stone, Matthew and Bonnie Webber. 1998. Textual economy through close coupling of syntax and semantics. In Proceedings of the Ninth International Workshop on Natural Language Generation (INLG’98), pages 178–187, Niagara-on-the-Lake, Ontario. [find](https://scholar.google.com/scholar?q=Stone%2C+Matthew+and+Bonnie+Webber%2E+1998%2E+Textual+economy+through+close+coupling+of+syntax+and+semantics%2E+In+Proceedings+of+the+Ninth+International+Workshop+on+Natural+Language+Generation+%28INLG%E2%80%9998%29%2C+pag)
35. Tarjan, Robert E. 1972. Depth-first search and linear time algorithms. SIAM Journal on Computing, 1(2):146–160. [find](https://scholar.google.com/scholar?q=Tarjan%2C+Robert+E%2E+1972%2E+Depth%2Dfirst+search+and+linear+time+algorithms%2E+SIAM+Journal+on+Computing%2C+1%282%29%3A146%E2%80%93160%2E)
36. Theune, Mariët. 2000. From Data to Speech: Language Generation in Context. Ph.D. thesis, Eindhoven University of Technology, Eindhoven, The Netherlands. van Deemter, Kees. 2000. Generating vague descriptions. In Proceedings of the First International Natural Language Generation Conference (INLG’00)… [find](https://scholar.google.com/scholar?q=Theune%2C+Marie%CC%88t%2E+2000%2E+From+Data+to+Speech%3A+Language+Generation+in+Context%2E+Ph%2ED%2E+thesis%2C+Eindhoven+University+of+Technology%2C+Eindhoven%2C+The+Netherlands%2E+van+Deemter%2C+Kees%2E+2000%2E+Generating+vague+desc)
37. Wilson, Robin J. 1996. Introduction to Graph Theory. Longman, Harlow, England, fourth edition. [find](https://scholar.google.com/scholar?q=Wilson%2C+Robin+J%2E+1996%2E+Introduction+to+Graph+Theory%2E+Longman%2C+Harlow%2C+England%2C+fourth+edition%2E)

*Updated 24 October 2026*