International audience

On a worldwide scale, an increasing number of victims of human trafficking were observed these last years, covering a majority of countries and territories. Among them, a large portion of women and girls are recruited primarily for sexual exploitation. United Nations Office on Drugs and Crime (UNODC) highlights the difficulties of access to justice which deprive victims of protection, a central issue behind our work. Our contribution is part of an emerging research trend, combining Artificial Intelligence (AI), Humanities and Social Sciences (HSS). It makes an original use of legal database to identify Human Trafficking Networks (HTNs), involving both sexual abuse victims and exploiters. First, a reformulation of the legal database as a numerical database is proposed, using new features expressing relationships between people involved in the same court case, likely to better reveal HTNs. Secondly, six machine learning algorithms, including Decision Tree, Random Forest, Gradient Boosting, Logistic Regression, Support Vector Machine (SVM) and K-Nearest Neighbors (KNN) are used to train on numerical database and learn to classify the input court case into one of the three classes: Not suspicious, Suspicious, or Probably suspicious. We in details discuss knowledge-based feature engineering, dataset balancing, parameters tuning, and best models selection. The comparative empirical evaluations between those classification algorithms have been conducted in order to highlights the relevance of our HTNs detection approach. To help the end-users, to better understand the displayed HTNs, for Decision Tree and Random Forest, we also provide explanations of why such court case can be classified. Those results were finally discussed with experts in the field of human trafficking, providing us with interesting feedback shedding light to this multidimensional form of modern-day slavery problem.

Computing high utility motifs is a fundamental data mining method for discovering useful itemsets yielding high utility values. Minimal and maximal high utility itemsets are two examples of compact representations used to reduce the output size due to the large and incomprehensible number of patterns. In this paper, we present a novel method for mining minimal and maximal high utility itemsets using propositional satisfiability. First, we show that minimal and maximal high utility patterns are X-minimal models of a CNF formula. Then, to improve the scalability issue of our method, we harness a decomposition paradigm that splits the transaction database into smaller and independent transaction sub-bases, allowing an efficient enumeration of minimal and maximal high utility itemsets. Finally, through extensive evaluation studies on various real-world datasets, we demonstrate that our approach is very competitive w.r.t. to the state-of-the-art specialized solutions.

In this paper, we propose an efficient overlapping community detection method using a seed set expansion approach. In particular, we make an original use of a particular concept of graph theory, called chordal graph, to discover densely connected structures in social interactions based on maximal cliques. Indeed, a chordal graph possesses a number of interesting and useful properties that can help us to efficiently recover all maximal cliques of a given graph. Then, we develop new seeding strategies based on different fitness functions for discovering meaningful communities. Experimental results demonstrate the effectiveness and the efficiency of our overlapping community model in a variety of real graphs.

Ontologies can represent knowledge in a structured and formally well-understood way, which is crucial for information sharing. However, in practice, it is often difficult to have an error-free ontology. Conflicts can occur due to modeling errors or ontology merging and evolution. Moreover, uncertainty can happen because of modeling choices or the lack of confidence for a constructed ontology. Argumentation frameworks for knowledge bases reasoning and management have received extensive interests in the field of Artificial Intelligence in recent years. In this paper, we propose a unified framework to handle conflicts in uncertain ontologies with the use of deductive argumentation. Different from existing approaches, we introduce a stronger notion of conflict that covers both inconsistency and incoherence, where the latter is a special contradiction that can occur in an ontology. The unified approach spreads uncertainty degrees throughout argumentation trees and the enriched argument structure leads us to two novel inference relations. We then present a method to compute (counter)-arguments as well as argumentation trees in the context of uncertain ontologies based on the developments of three notions called minimal conflicting subontologies, maximal nonconflicting subontologies, and prudent justifications.

How to succinctly represent the truly relevant information in big data graphs? The approach presented in this paper aims to discover hidden graph structures and exploit them to compactly summarize large graphs. First, we show that some special graph classes such as cliques and bicliques can be represented efficiently as Pseudo-Boolean (PB) constraints. Then, we propose three new graph classes representable as PB constraints, called nested, sequence and clique-nested bi-partite graphs. Finally, we derive a general approach for partial or complete summarization of an arbitrary graph as a disjunction of PB constraints. Our representation can be seen as an original way to represent the edges of the graph, as they correspond to particular solutions of the PB constraints. An extensive experimental evaluation on several real-world networks shows that our framework is competitive with the state-of-the-art compression technique.

In this paper, we propose a SAT-based encoding for the problem of discovering frequent, closed and maximal patterns in a sequence of items and a sequence of itemsets. Our encoding can be seen as an improvement of the approach proposed in [8] for the sequences of items. In this case, we show experimentally on real world data that our encoding is significantly better. Then we introduce a new extension of the problem to enumerate patterns in a sequence of itemsets. Thanks to the flexibility and to the declarative aspects of our SAT-based approach, an encoding for the sequences of itemsets is obtained by a very slight modification of that for the sequences of items.

In this paper, we propose a first application of data mining techniques to propositional satisfiability. Our proposed mining based compression approach aims to discover and to exploit hidden structural knowledge for reducing the size of propositional formulae in conjunctive normal form (CNF). It combines both frequent itemset mining techniques and Tseitin's encoding for a compact representation of CNF formulae. The experimental evaluation of our approach shows interesting reductions of the sizes of many application instances taken from the last SAT competitions.