Graph Traversal Strategies for Sequential Semantic Modeling

This direction is merged into another direction: graph linearization. Its last version stays readable and citable here.

Version 1 of 153 papers56 conceptsfrozen 2026-10-04

The core challenge in modern Natural Language Processing is the structural mismatch between how machines represent meaning and how they process language. Meaning is often represented as a graph—a multi-dimensional web of entities and relations like Abstract Meaning Representation (AMR) or Knowledge Graphs (KG). However, our most powerful models, such as Transformers and LSTMs, are fundamentally sequential; they are designed to read and write strings of text.

To bridge this gap, researchers have converged on a powerful, counter-intuitive strategy: instead of building specialized "graph-native" architectures, we should simply flatten the graphs into sequences. This process, known as linearization, allows us to treat complex semantic reasoning as a machine translation task.

The Art of Flattening

A graph has no inherent start or end, but a sequence does. To convert a graph into a string, we must decide on a traversal order that preserves as much structural information as possible.

As Leonardo F. R. Ribeiro demonstrates, general-purpose Pretrained Language Models (PLMs) like BART and T5 can outperform specialized graph architectures if the graph is serialized effectively. Common techniques include:

  • Depth-First Search (DFS) with Brackets: This method, often using PENMAN notation, uses parentheses to denote hierarchy. For example, a node and its children are wrapped in brackets, allowing the model to "see" the tree-like structure within a flat string. Deng Cai and Jackie Chun-Sing Ho have used this to retrofit sentence embeddings with semantic structure.
  • Breadth-First Search (BFS): Jinhao Jiang and Wayne Xin Zhao argue that BFS is superior for preserving local connectivity and structural proximity, ensuring that entities related in the graph remain close to each other in the resulting sequence.
  • Triple Serialization: For Knowledge Graphs, the simplest approach is often the most effective: converting facts into (subject, predicate, object) triples separated by special tokens. Pierre Dognin and Inkit Padhi show that this allows models to treat graph-to-text generation as a standard sequence-to-sequence problem.

Why Transformers Don't Need Graph Layers

A recurring finding across the literature is that specialized Graph Neural Networks (GNNs) are often unnecessary for semantic tasks. Luigi Procopio and Roberto Navigli frame this as "speaking the graph language."

The intuition lies in the Self-Attention mechanism. Because self-attention allows every token in a sequence to look at every other token, the model can dynamically reconstruct the graph's topology internally. If the linearized string contains enough "clues"—such as coreference markers or structural brackets—the Transformer can learn to attend to the "neighbors" of a node even if they are far apart in the flattened string. Jiaxin Bai and Yangqiu Song proved this by showing that "Sequential Query Encoding" (SQE) achieves state-of-the-art performance on complex logical queries without any recursive neural operators.

Overcoming the Sequential Bottleneck

Linearization is not without its flaws. When we force a graph into a line, we introduce a "search space" problem: which node should come first?

Early work by Linfeng Song and Yue Zhang treated this as a Traveling Salesman Problem (TSP), searching for the most fluent path through the graph's fragments. More recently, researchers have focused on Structure Loss Accumulation. In a long sequence, the model might forget the high-level structure by the time it reaches the end.

To solve this, Bofei Gao and Baobao Chang introduced Reverse Graph Linearization (RGL). By providing the model with a reversed version of the graph string, they move complex structural dependencies to the beginning of the sequence, where the model's hidden states are "fresher" and less prone to error.

Semantic Parsing as Machine Translation

The ultimate realization of this research direction is that semantic parsing (Text-to-Graph) and realization (Graph-to-Text) are just two sides of the same translation coin. Hongbin Ye and Ningyu Zhang note a massive shift from task-specific discriminative classifiers to unified generative models.

By linearizing graphs, we can leverage the "pre-trained wisdom" of models like GPT-4 or T5. As Dongqin Xu and Junhui Li demonstrate, pre-training on standard machine translation tasks actually helps the model learn how to parse AMR graphs, because both tasks require mapping one structured sequence to another.

In this paradigm, the graph is not a separate data structure to be engineered; it is simply another language for the model to speak. Whether it is extracting events in Doc2Event or generating radiology reports with FactReranker, the path to success is the same: flatten the complexity, and let the sequence model do the rest.

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_graph_traversal_strategies_for_sequentia_d8819b2d,
  title = {Graph Traversal Strategies for Sequential Semantic Modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-traversal-strategies-for-sequential-semantic-modeling/rdr_d8819b2d7b4c42f8973493a7263b946a},
  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_graph_traversal_strategies_for_sequentia_d8819b2d_v1,
  title = {Graph Traversal Strategies for Sequential Semantic Modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-traversal-strategies-for-sequential-semantic-modeling/rdr_d8819b2d7b4c42f8973493a7263b946a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}