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:
- Logical Flow: Michel et al. show in Path Neural Networks: Expressive and Accurate Graph Neural Networks that encoding paths with LSTMs creates an injective mapping that preserves structural information, outperforming even the 3-WL test on certain tasks.
- Numerical Reasoning: In CHAINSFORMER: Numerical Reasoning on Knowledge Graphs from a Chain Perspective, Zhao et al. treat relational paths as structured chains rather than global neighborhoods, allowing Transformers to better capture multi-hop dependencies for predicting attributes like dates or populations.
- Commonsense Reasoning: Lin et al. utilize RNNs in KagNet to capture the sequential dependencies of relations in reasoning chains, grounding language models in symbolic knowledge.
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.