Explaining Graph Neural Networks on Evolving Graphs: A Differential Geometric Approach
Graph Neural Networks (GNNs) have become the state-of-the-art models for making predictions on complex network data, from social networks to biochemical structures. However, a significant gap remains in our ability to interpret these models when the underlying data changes. This paper introduces a novel framework for explaining how GNN predictions shift as a graph evolves over time. By modeling the change in predicted probability distributions as a smooth curve on a differential geometric manifold, the authors develop a convex optimization method—AxiomPath-Convex—that identifies the most influential structural changes with superior sparsity and faithfulness compared to existing static explainers.
What Problem Does This Paper Address?
Most research into GNN explainability focuses on static graphs, answering questions like: "Why did the model predict X for this specific node right now?" However, real-world graphs are inherently dynamic. When a graph changes—such as a new edge forming in a social network or a node being deleted—the GNN’s prediction might shift accordingly.
The core challenge lies in explaining this transition. Existing methods often treat graph evolution as a discrete jump or attempt to model it as a linear change. This is problematic because GNNs output probability distributions, which exist in a non-linear space. A simple linear explanation fails to capture the "curvature" of how a model's confidence shifts, leading to explanations that are either unfaithful to the model's internal logic or too complex for human interpretation.
Methods: A Differential Geometric Viewpoint
To bridge the gap between discrete graph changes and smooth distributional shifts, the authors propose a differential geometric viewpoint.
- Path-Based Coordinates: The framework uses the contributions of specific paths in the GNN's computation graph as a coordinate system. This allows any predicted distribution to be represented as a point in a high-dimensional embedding space.
- The Manifold: The authors recognize that these predicted distributions actually lie on a low-dimensional manifold (a curved surface) within that high-dimensional space. They utilize the Fisher Information Matrix from information geometry to define a "curved metric." This ensures that the distances between distributions accurately reflect the model's internal sensitivity to changes.
- AxiomPath-Convex: To explain a prediction change resulting from a graph evolving from $G_0$ to $G_1$, the framework models the evolution as a smooth curve on this manifold. The authors then formulate and solve a convex optimization problem to find a "simple" curve—one defined by a sparse set of computational paths—that best approximates the actual change in prediction. This guarantees an explanation that is both concise (sparse) and accurate (faithful).
Key Insights and Ideas
- Geometry is Non-Negotiable: The most significant takeaway is that treating probability shifts as linear (a "flat earth" view of statistics) leads to poor explanations. By respecting the curvature of the manifold, the authors can identify highly salient paths that linear methods miss.
- Axiomatic Attribution: Building on DeepLIFT (an attribution method originally designed for images), the framework ensures that the sum of the path contributions exactly equals the total change in the model's output. This property is known as "completeness" or "sum-to-delta."
- Sparsity via Optimization: Instead of simply ranking edges by their gradient, the convex optimization approach allows the system to select a small, cohesive "team" of paths that collectively explain the change, avoiding the redundancy of just picking top individual performers.
Key Results
The researchers evaluated their method across three major tasks (Node Classification, Link Prediction, and Graph Classification) using eight diverse datasets, simulating evolution by adding or removing edges.
The authors compared AxiomPath-Convex against several baselines, including Gradient-based methods, GNNExplainer, GNN-LRP, and DeepLIFT.
- Faithfulness: Measured by KL divergence (which quantifies how close the explanation's "approximated" graph is to the real one), the proposed AxiomPath-Convex method consistently achieved the lowest error across all datasets.
- Sparsity: In node classification tasks on datasets like YelpChi and Weibo, AxiomPath-Convex maintained high faithfulness even when restricted to a very small number of paths. It significantly outperformed GNNExplainer, which struggled to adapt to the evolving context.
- Intuition: Qualitative case studies on the MUTAG (molecular mutagenicity) dataset demonstrated that the method correctly identified the addition or destruction of chemical rings as the primary reason for shifts in mutagenicity predictions.
Limitations and Future Work
While highly effective, the approach has a few limitations:
- Computational Complexity: Although the optimization problem is convex (guaranteeing a unique solution), the number of paths in a very deep or dense GNN can grow rapidly. While the authors implemented speed-ups using shared multiplier matrices, extremely large-scale graphs may still pose computational challenges.
- Fixed Parameters: The current model assumes the GNN's weights ($\theta$) remain fixed while the graph evolves. In real-world scenarios, models are often retrained as graphs grow.
- Future Directions: The authors suggest exploring more complex geometric properties of the manifold to better understand the "global" behavior of GNNs across entire families of graphs, moving beyond just local transitions.
Summary updated