TempME: Towards the Explainability of Temporal Graph Neural Networks via Motif Discovery
Authors: Jialin Chen
Zhitao Ying
Venue: NeurIPS 2023 poster (2023)
Keywords: Explainability
Temporal Graph Neural Network

Abstract: Temporal graphs are widely used to model dynamic systems with time-varying interactions. In real-world scenarios, the underlying mechanisms of generating future interactions in dynamic systems are typically governed by a set of recurring substructures within the graph, known as temporal motifs. Despite the success and prevalence of current temporal graph neural networks (TGNN), it remains uncertain which temporal motifs are recognized as the significant indications that trigger a certain prediction from the model, which is a critical challenge for advancing the explainability and trustworthiness of current TGNNs. To address this challenge, we propose a novel approach, called **Temp**oral **M**otifs **E**xplainer (**TempME**), which uncovers the most pivotal temporal motifs guiding the prediction of TGNNs.  Derived from the information bottleneck principle, TempME extracts the most interaction-related motifs while minimizing the amount of contained information to preserve the sparsity and succinctness of the explanation. Events in the explanations generated by TempME are verified to be more spatiotemporally correlated than those of existing approaches, providing more understandable insights. Extensive experiments validate the superiority of TempME, with up to 8.21% increase in terms of explanation accuracy across six real-world datasets and up to 22.96% increase in boosting the prediction Average Precision of current TGNNs.

TempME:
Towards the Explainability of Temporal Graph Neural Networks via Motif Discovery
Jialin Chen Yale University j jialin. chen@yale. edu
Rex Ying Yale University rex. rex.ying@yale.co edu
Abstract
Temporal graphs are widely used to model dynamic systems with time-varying interactions. In real-world scenarios, the underlying mechanisms of generating future interactions in dynamic systems are typically governed by a set of recurring substructures within the graph, known temporal motifs. Despite the success and prevalence of current temporal graph neural networks (TGNN). it remains uncertain which temporal motifs recognized the significant indications that trigger a certain prediction from the model, which is a critical challenge for advancing the explainability and trustworthiness of current TGNNs. To address this challenge, we propose novel approach, called Temporal Motifs Explainer (TempME), which uncovers the most pivotal temporal motif's guiding the prediction of TGNNs. Derived from the information bottleneck principle, TempME extracts the most interaction-related motifs while minimizing the amount of contained information preserve the sparsity and succinctness of the explanation. Events in the explanations generated by TempME are verified be more spatiotemporally correlated than those of existing approaches, providing more understandable insights. Extensive experiments validate the superiority of TempME, with up to 8.21% increase terms of explanation accuracy across six real-world datasets and up to 22.96% increase boosting the prediction Average Precision of current TGNNs!
Introduction
Temporal Graph Neural Networks (TGNN) are attracting surge of interest in real-world applications, such as social networks, financial prediction, etc. These models exhibit the ability to capture both the topological properties graphs and the evolving dependencies between interactions over time [1, 2, 3, 4, 5, 6, 7, 8J. Despite their widespread success, these models often lack transparency, functioning as black boxes. The provision human- camman-nttelliibblee explanations for these models becomes imperative, enabling better understanding of their diciisionmmaingg logic and justifying the rationality behind their predictions. Therefore, improving explainability fundamental in enhancing the trustworthiness of current TGNNs, making them reliable for deployment in real-world scenarios, particularly in high-stakes tasks like fraud detection and healthcare forecasting [9, 10, 11, 12].
The goal of explainability is to discover what patterns in data have been recognized that trigger certain predictions from the model. Explanation approaches on static graph neural networks have been well- studied recently [13, 14, 15, 16, 17, 18, 19]. These methods identify small subset of important edges or nodes that contribute the most to the model's prediction. However, the success of these methods on static graphs cannot be casily generalized to the field of temporal graphs, due to the complex and volatile nature of dynamic networks [8, 4, 3]. Firstly, there can be duplicate events occurring at the same timestamp and the same position in temporal graphs. The complicated dependencies
The code is available at https:://itthhi www.aauu..cmmmmmaaae www..ooo//rrraeeee and Gew.eetric-LLLLannggTeeeee
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

between interactions were under- ander-emphasized by existing explanation approaches [20, 21J. Moreover, the important events should be temporally proximate and spatially adjacent construct human- intelligible explanation [22]. We refer to explanations that satisfy these requirements as cohesive explanations. As illustrated Figure (a)) a non-cohesive explanation typically consists of scattered events (highlighted in purple). For instance, event 1 and event 10 in the disjointed explanation are neither temporally proximate nor spatially adjacent to other explanatory events, leading to a sub-optimal explanation and degrading the inspiration that explanations could bring us. There have been some recent attempts at TGNN explainability [21, 23). Unfortunately, they all face the critical challenge of generating cohesive explanations and fall short of providing human-inte intelligiible insights. Moreover, they entail high computational costs, making them impractical for real-world deployment.
To address the aforementioned challenges of temporal explanations, we propose to utilize temporal motifs in the explanation task. Tempo- ral motifs refer to recurring substructures within the graph. Recent studies [24, 25, 26, 27, 28, 29, 30, 31] demonstrate that these temporal motifs are essential factors that control the generative mechanisms of future events in real-world tem- poral graphs and dynamic systems. For example, preferential attachment (Figure ((c) elucidates the influencer effeet in e-commerce marketing graphs [32, 33]. Triadic closure (Figure 1 (d)) explains the common-frient rules in social net- works [34, 6, 1, 25]. Therefore, they are plau- sible and reliable composition units explain TGNN predictions. Moreover, the intrinsic self- connectivity of temporal motifs guarantees the cohesive property of the generated explanations (Figure 1(b)).
6
3
10
[a] non-cahesive explanation
(c) Preferential attachment
[b) cohesive explanation
(d) triadic closure
Figure I: (a) and (b): Non-cohesive explanation and cohesive explanation (highlighted in colors). (c) and (d): Temporal motifs govern the genera- tion of future interactions (numbers denote event orders).
Proposed work. In the present work, we propose TempME, a novel Temporal Motif-based Explainer to identify the most determinant temporal motifs to explain the reasoning logic of temporal GNNs and justify the rationality of the predictions. TempME leverages historical events to train a generative model that captures the underlying distribution of explanatory motifs and thereby improves the explanation efficiency. TempME is theoretically grounded by Information Bottleneck (IB), which finds the best tradeoff between explanation accuracy and compression. To utilize Information Bottleneck in the context of temporal graphs, we incorporate a null model (i.e., a randomized reference) [22, 35, 36] into the model to better measure the information contained in the generated explanations. Thereby, TempME is capable of telling for each motif how the occurrence frequency difference in empirical networks and randomized reference reflects the importance to the model predictions. Different from previous works that only focus on the effect of singular events [23, 21], TempME is the first to bring additional knowledge about the effect of each temporal motif.
We evaluate TempME with three popular TGNN backbones, TGAT [3], TGN [4] and GraphMixer [5]. Extensive experiments demonstrate the superiority and efficiency of TempME in explaining the prediction behavior of these TGNNs and the potential in enhancing the prediction performance of TGNNs, achieving up to 8.21% increase in terms of explanation accuracy across six real-world datasets and up to 22.96% increase in boosting the prediction Average Precision of TGNNs.
The contributions of this paper are: (1) We are the first to utilize temporal motifs in the field of explanations for TGNNs to provide more insightful explanations; (2) We further consider the null model in the information bottleneck principle for the temporal explanation task; (3) The discovered temporal motifs not only explain the predictions of different TGNNs but also exhibit ability in enhancing their link prediction performance.
2 Related Work
GNN Explainability Explainability methods for Graph Neural Networks can be broadly classified into two categories: non-generative and generative methods. Given input instance with its

---

prediction, non -on-eeeerative methods typically utilize gradients [15, 37], perturbations [38, 391, relevant walks [40], mask optimization surrogate models [41], and Monte Carlo Tree Search (MCTS) [16] to search the explanation subgraph. These methods optimize the explanation one by one during the explanation stage, leading to a longer inference time. On the contrary, generative methods train generative model across the entire dataset by learning the distribution of the underlying explanatory subgraphs [19, 18, 14, 42, 43, 44, 45J, which obtains holistic knowledge of the model behavior over the whole dataset. Compared with static GNN, the explainability of temporal graph neural networks (TGNNs) remain challenging and under-explored. TGNNExplainer [23] is the first explainer tailored for temporal GNNs, which relies the MCTS algorithm to search for combination of the explanatory events. Recent work [21] utilizes the probabilistic graphical model to generate explanations for discrete time series the graph. leaving the continuous-ting setting under- explored. However, these methods cannot guarantee cohesive explanations and require significant computation costs. There are also some works that have considered intrinsic interpretation in temporal graphs [26] and seek the self- eeffinttrprettble models [46, 20J. As ignored by previous works on temporal explanation, aim for cohesive explanations that human-un camman-undrrttandable and insightful in generative manner for better efficiency during the explanation stage.
Network Motif's The concept of network motifs is defined as recurring and significant patterns of intervonnections [35], which are building blocks for complex networks [47, 24J. Kovanen et al. [22] proposed the first notion of temporal network motifs with edge timestamps, followed by relaxed versions to involve more diverse temporal motifs [48, 24, 49]. Early efforts developed efficient motif discovery algorithms, egg. MFFndder [50], MAVisto [51], Kavosh [36], etc. The standard interpretation of the motif counting is presented in terms of a null model, which is randomized version of the real-world network [35, 52, 22, 53 Another research line of network motifs focuses on improving network representation learning with local motifs [54, 55, 56]. These approaches emphasize the advantages of incorporating motifs into representation learning, leading to improved performance on downstream tasks. In this work, constitute the first attempt to involve temporal motifs in the explanation task and target to uncover the decision making logic of temporal GNNs.
3 Preliminaries and Problem Formulation
Temporal Graph Neural Network. We treat the temporal graph as a sequence of continuous timestamped events, following the setting in TGNNExplainer [23]. Formally, a temporal graph can be represented as a function of timestamp by G(t) = (()), where ((t) and E(t) denote the set of nodes and events that occur before timestamp as = (U,, 2k. tk. ak), denoting that node 24 and node es have an interaction event at timestamp t < with the event attribution 0g. Without loss of generality, we assume that interaction is undirected [5, 1]. Temporal Graph Neural Networks (TGNN) take as input temporal graph ((t) and learn time-aware embedding for each node in (t). TGNNs' capability for representation learning on temporal graphs is typically evaluated by their link prediction performance [57, 1, 25), i.e. predicting the future interaction based on historical events. In this work, we also focus on explaining the link prediction behavior of TGNNs, which can be readily extended to node classification tasks.
Each element eμ in {() is represented
Explanation for Temporal Graph Neural Network. Let f denote a well- trained TGNN (aka. base model). To predict whether an interaction event e happens between and at timestamp t, the base model of leverages the time-aware node representation x. (t) and (x(()) to output the logit/probability. An explainer aims identifying subset of important historical events from E() that trigger the future interaction prediction made by the base model f. 'he subset of important events is known as an explanation. Formally, let Y,(c) denote the binary prediction of event e made by base model f. the explanation task can be formulated as the following problem that optimizes the mutual information between the explanation and the original model prediciton [13, 23]:
argmaxx I [(Ygle): Depp) 10 ISK
argmii 0 SK
Σ [Y c) (og(
where ((.,)) denotes the mutual information function, e is the interaction event to be explained, So.p denotes the explanation constructed by important events from (tt) for e. f(C is the probability output on the event predicted by the base model f. K is the explanation budget on the explanation size (i.e., the number of events in (
3

---

4 Proposed Method: Temp.EE
A simple optimization of Eq. 1 easily results in disjointed explanations [23]. Therefore, utilize temporal motifs to ensure that the generated explanations are meaningful and understandable.
The pipeline of TempME is shown in Figure 2. Given a temporal graph and a future prediction be- tween node u and node v to be explained, TempME first samples surrounding temporal motif instances (Sec. 4.1). Then Motif Encoder creates expres- sive Motif Embedding for each extracted motif in- stance, which consists of three main steps: event anonymization, message passing, and graph pooling (Sec.4.2). Based on Information--ottlleedd (IB) prin- ciple, TempME characterizes the importance scores of these temporal motifs, under the constraints of both explanation accuracy and information compres- sion (Sec. 4.3). In the explanation stage, succinct and cohesive explanations are constructed by sampling from the Bernoulli distribution controlled by the im- portance score for the prediction behavior of the base model.
enry VN OTEES
Lll Moti Extraction
Explonation
O+O eet wooeres orrssd
(2) Motif Encoder
Arorsmiaiiii Crash
(4) Somple- Bernkaa)
Importancep
(3) 18-bowedd
motif
0.98
mobe
0.24
Motif Embeddiing
0.36
Figure 2: Framework of TempME. Numbers on the edge denote the event order.
4.1 Temporal Motif Extraction
We first extract a candidate set of motifs whose importance scores are to be derived. Intuitively, event orders encode temporal causality and correlation. Therefore, we constrain events to reverse over the direction of time in each motif and propose the following Retrospective Temporal Motif.
Definition 1. Given temporal graph and node uo at time lo. a sequence of events, denotes as I = {(u,, U1, t1), (ug, U2, .2),,.., (u, Vi, tt)} is a n-node, l-length, 8-duration Retrospective Temporal Motif of node uo if the events are reversely time ordered within 6 duration, i.e., to >
t > 12 12.... > to and to - t S 8, such that ūn = ug and the induced subgraph is connected and contains n nodes.
Temporal dependencies are typically revealed by the relative order of the event occurrences rather than the absolute time difference. Consequently, we have the following definition of equivalence. Definition 2. Two temporal motif instances Jn and T2 are equivalent if they have the same topology and their events occur in the same order, denoted as J = Tz.
Temporal Motifs are regarded as important building blocks of complex dynamic systems [52, 35, 22, 50]. Due to the large computational complexity in searching high-order temporal motifs, recent works show the great potential of utilizing lower-order temporal motifs, e.g., two-length motifs [52] and three-node motif's [24, 55, 58], as units to analyze large-scale real-world temporal graphs. A collection of temporal motif's with up nodes and events is shown in Appendix B.
Given a temporal graph with historical events E and node uo of interest at time fo, we sample C' retrospective temporal motifs with at most n nodes
Algorithm 1: Temporal Motif Sampling (E, n,,,, uo to, C); / 2
and events, starting from uo (6 is usually large for the comprehensiveness of motifs). Alg. 12 shows our Temporal Motif Sampling approach, where E(S, i) denotes the set of historical events that occur to any node in S before time t. At each 3
as
Node set: S. <- {uo} for 1 SCSC Event sequence: I, + (), for Sesc for 1 to C' do
for j = 1 to / do Sample one event ej (1)));,4)) from t(s,
step, we sample one event from the set of historical events related the current node set. Alg. adapts Mfinder [50], motif mining algorithm on static graphs, to the scenario of temporal graphs. We could also assign different sampling probabilities to historical events in Step Alg. to obtain temporally biased samples. Since the purpose of
if [S < n then
S. = S. oug
J. = Ia ej
return (Le [[sesC]
our sampling is to collect candidate set of expressive temporal motifs for the explanation, we implement uniform sampling in Step 3 for algorithmic efficiency.

---

Relation to Previously Proposed Concepts. Recent works [1. 6] propose to utilize temporal walks and recurrent neural networks (RNN) [59] to aggregate sequential information. Conceptually, temporal walks construct a subset of temporal motif instances in this work. In contrast, temporal motifs capture more graph patterns for holistic view of the governing rules in dynamic systems. For instance, the motif of preferential attachment (Fig. I()) cannot be represented as temporal walks.
4.2 Temporal Motif Embedding
In the present work, we focus on explaining the link prediction of temporal graph neural networks. Given an interaction prediction between node u and node to be explained, we sample C' surrounding temporal motif instances starting from u and v, respectively. denoted M,, and M.. Note the proposed framework is also flexible for explaining other graph-related problems. For instance, to explain the node classification on dynamic graphs, we sample C' temporal motif instances around the node of interest. Each temporal motif is represented as (e1, f2..." et) with e; = (u,, %, t;) satisfying Definition 1. We design a Motif Encoder learn motif-level representations for each surrounding motif in M,, and M,.
Event Anonymization. The anonymization technique is at the core of many sequential feature distillation algorithms [1, 6, 60, 61]. Previous works [6, 1] mainly focus node anonymization, while temporal motifs are constructed by sequences of temporal events. To bridge this gap, we consider the following event anonymization to adapt to temporal motifs. To maintain the inductiveness, we create structural features to anatomize event identities by counting the appearance at certain positions:
h(e, u, v)[s !|I| I E M, U M., [[j] (u, v/ t); vttl for i (1,2...... ,1.-
(2)
h(e,, u, v) (abbreviated as h(e;) for simplicity) is a (-dimensional structural feature of e, where the j-th element denotes the number of interactions between u, and o at the j-th sampling position in M, U M,. h(e,) essentially encodes both spatial and temporal roles of event e,.
Temporal Motif Encoding. The extracted temporal motif is essentially subgraph of the original temporal graph. Instead of using sequential encoders, we utilize local message passing to distill motif-level embedding. Given a motif instance with node set V/ and event set &,, let X, denote the associated feature of node E Vı. Egg (Apg || T(t tpy) || h(epg)) denotes the event feature of event Epg E E,, where apg is the associated event attribute and h(epg) refers to the structural feature of event Epg (Eq. 2). Note that the impact of motifs varies depending on the time intervals. For instance, motifs occurring within a single day differ from those occurring within a year. Thus, we need a time encoder T(-) which maps the time interval into 2d-dimensional vectors via 7 T())) //ddccos cos(ss, At), si),sin((v sin(w, A!), cos(w At). sin(wAAt) with learnable parameters W1. ................................ wa [52, 1]. To derive the motif-level embedding, we initially perform message passing to aggregate neighboring information and then apply the READOUT function to pool node features.
X, MESSAGEPASSING( Eppla
4 E ()())) and m READOUT((X,, ViJ) (3)
Following Eq. 3, one may use GIN [62] or GAT [63] in MESS AGEAASSIG step and simple mean- pooling learnable adaptive-pooling [64] as READOUT function to further capture powerful motif representations. We refer to Appendix D.4 for more details about the Temporal Motif Encoder.
4.3 Information-Boolleneckk-
Generator
Motivation. A standard analysis for temporal motif distribution is typically associated with the null model, a randomized version of the empirical network [22, 50, 35]. The temporal motif that behaves statistically differently in the occurrence frequency from that of the null model is considered to be structurally significant. Therefore, we assume the information of temporal motifs can be disentangled into interaction-related and interaction-inelevan ones. The latter is natural result of the null model. Based on this assumption, we resort to the information bottleneck technique to extract compressed components that are the most cneracctionrelated We refer Appendix C for theoretical proofs.
Sampling from Distribution. Given an explanation query and motif embedding my with I E M. where M denotes the set of extracted temporal motifs, we adopt an MLP for mapping my to an importance score pr E [0, 1). which measures the significance of this temporal motif instance for the explanation query. We sample mask (a Bernoulli(pr) for each temporal motif instance and then apply the masks to screen for subset of important temporal motif instances via Maxp A M.
5

---

A is the mask vector constructed by ai for each motif I and @ denotes element- product. The explanation subgraph for the query can thus be induced by all events that occur Maxp'
To pack-propagate the gradients w.r. the probability ps during the training stage, we use the Concrete relaxation of the Berouuli distribution [65] via Bernoulli(p) zs af (logp- 1og(11 p) + log log(1 u))), where u ~ Uniform(( (0, 1). À is a temperature for the Concrete distribution and o is the sigmoid function. In the inference stage, we randomly sample discrete masks from the Bernoulli distribution without relaxation. Then we induce a temporal subgraph with Maxp as the explanation. One can also rank all temporal motifs by their importance scores and select the Top K important motifs to induce more compact explanations if there is a certain explanation budget in practice.
Information Bottleneck Objective. Let Gaxp and (e) denote the explanation and the computational graph of event (i.e., historical events that the base model used to predict e). To distill the most interaction- while compressed explanation, the IB objective maximizes mutual information with the target prediction while minimizing mutual information with the original temporal graph:
min (9 Yyle)) + BI 9(e)), S.J. 19eppl S K
where [y] refers to the original prediction of event B is the regularization coefficient and K is constraint on the explanation size. We then adjust Eq. 4 to incorporate temporal motifs.
The first term in Eq. 4 can be estimated with the cross-entropy, between the original prediction and the output of base model f given gexp as Eq. 1, where gaxp is induced by Maxp. Since temporal motifs are essential building blocks of the surrounding subgraph and we have access to the posterior distribution of Maxp conditioned on M with importance scores, we propose to formulate the second term in Eq. 4 as the mutual information between the original motif set M and the selected motif subset Mexp- We utilize a variational approximation ((Mexy)) to replace its marginal distribution P(Mexp) and obtain the upper bound of I [M, Mesp) with Kullback- divergence:
[(M, S EM (Po (M) ((Mesp))
(5)
where & involve learnable parameters in Motif Encoder (Eq. 3) and the MLP for importance scores.
Choice of Prior Distribution. Different choices of ((Maxp)) in Eq. 5 may lead different inductive bias. We consider two practical prior distributions for ((Maax)): uniform and empirical. In the uniform setting [42, 66], ((Msp)) the product of Bernoulli distributions with probability p E [o, 1]. that is, each motif shares the same probability p being in the explanation. The KL divergence thus
1-Pr, becomes DKL (P ss (-M IM); ((Maxp)) EnEm PI, log pt, + (1 - PI.) log 1-p Here p is p
hyperparameter that controls both the randomness level in the prior distribution and the prior belief about the explanation volume (i.e., the proportion of motifs that are important for the prediction).
However, uniform distribution ignores the effect of the null model, which is a better indication of randomness in the field of temporal graphs. To tackle this challenge, we further propose to leverage the null model to define empirical prior distribution for (M A null model is essentially randomized version of the empirical network, generated by shuffling or randomizing certain properties while preserving some structural aspects of the original graph. Following prior works the null model [67, 22], we utilize the common null model in this work, where the event order is randomly shuffled. The null model shares the same degree spectrum and shuffeluffeed event orders with the input graph [53] (see more details in Appendix D. We categorize the motif instances in M by their equivalence relation defined in Definition B. Let (U1, UT) denote T equivalence classes of temporal motifs and (Q1,'.. (T) is the sequence of normalized class probabilities occurring in Maxp with qi Ei,ev; /t,/ Σ1,em
where pr, is the importance score of the motif instance I,. Correspondingly, we have (m1. .mr) denoting the sequence of normalized class probabilities in the null model. The prior belief about the average probability of motif being important for prediction is fixed as p. Thus minimizing Fq. 5 is equivalent to the following equation.
T
1-s min DKL (P (Mxxpp (MM))((MM)))) ((Mosp)) e min(1 log 1-p
qo log sqi
8
(6)
pm;
where is computed by EIJEM Pt, MIM which measures the sparsity of the generated explanation. Combing Eq. 1 and Eq. 6 leads to the following overall optimization objective:
min Eees()) e c=0,1
Σ 1( c) log( (Gg + 8((1 5) log
1-
1 -p + qi log 84: ). (7)
pm,

---

Eq. 7 aims at optimizing the explanation accuracy with the least amount of information. It learns to identify the most interaction- temporal motifs and push their importance scores close to 1, leading to deterministic existences of certain motifs in the target explanation. Meanwhile, the interaction-irreleant components are assigned smaller importance scores to balance the trade-off in Eq. 7. TempME shares spirits with perturbation-base explanations [68, 69), where "interpretable components [68]" corresponds to temporal motif's and the "reference" is the null model.
Complexity. A brute-force implementation of the sampling algorithm (Alg. 1) has the time com- plexity O(C)). Following Liu et al. [52]. we create a 2/-digit to represent a temporal motif with I events, where each pair of digits is an event between the node represented by the first digit and the node represented by the second digit. We utilize these 21-digits to classify the temporal motifs by their equivalence relations, thus resulting in complexity of (CC). An acceleration strategy with the tree-structured sampling and detailed complexity analysis are given in Appendix D.3.
5 Experiments
5.1 Experimental Setups
Dataset. We evaluate the effectiveness of TempME on six real-world temporal graph datasets, Wikipedia, Reddit, Enron, UCI, Can.Parl., and US Legis [70, 71, 72] that cover wide range of domains. Wikipedia and Reddit are bipartite networks with rich interaction attributes. Enron and UCI are social networks without any interaction attributes. Car.Parl. and US Legis two political networks with a single attribute. Detailed dataset statistics are given in Appendix E.
The proposed TempME can be employed to explain any temporal graph neural network (TGNN) that augments local message passing. We adopt three state-of-the-art temporal graph neural networks as the base model: TGAT [3], TGN [4], and GraphMixer [5]. TGN and GraphMixer achieve high performance with only one layer due to their powerful expressivity or memory module. TGAT typically contains 2-3 layers to achieve the best performance. Following previous training setting [23, 1, 6]. we randomly sample an equal amount of negative links and consider event prediction as a binary classification problem. All models are trained in an inductive setting [6, 1].
Base Model.
Baselines. Assuming the base model contains T. layers and we aim at explaining the prediction on the event e, we first extract L-hop neighboring historical events as the computational graph G(e). For baselines, we first compare with two self-interpretable techniques, Attention (ATTN) and Gradient- based Explanation (Grad-CAM [37]). For ATTN, we extract the attention weights TGAT and TGN and take the average across heads and layers the importance scores for events. For Grad-CAM, we calculate the gradient of the loss function w.r.f. event features and take the norms as the importance scores. Explanation G is generated by ranking events in G(e) and selecting a subset of explanatory events with the highest importance scores. We further compare with learning-baat based approaches, GNNExplainer [13], PGExplainer [14] and TGNNExplaiiner [23]. following the haseline setting in prior work [23]. The former two are proposed to explain static GNNs while TGNNExplainer is a current state-of-the-an model specifically designed for temporal GNNs.
Configuration. Standard fixed splits [73, 72] are applied on each datasets. Following previous studies on network motifs [52, 22, 35, 56], we have empirically found that temporal motifs with most nodes and 3 events are sufficiently expressive for the explanation task (Fig. 4). We use GINE [74], a modified version of GIN [62] that incorporates edge features in the aggregation function, as the AGESASNNA function and mean-pooling as the READOUT function by default.
5.2 Explanation Performance
Evaluation Metrics. To evaluate the explanation performance, we report Fidelity and Sparsity following TGNNExplainer [23]. Let I and denote the explanation for event and the original temporal graph, respectively. Fidelity measures how valid and faithful the explanations are to the model's original prediction. If the original prediction is positive, then an explanation leading to an increase in the model's prediction logit is considered to be more faithful and valid and vice versa. Fidelity is defined as Fid Gixp) = 1(Y][e] = 1)( - [[]]le)) + [Yrlec] = ()([())(<] - (e)) Sparsity is defined as Sparsity = 19 (/ where ((e) denotes the computational graph of event An ideal explanation should be compact and succinct, therefore,
7

---

Table I: ACC-AUC of TempME and baselines over six datasets and three base models. The AUC values are computed over sparsity levels between and 0.3 the interval of 0.02. The best result is in bold and second best is underlined.
Wikipedia
Reddit
UCI
Enron
USL.gii
Can.Parl.
Random
70.91=1003
81.97=0.92
54.51=00.52
48.94+1.28
54.24+1.34
51.66=2.26
ATTN
77.1110.01
86.80.1.001
27.25.10.01
68.2810.01
62.24.10.00
79.92.10001
TGN TGAT
Grad-CAM
83.11+0.01
90.29+0.01
26.06+00.01
19.93+0.01
78.98+0.01
50.42+0.01
GNNExplainer
84.3410.116
89.4410.56
62.38:10.46
77.82+0.88
89.42::0.00
80.59=0.58
PGExplainer
84.26.10.78
92.91
59.47.11.68
62.3713.82
91.42.10.94
75.92.1.11
TGNNExplainer
85,74+00.56
95.73+0.36
68.26++2.22
8,902+1.94
90.3740084
80.67=1,49
TempME
+5.51+0055
96.69+0.38
76.47++0.80
81885+0.26
96.10++.20
84.48 0.97
Random
91.90.11.42
91,4
87.15.12.23
82.72.1.24
72.3111264
76.43
ATTN
93,28+00.01
93.81+0.01
83,24+0.01
83.57+0.01
75.62+00.01
79.38=0.01
Grad-CAM
93,46110.01
92.6010.00
87.51=0.011
81.1240.01
81.46.
77.19=0.01
GNNExplainer
95.62++0.53
05.5
94.68+0.42
88.61+0.50
82.91+0.46
83.32:00644
PGExplainer
94,28.10.84
94.42.10.36
92.3910085
88.3411.24
90.62.10.75
88.4611.42
TGNNExplainer
93.51++0.88
96.21+0.47
94.24++0.52
90.32+0.82
90.40++0.83
84.70=1.119
TemmME
95.80:10.42
98.661..80
96.34:10.00
92.64:0.27
9..3
90.63=0.72
Random
77.31+2.37
85.08
13.56:11277
64.07=0.86
85.54++0.3
87.79=0.51
Graph
Grad-CAM
76.63:10.01
84.4410.41
82.64.10.01
72.5010.00
88 88.98.10.01
85.8010.01
GNNExplainer
89.21:10.63
95.10:0..36
61.02:0.37
74.2340.11
89.67:0.35
92.28=0.10
PGExplainer
85.19:11.24
92.46.10.22
6.076.11.06
75.39.10.3
92.37110110
90.6310.22
TGNNExplainer
87.69++0.86
95.82++0.73
80.47+0.87
8188=+0.55
93.04++0455
93.78=0.74
TempME
90.15:10.30
95.05510.19
87.06.10.12
79.69-0.33
95.00110.16
05.9
higher fidelity with lower Sparsity denotes a better explanation performance. Besides, we further adopt the ACC-AUC metric, which is the AUC value of the proportion of generated explanations that have the same predicted label by the base model over sparsity levels from to 0.3.
Fidelty
Fidelky
Fideliy
Grad CAM
CriciCa GNNErstane
Chinxppaane mer
-22
PGEsppaaa
PGT eoreeseee
TGiNNE
To
-20
TeeooE
Sparsity
Sparsily
[a] TGAT
(b) TGN
(c) GraphMixer
Figure 3:
Curves Wikipedia dataset with different base models
Results. Table shows the explanation performance of TempME and other baselines w.E. ACC-AUC. TempME outperforms baselines on different datasets and base models in general. Notably, TempME achieves state-of-the-art performance in explaining TGN with strong ACC-AUC results (2 90%) over all six datasets. Specifically, the effectiveness of TempME is consistent across datasets with and without attributes, whereas the performance of baseline models exhibits considerable variation. For example, ATTN and Grad-CAM work well on datasets with rich attributes, e.g. Wikipedia and Reddit, while may yield poor performances on unattributed datasets. Therefore, events with large gradients or attention values are not sufficient to explain the decision-making logic of the base model.
Figure 3 demonstrates the Fidelity- curves of TempME and compared baselines on Wikipedia with different base models. From Figure 3. we observe that TempME surpasses the baselines in terms of explanation fidelity, especially with low sparsity level. In addition, it reveals that the optimal sparsity level varies among different base models. For TGAT, increasing sparsity initially diminishes and later enhances the general fidelity. Conversely, for TGN and GraphMixer, increasing sparsity consistently improves fidelity. These findings indicate that TGAT gives priority to a narrow subset (e.g., 1%) of historical events, while TGN and GraphMixer rely wider range of historical events.
Cohesiveness. To evaluate the cohesive level of the explanations, we propose the following metric:
Cohesiveness
Σ
Σ
cos(
1
Lj [[ ~ me)s
(8)
AT
exp
e,gg
e, ie

---

where AT means the time duration in the computational graph G(e), 1(e; ~ e₁) in- dicates whether e is spatially adjacent to e,. Meanwhile, temporally proximate event pairs are assigned with larger weights of cos(14, 11/AT). A higher level of cohesive- ness indicates a more cohesive explanation. From Table 2, we observe that ATTN and Grad-CAM excel in generating cohesive explanations compared to learning-based explainers. e,g., GNNExplainer, TGNNExplainer. However, TempME still surpasses all baselines and achieves the highest cohesiveness levels, primarily due to its ability to extract and utilize self- connected motifs, allowing it to generate explanations that are both coherent and cohesive. Efficiency Evaluation. We empirically investigate the effi- ciency of TempME in terms of the inference time for gener- ating one explanation and report the results for Wikipedia and Reddit on TGAT in Table 3, where the averages are
Table 2: Cohesiveness evaluation on Reddit and UCI with TGAT.
Reddit
UCI
calculated across all test events. GNNExplainer and TGN-
ATTN
0.0502
0.0708
NExplainer optimize explanations individually for each instance, making them less efficient. Notably, TGNNEX- plainer is particularly time-consuming due to its reliance on the MCTS algorithm. In contrast, TempME trains a generative model using historical events, which allows for generalization to future unseen events. As a result, TempME demonstrates high efficiency and fast inference.
Grad-CAM
0.0422
0.0722
GNNExplainer
0.0270
0.0337
PGExplainer
0.0233
0.0332
TGNNExplainer
0.0397
0.0538
TempME
0.0574
0.0749
Table 3: Inference time (seconds) of Table 4: Link prediction results (Average Precision) of one explanation for TGAT
base models with Motif Embedding (ME)
Wikipedia
Reddit
UCT
Enron
USLegii
Can.Parl.
Random
0.02:20.06
0.03:0009
TGAT
76.28
65.68
72.35
65.18
ATTIN
0.02:10.00
0.04:10.00
TGAT+ME
83.65(77a77)
68.37
(12.09)
95.31 (122.00)
(1135(111:17))
Grad CAM
0.03:10.00
0.04:10.00
TGN
75.82
76.40
77.28
64.23
GNNExplainer
PGExplainer
0.08++0.01
8.24+40.26
10.444-0.77
0.08+0001
TGN+ME
77.46 77.46(11.64)
(10.77))
(1.90(1).02)
79.46 (115.28)
TGNNExplainer
26.87::3.71
83,70:116.44
GraphMixer
89.13
69.42
66.71
76.98
TempMM
0.13:00.02
0.15::0.02
ME 90.11 (70.88)
(0.13(10.71)
81.42
(16.7)
(10.71)
79.33
Motif-enhanced Link Prediction. The extracted motifs can not only be used to generate explanations but also boost the performance of TGNNs. Let m, denote the motif embedding generated by the Temporal Motif Encoder (Eq. 3) and .M is the temporal motif set around the node of interest. We aggregate all these motif embeddings using Σiem mr m and concatenate it with the node representations before the final MLP layer in the base model. The performance of base models on link prediction with and without Motif Embeddings (ME) is shown in Table 4. Motif Embedding provides augmenting information for link prediction and generally improves the performance of base models. Notably, TGAT achieves substantial boost, with an Average Precision of 95.31% on USLegis, surpassing the performance of state-of-the-art models on USLegis [72, 73]. More results given in Appendix E.3.
We analyze the hyperparameter sensitivity and the effect of prior distributions used in TempME, including the number of temporal motifs C, the number of events in the motifs 1, and the prior belief about the explanation volume p. The results are illustrated in Figure 4.
Ablation Studies.
Firstly, when using smaller mo- tifs (e.g., = 2). TempME achieves comparable explanation accuracy when a sufficient num- ber of motifs are sampled. How- ever, the accuracy plateaus with fewer temporal motif' when / 3 or 1 4. Unfortunately, there are only three equivalence classes for temporal motifs with only two events, limiting the di- versity of perspectives in expla- nations. Following previous anal- ysis on temporal motifs [52, 22,
Accurso/13
ACC AUC
Wilpedal Wilpedaa
Colans: metiodoo
LG3O0
Pibr Ditt Exylin
LC3Kd)
16
64
[s] Number of Motiff
[b] Prior belif the explanation volume
Figure 4: (a) Hyperparameter sensitivity of number of temporal motifs C' and motif length (b) Comparison between uniform and empirical prior distribution in terms of ACC-AUC over sparsity
levels from 0 to 0.3.

---

24], we suggest considering temporal motif's with up to 3 events in the explanation task for the sake of algorithmic efficiency. Secondly. TempME achieves the highest ACC-AUC when the prior belief of the explanation volume is in the range of [0.3, 0.5]. Notably, TempME performs better with empirical prior distribution when p is relatively small, resulting sparser and more compact explanations. This improvement can be attributed to the incorporation of the null model, which highlights temporal motifs that differ significantly in frequency from the null model. Figure 4 (b) verifies the rationality and effectiveness of the empirical prior distribution in TempME. Additional insight into the role of the null model in explanation generation can be found in the explanation visualizations in Appendix E.5.
It is worth noting that when is close to 1, uniform prior distri- bution leads to deterministic ex- istences of all temporal motifs while empirical prior distribution pushes the generated explanations towards the null model, which forms the reason for the ACC- AUC difference of empirical and uniform as p approaches 1.
Table 5: Ablation studies on the main components of TempME in terms of the explanation ACC-AUC Wikipedia.
TGAT
TGN
GraphMixer
TempME
10.53
95.80 0.42
9..1510.30
Tempora Moni Eñcöder
w/ GCN
83.26.10.70
94.62-0.34
88.62110.55
w/ GAT
84.37=0063
95,46=0.73
88.59=0.88
w/ Adaptive Pooling
85,24=:0.46
95.73=0.27
90.15=0.277
w/o Event Anonymization
81.47.11.14
93.77-0.52
88. 38.32.10.93
w/o Time Encoding
79.42-10.82
92.64=070
87,90+0.86
Loss function
We further conduct ablation stud- ies on the main components of
w/ uniform
85.60+00.75
94.60=0.38
87.46+0.71
TempME. We report the explanation ACC-AUC on Wikipedia in Table 5. Specifically, we first replace the GINE convolution with GCN and GAT and replace the mean-pooling with adaptive pooling in the Temporal Motif Encoder. Then we iteratively remove event anonymization and time encoding in the creation of event features before they are fed into the Temporal Motif Encoder (Eq.3) Results in Table 5 demonstrate that all the above variants lead to performance degradation. Moreover, the Time Encoding results in a more severe performance drop across three base models. We further evaluate the effectiveness of empirical prior distribution by comparing it with uniform prior distribution. In both prior distributions, the prior belief on the explanation size p is set to 0.3. We report the best results in Table 5. We observe that the empirical prior distribution gains performance boost across three base models, demonstrating the importance of the null model in identifying the most significant motifs.
Conclusion and Broader Impacts
In this work, we present TempME, novel explanation framework for temporal graph neural networks. Utilizing the power tool of temporal motifs and the information bottleneck principle, TempME is capable of identifying the historical events that the most contributing to the predictions made by TGNNs. The success of TempME bridges the gap in explainability research on temporal GNNs and points out worth-exploring directions for future research. For instance, TempME be deployed to analyze the predictive behavior of different models, screen effective models that can capture important patterns, and online services to improve the reliability of temporal predictions.
By enabling the generation of explainable predictions and insights, temporal GNNs can enhance decision-make making processes in critical domains such as healthcare, finance, and social networks. Improved interpretability can foster trust and accountability, making temporal GNNs more accessible to end-users and policymakers. However, it is crucial to ensure that the explanations provided by the models are fair, unbiased, and transparent. Moreover, ethical considerations, such as privacy preservation, should be addressed protect individuals' sensitive information during the analysis of temporal graphs.
References
[1] Yanbang Wang, Yen-Yu Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. arXiv preprint arXiv:2101.055 2021.
[2] Yao Zhang, Yun Xiong, Dongsheng Li, Caihua Shan, Kan Ren, and Yangyong Zhu. Cope: modeling continuous propagation and evolution interaction graph. In Proceedings of the 30th
10

---

ACM International Conference on Information & Knowledge Management, pages 2627-2636, 2021.
[3] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. arXiv preprint arXiv:2002.07962 2020.
[4] Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006. 10637, 2020.
[5] Weilin Cong. Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do really need complicated model architectures for temporal networks? arXiv preprint ar3iv: 1636, 2023.
[6] Ming Jin, Yuan- Yuan-Fang Li, and Shirui Pan. Neural temporal walks: Motif-aware representation learning continuous-time dynamic graphs. In Advances in Neural Information Processing Systems, 2022.
[7] Amauri Souza, Diego Mesquita, Samuel Kaski, and Vikas Garg. Provably expressive temporal graph networks. Advances in Neural Information Processing Systems, 15:32257-33269, 2022.
[8] Jiaxuan You. Tianyu Du, and Jure Leskovec. Roland: graph learning framework for dynamic graphs. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2358 2366, 2022.
[9] Ismini Psychoula, Andreas Gutmann, Pradip Mainali, Sharon H Lee, Paul Dunphy, and Fabien Petitcolas. Explainable machine learning for fraud detection. Computer, 54(10)):9-59, 2021.
[10] Duygu Sinane, Umut Demirezen, and Seref Sagıroğlu. Explainable credit card fraud detection with image conversion. ADCAJ: Advances in Distributed Computing and Artificial Intelligence Journal, 10(1):63-76, 2021.
[11] Julia Amann, Alessandro Blasimme, Effy Vayena, Dietmar Frey, Vince Madai, and Pre- cise4Q Consortium. Explainability for artificial intelligence in healthcare: a multidisciplinary perspective. BMC medical informaties and decision making, 20:1-9, 2020.
[12] Christine M Cutillo, Karlie Sharma, Luca Foschini, Shinjini Kundu, Maxine Mackintosh. Kenneth D Mandl, and MI in Healthcare Workshop Working Group Beck Tyler Collier Elaine Colvis Christine Gersing Kenneth 1 Gordon Valery Jensen Roxanne Shabestari Behrouz 9 Southall Noel 1. Machine intelligence in explainability, usability, and transparency. NPJ digital medicine, 3(1):47, 2020.
on trustworthiness,
[13] Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
[14] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 1116966666311 2020.
[15] Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. CoRR, abs/1905 13686, 2019.
[16] Hao Yuan, Haiyang Yu, Jie Wang, Kang I.i, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In International Conference on Machine Learning, pages 12241-12252. PMLR, 2021.
[17] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In ICML, volume 70, pages 3319-3328, 2017.
[18] Anonymous. Dag matters! gflownets enhanced explainer for graph neural networks. In Openreview, 2022.
[19] Xiang Wang, Yingxin Wu, An Zhang, Fuli Feng, Xiangnan He, and Tat-Seng Chua. Reinforced causal explainer for graph neural networks. IEEE Trans. Pattern Anal. Mach. Intell., 2022.
11

---

[20] Zhen Han, Peng Chen, Yunpu Ma, and Volker Tresp. Explainable subgraph reasoning for forecasting on temporal knowledge graphs. In International Conference on Learning Represen- lations, 2021.
[21] Wenchong He, Minh N Vu, Zhe Jiang, and My T Thai, An explainer for temporal graph neural networks. In GLOBECOM 2022-2022 IEEE Global Communications Conference, pages 0384-6389 IEEE, 2022.
[22] Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs in time-dependent networks. Journal of Statistical Mechanics: Theory and Experiment, 2011(11):PI 1005, 2011.
[23] Wenwen Xia, Mincai Lai, Caihua Shan, Yao Zhang, Xinnan Dai, Xiang Li, and Dongsheng Li. Explaining temporal graph models through an explorer-navigator framework. In The Eleventh International Conference on Learning Representations.
[24] Ashwin Paranjape, Austin R Benson, and Jure Leskovec. Motifs in temporal networks. In Proceedings of the tenth ACM international conference on web search and data mining, pages 601-610, 2017.
[25] Jan Overgoor, Austin Benson, and Johan Ugander. Choosing to grow a graph: modeling network formation as discrete choice. In The World Wide Web Conference, pages 4409-1420, 2019.
[26] Shuang Li, Mingquan Feng, Lu Wang, Abdelmajid Essofi, Yufeng Cao, Junchi Yan, and Le Song. Explaining point processes by learning interpretable temporal logic rules. In International Conference on Learning Representations, 2022.
[27] Alexei Vázquez. Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. Physical Review E, 67(5):056104 004,00614444 2003.
[28] Jari Saramäki and Kimmo Kaski. Scale-free networks generated by random walkers. Physica A: Statistical Mechanics and its Applications, 341:80-86, 2004.
[29] Fragkiskos Papadopoulos, Maksim Kitsak, M Ángeles Serrano, Marián Boguná, and Dmitri Krioukov. Popularity versus similarity in growing networks. Nature, 489(7417):537-540 2012.
[30] Jure Leskovee, Lars Backstrom, Ravi Kumar, and Andrew Tomkins. Microscopic evolution of social networks. In Proceedings of the 14th ACM SIGKDD international conference Knowledge discovery and data mining, pages 462-470, 2008
[31] Matthew O Jackson and Brian W Rogers. Meeting strangers and friends of friends: How random social networks? American Economic Review, 97(3):890-915, 2007.
[32] Seungbae Kim, Jyun- Yu Jiang, Masaki Nakada, Jinyoung Han, and Wei Wang. Multimodal post attentive profiling for influencer marketing. In Proceedings of The Web Conference 2020, pages 2878 22844 2020.
[33] Albert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509-512 1999.
[34] Emily M Jin, Michelle Girvan, and Mark EJ Newman, Structure of growing social networks. Physical review E, 64(4):046132, 2001.
[35] Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Naday Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594))824-887, 2002.
[36] Zahra Razaghi Moghadam Kashani. Hayedeh Ahrabian, Elahe Elahi, Abbas Nowzari-Dalini, Elnaz Saberi Ansari, Sahar Asadi, Shahin Mohammadi, Falk Schreiber, and Ali Masoudi-Neeie Kavosh: a new algorithm for finding network motifs. BMC bioinformatics, 10(1):1-12, 2009.
[37] Phillip F. Pope, Soheil Kolouri, Mohammad Rostami, Charles E. Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In CVPR, pages 10772-10781, 2019.
12

---

[38] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, Dawei Yin, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. CoRR, abs/2001.06216. 2020.
[39] Michael Sejr Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting graph neural networks for NLP with differentiable edge masking. CoRR, abs/2010.00577, 2020.
[40] Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T. Schütt, Klaus- Robert Mülllr, and Grégoire Montavon, Higher-order explanations of graph neural networks via relevant walks. IEEE Trans. Pattern Anal. Mach. Intell., 2022.
[41] Minh N. Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. In NeurIPS, 2020.
[42] Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pages 15524-15543. PMLR, 2022.
[43] Xiaoqi Wang and Han-Wa Wei Shen. Gnninterpreter: A probabilistic generative model-level explanation for graph neural networks. arXiv preprint arXiv:2209.07924 2022.
[44] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 430 438, 2020.
[45] Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning enhanced explainer for graph neural networks. Advances in Neural Information Processing Systems, 34:22523-22533, 2021.
[46] Chao Chen, Haoyu Geng, Nianzu Yang. Xiaokang Yang, and Junchi Yan. Easydgl: Encode, train and interpret for continuous-time dynamic graph learning, arXiv preprint arXiv:2303. 12341, 2023.
[47] Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 66366 2016.
[48] Chunyao Song, Tingjian Ge, Cindy Chen, and Jie Wang. Event pattern matching over graph streams. Proceedings of the VLDB Endowment, 8(4):413-424, 2014.
[49] Yuriy Hulovatyy, Huili Chen, and Tijana Milenković. Exploring the structure and function of temporal networks with dynamic graphlets. Bioinformatics, 31(12)x111-ii88 2015.
[50] Nadav Kashtan, Shalev Itzkovitz, Ron Milo, and Uri Alon. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics, 20(11):1746- 1758, 2004.
[51] Falk Schreiber and Henning Schwöbbermeyer. Mavisto: a tool for the exploration of network motifs. Bioinformatics, 21(17):3572-3574 2005.
[52] Penghang Liu, Valerio Guarrasi, and Ahmet Erdem Sanyüce. Temporal network motifs: Models, limitations, evaluation. IEEE Transactions on Knowledge and Data Fngineering 35(1):945-957, 2021.
[53] Paolo Bajardi, Alain Barrat, Fabrizio Natale, Lara Savini, and Vittoria Colizza. Dynamical patterns of cattle trade movements. PloS one, 6(5)e 2011.
[54] Yanlei Yu, Zhiwu Lu, Jiajun Liu, Guoping Zhao, and Ji-rong Wen. Rum: Network representation learning using motifs. In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 1382-1393. IEFF, 2019.
[55] Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: a motif-based graph convolutional network for directed graphs. 2018 IEEE Data Science Workshop (DSW), pages 225-228. IEEE, 2018
13

---

[56] Lei Wang, Jing Ren. Bo Xu, Jianxin Li, Wei Luo, and Feng Xia. Model: Motif- deep feature learning for link prediction. IEEE Transactions on Computational Social Systems, 7(2):503-516, 2020.
[57] Purnamrita Sarkar, Deepayan Chakrabarti, and Michael Jordan, Nonparametric link prediction in dynamic networks. arXiv preprint arXiv: 1220663394 2012.
[58] Jingjing Wang, Yanhao Wang, Wenjun Jiang, Yuchen Li, and Kian-Lee Tan. Efficient sam- pling algorithms for approximate temporal motif counting. In Proceedings of the 29th ACM international conference on information & knowledge management, pages 1505-1514, 2020.
[59] Mike Schuster and Kuldip K Paliwal. Bidirectional recurrent neural networks. IEEE transactions on Signal Processing, 45(11):266 (5(11):26732668) 1997.
[60] Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics, 200:108-122 -208 2016.
[61] Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International conference on machine learning, pages 2186-2195, PMLR, 2018.
[62] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: trxiv:/8100008220 2018.
[63] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, Yoshua Bengio, al. Graph attention networks. stat, (050(20):10-4555)) 2017.
[64] Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 5470-5477, 200.0.....000.
[65] Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint
2016.
[66] Siqi Miao, Yunan Luo, Mia Liu, and Pan Li. Interpretable geometric deep learning via learnable randomness injection. arXiv preprint arXiv:2210. 16966, 2022.
[67] Paolo Bajardi, Alain Barrat, Fabrizio Natale, Lara Savini, and Vittoria Colizza. Dynamical patterns of cattle trade movements. PloS one, 6(5)ee19869, 2011.
[68] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. " "why should trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135-1144, 2016.
[69] Ruth C Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful perturbation. In Proceedings of the IEEE international conference on computer vision, pages 9429-3437, 2017.
[70] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[71] Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection, 2014.
[72] Farimah Poursafaei, Shenyang Huang, Kellin Pelrine, and Reihanch Rabbany. Towards better evaluation for dynamic link prediction. arXiv preprint arXiv:2207.1012. 2022.
[73] Le Yu. Leilei Sun, Bowen Du and Weifeng Lv. Towards better dynamic graph learning: New architecture and unified library. arXiv preprint arXiv:2303. 13047, 2023.
[74] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks, arXiv preprint arXiv: 1905. 12265, 2019.
14

---

[75] Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1269-1278, 2019.
[76] James W Pennebaker, Martha E Francis, and Roger J Booth. Linguistic inquiry and word count: Liwe 2001. Mahway: Lawrence Erlbaum Associates, 71(2001):2001, 2001.
[77] Jitesh Shetty and Jafar Adibi. The enron email dataset database schema and brief statistical report. Information sciences institute technical report, University of Southern California, 1(1):120-128, 2004.
[78] Pietro Panzarasa, Tore Opsahl, and Kathleen M Carley, Patterns and dynamics of users' behavior and interaction: Network analysis of an online community, Journal of the American Society for Information Science and Technology, 60(5):91 1 1-932, 2009.
[79] Shenyang Huang. Yasmeen Hitti, Guillaume Rabusseau, and Reihaneh Rabbany. Laplacian change point detection for dynamic graphs. In Proceedings of the 26th ACM SIGKDD Interna- tional Conference Knowledge Discovery & Data Mining, pages 349-358, 2020.
[80] Ily O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung. Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al. Mlp- mixer: An all-mlp architecture for vision. Advances in neural information processing systems, 34:24261-24272, 2021.
15

---

A Notation Table
The main notations used throughout this paper are summarized in Table
Table 6: Summary of the notations
Notation
Description
(())
Continuous-tine dynamic graphs Set of nodes that occur before timestamp t Set of events (intcractions) that occur before timestamp Interaction event eş between node uy and Uy at time with attribute as Temporal Graph Neural Network to explained (base model) Binary prediction of event made by the base model f
V(t)
(t)
ek
(Uk, Uk: tk (x)
Yi cl
(())
Computational graph of event e Explanation graph for the prediction of event
Sosp
Mutual information function
SOle
Probability output of the model f on the event Explanation budget on the size
K
A temporal motif instance Maximum number of nodes in temporal motif instances
Number of events in each temporal motif instance I-dimensional structural feature of the event Set of temporal motif instances starting from the node u Number of temporal motif instances sampled for each node of interest Associated feature of node p
h(e)
Ma
C X,
apg T(-)
Associated feature of event Epg that happens between node p and node g
Time encoder Motif-level embedding of Importance score of ! Mask for sampled from Bernoulli(p))
mı E [0 aj Bernoulli(pr)
M
Set of the extracted temporal motif's Set of explanatory temporal motifs Posterior distribution of MMexp given .M with learnable parameters ø
Mexp P MM ((Mex))
Prior distribution of Mexp
Prior belief about the explanation volume
B Temporal Motif
Given explanation query of the future link prediction between node i and node j at time to. consider the temporal motifs around node and node to explain which motifs contribute to the model's prediction. We first extract two sets of temporal motifs starting from node and from node j at time fo, respectively. Since we consider the effect of historical events, we constrain events to reverse over time direction in each temporal motif.
Definition. Given temporal graph and node ug time to. sequence of events, denotes as I {(u,, U1, t2), (M2, V2, f2),... (u,, Ut, tt)} is a n-node, l-length, 8 5-duration Retrospective Temporal Motif of node un if the events reversely time ordered within a 5 duration, i.e., > t1 > t2 > ti and to t; < 6, such that u, = un and the induced subgraph is connected and contains n nodes.
There can be collection of event sequences that satisfy the above definition. Intuitively, two motif instances are equivalent if the order of the events is the same, despite the absolute time difference.
Definition. Two temporal motif instances In and 12 are equivalent if they have the same topology and their events occur in the same order, denoted as I Iz.
We use {0, 1,.. to represent each temporal motif with events. Each pair of digits denotes an event between the node represented by the first digit and the other node represented by the second digit. The first digit pair
1} to denote the nodes in the motif and use I digit pairs to construct 21-digit
16

---

is always 01, denoting that the first event occurred between node 0 and node 1. The sequence of digit pairs and the digit number of each node follow the chronological order in each temporal motif. Consider the undirected setting, the examples of temporal motifs with at most 3 nodes and 3 events and their associated digital representations are shown in Figure 5 (a).
Source node interst
0102
010201
010212
010202
Wikipedia
Wikipedia (Null)
Reddit
Reddit (Null)
UCI
0112
011201
011212
011202
UCI (Null)
/2
0101
010101
010112
010102
Dataset
(a)
(b)
Figure 5: (a) Visualization of temporal motifs with up to 3 nodes and 3 events and the associated 21-digi (b) The proportion of sampled temporal motif equivalence classes in Wikipedia, Reddit,
UCI and their corresponding null models (only subset of the most frequent motifs are displayed)
C Theoretical Proof
The information bottleneck is technique to find the best tradeoff between accuracy and compression. Given a temporal graph 9 and a prediction Yy[e] over the future event e made by model f. The goal of the explanation is to extract a compressed but explanatory subgraph G2sp from the original graph g, such that Geep plays a pivotal role in leading the target prediction Yy(e). It can be formulated as an information bottleneck problem as follows.
min II Yyle)) + SI ((e)). s.t.
g S K,
(9)
where G(e) denotes the computational graph of event e, and K is constraint on the explanation size (i.e., number of historical events selected into 9xpp)
C.1 Accuracy Term: Cross Entropy
The first term in Eq. 9 can be approximated by the cross entropy between the model's prediction given Geep and the target prediction Yj (c).
min -I Yyle)) = min [Y (axp) - HY)l
+ min HYylec]
(exp) = min
Σ
-1 = log(f((( (10)
001
where H(-) is the entropy function and H(yyle)) constant during the explanation stage.
C.2 Variational Bounds for Information Bottleneck
Let M,, and M, denote the sets of sampled temporal motif instances surrounding the node u and node v. We propose to formulate the second term in Eq. 9 as the mutual information between M and Maxp. where M = M,, U M, denotes the set of all extracted motifs and Maxp is the set of explanatory temporal motifs, since they are the essential building blocks of ((e) and Goxp. We introduce @(Meex)) as variational approximation for the marginal distribution IP PPMeep)) and derive
17

---

the variational bounds for the second term in Eq. 9.
log P(Mexp MM P(Maxp)
Mexp) Br(M.Mop)
P(Moxp M) MMQ((Msp))
BP(M.MOTT)
log ((Mexp)) (PMMep))((MMM)) (PMopx))
(1I)
P(Mexp MM)
= -EP(M,Mor)
log Q(M
DKL (P(Maap) @(Max)))
S EP(M) (PL
M); ((Mox)))].
Let pr, denote the importance score of the motif instance I; E M,, which measures the probability of motif instance I being sampled as explanatory temporal motifs in Maxp. On average, the proportion
of temporal motif instances being selected into Mexp is -i,em PT, Let (U1.-.. .UT denote
M
equivalence classes that occur in M. Thus, q: Eiyev, Ptz denotes the proportion of the temporal Ei
motifs that belong to equivalence class U, MMxp. The prior belief about the average probability of motif being explanatory is p. Assume that in the null model, the proportion of the temporal motifs belonging to U, is my. Then we have
I (M: s (KLL)) IM); ((Mxx))
Be(M)
Σ UI.=I1,-.T
P(U, MM
P(U, .M), Q(U,)
+ (1 5) log(
1-8
T-
(12)
T
1
log sqi
-ee 8) log
9:
p
pmn
Combining Eq. and Eq. 12, we obtain the following optimization objective:
min E (t))(()
- [(Y][e) log(f(G)) :(11 - ss log I-p +
1 1
> qe log 84
) (13)
pm;
c=0,1
where á denotes learnable parameters in TempME, / is regularization coefficient.
D Proposed Approach
D.1
Null Model
The analysis of temporal motif distribution is typically presented in terms of a null model [53, 22]. A null model essentially randomized version of the empirical network, generated by shuffling or randomizing certain properties while preserving some structural aspects of the original graph. The null model serves as baseline against which the observed motif distribution can be compared, allowing us to evaluate the presence of meaningful patterns and deviations from randomness. By comparing the motif distribution the empirical network with that of the null model, we can distinguish between motif' that arise due non-random structural temporal features of the network from those that are simply a result of random processes. Following prior works on the null model [67, 22], utilize the most obvious null model in this work, where the event order is randomly shuffled. Formally, a temporal graph G = (V(t), {t) can be defined as a sequence of interaction events, i.e.. {uu, Us J.N where 14 and 8/ are two nodes interacting time t,. We generate permutation a E 5xx, where N refers to the number of interaction events within the temporal graph G. ordered graph G. is then constructed by Go (u,, vi, bo(s) )N In this way, the topological structure and degree spectrum of the temporal network are kept, while the temporal correlations are lost.
D.2 Equivalence Class
Two temporal motifs with the same digital representations are equivalent according to Definition With the 2(-digit representations, can easily classify all temporal motif instances according to
18

---

their equivalence class relations. For example, with up to 3 nodes and 3 events, there are twelve equivalence classes as shown in Figure 5 (a). In essence, the digital representation provides an efficient way to grow a motif. For instance, in Figure 5 (a), the last three columns of each row can be considered as the results of generating a new interaction event based on the motif in the first column. When it comes to motifs with 4 events, we attach new digit pairs to motifs with 3 events. For example, the next digit pair is one in {01, 02, 03, 12, 13, 23} for the temporal motif assigned with 010201.
Marginal distributions of temporal motifs reveal the governing patterns and provide insights into a better understanding of the dynamics in temporal graphs. To obtain comprehensive knowledge about the distribution of these temporal motifs, we sample a fixed number of temporal motifs around each node temporal graph and the corresponding null model. We compute the average probability of each equivalence class across all nodes and visualize the results in Figure 5 (b). We can observe that the difference between the empirical distribution of the temporal motifs and that of its randomized version varies significantly across different datasets. For example, the proportion of motif 010101, which corresponds to repeated interactions between two nodes, deviates significantly from randomness in Wikipedia, indicating its importance to the underlying dynamics. Moreover, results on the null model reveal that the motif 0112 is mostly a natural result of random processes.
D.3 Efficient Sampling and Complexity Anlaysis
The temporal motif sampling algorithm is given in Alg. 2. The brute-force implementation of Alg. 2 results in the time complexity of (CT)), which can be further decreased with tree-structured sam-1 pling. We discuss two cases. Firstly, when
Algorithm 2: Temporal Motif Sampling (E, n, ug to. C)
Node set: S. < {uo}, for 1 S ScSC Event sequence: Te + O) for 1 scsc for 1 to C do
n 2 2+1 1, there is actually no constraint on the number of nodes within each temporal motif. We create a sampling configuration [Ki, k2,,.. .. , 3 satisfying Σ h; = C. It indicates that we sam- ple l events starting from uh at the first step and then sample 22 neighboring events for each of the ky motifs sampled in the previous step. Repeat
for j 1 to I do
Sample one event ej (ug, 24,t4)
from E(S, tz-1)
if [S < n then
S. S. U Uug Us}
L = Le Ej
the step for times and we obtain E'z h; = C
temporal motifs in total. Secondly, if S I (i.e., Alg. 1), we create a sampling configuration
return (Te 1 SSccC]
[Ki, li,,... ... _1,-1] satisfying E K; = C. Similarly, we sample k; neighboring events at the i-th step. We repeat the process for
times and obtain C. temporal motifs with n 1 events in total. For each of the C' temporal motifs, we sample neighboring event for ( - n + 1 times and ensure the number of nodes in each temporal motif is no more than n, which completes the temporal motif to involve I events in total. The upper bound time complexity of the tree-structured sampling is OCC(l n + 2)). Specifically, when n 2 1+ 1, the time complexity is reduced (C). We use the 21-digit to represent the temporal motifs. Two temporal motifs that have the same 21-digit are equivalent. The equivalence classification results in the time complexity of OCC). For event anonymization, we first identify unique node pairs (u,, 0;) that occur in C' temporal motifs and count their occurrence times at each position j, where j = 1, ... .I. Then we utilize the position-awan counts to create the structural features for each event in the temporal motifs. This process results in the time complexity of OCCI).
1-length
On the other hand, the previous TGNNExplainer requires re-searching individually for each given instance. To infer an explanation for a given instance, the time complexity of TGNNExplainer with navigator acceleration is OCNDC), where N is the number of rollouts, D is the expansion depth of each rollout and C' is a constant including inference time of navigator and other operations.
D.4 Model Details
By default, we use GINE [74] as the MESSAGEPPSSING function and Mean-pooling as the READOUT function. GINE convolution adapts GIN convolution to involve edge features follows,
x = ha, ((1 + e) x, +
ReIJ((r, + hog (Fx)))
(14)
JEN(()
19

---

where he, and hag are neural networks. and E,; denote the features of node and edge i, respectively. Eji = (azx II T(t-tzi) || hi(e:)) contains the associated event attributes, time encoding and structural features. Nii) refers to the neighboring edges of node i. Mean-pooling takes the average of the features of all nodes within the graph and outputs motif-level embedding.
E
Experiments
E.1
Dataset
We select six real-world temporal graph datasets to validate the effectiveness of TempME. These six datasets cover a wide range of real-world applications and domains, including social networks, political networks, communication networks, etc. The brief introduction of the six datasets is listed as follows. Data statistics are given in Table 7.
Wikipedia [75] includes edits made to Wikipedia pages within a one-month period. The nodes represent editors and wiki pages, while the edges represent timestamped posting requests. The edge features consist of LIWC-feature vectors [76] derived from the edit texts, each with a length of 172.
Reddit dataset [75] captures activity within subreddits over a span of one month. In this dataset, the nodes represent users or posts, and the edges correspond to timestamped posting requests. The edge features consist of LIWC-feature vectors [76] extracted from the edit texts, with each vector having a length of 172.
Enron [77] is an email correspondence network where the interaction events are emails exchanged among employees of the ENRON energy company over a three-year period. This dataset has attributes.
UCI [78] is an unattributed social network among students of UCL. The datasets record online posts on the University forum with timestamps with the temporal granularity of seconds.
Carl [79] is dynamic political network that tracks the interactions between Canadian Members of Parliament (MPs) spanning the years 2006 2019. Each node in the network represents an MP who represents an electoral district, while the edges are formed when two MPs both vote "yes"
bill. The weight assigned to each edge reflects the number of times an MP has voted "yes" for another MP within a given year.
US Legis [79] focuses on the social interactions among legislators in the Senate through a co-sponsorship graph. The edges in the graph correspond to the frequency with which two congresspersons have jointly sponsored a bill during a specific congressional session. The weight assigned to each edge indicates the number of times such co- co-sponsorship has occurred. The dataset records the interactions within 12 congrcessions.
Table 7: The dataset statistics. Average interaction intensity defined as À = 2 2 /(VIT). where E and V denote the set of interactions and nodes, T is the dataset duration in the unit of seconds.
Datasets
Domains
#Nodes
#Links
Lio Features
Duration
Interaction intensity
Wikipedia
Social Social
9,227
157,474
0&:172
month
1.27
10
Reddit
10,984
672,447
0&172
month
4.57 x 10
Enron
Communication
184
125,235
0&0
month
1.20 x 10-5
UCI
Social
1.999
59,835
0&00
196 days
3.76
10 6
Car.Parl.
Politics
734
74.478
0&&1
14 years
4.95
US Logis
Politics
225
60,396
0&1
12 congresses
None of the used temporal graphs contains node attributes. Wikipedia and Reddit have rich edge attributes. Can.Parl. and US Legis contain a single edge attribute, while Enron and UCI contain no edge attribute. All datasets are publicly available at https:// //g thub. wwtccoom/oooooo Com/fpour/DCCt
E.2 Experimental Setup
Base Model. There are two main categories of Temporal GNNs [7]. One type utilizes local message passing update the time-aware node features (MP-TGNs). The other type aggregates temporal
20

---

walks starting from the nodes of interest and leverages RNNs to learn the sequential information (WA-TGNs). Since we aim at identifying the most explanatory historical events and their joint effects in the form of a temporal motif, we focus on MP-TGNs in this work.
We adopt three popular state-of-the-art temporal GNNs that augment local message passing, TGAT [3], TGN [4] and GraphMixer [5]. TGAT aggregates temporal topolooccal neighborhood features and time-feature interactions with modified self-attention mechanism. TGN incorporates memory module to better store long-term dependencies. Both TGAT and TGN leverage a time encoding function to effectively capture the time-evolving information contained in the interactions. GraphMixer' is one of the newest frameworks that utilize an MLP-Mixer [80]. On the contrary, GraphMixer uses a fixed time encoding function, showing great success and potential.
Configuration. We follow the standard dataset split for temporal graphs [1, 6]. We sort and divide all interaction events by time into three separate sets, corresponding to the training set, validation set and testing set. The split points for the validation set and testing set are 0.75I' and 0.8T, where T' the duration the entire dataset. We keep the inductive setting for all three base models. We mask 10% nodes and the interactions associated with the masked nodes during the training stage. For evaluation, we remove all interactions not associated with the masked nodes, so as to evaluate the inductiveness of temporal GNNs.
Results. Hyperparameters are sufficiently fine-tuned for each base model. The number of attention heads tuned in {1, 2, 3) and the number of layers in {1, 2, 3) for TGAT and TGN. The number of MLPMixer layers is 2 for GraphMixer. The dimension of the time encoding is 100, and the output dimension is 172. The maximum number of epochs is 50. An early stopping strategy is used to mitigate overfitting. The link prediction results (Average Precision) in the inductive setting are shown in Table 8.
Table 8: Link prediction results (Average Precision) of TGAT, TGN and Graph
Wikipedia
Reddit
UCT
Enron
UST.egis
Can.Parl.
TGAT 93,53
96.87
76.28
65.68
72.35
65.18
TGN GraphMixer
97.68
97.52
75.82
76,40
77.28
64.23
96.33
95.38
89.13
69.42
66.71
76.98
There exist some differences between Table 8 and the results in the original paper of GraphMixer. We ascribe the difference to our inductive setting. In the original paper of GraphMixer, they conduct experiments under the transductive learning setting. To keep consistent, follow [73] remove the one-hot encoding of the node identities in GraphMixer to ensure the inductivenss, which potentially results in performance degradation in some cases.
Baselines. We consider the following baselines:
ATTN leverages the internal attention mechanism characterize the importance of each interaction event. The intuition is that events that are assigned with larger attention values are more influential to the model's prediction. We adopt ATTN explain the predictions made by TGAT and TGN, since they both involve attention layers as their building blocks.
Grad-CAM was originally proposed in computer vision to identify the most significant patches in image. [37] proposes to generalize Grad-C
the discrete graph domain. We compute the gradient of the model's output w.z.. event features and take the norm as the importance score for the corresponding event.
GNNExplainer [13] is learning-basee method that optimizes continuous masks for neighboring events upon which a base model makes the prediction. We follow the same setting as proposed in the original paper.
PGExplainer [14] trains a deep neural network that generates continuous masks for the input graph. Event feature is defined as E, (a.l/T(tt t)) (())), the same the one used in our Temporal Motif Encoder (Eq. 3). PGExplainer takes as input the event features and outputs continuous mask for each neighboring event.
httppp//ggtaabbaaesssssselleeees gegiihub..co/yyuee-eBueu 'https://githin http://gthhub.cooyuueeeeeeeeeeee com/yylee-UAA/Dydlll
-eerning-nnnnnne to-ttmmporalggee graphs.
21

---

TGNNExplainer [23] is a searching- based approach that leverages the Monte Carlo Tree Search algorithm explore effective combinations explanatory events. We follow the same training procedure as proposed in the original paper.
Implementation Details. The implementation and training are based on the NVIDIA Tesla V100 32GB GPU with 5,120 CUDA cores and batch size is set as 64. The maximum training epochs is 100. We summarize the search ranges of other main hyperparameters used in TempME in Table
HPC cluster. The learning rate is initially set 1e
Table 9: Search ranges of hyperparameters used in TempME
temporal motifs per node C
Beta /
Prior Belief p
Wikipedia
{20, 30, 40, 50, 60}
(0.2,0.4, 0.6, 0.8, 1]
{0.1, 0.3, 0.4, 0.5) (0.1,0.2,0., 0.4,
Reddit
(20, 60, 80, 100)
0.8
UCI
{20, 30, 40, 50, 60}
(0.2,0.4,06600...,.
{0.2, 03. 0,,,0,,,,4,,,,,,,,,,,,
Enron
{20, 30,,30,40 40, 50, 60}
(0.2,0.4.0660....11
USLegis
{20, 30, 40, 50, 60)
(0.2,0.4,066.08..1
0,2,0,3,04,,,,,,666
Car.Parl.
{20, 40, 50, 60)
(0.200.4.0660.8.1)
{0.2, 0.3, 00,,0,33.0440,,,06600000)
E.3
Motif-enhanced Link Prediction
Table 10 shows the complete results on link prediction enhancement with motif embedding. The performance boosts on Wikipedia and Reddit are relatively limited, due to the exceedingly high performance achieved by base models. However, motif embedding demonstrates the ability to greatly improve the link prediction performance on more challenging datasets, e.g., USLegis, Can. We
Table 10: Link prediction results (Average Precision) of base models with Motif Embedding (ME)
Wikipedia
Reddit
UCI
Enron
USLegis
Can.Parl.
TGAT
93.53
96.87
76.28
65.68
72.35
65.18
TGAT+ME
95.12(11.59)
97.22
83.65(17.37)
68.37 (12.69)
95.31 (122.96)
76.35
TGN
97.68
97.52
75.82
76.40
77.28
64,23
TG
97.68(10.00)
(8.35(10.88)
(1.46()1.61)
75.62(00.78)
83.90(16.62)
(1.46()
GruphMixer
96.33
95.38
89.13
69.42
66.71
76.98
GraphMixer+ME
96.51 (10.18)
(12.43)
90.11 (0.11(10.98)
(10.98)
70.13("0.71)
(1.42((144.1)
79.33(12.38
can also notice that the performance improvement on Enron is not as significant as other datasets. The reason that there are multiple identical interactions in the Enron dataset. On average, each distinct interaction is accompanied by 3.284 exactly identical interactions within this dataset, far more than other datasets. While this phenomenon might be deemed reasonable within the context of email networks (e.g.. the Enron dataset), wherein multiple emails are dispatched to the same recipient at identical timestamps, it is not common phenomenon in other datasets and many real-world scenarios. For consistency with existing literature [22, 24] we restrict the timestamp of the next sampled event strictly earlier than the previous event, which is also a necessary condition of underlying causality between interactions. Consequently, many identical interactions in the Enron dataset are not sampled within a temporal motif, thereby potentially degrading the performance improvement of TempME over this specific dataset. As result, one limitation of TempME is analyzing temporal graphs characterized by high interaction density between the same node pairs at the same timestamp.
E.4 Runtime Evaluation
To empirically verify the time complexity and efficiency of the proposed TempME, we test sampling and encoding runtime w.r.f. number of temporal motifs and length of temporal motifs, as shown in Figure 6. The base model is set as TGAT and the dataset is Reddit, which is a massive and large-scale dataset. Encoding process includes the temporal motif encoding and the following MLP to generate the importance scores. The averages and standard deviations are calculated across all target events. The maximum number of nodes within each temporal motif set to the length of the temporal motifs, i.e., = I. We can make the following observations from Figure 6. (1) The runtime of sampling
22

---

0.3
sampling
sampling encoding
Runtime(s
encoding
Runtime(s (s)
0.2-
0.2
0.1
0.1-
0.0
4
8
16
32
64
2
3
(a) Number of temporal motifs
(b) Length of temporal motifs
Figure 6: (a) Sampling and encoding runtime w.r.t. the number of temporal motif's around each node (b) Sampling and encoding runtime w.t.. length of temporal motifss
much longer than that of the encoding process under the same number of motifs and motif length, especially with a larger number of temporal motifs. (2) The runtime of sampling and encoding approximately in proportion to the length of temporal motifs. The runtime comparison between TempME and baselines shown in Table 3.
E.5
Insights from Explanations
Helcads
LG
-140
Score
Importance
300
A/2
N N UC)
& X
(a) Wikipedia
Figure 7: Occurrence percentages of temporal motifs in empirical graph and its null model (only subset of the most frequent motifs are displayed). The lines represent the average importance score across all instances of motifs within the respective motif class.
The use of an information bottleneck framework in simplistic manner introduce bias that favors specific motifs, potentially leading to the oversight of less frequent yet important temporal patterns. Introducing the null model, on the other hand, has primary impact of shifting the focus from absolute proportions to relative proportions compared to the null model itself. This shift helps alleviate attention toward motifs that offer limited information when evaluated solely based on their frequency. Figure 7 illustrates the visualization of importance scores for temporal motifs and their corresponding occurrence percentages. In both prior distributions, the prior belief p is set to 0.3. The dashed gray line represents an importance score of 0.3. When employing the uniform prior distribution, the model tends assign all interaction-irrelvvann motifs the prior belief p, regardless of their varying occurrence percentages. Conversely, the empirical prior distribution takes the null model into consideration and highlights motifs that convey more information based on their occurrence percentages. Consequently, the empirical prior distribution leads to a higher deviation from the gray horizontal line, while the average importance score remains close the prior belief p. By considering the null model, a more comprehensive analysis becomes possible, encompassing the significance and uniqueness of the observed motifs beyond their raw occurrence probability. For instance, in the Wikipedia dataset, the empirical prior distribution captures the second and fourth motifs with high importance scores, as displayed Figure 7(a). Both motifs exhibit a significant difference in their occurrence probability compared to that in the null model. Conversely, in the UCI dataset, the uniform prior distribution yields a relatively uniform distribution of importance scores across motifs, thereby providing limited information regarding the distinct contributions of these temporal motifs.
23

---

(a) Original temporal graph
(b) Explanation (TGNNEXplainer)
(c) Explanation (Grad-CAM)
(d) Explanation (TempME)
Figure 8: (a) Original temporal graph. (b) Explanation example generated by TGNNExplainer. (c) Explanation example generated by Grad-CAM. (d) Explanation example generated by TempME. The link between the two red nodes is be explained. The explanations (i.e., explanatory edges) highlighted in colors.
Figure 8 shows the explanation examples generated by TGNNExplainer Grad-CAM and TempME on Wikipedia. The base model is TGAT with two layers. Red nodes indicate two ends of the event to be explained. All graphs are constrained within the 2-hop neighbor of the two red nodes. Figure 8(d), different colors represent the different types of temporal motifs the corresponding event contributes to. Compared with TGNNExplainer, TempME works better generating a cohesive explanation. Moreover, the explanation generated by TempME provides additional motif-level insights, thus being more human-intelligible.
F Discussion
Linitation. While employing temporal motifs generate explanations shows promise, several limitations need to be acknowledged. First, the identification of influential motifs relies on the assumption that motifs alone capture the essential temporal dynamics of the graph. However, in complex real-world scenarios, additional factors such external events, context, and user preferences may also contribute significantly to the explanations. Second, the scalability of motif discovery algorithms pose challenges when dealing with large-scale temporal graphs. Finally, the selection of null model may also introduce inductive bias to the desired explanations. Further analysis the null model setting will be one of the future directions.
Broader Impacts. By enabling the generation of explainable predictions and insights, temporal GNNs can enhance decision-makinn processes in critical domains such healtheare, finance. and social networks. Improved interpretability can foster trust and accountability. making temporal GNNs more accessible end-users and policymakers. However, provided by the models are fair, unbiased, and transparent. Moreover, ethical considerations, such as privacy preservation, should be addressed protect individuals' sensitive information during the analysis of temporal graphs.
crucial to ensure that the explanations
Future Works. In the future, several promising directions can advance the use temporal motifs proposed in this work. First, incorporating external context and domain-speciin knowledge can enhance the explanatory power of motif-based explanations. This can involve integrating external data sources, leveraging domain expertise, or considering multi-modal information. Moreover, developing scalable motif discovery algorithms capable of handling massive temporal graphs will facilitate the applicability of motif- based explanations in real-world scenarios.
24


Reviews:
[{"review_id": "OqumP9LaCr", "reviewer": "Reviewer_uwpb", "summary": "The Explainability of TGNN is essential for human understanding of model prediction results. This paper proposed a framework, TempME, to construct meaningful, cohesive explanations by utilizing temporal motifs. The framework consists of temporal motif extraction, motif encoder, information-bottleneck-based importance score generator, and an explanation process. Benefiting from the information bottleneck principle, TempME can balance the explanation accuracy and compression. Experiments on six real-world temporal graph datasets were conducted with three TGNN backbones. The result shows that the selected temporal motifs not only reason the predictions of the backbones but also enhance their link prediction accuracy.", "questions": "As stated in the weakness.", "limitations": "The proposed method assumed temporal motifs can capture the dynamics of the graph, which might not hold for real-world scenarios. For instance, external events or user preferences can also affect the explanations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-- Connecting the information bottleneck principle with the temporal motif explanation task is considered novel.\n\n-- The experiment results are promising. The TempME achieves up to an 8.21% increase in explanation accuracy across real-world datasets. Besides, up to 22.96% improvement in the performance of TGNNs shows the effectiveness of discovered temporal motifs.\n\n-- The author provides comprehensive theoretical analysis and extensive experiments.\n\n-- The TempME is efficient in terms of the inference time for producing explanations.\n\n-- The paper is well-organized and easy to follow.\n", "weaknesses": "-- The performance of the tempME might be susceptible to temporal motif extractions in the first stage, but fewer discussions on other motif mining algorithms.\n\n-- The proposed method assumed temporal motifs can capture the dynamics of the graph, which might not hold for real-world scenarios. For instance, external events or user preferences can also affect the explanations.\n\n-- The ACC-AUC of TempME in Table 1. outperforms baselines in most cases. However, the performance improvements of the Enron dataset are not significant. The reviewer also finds the results of the Enron dataset in Table 4. show less improvement in the performance of TGNN models with motif embedding. It would be better to investigate the limitation of the proposed method.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback and positive comments on the novelty, experimental results, theoretical analysis, and paper writing in this work. We address below the potential concerns.\n\n>The performance of TempME might be susceptible to temporal motif extraction in the first stage. Discussions on other motif mining algorithms.\n\nThanks for bringing this up. Exact motif counting results in high memory and large computation complexity. Therefore, most other motif extraction algorithms (e.g. MAVisto, Kavosh) mainly aim to reduce approximation error of motif counting with less memory and CPU time. However, in TempME, the target of motif extraction in the first stage is to collect a candidate set of expressive temporal motifs, instead of approximating the exact motif counting. Therefore, the performance of TempME is not sensitive to the temporal motif extraction algorithms. We will add more discussions on other motif mining algorithms in our revised version.\n\n>Clarification to “The proposed method assumed temporal motifs can capture the dynamics of the graph, which might not hold for real-world scenarios”\n\nWe totally agree that dynamic systems can be influenced by a multitude of external factors or emergent behaviors. However, many works have demonstrated that temporal motifs are essential building blocks of complex dynamic systems in real-world scenarios [1,2], which help us to gain a deeper understanding of the system’s functioning. We believe that this manuscript has a unique value in investigating how temporal motifs facilitate explainability. It is also a necessary first step before one can further extend to a multitude of factors in future works.\n\n[1]Temporal motifs in time-dependent networks\n\n[2] Motifs in Temporal Networks\n\n>The performance improvements of the Enron dataset are not significant compared with other datasets in Table 1 and Table 4.\n\nThanks for the interesting question. We also noticed that the performance improvement on Enron is not as significant as other datasets. One possible reason is that temporal interactions are the most dense in Enron, compared with other datasets in experiments. We refer to Table 6 in Appendix E.1 for dataset information. Here we define the interaction density as the ratio of #links to #nodes (regardless of time durations). It might be more challenging to analyze temporal graphs with high interaction density with motifs, since there could be complex interactions and mixed effects of multiple motifs. We are more than happy to further analyze and discuss potential limitations in our final version.\n"}, {"review_id": "8WUjs89SdB", "reviewer": "Reviewer_M5gq", "summary": "This paper proposes an approach, Temporal Motifs Explainer (TempME), to find out key sub-graph structures from temporal graph neural networks (TGNNs) that mostly influence the prediction for a better ability of explanation. It employs an generative approach including the steps, motif extraction and sampling, to retrieve the structures with explainability. Experiments show that the proposed TempMe improves the state-of-the-art explainable GNNs and TGNNs in prediction.\n", "questions": "1. The novelty seems not sufficient. It is claimed as the first work that utilizes temporal motifs for explanation. However, the compared state-of-the-art [23] targeted finding out sub-graph structures of TGNNs for explainability enhancement as well. Therefore, the claimed novelty is questionable.\n2. More related research should be compared in the section of related work. Following question 1,  it is strongly suggested to state the major differences of targeted research problems from the previous work [23]. In addition, as described in Lines 47-53, there are prior studies employing temporal motifs underlying generative mechanisms as well as the proposed work. The differences of contributions are not clearly illustrated in the manuscript though. Hence, the research value of this paper is inadequate accordingly.\n3. The experimental evidence is not sufficient to support the proposed approaches to address the claimed issues in prior research. As stated in Lines 34-36, the existing research [20, 21] has not thoroughly studied the characteristics of temporal graphs, the consequent influence on the prediction and explanation is not clearly stated. Moreover, the research is not compared in the experiments. That is, it lacks experimental evidence to support the improvement under consideration of the temporal information over these works. \n4. What is the time complexity of TempMe compared with [13, 14, 23]? Are there any trade-offs between the computational costs and the exploration of key motifs under TempMe?\n", "limitations": "1. The proposed approach is validated on the graphs with sparsity levels between 0 and 0.3, i.e., dense graphs with richer information. How about the effectiveness on the graphs with higher sparsity? ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Explainable AI in motif exploration is a promising research field that has not been widely studied.\n2. This paper is written in good organization. The motivation and the targeted problem are illustrated clearly.\n3. The designed procedure of method is clearly stated as well.\n", "weaknesses": "1. The novelty seems not sufficient as claimed.\n2. More related research should be compared in the section of related work.\n3. The experimental evidence is not sufficient to support the proposed approaches to address the claimed issues in prior research.\n\nPlease see the detailed comments in the review block - Questions.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the valuable suggestions and positive comments on the motivation, and organization in this work. However, there are some misunderstandings in the novelty and experimental setting of this work. We would like to clarify as follows.\n\n>The novelty seems not sufficient.\n\nOur main novelty lies in the first attempt to utilize temporal motifs as the building blocks to analyze and explain the functionality of current temporal GNNs, which have never been explored before. Furthermore, we innovatively resort to the information bottleneck principle in the temporal explanation scenario. As mentioned in Line 42-46, the sub-graph structures extracted by [23] do not provide any motif-level insight and also entail high computational costs (Table 3). We believe the methodological and theoretical novelty of this paper is substantial and solid.\n\n>More related research should be compared in the section of related work.\n\nIn this work, we focus on the same research problem with [23], i.e., the explainability of temporal GNNs.  Compared with [23], we are the first to utilize temporal motifs in this field. The temporal explanations generated by TempME provide knowledge of the combined effect of event sets and motif-level insight.\nIn lines 47-53, we introduce how temporal motifs are used to analyze the underlying generative mechanisms in real-world systems as traditional methods. However, they have never been used to explain temporal GNNs. These previous works inspire us to utilize temporal motifs as more plausible and reliable composition units in explanation tasks. We have clearly stated our contributions in Line 77-81.\n\n>The experimental evidence is not sufficient to support the proposed approaches to address the claimed issues in prior research. Why not compare references [20,21] in the experiments?\n\nExisting work [20] mainly focuses on extracting a query-relevant subgraph for temporal knowledge graph reasoning. Though it explains the reasoning logic in temporal knowledge graphs to some extent, it requires a key “predicate” to infer a subgraph, which is specific to the knowledge graph setting. Previous work [21] is based on a sequence of static snapshots of a temporal graph, which is a coarse approximation to real-world temporal graphs with continuous time-stamped events. [20] and [21] either cannot process complicated dependencies between massive interactions in real-world scenarios or cannot be applied to explain general temporal GNNs under our problem formulation. We didn’t involve [20,21] in our baselines since it might be problematic to compare models under different problem settings. We believe the extensive experiments (in terms of accuracy, sparsity, connectivity, efficiency, etc.) and outstanding results over state-of-the-art baselines to be sufficient to support the superiority of TempME. \n\n>What is the time complexity of TempME compared with [13,14,23]? Are there any tradeoffs between computational cost and the key motifs exploration?\n\nThe time complexity of TempME is discussed in Appendix D.3. For a thorough review, our TempME and PGExplainer[14] are more efficient than GNNExplainer[13] and TGNNExplainer[23]. TempME and PGExplainer learn a neural network to predict the importance score of a certain edge / motif, which is shared by all edges in the given graph. However, GNNExplainer and TGNNExplainer require retraining / re-searching individually for each given instance. To infer an explanation for a given instance, the time complexity of GNNExplainer is $\\mathcal{O}(T|E|)$, where $|E|$ is the number of edges in the computational graph, $T$ is the number of retraining epochs. The time complexity of PGExplainer is $\\mathcal{O}(|E|)$. However, these explainers ignore time information and fail to capture complicated interaction dependencies. \n\nTGNNExplainer is an MCTS-based method, where the search space increases exponentially w.r.t tree depth. The time complexity of TGNNExplainer with navigator acceleration is $\\mathcal{O}(NDC)$, where $N$ is the number of rollouts, $D$ is the expansion depth of each rollout and $C$ is a constant including inference time of navigator and other operations. The inference time of TempME is mainly determined by the sampling process, which results in a complexity of $\\mathcal{O}(Cl)$ where $C$ is the number of motifs and $l$ is the maximum length of the motif. Empirical results of the runtime are given in Table 3.\n\nWe also conduct ablation studies on computational cost, motif exploration and model performance in Figure 4(a) and Figure 6 in Appendix E.3. By setting appropriate $C$ and $l$, TempME archives the best tradeoff between performance and efficiency.\n\n>Clarification to “The proposed approach is validated on the graphs with sparsity levels between 0 and 0.3. What about the graphs with higher sparsity?”\n\nHere are some misunderstandings. We would like to clarify that the proposed approach is validated on graphs with any level of sparsity. The sparsity levels between 0 and 0.3 is used to control the size of the explanatory subgraph w.r.t. the original graph size, since the explanation accuracy is sensitive to the explanation size. We actually conduct experiments on datasets with a wide range of sparsity levels. We also report the dataset statistics in Table 6 in Appendix E.1 for reference.\n"}, {"review_id": "FNvXpT21kl", "reviewer": "Reviewer_HiZ7", "summary": "TempME is an inductive explainer for temporal graph neural networks (TGNNs) over link prediction tasks. It explains TGNNs using temporal motifs, guaranteeing temporally proximate and spatially adjacent explanations, hence more human interpretable. TempME’s pipeline can be broken down into three parts: sampling, embedding, and explaining. Given a link prediction instance, candidate motifs are sampled starting at either end of the edge. The motifs go through a series of steps to generate rich motif embeddings that encode the event's spatial and temporal roles. An MLP learns a Bernoulli distribution over the embeddings. The distribution is used to mask out the best explanation motifs from the candidates. The MLP is trained using the information bottleneck principle to keep the explanations succinct. The mutual information between the predicted label and the explanation is maximized, while the mutual information between the explanation motifs and the set of candidate motifs is minimized. TempME can also boost a model’s performance. The authors show improved results across datasets by concatenating the aggregation of the motif embeddings around a node of interest prior to a model’s final MLP layer.\n", "questions": "Overall, I like the paper. I am open to increasing the score if the authors address the weaknesses listed above and address the questions below.\n\n* Since we are trying to explain the black box and not the data, what if the black box is prioritizing the distant edges? In that case, will TempME force the explanation to be cohesive?\n* The authors state the use of a “generative model”. However, it is not found anywhere. The term “generative” brings VAEs and probabilistic graph models to mind, a model that can generate new graph instances that follow a specific distribution or capture the underlying patterns and characteristics of the observed graph data. There is no graph generation involved. Sampling is different from generating. What exactly do the authors mean by a “generative model”? Is it just the ability to generalize to unseen nodes? In that case, the authors should change the terminology as it is misleading.\n* In line 194, are C motifs sampled from both u and v, totalling 2C?\n", "limitations": "Yes, the authors have addressed the limitations in the appendix.\n\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Unlike prior work that measures the impact of singular events, TempME measures the combined effect of events on the black box prediction.\n2. Cohesive explanations are more human-interpretable than non-cohesive ones.\n3. It has significantly less computational cost compared to previous TGNN explainers.\n4. It can generalize to unseen nodes, which is highly desirable.\n5. The identified motifs can be utilized during training to boost model performance.\n", "weaknesses": "1. The authors have not experimented with synthetic datasets even though they are available. In graphs, the ground truth explanation is often unknown. Hence, synthetic graphs are vital to ascertain that the explanations comply with the ground truth. Please refer to the following for the synthetic datasets and their case study: *Xia, Wenwen, et al. \"Explaining temporal graph models through an explorer-navigator framework.\" The Eleventh International Conference on Learning Representations. 2022.*\n\n2. The authors have cited the following paper as prior work but have not used it as a baseline. *Wenchong He, Minh N Vu, Zhe Jiang, and My T Thai. An explainer for temporal graph neural networks. In GLOBECOM 2022-2022 IEEE Global Communications Conference, pages 462 6384–6389. IEEE, 2022.* Please either compare or provide a justification for not including as a baseline.\n\n3. The authors have compared with GNNExplainer and PGExplainer for comparison with static graph explainers. However, these are no longer state-of-the-art (SOTA) explainers for static graphs. Table 1 and Fig 3 show that GNNExaplainer and PGExplainer are competitive. Using SOTA static graph explainers might have yielded even better results for static explainers and led to different insights. A comparison with the following will be more fruitful:\n\n* *Tan, Juntao, et al. \"Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning.\" Proceedings of the ACM Web Conference 2022. 2022.*\n\n* *Yaochen Xie, Sumeet Katariya, Xianfeng Tang, Edward Huang, Nikhil Rao, Karthik Subbian and Shuiwang Ji. Task-agnostic graph explanations. NeurIPS, 2022.*\n\n4. Please provide the hardware details of the experimental setup.\n5. Please provide TempME’s training time as well. It is good to have fast inference, and at the end of the day, inference is what matters, but a user should also have an idea of how long it takes to train.\n6. The reference for GINE is correct; however, it does not explicitly use the term GINE in it, which may make it difficult for future readers to refer to. Please add a citation that uses the term GINE explicitly.\n7. Pip throws an error when using the author’s requirements.txt to setup the experimental environment.\n8. Some typos and grammar mistakes: \n * 158, 622: denotes -> denoted\n * 190: in this work (unnecessary)\n *  278: In meanwhile -> Meanwhile\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback, which significantly improves the quality of this work. We also address below the potential concerns. \n\n>Lack of Experiments on synthetic datasets\n\nThanks for your constructive comments. The synthetic dataset is a point process where the arrival of an event can affect the arrival rates of other events. However, there are still no ground-truth explanations from the motif perspective in the synthetic dataset. The relevance and applicability of the point process to real-world temporal graphs have been less tested by the community so far. We believe our extensive experiments on real-world datasets provide a more accurate representation of the challenges that our approach aims to address. We acknowledge the potential value of experiments on synthetic datasets. If time allows, we are more than happy to involve the results on synthetic datasets in our revised version.\n\n\n>Why not include Reference [21] as a baseline?\n\nPrevious work [21] is based on a sequence of static snapshots of a temporal graph, which is a very coarse approximation to real-world temporal graphs with continuous time-stamped events and may lose information by looking only at some snapshots of the graph over time. We didn’t involve [21] in our baselines since it might be problematic to compare two models under different problem settings.\n\n>Static graph explainers are no longer state-of-the-art explainers for static graphs. What about more recent explainers?\n\nThanks for your constructive suggestions. We agree using more SOTA static graph explainers yields stronger experimental results. [1] proposes $CF^2$ that utilizes counterfactual and factual reasoning to generate factual explanations, while guaranteeing the counterfactual property of the remaining subgraphs. \nWe refer to the official codes of $CF^2$ and test the explanation performance on Wikipedia and UCI. In our implementation, we generalize the original loss function to explain the link prediction task.  The results are reported as follows. We notice that $CF^2$ archives comparable performance with GNNExplainer, since the intrinsic training procedure of $CF^2$ is the same as GNNExplainer. We consider the additional constraint on the counterfactual property may not hold for temporal link prediction tasks, due to complex time dependencies between events (e.g. one event may have a factual contribution at timestamp $t_1$ but have a counterfactual contribution at timestamp $t_2$)\n\n|            | Wikipedia |        | UCI   |        |\n|------------|------------|--------|-------|--------|\n|            | $CF^2$       | TempME | $CF^2$  | TempME |\n| TGAT       | 84.46      | 85.81  | 73.24 | 76.47  |\n| TGN        | 93.23      | 95.80   | 94.16 | 96.34  |\n| GraphMixer | 89.77      | 90.15  | 60.38 | 87.06  |\n\nRegarding [2], the main focus is explanations for multi-task prediction. The backbone of the proposed explainer shares a very similar spirit with PGExplainer. Thus, [2] cannot be directly compared with our method since we focus on different problems. Meanwhile, we have included PGExplainer as a baseline.\n\n[1]Learning and Evaluating Graph Neural Network Explanations based on Counterfactual and Factual Reasoning\n\n[2]Task-Agnostic Graph Explanations\n\n>Hardware details of the experimental setup\n\nThe implementation of our model and training is based on the NVIDIA Tesla V100 32GB GPU with 5,120 CUDA cores on an HPC cluster. The experimental environment is based on  Python 3.8.10, PyTorch 1.10.1 and PyTorch Geometric 2.0.4. We will add hardware details in our revised version.\n\n> Training time of TempME\n\nThanks for bringing this up. We take Wikipedia as an example (which is a relatively large dataset). We set $C=30, l=3$ in the temporal motif extraction step. It takes around 200 seconds for an epoch and $\\approx 60$ epochs to converge. The training time depends on the dataset size. We will discuss this accordingly in our revised version.\n\n>Reference of term GINE\n\nThanks for the careful suggestions. GINE was first used in [1] as a modified version of GIN to incorporate edge features in the aggregation function. However, we didn’t find any literature that officially proposes the terminology of GINE. We would like to cite both [1] and PyG, which seem to first name this GIN variant as GINE. \n\n[1] Strategies for pre-training graph neural networks\n\n> Experimental environment setup error\n\nOur experimental environment is based on Python 3.8.10. We will refine and update our repository upon publication.\n\n> What if the black box is prioritizing the distant edges? Can TempME still force \"cohesive\"?\n\nWe note that TempME extracts explanatory motifs from the computational graph of a given instance. The number of layers in current temporal GNNs is typically 2 or 3, meaning that the black box considers 2 or 3-hop neighbors. In that case, if the black box is prioritizing the distant edges, TempME is still able to extract a motif that involves the distant edge and the edge to explain, which potentially ensures the “cohesive” property of the explanation.\n\n> Clarification to “generative model”\n\nWe agree with your understanding that “a generative model captures a specific distribution and characteristics of the observed graph data and obtains the ability to generate new instances”. TempME is exactly a generative model. We actually frame the explanation task as a generative problem, where the explainer is trained to capture the underlying distribution of explanatory motifs. The importance scores learned by TempME are used to model the Bernoulli distributions of certain motifs. TempME is also able to generate new explanatory subgraphs by sampling from the motif distributions.\n\n> In line 194, are C motifs sampled from both u and v, totalling 2C?\n\nYes. We sample $C$ motifs for $u$ and $v$ at both ends of the interaction and obtain $2C$ motifs in total.\n\n>Typos/grammar mistakes.\n\nThanks for pointing them out. We will revise our manuscript accordingly.\n"}, {"review_id": "cbOt6iIDy1", "reviewer": "Reviewer_NnW1", "summary": "This paper provides a method to extract temporal motifs in order to capture correlated building blocks of networks. ", "questions": "It is not clear to me what the mutual information is between a random variable and a graph. \n\nAre temporal motifs allowed to overlap each other? \n\nWhy is there no time component in Figure 1? \n\nThe elements in the edge set contain an event attribution but the motif definition ignores this event attribution. Why? \n\nIn Definition 1 why is u_0 = u_1 set ? What is the induced subgraph? What is the graph that this is a subgraph of? If this underlying graph is the union of all temporal graphs, then does it have multiple edges or self-loops? \n\nDefinition 2: When do two motif instances have the same topology? Is it their induced subgraph that has the same topology? Again, what happens to mutiple edges? \n\nWhy can the motif of preferential attachment not be represented as a temporal walk? \n\nWhat are `surrounding' motifs in Section 4.2.? \n\nTemporal motif encoding: what is T ( t - t_{pq})  ? What is N(p)? Is  there an underlying graph with a fixed number of nodes and a fixed topology? Is that a simple graph? \n\nHow is an importance score generally obtained? It is a crucial ingredient of the method. \n\nIn Section 5.2 it is stated that ``TempME still surpasses all baselines and achieves the highest connectivity levels, primarly due to it ability to extract and utilize self-connected motifs'' ; how does self-connectedness enter here? what it meant by that? \n\nWhy is the discussion from the supplementary information section F not in the main text? Is it not important? \n\n", "limitations": "The paper discusses limitations  only in the supplementary material. Clearly the choice of null model may have a major influence on the analysis, as does the choice of prior. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method of extracting temporal motifs is interesting; it is based on information theoretic concepts. ", "weaknesses": "In my view there are two main weaknesses of this paper. \nThe first weakness is the underlying assumption that network motifs should consist of nodes and edges which are in close time proximity to each other. This assumption is not questioned but often does not hold, as there are often seasonal effects in network time series. These seasonal effects could occur for example only once per week, as Sundays may be special in terms of network behaviour. \n\nThe second weakness is the presentation. It is stated that the method is in a continuous-time setting, but the events occur at separated time points from the description; there does not seem to be the possibility of having more than one event occurring simultaneously. The large number of questions below indicate that the paper may not be very clearly written. \n\nThe paper aims to provide an explanation of temporal GNNs; it would be good to see a worked example in which explanation relates to a tangible real-world scenario. Which are the motifs that are found in the different networks? How can they be viewed as builing blocks of these networks; do they point towards fundamental differences between, say, the Wikipedia network and the Enron network?  There is a start at this question in the supplementary material E.5 but the analysis may strongly depend on the chosen prior. \n\nFinally, the discussion from the supplementary information Section F should have been in the main text. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback and positive comments on the theoretical contribution. We address below the questions in order.\n\n> The assumption that ...  may not hold when there are seasonal effects.\n\nWe also believe that considering these seasonal effects is crucial. However, we think developing seasonal motifs might deserve another paper. First, the definition of temporal motifs that represent seasonal effects is nontrivial, since we might need to first recognize the most significant time intervals that reflect the system dynamics. Second, given a time interval, how to sample the target seasonal motifs efficiently is also under-explored, which requires extensive effort. We sincerely appreciate your valuable comments, which actually light up an interesting future direction for us.\n\n> The method is in a continuous-time setting, but the events occur at separated time points. There does not seem to be the possibility of having more than one event occurring simultaneously.\n\nSorry for any confusion. Actually, the continuous-time setting we used in this manuscript supports simultaneous events. “Continuous-time” means the timestamp($t_k$) in the event element can be any continuous value in the real number set $\\mathbb{R}$, rather than being restricted to a specific value derived from a sequence of time points with a constant time interval. In a continuous-time setting, there can be multiple simultaneous events with the same value of timestamp.\n\n> It would be good to see a worked example related to real-world scenarios.\n\nThanks for the constructive feedback. Please refer to the real-world example we provide in the general response.\n\n>What is the mutual information between a random variable and a graph?\n\nA graph is also a variable represented by its adjacency matrix, and node/edge attributes. Since the graph follows a certain distribution (either a prior distribution given the dataset, or a posterior distribution predicted by networks), we can calculate the mutual information between a random variable and this graph random variable.\n\n>Are temporal motifs allowed to overlap each other?\n\nYes. They can overlap each other.\n\n>Why no time component in Figure 1?\n\nTime components are included in Figure 1. Here “1,2,3…” indicates the order of event occurrence.\n\n>Why does motif definition ignore the event attribution?\n\nNetwork motifs primarily focus on the arrangement and connectivity patterns of nodes within a network. In this work, we also follow this idea for consistency with existing literature.\n\n>Why $u_0=u_1$ in Def. 1? What does “induced subgraph” mean? any multiple edges or self loops?\n\nIt means we sample motifs starting from the given node of interest. Therefore, the starting node of the first event should be the same as the given node. “Induced subgraph” means the graph formed from all vertices and events in $I$, which is the subgraph of the original temporal graph. There can be multiple edges between two nodes. Typically, in network motif studies, input networks are considered after all self-loops are discarded.\n\n>What does \"the same topology” mean? What about multiple edges?\n\n“The same topology” means the induced subgraph has the same topology and the corresponding events happen in the same order over time (regardless of the absolute time interval). We use a $2l$-digit to represent the identities of sampled nodes in the event order. “Two motif instances are the same” indicates the same $2l$-digit representation. It is able to manage multiple edges. We discussed more details in Appendix B and D.2. \n\n>Why cannot the preferential attachment ... as a temporal walk?\n\nIn Temporal Walk Extraction (Alg.1 in [1]), the next event is sampled from historical events that interact with the latest sampled node. For example, we have sampled $w_1\\rightarrow w_2\\rightarrow w_3$ that satisfies $w_1\\neq w_3$ in the current node set. To extract a motif for preferential attachment, the next event $(u, v, t)$ should satisfy $u=w_2$. However, since the latest sampled node is $w_3$, then $(u,v,t)$ is not in a valid historical event that interacts with the latest node. Therefore, the motif of preferential attachment cannot be sampled by the temporal walk extraction algorithm.\n\n[1] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks\n\n>What are “surrounding” motifs in Section 4.2?\n\nWe sample $C$ motifs starting from $u$ and from $v$ by Algorithm 1 respectively, which represent the surrounding topology. \n\n>What is $T(t-t_{pq})$? What is $N(p)$? \n\n$t$ is the timestamp of the event to explain, and $t_{pq}$ is the timestamp of the historical event $e_{pq}$ in the temporal motif. $T(\\cdot)$ is a time encoder that maps the time interval into a 2d-dimensional vector (Line215). $N(p)$ indicates the set of neighboring nodes of $p$. Here, it is essentially the set of nodes in the motif that have interaction with node $p$.\n\n>Is there an underlying graph with a fixed number of nodes and a fixed topology? Is that a simple graph?\n\nNo. We are not assuming an underlying graph with a fixed number of nodes/topology/a simple graph. \n\n>How is an important score generally obtained?\n\nGiven the motif embedding $m_I$ learned by Temporal Motif Encoder (Eq.3), we adopt an MLP for mapping $m_I$ to an importance score $p_I\\in[0,1]$ as mentioned in Line 230-231, which is later used to model the distribution of the corresponding motif.\n\n>What does “self-connectedness” mean?\n\n“Self-connectedness” means each motif sampled by TempME is self-connected. It is guaranteed by the sampling algorithm. The next event during motif sampling is from a set of historical events that interact with at least one node in the current node set. Thereby, the self-connectedness of each motif potentially ensures a high “cohesive” level in the generated explanation.\n\n>Discussion from the supplementary material should be in the main text.\n\nWe will adopt your suggestions to move part of the discussions to the main text in our revised version.\n"}, {"review_id": "QFVIRPyrDf", "reviewer": "Reviewer_U22B", "summary": "The work presents TempME, an explanation methodology for temporal graph neural networks that incoporates the idea of temporal motifs. By incoporating temporal motifs, the method demonstrates better cohesiveness, since motifs are constructed to be cohesive, i.e., connected and localized, as well as better explainability compared to prior explainability works.\n", "questions": "Regarding the motivation for presenting an explanation subgraph for TGNN: While with image instances we can verify that the important regions (e.g. highlighted by grad-cam) coincide with semantically meaningful regions in an image using human intuition and understanding, it is unclear if human intuition or logic can be applied to temporal graphs.\n- Can you provide examples of  human intuition or logic applied to temporal graphs? For example, with certain datasets, observing some part of the temporal graph would lead to a understanding on whether some target event should or should not exist.\n- Can you provide examples of the explanation subgraph presented by TempME and show how such explanation subgraph provides \"human intelligible explanation\" as stated in line 38?\n- Can you provide examples of the explanation subgraph presented by TGNNExplainer and Grad-CAM, as well as other baselines, to show how they do not present \"human intelligible explanation\"?\n", "limitations": "The paper presents some technical limitations but the discussions on potential negative societal impact could be strengthened by discussing the potential real-world application of explaining TGNNs.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The work presents an excellent contribution to TGNN explainability by proposing the use of temporal motifs.\n- The work presents solid technical material to support the proposed methodology.\n- The work further presents good and extensive results that covers many interesting aspects.\n\n", "weaknesses": "There are some unclarity in the paper. In particular, the goal of the evaluation and the evaluation setting for the explanation performance is not clear. In particular, the statement \"ACC-AUC, which is the AUC value of the proportion of generated explanations that have the same predicted label by the base model over sparsity levels from 0 to 0.3\" is hard to comprehend. Currently, the reviewer thinks that:\n- \"generated explanations\" are the explanation subgraphs extracted by the expalantion models.\n- \"sparcity level\" idicates the ratio of sizes between the the extracted explanation subgraph and the whole temporal graph\n- perhaps the \"predicted label by the base model\" is the prediction of the event/edge that the original target model gives when given the extracted explanation subgraph?\n\nIt could be clearer if at Section 3, it is noted that the budget \"K\" will be represented as \"sparsity\" and the objective of Equation 1 is spelled out more intuitively. \n\nBesides:\n- The inline equation for \"Fidelity\" has typos and the paranthesis does not match up. It also lacks intuitive explanations. Besides, it seems that Fidelity follows that constructed by TGNNExplainer, and a proper citation should be given. \n- norm of the gradient being utilized for Grad-CAM is essential to understanding the treatment of baseline and should be stated in the main paper.\n\nMiscellaneous:\nThe figures (especially the color shades and the lighter colors, when printed out) is not clear.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable feedback, which significantly improves the quality of this work. We would like to address the following potential concerns you raise.\n\n>The goal and setting of the evaluation are not clear. Clarification to “AUC value of the proportion of generated explanations that have the same predicted label by the base model over sparsity levels from 0 to 0.3”?\n\nSorry for any confusion. The sparsity level indicates the ratio of sizes between the extracted explanation and the computational graph of the event to explain. All of your other understanding is correct. To explain more, the accuracy of explanations is sensitive to the sparsity level. The area under the accuracy-sparsity curve is denoted as the ACC-AUC value, which is reported in Table 1.\n\n>It could be clearer if the budget “K” is represented as “sparsity” in Eq.1 and any intuitive explanations to Eq.1?\n\nThanks for the constructive comments. We will rewrite the budget $K$ as $|\\mathcal{G}_{\\exp }^e| \\leq s|\\mathcal{G}(e)|$, where $s$ is the sparsity level, $\\mathcal{G}(e)$ is the computational graph of the event $e$.  Eq(1) aims to maximize the mutual information between the explanation and the original model prediction. \n\n>Lack of intuitive explanations “Fidelity”. \n\n“Fidelity” measures how valid and faithful the explanations are to the model’s original prediction. If the original prediction is positive, then an explanation leading to an increase in the model’s prediction logit is considered to be more faithful and valid. If the original prediction is negative, then an explanation that decreases the prediction logit is better. We will add more intuitive explanations to this metric in our revised version.\n\n>Motivation for presenting an explanation subgraph for TGNN. How can human intuition or logic be applied to temporal graphs? How does TempME provide “human-intelligible explanation” for TGNN? How do other baselines fail to provide “human-intelligible explanations” for TGNN?\n\nThanks for the constructive feedback. Please refer to the real-world examples we provide in the general response. Explanation visualizations are provided in the 1-page pdf.   Compared with TGNNExplainer, TempME works better in generating a ”cohesive” explanation. Moreover, the explanation generated by TempME provides additional motif-level\ninsights. In our visualization, different colors indicate the different types of temporal motifs that the corresponding event contribute to. Temporal motifs work as the building block of the dynamic system and provide a unique perspective of how the combination of events (e.g., preferential attachment, triadic closure, etc) contributes to the prediction of temporal GNNs. In contrast, we observe that previous methods (e.g., GradCAM, TGNNExplainer) either fail to generate a \"cohesive\" explanation or fail to provide any model-level insight.\n\n> Others: Typos in the inline equation for “Fidelity” / Citation for Fidelity metric / Gradient Norm utilized for Grad-CAM / unclear color in figures\n\nThanks for your careful reviews. We will add the Grad-CAM details to the main text, cite for fidelity metric, change the figure colors for better readability, and fix the typos accordingly in our revised version.\n"}]

Author rebuttal:
We sincerely appreciate the reviewers for their valuable time and effort in reviewing this manuscript. We have extended our experiments, which we detail below. We appreciate your feedback on this, and we agree that additional empirical verification would better support our proposed framework and thus make the paper stronger.

We provide a visualization of real-world explanation examples on Wikipedia. The base model is TGAT with two layers. We demonstrate the explanations generated by Grad-CAM, TGNNExplainer, and the proposed TempME. We can make the following observations.
- Compared with TGNNExplainer, Grad-CAM tends to generate more "cohesive" explanations. One possible reason is that topologically close events tend to have close gradients. In contrast, the explanation generated by TGNNExplainer contains more isolated events, which degrades the inspiration that explanations could bring us.

- Compared with Grad-CAM and TGNNExplainer, the proposed TempME not only can generate more "cohesive" explanations but also provide additional knowledge on the combined effect of explanatory events from a unique perspective of temporal motifs. TempME is capable of capturing the importance of each motif to the dynamic of the temporal graph.

According to the suggestions from the reviewer, we add $CF^2$[1] as a baseline, which is a state-of-the-art explainer on static graphs. We report our preliminary results on Wikipedia and UCI in Table 1. Complete results will be given in the final version.

We hope that the experimental support improves your confidence in our work. Again we thank you for your feedback and we continue to look forward to the coming discussion.

[1]Tan, Juntao, et al. "Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning." Proceedings of the ACM Web Conference 2022. 2022.

Meta-review: The reviewers raised a few concerns, including the assumption, the performance studies, etc., on this paper. The authors addressed most of the concerns during the rebuttal/discussion phase, and the reviewers were finally all positive about the work. After reading the reviews and discussions, and also taking the scores into account, I am recommending this paper be accepted.
Decision: Accept (poster)