🤖 machine learning

DisjunctiveNet: Neural Symbolic Learning via Differentiable Convexified Optimization Layers

This paper proposes DisjunctiveNet, a unified end-to-end framework that enforces hard, input-dependent mixed-integer linear constraints within neural networks by representing rules as disjunctive constraints and applying hierarchical convex relaxations to create differentiable optimization layers that guarantee exact rule satisfaction.

Original authors: Shraman Pal, Can Li

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shraman Pal, Can Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are training a brilliant but reckless student (a neural network) to solve complex problems. This student is great at spotting patterns in data, but they are terrible at following the rulebook. Sometimes, they make predictions that are mathematically possible but physically impossible or dangerous—like a self-driving car deciding to drive through a solid wall because the data looked "similar" to a tunnel.

In many real-world fields like engineering or biology, we have a strict "rulebook" derived from physics, safety protocols, or expert knowledge. These rules often look like: "IF the temperature is high, THEN the fan must be on OR the AC must be on."

The problem is that standard AI struggles with these "If-Then" rules, especially when the rules change based on the situation. Existing methods try to "nudge" the student with a penalty (like a teacher saying "try harder"), but the student still occasionally breaks the rules. Other methods try to force the rules after the student has already answered, which is like correcting the homework after the test is over—it doesn't help the student learn the right way to think.

Enter DisjunctiveNet.

The authors propose a new framework that acts like a smart, real-time safety harness for the neural network. Here is how it works, using simple analogies:

1. The "Disjunctive" Puzzle

The rules in this paper are often "disjunctive," meaning they offer choices.

The Rule: "If it's raining, you must wear a raincoat OR an umbrella."
The Problem: The AI might predict "wear a raincoat AND an umbrella" (fine) or "wear neither" (bad). But the math behind "OR" is tricky for computers because it creates a shape with holes in it (non-convex). It's like trying to draw a smooth, round ball that has a giant bite taken out of it. Standard math tools can't easily roll a ball over that shape.

2. The "Convex Hull" Trick (The Magic Mold)

To fix this, the authors use a mathematical trick called a convex hull.

Imagine the valid answers (Raincoat OR Umbrella) are two separate islands in a sea. The AI is currently floating in the middle of the sea (an invalid answer).
Standard methods might just build a bridge to the nearest island, but it's shaky.
DisjunctiveNet builds a perfect, tight mold around all the valid islands. It creates a new, smooth shape that wraps exactly around the valid options without including any of the "forbidden" water in the middle.
Crucially, they do this in a "lifted" space. Think of it as taking a 2D map of the islands and projecting it onto a 3D sculpture. In this 3D view, the "holes" disappear, and the shape becomes a smooth, solid block that a computer can easily navigate.

3. The "Projection Layer" (The Bouncer)

This is the core innovation. The authors insert a special layer into the neural network that acts like a bouncer at a club.

The neural network makes its best guess (the "unconstrained prediction").
This guess is handed to the Bouncer (the optimization layer).
The Bouncer checks the "mold" (the convex hull). If the guess is outside the valid rules, the Bouncer instantly finds the closest possible valid spot inside the rules and snaps the prediction there.
The Magic: This snapping process is "differentiable." This means the Bouncer doesn't just fix the answer; it tells the student exactly how they went wrong so they can learn from it immediately. The student learns to avoid the "forbidden water" in the first place.

4. Handling "If-Then" Complexity

The paper highlights that some rules only apply in specific situations (Input-Dependent).

Example: "If the fan is broken, THEN use the AC." If the fan isn't broken, that rule doesn't apply.
DisjunctiveNet is smart enough to check the current situation, figure out which rules are active, and instantly reshape its "mold" to fit only the active rules. It doesn't use a one-size-fits-all approach; it customizes the safety harness for every single input.

The Results: Perfect Compliance

The authors tested this on two scenarios:

Cooling Systems: A simulated factory where the AI had to control fans and chillers without breaking safety rules.
Medical Data (scRNA-seq): Classifying cells based on gene markers, where biological rules dictate that if certain genes are present, the cell must be a certain type.

The findings were clear:

Rule Satisfaction: While other methods (like penalty-based ones) broke the rules frequently, DisjunctiveNet achieved 100% rule satisfaction. It never broke the rules.
Performance: In situations with very little data (where the AI usually struggles), DisjunctiveNet was much smarter than the others because the rules acted as a strong guide.
Trade-off: The "perfect" version (DNF) is computationally heavier (takes a bit more time to calculate the mold) than the "good enough" version (CNF), but it guarantees the rules are followed exactly.

Summary

DisjunctiveNet is a way to teach AI to respect hard, logical rules without guessing or hoping. It transforms complex, "holey" rulebooks into smooth, navigable shapes that the AI can learn from directly. It ensures that when the AI makes a decision, it is not just statistically likely, but physically and logically guaranteed to be safe and correct.

Technical Summary: DisjunctiveNet

Problem Statement

Many scientific and engineering learning tasks operate under sparse data regimes where purely data-driven deep learning models often fail to generalize or violate known structural, physical, or safety constraints. While these domains possess rich prior knowledge—expressed as physical laws, operational requirements, and expert heuristics—existing neuro-symbolic methods struggle to incorporate this knowledge effectively. Current approaches typically rely on soft penalties (which do not guarantee feasibility), assume input-independent rules, or utilize non-differentiable post-processing at inference time. Furthermore, extending differentiable optimization layers to handle logical or mixed-integer rules is challenging due to the inherent nonconvexity and disjoint nature of such constraint spaces.

Methodology

The authors propose DisjunctiveNet, a unified end-to-end framework for enforcing hard, input-dependent mixed-integer linear constraints within neural networks. The core methodology involves three key components:

Disjunctive Constraint Representation:
Domain knowledge is modeled as a collection of input-dependent rules. Each rule is an implication $I[x \in A_r] \Rightarrow I[y \in C_r(x)]$ , where the output feasibility set $C_r(x)$ is represented as a finite union of polyhedral sets (a disjunction). The authors demonstrate that this representation is as expressive as Mixed-Integer Linear Programming (MILP) constraints and Quantifier-Free Linear Real Arithmetic (QF-LRA).
Hierarchical Convexification (CNF vs. DNF):
To enable end-to-end differentiability while ensuring exact constraint satisfaction, the framework transforms the nonconvex feasible set (an intersection of unions of polyhedra) into a convex relaxation.
- CNF Relaxation: Convexifies each rule independently and then intersects the resulting convex sets. This scales linearly with the number of active rules but provides a looser relaxation.
- DNF Relaxation: Distributes intersections over unions by enumerating all possible intersections of disjuncts across active rules. The convex hull of these intersections is computed. This yields the exact convex hull of the original nonconvex feasible set, guaranteeing that the solution satisfies the original logical constraints.
- Sequential Convexification: A middle-ground approach is introduced where a subset of rules is expanded into DNF form while others remain in CNF, allowing for a trade-off between computational complexity and relaxation tightness.
Differentiable Optimization Layer:
The projection of an unconstrained network output $\hat{y}$ onto the convexified feasible set is formulated as a Linear Program (LP) using an $\ell_1$ -norm epigraph formulation. By lifting the variables into a higher-dimensional space (including auxiliary variables for the epigraph and convex combination weights), the nonconvex projection problem is converted into a tractable LP.
- Exactness: The authors prove that if the LP solver returns an extreme point solution (e.g., via the simplex algorithm), the resulting projection satisfies the original hard constraints exactly.
- Differentiability: The layer is made differentiable via implicit differentiation of the Karush-Kuhn-Tucker (KKT) conditions, allowing gradients to flow back to the neural network parameters during training.

Key Contributions

Unified Framework: The paper presents the first approach capable of enforcing hard, input-dependent mixed-integer linear constraints within neural networks during both training and inference.
Exact Feasibility Guarantees: Unlike prior methods that use convex relaxations as heuristics, the proposed DNF relaxation corresponds to the tightest possible convex hull. The authors formally prove that extreme point solutions to the lifted LP satisfy the original logical constraints exactly.
Expressiveness: The framework unifies logical rules (Boolean operators over linear inequalities) and optimization-based constraints (MILP) under a single disjunctive programming formulation.
Scalability Mechanisms: The introduction of sequential convexification and the analysis of the trade-off between CNF (scalable) and DNF (tight) relaxations provide practical tools for handling complex rule sets.

Experimental Results

The framework was evaluated on two benchmarks: a synthetic cooling-control task and a single-cell RNA sequencing (scRNA-seq) classification task.

Synthetic Cooling-Control:
- Performance: DisjunctiveNet (specifically the DNF variant) achieved perfect rule satisfaction (CSAT = 1.0) across both In-Distribution (IID) and Out-of-Distribution (OOD) test sets, significantly outperforming unconstrained baselines and soft-penalty methods.
- Generalization: In data-scarce regimes and under OOD shifts, the projection layer provided a strong inductive bias, resulting in substantially lower Mean Squared Error (MSE) compared to baselines.
- Efficiency: While inference requires solving an LP (taking ~25-29 ms per sample), the computational overhead was deemed practical, and the DNF formulation did not suffer from worst-case exponential blowup in the tested scenarios due to many infeasible disjunct combinations.
scRNA-seq Classification:
- Rule Satisfaction: DNF-based projections achieved near-perfect rule satisfaction (CSAT > 0.9), whereas penalty-based methods and the base network failed to consistently satisfy input-dependent marker-gene rules.
- Accuracy vs. Constraints: In low-data regimes, enforcing rules improved macro-F1 scores. As data increased, the base model's accuracy improved, but projection-based models maintained superior rule adherence, highlighting a trade-off between predictive accuracy and exact constraint satisfaction in high-data regimes.

Significance and Claims

The paper claims that DisjunctiveNet addresses a critical gap in neuro-symbolic learning by enabling exact enforcement of complex, input-dependent logical constraints without relying on soft penalties or post-hoc corrections. The significance lies in its ability to integrate domain knowledge directly into the learning process, ensuring that models adhere to physical and safety constraints even when data is limited or distribution shifts occur.

The authors position their work as a step toward more reliable AI in scientific and engineering applications. They acknowledge limitations, primarily the computational cost of DNF relaxations for large numbers of active rules and the dependency on LP solvers returning extreme points for exactness guarantees. However, they argue that for many real-world applications involving moderate rule sets, the framework offers a principled and effective solution for trustworthy neural network deployment.