Technical Summary: Temporal Motif Signatures for Temporal Graph Neural Networks

Problem Statement

Real-world temporal interaction streams (e.g., social communications, financial transfers, online reviews) contain predictive structure within short-horizon motif patterns, such as repetition, reciprocity, star diversity, and triadic flow. While modern Temporal Graph Neural Networks (TGNNs) are expressive sequence models capable of theoretically extracting any function of a temporal stream, their inductive biases and limited training budgets often prevent them from capturing specific, short-horizon structural regularities. These regularities are frequently straightforward to compute analytically but are critical for downstream tasks. The paper addresses the gap between what standard TGNNs learn and the explicit short-horizon statistics that characterize temporal streams, asking whether a principled, architecture-agnostic augmentation can bridge this residual gap.

Methodology

1. Empirical Diagnostics and Signature Identification

The authors first analyze per-candidate, past-window motif counts across a diverse set of 13 real and synthetic temporal datasets (including MOOC, Bitcoin Alpha/OTC, and TGB benchmarks). They identify that motif activity organizes consistently along three scale-stable axes:

• A1 (Dyadic Recency/Reciprocity): Captures the timing and frequency of direct interactions between a candidate pair $(u, v)$.
• A2 (Star Diversity): Measures the diversity of neighbors interacting with $u$ or $v$ within a time window (e.g., the number of distinct items a student has interacted with).
• A3 (Triadic Flow): Captures the flow of interactions through third parties bridging $u$ and $v$ (e.g., common neighbors).

2. The Motif Feature Map $h(u, v, t)$

Based on these axes, the authors design a compact, 13-coordinate, candidate-local motif feature map, $h(u, v, t) \in \mathbb{R}^{13}$. Key design constraints include:

• Leakage Safety: Features are computed strictly from the past window $W_{t}^{past}(\Delta) = \{i : t - \Delta \le t_i < t\}$, ensuring no future information leaks into the candidate representation.
• Fixed Dimension: The 13 features are concatenated via a learnable linear embedding matrix $M$ into any static or temporal encoder without architectural changes.
• Sub-families: The 13 coordinates correspond to the three axes:
  • A1 (5 features): Counts of $u \to v$ and $v \to u$ events, paired events, burstiness, and normalized time since the last reciprocal event.
  • A2 (4 features): Sizes of distinct neighbor sets ($N_{u}^{out}, N_{u}^{in}, N_{v}^{out}, N_{v}^{in}$) within the window, capped to handle hubs.
  • A3 (4 features): Sizes of directed cross-wedge and bi-wedge intersections between the neighbor sets of $u$ and $v$.
• Normalization: Heavy-tailed count coordinates undergo a $\log_{10}(1+x)$ transform to ensure comparability.

3. Theoretical Placement (Temporal Weisfeiler-Leman)

The paper establishes a theoretical bound for standard temporal message-passing GNNs (MP-GNNs). Under a common edge-scoring abstraction, these models are bounded by the first level of a candidate-anchored temporal Weisfeiler-Leman (WL) hierarchy (temporal-1-WL).

• The authors prove that there exist anchored temporal streams (e.g., a $C_6$ cycle vs. two disjoint triangles $2K_3$) that temporal-1-WL cannot distinguish (collapsing them to the same color), yet the motif feature map $h$ distinguishes them perfectly.
• This places the motif augmentation strictly above the expressive power of standard temporal MP-GNNs, acting as a "witness" that breaks the WL bottleneck.

Key Contributions

1. Diagnostics (Section 4): The paper articulates that per-candidate motif counts organize temporal streams along three dominant, scale-stable axes (A1, A2, A3). These per-dataset signatures predict where motif augmentation will yield the largest performance gains.
2. Temporal Expressivity (Section 6): The authors provide a theoretical placement of standard temporal MP-GNNs within a candidate-anchored temporal-WL hierarchy. They exhibit a specific pair of streams where motif features distinguish candidates that temporal-1-WL collapses, demonstrating that the augmentation lifts the model beyond the first level of this hierarchy.
3. Empirical Performance (Section 7): The paper demonstrates that motif augmentation consistently lifts performance across heterogeneous tasks (TGB link-property prediction, edge classification, and graph-level classification) when compared to strong TGNN baselines. The gain is interpretable: it is largest where the baseline fails to capture short-horizon structure (e.g., MOOC) and negligible where the baseline already captures the relevant structure.

Experimental Results

The framework was evaluated on:

• TGB Link-Property Prediction: Across five baselines (TPNet, HyperEvent, DyGFormer, TNCN, TGN) and three datasets (Wiki, Review, Coin).
  • Result: Motif augmentation lifted performance on all evaluated baseline-dataset pairs. The most significant gain was observed on DyGFormer for the tgbl-review-v2 dataset, where Mean Reciprocal Rank (MRR) increased from 0.224 to 0.413.
  • Observation: Gains were within one standard deviation of zero for baselines like TPNet on tgbl-coin-v2, consistent with those baselines already capturing the relevant short-horizon structure for that specific dataset.
• Edge Classification:
  • MOOC: A binary classification task predicting student drop-out. A vanilla GraphSAGE encoder achieved a PR-AUC of 0.0164. Adding the 4-feature star-count subset (A2) raised this to 0.1430, and the full 13-feature map achieved 0.1659.
  • Bitcoin Alpha/OTC: Trust classification tasks showed modest but consistent improvements (e.g., SAGE PR-AUC from 0.9282 to 0.9667 on Alpha).
• Graph-Level Classification: On synthetic temporal generators, motif augmentation improved accuracy significantly, notably lifting GAT from a collapsed 16.7% (majority class prediction) to 94.0% without architectural changes.

Ablation and Controls:

• Leave-one-out analysis confirmed that no single coordinate is uniformly redundant; different datasets rely on different axes (e.g., MOOC relies heavily on A2 star diversity, while Bitcoin Alpha relies on A1 reciprocity).
• Controls ruled out "extra capacity" as the source of gains (random features did not replicate the lift) and confirmed that the gain is not merely a proxy for simple node activity counts.

Significance and Claims

The paper claims that temporal motif signatures provide a compact, interpretable, and architecture-agnostic method to inject short-horizon structural regularities into TGNNs.

• Predictive Power: The per-dataset signature along the A1/A2/A3 axes serves as a diagnostic tool to predict where augmentation will be most beneficial.
• Theoretical Grounding: By placing the augmentation relative to the temporal-WL hierarchy, the paper clarifies why standard TGNNs fail on certain tasks (they are bounded by temporal-1-WL) and how the augmentation overcomes this.
• Practical Utility: The method requires no changes to the underlying encoder architecture, only the concatenation of a pre-computed feature vector, making it easily deployable on existing pipelines.

The authors maintain a modest stance, noting that the window radius $\Delta$ is a sensitive hyperparameter and that in sparse streams where triadic flow is negligible, the augmentation reduces to a lower-dimensional subspace with correspondingly smaller gains. The framework is presented as a principled way to expose specific structural signals that vanilla TGNNs often fail to expose to their edge scorers.