Anton Dries

Christian Bessiere, Clement Carbonnel, Anton Dries et al.

Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QUACQ, that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases.

Pedro Zuidberg Dos Martires, Anton Dries, Luc De Raedt

In probabilistic reasoning, the traditionally discrete domain has been elevated to the hybrid domain encompassing additionally continuous random variables. Inference in the hybrid domain, however, usually necessitates to condone trade-offs on either the inference on discrete or continuous random variables. We introduce a novel approach based on weighted model integration and algebraic model counting that circumvents these trade-offs. We then show how it supports knowledge compilation and exact probabilistic inference. Moreover, we introduce the hybrid probabilistic logic programming language HAL-ProbLog, an extension of ProbLog, to which we apply our inference approach.

Sergey Paramonov, Christian Bessiere, Anton Dries et al.

Answer Set Programming (ASP) is a powerful modeling formalism for combinatorial problems. However, writing ASP models is not trivial. We propose a novel method, called Sketched Answer Set Programming (SkASP), aiming at supporting the user in resolving this issue. The user writes an ASP program while marking uncertain parts open with question marks. In addition, the user provides a number of positive and negative examples of the desired program behaviour. The sketched model is rewritten into another ASP program, which is solved by traditional methods. As a result, the user obtains a functional and reusable ASP program modelling her problem. We evaluate our approach on 21 well known puzzles and combinatorial problems inspired by Karp's 21 NP-complete problems and demonstrate a use-case for a database application based on ASP.

David F. Nettleton, Vicenc Torra, Anton Dries

In this paper we present a novel approach for anonymizing Online Social Network graphs which can be used in conjunction with existing perturbation approaches such as clustering and modification. The main insight of this paper is that by imposing additional constraints on which nodes can be selected we can reduce the information loss with respect to key structural metrics, while maintaining an acceptable risk. We present and evaluate two constraints, 'local1' and 'local2' which select the most similar subgraphs within the same community while excluding some key structural nodes. To this end, we introduce a novel distance metric based on local subgraph characteristics and which is calibrated using an isomorphism matcher. Empirical testing is conducted with three real OSN datasets, six information loss measures, five adversary queries as risk measures, and different levels of k-anonymity. The results show that overall, the methods with constraints give the best results for information loss and risk of disclosure.