Hierarchical Bracketing Encodings Work for Dependency Graphs

Ana Ezquerro, Carlos Gómez-Rodríguez, David Vilares

TL;DR

This paper introduces a novel hierarchical bracketing encoding for dependency graphs, enabling efficient sequence labeling for graph parsing. This approach significantly reduces the label space while preserving crucial structural information like reentrancies and cycles, leading to improved exact match accuracy on a multilingual benchmark.

What Problem Does This Paper Address?

Dependency graph parsing, which models complex linguistic relationships beyond simple trees, has traditionally relied on intricate graph-based or transition-based decoders. While sequence labeling (SL) offers a simpler and more scalable approach for structured prediction tasks, adapting it to the complexities of graphs—specifically reentrancies, cycles, and disconnected components—has been a significant challenge. Existing graph linearization methods often struggle to represent these structures without exploding the label space or losing information. This paper aims to bridge this gap by demonstrating that a hierarchical bracketing encoding, previously applied to trees, can be effectively adapted for dependency graphs within an SL framework, simplifying the decoding process.

Methods

The core contribution is the application and empirical validation of a hierarchical bracketing encoding for dependency graphs. This method builds upon the concept of "rope covers" to define structural and auxiliary arcs within a graph. Each structural set (a structural arc and the auxiliary arcs that "lean" on it) is then encoded using a unique set of balanced superbrackets and single brackets. This hierarchical approach is theoretically defined to be optimal in terms of structural arcs and, crucially, removes the need for a hyperparameter k that limits the number of "relaxed planes" in previous bracketing methods. This leads to a more compressed representation and guaranteed 100% coverage of dependency graphs. The authors also detail a postprocessing step to correct any structurally invalid sequences predicted by the SL model.

Datasets

The experiments were conducted on a diverse set of datasets, including:

  • Five datasets from SemEval 2015 Task 18 with semantic annotations:
  • English dataset annotated with DELPH-IN MRS-Derived Bi-Lexical Dependencies (enDM)
    • English and Chinese datasets with Enju Predicate-Argument Structures (enPAS, ZhPAS)
    • English and Czech datasets with Prague Semantic Dependencies (enPSD, CSPSD)
  • A selection of datasets from the IWPT 2021 Shared Task (Bouma et al., 2021) with enhanced dependencies across 17 languages.

Key Insights and Ideas

  • Hierarchical Bracketing for Graphs: The paper successfully extends a hierarchical bracketing encoding, originally designed for trees, to handle the complexities of dependency graphs, including reentrancies and cycles.
  • Reduced Label Space and Full Coverage: The proposed method offers a more compact label space compared to previous bracketing encodings and guarantees 100% coverage of dependency graphs, unlike methods limited by a hyperparameter k.
  • Balanced Label Distribution is Key: A crucial finding is the strong correlation between a balanced label distribution (where a small percentage of frequent labels covers a large portion of occurrences) and improved exact match accuracy. The hierarchical bracketing encoding naturally leads to such a balanced distribution.
  • SL as a Viable Alternative for Graph Parsing: The work reinforces the idea that sequence labeling can be a powerful and simpler alternative to complex decoders for dependency graph parsing.

Key Results

The hierarchical bracketing encoding (HB) demonstrated competitive performance across a multilingual and multi-formalism benchmark.

  • Labeled F1 (LF) Score: HB achieved an average LF score that was only slightly below previous methods, with notable performance on specific treebanks. The biaffine parser generally achieved the highest LF score.
  • Exact Match (LM) Score: HB significantly outperformed other approaches, including the biaffine baseline, in exact match accuracy on 7 treebanks and achieved the best average LM score (38.50%).
  • Coverage: HB guarantees 100% coverage, outperforming methods like B64 where coverage is limited by k.
  • Label Space: The HB encoding results in a more balanced label distribution, which is shown to correlate with better exact match performance.

Limitations and Future Work

  • Unboundedness: The paper acknowledges that the proposed encoding is theoretically unbounded, meaning the number of labels needed is not fixed by a constant. However, they note that in practice, it requires fewer labels than some bounded encodings.
  • Future Work: The authors suggest that their work is the first empirical demonstration of hierarchical bracketing for dependency graph parsing, opening avenues for further research in this area. The success of this approach could lead to simpler and more efficient graph parsing systems.

Summary updated

Abstract

We revisit hierarchical bracketing encodings from a practical perspective in the context of dependency graph parsing. The approach encodes graphs as sequences, enabling linear-time parsing with $n$ tagging actions, and still representing reentrancies, cycles, and empty nodes. Compared to existing graph linearizations, this representation substantially reduces the label space while preserving structural information. We evaluate it on a multilingual and multi-formalism benchmark, showing competitive results and consistent improvements over other methods in exact match accuracy.
BibTeX
@inproceedings{ezquerro2025hierarchical,
  author = {Ana Ezquerro and Carlos Gómez-Rodríguez and David Vilares},
  title = {{Hierarchical Bracketing Encodings Work for Dependency Graphs}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure