Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes extensions of Neural Logic Machines (NLM, Dong et al 2019) to make them more scalable. NLMs operate on dense hypergraph representations. Since the space requirement is exponential in terms of number of entities, NLMs become quickly intractable as the number of entities increase. To remedy this, this paper proposes a sparse tensor based representation for hyoeredge. The expand, reduce and permute operations are also defined for sparse tensors. To achieve sparsity in training, they include a sparse regularization objective (based on Hoyer measure). Lastly, they also employ a subgraph sampling technique based on information sufficiency. 

On synthetic family tree relationships, the proposed model solves the dataset and is the only model that scales to 2000 entities. Moreover they achieve the optimal sparsity (quadratic).
main_review: Strengths:

1. Developing models for hyperrelation is interesting and under explored. The main contribution of paper is to make neural logic machines practical and scalable which is important
2. The method is well-motivated. For example, the use of Hoyer measure and subgraph sampling and training with information sufficiency is interesting and makes sense
3. They achieve good results on a synthetic and few real world KG benchmarks

Questions for authors:

1. The current experiments (relation extraction) and family tree are all finding a binary relation between a pair of entities. Since the method is developed for hyperedges, why is there not an experiment where the goal is to infer relations between more than a pair of entities?
2. How is the arity set? For example, for the family tree experiemnts, how did you come up with value 3? Is it set as a hyperparameter. 
3. In table 1, why does not memory networks scaled to 2000 objects? Is this an implementation issue?
4. In table 1, what does tested on 100 objects mean? I thought the number of objects are 20 and 2000?
5. I think the writing of the paper needs to significantly improved. For example, Figure 1 is very hard to understand for a reader who is not familiar with NLMs. Also readability of Figure 2 can be improved by adding proper captions as that is the main figure explaining the mechanism of the model.
summary_of_the_review: This is definitely interesting work and I think efficiently modeling hyper-edges is important. However, currently, the paper is very dense to read and needs to be improved. I would also like to see an experiment on inferring relations that exists between more than a pair of entities. 

=====Update 11/26=======

Thank you for the rebuttal. I am keeping my score to weak accept.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Motivated by an observation that in logical reasoning, rules only apply locally and sparsely to a small set of entities, the authors propose Sparse and Local Neural Logic Machines (SpaLoc), a structured neural network for hypergraph reasoning. In particular, this paper has three contributions:

1) the authors developed a way to do sparse tensor representation to alleviate the computation burden in NLM
2) use hyperedge gates to enforce sparsity and impose sparsity-related loss
3) a novel strategy to do subgraph sampling that leverages a metric they invented called information sufficiency

Also showed positive experimental results compared to baseline methods and provided some ablation studies.
main_review: strengths:
1) The study is based on a very nice observation that in logical reasoning we don't usually consider all entities but rather a local set of them, and the authors developed a novel method motivated by this observation that could improve efficiency by a lot.
2) the methods are sensible, from the sparse tensor representation to subgraph sampling to label calibration, all of which I can follow intuitively.
3) the experimental results looked very strong, especially on the synthetic datasets, which solved a large amount of instances that could not be solved by other methods given a fixed amount of memory budgets.

weakness:
The main problem I have for this paper is its presentation.  Specifically, the authors should improve on describing their methods and there is a lack of very important details in the experiments (even in the main part).
1) In figure 1(i), it's hard for me to tell why I+V should have a fixed length..  the first dimension of V decreases when the first dimension of I increases?
2) One of the most important claims in the paper is efficiency.  However, the authors are missing key details: for example, when the baseline methods hit OOM, what memory budgets did the authors put?  The authors also claim efficient inference time in various places, but not single empirical evidence is presented in the experiments section.
3) The new method achieves such amazing results on the synthetic datasets, but no single details are presented on the dataset was generated.

small comments:
1) the authors refer to fig 1b and fig 2b, but in both the figures, there are no sub-labeling
2) In fig 1, it's better add caption explaining what are I and V matrices
summary_of_the_review: The paper is strong overall in terms of novelty of the methods and good main experimental results.  However, I would really like the authors to improve on the presentation of this paper.  In general, I lean towards accepting this paper, but in order for me to improve the score I need to see more details on their new methods are efficient in terms of time and memory and how the synthetic dataset is generated.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes SpaLoc a Neural Logic Machine variant that improves the model scalability on the graph completion tasks. To do this, the authors 1) replace the original dense representation into sparse tensors; 2) apply a sparsity regularization on the original loss function; 3) propose a sub-sampling strategy that reduces the training complexity. The proposed method is evaluated with a set of differentiable ILP methods and GNN methods. Ablation studies are conducted to analyze the effectiveness of the proposed techniques.

main_review: As stated in the summary, this work proposes an NLM variant that seeks to solve the scalability issue. The proposed techniques are: using sparse representation, applying sparsity regularization, and using sub-graph sampling. These techniques do not pose significant changes to the original NLM model nor extend the model's capability in learning new classes of patterns. Furthermore, the techniques are specifically designed for the NLM, limiting the scope of this work. With that being said, I consider this work more or less incremental whose contribution is minor and limited. Therefore, I'm inclined to reject. My detailed comments are as follows:

The paper is difficult to read if the reader is unfamiliar with the NLM model
 - While this paper proposes a direct variant of NLM, it omits too many details on the original model. Personally, I'm not hindered by the writing as I'm familiar with NLM, but this is generally not true for most of the audiences with general KG background knowledge.
 - For example, section 2.2 introduces the EXPAND, REDUCE and PERMUTE operations but does not point out these operations are from NLM and why they are needed for KG reasoning.

How is the sparsity threshold epsilon set? Do authors run a grid search and set it to 5%?

What is N_train in section 3.2?

As the aim of SpaLoc is to address the scalability issue, the author should design the experiments around the scalability analysis. For example, besides Table 2, the author could provide the runtime comparison of each method. On the other hand, while I understand the authors choose to use the disjoint subset of FB15K and WN18 from (Teru et al., 2020) for inductive reasoning, the datasets are significantly smaller than the original benchmarks. For example, the largest dataset FB15K v5 only contains 5K nodes and 33K edges whereas the original FB15K contains 14K nodes and 272K edges. As the focus of this work is scalability rather than inductive capability, it is crucial to push the proposed method to its limit and evaluate it in a realistic setting.

summary_of_the_review: In summary, SpaLoc is an incremental variant of the NLM model. The contribution is minor and limited to the specific NLM model. Therefore, I recommend rejection.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a neural network, SpaLoc, which claims to improve the scalability of an existing architecture, Neural Logic Machines (NLM) (Dong et al). 
The main idea of this paper is to exploit the sparseness of k-arity relationships that are represented as k dimensional dense tensors in Dong et al.  SpaLoc instead records the indices of non-zero entries and represents k-dim tensors as an (Index, Value) tuple (I,V) of 2 dimensional tensors, and redefines all the operations (Reduce, Expand and Permute) of NLM to suit the (I,V) representation. 
It applies an auxiliary loss term to ensure sparseness of the intermediate as well as the final relationship learnt. 
Finally, for efficient training (and inference), it relies on subgraph sampling techniques that are based on preserving the information content required to make a prediction. While training, they calibrate the prediction target based on the information lost due to subsampling.
They experiment on 2 tasks: synthetic family tree reasoning task, and  Knowledge Graph (KG) reasoning tasks. On synthetic data, they show that the original NLM fails to scale on very large families and a GNN based baseline (R-GCN) performs worse than SpaLoc. On inductive KG reasoning, it beats the existing methods.

main_review: **Strengths:**
1. Successfully able to scale NLM and demonstrate its effectiveness on 2 large-scale tasks.
2. Employ heuristics to encourage sparseness and efficient training: demonstrated through ablation as well. 
3. Quantification of information content in a subgraph, and efficient subgraph sampling based on it.

**Weaknesses:**
My main concern is with the experiments in the paper. Please see the ‘summary of the review’ for the details.

summary_of_the_review: It’s an incremental work, focused on scaling an existing method by converting a dense representation into a sparse representation. 

Even though the theory is for generic arity, the experiments involve only binary relations, and hence many complex GNN based methods can be used in addition to R-GCN. For example, Recurrent Relational Networks (RRN)  (Palm etal 2018) that work very well for multi-hop reasoning and scale well across the size of the graph.

**Running time:**  For the sparse (I,V) representation, how are the three basic operations (Reduce, expand, permute) performed using fast tensor operations on GPU? In my understanding, one downside of sparsifying the tensors is: indexing now needs to be handled separately, and can’t be done using fast GPU tensor operations. All the three basic operations of NLM may require dictionary lookups done on CPU, instead of GPU. Hence, even though sparse tensors for very high arity may now fit in the GPU memory, performing basic NLM operations may require frequent interaction with CPU, and hence dramatically increasing the training / inference time.  Can you provide a comparison of the running times of different baselines with that of SpaLoc?

Experimental details are missing. For example, what is the maximum arity used in the intermediate layers for KG experiments? How many layers for both tasks?
Many baselines have not been cited or mentioned, except the acronym in the table (e.g. TACT in table 2). 

**Clarification Questions:**

1. *Subgraph sampling:* The description for both sampling techniques (neighbor expansion and path sampler) focuses on 2 arity edges.
Specifically, in neighbor expansion, it appears that node set is expanded based on only binary relations? Are relations with higher arity used when expanding the node set? In path sampler, do you consider paths via edges of higher arity?

2. On page 6, under **Subgraph Sampling**:  "*During inference, usually our goal is to just infer the relationship between one pair of entities:*" In its original form, NLM would predict the relationship between all pairs of nodes as it works with dense representations. In SpaLoc, don’t we get all the non-zero entries, in the tensor of the desired arity, all at once in the forward pass?

3. *Section 2.3:*  How do you select hyperparameter \epsilon = 5%?

4. *Ablation study:* there is no ablation on ‘sparsification loss’. How important is it?


**Typos**

1. Page 2, Line 6: whether a predicate is true **for** some tuple of entities.

2. Section 2, 2nd line: why is V a  tuple?

3. Figure 2, Last row in the output of Permute and NN should be (3,4) and not (4,3)

4. References to Figures say Fig1b, Fig2b, but there are no parts a and b of the figures. For example, in the 1st line of section 2.2.

5. Section 2.2, page 4, in the 3rd line of the paragraph describing ‘EXPAND’, what is gF?

6. Section 2.2, page 4, equation in the description of ‘REDUCE’: if output of f is a vector, then shouldn’t it be a max pool (max across each dimension), instead of just max?

7. Page 4, last word: superscript should be (i,r) instead of (i,k)

8. Page 6, Information Sufficiency: You have defined S = (V_S, E_S), but you refer to S as H_S subsequently. Also, in the hyper-edge path, the subscript on the last node of the 2nd edge should be r_2 and not r_1.

9. Section 3.4: Ablation Study: it should be mentioned that all ablations are on synthetic family tree reasoning tasks.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper considers the task of inductive relation prediction: given a set of entities and relations, predict new types of relations. A specific example is: given a collection of people and the “is parent of” relation, predict the “is grandparent of” relation. The main contribution is a memory-efficient training and inference method for the Neural Logic Machines (NLM) [Dong et al., 2019]. For this, the paper presents a sparse tensor representation for the relations and add a loss term that encourages sparsity in intermediate layers and the output. Training on hypergraphs with many entities becomes computationally tractable (presumably on memory-limited GPUs), by sub-sampling the hypergraph (that represents the entities as nodes and relations as hyperedges). To deal with the situation in which vital nodes or hyperedges are removed during sampling, the paper introduces information sufficiency, a quantity used to scale the ground-truth labels.
main_review: ## Strengths and weaknesses
Strengths:
- The experiments in section 3.3 show strong predictive performance improvements over previous works
- Both the sparse tensor representation and the sub-sampling are interesting and sound methods for reducing the memory footprint of NLM during training
- The information sufficiency term for two nodes is computed as the fraction of hypergraph-paths that are retained in the sampled hypergraph, where a hypergraph-path generalizes the notion of paths in graphs to hypergraphs. This is a reasonable way to quantify the amount of information that is lost during sampling and the ablation demonstrates the effectiveness of using this during training.
- The paper is well written and legible for the most part.

Weaknesses:
- The premise of the paper is: training with many entities at once (20 vs 2000) is necessary or beneficial. This is not obvious, nor is it supported theoretically or empirically in the paper. For example, the experiment in section 3.2 compares against NLM by testing on 100 entities, when trained on 20 and 2000 entities. Since training with 20 entities already leads to perfect accuracy for NLM, it is not obvious why one would want to train with more. Furthermore, training the proposed model with more entities actually degrades the performance of the “HasSister” class.
- Section 3.3 “Real-world knowledge graph reasoning” does not describe the experimental setup, so I assume the experiments were done using the same setup as described in [Teru et al., 2020]. According to their description, this task is inductive in the entities only (nodes) and not the relations (edge types), meaning that there are no new relations in the targets. This setting is markedly different from the experiment in 3.2 and requires explicit mention and discussion.
Furthermore, it is not obvious why NLM would not work in section 3.3 by training on smaller input sizes and extrapolating to larger test sizes.
- Section 2.3 presents a method that encourages sparsity in the intermediate and output hypergraphs. The paper claims that this speeds up inference on large graphs, without any further explanation or validation. An ablation and further discussions on the trade-offs are necessary to motivate the importance of the methods presented in this section.
- The Hoyer-Square measure is presented as a better sparsification loss than the Hoyer, L1, and L2 alternatives, without any empirical support. An ablation would help convince the reader.
- The information sufficiency (IS) term takes the hyperparameter tau that determines the maximum path length that is still considered in the computation of IS. This appears to be a crucial value to set correctly and warrants further discussion on how to pick it and mentions of the concrete values used in the experiments.

## Additional Feedback and Questions
- Much of the paper is written with the assumption that the reader is familiar with the NLM paper, making it less accessible to a broader audience. Some example points that should be explained in the paper: What are lifted rules? What are the hyperedge feature domains considered in this work? What are the S and D typically? What is the arity of considered relations and the intermediate layers.
- There are many details on the method and the experimental setups missing that require explanation in the paper or appendix. For example: What is gF in “... in gF by N times, creating …”? How does M change with the PERMUTE operation? What are the f_hat’s in Figure 4?
- The proposed method appears to beat previous methods on most benchmarks, but it is not clear why. One way to provide more clarity is to describe the most significant differences of the proposed approach with the baselines.
- The introduction claims that the NLM scales exponentially with the number of entities and presents a cubic example O(N^3) (that is not exponential in N). The exponential scaling claim appears wrong and should be polynomial instead.
- Miscellaneous: 
  - “Fig 1b”: there is no b
  - “L_g^(i,k)”: k should be r
  - “Let x be an arbitrary vector”: x_1, x_2, ... were already defined as the variables
  - “g^(i,r)”: this variable wasn’t introduced anywhere
  - “Sequence of k hyperedges”: mixing k and K here
  - Different notations (H’ and S) for the sampled hypergraph
  - “Label calibration..”: two dots 

summary_of_the_review: I recommend rejecting the paper: It is currently not apparent why one would want to use many entities during training, when it’s possible to train with few entities and extrapolate to many at test time. Furthermore, the good results reported in section 3.3 seem irrelevant, since the experiment actually performs a different task from "relational rule induction".

The paper contributes to a specific line of research, by extending the NLM [Dong et al., 2019] to larger input sizes. In general, the paper would significantly benefit from more justifications and explanations for the proposed methods. More details on the experiments are also essential for the reader to understand the results. The technical contribution consists of a combination of different existing methods or variations thereof, and the information sufficiency value which appears to be new. 

---

I thank the authors for the rebuttal and the additional ablation study and details on the hyperparameter tau. I keep my score at 3, because in my opinion the need of training with larger input graphs is insufficiently covered. In particular, the datasets reported in Table 2 are based on *sub-sampled* graphs, as described in Appendix F of [Teru et al., 2020]. This means that it is possible to train NLM on the KG datasets considered in this work, by simply applying the same sub-sampling strategy with fewer roots. The new results in Table 3 also do not support this point, since it looks like that training with the complete KG (instead of subgraphs v1, v2..) does not improve the performance.
review_title: null

Meta-review: This paper has conflicting reviews with no strong advocate.  One of the positive reviewers states the caveat that paper is "very dense to read and needs to be improved".  Having looked at the paper myself I would agree with this criticism.  One of the negative reviewers states that the paper gives "an incremental variant of the NLM model".  I am less confident in this judgement.  However, I find the density of the paper and the use of synthetic data to be significant drawbacks. With the lack of any real champions for the paper I do not see a path to acceptance.
Decision: Reject