💻 computer science

Towards the Explainability of Temporal Graph Networks via Memory Backtracking and Topological Attribution

This paper proposes MemExplainer, a novel framework that enhances the explainability of Temporal Graph Networks by introducing topology attribution and memory backtracking trees to quantify the influence of historical events on predictions, thereby outperforming existing methods across various temporal graph tasks.

Original authors: Yazheng Liu, Xi Zhang, Sihong Xie, Hui Xiong

Published 2026-07-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yazheng Liu, Xi Zhang, Sihong Xie, Hui Xiong

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you're trying to figure out why a super-smart robot friend predicted that two people in a social network are about to become besties. The robot, called a Temporal Graph Network (TGN), is great at making these guesses, but it's usually a "black box." You ask, "Why did you think that?" and it just shrugs.

The problem is that previous attempts to peek inside this black box were looking at the wrong thing. They looked at the current connections between people but ignored the robot's memory. Think of the robot's memory like a diary where it writes down every interaction it's ever seen. If you ignore the diary, you miss the whole story of how the robot learned to make its prediction.

The "Memory Backtracking" Breakthrough

The authors of this paper, Liu and team, say, "Wait a minute! To understand the prediction, we have to read the diary!"

They built a new tool called MemExplainer. Instead of just looking at who is friends with whom right now, this tool does two cool things:

The Topology Tree (The "Who's Who"): It maps out the immediate neighborhood. It asks, "Who are the neighbors of these two people, and what are their current 'vibes' (memory vectors)?"
The Memory Backtracking Tree (The "Time Travel"): This is the magic part. It traces the robot's diary entries backward in time. It asks, "Which specific past events (like a message sent three days ago or a comment from last week) actually updated the robot's memory to make it think these two are friends?"

Why the Old Way Failed

The paper explicitly argues against the old methods (like TGNNExplainer or TempME). These older tools treated the robot's memory as a frozen statue. They looked at the memory at the exact moment of prediction and said, "Okay, this is the state, let's explain it."

The authors show that this is a huge mistake. It's like trying to understand why a chef made a specific soup by only looking at the pot after the cooking is done, without ever looking at the ingredients they threw in earlier. By freezing the memory, the old methods missed the "long-term impact" of historical events. They couldn't see that a tiny interaction from weeks ago was the real reason the robot made its choice.

The "Conservation" Rule

Here's where the math gets playful. The authors use a method called Layer-wise Relevance Propagation (LRP). Think of this like a game of "hot potato" where the "heat" (the prediction score) must be passed down from the final answer all the way back to the original events.

The paper proves a strict rule: The total heat of all the past events must equal the final prediction score. Nothing is lost, and nothing is made up. If the robot predicts a 100% chance of friendship, the sum of all the "friendship points" from every past event must add up to exactly 100. This ensures the explanation is "faithful"—it's not just a guess; it's a mathematically guaranteed accounting of the robot's thoughts.

The Results: Did it Work?

The team tested this on nine different real-world datasets, ranging from Wikipedia edits and Reddit posts to email chains and even human movement videos (like doing a pull-up or running).

The Proof: They compared their method against four other top-tier explainers. In 77% of the cases, their method was statistically significantly better at explaining why the model made a prediction (measured by a metric called FidelityKL).
The Visuals: In a case study involving human actions (like climbing or running), the old methods usually highlighted almost the entire skeleton, making it hard to see what mattered. MemExplainer, however, picked out just the specific joints and movements that actually drove the prediction (like the hip-knee-ankle chain for running), leaving the rest in the dark.

What They Didn't Solve

The paper is honest about its limits. While the method works great, it can get computationally heavy if the "memory backtracking tree" gets too deep and wide. The authors suggest that for massive graphs, you might need to limit how far back in time you look (the "depth" of the tree) to keep the computer from running out of steam. They didn't claim to have solved this perfectly yet; they just showed that their current approach is the best we have so far.

The Bottom Line

The paper suggests that if you want to trust a Temporal Graph Network, you can't just look at the present. You have to follow the breadcrumbs of its memory back through time. By building these "backtracking trees," MemExplainer gives us a faithful, mathematically sound map of exactly which past moments shaped the robot's future predictions. It turns a black box into a transparent storybook.

Technical Summary: Towards the Explainability of Temporal Graph Networks via Memory Backtracking and Topological Attribution

Problem Statement
Temporal Graph Networks (TGNs) have achieved superior predictive accuracy in real-world applications such as fraud detection and healthcare forecasting. However, they operate as black-box models, offering little transparency regarding how historical events drive predictions. Existing explanation methods for TGNs (e.g., TGNNExplainer, TempME) primarily focus on the topological structure of the graph but overlook the memory module, a core component responsible for recording and updating node histories. By fixing the final memory vectors, these methods ignore the temporal evolution of node states, leading to unfaithful explanations that fail to capture how past interactions accumulate to shape future predictions.

Methodology
The authors propose MemExplainer, a framework that attributes TGN predictions to both neighboring events (spatial) and historical events (temporal) by explicitly modeling the memory module. The methodology consists of three main stages:

Topological Attribution Tree (Spatial Decomposition):
The framework constructs a topology attribution tree to quantify the contribution of neighboring events and node memory vectors to the target node embedding. Using Layer-wise Relevance Propagation (LRP), the method decomposes the target node embedding ( $z^t_u$ ) into contributions from the target memory, neighbor memories, and event features. A key theoretical contribution is the proof of a conservation property, ensuring that the sum of contributions from all neighbor events and node memories equals the original logits.
Memory Backtracking Tree (Temporal Decomposition):
To address the limitation of fixed memory vectors, the authors construct a memory backtracking tree. This tree recursively traces the influence of historical events on the current node memory vectors. By applying LRP to the memory update function (e.g., GRU or RNN), the method attributes the contribution of the current memory state back to the specific historical events that triggered updates. This process ensures that the total contribution of all historical events equals the total memory contribution, maintaining the conservation property throughout the temporal dimension.
Event Selection via Optimization:
Due to the nonlinear mapping from logits to probabilities, a simple top- $k$ selection of events may be unfaithful. To address this, the authors derive the KL divergence between the original prediction and the prediction made using only a subset of selected events. They formulate an optimization problem to select a subset of important events ( $E^*$ ) that minimizes this divergence, ensuring the explanation faithfully reproduces the model's behavior.

Key Contributions

Memory-Aware Explanation: Unlike prior works that fix memory vectors, this method explicitly tracks how historical events update node memories, providing a more faithful attribution of predictions.
Conservation Property: The framework ensures that the sum of contributions from all events (both neighboring and historical) equals the model's final logits, a critical property for rigorous explanation.
Dual-Tree Architecture: The combination of a topology attribution tree (spatial) and a memory backtracking tree (temporal) allows for a comprehensive decomposition of TGN predictions.
Optimization-Based Selection: The use of KL divergence minimization for event selection avoids the pitfalls of heuristic top- $k$ selection in nonlinear models.

Experimental Results
The method was evaluated on nine temporal graph datasets covering link prediction, node property prediction, and graph classification tasks (including Wikipedia, Reddit, Enron, UCI, and human action recognition datasets).

Performance: MemExplainer consistently outperformed state-of-the-art baselines (TGNNExplainer, TempME, GNNExplainer, PGExplainer) in terms of Fidelity (measured by $Fidelity_{KL}$ and $Fidelity_{prob}$ ) across all datasets.
Statistical Significance: A t-test between MemExplainer and the second-best baseline showed statistical significance in 77% of cases for $Fidelity_{KL}$ and 74% for $Fidelity_{prob}$ .
Case Studies: In human pose-based action classification, MemExplainer selected smaller, more focused subsets of edges that aligned with key biomechanical chains (e.g., hip-knee-ankle for running), whereas baselines often selected excessive, uninformative edges.
Efficiency: The method remains computationally feasible, with total running times under 6 seconds even with deep memory backtracking (depth 10) on large datasets.

Significance and Claims
The paper claims that by integrating memory backtracking with topological attribution, MemExplainer provides faithful explanations that reveal the critical role of the memory module in TGNs. The authors assert that their method enhances the trustworthiness of TGNs, which is essential for their safe deployment in high-stakes domains. The work highlights that ignoring the temporal evolution of node memories leads to inaccurate attributions, and their conservation-based approach offers a robust solution for understanding complex temporal dependencies. The authors modestly note a limitation regarding computational costs on very large graphs with deep memory backtracking, suggesting future work on pruning or depth limitation.