Dependency Parsing as a Maximum Spanning Tree Problem

122 concepts103 papers1 proposal

When parsing the syntactic structure of a sentence, a model must determine how words depend on one another. For years, the dominant paradigm relied on transition-based parsers, which construct a syntax tree step-by-step using a stack and a buffer. While highly efficient, these local, greedy methods suffer from a fundamental flaw: if the parser makes a single mistake early on, that error propagates through the remaining steps, often derailing the entire parse.

Graph-based dependency parsing offers an elegant alternative. Instead of building a tree incrementally, it treats the entire sentence as a fully connected, directed graph and searches for the globally optimal tree structure all at once. By framing syntactic analysis as a classic graph theory problem—specifically, finding a Maximum Spanning Tree (MST)—this approach guarantees an exact global optimum, eliminates error propagation, and naturally accommodates languages with flexible word orders.

The Sentence as a Dense Graph

To understand why this framework works, we must first change how we visualize a sentence. Instead of a linear sequence of words, imagine a directed graph $G = (V, E)$ where every word (plus a special dummy ROOT node) is a vertex $V$.

Every possible directed edge $(i, j)$ represents a potential dependency relationship where word $i$ is the head (the modifier) and word $j$ is the dependent.

[ ROOT ] ------> [ saw ] ------> [ a ]
   |               ^              ^
   |               |              |
   +---------------+--------------+

In an arc-factored model, we assign a score to each individual edge independently. This score reflects the likelihood of that specific head-dependent relationship, typically computed using morphological features, structural distance, or deep contextualized representations like BERT, as explored by Elena Fano in Deep Contextualized Word Embeddings in Transition-Based and Graph-Based Dependency Parsing - A Tale of Two Parsers Revisited.

The total score of any given parse tree $T$ is simply the sum of its edge weights:

$$Score(T) = \sum_{(i,j) \in T} Weight(i, j)$$

Our goal is to find the tree $T$ that maximizes this total score. However, a valid dependency parse cannot just be any collection of high-scoring edges; it must adhere to strict structural constraints:

  1. It must be a valid tree spanning all nodes.
  2. Every node except the ROOT must have exactly one incoming edge (one head).
  3. There can be no cycles (e.g., word A cannot be the head of word B while word B is simultaneously the head of word A).

The Decoding Mechanism: Chu-Liu-Edmonds

If we simply allowed each word to independently select its highest-scoring incoming edge—a naive strategy known as "ArcMax"—we would frequently violate the acyclic constraint. We would end up with isolated loops where words point to each other, disconnected from the main ROOT.

To resolve this, Ryan McDonald et al. introduced a well-known graph algorithm to the NLP community in their seminal paper, Non-Projective Dependency Parsing using Spanning Tree Algorithms. The Chu-Liu-Edmonds (CLE) algorithm finds the maximum spanning arborescence (a directed tree) in quadratic $O(n^2)$ time through a clever recursive process of cycle contraction:

  1. Greedy Selection: For every node in the graph (except ROOT), select the single highest-scoring incoming edge.
  2. Cycle Detection: Check if this selection forms any cycles. If no cycles are found, the current selection is the globally optimal tree, and the algorithm terminates.
  3. Contraction: If a cycle is detected, collapse all the nodes within that cycle into a single "super-node."
  4. Weight Recalculation: Adjust the weights of all edges entering the super-node from the outside. The new weight accounts for the "cost" of breaking the cycle to let an outside edge in.
  5. Recursion: Run the algorithm again on this contracted graph. Once the optimal tree is found for the simplified graph, uncollapse the super-node to reconstruct the final, valid global tree.
Initial Selection (Cycle found)      Contract into Super-Node
   [A] <=======> [B]                      +-----------+
    ^             |                       |  [A] [B]  | <--- [C]
    |             v                       +-----------+
   [C]           [ROOT]                         |
                                                v
                                             [ROOT]

This mechanism ensures that local structural decisions are balanced against global consistency. As Milos Stanojevic et al. demonstrate in A Root of a Problem: Optimizing Single-Root Dependency Parsing, even heuristic shortcuts used to enforce single-root constraints in modern parsing libraries are mathematically anchored to this underlying global MST optimality.

Why It Works: The Non-Projectivity Advantage

The true power of the graph-based MST formulation emerges when dealing with non-projective sentences.

A dependency tree is projective if its dependency arcs can be drawn above the sentence without any of them crossing. Projective structures map cleanly to linear word order and can be parsed using traditional context-free grammar charts or shift-reduce stacks. However, many languages with flexible word orders—such as Czech, German, or Hebrew—frequently exhibit non-projective structures, where long-distance dependencies cause arcs to cross.

Projective (No crossing):
  +------>
[ I ]   [ saw ] <--- [ birds ]

Non-Projective (Crossing arcs):
  +------------------------+
  |                        v
[ A ] <--- [ B ]   [ C ]   [ D ]
            |        ^
            +--------+

Because transition-based parsers operate linearly, they require complex, custom extensions to handle crossing arcs. In contrast, the MST framework treats the sentence purely as a spatial graph. The Chu-Liu-Edmonds algorithm does not care whether edges cross in linear text layout; it only evaluates the topological relationships between vertices.

As a result, graph-based models recover non-projective dependencies naturally and globally. In Hebrew Dependency Parsing: Initial Results, Yoav Goldberg et al. showed that graph-based parsers consistently outperform transition-based alternatives in morphologically rich languages precisely because they avoid local, greedy blindspots when navigating complex coordination and flexible word orders.

Global Optimization Beyond Single Parsers

The utility of the MST framework extends beyond decoding individual models; it serves as a powerful mathematical tool for synthesizing consensus across diverse systems.

In Single Malt or Blended? A Study in Multilingual Parser Optimization, Johan Hall et al. demonstrated that an ensemble of different parsers can be combined by treating their individual predictions as weighted votes on graph edges. By running an MST algorithm over these aggregated votes, the ensemble synthesizes a single, structurally valid, high-accuracy tree that resolves conflicts and prevents illegal cycles.

Ultimately, framing dependency parsing as a maximum spanning tree problem works because it decouples scoring from structural validation. Machine learning models can focus entirely on learning the strength of pairwise word relationships, leaving the exact, polynomial-time graph algorithms to handle the global constraints required to produce a coherent syntactic tree.

Key Foundational Work

Optimality Theory: Universal Grammar, Learning and Parsing Algorithms, and Connectionist Foundations (Abstract) (1994) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 106 papers
  2. Version 1 · 2026-10-04 · 102 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_graph_based_dependency_parsing_7488c7b7,
  title = {graph-based dependency parsing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-dependency-parsing/rdr_7488c7b74a50461fbc73b13cb8e141b4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_graph_based_dependency_parsing_7488c7b7_v2,
  title = {graph-based dependency parsing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-dependency-parsing/rdr_7488c7b74a50461fbc73b13cb8e141b4/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake