Improving Out-of-Distribution Detection with Markov Logic Networks
Authors: Konstantin Kirchheim
Frank Ortmeier
Venue: ICML 2025 poster (2025)
Keywords: Out-of-Distribution Detection
Markov Logic
Probabilistic Graphical Models
Anomaly Detection
Primary area: social_aspects->safety
TL;DR: We propose to use Markov Logic Networks for OOD detection; in combination with existing detectors, they improve results while being explainable.

Abstract: Out-of-distribution (OOD) detection is essential for ensuring the reliability of deep learning models operating in open-world scenarios. Current OOD detectors mainly rely on statistical models to identify unusual patterns in the latent representations of a deep neural network. This work proposes to augment existing OOD detectors with probabilistic reasoning, utilizing Markov logic networks (MLNs). MLNs connect first-order logic with probabilistic reasoning to assign probabilities to inputs based on weighted logical constraints defined over human-understandable concepts, which offers improved explainability. Through extensive experiments on multiple datasets, we demonstrate that MLNs can significantly enhance the performance of a wide range of existing OOD detectors while maintaining computational efficiency. Furthermore, we introduce a simple algorithm for learning logical constraints for OOD detection from a dataset and showcase its effectiveness.

Improving Out-of-Distribution Detection with Markov Logic Networks
Konstantin Kirchheim
Frank Ortmeier'
Abstract
DNN, such as predicted posteriors (Hendrycks & Gimpel, 2017), unnormalized logits (Zhang et al., 2022), or deeper latent representations (Lee al., 2018; Wang et al., 2022). These detectors often construct a model of the neural repre- sentations for in-distribution (ID) data and classify inputs with low probability under this model as OOD. While pro- viding reasonable performance in many settings, current detection methods face several limitations. Firstly, they rely on potentially superficial statistical patterns in the represen- tations learned by DNNs but neglect the semantics of these representations in the context of the task. Secondly, they lack explainability, as they generally provide only scalar outlier score without further justification for why an input is marked as OOD. Thirdly, integrating prior knowledge about the structure of the training distribution into existing detectors remains challenging, as this knowledge often con- cerns abstract concepts that are difficult to correlate with high-dimensional inputs. For instance, many people would intuitively classify blue stop signs as OOD because stop signs are typically red. However, embedding such domain- specific knowledge into current OOD detectors is difficult due to their reliance on entangled, opaque neural represen- tations.
Out-of-distribution (OOD) detection is essen- tial for ensuring the reliability of deep learn- ing models operating in open-world scenarios. Current OOD detectors mainly rely on statisti- cal models to identify unusual patterns in the latent representations of deep neural network. This work proposes to augment existing OOD detectors with probabilistic reasoning, utilizing Markov logic networks (MLNs). MLNs con- nect first-order logic with probabilistic reason- ing to assign probabilities to inputs based on weighted logical constraints defined over human- understandable concepts, which offers improved explainability. Through extensive experiments on multiple datasets, we demonstrate that MLNs can significantly enhance the performance of a wide range of existing OOD detectors while maintain- ing computational efficiency. Furthermore, we introduce simple algorithm for learning logical constraints for OOD detection from dataset and showcase its effectiveness.
Recently, neuro-symbolic approaches for OOD detection have shown promise in addressing these limitations. For ex- ample, LogicOOD (Kirchheim al., 2024) detects human- understandable concepts in inputs and verifies their con- figuration against a set of logical constraints. While this method increases performance on some datasets and offers a degree of explainability, its reliance on strict logical rules
1. Introduction
Deep Neural Networks (DNNs) (LeCun et al., 2015; Schmidhuber, 2015) provide state-of-the-art performance across various computer vision tasks, including image clas- sification (Dosovitskiy al., 2021), object detection (He al., 2017), and semantic segmentation (Ronneberger et al., 2015). However, DNNs are prone to making incorrect pre- dictions with high confidence when applied to data outside their training distribution (Nguyen et al., 2015). This prop- erty motivates out-o-ddistriuution (OOD) detection mech- anisms (Yang al., 2024: Kirchheim et al.. 2022), which aim identify OOD inputs at runtime. In recent years, wide array of OOD detectors has been developed, leverag- ing the representation of the input at different layers of
can too rigid for complex, real-world applications where probabilistic associations dominate.
This work proposes integrating existing OOD detectors with probabilistic graphical model specifiially,, Markov logic network - defined over human-understanddblle con- cepts. Such a model offers explainability and allows the seamless integration of prior knowledge. In particular, we make the following contributions:
Department of Computer Science, University of Magdeburg, Germany, Correspondence to: Konstantin Kirchheim <kirch- hei ovgu.e...
1. We introduce novel OOD detection framework based on Markoy logic networks (MINss, leveraging proba- bilistic reasoning over logical constraints (Section 3).
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
2. We propose a novel algorithm to automatically learn innen-interpretabll constraints for OOD detection

---

Improving Out-of-Distribution Detection with Markov Logic Networks
from a dataset (Section 4).
class and uses -1y -,,,,xx (xx) the outlier score, where y is the maximum posteriori class for x.
3. We demonstrate that combining MLNs with existing OOD detectors significantly improves performance across several datasets, detectors, and DNNs (Sec- tion 5).
Latent Rectification More recently, methods that rec- tify the representations of neural networks have been pro- posed. Mathematically, these methods introduce a rectifier f = h o r o Φ that alters the latents. Examples include DICE (Sun & Li, 2022), which sparsifies the activations, as well as ReAct (Sun al., 2021) and ASH (Djurisic et al., 2023), which replace unusual activations with alternative values. These modified representations often provide better performance when used with downstream OOD detector.
2. Background & Related Work
2.1. OOD Detection
Let f X + RN be a classifier that maps points from its input space X' S RK, drawn according to a distribution Piaaa to a vector of class logits. An OOD detector for f is scoring function D X + E that maps inputs to scalar outlier scores, such that OOD inputs, which have low probability under Pdata. receive higher score than ID data points that have high probability under Pdata- A simple thresholding scheme then makes the final decision as:
2.2. First-Order Logic
First-order logic (FOL) is a formal system for reasoning about objects, their properties, and their relationships. In FOL, a domain X' defines the set of objects being considered. Predicates P represent properties or relationships among objects, and functions F map objects to other objects in the domain. Such predicates could include, for example, RED X + {true, false), which supposedly evaluates to true for objects that are of red color. FOL formulas com- bine predicates and terms using logical connectives such as conjunction (A), disjunction (V), negation (-), implication (-)), exclusive or (+), and equality (=). Quantifiers specify whether a formula applies universally (V) or existentially (3) over the domain. The semantics of a FOL formula is provided by an interpretation I which maps predicates to functions PI X" + false), determining which tuples of objects satisfy the predicate, and functions F to functions F² 2 - X, defining their behavior over the domain.
true if 2
outlier(x)
(1)
false
else
In recent years, numerous OOD detection methods have been developed, with comprehensive overviews available in recent surveys (Lu et al., 2024; Yang et al., 2024; Kirch- heim et al., 2022). Broadly, many of these methods can be categorized into the following groups:
Posteriors Class membership probabilities can be ob- tained from classifier f by applying the normalizing softmax function to its output. The Maximum Soft- max Probability (MSP) baseline method (Hendrycks & Gimpel, 2017) uses the negative maximum class posterior, - -max; (x())); k. as an outlier score. Ensembling (Laksh- minarayanan et al., 2017) and Monte-Carle Dropout (Gal & Ghahramani, 2016) can enhance the performance of this baseline approach at the expense of additional computation.
As we only consider single inputs in this work, we will use subset of FOL consisting of universally quantified state- ments over unary predicates and functions in the following.
2.3. Markoy Logic Networks
Logits It has been observed that the DNN posteriors are systematically biased, and methods based on unnormalized logits can improve OOD detec- tion. Consequently, approaches such as using the maximum logit (Hendrycks et al., 2022) or its smooth variant, the Energy-based score (EBO) (Liu et al., 2020), computed as log Σ, (x))) have been proposed.
Markov logic networks (MLNs) (Richardson & Domingos, 2006) constitute a probabilistic generalization of first-order logic (FOL) and are instances of the neuro-symbolic com- puting paradigm (Besold et al., 2021). They can also be seen as a templating language for very large Markov networks.
Formally, an MLN M is knowledge base consisting of a set of FOL formulas & = [ each with an associated weight u, R. The weights represent the strength of each constraint, where higher weights correspond to increased influence. Thereby, an MLN represents a probability dis- tribution over finite set of possible worlds Z, where the probability of observing particular 2 E Z is given by
Latent Representations Typical DNN classifiers can be decomposed into feature extractor & that maps inputs to latent representations, and classification head h, such that f f= h o 4. The Mahalanobis method (Lee et al., 2018) fits a multivariate Gaussian to the latent representations of each ID class and then uses the Mahalanobis distance of new data points as an outlier score. Simplified Hopfield Energy (SHE) (Zhang et al., 2022) learns a center My for each ID)
PM(2) Z exp Σ (xx)
1
(2)
2

---

Improving Out-of-Distribution Detection with Markov Logic Networks
where, (1()) is the number of true groundings of in Ap., and
be represented point in a semantic space 2 such that
2 == (F F (x), Pf (x)..... P.d (x)), (5)
7 = Σ exp Σ mp)pl(()
(3)
#E2
where each dimension corresponds to a human- understandable concept. This disentangled representation can then be used to verify constraints imposed the semantic space. During the computation of the partition function in Eq. (3), we sum over this semantic space Z instead of the input space of the DNNs.
is normalizing constant, also referred to the partition function.
Unlike strict logical rules, MLNs can handle uncertainty or imperfect or contradictory knowledge. This makes them more suitable for settings in which probabilistic associations can more adequately represent the underlying structure of the data.
Probabilistic Reasoning Once the interpretations of all FOL. functions and predicates are determined, the truth value of logical formulas can be evaluated to determine whether some input complies with the defined constraints. Enforc- ing logical constraints strictly, as proposed in (Kirchheim et al., 2024), leads to rejecting all inputs that violate even a single constraint, which is unsuitable for many real-world applications. A more nuanced approach would be to adjust the OOD score based on the extent of constraint violations. For example, constraints that are frequently satisfied within ID data should contribute more heavily the OOD score when violated.
3. OOD Detection with MLNs
As discussed in Section 2.1, most existing OOD) detectors focus on identifying atypical patterns within the represen- tations in some layer of a deep neural network trained on ID data. However, certain outliers can be detected more naturally through human-interpretable semantic constraints. For example, using FOL, we can assert that for ID inputs, the following constraint should hold:
Markov logic networks provide powerful framework for such probabilistic reasoning. By defining a probability dis- tribution over the semantic space based on weights Iearned from ID data, MLNs allow for the integration of seman- tic reasoning with probabilistic flexibility. This approach alleviates the rigidity of strict logic-based methods while maintaining interpretability and robustness.
VX CLASS(X) stop.sign COLOR(X) red A SHAPE(X) octagon,
(4)
which states that stop signs must appear as red octagons. By describing the properties of the data-generating distribution at this semantic level, the decision-makiee process becomes more transparent and interpretable to humans.
In our proposed approach, we first use some DNNs to learn the semantic meaning of a set of FOL predicates and func- tions. Next, we check whether some input violates any weighted logical constraints via Markov logic network. Such violations change the sample's OOD score, enabling us to detect outliers that deviate from the known semantic structure of ID data while providing clear rationale for why an input might be OOD. Alg. provides an overview of the score computation, which will be described in the following.
3.1. Standalone MLNS
Given set of constraints and corresponding weights, we could directly use the negative probability -PM as de- fined by Eq. (2) as outlier score. However, computing the partition function Eq. (3) is computationally demanding, as it involves summation over 2. Since the partition function is identical for all inputs, and strictly monotonic transfor- mations, such as multiplication with a positive factor and exponentiation, will not change the ordering of the outlier scores, propose use the following outlier score:
Connecting DNNs and FOL Semantics To apply logical statements like Eq. (4) for OOD detection, we must bridge the gap between the high-level semantics of the used log- ical predicates and functions and the raw pixel space. In FOL, this connection achieved through the interpretation I. which determines which predicates evaluate to true for given input. Because manually specifying these interpre- tations for high-dimensional inputs is prohibitive, we train DNNs to approximate them. For instance, a neural color- classifier oR (x) outputs logits for candidate colors, and we take the arg max to decide if x is, e.g., "red". Given a set of DNNs which serve as interpretation I, an input x can
Dm(x) = Σ (x):
6
Omitting these operations significantly accelerates inference (see Section 5.4). While this comes the cost of probabilis- tic interpretability of the MLN outputs, this is not required for OOD detection. Furthermore, since D.M is just the neg- ative weighted sum of the satisfied constraints, the resulting score can be casily decomposed into the contribution of the individual constraints: if all constraints are satisfied, the outlier score is Σ, w;. The violation of constraint yo; will increase the score by wis Note, however, that weights can
3

---

Improving -iitrf--Ditirbution Detection with Markov Logic Networks
3.3. Supervised Training
OOO
ooD
Doniity
One of the most effective approaches in OOD detection remains the supervised training of a model with set of aux- iliary outliers (Hendrycks et al., 2018; Dhamija et al., 2018). However, the existing techniques have disadvantage: They usually reduce the model's classification accuracy on ID data or require special training schemes. They also have the same limitations as outlined in the introductory section.
Mr
-0.2
0.2
0.4
0.1
0.2
0.3
01.
0.5
VIM Outlier Soore
Mabalintbis Outlier Scoce
(a) ViM
(b) Mahalanobis
We can leverage the modularity of our approach by extend- ing existing MIL with additional predicate Pin for the concept of ID, which can be learned from auxiliary dataset containing ID and OOD data. Afterwards, we extend the knowledge base with a constraint that asserts that each input should be ID. Compared to existing approaches, this does not require any changes to the remainder of the system.
Figure 1. Distribution of outlier scores on ID samples from the CelebA dataset and some OOD data. A fitted generalized extreme value distribution (GED) in grey. Survival function below.
be negative, constraint violations could also effectively decrease the score.
Algorithm Combined Outlier Score Computation
3.2. Combining MLNs and existing OOD Detectors
1: Input: Input x, constraints sp with interpreted functions F and predicates pT, constraint weights w, normal- ization function pp, OOD detector D
Given DNN-based interpretation of some predicates, the MLN can determine how plausible the semantic representa- tion of some input is. but it does not directly account for how unusual the input appears in terms of its neural representa- tion. Conversely, common OOD detectors rely on neural representations but neglect explicit semantic constraints. Combining these complementary signals could potentially yield more robust OOD detection.
2: Output: Outlier score for x
3: oD < D(x)
4: op + (DD)
5: 2 = (F7 (x).)...., (x).
PT (x))
6: 0M + - (x))())
o = OM x D
return o
Score Normalization Different OOD detectors produce outlier scores on different scales, which complicates direct fusion (see Fig. 1). To address this, we propose to normalize an existing detector's s scores (xx) into the [0, 1] range by estimating its distribution pD on ID data. Specifically, for any new input x, we compute the survival function
4. In-Distribution Constraint Search
Given the absence of prior knowledge about constraints for some domains, we propose an algorithm to automatically learn constraints for OOD detection from data.
PD (Dxx)) = P(D(X) 2 D(x)),
A logical constraint, as used here, can be represented as full binary tree, where the leaves are (possibly negated) predicates or functions with an equality constraint, and the branches are binary logical connectors. An example is pro- vided in Fig. 2. For some sets of predicates and functions, let T be the set of all possible formulas representable by trees up to a certain depth (possibly subject to additional constraints on the tree's structure). We are then searching for an optimal set of formulas that maximizes the weighted sum of performance measure J of the resulting detector and an optional regularization term C' that penalizes the complexity of solution candidate to improve the general- ization of the found constraint set. Formally, we want to solve
which indicates how extreme the observed score is relative to ID samples.
Score Combination Once the baseline detector's outlier scores are normalized, we multiply them by the MLN-base outlier score, (x)(
(x) = DM((x) x (D(x)))
Intuitively, D (x) captures the semantic plausibility of x, while pD(D(x quantifies how rare x's neural representa- tion among ID samples. Since the survival function PD provides normalized values in bounded interval, we can omit the costly evaluation of the partition function Eq. (3) for the MI.N without affecting the overall ranking of outlier scores and, depending on the choice of distribution family, evaluating Pn is much faster. We note that if D already pro- duces normalized outputs, additional normalization might not be required.
max (E9A(T)
E (XXx.Xx00)) [J Xi,, XOOD)] -X
C(p)
Performance
Complexity
where D denotes the powerset, and À E Rgo is a balancing weighing factor.

---

Improving Out-of-Distribution Detection with Markov Logic Networks
Algorithm 2 Greedy Constraint Set Search
1: Input: Training set Duain. validation set D baseline performance Jo, set of possible constraints 'T
CLASS(x)= = =sop
2: Output: Set of constraints yp
3: Initialize +-
-COLOR(x) = blue
(SLOCTAGON(x)
4: Initialize + Jo
for each constraint sp; do yp + u (Pr)
Figure Representation of constraint as tree depth
Train detector with sp' Dunin
8:
J' <- Evaluate detector on V
Performance As measure of performance J of set of rules 9,, we can use the AUROC of the resulting detector D. The AUROC of D can be interpreted as the probability that a randomly drawn ID example receives higher outlier score than a randomly drawn OOD example:
9:
if J' J + 8mn then
10:
+ J'
11: yp + 4-'
12: end
13: end for
AUROC Exxx Xums [L[ ((xoo)) > D(xD)) (10)
14: return 4p
where 1 denotes the indicator function.
color=red and shape=octagon, into PyTorch op- erations. These operations can be executed for many in- puts in parallel, which allows efficient checking of large number of points against constraint during training and inference.
Complexity As measure of complexity C' of a set of rules sp, we use the number of constraints |sp).
Optimization Directly solving Eq. (9) by exhaustively evaluating all possible subsets of constraints is computation- ally infeasible for all but the smallest instances, as would require evaluating 2 combinations. To address this, we adopt greedy search strategy, described in Alg. 2. The pro- cedure begins with an initially empty (or partially specified) set of formulas sp. At each iteration, candidate constraint from the remaining pool is considered for inclusion. The augmented set is then used to train a detector on the train- ing set D irinn and evaluated on the validation set Dval, which contains both ID and OOD samples enable empirical esti- mation of the AUROC. A candidate constraint is retained only if it results in an improvement of the objective value. As we only consider adding a single constraint in each itera- tion, the complexity penalty implies that we will only accept the current candidate constraint if it improves the AUROC by least 6min E R>u- other words, in Alg. 8min serves the À weighting factor of the complexity penalty. While this greedy approach does not guarantee globally optimal solution, it significantly reduces the computational burden, requiring only [T] evaluations.
Choice of Distribution Family Empirically, we observe that the distribution of outlier scores of several existing detectors can be modeled with sufficient accuracy by gen- eralized extreme value distribution (GED) (see Fig. 1), and we will use this distribution family to model the survival function outlier scores in the following. An ablation study is provided in Section 5.4.
DNN and MIN Optimization During training, first optimize the parameters of the DNNs by minimizing the cross-entropy on some training data. Subsequently, the MINS parameters w, which we initialize with 1,, are opti- mized by minimizing the negative log- likelihooood, as
min W
Σ - log (M)()
(11)
D
XEDI
using the L-BFGS optimizer for 10 epochs with learning rate of 0.01. For large MLNs, optimizing the pseudo-likelihood instead could provide performance speedups (Richardson & Domingos, 2006).
5. Experiments
Dittr--Distribution Data As OOD test data, we use images from 8 different sources that cover near and far OOD data, including cropped and resized variants of the LSUN (Yu et al., 2015) and the TinylmageNet datasets, Gaussian and Uniform Noise, Places356 (Zhou et al., 2017), and iNaturalist (Van Horn et al., 2018). During constraint search, we use Textures (Cimpoi et al., 2014) as OOD data. For the supervised variant, we use database of tiny im- ages (Hendrycks al., 2018) as OOD training data.
The source code for our experiments available online.!
5.1. Implementation & Experimental Setting
Compiling Constraints We implement a compiler that transforms constraints formulated in human- understandable format, such as class=stop.sign ->
"https://gtt thub. /kk rchhei m/mmmmmmn
5

---

Improving Out-of-Distribution Detection with Markov Logic Networks
Seed Replicates Several works have found that training DNNs several times from different initializations can yield significantly different experimental results (Bouthillier et al., 2019; Summers& & Dinneen, 2021). We, therefore, replicate experiments several times with different random seeds to mitigate the effects of statistical fluctuations.
poses greater challenges for several reasons: Firstly, there is limited prior knowledge about possible constraints govern- ing the combinations of attributes. Secondly, the constraints in this dataset are likely softer than those in the GTSRB. For example, while it is reasonable to assume that individuals with grey hair are not young, there might plausibly be excep- tions. Lastly, prior work has identified significant labeling noise in the dataset (Lingenfelter et al., 2022), which likely reduces the effectiveness of strict constraint checking. Con- sequently, we expect probabilistic treatment to provide significant advantages over strictly logical approach.
5.2. Traffic Sign Classification
The German Traffic Sign Recognition Benchmark (GTSRB) dataset (Stallkamp et al., 2012) contains approximately 40,000 images of German traffic signs spanning 43 classes. While the dataset provides labels for the type of sign, addi- tional labels for the color and shape of each sign are known priori. This prior knowledge can be encoded into knowl- edge base containing statements resembling Eq. (4), which associate each traffic sign class with the usual color and shape. Note that no additional labeling is needed.
We apply the proposed Alg. 2 for constraints up to depth 2, constructed from selected 14 predicates. We use the implication (-+ as a logical connector which, combined with a negation (-), is functionally complete- and 6min 0.01 (i.e., we select a constraint if it increases the validation AUROC by at least 1 1%). The search over all 702 candidates yielded the following set of constraints:
Setup We train different WideResNet-40s (Zagoruyko & Komodakis, 2016) for the functions and predicates of the domain: CLASS, SHAPE, and COLOR. The original training set is split into 35,000 images for training, and 4,209 images for validation, with all pictures resized to 32 x 32. The DNNs, which were pre-trained on a downscaled variant of the ImageNet, are then further trained for ten epochs using mini-batch SGD with Nesterov momentum of 0.9, an initial learning rate of 0.01 with a cosine annealing schedule (Loshchilov & Hutter, 2017), and a batch size of 32. For the supervised variant, we additionally train DNN for the ID- ID-predicate PID (see Section 3.3).
Vx YOUNG(X)
(12)
Vx HEAVY -MKKUUPX) - GRAY (HARR()))
(13)
Vx WEARING WEARING.LIPSTICKI LIPSTICK(X) - GRAY HAIR(X)
(14)
Vx WEARING LIPSTICK(X) - NO BEARD(X)
(15)
VX -MALF(X) + NO_REARD(X)
(16)
Setup For this dataset, we use ResNet-18: (He et al., 2016) pre- -e-ttriined on ImageNet (Russakovsky et al., 2015). All im- ages are resized to 224 x 224. We split the data into 150000, 2599, and 50000 images for training, validation, and test- ing. respectively. Each DNN is trained for ten epochs using mini-batch SGD with a Nesterov momentum of 0.9, an initial learning rate of 0.01 with a cosine annealing sched- ule (Loshchilov & Hutter, 2017), and a batch size of 32. Again, additionally train DNN fiD to distinguish be- tween ID and OOD data.
Results The results are listed in Tab. 1. The naive MIN detector Eq. (6) achieves an AUROC > 86%, significantly above random guessing. This demonstrates that many OOD inputs can be detected on a purely semantic level. Further- more, combining the MLN with other OOD detectors outper- forms all purely pattern-based OOD detectors. For example, MI.N+Ensemble reduces the FPR95 by > 37% relative to the ensemble baseline. The observed AUROC improve- ment for the combined MLN+Ensemble compared to the standalone Ensemble of the individual detectors, while nu- merically small, is statistically significant (t-test p < 0.05) and has large effect size (Cohen's d R 1.27). When incor- porating auxiliary outliers, the supervised MLN+Ensemble++ achieves almost perfect scores, significantly outperforming all other methods, including the supervised approach based on logical reasoning.
Results Results for experiments on the CelebA dataset are provided in Tab. 1. MLN, on its own, outperforms random guessing and several other OOD detectors. Combined detec- tors incorporating an MIN sometimes outperform both the original detector and the MLN. For example, combining the Mahalanobis method and an MLN (MLN-Mahalanobis) re- duces the FPR95 by R 20%. Again, using auxiliary outliers during training further increases performance.
5.4. Ablation Studies & Discussion
Generalizing to other OOD Detectors Results for the combination of an MI.N with various OOD detectors, includ- ing those based on posteriors. logits, latent representations, and rectified latents, are provided in Tab. 3. The results demonstrate that incorporating an MLN-based semantic OOD detection consistently enhances the performance of
5.3. Face Attribute Prediction
The CelebA dataset (Liu et al., 2015) comprises approxi- mately 200,000 images with 40 binary attribute annotations, covering concepts such as gender, age, the presence of facial hair, and more. Compared to the GTSRB dataset, CelebA
6

---

Improving cnttof-Diisributtinn Detection with Markov Logic Networks
Table Mean performance and corresponding standard error of different OOD detection methods in our experiments. Results averaged
over ten experimental trials with different random seeds. The best result is in bold, and the second best is underlined. 1 indicates that higher values are better, while indicates the opposite values in percent.
Reasoning
Super- vision
AUROC 1
AUPR-ID
AUPR-OOD
FPR95
GTSRB
(Stilkkamp al., 2012)
MSP (Hendrycks & Gimpel. 2017)
X
98.96
+0.25
99.04
=0.30
96.62
+:1.19
3.04
=0.81
ERO (Liu ol., 2020)
99.05
+0.34
98.85
+-0.39
98.28
+0.46
3,58
+1.80
Eusemble (Lakshminnraaaann 2017)
+0.03
99.84
#0.05
=0.15
SHE: (Zhong et al,, 2022)
X
84.13
+22.8
83,23
+4.39
84.69
+1.63
61,00
+9.20
Mahalanobis (Lee et al. 2018)
99.23
+0.08
99.55
=0.
94.67
+2.31
1.85
=0.27
VIM (Wang al. 2022)
99.47
+00.88
99.63
+-0.33
97.30
+1.18
1.71
+0.30
DICE (Sun & Li, 2022)
99.04
+0.35
98.83
98.24
+0.47
3.62
#1.82
(Sun et al., 2021)
+0046
4.0.53
#1.86
Logic (Kirchheiim al. 2024)
Logical
86.
++0.8
91.73
+-2.4
90.72
+11.78
93,76
#4.19
Logic+Ensemble (Kirchheim al., 2024)
Logical
99.85
1.0.01
99.90
1.0003
99.35
1.0.29
0.48
1.0008
MLN (ours)
Probubilistic
86.16
++0.58
91.72
+22225
89.66
93,76
+4.19
MLN+Ensemblc (ours)
Probabilistic
99.89
+0002
99,90
#0.03
99.57
+0.17
0,54
=0.10
MrMalllanahis (ours)
Prohuhilistic
+-0.03
+-0.07
+0.70
+0.17
Dogic=Ensemble (Kirchheim al., 2024)
Logical
99.82
+40.00
99.93
+:0.01
99.32
4-0.32
0,36
+0.00
ML MLNeensemblee+ (ours)
Probabilistic
99.95
++0.0
99.97
+:0.01
99.74
+0.12
0.13
=0.01
MINN+Mahalanbbie- (ours)
Probabilistic
99.93
1.0.01
1.0.02
10.06
CelebA (Liu al.,, 2015)
MSP (Hendrycks & Gimpel, 2017)
X
48.08
++4.0
85.06
#:3.29
13.42
+2.80
85.59
=9.54
al., 2020)
4:3.03
77.22
47.69
Frstemile (I aksshminaraaaam et 11, 2017)
X
83.43
+-235
95.21
+1.86
48.51
+44.02
43.09
+7.23
SHE (Zhang et ul., 2022)
39.78
1.2.91
82.63
15.38
12.22
1.3.05
77.70
15.40
Mahalanobis (I (eeeet 2018)
95.12
+1.18
98.72
+00.36
80.68
+33778
17.77
+3.98
VIM (Wang et al., 2022)
X
84.94
13.82
93.75
12.99
69.62
16.51
48.59
111.30
DICE (Sun 2022)
46.83
+-4.55
+5.59
+22.97
76.05
#7.92
ReAct (Sun 2021)
X
44.84
1:4.22
82.29
25.50
12.69
1:3.03
77.53
88.37
Logic (Kirchheim et al., 2024)
Logical
$1.06
1:3.59
85.86
13.98
44.24
4:3.05
91.64
45.48
Logic+Ensemble (Kirchheim al., 2024)
Logical
54.46
76.55
MLN (ours)
Probabilistic
84.13
1.2.40
96.31
1:1.14
57.88
1.4.40
41.63
16.71
MLN+Ensemble (ours)
Probabilistic
90.42
1:173
97.48
1:0.8
65.23
1:4.12
24.84
1.77
MINN+Mahulamsbis (ours)
Probabilistic
96.01
1.0.4
99.01
1.0.28
80.98
1:3.01
14.17
1..18
Logie-Ensemblet /Kirchheim et al., 2024)
Logical
64.30
1:2.25
91,38
2:4.01
57.43
1:1.88
68.73
22.67
ML.N-Ensemlle+ (ours)
Probahilistic
97.42
4:1.72
1.0.98
4:3.52
.5.23
MLN++Mahllaoobis (ours)
Probabilistic
97.86
1.042
99.41
2:0.25
87.41
11.32
7,82
11.75
OOD detectors based on neural representations alone. This suggests that probabilistic reasoning over semantics offers a complementary signal for OOD detection, distinct from the pattern-base based signals identified by these detectors. Further- more, supervised training yields additional improvements, confirming the effectiveness of our approach in increasing detection performance.
intuitively be detrimental to the effectiveness of our ap- proach. To test this hypothesis, we train DNNs on the GT- SRB dataset using a linear classifier h; on top of a shared WideResNet-400 encoder & such that the DNNs f. = h, that constitute the interpretations of the used logical pred- icates and functions share parameters. Performance mea- surements averaged over several training runs are listed in Tab. 4. We observe a significant drop in the performance of MIN- and Logic-based methods compared to models with- out shared parameters, as expected. Still, the MLN-based approach outperforms logical constraint checking.
Generalization other DNNs To evaluate the MI.'s generalizability across different backbones, we conducted experiments using several DNN-based feature encoders in an otherwise identical experimental setting. The results, presented in Tab. 2, show the performance on the GTSRB dataset. As anticipated, more powerful backbones yield superior performance for the ensemble baseline as well as the standalone MIN. Integrating MIN with the ensem- ble method consistently outperforms both individual ap- proaches.
Omitting Constraints We would expect detection perfor- mance to increase as constraints are incrementally added to the system. Results for the GTSRB with varying numbers of constraints are shown in Fig. 3. As we can see, the MLN with small number of rules barely outperforms random guessing. However, as the number of rules increases, we ob- serve a monotonic improvement in performance. The results further indicate that certain constraints have a more signifi- cant impact on the MLN's performance than others. Here, the rule for the stop sign particularly increases performance.
Parameter Sharing Sharing parameters between DNNs decreases computational and memory requirements but could lead to correlated prediction errors, which would
7

---

Improving Out-of-Distribution Detection with Markov Logic Networks
Table 2. Performance of methods with different encoders GTSRB, Results averaged over ten seed replicates. For the Vision Transformer, images have been resized to 224 x 224.
Model
Re
ConvNext Tiny (Liu et al., 2022)
WideResNet-40
ViT
(He et ul., 2016)
(Zugoruyko & Komodakis, 2016)
(Dosovitskly et al., 2021)
AUROC1 1
FPR95
AUROC1
FPR95
AUROC
FPR95 1
AUROCT
FPR95 |
Ensemble
96.8
10.1
99.1
3.9
99.8
0.85
99,9
0.28
MLN (ours)
81,9
97.5
84.4
100.0
86.2
93,8
90.3
82.5
MI Ml.Neenseelle (ours)
98.0
8.3
99.5
2.9
99.9
0.54
99.9
0.17
99.90
Table 3. AUROC for different detectors using patter-based base- line detector, combination with MIN,, and a supervised MI.N- based detector. All values in percent, results averaged over ten diffcrent random seeds. A indicates the difference to the next left column.
AUROC
99.85
99.80
Detector
Detector
+MLN
Supervision
0
10
20
30
40
GTSRB (Stallkamp et al., 2012)
MSP
98.96
99.60 & 0.64
99.90 A 0.30
80
AUROC
Ensemble
99.80
99.88 A 008
99.96 A 0.08
Envemble
EBO
99.05
99.50 A 0.45
99.77 A 0.27
DICE
99.04
99,50 & 0.46
99.77 A 0.27
MLN
SHE
84.13
95.04 & 10.91
99.83 A 4.79
M-N-Ennembble
ReAct
96.85
99.09 A 2.34
99.92 A 0.8
10
40
Mahalanobis
99.23
99.72 A 0.49
99.96 A 0.23
Number of Rules
ViM
99.47
99.80
0.35
99.96 A 0.16
Figure 3. OOD detection performance on GTSRB for different numbers of constraints.
CelebA (Liu al., 2015)
MSP
48.68
60.72 A 12.04
71.10 L 10,38
Ensemble
83.43
90.42 & 6.99
97.42 A 7.00
Ensemble
EBO
45.24
73.89 & 28.5
89.89 & 16,00
40
DICE
46.83
74.98 & 2816
90.31 & 15.32
40
30
Val
SHE
39.78
71.54 & 31,76
89.75 A 18211
ReAct
44.84
72.06
27,22
89.55
10
5
4
Muhalanobis
95.12
96.01 &
97.86 185
100
VIM
84.94
91.75
97.12 A
95
AUROC
90
85
Constraint Search Regularization By varying the weight of the regularizer Ómin. we can trade off the complex- ity of the found rule set and its performance. An example is provided in Fig. 4: for 7min = 0, that is, without regular- ization, the algorithm identifies 40 constraints but overfits. Increased regularization decreases the number of rules and reduces overfitting up to a certain limit, after which the performance deteriorates again.
80
0.00
0.01
0.02
0.03
0.04
8min
Figure 4. Number of identified constraints and corresponding MLN+Ensemble performance for greedy constraint search on CelebA with varying regularization weight 8mi..
Method
NLN-EBsemble
Inference Time (ms)
10a
ML.N-Ensemlle wio Partition
Eneemble
Computational Overhead Fig. 5 depicts inference time and batch size on the GTSRB, averaged over 100 batches on an Nvidia A100. Checking the 43 constraints introduces a moderate computational overhead of several milliseconds per batch. Omitting the computation of the partition function reduces the overhead. For batch sizes > 128, the inference time is dominated by the computation required by DNNs because constraint checking is memory efficient and can be parallelized, leading to a constant overhead, even for large batch sizes.
MSP
10!
20
21
2
23
24
25
26
2
28
29
210
211
Batch Size
Figure 5. Inference time and batch size for GTSRB with 43 con- straints. The MLN introduces moderate computational overhead during inference compared to the ensemble.
8

---

Improving Out-of-Distribution Detection with Markov Logic Networks
Table Performance GTSRB for models sharing parameters between DNNs. The As indicate the difference to models without parameter sharing. All values percent.
Table 5. Effect of the distribution family used for outlier score normalization on AUROC (in percent). Higher values indicate better performance.
Detector
AUROC
FPR95 |.
Distribution
MLN+Ensemble
MLN+ViM
Ensemble
99.14
A 4-0.7
3.28
A.242
GED
99.88
99.80
Logic
47.69
--38.47
100.00
6.624
Uniform
99.76
99.46
Logic+Ensemble
56.96
A 42290
60.01
A 5,5953
Normal
99.07
98.13
MLN
53.61
A 32.55
100.00
6.244
Generalized Normal
98.67
99.63
EINNEnsemble
98.88
A-1.01
3.67
3.3.9
LogNormal
98.60
99.79
No Normalization
86.16
86.16
MSP Coufidence: 99.8
MSP Contdence: 9 Labd: Prisety Ruad Stape: Cirds
MSP Confidence 100,0 % Labdl: Sky Shape: Tringle
Labeh: Gise Way Shape: Cirole
96
AUROC
93
Places365
LSUNCrop
iNauralist
Tiny NeggnageNNeReiize
LSUNResize
UniformNois
GaussianNoise
Tuyymage
(a)
(h)
Figure 7. OOD samples with MSP confidence as predicted by DNN trained on the GTSRB dataset.
Figure Influence OOD datasel used for constraint search on evaluation performance for Mahaaahalanobis. Mahalanobis baseline performance is marked in red.
Explainability Fig. 7 depicts sample of OOD images for the GTSRB, together with the detected concepts and confidence predicted by the MSP baseline. Since the de- tected combination of concepts violates the constraint for the corresponding traffic sign, our method would increase the outlier score, and this increase can be traced back to specific rules. For example, Fig. 7c, the constraint that a stop sign implies an octagonal shape is violated. Since this constraint's weight 4.89, the violation of this constraint increases the outlier score the MLN assigns to the input by the same amount.
Influence of OOD Dataset The constraints discovered by the search algorithm are sensitive to the specific OOD dataset used during optimization. To investigate this de- pendency, we performed a constraint search independently for each OOD dataset included in our evaluation, and subsequently assessed the performance of the resulting MLN++ahalanobii detector on CelebA. Importantly, dur- ing evaluation, the OOD dataset used for the constraint search was excluded to simulate realistic generalization to unseen outliers. The results, shown in Fig. 6, indicate that performance typically surpasses the baseline, with the no- table exception of Gaussian Noise. This suggests that the diversity and realism of the training-time OOD samples play role in learning effective constraints.
6. Conclusion
In this work, we presented a novel framework for OOD detection based Markov logic networks that probabilis- tically verifies logical constraints over a low-dimensional semantic representation of a given input. This approach can be combined with various existing OOD detectors and backbones to increase OOD detection performance while providing a certain degree of interpretability. We also intro- duced a simple algorithm that can be used to automatically derive such logical constraints from dataset.
Influence of Normalization Tab. presents the effect of different distribution families used normalize outlier scores on detection performance. Among the tested options, the GED yields the highest AUROC scores across both MInN+en and ViM detectors. In contrast, omitting normalization leads to a substantial performance drop. These results highlight the critical role of selecting a well-matched distributional prior when modeling outlier scores.
A ckknowledgmnnt
This research received funding from the Federal Ministry for Economic Affairs and Climate Action (BMWK) and the European Union under grant agreement 19121039A.

---

Improving Out-of-Distribution Detection with Markov Logic Networks
Impact Statement
Cimpoi, M., Maji, S., Kokkinos, I., Mohamed, S., and
Vedaldi, A. Describing textures in the wild. In Pro- ceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 3606-3613 2014.
Advances in OOD detection, particularly in Neuro- Symbolic approaches, could potentially benefit the deploy- ment of safe Machine Learning-din world. While the societal impact of this is broad, we do not consider it specific to our work.
systems in the real
Dhamija, A. R., Günther, M., and Boult, T. Reducing net- work agnostophobia. In Advances in Neural Information Processing Systems, pp. 9157-9168, 2018.
The proposed algorithm Alg. 2 for learning constraints for OOD detection introduces the possibility of embedding discriminatory biases against underrepresented minority classes into the broader system. For instance, in the Face Attribute Prediction use case analyzed in our experiments, the learned in-distribution constraints, such as
Djurisic, A., Bozanic, N., Ashok, A., and Liu, R. Extremely simple activation shaping for out-of-distribution detection. International Conference on Learning Representations, 2023.
Dosovitskiy, A., Beyer, L.., Kolesnikov, A., Weissenborn,
VX MA)E(()) NO_BEARD(x)
D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 words: Transformers for image recognition at scale. International Conference on Learning Representations, 2021.
may be considered culturally contextually insensitive, as they might fail to capture the diversity of the population outside of the training distribution.
While this is a general problem in machine learning, com- pared to prior works, Markov logic networks offer several advantages in addressing these sensitive scenarios:
Gal, Y. and Ghahramani. Z. Dropout as Bayesian approxi- mation: Representing model uncertainty in deep learning. In International Conference on Machine Learning, pp. 1050-1059. PMLR, 2016.
Since the rules governing the detector's behavior are explicit and human-undens unnnaaabderst (as opposed to en- coded in the weights of a connectionist system), biases are more apparent and can be more easily identified and addressed.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learn- ing for image recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
He, K., Gkioxari, G., Dollár, P., and Girshick, R. Mask R-CNN. In Proceedings of the IEEE International Con- ference on Computer Vision, pp. 2961-2969, 2017.
Compared to methods like LogicOOD (Kirchheim et al., 2024), the employed probabilistic approach is able to learn weights flexibly, which allows the algo- rithm to account for violations of constraints given adequate representation of such cases in the training dataset.
Hendrycks, D. and Gimpel, K. A baseline for detecting misclassified and out-of-distribution examples in neural networks. International Conference on Learning Repre- sentations, 2017.
Furthermore, manually adjusting individual constraint weights is possible and has an intuitive interpretation.
Hendrycks, D., Mazeika, M., and Dietterich, T. Deep anomaly detection with outlier exposure. In International Conference on Learning Representations, 2018
Therefore, we believe that the transparency of the presented approach advances its potential to comply with ethical stan- dards.
Hendrycks, D.,, Basart, S., Mazeika, M.. Mostajabi. M., Steinhardt, J., and Song, D. Scaling -ut-of-dist detection for real-world settings. International Confer- ence Machine Learning, 2022.
References
Besold, T. R., d' Avila Garcez, A., Bader, S., Bowman, H.,
Kirchheim, K., Filax, M., and Ortmeier, F. PyTorch- -OD:: library for out-of-distribution detection based on PyTorch. In Proceedings of the IEEF/CVF Conference on Com- puter Vision and Pattern Recognition (CVPR) Workshops, pp. 4351-4360, June 2022.
Domingos, P., Hitzler, P., Kühnberger, K.-U., Lamb, L. C.,
Lima, P. M. V., de Penning, L., et al. Neural-symbolic learning and reasoning: A survey and interpretation 1. In Neuro-Symbolic Artificial Intelligence: The State of the Art, pp. 1-51. IOS press, 2021.
Kirchheim, K., Gonschorek, T., and Ortmeier, F. Out-of- distribution detection with logical reasoning. In Proceed- ings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 2122-2131, 2024.
Bouthillier, X., Laurent, C., and Vincent, P. Unreproducible research is reproducible. In International Conference on Machine Learning, pp. 725-734, 2019.
10

---

Improving Out-of-Distribution Detection with Markov Logic Networks
Lakshminarayanan, B., Pritzel, A., and Blundell, C. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Process- ing Systems, pp. 6402-6413, 2017.
M., et al. Imagenet large scale visual recognition chal- lenge. International Journal of Computer Vision, 115(3): 211-252, 2015.
Schmidhuber, J. Deep learning in neural networks: An overview. Neural Networks, 61:85-117, 2015.
LeCun, Y., Bengio, Y., and Hinton, G. Deep learning. Na- ture, 521(7553):436 2015.
Stallkamp, J., Schlipsing, M.. Salmen, J., and Igel, C. Man vs. computer: Benchmarking machine learning algo- rithms for traffic sign recognition. Neural Networks, 32: 323-332, 2012.
Lee, K., Lee, K., Lee. H., and Shin, J. A simple unified framework for detecting -ito---distrbbttion samples and adversarial attacks. Advances in Neural Information Pro- cexsing Systems, 31, 2018.
Summers, C. and Dinneen, M. J. Nondeterminism and instability in neural network optimization. In Interna- tional Conference on Machine Learning, pp. 9913-9922 PMLR, 2021.
Lingenfelter, B., Davis, S. R., and Hand, E. M. A quanti- tative analysis of labeling issues in the CelebA dataset. In International Symposium on Visual Computing, pp- 141. Springer, 2022.
Sun, Y. and Li, Y. Dice: Leveraging sparsification for out- of-distribution detection. In European Conference on Computer Vision, pp. 691-708. Springer, 2022.
Liu, W., Wang, X., Owens, J., and Li, Y. Energy-basede out- of-distribution detection. Advances in Neural Information Processing Systems, 33, 2020.
Sun, Y., Guo, C., and Li, Y. React: Out-of-distributis detection with rectified activations. Advances in Neural Information Processing Systems, 34:14 14:1444-55) 157, 2021.
Liu, Z., Luo, P., Wang, X., and Tang, X. Deep learning face attributes in the wild. In Proceedings of the IEEE International Conference on Computer Vision, pp. 3730- 2015.
Van Horn, G., Mac Aodha, O., Song, Y., Cui, Y., Sun, C.,, Shepard, A., Adam, H., Perona, P., and Belongie, S. The INaturalist species classification and detection dataset. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, June 2018
Liu, Z., Mao, H., Wu, C.-Y., Feichtenhofer, C., Darrell, T., and Xie, S. A convnet for the 2020s. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11976-1198, 2022.
Wang. H., Li, Z., Feng, L., and Zhang, W. Vim: Out-of- distribution with virtual- matching. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 4921-4930, 2022.
Loshchilov, I. and Hutter, F. SGDR: Stochastic gradient descent with warm restarts. International Conference on Learning Representations, 2017.
Yang, J., Zhou. K., Li, Y., and Liu, Generalized out-of- distribution detection: A survey. International Journal of Computer Vision, 132(12), 2024.
Lu, S., Wang, Y., Sheng, L., Zheng, A., He, L., and Liang, J. Recent advances in ood detection: Problems and ap- proaches. arXiv preprint arXiv:2409.1 1884, 2024.
Yu, F., Seff, A., Zhang, Y., Song. S., Funkhouser, T., and Xiao, LSUN: Construction of a large-scale image dataset using deep learning with humans in the loop.
Nguyen, A., Yosinski, J., and Clune, J. Deep neural net- works are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE Con- ference on Computer Vision and Pattern Recognition, pp. 427-436, 2015.
arXiv preprint arXiv: 1:X6vv/550603355 /506.03365 2015.
Zagoruyko, S. and Komodakis, N. Wide residual networks. In British Machine Vision Conference 2016. British Ma- chine Vision Association, 2016.
Richardson, M. and Domingos, P. Markov logic networks. Machine Learning, 62(1):107-136, 2006.
Zhang, J., Fu, Q.. Chen, X., Du, L., Z.,, Wang, G., Han, S., Zhang. D., et al. Out-of-distribution detection based on in on-distribution data patterns memorization with modern hopfield energy. In The Eleventh International Confer- ence on Learning Representations, 2022.
Ronneberger, O., Fischer, P., and Brox, T. U-Net: Con- volutional networks for biomedical image segmentation. In Medical image computing and computer-assisted in- tervention: 18th international conference, Munich, Ger- many, October 5-9, 2015, proceedings, part III 18, pp- 234-241. Springer, 2015.
Zhou, B., Lapedriza, A., Khosla, A., Oliva, A., and Tor- ralba, A. Places: A 10 million image database for scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017.
Russakovsky, O., Deng. J.. Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z.., Karpathy, A., Khosla, A., Bernstein,


Reviews:
[{"review_id": "r6fjdiauI2", "reviewer": "Reviewer_cnXo", "summary": "This work explores enhancing out-of-distribution (OOD) detection using Markov Logic Networks (MLNs), which integrate probabilistic reasoning with logical constraints for improved structure and interpretability. The proposed framework augments existing OOD detectors by incorporating MLNs to define human-understandable logical constraints, enhancing both detection accuracy and explainability. Additionally, a greedy algorithm is introduced to automatically learn logical constraints from data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We sincerely thank the Reviewer for the comprehensive and constructive feedback. Below, we address the specific points raised by the reviewer.\n\n### Contradictory Constraints\n> How does the algorithm handle contradictory constraints?\n\nDuring training, the algorithm can automatically down-weights the conflicting constraints. As a result, the network balances and resolves contradictions based on their relative statistical support in the data.\n\n### NLP or Tabular\n> Have you tested this method on natural images, NLP or tabular data?\n\nWe seek clarification regarding the term \"natural images,\" as we have conducted experiments on image datasets.\n\nRegarding NLP and tabular data, we have not yet tested our approach in these domains. We would greatly appreciate any recommendations from the reviewer regarding specific NLP or tabular datasets they consider valuable for additional evaluation.\n\n### Other Image Datasets\n>  However, the study does not test other OOD detection benchmarks such as CIFAR-10 vs. SVHN or ImageNet-O. \n\nIndeed, our approach relies explicitly on underlying \"structure\" or \"prior knowledge\" inherent to the training data. Such structure is, to our knowledge, absent in benchmarks like CIFAR-10 vs. SVHN or ImageNet-O, as these datasets do not provide semantic constraints or structured knowledge our MLN-based approach is designed to leverage.\n\n### Latency\n> Evaluating constraints and computing MLN weights increase inference time, as shown in Fig. 5 (Inference Time vs. Batch Size). While the paper omits the partition function (Z) in Equation (3) to accelerate inference, this compromises probabilistic interpretability.\n\nThe reviewer’s observation is accurate. Nonetheless, we kindly highlight that, even with the additional overhead, our approach introduces an additional computational overhead of only 2ms/image.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The paper does not have theoretical contribution.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This work builds upon and extends previous research by enhancing OOD detection, a crucial aspect of ensuring the reliability of deep learning models in real-world applications. By referencing and innovating upon existing OOD detection techniques, the paper introduces a novel approach that integrates probabilistic reasoning with logical constraints.", "essential_references_not_discussed": "The work discusses relevant works.", "other_strengths_and_weaknesses": "Strengths:\n\n1. Integrating MLNs with OOD detection is a novel approach.\n\n2. Traditional OOD detection methods (e.g., MSP, Mahalanobis distance) provide only a confidence score.\nThis paper incorporates logical constraints (e.g., \"A stop sign should be red\") and enhances them with MLNs, improving the explainability of the detection process.\n\nWeaknesses:\n\n1. MLNs introduce additional computational overhead to existing deep learning models. Evaluating constraints and computing MLN weights increase inference time, as shown in Fig. 5 (Inference Time vs. Batch Size). While the paper omits the partition function (Z) in Equation (3) to accelerate inference, this compromises probabilistic interpretability.\n\n2. The evaluation is limited to two datasets: GTSRB (German Traffic Sign Recognition Benchmark) and Celeb-A (Face Attribute Prediction), both featuring clear, discrete attributes (e.g., \"STOP sign is RED,\" \"Male vs. Female\"). However, the study does not test other OOD detection benchmarks such as CIFAR-10 vs. SVHN or ImageNet-O. Additionally, no NLP or tabular datasets are considered.", "other_comments_or_suggestions": "Here are some typos:\n\nline 110: \"refered to\" -> \"referred to\"\nline 96: \"were higher weights correspond\" -> \"where higher weights correspond\"", "questions_for_authors": "1. How does the algorithm handle contradictory constraints?\n\n2. Have you tested this method on natural images, NLP or tabular data?", "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": "", "extra_scores": {}}, {"review_id": "3x1QJk6ngg", "reviewer": "Reviewer_8kcf", "summary": "The paper presents a novel approach to OOD detection by integrating Markov Logic Networks (MLNs) with existing OOD detectors. This fusion of probabilistic reasoning with logical constraints over human-understandable concepts distinguishes it from traditional statistical or neural representation-based methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "### Explainability\nQuantitatively measuring explainability remains notoriously challenging, thus we rely primarily on qualitative and structural justification. However, we would highly appreciate if the reviewer could suggest some metrics. \n\nBy construction, our method's explainability stems directly from Equation 6, which explicitly represents the outlier score as a weighted sum of human-understandable constraints. This structure allows clear statements regarding by what amount each constraint violation or satisfaction increased or decreased the outlier score. \n\nAdditionally, we exemplify the practical benefits of our explainable rule sets explicitly in the \"Impact\" section.\n\n### Significance of Improvement\n\n> The assertion of \"significant\" performance improvement is overstated. Table 1 shows that for the GTSRB dataset, the AUROC increases from 99.8% (Ensemble) to 99.9% (MLN+Ensemble), a marginal 0.1% gain.\n\nWe respectfully disagree. The improvement is significant for two reasons:\n\n1. The improvement is statistically significant (t-test $p < 0.05$) with a Cohen's D of $\\approx 1.27$, which indicates an effect size that is considered \"very large\" by conventional standards.\n2. At a baseline performance (99.8% AUROC), a 0.1% absolute increase means effectively halving the remaining error rate.\n\n### Latency\n\n> The claim of maintaining efficiency is contradicted by Figure 5, where inference time for a batch size of 1 rises from ~2ms (baseline) to ~10ms (MLN-augmented), a 5x increase. [...] this undermines the efficiency claim for real-time or resource-constrained applications\n\nThe reviewer compares our method with the simplest baseline (MSP). However, this comparison neglects substantial accuracy improvements: FPR95 error decreases from approximately 3% (MSP) to 0.5% (MLN) - a 83 % error reduction.  \n\nAs Figure 5 shows, the primary overhead originates from using an ensemble rather than the MLN itself. Compared to the Ensemble, our method reduces FPR95 from 0.86% to 0.54% (a 37% reduction) at a cost of 2ms (+20%) per image.\n\nWe kindly emphasize that even under the slowest inference scenario (batch size 1), our method achieves more than 80 frames per second, arguably sufficient for typical real-time application requirements. \n\n### Ablation on OOD Training Distribution\nOur experiments confirm that constraints extracted from datasets exhibiting sufficient complexity (e.g., Textures, iNaturalist, ...) generalize reliably across various OOD scenarios, while constraints mined from e.g., Gaussian Noise, fail to generalize.\n\nWe conducted additional experiments to systematically assess this concern: constraints were mined using specific OOD datasets, explicitly excluding those same datasets from subsequent evaluation.\n\n| Dataset        | Method          | AUROC | FPR95 |\n| -------------- | --------------- | ----- | ----- |\n| iNaturalist    | Ensemble        | 84.06 | 42.54 |\n| iNaturalist    | MLN+Ensemble    | 87.44 | 33.52 |\n| iNaturalist    | Mahalanobis     | 95.20 | 17.66 |\n| iNaturalist    | MLN+Mahalanobis | 95.21 | 17.07 |\n| Places365      | Ensemble        | 84.76 | 41.17 |\n| Places365      | MLN+Ensemble    | 86.14 | 27.90 |\n| Places365      | Mahalanobis     | 95.34 | 17.07 |\n| Places365      | MLN+Mahalanobis | 96.06 | 13.89 |\n| Gaussian Noise | Ensemble        | 82.70 | 47.46 |\n| Gaussian Noise | MLN+Ensemble    | 79.74 | 60.19 |\n| Gaussian Noise | Mahalanobis     | 94.81 | 19.51 |\n| Gaussian Noise | MLN+Mahalanobis | 94.99 | 18.91 |\n\n### Alternative Constraint Optimisers\nWe discuss that exhaustive search is infeasible for realistic problems due to computational constraints. While we concur that more sophisticated search strategies might yield improved results, our straightforward greedy approach already achieves state-of-the-art performance and generalises effectively across multiple DNNs and OOD datasets.\n\n### Auxiliary Outlier Distribution\nWe selected the \"tiny images\" dataset as auxiliary outliers because it is well-established and commonly used in relevant literature, including foundational works such as Outlier Exposure by Hendrycks et al., Energy-based OOD Detection by Liu et al., and the related work on LogicOOD by Kirchheim et al. Thus, the precedent for using this dataset is firmly established.\n\n### Ablation on Score Normalisation\nHere are results (averaged over 10 random seeds) on GTSRB with different distributions choices for Mahalanobis and ViM:\n\n| Normalization      | MLN+Mahalanobis | MLN+ViM |\n| ------------------ | --------------- | ------- |\n| No Normalization   | 72.57           | 35.25   |\n| Normal Dist.       | 96.89           | 98.13   |\n| Uniform Dist.      | 99.21           | 99.46   |\n| Log Normal         | 99.67           | 99.79   |\n| Generalized Normal | 99.08           | 99.63   |\n| GED                | 99.72           | 99.80   |", "claims_and_evidence": "+ The authors suggest that MLNs provide \"improved explainability\" due to their use of human-understandable constraints. Yet, this is poorly substantiated. Figure 6 offers an anecdotal example of an OOD decision, but there’s no systematic demonstration or metric.\n+ The claim of maintaining efficiency is contradicted by Figure 5, where inference time for a batch size of 1 rises from ~2ms (baseline) to ~10ms (MLN-augmented), a 5x increase. While the overhead diminishes with larger batches, this undermines the efficiency claim for real-time or resource-constrained applications\n+ The assertion of \"significant\" performance improvement is overstated. Table 1 shows that for the GTSRB dataset, the AUROC increases from 99.8% (Ensemble) to 99.9% (MLN+Ensemble), a marginal 0.1% gain.", "methods_and_evaluation_criteria": "+ Testing is confined to two datasets, which is insufficient to claim broad applicability. GTSRB (traffic signs) and Celeb-A (faces) are visually distinct and relatively simple compared to diverse OOD challenges (e.g., ImageNet). This narrow scope questions the method’s robustness.\n+ Algorithm 1 employs a greedy strategy to select constraints, but its optimality is not justified against alternatives (e.g., exhaustive search, reinforcement learning). The paper acknowledges this limitation superficially without exploring its impact, weakening confidence in the method’s effectiveness.", "theoretical_claims": "The paper does not introduce new theoretical proofs or claims, relying instead on established MLN theory applied to OOD detection.", "experimental_designs_or_analyses": "+ The supervised variant uses auxiliary outliers, but the choice of these outliers (e.g., tiny images) is not justified, nor is their impact on performance explored.\n+ For Celeb-A, the constraint search uses a validation set with OOD data (Textures), potentially overfitting the constraints to this specific OOD type. The paper does not test against other OOD distributions (e.g., iNaturalist, LSUN) during constraint learning, risking poor generalization.", "relation_to_broader_scientific_literature": "The paper positions itself as an advance over statistical OOD detectors and neuro-symbolic methods like LogicOOD (Kirchheim et al., 2024) by introducing probabilistic MLNs.", "essential_references_not_discussed": "The paper cites neuro-symbolic works (e.g., Besold et al., 2021) but engages superficially, missing a detailed discussion of how MLNs differ from or build on prior probabilistic or symbolic OOD approaches.", "other_strengths_and_weaknesses": "**Strengths**:\n+ The concept of blending semantic reasoning with OOD detection is creative and could inspire future work.\n+ The constraint search algorithm (Algorithm 1) offers a practical step toward automating constraint derivation, a potential asset in knowledge-scarce domains.", "other_comments_or_suggestions": "+ Beyond \"cutlier\" and \"Mathemetically,\" minor grammatical errors persist (e.g., \"then ID data points\" in Section 2.1 should be \"than\"). These suggest a lack of polish.\n+ An ablation on components (e.g., normalization, GED choice) would clarify their contributions.", "questions_for_authors": "Refer to the above comments.", "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": "", "extra_scores": {}}, {"review_id": "8tWN2fNfyZ", "reviewer": "Reviewer_oa1P", "summary": "This paper proposes a novel framework for improving out-of-distribution (OOD) detection using Markov Logic Networks (MLNs), which combine probabilistic reasoning with human-interpretable logical constraints. The approach addresses limitations of traditional OOD detectors, such as reliance on superficial statistical patterns and lack of explainability. Empirical validation across benchmarks, demonstrating superior performance and computational efficiency.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "We sincerely thank the Reviewer for the comprehensive and constructive feedback. Below, we address the specific points raised by the reviewer.\n\n### Comment 2\n\n> the phrase \"maximizes the weighted sum of the discriminative power J\" leaves readers unclear about the meaning of \"discriminative power.\"\n\nThe term \"discriminative power\" is an established concept in machine learning and refers to the classifier's ability to distinguish between classes - in our case, ID and OOD. For binary classification, common performance measures include accuracy and AUROC, with AUROC being particularly prevalent for OOD detection tasks. This definition was explicitly stated immediately following the cited phrase:\n\n> \"As a measure of the discriminative power of the resulting OOD detector , we use the AUROC of the trained detector.\"\n\nA formal description of AUROC follows this explanation.\n\n### Comment 3\n\n>  why we need to penalize the complexity of a solution candidate, how is it calculated, and what is its relationship to Eq. (9)? \n\nThe complexity penalty serves as regularization to avoid overfitting by limiting model complexity. As described in Algorithm 1, we achieve this by only adding rules that enhance performance by at least a threshold $\\delta_{min}$. Appendix A formally demonstrates that this regularization corresponds to using the number of rules $| \\varphi |$ as a measure of complexity. We agree with the reviewer that this relationship could be clarified further and will explicitly include this clarification in a revised manuscript.\n\nFigure 4 in our ablation study illustrates that omitting the complexity penalty leads to models with high complexity (many rules) and decreased generalization performance.\n\nEq. (9) is the definition of the AUROC, which is the measure of discriminative power, $J$, that we optimize for.\n\n### Comment 4 \n\n> The authors proposes a greedy search strategy outlined in Alg. 1 to solving Eq. (8). However, why the strategy could solve the optimization of Eq. (8) is unclear.\n\nIndeed, solving Equation (8) exactly is computationally intractable, as we would have to evaluate $2^{702}$ solutions. Our proposed greedy algorithm runs for $\\approx 1$ hour (702 evaluations), and empirical results demonstrate that it finds solutions yielding strong performance. However, we concur (and do not claim otherwise) that this approach does not guarantee a global optimum compared to exhaustive search strategies, which would be computationally prohibitive.\n\n### Comment 5 \n\n> This suggests that the work represents an incremental advance over prior efforts by employing a different model to express logical rules in the context of OOD detection.\n\nWe respectfully disagree with this characterization. Previous research employed strictly logical rules, whereas our method introduces probabilistic rules through Markov Logic Networks, providing significantly greater expressive power. The advantage of probabilistic over purely logical approaches is clearly demonstrated by our results on Celeb-A, where LogicOOD (Kirchheim et al.) fails, performing no better than random chance, while our method achieves state-of-the-art results.\n\nMoreover, the recent survey \"Recent Advances in OOD Detection: Problems and Approaches\" references only LogicOOD (Kirchheim et al.) within this methodological paradigm. We explicitly compare against this baseline and surpass it in all experimental setups, underscoring the novel and substantial contribution of our work.\n\n### Comment 6 \n\n> present an overall algorithmic framework first, and if the detailed steps of a specific component are complex, include supplementary algorithmic details for clarity.\n\nWe kindly request the reviewer to consider that we have provided complete source code for all experiments as supplementary material, ensuring transparency and reproducibility. Due to space constraints, explicitly detailing every algorithmic aspect within the main paper has been challenging.\n\nTo clarify, our method follows a straightforward process:\n\n1. We first pass the input x through several deep neural networks (DNNs).\n2. Based on the outputs of these DNNs, we calculate a baseline outlier score.\n3. We normalize this baseline outlier score by estimating the probability that ID inputs receive an outlier score that is greater $P(D(x) > X)$. \n4. Concurrently, we compute a separate outlier score using weights of our trained MLN.\n5. Finally, we obtain our overall outlier score by multiplying these two scores.\n\nIn the additional page permitted for revisions, we will include an explicit and concise algorithmic description of these steps to further enhance clarity.\n\n### Question 1 \n> [...] “Additionally, we train a DNN for the ID-predicate”. The training methodology for this component is not described, [...]\n\nThe ID-predicate is produced by a DNN component trained in a supervised manner, as described in Section 3.3.\nWe agree that this connection was not sufficiently explicit and will clearly state this in the revision.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Not applicable, as this paper does not put forward any theoretical claims or provide corresponding proofs.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "The key contributions of the paper are closely related to the fields of out-of-distribution (OOD) detection and Markov Logic Networks (MLNs). The authors propose using MLNs to combine first-order logic constraints with probabilistic reasoning, allowing the model to incorporate human-understandable semantic constraints into the OOD detection process.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1. The authors propose using Markov Logic Networks (MLNs) to combine first-order logic constraints with probabilistic reasoning. This allows the model to incorporate human-understandable semantic constraints (e.g., \"stop signs are red and octagonal\") into the detection process, improving explainability and enabling the integration of prior knowledge.\n2. The framework combines MLN-derived semantic scores with traditional neural representation-based detectors through score normalization and multiplication. This hybrid approach leverages both semantic plausibility and neural pattern recognition, significantly boosting performance. Also, the authors propose an algorithm to automatically learn logical constraints from data when prior knowledge is unavailable. The greedy search strategy selects constraints that maximize detection performance while regularizing complexity, ensuring robustness against overfitting.\n3. Extensive experiments on datasets like GTSRB (traffic signs) and Celeb-A (face attributes) demonstrate that MLN-augmented detectors achieve higher AUROC and lower FPR95 scores compared to standalone methods.\n\nWeaknesses:\n1. The inline formula in Line 181 is missing a label and fails to clearly explain how the specific values are calculated.\n2. Section 4 needs to be reorganized and polished, as some sections lack clarity. For example, the phrase \"maximizes the weighted sum of the discriminative power J\" leaves readers unclear about the meaning of \"discriminative power.\"\n3. There is a lack of explanation and transition for the interpretation of C(\\phi) in Eq. (8). For example, why we need to penalize the complexity of a solution candidate, how is it calculated, and what is its relationship to Eq. (9)? \n4. The authors proposes a greedy search strategy outlined in Alg. 1 to solving Eq. (8). However, why the strategy could solve the optimization of Eq. (8) is unclear.\n5. In Section 1, it mentions that “neuro-symbolic approaches for OOD detection have shown promise in addressing these limitations”. This suggests that the work represents an incremental advance over prior efforts by employing a different model to express logical rules in the context of OOD detection.\n6. Additionally, it is recommended to provide a complete algorithmic workflow rather than focusing solely on the algorithmic steps of a minor module. Alternatively, present an overall algorithmic framework first, and if the detailed steps of a specific component are complex, include supplementary algorithmic details for clarity.", "other_comments_or_suggestions": "Please refer to the weaknesses above.", "questions_for_authors": "1. In Line 274, it mentions that “Additionally, we train a DNN for the ID-predicate”. The training methodology for this component is not described, and it remains unclear whether it follows the same training paradigm as the previously mentioned network.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper uses Markov Logic Networks (MLNs), integrating probabilistic reasoning with logical constraints, to realise improved structure and interpretability in out-of-distribution (OOD) detection. The reviewers found this paper (1) proposes novel approaches, (2) the experiments are solid and comprehsive, etc. which I mostly agree with. The reviewers also raised concerns, such as that overhead could incease, which are largely cleared. So, I recommend to accet this paper.
Decision: Accept (poster)