Logical GANs: Adversarial Learning through Ehrenfeucht Fraisse Games

Modern generative models excel at producing realistic samples--images, text, molecules-- but often lack guarantees about structural properties. A protein generator may produce plausible sequences that violate stability constraints; a network topology generator may create graphs that fail connectivity requirements; a molecule generator may output structures violating chemical valence rules. Standard GAN discriminators provide a global "real vs. fake" signal, but they cannot pinpoint which specific structural constraint failed or guarantee that generated samples satisfy formal specifications. Meanwhile, mathematical logic has developed precise tools for reasoning about structural properties. Ehrenfeucht-Fraïssé (EF) games [1, 2] characterize when two structures are indistinguishable by logical formulas up to a given complexity (quantifier depth k). First-order (FO) and monadic second-order (MSO) logics can express rich structural properties--connectivity, bipartiteness, planarity, acyclicity--that are crucial in applications but invisible to standard discriminators.