Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning
Authors: Jiani Huang
Ziyang Li
Binghong Chen
Karan Samel
Mayur Naik
Le Song
Xujie Si
Venue: NeurIPS 2021 Poster (2021)
Keywords: probabilistic database
logic reasoning
neural symbolic

Abstract: Deep learning and symbolic reasoning are complementary techniques for an intelligent system. However, principled combinations of these techniques have limited scalability, rendering them ill-suited for real-world applications. We propose Scallop, a system that builds upon probabilistic deductive databases, to bridge this gap. The key insight underlying Scallop is a provenance framework that introduces a tunable parameter to specify the level of reasoning granularity. Scallop thereby i) generalizes exact probabilistic reasoning, ii) asymptotically reduces computational cost, and iii) provides relative accuracy guarantees. On a suite of tasks that involve mathematical and logical reasoning, Scallop scales significantly better without sacrificing accuracy compared to DeepProbLog, a principled neural logic programming approach. We also create and evaluate on a real-world Visual Question Answering (VQA) benchmark that requires multi-hop reasoning. Scallop outperforms two VQA-tailored models, a Neural Module Networks based and a transformer based model, by 12.42% and 21.66% respectively.


Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning
Jiani Huang University of Pennsylvania j sanihessess. upenn. edu
Ziyang Li
Binghong Chen
University of Pennsylvania liby998seas upenn. edu
Georgia Institute of Technology binghong@gatech. edu
Karan Samel
Mayur Naik
Georgia Institute of Technology ksamel@gatech. edu
University of Pennsylvania mhnaik@seas. upenn. edu
Le Song Georgia Institute of Technology 1songêcc. gatech. edu
Xujie Si McGill University and CIFAR Al Chair, Mila xsi@cs mofds..mgill.cm
Abstract
Deep learning and symbolic reasoning are complementary techniques for an intelli- gent system. However, principled combinations of these techniques are typically limited in scalability, rendering them ill-suited for real-world applications. We pro- pose Scallop, system that builds upon probabilistic deductive databases, bridge this gap. The key insight underlying Scallop is provenance framework that in- troduces tunable parameter to specify the level of reasoning granularity. Scallop thereby i) generalizes exact probabilistic reasoning, ii) asymptotically reduces computational cost, and iii) provides relative accuracy guarantees. On synthetic tasks involving mathematical and logical reasoning, Scallop scales significantly better without sacrificing accuracy compared DeepProbL.og, principled neural logic programming approach. Scallop also scales to newly created real-world Visual Question Answering (VQA) benchmark that requires multi-hop reasoning, achieving 84.22% accuracy and outperforming two VQA-tailored models based on Neural Module Networks and transformers by 12.42% and 21.66% respectively.
Introduction
Integrating deep learning and symbolic reasoning in principled manner into single effective system a fundamental problem in artificial intelligence [10]. Despite great potential in terms of accuracy, interpretability, and generalizability, is challenging scale differentiable reasoning in the combined system while preserving the benefits of the neural and symbolic sub-systems (28).
In this paper, we propose Scallop, a systematic and effective framework to address this problem. The key insight underlying Scallop is principled relaxation of exact probabilistic reasoning via parameter & that specifies the level of reasoning granularity. We observe that scalability is primarily hindered by reasoning about all proofs in computing the probability of each outcome, For a given Scallop only reasons about the top-k most likely proofs. which asymptotically reduces computational cost while providing formal accuracy guarantees relative to the exact instantiation. Scallop thereby generalizes exact probabilistic reasoning and enables easy exploration of rich space of tradcoffs.
Jiani Huang and Ziyang Li contributed equally to this work. "The source code of Scallop is available at https://github.co.. wttpjiih...o/ccallppppppppp cowm//callloolaggssclloooo-ooo/
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

This tradeoff mechanism allows to drastically speed up the stochastic training of the involved neural components without sacrificing generalization ability.
The main technical contribution of Scallop concerns computing the set of top-k proofs associated with each discrete fact efficiently, during the evaluation of logic program, and correctly, by maintaining all and only the top-k proofs. Scallop achieves this goal by formulating the problem in the framework of provenance for deductive databases [6] The framework provides the theory and algorithms for tagging discrete facts derived by a logic program with information our case the set of top-k proofs. Concretely, Scallop targets Datalog M. syntactic subset of Prolog. Although not Turing-come Turing-complete. Datalog supports recursion and is expressive enough for a wide variety of applications.
Scallop inherits efficient algorithms and optimizations from the databases literature. In contrast, efficiently computing top-k proofs for Prolog is an open problem, to our knowledge. Moreover, the provenance framework enables Scallop to provide correctness guarantees. We leverage the theory of provenance semirings [17), which allows to define how to compute top-k proofs in a compositional manner for each logic operation in Datalog. while ensuring that the computation is correct across arbitrary combinations of these operations. This approach also makes Scallop easy to extend with features such as additional logic operations, probabilistic rules, and foreign functions.
We evaluate Scallop on diverse tasks that involve combining perception with reasoning. On a suite of synthetic tasks that involve mathematical and logical reasoning over hand-written digits, Scallop scales significantly better without sacrificing accuracy compared to DeepProbLogg [24). a principled neural logic programming approach. We also create and evaluate on a werl-world task called VQAR (Visual Question Answering with Reasoning) which augments the VQA task with an external common-sense knowledge base for multi-hop reasoning. The goal to answer a programmatic question with the correct subset of objects in a real-world image. Scallop takes 92 hours to finish 15 training epochs with & = 10 and takes only 0.3 seconds on average per training sample. In contrast, a difficult training sample can take DecpProbLog over 100 hours to compute, making it infeasible to train on the whole dataset. Scallop's 's differentiable symbolic reasoning pipeline enables it to achieve 84.22% test accuracy, outperforming two VQA-tailored neural models based on Neural Modulc Networks and transformers by 12.42% and 21 .66% respectively.
In summary, the main contributions of this paper are as follows:
1. We introduce the notion of top-k proofs which generalizes exact probabilistic reasoning, asymp- totically reduces computational cost, and provides relative accuracy guarantees.
2. We design and implement a framework, Scallop, which introduces tunable parameter k and efficiently implements the computation of top-k proofs using provenance in Datalog.
3. We empirically evaluate Scallop on synthetic tasks as well as a real-world task, VQA with multi-hop reasoning, and demonstrate that it significantly outperforms baselines.
2 Illustrative Overview
We illustrate our approach using two tasks: a simple task called sum2 and the real-world VQAR task.
Simple Task. The sum2 task from 24 concerns classifying sums from pairs of hand-writter
digits, e.g., 3 + = 10. As depicted in Figure [ we specify this task using a neural and symbolic component, following the style of DeepProbLogg 24). The neural component is perception model that takes in an image of hand- writter digit (20] and classifies it into discrete values {0, (o..... 9}. The symbolic component, on the other hand, is logic program Datalog for computing the resulting sum. The interface between the neural and symbolic components is probabilistic database which associates each candidate output of the perception model with a probability. For instance, the fact 0.85 :: d 3) denotes that image is recognized to be the digit 3 with probability 0.85.
Evaluating the logic program on the probabilistic database yields a weighted boolean formula for each possible result of the sum of two digits, i.e., values in the range ( 18]. Each clause of such a formula represents a different proof of the corresponding result. For instance, the bottom left of Figure| [ shows the formula representing all 9 proofs of the ground truth result 10. Each such formula is input to an off-the-shelf weighted model counting (WMC) solver to yield the probability of the corresponding result, e.g., 0.7261 sum 3 7 10).
The scalability of this approach is limited in practice by WMC solving whose complexity is at least #P-hard [I. We observe that computing only the top-k most likely proofs bounds the size of each
formula to k clauses, thereby allowing to trade diminishing amounts of accuracy for large gains in
2

---

Toput
Perception Model
Probabllistic Database
( 0);
0. 1);
(.01::d(B,2)
0.
0.
0. 0.05::d(B,)) (B)
0.
6);
0.01::d (B, 7);
0.03::d(B88) .8;
0.01::((B,9)
0.05::d(
( 10;;
0.01::d
1);
0.01::d 2) 0.01::0(
0.01::0(B)) 4];
0.
5,;);
0.01::d
6);
0.85::0
8,71;
0.01::d0.
0.03:: .)
Logle Program
Expected Result
Sun(A, B, R) digitiA, M), digit(B, N), R
N.
sun (5), 19.8,1100 10)
Possible Recults and Proofs
Resalt
sum (5, 4)
Sun(B) 3)
suB (8)
Sun(S, Pl
(U) (4
sum (8) (0
likeyy
Proud
Lease Mool Phoof
Weighted Boolean Formala for sunt E3, (
Prohability of sue R2 F2, 10)
d(M, (R,.)
(weights not shown for bravity)
Pr F.. (10) 0.7225
(d00), 33 733 (dMM, v ( Ad
Prisun .10) 0.7230
d( vv (1
dim,, lttli..........llll.l....... 11) 9))
4
(d(2, d) (R) vv (d 6) () V d(BB, ( (1t_ve(_,22))d_ld___
(sum
P (003 0.7261
Figure 1: Illustraioon of approach on the task
3
10 using different values of parameter A.
Ieput Image and Objects
Graph
Kuswledge Graph
Natural Leagunge Question
hume
hurbivorrus
'Identify the tall on the left"
giratfe
jabakles >
mammell
unimal
Answer
ginafic
o12
grazs lané
Query Resalt
(o1get(o12)
nnaeeo, giraffel. 0.84: attrie2, tall). 0.85:: 1eftto12, o2). (53.11 faets in total)
1. as_algiraffe, rawalll iss_ Iaaanna, animal).
Programmattc Query
target(0) name antrall, leftio, ot), attrlo, talli.
nametO, hi z- naneto, Mt), is__ll', N). (3,380 adomss and 6 rula tocal
Figure 2: An instance of the VQAR task. The scene graph and knowledge base are shown graphically (above) and in Scallop (below). The question and answer are shown in natural language (above) and in Scallop (below).
scalability. Moreover, stochastic training of the deep perception models itself can tolerate noise in data. As we show later in our experiments, the additional noise introduced by the top-k approximation can be well-compensated for by the stochastic training algorithm.
Scallop embodies this insight by introducing a parameter & which can be task-dependent, and even for a particular task, tuned differently for learning and inference. A higher & leads to slower inference, but accelerates the convergence of learning, especially for complex or sparse feedback; thus, Scallop enables to achieve the best of both worlds by employing a higher l during training, and a lower thereafter. While Scallop's inference time is under 0. 1 second per task for the sum2 task regardless of the choice of k. the difference is much more pronounced for the sum3 task of adding three digits: 0.05 seconds for l versus 6. 15 seconds for k 15.
Visual Question Answering. We next illustrate applying Scallop complex real-world task, Visual Question Answering (VQA) [2], which is widely studied in the deep learning literature. The task concerns answering given question using knowledge from given image of scene. Since we are interested in tasks that combine perception with reasoning, we extend the VQA task with multi-hop reasoning over an external common-sense knowledge base. The resulting task, which we call VQAR, improves upon the VQA task in two important ways: it generalizes the VQA task by allowing questions that require external knowledge, and allows to precisely control the reasoning complexity through the number of hops needed to answer them. We thereby develop a new dataset consisting of hops of reasoning in a fixed external knowledge base.
images of scenes and object identification questions that necessitate varying
'n contrast, prior works such as the GQA dataset [8 are limited to varying the reasoning complexity in the question alone, which renders the question unweildy.
3

---

(Constant)
(Probability)
(Variable)
V
(Prob. Input Fact) (Disjunction)
p:: fii..ija
EF
(Term)
V c
EJ
(Predicate)
(Query)
(Atom)
(Fact)
a
a(c), Cn)
bn)
E G
(Query Result)
g
(Program) P (F, R. 2)
(Input Fact)
g
F
(Prob. Program) P (F,R,J.Q)
(Rule) a :-
Om
E R
Figure 3: Abstract syntax of probabilistic Datalog programs.
It is natural to express the VQAR task using a combination of neural and symbolic modules akin to the sum2 task. As Figure 2 illustrates, these modules are more complex, reflecting the real-world nature of this task. The neural module is a perception model that takes the object feature vectors (extracted by pre-trained vision models) and outputs a scene graph comprising the predicted name and attribute distributions of each object, and relationships between the objects alll of which are uniformly represented as a probabilistic database. For instance, the tuple 0.83 :: name giraffe) denotes that name of object o12 is classified as giraffe with probability 0.83.
I Likewise, the symbolic module uniformly represents both the logic representation of the question and the external knowledge base as a logic program in Datalog Evaluating the program on the probabilistic database yields the answer, e.g., (rrge((o12) The example in Figure highlights the need for external knowledge: although the question refers to the concept of an "animal" that is missing in the scene graph, Scallop is able to derive the conclusion name(ol2, animal) without changing the perception model. The derivation involves two-hop reasoning- two applications the recursive rule name(O, (O, N) name(O. N'), aN' N) to facts from the scene and knowledge graphs:
name(O12. giraffe) is ig.a(gie, mammal)
name(O12 (ome(0:..mamml))
is a (mammal, animal)
name(o12, animal)
While more sophisticated models can learn the representation of concepts such as animal from a large corpus, relying on such pretrained representation sacrifices the benefits of symbolic reasoning, such as interpretability, data efficiency, and generalization to unseen concepts.
Background
We recap Datalog, the logic programming language that underlies Scallop, and present its probabilistic extensions that we leverage for inference and training tasks.
Syntax of Datalog. As shown in Figure 3 a Datalog program P consists of a set of input facts F, a set of rules R. and query Q. The building block is atom a(1,,... ... ft,)) which consists of n-ary predicate a and a list of terms f1,... tn as arguments. A fact is an atom which all the argument terms constants; it may be input fact (EDB) or derived fact (IDB). Datalog rules are of the form a :- O1,-.., Om. meaning that atom a in the head is true all atoms or in the body are true. Multiple rules sharing single head predicate denote disjunction (or union).
Semantics of Datalog. Datalog programs can be executed using bottom-up evaluation strategy. Starting from the input facts F. we repeatedly apply the rules R in any order to derive new facts until fixed point is reached. Upon completion, we obtain all the output facts q of the query Q. For example, with F = (left(o), 02), below (02, 03)} and Q = left(o1, i O), the execution of program (F, 0, Q) produces {left(o1, 02)}. We denote the execution result Exec(P) {
Probabilistic Extensions. To handle uncertain data, we introduce two probabilistic extensions to Datalog, which are inspired by pD [15] and ProbLog [1I]. First, we specify probabilistic input facts f by associating probability p with f. declaring that Pr(f) = p. Deterministic input facts have probability 1.0. Secondly, we allow disjunctions J among probabilistic input facts, denoted by
f1:...: fm. For example, the disjunction
0.01 digit( 3. 0); 0.82 digit 3 3): 0.06 :: digit B 9).
states that the digit 3 is recognized to be 0 to 9 with their respective probabilities, but cannot be more than one simultancously. F and J form a probabilistic database. By combining the F, J with R and Q, we obtain a probabilistic Datalog program P.
WWe presume that the input question is in programmatic form because existing models for semantic parsing achieve high accuracy in translating from natural language text to programmatic form (

---

f namefon giraffe) (1)) S/. (063)
f2 aaaggiraeee, mammal)
[AN
fo
fi name(os, giraff) Sn {(6))
fa name(os, tiger)
namelais, mammal) Sy W1)
is (mammal, animal)
8,, [(6))
[OX]
S/2 (16))
[AND]
targettos] S.
4 namelorg animal)
Se (2.152
Figure 4: Proof constr. with conjunction.
Figure 5: Proof constr. with disjunction.
Probability Calculation. Unlike discrete Datalog, which provides definite answers queries, we wish to compute the success probability of each query result q: Exec(P) {(g, Pr(4)))== To compute success probabilities, we first define proof of any fact g as a minimal set of (probabilistic) input facts f that can derive g. We denote a proof as F E PPFF) where IP denotes power set. Since fact y may be explained by multiple proofs, we use Sy to denote the complete Given the set of proofs Sg for query result the success probability Pr(g) is simply the likelihood of Sq. denoted Pr(Sg), which can be computed using Weighted Model Counting (WMC) [9
of proofs of g.
Framework
Scallop aims to solve the following two problems:
1. Inference (Section 4.1 Given a probabilistic Datalog program P (F, R, J, 2), efficiently compute each query result y with its set of proofs Sy.-
2. Learning (Section 4.2 Given neural symbolic reasoning dataset D and loss function L. learn a perception model M3 which, for each (r E D, transforms æ into a probabilistic database captured by Datalog program Pø We aim minimize the following objective: (()) =
(Z.))eD (Exec(P(i)))
[D]
4.1 Inference
Proof Construction. The goal of our proof construction is to construct the set of proofs S₃ for every query result q. We can efficiently compute Sg during the bottom-up execution of the Datalog program. We initially tag each input fact f E F with 3 {{})} and propagate proofs during execution from known facts to newly derived facts.
We illustrate proof propagation during conjunction in Figure When is derived from a conjunction on fi and f2, we combine the sets of proofs S₁, and Sy, to produce Sy, The resulting Sy contains a single proof {Ji, f2). as both fi and /2 must be true for g to be true. More formally, we define binary operation @ corresponding to conjunction. Given two sets of proofs S₁ and S2, we have
S @ S2 {F F = Fi U F2, (Fi, F2) E S1 X S2, F contains no disjunction conflict].
(1)
We next illustrate proof propagation during disjunction in Figure Consider VQAR instance in which the query concerns identifying a target object that is either giraffe or a tiger. Sg contains two separate proofs, one containing only fi and the other containing only f2, as each can individually explain q. We thereby define a binary operation @ corresponding to disjunction, as set union:
S @ S₂ = S₁ U..
Equipped with @ and 8, we can show that the collection of sets of proofs S P(P((F) forms a semiring, which we call the proof semiring. Following [17], every derivable fact g can be annotated with a corresponding algebraic formula representing the bottom-up construction of Sy- Since the proof semiring is both commutative and distributive, we show in Appendix A. that Sq
D F derives St).
However, the complexity of Sy renders the computation infeasible. In principle, we have |.S.) (22 showing that [Sy] grows exponentially with the amount of input facts. The actual version of our example shown in geenrrttse 2,619 proofs in total for all query results, and takes 14 minutes execute. This scalability issue is further exacerbated when the system is used in learning setting, where we need to execute millions of such programs.
Top-k Proof Construction. The probabilistic nature of our problem setting opens up room for approximation. A key observation that, when the inference system is used in a learning setting, the probability of a ground truth fact should significantly outweigh other facts, forming a skewed distribution. We can exploit this property by only including the "most likely" proofs in S., with the likelihood of proof F defined by Pr(F)- II Pr(f).
5

---

name(O, animaal animao..
sabgosl(O) lefb/o,
0.83
0.68
0.62
0.77
0.71
6.69
Top-3 Nauual Jeto
683:
issettl, wolt)
0M awin.,
atrist sif)
samc(o2, snimull)
salessafoo)
(arged(()) in BamecO, saimmol, lebro, O') attr(O, tall).
0.57
1. aiginitf, animal 6.83 sonettll greffi a 8.92365022. ol) odtraatrs,
Pitse, sigiostt, oninal) 88 aseetoll giaffl) o ass-oe at) U'ooatrii aill
Linecl sigioitl, sniral) 0.33 Dineeooo), glart)) (.82-19fttd, o4) a.P4..utree, tall)
latee setrad) ne soetel tigen 692: ol) ast. tell
Lieele alwelf astmul) o 10 (ilomenee,, wolf 0.82:iffeez o4) 0.4ccatticc, tall)
other preehs...
targetto))
Figure 6: Illustration top-k natural join using k = 3. Each ellipse represents a proof of the fact shown in the box. Given the top proofs for each "name(og, animal)" " and "suhgoal(o3)" we wish to derive the top 3 proofs for their conjunction, "a2r)e((o2)". The join yields 9 possible proofs. After computing the likelihood for each of the 9 proofs, we keep the top 3 most likely ones (green ellipses) and discard the rest (white ellipses).
We thereby introduce a top-k proof inference algorithm. With a user-specified hyper ahperr-arameter le 2 1. we perform top-k filtering at each step of the proof construction. We define two new operations, ()) for conjunction, and @ (k) for disjunction:
(3) Intuitively, whenever or @ is performed, we rank proofs by their likelihood and preserve only the top-k proofs. This allows us to discard the vast majority of proofs and thus make inference tractable. An example run-through of top-3 natural join (8)) is depicted in Figure 6, where we perform a normal @ operation followed by top-3 filtering.
S1 ② (R) S2 = (Sp @ S2),
S (*) 52 = Top (S1 @ S2)-
As before, we construct a top-k proof semiring (Appendix A.2 with which we can express the resulting approximated beam of proofs S,, = + (k)
X JEP St). Note that the size of S, F derives
is bounded by k. |$111 O(k), reducing the exponential complexity of exact inference to near constant one. As a comparison point, with top-3 proof inference, the full example shown in Figure 2 only generates 39 proofs, taking only 0.5 seconds to execute. Formally, our approximation of the success probability of a given query result q can be written as Pr(g) Pr(S,) ~ Pr(S.))
Discussion. We present some desirable properties of our top-k inference algorithm. The approxima- tion error bound is given by PPr(S,) Pr(S,)) < Er e S,,S, Pr(F'), and we can tune k to control the trade-off between scalability and accuracy. Furthermore, if no disjunctions are specified (J O), then we have Sg = Top (S,). that is, the beam of proofs S.g contains the global top-k proofs. The theorems and proofs are provided in Appendix A.3
We also note that our top-k inference algorithm is reminiscent of beam search. Both methods are iterative and explore only the top-k elements at each step. However, there are two major differences that distinguish us from beam search. First, while beam search is heuristic, our algorithm is backed by Datalog semantics and the provenance semirings framework for its correctness. We also present formal guarantees on its approximation error bound. Secondly, our algorithm operates over the beam of proof's S, for each derived fact q, while beam search is usually performed to search for output.
4.2 Learning
At high level, we want to train a perception model Me that takes in an input and produces a probabilistic database (F,T), captured by program P. such that after execution, can derive the ground truth y as the output. Note that the probability of the input facts in the probabilistic database is generated by the perception model Ma. Therefore each input probability pt = Pr(f.) is also associated with their gradients VPi(t) with respect to the model parameters A.
To back propagre the gradients through the inference process, similar to DeepProbLogg 24 Scallop adopts a gradient semiring augmented WMC procedure, for which we use Sentential Decision Diagram (SDD) 9. The beam of proofs S, will be transformed into a weighted Conjunctive Normal Form (CNF) formula, where for each variable, St. we attach the dual number (Pr(Js), PP(()) as its weight. As a result, the associated differentiable probability of each query result gi will be (Pr(q.), VPr(a)), computed by WMC. With everything above, we define the execution of our

---

Scallop
Task
Goal Predicate
#Out
Max #Proofs
DPL
=
A 3
= 10
T1
sum2
8
7
10
19
10
97.46%
96.90%
96.67%
96.29%
96.82%
T2
sum3
8
7
5
15)
28
75
95.31%
95.43%
95.76%
95.76%
95.56%
T3
sum4
2
7
S
17)
37
670
47.11%
95.47%
95.31%
95.07%
14
sort2
7
0,
1
55
80.43%
91.55%
91.75%
95.49%
98.04%
15
sort3
2.
220
70.34%
93.20%
96.15%
97.09%
95.50%
sort4
3, 3,
715
68.67%
87.90%
92.02%
91.87%
89.96%
Table 1: Testing accuracy Scallop and DoepProbLog (DPL) on suite synthetic tasks. numbers
except = 1 have standard deviation of < 2%.
06
Diference with
Accurary
Sooley
8805
02-
Number Training Datapoints
Figure 7: Training runtime (in seconds) vs. valida- tion accuracy for task T2 (sum3).
Figure Difference accuracy of varying kiea com-
pared to keett 10 for task T2 (sum3).
probabilistic Datalog program
Exec(P) = ((a,, (Pr(a:); VPngg)))E
(4)
The results of the execution along with the ground truth y is passed to the given loss function L. Lastly, the loss back- paok-propagated to update the parameters the perception model Ma.
For example, the ground truth label for the task sum conceptually representing the set:
R) is binary vector dimension 19,
{0.0 sum
... 1.0 :: sum
10), 0.0 :: sum 3 7 18)}.
and the predicted ý is set of the 19 results associated with their predicted probabilities, represented as probability vector of dimension 19. In our experimental setup, we apply the binary cross entropy loss function the two vectors. In practice, however, the loss function is fully customizable.
Evaluation
We evaluate Scallop on suite of synthetic tasks and VQAR. All experiments are conducted on machine with two 20-core Intel Xeon CPUs, four GeForce RTX 2080 Ti GPUs, and 768 GB RAM. Experimental details such as hyperparameter selection and dataset splits are provided Appendix C and implementation details of the Scallop framework explained in Appendix D
5.1 Synthetic Tasks
We extend the synthetic tasks from DeepProbLog (DPL) demonstrate that (1) Scallop is much more scalable, (2) Scallop does not sacrifice accuracy, and (3) how different levels of reasoning granularity during training and testing phases can affect model performance.
Table synthetic tasks and their corresponding sample goal predicates. Each task takes as input multiple MNIST [20] images and requires performing simple arithmetic (T1-T3) or sorting (T4-T6) over digits depicted in the given images. The difficulty of each task reflected by third and fourth columns, which show the size of the output space and the maximum number of proofs per output, respectively. Our goal is train a digit classifier end-to-end with the combined perception + reasoning pipeline. We elaborate on individual tasks further in Appendix E
Accuracy. We show accuracy comparison with DPL in Table | All models are trained under the same learning setting. Scallop able to achieve on par accuracy as DPL, despite using far fewer proofs. It also shows that in general, larger & implies better accuracy. Note that we are unable to collect result for DPL. on T3, as DPL. takes 24 hours only to complete 100 out of the 15,000 training samples. In contrast, Scallop with & finishes 5 epochs (75,000 training samples) within 4 hours.
7

---

Validation Recalle5 (%%
LXMERT NMNs
Scallop
Test Dataset
LXMERT
NMNs
Scallop
100
1000 C2
66.75%
79.32%
85.17 %
80
1000 C3
61.69%
61.98%
82.82%
1000 C4
63.82%
71.17%
83.25 %
60
1000 C5
64.05%
74.62%
85.53% %
40
1000 C6
56.51%
72.04%
84.30 %
5000 Call
62.56%
71.80%
84.22% %
0
10
15
Epoch
Table 2:
Testing accuracy (in Recall@:5) of Scallop, NMNs, and LXMERT on VQAR dataset.
Figure Results of training on 50K Cau tasks and testing on 5000 tasks of different clause lengths.
Runtime vs. Accuracy. We next evaluate the tradeoff between the training runtime vs. testing accuracy in Scallop. Figure 7 shows the results for the sum3 task. With k = 1, Scallop learns the fastest in the beginning, but has high variance and potential of failing to converge an optimal solution. On the other hand, with k = 5, it has much less variance and converges the fastest despite being slower in the beginning. We compare with DPL trained under the same setting. It achieves the same accuracy (95.56%) at the end of the 3rd epoch, but due to its long runtime (14 hours), we omit showing the whole curve in this figure.
Decoupling Reasoning Granularity. Scallop enables using different is during training and testing phases. The key idea is that a larger l will help faster convergence in training, whereas a smaller k suffices during testing since less probable proofs have minimal impact on the reasoning result. In Figure X compute the difference in testing accuracy on kiest E (1,3,5) 5). The figure shows that as the training progresses, the difference converges to 0%. This suggests we can tune kimain and kiest individually for better training as well as faster test time inference.
we fix a kunin 10 on the sum3 task. Taking accuracy with hie = 10 as baseline, we
5.2 Visual Question Answering
We next evaluate Scallop on the VQAR task described in Section 2 Besides DPL, we compare with two neural methods: Neural Module Network (NMN) and LXMERT, a transformer based approach.
Dataset. The VQAR dataset contains (a) 80,178 images, (b) object feature vectors + bounding boxes, (c) scene graphs with 500 object names, 609 attributes, and 229 relationships. (d) a shared knowledge graph with 6 rules and 3K knowledge triplets, and (c) 4M programmatic queries and answer pairs. The images and scene graphs from the GQA [18] dataset and the knowledge graph is from the CRIC [16] dataset. The object feature vectors and bounding boxes are then obtained by passing the images through pre-trained fixed-weight Mask RCNN and ResNet models. Using random walk combined scene graph and external knowledge graph, we generate object identification questions in the form of programmatic queries. We further categorize these queries into different levels of difficulty by the number of occurring clauses from C2 to C6, where C2 is the simplest and C6 is the hardest. For each image, we generate 10 different question and answer pairs for each clause length 2 to 6, to obtain 4 million data points in total. We split the images randomly into training (60%) validation (10%), and testing (30%) sets. Further details of this dataset are provided in Appendix B
We formulate VQAR as a multi-label classification task. For each datapoint (2r, v) in our VQAR dataset, the input x consists of (a) the entire knowledge graph KG, (b) a programmatic query, and (c) the object feature vectors and bounding boxes. The ground truth y is the set of objects that the given programmatic query identifies, All of our evaluated models share this same set of input and output (except LXMERT, which takes in natural language questions instead of programmatic queries). The accuracy is measured by Recall@5.
Setup of Scallop. We use a perception module consisting of three MLP-classifen Ma Mā), which predict names, attributes, and relations respectively. All predictions are transformed into probabilistic facts in a database. The outputs of MA form disjunctions because each object has only one name. With KG as part of the probabilistic database, we perform Datalog execution on the given programmatic query to obtain the set of identified objects. Note that the entire knowledge graph is used every Datalog execution. We use binary cross entropy as our loss function to compare the predicted set of objects and the ground truth set. The goal is to train the three classifiers in Scallop end-to-end, and identify the correct objects according to the question.
Baseline DeepProbL.og. is prohibitively slow to train with DPL. from scratch-a a regular training sample from C6 can take DPL more than 100 hours to run. Therefore, instead of training
8

---

LXMERT DATALOG-RI RL NMNs Scallop
LXMERT DATALOG-RL
NMNs Scallop
80
Recalli@5 (%)
Recall
00
40
C3
C4
100
1000
10000
Test Dalasel
Training Data Size
Figure 10: Generalizability to harder questions when trained 10K C2.
Figure 11: Data efficiency given training data size from 10,000
the perception model My trained with Scallop test DPL's inference capability. With 10 seconds timeout, DPL. times out on 38.66% of the testing samples, while Scallop finishes all with average running time under 0.3 seconds per sample.
with DPL,
Neural Module Network approach for VQA with external common-sense knowledge. This method first pretrains TransE embedding
Baseline 2: Neural Module Network. We compare against RVC [6
3 for the knowledge graph. Then, mimic the reasoning process, trains set of neural modules that perform knowledge retrieval, scene graph traversal, and logical operations. The modules are assembled according the programmatic query and can leverage object-based features.
Baseline 3: LXMERT. We also compare LXMERT 333 recent transformer based approach that
emphasizes its transfer learning ability. LXMERT takes in natural language question corresponding the given programmatic query. Similar other baselines, the object features and bounding boxes are taken as input. Since this model cannot explicitly use knowledge base, we leverage the implicit relations learned through pre-training over variety of image-language tasks: MS COCO (22). Visual Genome 2 and GQA [18). Finally, we fine-tune LXMERT on our VQAR training samples.
Ablation Study: Datalog Reinforvement Learning (DATALOG-RLE RL). In this study, we remove the differentiability in Scallop's learning pipeline. Instead, we sample discrete scene graph, run through the standard Datalog execution, and use the overlap in predicted objects as a reward to estimate the gradient using REINFORCE (35). This method does not scale with the training dataset of 50K tasks, so we only perform the generalizability experiments (Figure IOP.
Results. Table and Figure Figure compares the performance of Scallop. NMNs, and LXMERT based on 50K training tasks. Scallop significantly outperforms both in terms accuracy and data efficiency. Figure shows that Scallop generalizes to answer more difficult questions (IK from each of C2-C6) even when trained on only the easiest ones (10K C2). Figure [T] on the other hand, shows the testing accuracy (on IK C2) when trained on varying dataset sizes (10, 100, 1000, and 10,000 C2). We observe that Scallop has the best data efficiency. Finally, with DATALOG-RO RL. we observe that the addition of differentiable reasoning is crucial to Scallop's learning performance.
Discussion and Limitations
Top-k hyper-parameter selection. The hyper-parameter k much easier to tune than traditional one due to its deterministic behavior. At training time, lower k means faster inference time, and higher means higher inference accuracy. Note that sometimes higher may lead to faster convergence than a lower k. That is because the higher k means more proofs will be considered during the weighted model counting process. Subsequently, more gradients will be back pook-propagated to the source, resulting in faster convergence of learning. At testing time, k merely affects whether we consider certain low probability proofs. Therefore it will likely have less impact on the prediction result. For both the synthetic tasks and the VQAR task we performed, we found k=5 to be a suitable default value that balances accuracy and training cost. In practice, the user may start with k= 5, then, increase or decrease this value to achieve higher accuracy or lower training cost, respectively.
Scaling to large knowledge bases. In the real world, incorporating a larger knowledge base is helpful to avoid failures due to incomplete knowledge base and vocabulary. We estimate the efficiency of Scallop with regards the sizes of the knowledge base. For the knowledge base with 3K triplets,

---

it takes Scallop 0.2 seconds on average to process one query. When we use a subset of the ConceptNet knowledge base comprising 250K triplets with the same Scallop implementation, the time consumption per query increased to 2 seconds. Although Scallop runs fast with non-trivial-sized knowledge bases, to incorporate an even larger knowledge base such as the entire ConceptNet (34M) or WikiDDaa (94M) will require system-level optimizations and is beyond the scope of this paper.
Programming interface. The Scallop framework provides a generic interface for performing differ- entiable logical inference. The input to our interface is (1) a probabilistic relational database (F,3 J) consisting of tuples with associated probabilities (with gradients) that encodes the output of the neural components, and (2) a set of Datalog rules R that specifies the logic reasoning components. The output is the probabilistic query results, which can be either used to calculate the loss directly or as the input to subsequent neural components. The Scallop framework is able to capture a variety of machine learning tasks such as the examples shown in Appendix G
Natural language questions. In our VQAR task, the query is given in its programmatic form. However, in the generic setup of the visual question and answering (VQA) task, a question is usually provided in its natural language form. To convert natural language question into its programmatic form, the user may need to train a separate model for semantic parsing. Automatically generating such a program with end-to-end reasoning using program synthesis, semantic parsing, or inductive logic programming techniques is an interesting but orthogonal future direction.
7 Related Work
Neural symbolic methods. Neural symbolic methodology aims to disentangle low-level perception from high-level reasoning systematically. Generically speaking, there are three classes of the neural symbolic method.
(1) Logic regularization term. Whenever the network fails to obey the logic constraint, it will receive penalty 36). (2) Soft logic program execution. The primitive operations in a logic program are mapped differentiable mathematical operations or neural components 14 [2] (3) Proof-guided probability calculation. Approaches like exact probability calculation and abductive reasoning first execute the logic program and then map the generated proof constructs into differentiable expressions
8 21 24).
Using logic constraints as regularization terms can scale, but does not guarantee the reasoning correctness. Substituting logic reasoning steps by differentiable components fails to preserve the original semantics of logic reasoning. Exact probability calculation, on the other hand, maintains the purity of the logic reasoning pipeline, but has significant scalability limitation. Most application- specific neural symbolic approaches fall in categories (1) and (2) due to their high-efficiency demand.
Scaling reasoning algorithms. Other neural symbolic methods have explored optimization strategies for their reasoning algorithms. Neural Theorem Prover (NTP) 30 considers all reasoning paths in the inference procedure. Due to its high computation cost, subsequent works focus on improving its scalability. For instance, Greedy NTP (26 keeps a beam of proof states using nearest neighbor search. Another notable example is Conditional Theorem Prover (27] which applies soft proof selection by training a neural network to select the rules, deriving proofs individually.
Forward and backward chaining. Methods such as Scallop and TensorL 7 apply forward chaining, reasoning method that derives conclusion from known facts and rules. In particular, Scallop employs Datalog and a probabilistic deductive database to derive all possible query results. This is as opposed to backward chaining methods, such as (Deep) and NTP, which start from the goals and work backwards to determine if any data supports the goal.
8 Conclusion and Future Work
We proposed Scallop, a framework for scaling differentiable reasoning based on Datalog, motivated by real-world applications that necessitate combining perception and reasoning. The key idea underlying Scallop is to relax exact probablistic reasoning via a tunable parameter that specifies the level of reasoning granularity. We demonstrated the effectiveness of Scallop on diverse tasks including a newly created Visual Question Answering benchmark that requires multi-hop reasoning. In future, we plan to develop expressive extensions to Scallop, target more challenging neuro-symbolic applications, and optimize the end-to-end pipeline modern hardware.
Acknowledgements. We thank our anonymous reviewers for valuable feedback. This research was supported by grants from ONR (#N00014-18.112021)) NSF (#2107429 and #1 #1836936), and the Canada CIFAR AI Chair Program.
10

---

References
[1] ABITEBOUL, S., HULL, R., AND VIANU, V. Foundations of Databases: The Logical Level, 1st ed. Pearson, 1994.
[2] ANTOL, S., AGRAWAL, A., LU, J., MITCHELL, M., BATRA, D., ZITNICK, C. L., AND PARIKH, D. Vqa: Visual question answering. In Proceedings of the IEEE international conference on computer vision (2015), pp. 2425-2433.
[3] BORDES, A., USUNIER, N., GARCIA-DURAN A., WESTON, J., AND YAKHNENKO, O. Translating embeddings for modeling multi-relational data. In Neural Information Processing Systems (NIPS) (2013), pp. 1-9.
[4] CHEN, D., BOLTON, J., AND MANNING, C. thorough examination the cnn/daily mail reading comprehension task. CoRR (0s/1800.022888 (2016).
[5] CHEN, W., GAN, Z.,, LI, L.,, CHENG, Y., WANG, W., AND LIU, Meta module network for compositional visual reasoning. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (2021), pp. 655-664.
[6] CHENEY, J., CHITICARIU, L., AND TAN, W.-C. Provenance in databases: Why, how, and where. Foundations and Trends in Databases 1, (Apr. 2009).
[7] COHEN, W. W. Tensorlog: A differentiable deductive database. CoRR abs/1605.06523 (2016).
[8] DAI, W.-Z.,, XU, Q., YU, Y., AND ZHOU, 7.-H. Bridging machine learning and logical reasoning by abductive learning. In NeurlPS 2019 (2019).
[9] DARWICHE, A. Sdd: A new canonical representation of propositional knowledge bases. In Proceedings of the Twenty-Secont International Joint Conference on Artificial Intelligence Volume Volume Two (2011), UJCA 11, AAAI Press, p. 819-826.
[10] D' AVILA GARCEZ, A., GORI, M., LAMB, L.. C., SERAFINT, I.., SPRANGER, M., AND TRAN, S. N. Neural-symbolic computing: An effective methodology for principled integration of machine learning and reasoning, 2019.
[11) DE RAEDT, I.., KIMMIG, A., AND TOIVONEN, H. Problog: A probabilistic prolog and its application in link discovery. pp. 2462-2467.
[12] DEUTCH, D., GILAD, A., AND MOSKOVITCH, Y. Efficient provenance tracking for datalog using top-k queries. The VLDB Journal 27 (2018), 245-269.
[13] DEVLIN. J., CHANG, M., LEE, K., AND TOUTANOVA, K. BERT: pre-training of deep bidirectional transformers for language understanding. CoRR abs/1810.04805 (2018).
[14] EVANS, R., AND GREFENSTETTE, E. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research 61 (2018), 1-64.
[15] FUHR, N. Probabilistic datalog- a logic for powerful retrieval methods. In Proceedings of the 18th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (New York, NY, USA, 1995), SIGIR '95, Association for Computing Machinery, p. 282-290.
[16] GAO, D., WANG, R., SHAN, S., AND CHEN, X. From two graphs to n questions: vqa dataset for compositional reasoning vision and commonsense. arXiv preprint 1rXiv:1908.02990 (2019).
[17] GREEN, T. J., KARVOUNARAKIS, G., AND TANNEN, V. Provenance semirings. In Proceedings of the ACM SIGMOD SIGACT-SIGART Symposium on Principles of Database Systems (PODS) (2007).
[18] HUDSON, A., AND MANNING, C. GQA: new dataset for compositional question answering real-world images. CoRR 0bs//992.009000 (2019).

---

[19] KIMMIG, A., DEN BROECK, G. V., AND RAEDT, L. D. Algebraic model counting. CoRR abs/1211.4475 (2012).
[20] LECUN, Y., BOTTOU, L., BENGIO, Y., AND HAFFNER, P. Gradient-based learning applied to document recognition. Proceedings of the IEEE 86, 11 (1998), 2278-2324.
[21] LI, Q., HUANG, S., HONG, Y., CHEN, Y., WU, Y. N., AND ZHU, S.-C. Closed loop neural- symbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning. In International Conference on Machine Learning (2020), PMLR, pp. 5884 5894.
[22] LIN, T., MAIRE, M., BELONGIE, S. J., BOURDEV, L. D., GIRSHICK, R. B., HAYS, J., PERONA, P., RAMANAN, D., DOLLÁR, P., AND ZITNICK, C. L. Microsoft COCO: common objects context. CoRR abs/1405.031 0312 (2014).
[23] MAHDAVI, M., ZANIBBI, R., MOUCHERF, H., VIARD-GAUDIN, C., AND GARAIN, U. Iedar 2019 crohme + tfd: Competition on recognition of handwritten mathematical expressions and typeset formula detection. pp. 1533-1538.
[24] MANHAEVE, R., DUMANCIĆ, S., KIMMIG, A., DEMEESTER, T., AND RAEDT, L. D. Deep- problog: Neural probabilistic logic programming. In NeurIPS 2018 (2018).
[25] MARINO, K., RASTEGARI, M., FARHADI, A., AND MOTTAGHI, R. Ok-vqa: visual question answering benchmark requiring external knowledge. In Conference on Computer Vision and Pattern Recognition (CVPR) (2019).
[26] MINERVINI, P., BOSNIAK, M., ROCKTÄSCHEL, T., RIEDEL, S., AND GREFENSTETTE, E. Differentiable reasoning on large knowledge bases and natural language. CoRR abs/1912.10824 (2019).
[27] MINERVINI, P., RIEDEL, S., STENETORP, P., GREFENSTETTE, E., AND ROCKTÄSCHEL, T. Learning reasoning strategies in end-to-end differentiable proving, CoRR abs/2007.06477 (2020).
[28] RAEDT, L. D., MANHAEVE, R., DUMANCIC, S., DEMBESTER, T., AND KIMMIG, A. Neuro- symbolic neural + logical probabilistic. In International Workshop Neural-Symbolic Learning and Reasoning (2019).
[29] ROCKTÄSCHEL, T., AND RIEDEL, S. End-to-end differentiable proving, CoRR abs/1705.11040 (2017).
[30] ROCKTÄSCHEL, T., AND RIEDEL, S. End-to-end differentiable proving. arXiv preprint arXiv: 1705. 1040 (2017).
[31] SANG, T., BEAME, P., AND KAUTZ, H. A. Performing bayesian inference by weighted model counting. In AAAI (2005), vol. 5, pp. 475-481.
[32] SERAFINI, L.,, AND D' AVILA GARCEZ, A. S. Logic tensor networks: Deep learning and logical reasoning from data and knowledge. CoRR abs/1606.04422 04422 (2016).
[33] TAN, H., AND BANSAL, M. Lxmert: Learning cross-modality encoder representations from transformers, arXiv preprint 1XXv:1908.00490 (2019).
[34] WANG, P., WU, Q., SHEN, C., HENGEL, A., AND DICK, A. Explicit knowledge-based reasoning for visual question answering.
[35] WILLIAMS, R. J. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning 8, 3-4 (1992), 229-256.
[36] XU, J., ZHANG, Z., FRIEDMAN, T., LIANG, Y., AND VAN DEN BROECK, G. A semantic loss function for deep learning with symbolic knowledge. In Proceedings of the 35th International Conference on Machine Learning (10-15 Jul 2018), J. Dy and A. Krause, Eds., vol. 80 of Proceedings of Machine Learning Research, PMLR, pp. 5502-5511.
12


Reviews:
[{"review_id": "gsf4buAowas", "reviewer": "Reviewer_uqGA", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n**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.\n\n**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).\n\n**Clarity**: The paper was easy to read and most details were clear to me.\n\n**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.\n\n[1] Learning Reasoning Strategies in End-to-End Differentiable Proving\n[2] End-to-End Differentiable Proving", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and societal impact were not discussed. I do not believe the method has any negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "fFOFGe1adHp", "reviewer": "Reviewer_34Ja", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nA few suggestions for improving understanding of this method:\n\n- 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.\n- 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "_aQ9lkpqq1L", "reviewer": "Reviewer_NXqU", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n+ 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.\n+ Significant gains on benchmarks that involve image recognition and simple reasoning steps.\n+ Reasonable scalability: costly algorithms, such as weighted model counting, are applied in a way that does not immediately limit the scalability.\n\nCons:\n- 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.\n- Significant parts of the architecture have to be adapted to each task (scene graphs, logic programs matching the task).\n- toy benchmark/custom benchmark; claims to be real-world task, but I'm not totally convinced it is\n- 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.\n\nThe writing style is okay, but many parts could be written in a more concrete way. Some examples:\n- 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.\n- The introduction would benefit from clarifications on what the terms \"proof\", \"provenance\", and \"reasoning granularity\" mean exactly in the context of this work.\n- The introduction promises an evaluation on a \"real-world task\", but does not go into what this task is.\n\nQuestions to the authors:\n- 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?\n- 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?\n- 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?\n- The examples in Figure 1 look like you just need DNF counting instead of WMC counting? Why do you need WMC?\n\nNitpicks:\n- 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.\n- Check the capitalization of acronyms in the references ...", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ZQwnAupHUX", "reviewer": "Reviewer_2nJQ", "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.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n\n+ 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.\n\n+ 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. \n\n+ Experiments on 2 tasks show that Scallop achieves similar or better performance compared to baselines with significantly less time.\n\n\n## Questions and Weaknesses\n\n- 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. \n\n\n[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.  \n[B] Minervini, Pasquale, et al. \"Learning reasoning strategies in end-to-end differentiable proving.\" International Conference on Machine Learning. PMLR, 2020.  \n[C] Raghothaman, Mukund, et al. \"Provenance-guided synthesis of Datalog programs.\" Proceedings of the ACM on Programming Languages 4.POPL (2019): 1-27.\n\n- 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. \n\nExperiments 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.\n\n- 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.\n\n- 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. \n\n- 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? \n\n- In Line 86, \"a higher k ... accelerates the convergence of learning.\" Why?\n\n\n## Comments on the Final Rating\n\nI 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "## Technical Limitations\n\nSee my comments in \"Questions and Weaknesses\"\n\n## Societal Impact\n\nI do not see any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)