Sound Logical Explanations for Mean Aggregation Graph Neural Networks

We would like to thank the reviewer for their engagement with our paper and the time they took to review it. Please see below for our responses to their comments and questions.

Weaknesses

Query:

The main weakness is regarding the writing style and clarity of the paper. It is very hard to follow the logical flow, and the fact that the paper introduces an abundant and non-intuitive notation does not make the job easier. Overall, I found myself going back several times to the preliminaries to check what symbols mean, and the fact that notation is often introduced as free text in paragraphs makes it very hard to retrieve the desired meaning. A table of symbols might help in this sense, but in general, I recommend a substantial rewriting of the text to favor readability.

Response:

We appreciate this feedback from the reviewer, and are committed to improving the readability of the paper. We are grateful for the concrete insights that were given on confusing sections of the paper, and would appreciate more of it: this will allow us to adapt the paper to be more readable by the machine learning community at large.

Query:

Authors refer to GNN with the letter $\mathcal{N}$, which is instead frequently used in previous literature to denote the neighborhood of a node.

Response:

This is standard notation in some of the literature, most particularly the works upon which this paper is based [1,2,3]. We typically reserve $G$ for graphs.

Query:

I could not understand the difference between unary predicates $U$ and node colors $c \in \text{Col}$.

Response:

As stated in L68-69, unary predicates are associated with elements of the vector labels of nodes, and edge colours are associated with binary predicates. As shown in L65, the colours correspond to edges, not nodes. We will make this more explicit by editing our paper to state “is a set of directed edges with colour c” (L66).

Query:

Line 269 says ``we define a dataset $D_L^a$ to be the $L$-hop neighbourhood of the constant $a$ in $D^a$''. This is mixing concepts that are apparently distinct, like dataset, constant, and $L$-hop neighborhood.

Response:

As defined in L60-63, a dataset is a set of facts, which contain constants. $L$-hop neighborhood is well-defined in graphs, which makes them well-defined in datasets given the equivalence defined in L112-120. However, we appreciate that the phrase “$L$-hop neighborhood” may be confusing; we will try to find a better term and would welcome any suggestions.

Query:

The explanations provided in Table 3 are very promising and indicate a very interesting result. However, no details are provided about how those are extracted. Authors refer to Theorem 3, which however does not provide a constructive approach to extract those formulas. Also, it is not clear how predicates are defined, and whether they are user-defined or provided in the dataset. This is a crucial detail, as not every dataset may come with this kind of annotation. The authors should, at least, provide a concise and intuitive algorithm to compute those explanations.

Response:

On L310-L313 of our paper, we state how the rules are extracted: specifically, we enumerate all rules of the form given in Theorem 3 up to a number of body concepts, then use Proposition 4 to check for soundness. The latter step is not stated explicitly in this section, it is discussed on L199-L203; to improve readability, we will add a reference to Proposition 4 explicitly on L312. We will also add an algorithm in the appendices to show how the sound rules are computed.

As stated in L58-59, we assume a fixed signature of predicates, thus assuming that they are provided up-front (whether they originate from the dataset or from the user is independent of our claims). In our experiments, we use standard KG benchmarks, all of which come with pre-defined predicates.

Query:

The paper does not compare nor discuss alternative solutions for extracting logic formulas from GNNs already available in the literature.

Response:

We will add comparisons to these papers in our introduction - we thank the reviewer for bringing them to our attention.

Questions

Query:

Q1: How is your method different from [4,5]? (please note, we changed the citation numbering)

Response:

With respect to [4], they only consider explanations in EL, which is a fragment of ELUQ. Thus, our work considers more broad sound rules and explanations. Furthermore, the work provides no formal proofs that their rules are sound for the models - they rely only on empirical evidence.

On the other hand, [5] learn decision trees from GNNs, and then extract logical rules from the decision trees. These decision trees are not equivalent to the GNNs they are derived from (as can be seen in the fact that their performance differs from the GNNs they are learned from), so the extracted logical rules are also not strictly sound. Furthermore, it is not clear how understandable / human readable any of these extracted rules are.

In contrast, our work extracts rules directly from the GNN, with the guarantee that they will be sound for the model.

Query:

Q2: How are the predicates reported in Table 3 defined?

Response:

They are defined in the datasets.

Citations

[1] David Tena Cucala, Bernardo Cuenca Grau, Boris Motik, and Egor V Kostylev. On the correspondence between monotonic max-sum gnns and datalog. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 19, pages 459 658–667, 2023

[2] David Tena Cucala, Bernardo Cuenca Grau, Egor V Kostylev, and Boris Motik. Explainable gnn based models over knowledge graphs. In International Conference on Learning Representations, 452 2021.

[3] Matthew Morris, David Tena Cucala, Bernardo Cuenca Grau, and Ian Horrocks. Relational graph convolutional networks do not learn sound rules. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 21, pages 897–908, 2024.

[4] Köhler, Dominik, and Stefan Heindorf. "Utilizing Description Logics for Global Explanations of Heterogeneous Graph Neural Networks." CoRR (2024).

[5] Pluska, Alexander, et al. "Logical distillation of graph neural networks." Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning. 2024.

Our thanks to the reviewer for their further engagement, particularly with regard to how swift it was. We greatly appreciate the time they are taking and how their feedback is assisting in the improvement of our paper. Please see below for our response:

Nonetheless, [1,2,3] all come from the same main authors, and thus, I would not call this subset of literature representative

Thank you for pointing this out. We concur that our notation does come from a particular subset of the literature, which may not be representative. We are committed to making the paper more readable and are not attached to the use of $\mathcal{N}$ for GNNs. As such, we are happy to change it to whatever the reviewer would find most intuitive: perhaps simply $f$ or $f_\text{GNN}$?

To the best of my knowledge, colors are typically considered to be associated with nodes rather than edges, which are on their side typically referred to as relations.

Our thanks also for this. It is true that in the GNN literature, they are typically referred to as "relation types" rather than colours - the language of edge "colouring" comes from graph theory. This is also something we are very happy to change, in the interest of making the paper more readable and accessible to the machine learning community.

To my understanding, enumerating all rules means to search for any possible subgraph on the input which can be encoded in a manner compatible with rules in Theorem 3, right? Then each candidate rule is tested for soundness, which, to my understanding, means to take this subgraph and feed it back to the GNN that we want to explain.

This is an excellent question and we apologise for the confusion. The reviewer is mistaken about the process: we will try to clarify how it works.

It is true that a candidate rule is checked for soundness by passing a graph through the GNN. However, we do not consider every possible subgraph of the input which can be encoded in a manner compatible with rules in Theorem 3. Instead, we only consider the single dataset (graph) $D_\text{base}$ defined in Proposition 4. $D_\text{base}$ can be thought of as an instantiation of the body of the rule. Thus, for each rule we want to check for soundness, we only require checking the GNN output on a single graph.

To clarify further: the number of such rules (and equivalently, the number of such datasets $D_\text{base}$) is on the order of $2^p$, where $p$ is the number of predicates in the signature (i.e. the number of unique unary types and binary relations in the setting). This is independent of the size of the input graph.

The proof sketch given at the bottom of page 5 should hopefully give some ideas as to why this checking procedure is sound. Please do let us know if this explanation is still confusing, and we will attempt to clarify further.

Thank you for this additional clarification. I think this discussion is helping me (and hopefully other reviewers) to clarify our minds about this contribution.

I understand that this notion is much stronger than a simple witness of model prediction. But consider now the following statement:

This raises concerns for the logical expressivity of MAGNNs

This highlights severe limitations of MAGNNs, and I feel this goes against the interests of the authors, as the fact that they can extract sound explanations for GNNs is very much restricted. In a sense, this seems to suggest that the strong notion of explanation soundness they advocate for is actually very much restricted. Then, why would someone be interested in using a MAGNN rather than any other GNN?

I have an additional question: Can you please provide me with an example of a sound rule extracted for a MAGNN trained optimally for a task involving counting, like counting whether the input graph has more white than black nodes?

We would like to thank the reviewer for their engagement with our paper and the time they took to review it. Please see below for our responses to their comments and questions.

Weaknesses

Query:

The paper feels a bit unambitious, in my view, as theoretical results are a bit shallow and do not establish a clear-cut difference with previous work. For instance, is there any difference between the rules that can be expressed by MAPNNs and GNNs with sum-aggregation and positive weights? The latter can also express properties that lie beyond FO, but I see no reason why the two might not be equivalent in expressive power.

Response:

We assume the reviewer to mean “MAGNNs”, instead of “MAPNNs”. GNNs with sum aggregation and positive weights are characterised exactly by sound rules from the language of Datalog with inequalities, as proved by [1]. This means that they cannot express properties that lie beyond FO, since Datalog with inequalities is a fragment of FO (when not computing to a fixpoint). As such, they are strictly not equivalent to MAGNNs when it comes to expressive power, as we show in Proposition 1 (L136) that MAGNNs go beyond FO.

Query:

The fact that ELUQ is the strongest fragment of ALCQ that can be expressed with MAPNNs was a bit disappointing for me. I understand that this class of results is difficult, but certainly not impossible, and I would have appreciated to see at least some effort in this direction.

Response:

We appreciate that it is disappointing that we could not extend our analysis to fragments of ALCQ beyond ELUQ, or ideally to ALCQ itself. The reason for this is that the monotonicity (under injective homomorphisms) of ELUQ is essential for our proofs. Both negation and universal quantification are non-monotonic, so we had to exclude them from our fragment to be able to prove the claims in the paper.

Questions

Query:

Is there any difference in expressive power between MAPNNs and GNNs with sum aggregation and positive weights?

Response:

We assume the reviewer to mean “MAGNNs”, instead of “MAPNNs”. GNNs with sum aggregation and positive weights are characterised exactly by sound rules from the language of Datalog with inequalities, as proved by [1]. This means that they cannot express logical functions beyond FO, since Datalog with inequalities is a fragment of FO (when not computing to a fixpoint). As such, they are strictly not equivalent to MAGNNs when it comes to expressive power, as we show in Proposition 1 (L136) that MAGNNs go beyond FO. Furthermore, the class of ELUQ rules that MAGNNs can capture is very limited (given in Theorem 3), whereas sum-GNNs with non-negative weights can capture Datalog rules with inequalities, which is a much richer fragment of FO.

Citations

[1] David Tena Cucala, Bernardo Cuenca Grau, Boris Motik, and Egor V Kostylev. On the correspondence between monotonic max-sum gnns and datalog. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 19, pages 459 658–667, 2023

We would like to thank the reviewer for their engagement with our paper and the time they took to review it. Please see below for our responses to their comments and questions.

Weaknesses

Query:

Restricting weights to non-negative values simplifies theoretical analysis but severely limits practical applicability. Negative weights are essential for modeling inhibitory relationships.

Response:

Whilst negative weights are essential for modelling certain types of relationships, past works have found that restricting GNNs to non-negative weights leads to models that are still viable in practice, such as [2] for sum-GNNs and [1] for max GNNs. Our experimental findings also validate that, in practice, mean-GNNs with non-negative weights can still be viable and achieve performance equivalent to (and sometimes even better than) ones with negative weights (see Table 1).

Query:

Rules are trivialized; unclear if results hold for general mean-GNNs. Theorem 3 reduces rules to simplistic forms.

Response:

We consider the fact that Theorem 3 reduces rules to simplistic forms to be a strength of our paper, rather than a weakness. Starting from the general fragment of ELUQ, we can prove that any sound ELUQ rule $r$ is in fact subsumed by much simpler rules. The simpler the rules that subsume $r$, the more powerful the result and the more useful they are for providing explanations.

Questions

Query:

Theorem 3 suggests MAGNNs are limited to trivial monotonic rules. Is this a feature of mean aggregation itself, or an artifact of the non-negative weight constraint?

Response:

This is primarily a feature of mean aggregation. The sketch of the proof given in L182 onwards relies on the fact that, as neighbours of the same type are continuously added to a node, the computation at that node will become arbitrarily close to the computation on the graph including only a single neighbour of that type, and no other neighbours. This is similar to the technique used in the proof of Property D.7, of [3], albeit to prove different results, and using weighted mean aggregation.

Query:

Why do MAGNNs extract zero sound rules on WN18RRv1 (Table 2) despite decent accuracy (95.5%)? Is this due to theoretical limitations or optimization challenges?

Response:

These results show, as stated in the table caption, only the sound rules of the form given in Theorem 3 (which subsume all sound ELUQ rules). We can still use Theorem 6 to derive sound rules that explain predictions, and there may be further sound rules beyond ELUQ, which while sound are difficult (or possibly impossible) to prove to be sound. Ultimately, this is a theoretical limitation of the paper, as we can only check the soundness of certain kinds of rules - the ones given in Proposition 4 and Theorem 6.

Query:

How do you reconcile the 15% F1-score drop for MAGNNs on WN-hier_nmhier (Table 5) with the claim that non-negative weights ``do not significantly impact performance''?

Response:

Firstly, this is not a common benchmark, and our claim is that “restricting mean-aggregation GNNs to have non-negative weights does not significantly impact performance on common benchmarks” (L9-10). On the three benchmark datasets (FB237v1, WN18RRv1, NELLv1), performance of non-negative mean-GNNs is comparable or better to those with negative weights. Furthermore, this is one of only a few isolated examples of where performance drops in our experiments, meaning the claim is still broadly true in all our results. Finally, this dataset was proposed by [2] to specifically penalise models that are only able to learn monotonic rules, so it is not surprising that performance decreases when the weights are restricted to only being positive.

Citations

[1] David Tena Cucala, Bernardo Cuenca Grau, Egor V Kostylev, and Boris Motik. Explainable gnn based models over knowledge graphs. In International Conference on Learning Representations, 452 2021.

[2] Matthew Morris, David Tena Cucala, Bernardo Cuenca Grau, and Ian Horrocks. Relational graph convolutional networks do not learn sound rules. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 21, pages 897–908, 2024.

[3] Adam-Day, Sam, et al. "Almost surely asymptotically constant graph neural networks." Advances in Neural Information Processing Systems 37 (2024): 124843-124886.

Dear Reviewer,

The deadline for the author-reviewer discussion is approaching (Aug 8, 11.59pm AoE). Please read carefully the authors' rebuttal and engage in meaningful discussion.

Thank you, Your AC

We would like to thank the reviewer for their engagement with our paper and the time they took to review it. Please see below for our responses to their comments and questions.

Weaknesses

Query:

Both the theoretical analysis and experimental evaluation are limited to mean-GNNs with non-negative weights, which represent a relatively narrow and simplified subset within the broader family of GNN architectures.

Response:

Whilst the GNN architecture is limited, this was necessary for the analysis and rule extraction we were able to perform, and the results in Table 1 show that this restriction results in models which are still viable in practice. The approach of restriction to non-negative weights has been followed in several past works, for max aggregation [4] and sum aggregation [3]. Our work extends these techniques and analysis to a common aggregation function not yet considered (mean aggregation).

Query:

The experimental section lacks a comparison with existing rule-mining algorithms for knowledge graphs, which makes it difficult to assess the relative effectiveness of the proposed method

Response:

The goal of our paper is not to mine rules from knowledge graphs - this is an added benefit that our results allow for. As stated in our Abstract and Introduction, our motivation is as follows: given that GNNs with mean aggregation are commonly used on knowledge graphs, can we extract sound rules that explain their predictions and determine what kinds of rules can even be sound for such GNNs? With this goal in mind, we believe that comparing against knowledge graph rule-mining approaches would not support the arguments in the paper.

Questions

Query:

Comparison with rule-mining algorithms: There exist a number of works focusing on rule mining from knowledge graphs, including both deep learning–based and symbolic rule-based approaches (e.g., [1], [2]). To what extent are the rules extracted by these existing methods sound? Do those algorithms—and the proposed method—tend to capture similar types of relational patterns?

Response:

The rules learned by Ruleformer [1] are given in their section 3, and have the form r (X, Y ) ← r1 (X, Z1) ∧ ... ∧ rT (ZT −1, Y ). This is Datalog (without disjunction, negation, or inequalities), which is equivalent to the rules learned by GNNs with max aggregation and non-negative weights, as proved in [4]. It is unclear whether the extracted Ruleformer rules are sound for the model, as it is not proved in the paper.

By contrast, [2] prove that the rules learned by DRUM (another method) can be unsound or incomplete, and adapt DRUM such that the rules are sound and complete. In the adapted version of DRUM, the sound rules recovered come from Datalog with inequalities. This is equivalent to the rules extracted from GNNs with sum aggregation and non-negative weights, as proved by [3].

The rules we consider are fundamentally different, since mean aggregation introduces non-monotonicity into the model. By contrast, both of the above rule fragments are monotonic under injective homomorphisms.

Query:

Non-negative weights: The performance difference between GNNs with standard weights and those constrained to non-negative weights varies across datasets. As I understand it, the non-negative parameter space is a subset of the unconstrained one, yet the model with non-negative weights performs significantly better on the NELL dataset. Could the authors provide an analysis or explanation for this non-trivial behavior?

Response:

This matches the behaviour seen by [5] for sum-GNNs and [4] for max GNNs (as noted in L321 of our paper). Our hypothesis for this behaviour is that (1) the restriction to non-negative weights acts a regulariser for the model and (2) the patterns in the data do not require negative weights to be captured, so the restriction makes searching the weight space easier for the optimizer. We will add a brief explanation of this to the paper.

Query:

Broader GNN categories: While extending the theoretical framework to other categories of GNN may introduce additional complexity, it would be beneficial to include a discussion or empirical comparison with other GNN variants. Could similar experiments be conducted on more expressive architectures or more complex networks?

Response:

Other works have already performed empirical and theoretical comparisons between GNNs with different aggregation functions, such as [6]. Given that the contribution of our paper is primarily theoretical, we believe that empirical comparisons between the GNNs with mean aggregation used in our paper and other GNN architectures is outside of our scope, and that the wide-spread use of mean-GNNs (see L34 of our paper) is sufficient motivation for the problem.

Citations

[1] Xu, Zezhong, et al. "Ruleformer: Context-aware rule mining over knowledge graph." Proceedings of the 29th International Conference on Computational Linguistics. 2022.

[2] Wang, Xiaxia, et al. "Faithful rule extraction for differentiable rule learning models." (2024).

[3] David Tena Cucala, Bernardo Cuenca Grau, Boris Motik, and Egor V Kostylev. On the correspondence between monotonic max-sum gnns and datalog. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 19, pages 459 658–667, 2023

[4] David Tena Cucala, Bernardo Cuenca Grau, Egor V Kostylev, and Boris Motik. Explainable gnn based models over knowledge graphs. In International Conference on Learning Representations, 452 2021.

[5] Matthew Morris, David Tena Cucala, Bernardo Cuenca Grau, and Ian Horrocks. Relational graph convolutional networks do not learn sound rules. In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 21, pages 897–908, 2024.

[6] Eran Rosenbluth, Jan Toenshoff, and Martin Grohe. Some might say all you need is sum. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 4172–4179, 2023.

Dear Reviewer,

The deadline for the author-reviewer discussion is approaching (Aug 8, 11.59pm AoE). Please read carefully the authors' rebuttal and engage in meaningful discussion.

Thank you, Your AC