# Combining (second-order) graph-based and headed-span-based projective dependency parsing

arXiv: https://arxiv.org/abs/2108.05838 · HTML: https://mlsanity.com/paper/2108.05838/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 30 references that are in the map.
- First posted on arXiv 12 Aug 2021.

## Builds on (most cited first, 11 of 11)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Deep Biaffine Attention for Neural Dependency Parsing](https://mlsanity.com/paper/1611.01734/) (2016)
- [A Minimal Span-Based Neural Constituency Parser](https://mlsanity.com/paper/1705.03919/) (2017)
- [Efficient Second-Order TreeCRF for Neural Dependency Parsing](https://mlsanity.com/paper/2005.00975/) (2020)
- [Head-Driven Phrase Structure Grammar Parsing on Penn Treebank](https://mlsanity.com/paper/1907.02684/) (2019)
- [Recursive Non-Autoregressive Graph-to-Graph Transformer for Dependency Parsing with Iterative Refinement](https://mlsanity.com/paper/2003.13118/) (2020)
- [Second-Order Neural Dependency Parsing with Message Passing and End-to-End Training](https://mlsanity.com/paper/2010.05003/) (2020)
- [Headed-Span-Based Projective Dependency Parsing](https://mlsanity.com/paper/2108.04750/) (2021)
- [Dependency Parsing with Bottom-up Hierarchical Pointer Networks](https://mlsanity.com/paper/2105.09611/) (2021)
- [The (Non-)Utility of Structural Features in BiLSTM-based Dependency Parsers](https://mlsanity.com/paper/1905.12676/) (2019)

## Built on by (most cited first, 5 of 5)

- [Semantic Role Labeling as Dependency Parsing: Exploring Latent Tree Structures Inside Arguments](https://mlsanity.com/paper/2110.06865/) (2021)
- [Nested Named Entity Recognition as Latent Lexicalized Constituency Parsing](https://mlsanity.com/paper/2203.04665/) (2022)
- [Joint Entity and Relation Extraction with Span Pruning and Hypergraph Neural Networks](https://mlsanity.com/paper/2310.17238/) (2023)
- [Beyond Monolingual Assumptions: A Survey of Code-Switched NLP in the Era of Large Language Models across Modalities](https://mlsanity.com/paper/2510.07037/) (2025)
- [Revisiting Structured Sentiment Analysis as Latent Dependency Graph Parsing](https://mlsanity.com/paper/2407.04801/) (2024)

## Abstract (arXiv)

Graph-based methods, which decompose the score of a dependency tree into scores of dependency arcs, are popular in dependency parsing for decades. Recently, citetYang2022Span propose a headed-span-based method that decomposes the score of a dependency tree into scores of headed spans. They show improvement over first-order graph-based methods. However, their method does not score dependency arcs at all, and dependency arcs are implicitly induced by their cubic-time algorithm, which is possibly sub-optimal since modeling dependency arcs is intuitively useful. In this work, we aim to combine graph-based and headed-span-based methods, incorporating both arc scores and headed span scores into our model. First, we show a direct way to combine with O(n4) parsing complexity. To decrease complexity, inspired by the classical head-splitting trick, we show two O(n3) dynamic programming algorithms to combine first- and second-order graph-based and headed-span-based methods. Our experiments on PTB, CTB, and UD show that combining first-order graph-based and headed-span-based methods is effective. We also confirm the effectiveness of second-order graph-based parsing in the deep learning age, however, we observe marginal or no improvement when combining second-order graph-based and headed-span-based methods. Our code is publicly available at urlhttps://github.com/sustcsonglin/span-based-dependency-parsing.