TL;DR
This paper adapts an optimal hierarchical bracketing encoding to dependency graph parsing, turning complex graph prediction into a simple sequence labeling task. By leveraging "rope covers," the approach eliminates restrictive hyperparameters, shrinks the label space, and achieves 100% theoretical coverage while delivering state-of-the-art exact match accuracy.
What Problem Does This Paper Address?
While syntactic parsing often represents sentences as trees, semantic relationships frequently require graphs to capture complex phenomena like reentrancies (nodes with multiple heads), cycles, and disconnected components.
Parsing graphs is traditionally computationally expensive, requiring complex graph-based or transition-based decoders. A simpler alternative is Sequence Labeling (SL), which flattens the graph structure into a sequence of tags. However, previous SL graph parsers relied on a "plane-splitting" technique to handle crossing edges. This required a hard hyperparameter ($k$ planes) that limited the parser's theoretical coverage and bloated the label space as $k$ increased. The authors set out to eliminate this hyperparameter bottleneck while keeping the label space compact and learnable.
Methods
The authors operationalize the concept of rope covers and structural sets to create a Hierarchical Bracketing Encoding (HB) for graphs.
Instead of splitting edges into arbitrary planes, the graph is decomposed into a unique, mathematically optimal set of "structural arcs" (the rope cover) and "auxiliary arcs" that lean on them.
- Structural arcs are encoded using balanced superbrackets (e.g.,
\,>,<,/). - Auxiliary arcs are encoded using single bracket symbols.
- Crossing arcs between different structural sets are resolved by appending integer indices to the symbols, telling the decoder how many structural arcs to skip during processing.
This encoding allows a standard sequence tagger (XLM-RoBERTa or XLNet paired with simple feed-forward networks) to predict graph structures in linear time ($n$ tagging actions). A straightforward post-processing step handles any structurally invalid or unbalanced bracket sequences at inference time.
Datasets
The approach was evaluated on a comprehensive multilingual and multi-formalism benchmark:
- SemEval 2015 Task 18: Broad-coverage semantic dependency parsing datasets, including English (DM, PAS, PSD), Chinese (PAS), and Czech (PSD).
- IWPT 2021 Shared Task: Enhanced Universal Dependencies datasets covering 17 diverse languages.
Key Insights and Ideas
- Guaranteed 100% Coverage: Moving away from rigid $k$-plane heuristics to a principled rope-cover framework guarantees that any graph structure can be losslessly encoded and decoded without hyperparameter tuning.
- The Power of Balance: Hierarchical encoding results in a much more compact and balanced label distribution. For instance, in the English-DM dataset, the top 2.03% of HB labels account for half of all occurrences, compared to less than 1% for previous methods.
- Entropy and Exact Match: The authors discovered a strong linear correlation (up to 88.1%) between how balanced an encoding's label distribution is ($p_{0.5}$) and its exact match parsing performance. A more compact, well-distributed label space makes it easier for the model to get the entire sentence right.
Key Results
- State-of-the-Art Exact Match (LM): The HB approach outperforms previous sequence labeling methods and a strong graph-based Biaffine baseline on 7 treebanks, achieving the highest average exact match score across the board (HB: 38.50 vs. Biaffine: 37.69).
- Competitive F1 Scores: While HB slightly trails the best bounded bit-based encoding and the Biaffine baseline in Labeled F1 (LF) score (88.59 average LF vs. Biaffine's 90.45), it remains highly competitive while operating with a significantly smaller label vocabulary.
Limitations and Future Work
- The F1 Gap: Although exact match scores improved, the overall Labeled F1 score is slightly lower than traditional graph-based parsers, indicating room for improvement in token-level edge precision.
- Theoretical Unboundedness: In theory, the number of possible labels is unbounded because indices can grow arbitrarily large for highly complex graphs. However, the authors demonstrate that in practice, it actually uses fewer unique labels than bounded methods on real-world datasets.
- Scope of Formalisms: The empirical evaluation was limited to semantic graph parsing and enhanced dependency parsing. Future work could test its efficacy on other graph-based NLP tasks, such as structured sentiment analysis or emotion-cause chain extraction.
Summary updated