Rule Extraction from GNNs

Extraction strategies are defined by their scope of approximation:

• Global Extraction: Distills the entire GNN into a single, comprehensive rule set (e.g., a decision tree or logical formula set) that mimics the model's behavior across all inputs.
• Local Extraction: Generates rules that explain the prediction for a specific node or subgraph. This is often more computationally tractable for large graphs and focuses on instance-level counterfactual reasoning.
• Pedagogical vs. Decompositional: Pedagogical approaches treat the GNN as a black box and sample inputs/outputs, while decompositional approaches look inside the model's learned weights.

The extracted rules are typically expressed in first-order logic to capture relational graph structures:

• Predicates: Define node properties (e.g., AtomType(x, Carbon)) and edge relations (e.g., Bond(x, y)).
• Quantifiers: Use existential quantifiers to identify the existence of specific motifs or neighbors.
• Rule Structure: Prediction(x) ← Neighbor(x, y) ∧ Feature(y, High) ∧ ¬Edge(x, z). This format directly translates the GNN's message-passing logic into a human-readable logical clause.

The core challenge is balancing accuracy against interpretability:

• High Fidelity: The extracted rules perfectly replicate the GNN's output but may be as complex as the original model, defeating the purpose of extraction.
• High Comprehensibility: Short, simple rules are easy to audit but may introduce significant approximation error.
• Pareto Frontier: Advanced algorithms like GraphLIME or GraphSVX search for the optimal point where minimal rule complexity yields maximal predictive fidelity, often measured by the Jaccard index between the rule's coverage and the model's decisions.

Instead of extracting logical text, some methods extract discriminative subgraphs as visual rules:

• Frequent Subgraph Mining: Identifies recurring topological patterns (motifs) that strongly activate a specific class prediction.
• Rule Definition: The presence of a specific motif (e.g., a benzene ring in a molecule) becomes a binary rule for classification.
• GNNExplainer: While primarily a local explainer, its output of a compact subgraph can be interpreted as a structural rule: 'If this specific ring structure is present, predict mutagenic.'

A specific technique where a soft binary decision tree is trained to mimic the GNN:

• Hierarchical Rules: Each path from the root to a leaf represents a conjunctive rule.
• Graph-Specific Filters: The tree's internal nodes use learned filters that operate on the graph structure, such as checking the mean feature value of a node's 2-hop neighborhood.
• Regularization: The tree is regularized to be sparse and shallow, forcing it to learn a simplified, rule-based approximation of the GNN's complex decision boundary.

To verify if extracted rules represent true causal logic, not just spurious correlations, we use interventions:

• Graph Manipulation: Apply the extracted rule to a modified graph where the rule's antecedent is artificially satisfied or violated.
• Causal Fidelity: Check if the GNN's prediction changes in accordance with the rule's consequent. If Rule: A ∧ B → C, adding A and B to a graph should force the GNN to predict C.
• Robustness Check: This process distinguishes causal rules from mere associative patterns, ensuring the extracted logic is reliable for safety-critical applications like drug discovery.