Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes deep logic networks that can train with backpropagation and inference with binary values. The logic networks comprise logical gates arranged in layers, randomly selected connections between gates, and an output layer that sums the outputs from groups of gates to adapt cross-entropy loss or squared error loss. The types of gates are treated as parameters of the model and are optimized by Adam. The experiments show this network can perform classification tasks on MONK, Adult Census, Breast Cancer, MNIST, and CIFAR10, achieving good accuracy.
strengths_and_weaknesses: The paper is well written and easy to follow. To my best knowledge, the proposed Differentiable Logic Gate Networks is a highly novel idea. The model learns the type of gates instead of the weight matrix/connections. This training paradigm differs significantly from the standard DNN and other logic models. More interestingly, the Diff Logic Net uses randomly selected connections between gates, and the random connections are fixed during the training. This simple idea works surprisingly well and is probably the key reason it can learn the gate type in a scalable way. The experiments compare with a set of prior compact models and show the advantage of the Diff Logic Net in terms of accuracy, the number of operations, and actual inference time. I especially appreciate the results on CIFAR10 to demonstrate the scalability of this new breed of models. This work may significantly impact edge-device AI in both software and hardware aspects.

The success of Diff Logic Net looks too good to be true; therefore, discussing its limitation is highly appreciated. I saw it in Section 5 and consider the current section 5 reasonably informative. I believe the community will appreciate it more if section 5 is expanded further. One idea for exploring the current limitation is to examine its architectural robustness against several factors. For example:
1. Depth versus accuracy
2. If the input dimension is very high, would the random connection still work with a reasonable model width?
3. The variance of accuracy with different random connections

Note the above bullets are suggestions and I do not consider these are weaknesses of the paper.
questions: 1. Line 195: the first tau should be n?
2. Line 334: What is PTX?
3. What's the training time of each Diff Logic Net in Table 5?

limitations: The paper discussed 3 aspects of limitations in section 5.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper proposes the differentiable logic gate networks. The logic gate networks parameterize the logical operations by proposing a logic gate neuron that consists of 16 binary logic operations. The differentiable learning is done by 1) using soft logic operations and 2) introducing attention parameters over the 16 operations. The proposed model is evaluated on standard classification tasks, which seems to suggest that the model is faster in inference time.
strengths_and_weaknesses: ### Originality
Overall, the proposed method isn't intellectually novel. The idea of using soft logic and attention mechanism to learn a logic system in a differentiable way has been a common practice in the literature, and similar and more sophisticated designs for the same problems have been proposed and studied extensively in many prior works [1-5].  With that being said, this paper clearly misses a big part of the literature. For those cited work, the paper does a poor job in connecting them to the proposed method, either due to the comparison is missing (e.g., L95) or the comparison is unconvincing and confusing:
- "while this leads to some generalization, this generalization is limited"
- "While these works relax which nodes are connected to which nodes,85this is fixed in our work, and we relax which operator is at which node"


### Quality
I find some of the proposed designs difficult to understand and can be fundamentally flawed:
- Judging from Figure 1 and section 4,  it looks like the neuron accepts only two inputs from the previous layer, but it is unclear how they are picked. This can be problematic compared to the standard fully connected layer because not all logical combinations are included in the model space. Consider this a simple setting with 3 binary inputs (a, b, c) and two neurons f1 and f2 that connect to (a, b) and (b, c) respectively. Then it is impossible to represent any operations between (a, c). To consider all combinations, one needs n^2 number of neurons at each layer.
- L187, the classification is performed by simply grouping adjacent neurons and counting. My concern is that this implicitly makes the output dependent on the position of the neurons. For the image classification task, this means the network is not translational invariant as opposed to CNNs, because a small shift in the original image is going to lead to different results.



### Clarity
The writing needs an overhaul. This paper is prone to confusing statements, constant grammatical errors and informal presentations.  

The English writing should be improved:
- "as well as other machine learning methods that are fast and that we compare ourselves to with respect to inference cost and speed"
- Mixed usages of normal and italic "which" in L77-86

The wording should be improved; some of the contents are rather colloquial:
- "He does this to explore principles of learning and memorization" -> "The proposed method explores the  principles of learning and memorization"


### Significance
The proposed method is only evaluated on existing tasks and struggles to match with the performance of other baselines. The only merit seems to be that the proposed network excels in inference speed. However, this comes with serious limitations: 
- As mentioned by the author at L235, the network is expensive to train. However, it's unclear how expensive the training actually is because only inference time is compared in the experiments. To fairly compare with other baselines, it is necessary to include the training time.
- The network likely oversimplifies the layer connections and can be flawed in representing certain logical combinations.

That said, there is no substantial contribution in this work.

[1] Serafini, Luciano, and Artur d'Avila Garcez. "Logic tensor networks: Deep learning and logical reasoning from data and knowledge." arXiv preprint arXiv:1606.04422 (2016).

[2] Dong, Honghua, et al. "Neural logic machines." arXiv preprint arXiv:1904.11694 (2019).

[3] Shi, Shaoyun, et al. "Neural logic reasoning." Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020.

[4] Shanahan, Murray, et al. "An explicitly relational neural network architecture." International Conference on Machine Learning. PMLR, 2020.

[5] Yang, Yuan, and Le Song. "Learn to explain efficiently via neural logic inductive learning." arXiv preprint arXiv:1910.02481 (2019).
questions: I recommend the authors re-writing the paper and address the following concerns:
- What is the motivation of this work? 
- What are the benefits of using this network compared to other neural-symbolic models?
- How are the layers connected? Is there any theoretical or empirical justification to this design?

I also recommend re-designing the experiments:
- Include training time when comparing with other baselines.
- Include empirical analysis on certain parts of the proposed network. For example, shifts in the feature space, and classification via grouping.

limitations: Yes
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors proposed the Logic Gate Network - a neural network with neurons represented by binary logic gates. The network is parameterized by the choice of logic gates chosen from 16 logic operations. During training, the inputs to the neurons are relaxed from binary to probabilities to allow for differentiability. To allow for differentiability of the logic operations, each neuron has a weight vector of dimension 16, which when taken the softmax forms a categorical distribution. The activation of the neuron is the weighted sum of the distribution with their corresponding real-valued logic operation. At test time, the trained network is binarized to allow for fast inference. The authors evaluated their method on a set of classification tasks including MONK, Adult and breast cancer dataset, MNIST and CIFAR-10. Results show that compared to fully connected networks, the logic gate network is able to speed up inference time by 1-2 orders of magnitude and reduce the space consumption by roughly the same amount while moderately sacrificing accuracy in some tasks.
strengths_and_weaknesses: Strengths
- The authors made good progress in enabling binarized logic network to work reasonably well in small to midsize classification problems while significantly reducing the memory footprint and speeding up the inference process. I particularly enjoyed Sections 4.1 and 4.2 where the authors discussed practical considerations and tricks they have tried to improve the performance. This type of work has much practical value to the edge deployment of neural network models.

Weaknesses
- elucidation of the position of the proposed architecture within the deep learning literature can be improved. functionality-wise, do the authors see the logic gated network able to achieve most of what other networks can down the road, or by design it would occupy a different functional space (for example efficient inference on the edge with reduced accuracy)?
questions: - "after training, the network is binarized by choosing the logic gate with highest probability", this is not the same network that is being trained on, even though the binary network provides a speed up at inference, will the accuracy be higher with the "soft" version?

- "there is a total of 16 functions of signature" - can it be more than 16? if so will it improve performance?

- no comparison with CNN on image classification tasks, though this is for fair comparison with a fully connected logic net, can the authors comment how a CNN version of the logic net will perform?

- "CIFAR-10 reduced grayscale resolution and employ binary embedding",  why is this needed?

- The sparse neural network rows in Tables 4 and 5 are a bit confusing, they don't have inference times but instead sparsity metrics, which the diff logic net do not provide, not sure what the comparison here is.
limitations: The authors provided a reasonable set of limitations in Section 5. One of my concerns is that the input and output of the proposed logic network are Booleans, how would colored images be represented? Moreover, would regression tasks be out of the question for this type of network?
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces a new approach for fast-inference, low memory neural networks: logic gate networks. An output neuron is connected sparsely to only two neurons from the input layer, and training learns one of sixteen possible boolean functions on the two binary inputs. Training is done with real relaxations of the logic functions and averaging over all 16 functions, while testing uses the most common function. Using logic gates enables extremely efficient inference execution on CPU. The authors show logic gate networks perform comparably to alternatives on several small datasets.
strengths_and_weaknesses: Strengths:
- To my knowledge, this is a new idea. Using logic gates is a smart goal for achieving ultra-fast NN inference, and the authors seem to use the correct general approach to training such networks.
- Related work is well-cited, and the authors do a good job contextualizing to the space of similar techniques (sparse NNs/pruning, binarized NN's)
- Claims are fairly well supported. 
- Submission is mostly well-written, with some exceptions.
- Significance: the results are not game-changing **yet**, but I find the goal of logic-gate networks to be an exciting direction and the work the authors achieve in pursuit of this direction.
- In all experiments, the approach presented has the fastest inference time. 

Weaknesses:
- Overall writing quality could be better. Many details are not described well:
- The network architecture is poorly explained in section 3. The description is informal and at a high level of detail. The pieces don't really come together until the end of section 4; for example, the sparse net topology of 2 inputs per neuron is not fully explained with the random connectivity in line 221. 
- There is no architecture figure. While not 100% necessary, I think this would be a helpful aid to understanding the architecture, especially how the connective topology is organized.
- Many training and architectural design choices are not motivated well. Often there are reasonable alternative choices, which should be ruled out, or better yet experimented against to see which is best! For example, there could be alternate ways of making the choice of logic gate differentiable (smoothly interpolate between logic ops?), or you could try structured connectivity patterns rather than random connectivity patterns. Or you could try expanding the set of operators rather than reducing. Four inputs instead of two?
- The paper has a lot of unpleasant language that seems to be making a lot of effort to apologize for poor results "if we had more time down the line, we could implement more connectivity types", or "practical computation cost can be reduced through improved implementations" and the like. Ignoring the quality of results, such statements do not belong in a paper in my opinion.
- Many of the baseline comparison architectures do not seem justified well. Why does the breast cancer dataset neural network have 3810 parameters? Why does the Diff logic net have 1280 parameters? 
- It would be extremely valuable to have a comparison of training time for Diff Logic Nets and the baselines, even if some baselines' training time can't be given or can only be estimated. Even if DLN are much slower to train (that's okay!), this should be shown!

questions: Questions and suggestions:
- Line 195 I believe it should be "increasing n by a factor of 10, tau should be decreased..." not increasing tau.
- The paragraph in section 4.2 "aggregation of output neurons via binary adders" does not make any sense to me.
- I find the remark on lines 242-244 about being developed from scratch inappropriate for a paper. I would rewrite to discuss the possibility of future papers considering convolutions and other connectivity patterns without the excuse. And perhaps you should add a sentence explaining how the work is implemented (pytorch?)
- Higher training cost is mentioned for logic gate networks limitation in section 5. But how much higher is the cost? Quantifying this, even if the number might be improved down the line, seems like an important and useful benchmark to have.
- If you say practical cost of training can be reduced through improved implementations, then you should explain what stands to be improved and how much improvement we might gain. 
- "Thus, our model is objectively more than 10x cheaper to evaluate" — I do not like this sentence. Whether a net is cheaper to evaluate depends on factors other than the number of binary operations. 

limitations: Limitations:
- the limitations section is not very good. The statements are qualitative when it would be very easy to make them quantitative. Furthermore, there are more interesting things that could be said about future extensions. Most of the limitations section sounds like making excuses in case the reader is not impressed with the current work.
review_title: null

Meta-review: metareview: The paper proposes to train classifiers for binary data based on logic gate networks, also called arithmetic circuits or algebraic circuits in the knowledge representation and complexity literature [1,2]. The main motivation is that, once trained, they can be run fast by leveraging only binary operations. The authors achieve this by using the classical way to relax logic operations, via a first-order approximation with fuzzy norms. 

The reviewers found the proposed approach interesting and potentially useful for resource-constrained scenarios (where resources do not lack during training but during inference). I agree with them that this paper fits the tinyML literature more than the knowledge representation or reasoning (nowadays falling under the neuro-symbolic) one. However, I agree that believe the paper needs to fix certain aspects for the camera ready.

First, it is not clear why the authors are selecting the set of 16 logical operators, where, ideally only 2 are necessary (eg. AND, or product, and NOT, or negation) as all the others can be retrieved as combinations of the these two, as Table 1 illustrates. Furthermore, as using all 16 operators is the major bottleneck that makes the networks being very slow during training, an ablation test with a (even not minimal) subset of the operators is recommended. Clearly there is a trade-off in terms of accuracy w.r.t. the subset of ops used for a fixed depth network. And this trade-off needs to be made clear in the contribution (The authors can elaborate more than only saying "Omitting subsets of the operators decreased performance in all of our experiments."). 

Second, there are a number of claims that need to be fixed. For example, the issue with differentiability with the relaxed functions is that gradients are constant everywhere, and only not defined on a single zero-measure point (between the zero and one regions). This is also one of the issues when trying to learn decision tree structures in a differentiable way. Additionally, the discussion on decision trees being very different from logic gate networks/algebraic circuits is very misleading and needs to be fixed. In fact, a decision node in a tree can be easily represented as a sum unit over some product units or equivalently OR and AND units in propositional logic or SMT [3, 4].

Third, since during training the authors are effectively using a probabilistic mixture model (Eqs 2,3), they are training something similar to a sum product network (without any relevant structural properties, and with negative weights) [5,1]. Therefore, the effect of the temperature parameter is important in retrieving a binary operator and not sufficiently investigated. An ablation study is recommended.

Lastly, for the larger experiments, it seems the authors are reporting the results of competitors which, however, use a different preprocessing (e.g. they use more gray-scale values for CIFAR). This makes the space and time consumption not comparable across models and requires a clarification.

I advice the authors to take care of these aspects to make the paper stronger.



[1] Darwiche and Marquis, "A Knowledge Compilation Map", 2001
[2] Arora and Barak, "Computational complexity: a modern approach" 2009.
[3] Khosravi, et al. "Handling missing data in decision trees: A probabilistic approach." 2020
[4] Devos, et al. "Verifying tree ensembles by reasoning about potential instances." 2021
[5] Choi, et al. "Probabilistic Circuits: A Unifying Framework for Tractable Probabilistic Models" 2020 
confidence: Less certain
Decision: Accept