Graph-Based Parsing

The core algorithmic insight: treat every word as a node and every possible directed arc as a scored edge. The parser's job is to find the tree that maximizes the sum of arc scores. This is solved efficiently using the Chu-Liu/Edmonds algorithm for directed graphs, guaranteeing the globally optimal tree under the arc-factored model. Unlike transition-based methods, this avoids error propagation from early greedy decisions.

Graph-based parsers typically assume first-order factorization: the score of a complete dependency tree is simply the sum of its individual arc scores. This independence assumption makes global search computationally tractable.

• Arc score: Computed via a learned function (e.g., biaffine attention) over head-dependent pairs
• Trade-off: Enables exact inference but cannot capture sibling or grandparent interactions
• Higher-order extensions: Add factors for adjacent arcs to model richer syntactic contexts

A major advantage of graph-based parsing is native support for non-projective trees. The Chu-Liu/Edmonds algorithm finds the maximum spanning tree in a general directed graph without enforcing projectivity constraints.

• Crossing arcs: Required for languages with free word order (Czech, Dutch, German)
• Projective variants: Eisner's algorithm provides O(n³) decoding when projectivity is enforced
• Practical impact: Graph-based parsers consistently outperform transition-based systems on non-projective treebanks

Modern neural graph-based parsers use deep biaffine attention to compute arc scores. For each token pair (i, j), a bilinear transformation scores how likely word j is to be the head of word i:

• Architecture: BiLSTM or Transformer encodes each word into a contextualized vector
• Head and dependent representations: Separate feedforward layers produce distinct vectors for each role
• Biaffine classifier: score(i→j) = h_i^T · U · d_j + W · [h_i; d_j] + b
• Label prediction: A second biaffine layer assigns dependency relation labels (nsubj, dobj, etc.)

The canonical neural graph-based architecture that achieved state-of-the-art results across multiple treebanks. Key design choices:

• No feature engineering: Learns everything from word embeddings and character-level CNNs
• Deep biaffine scoring: Replaces simple dot-product attention with learned bilinear transformations
• Dropout on embeddings and hidden states: Critical regularization for small treebank sizes
• Performance: Achieved 95.7% UAS and 94.1% LAS on English Penn Treebank, setting a new standard for dependency parsing accuracy

The two parsing paradigms represent a fundamental accuracy-efficiency trade-off:

• Graph-based strengths: Global optimization, natural non-projectivity, higher accuracy on standard benchmarks
• Transition-based strengths: Linear-time O(n) complexity, incremental processing suitable for streaming, easier integration with dynamic oracles
• Convergence: Modern neural transition-based parsers with beam search approach graph-based accuracy while maintaining speed advantages
• Production choice: spaCy uses transition-based for speed; Stanza offers graph-based for accuracy

The foundational combinatorial optimization algorithm that finds the maximum spanning tree in a directed graph. In graph-based parsing, it decodes the highest-scoring dependency tree from the complete graph of all possible arcs. The algorithm works by:

• Greedily selecting the best incoming arc for each node
• Identifying and contracting cycles
• Recursively solving the reduced graph
• Expanding cycles by removing the minimum-weight arc This enables efficient non-projective parsing for languages with free word order.

A first-order parsing model where the score of a complete dependency tree decomposes into the sum of its individual arc scores. This assumes independence between edges for computational tractability. Key characteristics:

• Each arc (head, dependent) receives a score independently
• The total tree score is simply the sum of selected arcs
• Enables exact decoding via maximum spanning tree algorithms
• Cannot capture sibling or grandparent interactions
• Serves as the baseline for more complex higher-order models

A neural mechanism that computes scores for all possible head-dependent pairs using a bilinear transformation. Introduced by Dozat and Manning, it applies:

• Two separate feedforward networks to produce head and dependent representations
• A learned bilinear weight matrix between them
• A deep variant adds a multi-layer perceptron before the biaffine operation This enables efficient global arc prediction over the entire sentence in a single operation, replacing exhaustive pairwise scoring.

A neural graph-based parser architecture that combines BiLSTM-encoded word representations with deep biaffine attention for both arc and label prediction. Core components:

• Stacked BiLSTMs produce contextualized token representations
• Deep biaffine arc scorer computes head-dependent probabilities
• Separate biaffine label classifier predicts relation types
• Trained with cross-entropy loss on gold-standard treebanks Achieved state-of-the-art Labeled Attachment Score (LAS) across multiple languages upon introduction.

An early and influential graph-based dependency parser that uses the maximum spanning tree algorithm to find the globally optimal parse. Key design decisions:

• Scores arcs using linear classifiers with hand-engineered features
• Supports both projective (Eisner's algorithm) and non-projective (Chu-Liu/Edmonds) decoding
• Trained using the margin-infused relaxed algorithm (MIRA) for structured prediction
• Demonstrated that global optimization outperforms greedy transition-based approaches on long-distance dependencies
• Established the graph-based paradigm as a viable alternative to transition-based methods.

An extension beyond arc-factored models that incorporates features from sibling arcs, grandparent arcs, or tri-sibling configurations. These richer contexts capture:

• Coordination structures where conjuncts share a head
• Prepositional phrase attachment ambiguities
• Clause boundary identification Trade-offs include:
• Improved accuracy on complex syntactic phenomena
• Increased computational complexity (NP-hard for exact decoding)
• Requires approximate inference like belief propagation or cube pruning Modern neural approaches implicitly capture higher-order features through contextualized embeddings.