Explaining Temporal Graph Models through an Explorer-Navigator Framework
Authors: Wenwen Xia
Mincai Lai
Caihua Shan
Yao Zhang
Xinnan Dai
Xiang Li
Dongsheng Li
Venue: ICLR 2023 poster (2023)
Keywords: graph neural networks
gnn explainers
temporal graphs

Abstract: While GNN explanation has recently received significant attention, existing works are consistently designed for static graphs. Due to the prevalence of temporal graphs, many temporal graph models have been proposed, but explaining their predictions remains to be explored. To bridge the gap, in this paper, we propose T-GNNExplainer for temporal graph model explanation. Specifically, we regard a temporal graph constituted by a sequence of temporal events. Given a target event, our task is to find a subset of previously occurred events that lead to the model's prediction for it. To handle this combinatorial optimization problem, T-GNNExplainer includes an explorer to find the event subsets with Monte Carlo Tree Search (MCTS)  and a navigator that learns the correlations between events and helps reduce the search space. In particular, the navigator is trained in advance and then integrated with the explorer to speed up searching and achieve better results. To the best of our knowledge, T-GNNExplainer is the first explainer tailored for temporal graph models. We conduct extensive experiments to evaluate the performance of T-GNNExplainer. Experimental results on both real-world and synthetic datasets demonstrate that T-GNNExplainer can achieve superior performance with up to about 50% improvement in Area under Fidelity-Sparsity Curve. 

Published as a conference paper at ICLR 2023
EXPLAINING TEMPORAL GRAPH MODELS THROUGH AN EXPLORER-NAVIGATOR FRAMEWORK
Wenwen Xia Mincai Lai², Caihua Shan Yao Zhang', Xinnan Dai Xiang Li Dongsheng Li Shanggaa Jiao Tong University, "ShanghaiTech University, "Microsoft Research Asia FFudan University, 'East China Normal University
xi xiawenwen&s jtu. edu. en, {laime, wew.xn//saangaatteeeee edu. yaozhange fudan. edu. en, xiangli@dase ecnu. edu. on [caihuashan, dongsheng 1i www.:l//mmmmo.tt.commm
ABSTRACT
While Graph Neural Network (GNN) explanation has recently received signifi- cant attention, existing works are generally designed for static graphs. Due to the prevalence of temporal graphs, many temporal graph models have been proposed, but explaining their predictions still remains to be explored. To bridge the gap, in this paper, we propose a Temporal GNN Explainer (T-GNNExplainer) method. Specifically, we regard temporal graph a sequence of temporal events be- tween nodes. Given temporal prediction of model, our task is to find a subset of historical events that lead to the prediction. To handle this combinatorial opti- mization problem, T-GNNExplainer includes an explorer to find the event subsets with Monte Carlo Tree Search (MCTS), and navigator that learns the correlations between events and helps reduce the search space. In particular, the navigator is trained in advance and then integrated with the explorer to speed up searching and achieve better results, To the best of our knowledge, T-GNNExplainer is the first explainer tailored for temporal graph models. We conduct extensive experiments to evaluate the performance of T-GNNExplainer. Experimental results demon- strate that T-GNNExplainer can achieve superior performance with up to ~50 improvement in Area under Fidelity-Sparsity Curve.
INTRODUCTION
Temporal graphs are highly dynamic networks where new nodes and edges can appear at any time. The input is usually regarded as a sequence of events (node i, node j, timestamp t), which means there is an interaction (edge) between node i and j at timestamp
It is ubiquitous in many real- world applications, such friendship in social networks (Pereira et al. 2018 Barrat et al. 2021) and user-item interactions in e-commence (Li al. 2021c). Many applicable temporal graph models (e.g., Jodie (Kumar et al., 2019). TGAT Xu et al. 2020). TGN (Rossi et al. 2020g) are proposed considering both time dynamics and graph topology. Compared with static GNNs, temporal graph models learn the representation of each node a function of time and then predict future evolutions, e.g., which interaction will occur and what time node attributes change.
Despite the success, all these models black boxes and lack transparency. It is opaque how information aggregates and propagates over a graph and how a prediction is affected by historical events. Human-intelligent explanations and providing insights into model characteristics. Explainers could increase the trust and reliability of temporal graph models when they are applied to high-stakes situations, like fraud detection in financial systems (Wang et al. 2021b) and disease progression prediction in healthcare (Li et al.) 2021ah. Besides, explainers also help check and mitigate the privacy, fairness and safety issues in real-world applications (Doshi- Velez & Kim 2017).
critical for understanding the rationale of predictions
While currently there are no methods for explaining temporal graph models, some recent expla- nation methods (e.g., GNNExplainer (Ying et al., 2019). PGExplainer (Luo et al. 2020) and Sub- graphX YYuan et al. (02T) for static GNNs are the most related. They identify the important nodes,
"This work was done during Wenwen Xia's internship at MSRA. Corresponning author.

---

Published as a conference paper at ICLR 2023
edges and subgraphs for predictions by perturbing the input of GNN models. Obviously, these models cannot be used to explain a well-trained temporal graph model, as they cannot capture the temporal dependency mixed with the graph topology.
Here we propose T-GNNExplainer, an instance-level model-agnostic explainer for temporal graph models. For any prediction of larget event, aim find out important events from candidate events, which lead to the model's 's prediction of occurrence (or absence) of it. The candidate events are previously occurred events satisfying spatial and temporal conditions: they are in the k-hop neighborhood based on the message passing mechanism, and their timestamps should be close to that of the target event.
Specifically, T-GNNExplainer takes the advantages of search- and learning-basse basedd GNN ex- plainers together. Generally speaking, learning-basee explainer is inductive to all the target events, and explaining a target event is very quick once trained. A search-basee explainer searches for the best result for each target event, which more specific but time-consuming. While in this work, T-GNNEXppaiier is designed as a MCTS process with learned navigator. We pretrain a navigator advance to learn the inductive relationship between a target event and its candidate events. Then we utilize MCTS to explore the best combination of candidate events given any new target event. The navigator helps to bias the search process, significantly reducing the search time and improving the performance.
We evaluate T-GNNExplainer on both synthetic and real-world datasets for two typical temporal graph models (TGAT and TGN). On synthetic datasets, simulate temporal events by the mul- tivariate Hawkes process and pre-defined event relation rules. The highly accurate explanations demonstrate that T-GNNExplainer can find an exact influential event set. Since we do not know the ground truth for real-world datasets, the fidelity-sparsity curve is adopted to evaluate the superiority of T- T-GNNExplainer compared with baselines. We further provide case study on synthetic datasets to illustrate the practical events found by T-GNNExplainer and navigation information.
2
RELATED WORK
2.1 TEMPORAL GRAPH AND TEMPORAL GRAPH MODELS
Graphs can be divided into four types by temporal granularity: static graph, graph with time- weighted edges, discrete-ting dynamic graph (DTDG) and continuous-time dynamic graph (CTDG) (Kazemi et al.] 2020). The typical graph neural networks (e.g., GCN (Kipf & Welling 2017). GAT (Velickoii et al. 2018), GIN (Xu et al. 2018) can be used for the former two types to learn the static node embeddings. DTDGs are sequences of static graph snapshots taken at intervals in time. CTDGs are more general and are represented as a sequence of timestamped events, including edge/node addition, deletion, and feature transformations. In this work, consider temporal graphs as CTDGs and take a sequence of timestamped events as model input since CTDGs are mainstream dynamic graphs with the finest time granularity.
Instead of static node embeddings, temporal graph models are required to learn dynamic node em- beddings. DeepCoevelve (Dai et al., 2016) used RNNs to update node embeddings when some nodes are involved in new events. Jodie (Kumar et al. 2019) added the time projection module to make node embeddings evolve over time. However, they lack a GNN-like aggregation from node neighbors, which leads to the staleness problem (i.c., some node embeddings are out of date (Rossi al. 2020, Kazemi al. p020). Thus, CoPE (Zhang et al. 2027) and TGAT (Xu all, 2020) are proposed to utilize the message passing mechanism to update node embeddings by its own events and its neighbors' events. It has been demonstrated to improve expressive power. TGN (Rossi et al, 2020) is up-to-date framework and claims that most previous models are its specific cases. We choose the state-of-the-art TGAT and TGN as target models to be explained in the paper.
2.2 GRAPH EXPLAINERS
One popular way of explaining static graphs is to study the output variations of well-trained GNN models with respect to different input perturbations (Yuan et al. 2020bb. Intuitively, the output changes vastly when critical nodes, edges, or subgraphs are perturbed. There are mainly two ap- proaches assigning importance scores to graph entities by perturbations: learning-based and search-
2

---

Published as a conference paper at ICLR 2023
based. Learning-based methods (Luo al. 2020 Shan et al. 2021 I
Vu & Thai 2020 leverage
node representations generated by the trained GNN and adopt a neural network to learn crucial nodes/edges. They are trained with multiple instances, i.c., learning inductive explanation charac- teristics for multiple ones. Besides, search-based methods (Yuan et al. (202T): Wang et al. (2021a) utilize heuristic search algorithms with score function (e.g., defined by Shapley value or causality) to find an important input subset. Their inference time is longer because the search space of each
instance is different, and they need explore feasible solutions one by one. There 2022bb:
also some
works possessing intrinsically interpretable architectures (Han et al. 2020 Li et al.
Xiao
al. 2022b) or generating model-level explanations (Yuan et al. (2220)); Shin et al.
2022)) Most
of the self-interpretable models seek to a sparse subgraph during forward computation supported by the attention mechanism (Han al. 20200) or other internal scores (Li al. (2021b); Cui et al.
(02T)). There is concurrent work that also explains temporal graph models et al. (202)). How-
ever, they use discrete snapshots of a temporal graph while we focus on continuous event streams. In this work, mainly focus instance-level post-hoc explanation methods since most of the temporal graph models in the literature are not designed with specific consideration of explanations.
PRELIMINARY
3.1 TEMPORAL GRAPH MODEL
Assume that the input of temporal graph models is a sequence of events S = fei, C2, e2,... ... ). Each
e =nnu Rey 1, att;) } means that the node nu: and ne. have an interaction (edge) at timestamp t with edge attribute att, The att, could be the interaction feature, or an indicator to represent e; edge addition/deletion. Further, e; could involve only one node, {Ten null, 4, att;), represent node-wise event (node addition/deletion, or node attribute change). These events S constitute a temporal graph G (W.S) where S can be regarded as timestamped edges and N are nodes involved in S. Since G and S are mutually defined, we regard G as both a temporal graph and set of events in the following.
We utilize the setting defined in Kazemi et al. 2020) to unify different temporal graph models as an encoder-decoder framework. The encoder is to learn the dynamic embedding for each node over time, and the decoder utilizes the node embeddings for downstream prediction tasks, such future edge prediction. Specifically, let G denote the graph constructed just before the timestamp 4, i.e., containing the events {ei. ... C4-1 } but excluding eq- The encoder takes G as the input and obtains Z' where Z;, is the current embedding of the node n, at timestamp t4. The decoder constructs the loss by predicting whether
interaction between pair of nodes happen this timestamp (the positive sample is e = {Na,; No; while negative samples are the remaining pairs). Thus, the decoder uses 7' to predict the logit/probability of new event between any pair of nodes, computes the loss to backpropagate the gradients, and updates the model parameters.
Encoder(G'). z' Decoder(22 2²) + Logit/Probablic of Events - Loss
Let f()) denote well-trained temporal graph model including the encoder and the decoder sim- plify the notation. [ey) means that we use the encoder to compute Z' by g at timestamp t; and computes the logit/probability of event e, by leveraging Zi,,, and Znny'
3.2 PROBLEM FORMULATION
Given the sequence of events and a well-trained temporal graph model f(-). the temporal explainer explains why the model predicts an event 6 would occur or not. Specifically, we aim to find out subset of events RR from all the previous events G* to maximize the mutual information MY(Y,, k, R² Ys is the original prediction decided by [ex), which is 0 or 1. R² determines the distribution of the new prediction by [(R)) When they are strongly dependent, R is regarded as a good explanation for the prediction of occurrence/absence of event E5.-
According to (Ying et al. 2019), maximizing the mutual information MY(Y,, R*) is equivalent to minimizing conditional entropy H (Y+1R*) R because H(Y.) is a constant. Then we can transform H(Y2 (R*) into cross entropy loss based on (Farnia & Tse 2016
min R#
Σ
1(y c) log P(Ynow = c)
(I)
0=1.1
3

---

Published as a conference paper at ICLR 2023
T-ONNExplainer
Tamporal graph
Temporal graph model
Explorer
Ront
Nevigator
Boodl
Out!
tadpnaggatin
Aear
Figure 1: The framework of T-GNNExplainer. We first pre-train the navigator learn the inductive relationship between events. Then we invoke the explorer to search out a specific combination of important events based on MCTS, including node selection, node expansion, reward simulation and backpropagation. When expanding node, the navigator infers to decide which event is removed.
P(Ynew| (Rh) is calculated by [ex and is the label indicating whether the event occurs not.
Objective. Given target event eş which prediction is made by S()). T-GNNExxlainer is a mapping ! to infer the important events R* g(ex, 9 f()) by current temporal graph g* T- GNNExplainer also minimize the cross entropy loss for K target events. Formally, the optimal explainer g is defined as
K Σ
g" arg min
[Y = o + 1(% = 0) log(1- of
K
subject
Rst g(Eu, f()) and R C g and | S Nr
Here we assume f ((R*)(e)) a single-dimensional logit value produced by the model f()), and (-) indicates the sigmoid function. R should be concise so we use N, hyper-parameter to control the size of R
METHODOLOGY
4.1 OVERVIEW
Here we introduce how to identify important subset of events R for the target event ex. It is a combinatorial optimization problem where any subset of Ç whose size is equal to or smaller than N, could be the explanation. Besides, the search space of temporal graph explainer is more significant than that of static graph explainers because of duplicate timestamped edges and node- wise events. Therefore, we design explorer-navigator framework effectively and efficiently obtain R², shown in Fig. The navigator trained from multiple target events to capture the inductive correlation between events. The explorer is guided by the navigator and finds more specific result based on Monte Carlo Tree Search. We will present them in the following.
4.2 NAVIGATOR
Inspired by previous parameterized explainers (Luo et al. 2020p, we pretrain a navigator to provide global understanding of the relationship among events. Concretely, the navigator a feed-forward neural network ho(e,, ex), which infers the importance score of an event E w.r.t a target event eg. The scores will be leveraged in the node expansion of the explorer (Sec. 4.3 to facilitate the searching. The input features and the training/ifference process are described as follows.
Navigator features. To capture the correlation between the target event e₁ {nuu Reg , tg. att;} and each candidate event e, = {nuy Bay, t att,) ). we construct navigator input features as:
ZEL,ez [nnu |Xn.,
Time(t+) attt ||Xm..) ||Xn.,
Time(ty) atty)
X represents the node feature matrix. Time )) is function converting a real-valued timestamp to a vector that could be learnable (Xu et al. 2020 Rossi et al. 2020) or not (Vaswani et al. 2017) In
4

---

Published as a conference paper at ICLR 2023
this paper, adopt the harmonic encoder (Xu et al. 2020) the time function. We input all the candidate events w.r.t a target event as a batch into hig
Training Process. We use the same objective function described in Eq. The output of ha is regarded as a soft-mask assigning weights to corresponding temporal edges of G If the model f(-) differentiable w.r.t edge weights, add the soft-mask edge aggregation weights in the model, and then obtain the new prediction. Otherwise, the reparameterization trick is used in f()). More de- tails about reparameterization
be found in (Luo al.) 2020 Note that he is trained inductively, i.e, events in the training set are different from those to be explained by T-GNNExplainer.
Inference Process. Provided with a candidate event éj and a target event cg. we construct the input Zenie, put it into the trained navigator he and infer the score, which will be utilized by the explorer.
4.3 EXPLORER
We adopt Monte Carlo Tree Search (MCTS) in the explorer. First of all, initialize the root node as a set of candidate events. Then multiple rounds (a.k.a., rollouts) are conducted to expand nodes in the search tree, where each node represents feasible subset of events in the search space. There four aspects in each round: (I) select a path from the root to leaf node; (2) expand new children by removing unimportant events according the navigator in the path selecting procedure; (3) simulate reward of new nodes by temporal graph model: (4) backpropagate the leaf node's 's reward to update information in path nodes. At last, node achieving the best reward and satisfying the sparsity threshold is our final explanation result. We present the pseudo-code in Appendix.
4.3.1 INITIALIZATION
The root node includes all the candidate events, which are previously occurred events satisfying spatial and temporal conditions. Take the temporal graph in Fig. as an example where we explain 613. Assume that the encoder uses the 2-hop GNN-based aggregation, the set of seen events by encoder is {eg,... .112)- A temporal threshold is used to remove old events. If the threshold is set as 10, we preserve 10 recently occurred events. Finally, the root is initialized as {ea...., e12).
4.3.2 NODE SELECTION
We use ' to represent node in the search tree and use ej to indicate one action, i.e., discard the event 6, from A We follow the UCT (Upper Confidence bound applied to Trees) formula proposed in (Koesis& Szepesváni 2006) to balance the exploitation and the exploration in the node selection. Assume are node N the action criteria is
V Emecusy n(N's 1+n(Ni,e))
ccV'.e.) e.) n(N',e,) +
e" = arg max eyEC(A1)
(4)
C(N') indicates the events already expanded in A n(V', .ey) is the count for selecting ej node A in previous rollouts, and c(NVi,e) denotes the cumulative reward of selecting ej node Ari The first component is exploitation: we select the node with a high average reward. The second component corresponds to exploration: move to 's child node by removing the event ex from
select the node with few simulations. We select and
4.3.3 NODE EXPANSION
The strategy of node expansion significantly influences the performance because it affects the search space and hence the best node's 's quality. Previous works expand all possible children for any selected node (Yuan et al. 2021b. Instead, we only expand the best potential node refine the search space. Assuming the selected node A is expandable (i.e., the number of children is less than the number of events contained in the node), the explorer invokes the navigator (Sec. scores:
obtain potential
arg min ho(ez,ex) e, eyEN' (C(N))
(5)
5

---

Published as a conference paper at ICLR 2023
N /C/C((") means possible events which are not expanded in the previous rollouts. We remove the most unimportant event e" to expand new node. Since the navigator is learned in advance and infers the score quickly, the additional cost is negligible. We could also expand the top-k candidates or induce randomness to trade off the exploitation and exploration in the expansion step. For example, select e to expand with probability c and select random unexplored ej with probability
The node selection and expansion are done alternatively. We start from the root node. We expand new child node(s) for the root according to Eq. E Then we choose the node with the highest value based on Eq. from the root's original and new child nodes and move to it. Next we repeat the expansion and selection from the new node. The process ends when the current node is identified as a leaf node, c.g,, the node has less than five events.
4.3.4 REWARD SIMULATION AND BACKPROPAGATION
The reward is simulated by the temporal graph model. In detail, we compute the reward of a leaf node r(Ateal) by computing the negative cross entropy loss ! using Eq. [ where R / In backpropagation, all the nodes A/ from root to the leaf will update va(:-)) and c(--)) by adding the leaf node's 's reward and one respectively, i.e., c(V",, e) = c(N", ex) + r(Ntea)) n(N", ee) = nWN", et) + 1. is the action selected at N"
5 EXPERIMENTS
In this section, we evaluate the performance of T-GNNExplainer with several baseline explain- ers. We first describe synthetic datasets, real-world datasets and target models in Sec. [. Then we present the detailed experimental setup, including baselines and evaluation metrics in Sec. 5.2 Sec.5.3 a quantitative evaluation to demonstrate that T-GNNExplainer could surpass the baselines up to ~50% improvement in the Area Under the Pidelity-Sparsity Curve (AUFSC). Furthermore, we investigate the navigator's effect in Sec. 5.4] Finally, a case study in Sec. 5.3 constructed to show the explanations provided by T-GNNExplainer and navigation weights. The dataset statisties, target models' performance, and running time of all the methods are presented in Appendix. The code and datasets are attached in the supplementary.
5.1 DATASETS AND TARGET MODELS
Real-world datasets: We adopt two typical real-world temporal graphs: Wikipedia and Reddi The Wikipedia dataset consists of 9300 active users and top edited pages and 160,000 temporal edges. A 172-dimensional user editing feature accompanies each temporal edge. The Reddit dataset analogous to Wikipedia with ~11 ~,1,000 active users and subreddits and 700,0000 temporal edges. The 172-dimensional temporal edge features come from user post contents.
Synthetic datasets: We utilize the Hawkes process (Hawkes) I971] I) and tick library (Baery et al, 2017) to generate synthetic datasets. In Fig. 2 we define four types of events (E₁ ~ E4) in graph. According to the multivariate Hawkes process, the intensity of an event is divided into two parts: endogenous and exogenous. For example, Eg has endogenous intensity 0.5 to happen because of itself, and Ea has exogenous intensity 2 influenced by the happening of Ez. Given a pre-defined event relation including endogenoosslexogenous intensities, we adopt the tick library to simulate sequence of events with timestamps. We generate two synthetic datasets with ~ 10000 timestamps based on event relation v1 and v2 Fig. More details are described in Appendix.
Target models:
We adopt two recent state-of-the-art temporal graph models TGAT (Xu et al. 2020
and TGN (Rossi et al. 20200. TGAT presents temporal attention layer to aggregate node's pre- vious neighbours in chronological order and time encoder to encode temporal information. TGN further proposes a memory store and update module to persist each node's temporal state. A point process model Transformer Hawkes Process (THP) is also compared in See. Sec. in Appendix. These models are trained in a self-supervised manner for real-world datasets, i.e., events seen on the graph positive samples and randomly chosen unseen events are negative ones. For synthetic datasets,
A larger reward indicates better solution, hence negative CR is consistent with the objective in Eq. 2
3 http::/ssaapsstanfiie www.nfodd.ddujjotidwiiiii... eduujodiiwwikkieeii...v hhtp://saap.staa www.aaap.staa......eo. wew.foodddddujoiii/eddtt......

---

Published as a conference paper at ICLR 2023
Temporal graph structure
relation
Event relation v2
Ein
3
0.5
0.5
0.5
Predict
Figure 2: Synthetic temporal graph and pre-defined event relations. Values on nodes indicate en- dogenous intensities. Values on edges define exogenous intensities. Green edges are positive influ- ences while red edges are negative influences. Grey edges reflect no influence.
happened E3 timestamps are positive samples, and uniformly sample random timestamps as negative samples.
5.2 BASELINES AND SETUPS
Baselines: We compare the performance of T-GNNExplainer with several baseline methods. (1) We implement PGExplainer (PG) in (Luo et al. 2020) and adapt for the temporal graph scenario. The adapted PG computes weight to each event instead of each edge. The input information for event ej is the same as the Ze,e, in Eq. 3
We add the output score of PG to the attention weights in the target model for all layers and use the same training objectives T-GNNExxlainner (2) For the attention based explainer (ATTN), we extract the attention weights in TGAT/TGN and average the values over all layers. The averaged weights are regarded as importance scores. (3) Besides, implement a straightforward explainer by perturbing one candidate event (PBONE), i... we compute the importance of each event Ej E G by feeding g*/ /{e)) into the target model. Moreover, also compare with the seff-interpretable THP-based THPExplainer in Sec. A.8 in Appendix.
We adopt the fidelity F(d(f((")))) f(*)) and the sparsity Sp(R*, g*) to evaluate the performance. Instead of using the difference between the original and new pre- diction probabilities to define the fidelity in the previous work (Yuan al. 2020bp, we use the difference between logits because logits could exhibit explainers performance more clearly. The fidelity defined as Fid(f(g*)()
Evaluation metrics:
(RR)) = 1Y,, ()(f(R)) [ex) -f (ex)) + 1(Y,- The higher fidelity and higher sparsity mean better result. We draw the fidelity sparsity curve and compute area under the curve AUFSC to evaluate the performance. A larger AUFSC indicates a better performance. Note that AUFSC may be negative because fidelity could be negative.
()(f()))))) [ex] f [ex))(e)) [ex)). Besides, sparsity is defined as Sp =
Furthermore, we also use the metric Best Fid, indicating the best fidelity ever found by the explainer without sparsity limitations. For T-GNNExplaieer, we traverse all tree nodes to find node with the best fidelity. For baseline explainers, rank all the candidate events in ascending order by their importance scores produced by the explainer and successively preserve top events to find the subset with the best fidelity.
Experimental setup: We use a two-layer MLP with 128 hidden units to instantiate the navigator he- We set the exploration parameter À to 5 and the rollout number to 500 in the explorer. Following the same setting in TGAT and TGN, we adopt a two-layer attention architecture and harmonic encoding for timestamps. We train both TGAT and TGN with 70%, 15%, and 15% splitting scheme of datasets based on timestamps. For all methods, we limit the number of candidate events to 25 and randomly sample 500 events in the test dataset as target events for the explanation. We use a machine with an RTX 2080 GPU and a 48-core Intel(R) Xeon(R) CPU@2.2GHz. More hyper-parameters are listed in Appendix.
5.3 PERFORMANCE COMPARISON WITH BASELINES
In this section, we report the quantitative results in Table I and Table 2 for real-world and synthetic datasets respectively
D We find that T-GNNExplainer outperforms baseline explainers significantly and consistently for two metrics on all the datasets. On the real-world datasets, the gains of AUFSC (Best Fid) are up to 53% (26%), (45%), 147%,,,) and 74% (50%) w.r.t to the leading baseline
*Best results in bold and the second best are underlined.

---

Published as a conference paper at ICLR 2023
Table
Best fidelity (1) and AUFSC (1) achieved by each explainer on real-world datasets.
Wikipedia
Reddit
TGAT
TGN
TGAT
TGN
Best Fid
AUFSC
Best Fid
AUFSC
Best Fid
AUFSC
Best Fid
AUFSC
ATTN
0.891
0.564
0.479
0.073
0.658
-0.654
0.575
0.289
PBONE
0.027
-2.227
0.296
-0,601
0.167
-2.492
0.340
-0,256
PG
1.354
0.692
0.464
-0.231
0.804
-0.369
0.679
0.020
T-GNNExplainer
1,836
1,477
0.866
0.590
1.518
1.076
1.362
1.113
Table 2: Best fidelity (1) and AUFSC (f) achieved by each explainer synthetic datasets.
Synthetic vl
Synthetic
TGAT
TGN
TGAT
TGN
Best Fid
AUFSC
Best Fid
AUFSC
Best Fid
AUFSC
Best Fid
AUFSC
ATTN
0.555
0.390
2.178
1.624
0.605
0.291
0.988
-0,634
PRONE
0.044
-2.882
0.000
-3.311
0.096
-4.771
0.320
-5,413
PG
0.476
-0.081
2.006
0.626
1.329
-0.926
1.012
-1.338
T-GNNExplainer
0.780
0.666
2.708
2.281
1.630
1.331
4.356
3.224
in four scenarios. ATTN and PG obtain comparable performance while PBONE performs the worst. The results of synthetic datasets are analogous to those of real-world datasets.
Besides, illustrate the fidelity-sparsity Fig. S T-GNNExplainer achieves the highest final fidelity than other baselines and is also the highest under given sparsity threshold. Moreover, with relatively small sparsity threshold, e.g.. 0.2, T-GNNExplainer can already find solution with high fidelity compared to its final best value, which indicates that T-GNNExplainer explores the low-sparsity event subsets efficiently. Without the searching procedure, the fidelity of PG and ATTN increase slowly. PBONE performs the worst in all scenarios because it treats each event independently. More performance investigations of the navigator are illustrated in Sec. A.5 and Sec. A.6 in Appendix.
the real-world datasets intuitively, shown in
(a) TGAT, Wikipedia
(b) TGN, Wikipedia
(c) TGAT, Reddit
(d) TGN, Reddit
Figure 3: Fidelity-sparsity comparison of explainers on real-world datasets with target models.
5.4 EFFICIENCY INFLUENCE OF THE NAVIGATOR
In this section, investigate the efficiency enhancement of the navigator. We the rollout number to 500 for with navigator and without navigator. Here, we compare the time exhausted to achieve fidelity threshold. Let the best fidelity denote the larger final fidelity between with navigator and without navigator. We set the fidelity threshold to 0.8 0.8xbext, fidelity to compare the time exhausted.
Results for all the datasets and both models are shown in Fig. The results are averaged over all target events. We can find that the running time of with navigator is always less than that of without navigator under all settings. The efficiency improvement with navigator about 70. %, 60.1%. 48 2%, and 28.1%. 1%. On the synthetic datasets, can observe similar results as those on real-world datasets. The speedup of the navigator about 83.85%, 96.43%, 78.48%, and 43.66% respectively under four synthetic settings. Overall, the navigator effectively speeds up the searching procedure of the explorer to achieve reasonable solutions. More runtime comparisons with basclines and complexity analysis of T-GNNex illustrated in Sec. A.4 in Appendix.
8

---

Published as a conference paper at ICLR 2023
302
200
TOAT, opoche
TGAT, HAM
TOAT sm
TUK: V
FSN velpect
TGR modil
TGX sPAMEL
TUN, ars ANLVE
(a) TGAT
(b) TGN
Figure 4: Efficiency of the navigator on all the datasets with target models.
5.5
CASE STUDY
In this section, we visualize explanations for target events with TGAT on the synthetic dataset, Specifically, we show the scores given by T-GNNExplainerr the navigator, and the target models' intrinsic attention module. The values are normalized [0, 1]. Since T-GNNExplainer returns a subset, assign to the selected events and 0 to others. The bar colours consistent with type colours in Fig. 2 The light green and green colours represent positive events to trigger the event Eg, while the red colour indicate negative events to inhibit the event Fgz. The grey irrelevant events. Because we explain the happened target event Fgz, good explainer should assign relatively high scores green bars and low scores to gray and red events.
Fig. 5 and Fig. present the cases on synthetic vl and v2. ATTN finds a dense event subset including irrelevant or negative events (Fig. ) overlooks some previous positive events (Fig, b(c)). The navigator obtains a better result than ATTN. It assigns high scores to green bars and almost eliminates the gray and red ones. Assisted by the navigator, T-GNNExplainer utilizes the explorer
to further filter the events and make sure the final result is concise. Overall, our final event set is sparse while it remains the most important events leading to the occurrence of the target event E3.
OURS
NAVIGATOR
ATM
K6-
266
(a) OURS
(b) NAVIGATOR
(c) ATTN
Figure 5: Synthetic v1, target event index 7380.
g
(a) OURS
(b) NAVIGATOR
(c) ATTN
Figure 6: Synthetic v2, target event index 2013.
6 CONCLUSION
In this paper, we propose the T-GNNExplainer for temporal graph model explanation. We design a novel explorer-navigator framework to search for explanations effectively and efficiently. Experi- mental results illustrate the superiority of T-GNNExplainer on both synthetic and real-world datasets with two typical temporal graph models. Since instance-level explanations can be local and sensitive to the input, exploring model-level explanations for temporal graph models could be future work. Besides, how to generate simulated datasets to mimic real-worle dynamic graphs more accurately also deserves further investigation.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We thank Prof. Shenghong Li and our anonymous reviewers for delightful discussions and for pro- viding feedback manuscript. This work is funded by the National Nature Science Foundation of China under Grant $1971283, Shanghai Municipal Science and Technology Major Project under Grant 2021SHZDZX0102, and Shanghai Pujiang Talent Program No. 2IPJ1402900
REFERENCES
Emmanuel Bacry, Martin Bompaire, Stéphane Gaiffas, and Soren Poulsen. Tick: python library for statistical learning, with particular emphasis on time-dependent modelling. arXiv, 2017.
Alain Barrat, Valeria Gelardi, Didier Le Bail, and Nicolas Claidiere. From temporal network data to the dynamics of social relationships. Proc. Royal Soc. B, 288(20211164) 2021.
Hejie Cui, Wei Dai, Yanqiao Zhu, Xiaoxiao Li, Lifang He, and Carl Yang. Brainnnexplainer An interpretable graph neural network framework for brain network based disease analysis. arXiv preprint arXiv: 107.05097, 2021.
Hanjun Dai, Yichen Wang, Rakshit Trivedi, and Le Song. Deep coevolutionary network: Embedding user and item features for recommendation. arXiv, 2016.
Finale Doshi- Velez and Been Kim. Towards rigorous science of interpretable machine learning. arXiv,, 2017.
Farzan Farnia and David Tse. A minimax approach to supervised learning. Advances in Neural Information Processing Systems, 29, 2016.
Zhen Han, Peng Chen, Yunpu Ma, and Volker Tresp. Explainable subgraph reasoning for forecasting temporal knowledge graphs. In International Conference Learning Representations, 2020.
Alan G Hawkes. Spectra of some self-exciting and mutually exciting point processes. Biometrika, 58(1))83-90, 1971.
Wenchong He, Minh N Vu, Zhe Jiang, and My Thai. An explainer for temporal graph neural networks. arXiv preprint arXiv:2209.00807, 2022.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey. JMLR, 21(70):1-73, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In ECML, pp. 282-293. Springer, 2006.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in tem- poral interaction networks. In KDD, pp. 1269-1278, 2019.
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 ICLR, 2021a.
Xiaoxiao Li, Yuan Zhou, Nicha Dvomek, Muhan Zhang, Siyuan Gao, Juntang Zhuang, Dustin Scheinost, Lawrence H Staib, Pamela Ventola, and James Duncan. Braingnn: Interpretable brain graph neural network for fmri analysis. Medical Image Analysis, 74: 74:102233, 2021b.
Zhao Li, Pengrui Hui, Peng Zhang, Jiaming Huang, Biao Wang, Ling Tian, Ji Zhang, Jianliang Gao, and Xing Tang. What happens behind the scene? towards fraud community detection in e-commerce from online offline. In WwW, 2021c
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In NeurlPS, volume 33, pp. 19620- 19631, 2020.
10

---

Published as a conference paper at ICLR 2023
Fabiola SF Pereira, João Gama, Sandra de Amo, and Gina Oliveira. On analyzing user preference dynamics with temporal social networks. Machine Learning, 107(11):775-11733 2018.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. In ICML, 2020.
Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning en- hanced explainer for graph neural networks. In NeurlPS, volume 34, 2021.
Yong-Min Shin, Sun-Woo Kim, Eun-Bi Yoon, and Won- Won-Yong Shin. Prototype- explanations for graph neural networks (student abstract). 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Fukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurlPS, volume 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Minh N Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. NeurIPS, 2020.
Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat seng Chua. Causal screening to interpret graph neural networks, 2021a. URL sttps::/openreet www.ne/foorrmm....
hzKv5vx2fgel
Xuhong Wang, Ding Lyu, Mengjian Li, Yang Xia, Qi Yang, Xinwen Wang, Xinguang Wang, Ping Cui, Yupu Yang, Bowen Sun, al. Apan: Asynchronous propagation attention network for real- time temporal graph embedding. In SIGMOD, pp. 2628 2638, 2021b.
Tingsong Xiao, Lu Zeng, Xiaoshuang Shi, Xiaofeng Zhu, and Guorong Wu. Dual-graph learning convolutional networks for interpretable alzheimer's disease diagnosis. In International Confer- ence on Medical Image Computing and Computer-Assisted Intervention, pp. 406-415. Springer, 2022.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive represen- tation learning on temporal graphs. In ICLR, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2018.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Gen- erating explanations for graph neural networks. In NewrlPS, pp. 2250-9251, 2019.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In KDD, pp. 430-438, 2020a.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. arXiv, 2020b.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. ICML, 2021.
Yao Zhang, Yun Xiong, Dongsheng Li, Caihua Shan, Kan Ren, and Yangyong Zhu. Cope: Modeling continuous propagation and evolution interaction graph. In CIKM, pp. 2627-2636, 2021.
Simiao Zuo, Haoming Jiang. Zichong Li, Tuo Zhao, and Hongyuan Zha. Transformer hawkes process. In Proceedings of the 37th International Conference on Machine Learning, ICML'20.
JMLR.org, 2020.
11


Reviews:
[{"review_id": "ycTEDfo_-z", "reviewer": "Reviewer_zSpG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper \"Explaining temporal graph models through an explorer-navigator framework\" proposes a graph neural network (GNN) explainer model for temporal graphs. More specifically, the proposed model has mainly two components which are explorer and navigator. The explorer is to find the event subsets for explanation, and the navigator is to reduce the search space. The authors conduct various experiments to evaluate the performance and show that the proposed model can achieve superior performance than others. ", "summary_of_the_review": "In general, the paper seems to be well-organized and the proposed model can be significant. The idea of taking two advantages of search- and learning-based GNN explainer would be novel. But as aforementioned, 1) several notations need to be revised to be clearly understood, 2) enough literature survey is conducted and 3) More experiments and some illustrations seems to be needed for better version of paper.", "strength_and_weaknesses": "Strength\n- The proposed model is well designed. The authors take the advantages of search- and learning-based GNN explainer together. More specifically, the authors apply search-based explainer to explorer for finding the best results and use MCTS to reduce search time. Moreover, they train the navigator to learn the inductive relationships.\n\n- It can be a significant contribution since GNN explaining model for temporal graphs is under-explored.\n\n- Overall, the paper seems to be well-organized. In my view, the authors carefully composed the paper to understand what GNN explainer is, what the proposed model is, and so on.\n\nWeaknesses\n- Several notations are confusing to me. For example, the authors reuse the notation G^i in section 4.3.2, with (minorly) different meaning. But it can be confusing for readers to follow the paper. The reviewer expects that the authors use clear notations to be understood more easily.\n\n- Literature survey would not be enough. The authors claim that it is the first explainer for temporal graph models. But Z. Han et al., \"Explainable subgraph reasoning for forecasting on temporal knowledge graphs\" at ICLR 2021 tried to construct an explaining model for temporal knowledge graphs. In my view, although it is applied to temporal knowledge graphs, it needs to be mentioned and discussed in the related work section.\n\n- I think that several experiments are more needed. As far as I can tell, many works for GNN explainers (e.g., D. Luo et al., \"Parametrized explainer for graph neural network\" at NeurIPS 2020) illustrated the performances, and so that there can be several illustration rather than figure 5 and 6 in this paper.\n\n- Performance comparison between the proposed model with navigator and without navigator seems to be needed. The authors show the efficiency of the navigator with figure 4. But there is no performance (Fidelity, sparsity) comparison between them. If there is the performance comparison, the necessity of navigator can be more convinced. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "lJkYFjTt6Y0", "reviewer": "Reviewer_3TUm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The author proposed a new method for explaining temporal graph models. Most of the previous explainer models only focus on static graphs. To achieve the goal, the authors combine the explorer framework that uses Monte Carlo Tree Search with navigator frameworks that guide the search by predicting the correlation between an event to the target event. The authors then demonstrate the benefit of the proposed model in real-world and synthetic data.  ", "summary_of_the_review": "The paper has a nice contribution to temporal graph explainability. However, there are a few weaknesses, particularly in terms of the novelty of the proposed method.\nBased on the considerations above, I recommend a weak acceptance.", "strength_and_weaknesses": "Strengths:\n- The proposed method is one of the first graph explainer models for temporal graphs.\n- The combination of the MTCS explorer and the navigator is interesting.\n- The author shows the performance benefit on temporal graph explanation in terms of fidelity and sparsity.\n\nWeakness:\n- The idea of using parameterized navigator as well as MTCS explorer has been proposed in the previous graph explainers.\n- The use of MTCS in the solution search makes the running time relatively slow. The authors have not discussed the runtime complexity as well as the runtime comparison with the baselines. In static graphs PGExplainer runs much faster (in milliseconds). It will be good to see the runtime-performance trade-off as PGExplainer can also be modified to handle temporal graphs as well.\n- There is related work on the temporal graph explainer that was submitted to arXiv not long before the ICLR deadline, which may indicate concurrent works. However, it would still be beneficial if the author could compare and contrast with the work.\n> He, Wenchong, Minh N. Vu, Zhe Jiang, and My T. Thai. \"An Explainer for Temporal Graph Neural Networks.\" arXiv preprint arXiv:2209.00807 (2022).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0Jc6SZSblV", "reviewer": "Reviewer_J8qS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposed a post-hoc and instance-level explainer called T-GNNExplainer for temporal graph neural network on continuous-time dynamic graphs. The paper provides experimental evaluations on the effectiveness of the proposed explainer on real-world and synthetic datasets. \n", "summary_of_the_review": "The paper proposed a post-hoc and instance-level explainer called T-GNNExplainer for temporal graph neural network on continuous-time dynamic graphs. It constructed a navigator and explorer, where the navigator proposed by the paper can play the role of attention to output weights and help the optimization of the Monte Carlo Tree Search. However, the novelty of this paper is not very strong, and more experiment needs to be included. See the strength and weaknesses section for details\n", "strength_and_weaknesses": "Strength:\n1. The paper proposes an interesting idea of using Monte Carlo Tree Search to select the optimal edge (event) set that explains a prediction. \n\n2. The paper proposes a navigator (multilayer perceptron) to learn Monte Carlo tree weights to speed up the Monte Carlo Tree Search. \n\n3. The paper simulates synthetic datasets by the multivariate Hawkes process and some pre-defined event relation rules. The experiments on the synthetic datasets demonstrate the effectiveness of the proposed method.\n\nWeaknesses:\n1. For related works, the paper only covered post-hoc interpretative methods, where the explanatory model is trained on top of the well-trained classification model. However, there are also many works on intrinsically interpretable models, e.g., BrainGNN[1] and dGLCN[2].\n\n2. In experiments, the proposed method has many hyperparameters, but the paper did not provide parameter sensitivity analysis. It will be nice to add hyperparameter tuning results, such as N_{r}, \\lambda. \n\n3. Furthermore, considering that the algorithm proposed by the authors is plug-and-play, the paper only validated the idea on two instance-level post-hoc methods, TGAT (2020) and TGN (2020). It will be nice to add experiments on other target models to further demonstrate the effectiveness of the proposed method. There are also some baselines from non-post-hoc explainers (e.g., dGLCN[2]) and model-level algorithms (e.g., XGNN[3]). \n\n4. The overall writing is good, but there are some minor issues. The paper should use the full spelling for the first mention of the acronym, such as GNN in the abstract, and CR on page 6. The authors should use math equation language instead of programming language in Eq. 6.\n\n\n[1]BrainGNN: Interpretable Brain Graph Neural Network for fMRI Analysis\n[2]Dual-Graph Learning Convolutional Networks for Interpretable Alzheimer's Disease Diagnosis\n[3]Xgnn: Towards model-level explanations of graph neural networks\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster