# Utilizing Description Logics for Global Explanations of Heterogeneous Graph
Neural Networks

Dominik Köhler<EMAIL_ADDRESS>Paderborn UniversityPaderbornGermany
and  Stefan Heindorf<EMAIL_ADDRESS>Paderborn UniversityPaderbornGermany

###### Abstract.

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 $\mathcal{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.

##  1\. Introduction

Fraudulent assets in a financial network |  |
---|---|---
ABPCC$\exists$t$\exists$t$\exists$t$\exists$t |  ABPCC$\exists$t$\exists$t$\exists$t$\exists$t | AB $\sqcup$ PC$\exists_{\geq 2}$ t$\exists$t
Figure 1. In a financial network, where each node type is a specific account,
one asset account A might be labeled as fraudulent if it has transactions t
with at least two accounts of type business or personal (nodes of type B or
P), which both transact money to (possibly distinct) known criminal accounts
(nodes of type C). The two left-hand graphs refers to the CE
$\text{A}\sqcap\exists\text{t.}\left(\text{B}\sqcap\exists\text{t.C}\right)\sqcap\exists\text{t.}\left(\text{P}\sqcap\exists\text{t.C}\right)$
in $\mathcal{EL}$, which we implemented in our approach, whereas the class
expression (CE) on the right side refers to the more accurate CE
$\text{A}\exists_{\geq 2}\text{t. ((B $\sqcup$ P) $\exists$C) }$, an approach
we left for future work.

Node classification in graphs such as knowledge graphs (KGs), product graphs,
protein graphs, or citation graphs, is a critical task often addressed using
graph neural networks (GNNs) (Hu et al., 2020). However, understanding their
predictions, which is crucial for many applications, is challenging. Hence,
several explanation approaches such as GNNExplainer (Ying et al., 2019),
PGExplainer (Luo et al., 2020), SubgraphX (Yuan et al., 2021), XGNN (Yuan et
al., 2020), and GNNInterpreter (Wang and Shen, 2023) have been proposed, which
can be categorized into two types: _local_ and _global_ explanations. _Local_
explanations focus on why a particular node is classified in a certain way,
often represented by subgraphs highlighting crucial parts for that node’s
prediction. _Global_ explanations, on the other hand, elucidate why specific
labels are predicted. They do so in terms of graph patterns that describe the
set of nodes having a certain label. Typically, a graph pattern is a subgraph
of the metagraph, which encompasses node types and their connections.

Contemporary global explainers, however, do not offer sufficient
expressiveness. Whereas common families of GNNs can learn intricate patterns
expressed in the description logic $\mathcal{ALCQ}$ (Barceló et al., 2020)
supporting conjunctions, disjunctions, negations, and cardinality
restrictions, a subgraph of a metagraph is unable to capture disjunctions,
negations, and cardinality restrictions. Figure 1 shows an example. In this
example, we assume that the asset account $A$ is fraudulent if and only if it
transacts money to at least two different accounts (which can be business or
private accounts) that in turn send money to a criminal account $C$ (either
the same criminal account or a different one). The ideal class expression to
describe this situation is shown on the right. However, a single subgraph
explanation cannot describe this situation, as it can neither express
cardinality restrictions ($\exists_{\geq 2}$) nor disjunctions ($B\sqcup P$).

In response, we propose explaining GNNs based on $\mathcal{EL}$ (Baader et
al., 2003) class expressions (CEs) and in future work on $\mathcal{ALCQ}$,
with each node type as a named class and each edge type as an object property.
Then a CE can directly be used as a binary classifier. For example, given the
CE $A\exists_{\geq 2}\text{t. ((B $\sqcup$ P)$\exists$ C }$, we can check
whether the node fulfills this CE for each node in the graph.

Our approach works as follows: We randomly generate CEs via beam search and
select the CE maximizing our scoring function, making the explanation
independent of the dataset (Ramaswamy et al., 2023). We propose two scoring
functions: (1) We use the CE as a binary classifier and score its fidelity on
a validation set. (2) We choose the CE that maximizes the prediction of the
GNN. More precisely, given a CE $ce$ that aims to explain the prediction of
label $l$, we synthesize random graphs $G(ce)$ from the CE. At the same time,
for each graph $g\in G(ce)$, we synthesize a node $v_{g}$. Then we evaluate
the GNN for this graph, node, and label, denoted as $f_{l}(g,v_{g})$. To
retrieve the best explanatory CE $ce^{\prime}$, we average the GNN output for
all synthesized graphs, resulting in the formula:

$\displaystyle ce^{\prime}=\arg\max_{ce}[\text{aggr}_{g\in
G(ce)}f_{l}(g,v_{g})].$

Typical aggregation functions include _mean_ and _max_.

To evaluate our approach, we construct a heterogeneous version of the BA-
Shapes dataset (Ying et al., 2019) and as a first step, implement an explainer
for the description logic $\mathcal{EL}$ (Baader et al., 2003), which is a
subset of $\mathcal{ALCQ}$. We adapt metrics from graph-based explanations to
evaluate CE-based explanations. Our main contribution is a novel approach that
utilizes CEs to explain GNNs globally. Our code is publicly
available.111https://github.com/ds-jrg/xgnn-dl

##  2\. Related Work

We briefly review related works on GNNs, explanation approaches for GNNs, and
learning class expressions.

###  2.1. Graph Neural Networks

GNNs are employed for tasks such as node classification, graph classification,
and link prediction (Thomas et al., 2023; Wu et al., 2021; Ye et al., 2022).
They commonly utilize the message passing framework (Wang and Zhang, 2022;
Gilmer et al., 2017): In each layer, the GNN aggregates node features from
adjacent nodes for each node $v$. In a GNN with $n$ layers, the $n$-hop
environment of $v$ influences its embedding. Typically GNNs operate in the
_transductive_ setting, i.e., the same nodes are used for training and
testing, e.g., RGCN (Schlichtkrull et al., 2018). However, there is growing
support for the _inductive_ setting where training and testing nodes can
differ, e.g., GraphSAGE (Hamilton et al., 2017). In this paper, we focus on
inductive GNNs.

###  2.2. Explaining GNNs

Explaining GNNs has been widely studied in the literature, as summarized in
the surveys by Yuan et al. (2023) and Li et al. (2022). Evaluation frameworks
for the explanations have been proposed by Agarwal et al. (2023) and Longa et
al. (2022). Approaches can be divided as to whether they produce _local_ or
_global_ explanations.

_Local explanations_ , also known as instance-level explanations, explain the
prediction of a _single node_. The typical outputs are small, important
subgraphs of the original graph containing the node to be explained. The first
approach was GNNExplainer (Ying et al., 2019), which maximizes the mutual
information between a GNN’s prediction and the explanatory subgraph. PG-
Explainer (Luo et al., 2020) and GEM (Lin et al., 2021) synthesize explanatory
subgraphs via neural networks. SubgraphX (Yuan et al., 2021) searches for an
explanatory subgraph via Monte-Carlo Tree Search (MCTS). GStarX (Zhang et al.,
2022) employs a modified version of Shapley values, taking the graph structure
into account for selecting the collaborations. All of the aforementioned
_local_ explainers except for PGExplainer operate in the transductive setting,
i.e., predictions and explanations can only be computed for a graph seen
during training, but not for new, unseen graphs. Moreover, they can only
explain a single node prediction in contrast to global explainers.

_Global explanations_ , also known as model-level explanations, explain why
_multiple_ nodes are predicted to have a _certain label_. An explanation is
typically a subgraph of the metagraph. XGNN (Yuan et al., 2020) builds an
explanatory graph via reinforcement learning, optimizing the GNN score for the
created graph. Similarly, GNNInterpreter (Wang and Shen, 2023) searches for
graphs with a high GNN score, which are similar to the original dataset. PAGE
(Shin et al., 2022) clusters graphs to obtain a central graph that explains
all graphs in the cluster. Most closely related to our work, GLGExplainer
(Azzolin et al., 2023) generates explanations as Boolean combinations of
graphical graph patterns. The graphical graph patterns represent prototypical
explanations obtained from a _local_ explainer. To create _global_ predictions
with the _local_ explanations, the paper considers the similarity between
local graph patterns and graphs in an embedding space (via so-called concept
projections). As the embedding space is not amenable to humans, humans can
only use graphical explanations to produce approximate and intuitive
predictions on new data. In contrast, our CEs have clear and formal semantics
that humans can easily use to make precise, unambiguous predictions on new
data.

One other method that combines sub-symbolic and symbolic techniques to
generate global explanations is described by Himmelhuber et al. (2021a, b).
This method employs a local subgraph-based explainer, e.g. GNNExplainer (Ying
et al., 2019) to construct an ontology, which in turn is used by a class
expression learner to create CE-based global explanations. This method most
closely resembles our approach. However, we directly create global
explanations bypassing the need to create local explanations. Moreover, we
generate new graphs rather than relying on existing local explanations, which
allows us to recognize structures learned by the GNN that are not present in
the original dataset.

###  2.3. Learning Class Expressions

Description Logics (Baader et al., 2003) are a family of formal languages for
representing and reasoning about structured knowledge with varying degrees of
expressiveness. For example, the web ontology language (OWL) corresponds to
$\mathcal{SROIQ(D)}$, whereas our approach focuses on the lightweight DL
$\mathcal{EL}$ (see Section 3.1). Several approaches for learning CEs from
positive and negative examples in knowledge bases have been proposed. For
example, Evolearner (Heindorf et al., 2022) searches for CEs via evolutionary
algorithms, DRILL (Demir and Ngomo, 2023) searches for them via reinforcement
learning, CLIP (Kouagou et al., 2022) speeds up the search by predicting the
length of a CE, OntoSample (Baci and Heindorf, 2023) by sampling the ontology,
and NCES (Kouagou et al., 2023a, b) as well as ROCES (Kouagou et al., 2024)
directly synthesize CEs via set transformers. However, none of the approaches
have been used for explaining GNNs.

##  3\. Approach

After a brief introduction of preliminaries, we describe our search algorithm.

###  3.1. Preliminaries

Our goal is to explain GNNs trained on heterogeneous graphs that allow
multiple node and edge types (Shi et al., 2022; Wang et al., 2023).

###### Definition 3.1.

A heterogeneous graph $G$ is formally defined as a tuple
$G:=(V,E,T_{V},T_{E},N_{V},N_{E},\rho,\phi_{V},\phi_{E})$, where

  * •

$V$ is the set of nodes,

  * •

$E$ is the set of edges with $V\cap E\neq\emptyset$,

  * •

$T_{V}$ is the set of node types,

  * •

$T_{E}$ is the set of edge types,

  * •

$\rho:E\rightarrow V\times V$ is a total function mapping each edge to its
pair of nodes,

  * •

$\phi_{V}:V\rightarrow T_{V}$ is a total function mapping each node to its
type,

  * •

$\phi_{E}:E\rightarrow T_{E}$ is a total function mapping each edge to its
type.

  * •

We assume that each node type and edge type has a unique name, denoted by
$N_{V}$ and $N_{E}$, respectively.

The definition corresponds to a typed multi-graph, where each node and each
edge has a single type and there can be multiple edges between the same pair
of nodes.

####  3.1.1. Description logic

In description logics, _individuals_ are instances of named classes and
_links_ between individuals are instances of properties. In the terminology of
heterogeneous graphs, _nodes_ are instances of _node types_ and _edges_ are
instances of _edge types_.

Table 1. Syntax and semantics of $\mathcal{EL}$.
$\mathcal{I}=(\Delta^{I},\cdot^{\mathcal{I}})$ is an interpretation where
$\Delta^{\mathcal{I}}$ is its domain and $\cdot^{\mathcal{I}}$ is the
interpretation function.

Syntax | Construct | Semantics
---|---|---
$r$ | property | $r^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$
$C,D$ | classes |  $C^{\mathcal{I}}\subseteq{\Delta^{\mathcal{I}}}$, $D^{\mathcal{I}}\subseteq{\Delta^{\mathcal{I}}}$
$C\sqcap D$ | intersection | $C^{\mathcal{I}}\cap D^{\mathcal{I}}$
$\exists\ r.C$ | existential restriction | $\\{a^{\mathcal{I}}\in\Delta^{\mathcal{I}}|\ \exists~{}b^{\mathcal{I}}\in C^{\mathcal{I}},(a^{\mathcal{I}},b^{\mathcal{I}})\in r^{\mathcal{I}}\\}$

We define the syntax and semantics of class expressions over heterogeneous
graphs as shown in Table 1.

##### Syntax

Each named class $A,B\in N_{V}$ corresponds to a node type and each property
$r\in N_{E}$ corresponds to an edge type. A complex class expression $C$ can
be built from basic constructs: If $A$ is a named class, then $A$ is a class
expression; If $C,D$ are class expressions and $r$ is a property, then both
$C\sqcap D$ as well as $\exists r.C$ are class expressions.

##### Semantics

Given a (complex) class expression $C$, we want to define all nodes
$C^{\mathcal{I}}$ that fulfill this class expression. If $C$ is a named class,
its instances $C^{\mathcal{I}}$ is the set of nodes with the node type name
$C$. If $C$ is a complex class expression, its instances $C^{\mathcal{I}}$ can
be obtained by recursively applying the semantics of its constructs. This is
similar to a retrieval operator (Lehmann, 2010), but we will call the mapping
a homomorphism. A node $v$ in a graph fulfills a CE if a homomorphism from the
CE to the graph exists, where the CE’s root class is mapped onto the node $v$.

In an intersection $A\sqcap B$, $A$ and $B$ are called operands; in an
existential restriction $\exists r.B$, $B$ is referred to as filler and $r$ to
the property. When it is clear from the context, we may use the terms named
class, class, node type, and node type name; and also property, edge type, and
edge type name interchangeably. Our definition allows intersections and
existential restrictions, resembling the description logic $\mathcal{EL}$
(Baader et al., 2003).

###  3.2. The Search Algorithm

Figure 2 gives an overview of our approach illustrating our search for the
best explanatory class expression, for the predictions of a given GNN. We do
so via beam search: Initially, we randomly generate class expressions. To
evaluate the suitability of a class expression, we randomly generate graphs
with a node fulfilling the class expression and score the graphs and thus the
CE via the trained GNN. In the next iteration, we continue with the best CEs
found and their mutations.

CEscreate graphs from CEsscore graphsselect best CEsmutate CE Figure 2. An
overview of our approach: We start with class expressions (CEs), and score
them individually by using the GNN on graphs that have a node fulfilling the
CE. For the next iteration, we take (1) the best results and (2) mutated
versions of the best results.

##### Beam search

Algorithm 1 shows the pseudocode of our beam search. As parameters, it takes
the number of iterations $n$, the beam width $k$, the set of all available
$classes$, and the $class$ to be explained. We generate CEs of (increasing)
length for $n$ iterations: Initially, we create $k$ CEs (line 4). In each
iteration, for each candidate, we add a mutation of this candidate (lines
7–10). This is done by adding another CE of the form $\exists r.CLASS$. From
the resulting $2k$ candidates, we again choose the best $k$ candidates by a
scoring function for the next iteration (lines 12-13).

In the following, we presume that all edges have the same type, but the
approach is extendable to datasets with various edge types.

Algorithm 1 Beam Search

1:procedure BeamSearch($n$, $k$, $classes$, $class$)

2: $candidates\leftarrow$ EmptyList()

3: for $1\leq i\leq k$ do

4: $candidates$.append(RandomCE($classes,class$))

5: end for

6: for $1\leq i\leq n$ do

7: for $ce$ in $candidates$ do

8: $ce_{new}\leftarrow\textsc{MutateCE}(ce,classes)$

9: $ce_{new}$.score $\leftarrow$ ScoreCE($ce_{new},class$)

10: $candidates$.append($ce_{new}$)

11: end for

12: $\triangleright$ Choose the best $k$ CEs from $candidates$:

13: $candidates\leftarrow$Sort$(candidates,score)[:k]$

14: end for

15: return $candidates$

16:end procedure

##### Create random CE

For creating a random CE (line 4 of Algorithm 1, we are given the $class$ to
explain and all available $classes$. We uniformly randomly pick a class
$class_{new}$ from $classes$ and create the CE $class\sqcap\exists
r.class_{new}$. For example, with $class=A$, and $classes=\\{A,B,C\\}$, we
might randomly create the CE $A\sqcap\exists r.B$.

for tree=s sep=10mm, inner sep=1, l=1 [ $\sqcap$, name=root, tikz=[draw=red,
thick, rounded corners, fit=(), inner xsep=5pt, inner ysep=5pt] ; [$A$]
[$\exists r$ [$B$] ] ]

for tree=s sep=10mm, inner sep=1, l=1 [ $\sqcap$, name=root, tikz=[draw=red,
thick, rounded corners, fit=() (newNode), inner xsep=4.5pt, inner ysep=4.5pt]
; [$A$] [$\exists r$ [$C$, name=newNode]] [$\exists r$ [$B$] ] ]

for tree=s sep=10mm, inner sep=1, l=1 [ $\sqcap$ [$A$] [$\exists r$,
name=start [$B$, name=end, tikz=[draw=red, thick, rounded corners, fit=(),
inner xsep=5pt, inner ysep=5pt] ; ] ] ] ]

for tree=s sep=10mm, inner sep=1, l=1 [$\sqcap$ [$A$] [$\exists r$ [$\sqcap$,
, name=start, tikz=[draw=red, thick, rounded corners, fit=() (endB) (endC),
inner xsep=5pt, inner ysep=5pt] ; [$\exists r$ [$C$, name=endC]] [$B$,
name=endB] ] ] ]

Figure 3. Two possibilities for mutating the CE A $\sqcap\hskip
1.0pt\exists$r. B.

Class Expression |  Graphs
---|---
for tree=s sep=10mm, inner sep=1, l=1 [$\sqcap$ [$A$] [$\exists r$ [$\sqcap$ [$B$] [$\exists r$ [$\sqcap$ [$B$] [$\exists r$ [$A$] ] ] ] ] ] ] |  ABBrrrABBArrr

Figure 4. Different graphs for the CE
$\text{A}\sqcap\exists\text{r.}(\text{B}\sqcap\exists\text{r}.(\text{B}\sqcap\exists\text{r.
A}))$.

##### Mutate CE

The mutation of CEs (line 8 of Algorithm 1) is illustrated in Figure 3 and
Algorithm 2. The mutation function receives a CE $ce$ and a set of available
$classes$. Like above, we create an expression $ce_{new}=\exists
r.class_{new}$ where $class_{new}$ is chosen uniformly at random from
$classes$ (lines 2–3 in Algorithm 2). We add this expression $ce_{new}$ either
to an existing intersection or an existing class, referred to as $ce_{old}$
(each with a probability of 50%). In the former case, we uniformly randomly
choose an intersection among all intersections $ce.intersections$ that appear
in $ce$ and extend the intersection $ce_{old}$ with an additional operand
(Figure 3 top, Algorithm 2 lines 6 and 10). In the latter case, we uniformly
randomly choose a class $ce_{old}$ from the classes $ce.classes$ in the CE,
and replace the class with a new intersection with the two operands
$ce_{new}=\exists r.class_{new}$ and $ce_{old}$ (Figure 3 bottom, Algorithm 2
lines 8 and 10).

Algorithm 2 Mutate a CE by adding a Class

1:procedure MutateCE($ce,classes$)

2: $class_{new}\leftarrow$ Random($classes$)

3: $ce_{new}\leftarrow\exists r.class_{new}$

4: $place_{mutate}\leftarrow$ Random({“intersection”, “class”})

5: if $place_{mutate}=$ “intersection” then

6: $ce_{old}\leftarrow$ $ce$.Random($ce.intersections$)

7: else if $place_{mutate}=$ “class” then

8: $ce_{old}\leftarrow$ $ce$.Random($ce.classes$)

9: end if

10: $ce\leftarrow$ Intersection($ce_{old},ce_{new}$)

11: return $ce$

12:end procedure

Algorithm 3 Create Graph from CE

1:procedure CreateGraph(ce, graph=EmptyGraph())

2: $node\leftarrow None$

3: if TypeOf($ce$) is “class” then

4: $node\leftarrow$ CreateNodeOfType($ce$)

5: $graph$.AddNode($node$)

6: else if TypeOf($ce$) is “intersection” then

7: $class\leftarrow\textsc{FindClass}(ce)$

8: $node\leftarrow$ CreateNodeOfType($class$)

9: $graph$.AddNode($node$)

10: for $op$ in $ce$ except for $op=class$ do

11: $ograph,onode\leftarrow$ CreateGraph($op,graph$)

12: $graph$.MergeWithGraphOnNodes( ograph, onode, node)

13: end for

14: else if TypeOf($ce$) is “existential restriction” then

15: $fnode\leftarrow None$

16: if RandomChoice() then

17: $fnode\leftarrow graph$.FindNode($ce.filler$)

18: end if

19: if $fnode$ is None then

20: $fgraph,fnode\leftarrow\textsc{CreateGraph}($ $ce.filler,graph)$

21: $graph$.AddGraph($fgraph$)

22: end if

23: $node\leftarrow$ CreateNodeWithoutType()

24: $graph$.AddNode($node$)

25: $graph$.AddEdge($node$, $ce.property$, $fnode$)

26: end if

27: return $graph$, $node$

28:end procedure

Algorithm 4 Scoring a CE

1:procedure ScoreCE($ce,\lambda,GNN$, Aggr)

2: $graphs\leftarrow EmptyList()$

3: for $1\dots max\\_number$ do

4: $graph\leftarrow$ CreateGraphs($ce$)

5: $v_{r}\leftarrow$ RootNode($ce$)

6: $gnn\\_outs$.append($GNN(graph,v_{r})$)

7: end for

8: $score\leftarrow$ Aggr($gnn\\_outs$) + $\lambda*$ Length($ce$)

9: $gnn\\_out\leftarrow GNN($

10:end procedure

##### Score CE

We propose maximizing the GNN output of graphs that are valid for a CE to
score the CE. Towards this goal, we create graphs fulfilled by the CE and
subsequently assess the GNN’s performance on these graphs, as shown in
Algorithm 4. First, we explain the graph generation, then the scoring
function.

We use Algorithm 3 to create a graph from a CE recursively. This takes a CE
and a graph as parameters. The graph is initialized as an empty graph when
calling the function for the first time. In subsequent recursive calls, it
contains the graph that has been constructed so far. The variable $node$ keeps
track of the node that corresponds to the current CE’s root class. In summary,
Algorithm 3 works as follows:

  * •

If the CE consists solely of a named class (lines 3 to 5), then a graph with a
single node of type $ce$ is created.

  * •

If the CE is of type “intersection”, e.g., the root element of the CE’s parse
tree is an intersection (lines 6 to 12), then the unique root class of $ce$ is
determined through the function FindClass (line 7).222This is always possible
due to how our CE creation and mutation works (see above). The construction
ensures that each intersection has exactly one named class as an operand and
an arbitrary number of existential restrictions. For example, our construction
would create CEs like $A$, $A\sqcap\exists r.B$, $A\sqcap\exists
r.B\sqcap\exists r.C$, but never $A\sqcap B$. The result of
FindClass($A\sqcap\exists r.B$) would be $A$. Then a graph for each of its
operands is created recursively (line 11) and is merged with the current graph
(line 12) on their respective root nodes (root node $node$ of the current
graph $graph$, and root node $onode$ of the operator graph $ograph$).

  * •

If the CE is an existential restriction (lines 13 to 22), we decide randomly
with a probability of 50% whether we attempt to reuse parts of the existing
graph (line 16). If this is feasible, we identify a node for which the
filler’s CE is valid (line 17). Otherwise, we recursively create a new graph
for the filler (line 20) and add it to the current graph (line 21). All that
remains is to connect the filler graph to the current graph (lines 23–25).

Figure 4 gives an example by showing two possible graphs (right) generated
from the CE (left). In the first example (top right), two different nodes of
type A are created; in the second example (bottom right), a single node of
type A is reused.

In the scoring function, we evaluate how well a given CE $ce$ explains the
GNN’s prediction of label $l$ by computing a score for the CE as follows:

  1. (1)

In each iteration, we generate a graph such that the CE $ce$ holds for the
graph in the previously defined root node $v_{r}$, following the
aforementioned procedure in Algorithm 3 (line 4). Let $G(ce)$ be the set of
generated graphs.

  2. (2)

For each graph $g\in G(C)$ we calculate the GNN prediction $f(g,v_{g})$ (line
5) and aggregate these GNN predictions, using any aggregation function, like
max or mean (lines 7 and 8).

Thus, our provisional scoring function $\gamma$ of the CE $ce$ is

$\displaystyle\gamma(ce)=\text{aggr}_{g\in G(ce)}f_{l}(g,v_{g}).$

The number of classes in one CE corresponds to its complexity. Hence, we
propose regularizing the CE-scoring $\gamma$ by subtracting the number of
classes in the CE, multiplied by the hyperparameter $\lambda$ (line 6),
similarly to Heindorf et al. (2022):

$\displaystyle\text{score}(ce)=\gamma(ce)-\lambda\cdot\text{length}(ce).$

In Section 5, we discuss further methods for regularization.

###  3.3. Baseline

As a baseline, we modify the approach by replacing the scoring function with a
new objective: maximizing fidelity on a separate validation dataset.
Consequently, we can omit the creation of graphs for each CE, resulting in
explanations more closely tailored to the dataset on which the GNN is
utilized.

##  4\. Evaluation

We measured the quality of the generated explanations on a synthetic dataset
using the metrics accuracy and fidelity.

Table 2. Three class expressions (CEs) as example results, sorted by their GNN
score (top). For comparison, three CEs are retrieved by beam search maximizing
fidelity on a separate validation dataset (middle), and three possible ground-
truth CEs are given (bottom). For each CE, we evaluate fidelity, explanation
accuracy (EA) and the maximal GNN output for graphs created by Algorithm 3.
Fidelity was evaluated on a separate test dataset. We see, that each method
reaches its goal optimizing GNN-output and fidelty, respectively.

Results on Hetero-BA-Shapes, for a GNN trained on 2 layers CE scored by GNN
output Class Expressions Fidelity EA GNN $\text{1}^{\text{st}}$ CE
$B\sqcap\exists\text{to.}\left(\text{D}\sqcap\exists\text{to.}\left(C\sqcap\exists\text{to.A}\sqcap\exists\text{to.B}\right)\right)\sqcap\exists\text{to.C}\sqcap\exists\text{to.A}\sqcap\exists\text{to.D}\sqcap\exists\text{to.B}\sqcap\exists\text{to.A}\sqcap\exists\text{to.B}\sqcap\exists\text{to.D}$
$0.50$ $0.45$ $12.52$ $\text{2}^{\text{nd}}$ CE
$B\sqcap\exists\text{to.}\left(\text{D}\sqcap\exists\text{to.B}\sqcap\exists\text{to.}\left(\text{C}\sqcap\exists\text{to.A}\right)\right)\sqcap\exists\text{to.C}\sqcap\exists\text{to.A}\sqcap\exists\text{to.D}\sqcap\exists\text{to.B}\sqcap\exists\text{to.C}\sqcap\exists\text{to.B}$
$0.50$ $0.63$ $12.39$ $\text{3}^{\text{rd}}$ CE
$B\sqcap\exists\text{to.}\left(\text{D}\sqcap\exists\text{to.B}\sqcap\exists\text{to.}\left(C\sqcap\exists\text{to.A}\right)\right)\sqcap\exists\text{to.C}\sqcap\exists\text{to.A}\sqcap\exists\text{to.D}\sqcap\exists\text{to.B}\sqcap\exists\text{to.A}\sqcap\exists\text{to.B}\sqcap\exists\text{to.C}$
$0.51$ $0.63$ $11.89$ CE scored by fidelity $\text{1}^{\text{st}}$ CE
$\text{B}\sqcap\exists\text{to.}\left(\text{C}\sqcap\exists\text{to.}\left(\text{B}\sqcap\exists\text{to.B}\right)\sqcap\exists\text{to.C}\right)\sqcap\exists\text{to.A}$
0.97 1.00 $0.40$ $\text{2}^{\text{nd}}$ CE
$\text{B}\sqcap\exists\text{to.}\left(\text{C}\sqcap\exists\text{to.}\left(\text{B}\sqcap\exists\text{to.B}\right)\sqcap\exists\text{to.C}\right)\sqcap\exists\text{to.A}\sqcap\exists\text{to.B}$
$0.97$ $1.00$ $0.40$ $\text{3}^{\text{rd}}$ CE
$\text{B}\exists\text{to.}\sqcap\left(\text{C}\sqcap\left(\text{C}\sqcap\exists\text{to.C}\sqcap\exists\text{to.}\left(\text{C}\sqcap\exists\text{to.B}\right)\right)\sqcap\exists\text{to.A}\sqcap\exists\text{to.B}\sqcap\exists\text{to.B}\sqcap\exists\text{to.C}\right)$
$0.97$ $1.00$ $2.67$ Ground-truth CEs of increasing length
$\text{1}^{\text{st}}$ CE
$B\sqcap\exists\text{to.}\left(\text{B}\sqcap\exists\text{to.C}\right)\sqcap\exists\text{to.A}\sqcap\exists\text{to.C}$
$0.93$ $1.00$ $-1.91$ $\text{2}^{\text{nd}}$ CE
$B\sqcap\exists\text{to.}\left(\text{C}\sqcap\exists\text{to.C}\right)\sqcap\exists\text{to.}\left(\text{B}\sqcap\exists\text{to.C}\right)\sqcap\exists\text{to.}\left(\text{A}\sqcap\exists\text{to.B}\right)$
$0.96$ $1.00$ $1.67$ $\text{3}^{\text{rd}}$ CE
$B\sqcap\exists\text{to.}\left(\text{A}\sqcap\exists\text{to.B}\right)\sqcap\exists\text{to.}\left(\text{B}\sqcap\exists\text{to.A}\sqcap\exists\text{to.C}\right)\sqcap\exists\text{to.}\left(\text{C}\sqcap\exists\text{to.C}\right)$
$0.96$ $1.00$ $2.35$ 3 Graphs for: CEs scored by GNN output
$\text{1}^{\text{st}}$ $\text{2}^{\text{nd}}$ $\text{3}^{\text{rd}}$ CEs
scored by fidelity Graph for GT CEs Legend

###  4.1. Evaluation Setup

##### The Hetero-BA-Shapes Dataset

We adjusted the BA-Shapes dataset (Ying et al., 2019) to create a
heterogeneous version. As in the BA-Shapes dataset, we first created a random
Barabási-Albert Graph graph with $10\,000$ nodes, where each node is connected
iteratively to the graph via $3$ edges; and then connected $1000$ house-motifs
via a single edge to it. We introduced heterogeneity to the graph by assigning
each edge to be of the named edge type to and the nodes to different types
based on their position: Each node at the top of the house motif was assigned
to type $A$, the nodes in the middle of the house to type $B$, and the nodes
at the bottom of the house to type $C$. Each node in the rest of the graph was
assigned to type $A$, $B$, or $C$ by each $20\%$ probability, and of type $D$
by $40\%$ probability. Additionally, all nodes of type $B$ got the label $1$
if they are in a house motif, and $0$ otherwise. This results in $50\%$ of the
nodes of type $B$ holding label $1$. At last, all nodes have one feature which
was set to $1$.

000010000totototototototototo

Figure 5. One house motif (left) from our Hetero-BA-Shapes dataset that is
connected to a random Barabasi-Albert Graph (right). The colors indicate the
node type (red indicates type A, blue type B, orange type C, and green type
D). The numbers in the nodes indicate the label. The red node on the right
does not receive the label 1 because it is not part of a house motif.

##### Training, Validation, and Test Sets

For training and validation of the GNN, we used one dataset with $15\,000$
nodes, consisting of $10\,000$ nodes not in a motif. For testing, we created a
second dataset with $15\,000$ nodes. For creating explanations using the
approach to maximize fidelity, we used one separate dataset of $15\,000$ nodes
for evaluating fidelity.

##### Ground-truth CEs

We compare the CEs retrieved from our approach and our baseline to different
possible ground-truth CEs. We define a CE to be a ground-truth CE to the house
motif if a surjective homomorphism from the CE to the house motif exists.
Three different ground-truth CEs are used, as shown in Table 2: The first CE
is defined as the shortest possible while still being a ground-truth CE. The
second CE contains six object properties corresponding to the six edges in the
house motif. The third CE corresponds to the computation tree of a message
passing GNN with two layers.

##### GNN Model

We trained a 2-layer GNN on the Hetero-BA-Shapes dataset using one GraphSAGE
layer (Hamilton et al., 2017) per (node type, edge, node type)-triple and per
layer. The GNN was trained for 1000 epochs with a training, validation, and
test split of 40%, 24%, 36%, respectively, using Adam-optimizer with a
learning rate of $0.01$, reaching an accuracy of $0.97\pm 0.1$ (single
standard deviation) on the test set.

##### Hyperparameters for Explainer

We performed beam search as in Algorithm 1, using $k=10\,000$ as beam width
for $n=10$ iterations. For each CE, we created $m=100$ graphs for scoring. For
regularization, we used $\lambda=0.5$. We chose the hyperparameter by
iterative refinement, where minor modifications did not significantly alter
the results.

##### Implementation

For our experiments, we used Python 3.8, with PyTorch 1.12, and PyTorch
Geometric 2.01 for heterogeneous graphs, and the Ontolearn library for
handling class expressions.333https://pypi.org/project/ontolearn/

###  4.2. Evaluation Metrics

Our approach differs from most current approaches (Longa et al., 2022), as we
use CEs instead of subgraphs (Yuan et al., 2021) or motifs (Perotti et al.,
2023) to explain the predictions. This necessitates slight modifications of
existing evaluation metrics (Faber et al., 2021; Amara et al., 2022), which we
describe in the following.

##### Explanation Accuracy

We compute the explanation accuracy by mapping the CE to the ground-truth
motif (Ying et al., 2019; Faber et al., 2021), which, in the case of the
Hetero-BA-Shapes dataset, is the house motif from Figure 5. For the
computation, we extend the motif by one abstract node of type abstract, which
is connected to every node in the motif via every available edge type. We then
map the CE to the motif by a homomorphism, starting with the CEs’ root class.
For node classification tasks, this root class is the node type we want to
explain (in this paper $B$). Every class of the CE that cannot be mapped to a
node in the motif is mapped to the abstract node. We count the true positives
as all nodes in the motif a class was mapped on, the false negatives as the
remaining nodes in the motif, and the false positives as the number of classes
mapped on the abstract node. We don’t use true negatives, as we only have
positives in the motifs. If there are several possibilities for the mapping,
we take the one leading to the highest accuracy:

$\displaystyle\text{accuracy}=\frac{\text{tp}}{\text{tp}+\text{fp}+\text{fn}}.$

For example, the CE $\text{B}\sqcap\exists\text{to.A}$ has an accuracy of
$0.4$, because it has two true positives (A and B) as both classes A and B
from the CE are in the motif and each class can at most correspond to one tp,
no false positives, and three false negatives ($C,C$, and $B$). As a more
complex example, the accuracy of
$\text{B}\sqcap\exists\text{to.}\left(\text{A}\sqcap\exists\text{to.C}\right)$
would be $\frac{2}{2+1+3}$, as there is no connection between nodes of type A
and type C, leading to one false positive.

##### Fidelity

Fidelity refers to the degree to which the explanation accurately reflects the
model’s behavior, i.e. whether it is possible to predict the GNNs’ predictions
from the explanation. For calculating a CE’s fidelity, we use CEs as binary
classifiers, labeling every node that fulfills the CE with the label we want
to explain and assigning all other nodes to another label (assuming binary
classification). Then we use a test dataset, unseen by the GNN during
training, to approximate fidelity as the similarity of the GNN and the CE,
with $N$ being the number of test samples:

$\text{Fidelity}=\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}(y_{GNN}=y_{CE}).$

###  4.3. Experimental Results

We observe the results in Table 2, for CEs and their created graphs using
Algorithm 3. We compare the results of our approach to the baseline approach,
which maximizes fidelity, and three ground truth CEs of increasing length. We
see, that the GNN scores highest on graphs, that don’t contain the ground-
truth house motif and even contain the (node type, edge type, node
type)-triples, which aren’t present in the house motif, as A, to, C and D, to,
D. Removing these edges even decreases the GNN output on the graphs, leading
to the conclusion that the GNN learned spurious correlations, as visualized in
Table 3. The existence of spurious correlations on homogeneous motif datasets
was additionally observed by (Fan et al., 2024). Furthermore, we notice that
maximizing fidelity leads to CEs which can also serve as ground-truth CEs,
hence correctly explaining the GNN. This suggests learning explanations by
maximizing fidelity leads to better explanations, in contrast to maximizing
the GNN score, as currently done in the literature for global explanations, as
in (Yuan et al., 2020; Wang and Shen, 2023). In the pipeline provided by
(Azzolin et al., 2023), both maximizing the GNN output and maximizing fidelity
are used. In summary, the results show the ability to use our approach to
detect spurious correlations and to explain GNNs with high fidelity.

Table 3. The GNN scores with and without certain edge types are presented for the top-scoring graph created from the top-scoring CE in Table 2. We expect the GNN score to decrease when edges from the motif are removed and to increase otherwise. However, we do not observe this increase in the GNN score, suggesting that the GNN has learned spurious correlations. Edge-type | Edge in motif | GNN Prediction
---|---|---
Original graph |  | 12.52
w/o edges A–A | X | $12.52$
w/o edges A–B | ✓ | $7.75$
w/o edges A–C | X | $11.67$
w/o edges A–D | X | $10.97$
w/o edges B–B | ✓ | $8.08$
w/o edges B–C | ✓ | $9.91$
w/o edges B–D | X | $5.87$
w/o edges C–C | ✓ | $12.52$
w/o edges C–D | X | $12.28$
w/o edges D–D | X | $12.12$

##  5\. Discussion

##### Detecting spurious correlation

With our method, we can detect (node type, edge type, node type) triples the
GNN focuses on, making it easier to debug GNNs.

##### Heterogeneous vs. homogeneous datasets

By delivering more expressive explanations, especially for datasets with
different node and edge types, we encourage the use of heterogeneous GNNs
instead of homogeneous ones, resulting in more expressive explanations while
still achieving similar results (Wang et al., 2023). The approach can also be
applied to homogeneous datasets where categorical node features can serve as
classes instead of node types.

##### Maximizing GNN-score vs. maximizing fidelity

Our results indicate that learning explanations using metrics as fidelity
creates explanations for the general behavior of the model while maximizing
the GNN output identifies outliers. This is because fidelity considers every
node classified under a desired label by the GNN, providing a comprehensive
view, whereas maximizing GNN output focuses only on a potentially non-
representative subset.

##### Model-specific vs. model-agnostic

Our approach is model-agnostic, as it treats the GNN as a black box. This has
the advantage that our approach can generate explanations for all
architectures of GNNs.

##### Node classification vs. graph classification

Although we focus on node classification, the approach is extendable to graph
classification. In this case, we learn a CE by scoring the GNN on the created
graphs. If any node in the graph fulfills the CE, the entire graph is
classified accordingly, yielding the corresponding label.

##### Runtime

The algorithm runtime is primarily determined by the graph-creation step
during scoring, which takes significantly longer for longer CEs. For GNNs with
more layers, the explanations become longer, and larger graphs must be created
for scoring as additional layers make the GNN take a larger neighborhood into
account. Therefore, the algorithm scales to the complexity of the GNN.

##### Applications

This approach may be utilized for explaining molecule datasets, as promoted in
Figure 6, helping researchers gain new insights into the data by revealing
previously undetected structures. Furthermore, our method can be used for
debugging a trained GNN, by finding GNN peaks outside the training data and
detecting spurious correlations as discussed in Section 4.3, leading to more
explainable and transparent GNNs.

##### Regularization

The maximal node degree can be regularized to create less dense explanations
or explanations more aligned with the training data. Additionally, regulating
the graph distance avoids long chains of explanations.

##### Features

We propose introducing features as data properties into our explanation by
leveraging techniques from explainable AI on tabular data, especially decision
trees.

##### Comparison with other explanation approaches

In future work, it might be interesting to compare our explanations to further
approaches creating rule-based explanations, like EvoLearner (Heindorf et al.,
2022), GLGExplainer (Azzolin et al., 2023) or the approach of Himmelhuber et
al. (Himmelhuber et al., 2021a). Additionally, a comparison to graph-based
explanations like the motifs generated by Perotti et al. (Perotti et al.,
2023) or the heterogeneous implementations of Subgraphx (Yuan et al.,
2021)444https://docs.dgl.ai/en/1.1.x/generated/dgl.nn.pytorch.explain.HeteroSubgraphX.html,
PGExplainer (Luo et al., 2020)
555https://docs.dgl.ai/en/latest/generated/dgl.nn.pytorch.explain.HeteroPGExplainer.html
and GNNExplainer (Ying et al.,
2019)666https://docs.dgl.ai/en/1.1.x/generated/dgl.nn.pytorch.explain.HeteroGNNExplainer.html
could lead to interesting discoveries.

##### ALCQ

In our forthcoming research, we aim to refine our methodology by incorporating
the description logic $\mathcal{ALCQ}$, with a specific focus on unions and
cardinality constraints. Figure 6 illustrates how unions can enhance the
expressivity of explanations. A challenge associated with using unions is
ensuring that no information is duplicated across two separate operators
within a single union. To adapt our graph creation process, we plan to limit
edge connections in the graph such that they only connect with newly created
nodes. This adjustment aligns with the GNN’s computation graph and prevents
ambiguity, consistent with the message-passing procedure employed by most
GNNs.

Mutagenic: C6H11NO2 | Mutagenic: C6H11NH2
---|---
C_6H_11-N-O_2 |  C_6H_11-N-H_2
Figure 6. Two nitrogen nodes (left and right in blue) predicted to be part of
a mutagenic molecule. Previous explanation approaches would either identify
the graph pattern N–O_2 or N–H_2 as mutagenic, but they were unable to express
both explanations at the same time. In contrast, the class expression
$\ce{N}\sqcap\exists\text{hasBond. }(\ce{H2}\sqcup\ce{O2})$ can do so. Example
adopted from Luo et al. (2020).

##  6\. Conclusion

This paper presents a novel approach for explaining GNNs globally through
class expressions from description logics. By this, we identify and tackle two
problems of XAI on graph-structured data, (1) current graph-based explanations
do not provide global explanations and (2) maximizing the GNN is less suitable
for finding global explanations than evaluating the explanations on a
validation dataset. We demonstrated the effectiveness of our approach on
heterogeneous graphs on a synthetic dataset. In Section 5, we give an
extensive outlook on possibilities for future work. Overall, this paper
provides a foundation for utilizing class expressions as explanations for
heterogeneous GNNs, contributing to the field of XAI on graph-structured data.

## References

  * (1)
  * Agarwal et al. (2023) Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. 2023.  Evaluating Explainability for Graph Neural Networks.  _Scientific Data_ 10, 1 (2023), 144.
  * Amara et al. (2022) Kenza Amara, Zhitao Ying, Zitao Zhang, Zhichao Han, Yang Zhao, Yinan Shan, Ulrik Brandes, Sebastian Schemm, and Ce Zhang. 2022.  GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networks. In _LoG_ _(Proceedings of Machine Learning Research, Vol. 198)_. PMLR, 44.
  * Azzolin et al. (2023) Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Liò, and Andrea Passerini. 2023\.  Global Explainability of GNNs via Logic Combination of Learned Concepts. In _ICLR_. OpenReview.net.
  * Baader et al. (2003) Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider (Eds.). 2003\.  _The Description Logic Handbook: Theory, Implementation, and Applications_.  Cambridge University Press.
  * Baci and Heindorf (2023) Alkid Baci and Stefan Heindorf. 2023.  Accelerating Concept Learning via Sampling. In _CIKM_. ACM, 3733–3737.
  * Barceló et al. (2020) Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. 2020.  The Logical Expressiveness of Graph Neural Networks. In _ICLR_. OpenReview.net.
  * Demir and Ngomo (2023) Caglar Demir and Axel-Cyrille Ngonga Ngomo. 2023\.  Neuro-Symbolic Class Expression Learning. In _IJCAI_. ijcai.org, 3624–3632.
  * Faber et al. (2021) Lukas Faber, Amin K. Moghaddam, and Roger Wattenhofer. 2021\.  When Comparing to Ground Truth is Wrong: On Evaluating GNN Explanation Methods. In _KDD_. ACM, 332–341.
  * Fan et al. (2024) Shaohua Fan, Xiao Wang, Chuan Shi, Peng Cui, and Bai Wang. 2024.  Generalizing Graph Neural Networks on Out-of-Distribution Graphs.  _IEEE Trans. Pattern Anal. Mach. Intell._ 46, 1 (2024), 322–337.
  * Gilmer et al. (2017) Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017\.  Neural Message Passing for Quantum Chemistry. In _ICML_ _(Proceedings of Machine Learning Research, Vol. 70)_. PMLR, 1263–1272.
  * Hamilton et al. (2017) William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive Representation Learning on Large Graphs. In _NIPS_. 1024–1034.
  * Heindorf et al. (2022) Stefan Heindorf, Lukas Blübaum, Nick Düsterhus, Till Werner, Varun Nandkumar Golani, Caglar Demir, and Axel-Cyrille Ngonga Ngomo. 2022\.  EvoLearner: Learning Description Logics with Evolutionary Algorithms. In _WWW_. ACM, 818–828.
  * Himmelhuber et al. (2021a) Anna Himmelhuber, Stephan Grimm, Sonja Zillner, Mitchell Joblin, Martin Ringsquandl, and Thomas A. Runkler. 2021a.  Combining Sub-symbolic and Symbolic Methods for Explainability. In _RuleML+RR_ _(Lecture Notes in Computer Science, Vol. 12851)_. Springer, 172–187.
  * Himmelhuber et al. (2021b) Anna Himmelhuber, Sonja Zillner, Stephan Grimm, Martin Ringsquandl, Mitchell Joblin, and Thomas A. Runkler. 2021b.  A New Concept for Explaining Graph Neural Networks. In _NeSy_ _(CEUR Workshop Proceedings, Vol. 2986)_. CEUR-WS.org, 1–5.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020\.  Open Graph Benchmark: Datasets for Machine Learning on Graphs. In _NeurIPS_.
  * Kouagou et al. (2022) N’Dah Jean Kouagou, Stefan Heindorf, Caglar Demir, and Axel-Cyrille Ngonga Ngomo. 2022\.  Learning Concept Lengths Accelerates Concept Learning in ALC. In _ESWC_ _(Lecture Notes in Computer Science, Vol. 13261)_. Springer, 236–252.
  * Kouagou et al. (2023a) N’Dah Jean Kouagou, Stefan Heindorf, Caglar Demir, and Axel-Cyrille Ngonga Ngomo. 2023a.  Neural Class Expression Synthesis. In _ESWC_ _(Lecture Notes in Computer Science, Vol. 13870)_. Springer, 209–226.
  * Kouagou et al. (2023b) N’Dah Jean Kouagou, Stefan Heindorf, Caglar Demir, and Axel-Cyrille Ngonga Ngomo. 2023b.  Neural Class Expression Synthesis in _ALCHIQ(D)_. In _ECML/PKDD (4)_ _(Lecture Notes in Computer Science, Vol. 14172)_. Springer, 196–212.
  * Kouagou et al. (2024) N’Dah Jean Kouagou, Stefan Heindorf, Caglar Demir, and Axel-Cyrille Ngonga Ngomo. 2024\.  ROCES: Robust Class Expression Synthesis in
Description Logics via Iterative Sampling. In _IJCAI_. ijcai.org.

  * Lehmann (2010) Jens Lehmann. 2010\.  _Learning OWL Class Expressions_.  Ph. D. Dissertation. Üniversity of Leipzig.  https://jens-lehmann.org/files/2010/phd_thesis.pdf PhD in Computer Science, supervisors: Prof. Klaus-Peter Fähnrich, Dr. Sören Auer.
  * Li et al. (2022) Yiqiao Li, Jianlong Zhou, Sunny Verma, and Fang Chen. 2022\.  A Survey of Explainable Graph Neural Networks: Taxonomy and Evaluation Metrics.  _CoRR_ abs/2207.12599 (2022).
  * Lin et al. (2021) Wanyu Lin, Hao Lan, and Baochun Li. 2021.  Generative Causal Explanations for Graph Neural Networks. In _ICML_ _(Proceedings of Machine Learning Research, Vol. 139)_. PMLR, 6666–6679.
  * Longa et al. (2022) Antonio Longa, Steve Azzolin, Gabriele Santin, Giulia Cencetti, Pietro Liò, Bruno Lepri, and Andrea Passerini. 2022.  Explaining the Explainers in Graph Neural Networks: a Comparative Study.  _CoRR_ abs/2210.15304 (2022).
  * Luo et al. (2020) Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. 2020.  Parameterized Explainer for Graph Neural Network. In _NeurIPS_.
  * Perotti et al. (2023) Alan Perotti, Paolo Bajardi, Francesco Bonchi, and André Panisson. 2023.  Explaining Identity-aware Graph Classifiers through the Language of Motifs. In _IJCNN_. IEEE, 1–8.
  * Ramaswamy et al. (2023) Vikram V. Ramaswamy, Sunnie S. Y. Kim, Ruth Fong, and Olga Russakovsky. 2023.  Overlooked Factors in Concept-Based Explanations: Dataset Choice, Concept Learnability, and Human Capability. In _CVPR_. IEEE, 10932–10941.
  * Schlichtkrull et al. (2018) Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018.  Modeling Relational Data with Graph Convolutional Networks. In _ESWC_ _(Lecture Notes in Computer Science, Vol. 10843)_. Springer, 593–607.
  * Shi et al. (2022) Chuan Shi, Xiao Wang, and Philip S. Yu. 2022.  _Heterogeneous Graph Representation Learning and Applications_.  Springer.
  * Shin et al. (2022) Yong-Min Shin, Sun-Woo Kim, Eun-Bi Yoon, and Won-Yong Shin. 2022.  Prototype-Based Explanations for Graph Neural Networks (Student Abstract). In _AAAI_. AAAI Press, 13047–13048.
  * Thomas et al. (2023) Josephine Maria Thomas, Alice Moallemy-Oureh, Silvia Beddar-Wiesing, and Clara Holzhüter. 2023\.  Graph Neural Networks Designed for Different Graph Types: A Survey.  _Trans. Mach. Learn. Res._ 2023 (2023).
  * Wang et al. (2023) Junfu Wang, Yuanfang Guo, Liang Yang, and Yunhong Wang. 2023\.  Enabling Homogeneous GNNs to Handle Heterogeneous Graphs via Relation Embedding.  _IEEE Trans. Big Data_ 9, 6 (2023), 1697–1710.
  * Wang and Shen (2023) Xiaoqi Wang and Han-Wei Shen. 2023.  GNNInterpreter: A Probabilistic Generative Model-Level Explanation for Graph Neural Networks. In _ICLR_. OpenReview.net.
  * Wang and Zhang (2022) Xiyuan Wang and Muhan Zhang. 2022.  How Powerful are Spectral Graph Neural Networks. In _ICML_ _(Proceedings of Machine Learning Research, Vol. 162)_. PMLR, 23341–23362.
  * Wu et al. (2021) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2021\.  A Comprehensive Survey on Graph Neural Networks.  _IEEE Trans. Neural Networks Learn. Syst._ 32, 1 (2021), 4–24.
  * Ye et al. (2022) Zi Ye, Yogan Jaya Kumar, Goh Ong Sing, Fengyan Song, and Junsong Wang. 2022.  A Comprehensive Survey of Graph Neural Networks for Knowledge Graphs.  _IEEE Access_ 10 (2022), 75729–75741.
  * Ying et al. (2019) Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. 2019.  GNNExplainer: Generating Explanations for Graph Neural Networks. In _NeurIPS_. 9240–9251.
  * Yuan et al. (2020) Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. 2020\.  XGNN: Towards Model-Level Explanations of Graph Neural Networks. In _KDD_. ACM, 430–438.
  * Yuan et al. (2023) Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. 2023\.  Explainability in Graph Neural Networks: A Taxonomic Survey.  _IEEE Trans. Pattern Anal. Mach. Intell._ 45, 5 (2023), 5782–5799.
  * Yuan et al. (2021) Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. 2021.  On Explainability of Graph Neural Networks via Subgraph Explorations. In _ICML_ _(Proceedings of Machine Learning Research, Vol. 139)_. PMLR, 12241–12252.
  * Zhang et al. (2022) Shichang Zhang, Yozen Liu, Neil Shah, and Yizhou Sun. 2022\.  GStarX: Explaining Graph Neural Networks with Structure-Aware Cooperative Games. In _NeurIPS_.


# The emission positions of kHz QPOs and Kerr spacetime influence

ZHANG Chengmin1 Corresponding author<EMAIL_ADDRESS>WEI Yingchun1 YIN
Hongxing1 ZHAO Yongheng1 LEI YaJuan2 SONG Liming2 ZHANG Fan2 YAN Yan3 1\.
National Astronomical Observatories, Chinese Academy of Sciences, Beijing
100012, China  2\. Institute of High Energy Physics, Chinese Academy of
Sciences, 19B Yuquan Road, Beijing 100049, China  3.Urumqi Observatory,
National Astronomical Observatories, CAS, Urumqi 830011, China

###### Abstract

Based the Alfven wave oscillation model (AWOM) and relativistic precession
model (RPM) for twin kHz QPOs, we estimate the emission positions of most
detected kHz QPOs to be at $r=18\pm 3km$ $(R/15km)$ except Cir $X-1$ at $r\sim
30\pm 5km(R/15km)$. For the proposed Keplerian frequency as an upper limit to
kHz QPO, the spin effects in Kerr Spacetime are discussed, which have about a
5% (2%) modification for that of the Schwarzchild case for the spin frequency
of 1000 (400) Hz.The application to the four typical QPO sources, Cir $X-1$,
Sco $X-1$, SAX J1808.4-3658 and XTE 1807-294, is mentioned.

###### keywords:

kHz QPO, neutron star, low-mass X-ray binaries

††journal: Phys Mech Astron

,

##  1 Introduction

In thirty more low-mass X-ray binaries (LMXBs), the kiloHertz quasi-periodic
oscillations (kHz QPOs) have been found , where $2/3$ of them show the twin
peak kHz QPOs[1], upper and lower frequencies, in the ranges of $\sim 100$ Hz
- 1300 Hz for the sources with the different spectrum states, e.g. Atoll and
$Z$[2]. The separations of twin kHz QPOs are not constant[1, 3, 4, 5, 6, 7],
which are inconsistent with the beat model[8, 9]. The low frequency QPOs have
also been found, which follow the tight correlations with the kHz QPOs [1, 4].
Some kHz QPO models have been proposed,most of which are ascribed to the
accretion flow[10], and the Alfven wave mode oscillation[11, 12]. To account
for the varied kHz QPO separation, the relativistic precession model (RPM) is
proposed by Stella and Vietri[15], which ascribes the upper frequency to the
Keplerian frequency of orbiting material in an accretion disk and the lower
frequency to the periastron precession of the same matter.

However, for the detected twin kHz QPOs of neutron star (NS) in a LMXB, their
average ratio value is also $3:2$, but varies with the accretion, which may
indicate some distinctions between BHC and NS[1]. In this short letter, we
will investigate the orbital positions of kHz QPO emissions, based on the
Alfven Wave Oscillation Model (AWOM) [13, 14] and RPM[15]. The Kerr spacetime
modification is discussed by considering the spin influence on the Keplerian
frequency.

##  2 AWOM/RPM for kHz QPOs

AWOM ascribes an upper frequency to the Keplerian frequency of orbiting matter
at radius r, and a lower frequency to the Alfven wave oscillation frequency at
the same radius, as described in the following) [13, 14],

$\nu_{2}=\nu_{k}=1850AX^{\frac{3}{2}}$ (1)

with the parameter $X=R/r$ (ratio between star radius R and disk radius $r$)
and $A=(m/{R_{6}^{\ 3}})^{1/2}$ with $R_{6}=R/10^{6}(cm)$ and $m$ the mass $M$
in the units of solar masses. The ratio of twin kHz QPO frequencies can be
obtained as,

${\nu}/{\nu}=(1+(1-x)^{{1/2}})^{\frac{1}{2}}/X^{\frac{4}{5}}$ (2)

which only depends on the position parameter $X=R/r$, and has nothing to do
with the other parameters. The twin kHz QPO separation is obtained as,

$\nu_{2}-\nu_{1}=\nu_{2}[1-(1-(1-x)^{\frac{1}{2}})^{\frac{1}{2}}]^{\ast}X^{\frac{3}{4}}$
(3)

Figure 1:  Upper kHz QPO frequency vs. the position function
$(X=R/r,Y=3Rs/r,Rs=2GM/C2)$. The upper (down) solid curve represents AWOM with
the mass density parameters $A=0.7$ $(A=0.45)$, where the maximum frequency is
1850A (Hz); The upper (down) dashed curve represents RPM with the mass
parameters $m=2$ $(m=3)$ solar masses, where the maximum frequency is 2200/m
(Hz).  Figure 2:  Twin kHz QPO separation vs. the position function . Curve 1
and 2 represent AWOM with mass density parameters $A=0.7$ and $A=0.45$
respectively. Curve 3 (4) represents RPM with mass parameter $m=2$ $(m=3)$,
respectively. Figure 3:  Twin kHz QPO ratio vs. the position function (Same
meaning as shown in FIG.1). The ratio 1.5 (1) is the averaged (minimum limit)
value of the detected twin kHz QPOs.

In FIG.1, the upper kHz QPO frequency is plotted against the position
parameter $X=R/r$ ($Y=3Rs/r$, $Rs$ is the Schwarzschild radius) for AWOM
(RPM). For the detected twin kHz QPOs, the mass density parameter A is found
to be about 0.7 (e.g. Sco $X-1$) [13, 14]. In most cases (except Cir $X-1$),
the position parameter $X=R/r$ is lies in the range from 0.7 to 0.92, or
radius from $r=1.1R$ to $r=1.4R$. This implies that the emission positions of
most kHz QPOs are close to the surface of the NS $X=1$ for AWOM (for RPM the
emission positions are close to $3Rs$), which means that the maximum kHz QPO
frequency occurs at the surface (ISCO of star $r=R$ for AWOM (or $r=3Rs$ for
RPM). In FIG.2, the twin kHz QPO separation vs. position parameter is plotted,
where the maximum separation 375 (200) Hz is achieved for $A=0.7$ (0.45) at
$X=0.7$ for AWOM. The kHz QPO data of two accretion powered millisecond X-ray
pulsars (AMXPs), Sax J 1808.4-3658 and XTE 1807-294, approximately hint at the
condition of $A=0.45$, which presents relatively low kHz QPO separations. For
RPM, the maximum kHz QPO separations are 360 Hz (210 Hz) for the different
choices of mass parameter $m=2(3)$ solar masses, which occurs at $Y=0.76$. For
the two AMXPs, Sax J 1808.4-3658 and XTE 1807-294, RPM has to assume their
star masses are close to the NS mass upper limit, 3 solar masses, if
consistent theoretical curves with the detected data can be fitted. FIG.3 is
the diagram of twin kHz QPO ratios vs. position parameter. It can be noticed
that the averaged ratio 1.5 of the detected kHz QPOs corresponds to the
position $X=0.83$ for AWOM ($Y=0.89$ for RPM). The ratios of all sources but
Cir $X-1$ lie in the regimes between $ratio=1$ and $ratio=2$. The kHz QPO data
of Cir $X-1$ implies that its kHz QPO emitting positions are far away from the
star, i.e. $0.4<X<0.6$ or $2.5R>r>1.6R$, centered at about $2R$.

##  3 Kerr spacetime effect on the kHz QPO

If the influence of Kerr spacetime on the Keplerian frequency is taken into
account, then the orbital frequency of a spinning point mass $M$ with angular
momentum $J$ is expressed as below[1]

$\nu_{2}=\nu\nu_{k}\xi;\quad\nu_{k}=(GM/4\Pi r^{3})^{\frac{1}{2}}$ (4)

with the Kerr modification parameter

$\xi=1+jR_{g}^{\ \frac{2}{3}};\quad R_{g}=R_{s}/2$ (5)

$j=Jc/GM^{2};\quad J=2\pi I\nu_{s}$ (6)

where $I$ is the moment of inertia, with the maximum value for the homogeneous
sphere $I=(2/5)MR^{2}$. In the Schwarzschild geometry, $j=0$, Eq.4 recovers
the conventional Keplerian frequency; $0<j<1$ represents a prograde orbit. To
put the NS mass $(m=M/M_{\odot}$, radius and spin fre-quency parameters, we
have the following simplified expressions,

$j=4\Pi\nu_{2}R^{2}/R_{g}C=(0.22/m)R_{6}^{\ 2}(\nu_{s}/400HZ)$ (7)

$\xi=1+(0.0013m)R_{6}(\nu_{s}/400hz)$ (8)

If we set the conventional values $M=1.4M_{\odot}$, $R=15km$ and $s=400Hz$,
then the Kerr modification parameter has about a 2% contribution to the
Keplerian frequency, which cannot have too much influence on the kHz QPO model
based on the Keplerian frequency. For the maximum spin fre-quency $1122Hz$,
the Kerr modification contributes about 5% to the Schwarzschild spacetime, so
this influence should be considered when we estimate the NS parameters.

##  4 Discussions and results

The kHz QPO emission positions are analyzed by the models (AWOM and RPM),
which shows that most kHz QPOs (e.g. Sco $X-1$) come from the regimes of
several kilometers away from the stellar surface. This may correspond to the
condition of a spinning up NS, since the detected NS spin frequencies are
averaging $400Hz$[16], less than the upper frequencies. In RPM, the star mass
can be derived by the detected twin kHz QPOs, then it usually gives a value of
2 solar masses, higher than the typical NS mass of 1.4 solar masses. One
reason for RPM’s prediction of high NS mass may be originating from its
assumption of the vacuum circumstance around the star in introducing the
perihelion precession term[15], but the accretion disk does not satisfy this
clean condition. A value of about 3 solar masses for SAX J1808.4-3658 [17]
(e.g. XTE 1807-294) is obtained, which seems to suggest that RPM should be
modified. AWOM cannot predict a stellar mass by QPO but rather an averaged
mass density $(A\sim M^{1/2}/R^{3/2)}$, by which one can evaluate the equation
of state (EOS) of the star. For the presently known kHz QPO frequencies, AWOM
cannot give the prediction of quark matter[18] inside the star unless the QPO
frequency over 1500 Hz is detected. In addition, the Kerr spacetime influence
is investigated, and a 5% modification factor in Keplerian frequency exists
for a high spin frequency of 1000 Hz, which will increase the estimation of
the mass density parameter. Though the spectral properties of Cir $X-1$ are
typical of those of Z sources[19, 20], its detected 11 pairs of kHz QPOs are
generally low frequencies, 230 Hz to 500 Hz for the upper QPO and 56 Hz to 225
Hz for the lower QPO, increasing with accretion rate, which is contrary to
those of the other LMXBs. The peak separation lies at 175-340 Hz, similar to
those of other LMXBs [6]. Since the kHz QPO emitting positions of Cir $X-1$
are estimated to be beyond the orbit of 25 kilometers, we guess that its
rotating frequency is low, e.g. a hundred Hz.

This work is supported by National Basic Research Program of China-973 Program
2009CB824800; National Natural Science Foundation of China (10773017).

## References

  * [1] van der klis M. Rapid X-ray variability, in Lewin W H G, van der Klis M, eds, Compact Stellar X-ray Sources. Cambridge Univ. Press, Cambridge, 39-112.
  * [2] Hasinger G, & van der Klis M. Two patterns of correlated X-ray timing and spectral behavior in low-mass X-ray binaries. Astron Astrophys, 1989, 225: 79 96.
  * [3] Zhang C M, Yin H X, Zhao Y H, et al. The correlations between the twin kHz quasi-periodic oscillation frequencies of low-mass X-ray binaries. MNRAS, 366: 1373-1377.
  * [4] Belloni T., Psaltis D., van der Klis M., A Unified Description of the Timing Features of Accreting X-ray Binaries ApJ, 2002, 572, 392-396.
  * [5] Belloni T., Mendez M., Homan J., On the kHz QPO frequency correlations in bright neutron star X-ray binariesMon. Not. Roy. Astron. Soc. 2007, 376, 1133-1138.
  * [6] Boutloukos, S., van der Klis, M., Altamirano, D., et al.. Discovery of twin kHz QPOs in the peculiar X-ray binary Circinus X-1 . ApJ, 2006, 653, 1435-1444.
  * [7] Mendez, M., van der Klis, M. The Harmonic and Sideband Structure of the Kilohertz Quasi-Periodic Oscillations in Sco X-1. Mon. Not. Roy. Astron .Soc., 2000, 318, 938-943.
  * [8] Zhang W, Morgan E H, Jahoda K, et al. Quasi-periodic X-Ray Brightness Oscillations of GRO J1744-28. Astrophys J, 1996, 469, L29-32.
  * [9] Miller M C, Lamb F K, Psaltis D. Sonic-point model of kilo-hertz quasi-periodic brightness oscillations in low-mass X-ray bina-ries. ApJ, 1998, 508: 791-830.
  * [10] Osherovich V, Titarchuk L. Kilohertz quasi-periodic oscillations in neutron star binaries modeled as Keplerian oscillations in a rotating frame of reference. ApJ, 1999, 522: 113-116.
  * [11] Li X D, Zhang C M. A model for twin kilohertz quasi-periodic oscillations in neutron star low-mass X-ray binaries. ApJ, 2005, 635: 57-60.
  * [12] Shi C S, Li X D. The magnetohydrodynamics model of twin kilohertz quasi-periodic oscillations in low-mass X-ray binaries. MNRAS, 2009, 392: 264-270.
  * [13] Zhang, C.M.: The MHD Alfven wave oscillation model of kHz Quasi Periodic Oscillations of Accreting X-ray binaries. Astron Astrophys, 2004, 423, 401-404.
  * [14] Zhang, C.M., Yin, H. X., Zhao, Y. H., et al.. The applications of the MHD Alfven wave oscillation model for kHz quasi-periodic oscillations. Astron. Nachr./AN 2007, 328, 491-497.
  * [15] Stella, L., Vietri, M. kHz Quasi Periodic Oscillations in Low Mass X-ray Binaries as Probes of General Relativity in the Strong Field Regime. Phys. Rev. Lett. 1999, 82, 17-21.
  * [16] Yin H X, Zhang C M, Zhao Y H, et al. Correlation be-tween Neutron Star spin and kHz QPOs in LMXBs. AA, 471: 381-384.
  * [17] Wijnands, R., van der Klis, M., Homan, J., et al. Quasi-periodic X-ray brightness fluctuations in an accreting millisecond pulsar.. Nature, 2003, 424, 44-47.
  * [18] Li, X.D., Bombaci, I., Dey, M., et al. Is SAX J1808.4-3658 a Strange Star? Phys. Rev. Lett. 1999, 3776, 83-88.
  * [19] Ding G Q, Zhang S N, Li T P, Qu J L. Evolution of Hard X-Ray Spectra along the Orbital Phase in Circinus X-1. Astrophys J, 2006, 645: 576-588.
  * [20] Qu J L, Yu W, & Li T P. The Cross Spectra of Circinus X-1: Evolution of Time Lags. Astrophys J, 2001, 555: 7-11.