Graph-Based and Neural Dependency Parsing

This builds on dependency parsing, which fixed the dependency-tree formalism and built the transition-based parser — a greedy, linear-time stack-and-buffer machine. That family is fast but limited; the graph-based family scores whole trees instead, at a higher cost, which is where we pick up.

Graph-based parsing

Greedy transition parsing has two weaknesses: it commits locally, so a mistake is irreversible, and it cannot produce non-projective trees. Graph-based parsing fixes both by scoring whole trees rather than local decisions.¹ It is more accurate than transition-based parsing on long sentences, where a head can sit far from its dependent, and it produces non-projective trees for free.

The search is over ${\mathcal{G}}_S$, the space of all trees for a sentence $S$:

To make that argmax tractable we assume the score is edge-factored — the tree's score is the sum of independent edge scores:

Under this assumption the parser has two jobs: (1) assign a score to every possible edge, and (2) find the best tree given those scores.

Maximum spanning tree

Build a fully-connected weighted directed graph: one vertex per word plus $\text{ROOT}$, and a scored edge for every possible head-dependent pair (with $\text{ROOT}$ having outgoing edges only). A spanning tree of this graph that starts from $\text{ROOT}$ is exactly a valid parse, and the highest-scoring one — the maximum spanning tree — is the optimal parse.²

The Chu-Liu/Edmonds algorithm finds it. The idea rests on two facts. First, every vertex of a spanning tree has exactly one incoming edge, so a natural first move is greedy: for each vertex, keep only its single highest-scoring incoming edge. Second, only the relative weights of edges entering a vertex matter — subtracting a constant from every edge into a vertex leaves the maximum spanning tree unchanged. If greedy selection happens to yield a tree, it is optimal. When it instead produces a cycle, the algorithm re-scores (subtract each vertex's best incoming score from all its incoming edges, zeroing the selected ones), contracts the cycle into a single node, and recurses on the smaller graph; expanding the contracted node afterward reveals which single cycle edge to delete.²

On the fully connected graph the number of edges is $m=n^2$, and this version of the algorithm runs in $O(mn)=O(n^3)$ time; faster implementations reach $O(m+n\log n)$. Nothing in the procedure references word order, so the maximum spanning tree may cross itself — that is, graph-based parsing produces non-projective trees whenever the scores favor them, which is precisely what transition-based parsing cannot do.

A worked Chu-Liu/Edmonds trace

The one-line description of the algorithm hides the interesting case — the cycle — so work it through on real numbers. Take three words $a$, $b$, $c$ plus $\text{ROOT}$, with these edge scores (only the relevant edges shown):

Round 1 — greedy selection. For each non-root vertex keep only its single highest-scoring incoming edge. Vertex $a$'s best incoming edge is $\text{ROOT}\to a$ (9). Vertex $b$'s best is $c\to b$ (30, beating $\text{ROOT}\to b$ at 10 and $a\to b$ at 3). Vertex $c$'s best is $b\to c$ (31, beating $a\to c$ at 20). The selected set is $\{\text{ROOT}\to a,c\to b,b\to c\}$ — and $b\to c\to b$ is a cycle. Not a tree, so recurse.

Re-score. Subtract each vertex's best incoming score from all edges into that vertex, which zeroes the selected edge and makes every other incoming edge negative by its shortfall. Into $b$: $c\to b$ becomes $30-30=0$, $\text{ROOT}\to b$ becomes $10-30=-20$, $a\to b$ becomes $3-30=-27$. Into $c$: $b\to c$ becomes $31-31=0$, $a\to c$ becomes $20-31=-11$. Into $a$: only $\text{ROOT}\to a$, now $0$.

Contract. Collapse the cycle $\{b,c\}$ into one node $bc$. An edge entering the cycle from outside now enters $bc$ with its re-scored weight: $\text{ROOT}\to b$ gives $\text{ROOT}\to bc$ a score of $-20$; $a\to c$ gives $a\to bc$ a score of $-11$. Edges leaving the cycle keep their original scores.

Recurse and expand. On the contracted graph, $a$'s best incoming edge is $\text{ROOT}\to a$ (0) and $bc$'s best is $a\to bc$ ($-11$, since $-11>-20$). Those two form a spanning tree of the small graph, so the recursion returns $\{\text{ROOT}\to a,a\to bc\}$. Now expand $bc$ back into $b$ and $c$. The edge into the cycle was $a\to bc$, which came from $a\to c$, so $c$'s head is $a$; that breaks the cycle exactly at $c$, meaning we delete the cycle edge $b\to c$ and keep $c\to b$. The final tree is

with total score $9+20+30=59$. The greedy edge ($b\to c$ at 31) was dropped because keeping it would leave a cycle; the contraction found the best tree, not the best set of local edges.

Scoring the edges

The remaining job is scoring an edge. A feature-based scorer writes each edge score as a weighted sum of features — word forms, lemmas, and parts of speech of the head and dependent, features of the words between and around them, the candidate relation, its direction, and the head-to-dependent distance:

The weights are trained not to predict a class but to score correct trees above incorrect ones — inference-based learning with the perceptron rule: parse a training sentence, and if the predicted tree is wrong, lower the weights of the features present in the wrong parse but absent from the gold parse.¹

A biaffine neural scorer is the modern state of the art.³ Encode the sentence once into contextual embeddings $r_1,\dots ,r_n$. For each token, two feedforward networks produce a head representation and a dependent representation:

The score of the directed edge $i\to j$ (head $i$, dependent $j$) is a biaffine function, which mixes a bilinear term (multiplicative interaction) with a linear term and a bias:

with learned $U$, $W$, $b$. A softmax over all candidate heads $i$ of a fixed dependent $j$ turns these scores into $p(i\to j)$, trained with cross-entropy; the resulting scores feed the maximum-spanning-tree extractor.

The full labeled biaffine parser trains two classifiers: an edge-scorer, which picks the tree structure via maximum spanning tree, and a separate label-scorer of the same form, which assigns the best relation to each edge in that tree.

Evaluation

An exact-match metric — how many sentences are parsed perfectly — is too pessimistic to guide development, since one wrong arc condemns a whole sentence. Dependency parsers are scored at the level of individual words with attachment accuracy: the fraction of words assigned the correct head.⁴

Compare a reference and a system parse of Book me the flight through Houston, which has six scored words.

The system attaches five of the six words to the correct head — every word except me, which it hangs off flight instead of Book. That is a UAS of 5/6. Of those five, one more is labeled wrong (in Jurafsky & Martin's version the book $\to$flight arc is present but mislabeled), so four words have both the right head and the right label: an LAS of 4/6.⁴ A third figure, label accuracy (LS), counts correct labels regardless of attachment. Per-relation precision and recall (how many nsubj arcs the system proposed were right, how many gold nsubj arcs it found) diagnose which relations a parser handles poorly, and a confusion matrix shows which relations it swaps.

Neural dependency parsers

Jurafsky & Martin describe the neural oracle and the biaffine scorer in outline; the papers that introduced them are worth reading in their own right, because each fixed a concrete failure of the linear-model parsers that preceded it.

Chen and Manning (2014) built the first neural transition-based parser and reported the result that started the shift.⁵ Feature-based oracles spend most of their time not on classification but on feature extraction: instantiating and looking up millions of sparse, hand-conjoined indicator features (the $s_1.t\circ s_2.t$ templates), which the authors measured at over 95% of parse time. Their model replaces those templates with dense embeddings of a fixed set of stack and buffer positions — words, part-of-speech tags, and already-assigned arc labels — concatenated and passed through a single hidden layer with a cube activation $g(x)=x^3$, chosen so the hidden units mix triples of inputs and so recover feature conjunctions automatically. On the English Penn Treebank it reached 92.0 UAS / 89.7 LAS while parsing over 1000 sentences per second, both faster and more accurate than the sparse-feature parsers, and it did so with no manually specified feature combinations.⁵ The lesson others took from it: the value of the sparse templates was the conjunctions, and a small network learns those from embeddings.

Dozat and Manning (2017) produced the biaffine graph-based parser sketched above, and it remains a strong baseline.⁶ Two design choices carry the result. First, before the biaffine scorer, each token's encoder state passes through a small feedforward network that strips it down to just the information needed for head-or-dependent decisions — the recurrence carries a lot of tagging and morphological detail the arc decision does not need. Second, the scoring is genuinely biaffine rather than a plain bilinear form: the extra linear term $W(\mathbf{x}\oplus \mathbf{y})$ lets the model capture the prior probability that a given word is a head at all, independent of the candidate dependent, which a pure ${\mathbf{x}}^{\top }U\mathbf{y}$ cannot express. On the standard English benchmark the parser reached about 95.7 UAS / 94.1 LAS, then state of the art, and the same architecture won or placed near the top across dozens of languages in the CoNLL 2017 multilingual shared task.⁶ Feed it a modern pretrained encoder in place of its biLSTM and the numbers climb further.

Two directions extend these. Kiperwasser and Goldberg (2016) showed that a biLSTM feature extractor could be shared and trained jointly for both the transition-based and graph-based parsers, closing much of the gap between the two families and making clear that the encoder, not the inference algorithm, was doing most of the work.⁷ And once large pretrained encoders arrived, the trend was to drop explicit parsing structure: some systems predict each word's head by a softmax over positions with no tree constraint at all and only project to a valid tree at decode time, while others question whether an explicit parse is needed downstream when a transformer's attention already encodes much syntactic structure.⁸ The parser families in this lesson did not disappear — the biaffine scorer plus Chu-Liu/Edmonds is still how you get a guaranteed well-formed tree — but the balance of effort moved decisively from the inference algorithm to the representation it scores.

Where this sits

Dependency parsing trades the constituency tree's phrasal structure for a flatter, lexical picture that puts predicate-argument relations on the surface — the input the next stage needs. Both parser families are supervised, both learn from treebanks (built by hand for morphologically rich languages, or converted from constituency treebanks by head rules for English), and both now run on neural encoders. Transition-based parsing wins on speed with its linear greedy pass; graph-based parsing wins on accuracy and on non-projective languages by scoring whole trees. The typed arcs they produce — nsubj, dobj, and the rest — are the scaffold on which semantic roles and information extraction read off who did what to whom.