Journées RoCED (Reasoning on Complex and Evolving Data) atelier soutenu par les GDR Madics et GDR-IA

Approches hybrides pour le raisonnement et l’apprentissage automatique appliquées aux graphes de connaissances

6 juillet au matin et le 7 juillet après-midi lors du symposium du MADICS

Présentation des journées

Ces journées seront organisées à l'occasion du symposium MADICS du 5 au 9 juillet 2021.

Nous assistons aujourd’hui à une production de données évolutives et complexes sans précédent, dont une grande partie est publiée sous la forme de graphes de connaissances (GC). Bien que incomplets, hétérogènes et pouvant contenir des erreurs, ces graphes de connaissances contiennent une mine d’informations importantes qui peuvent être exploitées et analysées pour découvrir de nouvelles connaissances. Plusieurs approches existantes s'inspirent de techniques issues de différents domaines, tels que la fouille de données, le raisonnement et l’apprentissage automatique. Afin d’appréhender l'évolution des données et la complexité de certains domaines, tels que l’agronomie, l’IoT ou encore la médecine, le besoin de concevoir des approches hybrides combinant différentes techniques, se fait de plus en plus prépondérants.

L’objectif des journées de l'atelier RoCED du 6 et 7 juillet 2021 est de réunir les chercheurs intéressés pour échanger et discuter autour de la problématique de raffinement des graphes de connaissances à partir des techniques de raisonnement et/ou d’apprentissage automatique. Ces journées seront l'occasion de présenter des approches (mêmes préliminaires) récentes sur le sujet et d'identifier les verrous à lever.

Les sujets d'intérêt comprennent, sans s'y limiter, les thèmes suivants :

Comité d'organisation

Programme

6 juillet 9h - 13h

7 juillet 13h30 - 17h

Claudia d’Amato Machine Learning, Reasoning and Knowledge Graphs: a perspective on the usefulness of their interplay

Knowledge Graphs (KGs) are becoming important for several research fields, despite their inherent incompleteness and noise. A significant research effort has been devoted to knowledge graph refinement, aiming at correcting these issues with KGs. Particularly, link prediction and triple classification tasks have gained major attention. They have been targeted mostly by adopting numeric based machine learning methods since they resulted to be able to scale on very large KGs. Nevertheless, KGs may also rely on expressive representation languages, such as RDFS and OWL that are also endowed with deductive reasoning capabilities, but both expressiveness and reasoning are most of the time disregarded by the majority of the numeric methods that have been developed, thus somehow loosing knowledge that is already available. This talk aims at offering a perspective on the role that reasoning may play when developing numeric based solutions targeting KG completion at instance level, as well as on the utility of symbol-based machine learning methods, particularly for enriching KGs at schema level. Specifically, after illustrating concept and disjointness axiom learning methods, applicable to expressive knowledge representations while making use of reasoning capabilities, a general framework for exploiting reasoning and injecting background knowledge into KG embedding methods will be presented.

Arnaud Soulet Découverte d'indicateurs de classement dans le Web des données

Analyser l'impact d'entités au sein de leur domaine est fondamental pour le comprendre. A cette fin, il est essentiel de disposer d'indicateurs numériques fins retranscrivant les spécificités du domaine. Cet article propose une approche pour découvrir automatiquement des indicateurs d'impact pour classer les entités. Bien que l'approche soit transdisciplinaire, les indicateurs de classement identifiés doivent néanmoins disposer d'une sémantique intradisciplinaire. Pour cela, notre approche s'appuie sur les bases de connaissances du Web des données, pas seulement pour faciliter le calcul opérationnel des indicateurs mais aussi pour profiter de leur transparence et de la formalisation explicite de leur sémantique. L'hypothèse simple mais centrale de ce travail est que chaque répartition inégalitaire d'une quantité engendre un indicateur de classement pertinent. A cette fin, nous utilisons le coefficient de Gini pour identifier dans Wikidata les propriétés produisant des indicateurs de classement significatifs.

Discovering Ranking Score in the Web of Data Analyzing the impact of entities within their domain is fundamental task to understanding it. To this end, it is essential to have fine-grained numerical scores retranscribing the specificities of the field. This work proposes an approach to automatically discover impact scores to rank entities. Although the approach is transdisciplinary, the discovered ranking scores must nevertheless have an intradisciplinary semantics. For this purpose, our approach is based on the knowledge bases of the Web of data, not only to facilitate the computation of the scores but also to take advantage of their transparency and the explicit formalization of their semantics. The simple but central assumption of this work is that each unequal distribution of a quantity leads to a relevant ranking score. To this end, we use the Gini coefficient to identify in Wikidata properties producing meaningful ranking scores. De Runz, C., Giacometti, A., Markhoff, B., & Soulet, A. (2021). Découverte d’indicateurs de classement dans le Web des données. Extraction et Gestion des Connaissances: Actes EGC'2021, 12 pages.

Nacira Abbas Découverte de clés de liage dans le web des données avec l’Analyse Formelle de Concepts.

Nous nous intéressons à la découverte de liens d’identité dans le web des données. Les clés de liage, généralisant la notion de clé sur deux jeux de données, ont été introduites pour générer des liens d’identités entre deux individus appartenant à deux jeux de données. Puisque les clés de liage ne sont généralement pas fournies, des algorithmes de découverte de clés de liage dites “candidates” ont été proposés. Ces candidates sont évaluées grâce à des mesures de qualité adaptées et les meilleures sont considérées comme des clés de liage valides. Dans cet exposé, nous présentons les méthodes de découverte de clés de liage candidates qui s’appuient sur l’Analyse Formelle de Concepts (AFC) ainsi que sur les Pattern structures qui généralisent l’AFC pour traiter des données complexes.

Discovery of Link Keys in the Web of Data within Formal Concept Analysis. We are interested in the discovery of identity links in the web of data. Link keys, generalizing the notion of key, were introduced to generate identity links between two individuals belonging to two datasets. Since the link keys are generally not provided, algorithms for discovering so-called link key “candidates” have been proposed. These candidates are evaluated using suitable quality measures and the best ones are considered as valid link keys. In this talk, we present link key candidates discovery methods that rely on Formal Concept Analysis (FCA) as well as Pattern structures that generalize FCA to process complex data.

Jacques Everwyn Prédictions de relations dans les graphes dynamiques avec attributs – application à la surveillance maritime

Les opérateurs de surveillance maritime ont besoin de la meilleure représentation possible d'une situation sous leur responsabilité, une représentation connue comme la Situational Awareness maritime (SAM). Avec le développement rapide des données capteurs et satellites, ces opérateurs doivent traiter de larges flux de données venant de multiples sources de l'écosystème maritime. De ce fait, ils ont besoin d'une aide à la décision pour se repérer dans cet océan d'informations. Nous avons choisi les graphes dynamiques avec attributs pour représenter une situation maritime. Ce sont des graphes qui représentent les interactions entre les entités ainsi que l'évolution de leurs attributs. De telles structure peuvent représenter des situations de la vie réelle impliquant des objets mouvants et interagissant, ce qui permet d'obtenir des capacités de visualisation et de traitement avec une couche d'information sémantique. En pouvant prédire de nouveaux liens entre les entités d'une situation, nous pourrions lever des alertes anticipées aux opérateurs pour qu'ils sachent où regarder dans la donnée pour comprendre ce qu'il se passe. Cependant, la plupart des techniques de prédiction de liens ne traitent que des cas statiques ou sans attributs, ce qui les rend inutilisables dans notre cadre. Dans ces travaux, nous proposons Joint Evolution, un système d'encodeur-décodeur de bout en bout composé de deux réseaux de neurones. Joint Evolution utilisent les relations et les attributs d'un graphe de connaissance dans un contexte dynamique pour prédire de nouvelles relations entre les entités. L'hypothèse principale testée dans ces travaux est que l'ajout d'attributs dans la prédiction de liens peut améliorer les résultats grâce à l'ajout d'informations. Nous testons Joint Evolution sur deux jeux de données : datAcron, un jeu de données maritime qui remonte les événements arrivés dans la baie de Biscay pour 364 bateaux et DBLP, un réseau de citation avec des milliers d'auteurs qui sont co-auteurs et se citent les uns les autres.

Link prediction in dynamic attributed graphs applied to maritime situational awareness Maritime surveillance operators need to have the best view on the situation they monitor, a view known as Maritime Situational Awareness (MSA). With the rapid development of sensors and satellite data, these operators face a large flow of data coming from multiple sources in the maritime ecosystem. Hence, they require a decision aid to navigate through all the available information. We choose dynamic attributed knowledge graphs to represent a maritime situation. They are graph structures that represent the interactions between entities and the evolution of their attributes. Such structures can be used to represent real-life situations involving moving and interacting objects, unlocking visualization and processing capabilities with a semantic layer. By being able to predict new links between entities of a situation, we could raise early alerts to operators who will thus know where to look in the data to assess what is happening. However, most state-of-the-art link prediction models tackle only static (attributed) graphs or dynamic non-attributed graphs, which makes them unusable in this setting. In this work, we propose Joint Evolution, an end-to-end encoder-decoder system composed of two neural networks. Joint Evolution uses both attributes and relations of a knowledge graph in a dynamic setting to predict new relations between entities. The main hypothesis tested in this work is whether the inclusion of attributes during the relational link prediction can improve the results thanks to the additional information it provides. We test our method on two different datasets: datAcron, a maritime dataset that report events near the Bay of Biscay in France for 364 vessels, and DBLP, a citation network with thousands of authors that are co-authors or cite each other.

Pierre-Henri Paris Entités non nommées et imprécision

La présentation concerne deux travaux du projet NoRDF , qui vise à extraire et modéliser des informations complexes de textes en langage naturel. Le premier travail concerne les entités non nommées, c'est-à-dire les entités qui ne sont pas des noms propres pour simplifier. En effet, la majorité des entités dans les textes en langage naturel ne sont pas nommées et nous avons donc étudié la nature de ces entités. Ensuite, nous avons expliqué comment elles pourraient être représentées dans les bases de connaissances. Enfin, nous avons discuté des défis à relever pour ajouter systématiquement des entités non nommées aux bases de connaissances. Le second travail concerne les entités vagues. En effet, le langage naturel n'est pas toujours précis - et parfois intentionnellement. Nous avons donc étudié l'imprécision des groupes nominaux et analysé manuellement la fréquence des groupes nominaux vagues dans un corpus Wikipédia. Ainsi, nous avons constaté qu'un quart des groupes nominaux présentent une certaine forme d'imprécision. Nous avons rendu compte de leur nature et proposé une catégorisation. Nous avons aussi effectué une revue de la littérature et nous avons présenté différentes définitions de l'imprécision, et différentes méthodes existantes pour traiter la détection et la modélisation de l'imprécision.

Non-named Entities and Vagueness The presentation concerns two works of the NoRDF project , which aims at modeling and extracting complex information from natural language texts. The first work concerns non-named entities, i.e. entities that are not proper names for simplicity. Indeed, the majority of entities in natural language texts are not named and we have therefore studied the nature of these entities. Then, we explained how they could be represented in knowledge bases. Finally, we discussed the challenges of systematically adding non-named entities to knowledge bases. The second work concerns vague entities. Indeed, natural language is not always precise - and sometimes intentionally so. We therefore studied the vagueness of noun phrases and manually analyzed the frequency of vague noun phrases in a Wikipedia corpus. As a result, we found that a quarter of the noun phrases exhibit some form of vagueness. We reported on their nature and proposed a categorization. We also conducted a literature review and presented different definitions of vagueness, and different existing methods to deal with vagueness detection and modeling.

Francesco Bariatti Génération et sélection de motifs de graphes avec le principe MDL

Beaucoup de domaines utilisent des données représentées par des graphes étiquetés. Par exemple, en chimie et biologie, les molécules sont représentées par des graphes avec des atomes et des liaisons ; en linguistique, les phrases sont représentées par des graphes avec des mots et des liens de dépendance ; en web sémantique, la connaissance est représentée par un graphe avec des entités et des relations. Afin d'extraire de la connaissance de ces données, dans le domaine de la fouille de motifs beaucoup d'approches de fouille de graphes ont été proposées pour extraire des sous-structures fréquentes (motifs) de données. Les approches les plus classiques -appelées complètes- telles que MoFa, gSpan, Gaston, ou FFSM, extraient tous les motifs qui apparaissent avec une fréquence supérieure à un paramètre "minsup" donné par l'utilisateur. Le défaut majeur de ces approches est d'extraire un trop grand nombre de motifs, rendant leur interprétation difficile. Certaines approches, telles que gPrune ou CloseGraph réduisent le nombre de motifs générés en appliquant des contraintes ou en utilisant des représentations condensées. Mais généralement ne suffisent pas à réduire suffisamment le nombre de motifs générés pour permettre une analyse humaine. Plus récemment, des approches basées sur le principe MDL (Minimum Description Length) telles que Krimp, R-Krimp, ou SQS ont été proposées pour d’autres types de données (ensemblistes, relationnelles, séquentielles). Ces méthodes réussissent à extraire des petits ensembles de motifs descriptifs des données. Certaines méthodes basées sur le principe MDL ont aussi été proposées pour des graphes, notamment VoG ou SUBDUE. Cependant, la première ne gère que des graphes non étiquetés et des formes de motifs prédéfinies, et la deuxième introduit une perte d’information dans sa représentation et évalue chaque motif individuellement au lieu d'évaluer un ensemble de motifs comme un tout. Les approches GraphMDL et GraphMDL+ que nous présentons permettent de sélectionner un petit ensemble de motifs descriptifs à partir de graphes étiquetés. Elles introduisent la notion de « ports » pour décrire exactement comment les motifs extraits se connectent entre eux pour reconstituer les données sans perte d’informations. Le nombre de motifs extraits est drastiquement inférieur aux approches classiques, et ces motifs extraits peuvent avoir des formes complexes et transmettent de la connaissance sur les données.

Références :
[1] F. Bariatti, P. Cellier, and S. Ferré, ‘GraphMDL: Graph Pattern Selection Based on Minimum Description Length’, in Advances in Intelligent Data Analysis XVIII, Cham, 2020, pp. 54–66. doi: 10.1007/978-3-030-44584-3_5.
[2] F. Bariatti, P. Cellier, and S. Ferré, ‘GraphMDL+: interleaving the generation and MDL-based selection of graph patterns’, in Proceedings of the 36th Annual ACM Symposium on Applied Computing, New York, NY, USA, Mar. 2021, pp. 355–363. doi: 10.1145/3412841.3441917.

Graph Pattern Generation and Selection based on Minimum Description Length Many fields have complex data that need labeled graphs for an accurate representation. For instance, in chemistry and biology, molecules are represented as atoms and bonds; in linguistics, sentences are represented as words and dependency links; in the semantic web, knowledge graphs are represented as entities and relationships. In order to extract knowledge from those graphs, in the domain of pattern mining, many approaches of graph mining have been proposed, to extract frequent sub-structures (patterns) from the data. Classical approaches -called complete approaches- such as MoFa, gSpan, Gaston, or FFSM, extract all the patterns that appear with a frequency greater than a user-supplied parameter “minsup”. The main drawback of those approaches is to extract a huge amount of patterns, making their analysis difficult. Some approaches, such as gPrune or CloseGraph reduce the number of generated patterns by applying constraints or using condensed representations. However, they generally do not reduce the number of patterns enough to allow a human analysis. More recently, approaches based on the Minimum Description Length (MDL) principle have been proposed for other types of data such as Krimp, R-Krimp, or SQS for itemsets, relational data, sequences. These approaches manage to extract small sets of patterns that are descriptive of the data. Some MDL-based approaches have been proposed for graphs, such as VoG and SUBDUE. However, the former only allows non-labeled graphs et only extracts patterns with predefined shapes, while the latter introduce a loss of information in its representation and only evaluate each pattern individually instead of evaluating sets of patterns as a whole. The GraphMDL and GraphMDL+ approaches that we present allow to select a small set of descriptive patterns from labeled graphs. They introduce the notion of “ports” to describe exactly how the selected patterns interconnect in order to reconstitute the data without any loss of information. The number of extracted patterns is significantly lower compared to classical approaches, and the extracted patterns can have complex shapes and highlight knowledge about the data.

References:

[1] F. Bariatti, P. Cellier, and S. Ferré, ‘GraphMDL: Graph Pattern Selection Based on Minimum Description Length’, in Advances in Intelligent Data Analysis XVIII, Cham, 2020, pp. 54–66. doi: 10.1007/978-3-030-44584-3_5.
[2] F. Bariatti, P. Cellier, and S. Ferré, ‘GraphMDL+: interleaving the generation and MDL-based selection of graph patterns’, in Proceedings of the 36th Annual ACM Symposium on Applied Computing, New York, NY, USA, Mar. 2021, pp. 355–363. doi: 10.1145/3412841.3441917.

Alexandre Bento Raisonnement embarqué et distribué pour le Web des Objets

Le projet Constrained Semantic Web of Things (CoSWoT) a pour objectif de définir une plateforme pour le développement d'applications distribuées et intelligentes pour le Web des Objets utilisant les technologies du Web sémantique. Les graphes de connaissances et le raisonnement à base de règles constituent les éléments clés du projet. Nous proposons un état de l'art des travaux intéressants pour le raisonnement embarqué et distribué dans le cadre du Web des Objets, et traçons des lignes directrices pour la mise en place d'un tel raisonnement dans le projet CoSWoT.

Embedded and distributed reasoning for the Web of Things: a state of the artThe Constrained Semantic Web of Things (CoSWoT) project aims to define a platform for the developement of smart and distributed applications for the Web of Things that uses the technologies of the semantic Web. Knowledge graphs and rule-based reasoning are the key elements of the project. This paper proposes a state of the art of interesting works on embedded and distributed reasoning in the frame of the Web of Things. It also gives directions to set up such reasoning in the CoSWoT project.

Cédric PRUSKI Construction and exploitation of an historical knowledge graph to deal with the evolution of ontologies

With the advances of Artificial Intelligence, the need for annotated data increases. The semantics of annotations is usually specified in ontologies and these ontologies evolve over time. Thus, the quality of these annotations can be impacted when new versions of the ontology are published. The evolutionary relations between the successive versions of the ontologies are rarely described requiring a manual work of maintenance that laborious and error prone. Legal aspects and limited resources result into a huge quantity of datasets annotated at different times, becoming a real challenge for data- and knowledge-intensive systems to reuse them properly. In this talk we present a way to address this problem. We introduce the Historical Knowledge Graph (HKG) approach, where information from previous versions of an ontology can be found inside a single RDF graph, reducing storage space (no need for versioning) and data treatment time (no need for complex queries and laborious analysis of each version of the ontology). We will illustrate the applicability of an HKG for information retrieval and for the maintenance of semantic annotations.

Mélanie MUNCH Towards Interactive Causal Relation Discovery Driven by an Ontology

Discovering causal relations represents nowadays a challenging issue, as it gives a brand new way of understanding and reasoning within complex domains. However, this task is often impossible to perform from data alone. In this paper, we present a method to combine an ontology with a probabilistic relational model (PRM), in order to help a user to check their assumption on causal relations, which is used to guide the learning under causal constraints. The originality of this work is the combination of two broadly opposed philosophies: while the Bayesian approach favors the statistical analysis of the given data in order to reason with it, the ontological approach is based on the modelization of expert knowledge to represent a domain. Combining the strenght of the two allows to improve both the reasoning under uncertainty and the expert knowledge, allowing causal inferences.

Lucas SIMONNE Differential Causal Rules Mining in Knowledge Graphs Using Semantic Matching

This presentation is about mining causal differential rules in knowledge graphs. In recent years, keen interest towards knowledge graphs has been increasing in both academia and the industry. However, only few approaches focus on finding causal links in such graphs. We propose an approach to mine causal differential rules. These rules express that for two different class instances, a different treatment leads to different outcomes. Our approach is based on semantic matching as well as on strata that can be defined as complex sub-classes. Two experiments, one on an extract from DBPedia and another on a knowledge graph built with experts in nutritional behavior, show that such rules can help gain insights into various domains.

Thamer Mecharnia Y a-t-il de l'amiante dans les joints de vos fenêtres ? Approches sémantiques de prédiction de présence d'amiante dans les bâtiments

Le Centre Scientifique et Technique du Bâtiment (CSTB) a été sollicité pour développer un outil d’aide à l’identification des matériaux contenant potentiellement de l’amiante dans les bâtiments. Le CSTB dispose d’un ensemble de descriptions de bâtiments mais ces descriptions ne mentionnent pas le produit commercialisé utilisé mais uniquement la classe des produits. Nous présenterons dans le cadre de ce séminaire les deux approches guidées par une ontologie de domaine développées pour prédire la présence d’amiante dans les éléments de bâtiments. La première, basée sur deux ressources externes (l’INRS et l’Andeva)) contenant des descriptions temporelles sur les produits commercialisés et leur teneur en amiante, génère une probabilité de présence d’amiante en fonction des classes de produit et de la date de construction du bâtiment. La deuxième approche nommée CRA-Miner, s’inspire de méthodes issues de la Programmation logique Inductive (PLI) pour découvrir des règles à partir des exemples positifs et négatifs décrits dans le graphe de données du CSTB en se basant sur un contexte s ́emantique, et un ensemble d’heuristiques adaptées aux relations partie-tout, définis par l’expert. Nous présenterons les résultats obtenus sur 2998 descriptions de bâtiments et montrerons que si la pr ́ecision est meilleure dans le cas de la première approche, la deuxième permet de prendre plus de décisions.

Alexandre Bazin Hybrid Approach to Identifying the Most Predictive and Discriminant Features in Supervised Classification Problems

Dans cet exposé, nous parlerons du rôle des variables, en termes de prédiction et discrimination, dans les problèmes de classification supervisée. Nous discuterons de la différence entre prédiction et discrimination et d'une manière de reconnaître les variables particulièrement importantes pour ces deux tâches.

In this presentation, we will talk about the role of features, in terms of prediction and discrimination, in supervised classification problems. We will discuss the difference between prediction and discrimination and propose a way to identify the features that are particularly important for these two tasks.

Soumission

Deux types de soumission sont possibles :

  1. approche de recherche : Il est demandé de soumettre le titre et un résumé présentant le contenu de la présentation orale qui pourra être faite pendant les journées. Ce résumé peut décrire de nouvelles idées qui n'ont pas encore été évaluées. Ce résumé peut également correspondre à un article déjà accepté dans une conférence internationale afin de faire bénéficier la communauté RoD de ces travaux. Le résumé devra alors contenir un lien vers l'article publié.
  2. présentation de projet de recherche en cours : Il est demandé de soumettre le titre et un résumé présentant le contenu de la présentation orale qui pourra être faite pendant les journées. Ce résumé doit décrire les objectifs du projet en lien avec la thématique de la journée.

Le résumé devra être soumis par envois d’email aux organisatrices au plus tard le 18 juin.