Provably expressive temporal graph networks
Authors: Amauri H Souza
Diego Mesquita
Samuel Kaski
Vikas K Garg
Venue: NeurIPS 2022 Accept (2022)
Keywords: graph neural networks
temporal graphs
link prediction

Abstract: 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.

Provably expressive temporal graph networks
Amauri H. Souza', Diego Mesquita?, Samuel Kaski Vikas Garg
Aalto University Getulio Vargas Foundation UUniversity of Manchester YYaiYai Ltd famauri.. souza, samuel kaski) diego. wwwpoomteeuuuug...... br, vgargocsail. edu
Abstract
Temporal graph networks (TGNs) have gained prominence models for embed- ding 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. extend the 1-WL (Weisfeiler-Lemmn
test to temporal graphs, and show that the most powerful MP-TGNs should use injective updates, as in this case they become as expressive 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.
Introduction
Graph neural networks (GNNs)
36 39 have recently led breakthroughs in many applica-
by resorting to message passing between neighboring nodes in input graphs. While message passing imposes important inductive bias. does not account for the dynamic nature of interactions in time-evolving graphs arising from many real-world domains such as social networks several scenarios, these temporal graphs are only given as sequence have emerged as
tions 7 28 3
and bioinformatics [16 40
of timestamped events. Recently, temporal graph nets (TGNs) [I6] 27 32
38 42
prominent learning framework for temporal graphs and have become particularly popular due their outstanding predictive performance. Aiming at capturing meaningful structural and temporal patterns, time encoders [15]
TGNs combine a variety of building blocks, such as self-attention
33
recurrent models 5 13
and message passing [10
Unraveling the learning capabilities of (temporal) graph networks is imperative understanding their strengths and pitfalls, and designing better, more nuanced models that are both theoretically well-grounded and practically efficacious. For instance, the enhanced expressivity of higher-order GNNs has roots the inadequacy of standard message-passing GNNs to separate graphs that are indistinguishable by the Weisfeiler-Leman isomorphism test, known 1-WL test color refinement
algorithm [21 22 29 37 43 Similarly, many other notable advances on GNNs were made possible
by untangling their ability generalize O 35), extrapolate 45 compute graph properties 4 6
9
and express Boolean classifiers MI by uncovering their connections to distributed algorithms
graph kernels [ dynamic programming 4i diffusion processes B. graphical models
and combinatorial optimization [ and by analyzing their discriminative power 220 23 In stark contrast, the theoretical foundations of TGNs remain largely unexplored. For instance, unresolved questions include: How does the expressive power of existing TGNs compare? When do TGNs fail? Can we improve the expressiveness of TGNs? What are the limits on the power of TGNs?
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Overview of the theoretical results
PINT
Relationship between CTDGs and DTDGs
Prop.
Injective
MP-TGNs
Injective MP-IGNs ł MP-TGNs
Prop. 2
Sufficiently deep MP-TGNs do not need memory
Prop. 3
TGNN
SOTA MP-TGNs Injective MP-IGNs
Prop.
MP-TGNs WA-TGNs and WA-TGNs MP-TGNs
Prop.
Injective MP-IGNs _ temporal- WL test
Prop.
MP-TGNsCAWs cannol recognize graph properties
Prop.
Constructing injective temporal MP
Prop.
Open problems
PINT (ours) > both MP-TGNs and WA-TGNs
Prop.
Limitations of PINT
Prop. 10
Figure 1: Schematic diagram and summary of our contributions.
We establish series of results address these fundamental questions. We begin by showing that discrete-time dynamic graphs (DTDGs)) can always be converted to continuous-time analogues (CTDGs) without loss of information, so we can focus on analyzing the ability of TGNs to distinguish nodes/links of CTDGs. We consider general framework for peessage-passingg TGNs (MP-TGNs) 2 that subsumes a wide variety of methods [c.g.. 16 32 12 We prove that equipping MP-TGNs with injective aggregation and update functions leads to the class of most expressive anonymous MP-TGNs (i.e., those that do not leverage node ids). Extending the color-refinement algorithm to temporal settings, we show that these most powerful MP-TGNs are expressive the temporal WL method. Notably, existing MP-TGNs do not enforce injectivity. We also delineate the role of memory in MP-TGNs: nodes in network with only a few layers of message passing fail to aggregate information from a sufficiently wide receptive field (i.c., from distant nodes), so memory serves to offset this highly local view with additional global information. In contrast, sufficiently deep architectures obviate the need for memory modules.
Different from MP-TGNs, wglk-aggrgg TGNs (WA-TGNs) such as CAW 3S obtain represen- tations from anonymized temporal walks. We provide constructions that expose shortcomings of each framework, establishing that WA-TGNs can distinguish links cases where MP-TGNs fail and vice-versa. Consequently, neither class is more expressive than the other. Additionally, MP-TGNs and CAWs cannot decide temporal graph properties such as diameter, girth, or number of cycles. Strikingly, our analysis unravels the subtle relationship between the walk computations in CAWs and the MP steps in MP-TGNs.
show that
Equipped with these theoretical insights, we propose PINT (short for position-encoding injective temporal graph ner), founded and WA-TGNs. Like the most expressive MP-TGNs, PINT defines injective message passing and update steps. PINT also augments memory states with novel relative positional features, and these features can replicate all the discriminative benefits available to WA-TGNs. Interestingly, the time complexity of computing our positional features is less severe than the sampling overhead in CAW. thus PINT can often be trained faster than CAW. Importantly, we establish that PINT is provably more expressive than CAW as well MP-TGNs.
temporal layer that leverages the strengths of both TP-TGNs
Our contributions are three-fold:
rigorous theoretical foundation for TGNs laid elucidating the role of memory, benefits of injective message passing, limits of existing TGN models, temporal extension of the I-WL test and its implications, impossibility results about temporal graph properties, and the relationship between main classes of TGNs- - as summarized in Figure
explicit injective temporal functions are introduced, and a novel method for temporal graphs is proposed that is provably more expressive than state-of-the-an TGNs; extensive empirical investigations underscore practical benefits of this work. The proposed method is either competitive or significantly better than existing models on several real benchmarks for dynamic link prediction, transductive as well as inductive settings.

---

2
Preliminaries
We denote a static graph G as a tuple W. E),, where V = (1, n denotes the set of nodes and E C V V the set of edges. Each node u E V has feature vector z,, E X and each edge (u, v) E E has a feature vector Eue E E, where X' and & are countable sets of features.
Dynamic graphs can be roughly split according to their discrete- or continuous-ting nature [14]. discrete-time dynamic graph (DTDG) is of a sequence of graph snapshots (G,, G.....) usually sampled at regular intervals, each snapshot being a static graph G, = (V,, Er, X2,
contimuous-time dynamic graph (CTDG) evolves with node- and edge-level events, such as addition and deletion. We represent CTDG as sequence of time-stamped muulti-graphs (G(to), G(t)).....) such that Eg < fx+11 and G(fx+1) results from updating G(fx) with all events time fg++1 We assume no event occurs between Eg and fR+11 We denote an interaction (i.e., edge addition event) between nodes u and u time as a tuple (u, v, associated with a feature vector Eue (t). Unless otherwise stated, interactions correspond to undirected edges, i.e., (u, t) is a shorthand for (fu, t),
Noting that CTDGs allow for finer (irregular) temporal resolution, we formalize the intuition that DTDGs can be reduced to and thus analyzed as CTDGs, but the converse may need extra assumptions.
Proposition (Relationship between DTDG and CTDG), For any DTDG we can build CTDG with the same sets of node and edge features that contains the same information, iee, we can reconstruct the original DTDG from the converted CTDG. The converse holds the CTDG timestamps form subset of a uniformly spaced countable set.
38 42 we focus on CTDGs with edge addition events (see Appendix E for discussion on deletion). Thus, we can represent temporal graphs as sets G(t) [(u,, U22 tk f < t}. We also assume each distinct node e in (t) has an initial feature vector Z..
Following the usual practice 16
Message-passing temporal graph nets (MP-TGNss. Rossi al. 22 introduced MP-TGN general representation learning framework for temporal graphs. The goal is to encode the graph dynamics into node embeddings, capturing information that is relevant for the task at hand. To achieve this, MP-TGNs rely on three main ingredients: memory, aggregation, and update. Memory comprises a set of vectors that summarizes the history of each node, and is updated using recurrent model whenever an event occurs. The aggregation and update components resemble those in message- passing GNNs, where the embedding of each node refined using messages from its neighbors.
We define the temporal neighbohood of node v at time t as (N, t) = {(u, (t),,, t') |Eu, v, t') E (t)), i.e., the set of neighbor/featuuretimsstan triplets from all interactions of node prior to t. MP-TGNs compute the temporal representation h ( (t) of u at layer by recursively applying
((((()) = AGG (G (e- (C(())))())))
(u,e,t) EN(o,))
M (1) = (PDATE( (N. (1),(())))))
(2)
where H.B. denotes multisets, 1. - (1)= (t) is the state of at time f, and (G and (PDATE( are arbitrary parameterized functions. The memory block updates the states as events oceur. Let J(u, t) be the set of events involving e at time t. The state of v is updated due to J(e as
(t) = MEMAGG (t., s.,(t = MEMUPDATE(S (t),,,))))))
(f), t tv eva (t)] (e, u,,,,t) E {(e,t)
(3)
(4)
where s0) x. (initial node features), 8, ((+) denotes the updated state of due to events at time t, and t, denotes the time of the last update to v. MEMAGG combines information from simultancous events involving node and MEMUPDATE usually implements gated recurrent unit (GRU) [5]. Notably, some MP-TGNs do not use memory, or equivalently, they employ identity memory, i.c., st) I. for all t. We refer to Appendix A for further details.
Causal Anonymous Walks (CAWs). Wang et al. (8 proposed CAW as an approach for link prediction on temporal graphs. To predict if an event (u, u. occurs, CAW first obtains sets S, and S,
of temporal walks starting at nodes u and e at time 1. An (L 1)-length temporal walk is represented
as W (ww,, )), (222,2)).... .2)..... (Wr,, (r.),, with 4 > l2 > ... (r. and (w;-1, Wi, 4,) G(l) Vi > 1. Note that when predicting (u, v, 1), we have walks starting at time l L. Then, CAW anonymizes walks replacing each node with set ICAw (w; Su, = [g(w; Sw), (ww; S.)) of two
3

---

feature vectors. The E-th entry of (w; S.) stores how many times w appears at the ε-th position in a walk of S,, i.. g(w, S, = [[ E S. : (w, tx) WeH where We is E-th pair of W.
To encode walk W with respect to the sets S. and S., CAW applies ENC(W; Su, Sy) RNN (TcAw(w;; S.. S,)))l t,]][²)) a time encoder, and to- 11 Finally, CAW combines the embeddings of each walk in S, U S. using mean-pooling or self-attention to obtain the representation for the event (u, 0, 2,
where fi is a permutation-invarian function, f2 is
In practice, TGNs often rely on sampling schemes for computational reasons. However we are concerned with the expressiveness of TGNs, our analysis assumes complete structural information, i.e., Sy is the set of all temporal walks from u and MP-TGNs combine information from all neighbors.
3 The representational power and limits of TGNs
We now study the expressiveness of TGNs on node/edge-level prediction. We also establish connec- tions to variant of the WL test and show limits of specific TGN models. Proofs are in Appendix B
3.1 Distinguishing nodes with MP-TGNs
We analyze MP-TGNs w.n.t their ability to map different nodes to different locations in the embedding space. In particular, we say that L-layer MP-TGN distinguishes two nodes u, u of a temporal
graph at time t, if the last layer embeddings of u and v are different, i.e., ht ( (f) A It (t).
We can describe the MP computations of node v at time via its temporal computation tree (TCT) To (t). (t) has as its root and height equal to the number of MP-TGN layers L. We will keep the dependence on depth L implicit for notational simplicity. For each element (u, e.) E NN t) associated with we have a node, say i, in the next layer of the TCT linked to the root by an edge annotated with t"). The remaining TCT layers are built recursively using the same mechanism. We denote by d.. the (possibly many-to-one) operator that maps nodes in (t) back to nodes in (t), e.g., 4 = u. Each node in (t) has a state vector s, = $:g (t). To get the embedding of the root information is propagated bottom-up, i.e., starting from the leaves all the way up to the root each node aggregates the message from the layer below and updates its representation along the way. Whenever clear from context, we denote #2 simply as for cleaner notation.
We study the expressive power of MP-TGNs through the lens of functions on multisets adapted to temporal settings, i.e., comprising triplets of node states, edge features, and timestamps. Intuitively, injective functions 'preserve' the information as it is propagated, so should be essential for maximally expressive MP-TGNs. We formalize this idea in Lemma I and [Propssiion 2 via Definition
Definition 1 (Isomorphic TCTs), Two TCTs T!) and (t) at time I are isomorphic if there is a bijection f ((T)(()) (I) between the nodes of the trees such that the following holds: (u,,, t.) (t), = (f(u), t')),t') E (t))
V(u,v, I') E ((T=(()): : = (()ss (1) and Vu VV(T(()) s. = S and k., (()
Here, ku denotes the level (depth) of node in the tree. The root node has level 0, and for node with level kis the children of u have level ki + 1.
Lemma 1. If an MP-TGN Q with L layers distinguishes two nodes u, v of a dynamic gruph ((), then the L-depth TCTs (I) and T5 (() are not isomorphic.
For non-isomorphic TCTs, Proposition 2 shows that improving MP-TGNs with injective message passing layers suffices to achieve node distinguishability, extending results from static GNNs 4R]
Propusition 2 (MP-TGN) with injective message passing). If the L-depth TCTs of two nodes u, v of temporal graph (t) time are not isomorphic, then MP-TGN Q with L layers and injective aggregation and update functions at each layer is able to distinguish nodes u and v.
So far, we have considered TCTs with general memory modules, i.e., nodes are annotated with memory states. However, an important question remains: How does the expressive power of MP- TGNs change as a function of the memory? Naturally, different implementation of memory modules can determine whether the TCTs of two nodes are isomorphic or not. Thus, most expressive MP- TGNs should also employ injective memory aggregation/update. However, Propoostiooosiiiionn shows that adding GRU-based memory does not increase the expressiveness of suitably deep MP-TGNs.

---

(+(() 2 T,(()
Figure 2: Limitations of TGNs. [Left] Temporal graph with nodes u, v that TGN-AWTTAT cannot distinguish. Colors are node features, edge features are identical, and by > b2 > t1. [Center] TCTs of u and v are non-isomorphic. However, the attention layers of TGAT/TGN-Att compute weighted averages over same multiset of values, returning identical messages for and v. [Right] MP-TGNs fail to distinguish the events (2, v, ty) and (v, 2, (y) as TCTs of & and u are isomorphic. Meanwhile, CAW cannot separate (u, 2, (a) and (w', 2, la): the 3-depth TCTs of and u' are not isomorphic, but the temporal walks from u and u' have length 1, keeping CAW from capturing structural differences.
Proposition (The role of memory). Let O.M denote the class of MP-TGNs with recurrent memory and L layers. Similarly, we denote by Qr. the family of memoryless MP-TGNs with L layers. Let A be the temporal diameter of (() (see Definition B2). Then, holds that:
1. If L < A: 2,10) is strictly more powerful than 2r, in distinguishing nodes of G(t);
2. For any L Q1+a is at least as powerful as e in distinguishing nodes of G()..
The MP-TGN framework is rather general and subsumes many modern methods for temporal graphs [e.g..
16 32 42 We now analyze the theoretical limitations of two concrete instances MP-TGNs: TGAT
42 and TGN-Att (27. Remarkably, these models are among the best-performing MP-TGNs. Nonetheless, we can show that there are nodes of very simple temporal graphs that TGAT and TGN-Att cannot distinguish (see (eeuueegee 2). We formalize this in Prropositinn by establishing that there are cases in which TGNs with injective layers can succeed, but TGAT and TGN-Att cannot.
Proposition 4 (Limitations of TGAT/TGN-AIt, There exist temporal graphs containing nodes u, that have non-isomorphic TCTs, yet no TGAT nor TGN-Att with mean memory aggregator (i.e., using MEAN MEMAGG) can distinguish and v.
This limitation stems from the fact that the attention mechanism employed by TGAT and TGN-Att proportion invariant 22. The memory module of TGN-Att cannot counteract this limitation due to its mean-based aggregation scheme. We provide more details in Appendix B.6
3.2 Predicting temporal links
Models for dynamic graphs are usually trained and evaluated on temporal link prediction [8]. which consists in predicting whether event would occur at a given time. To predict an event between nodes u and v at f, MP-TGNs combine the node embeddings h (t) and 1n(z)()) (t), and push the resulting vector through an MLP. On the other hand, CAW is originally designed for link prediction tasks and directly computes edge embeddings, bypasssing the computation of node representations.
We can extend the notion of node distinguishability to edges/events. We say that a model distinguishes two synchronous events = (u, v, () and 7 (u', v', of a temporal graph it assigns different edge embeddings h, * h. for 7 and 7' Proposition 5) asserts that CAWs are not strictly more expressive than MP-TGNs, and vice-versa. Intuitively, CAW's advantage over MP-TGNs lies in its ability to exploit node identities and capture correlation between walks. However, CAW imposes temporal constraints on random walks, i.c. walks have timestamps in decreasing order, which can limit its ability to distinguish events. Figure Right) sketches constructions for Proposition 5)
Proposition (Limitations of MP-TGNs and CAW). There exist distinct synchronous events of temporal graph that CAW can distinguish but MP-TGNs with injective layers cannot, and vice-versu.
3.3 Connections with the WL test
The Peiifeiler-Leman test (1-WL) has been used as key tool to analyze the expressive power of GNNs. We now study the power of MP-TGNs under a temporally-extended version of 1-WL, and prove negative results regarding whether TGNs can recognize properties of temporal graphs.
Temporal WL test. We can extend the WL test for temporal settings a straightforward manner by exploiting the equivalence between temporal graphs and multi-graphs with tinestamped edges [24] In particular, the temporal variant of 1-WL assigns colors for all nodes in an input dynamic graph G(t) by applying the following iterative procedure:
5

---

Inirialization: The colors of all nodes in (t) are initialized using the initial node features: Yo e V(G(t), (v) = .,- If node features are not available, all nodes receive identical colors; Refinement: At step l, the colors of all nodes are refined using a hash (injective) function: for all v (()))) we apply cl+ = (cSH(c((v) (u) Cuo (t'), t') (u, e, t') E g(t) Termination: The test is carried out for two temporal graphs at time / in parallel and stops when the multisets of corresponding colors diverge, returning non-isomorphic. If the algorithm runs until the number of different colors stops increasing, the test is deemed inconclusive.
We note that the temporal WL test trivially reduces to the standard 1-WL test if all timestamps and edge features are identical. The resemblance between MP-TGNs and GNNs and their corresponding WL tests suggests that the power of MP-TGNs is bounded by the temporal WL test. Proposition conveys that MP-TGNs with injective layers are powerful as the temporal WL test.
Proposition 6. Assume finite spaces of initial node features X, edge features E. and timestamps T. Let the number of events of any temporal graph be bounded by a fixed constant. Then, there is an MP-TGN with suitable parameters using injective aggregatiion/pulate functions that outpuls different representations for two temporal graphs if and only if the temporal- WI. test outputs 'on-isomorphic'.
A natural consequence of the limited power of MP-TGNs is that even the most powerful MP-TGNs fail to distinguish relevant graph properties, and the same applies to CAWs (see Proposition 7).
Proposition 7. There exist non-isomorphic temporal graphs differing in properties such as diameter, girth, and total number of cycles, which cannot be differentiated by MP-TGNs and CAWs.
Figure 3) provides a construction for Proposition 7
The temporal graphs G(t) and gt( differ in diameter (oo vs. 3), girth (3 vs. 6). and number of cycles (2 vs. 1). By inspecting the TCTs, one can observe that, for any node in Gtt), there is a corresponding one isomorphic, e.g., Tu, (t)= = Tu (t) for t >> t3. As result, the multisets of node embeddings for these temporal graphs are identical.
4
G(O)
in g'()) whose TCTs
Figure 3: Examples of temporal graphs for which MP-TGNs cannot distinguish the diameter, girth, and number of cycles.
We provide more details and construction - where CAW fails to decide properties - in the Appendix.
4 Position-encoding injective temporal graph net
We now leverage insights from our analysis in Section 3 to build more powerful TGNs. First, we discuss how to build injective aggregation and update functions in the temporal setting. Second, propose an efficient scheme to compute positional features based on counts from TCTs. In addition, show that the proposed method, called position-encoding injective temporal graph net (PINT), is more powerful than both WA-TGNs and MP-TGNs in distinguishing events in temporal graphs.
Injective temporal aggregation. An important design principle in TGNs is to prioritize (give higher importance to) events based on recency 38 22
Proposition introduces an injective aggregation scheme that captures this principle using linearly exponential time decay.
Proposition 8 (Injective function on temporal neighborhood). Let X and be countable, and T countable and bounded. There exists a fffunction f and scalars a and 3 such that Σ, f(,,e)) -t, unique on any multiset M- = [ (2,, C4,t4) C X x TT with |M] < N, where N a constant.
Leveraging Proposition ajand the approximation capabilities of multi-layer perceptrons (MLPs), we propose -eciiiing injective temporal graph net (PINT). In particular, PINT computes the embedding of node e at time I. and layer E using the following message passing steps:
(t) = Σ
MLP(() deg
(h---10 (()
a- ((t-t')
(5)
A = (LP(() (N(--1)) 1 (() upd
(6)
where || denotes concatenation, (o) = (t), a and B are scalar
agg and MLP(()
and MLP(() upd denote the nonlinear transformations of the aggregation and update steps, respectively.
We note that to guarantee that the MI.ss PINT implement injective aggregation/updaate, we must further assume that the edge and node features (states) take values in finite support. In addition,

---

Compute (4) via
Temporal Graph
Injective Temporal MP
T T())
h
f2
22
cav
eau (fa)
eam (ts)
Our (t4)
time
Sult)
Fa
Menory
s.l()
(I)
Compute
(()
(9)
positional
features
22
Figure 5: PINT. Following the MP-TGN protocol, PINT updates memory states as events unroll. Meanwhile,
Eqs. IT) update positional features. To extract the embedding for node s, we build its TCT, annotate nodes with memory + positional features, and run (injective) MP.
we highlight that there may exist many other ways to achieve injective temporal MP - we have presented a solution that captures the 'recency' inductive bias of real-world temporal networks.
Relative positional features. To boost the power of PINT, we propose augmenting memory states with relative positional features. These features count how many temporal walks of given length exist between two nodes, or equivalently, how many times nodes appear at different levels of TCTss
Formally, let P be the d x d matrix obtained by padding (d -)-dimensional identity matrix with zeros on its top row and its rightmost column. Also, let " E Ná denote the positional feature vector of node j relative to u's TCT at time t. For each event (u, v, t), with and participating in other events at I, we recursively update the positional feature vectors as
D = {i}
Vite) Det = D (
Vi
[1,0 1 10,0,
...,
OJ 0J
i
i
(7) P (t)
Prija 1
(t)
Vi E D(0)
(10)
88)
if
(t Jou P Pr,f +
(2)
Vj V
(11)
where t to denote values "right after" t. The set V. keeps track of the nodes for which we need to update positional features when participates in an interaction. For simplicity, we have assumed that there are other events involving u or time I. Appendix provides equations for the general case where nodes can participate in multiple events at the same timestamp.
The value ri [k] (the k-th component of (t) (itt)) corresponds to how many different ways we can get from v to in k steps through temporal walks. Additionally, we provide in Lemma 2 an interpretation of relative positional features terms the so- called monotone TCTs (Detinition 2). In this regard. Figure 4 shows how the TCT of e evolves due to an event (u, U, () and provides intuition about the updates in Eqs. 10-11 1. The procedure amounts to appending the monotone TCT of u to the first level of the monotone TCT of v.
T Tt(tt)
T T((
T.
k
h
11
i
+
(0 (
The monotone TCT of a node u at time t, denoted by Tu (t), is the maximal subtree the TCT of u s.t. for any path p = (u, t1, u1, u2.u2.... from the root u to leaf nodes (t) time monotonically decreases, i.e., we have that 11 > t2
Definition 2.
Figure 4: The effect of (u, v, f) the monotone TCT Also, note how the positional features of node i, relative to can be incrementally updated.
Lemma 2. For any pair nodes i, u of a temporal graph G(I), the k-th component of the positional feature vector ( stores the number of times appears at the k-th layer of the monotone TCT of u.
Edge and node embeddings. To obtain the embedding h for an event 7 (u, v, f), an L-layer PINT computes embeddings for node u and v using L steps of temporal message passing. However, when computing the embedding 1 (1) of u, we concatenate node states (t) with the positional features (t) j-tu and (1) ド= for all node j in the L-hop temporal neighborhood of u. We apply the same procedure to obtain h (t), and then combine lof( and hb((t (t) using readout function.
7

---

Similarly, to compute representations for node-level prediction, for each node j in the L-hop neigh- borhood of u, we concatenate node states st( with features r- Then, we use our injective MP to combine the information stored in u and its neighboring nodes. Figure Sillustraaes the process.
Notably, Proposition 9 states that PINT is strictly more powerful than existing TGNs. In fact, the relative positional features mimic the discriminative power of WA-TGNs, while eliminate their temporal monotonicity constraints. Additionally, PINT can implement injective temporal message passing (either over states or states + positional features), akin to maximally-expreseee
MP-TGNs.
Proposition 9 (Expressiveness of PINT: link prediction). PINT (with relative positional features) is strictly more powerful than MP-TGNs and CAWs in distinguishing events in temporal graphs.
When does PINT fail? Naturally, whenever the TCTs (annotated with positional features) for the endpoints of two edges (u, u, () and (u', v', are pairwise isomorphic, PINT returns the same edge embedding and is not able to differentiate the events. Figure 6 shows an example in which this happens we assume that all node/edge features are identical. Due to graph symmetries, u and z occur the same number of times in each level of v's monotone TCT. Also, the sets of temporal walks starting at u and are identical we swap the labels of these nodes. Importantly, CAWs and MP-TGNs also fail here, as stated in Proposition 9
22
8
t
Figure 6: PINT cannot distinguish the events (u, v. La) and (v, ta)..
Proposition 10 (Limitations of PINT). There are synchronous events of temporal graphs that PINT cannot distingwish (as seen in Figure 6).
Implementation and computational cost. The online updates for PINT's positional features have complexity O (d | + d Similarly to CAW's sampling procedure, our online update is sequential process better done in CPUs. However, while CAW may require significant CPU- proportional to both the number of walks and their depth we only
GPU memory exchange communicate the positional features. We can also speed-up the training of PINT by pre-computing the positional features for each batch, avoiding redundant computations at each epoch. Apart from positional features, the computational cost of PINT is similar to that of AGN-Att. Following standard MP-TGN procedure, we control the branching factor of TCTs using neighborhood sampling.
Note that the positional features monotonically increase with time, which undesirable for practical generalization purposes. Since our theoretical results hold for any fixed t. this issue can be solved by dividing the positional features by a time-dependent normalization factor. Nonetheless, we have found that employing L normallizaiion leads to good empirical results for all evaluated datasets.
5 Experiments
We now assess the performance of PINT on several popular and large-scale benchmarks for TGNs. We run experiments using PyTorch e and code is available at www.giithu... www. httm//aatooMML/PII
Tasks and datasets. We evaluate PINT on dynamic link prediction, closely following the evaluation
setup employed by Rossi et al. 27 and Xu et al. 42 We use six popular benchmark datasets: Notably, UCI, Enron, and LastFM are non-attributed networks, i.c., they do not contain feature vectors associated with the events. Node features are absent in all datasets, thus following previous works we set them to vectors of zeros 27 42). Since Twitter is not publicly available, we follow the guidelines by Rossi et al. [2 to create our version. We provide more details regarding datasets in the supplementary material.
Reddit, Wikipedia, Twitter, UCI, Enron, and LastFM [6
B8
Jodie [T., DyRep 13 TGAT 42 TGN-Att (27]. and CAW 38 For completeness, we also report results using two static GNNs: GAT 34 and GraphSage 112] Since we adopt the same setup as TGN-Att, we use their table numbers for all baselines but CAW on Wikipedia and Reddit. The remaining results were obtained using the implementations and guidelines available from the official repositories. As ablation study, also include a version of PINT without relative positional features in the comparison. We provide detailed information about hyperparameters and the training of each model in the supplementary material.
Baselines. We compare PINT against five prominent TGNs:
Experimental setup. We follow Xu et al. 42 and use a 70%-15%-155 (train-val-test) temporal split for all datasets. We adopt average precision (AP) as the performance metric. We also analyze separately predictions involving only nodes seen during training (transductive), and those involving
8

---

Table 1: Average Precision (AP) results for link prediction. denote best-performing model (highest mean AP) in blue. In 5 out of 6 datasets, PINT achieves the highest AP in the transductive setting. For the inductive case, PINT outperforms previous MP-TGNs and competes with CAW. We also evaluate PINT w/ and w/o relative positional features. Adopting positional features Ieads to significant performance gains.
Model
Reddit
Wikipedia
Twitter
UCI
Enron
LastEM
GAT
97.33 0.2
94.73 0.2
GruphSAGE
97.65 + 0.2
93.56 0.3
Transductive
Jodie
97.11 0.3
94.62 0.5
98.23 101
86.73
T7.31
1
69.32
DyRep
97.98 + 0.1
94.59
0.2
98.48
54.60
3.1
77.68
1.6
69.24
TGAT
98.12 + 0.2
95.34 0.1
98.70 +.1
77.51
0.7
68.02 0.1
54.77 + 0.4
TGN-Att
98.70 = 0.1
98,46 0.1
98.00
80.40
1.00+10 1.4
79.91 1.3
80.69 - 0.2
CAW
98.39 1 0.1
98.63 0.1
1.01
92.16 0.1
92.09
0.7
81.29 1 0.1
PINT
(wdl
98.62 + .04
98.43 + .04
98.53 +
92.68 +
83.06 +.1
81.35 + 1.6
PINT
99.03 = 001
98.78 + 0.1
99.35 01
96.01 + 0.1
88.71 + 1.3
88.06 + 0.7
GAT
95.37 1 0.3
91.27 T. 0.4
GraphSAGE
96.27 1: 0.2
91.09 1 0.3
Inductive
Jodie
94.36 = 1.1
93.11 + 0.4
96.06 - 0.1
75.26 + 1.7
76.48 3.5
80.32 : 1.4
DyRep
95.68 + 0.2
92.05 + 0.3
0.2
50.96 + 1.9
66.97 3.8
82.03 = 0.6
TGAT
96.62 -: 0.3
93.99 1 0.3
96.33
70.54
56.76 1 0.9
TGN-Att
97.55 + 0.1
97.81
+ 0.1
95.76+0.1
74.70 +.99
78.96 0.5
84.66 0.1
CAW
97.81 1: 0.1
98.52
98.54
92.56 0.1.1
1.7 91.74
85.67
0.5
PINT (wdl pos. (eaat)
97.22 + 0.2
97.81 0.1
06.
90.25
+-25+00.
75.99
2.3
88.44
PINT
98.25 = .04
98.38 .04
98.20 .03
93.97
81.05 2.4
91.76 0.7
novel nodes (inductive).
We report mean and standard deviation of the AP over runs. For further We provide additional results in the supplementary material.
details, see Appendix D
Results. Table I shows that PINT is the best-performing method on five out of six datasets for the transductive setting. Notably, the performance gap between PINT and TGN-Att amounts to over 15% AP on UCI. The gap also relatively high compared to CAW on LastFM, Enron, and UCI; with CAW being the best model only on Enron. We also observe that many models achieve relatively high AP on the attributed networks (Reddit, Wikipedia, and Twitter). This aligns well with findings from (8) where TGN-Att was shown to have competitive performance against CAW on Wikipedia and Reddit. The performance of GAT and TGAT (static GNNs) on Reddit and Wikipedia reinforces the hypothesis that the edge features add significantly to the discriminative power. On the other hand, PINT and CAW, which leverage relative identities, show superior performance relative to other methods when only time and degree information is available, i.e., unattributed networks (UCI, Enron, and LastFM). Table I also shows the effect of using relative positional features. While including these features boosts PINT's performance systematically, our ablation study shows that PINT w/o positional features still outperforms other MP-TGNs on unattributed networks. In the inductive case, observe similar behavior: PINT is consistently the best MP-TGN, and is better than CAW on 3/6 datasets. Overall, PINT (w/ positional features) also yields the lowest standard deviations. This suggests that positional encodings might be useful inductive bias for TGNs.
compares the training times of PINT against other TGNs. For fairness, we use the same architecture (number of layers & neighbors) for all MP-
Time comparison. Figure 7
Wikipedia
UCI
Avp. time per opech log
TGNs: i.e., the best-performing PINT. For
6
CAW, we use the one that yielded results in
3
Table 1, As expected, TGAT is the fastest model. Note that the average time/epoch of PINT gets amortized since positional fea- tures are pre-comp Without these fea- tures, PINT's runtime closely matches TGN- Att. When trained for over epochs, PINT runs considerably faster than CAW. We pro- vide additional details and results the sup- plementary material.
2
25
50
100
150
200
25
50
100
150
200
Epochs
Epochs
MNT
PINT (udo (wdo-poo.)
TGAT
CAW
TON-AH
Time comparison: PINT versus TGNs log- scale). The cost of pre-computing positional features is quickly diluted as the number of epochs increases.
Figure

---

Table 2: Average precision results for TGN-Att relative positional features.
Transductive
Inductive
UCI
Enron
LasIFM
UCI
Enron
LastFM
TGN-AI
80.40 14
79.91 1.3
80.69 0.2
74.70 0.9
78.96 + 0.5
84.66 + 0.1
TON-AI+ + RPF
95.64
85.04 2.5
00.9
92.82 # 0.4
76,27 334
91.63 + 0.3
PINT
96.01 0.1
88.71
0.7
0.1
81.05
9.7
Incorporating relative positional features into MP-TGNs. We can use our relative positional features (RPF) to boost MP-TGNs, [Table showws the performance of TGN-Att with relative positional features on UCI, Enron, and M. Notably, TGN-Att receives a significant boost from our RPF. However, PINT still beats TGN-At+RPP on 5 out of 6 cases. The values for TGN-At++RPF reflect outcomes from 5 repetitions. We have used the same model selection procedure as TGN-Att Table 1, and incorporated d = 4-dimensional positional features
Dimensionality of relative positional features. We assess the performance of PINT as a func- tion of the dimension d of the relative positional features. Figure 8) shows the performance of
UCT
Enros
541
65
PINT for d E 4, 10, 15, 20} on UCI and Enron. We report mean and standard deviation of AP on test set obtained from five independent runs. In all experiments, we re-use the optimal hyper- parameters found with = Increasing the dimensionality of the positional features leads to performance gains on both datasets. Notably, we obtain a significant boost for Enron with d = 10: 92.69 + 0.09 AP in the transductive setting and 88.34 0.29 in the inductive case. Thus, PINT becomes the best-perforning model on Enron (transductive). On UCI, for d = 20, we obtain 96.36 + 0.07 and 94.77 + 0.12 (inductive).
64
101
-6- trnobattive
indective
10 15
10
13
Dius 60
Dans. 60
Figure 8: PINT: AP (mean and std) function of the dimensionality of the positional features.
Conclusion
We laid rigorous theoretical foundation for TGNs, including the role of memory modules, relation- ship between classes of TGNs, and failure cases for MP-TGNs. Together, our theoretical results shed light on the representational capabilities of TGNs, and connections with their static counterparts. We also introduced a novel TGN method, provably more expressive than the existing TGNs.
Key practical takeaways from this work: (a) temporal models should be designed to have injective update rules and to exploit both neighborhood and walk aggregation, and (b) deep architectures can likely be made more compute-friendue as the role of memory gets diminished with depth, provably.
Acknowledgments and Disclosure of Funding
This work was supported by the Academy of Finland (Flagship programme: Finnish Center for Artificial Intelligence FCAI and 341763), ELISE Network of Excellence Centres (EU Horizon:2020 grant agreement 951 847) and UKRI Turing AI World-Leading Researcher Fellowship, EP/W002973/1. We also acknowledge the computational resources provided by the Aalto Science-IT Project from Computer Science ITT AS and DM also would like to thank Jorge Perez, Jou-Hui Ho, and Hojin Kang for valuable discussions about TGNs, and the latter's 's input on preliminary version this work.
Societal and broader impact
Temporal graph networks have shown remarkable performance in relevant domains such social networks, e-commerce, and drug discovery. In this paper, we establish fundamental results that delineate the representational power of TGNs. We expect that our findings will help declutter the literature and serve as a seed for future developments. Moreover, our analysis culminates with PINT, a method that provably more powerful than the prior art and shows superior predictive performance on several benchmarks. We believe that PINT (and its underlying concepts) will help engineers and researchers build better recommendation engines, improving the quality of systems that permeate our lives. Also, we do not foresee any negative socictal impact stemming directly from this work.
10

---

References
[1] P. Barceló, E. V. Kostylev, M. Monet, J. Pérez, J. L. Reutter, and J.-P. Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations (ICLR), 2020.
[2] Q Cappart, Chételat, E. Khalil, Lodi, C. Morris, and Velickovie. Combinatorial optimization and reasoning with graph neural networks, In International Joint Conference on Artificial Intelligence (IJCAI), 2021.
[3] B. Chamberlain, J. Rowbottom, M. Gorinova, M. M. Bronstein, S. Webb, and E. Rossi, GRAND; graph neural diffusion. In International Conference Machine Learning (ICML), 2021.
[4] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning (ICML), 2020.
[5] K. Cho, B. van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Empirical Methods in Natural Language Processing (EMNLP), 2014.
[6] N. Dehmamy, A.-L. Barabási, and R. Yu. Understanding the representation power of graph neural networks in learning graph topology. In Advances in neural information processing systems (NeurIPS), 2019.
[7] A. Derrow-Pinion. J. She, D. Wong. O. Lange. T. Hester, L. Perez, M. Nunkesser, S. Lee. X. Guo, B. Wiltshire, W. Battaglia, V. Gupta, A. Li. Z. Xu, A. Gonzalz-Gozzaezz. Y. Li, and P. Velickovic. Eta prediction with graph neural networks google maps. Conference on Information and Knowledge Management (CIKM), 2021.
[8] S. S. Du, K. Hou, R. Salakhutdinov, B. Póczos, R. Wang, and K. Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Newral Information Processing Systems (NeurIPS), 2019.
[9] V. Garg, S. Jegelka, and T. Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning (ICML), 2020.
[10] Gilmer, S. S. Schoenholz. P. F. Riley, Vinyals, and G. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), 2017.
[11] M. Gori, G. Monfardini, and Scanselli. A new model for learning in graph domains. In IEEE International Joint Conference on Neural Networks (JCNN), 2005.
[12] W. Hamilton, Z. Ying. and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[13] S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural Computation, 983) 1997.
[14] S. Kazemi, R. Goel, K. Jain, I. Kobyzev, A. Sethi, P. Forsyth, and P. Poupart. Representation lcarning for dynamic graphs: A survey. Journal of Machine Learning Research, 21(70):1 73, 2020.
[15] S. Kazemi, R. Goel, Eghbali, J. Ramanan, J. Sahota, Thakur. Wu, Smyth, Poupart, and M. Brubaker. Time2vec: Learning a vector representation of time. ArXiv: 1907.0532/ 2019.
[16] S. Kumar, X. Zhang, and J. Leskovee. Predicting dynamic embedding trajectory in temporal interaction networks. In International Conference on Knowledge Discovery & Data Mining (KDD), 2019.
[17] R. Liao, R. Urtasun, and R. Zemel. A PAC-bayesian approach to generalization bounds for graph neural networks. In International Conference on Learning Representations (ICLR), 2021.
[18] D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. Journal of the American Society for Information Science and Technology, 1817):1019-100 1031, 2007.
[19] A. Loukas. What graph neural networks cannot learn: depth vs width. International Conference on Learning Representations (ICLR), 2020.
[20] A. Loukas. How hard is to distinguish graphs with graph neural networks? In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[21] H. Maron, H. Ben Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.

---

[22] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference Artificial Intelligence (AAAI), 2019.
[23] H. Nguyen and T. Machara. Graph homomorphism convolution. In International Conference on Machine Learning (ICMI.), 2020.
[24] F. Orsini, P. Frasconi, and L. D. Raedt. Graph invariant kernels. In International Joint Conference on Artificial Intelligence (ICCAI). 2015.
[25] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. Vetio, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer. Automatic differentiation in pytorch. In Advances in Neural Information Processing Systems (NeurIPS Workshop), 2017.
[26] J. Pérez, J. Marinković, and P. Barceló. On the turing completeness of modemn neural network architectures. In International Conference Learning Representations (ICLR). 2019.
[27] E. Rossi, B. Chamberlain, F. Frasca, D. Eynard, E. Monti, and M. Bronstein. Temporal graph networks for deep learning on dynamic graphs. In ICML 2020 Workshop on Graph Representation Learning, 2020.
[28] A. Gonzaez-Gonzalez, J. Godwin, T. Pfaff, R. Ying, J. Leskovec, and P. Battaglia. Learning to simulate complex physics with graph networks. In International Conference on Machine Learning (ICML), 2020.
[29] R. Sato, M. Yamada, and H. Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[30] F. Scarselli, M. Gori, A. C. Tsai, M. Hagenbuchner, and Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20( 1):61-00, 2009.
[31] J. M. Stokes, K. Yang. K. Swanson, W. Jin, A. Cubillos-Ruiz, N. M. Donghia, C. R. MacNair, S. French, L. A. Carfrae, Z. Bloom-Ackermann, V. M. Tran, A. Chiappino-Pepe, A. H. Badran, I. W. Andrews, E. J. Chory, G. M. Church, E. D. Brown, T. S. Jaakkola. R. Barzilay, and J. J. Collins. A deep learning approach to antibiotic discovery. Cell, 180(4):688 702, 2020.
[32] R. Trivedi, M. Farajtabar, P. Biswal, and H. Zha. DyRep: Learning representations over dynamic graphs. In International Conference on Learning Representations (ICLR), 2019.
[33] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need, In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[34] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph Attention Networks. In International Conference on Learning Representations (ICLR), 2018.
[35] S. Verma and Z.-L. Zhang, Stability and generalization of graph convolutional neural networks. In International Conference on Knowledge Discovery & Data Mining (KDD), 2019.
[36] Y. Verma, Kaski, M. Heinonen, and V. Garg. Modular flows: Differential molecular generation. In Advances in Neural Information Processing Systems (NeurlPS), 2022.
[37] C. Vignac, A. Loukas, and P. Frossard. Building powerful and equivariant graph neural networks with structural pressageppassing. In Neural Information Processing Systems (NeurIPS), 2020.
[38] Y. Wang, Y. Chang, Y. Liu, Leskovec, and P. Li. Inductive representation learning in temporal networks via causal anonymous walks, In International Conference on Learning Representations (ICLR), 2021.
[39] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, pages 1-21, 2020.
[40] D. Xu, W. Cheng, D. Luo, Y. Gu, X. Liu, J. Ni, B. Zong, H. Chen, and X. Zhang. Adaptive neural network for node classification in dynamic networks. In IEEE International Conference on Data Mining (ICDM), 2019.
[41] D. Xu, C. Ruan, E. Korpeoglu, S. Kumar, and K. Achan. Self-attention with functional time representation learning. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[42] D. Xu, C. Ruan, E. Korpeoglu. S. Kumar. and K. Achan. Inductive representation learning on temporal graphs. In International Conference on Learning Representations (ICLR). 2020.
[43] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
12

---

[44] K. Xu, Li. M. Zhang, S. Du, K.-I. Kawarabayashi, and S. Jegelka. What can neural networks reason about? In International Conference Learning Representations (ICLR), 2020.
[45] K. Xu, M. Zhang. J. Li, S. S. Du, K.-I. Kawarahayashi, and S. Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference Learning Representations (ICLR). 2021.
[46] Z. Zhang, F. Wu, and W. S. Lee. Factor graph neural networks. In Advances in Neural Information Processing Systems (NeurlPS), 2020.
13


Reviews:
[{"review_id": "peh2Di2leLd", "reviewer": "Reviewer_gAwT", "summary": "The paper studies the topic of graph neural networks in temporal settings, which is a very significant avenue of graph learning applications. In doing so, a number of recent prominent works in this sub-topic is converged in this paper through solid theoretical analyses. Particularly, theoretical foundations have been developed (summarized in Fig 1 with references to relevant statements) which improves the understanding of temporal GNNs and provides a basis for further improvement targeting this research domain. Standing on such theoretical studies, the paper proposes a position-encoding temporal graph network (PINT) which is provably powerful than existing GNNs for temporal graph learning, which is empirically powerful than existing methods on the benchmarks used.", "questions": "-What would be the effect of directly adopting positional encodings that have been developed for static GNNs (which the paper reviews in the supplementary sections), say for different static graph snapshots at different timestamps?   \n-In line 347-349, it is claimed that MP-TGNs are outperformed by PINT w/o pos. feat. However, from Table 1, it is observed that in 7/12 results (12 = 6 transductive + 6 inductive), it is not the case.   \n-With respect to the time complexity analysis, the Figure 6 has an interesting mark at epoch 25, after which PINT's runtime is faster than CAW. To this end, will it possible to show some sample evaluations of PINT at only 25 epochs (or lesser) of training? This could provide a useful insight on comparison of PINT with CAW at a situation where PINT's runtime is not better than CAW.   ", "limitations": "Yes, the limitations are clearly discussed as well as societal impact mentioned.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "=>Strengths:   \n-This work is an excellent convergence of the recent advances in extending GNNs on temporal graphs. It includes several studies in terms of theoretical property of existing temporal GNNs, what are their limitations, extending WL test analysis on temporal graphs, and ways to improve TGNs beyond MP-TGNs.    \n-In terms of originality, I feel the paper is greatly motivated from existing theoretical advancements of GNNs applied to static graphs (in terms of 1-WL like quantification, limitations and positional encodings). Nevertheless, this extension and presentation of the theoretical insights to temporal graph settings is novel.    \n-In terms of significance, the results and insights from this paper would definitely be used in further developments.    \n-The paper writing is clear, the related literature and existing concerns are discussed.    \n-Overall this paper does a fundamental contribution for the topic of developing machine learning foundations on temporal and time dynamic graphs.   \n\n=>Weaknesses:   \nWhile there seems no significant weakness in the contribution of this work, below are some minor observations:\n-Are the experimental results significant looking at the score differences of PINT with best model of the literature. For instance the differences are in the ranges ~0.5 scores of AP for many results in Table 1?    \n-Whether positional encoding (pe) is main contributor of good performance of PINT? Would incorporating the 'pe' in existing TGNs would be at par performance of PINT+pe?   ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GLN7KolKIJN", "reviewer": "Reviewer_pA52", "summary": "The paper provides a theoretical framework to analyse the expressive power of temporal graph networks (TGNs), and designs a novel model, PINT, which is provably more expressive than existing ones. Specifically, the paper proves the role of memory, benefits of injective message passing, limits of existing TGN models, temporal extension of the 1-WL test and its implications, impossibility results about temporal graph properties, and the relationship between main classes of TGNs. Then, PINT is introduced, with the elaborately design of injective temporal aggregation and relative positional features. Empirical investigations show that PINT is competitive or better than existing models on several real benchmarks for dynamic link prediction in different settings.", "questions": "1. The model does not outperform certain baselines on Enron in the transductive setting, and is relatively worse in the inductive setting. However, the authors do not provide a plausible explanation on these phenomena.\n\n2. Several experiments are missing. For example, the results on node classification is more straighforward to show the models' power of distinguishing nodes than dynamic link prediction. Also, parameter sensitivity can be analysed on \\alpha and \\beta, because it may be important for controling the learned injective function.\n\n3. Does PINT still fail in differing properties mentioned in Proposition 7, even the relative positional features are added?\n\n4. There are some places that can be improved to make the discussion clearer. For example, I am a bit confused when reading line 45-50, because I fail to recognize the concept \"injective MP-TGN\", as it is referred to as \"MP-TGNs equipped with injective functions\" and \"these most powerful MP-TGNs\", and is contained in \"MP-TGN\" mentioned in the last sentence of this paragraph. Besides, there is no clear definition of the concept \"anonymous TGNs\", which comes up for several times in the paper.\n\n5. A minor flaw: the term \"discrete-time dynamic graph\" in line 83 should be in italic type, aligning with line 85.", "limitations": "This work do not show any potential negative societal impact. The authors illustrate cases when the model fails, which is possibly related to temporal 1-WL test. Future works can be focused on going beyond this.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper puts forward an interesting research direction of theoretically analysing the expressive power of temporal graph networks, which is of great importance yet long be ignored.\n2. The theoretical results in the paper are solid. The authors extend the analysis framework in static GNNs to TGNs. The lemmas and propositions are closely linked to each other. The proofs seem logically rigorous, covering both special and general cases.\n3. The design of PINT is concise yet with firm theoretical foundation.\n4. Impossibility results of PINT are also introduced.\n\nWeakness:\n1. Discussion on the experimental results are not sufficient. Notice that the model does not outperform certain baselines on Enron in the transductive setting, and is relatively worse in the inductive setting. However, the authors do not provide a plausible explanation on these phenomena.\n2. Several important experiments are missing. For example, the results on node classification is more straighforward to show the models' power of distinguishing nodes than dynamic link prediction.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CgmhO0mU4qP", "reviewer": "Reviewer_9vm8", "summary": "The paper attempts to address the limitations of message-passing TGNs (MP-TGNs) and walk-aggregating TGNs (WA-TGNs). To be specific, a so-called position-encoding injective temporal graph net (PINT) is proposed, which not only defines injective message passing and update steps, but augments memory states with novel relative positional features. Note that, the time complexity of computing and communicating positional features in PINT is less than CAW. Experimental results show that PINT outperforms existing TGNs on several real-world benchmarks in both transductive and Inductive settings.", "questions": "Questions: \n1. Can the proposed PINT deal with long-term dependencies?\n2. For edge and node embeddings, why the authors consider 10/20-hop neighbors? Will the small number of neighbors will impact the performance? \n3. I am curious whether the proposed PINT model can be used for node classification/forecasting?\n4. The standard deviations of PINT on Reddit and Twitter (for both transductive and Inductive settings) are very small. I wonder is there any reasons/ways to interpret this scenario?\n5. For Eqs. 9 and 10. Why the authors only do multiplication between $P$ and $r^{t^-}_{i \\rightarrow u}$ (e.g., in Eq. 9)?", "limitations": "I have no ethical concerns with this paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is clearly written and easy to follow. The Introduction and Related Works (Preliminaries) parts are well written.\n2. Visualizations and plots are intuitive.\n3. Building injective aggregation and update functions in the temporal setting is interesting and somewhat novel.\n4. Experiments are extensive and promissing, considering both transductive and Inductive settings.\n\nWeaknesses:\nAlthough the authors have already show that PINT can be trained faster than CAW (which is the main competitor shown in Table 1). I wonder will the large-scale temporal networks limit the behavior of PINT?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6pzKsEOJ1Cv", "reviewer": "Reviewer_HPYE", "summary": "This work studies the expressivity limitation of temporal graph neural networks, mainly on two state-of-the-art (SOTA) methods, TGNs (MP-TGN in paper) and CAWs, then proposes a more expressive framework, PINE.", "questions": "1. Around CTDG definition (line 85), it will be better to use different symbols for G since it will have two meanings before and after line 85. Before the line, G refers to simple graph (no dup edges, static or happening in specific time range); but after the line, G refers to multi-graph (have multi edges linking same nodes) whose edges are additionally distinguished by extra timestamps. It is important to highlight this shifting to avoid confusion in later content.\n2. I am not sure the correctness of uniformly spaced countable set in Proposition 1 (line 93), please clarify: To transform CTDG to DTDG, we only need to put all timestamps as a real value feature on nodes or edges, and let different timestamp generate different snapshot, thus just countable will be enough. And I think this requirement may even be meaningless since even for CTDG, you can not store infinite timestamps, and with finite timestamps, CTDG and DTDG are same.\n3. Need clarification of memory aggregation for equation (3) (line 114) and experiments. Equation (3) shows that you are using most recent memory aggregation in the paper, but in appendix, you investigate mean aggregation of TGN, which one are you really using? Besides, if you are using mean memory aggregation, shouldn't you decrease MP-TGN by 1 layer for fairness? Since it is a kind of graph convolution.\n4. The TGN limitation example (figure 2) is unfair since TGN-Att is just a specific hyperparameter setting of original TGN paper, and I think that another setting TGN-sum can solve this counterexample, thus this is not a real counterexample for TGN.\n5. TCT node symbol i_u is bad and causes confusion. In line 142, i_u should not have u as subscript since it implies a unique TCT node is assigned with u but we can have multi nodes in the same TCT layer corresponding to the same u (but different times). A better notation is required to make it clear that a real node u can appear multiple times in both the same and different layers in TCT.\n6. Besides, should mapping #v also have t as an argument since it is reverse mapping in a sub tree of root (v, t)?\n7. Is line 155 of definition 1 indeed s_u = s'_{f(u)}? I don't think current statement makes any sense. Omitting root node makes the notation confusing.\n8. Can proposition 6 and 7 extend to random walk methods, e.g. CAW? Since without such extensions, it looks same as conclusion of reference [49] that with proper injective mappings, we can always distinguish temporal graph isomorphism like a static graph, and even the most power methods are not good for learning relations? If so, you can move this part to appendix and clarify other parts better or put other parts there, e.g., how can your method deal with deletion.\n9. What is the square root term in equation (4)? It is different from proposition 8, and no explanation or intuition is provided for such modification in the paper.\n10. It will be better to add more space between P and r in equation (9) and (10) since it looks like Pr on the first sight.\n11. There is a highly related work CAW-TGN [1] that use CAW to get positional info for TGN which is similar to your paper, and you should add this into your comparison baseline and do ablation study.\n12. Why some datasets do not have static method performance?\n\nMinor typos:\n- Figure 2: (v, z, t3) to (u, z, t3)\n\n[1] Makarov, I., et al. (2021). Temporal graph network embedding with causal anonymous walks representations.", "limitations": "This paper provides the limitation of PINE which reveals the direction for future efforts and reports societal impact in appendix.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this paper is:\n1. Propose a concrete failure case of SOTA methods, e.g., CAW, which can be used as a benchmark for temporal graphs.\n2. Studying temporal graph neural networks expressivity by temporal computation tree (TCT) and proposed temporal WL test variant.\n3. Design more expressive PINE which achieve empirically better performance in 5/6 widely used datasets.\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept