Generating Explanations for Conceptual Validation of Graph Neural Networks: An Investigation of Symbolic Predicates Learned on Relevance-Ranked Sub-Graphs

GNNs were invented to make predictions and accomplish tasks for graph-structured data. In contrast to CNNs that process grid-structured inputs in a sequential manner, GNNs operate on graph structures, not necessarily by a pre-specified order. The tasks that they can effectively solve are node classification, link prediction, and graph classification.

One of the first architectures, the Graph Convolutional Network (GCN) [60], took inspiration from CNNs to accomplish tasks, meaning that information about each element is computed by aggregating and combining information from neighboring elements. By the same means as the grid-structured neighborhood of a pixel is used to compute the filter values of a CNN, the k-hop neighborhood of a node is utilized and updated during the training process.

Equation 1 describes the main operations performed in a GNN that update the values of the initial features h on nodes and edges in a manner that is guided by training. k is the number of aggregation iterations and corresponds to the number of hops in the neighborhood \(\mathcal {N}\) that will be considered. The aggregation operation (Eq. 1) uses all features of the neighboring nodes (denoted with u); those can be of any form and can numerically encode several characteristics like size, color, shape and many more.After the aggregation operation, the combine operation provides the new values for the features of node v (equation 1), which are typically called embeddings.

Those two operations are used by GNNs to solve all possible tasks; depending on the task, researchers have found that GNNs can be extended by functionality, having different purposes and serving different goals [60]. Particularly the Graph Isomorphism Network (GIN) architecture learns a function with the use of Multi-layer Perceptrons (MLP) [3]. This provides the necessary flexibility for injectiveness, for the maximum possible discrimination ability, as well as the property of mapping similar graph structures to nearby embeddings. Graph classification with the use of this architecture could succeed in separating different KP classes. xAI methods uncovering the GNN’s decision-making process could help researchers see if those decisions are based on elements that make humans understand the causal factors of a decision [61].

Several methods have been proposed to uncover the underlying decisions made by a GNN classifier by computing relevance scores for nodes, edges, features thereof, walks and sub-graphs. They provide the means toward transparency and, ideally, could be used in combination with symbolic approaches to generate verbal or language-like explanations for increased comprehensibility and better control of the overall system to satisfy the validation and improvement requirements of human-centric AI [10, 35, 45].

However, currently, none of the existing GNN explainers generates verbal or language-like explanations and the vast majority of them search for the substructure that has the highest relevance according to specially designed losses, metrics, and assumptions. In the following paragraphs, we give a short overview.

GNNExplainer: For node as well as graph classification tasks, the GNNExplainer is used to identify important sub-graphs in the input graphs that are going to be explained [17]. Graph and node features are masked; the search for an adequate mask is performed by an optimization algorithm. If the substructure has a high mutual information value [62] w.r.t. the predicted label distribution, then it is a good enough explanation. A variant of this method, the PGExplainer [63] uses a deep neural network to parameterize the generation process of the masks and the explanations in general, thereby explaining multiple instances of sub-graphs at the same time.

GNN-LRP [16]: is a method that applies the Layer-wise Relevance Propagation (LRP) principle [64] to GNN architectures that fulfil the required constraints. The main strategy of LRP, namely the backpropagation of relevance from the output to the input, layer-by-layer, reflecting the intensity of the learned weights in proportion to each other, is transferred to the GNN message-passing scheme (see section 3.1). By applying Taylor decomposition w.r.t. to the graph’s Laplacian matrix, the relevance of each possible walk of a particular size in the graph is computed. This method, although time and memory-consuming, has several benefits that go beyond the fact that it computes both positive and negative relevance. By returning a relevance for each walk, the “flow” of the relative importance of a node is captured in the relevance of its neighboring nodes.

MotifExplainer: [65] is trying to find motifs (sub-graphs that may be characteristic, e.g., circles) in the computation graph of each node that is classified. The domain knowledge is incorporated to reduce the search space effectively by selecting motifs that are known to play a role in the prediction; this procudes explanations that have both high fidelity and sparsity. Those motifs are fed into the model, their embeddings, as well as the performance of the model, is registered and an additional attention model provides the weights by which sub-graphs are selected. The motifs that have a similar prediction performance and have a high attention weight are the ones that are characterized as relevant [14].

GraphLIME: [18], in the same means as LIME [66], tries to find a local surrogate model to explain each node. The N-hop neighborhood of a node is sampled to compute the most representative features, which then serve as the explanations of the prediction.

PGMExplainer: The PGM-Explainer is one of the first counterfactual xAI methods for GNNs [19]; the main goal is to answer the question “what if” the input was different. Counterfactuals are usually created by adding or removing features from the input and this creates a broad spectrum of possibilities on graph data sets. Perturbing the topology of a graph in a way guided by the change in performance leads to the computation of a Probabilistic Graphical Model (PGM) [67, 68] with the help of structure and parameter learning. The resulting PGM’s random variables (also expressed through their conditional probability tables) determine the distribution of values that node features can take.

XGNN: This method uses Reinforcement Learning to guide the search toward the substructure in the graph that was relevant to the decision [69]. It takes into account prior knowledge by starting with an initial state - a small sub-graph - and trying to find the substructure that will keep the prediction performance intact by exploration and exploitation, but also selects graphs that are in accordance with domain knowledge.

While metrics exist to measure the efficiency of an explanation in an algorithmic way, such as fidelity, we believe that for humans, verbal explanations may provide insight into a GNNs decision-making in the most natural way. Furthermore, verbal explanations could be utilized to validate the graph explainer itself. The graphs extracted from symmetrical and non-symmetrical KFs provide an ideal benchmark for such experiments, as they can be categorized into sub-concepts (the sub-graphs with attributes) and verbally described by a human.

In our benchmark, we put a special focus on simulating the expectations of a human user w.r.t. explanations for GNNs. For this particular data set, the input graph is perturbed in all possible ways and while assuming a correct GNN prediction, the human prospects for the relevance values for nodes, edges, and sub-graphs are computed. We chose this approach strategically to enable human-in-the-loop valuable input in a post-hoc procedure, rather than requiring the human to mask the extracted input graph according to domain-specific concepts. Allowing the explainer to only perturb features with or without a concept would not be feasible since it would require modifying each explainer at its very core. This would not be an adequate step toward a general tool for the validation of any explanation inferred by any relevance-based explainer.

In this work, we explore and investigate a new strategy to map human-masked concepts to a learnable model parameter (here: symbolic predicates) inferred by an ILP system. This is done by decomposing the input graph into sub-graphs that contain or do not contain the sub-concepts of interest. After each decomposition, relevance scores are re-calculated for our simulated explainer. We argue that the distribution of relevance scores should remain robust to these concept-wise perturbations and thus will converge to a model parameter.

As a first investigation, we use a synthetic data set with hypothetical relevance scores to validate the general feasibility of our approach. Once the general applicability of the presented approach is fully validated, we will explore relevance scores that are produced by the explainers described in Sect. 3.2.

The usual GNN-based graph classification pipeline, including the explanation of predictive outcomes, would basically consist of three steps. First, the GNN is trained and tested on pre-labeled graph-structured input examples to achieve the highest possible classification performance. Second, the learned GNN model is ready to be applied to yet unseen graph-structured examples from the same domain in order to derive class labels. In the third step, developers and decision-makers can ask for explanations for individual classified examples. These explanations are computed by GNN explainers and their extensions (e.g., ILP as an extension to produce comprehensible output for GNN explainers). Recall Fig. 1 for an overview.

Our work has two branches as far as relevance distributions are concerned. First, we use human domain knowledge for modeling the expected relevance values, and second, we’ve already started analyzing GNN explainers, as presented in Sect. 3.2. The relevance values comprise the basis for the symbolic representation and input to ILP after transformations that will be clarified in Sect. 5. As presented in Fig. 1, our ultimate goal is to compare the explanations expected by humans and the ones created by explainers and thereby achieve concept validation.

Figure 3 illustrates our benchmark, that is based on KFs of vertical symmetry. KFs are depicted on the left side, and the respective explainer output for their graph representation is on the right side of part (a). Each object (yellow triangle, blue circle, etc.) is represented as a node, which is connected through edges to all the other nodes. The red coloring of nodes and edges illustrates the value of relevance assigned by a GNN explainer or as given by humans. The more intense the red color is, the higher is the relevance of the component. Attributes of objects, like shape, size, color and the coordinates of the center-point of an object, are assigned as well with relevance values. In order to derive the relevance for sub-concepts and not for the whole graph of a KF, we decompose each example. Part (b) illustrates the human-understandable sub-concepts (e.g., “a single red triangle”, “two yellow circles side by side”, etc.). At this point, we want to point out that ILP is capable of generalizing from concrete attribute values by introducing variables, making it possible to express more abstract sub-concepts like “some objects side by side”. Part (c) depicts the sub-graphs derived from decomposed KFs and assigned with relevance based upon our assumptions as described in Sect. 2. Since our assumption is that important sub-concepts aggregate more relevance, we summarize the relevance r for each sub-graph G to derive its total relevance R. We then transform the sub-graphs with relevance R into a symbolic representation in Prolog syntax (see part (d)). An example can be found in Fig. 5.

Note that our goal is not to learn an interpretable surrogate model for a GNN with ILP, as presented in [37], but to identify the sub-concepts that are present in the more relevant sub-graphs in contrast to the less relevant sub-graphs. This is a different type of learning task that is not based on splitting symmetrical and non-symmetrical examples. It takes into account that structures that are present in the most relevant sub-graphs from symmetrical and non-symmetrical KFs do not have to be disjoint. This applies, for example, to the edge between two horizontally located nodes that have the same y-axis position in case of symmetry or not in case of non-symmetry. In both cases, the edge holds important information about the class: it is either a horizontal or a diagonal line.

As outlined on the right side of Fig. 3, ILP learns rules from the set of all sub-graphs (represented in Prolog) that apply only to the most relevant sub-graphs. Thus, each rule may contain a symbolic representation of sub-concepts in the form of so-called predicates to learn symmetry and non-symmetry.

For the validation of GNNs and GNN explainers with the help of ILP, we provide a benchmark data set based on the KP for vertical symmetry. Every image in the data set contains either a vertically symmetric constellation of objects or not. Currently, our benchmark includes graphs with one to four objects which have a predefined size, color, and shape, e.g., one triangle and one circle left of the mirror axis and similarly on the right. We created both symmetric and slightly perturbed cases as far as the positions of the objects are concerned. In particular, to create non-symmetrical constellations, each of the coordinates of the four nodes is a noisy version of the corresponding coordinates in the symmetric case. The added noise is sampled eight times in total (twice for each node, one for each coordinate) from a normal distribution \(\mathcal {N}(\mu , \sigma ^2)\) with \(\mu =0\) and \(\sigma = 0.1\). The benchmark generator makes sure that the produced objects do not overlap and that they have distinct relations to each other, as presented in Fig. 2. We consider all possible sub-graphs that can be generated from input graphs with one, two, three, and four objects. For each set of objects, we compute every possible graph with every possible combination of edges. We further include all possible sets of nodes that are not connected by edges.

The total relevance R of each sub-graph G can range from 0 to 1 and is the sum of all relevance values of nodes and edges \(\in \) G. The relevance distribution inside G is defined with the use of domain knowledge about sub-concepts that may be important for differentiating between symmetry and non-symmetry from a human’s perspective. The following principles were applied: First, the R is non-uniformly distributed within a sub-graph to account for the fact that not all components may be equally important, especially in larger sub-graphs. This is preserved even for sub-graphs, where important sub-concepts occur multiple times, under the assumption that GNNs weigh features efficiently and not for the sake of completeness. Second, in accordance to our assumptions presented in Sect. 2, horizontal edges or vertical edges, as well as equal coordinate values of any two nodes on the symmetry axis get a higher R in symmetrical figures compared to non-symmetrical ones. Diagonal edges and unequal coordinates for any two nodes get a higher R in non-symmetrical figures compared to symmetrical ones. Further, some edges get a higher R in both cases if the connection they express is independently important, e.g., a line between a pair of objects (being horizontal in symmetry and diagonal in non-symmetry). Sub-graphs that contain no edges and where the GNN would rather consider the size, shape, or color of an object, are assigned with a lower R in order to account for the considerable irrelevance of such features w.r.t. symmetry. Of course, symmetry holds only if the objects on the symmetry axis are equal in appearance, but in general, concrete size, shape or color values should not play a role. The distribution of relevance in a sub-graph is exemplified in Fig. 4. It shows a non-symmetrical example in which edges that are nearly horizontal get a higher relevance than others.

We further create sub-graphs on four levels of expressiveness named single objects, x-axis, y-axis, and alignment relations. In the case of single objects, all object constellations are created without any edge connecting them - practically all graphs with no edges. In the x-axis case, all possible graphs are created. However, the connection between two nodes is only kept if it expresses a relation w.r.t. the x-axis (“left-of” and correspondingly “right-of”). Similarly, for the y-axis case, only the “down-of” and “up-of” relations are kept. For the alignment case, the eight spatial relationships are: “top-left”, “top-middle”, “top-right”, “middle-left”, “middle-right”, “bottom-left”, “bottom-middle”, and “bottom-right”. To compute them, each object in an image takes an imaginary center position, and the object connected to it, is either inside (contained in) one of the eight sectors or it will be found on one of the eight lines that separate the sectors. It is obvious that if a particular relation is found between two objects, then the corresponding reverse relation must be detected for the same two objects. The code to generate and re-use our benchmark can be found in the corresponding GitHub repository.¹

ILP can be applied to symbolic input to induce a set of logic rules that separates a target class from contrastive classes. Most ILP frameworks perform concept learning, meaning induction based on a set of so-called positive examples, belonging to the target class, and a set of so-called negative examples, not belonging to the target class. The input data, the algorithm as well as the learned set of rules is represented as logic programs that are interpretable for humans [35]. To be more specific, ILP is based on first-order logic, and program code is represented in Prolog, which is a declarative programming language. We shortly summarize the key terminology of ILP and Prolog based on the introduction given in [44].

Prolog programs consist of a finite set of Horn clauses. A Horn clause is a set of disjunctive literals with at most one positive literal and can be represented as an implication, written in the formEach literal \(A_i\) has the form \(p(t_1,\ldots ,t_m)\), consisting of a predicate p and terms \(t_i\). Terms are either a constant symbol, a variable or a composite expression. The literal \(A_0\) is called the head and the conjunction of elements \(\bigwedge _{i=1}^n A_i\) is called the body of a clause. In Prolog, implication \(\leftarrow \) is denoted by \(:-\) and the colon represents conjunction \(\wedge \). Clauses end in a full stop.

Basic Prolog concepts include facts, rules and queries. Horn clauses with an empty body are denoted as facts and express unconditional statements, otherwise they are called rules and express conditional statements. Semantically, we can read a clause as “the conclusion (or head) \(A_0\) is true if every \(A_i\) in the body is true”. Facts are literals with constant terms. Rules express a logical implication to describe that a condition holds if a combination of literals holds, supported by given facts. Queries can be used to retrieve information from a Prolog program. Queries can be either facts, to check for their truth or falsity, or can be composite expressions to retrieve terms that make those expressions true. Since we do not apply queries directly in our approach, we focus on facts and rules in the following paragraphs.

To learn symbolic rules that contain relevant sub-concepts to explain the classification of KFs, we applied the ILP framework Aleph [70]. Aleph uses inverse entailment to induce a theory, consisting of Prolog rules, from a set of positive and negative examples and background knowledge that describes these examples. The default algorithm performs four steps. First, it selects an example to be generalized. Second, it constructs a most specific clause based on a pre-defined syntactical restriction. Then, a clause that is more general than the most specific clause and which entails the selected example is found, and finally, all the examples that are covered by the more general clause (rule) are removed from the set of candidate examples to be generalized.

Figure 5 serves as an illustrative example for our KP benchmark. At the top, it contains an excerpt from the so-called background knowledge, describing one sub-graph of a KF represented by symbolic facts. The facts express which objects are contained in a graph (both denoted by their respective identifiers) and which spatial relationships hold between the contained objects (e.g., “left_of”) as well as the attributes in terms of coordinates (denoted by “has_coordinates”), shape (d. b. “is_a”) and color (d. b. “has_color”) of the objects. We omit the relevance values for all predicates, except for the relevance of the whole graph (d. b. “has_relevance”). These relevance values are excluded from the ILP learning process since the relevance is solely used to split the examples into positive and negative ones. At the bottom, Fig. 5 shows a rule that may be learned by Aleph to discriminate between more relevant and less relevant sub-graphs. It is a rule that covers only vertically symmetrical examples. It represents the sub-concept of equal y-position of contained objects. It may also contain rather irrelevant sub-concepts like the color of an object.

In accordance with our assumptions presented in Sect. 2 and the design of our benchmark that is in line with these presuppositions (see Sect. 4), we expect that ILP learns a set of rules, some of which may cover only symmetrical examples or non-symmetrical examples and where some may cover both. For vertical symmetry, we expect ILP to consider equal y coordinates in objects as well as horizontal and vertical connections between such objects, while for the non-symmetrical examples we expect ILP to consider diagonals between objects with different y coordinates. We further expect that there might be some sub-concepts, like the shape and color of objects that might be included for symmetry if they are equal for different objects and which might be included for non-symmetry if they are not equal.

For our experiments, we distinguish four levels of expressiveness, as presented in Sect. 4. We want to test different levels of detail in the background knowledge for representing sub-graphs of the original graph and, thus, sub-concepts.

Determined by the number of possible combinations, the set of input examples is 20 for single objects and 216 for the x-axis relational case, the y-axis relational case and the more advanced spatial alignments. We set the relevance threshold to a particular value and split the input examples in order to assign them either to the target class or the contrastive case: the ones with less relevance than the threshold value (negative examples) and the ones with equal or more relevance (the positive examples) than the threshold. Figure 6 shows an exemplary split at a threshold of 0.5. We performed experiments for different relevance thresholds - ranging from a minimum threshold of 0.05 (meaning 5 % of a maximum relevance of 1) to the maximum threshold of 0.95 - to test Aleph’s robustness against imbalanced input data and its generalization capabilities. Different thresholds lead to a different number of positive and negative examples and, thus, to imbalanced input. Figure 7 shows the distribution of examples according to the threshold for single objects, whereas Fig. 8 depicts the distribution for spatial relations (along the x-axis, y-axis, and as alignments). As expected, the threshold regulates the balance or imbalance of the input data set for Aleph. This is in line with the fact that relevance values computed by GNN explainers (see 3.2) are generally not equally distributed over sub-graphs. This valuable property is used to explore the capabilities of Aleph to learn from small and potentially imbalanced data sets.

The unequal distribution of relevance values puts the generality of explanations produced by ILP under test. Therefore, we examine the robustness of explanations dependent on the distribution of the relevance across sub-graphs and the chosen threshold. We observe that the best balance for single objects is at t = 0.25 (see Fig. 8), for relations, it is 0.55 (depicted in Fig. 8). In the case of single objects, a split of examples at a threshold of 0.05 yields no negative examples, whereas a threshold of 0.35 yields no positive examples. Similarly, for relations, the corresponding thresholds are 0.05 and 0.85. This is in accordance with the fact that graphs do not accumulate enough relevance at higher thresholds.

This section presents the results for each of our four levels of expressiveness. In particular, we list some rules that had the highest number of covered positive examples while covering as few negative examples as possible and some interesting cases that demonstrate the suitability of learned symbolic predicates for validation.

Figure 9 lists nine exemplary rules that stood out from our results. The first rule was learned for spatial alignment at the threshold of 0.25. Although there was just a small number of contrasting examples (see Fig. 8), the rule is quite representative for symmetrical examples (covering 98 of them) by containing a predicate that imposes the condition of the same y-coordinate value on two related objects, C and B. The rule further states that the graph must contain an object D that is yellow. Something similar applies to the second rule that is learned for the same use case for sub-graphs from non-symmetrical examples. There is a yellow object E; in contrast to the first rule, the predicate expressing the spatial relationship describes a diagonal (B is middle-right top-right of C). Another interesting rule is the third one. Here, ILP found a set of predicates that covers symmetrical as well as non-symmetrical examples, where the sub-graphs had a total relevance higher than the threshold of 0.55. The rule contains several diagonals, e.g., the diagonals top-middle-top-left and bottom-middle-bottom-left. Comparing rules 4 and 5 that were learned for x-Axis relations, one for a threshold of 0.45 and the other for a threshold of 0.55, we can see that rule 4 which covers only symmetrical examples, contains a predicate for the same y-coordinate again. Rule 5, on the other hand, covers only non-symmetrical examples and contains no predicates that are representative of symmetry. Instead, the colors of objects seem to provide a more general pattern here by being different (yellow, blue). Rules 6 and 7 were both learned for y-Axis relations. Their comparison shows how important it is to balance positive and negative examples, meaning examples with higher relevance and those with lower relevance, in order to avoid noise. For rule 6, which was learned at a threshold of 0.25, a total of 98 symmetrical examples could be covered. However, the rule contains a rather irrelevant restriction to the color yellow for an object. In contrast to this, in rule 7, which was learned at a threshold of 0.55 (which is the most balanced case for relations; see Fig. 8), no statements about color are included. Instead, only predicates of containment and spatial relations were induced. For the single objects, we selected two interesting rules. While rule 8 was learned for 12 symmetrical as well as 12 non-symmetrical examples, rule 9 covered only four symmetrical examples. The first one includes information, such as the kind of shape (here: circle), and the second one contains a statement about the same y-coordinate again.

Our results show that aligning the relevance threshold with the distribution of relevance in the sub-graphs produces rules that contain symbolic predicates that match with human-expected sub-concepts.