Dual Message Passing for Co-evolving Nodes and Edges

This direction is merged into another direction: node-edge co-evolution. Its last version stays readable and citable here.

Version 1 of 119 papers24 conceptsfrozen 2026-10-04

In traditional Graph Neural Networks (GNNs), edges are often treated as "second-class citizens." They might serve as static weights or one-hot labels to guide the aggregation of node features, but they rarely change. However, in many real-world systems—like molecules where bonds have specific properties or knowledge graphs where relations carry deep semantic meaning—the edges are just as informative as the nodes they connect.

A growing body of research proposes a shift toward Dual Message Passing. Instead of only updating node representations, these models treat nodes and edges as equal partners that evolve through a reciprocal, bidirectional conversation.

The Communicative Loop

The core intuition behind this direction is that node identities are shaped by their connections, and connection identities are shaped by the nodes they join. To capture this, models like CMPNN, developed by Ying Song and colleagues, implement a "two-way conversation."

In each layer of such a network, the update happens in two interleaved steps:

  1. Edge-to-Node: Nodes aggregate the features of their incident edges to update their latent states.
  2. Node-to-Edge: Edges then aggregate the updated features of their endpoint nodes to refine their own representations.

This iterative exchange ensures that relational information is dynamically integrated into the reasoning process. As Sijie Mai and Shuangjia Zheng demonstrate with the CoMPILE framework, this communicative approach is particularly powerful for inductive reasoning, where the model must predict relationships between entities it has never seen before by relying on the evolving semantics of the graph's structure.

Switching Perspectives with Line Graphs

How do you mathematically treat an edge like a node? Several researchers, including Xiaodong Jiang and Sheng Li, solve this by leveraging the Line Graph.

In a line graph, the edges of the original graph become nodes, and two of these new "nodes" are connected if their corresponding original edges shared a common endpoint. By alternating between the original graph and its line graph dual, the CensNet architecture (Convolution with Edge-Node Switching) allows standard graph convolution operations to be applied to both domains.

Xin Liu and Yangqiu Song formalized this in DMPNN, proving that searching for patterns in a graph is mathematically equivalent to searching in its dual. This symmetry allows the model to align node and edge representations in a shared latent space, making it significantly more effective at identifying complex structural matches like subgraph isomorphisms.

Contextualizing Relations

Treating edges as dynamic features allows models to capture context that static models miss. In natural language processing, Shiyao Cui and Tingwen Liu introduced EE-GCN, which treats syntactic dependency labels (like "subject" or "object") as context-aware features. As the model processes a sentence, the representation of the "subject" relation changes based on the specific words it connects, leading to more precise event detection.

Similarly, in computer vision, the BC-GNN model by Yueran Bai and Yunhai Tong applies this to video. They treat temporal boundaries as nodes and the video content between them as edges. By letting the boundaries and content "talk" to each other, the model refines its understanding of where an action starts and ends based on the visual evidence of the action itself.

Why Co-evolution Matters

The shift toward dual updating represents a move away from "squashing" rich relational data into static vectors. Whether it is Ruisheng Cao using line graphs to improve Text-to-SQL translation or Liang Li automating the discovery of these architectures through EGNAS, the conclusion is the same:

When edges are allowed to learn and adapt alongside nodes, the model gains a much deeper "structural IQ." It no longer just sees that two things are connected; it understands the evolving nature of that connection within the global context of the graph.

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_dual_message_passing_for_co_evolving_nod_85181cc7,
  title = {Dual Message Passing for Co-evolving Nodes and Edges},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dual-message-passing-for-co-evolving-nodes-and-edges/rdr_85181cc7eb0f4998a9e8de19fa7629c9},
  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_dual_message_passing_for_co_evolving_nod_85181cc7_v1,
  title = {Dual Message Passing for Co-evolving Nodes and Edges},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dual-message-passing-for-co-evolving-nodes-and-edges/rdr_85181cc7eb0f4998a9e8de19fa7629c9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}