Bidirectional Message Passing in Directed Graphs

20 concepts17 papers1 proposal

When modeling structured data—whether it is a natural language dependency tree, a source code flowchart, or a neural network architecture—we often turn to directed graphs. Directed edges are powerful because they preserve asymmetric relationships: they tell us that a SQL clause modifies a specific table, or that a software operation passes its output to a subsequent layer.

However, standard Graph Neural Networks (GNNs) face a fundamental dilemma when processing directed graphs. If they strictly follow the direction of the edges, information only flows one way (e.g., from parent to child). This creates a structural blind spot where upstream nodes remain completely oblivious to downstream context. Conversely, if we ignore edge directions entirely to allow free communication, we erase the hierarchical and logical constraints that define the graph's meaning.

To resolve this, a prominent research direction employs bidirectional graph encoding. By explicitly propagating information along both the original and the reversed edge directions, models can capture a node's complete structural context without sacrificing the underlying asymmetry of the network.

The Information Bottleneck of One-Way Flow

To understand why bidirectional encoding is necessary, consider how a node builds its representation in a directed graph. In a standard message-passing scheme, a node updates its state by aggregating features from its immediate neighbors. If the graph is directed, this aggregation is typically restricted to either incoming edges (in-degree) or outgoing edges (out-degree).

As Frank et al. point out in the context of graph summarization, defining node relationships based solely on one direction severely limits a model's ability to capture the full topological context. If a model only looks downstream, it cannot see what influenced its current state; if it only looks upstream, it cannot anticipate its downstream impact.

In natural language processing, this one-way flow breaks semantic cohesion. For example, during Abstract Meaning Representation (AMR) to text generation, Song et al. argue that unidirectional information flow fails to provide the complete structural role of a concept, which is vital for determining correct grammatical forms. To accurately translate a semantic node, the model must simultaneously resolve its relationship to both its parents and its children.

The Dual-Path Solution

The core mechanism of bidirectional graph encoding is elegant: instead of choosing between forward or backward propagation, the network executes both. This is typically achieved through two parallel paths:

  1. The Forward Path: Processes the graph using its original edge directions to capture top-down, causal, or source-to-target context.
  2. The Reverse Path: Processes an inverted version of the graph (where every edge $u \to v$ becomes $v \to u$) to capture bottom-up, relational, or target-to-source context.
Original Graph (Forward Path)       Reversed Graph (Reverse Path)
       [Root Node]                         [Root Node]
          /   \                               ^     ^
         v     v                             /       \
    [Child 1] [Child 2]                 [Child 1] [Child 2]

By maintaining separate parameter spaces or attention heads for these two paths, the model preserves the distinct meaning of edge directionality while ensuring global information flow.

For instance, Ribeiro et al. and Zhao et al. utilize this dual-encoder strategy for AMR graphs. The forward pass tracks global hierarchical context originating from the root node, while the reverse pass aggregates local semantic constraints from the leaf nodes. Combining these views yields a comprehensive embedding where each node knows both its global position and its local boundaries.

Why It Works: Domain Intuitions

The success of bidirectional graph encoding spans multiple domains because it maps directly to how humans reason about dependencies.

1. Syntax and Semantics (NLP)

In sentence simplification and coreference resolution, words cannot be understood in isolation from their syntactic phrases. Wan et al. demonstrate that encoding semantic dependency graphs via separate forward and reverse passes ensures that the source and target of an action are equally represented.

When resolving complex phrase structures, Jiang et al. use a bidirectional Graph Attention Network (GAT) to pass information upward from individual tokens to overarching phrases, and downward from phrases back to tokens. Similarly, Du shows that bilateral information flow allows features to propagate fluidly across dependency trees, significantly reducing the search space for multilingual sentence generation.

2. Logic and Control Flow (SQL and Source Code)

For structured execution paths like SQL queries or flowcharts, edge direction dictates logic. Xu et al. show that distinguishing between incoming and outgoing edges is critical for maintaining the logical integrity of structured data during translation.

When generating code from visual flowcharts, Liu et al. apply bidirectional encoding so that each step in the generated code accounts for both its execution predecessors (how it was reached) and its subsequent targets (where it leads).

3. Inputs vs. Downstream Impacts

In tasks like Neural Architecture Search (NAS) or task scheduling, a node represents an operation or a task. Lukasik et al. and Lukasik et al. use bidirectional propagation to predict neural network performance. The forward pass models how data changes as it flows through layers, while the backward pass captures how a specific layer's operations constrain downstream performance.

This is mirrored in computational scheduling: Huang et al. extract structural features from Directed Acyclic Graphs (DAGs) by performing two-way aggregation across predecessor and successor nodes, allowing deep reinforcement learning models to spot data bottlenecks before they occur.

4. Propagation vs. Dispersion

Social media networks exhibit distinct directional dynamics during information cascades. Bian et al. apply bidirectional graph convolutions to rumor detection by modeling two distinct patterns: the top-down causal path of how a rumor spreads from a source to followers, and the bottom-up dispersion path showing how responsive communities aggregate around specific sub-structures.

Conclusion

Bidirectional graph encoding works because it treats edge directionality as a feature to be leveraged rather than a constraint that limits communication. Whether aggregating multi-hop subgraphs for question generation (Chen et al.) or aligning entities across knowledge graphs (Wang et al.), capturing both the in-degree and out-degree contexts ensures that the final node representations are fully aware of their place within the global topology.

Key Foundational Work

A Graph-to-Sequence Model for AMR-to-Text Generation (2018) — contributed 3 concept elements to this direction.
Enhancing AMR-to-Text Generation with Dual Graph Representations (2019) — contributed 2 concept elements to this direction.
Learning to Order Graph Elements with Application to Multilingual Surface Realization (2019) — contributed 2 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_bidirectional_graph_encoding_41c25b4c,
  title = {bidirectional graph encoding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bidirectional-graph-encoding/rdr_41c25b4cece74d7086b82c4d735531df},
  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_bidirectional_graph_encoding_41c25b4c_v1,
  title = {bidirectional graph encoding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bidirectional-graph-encoding/rdr_41c25b4cece74d7086b82c4d735531df/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake