Streaming Motif Counts for Expressive, Inductive Temporal Graph Models

Models that learn from streams of timestamped interactions, such as payments, comments, or trades, update each node's internal state from the messages it receives. These messages are built only from the two endpoints of each event. Such models inherit a known blind spot of standard graph neural networks: they cannot tell whether a node's partners also talk to each other. Two disjoint triangles and a single hexagon look the same to them, and so does a closed trading ring versus an open chain. The best-known fix for temporal models gives every node a learned identity vector. That breaks the symmetry, but the model can no longer generalize to nodes it has never seen, and those unseen nodes are exactly where the strongest temporal benchmark reports neural models failing.

We propose a cheaper and inductive alternative. At the moment each event arrives, we count how many recent common partners its two endpoints share, weighted by how recently each partner was seen. We attach this count to the event message before a non-dissipative continuous-time model consumes it. The counting runs on the full stream at roughly the cost of the neighbor lookup these models already perform. Because of that, we can afford to prune most edges before the expensive neural model runs while keeping the structural signal that pruning would otherwise destroy. The proposal ties four concerns into one testable system. The 1-WL limit is the deficiency it fixes. Large streams are the regime it must run in. Edge pruning is the efficiency lever whose damage it should undo. Feature-rank collapse of node states is the diagnostic that tells us whether the extra signal actually survives inside the model.

Core Claim

How Powerful are Graph Neural Networks? showed that neighbor-aggregating networks are exactly as discriminative as 1-WL color refinement, an iterative procedure that recolors each node from the multiset of its neighbors' colors. On the equivalence between graph isomorphism testing and function approximation with GNNs showed that failing to separate two graphs means failing to approximate any target that differs on them. Breaking the Limits of Message Passing Graph Neural Networks gave the canonical failure: two triangles versus one hexagon. These results motivate the proposal.

In continuous time, Long Range Propagation on Continuous-Time Dynamic Graphs introduced CTAN. CTAN evolves node states with anti-symmetric differential equations, whose weight matrices satisfy $W=-W^T$, so signals neither fade nor explode over long event chains. Its messages are still pairwise and local. Enhancing the Expressivity of Temporal Graph Networks through Source-Target Identification (TGNv2) proved that permutation-invariant temporal messages cannot even represent moving averages, and fixed this with node identity vectors at the cost of inductivity.

Our claim has three parts. First, a time-decayed count of shared recent partners, maintained online per event, separates event streams that CTAN and TGN without identities provably cannot separate, and it does so without node identities. Second, it can be maintained at $O(k)$ cost per event, where $k$ is the size of the per-node recent-neighbor buffer these models already keep. Third, computing it on the unpruned stream and feeding it to a model trained on a curvature-pruned stream recovers most of the accuracy pruning loses.

For an event between $u$ and $v$ at time $t$, the count is

$$ c_{uv}(t) = \sum_{w \in B_u(t)\cap B_v(t)} e^{-(t-t_{uw})/\tau}\, e^{-(t-t_{vw})/\tau}, $$

where $B_u(t)$ is the set of $u$'s last $k$ interaction partners before $t$, $t_{uw}$ is the most recent interaction time between $u$ and $w$, and $\tau$ is a decay scale. We also keep directed variants (cyclic versus transitive closure) and a recurrence term counting prior $u$–$v$ events. Each is a small number of scalars appended to the message.

Research Program

The theoretical part has two steps. We first state and prove a proposition in the spirit of the unfolding-tree argument of Weisfeiler-Lehman goes Dynamic. That paper defined dynamic 1-WL on snapshot sequences, proved snapshot-encoder-plus-RNN models universal for it, and noted that full node separation can require $2N-1$ layers. The proposition says the following. Take two event streams built by interleaving the edges of two triangles versus a hexagon, with identical per-node timestamps and degrees. Every node then has identical temporal unfolding trees, so any memory model whose messages are permutation-invariant functions of endpoint states, time gaps, and edge features (TGN, JODIE, CTAN) assigns them identical states. The augmented messages separate them after one closing event.

We then characterize what the decayed counts cannot capture, for instance longer chordless temporal cycles. This keeps the expressivity claim bounded and honest rather than "beyond 3-WL" in the sense of Weisfeiler and Lehman Go Topological.

The system part builds a streaming counter on top of the recent-neighbor buffers used by TGN-style samplers. It intersects the two endpoint buffers with a hash set at arrival time, writes the counts into the event message, and plugs them into both CTAN and TGN. The counter is decoupled from training: it is a single pass over the full event log. That makes it compatible with sparsification. We run TRicci, which ranks temporal edges by Forman-Ricci curvature with a recency kernel and drops up to 80% of them, to decide which events the neural model sees. The counts, however, still come from the unpruned stream.

The diagnostic part brings over-smoothing measurement into the streaming setting. Are we measuring oversmoothing in graph neural networks correctly? showed that Dirichlet energy misses collapse in trained networks, while effective rank (the entropy of normalized singular values of the feature matrix) tracks accuracy with average Pearson correlation 0.91 on static graphs. We compute effective rank of the node-memory matrix at regular points along the stream. The question is whether memories of structurally different nodes drift toward a low-rank subspace over long horizons, and whether the counts slow that drift. We treat rank only as a necessary condition: the same paper warns that random noise has maximal rank and no signal. A rank increase therefore counts only if it co-occurs with accuracy gains.

Baselines

The naive reference points are the non-learning heuristics in Temporal Graph Benchmark for Machine Learning on Temporal Graphs: Moving Average and Persistent Forecasting for node affinity, and EdgeBank for link prediction. TGB reports that these heuristics often beat neural models. On tgbn-reddit, Moving Average reaches NDCG@10 of 0.559 against 0.315 for TGN. Beating these is a minimum requirement. We use the official TGB splits, negatives, and streaming protocol.

The strongest expressive competitor is TGNv2. On tgbn-trade it reports NDCG@10 of 0.735, against 0.374 for TGN. It is the strongest competitor because it attacks the same permutation-invariance limit with a different tool. We rerun it with its published configuration and give it the same hyperparameter search budget and GPU hours as our model. "Beating it" has two parts: matching it within noise on transductive tgbn-* tasks, and clearly exceeding it on events whose endpoints first appear in the test period. For link prediction, the strongest number in the file is NAT's MRR of 0.749 on tgbl-wiki, reported by TGB. For CTAN on TGB tasks, and for any method on tgbn-token, no reported result was found on Lacuna, so we will produce those numbers ourselves.

The direct parent baseline is CTAN without counts, run with identical buffers, solver, and step size. This isolates the key ingredient. The decisive ablations are four:

  • counts replaced by degree-only features of the same dimensionality;
  • counts without time decay;
  • counts computed on the pruned rather than the full stream;
  • random node features as an inductive symmetry breaker.

For sparsification, the reference is TRicci itself. On its 12 datasets it retains 97.7% of full-graph ROC-AUC at 80% pruning, versus 89.4% for the strongest prior pruner, TEDDY. Beating it means retaining more than 97.7% at the same pruning budget and comparable runtime.

Why not just…?

Why not just give nodes identity vectors, as TGNv2 does? Identities solve the transductive problem well, as the 0.735 on tgbn-trade shows, and we expect them to remain competitive there. Their weakness is structural. Embeddings for nodes never seen in training are untrained, and TGB's surprise-index analysis shows that unseen edges are where neural models collapse. Our experiments split every test set by whether endpoints were seen during training. If TGNv2 matches us on the unseen split as well, the inductivity argument fails and we will report that. We also test the combination of identities and counts, since the two are not mutually exclusive.

Why not just lift snapshots to simplicial complexes? Message Passing Simplicial Networks (MPSNs) are strictly more expressive than 1-WL, but clique lifting grows combinatorially on dense graphs. It also assumes a fixed complex, while our setting has triangles forming and dissolving between events. Binning a 72-million-edge stream into snapshots would also discard the continuous timing that CTAN exploits. We will run an MPSN on discretized versions of the synthetic tasks and of tgbl-wiki. There we can measure whether its higher expressivity buys accuracy beyond the counts, and how much it costs per event.

Why not just precompute static triangle counts or other structural encodings once? Precomputation is what decoupled scaling methods do. The file notes that edge additions invalidate such cached features. A static count also mixes in future edges, which leaks information in a forecasting protocol. The stale-count ablation, with counts computed on the training-period graph and frozen, directly measures what online maintenance buys.

Why not just use the heuristics, since they already win? This is a real threat on affinity tasks dominated by repetition. We do not claim to beat Moving Average everywhere. The test is whether the counts close the gap on datasets where heuristics win and widen the lead where structure matters. We report results per dataset rather than averaged.

Proposed Experiments and Decisive Checks

The first check is synthetic and should be clean. We use the triangle-versus-hexagon stream family, a directed variant contrasting cyclic and transitive closure, and the synthetic dynamic 1-WL dataset from Beddar-Wiesing et al., on which a GIN-based snapshot model reaches 100% accuracy. CTAN and TGN should sit at chance on our families and the augmented models near 100%. We also run T-PathGraph to confirm that the added features do not hurt CTAN's long-range propagation up to path length 20.

The second check covers real streams: tgbl-wiki, tgbl-review (high surprise), tgbl-coin, and tgbl-comment for link prediction by mean reciprocal rank, and tgbn-trade, tgbn-genre, tgbn-reddit, and tgbn-token for affinity by NDCG@10. Each is split into seen and unseen endpoints. We report wall-clock throughput and peak memory, and verify that counting adds at most a small constant factor over the neighbor lookup on tgbn-token.

The third check is the pruning test on the GraphPulse token networks and the three TGB sets used by TRicci. We compare TRicci alone against TRicci with full-stream counts across pruning budgets of 50–90%. The decisive outcome is whether retention rises above 97.7% at 80% pruning while runtime savings stay near the reported 55.94%.

The fourth check tracks effective rank of node memories along each stream, in the style of Zhang et al. We correlate it with rolling accuracy. The question is whether models without counts lose rank over long horizons and whether that loss predicts their accuracy decay. A negative result here would still be informative: it would show that streaming collapse is not the operative failure and that the gains come purely from separability.

The proposal fails cleanly in either of two cases: the synthetic separation does not transfer to any real dataset beyond the degree-feature ablation, or TGNv2 matches it on unseen endpoints.