--- title: "Discovering Relations among Named Entities — Hasegawa 2004" description: "The paper tackles relation discovery: finding meaningful links between named entities, such as leadership roles or company acquisitions, without any…" authors: ["Takaaki Hasegawa", "Satoshi Sekine", "Ralph Grishman"] year: 2004 venue: "Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04)" source: "https://aclanthology.org/P04-1053/" doi: "10.3115/1218955.1219008" 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/hasegawa-2004-discovering-relations-among-named-entities/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/hasegawa-2004-discovering-relations-among-named-entities/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2004](https://md.research.elamur.ai/free/en/papers/2004/) / Discovering Relations among Named Entities from Large Corpora # Discovering Relations among Named Entities from Large Corpora **Authors:** Takaaki Hasegawa, [Satoshi Sekine](https://md.research.elamur.ai/free/en/authors/satoshi-sekine/), [Ralph Grishman](https://md.research.elamur.ai/free/en/authors/ralph-grishman/) · **Year:** 2004 · **Venue:** Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04) · **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/P04-1053/) · [PDF](https://aclanthology.org/P04-1053.pdf) · [DOI 10.3115/1218955.1219008](https://doi.org/10.3115/1218955.1219008) · [OpenAlex](https://openalex.org/W2123143128) **Citations:** 397 citations (openalex-snapshot · 2026-10-14) · [89](#cited-by) in our library, of the 140884 papers whose bibliographies we read ## Summary The paper tackles relation discovery: finding meaningful links between named entities, such as leadership roles or company acquisitions, without any annotated training data and without seed examples. Earlier work in the MUC/ACE tradition relied on supervised learning over richly tagged corpora. Bootstrapping methods such as Brin's or Agichtein's needed hand-picked seeds and a fixed relation in advance. The authors' pipeline needs only a named entity tagger, here an extended tagger by Sekine. It runs the tagger over a year of newspaper text and keeps entity pairs that co-occur often within a sentence. Each pair is represented by the stemmed words that appear between the two entities, weighted with tf*idf. Pairs of the same type combination, such as PERSON–GPE or COMPANY–COMPANY, are grouped by complete-linkage hierarchical clustering on cosine similarity. Each cluster is then named by the words its members most often share. Experiments in the PER-GPE and COM-COM domains found relations with high recall and precision, and the large clusters received fitting labels. The work matters because it lets the set of relations emerge from the data instead of being fixed beforehand. ## Key points - **Five-step pipeline:** - tag named entities; - collect co-occurring pairs and their context; - compute context similarity; - cluster the pairs hierarchically; - label each cluster with its frequent shared words. - **Co-occurrence and filtering:** - Two entities count as co-occurring only within one sentence, with at most 5 intervening words in the experiments. - Pairs seen fewer than 30 times were dropped. - Context vectors with very small norms were also removed. - **Direction and preprocessing:** - The order in which the two entities appear is encoded in the term frequencies, so the system can tell the direction of a relation. - Words are stemmed, but past participles are kept separate so passive and active voice stay distinct. - Stop words and source-specific boilerplate are removed. - **Clustering choice:** - Complete linkage beat single and average linkage on F-measure. - Its best cosine threshold, just above 0, was nearly the same in both domains. - With that threshold, every pair in a cluster shares at least one word with every other pair. - **Results by domain:** - Performance was somewhat better in PER-GPE than in COM-COM. - COM-COM was harder because company relations overlap (for example, M&A versus parent company) and are directional. - Wrong-direction alignment caused errors in 2 of 15 clusters. ## Interesting ideas - **A "domain" is a pair of entity types.** Comparing only pairs with the same type combination is a cheap way to cut noise and shrink the search space. It could carry over to relation mining on Ukrainian news or trade texts, given a decent NER model. - **Signed similarity for direction.** Order-sensitive term frequency makes cosine similarity negative when two pairs share context words but appear in reverse order. This is a simple trick for recognising asymmetric relations, such as parent and subsidiary, without any syntax. - **Conservative clustering with a threshold just above zero.** Complete linkage with that threshold guarantees every pair in a cluster shares at least one context word with every other pair. This is a transparent, nearly parameter-free stopping rule for cases where the number of clusters is unknown. - **Labels from pairwise shared words.** Counting the words shared across all pair combinations in a cluster, normalised by the number of combinations, produces human-readable names for discovered groups. The same approach could name topics or entity groupings in other unsupervised tasks. - **Unsupervised output as bootstrapping seeds.** The authors propose using the tightest clusters as seeds for bootstrapping, then attaching rarer pairs under looser overlap rules. This addresses the usual question of how to choose seeds for weakly supervised extraction. *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/) Topics: [Named entity recognition](https://md.research.elamur.ai/free/en/topics/named-entity-recognition/) · [Part-of-speech tagging](https://md.research.elamur.ai/free/en/topics/part-of-speech-tagging/) ## Cited by Cited by 89 papers of our library cite it (of the 140884 whose bibliographies we read); 2 of them have a page here, 87 not yet. - [Relation Classification via Multi-Level Attention CNNs](https://md.research.elamur.ai/free/en/papers/wang-2016-relation-classification-multi-level-attention/) - [Relation Classification via Convolutional Deep Neural Network](https://md.research.elamur.ai/free/en/papers/zeng-2014-relation-classification-convolutional-deep-neural/) ## Cite The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{hasegawa2004discovering, title = {{Discovering Relations among Named Entities from Large Corpora}}, author = {Hasegawa, Takaaki and Sekine, Satoshi and Grishman, Ralph}, booktitle = {Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04)}, year = {2004}, doi = {10.3115/1218955.1219008}, url = {https://doi.org/10.3115/1218955.1219008} } ``` - [← previous Differentiating Types of Verb Particle Constructions](https://md.research.elamur.ai/free/en/papers/aclbulk-2004-patrick-differentiating-types-verb-particle-constructions/) - [next → Exploiting Coreference Annotations for Text-to-Hypertext Conversion](https://md.research.elamur.ai/free/en/papers/holler-2004-exploiting-coreference-annotations-text-hypertext/) - [↑ back to papers of 2004](https://md.research.elamur.ai/free/en/papers/2004/) ## References 9 references, 2 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. Eugene Agichtein and Luis Gravano. 2000. Snowball: Extracting relations from large plain-text collections. In Proc. of the 5th ACM International Conference on Digital Libraries (ACM DL’00), pages 85–94. [find](https://scholar.google.com/scholar?q=Eugene+Agichtein+and+Luis+Gravano%2E+2000%2E+Snowball%3A+Extracting+relations+from+large+plain%2Dtext+collections%2E+In+Proc%2E+of+the+5th+ACM+International+Conference+on+Digital+Libraries+%28ACM+DL%E2%80%9900%29%2C+pages+85%E2%80%939) 2. Sergey Brin. 1998. Extracting patterns and relations from world wide web. In Proc. of WebDB Workshop at 6th International Conference on Extending Database Technology (WebDB’98), pages 172–183. [find](https://scholar.google.com/scholar?q=Sergey+Brin%2E+1998%2E+Extracting+patterns+and+relations+from+world+wide+web%2E+In+Proc%2E+of+WebDB+Workshop+at+6th+International+Conference+on+Extending+Database+Technology+%28WebDB%E2%80%9998%29%2C+pages+172%E2%80%93183%2E) 3. Defense Advanced Research Projects Agency. 1995. Proceedings of the Sixth Message Understanding Conference (MUC-6). Morgan Kaufmann Publishers, Inc. [find](https://scholar.google.com/scholar?q=Defense+Advanced+Research+Projects+Agency%2E+1995%2E+Proceedings+of+the+Sixth+Message+Understanding+Conference+%28MUC%2D6%29%2E+Morgan+Kaufmann+Publishers%2C+Inc%2E) 4. Dekang Lin and Patrick Pantel. 2001. Dirt - discovery of inference rules from text. In Proc. of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2001), pages 323–328. [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+Proc%2E+of+the+7th+ACM+SIGKDD+International+Conference+on+Knowledge+Discovery+and+Data+Mining+%28KDD%2D2001%29%2C+pages+323) 5. National Institute of Standards and Technology. 2000. Automatic Content Extraction. [http://www.nist.gov/speech/tests/ace/index.htm](http://www.nist.gov/speech/tests/ace/index.htm). [↗](http://www.nist.gov/speech/tests/ace/index.htm) 6. Deepak Ravichandran and Eduard Hovy. 2002. Learning surface text patterns for a question answering system. In Proc. of the 40th Annual Meeting of the Association for Computational Linguistics (ACL-2002), pages 41–47. [find](https://scholar.google.com/scholar?q=Deepak+Ravichandran+and+Eduard+Hovy%2E+2002%2E+Learning+surface+text+patterns+for+a+question+answering+system%2E+In+Proc%2E+of+the+40th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28ACL%2D200) [our card](https://md.research.elamur.ai/free/en/papers/ravichandran-2002-learning-surface-text-patterns-question/) 7. Satoshi Sekine, Kiyoshi Sudo, and Chikashi Nobata. 2002. Extended named entity hierarchy. In Proc. of the Third International Conference on Language Resources and Evaluation (LREC-2002), pages 1818–1824. [find](https://scholar.google.com/scholar?q=Satoshi+Sekine%2C+Kiyoshi+Sudo%2C+and+Chikashi+Nobata%2E+2002%2E+Extended+named+entity+hierarchy%2E+In+Proc%2E+of+the+Third+International+Conference+on+Language+Resources+and+Evaluation+%28LREC%2D2002%29%2C+pages+1818%E2%80%9318) 8. Satoshi Sekine. 2001. OAK System (English Sentence Analyzer). [http://nlp.cs.nyu.edu/oak/](http://nlp.cs.nyu.edu/oak/). [↗](http://nlp.cs.nyu.edu/oak/) 9. Dmitry Zelenko, Chinatsu Aone, and Anthony Richardella. 2002. Kernel methods for relation extraction. In Proc. of the Conference on Empirical Methods in Natural Language Processing (EMNLP-2002), pages 71–78. [find](https://scholar.google.com/scholar?q=Dmitry+Zelenko%2C+Chinatsu+Aone%2C+and+Anthony+Richardella%2E+2002%2E+Kernel+methods+for+relation+extraction%2E+In+Proc%2E+of+the+Conference+on+Empirical+Methods+in+Natural+Language+Processing+%28EMNLP%2D2002%29%2C+pages) [our card](https://md.research.elamur.ai/free/en/papers/zelenko-2002-kernel-methods-relation-extraction/)