Elamur Research⌕
☰
home / papers / 2007 / GrAF: A Graph-based Format for Linguistic Annotations

GrAF: A Graph-based Format for Linguistic Annotations

Paper · 2007 · Nancy Ide and Keith Suderman

Summary

Linguistic annotations of the same text are often produced by different groups in incompatible formats, which makes them hard to combine, reuse, or feed into existing tools. Ide and Suderman present GrAF (Graph Annotation Format), an XML serialization of the abstract model of the Linguistic Annotation Framework (LAF), which was developed under ISO TC37 SC4. In this model every annotation is a directed graph. Its nodes carry feature structures, and its edges point either to spans of the primary data or to other annotations. To test the format, the authors took several independently produced annotation layers over the Wall Street Journal corpus and automatically transformed them into GrAF: Penn TreeBank, PropBank, NomBank, Penn Discourse TreeBank, and TimeBank. They then merged these layers into one graph, which can be visualized and explored with standard graph algorithms such as traversal and frequent-subgraph mining. The conversion also exposed weaknesses in existing schemes, especially structural relations that only a human reader can infer. The work matters because it offers a single, easily mappable model for annotation exchange and multi-layer analysis.

Key points

  • A shared pivot format means each scheme needs only two mappings, one into the pivot and one out. Across the community this gives 2n converters in total, compared with n²−n pairwise converters without a pivot.
  • The LAF model has four parts:
    • a directed graph of annotations;
    • a base segmentation built from virtual nodes placed between characters of the primary data (UTF-16 by default for text), with the resulting spans acting as sink nodes;
    • serializations of the model, one of which serves as the pivot;
    • methods for manipulating the model.
  • GrAF uses <node>, <edge> and <sink> elements, each annotation document has its own namespace, and annotation content follows ISO TC37 SC4 document N188 for feature structures.
  • The WSJ layers came in a mix of embedded and stand-off formats. NomBank, PropBank and PDTB annotate PTB tree nodes rather than the raw text.
  • The resulting graph model is stated to be isomorphic to UIMA's Common Analysis System and easy to map to RDF/OWL. The authors also report compatibility with the PDTBAPI, and they ran the IBM Frequent Subgraph Miner on the merged PropBank/NomBank graph.

Interesting ideas

  • I1. Relations as nodes. GrAF turns relations that are usually drawn as labeled edges, such as dependency arcs, into nodes. Objects and relations can then be queried in the same way, and one annotation can easily attach to several targets. This is a useful trick for any multi-layer store, for example one combining UD trees with NER or coreference.
  • I2. Edge labels for link roles. Edge labels are reserved for the role of a link (ordered split argument, coreferent targets, or a set of alternatives), while linguistic content stays on the nodes. Separating these two kinds of information keeps the schema clean and avoids ambiguous multi-target annotations.
  • I3. Finding overlaps by graph coloring. When layers are merged, each layer can mark the nodes it touches. Nodes marked by two layers reveal where the phenomena interact. In the paper, nodes covered by both PropBank and NomBank exposed verb/nominalization pairs that could enrich semantic lexicons.
  • I4. Design schemes as graphs first. The authors argue that a scheme designer should sketch the annotation as nodes and links before choosing a format. The PB/NB line format left unclear which fields applied to which parts, and that ambiguity blocks fully automatic conversion. This is a cheap sanity check for any new annotation scheme or dataset format.
  • I5. Stand-off layers over a shared segmentation. Keeping each layer in a separate stand-off file that points to one shared segmentation lets independent teams add layers without touching the text or each other's work. This suits collaborative corpus projects.

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, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksLiterature and Literary Theory · 519 works

Cite

Cite as Nancy Ide and Keith Suderman. 2007. GrAF: A Graph-based Format for Linguistic Annotations. Proceedings of the Linguistic Annotation Workshop.

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

@inproceedings{ide2007graf,
  title = {{GrAF: A Graph-based Format for Linguistic Annotations}},
  author = {Nancy Ide and Keith Suderman},
  booktitle = {Proceedings of the Linguistic Annotation Workshop},
  year = {2007},
  url = {https://aclanthology.org/W07-1501/}
}

References

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

  1. A. Cardon and Maxime Crochemore, 1982. Partitioning a graph in O(\|A\| log2 \|V\| ).Theoretical Computer Science, 19(1):85–98. find
  2. Akihiro Inokuchi, Takashi Washio, and Hiroshi Motoda, 2005. A General Framework for Mining Frequent Subgraphs from Labeled Graphs. Fundamenta Informaticae, 66:1-2, 53-82. find
  3. Andrew A. Krizhanovsky, 2005. Synonym search in Wikipedia: Synarcher. http://www.citebase.org/abstract?id=oai:arXiv.org:cs/0606097 ↗
  4. Dat P.T Nguyen, Yutaka Matsuo, and Mitsuru Ishizuka, 2007. Exploiting Syntactic and Semantic Information for Relation Extraction from Wikipedia . IJCAI Workshop on Text-Mining & Link-Analysis (TextLink 2007). find
  5. Dominic Widdows and Beate Dorow, 2002. A graph model for unsupervised lexical acquisition. Proceedings of the 19th International Conference on Computational Linguistics, 1093-1099.
  6. Evgeniy Gabrilovich and Shaul Markovitch, 2007. Computing Semantic Relatedness Using Wikipedia-based Explicit Semantic Analysis. Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India. find
  7. Hang Cui, Renxu Sun, Keya Li, Min-Yen Kan and Tat-Seng Chua, 2005. Question answering passage retrieval using dependency relations. SIGIR '05: Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 400-407. find
  8. Jeffrey Dean, Monika R. Henzinger, 1999. Finding related pages in the World Wide Web. Computer Networks, 31(11-16):1467–1479. find
  9. John E. McEneaney, 2001. Graphic and numerical methods to assess navigation in hypertext. International Journal of Human-Computer Studies, 55, 761-786. find
  10. Jon M. Kleinberg, 1999. Authoritative sources in a hyper-linked environment. Journal of the ACM 46(5):604-632. find
  11. Michel Habib, Christophe Paul, Laurent Viennot, 1999. Partition refinement techniques: An interesting algorithmic tool kit. International Journal of Foundations of Computer Science, 10(2):147–170. find
  12. Mohammed J. Zaki, 2002. Efficiently mining trees in a forest. Proceedings of SIGKDD’02. find
  13. Nancy Ide and Laurent Romary, 2004. A Registry of Standard Data Categories for Linguistic Annotation. Proceedings of the Fourth Language Resources and Evaluation Conference (LREC), Lisbon, 135-39. find
  14. Nancy Ide and Laurent Romary, 2004. International Standard for a Linguistic Annotation Framework. Journal of Natural Language Engineering, 10:3-4, 211-225.
  15. Nancy Ide and Laurent Romary, 2006. Representing Linguistic Corpora and Their Annotations. Proceedings of the Fifth Language Resources and Evaluation Conference (LREC), Genoa, Italy. find
  16. Razvan C. Bunescu and Raymond J. Mooney, 2007. Extracting relations from text: From word sequences to dependency paths. In Anne Kao and Steve Poteet (eds.), Text Mining and Natural Language Processing, Springer, 29-44. find
  17. Sergey Brin, 1998. Extracting patterns and relations from the world wide web. Proceedings of the 1998 International Workshop on the Web and Databases, 172-183. find
  18. Sisay Fissaha Adafre and Maar ten de Rijke , 2005. Discovering missing links in Wikipedia. Workshop on Link Discovery: Issues, Approaches and Applications. find
  19. Stephen Bird and Mark Liberman, 2001. A formal framework for linguistic annotation. Speech Communication, 33:1-2, 23-60. find
  20. Vivi Nastase and Stan Szpakowicz, 2006. Matching syntactic-semantic graphs for semantic relation assignment. Proceedings of TextGraphs: the Second Workshop on Graph Based Methods for Natural Language Processing, 81-88. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/ide-2007-graf-graph-based-format-linguistic/