A constrained graph algebra for semantic parsing with AMRs

Jonas Groschwitz, Meaghan Fowlie, Mark Johnson, Alexander KollerIWCS 2017 · OpenReview

A Constrained Graph Algebra for Semantic Parsing with AMRs

Introduction

Semantic parsing involves translating natural language into formal meaning representations. Abstract Meaning Representation (AMR) has emerged as a popular format, representing sentence semantics as rooted, directed graphs. However, a significant hurdle in developing effective semantic parsers is grammar induction: the process of discovering the intermediate steps required to construct a target AMR graph from a given sentence.

The Problem of Spurious Ambiguity

Previous approaches to grammar induction often relied on the Hyperedge Replacement (HR) algebra. While mathematically robust, the HR algebra is overly flexible, offering a vast number of ways to assemble even simple graphs. For a graph with only five nodes, the HR algebra can generate approximately $10^{17}$ distinct derivation terms. This "spurious ambiguity" creates a computational bottleneck, as most of these derivations are linguistically nonsensical, making it nearly impossible for a parser to efficiently find the correct structure.

The Apply-Modify (AM) Algebra

To address this, the authors introduce the Apply-Modify (AM) graph algebra. Unlike the generic operations of the HR algebra, the AM algebra is constrained by linguistic principles. It utilizes two primary operations:

  1. APP (Application): Represents a head (predicate) taking a complement (e.g., a verb taking an object).
  2. MOD (Modification): Represents an adjunct modifying a head (e.g., an adjective modifying a noun).
Comparison of AM and HR terms for graph construction, illustrating the step-by-step merge and forget process.

As shown in Figure 3, the AM algebra simplifies the derivation process by focusing on these core linguistic relations. The "secret sauce" of this framework is the introduction of graph types. Each graph fragment is annotated with its requirements—for instance, a transitive verb is typed to indicate it requires both a subject and an object. As operations are performed, these types are updated, ensuring that the resulting graph remains linguistically valid.

Handling Re-entrancy and Complex Structures

A defining feature of AMR is re-entrancy, where a single node can have multiple parents, representing shared semantic roles. This occurs in phenomena such as control ("The sheep wants to relax") or coordination.

An example AMR graph demonstrating complex re-entrancy where nodes like 'snake' and 'prey' serve multiple roles across different predicates.

The AM algebra handles re-entrancy through its type system rather than arbitrary merging. By allowing nodes to be shared across different parts of the derivation based on their types, the algebra naturally models complex linguistic constructions. This approach treats "blobs"—a central node and its immediate edges—as the atomic building blocks of the graph.

Empirical Results

The impact of these constraints is substantial. When evaluated on the AMRBank (LDC2016E25) corpus, the AM algebra demonstrated a dramatic reduction in search space. For a 5-node graph, the number of candidate terms dropped from $10^{17}$ in the HR algebra to just 21.

Furthermore, the AM algebra is significantly more efficient, decomposing large, complex graphs in seconds where the HR algebra would often time out. Despite its constraints, the AM algebra (specifically the AM-C2 variant) achieved higher dataset coverage than the HR algebra, suggesting that its linguistically-driven constraints align well with the actual structure of human language.

Conclusion

The AM algebra represents a significant step forward in semantic parsing. By replacing generic graph operations with linguistically motivated ones, it collapses the search space for grammar induction and provides a more efficient, interpretable framework for building AMR graphs. Future work will focus on using this algebra to induce full-scale grammars capable of mapping novel sentences to their semantic representations.

Summary updated

BibTeX
@inproceedings{groschwitz2017constrained,
  author = {Jonas Groschwitz and Meaghan Fowlie and Mark Johnson and Alexander Koller},
  title = {{A constrained graph algebra for semantic parsing with AMRs}},
  booktitle = {IWCS},
  year = {2017},
  url = {https://openreview.net/forum?id=M0HiksvAAHb},
}
Figure