[Re] Explaining Temporal Graph Models through an Explorer-Navigator Framework
Authors: Miklós Hamar
Matey Krastev
Kristiyan Danielov Hristov
David Beglou
Venue: Accepted by TMLR ()

Abstract: Temporal graphs model complex dynamic relations that change over time, and are being used in a growing number of applications. In recent years, several graph neural networks (GNNs) were proposed, designed specifically for this temporal setting (Xu et al., 2020; Rossi et al., 2020). However, these models are notoriously hard to interpret. For this reason, the original authors (Xia et al., 2023) propose the Temporal GNN Explainer (T-GNNExplainer) – an explorer-navigator framework to efficiently compute sparse explanations of target Temporal GNNs. We reproduce the main findings of the original paper, extend their work by proposing a different type of navigator method, and examine in detail the explanation capabilities and efficiency of the provided framework within various model and hyperparameter settings. We confirm that their explainer outperforms the other baselines across nearly all datasets and metrics. Our findings suggest the navigator helps bias the search process, as well as that T-GNNExplainer can find an exact influential event set. Moreover, we examine the effect of different navigator methods and quantify the runtime-fidelity tradeoff controlled by two hyper-parameters.

Published in Transactions on Machine Learning Research (05/2024)
[Re] Explaining Temporal Explorer-Navigator Framework
Graph
Models
through an
Miklós Hamar University of Amsterdam
mukkoo.homorrrstudennn..uu
Matey Krastev University of Amslerdam
madeyy.bruskeuu@sstdddd......v
Kristiyan Hristov
brsttigg.Iristoofttdddddd.....
University of Amsterdam
David Beglou
david. huniil.bgllou@sstudeer.....uu
University of Amsteriam
Reviewed on OpenReview: https: // openreview. net/ forum? id= FI1XvupchC
Abstract
Temporal graphs model complex dynamic relations that change over time, and are being used in a growing number of applications. Recently, several graph neural networks (GNNs) were proposed, designed specifically for this temporal setting (Xu al. 2020 Rossi al, 2020). However, these models are notoriously hard to interpret. For this reason, the original authors (Xia et al.) 2023) propose the Temporal GNN Explainer (T-GNNExplainer) an explorer-navigator framework to efficiently compute sparse explanations of target Temporal GNNs. We reproduce the main findings of the original paper, extend their work by proposing & different lype of navigator method, and examine in detail its explanation capabilities and efficiency within various model and hyperparameter settings. We confirm that their explainer outperforms the other baselines across nearly all datasets and metrics. Our findings suggest the navigator helps bias the search process and that T-GNNExplainer can find an exact influential event set. Moreover, we examine the effect of different navigator methods and quantify the runtime-fidelity fidelity trade-off controlled by two dyper-parameter.
1 Introduction
Graphs and complex relational networks are well-known and studied tools for modelling enormous variety of natural processes, being employed in nearly every domain. Similarly, Temporal Graphs are specific subset of graphs designed to model complex dependencies within data, that may evolve across different time
steps [Kostakos] 2009). Within Temporal Graphs, nodes and edges between data points can dynamically change with time, which makes them particularly useful for complex applications such as traffic prediction
and forecasting. action identification, and anomaly detection, among others (Zhao et al. 2020 Cai ct al. Yan et al. 2018).
2021
The greater the importance of the applications of such models, the greater the need for more insight into their workings, which ensures that the decisions of the model are fair, unbiased and logically sound. In particular, Graph Neural Networks (GNNs), have been notoriously hard to interpret. (Yuan et al.) (023). Therefore, various methods for post-hoc explanations of the decisions made by such graphs have been developed instead. However, many those techniques fail to trivially apply to temporal graphs, as the latter are relatively novel models. To explain why a Temporal Graph Neural Network (T-GNN) made certain prediction, one might want to find the subset of events preceding the current prediction, which has the highest in influence.

---

Published in Transactions on Machine Learning Research (05/2024)
Preferably, these explanations should also be sparse, in other words, only small number of past events should be selected, because it helps interpretability.
To compute such explanations, Xia et al. (2023) propose the T-GNNExplainer method, which performs Monte Carlo Tree Search (MCTS) guided by an inductively trained navigator to efficienlly compute sparse and accurate explanations. They demonstraate the performance of their explainer by comparing against several baselines on two metrics. They also show evidence that the navigator can efficiently guide the search process. Finally, they show a case study, where they demonstrate the correctness of the computed explanations.
After the original paper was published, Chen & Ying (2023) proposed another approach, termed Temporal Motifs Explainer (TempME). Temp.M is a T-GNN explanation method, which trains a generalive model on the input data, coupled with the target model's predictions to generate temporally local and consistent sub- graphs of the imput graph, called motifs, with respect to some target event. TempME is shown to outperform the T--NNExplainer on nearly all datasets and metrics, making it a superior approach to the one discussed here. However, do not consider TempME in this report, as it was published after the original paper and is not within the scope of this work.
Motivation The growing number of applications for T-GNNs outlines the need for specific explanation methodology. Xia al. (2023) not only provided a framework for the generation of such applications, but also open-sourced the code foundation for the study.
We endeavoured to reproduce their experimental results and expand upon their findings. We encountered several inconsistencies between the provided code base and the authors' claims, which we sought out to interpret and compare with our experimental results, as well as to provide a better foundation for future parties to readily use the proposed framework for model explanations.
Structure of the Paper In this reproducibility study, we aim to replicate the aforementioned claims of Xia et al. 2023). Additionally, we implement and evaluate three different navigator methods and conduct an in-depth analysis of two uyper-parameters, regarding their effect on the runming time and correctness of the explanations. In the following sections, we state the scope of our report, describe the methodology proposed by the original authors, as well as our extensions to it. Then, we show our experimental setup and show our results. Finally, we summarise our results, highlighting the strengths and weaknesses of this method. We conclude our work with short feasibility study and motivate future work.
2 Scope of Reproducibility
The main contribution of the original paper (iia al., 2023) method, which utilizes an explorer-navigator framework to efficiently compute sparse explanations of single prediction generated by target temporal graph neural network (T-GNN). More precisely, they propose the T-GNNExplainer model, which performs guided Monte Carlo Tree Search (MCTS) to find probable explanations. The authors further claim that this method is first-of-its-kind and provide an experimental evaluation on two real-world and two synthetic datasels, using two different temporal graph neural networks (TGN by Rossi et al. and TGAT by Xu et al.). The authors also propose several different baselines and compare their performance using a metric called Arca Under the Fidelity-Sparsity Curve (AUFSC).
an instance-level post-hoc explanation
In this report, we aim to reproduce the following claims made in Xia et. al. (2023
1. Experimental results demonstrate that T-GNNExxlainer achieve superior performance with up to 50% improvements in Area under Fidelity-Spansity Curve, concerning their proposed baselines.
2. The navigator helps to bias the search process, significantly reducing the search time and improving the performance of the explorer.
3. The highly accurate explanations demonstrate the explainer find exact influential event set..
2

---

Published in Transactions on Machine Learning Research (05/2024)
In addition to reproducing the aforementioned claims of the authors, we also perform number of our own experiments to better understand the capabilities and limitations of the T-GNNExplainer method. These extensions are the following:
We note a discrepancy between the navigator method described in the paper and the provided implementation. We implement and experiment with both.
We propose a new temporal graph explanation method, deriving inspiration from the original au- thors' proposal for an MCTS explorer with navigator neural network and compare its performance with that of the original T-GNNExplainer model.
3. We experiment with the number of candidate events that the explainer models consider during inference, and analyse the runtime-fidelity trade-off as a function of rollouts of the MCTS algorithm.
3 Methodology
3.1 Problem Formulation
For the sake of our arguments, we define some notation conventions, derived entirely from Xia et al. (0023 A temporal graph g = S) can be regarded as an ordered sequence of events (or interactions), S (ei, .). Each event e; E S is tuple of the form (u,, U, t,, aft;), where u, and e are the source and target nodes (set N),, t, E R is the timestamp of the event and att, R is an attribute vector of d dimensions. Unlike static graphs, where the nodes and edges are fixed, temporal graphs develop over time.
Temporal Graph Neural Networks The authors of the paper use the encoder-dccoder framework proposed in Kazemi et al. (2020) to define a temporal graph neural network (T-GNN). The encoder learns the dynamic embedding of the nodes and edges (or events) of the imput graph, while the decoder uses these embeddings to predict future events. More precisely, a T-GNN defined as second-order function
2
where is a d-dimensional vector space of node and edge embeddings. By writing fe(G") we denote the probability that event Eμ occurs time t given the history of the graph up time the denoted as G predicted by the T-GNN model. In the following, will refer to such models target models.
Objective The aim is to discern the key events influencing the prediction of given model at a specific time step (t&). This involves identifying a smaller, significant portion of the input graph, R*, which closely mirrors the model's prediction on the full input graph g*.
Performance metric Because the objective is to find the most influential events the input graph, we usually do not have access ground truth explanations. The original authors instead use fidelity as the main performance metric. Fidelity the ratio between the prediction of the target model on the entire graph Gi and the prediction the explanation. Note that the full input graph trivially has the highest fidelity. To avoid this, the authors also use spersity as a second performance metric. Sparsity is the ratio between the number of events in the explanation and the number of events the input. We can combine these two metrics by plotting the maximum achieved fidelity given a certain sparsity constraint, i.c. the fidelity-sparsity curve. Thus, the Area Under Fidelity-Sparsity Curve (AUFSC) is used as the main performance metric. higher AUFSC indicates better performance.
the explanatory sub-graph R The higher the fidelity, the more accurate
3.2 Temporal Graph Attention (TGAT)
Albeit not explicitly defined Xia et al. (023)) the TGNN-Explainer model, as well as one of the basclines relies heavily on the Temporal Graph Attention (TGAT) block, which is employed in the architectures of both TGAT and TGN target models (Xu et al. 2020: Rossi et al. 2020 The TGAT block uses multi-head,
3

---

Published in Transactions on Machine Learning Research (05/2024)
Mux
No.
7g
E
N₂.
No
T
A
S
Target Event
No
N₂
22
Nug
Nwp
T2
Ea
8g
Feature Encoder
Na
No.
Nus
Nus
T3
5
Candidate
Eventa
No.
No.
Te
Ba.
No.
No.
Ta
MLP
Figure 1: Visualization of the inner structure of the Parameterized Graph Explainer (Luo et al. 2020 adapted for the temporal graph setting. The input representation (source node features, target node features. event time features, and edge features) of the target event is concatenated with the representations for all candidate events considered.
dot-product self-attention layer adapted for temporal setting. Given a candidate event eg at time t well as its neighbouring events e; [ee,, (x) S, at corresponding times 4. The TGAT block takes input the hidden representations [hv]ll (He,e)) of these events and uses a relative temporal embedding
function T to create the input matrix Z = [l + (()) [7, + o(tx sase--55))) ts)leseN(es.tt)
[uu et al. 2020
Then, following the standard definition of the dot-product self-attention mechanism Vaswani et al.
2017
the TGAT block with M 2 1 heads computes the attention scores {Y (eE((ee)))) for head m I M as
explq" Im=o exp(q"
Am
where = 2 is the query vector and K2 is the 1th row of the key matrix K = ZWK- Next, we use the value matrix V = ZWy to obtain the output Attn Q, K, V) \ The weight matrices Wo, W and Wr are learned projection matrices /Vaswani et al. 2017), the superscript. ()m refers to the index of the attention head m S M. Finally, the TGAT block concatenates the outputs of the M different attention heads and feeds them through feed-forward neural network s(,0) with ReLU activations to obtaín the output hidden representation
ha = ReRLUUg(AAAt 1:M (Q, V)+,))
Ultimately, the TGAT model contains block the hidden representation h of the targel event, the outputs of the (L- 1)st block are the hidden representations of its neighbourhood e; E (eex, and so on. So, TGAT model with L blocks considers the (L h)-hop neighbourhood of the target event. For further details, please refer to Xu et al. 2020).
such TGAT blocks, one after the other. The output of the Lth
The authors of Xia et al. 2023) use the attention weights Ae, in their implementation. More precisely, given a set of candidate events Cj the (L - 1)- neighbourhood of given target event es, they compute the mean attention scores these candidate events
Aggregated Attention Scores
L Ae.
Σ Xe
ΣE 8
for all events e; Cg. Here, Nr the allention score of event e; in the 7th TGAT block, averaged over the attention heads, 0 if the event is not considered in this block. Similarly, &" 1 if the event is present in the 7hh block and 8y = 0 otherwise. Details on how the candidate events are selected are discussed in
Section 3.3
These Ae, values form the basis the proposed ATTN baseline and are also adapted for use their interpretation of the PGExplainer (Luo et al. 2020) bascline. Furthermore, the implementation for PG- Explainer shared by the PGNavigator which outputs scores that guide the MCTS expansion process. We elaborate these in more detail in sections 3.3 and 3.4 respectively.
4

---

Published in Transactions on Machine Learning Research (05/2024)
3.3 Model descriptions
In this section, we describe the explorer-navigloor framework for temporal graphs, which is the main the- oretical contribution of the paper. We also describe the T-GNNExplainer model and the various baselines they proposed.
Explorer-Navigator Framework In the previous section, we defined explanations as sub-graphs of the imput graph, which maximizes the mutual information between the prediction of the target model on the sub-graph and the prediction on the entire graph. However, this is combinatorial optimization problem, which is intractable to solve in practice. Instead, the authors use approximate solution, based the explorer-navigator framework. The explorer is Monte Carlo Tree Search (MCTS) algorithm guided by a pre-trained navigator.
The navigator is a feed-forward neural network, which assigns importance scores to event pairs of the input graph. More preciscly, given sequence of events S, the navigator is defined as a function:
(S x S) + R.
The T-GNNExplainer, given a set of candidate events, spatially and temporarily close to the target event, uses this navigator to compute pair-wisc importance scores for each candidate and the target event.
Finally, the explorer is search almorithm, which considers different subsets of the candidate events to come up with viable explanations. In (Xia et al. 2023), the authors use the Monte Carlo Tree Search (MCTS) for this. The MCTS algorithm is used to find the best path in a tree, where each node represents a state of the system and each edge represents a possible action. In our problem, a state (or tree node) is a collection of events, and each edge means the removal of certain event from this collection. Thus, a tree node of events has n distinct children. The MCTS algorithm finds the (approximate) best path in this tree with the highest associated score. The score function is simply the fidelity of a set of events in given node. More precisely, given the input graph up to time step t. (g' = (V,8*), target model f(),, and set of events present in some tree node N3, (R** C 8*), the fidelity of this set of events is the binary cross-entropy between the target's 's prediction on the entire input against the prediction on the given subset:
( -
if Y;
Ad(g",R"
-(R if 0
where Y, is the ground truth label whether event e occurs not. This algorithm is deterministic because the fidelity function is deterministic given a set of events and a fixed target model f(-). Always selecting the path with the highest score is called exploitation and traversing different paths is called exploration. For the search algorithm to succeed, these two strategies should be balanced. The Upper Confidence bound applied to Trees (UCT) Koosss & Szepesvári (006)) a commonly used method to address this problem. Given a tree node N the UCT algorithm selects the best action, i.e. the removal of some event e*, from the set of events available in N by solving:
((V'c,) V Eesoury((N EC(N))
e* = aig min
n(N),e,, + A 1+n(Ni,,))
Here, C(Ni) is the set of nodes already expanded in node N n(N',, ej) is the number of times event ej was previously removed from node A and e() is the cumulative reward of removing ej. The first term selects the event with the highest cumulative reward (erploitation), while the second term selects the event with the highest uncertainty (exploration). The parameter À controls the trade-off between the two. We refer to single path selection procodure, from the root to leaf, as rollout. During scarch, a predefined number of such rollouts are executed. In each subsequent rollout, the UCT algorithm considers all the previous iterations to find the best path. Ultimately, we select the highest fidelity tree node as the explanation.
The T-GNNExplainer model utilizes this explorer-navigatee framework to compute explanations for given prediction made by target model. When called with target event, it selects
T-GNNExplainer
5

---

Published in Transactions on Machine Learning Research (05/2024)
1.0
1.0
1.0
1.0
Beet Rooowns (80
0.8-
Deet Rewere (15)
Bext Reowerd (%)
0.8
0.4
0.2
0.-
PGNavigatr
0.2
0.2
galor
PC (ND NAV)
PGNasiggato (ND NAV)
(ND NAV]
PGNNwrrpe galor (ND NAV)
0.0
0.0
0.0
0.0
100
400
200
400
000
200
300
400
600
100
200
300
400
Roilout stop
Rollout stop
Rollout stop
Rollout stop
(a) TGAT Reddit
(b) TGN Reddit
(c) TGAT Synthetic V1
(d) TGN Synthetic V1
Best fidelity- curves with and without the navigator on TGAT (a, c) and TGN (b, d) models evaluated on Reddit and Synthetic VI datasets. We denote the points where the fidelity first reaches 80% best fidelity. We can see that the navigator helps the search process in the Reddit datasct, but hinders the Synthetic V1 dataset, especially the TGN backbone.
Figure 2:
pre-defined number of candidate events (sometimes this number is referred to as threshold) and computes the importance scores using the navigator. Finally, the MCTS algorithm used to compute an explanation. It considers the candidate events decreasing order of importance.
3.4 Baselines
In addition to the T-GNNExplainer model, a first-of-its-inn temporal graph explainer, the authors propose several baseline TGNN explanation methods to compare their performance. A crucial difference between the basclines and the T-GNNExplainer is that the latter is scarch-based, while the former are not. The basclines are follows:
PBONE Obtain explanations by local perturbations of the candidate events. This is based on the as- sumption that the more influential an event is, the more sensitive the target model will be to small changes in that event.
The computed mean io scores of the target model, (Ac, Jo,eCu, as described in Section 3.2 This method is based on the assumption, that the more influential an event is, the more attention the target model pays to that event.
ATTN
PGExplainer is modified version of the Parameterized Graph Explainer model, first proposed in Luo et al. (2020). At the core of it is Multi-Layer Perceptron (MLP), denoted as ,(:,,,), f), whose paramcters, 0, are trained to predict pair-wise importance scores of imput events. The authors deviate from Luo et al. (2020) in two crucial details. First, they adapt this model to the temporal setting, via harmonic temporal embeddings. Secondly, they use the predictions of the MLP as soft-masks over the input graph, and then similarly compute the mean attention scores as in the ATTN baseline. Formally, given a target event e and corresponding set of candidate events Ck for each candidate 6, E Cs2 the importance score is computed as
ASM SM
Se,
where SM the mean attention score (as defined in Section 3.2) of the target model on event eis when evaluated on the soft-masked input {he, g(hk, h4 F)eee
3.4.1 Navigators
While the previous sections give an intuitive understanding of the explorer-navigaton framework and the proposed baselines, our main contribution to this project is the comparison of three different navigator methods. this section, we aim introduce each and clarify the key differences between them.
The authors of the paper Xia (0223) propose a navigator model, essentially feed- forward neural network, computing pair-wise importance scores between the input representations of the
MLPNavigator

---

Published in Transactions on Machine Learning Research (05/2024)
FIMRY
Fo0tyy
ATM
Al IN
4
ATTN PRONE
ATT8 PSONE
-22
-04
Sparity
Spars
Spaniit
Spansity
(a) Wikipedia
(b) Reddit
(c) Synthetic V1
(d) Synthetic V2
1.0
0.5-
0.4-
Fodttt
ATTM
AITh
ATTN PRONE
ATTS FRONE
-22
PGNowigsto
-44
Spanity
Sporiiy
Spansiyy
(e) Wikipedia
(f) Reddit
(g) Synthetic V1
(h) Synthetic V2
Figure sppesityysparsity curves for TGAT (a-d) and TGN (e-h), threshold 20. By comparing the area under these curves, one can evaluate the performance of different explainer models. The greater the area, the better the method at finding high-fidelity explanations across different sparsity constraints. We can see that the proposed T-GNNExplainer (red) out-performs the baselines in almost all cases.
target event and the candidate events. Formally, is function g(s-00,, where 0 are the learned parameters of the network, equivalent to the pre-trained parameters of the PGExplainer baseline. Given a larget event. ex and a set of candidate events e Ck. the MLPNavigator computes
Se, g h4 0),
where h h2 are the input representations. We have additionally provided visualization for how this navigator works in practice in the TGNN setting in Figure [ In the following, we will refer to this method as MLPNavigator. Note that, albeit this definition is aligned with the definition given in Xia et al. (2023) in practice, they used a slightly different method, which we discuss next.
PGNavigator As it became evident from the provided code base and subsoquent reproduction results, the navigalor method is not exactly as described by Xia et al. (2023). In fact, the candidate importance scores are obtained precisely using the method of the above-defined version of the PGExplainer baseline. To disambiguate this approach from the Aaviavig,,, in our work, we refer to this navigator as PGNavigator.
See Xia et al. 2023 sec. 4.2) for more details.
Dot Naoduettttaa Finally, to further evaluate the performance of the navigator, we propose a differ- ent approach, which we call DodProductNavigator In this method, instead of computing inductively learned pair-wise importance score between imput event pairs, we compute the pair-wise dot product of the output embedding of the target model's encoder module. As such, given a target event eg and candidate events e E Ck. we compute the importance score as
Sr;
22 Bap
where hey he, are oulput hidden representations of the larget model's encoder module (see Section 3.2 We hypothesize that a high performance on this method shows that the target model learns to encode the input graph in way, such that excitatory events appear close the target event in the embedding space. This is a desirable property since it provides an intuitive understanding of the model and its training goals, even beyond the scope of local interpretability.

---

Published in Transactions on Machine Learning Research (05/2024)
4 Experimental setup and code
We based our experiments on the code provided by the authors This repository contains the code for the larget models, the T-GNNExplainer model and the baselines. Shell scripts and configuration files are also supplied, to help run the experiments, train the target models and pre-process the datasets.
In the following, we describe the datasets we used and the results we obtainod. We also discuss the compu- tational requirements and list the typer-parameters we used in Appendix A. and A.2 respectively.
In addition, we provide detailed documentation running the explainer pipeline, structured executable scripts to reproduce all findings, well as several optimizations. Full details are available in Appendix A.3
4.1 Datasets
The authors of the paper evaluated their explainer model two real-world and two synthetic datasets. The real-world datasets are the following:
Reddit consists of posts made by the 10 000 most active users over a one month period on the 1000 most active subreddits; contains a total of 672 447 interactions between users and subreddits(Kumar et al., 2019)
Wikipedia is a collection edits on the 1 1000 most edited wikipedia pages over a one month period. It contains 8 227 editors and 157 474 interactions total (Kumar et al., 2019).
Synthetic V1 and V2 The synthetic datasets are both generated by the multivariate Hawkes process Hawkes processes are point processes, which model the
(Hawkes 1971 with different occurrence of events over time. The events are generated by simple event-relation graphs, where edges roughly correspond to probabilitics that the two nodes interact at given time step. The authors propose two different event-relation graphs and generate two datasets of approximately 10000 timestamps. They make use of the tick library (Bacry et al. 2018) to model the Hawkes processes.
The synthetic datasets fit well within the scope of this project, as they inherently contain ground truth data due to the generating hyperparameters. The authors make of the datasets particularly within the case study which aims to evaluate the accuracy of the proposed explanations.
5
Results
5.1 Results reproducing the original paper
We list the main results reproducing the authors' described experiments in Table 1a and 1b comparison, we also provide the authors' original results as well as the relative divergence ratio of our results and theirs in Tables aad 5) Furthermore, we reproduce the fidelity-sparsity curves for the different datasets and the case study of ground truth explanations, as provided by the original authors.
For a detailed
Generally, we observe a large variance in the results of the proposed evaluation metrics. The Best Fidelity in particular seems to be particularly prone large differences from setting to setting. The AUFSC metric seems less volatile, but the observed variance remains high, which complicates an accurate evaluation of the proposed method against the baselines. In the following, we atlempt to summarise our results concerning the three main claims we laid out in Section 2
Claim 1: Superior performance compared to baselines We note approximate relative difference
between the reproduced and original results the proposed explainer (PGNavigator) -19% and -46% on the TGAT, and the TGN target models, respectively. Regardless, the explainer still outperforms the other baselines with gains across the Wikipedia, Reddit, Synthetic V1 and V2 datasets on AUFSC (Best
http:://opaneeieeree////ommmraa ZhvcYbcJ
http://mmp..tafffrtteee///aaaa/
8

---

Published in Transactions on Machine Learning Research (05/2024)
Wikipedia
Reddit
Synthetic V1
Synthetic V2
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
ATTN
0.622
0.179
0.060
-0.085
0.812
0.514
0.466
-0.936
PBONE
1.024
0.628
0.708
0.442
1.260
0.869
1.212
0.817
PG
0.678
-0.306
0.746
0.228
0.685
-0.375
0.548
-0.829
PGNavigator
1.155
0.842
0.789
0.720
1.513
1.143
1.155
0.444
MLPNavigator
1.182
0.777
0.795
0.605
1.395
0.881
1.162
0.368
0.987
0.469
0.783
0.713
1.253
0.598
1.223
0.596
(a) i Best Fidelity (f) and AUFSC (f) achieved by each explainer on TGAT model.
Wikipedia
Reddit
Synthetic V1
Synthetic V2
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
ATTN
1,502
0.889
1.660
-0.677
0.515
0.313
0.145
-1.466
PBONE
1.814
0.886
2.813
-0.290
0.648
0.393
0.244
-0.629
PG
1,436
0.092
1.112
-1.903
0.460
-0.367
0.117
-2.209
PGNavigator
1.824
1.445
2.816
1.916
0.960
0.700
0.289
.1.120
MLPNavigator
2.037
1.611
2.443
0.898
0.829
0.444
0.239
-1.992
DodProducttNavggtoo
1.219
0.053
2.975
0.404
0.943
0.317
0.291
-1.391
(b) f Best Fidelity (1) and AUFSC (f) achieved by each explainer on TGN model.
Table 1: Results for each target setting. Best score is emphasized and sccond-best is underlined. We can see that the T-GNNExplainer variants (last three rows) dominate across almost all datasets and target models.
Fidelity) of 31%())%), 62%,,%%), 32%())))) and -5%((-4%) on the TGAT model, as well as 63%(11)) 821)(1%), 748(4,,), (14%) on the TGN model. We further note that the sccond-best bascline in the original paper, PGExplainer does perform nearly well the authors report. The performance of the perturbation bascline PBONE, within experiments, diverges from the original paper, where it performed marginally worse than all other explainers. The ATTN baseline performs identically in most settings.
Performance within the constraints of sidelity-sparsity (Figure 3) appears comparable to the original study, Notably again, PBONE, which in the original paper was the worst performer across the various settings, performs competilively with the other baselines and marginally surpasses them on AUFSC.
Claim 2: Navigator improves performancc The authors originally claim that the navigator improves the performance of the explorer and provide quantitative evidence that the explorer, guided by the navigator crosses certain fidelity threshold much earlier than the explorer without the navigator on all datasets and target models. They show the measured running time of the explorer to find explanation, whose fidelity is at least 80% of the best fidelity found overall. Here we note that the running time in seconds is inherently volatile and largely depends on the hardware used. Instead, we plot the achieved highest fidelity explanation over the number of rollouts of the MCTS algorithm.
Figure 2 shows representative examples of our results. We observe that in the case of wollworld datasets (Wikipedia. and Reddit), the navigator improves the performance. However, this is not the case for synthetic datasets, where using the navigator causes the explainer to reach the same fidelity more slowly. This is interesting result and may be explained by noting that the synthetic dalasets represented dimensions in the imput, whereas the real-world datasets have much higher embedding dimensionality. This can cause the navigator to overfit the training data and thus provide less useful guidance to the explorer. This result is contrary to what was reported in Xia et al. 22023) even though we used the same hyper-parameter initialize it (see Appendix B
only 4
Claim 3: Sparse and accurate explanations We show explanations produced by the authors' proposed
explainer model in Figure We replicated the conditions presented in [ia et. al. 2023 sec. 5.5). Namely,

---

Published in Transactions on Machine Learning Research (05/2024)
1.0
1.0
0.8
0.8
scores
0.6
scores
0.4
0.4
0.2
0.2
0.0
7360
7361
7362
7363
7364
7385
7388
7367
7368
7368
7370
7371
7372
7373
7374
7375
7376
7377
7378
7379
1993
1994
1995
1996
1997
1998
1989
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
candidafes
candioate
candidafes
(a) Synthetic V1 Event 7380
(b) Synthetic
Event 2013
Figure 4: Explanations produced by the authors' proposed explainer model (using PGNavigator). The bar plot shows the candidate events the explainer model considered and sets all events that are part of the highest fidelity explanation 1 and all others to 0. Patterned bars represent authors' claimed results whilst bars with background fill color refer to results. Dark- and light-green columns represent excitatory events, while grey and red columns represent unimportant and inhibitory events, respectively. Both explanations were produced for the TGAT model. Note that while on the left, the reproduced explanation similarly sparse and selects mostly excitatory events, this is not the case for our reproduction on the right, where all except two events were selected, many of which are inhibitory.
evaluate the explainer over the TGAT model, event number 7380 of the Synthetic VI dataset and event number 2013 of the Synthetic V2 dataset. We can see that the explainer model can produce sparse and accurate explanations in the first case, but fails to do so in the second case. This is inconsistent with the author's results, where the explanations were line with their claims in both cases.
5.2 Results beyond the original paper
As mentioned in Section 2 on top of the reproduction of the original paper, we also conduct. number of
additional experiments. We motivate and describe these experiments and provide the results we obtained.
5.2.1 Navigators
Tables 1a and lb summarise the performance of the T-GNNExplainer, executed using different navigator implementations, as well as the performance of the basclines. We evaluated them on two metrics, namely the highest fidelity explanation computed and the area under the fidelity-sparsity curve. In general, we can see that the T-GNNExplainer variations outperformed the baselines on both metrics.
Further, we observe that the navigator proposed by the original authors (PGNavigator) marginally outper- forms the other two in most cases. The navigator described by the authors (Xia et al. 2023 (MI.PNavigator) is competitive.
Finally, the DotProduetNaviggan performed similarly competitively, albeit with a very weak performance for the Wikipedia with TGN backbone setting. This suggests that the candidate events do in fact appear similar to the target event in the Icarned embedding space of both target models for many cases and morits further exploration as an explainer method. Overall, we can conclude, as per the authors' original claim, the PGExplainer mode can be used as navigator for an MCTS algorithm to efficiently guide the search process for accurate and sparse explanations in the given settings.
Note the identical inference method PGNavigator.
10

---

Published in Transactions on Machine Learning Research (05/2024)
0.75
0.50
0.5-
0.00
treeshol 5
Iresshold
treeshod 5
Stredhold 5
treshood 10
Finaheld 10
Breshold 10
-0.25
dwsolhidd 10
thrshoold
20
thisshlld
thresoold222
Droshold
-0.00
Shrosh
0.0
0.2
044
08
08
10
0.4
0.6
0.8
1.0
0.0
0.2
0.4
08
08
10
0.0
0.2
0.8
6B8
1.0
(a) TGN Synthetic V1 (b) TGN Synthetic V2
(c) TGAT Synthetic V1
(d) TGAT Synthetic V2
Figure 5: Fidelity-sparsity curves for the two larget models on the synthetic datasets, al considered candidate events threshold (5, 10, 20, 25). The performance of the explainer grows proportionally with the number of candidate events until 20 but the performance at 25 candidate events is only marginally better than 20.
5.2.2 Number of Candidates and Rollouts
As mentioned Sections 2 we conducted hyper-parameter tuning experiments on the number of candidato events the explainer considers. This is a significant hyper-parameter, as it controls the effective search space the explainer has access for finding probable explanations. Intuitively, a higher number of candidate events should lead to more accurate explanation but also increase the time complexity of the model. The authors Xia et al. (2023) claim to have used the most recent S 25 events in the k-hop neighbourhood of the target event, but also performed experiments with 5, 10, 15 and 20 such events. We show represenlative example the resulting fidelity-sparsity curves in Figure
In our experiments, we found that the AUFSC score grows proportionally to the number of candidate events, up to 20, but at larger numbers this growth quickly becomes insignificant. To explain this result, we note that both synthetic datasots contain only four nodes and their event-relation graphs are almost trivial. As a result, the current event is always largely decided by the short-term history of the event sequence preceding the target. We also note that the optimal value for this parameter is likely much higher for real-world datasets, which are much more intricate and complex temporal graphs. We hypothesize, that the optimal value for this parameter is closcly related to the complexity of the underlying dataset.
Finally, we wanted to find an appropriate number of rollouts. This mumber directly affects the length of the search process and subsequently limits the proportion of the search space the MCTS algorithm explores. our analysis, we wanted quantify this tradooff. Figure 2 shows the highest fidelity reached by the explorer 500 rollouts. We find that these curves roughly follow cumulative Pareto distribution and 80% of the best fidelity is reached within the first se 200 rollouts.
6 Discussion
Overall, we conclude that the results of the paper are not completely reproducible, partly due to the incom- plete information about the random number generator used in their experiments. Regardless, our obtained values are marginally within the original authors' reported results.
Concerning the authors' original claims, we found that
1. The T-CNNExplainer outperforms the other baselines across nearly all datasets and metrics. How- ever, the performance of the proposed explainer model is not as high as the authors claim. We partly attribute this finding to the high volatility the proposed metrics.
The navigator increases the performance the explorer, but only for real-world datasets. For synthetic datasets, the navigator hinders the search process. We surmise that the navigator could possibly be overfitting to the training data.
The T-GNNExplainer can produce sparse and accurate explanations, but not all cases. We partly attribute this to differently trained target models (See Appendix 3 and note the need for further exploration.
11

---

Published in Transactions on Machine Learning Research (05/2024)
Additionally, evaluated three different navigator implementations and found that (i) the provided imple- mentation is marginally better than what was described in the paper and (ii) using dot product similarity between candidate and target events performs particularly badly on the AUFSC metric. This suggests that the importance of candidate events concerning a target event does not correlate well with their similarity in the embedding space of the largel models.
Finally, we also experimented with the number of candidate events the explainer has access to and found that in the case of the synthetic datasets, considering the 20 most recent events candidates yields the best runtime-fidell tradeoff. Furthermore, also found that 80% of the best fidelity is reached within the first 200 rollouts of the MCTS algorithm.
What was easy The paper provided an in-depth explanation of their methodology in a precise and concise manner. This made it easier to understand the theoretical background of their approach. Furthermore, the authors provided code basc, which saved lot of time in our experiments.
What was difficult Understanding the provided code base proved to be difficult, as it not only did not follow the conventions introduced in the paper, but it also not entirely consistent with the descriptions of the paper, which made it difficult at times to reproduce their results. Part of our contribution is that we ensure the code base can be set up and executed without errors. Moreover, we also provide some running time optimizations to the MCTS algorithm and disambiguate the naming conventions. We provide more details in Appendix A.3
6.1 Feasibility
In this section, we attempt to summarise our findings such that the reader can evaluate whether the T- GNNExplainer model feasible for real-world applications.
Earlier, in Section 3.4.1 we noted that the PGNavigator is equivalent to the PGExplainer baseline. In our experiments discussed in Section 5.1 we found that this search process improves the fidelity of the explanations by 30% and also brings 30% increase on the AUSFC metric, on real-world datasets. On the other hand, we also noted in Section 5.2 that exccuting the MCTS algorithm takes significant time and this time grows exponentially in the number of candidate events considered. Conversely, the inference time of the PGExplainer model only grows linearly in the mumber of candidates.
Further, is important to reiterate, that the PGNavigator, implemented in the supplementary material of Xia et al. (023)) is not equivalent to PGExplainer, originally described in Luo et al. (2020). The most crucial difference is that this version derives its output from the aggregated attention scores Acç as discussed in Sections 3.2 and 3.4.1 Here note that this limits the applicability of the T-GNNExplainer model to the set of models that rely on architectures similar to that of the TGAT architecture (Xu et al. 2020).
Overall, we recognise the significant improvement in the fidelity of the explanations computed by the T- GNNExplainer, but also note a siguificant running time overhead compared to less accurate, inference-only solutions. Thus, in large-scale deployment, it may be advisable to use some ensemble of inference-only explainers and only invoke the T-GNNExplainer for a select few cases, where high fidelity instrumental.
Finally, we note that the TempME model (Chen & Ying, 2023 is more recent approach, which has been shown to outperform the T-GNNExplainer model in nearly all datasets and metrics, producing more interpretable explanations.
6.2 Future work
Earlier, we noted that for synthetic datascts, observing the 20 most recent events yiclds the highest runtime- fidelity trade-off. We also note that this may not. be the case for real-world datasets. We hypothesize that this parameter is an inherent characteristic of the underlying dataset and the optimal value this parameter may be orders of magnitude larger for more complex temporal graphs. Quantifying the number of candidate events needed for good explanations as a function of the input graph's complexity would not only help with explanations but also introduce a novel aspect of characterising temporal graphs and T-GNNs.
12

---

Published in Transactions on Machine Learning Research (05/2024)
6.3 Communication with original authors
We reached out to the authors for a more detailed description of their hyper-parameteess and to inquire about follow-up research conducted since the publishing of the original article. We have not received any replies.
References
Emmanuel Bacry, Martin Bompaire, Philip Deegan, Stéphane Gaïffas, and Søren V. Poulsen. tick: python library for statistical learning, with an emphasis on hawkes processes and timo-dependent models. Journal of Machine Learning Reseavch, 18(214):1 5, 2018. URL
.hmml
Lei Cai, Zhengzhang Chen, Chen Luo, Jiaping Gui, Jingchao Ni, Ding Li, and Haifeng Chen. Structural temporal graph neural networks for anomaly detection in dynamic graphs. In Proceedings of the 30th ACM international conference on Information & Knowledge Management, pp. 3747-3756, 2021.
Jialin Chen and Rex Ying. Tempme: Towards the explainability of temporal graph neural networks via motif discovery. In A. Oh, T. Neumann, A. Globerson, K. Sacnko, M. Hardt, and S. Levine (cds.), Advances in Newral Information Processing Systems, volume 36, pp. 29005 29028. Curran Associates, Inc., 2023.
Alan Hawkes. Point spectra of some mutually exciting point processes. Journal of the Royal Statistical Society. Series B, 33, 07 1971. doi: (0.111//25517-61111199....
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey. The Journal of Machine Learning Research, 21(1):2648 2720, 2020.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou (eds.), Machine Learning: ECML 2006, pp. 282 293, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-46056-5.
Vassilis Kostakos. Temporal graphs. Physica A: Statistical Mechanics and its Applications, 3806610000 2009.
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 and data mining. ACM, 2019.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Pa- rameterized explainer for graph neural network, 2020.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs, 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In T. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL http::t:/tocteeetttttttt neurips..rrpp.... www..ps..c/paperr... files/ /aper/ harfffiifffee22666eee11111113012
pdf
Wenwen Xia, Mincai Lai, Caihua Shan, Yao Zhang, Xinnan Dai, Xiang Li, and Dongsheng Li. Explaining temporal graph models through an explorer- framework. In The Eleventh International Confer- ence on Learning Representations, 2023. URL
Da. Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs, 2020.
Sijic Yan, Yuanjun Xiong, and Dahua Lin. Spatial temporal graph convolutional networks for skeleton-basod action recognition. Proceedings of the AAAI Conference on Artifiical Intelligence, 32(1), Apr. 2018. doi: 10.1609/anes v32i1. 12328. URL http:////ssaaaaa.....aaa aaai http:///wwwaa..o.occ////////////
13

---

Published in Transactions on Machine Learning Research (05/2024)
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEFF Transactions on Pallern Analysis and Machine Intelligence, 45(5):5782-5773) 2023. doi: 10.1100/TPAML22222200022
Ling Zhao, Yujiao Song, Chao Zhang, Yu Liu, Pu Wang, Tao Lin, Min Deng, and Haifeng Li. T-gen: A tem- poral graph convolutional network for traffic prediction. IEEE Transactions Intelligent Transportation Systems, 21 (9):3888 3858, 2020. doi: 10. 22109//T775220192255552222
14

---

Published in Transactions on Machine Learning Research (05/2024)
A
Appendix
A.1
Computational requirements
To run our experiments, the following hardware. Reported results will be indicated with one of the associated symbols when shown in tables.
MBP Intel Core 19-9900H CPU @ 2.30GHz and 16GB RAM, AMD Radeon Pro 560X GPU
Snelliust Intel Xeon Platinum 8360Y (2x) 36 Cores/Socket 2.4 GHz, 32GB RAM, NVIDIA A100
Training the target models Training the target models requires significant resources and time. For this reason, we decided to only train them once. Additionally, we release the learned parameters of these models so that they can be used for further experiments.
A.2 Hyper- pappeepprameters
Finally, list the hyper-parameters used in our experiments with the T-GNNExplainer model. Hyper- parameters related to training the target models are listed in Appendix B
The navigator is a two-layer perceptron network with ReLU activations and 128 hidden units. Timestamps are encoded using two-layer attention architecture and harmonic encoder, as described in both Rossi et al. (2020) and Xu et al. (2020). The datasets are randomly split into training, validation ion and test which consist of 70%, 15% and 15% sets the data respectively. The learned model weights are shared across the authors' and our navigator implementations, as well as with the PGExplainer baseline.
Navigator
Explainer We evaluate the T-GNNExplainer on three different navigators (see Section 3.4.1 We set the number of rollouts of the MCTS algorithm to 500, and the parameter of the UCT algorithm, controlling exploration-exploitatioo trade-off, to 5. These hyper-parameters authors. Additionally, to reduce the cost of our experiments, we randomly selected only 100 target events for explanations, instead of 500 used by the authors. This is minor divergence since results are aggregated over all explained events. Finally, we noticed evidence in the provided code base and in the paper, that the authors evaluated all explainer models (both PGNavigator and the baselines) with the 20 most recent candidate events. This is a divergence from the paper, where 25 claimed for this parameter. We experiment with both values and additionally explore the effects of considering only and 10 candidate events. We provide analysis the effect of this parameter in Section 5.2 and in Appendix A.6
the same as the ones used by the
Random seed Lastly, it is important to note that although the pre-training of the navigator and the tar- get models involves randomly initialized parameters, at inference time, both the T-GNNExplainer and the baselines are deterministie. Moreover, both the training of the target models and executing complete ex- periment took significant time and resources. For these reasons, we did not conduct any further experiments with differently initialized random number generators.
A.3 Changelog
In this section, we highlight the most important changes have performed on the code base. It includes fixes to some of the discrepancies between the paper and the provided code base, as well as some minor optimizations and non-functional changes to the code base.
Number of candidate events As we noted in Section 3.3 according to the paper, both the baseline explainers and the T-GNNExxlainer model consider the 25 most recent events in the k-hop neighbourhood of the target event. However, in the provided code base, this parameter hard-coded to The value of this parameter significant, as controls the effective size of the search-space that the explainers condider. In work, however, we could not initially determine whether the reported experimentation results were
15

---

Published in Transactions on Machine Learning Research (05/2024)
produced using the value of 20 or 25. For this reason, we experimented with both. Additional information is provided in Section 5.2
À parameter In the article, the authors claim that they used À = 5 for the UCT algorithm. However, in the provided code base, it is set to 100. For the interested reader, this parameter is called c_punct in the provided code base We set this paramcter to 5 for all our experiments.
Further changes On top of the above mentioned inconsistencies, we also performed small optimizations and some improvements to the code basc. These include:
In the original code base there was no clear distinction between the PGExplainerTG class and the MLP used as navigator in the authors' explainer model. In fact, the MLP used as a naviga- tor was instantiated by a static method within the PGExplainer class and the pre-trained model weights would be loaded during this process. We slightly modified the code base by introducing a new module navigators which now contains three classes: PGNavigator, MLPNavigator and DoiProduuttNavigatorr One can switch between using these different. navigators by setting the navigator_ type parameter in the relevant configuration file
We optimized the MCTS algorithm by removing superftuous linear searches in the node selection algorithm. This optimization lead a meaningful performance improvement of the TGNN-Explainer of around 30%.
We introduced a new hyper-parameter, controlling the number of most recent events that the ex- plainers consider. This parameter was hard-coded to 20 in the provided code base.
The implementation of the PGExplainer the provided code base was inefficient, that each time was called, it would reload the trained model weights from a checkpoint. In the absence of such checkpoint, it would first train the model, and then return from the function. In case of 25 candidate events, this would mean that the PGExplainer would be trained once for the first event and its model weights would be reloaded 24 times. We fixed this by moving this logic to the constructor on the PGExplainer model, where all the necessary information is available.
Finally, we also noted that in the absence of a pre-trained PGExplainer model, the navigator would not be properly instantiated and the T-GNNExplainer model would fail to run. One possible reason for this bug is that both the architecture and the training procedure of the navigator coincide with the PGExplainer model, and instead of re-implementing the navigator, the authors simply exposed the fully connected layers of the PGExplainer when instantiating the T-GNNExplainer.
A.4 Runtime Comparison
We list the required wall-time for the explanation of single event within the framework of the proposed by the authors' baselines, well as the search-based explorer- framework methods (Table D
Notably, the search-based algorithms take considerably longer to be completed due to the tree traversal required, which 1) cannot be reliably parallelized; and 2) requires the computing of the model probabilities along almost all steps of the traversal.
The variant of PGNavigator explainer algorithm that does not use navigator is only faster in the case of the Synthetic V1 dataset.
A.5 Performance of the Proposed Navigators
We furthermore provide additional figures Figure t that aim showcase the performance of the addi- tional navigators we have implemented, as they have been shown to perform close or even surpass the
" www.eppaainer.xxrapph.ooo method. navigators fiettmamnn///eeeeeoooo/////////n yymm
16

---

Published in Transactions on Machine Learning Research (05/2024)
Synthetic V1
Synthetic V2
Wikipedia
Reddit
ATTN
0.009=0.0
0.009=0.0
0.016#0.0
0.034+0.0
PBONE
0.132=00.0
0.13210.0
0.265
0.282:1..0
PG
0.001+0.0
0.001+0.0
0.001+0.0
0.001+0.M
PGNavigator
19.956=1004
14.5
43.17812.9
52.496-66.5
PGNavigator (NO NAV)
33.784=5.9
34.971+14.3
47.286+12.0
80.111+17.8
MLPNavigator
33.577=7.0
43.377+12.3
63. 63.063+11199
56.84847.3
DotProductNNvvigttr
36.433-7.99
40.787118.4
19.003#11.6
52.723
(a) Runtime comparison for single event explanation with TGAT base model (in seconds).
Synthetic V1
Synthetic V2
Wikipedia
Reddit
ATTN
0.006110.0
0.006:10.0
0.014
0.029:10.0
PBONE
0.079=0.0
0.079=0.0
0.222=0.0
0.251=0.0
PG
0.001+0.0
0.001+0.0
0.001+0.0
0.001+0.0
PGNavigator
29.252
13.301+144
45.987+11.5
56.31247.5
PGNavigator (NO NAV)
37.274=3.8
13.239+1.8
51.807#11.8
56.55227.9
MLPNNavigtor
23.547-8.9
14.031=1.6
42.57316.8
74.467118.2
Dot Doouuuucctavviottor
25.381+4.6
12.470+1.5
69.283+-286
56.260+8.1
(b) Runtime comparison for single event explanation with TGN base model (in seconds).
Table 2: We record the execution times of an event-level explanation over 100 different explained events and all proposed evaluation settings. The results are aggregated and an estimate for the required time of full event explanation is provided. The baseline methods are not search-based, thus the time required is much shorter. Conversely, as the T-GNNExplainer variants are inherently search- search-based, they perform considerably slower.
implementation of the original aut horso as presented in Tables 1a and 1b with a threshold of 20 candidate events.
The reported results are, as before,
The differences between navigators are often not significant. The MLPNavigator performs more or less similarly with the original PGNavigator proposed by the authors.
The DodevoouetNavigator
extension to the project also performs similarly and occa- sionally surpasses the other navigators, but seems to struggle at lower sparsity constraints. Thus, if for performance reasons, a lower rollout number selected (e.g. 200 instead of 500) for faster performance, relatively lesser final fidelity might be expected, but could potentially perform faster.
propose
However, the relatively high performance of the DotProductNavigator still merits further research. In future work within temporal graph explanation, we disregard the MCTS algorithm, which, by definition attempts to find a sparse subset of events that maximizes fidelity through the use of navigators, and only consider an explainer based on the dot product of larget event and candidate events.
A.6 Results with Threshold 25
We show figures of our experiment using the 25 most recent events as candidates, as the authors claimed in the article in Figure 7 We note, however that the higher number of candidate events considered at each step of the tree expansion leads to an explosion of the number of total candidates considered, which is the primary drawback to this method.
Otherwise, already noted in Section 5.2.2 and Figure 5 the performance improvement is only marginal.
17

---

Published in Transactions on Machine Learning Research (05/2024)
0-
0-
-2-
MLPNovigator
DoProductharggtt
-6-
DoiProduthaaiggttr
NLPNovigator
MLPNovigatr
DeProduchaargtter
-025-
PiNtavrgatoor
PGNavigator
PGNtavggttor
-0.50
PGNevtgatoo
0.0
02
0.4
0.6
0.8
1.0
0.
08
0.
0.4
0.8
1.0
(a) Wikipediaa
(b) Reddit
(c) Syuthetic V1
(d) Synthetic V2
-1-
M.Phieggtrr DoPProdudhaavgato
MLPNanggator DoProducthooggtz
-6
M. MLPhieipator
PONay
PGNavigator
PGNovigator
0.0
02
0.4
0.6
0.8
10
088
0.0
02
0.4
0.6
(e) Wikipedia
(f) Reddit
(g) Synthetic V1
(h) Synthetic V2
Figure 6: ft Results for the different navigators with TGAT (a-d) and TGN (c-h) with threshold 20.
0.75
Fidelity
Foaiitty
MLPNoxigator
Fidalty
MLPNarigato ATTN
Fidelit
0.6
MLPNaiggator
ATTN
ATTN
ATTN
PBONE
PBONE
FEONE
0.00
PBONE
PG
2
PG
PGNeedgetor
PGDlwwggator
PGNaeiigatre
PGNestgrter
02
1.0
0.4
0'8
0.9
0.4
1.0
Sparsity
Sparsity
Sparsity
Sparsity
(a) Wikipedia
(b) Reddit
(c) Synthetic V1
(d) Synthetic V2
Fidelty
MLPMiuvigator
gator
Fidelty
MLPNaiiggttor
ATTN
ATTN
ATTN
ATTN
PBONE
PRONE
FEONE
PBONE
PG
3
PGNastgator
-8-
Ptilavggator
PiGNovigator
PGNestgator
02
1.0
0.4
0'8
0.8
02
1.0
Sparsity
Sparsity
Sparsity
Sparsity
(e) Wikipedia
(f) Reddit
(g) Synthetic V1
(h) Synthetic
Figure f Pideeity-sparsity curves for TGAT (a-d) and TGN (e-h) at threshold 25.
18

---

Published in Transactions on Machine Learning Research (05/2024)
B
Model Training
The TGAT and TGN models underwent training using distinct sets of hyperparameters, anticipated. Ad- ditionally, the hyperparameters varied across different datasets. The specific details of these hyperparameters are outlined below.
TGAT sampled edge neighbours; hidden layers; attention heads; learning rate 0.0001; dropout probability 10%; hidden node embedding dimension 100; hidden time embedding dimension 100.
TGN 10 sampled edge neighbours; 2 hidden layers; 2 attention heads; learning rate 0.0001; dropout probability 10%; hidden memory dimension for synthetic datasets, 172 otherwise; hidden node embedding dimension 100; hidden time embedding dimension 100; and message dimension 100.
The models for the real datasets were trained with batch size 512 for 10 epochs, while the synthetic datasets trained with batch size 256 for 100 epochs. The Adam optimizer was used for both models.
TGAT
TGN
ACC
AP
ACC
AP
Synthetic V1
0.9143
0.9470 (0.9632)
0.9352
0.9540
(0.9687)
Synthetic V2
0.8831
0.9082 (0.9641)
0.9436
0.9603 (0.9535)
Wikipedia
0.9042
0.9724 (0.9791)
0.8624
0.9544 (0.9851)
Reddit
0.9290
0.9814 (0.9750)
0.9252
0.9623 (0.9664)
Table 3: Initial training results of the models, accuracy (ACC) and average precision (AP). Reported mumbers by original authors in brackets.
19

---

Published in Transactions on Machine Learning Research (05/2024)
C Original Results and Differences
Furthermore, in Table
4a and
4a
WC list the full results of the original authors. For clearer comparison
between their results and ours, in results and our reproduction.
Table 46 and 5b are listed the relative differences weew their reported
Table 4: Results comparison with the original study, for the TGAT model.
(a) Results for TGAT model from the original paper.
Wikipedia
Reddit
Synthetic
Synthetic
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
ATTN
0.891
0.564
0.658
-0.654
0.555
0.390
0.605
0.291
PBONE
0.027
-2.227
0.167
-2.492
0.044
-2.882
0.096
-4.771
PG
1.354
0.692
0.804
-0.369
0.476
-0.081
1.329
-0.926
PGNavigator
1.836
1.477
1.518
1.076
0.780
0.666
1.630
1.331
(b) Relative difference in results for TGAT model with respect to the original paper (in %).
Wikipedia Best FID
Reddit
Synthetic V1
Synthetic V2
AUFSC
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
ATTN PBONE
-40.546
-85.443
-93.785
-82.411
57.212
52.502
-21.486
-412.173
3381.139
-124.126
294.332
-113.917
2760.941
-129.916
1176.928
-118.316
PG
-54.233
-146.531
-10.673
-156.970
50.210
407.540
-63.990
-11.286
PGNavigator
-37.082
-42.960
-48.038
-33.124
94.020
71.568
-29.114
-66.640
Table 5: Results comparison with the original study, for the TGN model.
(a) Results for TGN model from the original paper.
Wikipedia
Reddit
Synthetic V1
Synthetic V2
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
ATTN
0.479
0.073
0.375
0.289
2.178
1.624
0.988
-0.634
PBONE
0.296
-0.601
0.340
-0.256
0.001
-3.311
0.320
-5.413
PG
0.464
-0.231
0.679
0.020
2.006
0.626
1.012
-1.338
PGNavigator
0.866
0.590
1.362
1.113
2.708
2.281
4.356
3.224
(b) Relative difference results for TGN model with respect to the original paper (in %).
Wikipedia
Reddit
Synthetic V1
Synthetic V2
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
Best FID
AUFSC
ATTN
197.033
980.014
186.780
-437.141
-72.596
-74.254
-81.690
129.742
PBONE
466.775
-224.938
778.892
-153.866
73351.165
-113.057
-17.116
-88.612
PG
184.266
-95.200
45.838
-11664.245
-72.589
-166.895
-85.158
62.869
PGNavigator
110.238
148.700
107.432
58.986
-66.004
-70.174
-93.906
-132.758
20


Reviews:
[{"review_id": "aHQ3nihcyF", "reviewer": "Reviewer_2PhJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "S1. Reproduction studies are generally good to have (but see W1)\n\nS2. Highlights a few inconsistencies between T-GNNExplainer paper and the actual implementation\n\nS3. Explores impact of some design choices not explored in original paper\n\nW1. Not really a reproducibility study as it uses the original implementation, the original metrics, the original datasets, original hyperparameters (largely), and even the original anecdotal examples.\n\nW2. Differences in results not clearly explored. The paper points out that their results are somewhat different to the ones in the original paper at times, but does not investigate why this is the case. It's also not clear how much variance there is in these performance numbers, as the authors only do one run on a subset of the test data; e.g., it's net clear whether or not all of the differences are due to variances.\n\nW3. Does not go beyond original work and hence does not provide any tangible and interesting insight. In particular, the paper does not explore the potential and limitations of T-GNNExplainer. It also does not relate it to other work (e.g., Lie et al., \"A differential geometric view and explainability of gnn on evolving graphs\", also ICLR23).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This is an experimental paper that reruns the experimental study of T-GNNExplainer (Xia et al, ICLR23) plus a few additional experiments. I'd hesitate to position this paper as a reproducibility study since it uses the original implementation, the original metrics, the original datasets, original hyperparameters (largely), and even the original anecdotal examples. It does add an ablation of replacing the navigator (one component of the T-GNNExplainer model) by simpler ones as well as on the impact of two hyperparameters.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "-", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "hlkbfvPILy", "reviewer": "Reviewer_pXPi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "First, let me consider the need for a reproducibility study. The authors claim at the very beginning that \"*Understanding the provided code base proved to be difficult*\". I have tried running the original code and I can validate this claim, it has practically no documentation or comments, and installing it runs into many errors due to missing requirements (e.g., dig, tick, ...). By comparison, the codebase provided by the reproducibility study is well documented, clear, with several notebooks and explanations. I think that the need for a reproducibility study can be highlighted more, see **requested changes R1-R2** below.\n\nThe paper is clear in the first part, a bit less on the methodological part without reading in detail the original paper. I am not sure what are the guidelines here. In particular:\n\n1. The structure of the encoder-decoder T-GNN is unclear. I am assuming it is using some graph attention mechanism since attention is mentioned in the baselines (\"*The computed mean attention scores of the target model*\"), but this is unclear.\n\n2. I don't understand how the navigator is trained from this paper. Similarly, I do not understand the differences between the first two navigators they investigate, and how these are related to the \"PGExplainer\" baseline (which does not look similar to the original PGExplainer paper, to be honest). See **requested change R3** below.\n\nThe experimental results are interesting, and I think that the added hyper-parameter evaluations add value to the original paper. There seems to be some super-position between the experiments on the rollout parameter and some results presented by the authors in the rebuttal phase (https://openreview.net/forum?id=BR_ZhvcYbGJ, in particular \"Response to Reviewer 1, Q2\"). Can the authors clarify this point?\n\nConcerning the comparison with the original paper, the abstract hints that almost all results were correctly reproduced, while instead the experiments hints at several discrepancies (\"*Overall, we conclude that the results of the paper are not completely reproducible*\"). See **requested change R4** below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper is a reproducibility study of the **T-GNNExplainer** model proposed in (Xia et al., 2023) at ICLR 2023. T-GNNExplainer adds a trainable \"navigator\" module on top of a temporal GNN (T-GNN) that predicts the relevance of each possible pair of edges (\"events\"). Then,it uses this navigator to guide a search process for the most influential set of events that constitute the \"explanation\" for the prediction.\n\nThe authors have re-implemented the codebase from the original paper, highlighting a major inconsistency from the paper (in the navigator part), and comparing three navigators: the one from the original codebase, the one described in the original paper, and another (simpler) variation they propose (a dot-product based navigator). They also evaluate some hyper-parameters that were set as defaults in the original paper, including the number of rollouts in the search algorithm.\n\nI am not very familiar with reproducibility studies, especially in TMLR (is this a special section of the journal?). I'll do my best to evaluate the paper on its own merits, but my evaluation is that the paper is a potential good reproducibility study if the weaknesses below are addressed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "R1. I suggest highlighting better the need for a reproducibility study. The authors initially mention that \"*The provided repository contained the code for the target models, the T-GNNExplainer model and the baselines, as well as shell scripts and configuration files to run the experiments, train the target models and pre-process the datasets.*\", making me wonder why a reproduction was needed. Issues with the code are only mentioned on page 11, with no details on what specific issues were found. I think a short summary of some inconsistencies or code difficulties (e.g., missing requirements) can be added to the introduction.\n\nR2. Concerning the sentence: \"*The learned model weights are shared across the authors’ and our navigator implementations, as well as with the PGExplainer baseline.*\" Can you clarify what you mean by \"*shared across the authors’ implementations*\"? Are they taken from the original codebase? Is this pipeline consistent with the original paper?\n\nR3. I suggest adding some equations to clarify the methodology, including (a) the structure of the T-GNN, (b) the specific equations for the navigators, and (c) the optimization task that was used to train the navigator (unless this is common in reproducibility studies, in which case you can ignore this comment).\n\nR4. I also suggest adding a table listing the main reproductions and/or inconsistencies of the paper compared to the original one.\n\nR5. The paper needs a proofediting, especially in the mathematical part. I list three small concerns below as examples.\n\n* p2: $S$ should be $\\mathcal{S}$.\n* p3: \"*the authors define fidelity*\", fidelity is a standard metric in explainability literature, I suggest rewording this sentence.\n* p4: \"$\\mathcal{C}(\\mathcal{N}^i, e_j)$ should be $\\mathcal{C}(\\mathcal{N}^i)$.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "XDazCeQmEX", "reviewer": "Reviewer_tqWE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strong Aspects:\n1. Reproducibility: The submission does an excellent job of reproducing the original paper's results by Xia et al. (2023), which is critical for validating the claims made by the original authors. This strengthens the credibility of the T-GNNExplainer framework.\n2. Novel Extensions: The introduction and evaluation of different navigator methods, especially the new DotProductNavigator, provide meaningful additions to the existing literature and could potentially lead to more effective explanation tools for temporal GNNs.\n3. Detailed Analysis: The authors' in-depth examination of hyperparameters and their impact on the model's performance offers valuable insights into how the T-GNNExplainer operates and can be optimized for better efficiency and accuracy.\n\nWeaker Elements:\n1. Clarity on Navigator Discrepancies: The authors note discrepancies between the navigator method described in the original paper and the provided implementation. It would be beneficial if the authors could offer a more precise explanation of these differences and their implications.\n2. Implementation Details: To ensure that others can maintain the reproducibility of the study, the authors should provide comprehensive details about their implementation, including explicit descriptions of the new navigator methods.\n3. Baseline Comparison: Although the submission states that T-GNNExplainer outperforms other baselines, the authors should ensure that they have included a diverse range of competitive baselines to benchmark against to rule out any potential biases towards their method.\n4. Limitations and Failure Cases: The authors should discuss any limitations of their method, including scenarios where T-GNNExplainer may not perform well.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This framework uses an explorer-navigator method to compute sparse explanations for the predictions made by these complex models. The contributions and new knowledge presented include the following:\n1. Reproduction of Main Findings: The authors of the submission have replicated the main findings of the original paper by Xia et al. (2023), confirming the effectiveness of the T-GNNExplainer in providing sparse and interpretable explanations for Temporal GNNs.\n2. Extension with Different Navigator Methods: The authors have extended the original work by proposing and evaluating a new type of navigator method, called the DotProductNavigator, intended to enhance the explanation capabilities of the framework.\n3. In-depth Examination of Explanation Capabilities and Efficiency: They have performed a detailed analysis of how various model settings and hyperparameters affect the explanation capabilities and computational efficiency of the T-GNNExplainer.\n4. Quantitative Analysis of Hyperparameters: The submission includes an analysis of two hyperparameters—namely, the number of rollouts in the Monte Carlo Tree Search (MCTS) and the number of candidate events—on the runtime and fidelity of the explanations.\n5. Performance Evaluation: The authors have confirmed that the T-GNNExplainer outperforms other baseline methods across nearly all datasets and evaluation metrics. They also highlight that the navigator helps to bias the search process and that the method can find an exact influential event set.\n6. Feasibility Study and Future Work Motivation: The paper concludes with a feasibility study that motivates future research directions in explaining Temporal GNNs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Clarification of Discrepancies: The authors must clarify the discrepancy between the navigator method described in the original paper and the one implemented in their study. This is critical to ensure the reproduction study's integrity and the comparison's validity.\n2. Detailed Implementation Information: The authors should provide detailed descriptions of their implementation, including the algorithms for the new navigator methods, to enable others to replicate their work accurately.\n3. Limitations and Failure Cases: The authors should discuss the limitations of their approach and any potential failure cases. This is crucial for readers to understand the boundaries within which the T-GNNExplainer performs effectively.\n4. Enhanced Baseline Comparison: Including a wider array of competitive baselines for comparison would enhance the robustness of the performance evaluation.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: TMLR encourages submission of reproducibility reports and this paper has done a great job on this, and not only reproduced the original paper, but also provided additional insights.

I'm not recommending a certification as the approach being studied here is not the best performing one and the scope of the additional insight is a bit small.
Decision: Accept (poster)