Transition Based Incremental Graph Construction

26 concepts21 papers1 proposal

Many natural language processing tasks require transforming a linear sequence of words into a complex, interconnected graph. Whether mapping a sentence to an Abstract Meaning Representation (AMR), extracting overlapping event triggers, or identifying argument structures, the target output is rarely a simple sequence or a clean tree. Instead, it is often a Directed Acyclic Graph (DAG) where nodes can have multiple parents, and entities can participate in several overlapping relations.

Traditionally, models tackled this structural complexity using multi-stage pipelines (e.g., first identifying entities, then predicting relations) or exhaustive global optimization. However, pipelines suffer from severe error propagation—a mistake in early entity extraction dooms subsequent relation assignment. Conversely, global optimization models face a combinatorial explosion, often requiring quadratic time complexity to evaluate every possible pair of nodes.

To resolve these challenges, a prominent line of research focuses on incremental transition-based graph construction. The core intuition is to decompose the global graph generation task into a sequence of localized, discrete actions. By processing the text linearly and building the graph step-by-step, these systems achieve linear time complexity while allowing information to flow bi-directionally between subtasks.


The Core Mechanism: Stacks, Buffers, and Transition Actions

The foundation of incremental graph construction relies on a state-transition system, typically adapted from syntactic dependency parsing. The parser maintains a memory state composed of a buffer (containing incoming words or concepts) and a stack (holding partially constructed graph structures).

At each step, the model selects from a set of discrete actions—such as Shift (move an element from the buffer to the stack), Node (create a semantic concept), or Arc (establish a directed edge between elements). As shown by Daniel Hershcovich et al. in TUPA at MRP 2019: A Multi-Task Baseline System, this simple abstraction allows a single architecture to parse highly diverse semantic graph frameworks by reducing the problem to a series of local classification decisions.

Initial State:  [Stack: [Root]]       [Buffer: "John", "seeks", "a", "unicorn"]
Action 1: Shift -> [Stack: [Root, John]] [Buffer: "seeks", "a", "unicorn"]
Action 2: Node  -> [Stack: [Root, John, SEEK-01]] ...
Action 3: LeftArc-> Establishes (SEEK-01 -> John) as an argument relation

This step-by-step assembly fundamentally changes how models handle structural complexity. For instance, Shaolei Wang et al. applied this to joint entity and relation extraction in Joint Extraction of Entities and Relations Based on a Novel Graph Scheme, demonstrating that a transition-based system can naturally handle overlapping relations where a single entity participates in multiple facts. Similarly, Chuang Fan et al. utilized a stack-buffer transition model in Transition-based Directed Graph Construction for Emotion-Cause Pair Extraction to extract emotions and their underlying causes simultaneously, bypassing the error propagation inherent in multi-stage pipelines.

By framing graph construction as a path through a transition state-space, the computational burden drops dramatically. As noted by Jianzhu Bao et al. in A Neural Transition-based Model for Argumentation Mining, this transition strategy reduces the computational complexity of building argument graphs from quadratic to linear, eliminating the need to exhaustively evaluate all possible component pairs.


Why It Works: Dynamic State Refinement

A naive transition system makes decisions based purely on static representations of the input words. However, the true power of modern incremental parsing lies in dynamic state refinement: updating the representations of nodes in real time as new edges are discovered.

When a parser creates a relation between two nodes, the semantic roles of those nodes change. For example, once a word is identified as the patient of a verb, its vector representation should reflect that role in all future decisions.

The authors of Transition-based Dependency Parsing Using Two Heterogeneous Gated Recursive Neural Networks addressed this by introducing specialized Gated Recursive Neural Networks (GRNNs). Every time a new dependency arc is formed, the model updates the node embeddings in the stack, ensuring that the representation of the partial parse tree evolves alongside the sentence structure.

[Node A] + [Node B]  ---(Arc Action)--->  [Node A (Updated)] ----> [Node B (Updated)]
       │                                         │
 (Static Vector)                           (Refined with Structural Context)

This concept was extended to graph structures by Wanxiang Che et al. in A Neural Transition-Based Approach for Semantic Dependency Graph Parsing. Because semantic graphs are DAGs rather than trees, words frequently serve as arguments for multiple predicates. By using a tree-structured neural network to dynamically update node representations as new edges are added, the parser incorporates the evolving sub-graph topology directly into its future decision-making states.

Even when using powerful sequential encoders like BiLSTMs, explicitly re-encoding the state as the graph grows provides a crucial structural bias. As Miryam de Lhoneux demonstrated in Recursive Subtree Composition in LSTM-Based Dependency Parsing, incremental state re-encoding ensures that the model's internal features dynamically track the hierarchical relationships established during the parsing process.


Conditioning on the Partial Graph

Beyond updating individual node vectors, the sequence of actions itself can be conditioned on the topology of the partially constructed graph. This creates a feedback loop where structural history guides future structural discovery.

In AMR Parsing via Graph-Sequence Iterative Inference, Deng Cai et al. designed an end-to-end parser that builds graphs one node at a time. Instead of predicting the entire structure in a single pass, the model maintains a living representation of the partial graph state. Concept prediction (what node to add next) and relation prediction (where to connect it) mutually inform and refine each other at every step.

This incremental conditioning proves highly effective for resolving complex structural ambiguities:

Ultimately, incremental graph construction works because it balances local transition efficiency with global structural awareness. By breaking down a complex graph into a sequence of well-informed, state-refining actions, these models parse deep semantic meaning with remarkable speed and accuracy.

Key Foundational Work

Interpretation of Noun Phrases in Intensional Contexts (1988) — contributed 1 concept elements to this direction.
Semantic Parsing as Graph Language Transformation - A Multidimensional Approach to Parsing Highly Inflectional Languages (1984) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_incremental_graph_construction_182860d6,
  title = {incremental graph construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/incremental-graph-construction/rdr_182860d696b242f99bb84aef0ca02523},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_incremental_graph_construction_182860d6_v1,
  title = {incremental graph construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/incremental-graph-construction/rdr_182860d696b242f99bb84aef0ca02523/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake