International audience

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.

Database users can be frustrated by having an empty answer to a query. In particular, querying RDF triple-stores are prone to failure due to the nature of RDF data. The problem of query relaxation is thus a helpful technique for efficiently querying RDF databases by providing users with alternative answers instead of an empty result. The main shortcoming of most prior researches is that they focus on the relaxation itself rather than the causes of failure. Yet, determining possible explanations, i.e. diagnoses, for an unexpected behavior of the system under observation is crucial to the user. In this paper, we present CADER, a novel approach for computing relaxations for failed queries over RDF databases. We show how the number of required database queries for determining all the possible relaxations can be limited to the search of failed subqueries of the user query. Then, we point out how the hitting set problem can be applied for determining the possible relaxed queries in an efficient way without querying the RDF database. Finally, the efficiency and scalability of CADER against existing solutions are shown through extensive experiments on the well-known RDF benchmarks with a variety of queries of different shapes.

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.