Global Explainability of GNNs via Logic Combination of Learned Concepts
Authors: Steve Azzolin
Antonio Longa
Pietro Barbiero
Pietro Lio
Andrea Passerini
Venue: ICLR 2023 poster (2023)
Keywords: Explainability
Graph Neural Networks
Concept Learning

Abstract: While instance-level explanation of GNN is a well-studied problem with plenty of approaches being developed, providing a global explanation for the behaviour of a GNN is much less explored, despite its potential in interpretability and debugging. Existing solutions either simply list local explanations for a given class, or generate a synthetic prototypical graph with maximal score for a given class, completely missing any combinatorial aspect that the GNN could have learned.
In this work, we propose GLGExplainer (Global Logic-based GNN Explainer), the first Global Explainer capable of generating explanations as arbitrary Boolean combinations of learned graphical concepts. GLGExplainer is a fully differentiable architecture that takes local explanations as inputs and combines them into a logic formula over graphical concepts, represented as clusters of local explanations. 
Contrary to existing solutions, GLGExplainer provides accurate and human-interpretable global explanations that are perfectly aligned with ground-truth explanations (on synthetic data) or match existing domain knowledge (on real-world data). Extracted formulas are faithful to the model predictions, to the point of providing insights into some occasionally incorrect rules learned by the model, making GLGExplainer a promising diagnostic tool for learned GNNs.

Published as a conference paper at ICLR 2023
GLOBAL EXPLAINABILITY OF GNNS VIA LOGIC COMBINATION OF LEARNED CONCEPTS
Steve Azzolin', Antonio Longa' 1.3 Piettro Barbiero?, Pietro Liô² & Andrea Passerini'
'University of Trento. University of Cambridge, FFondazione Bruno Kessler
atteve.azzol. aezolineestuuunttt unitn. it. (pb737, p1219] ak. uk Iattonio.longa. andrea wwweeraiinensneeeee.....
ABSTRACT
While instance-level explanation of GNN is well-studied problem with plenty of approaches being developed, providing global explanation for the behaviour of a GNN is much less explored, despite its potential in interpretability and debugging. Existing solutions either simply list local explanations for a given class, gener- ate a synthetic prototypical graph with maximal score for a given class, completely missing any combinatorial aspect that the GNN could have learned. In this work, we propose GI. G..xxllaiie (Global Logic-based GNN Explainer), the first Global Explainer capable of generating explanations as arbitrary Boolean combinations of learned graphical concepts. GLGExplainer is a fully differentiable architecture that takes local explanations as inputs and combines them into a logic formula over graphical concepts, represented as clusters of local explanations. Contrary to ex- isting solutions, GLGExplainer provides accurate and human- intrann-nterretabble global explanations that are perfectly aligned with ground-truth explanations (on syn- thetic data) or match existing domain knowledge (on real-world data). Extracted formulas are faithful to the model predictions, to the point of providing insights into some occasionally incorrect rules learned by the model, making GLGEx- plainer promising diagnostic tool for learned GNNs.
INTRODUCTION & RELATED WORK
Graph Neural Networks (GNNs) have become increasingly popular for predictive tasks on graph structured data. However, as many other deep learning models, their inner working remains a black box. The ability to understand the reason for certain prediction represents critical requirement for any decision-critical application, thus representing big issue for the transition of such algorithms from benchmarks to real-world critical applications.
Over the last years, many works proposed I Local Explainers (Ying et al. 2019 Luo et al. 2020 Yuan
ctt al. [022]] Vu & Thai 2020 [haan et al. 2021 Pope et al. 2019]] Magister et al., 202 1| to explain the decision process of GNN in terms of factual explanations, often represented subgraphs for each sample in the dataset. We leave to Yuan et al. 2022) a detailed overview about Local Ex- plainers, who recently proposed taxonomy to categorize the heterogeneity of those. Overall, Local Explainers shed light over why the network predicted a certain value for a specific input sample. However, they still lack global understanding of the model. Global Explainers, the other hand, are aimed at capturing the behaviour of the model as a whole, abstracting individual noisy local explanations favor single robust overview of the model. Nonetheless. despite this potential in interpretability and debugging, little has been done in this direction. GLocalX (Setzu et al.) 2021) is a general solution to produce global explanations of black-box models by hierarchically aggregating local explanations into global rules. This solution is however not readily applicable to GNNs as it requires local explanations to be expressed as logical rules. Yuan et al. Yuan et al.) (2020) proposed XGNN, which frames the Global Explanation problem for GNNs a form of input optimization (Wu al. 2020). using policy gradient to generate synthetic prototypical graphs for each class. The approach requires prior domain knowledge, which is not always available, drive the generation of valid prototypes. Additionally, it cannot identify any compositionality in the returned explanation, and has principled way generate alternative explanations for given class. Indeed, experi-

---

intrinsically part of the input domain without requiring Published as a conference paper at ICLR 2023
mental evaluation shows that XGNN fails generate meaningful global explanations in all the tasks we investigated.
Concept-based Explainability (Kim ct al., 2018 Ghorbani et al. 2019 Ych et al. 2020 is parallel line of research where explanations are constructed using "concepts" I.c., intermediate, high-level and semantically meaningful units of information commonly used by humans to explain their deci- sions. Concept Bottleneck Models (Koh et al., 2020) and Prototypical Part Networks (Chen et al.]
2019a) are two popular architectures that leverage concept learning to learn explainable-by-desiign neural networks. In addition, similarly to Concept Bottleneck Models, Logic Explained Networks (LEN) (Cravvegna et al. 2021a) generate logie-based explanations for each class expressed in terms of set of input concepts. Such concept-basse based classifiers improve human understanding as their in- put and output spaces consist of interpretable symbols (Wu et al.. 2018, Ghorbani et al. 2019 Koh et al.
2020). Those approaches have been recently adapted to GNNs (Zhang et al. [022 Georgiev et al.
2022 Magister et al. 2022). However, these solutions are not conceived for explaining already
learned GNNs.
Our contribution consists in the first Global Explainer for GNNs which i) provides a Global Expla- nation in terms of logic formulas, extracted by combining in fully differentiable manner graphical concepts derived from local explanations; äi is faithful to the data domain, i.c., the logic formulas, being derived from local explanations,
any prior knowledge. We validated our approach on both synthetic and woal-world datasets, showing that method is able to accurately summarize the behaviour of the model explain in terms of concise logic formulas.
BACKGROUND
2.1 GRAPH NEURAL NETWORKS
Given a graph G = EV,E) with adjacency matrix A where A. = 1 if there exists an edge between nodes and j. and node feature matrix X E R|vXr where X; is the r-dimensional feature vector of node i, a GNN layer aggregates the node's neighborhood information into a d-dimensional refined representation H R Vixd The most common form of aggregation corresponds to the GCN (Kipf & Welling 2016 architecture, defined by the following propagation rule:
(1) where A A+ I, Đ is the degree matrix relative to Á, a activation function, and W E FxF is a layer-wise wise learned linear transformation. However, the form of Eq heavily dependent on the architecture and several variants have been proposed (Kipf & Welling 2016 Veličković et al. 2017
#+ σ (D AD ***
Gilmer et al. 2017)
2.2 LOCAL EXPLAINABILITY FOR GNNS
Many works recently proposed Local Explainers explain the behaviour of GNN Yuaan et al. 2022]. In this work, we will broadly refer to all of those whose output can be mapped to a subgraph of the input graph (Ying et al., 2019 Luo et al. 2020 Yuan et al., 2021; Vu & Thai 2020 Shan
be the weighted graph obtained by applying the local explainer LEXP to generate a local explanation for the prediction of the GNN ff over the input graph G, where each Aij relative to ğ is the likelihood of the edge (i.j) being an important edge. By binarizing the output of the local explainer & with threshold 0 R we achieve set of connected components G; such that U, G. C &. For convenience, will henceforth refer to each of these G, local explanation.
al. 2021 Pope al. 2019). For the sake of generality, let LEXP ( 9)
3 PROPOSED METHOD
The key contribution of this paper is a novel Global Explainer for GNNs which allows to describe
the behaviour of trained GNN f by providing logic formulas described in terms of human-
understandable concepts (see Fig. T. In the process, we use one of the available Local Explain-
(Ying al. 2019 Luo al. 2020 Yuan et al. 2021 Vu & Thai 2020 Shan et al. 2021 Pope
2

---

Published as a conference paper at ICLR 2023
GNN 11
Binarization
Prediction
GLGExplainer
Explainer
Logic formula
Local Explanations Extraction
DATASET
Concept Projection
Formulas Learning
Learned concepts
Softmax
Discretization
Paoling
Embedding ng Local Expl. hi]
d(p1
0.7
E-LEN
d(p2
Q
Entropy Layer
d(p3
0.6
MLP
d(p4
0.1
Logic formula
Prediction
Figure 1: Illustration of the proposed method.
ct al. 2019) to obtain a local explanation for each sample in the dataset. We then map those local explanations some learned prototypes which will represent the final high-level concepts (e.g. mo- tifs in a graph). Finally, for the formulas extraction, we input the vector of concept activations to an Entropy-based LEN (E-LEN) (Barbiero al., [002]] Ciravegna al. 20211) which is trained to match the predictions of f. In the following, we will describe every step in more detail.
The first step of our pipeline consists in extracting local explana- tions. In principle, every Local Explainer whose output can be mapped to subgraph of the input sample compatible with our pipeline (Ying et al. 2019 Luo et 2020 Yuan et al. 2021 Vu & Thai 2020 Shan et al.) 2021 Pope et al.) 2019). Nonetheless, in this work, we relied on PGEx- plainer (Luo al. 2020) since it allows the extraction of arbitrary disconnected motifs as explana- tions and it gave excellent results in our experiments. The result of this preprocessing step consists
Local Explanations Extraction:
a list D of local explanations, which are provided as input to the GLGExplainer architecture. More details about the binarization are available in Section 4.2
Embedding Local Explanations: The following step consists learning an embedding for each local explanation that allows clustering together functionally similar local explanations. This is achieved with a standard GNN which maps any graph & into a fixed-sized embedding h()) E Rd Since each local explanation & is subgraph of an input graph G, in our experiments used the original node features of the dataset. Note, however, that those features can arbitrarily augmented make the aggregation easier. The outcome of this aggregation consists set (h()), VG D} of graph embeddings.
Concept Projection:
Inspired by previous works on prototype learning (Li al. 2017 Chen al.
2019b), we project each graph embedding E E' into set P of m prototypes {p. E F7
I,..., m) via the following distance function:
d(pr, e) sosssotaaa (1og( ||e P1l +
log( |le Pm
log(
(2)
|ee 1 +
|e Pm 12 2
Prototypes are initialized randomly from a uniform distribution and are learned along with the other parameters of the architecture. As training progresses, the prototypes will align as proto- typical representations of every cluster of local explanations, which will represent the final groups of graphical concepts. The output of this projection is thus a set V {we, Ve E E} where Ve [d(p1, e), .., d(pm, e)] is vector containing a probabilistic assignment of graph embedding (thus the local explanation that maps to it) to the m concepts, and will be henceforth referred to as concept vector.
Formulas Learning: The final step consists of an E-LEN, i.c., a Logic Explainable Net- work (Ciravegna al. 2021a) implemented with Entropy Layer first layer (Barbiero al.
3

---

Published as a conference paper at ICLR 2023
2021). An E-LEN learns map a concept activation vector to a class while encouraging sparse use of concepts that allows to reliably extract Boolean formulas emulating the network behaviour. We train an E-LEN to emulate the behaviour of the GNN feeding it with the graphical concepts extracted from the local explanations. Given a set of local explanations 91 ..... ... for an input graph 9i and the corresponding set of the concept vectors U1 ... Un,, we aggregate the concept vectors via a pooling operator and feed the resulting aggregated concept vector to the E-LEN, providing fG.) as supervision. In our experiments we used max-pooling operator. Thus, the Entropy Layer learns mapping from the pooled concept vector to (i) the embeddings 2 (as any linear layer) which will be used by the successive MLP for matching the predictions of f. (ii) truth table T explaining how the network leveraged concepts to make predictions for the target class. Since the input pooled concept vector will constítute the premise in the truth table T, a desirable property to improve hu- man readability is discreteness, which we achieve using the Frraiigh-TThrougge (ST) trick used for discrete Gumbel-Softmal Estimator (Jang et al. 2016). In practice, we compute the forward pass discretizing each e via argmax, then, in the backwart pass to favor the flow of informative gradient we use its continuous version.
Supervision Loss: GLGExplainer is trained end-to-end with the following loss:
L = Lsurr + A1 LRi + A2
(3)
where Leury corresponds to a Focal BCELoss (Lin et al., 2017) between the prediction of our E-LEN and the predictions to explain, while Lıa and Lyz2 respectively aimed to push every prototype Py to be close to at least one local explanation and to push each local explanation to be close to at least prototype (Li et al. 2017). The losses are defined as follows:
L Barr -y(1 p)" log p - (1 - yy)p" log(1 - p)
(4)
m
LRI
min llp, h(11112 SED m 1=1
Σ
(5)
LR2
min
[|p h())
(6)
D
jE[2m]]
GED
where p and y represent respectively the probability for positive class prediction and the focusing parameter which controls how much to penalize hard examples.
4 EXPERIMENTS
We conducted an experimental evaluation on synthetic and real-world datasets aimed at answering the following research questions:
Q1: Can GLGExplainer extract meaningful Global Explanations?
Q2: Can GLGExplainer extract faithful Global Explanations?
The source code of GLGEEplainer, including the extraction of local explanations, well as the datasets and all the code for reproducing the results is made freely available online")
4.1 DATASETS
We tested our proposed approach on three datasets, namely:
BAMultiShapes: BAMultiShaess is a newly introduced extension of some popular synthetic bench- marks (Ying al. 2019) aimed to assess the ability of a Global Explainer deal with logical com- binations of concepts. In particular, we created dataset composed of 1,000 Barabási-Alberr (BA) graphs with attached in random positions the following network motifs: house, grid, wheel. Class contains plain BA graphs and BA graphs enriched with house, grid, wheel, or the three motifs together. Class I contains BA graphs enriched with a house and a grid, a house and a wheel, or a wheel and a grid.
https::/ http://thhhbcccmm/tteeeraaa//oo
4

---

Published as a conference paper at ICLR 2023
Mutagenicityy
The Mutagenicity dataset is collection of 4,337 molecule graphs where each graph is labelled as either having a mutagenic effect or not. Based on Debnath et al. [1991). the muta- genicity of molecule is correlated with the presence of with nitro groups (e.g. NO2). Moreover, compounds with three or more fused rings tend to be more mutagenic than those with or two. Most previous works on this dataset have focused on finding the functional group NO2, since most of them struggle in finding compounds with more than two carbon rings.
elements conjugated
Interaction Network (HIN): HIN is a new real-world benchmark proposed in this work. It represents the third-order ego graphs for doctors and nurses collected in an hospital (Vanhems et al.] 2013). There are four types of individuals in the network: doctors (D), nurses (N), patients (P), and administrators (A). Such typologies constitute the feature vector for each node, represented as one-hot encoding. Each ego network is an instance, and the task is to classify whether the ego in the ego network is a doctor or nurse (without knowing its node features, which are masked). More details about the dataset construction are available in the Appendix.
Hospital
face-to-face interaction network
For Mutagenicity we replicated the setting in the PGExplainer paper (Luo et al. 2020 while for BAMultiShapes and HIN we trained until convergence 3-layer GCN. Details about the training of the networks and their accuracies are in the Appendix.
4.2 IMPLEMENTATION DETAILS
Local Explanations Extraction: As discussed in Section 3 we used PGExplainer (Luo al. 2020) as the Local Explainer. However, we modified the procedure for discretizing weighted graphs into set of disconnected motifs. Indeed, the authors in Luo et al. (2020) limited their analysis to graphs that contained the ground truth motifs and proposed to keep the top-k edges as a mule-of-thumb for visualization purposes. For Mutagenicity, over which PGExplainer was originally evaluated, we simply selected the threshold 0 that maximises the Fl score of the local explainer over all graphs, including those that do not contain the ground- truth motif. For the novel datasets BAMultiShapes and HIN, we adopted dynamic algorithm to select 9 that does not require any prior knowledge about the ground truth motifs. This algorithm resembles the flbow-methood i.c., for each local explanation sort weights in decreasing order and chooses as threshold the first weight that differs by at least 40% from the previous one. We believe that threshold selection for Local Explainers is a fundamental problem to make local explainers actionable, but it is often left behind in favor of top-k selections where k is chosen based on the ground-truth motif. In the Appendix we show some examples for each dataset along with their extracted explanations.
GLGExplainer: We implemented the Local Explanation Embedder h as a 2-layers GIN (u et al, 2018) network for each dataset except HIN, for which we found GATV2 (Brody al., (021) to provide better performance as the attention mechanism allows the network to account for the relative importance of the type of neighboring individuals. All layers consist of 20 hidden units followed by non-linear combination of max, mean, and sum graph pooling. We set the number of prototypes m to 6, 2. and for BAMultiShapes, Mutagenicity, and HIN respectively (see Section 4.4 for an analysis showing how these numbers were inferred). keeping the dimensionality d to 10. We trained using ADAM optimizer with early stopping and with a learning rate of 1e - for the embedding and prototype learning components and learning rate of 5e for the E-LEN. The batch size was set to 128, the focusing parameter 7 to 2, while the auxiliary loss coefficients a and X2 were set respectively to 0.09 and 0.00099. The E-LEN consists of an input Entropy Layer (R - R11),, a hidden layer 1 + R and an output layer with LeakyReLU activation function. We turned off the attention mechanism encouraging sparse use of concepts from the E-LEN, as the end-to- end architecture of GLGExplainer already promotes the emergence of predictive concepts, and the discretization step preceding the E-LEN encourages each concept activation vector to collapse on a single concept. All these typer-parameted were identified via cross- cross-validation over the training set.
4.3 EVALUATION METRICS
In order to show the robustness of our proposed methodology, we have evaluated GLGExplainer on the following three metrics, namely: i) FIDELITY, which represents the accuracy of the E-LEN in matching the predictions of the model f to explain; üi) ACCURACY, which represents the accuracy
5

---

Published as a conference paper at ICLR 2023
Table 1: Raw formulas extracted by the Entropy Layer along with their test Accuracy. Each formula was rewritten to just keep positive literals.
Dataset
Raw Formulas
Accuracy
Classo
V V V
BAMultiShapes
(P1 P3 A ABV ARDV
0.98
Class
(P4 A Pi) PDV (P. BAA.AAAAAAAAAAAAAAAAAAA
P2
Classo
P P A PD)
Mutagenicity
0.83
Class
Po
Classp
P
HIN
0.84
Class;
P2
of the formulas matching the ground-truth labels of the graphs; ii) CONCEPT PURITY, which computed for every cluster independently and measures how good the embedding is clustering the local explanations. A more detailed description of those metrics is available in the Appendix. For BAMultiShapes and Mutagenicity, every local explanation ground-truth motif, or Others in case it did not match any ground-truth motif. For HIN, since no ground truth explanation available, the users involved in the interaction (e.g., in a local explanation representing the interaction between a nurse and patient, the label corresponds to NP). Since labelling each possible combination of interactions between 4 types of users would make the interpretation of the embedding difficult, we annotated the most frequent seven (D, N, NA, P, NP, MN, MP), assigning the rest to Others. Note that such unsupervised annotation may negatively impact the resulting Concept Purity since it ignores the correlation between similar but not identical local explanations.
annotated with its corresponding
labeled each local explanation with string summarizing
4.4 EXPERIMENTAL RESULTS
In this section will go through the experimental results with the aim of answering the search questions defined above. Tresent the raw formulas extracted by the Entropy Layer where, improve readability, we have dropped negated literals from clauses. This means that for each clause in a formula, missing concepts are implicitly negated. Those formulas can be fur- ther rewritten in a more human-une unmaaannnnnsttaabbeleee format after inspecting the representative elements of each cluster shown in Figure 2 where for each prototype Pj the local explanation & such that G = g ( ((G')) is reported. The resulting Global Explanations are reported in Figure 3 where we included qualitative comparison with the global explanations generated by XGNN Yuan et al.) (2020), the only available competitor for global explanations of GNNs. Finally, Table 2
shows the results over the three metrics described in Section 4.3 Note that XGNN is not shown in the table as it cannot be evaluated according to these metrics.
P
P
P
WHEEL
ICUst
DMD
Hospital Interaction Network (HIN)
P
P
P
MIX
NOS
NURSES
IATEENTS
MANNT
McKoos MileNts
Figure 2: representative element for each concept. For completeness, the Appendix we report five random instances for each concept.
Q1: Can GLGExplainer extract meaningful Global Explanations? The building blocks of the Global Explanations extracted by GLGExplainer are the graphical con- cepts that leamned in the concept projection layer. Figure clearly shows that each concept rep-

---

Published as a conference paper at ICLR 2023
GLGExplainer
XGNN
max
max
max
Class
BAMultSSaaee
[BA]
[Gri]]
[House]
[Wheee)]
Class
[Dthers
max node
3
max node
max node
Mutagenicity
V oo
a
[Others)]
Class
node
node
node
VERTH
Class
HIN
Class
Figure 3: Global explanations of GI.GExplainer (ours) and XGNN. For Class 0 of BAMultiShapss,, XGNN was not able to generate graph with confidence 2 0.5. Note that for each clause, missing concepts are implicitly negated.
Table 2: Mean and standard deviation for Fidelity, Accuracy, and Concept Purity computed over
runs with different random seeds. Since the Concept Purity computed for every cluster indepen- dently, here we report mean and standard deviation across clusters over the best run according to the validation set.
Fidelity
Accuracy
Test Concept Purity
Dataset
Train
Test
Train
Test
BAMultSShapes Mutagenicity HIN
0.96 + 0.03
0.96 + 0.03
0.92 + 0.03
0.96 + 0.03
0.87 + 0.24
0.82 + 0.00
0.81 0.01
0.78
0.00
0.79 + 0.01
1.00 + 0.00
0.89 = 0.00
0.85 + 0.02
0.86 + 0.01
0.85 + 0.02
0.78 + 0.18
resents local explanations with specific characteristics, thus achieving the desired goal of creating interpretable concepts. Note that clusters corresponding to concepts are on average quite homo- geneous (see Concept Purity in Table 2). and the concept representatives in the figure are faithful representations of the instances in their corresponding cluster. See the Appendix for further de- tails, where we report five random instances for each concept. It is worth noting that this clustering emerges solely based on the supervision defined by Eq while no specific supervision was added to cluster local explanations based on their similarity. This is the reason behind the emergence of the Mix cluster around P2 in the upper part Figure 2, which represents all local explanations with at least two motifs that present solely in Class I of BAMultiShapes.
Additionally, as shown in Figure 3 GLGExplainer manages to combine these building blocks into highly interpretable explanations. The explanation for BAMultiShapes almost perfectly matches the ground-trun formula, where the only difference is the conjunction of all motifs being assigned to Class I rather than Class 0. This however is due discrepancy between the ground-truth formula and what the GNN learned, as will be discussed in the answer to Q2. Note that the Mix cluster has been rewritten as the conjunction of the shapes it contains when extracting the human-interpretable
7

---

Published as a conference paper at ICLR 2023
formulas. For Mutagenesis, the GLGExplainer manages to recover the well-known NO2 motif as an indicator of mutagenicity (Class 0). It is worth reminding that in all formulas in Figure 3 negative literals have been dropped from clauses for improved readability. Having formulas for Mutagenesis only two concepts, this implies that the formula for Class O actually represents NO2 itself ((NO2 OTHERS) V (NO2 A OTHERS) > NO2). For HIN, the global explanations match the common belief that nurses tend to interact more with other nurses or with patients, while doctors tend to interact more frequently with other doctors (or patients, but less frequently than nurses).
Conversely to our results, XGNN (Yuan et al. 2020) fails to generate explanations matching either the ground truth or common belief about the dataset in most cases, while failing to generate any graph in others.
Q2: Can GLGExplainer extract faithful Global Explanations?
The high Accuracy reported in Table 2 shows that the extracted formulas are correctly matching the behaviour of the model in most samples, while being defined over fairly pure concepts as shown by the Concept Purity in the same Table. It is worth highlighting that GLGExplainer is not simply generating an explanation for the ground-truth labeling of the dataset, bypassing the GNN it is supposed to explain, but it is indeed capturing its underlying predictive behaviour. This can be seen by observing that over the training set, Fidelity is higher than Accuracy for all datasets. Note that on BAMulltShapps, training accuracy is lower than test accuracy. The reason for this train-test discrepancy can be found in the fact that the GNN fails to identify the logical composition of all three motifs (which rare and never occur in the test set) seen by decomposing the GNN accuracy with respect to the motifs that occur in the data (Table and observing that the accuracy for the group with all three motifs (All) is exactly zero Quite remarkably, GLGExplainer manages to capture this anomaly in the GNN, as the clause involving all three motifs is learned as part of the formula for Class instead of Class O, as shown in Figure 3 The ability of GLGExplainer to explain this anomalous behaviour is a promising indication of its potential as a diagnostic tool for learned GNNs.
indicator of Class O. This can be
Table 3: Accuracy of the model to explain on the train set of BAMultiShapes with respect to every combination of motifs to be added the BA base graph. H. G, W stand respectively for House, Grid, and Wheel.
Class 0
Class 1
Motifs Accuracy (%)
H
G
W
All
H G
H W
G+ W
1.0
1.0
0.85
1.0
0.0
1.0
0.98
1.0
In the rest of this section we show how the number of prototypes, that critically affects the inter- pretability of the explanation, can be easily inferred by trading-off Fidelity, Concept Purity and sparsity, and we provide an ablation study to demonstrate the importance of the Discretization trick.
Choice of the number of prototypes: The number of prototypes in the experiments of this section was determined by selecting the smallest m which achieves satisfactory results in terms of Fidelity and Concept Purity, as measured on a validation set. Specifically, we aim for a parsimonious value of m comply to the human cognitive bias of favoring simpler explanations to more complex ones (Miller) 1956). Table 4 reports how different values of m impact Fidelity and Concept Purity. The number of prototypes achieving the best trade-off between the different objectives was identified as 6, 2 and 4 for BAMultiShapes, Mutagenicity, and HIN respectively.
The Discretization trick was introduced in Section B to enforce a discrete prototype assignment, something essential for an unambiguous definition of the concepts on which the formulas are based. We ran an ablation study to evaluate contribution to the over- all performance of G.GExplainer. Figure 4 (left) shows the reduction in concept vector entropy achieved by GLGExplainer with the discretization trick (red curve, zero entropy by construction) as compared to GLGExplainer with the trick disabled (orange curve). Figure 4 (middle) reports the Fidelity over the training epochs for the two variants. The figure shows the effectiveness of the discretization trick in boosting Fidelity of the extracted formulas, which is more than double the one achieved disabling it. We conjecture that the reason for this behaviour is the fact that the discretiza- tion trick forces the hidden layers of the E-LEN to focus on the information relative the closest
Role of the Discretization trick:
8

---

Published as a conference paper at ICLR 2023
Table 4: Fidelity and Concept Purity functions of the number of prototypes in use. Results referred to the validation set.
Metric
Dataset
m 2
m =
m
m 8
BAMultiShapes
0.93
0.93
0.95
0,95
Fidelity
Mutagenicity
0.83
0.83
0.84
0.79
HIN
0.88
0.89
0.89
0.88
BAMuleiShapes
0.42
0.73
0.84
0.91
Concept Purity
Mutagenicity
0.97
0.99
0.96
0.99
HIN
0.45
0.80
0.77
0.70
prototype, ignoring other positional information of local explanations. Thus, the E-LEN predictions much better aligned with the discrete formulas being extracted, and indeed the Accuracy of the formulas matches the Fidelity of the E-LLEN, which is shown in the right plot. On the other hand, GLGExplainer without discretization has high Fidelity but fails extract highly faithful formulas. Note that simply adding an entropy loss over the concept vector to the overall loss (Eq. 3 fails to achieve the same performance obtained with the discretization trick.
Discnetization
Discretization
Concept Vector Entropy
Accuracy
Fidelity
1.0
3.0
08
ontropy
8
02
12-
25
102
700
100 o.pochs
403
500
700
932
100
602
Figure 4: Impact of the Discretization Trick. Each run halted with early stopping on the validation set.
CONCLUSION
We introduced GLGExplainer, the first Global Explainer for GNNs capable of generating explana- tions as logic formulas, represented terms of learned numan-interpretable graphical concepts. The approach is inherently faithful to the data domain, since it processes local explanations extracted by an off-the-shelf Local Explainer. Our experiments showed that GLGExplainer, contrary to exist- ing solutions, can faithfully describe the predictive behaviour of the model, being able to aggregate local explanations into meaningful high-level concepts and combine them into formulas achieving high Fidelity. GLGExplainer even managed to provide insights into some occasionally incorrect rules learned by the model. We believe that this approach can constitute the basis for investigating how GNNs build their predictions and debug them, which could substantially increase human trust in this technology.
The proposed GLGExplainer is inherently faithful to the data domain since processes local expla- nations provided by a Local Explainer. However, the quality of those local explanations, in terms of representativeness and discriminability with respect to the task sssc-fpcciiic class, has direct effect on the Fidelity. If the generated concept vector does not exhibit any class-specific pattern, then the E-LEN will not be able to emulate the predictions the model to explain. Despite being a potential limitation of GLGEXplainer, this can actually open to the possibility of using the Fidelity of local explanations quality, which notoriously difficult to assess. We leave this investigation to future work. Despite tailoring our discussion graph classification, our approach can be readily extended to any kind of classification task on graphs, provided that a suitable Local Explainer is available.
proxy

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This research was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215.
REFERENCES
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. In arXiv:2208. 093399 2022.
Pietro Barbiero, Gabriele Ciravegna, Francesco Giannini, Pietro Lió, Marco Gori, and Stefano Melacci. Entropy-based logic explanations of neural networks, 2021. UR//httss://rxxv
org/abs/ 2106. 06804
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? arXiv preprint arXiv:2105. 2021.
Chaofan Chen, Oscar Li, Daniel Tao, Alina Barettt, Cynthia Rudin, and Jonathan K Su. This looks like that: Deep learning for interpretable image recognition. Advances in Neural Information Processing Systems, 32:8930-8941, 2019a.
Chaofan Chen, Oscar Li, Daniel Tao, Alina Barnett, Cynthia Rudin, and Jonathan K Su. This looks like that: Deep learning for interpretable image recognition. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019b. URL adf 14bbee 888872443
.ddf
Gabriele Ciravegna, Pictro Barbiero, Francesco Giannini, Marco Gori, Pietro Lió, Marco Maggini, and Stefano Melacci. Logic explained networks. arXiv preprint arXi::2108.05144 2021a.
Gabriele Ciravegna, Pietro Barbiero, Francesco Giannini. Mareo Gori, Pietro Lió, Marco Maggini, and Stefano Melacci. Logic explained networks, 2021b. URL htttt:t///axiiiiee org/abs/
2108 09149
Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, and Cor- win Hansch. ceuuuture-activvig relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chemistry, 34(2)788-7777, 1991. doi: 10.1021/m00006alll URI. /tt.hhttss////o.ccrrt
1021 1021/3m001 0 64046
Dobrik Georgiev, Pietro Barbiero, Dmitry Kazhdan, Petar Veličković, and Pietro Liò. Algorith- mic concept-based explainable reasoning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6685-6693, 2022.
Amirata Ghorbani, James Wexler, James Y. Zou, and Been Kim. Towards automatic concept-based explanations. In Neural Information Processing Systems (NeurlPS), pp. 9273-9282, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
Eric Jang. Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax, 2016. httpg//bb//111....
URL httphhsss//aaiv..ooooo http:/wwwrrggab//11....o
Been Kim, Martin Wattenberg, Justin Gilmer, Carrie J. Cai, James Wexler, Fernanda B. Viégas, and Rory Sayres. Interpretability beyond feature attribution: Quantitative testing with concept activation vectors (TCAV). In International Conference on Machine Learning (ICML), volume 80
of Proceedings of Machine Learning Research, pp. 2673-2682. PMLR, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv preprint arXiv: 1609.02977, 2016.
10

---

Published as a conference paper at ICLR 2023
Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In International Conference on Machine Learning (ICML). volume 119 of Proceedings of Machine Learning Research, pp. 5338-5344 PMLR, 2020.
Oscar Li. Hao Liu, Chaofan Chen, and Cynthia Rudin. Deep learning for case-based reason- ing through prototypes: A neural network that explains its predictions, 2017. URL https:
04806
Tsung-Yi Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. Focal loss for dense object detection, 2017. httth::::///: org/ abs/aass//10 atgg/bs/1708 02002
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong. Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network, 2020. URL https://arxiv.
org/ abs/2011. 04573
Lucie Charlotte Magister, Dmitry Kazhdan, Vikash Singh, and Pietro Liò. Gcexplainer: Human in- the-loop concept- explanations for graph neural networks. arXiv preprint arXiv:2 1189, 2021.
Lucie Charlotte Magister, Pietro Barbiero. Dmitry Kazhdan, Federico Siciliano, Gabriele Ciravegna, Fabrizio Silvestri, Mateja Jamnik, and Pietro Lio. Encoding concepts in graph neural networks. arXiv preprint arXiv:2207. 13586, 2022.
George A Miller. The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psychological review, 63(2):81, 1956.
Phillip E. Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10772-10781, 2019.
Mattia Setzu, Riccardo Guidotti, Anna Monreale, Franco Turini, Dino Pedreschi, and Fosca Gian- notti. GLocalX from local to global explanations of black box Al models. Artificial Intelligence, 294:103457, may 2021. doi: 10.1016/j 2rtint.2021.103457 URL 101652FJ. ar..aatiin. int. 2021 103457
Caihua Shan, Yifei Shen, Yao Zhang, Xiang Li, and Dongsheng Li. Reinforcement learning enhanced explainer for graph neural networks. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 22523-22533. Curran Associates, Inc., 2021. URL lttts::/proceeddice nww.ips........ cc/paperr202///1ee pdf
be26 6abe 2ttpee/occcaaaa22ccccceceee
Philippe Vanhems, Alain Barrat, Ciro Cattuto, Jean-François Pinton, Nagham Khanafer, Corinne Régis, Byeul-a Kim, Brigitte Comte, and Nicolas Voirin. Estimating potential infection transmis- sion routes in hospital wards using wearable proximity sensors. PLoS One, 8(9):, 2013.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710. 17t0.19000... 2017.
Minh N. Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks, 2020. URL /RL.tttps///rrx/..ooo///////
05788
Mike Wu, Michael C. Hughes, Sonali Parbhoo, Maurizio Zazzi, Volker Roth, and Finale Doshi- Velez. Beyond sparsity: Tree regularization of deep models for interpretability. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), AAAI Conference on Artificial Intelligence, pp. 1670 1678. AAAI Press, 2018
Weibin Wu, Yuxin Su, Xixian Chen, Shenglin Zhao, Irwin King, Michael R. Lyu, and Yu- Wing Tai. Towards global explanations of convolutional neural networks with concept attribution. In 2020 JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. (649-8658, 2020. doi: 10. 10.1099CCVP42260222000000

---

Published as a conference paper at ICLR 2023
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? arXiv preprint arXiv:1810.00S26, 2018.
Chih-Kuan Ych, Been Kim, Sercan Ömer Arik, Chun-Liang Li, Tomas Pfister, and Pradeep Raviku- mar. On completeness-aware concept-based explanations in deep neural networks. In Neural Information Processing Systems (NeurIPS), 2020.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Gen- erating explanations for graph neural networks, 2019. URL
1903. 03894
Hao Yuan, Jiliing Tang, Xia Hu, and Shuiwang Ji. XGNN: Towards model-level explanations of graph neural networks. In Pruceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, aug 2020. doi: 10.1145/3394486.3400355.. URL
httpp:://dot www.oogg.o....oooooooooo.o
3403085
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations, 2021. httpt/tts///a.tt.. ottporra//bb///// 051
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Cheekong Lee. Protgnn: Towards self- explaining graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 36, pp. 9127-9135, 2022.
A APPENDIX
A.I DATASETS DETAILS
While BAMultiShapes and Mutagenicity were already described in detail in Section 4.1 here we report more details about the newly introduced dataset for graph Explainability. Figure presents some random examples for each dataset, with their extracted explanation in bold.
HIN: Hospital Interaction Networks is new real benchmark that we propose in this work. The dataset was collected using wearable sensors, equipped with undo-frrequency identification devices (RFIDs) capturing face-to-face interactions. The devices record interaction if and only if there at least one exchanged signal within 20 seconds. The dataset was collected by Sociopatterns collaboration in the geriatric ward of university hospital (Vanhems et al. 2013) in Lyon, France, over four days in December 2010. The individuals belong to four categories: medical doctors (M), nurses (N), administrative staff (A), and patients (P).
Since the interaction network GT evolves over time, we convert the temporal network into a se- quence of graph snapshots, aggregating interactions every five minutes (GT [91. 92....... G,)) For each static graph G., we extract the ego graph with radius centered in each doctor and each nurse, obtaining set ego graphs. A GNN trained in classifying between ego networks of doctor and nurse, where the feature of each ego node is masked.An illustrative example of this procedure shown in Figure 5 In particular, the top of the figure shows static snapshot (G.) of the temporal graph. In the middle, we show three ego graphs (with radius equal to 2 for convenience) cen- tered on two doctors (D; and D2) and a nurse (Ni) respectively. Finally, the ego node features are obtain 880
masked, as depicted at the bottom of Figure At the end of this extraction procedure, and 2009 ego graphs for doctors and nurses respectively. To avoid class imbalance, we sub-sample the nurse class, obtaining balanced dataset of 1760 graphs.
A.2 IMPLEMENTATION DETAILS
A.2.1 TRAINING THE GNN /
In this section we will provide more details about the training of the GNN to explain f. While for Mutagenicity we limited to reproduce the results presented (Luo et al. 2020) both in terms of
http://www..scconpattess.oog
12

---

Published as a conference paper at ICLR 2023
Graph snapshot (9.)
D
P
N
N.
A
Ego graph (g
Ego graph (g.
Ego graph (g)
D
N.
Figure 5: Extraction of ego graphs in Hospital Interaction Network (HIN).
model to explain (a 3 layers GCN Kipf & Welling 2016)) and local explanations, for BAMulti- Shapes and HIN we trained our own networks. For BAMultiShapes adopted 3-layers GCN (20-20-20 hidden units) with mean graph pooling for the final prediction, whilst for HIN we em- ployed 3-layers GCN (20-20-44 20-20-20 hidden units) with non-linear combination of sum, mean, and max graph pooling. The final model performances are reported in Table In both cases we used ADAM optimizer, training until convergence and using the validation set to select the best epoch.
A.2.2 EXPLAINERS
In this work we relied mainly on two off-the-shelf explainers, namely, PGExplainer (Luo et al. 2020) and XGNN (Yuan et al. 2020). Here we report some details about their usage.
PGExplainer: For Mutagenicity and BAMultiShapes, we used the original implementation as provided by Luo et al. (2020). For BAMultiShapes we changed to original hyper-parameters to (epochs: 5, args e1r=0.... 007, args wwwffttfff]ooooooo 0, args coff. 0005 args. cof f_ e D000. For HIN we instead used the PyTorch implementation provided by Agarwal et al. (2022), using custom hyper-parameters (t0=1, t1=1, max.epochs=30), Finally, for BAMuluShapes and HIN, for which we extracted our own local explanations. we trained PGExplainer on the train split of the original dataset. It is worth mentioning that for HIN, after the local explanations extraction, we removed every local explanation not containing the ego node.
XGNN:
The official code provided here is specifically tailored for generating explanations for the Mutagenicity dataset. For the other two, despite the algorithm accepting an heavy optimization for the task at hand (like defining custom rewards functions for each task), we made minimal changes to the architecture and to the original hyppe--arrmetees in order not input any a-priori knowledge. For HIN, specifically, and the custom check val..ialllie dity function to define whether the generated graph is valid, i.c.. it must contain single ego node. For what concern the evaluation metries presented in Section
adapted the node type generation match the node types of the dataset,
13

---

Published as a conference paper at ICLR 2023
Table 5: Accuracies of the different models explain.
Split
BAMultiShapes
Mutagenicity
HIN
Train
0.94
0.87
0.92
Val
0.94
0.86
0.87
Test
0.99
0.86
0.86
since XGNN and GLGExplainer return explanations in two substantially different formats, could not compare quantitatively the explanations provided by XGNN with ours. Thus, a direct comparison of XGNN under metric is not possible.
A.2.3 CHOOSING A AND A2
In Eq S we introduced the two parameters regulating the importance of the two auxiliary losses described in Section 3 Those parameters were kept fixed to, respectively, 0.09 and 0.00099 for all the experiments and were chosen via cross validation. In Figure 6 we show how the Fidelity over the validation set changes with different combinations of such hyper- apper-parameters.
BAMultiShapes
Mutagenicity
100
Kajlalyy
0.88
0.88
Fideity
0.75
0.75
0.62
0.50
0.50
0.00039
0.0009
0.09
0.0009
0.00099
X1
0.9
72
0.09
A1
0.9
0.0009
Figure 6: How does the selection X and 2 impact Fidelity?
A.3 LOCAL EXPLANATIONS EMBEDDING
For layout reasons, did not report in the main paper the 2D embedding plot for each dataset. However, we believe it is of great interest since gives a visual sense of how similar local ex- planations get clustered in the same concept. Thus, we report Figure IO the 2D plot of local explanations embedding for BAMultiShapes, Mutagenicity, and HIN.
In addition this, we report graphical materialization of five random samples for each concept, in Figures
B
14

---

Published as a conference paper at ICLR 2023
Class
Class
Figure 7: Random examples of input graphs along with their explanations in bold as extracted by PGExplainer, for BAMultiShapes.
Class
Class
Figure 8: Random examples of input graphs along with their explanations in bold as extracted by PGExplainer, for Mutagenicity
15

---

Published as a conference paper at ICLR 2023
Class
Class
Figure 9: Random examples of input graphs along with their explanations in bold as extracted by PGExplainer, for HIN
local explanations embeddings
prototype assignments
grid wheel
02
p1
house + grid.
D55 p1
p3
wheel grid
p4
priccppll comp. 1
-05
90
45
local explanations embeddings
prototype assignments
p00
NO2
po
6/
02
6.-
1,P1
principal comp,
local explanations embeddings
prototype assignments
principal comp. N
M
.33
N
p1
PI.
PAT
PD
02
00-
MP
-22
0,0
92
94
principal comp. 1
24
-02
19
62
64
6/
Figure 10: 2D PCA-reduced embedding for, respectively, BAMultiShapes and Mutagenieity and HIN
16

---

Published as a conference paper at ICLR 2023
Po
BA
Pi
Wheel
P2
Mix
P3
Grid
P4 House
Ps
Grid
Figure 11: Five random local explanations for each concept in BAMultiShapes.
Po Others
Pi
NO
Figure 12: Five random local explanations for each concept in Mutagenicity.
Po Nurses (+ Adm.)
Ego
800
P1 Patients
5go
ugo
Doctors
Ego
(+ /Pt./Pat.)
Pg Nurses
Eg0
Egoo
Patients
Ego
Figure 13: Five random local explanations for each concept HIN.
17

---

where C₁ corresponds to the cluster having pt prototype (i.e., the cluster containing ev- ery local explanation associated to prototype p; by the distance function d(...) described instead returns the number of local ex- Published as a conference paper at ICLR 2023
A.4 EVALUATION METRICS
Here we will describe in more detail the metrics briefly introduced in Section 4.3
Fidelity measures the accuracy between the prediction of the E-LEN and the one of the GNN explain. It is computed as the accuracy between the class predictions of the E- LEN and the GNN f.
Accuracy Barbiero et al. (021) represents how well the learned formulas can correctly predict the class labels. compute this metric, we treat the final formulas as classifier that given an input concept vector predicts the class corresponding to the clause evaluated to true. In the cases in which either no clause or more clauses of different classes are evaluated to be true, the sample is always considered as wrongly predicted.
Concept Purity is computed for every cluster independently and measures how good the embedding is at clustering the local explanations. was first proposed in Magnster et al.. (2021) for evaluating concept representations by means of graph edit distance. However, since the computation of the graph edit distance is expensive, in our work we adapted such metric exploit the annotation of local explanations as described in Section 4.3) Specifi- cally, in our cases such annotation corresponds to the typology of the motif represented by the local explanation. The computation of the metric can be summarized by:
Concept Purity( mosll Labeeeeuull..be(e(((
[G]
in Section 3)
planations anmotated with the most present label in cluster C,. The Concept Purity results reported in Table 2 are computed by taking the mean and the standard deviation across the m clusters.
A.5 ENTROPY-BASED LOGIC EXPLAINED NETWORKS
Concept-based classifiers (Koh et al. 2020) are a family of machine learning models predicting class memberships from the activation scores of human-understandable categories, i.e., q C + D, where C C [0. 1] Concept- based classifiers improve human understanding as their input and output spaces consist of interpretable symbols (Wu al.
2018 Ghorbani et al., 2019) Koh al. 2020). Logic Explained Networks (LENs (Ciravegna et al. 202 ) are concept-based neural models
providing for each class simple logic explanations Øi C ^>
(0. 1} for their predictions (c) E {0,1), 1}. In particular LENs provide concept-based First-Order Logic (FOL) explanations for each classification task:
Ye Va C C.: (C) ++ (e)..
where of is a concept- formula in disjunctive normal form. The E-LEN employed in our work corresponds to LEN with Entropy Layer Barbiero et al. (202T) first layer, which is the responsible for the extraction of the logic formulas. As mentioned in Section 4.2 given that our architecture already promotes by construction singleton activation of concepts, the entropy- based regularization described in Barbiero et al. (202T) promoting a parsimonious activation of the concepts, allowing the E-LEN to predict class memberships using few relevant concepts only, is removed.
A.5.1 EXTRACTION OF LOGIC FORMULAS
Considering the removal of the entropy-based regularization mentioned above, the process of for- mula extraction can be summarized as follows: given a classification task with r classes, and given a truth table 7 for each of the classes, the 1-th row of the resulting table 7 obtained by con- catenating together the (-th input concept activation vector & with the respective prediction g (ā)::
T = (a (G))
(9)
18

---

Published as a conference paper at ICLR 2023
Then, for every row where ('i) concepts in connected with the AND operator resulting in a logic clause where concepts that appear as false in é are negated. Finally, the final formulas in disjunctive normal form for table 7 are obtained by connecting every clause with the OR operator. Further details are available in Barbiero et al. 2021
A.5.2 ENHANCEMENTS GLGEXPLAINER TO THE E-LEN FRAMEWORK
To make clear the enhancements of our proposed GLGExplainer to the E-LEN framework, note that the original formulation of the E-LEN requires C' to be known. Indeed, the experiments carried out in Barbiero et al. (202T) were all assuming a known mapping from the input space to C. In this case, however, since such mapping is not available, concepts. The choice of learning such concepts from local explanations, rather than generating them via any graph-generation process, allowed our contribution to be faithful to the data domain contrary to previous works on Global Explainability for GNNs Yuan et al. (2020). Since the E-LEN framework does not provide a principled way for dealing with the peculiarities of the graph domain, it cannot be directly applied on top of local explanations. We thus devised the method proposed in Section 3 in order aggregate local explanations into clusters of similar subgraphs, with no further supervision than the one provided by Eg The experimental evaluation in Section 4.4 shows that the learned clusters have indeed a numan-understandable meaning, and the final formulas correctly allow to assess the performances of the model to explain. On the same vein, the framework proposed in Barbiero et al. (202I) is aimed at creating an interpretable classifier which can generate logic architecture. This is radically different from our scenario, where we provide explanations of an already trained model. Finally, given the fact that we removed the entropy- -bsed regularization from the original implementation of the Entropy Layer"] we are basically restricting the usage of it to just the principled process of extracting logic formulas from the truth table T, introduced in Barbiero al. (2021)
aim at learning set of human- uumaan-nndrrtanddblle
explanations of its predictions, resulting in
cerrpretable-by-deeee
A.6 DISTANCE FUNCTION d(...)
In Section 3 we presented Eq. as the distance function d(p;, e) to compute a relative assignment value for the graph embedding to prototype p;, expressed as a probability value thanks to the softmax. For convenience, we report again the mathematical definition below:
d(p,,e) e) = softmar [oog( ||e - 111 +
|le 12 + )............... log( |le Pm 113 )
(10)
|le Pm 2
Note that when d(p;, e) has a high activation value for a prototype pi, then the graph embedding very close to prototype p; the embedding space, thus meaning that the input graph leading to exhibit a similar high-level concept to what p; represents.
Overall, the output of the projection step described Section 3 is set V {we. Ve E} where v. = [d(p), e), d(pm. e)] is vector containing a probabilistic assignment of graph embedding the m prototypes.
19


Reviews:
[{"review_id": "oxYavw-DXJ", "reviewer": "Reviewer_gQT1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an approach to applying the Entropy-based Logic Explained Network (E-LEN) to generate global explanations for a GNN from computed local explanations of the GNN, where both local and global explanations are expressed by sub-graphs. Experimental results on three datasets demonstrate good performance in terms of fidelity, accuracy and concept purity.", "summary_of_the_review": "The paper addresses an important yet insufficiently-studied problem by applying the E-LEN framework. New datasets are proposed to accelerate the on-going studies. However, the proposed approach lacks comparison with the state-of-the-arts in main metrics. Besides, the paper is unclear in some important aspects and need to be improved by clarifying them.", "strength_and_weaknesses": "Strengths:\n\n(1) The work may have a significant impact since generating global explanations for GNNs is seldom studied by now. There seems only one notable approach to generating global explanations for GNNs, namely XGNN (Yuan et al., 2020), but this approach is based on reinforcement learning and thus is unstable and time consuming in course of training.\n\n(2) Out of three experimental datasets, two are proposed by the paper for the first time. The authors promise to make them publicly available upon acceptance.\n\nWeaknesses:\n\n(1) The novelty is limited since the proposed approach seems to be only an application of E-LEN. I suggest the authors to strengthen the novelty for clarifying which enhancements are made beyond the framework of E-LEN.\n\n(2) There is no comparison with XGNN in terms of the main metrics namely fidelity, accuracy and concept purity. In particular, the proposed approach seems inferior to XGNN on Mutagenicity in terms accuracy according to the accuracy reported in (Yuan et al., 2020).\n\n(3) The presentation is generally good but can be improved by clarifying the following two questions.\n\nQ1: How to convert a prototype vector (obtained in the concept projection step) to a subgraph (learnt concept) as shown in Figure 3?\n\nQ2: Why not to use the same set of metrics provided in (Yuan et al., 2020) but introduce a new metric concept purity? Besides, concept purity has not been clearly defined in the paper; it should be defined in a more formal way, e.g., by using formulas.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hmio-Jg2zPf", "reviewer": "Reviewer_CpLz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes GLGExplainer (Global Logic-based GNN Explainer), which is aimed at capturing the behavior of the model as a whole, abstracting individual noisy local explanations in favor of a single robust overview of the GNN model by generating explanations as arbitrary Boolean combinations of learned human-understandable graphical concepts. GLGExplainer uses PGExplainer to extract local explanations (as subgraphs) from graphs and learns an embedding for each local explanation that allows to cluster together functionally similar local explanations, and then projects each local explanation embedding into a set of m prototypes, which are initialized randomly from a uniform distribution and are learned along with the other parameters. The projection for each embedding is thus a vector containing a probabilistic assignment of local explanation embedding. Finally, a Logic Explainable Network learns to map a concept activation vector to a class while encouraging a sparse use of concepts that allows to reliably extract Boolean formulas emulating the network behavior. The authors validated GLGExplainer on both synthetic and real-world datasets, and claims that GLGExplainer is able to accurately summarize the behavior of the model to explain in terms of\nconcise logic formulas.", "summary_of_the_review": "GLGExplainer is the first Global Explainer for GNNs in terms of logic formulas, and it offers a helpful and human-understandable diagnostic tool for learned blackbox GNNs.", "strength_and_weaknesses": "- Strength\n    - The paper is well written and organized, and readers can easily follow the content.\n    - The paper organically aggregates a series of established methods, such as PGExplainer for extracting local explanation subgraphs, and concept or prototype based learning for human-understandable graphical concepts, and E-LEN for generating explanations with compositionality in form of Boolean combinations, in order to address an interesting and useful problem of capturing the behavior of the model as a whole.\n- Weaknesses\n    - There is only single baseline XGNN in the experiments. This is understandable, after all, the previous work on Global Explainer is limited. The table 2 only shows the performance of GLGExplainer, but does not show that of the baseline. \n    - Although this paper mainly aggregates a series of established methods, it would be helpful if some specific details were explained more clearly in self-contained way.\n        - For example, the Equation 2 and E-LEN\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IG81ZAxxB-K", "reviewer": "Reviewer_8iKd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This practical paper proposes a method for computing global explanations for the predictions made by graph neural networks (GNNs). The approach hinges on the use of a local GNN explainer invoked for computing local explanations for the GNN's predictions in the form of sub-graphs of the inputs. Given a number of local explanations, the proposed approach then combines them into a single propositional formula serving as a global summary of the GNN's behavior. The experimental results obtained on three datasets demonstrate the faithfulness and accuracy as well as high interpretability of the proposed approach.", "summary_of_the_review": "In my view, the paper is under-delivering on the novelty side and represents purely practical/engineering effort. I doubt that this should meet the quality standards of a flagship AI/ML conference like ICLR. However, given the lack of my expertise, I admit that I may overlook some important merits of the work, hence my score is not entirely negative.", "strength_and_weaknesses": "First of all, I am not an expert on GNNs and their explainability and so I am afraid I am not the right person to judge the merits of this concrete work. For the same reason, I find this paper quite hard to follow.\n\nThis is a purely practical paper that describes how one can aggregate local explanations, provided in the form of sub-graphs of the input graphs, into a joint propositional formula that summarizes the behavior of the GNN model from the global perspective.\n\nOne of the upsides of the paper is that it is rigorous in terms of citations and seems to cover the prior work in the area quite extensively. It offers a large number of nicely drawn images illustrating the general flow and also examples in the experimental results, which is also a plus as they help a reader a lot.\n\nHaving said that, I have to mention that the proposed solution does not look like a sufficient contribution to me. Granted that this paper hinges on a significant amount of engineering work but the insight is a bit shallow. The fact that the approach is described in essentially a single page seems to confirm this issue. What is worse, the authors give no rationale behind the choices they propose to make. It is just a sequence of steps (1), (2), ..., followed by (n) and a non-expert reader like me is left wondering why these steps are better than the possible alternatives (if any). The steps themselves can be seen as a bunch of technicalities applied widely in the ML community and so the novelty seems a bit on the edge here (again, for a non-expert).\n\nExperimental results are thoroughly presented and discuss the accuracy and fidelity of the computed explanations. However, these concepts do not look sufficient for measuring the \"quality\" of explanations, especially from the perspective of logic and formal correctness of those. I believe in this case a user study is necessary to confirm to what extend the explanations offered by this approach actually help a human understand the behavior of the model.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster