In this paper, we present fast polynomial-time algorithms for solving classes of submodular constraints over Boolean domains. We pose the identified classes of problems within the general framework of Weighted Constraint Satisfaction Problems (WCSPs), reformulated as minimum weighted vertex cover problems. We examine the Constraint Composite Graphs (CCGs) associated with these WCSPs and provide simple arguments for establishing their tractability. We construct simple - almost trivial - bipartite graph representations for submodular cost functions, and reformulate these WCSPs as max-flow problems on bipartite graphs. By doing this, we achieve better time complexities than state-of-the-art algorithms. We also use CCGs to exploit planarity in variable interaction graphs, and provide algorithms with significantly improved time complexities for classes of submodular constraints. Moreover, our framework for exploiting planarity is not limited to submodular constraints. Our work confirms the usefulness of studying CCGs associated with combinatorial problems modeled as WCSPs.
Machine learning is vulnerable to adversarial examples-inputs designed to cause models to perform poorly. However, it is unclear if adversarial examples represent realistic inputs in the modeled domains. Diverse domains such as networks and phishing have domain constraints-complex relationships between features that an adversary must satisfy for an attack to be realized (in addition to any adversary-specific goals). In this paper, we explore how domain constraints limit adversarial capabilities and how adversaries can adapt their strategies to create realistic (constraint-compliant) examples. In this, we develop techniques to learn domain constraints from data, and show how the learned constraints can be integrated into the adversarial crafting process. We evaluate the efficacy of our approach in network intrusion and phishing datasets and find: (1) up to 82 state-of-the-art crafting algorithms violate domain constraints, (2) domain constraints are robust to adversarial examples; enforcing constraints yields an increase in model accuracy by up to 34 must alter inputs to satisfy domain constraints, but that these constraints make the generation of valid adversarial examples far more challenging.
We study propagation of the RegularGcc global constraint. This ensures that each row of a matrix of decision variables satisfies a Regular constraint, and each column satisfies a Gcc constraint. On the negative side, we prove that propagation is NP-hard even under some strong restrictions (e.g. just 3 values, just 4 states in the automaton, or just 5 columns to the matrix). On the positive side, we identify two cases where propagation is fixed parameter tractable. In addition, we show how to improve propagation over a simple decomposition into separate Regular and Gcc constraints by identifying some necessary but insufficient conditions for a solution. We enforce these conditions with some additional weighted row automata. Experimental results demonstrate the potential of these methods on some standard benchmark problems.