Venue: NeurIPS 2022 Conference

Reviews:

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 investigates a couple different things, but at its core its investigating the certified robustness of systems that leverage "logical reasoning" (i.e. Markov Logic Networks) on top of regular statistical learning neural networks (what this paper calls a "sensing-reasoning" pipeline).

This paper has 3 primary contributions:
1. It examines the problem of certifying robustness for graphical models as well as its computational complexity.
2. It proposes an approach for certifying robustness for these models.
3. It demonstrates that on a variety of tasks it looks at, this sensing + reasoning pipeline can lead to better robustness than pure sensing.


strengths_and_weaknesses: Strengths:
1. I hadn't thought about this particular angle before, but I think it's a very interesting and relevant problem to tackle. One pitch for hybrid neuro-symbolic approaches for quite some time has been robustness, but I haven't seen any papers tackle certified robustness for these systems before, which made their claims of "robustness" less convincing.
2. The proof of the difficulty of certifying robustness on the reasoning component seems useful, although I lack the expertise to verify how interesting it is (the reduction wasn't obvious to me at least).
3. The approach for certifying robustness of the reasoning component seems reasonable and fairly interesting to me.
4. The authors demonstrate that their sensing+reasoning pipeline achieves better certified robustness than pure sensing approaches on a wide array of datasets/tasks, which is great!
5. I also appreciated the intuitive examples of why sensing + reasoning would lead to better robustness compared to pure sensing.

Weaknesses:
The main issue I have about this paper relate to the specific tasks it uses, which is related to the specific kinds of "sensing + reasoning" networks it uses. As a result of the particular kind of pipeline it requires, the tasks it evaluates on are not standard "certified robustness" tasks, as far as I can tell. This means that they do not compare against any existing papers/baselines on their tasks, only the baselines they've created for these tasks. This is somewhat worrisome, although the baselines they choose do seem reasonable.

It would be much  more convincing to me if the authors were able to demonstrate SOTA robustness results against standard robust baselines.

Overall, the authors do a great job of introducing the task of certified robustness to a new class of (quite interesting!) models, examine its difficult and computational complexity, and evaluating its robustness on a wide array of tasks. However, the lack of experiments against standard established baselines and tasks gives me some pause. Still, I think this paper is quite interesting and should be accepted.

questions: One thing that was confusing to me was what the baseline "sensing only" models actually *were*? For example, on the PrimateNet tasks, there are a bunch of "leaf sensing" nodes that the reasoning component leverage to make its final prediction. However, how is the model without the "reasoning" actually arriving at its final prediction?
limitations: Yes.
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 proposes to improve robustness certification by leveraging a reasoning component based on Markov logic networks (MLN). Human knowledge (i.e., logical rules) are formalized as variables and factors in the reasoning component, thereby guiding the sensing-reasoning pipeline to exhibit better certified robustness. Concretely, the contribution of this paper is three-fold:

1. This paper proves that the computational complexity of certifying the robustness of MLN is #P-hard. The basic idea is to reduce the famous #P-complete COUNTING problem to checking for reasoning robustness. This hardness result tells us why this task is challenging, indicating that the key points to mitigate it are: (1) choosing a "good" reasoning component that have efficient inference algorithm; (2) find an efficient approximation algorithm that can reduce the problem of cerifying the robustness to the statistical inference oracle, and prove how good (the bounds) the algorithm is.
2. This paper complete the two key points mentioned above. The reasoning component is designed as Markov logic networks (MLN), of which the inference is #P-complete but has efficient approximation algorithms that can be regarded as oracles. Based on this, the authors provide an effective certification method for reasoning robustness.
3. Experimental results on several applications demonstrate the robustness of such ML pipelines.
strengths_and_weaknesses: Pros:
- Certified robustness is an important topic in machine learning, and it is promising that introducing human knowledge expressed as logical rules can further improve the overall certified robustness. This topic is challenging, as discussed in Section 3.
- Knowledge is expressed in the framework of Markov logic networks. This is elegant and easy-to-understand. This design choice also helps the authors propose the efficient algorithm.
- Key points in this paper are well formulated and proven.
- Good experimental results on different applications, with good result analysis.

Cons:
- It is quite hard for me to understand the relationships among Section 2, 3, and 4 (especially how Section 4 is based on Section 3), as I'm not an expert in this area. I try to summarize my understanding in the "Summary" part above, but I'm not sure whether it is correct or not. I hope that the authors can point out incorrect understandings in my summary in the rebuttal. Moreover, I also list detailed questions that are still unclear for me as follows.
questions: Q1: maybe the authors can provide an explicit definition of "Statistical Inference" as background knowledge. In Figure 1, it looks like statistical inference is done by the sensing component, which is decoupled with the reasoning component. However, in Section 3 and 4, we say "statistical inference of the reasoning component".

Q2: In Section 4, the authors use the wording "we assume that we have access to an oracle for statistical inference". I think it could be better if the authors can explicitly tell us what the concrete oracles are.

Q3: L86 "Surprisingly, providing certified robustness for MLN is possible because of the structure inherent in the probabilistic graphical models and distributions in the exponential family." Maybe the authors can explain more about this point as it is still unclear for me how this point is concluded from Section 4.
limitations: Q4: (about the limitation) what is the limitation of MLN comparing to other statistical inference models? Can the methodology proposed in this paper generalize to others?
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper tries to introduce certified robustness into a probabilistic reasoning system. First, Markov logic network (MLN) is used as a generic model that can represent every probabilistic logical reasoning system. Then, the authors proved that the complexity of certifying a MLN model reasoning model robustness is #P-Hard. Furthermore, a novel algorithm to certify the reasoning robustness is proposed with an assumption that two partition functions are available. Experimental results on both road sign classification and information extraction show that sensing-reasoning pipeline can have much higher certified accuracy. Detailed analysis showed that by incorporating reasoning components, the number of examples with a large “margin” under adversarial attacks significantly increased.
strengths_and_weaknesses: Strengths: \
1.	Certified robustness is a very important research topic.\
2.	Theoretical analysis in this paper is valuable.

Weaknesses:\
It is not clear what the key idea the paper wants to deliver is. There are several points in this paper: \
a. the complexity of certifying robustness; \
b. an algorithm to estimate the upper/lower bound; \
c. experimental results show that incorporating reasoning components can improve the certified robustness. \
However, it seems they are all independent between each other. I cannot see a coherent story line in this paper. For example, experimental results show that incorporating reasoning components can significantly improve robustness. But, how are these results related to the proposed algorithm on upper/lower bound estimation or the complexity?

questions: 1.	Is there a clear definition of \textit{certified robustness}? The paper should include this definition for self-completion. 
2.	Some notions are used but not defined. For example, at line#154, what is $f_H()$?
3.	In section 4.2, the partition functions $Z_1$ and %Z_2$ are assumed to be available beforehand. How are these functions obtained for the two tasks in the experiments?
4. What is the key point the authors want a reader should take away from this paper? I am confused by the independent points in this paper.
limitations: Certified robustness is an important topic that can be beneficial to societal good through building robust and trustworthy machine learning models.
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: This paper proposed to integrate statistical ML models with knowledge as a reasoning component using Markov logic networks in order to improve certified robustness. They start from a sensing-reasoning pipeline, followed by deriving the hardness of certifying general reasoning model, and finally certifying the robustness of sensing-reasoning pipeline. Experiments on five datasets show that their method outperforms models from prior work. 
strengths_and_weaknesses: I'm not an expert in this area so I didn't check the correctness of the math thoroughly. 

Overall I think this is a nice paper with thorough theoretical analysis and solid experiments. The paper is well written.

One weakness that I can think of is that it would be great if you could provide more experiments on large-scale datasets.
questions: N/A
limitations: Same as the weakness point mentioned in the above section.
review_title: null

Meta-review: metareview: I agree with zVbd that the paper has too many points. A paper should try to make a single point and then one can write more papers :-). The #P hardness result seems the least interesting of the points. I am also not very interested in the certification of robustness. The real question is can Carlini defeat it. But this paper raises an issue that I have always suspected is important --- are structured labels inherently more robust?  I would certainly want to see what Carlini can do in generating adversarial examples for highly structured labels.  As I believe that robustness for structured labels deserves more attention, and this paper purports to have positive empirical results in that direction with reasonable review scores I will recommend acceptance.

confidence: Less certain
Decision: Accept