A Differential Geometric View and Explainability of GNN on Evolving Graphs

Yazheng Liu, Xi Zhang, Sihong Xie

Abstract

Graphs are ubiquitous in social networks and biochemistry, where Graph Neural Networks (GNN) are the state-of-the-art models for prediction. Graphs can be evolving and it is vital to formally model and understand how a trained GNN responds to graph evolution. We propose a smooth parameterization of the GNN predicted distributions using axiomatic attribution, where the distributions are on a low-dimensional manifold within a high-dimensional embedding space. We exploit the differential geometric viewpoint to model distributional evolution as smooth curves on the manifold. We reparameterize families of curves on the manifold and design a convex optimization problem to find a unique curve that concisely approximates the distributional evolution for human interpretation. Extensive experiments on node classification, link prediction, and graph classification tasks with evolving graphs demonstrate the better sparsity, faithfulness, and intuitiveness of the proposed method over the state-of-the-art methods.

Introduction

Graph Neural Networks (GNNs) have revolutionized predictive modeling for structured data like social networks and molecular compounds. However, these models often operate as "black boxes," making it difficult to understand the logic behind their predictions. This challenge is amplified in real-world scenarios where graphs are dynamic—edges are added and nodes are removed continuously.

Existing explainability tools, such as GNNExplainer or DeepLIFT, are primarily designed for static snapshots. They can explain why a model makes a specific prediction at a single point in time, but they struggle to explain the transition between states. When a GNN changes its prediction due to graph evolution, we need to understand which specific structural changes drove that shift. This paper introduces a differential geometric framework to address this gap.

Modeling Evolution on a Probability Manifold

The core innovation of this work is treating the shift in GNN predictions as a continuous movement on a curved manifold. Because GNNs output probability distributions, their predictions do not live in a flat Euclidean space but on a low-dimensional manifold within a high-dimensional embedding space.

Conceptual framework of the manifold of GNN predicted distributions and differentiable evolution curves.

To bridge the gap between discrete graph changes and continuous probability shifts, the authors utilize:

  1. Path-based Coordinates: Using axiomatic attribution (DeepLIFT), they decompose predictions into contributions from specific computation paths. These serve as coordinates in the embedding space.
  2. Riemannian Metrics: They use the Fisher Information Matrix to define a metric that respects the manifold's curvature, acknowledging that small structural changes can lead to non-linear jumps in model confidence.
  3. AxiomPath-Convex: The authors formulate a convex optimization problem to find a "simple curve"—a sparse subset of computation paths—that most accurately approximates the evolution of the prediction from graph $G_0$ to $G_1$.

Experimental Evaluation

The researchers evaluated AxiomPath-Convex across diverse tasks and real-world datasets:

  • Node Classification: Fraud detection (YelpChi, YelpNYC) and rumor detection (Pheme, Weibo).
  • Link Prediction: Bitcoin trust networks (BC-OTC, BC-Alpha).
  • Graph Classification: Molecular biology (MUTAG).

Evolution was simulated by adding or removing edges based on timestamps or controlled perturbations. The primary metric for success was faithfulness, measured by the KL-divergence between the actual predicted distribution and the distribution reconstructed using only the explanatory paths.

Results: Faithfulness and Interpretability

Across all datasets, AxiomPath-Convex consistently outperformed state-of-the-art baselines like GNN-LRP and GNNExplainer. As shown in the performance plots, the proposed method achieves significantly lower KL-divergence ($KL^+$), indicating that the selected paths are much more faithful to the model's internal logic.

Faithfulness comparison (KL+ divergence) on the Pheme dataset under edge addition and removal.

Beyond faithfulness, the method excels in sparsity. It typically identifies fewer than 10 critical paths to explain a prediction change, making the results highly interpretable for humans. For instance, in molecular tasks, the method correctly pinpointed the addition or destruction of specific chemical rings as the primary driver for classification shifts.

Conclusion

By viewing GNN predictions through the lens of differential geometry, this work provides a robust framework for explaining model behavior on evolving graphs. While identifying computation paths in extremely dense networks remains a computational challenge, the use of convex optimization ensures that the found explanations are both unique and sparse. Future work will look into extending this framework to account for changes in model weights during retraining, further broadening the scope of GNN explainability.

Summary updated

Abstract

Graphs are ubiquitous in social networks and biochemistry, where Graph Neural Networks (GNN) are the state-of-the-art models for prediction. Graphs can be evolving and it is vital to formally model and understand how a trained GNN responds to graph evolution. We propose a smooth parameterization of the GNN predicted distributions using axiomatic attribution, where the distributions are on a low-dimensional manifold within a high-dimensional embedding space. We exploit the differential geometric viewpoint to model distributional evolution as smooth curves on the manifold. We reparameterize families of curves on the manifold and design a convex optimization problem to find a unique curve that concisely approximates the distributional evolution for human interpretation. Extensive experiments on node classification, link prediction, and graph classification tasks with evolving graphs demonstrate the better sparsity, faithfulness, and intuitiveness of the proposed method over the state-of-the-art methods.
BibTeX
@inproceedings{liu2023differential,
  author = {Yazheng Liu and Xi Zhang and Sihong Xie},
  title = {{A Differential Geometric View and Explainability of GNN on Evolving Graphs}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=lRdhvzMpVYV},
}
Figure