TL;DR
GLGExplainer is the first global explainability framework for Graph Neural Networks (GNNs) that generates human-readable Boolean logic formulas to describe a model's behavior. By aggregating local subgraph explanations into high-level "graphical concepts," it provides a faithful, high-level summary of how a GNN combines different structural motifs to make its predictions.
What Problem Does This Paper Address?
While Graph Neural Networks (GNNs) are powerful, they are notoriously "black boxes." Most research into their interpretability focuses on local explainability—identifying which specific nodes or edges in a single input graph led to a prediction. However, local explanations are often noisy and don't tell you how the model behaves across the entire dataset.
Existing global explainers have significant drawbacks: they either just list a collection of local examples or generate a single "prototypical" graph that maximizes a class score. These methods fail to capture compositionality—the idea that a GNN might look for a combination of different motifs (e.g., "Class A if Motif X and Motif Y are present, but not Motif Z"). GLGExplainer addresses this gap by extracting global rules as arbitrary Boolean combinations of learned concepts.
Methods
The GLGExplainer pipeline consists of four main stages, illustrated in Figure 1:
- Local Explanations Extraction: The system uses an off-the-shelf local explainer (like PGExplainer) to extract important subgraphs for every sample in the dataset.
- Embedding Local Explanations: These subgraphs are passed through a GNN encoder to create fixed-size vector representations.
- Concept Projection: The embeddings are projected into a space of $m$ learned prototypes. Each prototype represents a "graphical concept" (e.g., a "house" motif or a "grid" motif). A "discretization trick" (using a straight-through estimator) ensures that each local explanation is assigned to its closest concept, creating a binary concept activation vector.
- Formulas Learning: These binary vectors are fed into an Entropy-based Logic Explained Network (E-LEN). The E-LEN is trained to mimic the original GNN's predictions. Because its first layer is an "Entropy Layer" that encourages sparsity, the model naturally settles on a concise Boolean formula (using AND, OR, and NOT) that explains the class.
Datasets
The authors evaluated their method on three distinct datasets:
- BAMultiShapes: A new synthetic benchmark extending the popular BA-Shapes. It involves Barabási-Albert graphs enriched with combinations of motifs (house, grid, wheel). This specifically tests the ability to learn logical combinations (e.g., Class 1 requires at least two specific motifs).
- Mutagenicity: A real-world dataset of 4,337 molecules. The task is to predict if a molecule is mutagenic, a property known to be linked to specific functional groups like $NO_2$.
- Hospital Interaction Network (HIN): A new real-world benchmark introduced in this paper. It represents face-to-face interactions between doctors, nurses, patients, and admins in a hospital. The task is to classify whether an "ego-network" belongs to a doctor or a nurse based on their interaction patterns.
Key Insights and Ideas
- Faithfulness as a Diagnostic Tool: GLGExplainer doesn't just explain what the model should do; it explains what the model actually does. In the BAMultiShapes task, the GNN failed to correctly classify graphs containing all three motifs. GLGExplainer faithfully captured this "bug," showing that the model had learned an incorrect rule for that specific combination.
- Emergent Clustering: Even without explicit supervision to cluster similar shapes, the prototypes naturally aligned with distinct graphical motifs (see Figure 2) simply by being trained to minimize the prediction error of the E-LEN.
- Compositionality is Key: Unlike its main competitor, XGNN, which struggles to generate meaningful graphs for complex classes, GLGExplainer can describe multi-motif requirements easily through its logic layer.
Key Results
GLGExplainer demonstrated high Fidelity (how well the explanation matches the GNN's predictions) and Accuracy (how well the explanation matches the ground truth labels).
- BAMultiShapes: Achieved a test fidelity and accuracy of 0.96, successfully recovering complex logical rules (see Table 1).
- Mutagenicity: Recovered the well-known $NO_2$ motif as a primary indicator of mutagenicity, achieving 0.81 fidelity.
- HIN: Achieved 0.85 fidelity, discovering rules that align with sociological expectations (e.g., nurses interact more with other nurses and patients, while doctors interact more with other doctors).
As shown in Figure 3, GLGExplainer provides clear, symbolic motifs and formulas, whereas the competitor XGNN often generates generic or uninterpretable structures.
Limitations and Future Work
The primary limitation is the dependence on local explainers. GLGExplainer is a "wrapper" that aggregates local information; if the underlying local explainer produces poor or unrepresentative subgraphs, the global logic formula will be inaccurate. The authors suggest that "Fidelity" could actually be used as a proxy metric to evaluate the quality of local explainers in the future.
Additionally, while the method works well for graph classification, extending it to node classification or link prediction remains a task for future research. The authors also note that the number of prototypes ($m$) currently needs to be tuned as a hyperparameter to balance simplicity and accuracy.
Summary updated