GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules

Abstract

Instance-level explanation of graph neural networks (G NN s) is a well-studied area. These explainers, however, only explain an instance (e.g., a graph) and fail to uncover the combinatorial reasoning learned by a G NN from the training data towards making its predictions. In this work, we introduce G RAPH T RAIL , the first end-to-end , post-hoc, global G NN explainer that translates the functioning of a black-box G NN model to a boolean formula over the (sub)graph-level concepts without relying on local explainers. G RAPH T RAIL is unique in automatically mining the discriminative subgraph-level concepts using Shapley values . Subsequently, the G NN predictions are mapped to a human-interpretable boolean formula over these concepts through symbolic regression . Extensive experiments across diverse datasets and G NN architectures demonstrate significant improvement over existing global explainers in mapping G NN predictions to faithful logical formulae. The robust and accurate performance of G RAPH T RAIL makes it invaluable for improving GNNs and facilitates adoption in domains with strict transparency requirements.