Tree Approximations for Semantic Graph Parsing

This direction is merged into another direction: graph-to-tree information loss. Its last version stays readable and citable here.

Version 1 of 128 papers39 conceptsfrozen 2026-10-04

In natural language processing, we often represent the structure of a sentence as a tree. This works well for syntax—where each word typically has one "head"—but it fails to capture the full complexity of meaning. Semantic representations, such as Abstract Meaning Representation (AMR) or Universal Conceptual Cognitive Annotation (UCCA), are naturally Directed Acyclic Graphs (DAGs). In these graphs, a single entity can play multiple roles (re-entrancy), and relationships can form complex, non-hierarchical webs.

The central tension in this research area is a trade-off between computational efficiency and representational fidelity. While we have highly optimized, fast algorithms for parsing trees, parsing general graphs is significantly harder. To bridge this gap, researchers have developed "tree approximation" methods that attempt to squeeze semantic graphs into tree structures.

The Tree Bottleneck

The primary reason to use trees is pragmatic: we have decades of research into efficient tree parsers. As David McClosky, Christopher D Manning, and Mihai Surdeanu demonstrated in Event Extraction as Dependency Parsing, framing complex event extraction as a tree-parsing problem allows the use of global reranking parsers.

However, this convenience comes at a cost. Trees are strictly hierarchical; every node (except the root) has exactly one parent. In contrast, semantic graphs often feature re-entrancy, where a node has multiple parents. For example, in the sentence "John wants to eat," the entity "John" is both the wanter and the eater. In a tree, you must choose one path or the other. When Michael Pust and Kevin Knight adapted syntax-based machine translation to parse AMR in Parsing English into Abstract Meaning Representation Using Syntax-Based Machine Translation, they noted that converting these DAGs into trees creates an inherent performance ceiling. If the conversion process discards re-entrant edges, the system can never recover those semantic nuances, leading to an irreversible loss of recall.

Squeezing Graphs into Trees

To minimize this loss, researchers use two primary strategies to transform graphs into trees: pruning and encoding.

Pruning and Packing

In Copenhagen-Malmö: Tree Approximations of Semantic Parsing Problems, Anders Søgaard and Natalie Schluter describe techniques to "trick" tree parsers. Pruning involves removing edges that violate tree constraints (like cycles or multiple parents). While this simplifies the task, it is subtractive. To counter this, "packing" attempts to store the information of the removed edges elsewhere, often within the labels of the remaining edges.

Label Encoding

Instead of just deleting an edge, we can encode the "missing" relationship into the label of a nearby tree edge. Yoshihide Kato and Shigeki Matsubara applied this to the Penn Treebank in PTB Graph Parsing with Tree Approximation, encoding nonlocal dependencies like "traces" directly into tree labels.

This creates a new trade-off: structural simplicity vs. label complexity.

  1. If you keep the labels simple, the parser is fast and accurate, but you lose the graph's richness.
  2. If you encode graph paths into labels, you preserve information, but you create a "long tail" of rare, complex labels.

As Jenna Kanerva and Filip Ginter found in their work on Enhanced Universal Dependencies, these infrequent labels are difficult for machine learning models to generalize, acting as a primary bottleneck for parser accuracy.

Beyond the Tree Approximation

While tree approximations are powerful, some researchers argue that we should stop trying to flatten the meaning of language. In A Transition-Based Directed Acyclic Graph Parser for UCCA, Daniel Hershcovich and Omri Abend introduced TUPA, a parser designed from the ground up to handle DAGs without converting them to trees first. By using a specialized set of transitions that allow for creating re-entrant edges and discontinuous units, they avoid the "information loss" inherent in approximation.

Similarly, Linfeng Song and Yue Zhang moved away from intermediate trees in AMR-to-text Generation with Synchronous Node Replacement Grammar. They argued that when we force non-projective semantic dependencies into a tree format, we propagate errors that the final generation process can never fix.

Why It Works (and Why It Fails)

Tree approximation works because language is mostly hierarchical. Most semantic relations follow the syntactic backbone of the sentence. If the "non-tree" parts of a semantic formalism occur infrequently, the efficiency gains of using a standard tree parser outweigh the minor loss in accuracy.

However, as we move toward "deeper" semantics—capturing discourse structures as Jiangming Liu and Mirella Lapata do in Discourse Representation Structure Parsing—the "tree-likeness" of the data decreases. In these cases, the loss of nuanced logical constraints and pointers becomes a significant barrier, pushing the field toward native graph-based architectures.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_tree_approximations_for_semantic_graph_p_f88cee9b,
  title = {Tree Approximations for Semantic Graph Parsing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tree-approximations-for-semantic-graph-parsing/rdr_f88cee9b2e264168bab6e2255de754dd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_tree_approximations_for_semantic_graph_p_f88cee9b_v1,
  title = {Tree Approximations for Semantic Graph Parsing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tree-approximations-for-semantic-graph-parsing/rdr_f88cee9b2e264168bab6e2255de754dd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}