Rule Based Learning with Dynamic (Graph) Neural Networks

Summary

The paper proposes a method for neural network-based learning to incorporate expert knowledge in the neural network architecture by building rules and utilizing them in "rule-based" layers of the learned neural networks. It introduces RuleGNNs as a concrete application of the proposed method and evaluates its performance against a few other SOTA methods. Empirical studies show competitive performance of RuleGNNs compared with other alternative methods.

Strengths

- The idea of having dynamic rule-based layers in a neural network and especially for graph neural network learning is interesting. Although some existing methods in the literature including WL labeling could be considered doing the same, the proposed method builds on top of these building blocks and extends their ideas. - Theoretical discussions in the paper and the assumptions behind them are clear. - Experimental results cover an adequate set of alternative methods.

Weaknesses

- The performance of RuleGNNs is expected to heavily rely on the quality of the rules generated from additional information or domain knowledge, however, the paper solely focuses on application of such rules without adequately discussing the challenges of building quality rules and feasibility of this fundamental step in the proposed method. - Lack of clarity around how rules in RuleGNNs look like and how they can influence learning model parameters. - Experimental results are not fully discussed. For example, WL-Kernel shows superior performance in three data sets and it would have been useful to provide more insights about what data set characteristics contribute to this.

Questions

As stated under the weaknesses section, the main question from the reviewer is about where (i.e. for what type of data sets) one can expect RuleGNNs to outperform other alternatives methods, especially WL-Kernel which shows promising results and superior performance in a few tested data sets.

Rating

4

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Authors have adequately addressed the limitations of their work by listing the following limitations: - They have only considered 1 dimensional input signals and labels. - They have not considered graphs with multi-dimensional node features. - Edge features are not considered. - Computation and storage limitation for large/dense graphs. In addition, authors have clearly discussed structure, Combinatorics, and Implementation limitations of their work.

Summary

This paper proposes a novel model architecture rule-based layer, which induces different parameters given different inputs. Theoretical analysis demonstrates how the proposed architecture reduces back to classical feed-forward layers, and empirical results on both synthetic and real-world data sets demonstrate that the proposed method can improve upon existing works.

Strengths

The idea of rule-based layers and rule-based GNN is novel and interesting.

Weaknesses

- The implementation in this work may need further elaboration to make the proposed method easier to understand. - Empirical results may need further improvements to better support the proposed method.

Questions

- The notations may require further explanation. Regarding the “additional information” $I$ introduced in Section 2, how do we assume the additional information can be used to derive a set of static or dynamic rules $R$? While the authors provide some rule examples in Appendix A.4, it would be better if the authors can provide some examples on the additional information as well. - Also, how can we actually derive rules from the “additional information”? Do we need to manually design some rules or we need to apply some learning algorithms? While the authors claim it may not be the main focus of this paper, some clarification may still be needed to better understand the proposed method. - I am also confused on how we obtain the parameters for the proposed rule-based GNN. Basically, compared with standard GNN models, I suppose the rules in $R$ enable us to use different parameters for different input $x$. Then do we simply learn these parameters by standard stochastic optimizers? The authors may need to explain more on that. - While the proposed method seems to yield significant improvements in Table 2, the improvement in Table 1 for real-world data sets on the contrary seems quite marginal. As such, are there any other advantages of the proposed method compared with baseline methods in these tables? The authors may need to add more explanations on that. - It seems also confusing why the authors do not explicitly mention the rules used for experiments in Table 1 and 2, which should be essential to understand how the proposed method performs well on these data sets. - Moreover, no ablation studies or hyper-parameter sensitivity analysis is present in current submission. How do different rules (if they are manually set) or different learning algorithms affect the performance of proposed method? Such results and discussion are certainly needed to better understand the proposed method.

Rating

3

Confidence

3

Soundness

2

Presentation

1

Contribution

2

Limitations

The authors discuss about possible limitations in the conclusion part, and no direct negative societal impact exists for this work from my perspective.

Summary

This paper introduces rule-based (dynamic) neural network layers. The basic idea is to have a common set of parameters, i.e., weights and biases, where, depending on a certain rule, only a subset of these parameters are used in the forward pass. They show that certain fully connected and convolutional layers can be regarded as a type of static rule-based neural network layer. In the remainder of the paper, the authors introduce three dynamic rules for graph classification tasks and perform experiments on synthetic and real-world datasets.

Strengths

Overall, the concept of using rules based on expert knowledge to select different subsets of weights for various data samples or tasks seems useful and promising. This approach could offer significant benefits, such as training the same model on different tasks or on different datasets. Moreover, an approach which is able to learn on variably sized input data could be valuable on its own. The proposed rule-based layers for graph classification tasks outperform standard message-passing graph neural networks on synthetic and real-word datasets.

Weaknesses

One of my primary concerns is that the main theoretical result of the paper, Theorem 1, is not proven. Specifically, while the authors show in Prop. 1 and Prop. 2 that fully connected layers _without bias_ and convolutional layers _without bias, padding, stride of one, and quadratic kernels_ can be expressed using their proposed (static) rule-based layer, the following paragraph leading to Theorem 1 claims this can be generalized to arbitrary convolutional layers. Although this might be straightforward to prove (and could be included in the appendix), the lack of a complete and formal proof severely undermines the soundness of the submission. If Theorem 1 is intended as a summary of Proposition 1 and Proposition 2, I suggest making this explicit by clearly stating the specific types of FC and CNN layers and renaming Theorem 1 to Corollary 1, or merging Prop. 1 and Prop. 2 into Theorem 1. Moreover, while the paper introduces some mathematical framework and formalizes existing concepts within this framework, it lacks proofs demonstrating what this framework can achieve and fails to establish connections to existing work. Given the lack of substantial theory, I think a more thorough empirical investigation could strengthen the submission. Comparisons with more expressive architectures are missing (e.g., in Table 1 there are no results reported for more expressive architectures for almost half of the datasets; for the synthetic datasets no comparison is done with more expressive architectures), making it difficult to appreciate the practical advantages of using the rule-based layers in practice. The practical relevance is limited further by the fact that the rule-based layer can only process one-dimensional features, and the higher space complexity for dense graphs. Regarding clarity, there is considerable room for improvement. The concept of how a rule-based layer works was not fully clear to me until page 4. If my understanding is correct, we have a matrix $\mathcal{W}$ that contains all possible weights (and similarly a bias vector $\mathcal{B}$ with all possible biases). A rule restricts $\mathcal{W}$ to a subset of weights; applying rule *R* means setting some entries in $\mathcal{W}$ to zero. If my understanding is incorrect, this indicates that the writing lacks some clarity. I suggest shortening the introduction and preliminaries, which are at times verbose, and including a briefer example from Appendix A.4 earlier in the paper, or providing a clearer definition sooner. Additionally, the notation for the rule-based layer presentation is somewhat convoluted. The readability of the paper is also hindered by the inconsistent use of formal definitions and natural language. While both approaches can be fine (as long as they are precise), there is a noticeable mismatch between the rigor in the preliminaries and, for example, Section 4. Many aspects of the paper are thus unclear; please refer to the *Questions* and *Minor Remarks* for specific examples. Overall, I think this paper presents promising ideas in a preliminary manner. As also stated by the authors, the dynamic rule-based layer seems to be reasonable for graphs, but is more difficult to devise for other structures. One approach could be to revise the paper from a graph learning perspective, and, if the authors have novel results which hold for general structures, present these results in a follow-up paper. Another exciting direction could be to use rules to create flexible machine learning models for different tasks and input data. *Minor remarks*: * line 33: each new information -> each new piece of information * line 34: the essence -> a bit vague, what is the essence of dynamic NNs? * Fig. 1 is too small and difficult to parse in general; there is also and typo in the last sentence * line 75: dot missing after end of sentence * line 95: concatentation -> should this be "composition"? * line 111: dot missing after end of sentence * Somewhat inflationary use of "respectively" * line 123, 140: I would strongly advise to not use $y$ here for $x, y \in D$, as $y$ is already used to denote labels earlier * It would be helpful to refer to equations as eq. (1) (instead of just (1)) * Could it simplify presentation if you define $\Theta$ as tuple $(\mathcal{W}, \mathcal{B})$? * Last sentence of Prop. 1 is difficult to read * Why do we call the learnable parameters $\Theta$ in Prop. 1 and $W^i$ in Prop. 2? * line 190: higher dimensions -> higher dimensional * line 202: network -> network architecture * lines 206-214: I suggest to consider moving this to the preliminaries * line 221: either rule function (singular) or rule functions R_W, R_B * line 225: circle -> cycle * Prop. 3: "its" -> not clear what it refers to * line 231: If R permutation-equivariant -> language sounds off, maybe "For permutation-equivariant R" or "If R is permutation-equivariant" * line 255: typo in isomorphism * Pattern counting rule: $d$ is never defined * line 347: missing space

Questions

1. Is it possible to encode multiple rules into one layer? E.g., if a rule consists of a conjunction, are there beneftis/downsides to encoding the conjuncts in different layers or all in one? 2. Could you give more examples of how to exploit the fact that dynamic layers allow for arbitrarily sized input (beyond graphs)? 3. Could you elaborate on the precise meaning of "injective based on the labels and an additionally defined shared property"? 4. Does the presented approach allow to combine different data types/modalities and train them in the same network (towards, e.g., in-context learning)? 5. Did you experiment on strongly regular graphs? The ability to count cycles is helpful for that graph class and it could give some information about the expressivity of the rule-based graph layers. 6. Line 258: "We compute all possible embeddings". What does embedding refer to here? 7. Could you put your work into context with other modular (dynamic) neural network approaches (e.g., https://arxiv.org/pdf/1910.04915 or https://arxiv.org/pdf/2010.02066). 8. What happens if we want to classify a new sample, but we do not know what rule to use. How can we use the proposed approach in this scenario?

Rating

3

Confidence

4

Soundness

1

Presentation

1

Contribution

2

Limitations

One of the main limitations, as the authors point out themselves, is that their proposed rule-based layer can only process one-dimensional node features, and no edge features, which impacts the practical value of their method. For more limitations, please refer to *Weaknesses* and *Questions*.

Summary

The authors develop a broad framework for adding expert knowledge to Neural Networks. They formalize this by extending the learnable parameterized functions with an additional parameter consisting of the set of formal rules. In general, these rules maybe learnable as well. However, the authors focuses on these rules being given in the form of expert-knowledge. The authors then introduce the set of rule based layers. And shows that fully connected NN layers and CNN layers are special cases of the rule based layers. They introduce three rule based layers for graphs: Weisfeiler-Leman Layer, Pattern-Counting layer and Aggregation layer. The author shows that there exists a GNN with rule based layers that can distinguish any two isomorphic graphs. Finally the author introduces some examples of rule based layers for specific molecule graphs. And presents experimental results on synthetic and real-world data.

Strengths

-- The idea of adding expert knowledge to NNs and GNNs specifically is quite interesting and widely investigated. -- The presented theory is very general and simple

Weaknesses

-- The author has used the notion of rules rather broadly. There is no formal language (logic or matrix language) for the rules. They are just arbitrary functions. This basically means that any existing NN model, in one way or another, can be seen as a special case of Rule based NN. In my understanding, this makes the introduced framework a rather simple formalization of how expert knowledge maybe added to NNs. However, this formalization is so loose, that it does not really admit any meaningful analysis or provide any meaningful guidance to the user for adding knowledge. -- None of the examples presented by the author are beyond what would be anyway possible by adding some simple graph features to the node features. This could be an interesting direction to investigate. But just formally stating that this is possible is not very interesting.

Questions

How does your framework help a practitioner, in a meaningful way, more than just augmenting feature vectors in GNNs with expert knowledge? How does your framework enable any new theoretical analysis of GNNs?

Rating

3

Confidence

3

Soundness

3

Presentation

1

Contribution

1

Limitations

The authors have indeed touched upon most of the points I mention as weaknesses. However, as mentioned earlier, the proposed framework is very broad and does not provide a meaningful way to proceed.

Thanks for the rebuttal

I thank the authors for the detailed response. My fundamental concern regarding the paper remains that the paper does not really present a meaningful, designable or interpretable notion of rules. For instance Figure 1 and Figure 6 (as pointed in the rebuttal), in my understanding, do not aid interpretability. Furthermore, Example in Figure 6 has a rather simple underlying rule, and the paper's method does not make this easily accessible to the user. Finally, I maybe wrong about comparing paper's method to simply adding node features. But I really have difficulty in understanding how this method helps in adding expert knowledge besides cases where one can easily spell out small amounts of expert knowledge already in some other way or form (eg. additional node features, additional subgraph count or distance oracles with learnable weights). This is also reflected in the paper's exceptional performance in Table 2, where all relevant knowledge is known before hand, and moreover it is known how to express it easily. In real-world cases, as indicated in some experiments in the appendix A.7, it is not always easy to find meaningful rules that lead to improvements. Furthermore, you also mention that the number of learnable parameters are high, but all of them are not used. This definitely hurts interpretability and I am not sure how easy or meaningful is deciding the threshold for weights with small absolute value (as mentioned in the appendix). As mentioned in the rebuttal: - The paper is not aimed at practitioners. - The paper does not provide a general method to translate existing expert knowledge into rules that can be incorporated into NNs. Finally, in my understanding, the paper's methods cannot extract meaningful expert knowledge beyond what is possible by normal data analysis/visualization techniques. Regarding the ambivalence in my review, it stems from a general appreciation of the idea of adding expert knowledge to NNs and rule learning in general. However, the paper does not deliver an impactful step in this direction.

Acknowledging your rebuttal

I would like to first thank the authors for your detailed response. I appreciate that you have proposed a general framework for rule-based GNN. My key concern is that the proposed framework largely depends on the rule, which depends too much on appropriate expert knowledge and makes the effectiveness of proposed method questionable. Suppose we have enough expert knowledge, why should we choose the proposed framework instead of other ways to inject such knowledge (as is also mentioned by reviwer 9LgA)? Such dependency on expert knowledge is also partially reflected by results in Table 1 and Table 2, where the proposed framework achieves superior performance in Table 2 where rule can be directly induced, but not so in Table 1. Based on such concern and checking the reviews from other reviewers as well as your reply to them, I decided to keep my score and hope the authors can further improve the proposed framework based on current reviews.