Sequential Path Modeling in Graph Neural Networks

93 concepts72 papers1 proposal

Standard Graph Neural Networks (GNNs) are built on a fundamental constraint: permutation invariance. To process a node's neighborhood, a model must treat its neighbors as an unordered set, typically using symmetric aggregators like sum, mean, or max. While this ensures the model is indifferent to the arbitrary indexing of nodes, it creates a structural "blindness." By discarding the order and specific arrangements of connections, standard GNNs struggle to distinguish complex topological features like cycles and cliques, and often fail to capture the logical flow of multi-hop relationships.

A growing body of research suggests that we can break this bottleneck by reframing graph structures—such as neighborhoods and multi-hop paths—as sequences. By applying recurrent neural networks (RNNs) or Transformers to these structural sequences, models can capture the nuanced dependencies and compositional logic that define complex networks.

Breaking the Permutation Invariance Bottleneck

The primary limitation of standard message passing is that it is "nearsighted." As Flam-Shepherd et al. argue in Neural Message Passing on High Order Paths, aggregating only from immediate neighbors loses the specific sequence of nodes and edges that define molecular substructures or geometric features like bond angles.

To overcome this, researchers have begun replacing symmetric aggregators with sequence-aware architectures. In Recurrent Aggregators in Neural Algorithmic Reasoning, Xu et al. demonstrate that using an LSTM as a neighborhood aggregator allows models to align more effectively with classical algorithms that operate on ordered data. Similarly, Huang et al. propose PG-GNN in Going Deeper into Permutation-Sensitive Graph Neural Networks, which uses RNNs to encode neighbor arrangements. This shift allows the model to detect local cliques and cycles that are indistinguishable to the standard 1-Weisfeiler Lehman (1-WL) test.

Even when neighbor order isn't naturally present, it can be learned. Chatzianastasis et al. introduce GOAT in Graph Ordering Attention Networks, which uses an attention mechanism to sort neighbors into a meaningful sequence before processing them with a bidirectional LSTM. This approach captures synergistic interactions between neighbors that permutation-invariant functions typically ignore.

Paths as Semantic Chains

Beyond local neighborhoods, the "sequential" perspective is most powerful when applied to multi-hop paths. In Knowledge Graphs (KGs), the meaning of a connection between two entities is often defined by the specific sequence of relations that link them.

Yin et al. demonstrate in Recurrent One-Hop Predictions for Reasoning over Knowledge Graphs that treating relations as sequential inputs to an RNN allows the model to update a hidden state representing the path's cumulative semantics. This is echoed by Wang et al. in Explainable Reasoning over Knowledge Graphs for Recommendation, where the Knowledge-aware Path Recurrent Network (KPRN) uses LSTMs to model the compositional logic of paths connecting users to items.

This sequential framing enables models to handle complex reasoning tasks:

Scaling Sequential Reasoning

While RNNs are the traditional tool for sequences, recent work has explored more efficient ways to scan graph structures. Choi et al. introduce SpoT-Mamba in SpoT-Mamba: Learning Long-Range Dependency on Spatio-Temporal Graphs with Selective State Spaces, leveraging selective state space models to scan graph walk sequences. This approach preserves the sequential order of traversals (like depth-first searches) without the heavy computational cost of the positional encodings required by Transformers.

Furthermore, the sequential view allows for better handling of sparse or dynamic data. Mei et al. argue in An Adaptive Logical Rule Embedding Model for Inductive Reasoning over Temporal Knowledge Graphs that by encoding historical interaction sequences as paths, models can prioritize the sequence of actions over specific entity identities. This enables "zero-shot" reasoning, where the model can predict relationships for entirely new entities based on the logical patterns it has learned from previous sequences.

By treating the graph not just as a static set of connections, but as a collection of traversable sequences, these models bridge the gap between structural connectivity and logical reasoning.

Key Foundational Work

Neural networks for relational learning: an experimental comparison (2011) — 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_relational_sequence_modeling_99fdcf07,
  title = {relational sequence modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relational-sequence-modeling/rdr_99fdcf0770ee4423840e16fd2e1eb214},
  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_relational_sequence_modeling_99fdcf07_v1,
  title = {relational sequence modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relational-sequence-modeling/rdr_99fdcf0770ee4423840e16fd2e1eb214/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