Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work presents a combination of techniques for learning and probabilistic reasoning over databases to improve visual question answering (and reasoning) performance. A perception model reads the visual input and converts it into an interpretable format (which can be, e.g., a probabilistic database or a scene graph) that is then used for probabilistic reasoning together with a (fixed) knowledge graph. This reasoning produces the top-k explanations for a result.
main_review: Pros:
+ Interesting approach and combination of techniques: The paper combines probabilistic reasoning over knowledge graphs, datalog, weighted model counting, and deep learning (for the perception parts) in a meaningful way. On the technical level this is quite an achievement.
+ Significant gains on benchmarks that involve image recognition and simple reasoning steps.
+ Reasonable scalability: costly algorithms, such as weighted model counting, are applied in a way that does not immediately limit the scalability.

Cons:
- Complexity of the approach: The approach combines knowledge graphs, datalog, weighted model counting and backprop. This means that there are many moving parts and it is hard for me to understand how the system could be applied to a new task.
- Significant parts of the architecture have to be adapted to each task (scene graphs, logic programs matching the task).
- toy benchmark/custom benchmark; claims to be real-world task, but I'm not totally convinced it is
- The paper highlights the introduction of a tunable parameter as a contribution, which I find confusing: I prefer methods that have fewer (hyper)parameters that I have to tune.

The writing style is okay, but many parts could be written in a more concrete way. Some examples:
- Many claims are very general and abstract, and while reading the paper I often missed concrete evidence for claims. E.g. the first two sentences of the abstract.
- The introduction would benefit from clarifications on what the terms "proof", "provenance", and "reasoning granularity" mean exactly in the context of this work.
- The introduction promises an evaluation on a "real-world task", but does not go into what this task is.

Questions to the authors:
- I do not fully understand the VQAR task and believe some crucial details are missing: what exactly are the inputs and what does your model predict? In particular, I wonder about the scene graph. In the introduction you write that the scene graph has to be predicted by the vision model; how exactly does this work?
- How did you split the data into train/test for the VQAR task? Do the queries from the train and test set share the same pictures?
- Scalability: The paper claims to present a scalable method, but there are no experiments on how well it scales with the size of the knowledge graph, the queries, or images. Do I understand correctly that the main claim is that the method scales better than DPL? Could you discuss the limits of scalability?
- The examples in Figure 1 look like you just need DNF counting instead of WMC counting? Why do you need WMC?

Nitpicks:
- line 78, 79: "WMC is at least #P-complete" -> should be either "is at least #P hard" or "is #P complete". Also, your approach does not need to solve WMC exactly, but approximate solutions are sufficient. Then the problem is not #P hard anymore. See works by Kuldeep Meel. However, this does not invalidate the underlying point that the authors want to make: WMC is a hard problem.
- Check the capitalization of acronyms in the references ...
limitations_and_societal_impact: None
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper presents a method for scaling probabilistic reasoning by using only the top-k proofs in computing the probability of each outcome. Their algorithm, Scallop, allows tuning k at both training and test time, allowing for larger k at training and smaller k at test (and therefore speedier inferences). Empirically, Scallop outperforms leading, contemporary methods on a challenging VQA task requiring multi-hop reasoning. Further, Scallop shows clear speed ups in training wall clock time with respect to typical neural logic programming approaches that do not perform Scallop's k-width beam search over proofs.
main_review: This paper introduces a straightforward idea for speeding up the inference time of differentiable probabilistic reasoning systems. The paper presents a clear formalism and theoretical justification for soundness of their core technique of a k-width beam search over proofs. The experimental section shows clear gains in wall-clock time for both training and inference compared to baselines, as well as Scallop's ability to generalize well to more challenging VQAR questions. Overall, I find the paper makes a compelling case for the benefits of this method. 

A few suggestions for improving understanding of this method:

- It would be revealing to look at which kinds of queries lead to incorrect outputs by Scallop, and whether these errors are due to errors in the differentiable layers or due to limiting the proof budget to *k*. The proportion of errors due to the latter is the real error rate that matters in comparison to baselines making use of the full set of proofs.
- Of course, it would be useful to know how sensitive Scallop is to various hyperparameters, and importantly, how learning rate and batch size might impact the best choice of k.
limitations_and_societal_impact: - The authors should address the issues of bias that can result in relying on automated decisions from a probabilistic database, and that such systems ultimately rely on relational rules that can be highly biased.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors introduce a framework that combines neural modules for visual perception with a probabilistic model that computes the top-k proofs of objects being in images given a logical rule.
main_review: I find it difficult to evaluate this paper. While some literature exists with some similar approaches, [1] there is no direct comparison with other probabilistic methods that compute proofs and only a comparison with one method that uses knowledge graphs. While the authors use LXMERT to compare, they do this on their own task that they develop as an extension from GQA but they use a Recall@5 metric which makes the LXMERT results not interpretable to previous results on GQA.

**Originality**: It is not new to use some form of truncated proof evaluation to make methods like this computationally feasible. While top-k truncation[2] and learned truncation[1] have been employed to shorten the paths of proofs, I believe, as I understand the paper, that the authors include the top-k proofs in downstream computation to reduce the computational burden. To me, this seems to be a novel contribution -- albeit I am not sure this is true.

**Quality**: The quality of evidence that the authors provide for their method is poor. It is difficult to trust a new dataset that was designed for the author's method where the report results are a non-standard metric. The results would be much more trustworthy if they would be more closely tied to the existing literature (either in VQA, or some kind of neural theorem provers).

**Clarity**: The paper was easy to read and most details were clear to me.

**Significance**: The results vs LXMERT look impressive but I also find that it is difficult to interpret these results. As such, it is difficult to say how significant these results are truly are.

[1] Learning Reasoning Strategies in End-to-End Differentiable Proving
[2] End-to-End Differentiable Proving
limitations_and_societal_impact: Limitations and societal impact were not discussed. I do not believe the method has any negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes Scallop: a system for differentiable reasoning on probabilistic deductive databases. Scallop improves upon prior works in terms of scalability. Its core idea is to consider only top-k proofs rather than all proofs during deductive inferences. The method can be implemented efficiently leveraging provenance for deductive databases. Experiments on a synthetic addition task and a real-world VQA task show that Scallop outperforms baselines in speed and accuracy.
main_review: ## Strengths

+ Having to consider all proofs is a speed bottleneck for neuro-symbolic reasoning. This paper addresses it by keeping only the top-k proofs in each reasoning step. It is an intuitive and straightforward idea since many proofs have marginal effects on the score of the final answer.

+ The authors propose an elegant implementation for selecting top-k proofs using provenance—a mechanism developed in the deductive database community for attaching additional information to the derived facts. It enables using highly optimized off-the-shelf datalog solvers, without having to implement the inference algorithms from scratch. 

+ Experiments on 2 tasks show that Scallop achieves similar or better performance compared to baselines with significantly less time.


## Questions and Weaknesses

- The submission missed a few closely related works. Both [A] and [B] improve the scalability of Neural Theorem Provers [28]. Similar to this paper, they notice that having to consider all proofs is the speed bottleneck, and they try to solve it by using only some proofs. Though their methods are different from Scallop. I think it would be helpful to have a short discussion of them in the related work section.  In addition, researchers have used provenance for synthesizing datalog programs ([C]), which is a different task but could also be worth mentioning. 


[A] Minervini, Pasquale, et al. "Differentiable reasoning on large knowledge bases and natural language." Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 04. 2020.  
[B] Minervini, Pasquale, et al. "Learning reasoning strategies in end-to-end differentiable proving." International Conference on Machine Learning. PMLR, 2020.  
[C] Raghothaman, Mukund, et al. "Provenance-guided synthesis of Datalog programs." Proceedings of the ACM on Programming Languages 4.POPL (2019): 1-27.

- Experiments in this paper do not present sufficient evidence that Scallop is flexible enough for real-world applications. On both tasks, there is a lot of task-specific prior knowledge built into the model. For example, the datalog programs are manually constructed. What if there is an elephant in the image but "elephant" is not in the vocabulary of the datalog program? I understand that some of these issues cannot be solved easily in one paper, but I would suggest at least stating these limitations clearly in the paper. 

Experiments are narrow. Models have a lot of task-specific knowledge, e.g., manually constructed datalog programs. Compare with a baseline that sums the two numbers directly after classification.

- The paper lacks sufficient details about how gradients are computed in Eqn. 4. It looks like the authors are using dual numbers similarly to forward-mode AD. But it's not clear how dual numbers propagate through the inference procedure.

- The paper lacks sufficient details about the weighted model counting (WMC) procedure used for computing the score of the final answer. What is a WMC problem? Which WMC solver is used in the paper? Also, the paper says that scalability is limited by WMC solving (Line 78). I was surprised because I thought the limit was primarily in datalog solving. 

- What is the datalog solver used in this paper? In the example in Fig. 1, how is the predicate "+" defined in datalog? Is it a built-in operator of the datalog solver? 

- In Line 86, "a higher k ... accelerates the convergence of learning." Why?


## Comments on the Final Rating

I appreciate the idea of using only top-k proofs to speed up neuro-symbolic reasoning, and I think implementing it using provenance is a brilliant idea. However, the paper lacks details in many components, and the experiments are not as convincing as advertised in the intro. Therefore, I think the paper is not suitable for publication in its current form.
limitations_and_societal_impact: ## Technical Limitations

See my comments in "Questions and Weaknesses"

## Societal Impact

I do not see any potential negative societal impact.
review_title: null

Meta-review: Four knowledgeable reviewers praised the idea of combining forward chaining with differentiable and probabilistic programming to tackle tasks such as VQA where the combination of symbolic and sub-symbolic systems clearly pays off.

During the rebuttal, authors provided enough context and details to better cast the proposed Scallop into the literature and to better evaluate the experiments.

The paper is accepted, as it can spawn further discussion in the neuro-symbolic community about such an important research direction.
However, acceptance is conditional on the authors including all the promised (and discussed) details in the camera-ready. One additional point to clarify in the camera-ready is how Scallop differs from modern implementation of (Deep) ProbLog where essentially forward reasoning is used. 

Decision: Accept (Poster)