--- title: "A Shortest Path Dependency Kernel for — Bunescu 2005" description: "The paper tackles relation extraction: deciding whether, and how, two named entities in one sentence are related." authors: ["Razvan Bunescu", "Raymond Mooney"] year: 2005 venue: "Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing" source: "https://aclanthology.org/H05-1091/" 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/bunescu-2005-shortest-path-dependency-kernel-relation/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/bunescu-2005-shortest-path-dependency-kernel-relation/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2005](https://md.research.elamur.ai/free/en/papers/2005/) / A Shortest Path Dependency Kernel for Relation Extraction # A Shortest Path Dependency Kernel for Relation Extraction **Authors:** [Razvan Bunescu](https://md.research.elamur.ai/free/en/authors/razvan-bunescu/), [Raymond Mooney](https://md.research.elamur.ai/free/en/authors/raymond-mooney/) · **Year:** 2005 · **Venue:** Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing · **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/H05-1091/) · [PDF](https://aclanthology.org/H05-1091.pdf) · [OpenAlex](https://openalex.org/W2138627627) **Citations:** 955 citations (openalex-snapshot · 2026-10-14) · [218](#cited-by) in our library, of the 140884 papers whose bibliographies we read ## Summary The paper tackles relation extraction: deciding whether, and how, two named entities in one sentence are related. The authors argue that nearly all the useful syntactic evidence lies on the shortest path linking the two entities in the undirected dependency graph, which is a much smaller structure than the minimal subtrees used by earlier tree kernels. Each path is a chain of words and arrows showing dependency direction. To reduce lexical sparsity, every position on the path is expanded into a set of word classes: the word itself, its POS tag, a coarser category, and the entity type at the endpoints. The feature space is the Cartesian product of these sets. An SVM compares examples through a kernel computed over these chains. Dependencies come from either a CCG parser or a CFG parser. On the five top-level ACE relation types, the shortest-path kernel beats the dependency tree kernel of Culotta and Sorensen (2004). The method is also fast and easy to interpret, which shows that a compact, well-chosen input representation can reduce overfitting while making the model more transparent. ## Key points - Task: extract the 5 top-level relation types from the ACE newspaper corpus, with the entities assumed to be given. Two setups were tested: S1 uses a single multi-class SVM with an extra no-relation class, and S2 first detects a relation with a binary SVM and then classifies it. - Results (F-measure): SP-CFG reaches 50.5 (S1) and 52.5 (S2), SP-CCG reaches 48.0 and 50.2, and the baseline K4 kernel reaches 38.0 and 45.8. Most of the gain comes from recall, for example 43.8 vs 35.0 in S2. - SP-CFG did better than SP-CCG. Error analysis credited this to Collins' parser capturing local dependencies more accurately, even though CCG can also recover long-distance ones. - One example path, "protesters → seized ← stations", expands into 4×1×3×1×4 = 48 features. - Efficiency: each SP kernel run took 2–3 hours for training and testing on a 2.6GHz Pentium IV. Paths longer than 10 words were given a kernel value of 0. Normalizing the kernel slightly lowered accuracy. ## Interesting ideas - **Cut the input down to the shortest dependency path.** Removing everything except the connecting path acts as strong, linguistically motivated feature selection. It could help any pairwise task over parsed text, such as event–argument linking or entity linking within a sentence. - **Back off each path position to word classes.** Letting every node appear as the word, its POS tag or a broad category produces generalized patterns, including partial ones, without hand-writing templates. This is a practical way to fight sparsity in morphologically rich languages, where exact word forms seldom repeat. - **Mark negation directly on path nodes.** Adding a "(-)" suffix to verbs or nouns modified by words like "not", "never" or "no" keeps polarity inside the path representation at almost no cost. Without it, a relation and its denial would look identical. - **Use a transparent kernel.** Every dimension corresponds to an explicit path feature, so the kernel can be restricted to pattern types considered relevant. That makes models easier to inspect and adjust than opaque tree kernels. - **Detect first, then classify, when data are skewed.** Splitting the task into binary detection followed by multi-class typing improved recall when no-relation cases dominate. This setup could transfer to other imbalanced extraction tasks. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* Fields: [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/) ## Cited by Cited by 218 papers of our library cite it (of the 140884 whose bibliographies we read); 15 of them have a page here, 203 not yet. - [Open Information Extraction from the Web](https://md.research.elamur.ai/free/en/papers/banko-2007-open-information-extraction-web/) - [Attention Guided Graph Convolutional Networks for Relation Extraction](https://md.research.elamur.ai/free/en/papers/guo-2019-attention-guided-graph-convolutional-networks/) - [Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations](https://md.research.elamur.ai/free/en/papers/krishna-2016-visual-genome-connecting-language-vision/) - [Incremental Joint Extraction of Entity Mentions and Relations](https://md.research.elamur.ai/free/en/papers/li-2014-incremental-joint-extraction-entity-mentions/) - [End-to-End Relation Extraction using LSTMs on Sequences and Tree Structures](https://md.research.elamur.ai/free/en/papers/miwa-2016-end-end-relation-extraction-lstms/) - [Reasoning with Latent Structure Refinement for Document-Level Relation Extraction](https://md.research.elamur.ai/free/en/papers/nan-2020-reasoning-latent-structure-refinement-document/) - [Named Entity Recognition for Chinese Social Media with Jointly Trained Embeddings](https://md.research.elamur.ai/free/en/papers/peng-2015-named-entity-recognition-chinese-social/) - [Cross-Sentence N-ary Relation Extraction with Graph LSTMs](https://md.research.elamur.ai/free/en/papers/peng-2017-cross-sentence-n-ary-relation/) - [Relation Classification via Multi-Level Attention CNNs](https://md.research.elamur.ai/free/en/papers/wang-2016-relation-classification-multi-level-attention/) - [Open Information Extraction Using Wikipedia](https://md.research.elamur.ai/free/en/papers/wu-2010-open-information-extraction-wikipedia/) - [Classifying Relations via Long Short Term Memory Networks along Shortest Dependency Paths](https://md.research.elamur.ai/free/en/papers/xu-2015-classifying-relations-long-short-term/) - [Relation Classification via Convolutional Deep Neural Network](https://md.research.elamur.ai/free/en/papers/zeng-2014-relation-classification-convolutional-deep-neural/) - [Graph Convolution over Pruned Dependency Trees Improves Relation Extraction](https://md.research.elamur.ai/free/en/papers/zhang-2018-graph-convolution-over-pruned-dependency/) - [A Frustratingly Easy Approach for Entity and Relation Extraction](https://md.research.elamur.ai/free/en/papers/zhong-2020-frustratingly-easy-approach-entity-relation/) - [Attention-Based Bidirectional Long Short-Term Memory Networks for Relation Classification](https://md.research.elamur.ai/free/en/papers/zhou-2016-attention-based-bidirectional-long-short/) ## Cite The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{bunescu2005shortest, title = {{A Shortest Path Dependency Kernel for Relation Extraction}}, author = {Bunescu, Razvan and Mooney, Raymond}, booktitle = {Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing}, year = {2005}, doi = {10.3115/1220575.1220666}, url = {https://doi.org/10.3115/1220575.1220666} } ``` - [← previous A Hierarchical Phrase-Based Model for Statistical Machine Translation](https://md.research.elamur.ai/free/en/papers/chiang-2005-hierarchical-phrase-based-model-statistical/) - [next → A Twin-Candidate Model of Coreference Resolution with Non-Anaphor Identification Capability](https://md.research.elamur.ai/free/en/papers/yang-2005-twin-candidate-model-coreference-resolution/) - [↑ back to papers of 2005](https://md.research.elamur.ai/free/en/papers/2005/) ## References 14 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. Richard Campbell. 2004. Using linguistic principles to recover empty categories. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04), pages 645–652, Barcelona, Spain, July. [find](https://scholar.google.com/scholar?q=Richard+Campbell%2E+2004%2E+Using+linguistic+principles+to+recover+empty+categories%2E+In+Proceedings+of+the+42nd+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%2D04%29%2C+pages+645%E2%80%93652%2C+Bar) 2. Michael J. Collins. 1997. Three generative, lexicalised models for statistical parsing. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics (ACL-97), pages 16–23. [find](https://scholar.google.com/scholar?q=Michael+J%2E+Collins%2E+1997%2E+Three+generative%2C+lexicalised+models+for+statistical+parsing%2E+In+Proceedings+of+the+35th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%2D97%29%2C+pages+16%E2%80%9323) [our card](https://md.research.elamur.ai/free/en/papers/collins-1997-three-generative-lexicalised-models-statistical/) 3. Nello Cristianini and John Shawe-Taylor. 2000. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press. [find](https://scholar.google.com/scholar?q=Nello+Cristianini+and+John+Shawe%2DTaylor%2E+2000%2E+An+Introduction+to+Support+Vector+Machines+and+Other+Kernel%2Dbased+Learning+Methods%2E+Cambridge+University+Press%2E) 4. Aron Culotta and Jeffrey Sorensen. 2004. Dependency tree kernels for relation extraction. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04), Barcelona, Spain, July. [find](https://scholar.google.com/scholar?q=Aron+Culotta+and+Jeffrey+Sorensen%2E+2004%2E+Dependency+tree+kernels+for+relation+extraction%2E+In+Proceedings+of+the+42nd+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%2D04%29%2C+Barcelona) [our card](https://md.research.elamur.ai/free/en/papers/culotta-2004-dependency-tree-kernels-relation-extraction/) 5. Ralph Grishman. 1995. Message Understanding Conference 6. [http://cs.nyu.edu/cs/faculty/grishman/muc6.html](http://cs.nyu.edu/cs/faculty/grishman/muc6.html). [↗](http://cs.nyu.edu/cs/faculty/grishman/muc6.html) 6. Julia Hockenmaier and Mark Steedman. 2002. Generative models for statistical parsing with combinatory categorial grammar. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL-2002), pages 335–342, Philadelphia, PA. [find](https://scholar.google.com/scholar?q=Julia+Hockenmaier+and+Mark+Steedman%2E+2002%2E+Generative+models+for+statistical+parsing+with+combinatory+categorial+grammar%2E+In+Proceedings+of+the+40th+Annual+Meeting+of+the+Association+for+Computational) 7. Roger Levy and Christopher Manning. 2004. Deep dependencies from context-free statistical parsers: Correcting the surface dependency approximation. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04), pages 327–334, Barcelona, Spain, July. [find](https://scholar.google.com/scholar?q=Roger+Levy+and+Christopher+Manning%2E+2004%2E+Deep+dependencies+from+context%2Dfree+statistical+parsers%3A+Correcting+the+surface+dependency+approximation%2E+In+Proceedings+of+the+42nd+Annual+Meeting+of+the+Ass) 8. NIST. 2000. ACE – Automatic Content Extraction. [http://www.nist.gov/speech/tests/ace](http://www.nist.gov/speech/tests/ace). [↗](http://www.nist.gov/speech/tests/ace) 9. Soumya Ray and Mark Craven. 2001. Representing sentence structure in hidden Markov models for information extraction. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-2001), pages 1273–1279, Seattle, WA. [find](https://scholar.google.com/scholar?q=Soumya+Ray+and+Mark+Craven%2E+2001%2E+Representing+sentence+structure+in+hidden+Markov+models+for+information+extraction%2E+In+Proceedings+of+the+Seventeenth+International+Joint+Conference+on+Artificial+Int) 10. Bradley L. Richards and Raymond J. Mooney. 1992. Learning relations by pathfinding. In Proceedings of the Tenth National Conference on Artificial Intelligence (AAAI-92), pages 50–55, San Jose, CA, July. [find](https://scholar.google.com/scholar?q=Bradley+L%2E+Richards+and+Raymond+J%2E+Mooney%2E+1992%2E+Learning+relations+by+pathfinding%2E+In+Proceedings+of+the+Tenth+National+Conference+on+Artificial+Intelligence+%28AAAI%2D92%29%2C+pages+50%E2%80%9355%2C+San+Jose%2C+CA%2C+Jul) 11. D. Roth and W. Yih. 2004. A linear programming formulation for global inference in natural language tasks. In Proceedings of the Annual Conference on Computational Natural Language Learning (CoNLL), pages 1–8, Boston, MA. [find](https://scholar.google.com/scholar?q=D%2E+Roth+and+W%2E+Yih%2E+2004%2E+A+linear+programming+formulation+for+global+inference+in+natural+language+tasks%2E+In+Proceedings+of+the+Annual+Conference+on+Computational+Natural+Language+Learning+%28CoNLL%29%2C+p) [our card](https://md.research.elamur.ai/free/en/papers/roth-2004-linear-programming-formulation-global-inference/) 12. Mark Steedman. 2000. The Syntactic Process. The MIT Press, Cambridge, MA. [find](https://scholar.google.com/scholar?q=Mark+Steedman%2E+2000%2E+The+Syntactic+Process%2E+The+MIT+Press%2C+Cambridge%2C+MA%2E) 13. Vladimir N. Vapnik. 1998. Statistical Learning Theory. John Wiley & Sons. [find](https://scholar.google.com/scholar?q=Vladimir+N%2E+Vapnik%2E+1998%2E+Statistical+Learning+Theory%2E+John+Wiley+%26+Sons%2E) 14. D. Zelenko, C. Aone, and A. Richardella. 2003. Kernel methods for relation extraction. Journal of Machine Learning Research, 3:1083–1106. [find](https://scholar.google.com/scholar?q=D%2E+Zelenko%2C+C%2E+Aone%2C+and+A%2E+Richardella%2E+2003%2E+Kernel+methods+for+relation+extraction%2E+Journal+of+Machine+Learning+Research%2C+3%3A1083%E2%80%931106%2E) [our card](https://md.research.elamur.ai/free/en/papers/zelenko-2002-kernel-methods-relation-extraction/)