1. Livres & vidéos
  2. Data Scientist et langage R
  3. Knowledge Graphs
Extrait - Data Scientist et langage R IA, Machine Learning et Statistiques, Forecast, Tenseur, Gradient, Pytorch, Keras, CNN, LLM, GPT, RAG… (4e édition)
Extraits du livre
Data Scientist et langage R IA, Machine Learning et Statistiques, Forecast, Tenseur, Gradient, Pytorch, Keras, CNN, LLM, GPT, RAG… (4e édition) Revenir à la page d'achat du livre

Knowledge Graphs

Introduction

L’étude des graphes porte sur des aspects variés. Les principales différences ou similarités sont étudiées soit entre des graphes ou des parties de graphe, soit entre des nœuds de graphe (typiquement dans un graphe ou une partie de graphe).

Plus haut dans l’ouvrage, nous avons présenté la notion de degré, qui est une feature simple mais malheureusement insuffisante pour qualifier les graphes et les nœuds.

Des noyaux (kernels) appliqués aux graphes permettent de capturer puis de manipuler diverses caractéristiques de la structure des graphes au travers de nos techniques de Machine Learning habituelles, ce n’est donc pas l’objet ici. Ce chapitre se focalise sur des aspects vraiment spécifiques des graphes.

Premiers pas

La théorie des graphes comprend de nombreux concepts, théorèmes et notations très précis, mais un peu troublants car ces définitions varient à la marge suivant les auteurs. Nous ne définirons pas mathématiquement tous les concepts sous-jacents à notre utilisation des graphes, car un chapitre n’y suffirait pas. Vous trouverez ici une sélection de termes clés et de définitions "en français" assez fiables pour permettre de manipuler les graphes dans un contexte opérationnel.

1. Quelques notions et notations complémentaires basiques

Il faut s’imprégner des notions suivantes et chercher à les reconnaître dans les graphes que vous croiserez.

Un graphe fini non orienté sans boucle (loop), c’est-à-dire un graphe simple (undirected simple) s’écrit G(V, E). Attention, parfois on note de la même façon des graphes d’autre nature (non simples, orientés, hypergraphes...).

Ses nœuds ou vertices s’écrivent V(G) = {v1,,..., vn}.

Point de vocabulaire : en anglais vertices est le pluriel de vertex.

Ses arêtes ou edges s’écrivent E(G) = {e1,,...,en}.

Quand il n’y a pas d’ambiguïté, il est inutile d’écrire le (G).

Les arêtes sont des éléments du produit cartésien V x V.

Deux nœuds distincts sont adjacents quand ils partagent la même arête.

Deux arêtes distinctes sont adjacentes quand elles partagent un même nœud.

Une chaîne (walk) entre deux nœuds distincts, ses extrémités, est un graphe de nœuds adjacents tels que seules les extrémités ont un degré égal à 1 au sein de ce graphe. Parfois on parle de chaîne ouverte ou open walk.

Une chaîne élémentaire (trail) est une chaîne dont le degré maximum d’un nœud est 2 : elle ne repasse jamais par le même nœud (attention, dans certains textes le terme chaîne désigne une chaîne élémentaire).

Un cycle (closed walk, cycle) est un graphe de nœuds adjacents de degrés au moins égaux à 2 au sein de ce graphe.

Un cycle élémentaire est un cycle dont...

Graphes et réseaux (sociaux)

Les notions que nous allons mettre en œuvre ici ne sont pas spécifiques de l’étude des réseaux sociaux, mais elles sont largement employées dans ce cadre.

Un réseau social est composé d’acteurs (des humains, des groupes d’humains, des personnes morales) qui sont reliés par des liens que l’on qualifie comme liens sociaux, typiquement des interactions, synchrones ou non.

Évidemment, il est d’usage de représenter les acteurs par des nœuds et les relations par des arêtes ou des arcs, ce que l’on nomme parfois sociogramme quand les relations portent directement ou indirectement des concepts d’affinité entre les acteurs (qui est choisi par qui, qui est meneur...).

Les relations peuvent être structurelles (employé par…, collègue de...), factuelles (dialogue avec, participe à... avec...), ou déclaratives (like..., aime...). Souvent ces relations s’étendent aux objets entourant les acteurs : "untel aime tel film".

Quand les relations sont symétriques, comme le fait d’être relié sur LinkedIn, on obtient des graphes non orientés. Quand les graphes représentent l’expression d’opinions (sur quelqu’un ou quelque chose) ou quand ils représentent les abonnements à des services ou les envois de tweets ou de mails, cela donne des graphes orientés.

Si la relation est quantifiée, comme le nombre de tweets envoyés à quelqu’un, le nombre d’étoiles signifiant que l’on apprécie quelque chose, le nombre de liens communs, de smileys... on a affaire à un graphe valué (qui comporte des poids, weights en anglais).

Les types de relations sont étiquetés sur les arcs ou les arêtes (collègue, follower...).

1. Analyse des réseaux sociaux : concepts de base

Les notions les plus couramment utilisées dans l’analyse des réseaux sociaux sont la densité des liens du réseau (density of links) et la centralité (centrality).

La densité de liens représente tout simplement le nombre de liens réels versus le nombre de liens possibles. Elle transparaît quand certaines parties du graphe comportent de nombreux...

Embedding de graphes

L’embedding de graphe peut être effectué de façon très naturelle. Les graphes capturent déjà les relations entre des concepts et donc encapsulent déjà une connaissance explicite, alors que les chaînes de caractère d’un document nécessitent un travail conséquent pour faire émerger de la connaissance. Pour créer un embedding naturel "naïf" d’un graphe donné, il suffit donc d’effectuer un SVD adapté sur sa matrice d’adjacence, ce qui a de plus l’intérêt de diminuer le "bruit" éventuel encodé dans le graphe, moyennant le filtrage effectué en ne conservant que de grandes valeurs singulières.

Comme d’habitude, d’autres solutions s’offrent à vous :

images/15EP01N.png

Solutions simples à mettre en œuvre pour l’embedding de graphes

GNN (Graph Neural Networks)

Pour implémenter un GNN, il est commode de définir ou d’utiliser sur étagère une fonction de convolution dédiée aux graphes, nous la nommerons "GraphConv", à savoir sa dénomination dans la librairie Python spektral.layers, compatible avec Keras.

En exploitant à la fois les caractéristiques locales et la structure globale du graphe, ce type modèle traite de contextes où la relation entre les entités (représentées par des nœuds) influence leur classification ou leurs propriétés. Il pourrait par exemple être utilisé pour :

  • la détection de communautés ou le regroupement dans les réseaux sociaux ;

  • la prédiction de propriétés moléculaires en bioinformatique ;

  • la recommandation d’éléments dans des systèmes de recommandation basés sur des réseaux d’interactions.

Dans ce contexte, le terme "caractéristiques" fait référence aux attributs ou aux informations numériques qui décrivent chaque nœud du graphe. Pour chaque nœud, on dispose donc d’un vecteur de dimension 10, qui regroupe différentes mesures ou propriétés de ce nœud. Ces caractéristiques peuvent être, par exemple, des indicateurs...