---
title: "Splitting EUD Graphs into Trees — Anderson 2021"
description: "The paper describes the FASTPARSE team's system for the IWPT 2021 shared task, which requires building Enhanced Universal Dependencies (EUD) graphs."
authors: ["Mark Anderson", "Carlos Gómez-Rodríguez"]
year: 2021
venue: "Proceedings of the 17th International Conference on Parsing Technologies and the IWPT 2021 Shared Task on Parsing into Enhanced Universal Dependencies (IWPT 2021)"
source: "https://aclanthology.org/2021.iwpt-1.17/"
doi: "10.18653/v1/2021.iwpt-1.17"
arxiv: "2106.13155"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/papers/anderson-2021-splitting-eud-graphs-into-trees/"
---
[Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/anderson-2021-splitting-eud-graphs-into-trees/)

[home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [2021](https://md.research.elamur.ai/free/papers/2021/page/3/) / Splitting EUD Graphs into Trees: A Quick and Clatty Approach

# Splitting EUD Graphs into Trees: A Quick and Clatty Approach

**Authors:** [Mark Anderson](https://md.research.elamur.ai/free/authors/mark-anderson/), [Carlos Gómez-Rodríguez](https://md.research.elamur.ai/free/authors/carlos-gomez-rodriguez/) · **Year:** 2021 · **Venue:** Proceedings of the 17th International Conference on Parsing Technologies and the IWPT 2021 Shared Task on Parsing into Enhanced Universal Dependencies (IWPT 2021) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2021.iwpt-1.17/) · [PDF](https://aclanthology.org/2021.iwpt-1.17.pdf) · [DOI 10.18653/v1/2021.iwpt-1.17](https://doi.org/10.18653/v1/2021.iwpt-1.17) · [arXiv 2106.13155](https://arxiv.org/abs/2106.13155) · [OpenAlex](https://openalex.org/W3174013410)

**Citations:** 0 citations (openalex-snapshot · 2026-10-14) · [2](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
The paper describes the FASTPARSE team's system for the IWPT 2021 shared task, which requires building Enhanced Universal Dependencies (EUD) graphs. The authors were the first to apply a sequence-labelling approach to graph parsing, in which each token receives a single label. They decompose each EUD graph into four trees using linguistic criteria. The base tree is the one most similar to a regular UD tree, and the other three cover relative clauses, coordination (conj) and control (xcomp). These trees may overlap with one another. For each tree type on each treebank, a separate BiLSTM parser was trained with the bracketing encoding of Strzyz et al. (2019b). The predicted trees were then merged back into a graph with a very simple rule: take the union of all edges, and take the label from the first tree in which the edge occurs. Overall, the parser reproduces the unlabelled graph structure correctly, but it assigns edge labels considerably worse. In the final results, it is the weakest system among those that submitted results for all treebanks. The value of the work is that it shows that a linguistically motivated decomposition of a graph into trees works in principle. The main bottlenecks are edge labelling and the way the trees are assembled into a graph.

## Key points
- Allowing a node only one incoming edge covers 94.15% of EUD edges, and allowing two covers 99.53%. Thus almost the entire graph can be represented as several trees.
- As a check, the authors decomposed the gold graphs into trees and reassembled them. On dev, ELAS is roughly 91–99 for most treebanks, and 95.97 for uk-iu. A notable exception is ar-padt (81.91), which the authors attribute to a likely implementation error.
- Average results on dev: EUAS 86.66, EULAS 72.02, ELAS 69.21. The authors explain the large gap between unlabelled and labelled structure by the fact that the relative position of the lemma for case marking was added to the label.
- On test, the average scores are EULAS 68.78 and ELAS 65.81. For Ukrainian, EULAS is 65.41 and ELAS is 63.42. In the overall ranking, the system placed second to last.
- Preprocessing (tokenization, lemmatization, tags) was done by UDPipe 2.0. FastText embeddings with a vocabulary of up to 50K words were used. The authors acknowledge two errors: incorrect construction of the relative-clause tree and missing ccomp edges in the control tree.

*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: [Linguistics & languages](https://md.research.elamur.ai/free/shelves/linguistics/)

Topics: [Treebanks](https://md.research.elamur.ai/free/topics/treebanks/)

## Cited by

Cited by

2 papers of our library cite it (of the 140673 whose bibliographies we read); 1 of them have a page here, 1 not yet.

- [From Raw Text to Enhanced Universal Dependencies: The Parsing Shared Task at IWPT 2021](https://md.research.elamur.ai/free/papers/ud-2021-bouma-raw-text-enhanced-universal-dependencies/)

## Cite

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

```bibtex
@inproceedings{anderson2021splitting,
  title = {{Splitting EUD Graphs into Trees: A Quick and Clatty Approach}},
  author = {Anderson, Mark and Gómez-Rodríguez, Carlos},
  booktitle = {Proceedings of the 17th International Conference on Parsing Technologies and the IWPT 2021 Shared Task on Parsing into Enhanced Universal Dependencies (IWPT 2021)},
  year = {2021},
  doi = {10.18653/v1/2021.iwpt-1.17},
  eprint = {2106.13155},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/2021.iwpt-1.17}
}
```

- [← previous SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking](https://md.research.elamur.ai/free/papers/formal-2021-splade-sparse-lexical-expansion/)
- [next → Stages rather than ages in the acquisition of movement structures: Data from sentence repetition and 27696 spontaneous clauses](https://md.research.elamur.ai/free/papers/lingbulk-2021-friedmann-stages-rather-than-ages-acquisition/)
- [↑ back to papers of 2021](https://md.research.elamur.ai/free/papers/2021/page/3/)

## References

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

1. Mark Anderson and Carlos Gómez-Rodrı́guez. 2021. A modest Pareto optimisation analysis of dependency parsers in 2021. In Proceedings of the 17th International Conference on Parsing Technologies and the IWPT 2021 Shared Task on Parsing into Enhanced Universal Dependencies, Online. Association for Co… [find](https://scholar.google.com/scholar?q=Mark+Anderson+and+Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez%2E+2021%2E+A+modest+Pareto+optimisation+analysis+of+dependency+parsers+in+2021%2E+In+Proceedings+of+the+17th+International+Conference+on+Parsing+Technologies+and+t)
2. Gosse Bouma, Djamé Seddah, and Daniel Zeman. 2021. From raw text to Enhanced Universal Depen-Michalina Strzyz, David Vilares, and Carlos Gómez-Rodrı́guez. 2019a. Sequence labeling parsing by learning across representations. In Proceedings of the 57th Annual Meeting of the Association for Computati… [find](https://scholar.google.com/scholar?q=Gosse+Bouma%2C+Djame%CC%81+Seddah%2C+and+Daniel+Zeman%2E+2021%2E+From+raw+text+to+Enhanced+Universal+Depen%2DMichalina+Strzyz%2C+David+Vilares%2C+and+Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez%2E+2019a%2E+Sequence+labeling+parsing+by+learnin)
3. Yoeng-Jin Chu and Tseng-Hong Liu. 1965. On the shortest arborescence of a directed graph. Scientia Sinica, 14:1396–1400. [find](https://scholar.google.com/scholar?q=Yoeng%2DJin+Chu+and+Tseng%2DHong+Liu%2E+1965%2E+On+the+shortest+arborescence+of+a+directed+graph%2E+Scientia+Sinica%2C+14%3A1396%E2%80%931400%2E)
4. Michalina Strzyz, David Vilares, and Carlos Gómez-Rodrı́guez. 2019b. Viable dependency parsing as sequence labeling. In Proceedings of NAACL-HLT, pages 717–723. [find](https://scholar.google.com/scholar?q=Michalina+Strzyz%2C+David+Vilares%2C+and+Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez%2E+2019b%2E+Viable+dependency+parsing+as+sequence+labeling%2E+In+Proceedings+of+NAACL%2DHLT%2C+pages+717%E2%80%93723%2E)
5. Mathieu Dehouck, Mark Anderson, and Carlos Gómez-Rodrı́guez. 2020. Efficient EUD parsing. In Proceedings of the 16th International Conference on Parsing Technologies and the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies, pages 192–205, Online. Association for Computational L… [find](https://scholar.google.com/scholar?q=Mathieu+Dehouck%2C+Mark+Anderson%2C+and+Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez%2E+2020%2E+Efficient+EUD+parsing%2E+In+Proceedings+of+the+16th+International+Conference+on+Parsing+Technologies+and+the+IWPT+2020+Shared+Task+on+)
6. Michalina Strzyz, David Vilares, and Carlos Gómez-Rodrı́guez. 2020. Bracketing encodings for 2-planar dependency parsing. In Proceedings of the 28th International Conference on Computational Linguistics, pages 2472–2484. [find](https://scholar.google.com/scholar?q=Michalina+Strzyz%2C+David+Vilares%2C+and+Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez%2E+2020%2E+Bracketing+encodings+for+2%2Dplanar+dependency+parsing%2E+In+Proceedings+of+the+28th+International+Conference+on+Computational+Linguist)
7. Weiwei Sun, Junjie Cao, and Xiaojun Wan. 2017. Semantic dependency parsing via book embedding. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 828–838, Vancouver, Canada. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Weiwei+Sun%2C+Junjie+Cao%2C+and+Xiaojun+Wan%2E+2017%2E+Semantic+dependency+parsing+via+book+embedding%2E+In+Proceedings+of+the+55th+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28Volume+1%3A+Lon)
8. Jack Edmonds. 1967. Optimum branchings. Journal of Research of the national Bureau of Standards B, 71(4):233–240. [find](https://scholar.google.com/scholar?q=Jack+Edmonds%2E+1967%2E+Optimum+branchings%2E+Journal+of+Research+of+the+national+Bureau+of+Standards+B%2C+71%284%29%3A233%E2%80%93240%2E)
9. Daniel Fernández-González and Carlos Gómez-Rodrı́guez. 2018. A dynamic oracle for linear-time 2-planar dependency parsing. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pa… [find](https://scholar.google.com/scholar?q=Daniel+Ferna%CC%81ndez%2DGonza%CC%81lez+and+Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez%2E+2018%2E+A+dynamic+oracle+for+linear%2Dtime+2%2Dplanar+dependency+parsing%2E+In+Proceedings+of+the+2018+Conference+of+the+North+American+Chapter+of+the)
10. Junru Zhou, Zuchao Li, and Hai Zhao. 2020. Parsing all: Syntax and semantics, dependencies and spans. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 4438–4449, Online. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Junru+Zhou%2C+Zuchao+Li%2C+and+Hai+Zhao%2E+2020%2E+Parsing+all%3A+Syntax+and+semantics%2C+dependencies+and+spans%2E+In+Findings+of+the+Association+for+Computational+Linguistics%3A+EMNLP+2020%2C+pages+4438%E2%80%934449%2C+Online%2E)
11. Carlos Gómez-Rodrı́guez and Joakim Nivre. 2010. A transition-based parser for 2-planar dependency structures. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL 2010), pages 1492–1501. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez+and+Joakim+Nivre%2E+2010%2E+A+transition%2Dbased+parser+for+2%2Dplanar+dependency+structures%2E+In+Proceedings+of+the+48th+Annual+Meeting+of+the+Association+for+Computational+Linguistic)
12. Carlos Gómez-Rodrı́guez and Joakim Nivre. 2013. Divisible transition systems and multiplanar dependency parsing. Comput. Linguist., 39(4):799–845. [find](https://scholar.google.com/scholar?q=Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez+and+Joakim+Nivre%2E+2013%2E+Divisible+transition+systems+and+multiplanar+dependency+parsing%2E+Comput%2E+Linguist%2E%2C+39%284%29%3A799%E2%80%93845%2E)
13. Carlos Gómez-Rodrı́guez and David Vilares. 2018. Constituent parsing as sequence labeling. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 1314– 1324. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Carlos+Go%CC%81mez%2DRodr%C4%B1%CC%81guez+and+David+Vilares%2E+2018%2E+Constituent+parsing+as+sequence+labeling%2E+In+Proceedings+of+the+2018+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+pages+1314%E2%80%93+1324%2E)
14. James Henderson, Paola Merlo, Ivan Titov, and Gabriele Musillo. 2013. Multilingual Joint Parsing of Syntactic and Semantic Dependencies with a Latent Variable Model. Computational Linguistics, 39(4):949–998. [find](https://scholar.google.com/scholar?q=James+Henderson%2C+Paola+Merlo%2C+Ivan+Titov%2C+and+Gabriele+Musillo%2E+2013%2E+Multilingual+Joint+Parsing+of+Syntactic+and+Semantic+Dependencies+with+a+Latent+Variable+Model%2E+Computational+Linguistics%2C+39%284%29%3A9)
15. Zuchao Li, Jiaxun Cai, Shexia He, and Hai Zhao. 2018. Seq2seq dependency parsing. In Proceedings of the 27th International Conference on Computational Linguistics, pages 3203–3214, Santa Fe, New Mexico, USA. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Zuchao+Li%2C+Jiaxun+Cai%2C+Shexia+He%2C+and+Hai+Zhao%2E+2018%2E+Seq2seq+dependency+parsing%2E+In+Proceedings+of+the+27th+International+Conference+on+Computational+Linguistics%2C+pages+3203%E2%80%933214%2C+Santa+Fe%2C+New+Mexic)
16. Drahomı́ra Johanka Spoustová and Miroslav Spousta. 2010. Dependency parsing as a sequence labeling task. The Prague Bulletin of Mathematical Linguistics, 94(2010):7–14. [find](https://scholar.google.com/scholar?q=Drahom%C4%B1%CC%81ra+Johanka+Spoustova%CC%81+and+Miroslav+Spousta%2E+2010%2E+Dependency+parsing+as+a+sequence+labeling+task%2E+The+Prague+Bulletin+of+Mathematical+Linguistics%2C+94%282010%29%3A7%E2%80%9314%2E)