Sound Logical Explanations for Mean Aggregation Graph Neural Networks

AI summary

Overview

Research area: Neuro-symbolic AI and explainable machine learning, specifically the logical expressivity of graph neural networks (GNNs) used for knowledge graph completion and node classification.

Technical level: Advanced. The paper depends on first-order logic, description logics (ALCQ, EL), Datalog-style rule semantics, and GNN message-passing formalism, alongside an empirical benchmark study.

Scope in one sentence: The paper characterises which monotonic logical rules can be sound for mean-aggregation GNNs with non-negative weights (MAGNNs), gives a fragment of first-order logic that can explain any such prediction, and tests empirically whether the monotonicity restriction costs accuracy.

What This Paper Is About

GNNs are widely used to predict missing facts in knowledge graphs, but their predictions are hard to verify because they are black boxes. Prior work produced sound logical rules - rules that, applied to any dataset, only ever derive facts the model would also predict - for GNNs using max or sum aggregation, but nothing similar existed for the very common case of mean aggregation. This paper closes that gap for mean-GNNs restricted to non-negative weights, proving what sound rules can look like and showing how to explain individual predictions, while checking that the restriction does not wreck performance on benchmarks.

Key Contributions

1. Proof that equivalent FOL programs generally do not exist for MAGNNs. Proposition 1 exhibits a MAGNN whose behaviour is "at least half of a node's neighbours have property U," a counting function that cannot be defined in first-order logic, so the equivalent-program approach used for max/sum GNNs is impossible in general.
2. Exact characterisation of sound monotonic rules. Theorem 3 shows that any sound ELUQ rule (a fragment between EL and ALCQ, using conjunction, disjunction, existential and at-least-n counting) is subsumed by a finite set of much simpler sound rules of the form ∃P₁.⊤ ⊓ … ⊓ ∃P_j.⊤ ⊓ A₁ ⊓ … ⊓ A_k ⊓ ⊤ ⊑ A_{k+1}.
3. A practical soundness test. Proposition 4 reduces checking whether such a rule is sound for a MAGNN to a single forward pass of the model on one tiny "base" dataset; the paper also notes each rule is either sound or not and describes an optimisation based on body-concept containment.
4. A rule language Ω that explains any prediction. Theorem 6 shows that for every MAGNN M, dataset D_a and predicted fact A(a), a rule of the form C^a_L ⊑ A exists that both derives A(a) on D_a and is sound for M, using a new "exists n unique" (∃_n) operator.

Main Findings

• Mean GNNs cannot be fully captured by FOL: The MAGNN in Proposition 1 predicts U(a) exactly when at least half of a's neighbours satisfy U, and this cannot be expressed in first-order logic, so no equivalent rule set can exist for all MAGNNs.
• Sound ELUQ rules are extremely limited in form: Every sound ELUQ rule for a MAGNN is subsumed by a finite collection of rules combining existentials over binary predicates with conjunctions of unary predicates; the authors describe this as "very limited" and note it raises concerns about the logical expressivity of MAGNNs.
• Soundness checking is cheap: For rules of the restricted form, soundness is equivalent to checking that the target fact is produced by the model on a base dataset such as D_base = {A₁(a), …, A_k(a), P₁(a,b), …, P_j(a,b)} for a ≠ b. The number of candidate rules of the relevant shape is stated as δ · 2^(δ·|Col|).
• Link prediction rules collapse to a simple shape: Combining the results with the standard link-prediction encoding from Tena Cucala et al., every monotonic rule sound for the whole link-prediction transformation is subsumed by rules of the form R₁(x,y) ∧ … ∧ R_{m−1}(x,y) → R_m(x,y).
• Non-negative weights often help or match performance on mean GNNs: On WN-sym, mean aggregation with non-negative weights reached 100 ± 0.0 accuracy, precision, recall and F1 versus 99.4/99.5/99.3/99.4 for standard weights; on WN18RRv1 it reached 95.5/98.1/92.7/95.3 versus 93.7/98.5/88.8/93.4; on FB237v1, 71.8/75.4/64.8/69.7 versus 68.7/95.4/39.3/55.7; and on NELLv1, 93.4/88.8/99.4/93.8 versus 75.2/93.8/53.4/65.7.
• Some datasets lose accuracy under the restriction: On LUBM, non-negative weights gave 91.5 accuracy, 87.8 precision, 96.4 recall and 91.9 F1 versus 97.1/96.9/97.2/97.1 for standard weights; on WN-hier_nmhier (which mixes monotonic hierarchy and non-monotonic hierarchy patterns) non-negative weights gave 71.6/80.1/58.8/67.2 versus 86.2/84.7/88.4/86.5.
• Sound rules are recoverable in practice: The authors report recovering a variety of sound monotonic rules; Table 2 records counts including 0 such rules for WN18RRv1, 1 for NELLv1, 136 total for FB237v1, 22.6 total for WN-hier (15.6 with only unary atoms), 53.6 total for WN-hier_nmhier (4.6 unary, 49 mixed), 11.6 total for LUBM (1.4 unary, 9.8 binary, 0.4 mixed) and 0.4 total for WN-sym.
• Explanations can be generated: Sound explanatory rules of the form in Theorem 6 were computed for all true positive predictions made on the test set of LUBM.
• Rules expose model defects: Despite good test-set performance, MAGNNs still learn some nonsensical sound rules, which the authors present as evidence for the value of explainability.

Methodology in Plain English

The authors study GNNs whose only aggregation operation is the mean, and they additionally force all weight matrices to be non-negative ("Non-Neg" models are trained by clamping negative weights to 0 after each optimiser step). This restriction isolates the mean aggregation itself as the source of non-monotonic behaviour, since negative weights would be another source.

On the theory side they work in a logic framework where datasets and coloured graphs correspond one-to-one, so a GNN induces a transformation from datasets to datasets. They ask two questions: what is the most general style of monotonic rule that can be guaranteed sound, and can every single prediction be given a sound explanation? They answer these by constructing explicit rule sets and showing that a single model forward pass suffices to test soundness.

On the empirical side they train max, sum and mean GNNs with 2 layers, a hidden dimension twice the input dimension, ReLU after the first layer and sigmoid after the second, for 8000 epochs with early stopping after 50 epochs without improvement, using binary cross-entropy and Adam with a learning rate of 0.001. Thresholds are chosen by scanning 108 thresholds between 0 and 1 on validation accuracy. Each experiment uses 5 random seeds, with 95% confidence intervals computed as 1.97 × standard error of the mean, assuming a normal distribution. Testing uses inductive benchmarks (WN18RRv1, FB237v1, NELLv1), the node-classification dataset LUBM, and the LogInfer variants WN-hier, WN-sym and WN-hier_nmhier, where 10% of input facts are randomly set aside each epoch as ground-truth positives. Rules are searched up to a differing number of body concepts (4 for LUBM, all 15 for WN-based datasets, 1 for FB237v1, 2 for NELLv1), giving totals such as 383670 candidate rules for LUBM, all 360448 for WN18RRv1 and the LogInfer datasets, 56169 for FB237v1 and 216600 for NELLv1, with subsumed rules not counted. Experiments ran on PyTorch Geometric with 2 CPUs and 16GB of memory on a Linux server, using 34 days of compute time.

Why This Matters

Impact on research: This is the first analysis of logical expressivity and sound rule extraction for mean-aggregation GNNs, complementing existing results for max- and sum-aggregation GNNs. It also gives a negative-flavoured result — sound monotonic rules for MAGNNs are severely restricted, and some MAGNNs have no equivalent FOL program at all — which sets boundaries for the broader neuro-symbolic programme of turning GNNs into readable logic. The paper's construction of a sound rule for every prediction shows that per-prediction explanation remains possible even when a compact global rule set is not.

Real-world applications:

• Knowledge graph completion, where predicted missing facts may need justification before being trusted.
• Predicting properties of drug combinations, cited as a GNN application area.
• Recommender systems, also cited as a GNN application area.
• Any deployment where a model built on a knowledge graph feeds a downstream decision that must be audited or debugged.

Industry relevance: Because mean aggregation is a common default in practical GNN implementations (the architecture resembles R-GCN with the normalisation constant set to the number of c-coloured neighbours), the finding that non-negative weights often preserve or improve performance on inductive benchmarks matters for teams that want verifiable models without paying a large accuracy cost. The paper also demonstrates a concrete auditing use case: sound rules can reveal nonsensical learned behaviour that test metrics hide.

Future Directions

• Is ELUQ maximal? The paper explicitly leaves open whether ELUQ is a maximal monotonic fragment of ALCQ, so a sharper characterisation of monotonic rules may still exist.
• Beyond non-negative weights. The restriction to non-negative weights was chosen to isolate non-monotonicity in the aggregation function; extending the analysis to negative weights is a natural next step.
• Scaling rule extraction. The rule space grows exponentially with the number of predicates; the experiments already had to cap body concepts differently per dataset (for example, 1 for FB237v1 and 2 for NELLv1), so more efficient search or rule-quality strategies remain needed.
• Reducing nonsensical sound rules. Since MAGNNs learn sound rules that are logically valid but semantically wrong, improving the explanation-generation procedure (the paper mentions discussing further strategies in an appendix section) is an open engineering problem.

Target Audience

This paper is aimed at researchers and graduate students working on neuro-symbolic AI, knowledge graph representation learning, and explainable machine learning, particularly those already familiar with description logics, Datalog-style rule semantics and GNN message passing. Practitioners who deploy GNNs on knowledge graphs and need auditable predictions will find the empirical comparison of standard versus non-negative weights and the discussion of rule extraction directly useful, although the theoretical sections require a logic background.

Authors’ abstract

Graph neural networks (GNNs) are frequently used for knowledge graph completion. Their black-box nature has motivated work that uses sound logical rules to explain predictions and characterise their expressivity. However, despite the prevalence of GNNs that use mean as an aggregation function, explainability and expressivity results are lacking for them. We consider GNNs with mean aggregation and non-negative weights (MAGNNs), proving the precise class of monotonic rules that can be sound for them, as well as providing a restricted fragment of first-order logic to explain any MAGNN prediction. Our experiments show that restricting mean-aggregation GNNs to have non-negative weights yields comparable or improved performance on standard inductive benchmarks, that sound rules are obtained in practice, that insightful explanations can be generated in practice, and that the sound rules can expose issues in the trained models.