Abstract
The connection between the maximum spanning tree in a directed graph and the best dependency tree of a sentence has been exploited by the NLP community. However, for many dependency parsing schemes, an important detail of this approach is that the spanning tree must have exactly one edge emanating from the root. While work has been done to efficiently solve this problem for finding the one-best dependency tree, no research has attempted to extend this solution to finding the $K$-best dependency trees. This is arguably a more important extension as a larger proportion of decoded trees will not be subject to the root constraint of dependency trees. Indeed, we show that the rate of root constraint violations increases by an average of $13$ times when decoding with $K=50$ as opposed to $K=1$. In this paper, we provide a simplification of the $K$-best spanning tree algorithm of Camerini et al. (1980). Our simplification allows us to obtain a constant time speed-up over the original algorithm. Furthermore, we present a novel extension of the algorithm for decoding the $K$-best dependency trees of a graph which are subject to a root constraint.
The Root Constraint Problem
In Natural Language Processing (NLP), non-projective dependency parsing is often modeled as finding the Maximum Spanning Tree (MST) in a directed graph. A critical linguistic requirement, however, is the root constraint: a valid dependency tree must have exactly one edge emanating from the root node.
While algorithms exist to find the single best tree ($K=1$) that respects this constraint, standard $K$-best MST algorithms often ignore it. The authors demonstrate that as $K$ increases, the number of "illegal" trees (those with multiple root edges) grows significantly. Across 63 languages, the violation rate for $K=50$ is on average 13 times higher than for $K=1$, reaching up to 37% in some cases. This "violation explosion" means that without a specialized algorithm, a large portion of a $K$-best list might be linguistically invalid.
Algorithmic Contributions
The paper provides two major technical improvements to the state of the art:
1. Simplifying the "Feared" Algorithm
The standard algorithm for $K$-best spanning trees, introduced by Camerini et al. in 1980, is notoriously difficult to implement. The authors provide a simplification that replaces complex edge-ordering proofs with intuitive ancestry reasoning. This version performs half as many "cycle-contraction" operations—the most computationally expensive step—leading to a 1.39x constant-time speedup while maintaining the optimal $O(KN^2)$ complexity for dense graphs.
2. The kbest_dep Algorithm
The authors introduce a novel extension specifically for dependency parsing. This algorithm efficiently explores subgraphs to find the $K$-best trees that satisfy the root constraint. By iteratively applying "edge exclusion" logic, it ensures that every tree in the generated list is a valid dependency structure.
Key Results and Impact
The proposed algorithms were evaluated using Universal Dependencies (UD) treebanks and the Stanza toolkit. Key findings include:
- Linguistic Validity: The
kbest_depalgorithm successfully generates $K$-best lists where 100% of the trees respect the root constraint, whereas baselines show massive violation rates. - Efficiency: The simplified MST algorithm provides a measurable speedup without increasing theoretical complexity.
- Practicality: Both algorithms maintain $O(KN^2)$ runtime, making them suitable for real-world re-ranking tasks in NLP pipelines.
Conclusion and Future Work
By demystifying a classic graph theory algorithm and extending it to handle linguistic constraints, this research provides a vital tool for structured prediction in NLP. Future work may involve extending these techniques to projective dependency parsing or utilizing the $K$-best lists for marginalizing latent variables in more complex models.
Summary updated