  Graph Neural Networks (GNNs) are effective for node classification in
graph-structured data, but they lack explainability, especially at the global
level. Current research mainly utilizes subgraphs of the input as local
explanations or generates new graphs as global explanations. However, these
graph-based methods are limited in their ability to explain classes with
multiple sufficient explanations. To provide more expressive explanations, we
propose utilizing class expressions (CEs) from the field of description logic
(DL). Our approach explains heterogeneous graphs with different types of nodes
using CEs in the EL description logic. To identify the best explanation among
multiple candidate explanations, we employ and compare two different scoring
functions: (1) For a given CE, we construct multiple graphs, have the GNN make
a prediction for each graph, and aggregate the predicted scores. (2) We score
the CE in terms of fidelity, i.e., we compare the predictions of the GNN to the
predictions by the CE on a separate validation set. Instead of subgraph-based
explanations, we offer CE-based explanations.
