Most natural language processing tools treat sentences as sequences or hierarchical trees. While trees are excellent for capturing syntax—how words group into phrases—they often fail to capture the full logic of a sentence. In a sentence like "John wants to eat," John is both the person doing the wanting and the person doing the eating. In a tree, a node can only have one parent, forcing us to choose one relationship or duplicate the entity.
To solve this, researchers use Abstract Meaning Representation (AMR) and other graph-based formalisms. These represent meaning as Directed Acyclic Graphs (DAGs), where a single concept can have multiple parents. This property, known as reentrancy, allows models to explicitly represent coreference, shared arguments, and complex logical structures.
The Challenge of Reentrancy
The core difficulty in this field is a structural mismatch. As Jacob Andreas and Kevin Knight noted in Semantics-Based Machine Translation with Hyperedge Replacement Grammars, while human meaning is inherently reentrant, most standard grammar formalisms are restricted to strings or trees.
When a single concept participates in multiple relations, standard parsers struggle. If you try to "flatten" a graph into a tree to use off-the-shelf tools, you lose the very connections that define the sentence's logic. Marco Damonte and Shay B Cohen demonstrated in Structural Neural Encoders for AMR-to-text Generation that preserving these reentrancies is essential; models that keep the full graph structure significantly outperform those that simplify graphs into trees.
Parsing: Turning Text into Graphs
How do we transform a linear string of words into a complex web of semantic relations? Researchers have converged on three main strategies:
- Transition-based Parsing: These models process a sentence from left to right, using a stack to keep track of concepts and a set of actions (like "Add Edge") to build the graph. Marco Damonte introduced AMREager An Incremental Parser for Abstract Meaning Representation, which operates in linear time. Similarly, Miguel Ballesteros utilized Stack-LSTMs AMR Parsing using Stack-LSTMs to manage the parser's state, allowing the model to predict non-projective edges where relationships cross over each other.
- Graph Optimization: Rather than building the graph step-by-step, some models identify all possible concepts first and then find the most likely set of edges to connect them. Jeffrey Flanigan pioneered this with JAMR A Discriminative Graph-Based Parser for the Abstract Meaning Representation, treating parsing as a Maximum Spanning Connected Subgraph problem.
- Grammar-based Approaches: Some researchers use formal graph grammars to ensure the output is mathematically sound. Alexander Koller and Jonas Groschwitz developed highly efficient algorithms for s-graph grammars Graph parsing with s-graph grammars, which use algebraic operations to assemble graphs from smaller fragments.
Generation: Turning Graphs into Text
The inverse problem—generating natural language from a graph—requires the model to decide the order in which to visit nodes and how to express their relationships.
Traditional Graph Neural Networks (GNNs) often struggle here because they only pass information between immediate neighbors. In a semantic graph, two nodes might be conceptually related but many hops apart. To fix this, Deng Cai and Wai Lam proposed the Graph Transformer Graph Transformer for Graph-to-Sequence Learning. By encoding the shortest path between any two nodes directly into the attention mechanism, the model allows every concept to communicate with every other concept, regardless of their distance in the graph.
Other approaches treat generation as a combinatorial puzzle. Linfeng Song and Yue Zhang reframed AMR-to-text generation as a Traveling Salesman Problem AMR-to-text generation as a Traveling Salesman Problem, searching for the optimal sequence to visit graph fragments to produce a coherent sentence.
Beyond English: Cross-Lingual Semantics
Because AMR represents "who did what to whom" rather than specific words, it is a powerful tool for machine translation and cross-lingual tasks. Dongqin Xu and Junhui Li developed XLPT-AMR XLPT-AMR: Cross-Lingual Pre-Training via Multi-Task Learning for Zero-Shot AMR Parsing and Text Generation, which uses English AMR data to enable "zero-shot" parsing in other languages. By treating the semantic graph as a universal "pivot," these models can bridge the gap between languages with very different syntactic structures.
Ultimately, the shift from trees to graphs represents a move toward a more "holistic" understanding of language. By explicitly modeling reentrancy and non-linear dependencies, these systems capture the underlying logic of human thought more faithfully than a simple hierarchy ever could.