🤖 machine learning

Model-Level GNN Explanations via Rule-to-Graph Readout for Logit Reconstruction

This paper introduces a novel model-level GNN explanation framework that reconstructs raw multiclass logits by composing grounded subgraph concepts into symbolic rules and passing them through a frozen classifier, thereby achieving high-fidelity, test-time instantiable global explanations with rule-level contribution analysis that are significantly faster than prior methods.

Original authors: Shengyao Lu, Jiuding Yang, Aedan J. DeFrates, Keith G. Mills, Baochun Li, Di Niu

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shengyao Lu, Jiuding Yang, Aedan J. DeFrates, Keith G. Mills, Baochun Li, Di Niu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a super-smart robot (a Graph Neural Network, or GNN) that looks at complex networks of dots and lines—like molecules or social networks—and makes predictions. It's incredibly accurate, but it's a "black box." You ask it, "Why did you say this molecule is dangerous?" and it just says, "Because I said so," without explaining how it reached that conclusion.

Existing methods try to explain the robot by pointing out specific patterns it likes. For example, "Oh, it likes molecules with a red ring." But this is like trying to explain a chef's complex recipe by just listing the ingredients they like. It doesn't tell you how the chef mixes them, how much of each they use, or how they balance the flavors to get the final taste.

TreeX is a new tool that changes the game. Instead of just listing ingredients, TreeX tries to rebuild the robot's entire decision-making process using simple, human-readable rules.

Here is how TreeX works, using some creative analogies:

1. The "Recipe Reconstruction" Analogy

Think of the robot's final prediction not as a single "Yes/No" answer, but as a complex flavor profile (like a score for "Spicy," "Sweet," and "Sour").

Old Way: Previous tools tried to find a rule like "If it has a red ring, it's Spicy." They just matched patterns to labels.
TreeX Way: TreeX says, "Let's take the robot's raw flavor scores and rebuild them from scratch using a recipe." It breaks the robot's decision down into logical rules (like "If it has a red ring AND no blue square, add 5 points to Spicy").

TreeX doesn't just guess the final label; it tries to mathematically reconstruct the exact numbers (logits) the robot used before making its final choice. If TreeX can rebuild the robot's "flavor profile" perfectly using simple rules, we know those rules are a true explanation of how the robot thinks.

2. The "Construction Kit" (Concept Mining)

To build these rules, TreeX needs building blocks. It looks inside the robot's brain (its hidden layers) and finds subgraph concepts.

The Analogy: Imagine the robot sees a molecule. TreeX looks at the robot's internal view and says, "Ah, I see a 'Nitro Group' here and a 'Ring Structure' there." It groups similar-looking parts of the graph into reusable "concepts."
The Twist: TreeX is smart about this. It doesn't just grab random pieces; it finds stable, recurring patterns (like finding the same type of brick in different houses) so it can use them as reliable building blocks for its rules.

3. The "Rule Book" (Symbolic Logic)

Once it has the building blocks, TreeX writes a Rule Book.

It uses logic like: "IF (Concept A is present) AND (Concept B is missing), THEN increase the score for Class 1."
The "Negative" Trick: A key feature of TreeX is that it understands absence. Just as a chef might say, "This soup is good because there is no salt," TreeX can create rules based on what is missing. This is crucial for complex decisions where the lack of a feature is just as important as its presence.

4. The "Live Performance" (Test-Time Grounding)

This is where TreeX shines compared to others.

Old Way: Some tools give you a static rule book that applies to the whole dataset, but they can't show you how it works on a specific new molecule you just handed them.
TreeX Way: When you give TreeX a new graph, it instantly activates the relevant rules. It points to the exact parts of the graph that triggered the rule (grounding) and shows you exactly how much that rule pushed the score up or down.
The Analogy: It's like a live sports commentator. Instead of just giving you the final score, TreeX says, "Right now, the team is winning because Player A (Rule 1) scored a goal, which added +2 points, while Player B (Rule 2) missed a shot, which subtracted -1 point."

Why is this better?

The paper claims TreeX is superior for three main reasons:

Faithfulness: It doesn't just guess the right answer; it mathematically reconstructs the robot's internal "confidence scores" (logits) with high accuracy. If TreeX's rules can recreate the robot's exact numbers, the explanation is trustworthy.
Speed: It is up to 20 times faster than previous methods. It's like switching from hand-writing a novel to using a high-speed typewriter.
Actionable Insight: It doesn't just say "This is why." It says, "This rule supports the winning team, while that rule suppresses the losing team." It allows you to see which rules are the "stars" of the show and which are just background noise.

In Summary

TreeX takes a black-box robot, dissects its decision-making into a set of simple, logical "If-Then" rules, and proves those rules work by rebuilding the robot's exact predictions. It handles both what is present and what is missing, works incredibly fast, and gives you a live, detailed breakdown of how the robot thinks for every single new example it sees.

Technical Summary: TreeX - Model-Level GNN Explanations via Rule-to-Graph Readout

Problem Statement

While Graph Neural Networks (GNNs) achieve strong predictive performance, understanding their decision logic remains challenging. Existing approaches primarily focus on instance-level explanations, identifying specific nodes or subgraphs responsible for a single prediction. However, local explanations fail to reveal whether evidence is used systematically across a dataset, whether models rely on spurious shortcuts, or how multiple concepts jointly define class-level decision boundaries.

Current model-level explainers typically attempt to identify graph patterns or symbolic rules associated with a specific class. A critical limitation of these methods is that they treat rules as post-hoc class descriptors rather than functional computational units. They do not explain how multiple rules jointly produce the GNN's final decision or reconstruct the model's raw prediction logits. Consequently, they lack the ability to perform rule-level contribution analysis at test-time or to explain the suppression of competing classes.

Methodology: TreeX

The authors propose TreeX, a novel model-level GNN explanation framework that shifts the explanation target from class-wise rule extraction to rule-based logit reconstruction. TreeX intervenes at the readout interface of a pretrained GNN, keeping the message-passing layers and classifier head frozen, while replacing the original node-to-graph readout with a weighted rule-to-graph readout.

The methodology consists of four main stages:

1. Subtree-Inspired Concept Mining

To ground global rules on local instances, TreeX mines subgraph concepts from the GNN's hidden states:

Local Mining: Node embeddings within a graph are clustered. Each cluster is converted into a support subgraph by aggregating the $l$ -hop receptive fields of its member nodes (subtrees). This biases concepts toward structurally stable evidence rather than noise.
Global Mining: Local concept embeddings are clustered again to form a global concept bank. Representative subgraphs are selected using a two-stage lexicographic majority filter (based on shape and degree signatures) followed by a centroid-distance tie-break.
Theoretical Justification: The paper argues that for maximally powerful MPNNs (like GIN), the $l$ -th layer node embedding is a "Perfect Rooted Tree Representation" of the full $l$ -hop subtree, justifying the use of node embeddings to represent substructures.

2. Neuro-Symbolic Rule Learning

TreeX learns symbolic rules over the global subgraph concepts using a CNF (Conjunctive Normal Form) structure, specifically an OR-of-CNF relaxation:

Class-wise Discovery: Rules are initially learned in a one-vs-rest manner for each target class. Positive literals ( $P[k]$ ) and negative literals ( $\neg P[k]$ ) are instantiated based on the discriminative power of global concepts.
Differentiable Logic: A hierarchical differentiable logic parameterization is used. Clauses are satisfied via a Gödel t-conorm (max over gated literals), and rules are formed via a product-style soft AND across clauses. The final class prediction uses a probabilistic sum (noisy-OR) over candidate rules.
Merging: Class-specific rule candidates are merged into a unified shared rule bank. This two-stage design ensures the discovery of discriminative rules per class while maintaining a shared structure for multiclass reconstruction.

3. Rule-to-Graph Readout

The core innovation is recasting the readout layer:

Rule Embeddings: Rule embeddings are computed by aggregating the embeddings of their constituent literals (weighted by gate activations). Negative literals are represented as the negated embeddings of their positive counterparts.
Logit Reconstruction: Active rules are weighted by a learned global weight vector $w$ . The weighted combination of active rule embeddings is passed through the frozen classifier head of the base GNN to reconstruct the raw multiclass logits ( $\hat{o}_G$ ).
Objective: The model is trained to minimize the Mean Squared Error (MSE) between the reconstructed logits and the original GNN's raw logits.

4. Test-Time Grounding and Analysis

At test time, TreeX projects unseen graphs into the shared concept space, evaluates the fixed rules, and produces instance-specific explanations. It enables:

Grounding: Mapping satisfied literals to concrete local subgraph evidence (for positive literals) or the absence of concepts (for negative literals).
Ablation: Measuring the contribution of each rule by zeroing out its weight and observing the change in reconstructed logits ( $\Delta_{g,r}$ ).

Key Contributions

New Explanation Target: Formulates model-level GNN explanation as rule-based logit reconstruction, moving beyond simple association of patterns with labels to explaining the generation of raw prediction logits.
Symbolic Readout Interface: Introduces a rule-to-graph readout where grounded logical rules act as computational units. Active rule embeddings are aggregated and passed through the frozen classifier to reconstruct multiclass logits.
Grounded and Compositional Rule Construction: Mines subtree-inspired subgraph concepts for continuous embeddings and concrete evidence. It learns OR-of-CNF rules, which preserve alternative realizations within required constraints, offering greater structural expressiveness than DNF-style formulations under the same rule budget.
Functional and Faithful Explanations: Demonstrates that identified critical rules actively support the predicted class and suppress non-target classes, acting as functional units rather than mere post-hoc artifacts.

Experimental Results

TreeX was evaluated on three synthetic (BA-2Motifs, BAMultiShapes, BA-Neg) and two real-world molecular (Mutagenicity, NCI1) datasets.

Logit Faithfulness: TreeX faithfully reconstructs the base GNN's raw multiclass logits, achieving high Absolute Probability Fidelity (APF) (e.g., >97% on BA-2Motifs, >75% on real-world datasets).
Rule Impact: Ablation studies show that top active rules consistently increase the logit of the target class while suppressing non-target classes, confirming their functional role in the decision process.
Necessity of Design: Ablations confirm that removing the rule module, the merging step, or negative literals significantly degrades performance, particularly in reconstructing raw logits.
Efficiency and Comparison: Compared to prior class-wise rule-based explainers (LogicXGNN, GLGExplainer, GraphTrail), TreeX achieves competitive or better Prediction Agreement (PA) while being up to 20× faster. Unlike baselines, TreeX provides rule weights, test-time grounding, and logit-level contribution analysis.

Significance and Claims

The paper claims that TreeX provides a global, test-time instantiable, and subgraph-grounded explanation framework. By shifting the focus to logit reconstruction, TreeX offers a more rigorous evaluation of explainability: rules are not just descriptive but are shown to be functional units that actively shape the decision margin.

The authors emphasize that TreeX is not merely a post-hoc summary tool but a mechanism that reveals how a GNN's decision logic can be decomposed into reusable, weighted symbolic rules. This approach allows for the analysis of how rules support predicted classes and suppress competitors, addressing a gap in current model-level interpretability where the interaction between multiple rules and the final decision boundary remains opaque. The framework suggests a broader route for explaining neural models by identifying human-interpretable concepts, composing them into symbolic rules, and using these rules as readout-level units to reconstruct model behavior.