🤖 machine learning

Explaining Temporal Graph Predictions With Shapley Values

This paper introduces two novel model-agnostic explainers for Temporal Graph Neural Networks (TGNNs)—an event-level Shapley explainer and a feature-level Owen value-based explainer—that outperform existing methods and can identify flaws in model implementations.

Original authors: Lea-Marie Sussek, Stefan Heindorf

Published 2026-04-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Lea-Marie Sussek, Stefan Heindorf

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 are a detective trying to understand why a high-tech security system suddenly decided to sound an alarm. You know the system looks at a massive, constantly changing web of data—who walked through which door, at what exact millisecond, and what they were carrying.

The problem? The security system is a "Black Box." It gives you an answer (Alarm! or No Alarm!), but it won't tell you why. Was it because a specific person walked through a specific door at 3:00 AM? Or was it because of the heavy bag they were carrying?

This paper introduces two new "Digital Detectives" (called Explainers) that help us peek inside these complex, time-sensitive systems, which scientists call Temporal Graph Neural Networks (TGNNs).

The Problem: The "Moving Target"

Most AI tools are good at looking at static pictures (like a single photo of a crowd). But the world is more like a movie. In a "Temporal Graph," everything is moving: people are connecting, disconnecting, and moving through time. Existing tools for explaining these "movies" are either too slow, too complicated, or they only tell you that something happened, but not exactly what caused it.

The Solution: Two New Detectives

The researchers created two tools based on a mathematical concept called Shapley Values. Think of Shapley Values as a way to fairly divide a "bonus" among a team of players based on how much each person actually contributed to a win.

1. The Event Detective (The "Who and When" Specialist)

Imagine a basketball game. The team wins, and you want to know which specific plays (events) were most important.

How it works: This detective looks at the whole "movie" of data and assigns a score to every single interaction (an "event").
The Result: It tells you, "This specific interaction between Person A and Person B at 2:05 PM was the main reason the alarm went off." It can even tell you if an event helped prevent an alarm (a positive contribution) or triggered one (a negative contribution).

2. The Feature Detective (The "Deep Dive" Specialist)

Now, imagine the Event Detective tells you, "The interaction at 2:05 PM was important." You might say, "Okay, but why? Was it the person, the time, or what they were holding?"

How it works: This detective uses a more advanced math trick called Owen Values. It takes that one important event and breaks it down into even smaller pieces.
The Result: It provides a "zoom-in" view. It tells you, "The event was important, but specifically because of the timestamp and the weight of the object being carried, not the person themselves." It’s like moving from seeing a whole car to seeing the specific spark plug that caused the engine to roar.

The "Aha!" Moment: Catching a Glitch

The coolest part of this paper isn't just that they built these tools, but that they used them to catch a "liar" in a popular AI model.

They noticed a common AI model was making predictions that seemed too good to be true. By using their Feature Detective, they discovered the model was "cheating." It wasn't actually learning the patterns of the graph; it was accidentally picking up on a tiny mathematical glitch that allowed it to see the "absolute time" (like looking at a clock) instead of just the "relative time" (like seeing how much time passed between two events).

It’s like a student who passes a math test not because they understand algebra, but because they noticed the teacher always uses a blue pen for the correct answers. The researchers' tool caught the "blue pen" glitch!

Why does this matter?

In the real world, we use these "Temporal Graphs" for critical things:

Healthcare: Predicting how a disease spreads through a population over time.
Finance: Detecting fraudulent transactions in a sea of moving money.
Cybersecurity: Spotting a hacker moving through a network.

In these high-stakes areas, "Because the computer said so" isn't a good enough answer. We need to know why. These new detectives provide the "why," making AI more trustworthy, transparent, and easier to fix when it makes a mistake.

Technical Summary: Explaining Temporal Graph Predictions With Shapley Values

1. Problem Statement

Temporal Graph Neural Networks (TGNNs) have become the standard for modeling evolving graph structures (Continuous-Time Dynamic Graphs or CTDGs) by combining spatial and temporal information. However, these models function as "black boxes," making their decision-making processes difficult to interpret. This lack of transparency is a significant barrier in high-stakes domains like healthcare, finance, and cybersecurity.

Existing explainability methods for TGNNs face several limitations:

Static Explainers: Fail to capture temporal dynamics.
Discrete-Time Explainers: Often rely on additional trainable auxiliary models, making them slow, hyperparameter-sensitive, and dependent on specific architectures (e.g., requiring differentiability).
Lack of Granularity: Most current methods provide importance scores but do not quantify whether an event has a positive or negative impact, nor do they decompose an event into its constituent features (timing, features, or node roles).

2. Methodology

The authors propose two novel, model-agnostic, and lightweight explainers based on cooperative game theory.

A. Event-Level Explainer (Shapley Values)
This method treats each temporal event in a node's computational subgraph as a "player" in a cooperative game.

Mechanism: It uses the KernelSHAP algorithm to estimate the contribution of each event to the model's prediction.
Handling Disconnection: To prevent the graph from becoming disconnected when an event is "removed" (which would break message passing), the authors replace masked events with an "Average Event" ( $\bar{e}$ ). This average event uses the mean feature vector and a mean temporal delta, ensuring the structural integrity of the graph remains intact during the explanation process.
Output: It provides the magnitude and direction (positive or negative influence) of each event's contribution.

B. Feature-Level Explainer (Owen Values)
To achieve finer granularity, the authors extend the framework to decompose an event's Shapley value into its internal components (features, timestamp, and source node role).

Mechanism: Because features within an event are naturally grouped, the authors use Owen values, a generalization of Shapley values designed for hierarchical structures.
Hierarchical Efficiency: By using a "two-step" formulation, the Owen value of a feature is calculated as its contribution to the Shapley value of its parent event. This ensures mathematical consistency: the sum of all feature-level Owen values equals the total event-level Shapley value.
Computational Efficiency: To avoid the exponential complexity of calculating Owen values, the authors implement a Monte-Carlo sampling approach combined with KernelSHAP, reducing complexity to $O(k \cdot l)$ (where $k$ and $l$ are sample sizes).

3. Key Contributions

Model-Agnosticism: Unlike existing SOTA methods (like TempME), these explainers do not require training auxiliary networks or specific attention-based architectures.
Hierarchical Decomposition: The introduction of Owen values allows for a multi-level explanation (Event $\rightarrow$ Feature).
Directional Interpretability: Unlike importance-score-based methods, these explainers explicitly show if an event helps or hinders a prediction.
Diagnostic Capability: The explainers are capable of uncovering implementation flaws in existing TGNN architectures.

4. Results

The authors evaluated their methods on three real-world datasets (MOOC, Wikipedia, Reddit) and one synthetic dataset using metrics such as Fidelity, Deviation, and Graph Explanation Faithfulness (GEF).

Quantitative Performance: The proposed explainers outperformed state-of-the-art (SOTA) baselines (TGNN-Explainer and TempME) across most metrics. The Feature Explainer, in particular, showed superior performance in regression tasks.
Efficiency: While the Feature Explainer is slower than the Event Explainer due to increased sampling, it is still more efficient than TGNN-Explainer, which relies on expensive Monte-Carlo Tree Search (MCTS).
Discovery of Model Flaws: In a qualitative study using a synthetic dataset, the Feature Explainer successfully identified a "spurious signal" in a common TGAT implementation. It revealed that the model was incorrectly using "non-existent" events (zeroed-out features) to infer absolute timestamps via the softmax normalization of attention weights.

5. Significance

This work advances the field of Explainable AI (XAI) for temporal graphs by providing a mathematically rigorous and hierarchical framework. By moving away from auxiliary-model-dependent explainers, the authors provide a more robust and generalizable tool for developers to audit, debug, and trust Temporal Graph Neural Networks. The ability to detect "information leakage" (as seen in the TGAT case) highlights the practical utility of these explainers as diagnostic tools for model debugging.