Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper explores the expressiveness of neural network-based relational learning models, such as graph neural networks and Transformer. To this end, a rational neural network is built upon the hypergraph structures to unify different models. Synthetic datasets are used for performance evaluation.
main_review: Strengths:
The studied problem of improving the representation and model generalization ability is important for many relational learning tasks.

The theoretical discussion of the unified relational learning framework is provided with theoretical analysis results.

Weaknesses:

State-of-the-art relational learning models are missing in the performance comparison, which can hardly demonstrate the effectiveness of the new learning framework. For example, the new framework should be compared against state-of-the-art graph neural models for capturing graph structural relationships, and the Transformer-based sequence learning.

The model scalability should be investigated in the experiments. Since the new model is built over the hypergraph structure, how is the time complexity of the hypergraph-guided relational learning should be investigated.

Lack of detailed description with respect to hyperparameter tuning strategies on the new proposed framework. Different hyperparameter selection may provide different prediction performance, which has been demonstrated in previous research work on graph neural networks and Transformer. It is necessary to present how the models are tuned to achieve good performance under a fair experimental setting.
summary_of_the_review: Several concerns for this work: (1) Key experimental setting information is missing in the evaluation section. (2) Many state-of-the-art relational learning methods are missing. (3) For fair evaluation, it is better to present the hyperparameter tuning for the new method.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper presents a new generic framework of relational neural network defined over hypergraphs, which they call RelNN. RelNNs take an architecture which hierarchically operates on representation functions of node tuples of different sizes and can be stacked into multiple layers. The framework is claimed to have unified graph neural network, neural logical machines and tranformers. The authors conduct analysis of RelNNs and show that its expressiveness increases as the artity or the number of RelNN layers grows sufficiently large. The paper also characterizes the generalizability of RelNN under certain conditions. 
main_review: Pros:
1.	The proposed hierarchical architecture of RelNN presents a novel angel to understand relational neural networks.
2.	Its proof on RelNN’s improved expressiveness with larger D and B seems correct, and it brings meaningfully new knowledge.

Cons:
1.	Questionable claim. RelNN’s claimed unification of GNN, Transformers, NLM seems far-fetched and lacks justification. It is true that most GNNs can be conceptually viewed as a message passing process involving successive updates of edge features and then of node features. While I have no problem with the resemblance, how GNN’s computation graph can be rigorously expressed using RelNN’s framework is completely unjustified. It would be very helpful to explicitly explain what each T_{i,j} in Fig. 1 refers to for at least two concrete instances of GNN (GCN and GAT for example), as is also the case with Transformer. The correctness of this claim on unification appears questionable to me before more details are confirmed.
2.	Limited Readability. Besides the first point, there are many other places where the reasoning seems ambiguous or even arbitrary with abused terms and typos. For example in Sec.2.1, it first defines hypergraph representation functions as X = {X_0, X_1, X_2 …} and then in the example right below it uses X = {X_2}, which contradicts; in the same subsection it mentions “hyperedge representation function Y on V”, which should be “hypergraph representation function Y on the set of all size-k tuples of V’s nodes”; In the third bullet point,  Y = {X_1} should be Y = {Y_1}. In sec. 2.2, the "j+1 dimension" should be (j+1)st and it should be clarified that the feature dimension is the last dimension of the tensor. There are many other such places throughout the paper. While some are easy to sort out the actual meaning based on context, some others take readers significant time to figure out or even to realize. Therefore, the general readability is very limited.  
3.	Experiments and Scalability. The paper claims main contribution on hypergraphs, but the experiments are limited to graph datasets only. Meanwhile, only n=80 is tested. Can RelNN work when n is large? It seems that RelNN struggles seriously with slightly larger graphs or hypergraphs with large hyperedges because of its node tuple definition. A thorough analysis here is very necessary. It also appears unclear what a 3-ary GNN is. Is that a realization of RelNN with B = 3? That also comes down to my first point what GNN is instantiated using RelNN.

summary_of_the_review: In summary, I appreciate that the authors make a great effort to unify several important relational neural networks. However, the paper suffers from its weak justification (on the claimed unification), lack of scalability, insufficient experiment, and ambiguous writing style in general. Therefore, I do not vote for its acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors present a framework to study the expressiveness and the generalisation capacity of a class of forward message passing algorithms that encompass graph neural networks, transformers and neural logic machines.   
main_review: On the positive side: 1) the authors introduce quite a general class of trainable models, and 2) they characterise the expressiveness and the generalisation capacity of these models. Noteworthy is the notion of quantifying the generalisation as a function of the size of the input test graphs. 
On the negative side: the theoretical analysis is not accompanied by an adequate empirical investigation. 
First of all, it is not clear if the graphs in the experiments are labelled or unlabelled: if they are labelled it would be of interest to report the label alphabet size and distribution; if the results refer to unlabelled graphs, it should be of interest to extend the experimentation to the more realistic case of labelled graphs.
Since one of the main contribution is the characterisation of the sample complexity and the generalisation to larger graphs, it would be appropriate to report an extensive experimental analysis of the alignment between theory and practice; it would therefore be of interest to report: 1) learning curves (i.e. reporting on the horizontal axis the training set size) to analyse the sample complexity behaviour in various scenarios  and 2) an analysis of the performance as the test set graphs size increases.
Presenting result on some more challenging tasks would also be of interest, e.g. a graph diameter regression task.
Please consider using an adequate testing of the significance of the result differences (e.g. following [Benavoli, Alessio, Giorgio Corani, Janez Demšar, and Marco Zaffalon. "Time for a change: a tutorial for comparing multiple classifiers through Bayesian analysis." The Journal of Machine Learning Research 18, no. 1 (2017): 2653-2688.] or using the library [https://github.com/sherbold/autorank]).
 
summary_of_the_review: The theoretical analysis is not accompanied by an adequate empirical investigation.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Neural Networks for relational data have been an active topic of research interest in recent years. There is still a lack of full understanding of the expressivity, generalisability of these models. The contributions of the paper are:
1) Development of relational neural networks (RelNNs) for (hyper)graphs that unify graph neural networks (GNNs), neural logical machines (NLMs), and transformers,
2) Analysis of the expressivity of RelNNs in terms of (i) maximum hyperedge size and (ii) depth of RelNN, and
3) A study of the generalisability of RelNNs to unseen test data.
main_review: 
### **Strengths**

1) The paper is well organised.
2) RelNNs unify three neural network architectures on relational data (GNNs, NLMs, Transformers).
3) The paper studies expressiveness and generalisability of RelNNs.


### **Weaknesses**

1) An important contribution claimed in the paper is that RelNNs can be applied to hypergraph reasoning tasks. However, all tasks in the experiments are graph-related (i.e., without hyperedges of size more than two). 
2) The experiments seem to not compare with existing methods, e.g., [Barcelo et al., ICLR'20]. Adding such a comparison would help making an empirical argument for why the results are significant.
3) All datasets are synthetically generated and it is unclear how the results of the paper can be generalised to real-world relational data (e.g., real-world graph classification problems such as molecule property prediction).
4) The synthetic datasets are tiny: all graphs contain fewer than 100 nodes.
5) There is no discussion of important prior work and it is unclear if RelNNs can generalise neural networks defined on hypergraphs. Some publications are listed below:
    1) Hypergraph Neural Networks, AAAI'19,
    2) HyperGCN: A New Method for Training Graph Convolutional Networks on Hypergraphs, NeurIPS'19,
    3) Hypergraph Convolution and Hypergraph Attention, Pattern Recognition'21,
    4) Hyper-SAGNN: a self-attention based graph neural network for hypergraphs, ICLR'20,
    5) Be More with Less: Hypergraph Attention Networks for Inductive Text Classification, EMNLP'20,
    6) UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks, IJCAI'21.
summary_of_the_review: Overall the paper is well organised with good theory. 
However, the main claims made in the paper need rigorous empirical evaluation.
Positioning with missing prior work and empirical evaluation on real-world hypergraph reasoning tasks would greatly improve the quality of the paper.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a unifying study of models for relational learning, namely Transformers, Graph Neural Networks (GNNs), and Neural Logic Machines (NLM), under the RelNN framework, and provides a series of results pertaining to their expressiveness relative to the arity of relations they support, as well as the depth, i.e., the number of iterations, they use during computation. In particular, arity and depth hierarchies are studied, and a set of arity and depth requirements are stated for a set of computational problems. Furthermore, the generalization ability of RelNN models is studied in the fixed-precision and infinite-precision settings. In the former setting, it is shown that there exists a finite size N for input graphs at which perfectly fitting all possible input graphs yields perfect generalization onto graphs of size greater than N. In the latter case, the sample complexity required to achieve certain error bounds is studied, and it is shown that more range-restricted aggregation function such as max and mean enable improved sample complexity. Finally, the paper conducts an experimental analysis on several synthetic problems, and achieves results validating the earlier provided arity and depth results for RelNN.
main_review: The paper offers an interesting perspective on relational models in that it studies them via a unifying framework. Moreover, it generalizes existing results beyond the binary setting into arbitrary arity settings. However, the results presented in the paper are not significant enough. Indeed, the proposed arity hierarchy is a simple generalization of existing expressiveness results as well as results on the WL hierarchy, and such results are not surprising, as they are already established, e.g., for higher-order GNNs [1], which study the higher-arity setting. Moreover, the depth and arity requirements provided in Table 1 follow easily from the FOC^k characterization, and thus do not offer any new insights in my opinion. To illustrate, connectedness can clearly be captured with B=3, as the general connectedness task can be written as a formula in FOC^3 (even just FO^3). By contrast, FOC^2 is not sufficient to capture connectedness, and this propagates to RelNN with B=2 and fixed depth. Moreover, all S-T problems can be easily solved with a depth n GNN, simply by propagating a ``beacon'' from S to N and seeing whether this reaches T after n hops. The proposed conjectures are also not rigorous enough, and do not provide further insights as to the power of RelNN models.

I also find that the RelNN framework does not produce any novel understanding of relational models. Indeed, the connection between, e.g., GNNs and Transformers is already well-established and studied in the literature [2], and the current study does not propose any novelty here. Furthermore, the experimental analysis is not convincing, and merely confirms the aforementioned simple results, and does not study the learning bounds part of the paper with sufficient detail. 

All in all, the paper makes a series of small contributions which, in my opinion, are not sufficient for publication. 

[1] Nicolas Keriven and Gabriel Peyre. Universal Invariant and Equivariant Graph Neural Networks, NeurIPS 2019.

[2] William L. Hamilton. Graph Representation Learning. Morgan and Claypool Publishers, 2020.
summary_of_the_review: The paper's main contributions and results, especially on the expressiveness side, are simple and already well-studied in the literature, and thus are not insightful or novel enough to warrant publication.
review_title: null

Meta-review: The paper aims to improve our understanding of GNNs for relational reasoning. In this regard, authors develop a conceptual framework unifying popular models (GNNs, Transformers, etc.) for analyzing their expressiveness and learning capacity. We thank the reviewers and authors for engaging in an active discussion. Based on author comments, the goal of the paper was more of a conceptual exposition, however this did not come across to the reviewers from the manuscript at first. Thus, a better presentation would definitely make the paper much more accessible and useful to the community. Moreover, there were some concerns about the significance of the exposition and better positioning would help (e.g., how the results help improve our understanding of GNNs). Thus, unfortunately I cannot recommend an acceptance of the paper in its current form.
Decision: Reject