Traditional graph representation learning treats a node’s neighborhood as an unordered set of neighbors. While effective for static structures, this approach discards the "story" of how a network evolved. In dynamic systems—ranging from social interactions to program execution—the sequence in which edges form is often more informative than the final connectivity. Recent research suggests that by linearizing neighborhoods into ordered sequences and prioritizing temporal dynamics over spatial structure, models can achieve significantly higher expressivity and predictive power.
From Sets to Sequences
In a static Graph Neural Network (GNN), a node aggregates information from its neighbors simultaneously. However, Draief et al. et al. argue in KONG: Kernels for ordered-neighborhood graphs that representing neighborhoods as ordered sequences based on edge timestamps captures structural evolution that is otherwise lost. By treating these neighborhoods as strings, the authors can apply sequence-based kernels to classify graphs more accurately.
This shift from sets to sequences allows models to distinguish between different causal flows. For instance, Ma et al. et al. demonstrate in Streaming Graph Neural Networks that capturing the specific chronological order and precise time intervals of interactions allows models to prioritize recent events, which are often more representative of a node's current state. Similarly, Zhao et al. et al. find that in temporal knowledge graphs, the chronological sequence of events involving an entity provides more predictive value than its static structural neighborhood, especially when reasoning about new entities with no prior history.
The Building Blocks of Temporal Logic
If static graphs are built from triangles and cliques, temporal graphs are built from temporal motifs: small, recurring patterns of timestamped edges. Paranjape et al. et al. introduced $\delta$-temporal motifs in Motifs in Temporal Networks, defining them as sequences of edges that must occur within a specific time window.
These motifs serve as "temporal signatures." For example:
- Group Dynamics: Lee and Shin extend this to hypergraphs, showing that the relative order of group interactions reveals hidden dynamics in communication networks.
- Information Flow: Kriege et al. et al. use temporal graphlets to classify how diseases or information disseminate through evolving networks.
- Feature Learning: Tu et al. et al. propose gl2vec, which identifies sequences of edges within temporal windows to learn representations for entire directed networks.
The Time-Then-Graph Architecture
A key architectural insight emerging from this field is the hierarchy of information integration. Wang and Chen argue in Calibrate and Boost Logical Expressiveness of GNN Over Multi-Relational and Temporal Graphs that architectures processing temporal dynamics before spatial graph structure exhibit higher logical expressiveness than those that process them simultaneously.
This "time-then-graph" approach is central to the EvoBrain framework developed by Kotoge et al. et al. By prioritizing temporal evolution, the model avoids the premature compression of complex time-varying signals, such as those found in EEG data. This sequential priority allows the model to distinguish between distinct trajectories of brain activity, leading to state-of-the-art performance in seizure detection.
Execution-Order Message Passing
The intuition of ordered neighborhoods extends beyond physical time to logical time, such as program execution. In Smart Contract Vulnerability Detection using Graph Neural Network, Zhuang et al. et al. propose Temporal Message Propagation. Instead of standard graph convolutions, they propagate messages along edges in the exact sequence they occur during code execution.
As further detailed by Liu et al. et al., this execution-order-aware passing captures dynamic state changes and data dependencies that static analysis misses. By respecting the order of operations, the model can identify vulnerabilities like reentrancy, where the specific sequence of calls determines whether a contract is exploitable.
Why It Works
The success of these methods stems from the fact that temporal order is a strong proxy for causality. Whether it is the flow of influence in a social network (Heeg and Scholtes) or the evolution of subgraphs in a contrastive learning task (Chen et al.), explicitly incorporating edge timestamps and sequence order provides a more robust foundation for representation. By treating the neighborhood as a chronicle rather than a collection, these models capture the underlying logic of the system's evolution.
Key Foundational Work
KONG: Kernels for ordered-neighborhood graphs (2018) — contributed 3 concept elements to this direction.
Motifs in Temporal Networks (2016) — contributed 1 concept elements to this direction.