Training-free Counterfactual Explanation for Temporal Graph Model Inference
Authors: Mingjian Lu
Haolai Che
Yangxin Fan
Qu Liu
Fei Shao
Tingjian Ge
Xusheng Xiao
Yinghui Wu
Venue: ICLR 2026 Poster (2026)
Keywords: Temporal Graph Nerual Networks
Explainability
Training Free
Primary area: interpretability and explainable AI

Abstract: Temporal graph neural networks (TGNN) extend graph neural networks to dynamic networks and have demonstrated strong predictive power. However, interpreting TGNN remains far less explored than their static-graph counterparts. This paper introduces TEMporal Graph eXplainer (TemGX), a training-free,post-hoc framework that help users interpret and understand TGNN behavior by discovering temporal subgraphs and their evolution that are responsible for TGNN output of interests.We introduce a class of explainability measures that extends influence maximization in terms of structural influence and time decay to model temporal influence. We formulate the explanation task as a constrained optimization problem, and propose fast algorithms to discover explanations with guarantees on their temporal explainability. Our experimental study verifies the effectiveness and efficiency of TemGX for TGNN explanation, compared with state-of-the-art explainers. We also showcase how TemGX supports inference queries for dynamic network analysis.

Published as a conference paper at ICLR 2026
TRAINING-FREE COUNTERFACTUAL EXPLANATION FOR TEMPORAL GRAPH MODEL INFERENCE
Mingjian Lu', Haolai Che', Yangxin Fan', Qu Liu", Fei Shao',
Tingjian Ge², Xusheng Xiao*, Yinghui Wu!
Cass Western Reserve University
Uniiversity of Massachusetts Lowell
Arizona State University
ABSTRACT
Temporal graph neural networks (TGNN) extends graph neural networks (GNNs) and have demonstrated promising performance for dynamic and spatiotemporal network analysis. However, interpreting TGNN over dynamic graphs remains far less explored. This paper introduces TEMporal Graph eXplainer (TemGX), a training- free, agnossig and query-able framework to help users interpret and understand TGNN- based graph analysis. TemGX discovers temporal sub- graphs and their evolution that are responsible for inference results of interest, terms of temporal counterfactual analysis. We introduce class of explainability measures that integrate spatial-temporal influence and time decay model, to cap- ture temporal influence contextualized by sliding windows. We formulate the ex- planation task as a constrained optimization problem, and present fast algorithms to discover explanations with guarantees on their temporal explainability. Our ex- perimental study verifies the effectiveness and efficiency of TemGX for TGNN explanation, compared with state-of-the-art explainers. We also showcase how TemGX supports temporal queries for interpretable dynamic network analysis.
INTRODUCTION
Temporal graphs provide powerful abstraction represent complex dynamic systems, where nodes specify evolving entities, and edges denote temporal relationship. Temporal Graph Neural Networks (TGNNs) (Kazemi al. (2220) model temporal graphs by incorporating temporal features, relations, and their dependencies, making them capable of predicting evolving interactions. TGNNs have demonstrated their effectiveness in various tasks, such as link prediction and node classification, in various applications e.g., traffic analysis, transaction networks. In nutshell, a TGNN M takes as input temporal graph (a sequence of graph snapshots) G, {G',, .... Gt-1), where each snapshot G is represented by pair (X,, A;) of node feature matrix X; and an adjacency matrix A, at time (i [1, 4]). trained predict the representation (X,, Ar) of next graph G³, which can then be transformed task-specifi output, such class labels for node classification, features for regression analysis, or new links (events) for link prediction.
Despite their powerful predictive capabilities, TGNNs often considered lack of interpretability. The decision-making process of TGNNs is deeply embedded within multiple layers of nonlinear transformations and complex temporal mechanisms, which result in opaque predictions (Xia et al. 2022). Such "black-box" behavior raises significant concerns in applications requiring transparent, trustworthy, and accountable temporal graph analysis, such financial transactions or health-related predictions. Consider the following example.
In Bitcoin blockchain transactions, money launderers employ variety of techniques to conceal illicit cryptocurrency activities and evade detection by law enforcement agencies and Al-based monitoring systems (Bellei et al.) 2024, Cheng et al. (003).. shown in Figure I an input temporal graph G includes account IP addresses and Bitcoin transactions among the accounts at different timestamps.
Example 1:

---

Published as a conference paper at ICLR 2026
A temporal edge (U1, 02, '2)) in G represents transaction committed from IP address i1 to address 1/2 at timestamp 2. Each IP address (a temporal node) is associated with set of transaction features, egg., the number of blockchain transac- tions, the number of transacted bitcoins, and the amount of fees in bitcoins. There are two illicit IP addresses: V1 and Vg. They utilize money laundering patterns known as Peel Chain (Bellei et al. 2024) (P1) and Spindle (Cheng et al. (023) (P2) to ob- seure their illegal transactions. The perpetrators take Spindle strategy to generate multiple shadow addresses, and transfer il- licit assets along lengthy paths that converge at a specific des- tination. Fach path typically involves small amounts to avoid detection. Peel Chain launders cryptocurrency through a se- ries of small transactions that are 'pecled' from the original address and sent to exchanges for conversion into fiat currency or other assets to minimize risks.
L las
8
G1
G₂2
Figure 1: A temporal bitcoin trans- action network G that depicts money laundering activities (nodes: IP ad- dresses; edges: transactions).
A TGNN--aseed classifier detected both accounts as "illicit" at timestamps 4 and 9, respectively. Law enforcement needs evidence validate these results. A temporal subgraph G., explains "why" 0, is
"illicit" by containing historical transactions during period 1,4]-if not captured in history, TGNN
fails to detect 2t as "illicit" (counterfactual explanations (Kuratomi al. 2024 Lucic al. 2022
Multiple such structures exist over time, requiring a "global" model to fit their distribution. This summary can validate known patterns like "Peel Chain" and reveal how strategies "evolved" over time, e.g,, U1 has temporal dependency with e, via suspicious transactions, with dependencies evolv- ing into new patterns during period [5, 8). indicating switching from "Peel Chain" "Spindle". O
The above example calls for effective method that can (1) generate "instance-level"" explanations that expose activities as temporal subgraphs that are responsible for TGNN outputs in terms of counterfactual analysis; (2) summarize such structures over time as "global" statistical models, and (3) be conveniently queried to understand their evolving interactions. Several methods have been proposed for TGNN explanation e.g., (Xia al. (022). These methods aim to trace the model's behavior by finding important node features e.g., (Xia et al. 2022), which may not suffice to capture complex temporal dependencies between nodes and temporal edges; or sampling cohesive motifs following Information Bottleneck principle (Chen & Ying 2023), which may contain irrelevant, non-counterfactual structures for TGNN inferences. How make the explanations accessible and responsive to users' queries is also not addressed by prior work.
Our Contribution. We introduce an explanatory framework to discover temporal explanations for TGNN outputs. (1) We introduce temporal graph explanations (TemGX), an instance-level struc- ture for TGNN output (Section 33.. A TemGX integrates set of counterfactual, cohesive temporal subgraphs to provide "instance-Tever Tevel" interpretation for TGNN output. We extend counterfactual analysis (Kuratomi et al.] (024) to sliding window justify historical critical structures as those whose removal alter the output of TGNNs if not observed. (2) We propose a class of temporal explainability measures quantify the quality of TemGX. Our idea extends information cascad- ing models and resistant distance analysis, to capture the temporal influence in terms of temporal topology and node embedding similarity as an adaptive measure more suitable for evolving graphs. We show that while it is in PTTME to verify the counterfactual properties for temporal subgraphs, their generation remains Na-hard. nations for TGNN output (Section 4). The algorithm assembles instance-level temporal subgraphs by detecting a set of promising explanatory nodes.
(3) We develop efficient algorithms to discover temporal expla-
Using real-world datasets, we experimentally verify the efficiency and explainability of TemGX- based TGNN explanation (Section We show that TemGX efficiently generates that can be justi- fied by real events, and outperform state-of-the-art TGNN explainers in terms of common measures such as fidelity. Our case study further verifies the applications of TemGX for egg. interpretable event detection in financial transaction networks, and for event detection in cybersecurity.
2

---

Published as a conference paper at ICLR 2026
2 TEMPORAL GRAPHS AND TGNNS
Temporal Graph. A temporal graph 9 a pair (V, where V a finite set of nodes, and E is set of temporal edges. Each temporal edge is triple (u, u, representing directed interaction from a node u to a node v (u, v E V) at time (indexed with a timestamp t). Each node v E V carries label e.L, and feature set X where X E Rd is the feature vector of v at time t.
We shall use the following notations. (1) A temporal graph G = (V, E) can be represented by a discrete-time time dynamic graph {G1.... G.) (Kazemi et al. 2020h, which is sequence of snapshots. Each snapshot G; = (V, ,,) has a node set V. and an edge set E' C E that contains all the temporal edges timestamp in E (i E []. The size of & refers to the total number of nodes and temporal edges, i.e., |V+ + (2) Given a temporal graph G and a time window W with length I, an temporal graph induced by W is a temporal graph G. {G² ..... G² of t
consecutive snapshots (a length t - 1 subsequence of the snapshots) from G. where Go refers to the j-th snapshot in the samples with a counterpart G; at timestamp in G may not be the same as j). (3) Given G, temporal path Ps within duration 5 between node to another node is time-ordered sequence of temporal edges {(v,, to. ... (V,, 1141; t.), ... (Um: U, {m) where [1 S to S fm S ft). and Im- to S 5. We say u, 8-reaches e if such a path ps exists. (4) We say a temporal edge (v, v',(") can "induced" by a node set V. G, if both U, E Ve, and l' S I. A temporal graph G. V") is a temporal subgraph of G. EV, if it has the same set of nodes V, and E' E.
Temporal Graph Neural Networks. Following the prior study of TGNN interpretation (Kazemi it al. 2020; Xia et al.) 2022, Longa et al. (023), we consider a TGNN M as a composition of an encoder function fE and a decoder function fo. The encoder fE takes an input temporal graph G, = .... .a.......1.. G with t - 1 snapshots (typically induced by time window sliding over an original temporal graph 9), and obtains 7 where Z is the embedding of the node v E V at time The decoder InD takes as input z:-1 and output logits Z' at next timestamp.
2,
(e(9:)=Z'-1
1=(
Here the logits (') is the oulput embedding of node u at time I, and M(G,, u) (resp. M(Ge, e)) refers to an outpul of M at node v (resp. edge e). The logits Z' can be post-processed to task- specific "output" such as a probabilistie matrix or discrete values. For example. MMG., v) for node regression (resp. node classification) refers to a predicted values (resp. a class label), and M(G is binary label for link prediction ("true" if exists in G at time t).
3 EXPLANATORY TEMPORAL SUBGRAPHS
A desirable explanatory structure shall be (1) responsible for TGNN output, ideally as verifiable counterfactual analysis, i.e., the inference process of TGNN changes if such structures moved from the dynamic networks; (2) capturing the temporal influence via temporal cohesive structures,and (3) support fast retrieval of temporal dependencies over time. We next introduce class of temporal graph structures, which are justified by all the three requirements.
Given input temporal graph G-=(V, TE) of a TGNN M, and output M v) to be explained a target node v. temporal edge e = (u,, t) is a counterfactual edge of M(G v). if M(G. \ {e),,) # M(G,, v): here G. \ {e} is the temporal graph obtained by removing e from G.. A node v, E V is an explanatory node of M v). if there exists at least one of its adjacent temporal edge in G. as a counterfactual edge of MMG.. v).
Given M(G v). and a duration constraint 8, an explanatory temporal subgraph G. (Ve, E.) of M(G,, v) is temporal subgraph of G, induced by a time window of duration 6, where
o Ve = V, V.. where (a) V, is set of explanatory nodes of M v), and (b) V. is a set of temporal connection nodes, such that for each U, E V., Ug 8-reaches in G. via a set of connection nodes from Ve: here V, and V. are not necessarily disjoint, i.e., an explanatory node may also be a connection node;
E. refers to the temporal edges induced by V. in G.-
The counterfactual set of V, contains all the counterfactual edges of the nodes in V,,
Justification. We remark the following. (1) An explanatory temporal subgraph is temporally cohe- sive, a desirable property as for explaining GNNs in static graphs (Chen et al. 2021 Chen & Ying
3

---

Published as a conference paper at ICLR 2026
Temporal Graph Input
ICM Influence Calculation (1 - Pirary inf of, ('))
Induced Connecting Nodes
in
II
Ve
V,
inf
Ve {vg)
TGNN
51
0.30
M
0/
0.42
Ge1
CounterFactual Verification
(Prid...) o) Prol. Vel.c)
12
Pg
TGNN
M
Influence Back-propagation with TRD trd- = (2" (z,) Z (e))" (w))
reschable Node
M v. 0.81
MGG \ (V.),, v.) 0.43
tnd- 0.25
And = 0.18
U2
Counterfactual Explanatory Subgraph
Temporal Influence Score
inf(e,, t') g(trd(s,, (,) cxp(-A(t-3))))
À m 0.5 me w(fg) - 1.00, vn(()) - 0.61
V. = {u, U2}
Target node
inf(t.) 0.30, tnd(e:) 0.25
0.50
Exploratory node
: inf((2)) 0.42, ted((g) 0.18 =m 0.30
Ve {u3}
Counterfactual Connectting node
K2
:
ind(tz) = 0.18, trd((s) = 0.30 g 0.14
Figure 2: Overview of TemGX framework. Given target node oi and temporal graph GI, it constructs 6- reachable candidate pool and estimate influence as the probability changes when removing each candidate. TRD prop-apopaatiion captures temporal resistance, and a temporal influence score & combines influence, TRD, and temporal decay. Top-scoring nodes form the explanatory set V., induced connectors V. ensure temporal connectivity, and counterfactual verification confirms that removing V. U Ve changes the TGNN prediction M (Gr, 8t), which in turn contribute to temporal explanations.
This property is ensured by enforcing temporal reachability from any explanatory nodes to the target node. (2) It retains useful temporal structures that conform to counterfactual analysis to TGNN output. Unlike prior work, we distinguish "cxplanatory nodes" V, and "connecting nodes" Vo, based on a natural observation that not all nodes that (temporally) reach v are necessarily "in- fluencing" the decision of TGNNs. Indeed, those that may be responsible for TGNN output can be temporarily remote ("from the past") and structurally non-adjacent with v. (3) They readily support both temporal graph queries, to extract "instance-level"" explanations, and probabilistic inference via egg, dynamic Bayesian networks, to understand temporal dependencies over time (see Section 4 Temporal Explainability. We next quantify the explainability of an explanatory temporal subgraph Ge in terms of its temporal influence to a targeted output M v). considering both temporal propagation and the node embedding similarity, consistent with TGNN inference process.
2023
(1) We formulate temporal impact to TGNN output, by extending the Independent Cascade Model (ICM), which models influence propagation through independent edge activations with probability p(u, v', f) at time t. Given G. and a target output M(G., v), the temporal influence of temporal edge e at time t on node is defined as:
Pe = Pr(C,)) Pr(G, \ fe).ei]
where Pr(Ge, v) is the task-specific output probability from the embedding Zz(v) and Pr(g, (c).v) the probability if is removed at time + The influence of an explanatory node U, on recursively aggregates along all 8-reachable temporal paths:
in v1() =
II
(1 (1-Pet inf v',,)) (1)
8-85t'
We set (n,, f2 = 1 to ensure that an explanatory node has full influence to itself.
(2) An TGNN inference process propagates node embeddings via temporal paths output for deci- sion making. This effect can be approximated by class of temporal effective resistance distance, which has a justified static counterpart in GNNs behavior analysis (Zhu et al., (2024; Black et al.) 2023) and model optimization (Shen et al. 2024). Given a pair (Uz, v) of an explanatory node U and targeted node v, we define the temporal resistance distance at time t' as:
trd v., t') = (Z" (vx) z (v)) L (z" (v.)
Z (x)))
'The absolute value captures magnitude since edge removal increase decrease the probability.
4

---

Published as a conference paper at ICLR 2026
where Zd (ve) (resp. (v)) refers to the embedding of U, time t' (resp. the output embedding of u at time t). Let Ly be the Laplacian matrix of the snapshot Gy E G. (i.e., Ly Dy - Av:: where Dy and Ae refers to the degree matrix and the adjacency matrix of snapshot Gy with eigenvalues A1,... An and corresponding eigenvectors V1, Un, the Laplacian pseudo inverse T.6. at time is computed as Di=2 X; 4t uf. We adopt efficient algorithms such as (Liao et al. 2023 to approximate (rd v, f) in low polynomial time.
The temporal influence a set of explanatory nodes V, over [t - 12-5+3 + - 1] is aggregated as
@V.. v)
Σ Σ
inf(e., u, g(rdd((, v, v,{)) A(--()
VVEV, t'=t-6+1
monotone decreasing function of the temporal resistance distance and A > 0 controls exponential time decay. The multiplicative form lets temporal resistance modu- late rather than cancel influence, while e --t discounts older interactions
where g RR2--1 - [0,
recent ones weigh more (Mei & Eisner 2017). Because inf E [0, 1], g E [0, 1], and the decay term is in (0, for t' t, (VV,, E [0, IJ. A larger & indicates stronger, more recent influence under 6 d-reachability. The de- cay parameter À is adaativ, typically inversely proportional to the temporal granularity (Rossi
al. 2020a). Note that cohesiveness does not require consecutive temporal edges.
Based on the explainability measures, we formulate TGNN explanation problem. Given set of targeted nodes Vr, with target outputs M(G., v) (v E Vr), and duration bound 8, for each node E Vr, the problem temporal subgraphs induced by set of explanatory nodes V such that
Explanation Generation for TGNNs.
find an optimal set of explanatory
ΣΣ D(V,,e); VEVT EVEV
arg max
V.IS
where e ranges over VT, V Usev, V and V is the set of all the explanatory nodes for target output M(G,, v). addition, a size bound & constraints the total number of explanatory nodes, to allow users specify concise, iizenddudded instance-level explanations.
We investigate the hardness of the problem. We start with verification problem as "building block" task. Given an output M(G., v) to be explained, duration bound ö, and set of nodes V., is to verify if V. induces an explanatory temporal subgraph with temporal explainability above given threshold. Successful verification of V. indicates the existence of instance-level explanations and proper interpretable domain 1)-
Lemma 1: The verification problem is in PTIME.
We prove the above result by constructing a PTIME procedure (Verify). It computes influence scores of given temporal subgraph G, to be verified, and invokes TGNN inference process to verify if its counterfactual set is empty. Despite the tractability of verification, the overall explanation discovery problem is nontrivial.
Lemma 2: TGNN explanation generation problem is NP-hard.
The hardness of the low-level optimization can be verified by a reduction from the maximum cov- erage problem (MCP), a known NP-hard problem. We present the detailed proof Appendix 7 Despite the hardness, next introduce efficient algorithms generate temporal explanations with guaranteed temporal explainability.
4 DISCOVERING TEMPORAL GRAPH EXPLANATIONS
We start with a setting for a single output M(G., u). Our algorithm, denoted as TemGX, follows a "selection-and-vers process to grow of exploratory V. that simultaneous survive counter- factual checking posed on their temporally adjacent edges.
Algorithm Outline. TemGX applies a greedy selection procedure to iteratively expand the explana- tory set V. inside sliding window W. It begins with V. {w} and candidate pool C' formed by the L-hop temporal neighbors (v) within the induced temporal graph Gw. . At each iteration, the algorithm selects the node V in C' that maximizes the temporal influence score Φ(v,, v), updates the influence scores of remaining candidates, and invokes the Verify procedure to ensure that o preserves the counterfactual property of the TGNN output. The verified nodes are appended to V..
5

---

Published as a conference paper at ICLR 2026
Algorithm TemGX M,,GM,
1. set := 8; set C := 0: 0:
2. for each window W of size over 9 do
3. set V2, = {0); set C 0; induce temporal graph Gw with current window W; for each time step f in do induce L--hop temporal neighbor set (z( in Gw:
5. for each r' E (w) do update v' . 4(v', u)) C== {
1"t select and verify explanatory nodes */
while + 0 do select and verify explanatory nodes */
select node v arg max8,ec EC (e,,, v): updatePhi(C); false then C = C {o continue;
if
V.. (
9.
if IV, < k then V, V. {e); := = {v,); break;
10.
else set Rset V*: replacement policy
11.
while Rset * 0 do select node ot arg maxe EReat ((V. (ut) (vt]):
12.
if MMG,, Ve {ur } [v.],, false
13.
then Rset:=Rset (or continue;
14.
else Vg == V. (vr²) } {D {v.}: break;
1 construct temporal explanatory subgraph
15.
induces G. with V.. V. (connect nodes) and E.; == (G.):
16. return yç
Figure Algorithm TemGX
whereas failed candidates are removed from C. When [Va reaches the budget k replacement pol- icy is triggered: it searches temporary set Rset of nodes in V, and greedily swaps node vt in Rset with a candidate vç if the exchange yields a larger marginal influence gain @VV. {or } U {uz), and passes verification. This process continues until the candidate pool is empty, and returns the temporal explanatory subgraphs G, with connecting nodes Ve and temporal edges E.,
Analysis. Denote the optimal set of explanatory nodes as VO, we present the following result.
Lemma 3: Algorithm TemGX is a (1 = -approximaaionn i.e., D(V., v) 2 (1- (1- v).
We prove the above result by (1) reducing the problem to an equivalent online monotone submodular stream of temporal edges, and (2) proving that the greedy replacement policy ensures a (1- >aaproximmation for as a monotone submodular function (Qian al.] 2017). For time cost, it takes TemGX most f rounds of node selection, each in (v) (T)) time to compute the temporal influence score, where Ty is the polynomial-time inference cost of the TGNN M. We remark that TemGX is "one-pass" algorithm: the temporal nodes and their temporal neighbors are visited and processed only once as the sliding window moves forward. We present the detailed analysis in Appendix 7
maximization problem with cardinality constraint
Querying Temporal Explanations. TemGX provides a natural query access point with semantics
of temporal pattern matching (Ding et al. 2023 Chen & Ying 2023). (1) A temporal pattern Q, (Vo, Eq. o, 8') specifies a set of query nodes Vi and query edges Eq. Each query node 72 E V/9 may carry label eq. Here is temporal order posed Eq- Given set of temporal explanatory subgraphs 17 with a node set V,,, and a query Q, = (Vo, Eq, or 8'), there exists a match of Q in 17.
there is a mapping : Vo + Vy, such that for each edge e (u, u4+1) in Q, (i) h(u)) = U, u, u,
L; (ii) h(4+1)) 1)= = 11+1, u4+1-L = 1.41-Li and (iii) v, d'-reaches v/. Such queries can be efficiently processed by temporal pattern matching algorithms e.g., (Li Zou 2021 AAgasadeeghi et al.) 2024). (2) Better still, TemGX supports a statistical inference analysis via an efficient summary that learns dynamic Bayesian network. We defer the details in Appendix
5 EXPERIMENTAL STUDY
We evaluate the explainability and efficiency of TemGX. Our code and datasets are available
5.1
EXPERIMENTAL SETUP
Models and Datasets. We evaluate six real-world temporal graphs. (1) For spatio-temporal
gression, we use METR-LA and PEMS-BAY (Li al. 2018). For link prediction, we use Wiki (Ku-
https: http://ggtttt..occ cwwpniccomm//iieeeeeeeoeeee nejjiiicejjii 899 emex/

---

Published as a conference paper at ICLR 2026
Table 1: AUFSC, Fidelity, and Runtime (seconds) of generating one explanation on each dataset/backbone (mean + std).
Deaast
Medal
ALFSC
FM
Tome
AUPSC
Fil
Tuw
ALFSC
FA
Tuxe
AUPSC
Fd
Tase
UEIM
TGAT
0.43 +0.011
84435
40030
7.60017 67
0
40013
0 40.05
0191
40013
8167 40615
69 693-4.9
0 40 000
6 5.00 40
384-4.
Wispedda
YGAA
8,540
22006
0.63
Abides
m13
0038
50017
01335 andia
686
0.30
106.
12.0
Tempural Regression
TemCX
TGVes
Dutaset
Model
Fid
Time
ALTSC
METR-LA
STGON
DORNN
0.443 10.010
+0.099
0.436 20.012
0.471
+0.01
6.4
+0.12
0.258 20:011
0.276 +0:10
0.258 10.011
0.276
6.6
PEMS-RAY
STOCN
DORNN
0,480 20.08
0,468 20.009
0.473 20.008
0.44] 20.009
6,7 10.10
6.3 20.10
0.277 20:009
0.261 10.010
0.277 10.010
0.261 10,010
688 20.13
6.13
mar et al. 2019) and UCIM (Kunegis) 2013). For classification, we use Multihost (Gao et al. 2021 and Elliptic++ (Elmougy & Liu 2023) Dataset details are provided in Appendix 7 (2) We have
trained four types of TGNNs. (TGNN (Yu et al., 2018) employs graph convolution to capture spatial dependencies and temporal convolution model temporal patterns. (2) DCRNN (Li et al.,
2018) captures spatial dependencies through graph diffusion and temporal dynamics via recurrent units; enabling accurate spatio-temporal forecasting. (3) TGN (Rossi et al.] 2020b) uses memory
modules and attention mechanisms to capture the temporal evolution of node states, (4) TGAT (Xu al. 2020) combines self-attention learn spatial dependencies. We trained STGCN, DCRNN for MET R-LA, PEMS-BAY; and TGN and TGAT for Wiki and UCIM, uniformly with 70%, 15% and 15% for training. validating, and testing.
TGNN Explainers. We have implemented the following. (1) TemGX explainer; (2) TGVex, an extension of GVex (Chen et al. 2024) by applying it over "static" snapshots induced by sliding window to generate a sequence of explanatory subgraphs; (3) TGNNExplainer (Xia et al. 2022). an explorer-navigator framework to explain T TGNN-based link (event) inference: (4) TempME (Chen & Ying 2023), temporal motif-based explainer that finds events in terms of information bottleneck scores. (5) CoDy (Qu et al.)., counterfactual explainer that leverages Monte Carlo Tree Search to efficiently identify minimal event subsets whose removal flips the TGNN prediction. Among these, TempME and TGNNExplainer are learning- based explainers: CoDy uses both search and training and all are model-specific hence their time cost include ad-hoc training overhead. TGNNExplainer, Co and TempME are designed for event explanation and generate edges only. Hence, we com- pared TemGX with them using Wiki and UCIM for event analysis.
5.2 EXPERIMENTAL. RESULTTS
Exp-1: Explainability. We report the fidelity and sparsity of all explainers.
Fidelity: Overall. Table D reports the fidelity of all methods under the same evaluation protocol. For Wiki and UCIM, we set = 50 and Vr = 500 and we use both TGN and TGAT backbones for link prediction tasks. For METR-LA and PEMS-BAY, we adopt STGCN and DCRNN for spa- tio-temporal regression tasks. (1) TemGX achieves the best fidelity across all datasets and models. Its advantage stems from the use of temporal influence scores and the counterfactual property. which capture dynamic dependencies missed by snapshot- approaches. For example, on UCIM with TGN, TemGX attains a fidelity of 0.468, surpassing TempME (0.219) by 113%, 6.5x higher than TGNNEXplainer (0.072), and still 19% higher than the strong CoDy baseline (0.394). On the TGAT backbone. TemGX improves fidelity to 0.415, exceeding TempME (0.156) by 166%. 2.2x higher than TGNNExplainer (0. and outperforming CoDy (0.382) by 9%. On Wiki, TemGX obtains the highest fidelity on both backbones (c.g.. 0.262 on TGN and 0.335 on TGAT), surpassing CoDy (0.219 0.201) by about 20% and 67%. and remaining far ahead of TempME (0.128 / 0.155) and TGNNExplainer (0.098/ / 0.117). For regression tasks, TemGX also leads: it improves over TGVex by about 20% on METR-LA (DCRNN) and 18% on PEMS-BAY (DCRNN), with similar margins on the TGCN backbone. (2) TGVex performs poorly because its snapshot-pattern mining ignores ò-reachability and dynamic temporal dependencies that drive TGNN inference. (3) TGNNExplainer struggles in particular on dense graphs such as Wiki, where its edge-centric centric Monte Carlo search cannot efficiently identify nodes with strong accumulated temporal influence. (4) TempME benefits from motif discovery and achieves competitive scores on some link preddccciiioon settings, but mainly captures frequent motifs and often misses less frequent yet highly influential temporal patterns.
7

---

Published as a conference paper at ICLR 2026
UCIM TGN
UCIM TOAT
Wikipedia TGN
Wikipedia TGAT
0.4
0.6
Fidelity
0.4
0.3
0.4-
0.4
0.2
0.2
0.1
TemGX
0.0
0.2
1.0
0.8
1.0
0.0
0.2 0.4
0.6
100
TempME
Sparsity
Sparsity
Sparsity
Sparsity
TGNNExplainer
METR-LA SYGCN
METR-LA DCRNN
PEMS-BAY STGCN
PEMS-BAY DCRNN
CoDy
0.6
0.6
0.6
TGVex
Fideliy
0.4
0.4
0.2
0.2-
0.0
0.2 0.4
0.6
0.8
1.0
0.2 0.4 0.6 Sparsity
0.8
1.0
0.0
0.2 0.4
0.6 Sparsity
0.8
0.0
0.2 0.4 0.6 0.8 1.0 Sparsity
Sparsity
Figure 4: Hidelity-Sparsity Trade off.
AUFSC: Overall. Table reports the AUFSC scores under the same setting. TemGX again achieves the best results across all datasets and models. On UCIM (TGN) it reaches AUFSC of 0.475, more than 2.2x that of TempME (0.218), over 6.5x higher than TGNNExplainer (0.073), and still 31% higher than the strong counterfactual baseline CoDy (0.361). On the TGAT back- bone, TemGX achieved AUFSC to 0.423, exceeding TempME (0.153) by 176%, 2.2x higher than TGNNExplainer (0.191), and outperforming CoDy (0.349) by clear 21% % margin. On Wiki, TemGX maintains clear superiority, achieving AUFSC of 0.266 (TGN) and 0.340 (TGAT), surpassing CoDy (0.200/ / 0. 0844 by about 33% and 85%, and remaining far ahead of both TempME (0.128/ 0.155) and TGNNExplainer (0.098/ / 0.117). For spatio-temporal regression tasks, TemGX also consis- tently dominates TGVex, with the largest margin (about 65%) observed on PEMS-BAY (DCRNN). sieelity-sparsty trade-off curves. Using Wiki with |Vr 500 as in Fig. 4
we report the Fidelity- Sparsity trade-off curves of TemGX in Fig. 4 These curves illustrate how the fidelity of TemGX evolves as its explanation size varies, providing insight into the internal pparsity-fidelii behavior of our method.
Exp-2: Efficiency. We also report in Table I the time required to generate a single explanation. (1) TemGX is consistently fast: on link preedieein datasets it completes in 12.5 s, and regression datasets, within 6.7s. (2) On the dense Wiki graph, TemGX delivers x.2x-6.4X speedups over TGNNExplainer (65.2/68.6s) and TempME (72.8/75.4s). and up 10x over CoDy (125.0/108.20g while maintaining the highest AUFSC and fidelity. On UCIM, TemGX is 8.3x-8.4x faster than TGNNExplainer, 10.8x faster than TempME, and about 4.3x-4.9x faster than CoDy. (3) TGVex is competitive with Tem on the sparser METR-LA and PEMS-BAY networks, but at the cost of lower fidelity (see Fig. (4) Training cost matters: TGNNExplainer (navigator) and TempME (motif scorer) are learning based and require an extra training phase before explaining, whereas both TemGX and CoDy are training-fres search methods operating directly on a peppperaiinetee trained TGNN. Given similar training-free settings, TemGX attains substantially better AUFSC/Fidelity than CoDy while also being much faster, which further widens the efficiency gap in practice.
Exp-3: Case Analysis. We next demonstrate how TemGX enables queryable explanations for real- world TGNN tasks. (1) Clarifying Suspicious Transactions. Fig. 5 shows Bitcoin subgraph centered on node 140 (an "illicit" IP detected by a TGN). Fig. ii) presents three temporal ex- planatory subgraphs Ge, -Ge, produced by TemGX for node 140, aligned with known patterns (blue dashed circles for "Spindle", red for "Peel Chain"). IPs 418, 2819, 2411, and 140 form a Spindle match at the first timestamp; next, 418 is replaced by 782 with 2558 as new Spindle participants; later, a "Peel Chain" involving 2216 emerges. These subgraphs can be directly queried to retrieve suspicious matches of either pattern for follow-up investigation.
(2) Multi-stage Cyber Attack Analysis. Fig- (i) showcase a three-stage attack from Multihost: compromises via Shellshock (hostl executes patthrrppassor..shh. identifies and sends crack_passwd.d for password cracking on host2 (downloading malicious "libfoo.so"), and data exfiltration (using an MD5 hash to ex- tract "john.zip")) Two temporal explanatory subgraphs found by TemGX (Fig. (ii())) accurately
8

---

Published as a conference paper at ICLR 2026
Spindle
Spindle
Spindle
(a)
Peel Chain
Ge
Gez (ii)
G
(b)
Impilttuus
rmplreed an Landereers
G E
Password Crack
G
(i)
Figure 5: Case Analysis
cover the critical hostl- paths, including nodes and connections with pather_passworr and crack passwd.sh, illustrating TemGX ability explain complex multi- attacks.
RELATED WORK
Temporal Graph Neural Networks. TGNNs extends GNNs by integrating graph convolutions with temporal dependency of dynamic patterns. TGNNs can effectively capture both spatial dependencies and temporal sequences in a dynamic network, leading to more accurate predictions of future graph states (Longa et al. 2023). The temporal inference process operates on sequence of temporal features to produce prediction of the expected output at the subsequent times. Notable TGNNs include TGCNs Yu et al. 2018), DCRNNs (Li et al. 2018), among others (Xu et al. 2020).
Graph Neural Network Explanation. Among the relevant approaches post-hoc methods (Funke ct al. 2023 Luo et al.) 22200) Vu & Thai 20200] Ding et al. 2023] Chen et al., [2024] |Prenkaj et al.,
2024
which create separate models to generate explanations for GNN. Notably, PGExplainer
(Luo et al. 2020) extracts important features and substructures that influence GNN predictions.
Vu & Thai 2020) generates Bayesian network that best fits a of subgraphs that influences
GNN output. iDigg et al.) 2023) generate motifs as explanations. (Chen et al. (024) generates explanatory views that contain graph patterns as explanatory structures. For TGNNs, (He et al.) 2022) extends (Vu & Thail 2020) to learn an optimal Bayesian networks over sliding windows. TGNNExplainer (Xia et al. 2022 pretrains navigator (a feed-forward neural network) that infers importance scores among events, and an explorer that uses Monte Carlo Tree Search to infer events that minimize a cross entropy loss to target events. TempME (Chen & Ying) (203) samples motifs and learns to infer their importance in terms of the information bottleneck scores explainability measure. CoDy (Qu et al.) employs a Monte Carlo Tree Search-based strategy to search for minimal event subsets whose removal alters TGNN output. (Vu & Thai 2022) analyzed the limitations of perturbation- TGNN explainers and proposed temporal perturbation as direction for faithful temporal reasoning. Our work among the first unify counterfactual analysis, instance-level temporal explainability and continuous query into an efficient framework for TGNNs.
CONCLUSIONS
We have presented TemGX, a novel framework for TGNN output explanation. We introduced tem- poral graph explanation (TemGX), that integrates instance-level temporal explanation subgraphs to capture their temporal dependencies over time. We have developed fast algorithms to gener- ate TemGX. Our experimental study has verified that TemGX outperforms state-of-the-an TGNN explainers in explainability and efficiency. A future topic is to optimize TemGX to scale TGNN interpretation over large distributed networks and real-time graph stream analysis.

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
All authors of this submission adhere to the ICLR Code of Ethics. Our work does not involve hu- man subjects, sensitive personal data, or high-risk applications. Potential concerns such as privacy, security, or legal compliance have been carefully considered and are not applicable. To the best of our knowledge, no conflicts of interest, discrimination, or harmful insights arise from the methods or datasets used in this paper.
REPRODUCIBILITY STATEMENT
We have made every effort to ensure the reproducibility our results, All models, hyperparameters. and training procedures are described in the main text and Appendix. An anonymized repository containing source code and datasets is provided in the supplementary materials and via a github link https://gi cttttuu..oomm//// commnicee/ j1899/ TemGX/| allowing independent verification of all tests. Detailed proofs the theoretical claims are included in the Appendix, and all preprocessing scripts supplied to facilitate replication of the reported results.
REFERENCES
Amir Aghasadeghi. Jan Van den Bussche, and Julia Stoyanovich. Temporal graph patterns by timed automata. The VLDB Journal, 33(1):25-47, 2024.
Claudio Bellei, Muhua Xu, Ross Phillips, Tom Robinson, Mark Weber, Tim Kaler, Charles Leis- erson, Arvind, and Jie Chen. The shape of money laundering: Subgraph representation learning on the blockchain with the elliptic2 dataset. In KDD Workshop on Machine Learning in Finance, 2024.
Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. ICML, 2023.
Jialin Chen and Rex Ying. Tempme: Towards the explainability of temporal graph neural networks via motif discovery. Advances in Neural Information Processing Systems, 36:29005-29028, 2023.
Tingyang Chen, Dazhuo Qiu, Yinghui Wu, Arijit Khan, Xiangyu Ke, and Yunjun Gao. View-based explanations for graph neural networks. Proceedings of the ACM Management of Data, 2(1): 1-27, 2024.
Xiaoshuang Chen, Kai Wang, Xuemin Lin, Wenjie Zhang, Lu Qin, and Ying Zhang. Efficiently answering reachability and path queries temporal bipartite graphs. Proceedings of the VLDB Endowment, 2021.
Ling Cheng, Feida Zhu, Yong Wang, Ruicheng Liang, and Huiwen Liu. Evolve path tracer: Early detection of malicious addresses in cryptocurrency. In KDD, 2023.
Feng Ding, Naiwen Luo, Shuo Yu, Tingting Wang, and Feng Xia. Mega: Explaining graph neu- ral networks with network motifs. In 2023 International Joint Conference on Neural Networks (IJCNN) pp. 1-9, 2023.
Youssef Elmougy and Ling Liu. Demystifying fraudulent transactions and illicit nodes in the bitcoin network for financial forensics. In SIGKDD, pp. 3979-3990, 2023.
Thorben Funke, Megha Khosla, Mandeep Rathee, and Avishek Anand. Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks. IEEE Trans. Knowl. Data Eng., 35(8):8687- 8698, 2023.
José A Gámez, Juan I. Mateo, and José M Puerta. Learning bayesian networks by hill climbing: effi cient methods based on progressive restriction of the neighborhood. Data Mining and Knowledge Discovery, 1.
Peng Gao, Fei Shao, Xiaoyuan Liu, Xusheng Xiao, Zheng Qin, Fengyuan Xu. Prateek Mittal, San- jeev R Kulkarni, and Dawn Song. Enabling efficient cyber threat hunting with cyber threat intel- ligence. In ICDE, pp. 193-204, 2021.
10

---

Published as a conference paper at ICLR 2026
Wenchong He, Minh N Vu, Zhe Jiang, and My T Thai. An explainer for temporal graph neural networks. In GLOBECOM, pp. 6384 6389, 2022.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey. Journal of Machine Learning Research, 2700)):1-73, 2020.
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in tem- poral interaction networks. In KDD, KDD '19, 2019.
Jérôme Kunegis. Konect: the koblenz network collection. In Proceedings of the 22nd international conference on world wide web, pp. 1343-1350, 2013.
Alejandro Kuratomi, Zed Lee. Panayiotis Tsaparas, Guilherme Dinis Junior, Evaggelia Pitoura, Tony Lindgren, and Panagiotis Papapetrou. Counterfair: Group counterfactuals for bias detection, mitigation and subgroup identification. In ICDM, 2024.
Faming and Zhaonian Zou, Subgraph matching on temporal graphs. Information Sciences, 578: 539-558, 2021.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural net- work: Data-driven traffic forecasting. In ICLR, 2018
Meihao Liao, Rong-Hua Li, Qiangqiang Dai, Hongyang Chen, Hongchao Qin, and Guoren Wang- Efficient resistance distance computation: The power of landmark-based approaches. SIGMOD, 1(1):1-27, 2023.
Antonio Longa, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri. Pietro Lio, Franco Scarselli, and Andrea Passerini. Graph neural networks for temporal graphs: State the art, open challenges, and opportunities. arXiv preprint 2302.0030...111. 2023.
Ana Lucic, Maartje A Ter Hoeve, Gabriele Tolomei, Maarten De Rijke, and Fabrizio Silvestri. Cf-gnnexplainer: Counterfactual explanations for graph neural networks. In AISTATS, pp. 4499- 5511,2022.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information pro- cessing systems, 33:19620-19631, 2020.
Hongyuan Mei and Jason M Eisner. The neural hawkes process: A neurally self-modulating multi- variate point process, Advances neural information processing systems, 30, 2017.
Kevin Patrick Murphy. Dynamic bayesian networks: representation, inference and learning. Uni- versity of California, Berkeley, 2002.
Bardh Prenkaj, Mario Villaizán- Vallelado, Tobias Leemann, and Gjergji Kasneci. Unifying evolu- tion, explanation, and discernment: A generative approach for dynamic graph counterfactuals, In Proceedings of the 30th ACM SIGKDD Conference on Knwwledge Discovery and Data Mining, pp. 2420-2431, 2024.
Chao Qian, Ting-Cheng Shi, Yang Yu, and Ke Tang. On subset selection with general cost con- straints. In IJCAI, volume 17, pp. 2613-2619, 2017.
Zhan Qu, Daniel Gomm, and Michael Färber. Cody: Counterfactual explainers for dynamic graphs. In Fecty- International Conference on Machine Learning.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint arXiv:2006. 10637, 2020a.
11

---

Published as a conference paper at ICLR 2026
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs, 2020b. URL https:
/aaxii..org//b//20005 2006.10637777777
Xu Shen, Pietro Lio, Lintao Yang, Ru Yuan, Yuyang Zhang, and Chengbin Peng. Graph rewiring and preprocessing for graph neural networks based on effective resistance. TKDE, 2024.
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning rep- resentations over dynamic graphs. International conference on learning representations, 2019.
Vijay Vazirani. Approximation algorithms. Springer, 2013.
Minh N. Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks, 2020.
Minh Vu and My T Thai. On the limit of explaining black-box temporal graph neural networks. arXiv preprint arXiv:2212.00952, 2022.
Wenwen Xia, Mincai Lai, Caihua Shan, Yao Zhang, Xinnan Dai, Xiang Li, and Dongsheng Li. Explaining temporal graph models through an explorer-navigaoor framework. ICLR, 2022.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Self-attention with functional time representation learning. Advances in neural information processing systems, 32, 2019.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kanman Achan, Inductive represen- represen- tation learning on temporal graphs, 2020. URLhttts::/arra http://///raaaoooo////////////00
http://bb/2200..00
Bing Yu, Haoteng Yin, and Zhanxing Zhu. Spatio-temporal graph convolutional networks: deep learning framework for traffic forecasting. In IJCAI. International Joint Conferences Artificial Intelligence Organization, 2018
Mingzhe Zhu, Liwang Zhu, Huan Li, Wei Li, and Zhongzhi Zhang. Resistance distances in directed graphs: Definitions, properties, and applications. Theoretical Computer Science, 1009: 11470,, 2024.
12

---

Published as a conference paper at ICLR 2026
APPENDIX
A DETAILS OF THE ALGORITHMS
Algorithm TemGX (Fig 3) takes as input a temporal graph G', a TGNN model M, target output M (G", v) to be explained, and a budget parameter k. works with a sliding window of length ó over Go to generate a set of instance-level explanations For each window W, it generates a temporal explanatory subgraph with at most explanatory nodes through a selection and verify process.
(1) Initialization and Window Setup (lines 1-5). TemGX initializes the result set 1) = 0 and candidate pool C (line 1), then processes each sliding window W of size ō over the temporal graph Go (line 2). For each window, it sets the explanatory set V. {v) starting with the target node, resets the candidate pool C = 0, and induces a temporal subgraph Gw with the current window W (line 3). For each time step t; in W, it induces the L-hop temporal neighbor set Nz (v) in Gw (line 4). For each node E NL (v). it computes the temporal influence score v' == ((v', v) and adds to the candidate pool C == C' J {v, (line 5). This exploits spatiotemporal data locality constrain the search space to nodes that may participate in TGNN M inference under duration constraint 8.
(2) Greedy Selection and Replacement (lines 6-14). TemGX adopts a greedy selection and re- placement policy through "one-pass" processing of C. The main selection loop continues while the candidate pool is non-empty (line 6). At each iteration, it selects the candidate node vi that maximizes the temporal influence score & (V., u) over all v. E C and updates influence scores of re- maining candidates via updatePhi(C") (line 7). It invokes the Verify procedure with model M, target output M (G', v), current explanatory set V., and target node (line 8)-if verification fails, og is removed from C and the loop continues. When [V.| < k. the algorithm adds U, to V, and removes U, from C², then breaks (line 9). For [V.l = k. it switches to replacement strategy (line 10): it sets Rsst V, and selects node ut' that maximizes (VV,) \ {oz' } U {ugh) (line 11). If verification of the replacement with model M fails, vz removed from Rset (lines 12-13); otherwise, the re- placement executed: V, := V. {ot') U {ut} and Ug removed from C' (line 14). This process repeats until C' is completely processed.
(3) Explanation Construction (lines 15-16). Once the selection process completes, the algorithm constructs temporal explanatory subgraph G. by inducing it with explanatory nodes V., connecting nodes Vi. and edge set E, (line 15). The constructed explanation G, added to the result set 7 == U }. The algorithm processes the next window and terminates when all sliding windows are consumed, returning the complete set 17 of discovered temporal explanatory subgraphs (line 16).
B TEMPORAL EXPLANATORY SUBGRAPHS: SUMMARIES AND QUERYING
We elaborate how TemGX support cost-effictive and fast query access and statistical inference of temporal explanatory subgraphs. TemGX employs Dynamic Bayesian Networks (DBN) (Murphy) 2002) as summary structure to encode the dynamic trajectory of the explanatory nodes and their temporal edges. The summarization process serves as a necessary statistical modeling step that allows users to perform temporal reasoning and "What-if" analysis over the discovered explanations.
Summarization Structure. Temporal dependencies arise from the interactions among explanatory nodes and sequences of explanatory temporal subgraphs. Probabilistic graphical models such as dynamic Bayesian networks (DBN) (Murphy) 2002) provide a concise and expressive model to capture temporal dependencies. To summarize and enable querying of instance-level explanations over time, we introduce DBN-based summarization structure.
Structure Definition. Given a set of temporal explanatory subgraphs n = [G!.....9. ...) over time [1, as discovered explanations for M(G,, v), temporal explanation summary P is directed acyclic graph (DAG) which contains a set of variables X for each timestamp (i E [1,t]), where:
(1) Each variable x in P corresponds to an explanatory node of at time i from subgraph in 7,, and is associated with a discrete, temporal state from a finite state set via a state encoding function from of to zrd The state set at timestamp i is denoted as X,, which may encode node label in node
13

---

Published as a conference paper at ICLR 2026
classification, edge labels for link prediction. Each variable z² carries conditional probability table r,,T to bookkeep its temporal dependencies with its neighboring variables.
(2) There are two types of edges: (a) An "intra-slice" edge outlines the conditional dependencies between two variables from a subgraph in at time i, and (b) a set of "iter-sllic" edges, connecting variables across time stamps, with their directions aligned with the progression of time. These edges help track temporal state changes as the variables evolve, capturing the dynamic nature of the temporal subgraphs.
Summary Learning Objective. Constructing summary P over given set temporal explana- tory subgraphs can be consistently formulated learning an optimal dependency structure of DBN (Klllrr Friedman, 2009p. The learning objective of P can be formulated as optimizing a unified Bayesian Information Criterion (BIC) that optimizes both intra-slice and inter-slice depen- dencies. Given 17 and a DBN P, the BIC score is computed as follows:
PP
log |n.S|
where LL)))S)P) is the log-likelihood of the states 13.S given 1j and the learned structure of P, [P] is the number of the free parameters in the learned structure of P, and |n.S]| is the number of observed states associated to the nodes in Given 1y. TemGX learns a summary P with state encoding and structure such that v is optimized.
Summary Generation Process. For each explanatory node U, E V, at timestamp i, the summariza- tion process extracts feature embeddings from temporal snapshots and discretizes the values using uniform binning to ensure a finite state representation. This yields a structured discrete state set 17.S encode the temporal distribution of V, in a probabilistic space.
The process then learns a set of intra-slice edges and inter-slice edges for V, and v, using BIC score evaluated on aggregated data from all consecutive timestamp pairs [ + for i [1,t-2]. To this end, it invokes fast heuristics (Gámez et al., 2011) 1) that ensures competitive local optima. It finally performs Maximum Likelihood Estimation to optimize the conditional probability distributions of the state nodes, to ensure P accurately fits the observed 7).
Query Support via DBN Summarization. The learned DBN summary P naturally supports in- ference analysis for temporal reasoning. One type of useful inference analysis is to request the likelihood of value of variable xu of interests in 1) particular time t' [1, t] (where the value may not be seen in G.), given a confirmed occurrence of the value of another node variable x' at another time t" [1. This allows efficient "What if" questions.
For example, "What-if" question ask "How likely U, label becomes 'licit' (indicating that TGNN makes a mistake) if the label of 01 is enforced be 'licit', given discovered explanations 17?" The inference analysis can be performed by efficient DBN inference process (Murphy) 2002). with time cost in (In)t) time, where |n) is the total number of nodes and edges of the temporal subgraphs in and t refers to the total period length.
C PROOFS OF MAJOR THEORETICAL RESULTS
Proof of Lemma I We introduce procedure to verify if selected set of nodes V, satisfies the required condition PTIME. (1) The procedure first computes the temporal influence scores Φ(U., v) each timestamp for each explanatory node U. E by definition. This is computable in PTIME. It then induces set of temporal nodes Vo, edges E, and E, via 8-reachability from v, to v. (2) It next verifies the counterfactual property of induced temporal edges, by invoking the inference process of M. which is also in PTIME for mainstream TGNNs. If V. induces set of adjacent edges E. that are counterfactual set, then V, set of valid explanatory nodes. Putting these together, the verification process is in PTIME.
Proof of Lemma The The hardness of the optimization problem. in its decision version, can be verified by a reduction from the maximum coverage problem (MCP), a known NP-hard problem. Given a universe set L4 {u.,..., ), collection of its subsets S (Si...., Sm), and an integer k, the
14

---

Published as a conference paper at ICLR 2026
task is to select at most i subsets from S to instance (4, S, k) of MCP, we construct in polynomial time an instance of lower-level optimization problem follows. (I) Given the universal set 21 for each data point u, in U, we set distinct test nodes Ut, and include it into a test set Vr, with a fixed label I; (2) For each subset S; C U4 we set a "group node" U/, and for each data point tj St, add temporal path ps from U2 vi2 to ensure oy 6-reaches vt,, If uj & St then does not d-reaches Vt,, (3) We choose a simple TGNN that contains single input and constant output layer that directly maps input nodes with constant features to a fixed label 1, hence each group node U2 is an explanatory nodes for the nodes in Vi that can be 6-reached (and temporally influenced) by 2/- We may then verify that there is a k-set of explanatory nodes that "cover" targeted set Vr, if and only if the corresponding & subsets that can cover at a threshold. As MCP NP-hard, the hardness of low-level problem follows.
many elements of U as possible. Given an
Proof of Lemma Algorithm TemGX is a (1 -paprooximaaion for the instance-level optimiza- tion problem, i.e., (V,, 2 (1 ) (VV2 v). We show this result by proving that the problem essentially aims to maximize monotone submodular functiin under a cardinality constraint, set- ting where the greedy algorithm guarantees a :)) approximation (Qian et al. 2017).
Consider the candidate set C for the target output M(Ga, v) and let &(,,, v) denote the temporal influence of any V, S C on M(Gr, v). Let
Vo arg
max IVC.S
(VV., v).
The TGNN model is fully trained and kept fixed, and the input temporal graph window G2 is also fixed during the explanation phase. All influence and resistance scores inf (v., v, (') and trd (v,, v, E') are evaluated once on G; using the trained model and reused throughout the greedy procedure; no model retraining or graph updates are performed while the subset V, grows. Under this evaluation strategy the value of each pairwise score constant during selection.
By the definitions in Section 3
Σ
+ V.. v)
Σ
inf(vs, g(tdd(()) (')) exp(-A(1 (((()))) ()).
8 V.EV 1-=--+11
Define the singleton contribution
t-1
6(U,, 0)
Σ
inf(u,, u, g(rd(,,,, v, v,t') exp(- -t)),
1'=1-6+1
so that (VV,, = En,ev, D).
Monotonicity.
Because every term is non- negateea, for any V, S and v, E C CV.. V.. (V, (v.), o) *(V.,v) (vv,, v) 0.
Submodularity.
Let S B C C and vs E C B. Since @(v,, v) is independent of the current
subset,
Φ (AA (AU - * 2 (B.). ((B,)).
Notice from the definition that the marginal gain introduced by adding node u, is independent of the nodes already present in the set. Specifically, the contribution of node v, is given explicitly by Ei inf v, t') (trdd(v, v, t')) -ex((e((t(("")) which is unaffected by the presence or absence of other nodes in the selected set. Consequently, the marginal gain is constant with respect to the subset context, trivially fulfilling the diminishing returns condition required for submodularity. Therefore, (D-) is submodular over subsets of C.
Because (-)) is monotone submodular applying the standard greedy algorithm under the cardinality constraint |V, < yields a (1 - ( approximation guarantee. Therefore the set V, returned by TemGX satisfies
(V,,, r) 2 (1 - LV v),
The above analysis completes the proof.
15

---

Published as a conference paper at ICLR 2026
Performance analysis of GX for multiple target outputs. By reducing the problem to maxi- mum coverage problem (Vazirami 2013), TemGX ensures the same guarantee of 1 1 as its counter- part for single targeted TGNN output, and can be implemented with the same worst-case time cost. To see this, we show that the algorithm only needs to invoke the single-test node counterpart (Algo- rithm 1) multiple types, and consistently apply greedy selection strategy, that essentially solves maximum weighted coverage problem.
The maximum weighted coverage problem takes as input collection S of sets {S (n), and aims to find a subset S' C S of size k, such that the total weight of the elements in USeS S is maximized. Given graph G a single snapshot with a set of target nodes Vr and their outputs, we construct the following reduction. (1) We set S to be Vr. (2) For each node v in G, we invoke the verification procedure check if any of its adjacent edge is counterfactual edge for any target node "/ E Vr: if so, add the node to set of explanatory nodes Ve, corresponding to the target node 1/-- We say e "covers" V/ in this case. This process takes at most [V verifications. (3) We then construct a universal explanatory node set Ve, which contains explanatory nodes that at least cover one target node in Vy. For each explanatory node v. E V., We initialize a set of subsets of nodes S, such that each subset S E S contains the test nodes covered by c... (4) We set the weights of each element as the temporal influence score (vv, v), for each pair of explanatory node v. and the target node it covers. We may then verify that the solution of the maximum weighted coverage problem, as a subset S' C S, can be converted to a set of selected explanatory nodes that cover exactly a set S of targeted nodes S'. This provides solution for node selection with multiple outputs.
The optimality guarantee follows from the greedy strategy applied for solving maximum weighted coverage problem, which is ensured by solving the problem of maximization of submodular func- tions with a cardinality constraint. As the sum of submodular functions remain to be a monotone submodular function, we only need extend algorithm TemGX for Vr, which (1) for each node in G, verifies if each of its edges is in counterfactual set, for every node in Vr, in single batch, to decide the many-to-many coverage relation; and (2) initializes an instance of a maximum weighted coverage problem, and apply consistently the greedy selection strategy to obtain the results.
The overall cost in O( x k log k + & (Vr) The worst case occurs when each node in VT has distinct set of explanatory nodes that are disjoint with any counterpart of the rest of the nodes in VT.
D DETAILS OF DATASETS
Datasets. We use six weal-world temporal graphs below (summarized in Table 2}. (1) METR-
LA et 2018) and PEMS-BAY (Li et al. 2018) are transportation networks with traffic speeds in Los Angeles and Bay Areas, respectively, where nodes are locations and edges represent road segments. (2) Wiki (Kumar et al.) 2019) includes one month of Wikipedia edits, with nodes as editors and pages and edges as timestamped posting requests. Edge features are 172-dimensional vectors from edited texts. (3) UCIM (unneii 2013) is temporal social interaction network of time- stamped user messages spanning 196 days with a high ratio of unique edges. (4) Multihost (Gao et al. 2021 is cybersecurity dataset capturing multi-step attack scenarios, where nodes represent network hosts, processes, and files, and edges denote attack propagation events including process executions and network connections. (5) Elliptic++ (Elmougy & Liu| 2023) is a dynamic Bitcoin transaction dataset, where nodes correspond to wallet addresses (transactions) and temporal edges represent timestamped cryptocurrency transfers, with the task of classifying illicit transactions.
E EXPERIMENTAL SETTINGS
Set up. All methods and tests are implemented in Python 3.10.12 by PyTorch Geometric. Tests are deployed on HPC cluster with Tesla V100-SXXM-3220 GPU (CUDA ver. 12.2), an NVIDIA driver (ver. 535.54.03 and a dual Intel Xeon Gold 6226 CPU with 24 cores at 3.7 GHz, managed by Slurm. All tests were conducted independent times using different random seeds, and the average results are reported.
Baseline Implementation and Parameter Alignment
16

---

Published as a conference paper at ICLR 2026
Table 2: Summary of datasets, snapshot: average snapshot size (# nodes, # edges); # feature: the
average number of features per node/edge; period: the total time t, iee, number of snapshots in G d: window size; task: the task a TGNN is trained for.
Dataset METR-LA
snapshot
#feature
(period,6)
task
(207,1515)
(34272,12)
regression
PEMS-BAY
(325,2369)
1
(52128,12)
regression
Wiki
(9227,157474)
172
(731,14)
link prediction
UCIM
(1899,59835)
(196.12)
link prediction
Multihost
(6457,252457)
8
(66,4)
classification
Elliptic++
(5156,4784)
166
(49,6)
classification
All baseline explainers were implemented using their official repositories, and all experiments were conducted under identical backbone (TGN, TGAT), (TGN,TGAT), temporal reachability (6 = 12), neighborhood
depth (L 2), and explanation budget (k= = 50). (1)TemGX with 5 12, L 2, k 50. C2) (Qu et al.) with sample_size-see size==0, candidates. sisttessss and a = using identical L = 2. We use CoDy-Spatio- Spaatoo--oTTlllalll recommanded variant (Qu et al.) due its more comprehensive outputs compare with other variants in the CoDy family (which has also been verified by our tests). (3) (3)TGNNExplainer (Xia al. 2022 trained for 200 epochs with learning rate 10-3 and batch size 32, selecting top-k = 50 most influential temporal edges per target link. (4)TempME (Chen & Ying 2023) with learning rate 10 contrastive loss weight A = 1.0, dynamic loss weight 0.5 and fixed mask sparsity threshold corresponding to top-50 edges. (5)For regression datasets (METR-LA, PEMS-BAY), we maintain k 50 ensure comparability of temporal in- fluence fidelity. Additional ablations in Appendix I.1 report results across k E {10, 20, 30, 40, 50), confirming consistent ranking and robustness.
Ad
Evaluation Metrics. For a fair comparison with (Xia et al. 2022 Chen & Ying 2023 we use
three common measures below. (1) The fidelity Fid measures the difference between the orig- inal and new prediction probabilities. Consider an induced explanatory temporal subgraph Ge with temporal edges E., of an explainer. (a) For TGNNExplainer and TempME. E, refers to a set of critical events (edges) as explanations. (b) For link prediction, we compare TemGX, TGNNExplainer, and TempME. Follow the convention (Xia et 2022) that measure the difference over the learned logits Z,= (f)((()))) we define Fid(C., [,, Vr) I(T = 1)- (Z.
(Z(V)) I[r = 0)- (Tr - [). where I(.) is the indicator function, Yr is the true label of Vr, [[]r] and [e[1/ [r] represent the logits of VT on input graph G, and G., respectively. (c) For node regression tasks, TGNNs output predicted values rather than links, hence with their source codes, TempME and TGNNExplainer not directly applicable. We compare TemGX and TGVex, and define fidelity VVV)) 1 - [LMIG. - where M(G))[VT] and M(G are the model [MG
predictions for node V on the explanatory temporal subgraph G. and the full graph G', respec- tively. (2) The sparsity assesses the conciseness of the explanations. We normalize the sparsity E, [VT)] where (V7) refers the temporal edges within I-hopp neighbors of the nodes in targeted nodes VT in the temporal graph Gr, for L-llayered TGNNs. (3) We evaluate performance Curve (AUFSC), consistently following the baseline TGNN explainers. The higher, the better (Xia et al.,
using the fidelity-sparsity curve (FSC) and calculate the Area Under the Fidelity-Spanne
2022
Chen & Ying 2023).
F
STUDY OF ABLATION ON UCIM+TGN
To evaluate the contribution of each component and the sensitivity of critical parameters, we conduct a series of ablation experiments on the UCIM dataset with TGN backbone. These studies quantify the effect of temporal influence modeling, temporal resistance distance (TRD), and temporal decay on both the fidelity and sparsity of the generated explanations.
Component analysis. We first compare four model variants: (1) the full TemGX model, (2) TemGX without temporal decay, (3) TemGX without TRD, and (4) TemGX without ICM influence. The re- sults show that removing any of these components leads to clear drop in fidelity, with the absence of ICM producing the most significant degradation. For example, at the highest sparsity level the fidelity of the full model reaches 0.468, whereas removing TRD reduces fidelity 0.388 and
17

---

Published as a conference paper at ICLR 2026
Table Component ablation on UCIM+TGN, Fidelity is reported at the highest sparsity level.
Variant
Fidelity 1
Relative Drop
Full TemGX
0.468
No Time Decay
0,400
-14.5%
No TRD
0.388
-17.1%
No ICM
0.308
-34.2%
344
3.4
9.2
NXTRO
C1-
1-24
345
0.2
Sparthy
Spanity
Spandty
Tuepporal Decay Rato
(a) Component ablation (b) Effect of sparsity (c) Effect of temporal (d) Temporal decay rate X UCIM+TGN.
bound &..
neighborhood size L.
sensitivity.
Figure 6: Ablation results on UCIM+TGN. (a) compares component settings, (b) studies the im- pact of sparsity bound k, (c) evaluates the influence of the L-hop temporal neighborhood, and (d) analyzes temporal decay rate À sensitivity.
moving ICM reduces fidelity to 0.308. These observations confirm that both temporal influence computation and structural resistance are important for achieving high-quality explanations.
Parameter sensitivity. We next study the influence of three key hyperparametens: the sparsity bound k. the L-hop temporal neighborhood size, and the temporal decay rate X. Increasing k allows larger explanation subgraphs and steadily improves fidelity, from 0.325 Fidelity rises sharply when enlarging the neighborhood from I. = 1 to J. = 2, but beyond T. = 2, indicating that two-hop temporal neighbors capture most of the informative context.
0.468 k 50.
For the decay parameter X, we conduct sensitivity analysis across values ranging from 0.01 to 1.0 as shown in the bottom right of Figure 6 The results reveal a inverted-U shaped relationship between À and fidelity. Very small values (A 0.01) yield suboptimal performance (fidelity 0.385) as they fail to capture distant temporal information. Conversely, large values (A = 1.0) also degrade performance (fidelity 0.375) by emphasizin recent snapshots and losing long-range temporal dependencies. The optimal value À = 0.1 achieves peak performance (fidelity 0.468), effectively balancing recent and historical temporal influence. This systematic parameter sweep validates choice of À = 0.1 and addresses concerns about arbitrary parameter selection.
Overall, these results demonstrate that the proposed temporal influence computation, temporal sistance distance, and decay mechanism are all essential for achieving high fidelity and compact explanations. The sensitivity analyses further guide practical parameter choices: 2-hop neighbor- hood (L 2), a moderate sparsity bound (k- 50). and decay rate around À = 0.1 consistently deliver a favorable tradeoff between interpretability and predictive faithfulness on UCIM+TGN.
G STUDY OF ABLATION ON METR-LA+STGON
To evaluate the generalizability of our approach across different domains and tasks, we conduct ablation experiments on the METR-LA dataset with an STGCN backbone for spatio-temporal re- gression. These studies examine how component contributions and parameter sensitivities differ between social network analysis (UCIM+TGN) and traffic prediction (METR-LA+STGCN), pro- viding insights into domain- speciffc explanation requirements.
Component analysis. We compare the same four model variants: (1) the full TemGX model, (2) TemGX without temporal decay, (3) TemGX without TRD, and (4) TemGX without ICM influence. Interestingly, the component importance ranking differs significantly from the classification task on UCIM. For the traffic regression task, removing temporal decay produces the most severe perfor- mance degradation, with fidelity dropping from 0.471 to 0.393 (a 16.6% decrease). TRD removal
18

---

Published as a conference paper at ICLR 2026
Table 4: Ablation study on METR-LA+STGCN, Fidelity reported at the highest sparsity level.
Variant
Fidelity 1
Relative Drop
Full TemGX
0.471
No Time Decay
0.393
-
-16.6%
No TRD
0.413
-12.3%
No ICM
0.443
-5.9%
8.50
C59
051
324
C45
045
345
8.00
1-26
035
Ostin
Sparsity
Speraity
Speriity
Temporal Denny Rete
(a) Component ablation (h) Effect of
sparsity
(c) Effectt of temporal
(d) Temporal decay rate sensitivity.
METR-LA+STGCN. bound k.
neighhorhond size L.
Figure 7: Ablation results on METR-LA+STGCN. (a) compares component settings, (b) studies the impact of sparsity bound k; (c) evaluates the influence of the T--hop temporal neighhorhood, and (d) analyzes temporal decay rate À sensitivity for traffic regression.
causes 12.3% performance drop (fidelity 0.413), while ICM removal has the smallest impact with only 5.9% degradation (fidelity 0.443).
Parameter sensitivity. We examine the same hyperparameters, but observe distinct optimal values reflecting traffic data characteristics. The impact of the sparsity bound exhibits similar trend, consistent with the performance plateauing
50 (fidelity 0.471) and minimal improvement at h: = 100 (fidelity 0.473). The L-hop neighborhood analysis reveals that the results at I, = slightly outperforms its counterpart at 7. in traffic networks (fidelity 0.476 vs 0.471), capturing longer-range spatial propagation of congestion effects along interconnected road segments. Most notably, the temporal decay rate À requires different discounting strategies for traffic data, with optimal performance at À = 0.07 compared to À 0.1 for social interactions. This reflects the finer temporal granularity traffic patterns (5-minute intervals), where maintaining more historical information is crucial for capturing traffic cycles and rush-hour dynamics.
The domain-speciffr differences reveal important insights about temporal graph explanation. In traffic networks, temporal patterns (captured by decay mechanisms) are even more dominant than in social networks, with a 16.6% performance drop compared to 14.5% UCIM, as traffic flow follows highly predictable temporal cycles with rush-hour patterns. The temporal resistance dis- tance remains important but shows increased significance (12.3% vs 17.1% UCIM), reflecting the continuous spatial propagation nature of traffic congestion compared to discrete social connections. Notably, ICM influence shows dramatically reduced importance in traffic regression (5.9% vs 34.2% in social classification), suggesting that influence maximization concepts less relevant for physi- cal flow prediction than social interaction modeling. These findings demonstrate that while TemGX maintains some consistent parameter optimization strategies importance and temporal decay requirements must be carefully adapted to domain-specific charac- teristies. The sensitivity analyses further guide practical parameter choices for traffic applications: a 2-hop neighborhood (L 2) to capture extended spatial propagation, a moderate sparsity bound (I: 50), and a finer temporal decay rate (A 0.07) that preserves more historical information for spatio-temporal regression on METR-LA+STGEN.
50), both the relative component
H TemGX IN THE WILD: APPLICATIONS
Case I: Interpretable Illicit Account Detection Bitcoin Transactions. The Bitcoin transac- tions dataset is derived from Elliptic++ (Elmougy & Liu 2023), where nodes wallet addresses and temporal edges are timestamped transactions. We train TGN and TGAT for clas- sification and apply TemGX for instance-level explanations.
19

---

Published as a conference paper at ICLR 2026
Parameter settings. We set the hop size L 2, temporal decay À 0.1, and the explanation size k = 5 per window. Each window uses a distinct test node.
Results. Table [ showcases set of explanatory subgraphs reported by TemGX. The Red nodes denote the explanatory set V., blue nodes are connecting nodes Ve, and the green node is the target host Ví. and the corresponding ground truth. We report the two summarized patterns. We found that these two patterns are highly consistent with the verified money laundering patterns in Bitcoin transaction: Peel Chain and Spindle. Moreover, TemGX can capture how the transactions "evolve" from one strategy to another.
For example, in the time window Wi in Table TemGX generates an explanatory subgraph for the target node 4827 (classified by TGN as an illicit account) that clearly reveals real Bitcoin "peel chain" money-laundering pattern. The most influential explanatory nodes include 1247, 2103, 892, 4785, and 921: among them, 2103 acts as an upstream fund aggregation hub that frequently receives large external transfers; 1247 and 892 exhibit high-frequency dress changes, serving typical relay accounts; and 4785 and 921 provide supplementary fund in- puts to 4827 within a short time span. The main transaction paths appear as 2103 - 1247 + 4827, 4785 + 892 + 4827, and a direct transfer 921 + 4827, forming a multi-source peel-chain struc- ture.
transaciannsts and frequent ad-
Leveraging the 9-reachability constraint, TemGX ensures that these nodes remain temporally nected to 4827, thereby isolating the most time relevant upstream fund sources likely to influence the TGNN model's prediction. The resulting explanation not only covers all key accounts and trans- action paths of the peel chain, but also strictly respects temporal constraints, providing verifiable and practically meaningful evidence for classifying 4827 as an illicit account. Unlike TemGX, the sub- graphs generated by CoDy and TGNNExplainer lack this temporally coherent, 5-reachable structure and fail to capture the temporal peel-chain transactions.
Case II: Explainable Multi-step Cybera Cyberattack Detection
The Cyberattack dataset (Gao et al. 1021 is constructed from system audit logs, where nodes represent hosts, processes, or files and temporal edges record timestamped events. We train TGN and TGAT for host compromise classification and apply TemGX for eetance-levee explanations.
Parameter settings. To capture long-range attack chains, we the hop size L 3, temporal decay À = 0.1, and explanation size k- 4 per window. Distinct target hosts sampled for each window.
Results. Table d demonstrates that TemGX identifies critical multi-stage cyber attack pathways across four representative time windows, with the discovered explanatory subgraphs (red nodes) and connecting nodes (blue nodes) capturing the temporal progression from initial compromise through privilege escalation to data exfiltration that domain experts recognize realistic attack scenarios.
For example,in time window W4 in Table TemGX generates an explanation subgraph for the target node 235 (classified by the TGAT as a compromised core server srv235) that reconstructs the multi-stage attack chain from initial intrusion to data exfiltration. The key explanatory nodes include srv294, srv900, proc787, relay 173, and relay442. srv294 records the first cross-domain login attempt following external scanning srv900 subsequently escalates privileges to obtain higher access rights; proc787 executes repeated MD5 hash operations in short period, corresponding to the attacker preparing data packaging; relay 73 acts as a cross-subnet relay, forwarding multiple files containing sensitive credentials to relay442 within 10 minutes; finally, relay442 establishes high-privilege session with srv235 and triggers an abnormal read of finance_report.z2) which aligns with known data-exfiltration behavior.
TemGX's 's temporal ó reachability together with temporal resistance distance (TRD) accurately iso- lates nodes that are both temporally and structurally closest to srv235, ensuring that each attack path (e.g., line and causal order. In contrast, TGNNExplainer and CoDy contain only a few isolated nodes. This structurally consistent explanation not only provides direct evidence for the TGNN prediction that srv235 is compromised, but also enables security analysts to reproduce the attack scenario and design targeted defense strategies.
respects the real attack time-
20

---

Published as a conference paper at ICLR 2026
Table 5: Explanations by TemGX Elliptic++
(Elmougy Liu 2023
Time Win- dow
Target Node
TGN (TemGX)
TGAT (TemGX)
Ground Truth
Description
W1
4827
Peel Chain.
W2
4123
Peel Chain.
Wg
3291
Spindle.
W4
3011
Spindle.
21

---

Published as a conference paper at ICLR 2026
Table 6: Explanations by TemGX on the Cyberattack (Gao et al. 2021
Time Win- dow
Target Host ID
TGN (TemGX)
TGAT (TemGX)
Ground Truth
Description
Initial compromise chain to the target host.
W
664
Privilege escalation following compromise.
W2
702
Data exfiltration via covert/relay steps.
W;
233
Data exfiltration via covert/relay steps.
W,
235
22

---

Published as a conference paper at ICLR 2026
Case III: Comparison of explanation structures. We analyze the structural characteristics of ex- planations generated by different temporal graph explainers on the Wiki datasets (Table revealing key methodological differences:
Temporal Cohesiveness. the Wiki link prediction task, each target edge p. represents that user edits page p time CoDy relies Monte Carlo sampling and backtracking, frequently combining events from disjoint time periods that are not ô-reachable, producing temporally frag- mented subgraphs. TempME tends select local motifs on each side of the target edge, resulting in two separated clusters with no temporal bridge. TemGX, in contrast, enforces ò-reachability so that only events within the time window and connected to (u. p, t) are retained. The resulting explana- tions form time-respectin respecting paths, such as "co-edit - short gap - repeated co-edit - target edit," avoiding the disconnected event islands seen in the baselines.
Queryable Capabiliiiess TGNNExplainer, CoDy, and TempME output a single static subgraph that cannot be further queried. Analysts cannot directly ask questions such as "within a 8-window, which group of co-editing users jointly influence the target edge?" or "wwat is the impact of remov- ing cross-page edits within the last hour?". TemGX outputs queryable temporal subgraph: under the ò-reachability constraint, analysts ports probabilistic summarization via a Dynamic Bayesian Network (DBN), condensing frequent temporal patterns (e.g., "near-time co-edit target edit") into reusable transition probabilities for analysis.
issue temporal pattern queries. Moreover, TemGX sup-
Computational Considerations. TGNNExplainer requires additional training of navigator incur- ring high training and explanation costs. CoDy depends on large-scale Monte Carlo candidate sam- pling with iterative backtracking, which is computationally expensive. TempME performs random- walk motif matching, and its inference time grows quickly with motif complexity or candidate size. TemGX is training-free free and uses one-pass greedy selection guided by ICM and TRD scores. The 5-reachability prunes temporally irrelevant events and keeps the search space within a time window around the target, ensuring stable runtime and memory usage even large temporal graphs.
Overall, for Wiki's link prediction task, TGNNExplainer's navigator produces temporally discon- nected explanations, CoDy's 's sampling yields cross-windde fragments, and TempME fails to capture continuous time decay. TemGX ensures temporal cohesiveness, integrates TRD with temporal de- cay modeling, and supports queryable probabilistic analysis, delivering explanation subgraphs with temporal consistency and practical interpretability.
Table 7: Comparison of Explanation Subgraphs on Wiki Dataset (Fixed k = 5).
Case
TemGX
CoDy
TGNNExplainer
TempMF
Usen2913
Case
User:2913
1
Item:8887
Item:8867
Item:8887
User:2913
User:2913
Htem8887
Case
User:3055
User:3055
User:3055
Item:6122
Item81122
Item:81122
Item66
User:3055
I STUDY OF QUERYING TEMPORAL EXPLANATIONS
Exp-4: Querying Temporal Explanations. We next showcase how TemGX supports queryable explanation for real-world TGNN use cases.
23

---

Published as a conference paper at ICLR 2026
COFDS 1991
HAUR
2000 2016 210
0.653
2
Sytedt
Spiack
10
Implotious
Poomeed Croc
Proree Creck
G.
Pud Chais
(a) Bitcoin Transaction Analysis
(b) Multi-stage Attack Detection in Provenance Graphs
Figure 8: Querying Temporal Explanations Case Analysis
Clarifying Suspicious Transactions. Fig. 5 (i) shows a fraction of the Bitcoin network around node 140 (an "illicit" IP detected by a TGN). Fig. 5 (ii) illustrates three temporal explanatory subgraphs Ge--G. -Geg generated by TemGX for node 140. To demonstrate instance-level querying capabilities, consider temporal pattern queries Q, (VQ. Eq. a, 8') posed on the discovered explanations. For example, "Spindle" pattern query with nodes (418, 2819, 2411} can be efficiently matched against G. at the first timestamp through TemGX algorithm. Similarly, querying for "Peel Chain" patterns involving node 2216 successfully retrieves matches from Geg. highlighting how explanatory struc- tures evolve over time.The querying interface allows users to search for specific temporal depen- dencies: "Find all explanatory subgraphs where node 418 transitions to 782 as Spindle participants" returns Ge with updated participants {782, 2558, 2411, 2819). Such queries enable the investiga- tion of suspicious transactions that are well-grounded by money-laundry patterns, and track their temporal evolution across different laundering strategies via DBN inference.
Fig. (iii) illustrates fraction of summary explanation P, referring to explanatory IPs and their temporal states over time, which allows analysts query cross-time dependencies that standard static models would miss. For example, an inference query that asks "what is the likelihood of an 'licit' account 2411 be 'illicit'?" returns that 2411 has 63. 10% chance remain licit and 36.90% chance to become illicit at time t2, yet a higher chance 65. 20% at time f3. Indeed, 2411 is under more substantial influence from illicit IP 140, grounded by Spindle and Peel Chain matches in Ge, at instance level.
Multi-stage Cyber Attack Analysis. Fig. (i) illustrates multi-stage cyber attack scenario from the Multihost dataset, where TemGX enables querying of malicious activities across network hosts. instance, querying "Find attack paths involving sattherrpasworr..ss followed by crack track.passwd.stt efficiently retrieves the temporal dependency chain from hostl to host2 across the discovered sub- graphs in Fig. (ii).
Security analysts can pose more complex temporal queries such as "Identify hosts where Shellshock vulnerability leads to payload download within 8' = 2 time steps", which matches the attack pro- gression involving libfoo.so download host2. Similarly, data exfiltration queries targeting "MD5 hash operations on john.zip" can be processed to trace the complete attack kill chain.Such instance- level querying enables security teams to investigate attack patterns, validate incident response proce- dures, and identify similar attack vectors across different temporal windows, transforming explana- tory subgraphs into actionable threat intelligence.
Fig. g (iii) illustrates a fraction of summary explanation P. An inference query that asks "what is the likelihood of host 2924 being attacked if host 3259 is attacked?" posed TemGX returns that 2924 has only a 5% risk when host 3259 is secure, yet when host 3259 is attacked, this proba- bility increases to 32.1% 1% at the second timestamp and further escalates to 75.7% during the lateral movement phase. This demonstrates TemGX's s ability to provide grounded explanations for complex multi-step cyber attack analysis.
24

---

Published as a conference paper at ICLR 2026
J FIXED EXPLANATION SIZE ANALYSIS
We conduct additional experiments evaluating all methods at fixed explanation sizes k E {10, 20, 30, 40,50). This controlled setting ensures that performance differences reflect edge se- lection quality rather than the number of edges used. We focus on UCIM and Wiki datasets with TGN backbone. At k = 50, this corresponds to fidelity values of 0.468 and 0.262, matching Table configurations.
Fidelity Analysis. Figure (a-b) shows that TemGX consistently outperforms basclines across all values on both datasets, On UCIM, TemGX achieves 18.8% higher fidelity than CoDy at k = 50 (0.468 vs 0.394), with the gap widening from 6.8% k improvement with larger k. CoDy shows 43.3% improvement from & = 10 to k = 50, whereas TemGX maintains steady growth (58.64 6% improvement). This validates our contribution: TemGX's ICMx (CM identifies structurally critical edges even when temporally distant.
Critically, while all methods show
0.5
Fldelity
Fidality
0.30
0.1
Tmmphi
0.03
Timatiz
ToMNExch nor
TOAMExpaaiee
0.0
30
0.00
10
56
(a) UCIM fidelity.
(b) Wiki fidelity.
Figure 9: Fixed explanation size comparison UCIM and Wiki datasets with TGN backbone.
K. FLIP-RATE ANALYSIS
We have added flip-rate analysis reporting the frequency of prediction changes after removing explanatory subgraphs across all datasets and backbones. For a target node with prediction
(GG,, v2) Mpredd we define flip-rate as: flip rate Ge the discovered explanatory subgraph and Vr is the set of test targets. For classification and link prediction tasks, "L" indicates different predicted class/link; for regression, "L" means [M(.,) - M(G, \ G.)l > 0.05 x (M.) (i.e., more than 5% relative change).
where
[Vrl
Table presents flip-rate statistics across all experimental configurations. Flip-rates consis- tently range from 81-87% across 12 backkbe configurations, confirming counterfactual validity across diverse tasks and application domains. Removing the explanatory subgraphs changes the majority of predictions, demonstrating that TemGX identifies important temporal-structte sttuuctual sub- graph rather than merely correlated features.
Results:
L TEMPORAL PARAMETER SELECTION AND THEORETICAL RELATIONSHIP
The ô-reachability threshold and temporal decay rate À theoretically coupled rather than inde- pendent. Following temporal kernel theory (Mei & Eisner 2017: Trivedi et al. 2019). we suggest aa/6, where a [0.8, 1.2) normalizes for dataset-specific temporal density. This ensures the effective time (1/A) aligns with the time window ò, preventing overly rapid or slow decay. At the 0.37-0.45, providing mean-
reachability boundary (t d). the temporal weight e ingful decay consistent with TGNN kernels (Xu et al. 2019
Practical setting. We choose 5 based domain-specifec temporal scales e.g.. 5 12 for social graphs (UCIM, Wiki), = 12 for traffic data (METR-LA, curity logs (Multihost). Given 5, X is initialized 1/6 and slightly adjusted (e.g., 0.00000..
and = 4-6 for cyberse-
25

---

Published as a conference paper at ICLR 2026
Table 8: Flip-Rate Analysis: Frequency of Prediction Changes After Removing Explanatory Sub- graphs. Results shown for all
configurations.
Dataset
Model
Task
Flip-rate
Avg Fidelity
TGN
Link Prediction
87.3%
0,468
UCIM
TGAT
Link Prediction
85.6%
0.415
TGN
Link Prediction
81.2%
0,262
Wiki
TGAT
Link Prediction
83.7%
0.335
STGCN
Regression 84.6%
0.471
METR-LA
DCRNN
Regression
83.1%
0,436
STGCN
Regression 85.2%
0,473
PEMS- BAY
DCRNN
Regression
83.9%
0.441
TGN
Classification 84.2%
0,281
Multihost
TGAT
Classification
82.5%
0,267
TGN
Classification 85.4%
0.358
Elliptic++
TGAT
Classification
83.6%
0.342
0.50
0.30
26
* 5-12
0.45
0.25
15
Sccond
Seconds
0.35
0.25
16
20
0.10
12
12
20
16
20
Window Stze (8)
Window See
(a) UCIM fidelity.
(b) Wikipedia fidelity.
(c) UCIM runtime.
(d) Wikipedia runtime.
Figure 10: Window size sensitivity analysis UCIM and Wiki with TGN backbone.
M WINDOW SIZE SENSITIVITY ANALYSIS
We analyze the impact of window size (d)) on TemGX performance to validate our parameter lection. We evaluate TemGX on UCIM and Wiki datasets with varying {4,8, 12, 16, 20) while keeping other parameters fixed (k 50, L 2. Vr 100).
Results and Analysis: Figure TO presents the sensitivity analysis results. We observe distinet pat- terns across datasets: UCIM (Figures (a(a) and [O(C):: Fidelity exhibits a inverted U-shape curve,
achieving peak performance at 8 12 (fidelity00.468) Smaller windows (6 12) suffer from incomplete temporal coverage, missing long-range dependencies that contribute to TGNN predic- tions. For instance, 8 4 achieves only 0.285 fidelity (39% lower than optimal), critical historical events beyond the 4-snapshot window are excluded. Conversely, larger windows (8 >> 12) introduce noise from distant, weakly relevant events, degrading fidelity to 0.412 5 20 (124 11% below peak). Runtime grows with ő due to early termination in our greedy selection, scaling from 3.2s at 13.8s
to 20. Wiki (Figures 10(b) and [0(d): Fidelity demonstrates plateau region between = 12 and 5 16 (0.255-0.258), indicating robustness to window size within this range. This plateau reflects Wikipedia's denser temporal graph structure, where editing patterns involve multi- ple interconnected snapshots. We select = 12 as it provides optimal fidelity (0.255) with lower computational cost (1 (1))8) compared 8 16 (14.2x), maintaining consistency with UCIM's opti- mal setting. Similar to UCIM, very small windows
4: 0.143 fidelity) fail to capture sufficient temporal context, while excessively large windows (Ō 20: 0.235 fidelity) accumulate noise.
N SCALABILITY ANALYSIS
To further validate the efficiency of TemGX under varying input scales, we conduct a scalability test with respect to (1) the number of explanatory edges & and (2) the number of target nodes [V]]. All
26

---

Published as a conference paper at ICLR 2026
experiments performed the Wiki dataset with TGN backbone under the same hyperparameter configuration (L = 2, ò = 12).
10
Total Time (seconds)
Total Time (seconds)
10a
10
TGNNExplains
TempME
Copy
Tem6X
TGANExplainer
103
10a
500
[V_T]
(a) Runtime explanation size k
(b) Runtime vs. number of target nodes
|vr
Figure 11: Scalability test TemGX and baseline explainers. (a) shows runtime growth with respect
to explanation size k and (b) with respect to target node count [V Both are shown in log scale.
[Tbb) report the total computation time TemGX, TGN- NExplainer, TempME, and CoDy. We observe that TemGX consistently achieves the lowest runtime across all settings. As l increases from 10 to 50, TemGX increase from 2.5 x 109 to 6.3 x 10s sec- onds, while TGNNExplainer and TempME range between 3.4 x 104-3.8 10a seconds, and CoDy grows to over 6.2 x 10t seconds due to Monte Carlo Tree search. Similarly, as |Vr] increases from 100 500, TemGX's total runtime rises from 1.2 x 10 6.2 10a seconds, whereas TGNNEX- plainer and TempME increase from roughly 6.8 x 108-3.8 x 10a seconds, and CoDy expands from 1.2 10* to 6.3 x 104 seconds. This scalability test verifies that TemGX's computational cost grows with local neighborhood size rather than global graph scale. The scalability advantage primar- ily arises from the greedy selection and verification mechanism that avoids redundant traversal over the temporal graph, in contrast to iterative retraining or exhaustive search required by model-specific explainers.
Results and Analysis. Figures (T(a) and
27


Reviews:
[{"review_id": "SGCBrbwIao", "reviewer": "Reviewer_nRh9", "summary": "This paper introduces TemGX, a training-free, model-agnostic framework for explaining predictions from Temporal Graph Neural Networks (TGNNs). The proposed method discovers instance-level temporal subgraphs whose removal changes model predictions, aligning with counterfactual reasoning. TemGX quantifies temporal influence using information cascading and resistance distance metrics, and provides algorithms for efficient explanation generation with guarantees.", "questions": "1 What exact implementation of CoDy and other baselines were used, what are the hyperparameters?\n\n2 Why were Multihost and Elliptic++ not quantitatively evaluated like the others?\n\n3 How does TemGX behave when no counterfactual explanations exist for a prediction?\n\n4 Please address the weaknesses mentioned above.", "limitations": "", "rating": 2, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1 The paper introduces a training-free and queryable framework for generating counterfactual explanations of temporal graph models\n\n2 The proposed method is straightforward and computationally efficient, and it could be adapted for different temporal GNN architectures and tasks.\n\n3 The framework combines temporal influence modeling, resistance distance, and time-decay mechanisms in a coherent formulation supported by an approximation guarantee.", "weaknesses": "1 Baseline implementation details are insufficient. It is not mentioned which CoDy variant is used, nor its hyperparameters. Hyperparameters for the other baselines are also not mentioned. Code for the baseline implementations are not provided. \n\n2 Evaluation metrics are defined in an unconventional and problematic way. \nHigher sparsity (i.e., larger explanatory subgraphs) is implied to be better (explicitly stated in Appendix E), but this is confusing. Shouldn’t it be that smaller sparsity indicate more concise explanations, and therefore preferred? Instead, the current design seems to reward larger subgraphs, which naturally include more of the L-hop neighborhood and hence boost fidelity and AUFSC scores.\nThis effect is clearly visible in Figure 4, where the fidelity score of TemGX increases when the sparsity score increases. However, the fidelity score of CoDy basically stopped growing when sparsity reaches around 0.2. Doesn’t this mean that CoDy is superior, since it is able to identify the most decisive but also concise and stable counterfactual explanation?\nMoreover, when sparsity equals to 1, it means the entire L-hop neighborhood is used for the explanation, which raises doubts about the usefulness of such explanations. If all available context is included, the explanation is questionable.\nIn addition, there appears to be inconsistency between Table 1 and Figure 4. While fidelity and AUFSC scores are reported in Table 1, the corresponding sparsity levels are not shown, making it difficult to interpret the trade-off. I would assume that the sparsity scores are fixed for all explanation methods, but this is never clarified. Based on Figure 4 and Table 1, it appears that in some cases, CoDy and TemGX are compared at different sparsity levels. For example, in the UCIM + TGN case, the fidelity scores for TemGX and CoDy are 0.468 and 0.394, respectively, as reported in Table 1. However, Figure 4 shows that TemGX achieves such fidelity score at a sparsity of around 0.4, while CoDy reaches its reported fidelity at a sparsity of around 0.2. This suggests that TemGX’s explanatory subgraph is roughly twice the size of CoDy’s in this setting. Without controlling for sparsity, it becomes unclear whether the fidelity improvement of TemGX truly reflects better explanation quality or simply results from including more of the neighborhood context.\nIn general, the evaluation is not convincing to me, and I believe this is the biggest weakness of the paper. If this issue can be sufficiently addressed, I would consider to increase the score.\n\n3 Counterfactual analysis is under-specified. No results are provided on the flip-rate (how often the prediction actually changes, or how often counterfactual explanations can be found). Without this, the counterfactual nature of the explanations remains unproven.\n\n4 Classification datasets (Multihost and Elliptic++) are used only in qualitative case studies and are excluded from quantitative results. The paper mentioned these 2 datasets are used for classification, but does not mention the model nor the quantitative explanation results, leaving this part of the evaluation incomplete.\n\n5 Case studies: The case studies are poorly analyzed and not compared with the baselines, and their connection to the claimed strength of TemGX is superficial at most.\n\n6 Poor writing. In general, the writing of the paper should be improved. The example in the introduction is difficult to follow. Figure 1, 2, and 5 all contain many subgraphs that are very small, and not sufficiently described, this is difficult for the readers to follow. The conclusion is overly brief. \n\n7 Missing citation and baseline. It seems that this paper is focusing on discrete time dynamic graphs, but CoDy is designed for continuous time dynamic graphs by its nature. The following paper presents a counterfactual explanation method for DTDGs, it should be included as a baseline, and their evaluation metrics validity and GED should also be taken into consideration. \n\nPrenkaj, B., Villaizán-Vallelado, M., Leemann, T., & Kasneci, G. (2024, August). Unifying Evolution, Explanation, and Discernment: A Generative Approach for Dynamic Graph Counterfactuals. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 2420-2431).", "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": "", "extra_scores": {}}, {"review_id": "J3KPQN5qaZ", "reviewer": "Reviewer_4jHd", "summary": "The paper proposes a temporal graph explainer that identifies temporal subgraphs and their solutions based on counterfactual reasoning without any additional training over the base model. The explanation task is framed as a constrained optimization problem over temporal edges and nodes. The detailed experiments show the superiority of the proposed model.", "questions": "- You define temporal counterfactual edges, and then aggregate corresponding nodes/edges into a temporal subgraph as the explanation. Under what conditions does this subgraph remain a counterfactual? Please clarify your assumptions.\n- Given the small number of trials, can you include mean ± standard deviation (and optionally statistical confidence) for all metrics? \n- Can you clarify where does stochasticity enter the pipeline?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clear, well-written introduction that makes the problem easy to understand.\n- Extensive experiments across multiple datasets with strong baseline comparisons.\n- Tackles a difficult problem with a careful, principled formulation.\n- Supported by theoretical analysis.\n- Open-source code is provided and well documented.", "weaknesses": "- The role and sources of randomness in the method are underexplained.\n- The number of experimental trials (k = 5) is small for robust statistical conclusions.", "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": "", "extra_scores": {}}, {"review_id": "IgzVUFZZ0p", "reviewer": "Reviewer_PEm2", "summary": "The paper proposes TemGX, a training-free, model-agnostic, and counterfactual explanation framework for TGNNs that: (1) efficiently identifies temporal explanatory subgraphs responsible for a model prediction. (2) propose a class of temporal explainability measures to verify these explanations. Experimental results show that TemGX outperforms other TGNN explainer methods in AUFSC, Fidelity and running time.", "questions": "- Please see Weaknesses section. Below are some extra questions:\n- Can the author provide insights on how window size can impact TemGX performance?\n- Temporal decay also seems to provide limited performance improvement compared to ICM and TRD. Can the authors provide insights on why this is the case.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is well-written, and the case analyses provide good insights into the real-world applicability of the proposed framework.\n- Experimental results show that TemGX outperforms other TGNN explainers on AUFSC, fidelity, as well as efficiency. \n- The paper provides formal proofs that TemGX is a (1-1/e)-approximation, and it is in PTIME to verify the counterfactual properties for temporal subgraphs, which are meaningful contributions.\n- The paper provides an analysis of the impact of different components (ICM, TRD, and temporal decay) of the temporal explainability measure on the fidelity score and shows that each component has a meaningful impact.", "weaknesses": "- It seems like the temporal explainability measure is a composition of established concepts, i.e. temporal effective resistance distance was previously proposed in (Zhu et al., 2024; Black et al., 2023), temporal decay was previously proposed in (Mei & Eisner, 2017), and temporal impact is an extension of the Independent Cascade Model. Can the authors clarify the novelty of this formulation?\n- There is a lack of scalability analysis in the paper. It is unclear how the algorithm will scale to large temporal graphs. Even if the current algorithm is not scalable to large temporal graphs, the authors should still provide a theoretical or empirical scalability discussion.\n- It seems like the algorithm is sensitive to the choice of the temporal decay rate λ. Does that mean we have to re-run hyperparameter sweeping for λ on each new dataset or task?", "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": "", "extra_scores": {}}, {"review_id": "DgGLHKu6nS", "reviewer": "Reviewer_Kj7f", "summary": "The paper proposes an efficient explanation method for temporal graph neural networks. They introduce several engineering techniques and approximation algorithms to find the set of important input information that explains the model's decision.", "questions": "Previously, the work \"On the Limit of Explaining Black-box Temporal Graph Neural Networks\" (https://arxiv.org/pdf/2212.00952) pointed out that there exists certain information of TGNN that can never be faithfully recovered if only perturbation are used to examine TGNN. I am wondering how this work addresses the problem pointed out in the above paper?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think this is a solid paper. The problem is well analyzed and the reasoning and technicalities of the method make sense to me. I also think the experimental results are thorough and carefully designed.", "weaknesses": "I expect general readers will have a hard time digesting this paper since it involves a lot of technicalities (from TGNN, explanation methods for it and some background in approximation algorithms), I would prefer if the authors can present the work in more intuitive manners.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)