  Temporal graph networks (TGNs) have gained prominence as models for embedding
dynamic interactions, but little is known about their theoretical
underpinnings. We establish fundamental results about the representational
power and limits of the two main categories of TGNs: those that aggregate
temporal walks (WA-TGNs), and those that augment local message passing with
recurrent memory modules (MP-TGNs). Specifically, novel constructions reveal
the inadequacy of MP-TGNs and WA-TGNs, proving that neither category subsumes
the other. We extend the 1-WL (Weisfeiler-Leman) test to temporal graphs, and
show that the most powerful MP-TGNs should use injective updates, as in this
case they become as expressive as the temporal WL. Also, we show that
sufficiently deep MP-TGNs cannot benefit from memory, and MP/WA-TGNs fail to
compute graph properties such as girth.
  These theoretical insights lead us to PINT -- a novel architecture that
leverages injective temporal message passing and relative positional features.
Importantly, PINT is provably more expressive than both MP-TGNs and WA-TGNs.
PINT significantly outperforms existing TGNs on several real-world benchmarks.
