Beyond Spectral Graph Theory

An Explainability-Driven Approach to Analyzing the Stability of Graph Neural Networks to Topology Perturbations

Bachelor thesis (2024)

Authors

R. Arike Electrical Engineering, Mathematics and Computer Science

Contributors

E. Isufi (mentor)
Maosheng Yang (mentor)
M. Sabbaqi (mentor)
K.A. Hildebrandt Computer Graphics and Visualisation - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science
Explainable AI Graph Neural Networks Stability
More Info
expand_more

Published Date

26-06-2024

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Graph Neural Networks (GNNs) have emerged as a powerful tool for learning from relational data. The real-world graphs such models are trained on are susceptible to changes in their topology. A growing body of work in the field of GNNs' stability to topology perturbations is trying to characterise how models respond to those changes, providing valuable insights that have enhanced the robustness of GNNs to adversarial attacks. The past work in this field, however, has only approached stability analysis using spectral graph theory, which is not applicable to all kinds of GNN models. In this paper, we aim to extend the past work in GNN stability by proposing an algorithm for analysing the stability of GNNs with model-agnostic GNN explainability tools instead of the mathematical framework of spectral graph theory. We demonstrate that the outputs of explainability tools can encode useful insights into the stability of GNNs and present a case study on using those insights to analyse node removal, edge removal, and edge weight perturbations.