# Découverte de connaissances à partir de grands graphes biologiques

Sabeur Aridhi

► To cite this version:

Sabeur Aridhi. Découverte de connaissances à partir de grands graphes biologiques. Informatique [cs]. Université de Lorraine, 2023. tel-04364210

HAL Id: tel-04364210

https://hal.science/tel-04364210

Submitted on 26 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Découverte de connaissances à partir de grands graphes biologiques

## MÉMOIRE

présentée et soutenue publiquement le 18 décembre 2023

pour l'obtention d'une

Habilitation de l'Université de Lorraine
(mention informatique)

par

Sabeur Aridhi

## Composition du jury

*Rapporteurs :* Fatiha Sais, Professeur, LRI, Université Paris Saclay, France
Philippe Fournier-Viger, Professeur, Shenzhen University, Chine
Osmar Zaiane, Professeur, University of Alberta, Canada

*Examinateurs :* Sarah Cohen Boulakia, Professeur, LRI, Université Paris-Saclay, France
Abdoulay Baniré Diallo, Professeur, Université du Québec à Montréal, Canada
Yannick Toussaint, Professeur, Loria, Université de Lorraine, France

*Marraine scientifique :* Marie-Dominique Devignes, Chargée de recherche (HDR), CNRS, France
Mis en page avec la classe thesul.
Abstract

Graphs are used in many different fields, ranging from social networks computer security, geography and bioinformatics. Their versatility and their ability to model complex data make them a valuable tool for solving several problems especially in the domain of knowledge extraction from biological graphs which is our domain of interest. However, the use of graphs can present several challenges such as data representation, scalability and the dynamic/temporal behavior of some real world graphs. In the particular case of biological graphs, challenges related to the complexity of biological systems, interpretability and validation could be raised. Without achieving all of these challenges, we present in this manuscript several contributions. First, we present a novel protein-protein network (PPN) based approach which combines the notion of domain similarity with a graph neighborhood inference technique for protein function annotation. Then, we describe an explainable link prediction approach in biological knowledge graphs for drug repositioning. Finally, we present our contributions on distributed graph clustering and large-scale knowledge graph embedding.

**Keywords:** Protein function annotation, knowledge graphs, link prediction, structural clustering, knowledge graph embedding.

Résumé

Les graphes sont utilisés dans de nombreux domaines différents, allant de la sécurité informatique des réseaux sociaux, à la géographie et à la bioinformatique. Leur polyvalence et leur capacité à modéliser des données complexes en font un outil précieux pour résoudre plusieurs problèmes notamment dans le domaine de l'extraction de connaissances à partir de graphes biologiques qui est notre domaine d'intérêt. Cependant, l'utilisation de graphes peut présenter plusieurs défis tels que la représentation des données, l'évolutivité et le comportement dynamique/temporel de certains graphes réels. Dans le cas particulier des graphes biologiques, des défis liés à la complexité des systèmes biologiques, à l'interprétabilité et à la validation pourraient être soulevés. Sans s'attaquer à l'ensemble de ces défis majeurs, nous présentons dans ce manuscrit d'HDR plusieurs contributions. Tout d'abord, nous présentons une nouvelle approche basée sur un graphe de protéines qui combine la notion de similarité de domaine avec une technique d'inférence de voisinage de graphe pour l'annotation de la fonction des protéines. Ensuite, nous décrivons une approche de prédiction de liens explicables dans les graphes de connaissances biologiques pour le repositionnement des médicaments. Enfin, nous présentons nos contributions sur le clustering de graphes distribués et le plongement de graphes de connaissances à grande échelle.

**Mots-clés:** Annotation fonctionnelle de protéines, graphes de connaissances, prédiction de liens explicables, clustering structurel, plongement de graphes de connaissances.
Remerciements

Je tiens à remercier tout d'abord Fatiha Sais, Philippe Fournier-Viger et Osmar Zaiane pour avoir accepté de relire ce mémoire et pour l'avoir fait avec beaucoup de bienveillance. Merci également à Sarah Cohen-Boulakia, Abdoulay Baniré-Diallo et Yannick Toussaint pour avoir accepté d'examiner ce travail. Un très grand merci à Marie-Dominique Devignes pour le par- rainage et pour tout l'accompagnement et les conseils précieux durant ces dernières années au sein de l'équipe Capsid. Le travail décrit dans ce mémoire d'HDR n'est pas le fruit de mon seul travail, mais celui de nombreux échanges et collaborations. Je remercie Manel, Wissem, Bishnu et Kamrul pour les nombreuses réalisations de leurs thèses de science soutenues. Merci Bernard, Malika, Isaure, Hamed et Yasaman pour les conseils réguliers et les bons moments. Merci à tous les collègues du Loria. Merci à tous les collègues de Telecom Nancy et aux collègues administratifs et notamment à Antoinette, Isabelle, Carole pour me faciliter énormément la vie. Many thanks to UFC friends! José, Joao Paulo!

Last but not least, je voudrais adresser mes remerciements les plus chaleureux à ma chère et formidable épouse Manel et à mes chers enfants : Adam, Youssef et Yanis : Vous êtes l'essence de ma vie.
# Table des matières

Résumé i

Remerciements iii

Table des figures ix

Introduction 1

## Chapitre 1

### Introduction

1.1 Extraction de connaissances à partir des graphes 3

1.2 Contexte : projets de recherche et encadrements 4

1.3 Notions préliminaires 6

1.3.1 Les protéines et leurs annotations 6

1.3.2 Les graphes : notations et définitions 7

1.4 Organisation du manuscript 13

## Partie I Intelligence artificielle et graphes de connaissances pour l'annotation de proteines et le repositionnement de médicaments 15

## Chapitre 2

### Propagation de labels dans des graphes de protéines

2.1 Introduction 17

2.2 Des approches à base de graphes pour l'annotation 18

2.2.1 Construction d'un graphe de protéines 19

2.2.2 Annotation fonctionnelle de protéines par des numéros EC 21

2.2.3 Annotation fonctionnelle de protéines par des termes GO 23
<table><tr><td>2.3</td><td>Résultats</td><td>25</td></tr><tr><td>2.3.1</td><td>Préparation de données pour la prédiction des numéros EC</td><td>25</td></tr><tr><td>2.3.2</td><td>Préparation de données pour la prédiction des termes GO</td><td>26</td></tr><tr><td>2.3.3</td><td>Analyse des performances des annotations EC</td><td>27</td></tr><tr><td>2.3.4</td><td>Analyse des performances des annotations GO</td><td>31</td></tr><tr><td>2.4</td><td>Discussion et conclusions</td><td>32</td></tr></table>

# Chapitre 3

## Prédiction de liens dans des graphes de connaissances complexes

<table><tr><td>3.1</td><td>Introduction</td><td>35</td></tr><tr><td>3.2</td><td>Échantillonnage négatif simple (SNS)</td><td>37</td></tr><tr><td>3.3</td><td>Explication des prédicitions</td><td>42</td></tr><tr><td>3.3.1</td><td>Génération d'un graphe bidirectionnel</td><td>44</td></tr><tr><td>3.3.2</td><td>Fouille de règles</td><td>44</td></tr><tr><td>3.3.3</td><td>Abduction pour la prédiction de lien explicable</td><td>48</td></tr><tr><td>3.4</td><td>Repositionnement de médicaments explicable avec évaluation au niveau mo-léculaire pour COVID-19</td><td>48</td></tr><tr><td>3.5</td><td>Résultats</td><td>51</td></tr><tr><td>3.5.1</td><td>Évaluation de l'échantillonnage négatif SNS</td><td>51</td></tr><tr><td>3.5.2</td><td>Évaluation de l'explicabilité</td><td>52</td></tr><tr><td>3.5.3</td><td>Évaluation de la prédiction de médicaments pour le COVID-19</td><td>56</td></tr><tr><td>3.6</td><td>Discussion et conclusions</td><td>61</td></tr></table>

# Partie II Calcul distribué et grands graphes complexes 63

# Chapitre 4

## Approches distribuées pour l'analyse de grands graphes dynamiques

<table><tr><td>4.1</td><td>Introduction</td><td>65</td></tr><tr><td>4.2</td><td>Plateformes de calcul distribué : état de l'art</td><td>66</td></tr><tr><td>4.2.1</td><td>Catégorisation des plateformes de calcul distribué sur des graphes</td><td>67</td></tr><tr><td>4.2.2</td><td>Catégorisation des plateformes de Big Data</td><td>68</td></tr><tr><td>4.3</td><td>Approche générique pour le calcul distribué sur des grands graphes dynamiques</td><td>70</td></tr><tr><td>4.4</td><td>Clustering distribué et incrémental des grands graphes dynamiques</td><td>73</td></tr><tr><td>4.4.1</td><td>Partitionnement de graphes distribués</td><td>74</td></tr><tr><td>4.4.2</td><td>Clustering distribué</td><td>74</td></tr><tr><td>4.4.3</td><td>Mise à jour du clustering</td><td>77</td></tr></table>
<table><tr><td>4.5</td><td>Résultats</td><td>82</td></tr><tr><td>4.5.1</td><td>Temps de réponse du clustering distribué initial</td><td>82</td></tr><tr><td>4.5.2</td><td>Temps de réponse et clustering incrémental</td><td>83</td></tr><tr><td>4.5.3</td><td>Scalabilité de DISCAN</td><td>83</td></tr><tr><td>4.6</td><td>Discussion et conclusions</td><td>84</td></tr></table>

## Chapitre 5

### Apprentissage de plongements dans les grands graphes de connaissances distribués

<table><tr><td>5.1</td><td>Introduction</td><td>87</td></tr><tr><td>5.2</td><td>Une approche distribuée de KGE</td><td>88</td></tr><tr><td>5.2.1</td><td>Établissement d'un réseau de communication</td><td>89</td></tr><tr><td>5.2.2</td><td>Partitionnement du KG</td><td>90</td></tr><tr><td>5.2.3</td><td>Entraînement du modèle de plongement</td><td>91</td></tr><tr><td>5.3</td><td>Résultats</td><td>93</td></tr><tr><td>5.4</td><td>Discussion et conclusions</td><td>96</td></tr></table>

## Partie III Projet de recherche scientifique 99

### Chapitre 6

#### Projet de recherche scientifique

<table><tr><td>6.1</td><td>Méthodes incrémentales d'analyse de graphes dynamiques et application à la biologie structurale</td><td>102</td></tr><tr><td>6.2</td><td>KGE et apprentissage profond à grande échelle pour le repositionnement de médicaments</td><td>104</td></tr><tr><td>6.2.1</td><td>Plongement multivues pour le repositionnement de médicaments</td><td>104</td></tr><tr><td>6.2.2</td><td>Transférabilité des modèles de KGE</td><td>105</td></tr><tr><td>6.2.3</td><td>Partitionnement intelligent de grands KGs</td><td>106</td></tr><tr><td>6.2.4</td><td>Explicabilité des modèles d'apprentissage profond sur les graphes</td><td>107</td></tr><tr><td>6.3</td><td>Techniques d'apprentissage artificiel avancées pour l'annotation de la fonction des protéines</td><td>108</td></tr></table>

## Bibliographie 113
Table des figures

<table><tbody><tr><td>1.1</td><td>Représentation du processus d'Extraction de Connaissances à partir des données [Fayyad et al., 1996].</td><td>4</td></tr><tr><td>2.1</td><td>Le workflow d'annotation utilisé dans GrAPFI.</td><td>19</td></tr><tr><td>2.2</td><td>Exemple d'annotation par des numéros EC. [Sarker et al., 2020b]</td><td>23</td></tr><tr><td>2.3</td><td>Performances et couvertures en fonction de divers seuils des indices de similarité de Jaccard pour le protéome de référence A. thaliana. [Sarker et al., 2020b]</td><td>29</td></tr><tr><td>2.4</td><td>Comparaison des performances de GrAPFI avec des outils de la littérature</td><td>30</td></tr><tr><td>3.1</td><td>La méthode d'échantillonnage SNS</td><td>39</td></tr><tr><td>3.2</td><td>Différents types de chemins pour définir des règles de longueur 2. [Islam et al., 2022]</td><td>43</td></tr><tr><td>3.3</td><td>Fouille de règles pour une relation cible r. [Islam et al., 2022]</td><td>44</td></tr><tr><td>3.4</td><td>Flux de travail global de l'étude</td><td>50</td></tr><tr><td>3.5</td><td>Changement des performances et de la qualité des prédicitions avec différents pourcentages de règles extraites de longueur 2 dans le graphe Family. [Islam et al., 2022]</td><td>55</td></tr><tr><td>3.6</td><td>Superposition des poses de liaison avec la cible nsp13 pour Fosinopril (en vert), Macitentan (en bleu foncé), Eprosartan (en rouge) et Dinoprostone (en magenta) contre Diosmine (en bleu clair), Ergotaminine (en gris) et Risperdal (en marron). Les ligands le long de l'axe vertical sont les ligands prédits, tandis que ceux le long de l'axe horizontal sont les ligands connus. [Islam et al., 2023]</td><td>61</td></tr><tr><td>4.1</td><td>Architecture de BLADYG [Aridhi et al., 2017]</td><td>71</td></tr></tbody></table>
<table>
  <tbody>
    <tr>
      <td>4.2</td>
      <td>Impact de la taille du graphe sur le temps de traitement des variantes SCAN et DISCAN. [Inoubli et al., 2022]</td>
      <td>82</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Impact du nombre de mises à jour sur le temps de traitement de pSCAN, ppSCAN et DISCAN (ε=0.5, μ=3). [Inoubli et al., 2022]</td>
      <td>84</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Impact du nombre de workers sur le temps de traitement de DISCAN (ε=0.5, μ=3). [Inoubli et al., 2022]</td>
      <td>85</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Architecture du framework distribué pour l'apprentissage de plongements. [Islam, 2022]</td>
      <td>89</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Illustration du mécanisme d'agrégation de gradients Ring-AllReduce pour une entité/relation spécifique dans un espace latent tridimensionnel.</td>
      <td>93</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>Métriques de performance de prédiction de liens pour les jeux de données FB15K et YAGO pour différents nombres de workers. [Islam, 2022]</td>
      <td>95</td>
    </tr>
    <tr>
      <td>5.4</td>
      <td>Temps de calcul par époque sur les ensembles de données FB15K et YAGO3-10 pour un nombre différent de workers. [Islam, 2022]</td>
      <td>96</td>
    </tr>
    <tr>
      <td>5.5</td>
      <td>Accélération de l'apprentissage distribué de deux modèles de plongement sur les ensembles de données.</td>
      <td>96</td>
    </tr>
  </tbody>
</table>
# Introduction
<figure><img src="image_1.png" /></figure>
# Chapitre 1

## Introduction

### 1.1 Extraction de connaissances à partir des graphes

Les graphes sont utilisés dans de nombreux domaines, allant des réseaux sociaux à la sécurité informatique en passant par la géographie et la bioinformatique. Leur polyvalence et leur capacité à modéliser des données complexes en font un outil précieux pour la résolution de plusieurs problèmes. En règle générale, l'extraction de connaissances à partir des graphes consiste à utiliser des techniques d'analyse de graphes pour découvrir des connaissances cachées dans les données représentées par les graphes. Dans le contexte de nos travaux de recherche, nous avons fondé nos contributions sur le processus classique d'extraction de connaissances à partir de données (ECD) illustré dans la Figure 1.1 [Fayyad et al., 1996]. Il s'agit d'un processus en plusieurs étapes qui vise à extraire des connaissances utiles à partir des données brutes. Il débute par la considération de données hétérogènes, qui sont préparées (c'est-à-dire, intégrées, structurées), fouillées, pour générer des régularités qui sont ensuite interprétées pour donner naissance à des connaissances [Coulet, 2019]. Ce processus nécessite la compréhension approfondie des données, des techniques d'analyse et de la manière dont les résultats peuvent être interprétés et appliqués.

Dans le contexte de nos travaux de recherche, la représentation en graphes a été utilisée pour représenter des données biologiques et le processus d'ECD a été utilisé pour extraire des connaissances utiles qui sont validées et interprétées par des experts de l'équipe Capsid du Loria-Inria Nancy. Comment utiliser la représentation en graphes pour représenter des données biologiques et extraire des connaissances utiles tout en considérant la complexité et la quantité des données
<figure><img src="image_2.png" /><figcaption>FIGURE 1.1 – Représentation du processus d'Extraction de Connaissances à partir des données [Fayyad et al., 1996].</figcaption></figure>

disponibles est la problématique transversale de ce mémoire d'HDR et constitue un fil de lecture.

## 1.2 Contexte : projets de recherche et encadrements

Les contributions décrites dans ce mémoire d'HDR ont été réalisées dans le cadre de projets de recherche, ainsi que dans le cadre de l'encadrement de thèses et de Masters, auxquels j'ai été directement impliqué après l'obtention de mon doctorat.

Une description plus détaillée de mon profil est disponible sur mon curriculum vitae en ligne, que vous pouvez consulter à l'adresse https://members.loria.fr/SAridhi/cv/. J'ai choisi de séparer délibérément ces deux documents afin que ce mémoire d'HDR se focalise exclusivement sur l'aspect scientifique de mon projet d'habilitation.

**La thèse de Manel Zoghlami** [Zoghlami, 2019]. J'ai co-encadré Manel Zoghlami entre Sep-
tembre 2015 et Décembre 2019. Les travaux de cette thèse traitent de l'utilisation des approches
d'apprentissage multi-instances (MI) pour la prédiction de la résistance aux rayonnements ioni-
sants chez les bactéries [Zoghlami et al., 2020] [Aridhi et al., 2016b]. C'est à travers cet encadre-
ment que je me suis intéressé à l'utilisation de l'intelligence artificielle (IA) pour résoudre des
problèmes biologiques.

**La thèse de Bishnu Sarker** [Sarker, 2021]. J'ai co-encadré Bishnu Sarker entre Novembre 2017 et Avril 2021. Cette thèse traite des approches à base de graphes pour effectuer l'annotation automatique des fonctions protéiques tout en étudiant l'impact de l'architecture en domaines sur les fonctions protéiques [Sarker et al., 2020b, Sarker et al., 2020a, Sarker et al., 2022].

**La thèse de Wissem Inoubli** [Inoubli, 2021]. J'ai co-encadré Wissem Inoubli entre Novembre 2017 et Janvier 2021. L'intérêt de Wissem Inoubli pour les méthodes de calcul distribué sur les graphes nous a menés à des travaux sur la classification non supervisée des grands graphes dynamiques qui ont été publiés dans des revues internationales [Inoubli et al., 2018] [Inoubli et al., 2022].

**La thèse de Md Kamrul Islam** [Islam, 2022]. J'ai co-encadré Kamrul Islam entre Novembre 2019 et Décembre 2022. Le travail de thèse de Kamrul s'intéresse à la prédiction de liens dans des graphes de connaissances et à l'application de ces méthodes pour la tâche de repositionnement de médicaments. Les travaux de cette thèse ont mené à des publications dans des conférences [Islam et al., 2021] et des revues internationales [Islam et al., 2022] [Islam et al., 2023].

**Le projet Tempographs.** J'ai été responsable scientifique et coordinateur du projet TempoGraphs<fnref n="1" />, un projet de collaboration franco-brésilien PRC-CNRS-FAPs entre l'Université de Lorraine et l'Université de Céara au Brésil. Ce projet traite l'étude et l'application des outils d'apprentissage automatique et des graphes temporels pour l'annotation automatique des protéines. Ce projet a permis dans un premier temps d'étendre le travail de thèse de Wissem Inoubli pour le traitement des graphes temporels dans un contexte distribué [Inoubli et al., 2017]. Dans un deuxième temps, ce projet nous a permis d'étudier l'utilisation de différentes méthodes de similarité dans le contexte de travail de Bishnu Sarker [Veras et al., 2022].

<footnote n="1">1. https://tempographs.loria.fr/</footnote>
## 1.3 Notions préliminaires

### 1.3.1 Les protéines et leurs annotations

Les protéines sont des macromolécules importantes qui constituent la base de la vie et jouent un rôle vital dans tout organisme vivant. Dans chacune des cellules qui composent un être vivant, les protéines remplissent de multiples fonctions dont la connaissance permet de mieux comprendre les mécanismes biologiques pour, entre autres, anticiper l'évolution des maladies et concevoir de nouveaux médicaments. Selon le dogme central de la biologie moléculaire, l'information génétique codée à l'intérieur de l'ADN est transcrite en ARN et à partir de l'ARN, elle est traduite en protéines qui agissent finalement à l'intérieur de la cellule. Les protéines sont, en quelque sorte, les produits finaux du processus de décodage de l'information génétique.

L'annotation fonctionnelle de protéines consiste à attribuer des caractéristiques fonctionnelles appropriées aux protéines. Ces caractéristiques sont souvent des termes de l'ontologie GO ou bien des numéros EC lorsqu'il s'agit d'une enzyme.

**L'ontologie Gene Ontology (GO).** Gene Ontology (GO) [Ashburner and et al., 2000] répertorie le vocabulaire contrôlé des termes qui décrivent les fonctions et ses termes font référence aux diverses fonctions biologiques que les protéines et les gènes remplissent dans les cellules et les organismes vivants. Dans GO, les termes fonctionnels sont présentés dans une hiérarchie en trois graphes acycliques dirigés (DAG), à savoir : 1) le processus biologique (BP), 2) la fonction moléculaire (MF) et 3) le composant cellulaire (CC). Chaque terme GO est un nœud dans le DAG. Chaque DAG commence à partir d'un terme racine et se connecte à d'autres termes hiérarchiques à travers différents types de liens indiquant différents types de relations. Les relations les plus utilisées sont « est un », « fait partie de » et « régule » tels qu'ils apparaissent dans la base de données GO.

**Les numéros EC.** La nomenclature EC (EC est l'abréviation de Enzyme Commission, la Commission des Enzymes) est une classification numérique des enzymes, basée sur la réaction chimique qu'elles catalysent [Cornish-Bowden, 2014]. Cette nomenclature attribue à chaque enzyme un numéro à quatre chiffres. Ce système de classification a une structure hiérarchique. Le premier niveau comprend six classes principales d'enzymes : (i) les oxydoréductases, (ii) les transférases, (iii) les hydrolases, (iv) les lyases, (v) les isomérides et (vi) les ligases, représentées
par le premier chiffre. Chaque nœud de classe principale plus loin s'étend à plusieurs nœuds de sous-classes, spécifiant des sous-classes d'enzymes, représentées par le deuxième chiffre. De même, le troisième chiffre indique la sous-sous-classe, et le quatrième chiffre désigne les sous-sous-sous-classes. Considérons comme exemple une enzyme de restriction de type II, qui est annotée EC 3.1.21.4. Le premier chiffre, 3, indique qu'il s'agit d'une hydrolase. Le deuxième chiffre, 1, indique qu'il agit sur les liaisons ester. Le troisième chiffre, 21, indique qu'elle est une endodésoxyribonucléase produisant des 5-phosphomonoesters. Le dernier chiffre, 4, spécifie qu'il s'agit d'une désoxyribonucléase site-spécifique de type II.

1.3.2 Les graphes : notations et définitions

Les graphes

Un **graphe**, $G = (V, E, X, W)$ est une représentation d'un réseau, où $V$ est l'ensemble des sommets (ou nœuds), $X$ est un ensemble d'attributs de nœud, $E \subseteq V \times V$ est un ensemble d'arêtes (ou de liens) qui relie deux nœuds et $W$ est un ensemble d'attributs de lien. Les nœuds représentent des entités dans des réseaux, telles que des personnes dans un réseau social, des protéines dans un réseau d'interactions protéine-protéine (PPI), des auteurs et des articles dans un réseau de co auteurs, etc. Les nœuds peuvent contenir des informations descriptives, telles que des noms, des types, des sources. Les liens représentent des connexions entre des paires d'entités, telles que le co-auteur dans les réseaux d'auteurs, l'amitié dans les réseaux sociaux, l'interaction dans les réseaux PPI. Les liens peuvent contenir des informations descriptives, telles que des noms, des sources, des pondérations.

$|V|$ et $|E|$ indique respectivement le nombre de nœuds et le nombre de liens. Le lien entre deux nœuds $x \in V$ et $y \in V$ est noté $e_{xy} \in E$. $e_{xy}$ est appelé un lien dirigé si le sens du lien va du nœud $x$ au nœud $y$ et un lien non dirigé sinon. Pour un lien dirigé, $e_{xy} \in E$, $x$ et $y$ sont respectivement appelés source et destination. Deux nœuds $x, y \in V$ sont **voisins** s'ils sont liés, c'est-à-dire, $e_{xy} \in E$. Les voisins du nœud $x$ forment collectivement un ensemble de voisins $\Gamma_x$ du nœud. Le nombre de voisins pour un nœud, $x$ est appelé **degré** du nœud et noté $|\Gamma_x|$. Une **matrice d'adjacence**, $A$ est une représentation matricielle du graphe, $G$ où un élément $A_{xy}$ indique si les nœuds $x$ et $y$ sont adjacents ou non dans le graphe.
$$A_{xy} = \begin{cases} 1 & \text{si } e_{xy} \in E \\ 0 & \text{si } e_{xy} \notin E \end{cases}$$

Un chemin, $P_{x,z}$ est une séquence de liens $e_{xy} - e_{ya} - \dots - e_{tz}$ entre les nœuds $x, z \in V$ où $x, y, a, \dots, t, z \in V$ et $e_{xy}, e_{ya}, \dots, e_{tz} \in E$. Le nombre de liens dans $P_{x,z}$ est appelé **longueur du chemin**. Un chemin de longueur $l$ entre deux nœuds $x$ et $y$ est noté $P_{x,y}^l$. Il peut exister plusieurs chemins dans $G$ entre une paire de nœuds $x, z$. Parmi les chemins, le chemin avec la plus petite longueur est appelé le plus court chemin noté $P_{x,z}^{shortest}$. Un graphe est connexe s'il existe un ou plusieurs chemins entre chaque paire de nœuds.

Si $E$ ne contient que des liens orientés alors $G$ est appelé un **graphe orienté**. D'autre part, tous les liens dans $E$ sont non orientés dans un **graphe non orienté**. Un graphe est appelé **graphe pondéré** si pour chaque lien, un poids est attribué. Sinon, le graphe est appelé un **graphe non pondéré**. Le poids d'un lien peut représenter un coût, une longueur ou une capacité. Un graphe est appelé **multi-graphe** s'il autorise plusieurs liens entre une paire de nœuds.

## Clustering structurel de graphes

Le clustering de graphes consiste à découper un graphe en plusieurs partitions ou sous-graphes. Comme avec d'autres techniques de clustering, nous devons utiliser une ou plusieurs métriques pour mesurer la similarité entre deux sommets ou partitions dans le graphe. Dans la technique de clustering structurel, la structure ou la topologie du graphe est divisée en un ensemble de sous-graphes relativement distants et un ensemble de sommets fortement connectés. L'algorithme de référence de clustering structurel est l'algorithme SCAN [Xu et al., 2007] qui utilise la similarité structurelle entre les sommets pour effectuer le regroupement.

Dans ce qui suit, nous présentons quelques définitions essentielles du clustering structurel de graphes, qui seront principalement utilisées dans la partie II du mémoire.

**Définition 1.3.1. (Voisinage structurel)** Le voisinage structurel d'un sommet $v$, est noté $N(v)$,
et représente tous les voisins d'un sommet donné $v \in V$, y compris le sommet v :

$$N(v) = \{u \in V | (v, u) \in E\} \cup \{v\} \qquad (1.1)$$

**Définition 1.3.2. (Similarité structurelle)** La similarité structurelle entre chaque paire de sommets $(u, v)$ dans un ensemble d'arêtes E représente un certain nombre de voisins structurels partagés entre u et v. Il est défini par $\sigma(u, v)$.

$$\sigma(u, v) = \frac{|N(u) \cap N(v)|}{\sqrt{|N(u)| \cdot |N(v)|}} \qquad (1.2)$$

Après avoir calculé la similarité structurelle avec l'équation 1.2, l'algorithme de référence SCAN utilise deux paramètres $\epsilon$ et $\mu$ pour détecter les sommets noyaux dans un graphe donné G.

**Définition 1.3.3. (ε-voisinage)** Chaque sommet a un ensemble de voisins structurels, comme il est mentionné dans la définition 1.3.1. Pour regrouper un sommet et ses voisins dans le même cluster, ils doivent avoir une connexion forte (notée $\epsilon$-voisinage) entre eux. SCAN utilise un seuil $\epsilon$ et l'équation 1.3 pour filtrer, pour chaque sommet, ses connexions les plus fortes. Le voisinage $\epsilon$ est défini comme suit.

$$N_{\epsilon}(u) = \{N(u) | \sigma(u, v) \geq \epsilon\} \qquad (1.3)$$

Le seuil $\epsilon$ ($0 < \epsilon \le 1$) montre dans quelle mesure deux sommets u et v sont connectés en fonction des voisins structurels partagés. De plus, il représente une métrique avec laquelle les sommets les plus importants, également appelés sommets noyaux, sont détectés.

**Définition 1.3.4. (Sommet noyau ou Core)** La détection des sommets noyaux est une étape fondamentale de l'algorithme SCAN. Elle consiste à trouver les sommets dominants dans un graphe donné G. Cette étape permet de construire l'ensemble des clusters. Un sommet noyau v est un sommet qui a un nombre suffisant de voisins fortement connectés avec lui $N_{\epsilon}(v)$. Nous utilisons $\mu$ comme nombre minimum de voisins fortement connectés (voir Définition 1.3.3). L'ensemble des sommets noyau est modélisé comme suit :

$$V_c = \{v | |N_{\epsilon}(v)| \geq \mu\} \qquad (1.4)$$
**Définition 1.3.5.** (Sommet bordure ou Border) Soit $v_c$ un sommet noyau. $v_c$ a deux listes de voisins structurels : (1) voisins faiblement connectés à $v_c$, également appelés sommets bruits ($N(V_c) \setminus N_\epsilon(V_c)$), et (2) voisins fortement connectés appelés voisins structurels accessibles. Dans notre travail, les voisins structurels accessibles sont appelés sommets bordures. $N_\epsilon(V_c)$ représente l'ensemble des sommets de bordures d'un sommet noyau $V_c$.

Une fois les nœuds et leurs sommets de bordures déterminés, il est simple de démarrer une étape de clustering. Pour ce faire, nous utilisons la définition suivante :

**Définition 1.3.6.** (Groupe ou Cluster) Un cluster $C$ ($|C| \ge 1$) est un sous-ensemble non vide de sommets composé de l'ensemble des sommets noyaux et leurs sommets de bordures.

L'algorithme de construction des clusters se compose des principales étapes suivantes :

1. Choix aléatoire d'un sommet noyau dans la liste des noyaux et création d'un cluster $C$.

2. Ajout du noyau et de ses bordures dans le même cluster. En parallèle, l'algorithme vérifie si la liste des nœuds frontières contient un sommet noyau.

3. Ajout récursif des bordures dans le même cluster, en appliquant cette étape jusqu'à ce que toutes les bordures des noyaux connectés soient ajoutées.

4. Choix d'autres sommets noyaux et exécution des étapes précédentes jusqu'à ce que tous les sommets noyaux soient vérifiés.

Parmi les informations fondamentales renvoyées par SCAN, par rapport aux autres algorithmes de clustering de graphes, nous mentionnons les informations sur les sommets de type pont et les *outliers*, définis comme suit :

**Définition 1.3.7.** (Pont ou Bridge) Un pont $b$ est un sommet $v \in V$ qui n'appartient à aucun cluster après avoir effectué l'étape de clustering, et qui a au moins deux liens (arêtes) avec deux clusters différents.

**Définition 1.3.8.** (Outlier) Un sommet outlier $o$ est un sommet $v \in V$ qui n'appartient à aucun cluster après l'étape de clustering, et ce n'est pas un pont.

L'étape de clustering agrège les sommets noyaux et leurs bordures en un ensemble de clusters. Cependant, certains sommets n'ont pas de connexions fortes avec un sommet noyau, ce qui ne
donne pas la possibilité de rejoindre un cluster. Dans ce contexte, l'algorithme SCAN classe ces sommets en deux familles : les ponts et les outliers. Un sommet $v$, qui ne fait partie d'aucun cluster et qui a au moins deux voisins dans des clusters différents, est appelé pont. Sinon, il est considéré comme outlier.

## Les graphes de connaissances

Un graphe de connaissances (KG) est un graphe qui permet d'encoder plus d'informations sémantiques par rapport à un graphe simple. Les KG sont généralement représentés à l'aide du modèle de données RDF (Resource Description Framework) [Klyne, 2004]. Le modèle RDF permet l'occurrence de liens multiples, de boucles, de liens dirigés, de noms de liens obligatoires et d'attributs de nœud et de lien auxiliaires [Paulheim, 2017]. Formellement, un graphe de connaissances est défini comme $KG = (V, R, Q)$ [Gao et al., 2022], où

- $V$ est un ensemble de nœuds représentant des entités;

- $R$ est un ensemble de noms de relations;

- $Q \subseteq V \times R \times V$ est un ensemble de faits (ou triplets positifs);

Les faits sont formatés sous la forme de triplet, $(h, r, t) \in Q$ où $h \in V$ et $t \in V$ qui sont respectivement appelés les entités de tête et de queue et $r \in R$ est une relation dirigée de $h$ vers $t$.

Sur la base des propriétés structurelles, une relation peut être symétrique ou anti-symétrique, inverse d'une autre relation et composée de plusieurs relations [Sun et al., 2018]. Formellement, si $\{(h, t)\}$ est l'ensemble des paires d'entités pour une relation $r$, alors la relation $r \in R$ est

- anti-symétrique, si $\forall_{(h,t)}(h,r,t) \in Q \implies (t,r,h) \notin Q$.

- symétrique, si $\forall_{h,t}(h,r,t) \in Q \implies (t,r,h) \in Q$.

- composée de deux relations, $r_1, r_2 \in R$, si $\forall_{h,t}(h, r_1, z) \in Q \land (z, r_2, t) \in Q \implies (h, r, t) \in Q$.

- inverse d'une autre relation, $r_1 \in R$, si $\forall_{h,t}\{(h, r, t) \in Q \implies (t, r_1, h) \in Q\}$.

- un à plusieurs, si $(h, r, t_1) \in Q \land (h, r, t_2) \in Q \land \dots \land (h, r, t_n) \in Q$.

- plusieurs à un, si $(h_1, r, t) \in Q \land (h_2, r, t) \in Q \land \dots \land (h_n, r, t) \in Q$.
## Plongement de graphes de connaissances

L'idée principale du plongement de graphes de connaissances (ou Knowledge Graph Embedding (KGE)) est de représenter les entités et les relations d'un graphe de connaissances dans des espaces vectoriels. Cela permet de simplifier la manipulation du graphe tout en préservant l'essentiel de sa sémantique. L'objectif principal est de vérifier que les éléments qui sont proches dans le graphe de connaissances se trouvent également proches dans l'espace vectoriel où ils sont plongés. En général, les modèles de KGE emploient les techniques relatives au domaine d'apprentissage automatique, et se fondent sur des fonctions objectives précises.

## Prédiction de liens dans des graphes de connaissances

Étant donné un graphe de connaissances $KG = (V, R, Q)$, où $V$ est l'ensemble des entités, $R$ est l'ensemble des noms de relations, $Q$ est l'ensemble des faits, le problème de prédiction de lien est défini comme la prédiction de l'entité manquante dans un triplet $(h, r, ?)/(? , r, t)$, où ? représente l'entité manquante [Rossi et al., 2021, Liang et al., 2022].

Les performances de la tâche de prédiction de lien sont définies avec deux métriques largement utilisées : Hit@z et le Mean Reciprocal Rank (MRR) [Wang et al., 2021]. Les métriques sont définies en fonction du rang du triplet positif de test. Hit@z est défini comme le nombre moyen de fois qu'un triplet de test positif figure parmi les z triplets les mieux classés; alors que MRR est le rang réciproque moyen du triplet de test positif [Bordes et al., 2013, Yang et al., 2015]. La plage des deux scores est de 0 à 1. La valeur la plus élevée de MRR démontre le meilleur classement des triplets de test positifs et un meilleur classement offre de meilleures performances de prédiction. De plus, un score Hit@z plus élevé indique de meilleures performances. Pour illustrer, considérons le triplet de test positif $q = (h, r, t) \in D$. Un ensemble de triplets négatifs $q'_{t} = \{(h, r, t') \notin Q | t' \in E\}$ est généré par simple perturbation de triplet (remplacement de la queue par d'autres entités) [Bordes et al., 2013, Ji et al., 2015] confirmant qu'aucun triplet positif n'existe dans $q'_{t}$. Les triplets de $q \cup q'_{t}$ sont ensuite classés par ordre décroissant de leurs scores (calculés par la fonction de score de l'approche de prédiction). Le rang du triplet de test positif $q$ dans $q \cup q'_{t}$ est défini comme $\text{rank}_{q}^{t}$. Sur la base du rang de chaque triplet de test positif $q$, les métriques de performance sont définies dans les équations 1.5 et 1.6.
$$ Hit^t@z = \frac{1}{|\mathbb{D}|} \sum_{q \in \mathbb{D}} hit_q^t, \quad hit_q^t = \begin{cases} 1, & \text{if } rank_q^t \le z \\ 0, & \text{otherwise} \end{cases} \qquad (1.5) $$

$$ MRR^t = \frac{1}{|\mathbb{D}|} \sum_{q \in \mathbb{D}} \frac{1}{rank_q^t} \qquad (1.6) $$

L'ensemble du processus d'évaluation est également répété en corrompant également l'en-
tité principale de chaque triplet positif et $Hit^h@z$, $MRR^h$ sont calculés. Les métriques fi-
nales $Hit@z$, $MRR$ sont la moyenne des métriques tête et queue c'est-à-dire, $Hit@z = (Hit^t@z + Hit^h@z)/2$ et $MRR = (MRR^t + MRR^h)/2$. En suivant la majorité des travaux de recherche sur la prédiction de liens dans des graphes de connaissances, nous considérons $z \in \{1, 3, 10\}$.

1.4 Organisation du manuscript

Ce manuscrit d'HDR a pour but de présenter mes travaux (réflexifs et expérimentaux) et
contributions qui illustrent le mieux l'utilisation efficace de la représentation en graphe pour la
découverte des connaissances biologiques à grande échelle.

Les parties I et II de ce mémoire d'HDR présentent éssentiellement mes activités de recherche.

Ces parties sont constituées de quatre chapitres principaux.

Les deux premiers chapitres 2 et 3 traitent en particulier les contributions d'apprentissage
automatique sur des graphes et leurs applications pour résoudre deux problèmes biologiques :
(1) l'annotation fonctionnelle de protéines et (2) le repositionnement de médicaments. Le cha-
pitre 2 explique et met en évidence l'intérêt de la décomposition en domaines des protéines pour
représenter les protéines par des graphes de similarité. Il présente également l'application de mé-
thodes de propagation d'étiquettes sur ces graphes pour l'annotation fonctionnelle de protéines.
Le chapitre 3 se concentre sur la prédiction de liens dans des graphes de connaissances biologiques
pour le repositionnement de médicaments. Il décrit notamment notre travail sur la génération
d'exemples négatifs et l'utilisation de techniques de plongement de graphes de connaissances
pour améliorer la prédiction de liens.

Le chapitre 4 traite la proposition d'approches distribuées pour l'analyse de grands graphes.
Nous décrivons dans un premier temps une étude comparative sur les plateformes de traitement et d'analyse de données massives et plus particulièrement des grands graphes. Dans un second temps, nous décrivons notre travail sur le clustering de grands graphes dynamiques.

Le chapitre 5 est consacré à la description de nos travaux sur le passage à l'échelle des approches de plongement dans des grands graphes de connaissances.

La partie III de ce document explicite mes perspectives de recherche dans le contexte de l'utilisation des graphes simples ou de connaissances et des techniques d'apprentissage automatique de pointe pour résoudre des problèmes biologiques.
Première partie

Intelligence artificielle et graphes de
connaissances pour l'annotation de
proteines et le repositionnement de
médicaments
<figure><img src="image_3.png" /></figure>
# Chapitre 2

## Propagation de labels dans des graphes
de protéines

### 2.1 Introduction

Il est important de noter qu'une quantité importante de séquences protéiques sont déjà disponibles dans les bases de données publiques. Par exemple, la base de données « UniProt KnowledgeBase » (UniProtKB)<fnref n="2" /> est la plus grande base de données publique pour le stockage des séquences protéiques. UniProtKB contient plus de 250 millions de séquences selon la version de Février 2023. Ce grand volume de séquences protéiques ouvre, d'une part, plusieurs opportunités pour réaliser des analyses utiles et pour répondre à des questions de recherche en biologie. D'autre part, cela pose des défis en raison du fait que cette énorme base de données est presque impossible à annoter manuellement. UniProtKB est divisé en deux parties : 1) UniProtKB/SwissProt et 2) UniProtKB/TrEMBL. Dans UniProtKB/SwissProt, les séquences protéiques sont annotées manuellement. Ce travail d'annotation manuelle nécessite un travail important pour les annotateurs humains. En fait, il faut beaucoup de temps pour lire des publications, trouver des informations sur une protéine particulière, identifier ses propriétés et produire finalement une annotation. Ce processus est donc très coûteux. Ce sont les principales raisons de la croissance très lente d'UniProtKB/SwissProt au cours des années. Selon la version 2023 de UniProtKB/SwissProt, il existe environ 569,000 séquences de protéines dont les annotations ont été produites et examinées

<footnote n="2">2. https://www.uniprot.org/</footnote>
manuellement. Au contraire, dans UniProtKB/TrEMBL, les séquences protéiques reçoivent des
annotations générées par des outils informatiques et qui ne sont pas revues manuellement. Quand
UniProtKB reçoit une nouvelle séquence protéique, elle est ajoutée à UniProtKB/TrEMBL et la
séquence est disponible en ligne pour une enquête plus approfondie. Ainsi, UniProtKB/TREMBL
a connu une très forte croissance au fil des ans, notamment par le moyen de la traduction automa-
tique des régions codantes des génomes au fur et à mesure de leur séquençage. Selon la version
de Février 2023, UniProtKB/TREMBL contient environ 249 millions de séquences protéiques
sans annotation fonctionnelle validée manuellement. Pour enrichir et exploiter cette quantité im-
portante de séquences protéiques, il est fortement souhaité de les annoter avec des propriétés
fonctionnelles telles que les numéros de commission enzymatique (EC) ou les termes de l'onto-
logie Gene Ontology (GO) décrivant leurs fonctions. Ce travail est considérable et, pour réduire
l'écart entre le volume des séquences protéiques non annotées et celui des séquences annotées,
il est essentiel de développer des techniques d'annotation automatique de la fonction des pro-
téines. Dans ce chapitre, je présente nos contributions majeures pour l'annotation automatique
des fonctions protéiques en utilisant la représentation en graphe et les méthodes de propagation
des étiquettes (ou labels) dans les graphes.

## 2.2 Des approches à base de graphes pour l'annotation

Dans le cadre de la thèse de Bishnu Sarker [Sarker, 2021], nous avons travaillé sur la proposi-
tion d'approches à base de graphes pour l'annotation des protéines. Nous avons principalement
proposé *GrAPFI* ("Graph-based Automatic Protein Function Inference") [Sarker et al., 2020b]
pour l'annotation automatique des protéines par les numéros EC et par des termes de l'ontologie
GO. La méthode *GrAPFI* explore la composition en domaines des protéines en construisant
un graphe de similarité de domaines et en effectuant une propagation d'étiquettes basée sur le
voisinage pour prédire les annotations des protéines non annotées.

Une vue générale de la méthode *GrAPFI* est présentée dans la Figure 2.1.
<figure><img src="image_4.png" /><figcaption>FIGURE 2.1 – Le workflow d’annotation utilisé dans *GrAPFI*. La partie droite du flux de travail représente la construction du graphe à l’aide de protéines validées de l’UniprotKB/Swissprot. La partie gauche montre le processus d’annotations. [Sarker et al., 2020b]</figcaption></figure>

### 2.2.1 Construction d'un graphe de protéines

Nous présentons ici une nouvelle façon de connecter des séquences de protéines en utilisant leurs domaines associés. Les domaines peuvent être considérés comme des blocs de construction naturels des protéines. En raison de l'évolution, les domaines protéiques peuvent avoir subis des changements tels que la duplication, la fusion, la recombinaison pour produire des protéines avec des structures et des fonctions distinctes [Kummerfeld and Teichmann, 2009]. Ici, chaque nœud du graphe représente une protéine, tandis qu'un lien entre deux nœuds signifie que les protéines présentent un niveau donné de similarité de domaine. Ainsi, chaque nœud *u* est identifié par un ensemble d'étiquettes *L(u)*, a un ensemble de voisins *N(u)*, et pour chaque voisin *v*, un poids associé *Wu*, *v*. L'objectif général est de propager des étiquettes (c'est-à-dire des annotations) à partir de nœuds ayant des étiquettes vers des nœuds similaires dépourvus d'étiquettes.

Pour illustrer la construction du graphe des protéines, prenons l'exemple de cinq protéines désignées par les noms symboliques P1, P2, P3, P4 et P5. Supposons que ces protéines soient com-
posées des domaines suivants : $D1 = \{d1, d2, d3, d4\}, D2 = \{d1, d3, d5\}, D3 = \{d1, d2, d10\}, D4 = \{d5, d6, d1\}$, et $D5 = \{d4, d1, d10, d40, d7, d9, d12, d52, d100\}$.

La composition des domaines d'une protéine est l'ensemble des domaines trouvés dans une séquence protéique et considérés indépendamment de l'ordre d'apparition dans la séquence. Par exemple, les informations de domaine dans $D1 = \{d1, d2, d3, d4\}$ peuvent être utilisées dans n'importe quel autre ordre. Par conséquent, la composition n'est pas strictement linéaire. Le chevauchement des domaines n'est pas pris en compte tant que les domaines chevauchants ont une nouvelle identification de domaine. Il est alors évident que les protéines P1 et P2 possèdent deux domaines en commun (d1 et d3). Par conséquent, les protéines P1 et P2 peuvent être liées et le nombre de domaines partagés peut servir de poids de liaison donné par $W_{P1,P2} = |\{d1, d2, d3, d4\} \cap \{d1, d3, d5\}| = |\{d1, d3\}| = 2$.

De la même manière, les protéines P1 et P5 peuvent être liées avec un poids de liaison de $|\{d1, d2, d3, d4\} \cap \{d4, d1, d10, d40, d7, d9, d12, d52, d100\}| = |\{d1, d4\}| = 2$. Dans les deux cas, le poids du lien est de 2. Cependant, le poids du lien calculé de cette manière ne reflète pas la force relative de la relation entre les protéines. Plus précisément, dans le premier cas, les deux protéines ont $|\{d1, d2, d3, d4\} \cup \{d1, d3, d5\}| = |\{d1, d2, d3, d4, d5\}| = 5$ domaines différents, dont deux sont partagés. Dans le second cas, il y a $|\{d1, d2, d3, d4\} \cup \{d4, d1, d10, d40, d7, d9, d12, d52, d100\}| = 11$ domaines différents dont encore deux sont partagés. Bien que deux domaines soient partagés dans chaque cas, la protéine P1 est intuitivement plus alignée avec P2 que P5. Par conséquent, au lieu d'utiliser le score de similarité brut ci-dessus, nous avons utilisé l'indice de similarité de Jaccard, ou coefficient de similarité de Jaccard, pour mieux refléter la similarité dans la composition.

Ceci est calculé comme $\frac{|A \cap B|}{|A \cup B|}$, où A et B sont les deux ensembles de domaines constitutifs. À l'aide de l'indice de similarité Jaccard, les poids des liens pour P1 et P2 sont calculés comme suit : $W_{P1,P2} = \frac{|\{d1,d2,d3,d4\} \cap \{d1,d3,d5\}|}{|\{d1,d2,d3,d4\} \cup \{d1,d3,d5\}|} = \frac{|\{d1,d3\}|}{|\{d1,d2,d3,d4,d5\}|} = \frac{2}{5} = 0.4$.

De même, pour P1 et P5, le poids du lien est calculé comme suit : $W_{P1,P5} = \frac{|\{d1, d2, d3, d4\} \cap \{d4, d1, d10, d40, d7, d9, d12, d52, d100\}|}{|\{d1, d2, d3, d4\} \cup \{d4, d1, d10, d40, d7, d9, d12, d52, d100\}|} = \frac{2}{11} = 0.18$.

En utilisant l'indice de similarité Jaccard, le graphe final est construit en deux étapes simples. Dans la première étape, les informations sur les protéines examinées sont analysées pour collecter les domaines constitutifs de chaque protéine. Si les données d'apprentissage ne contiennent que des séquences, l'outil InterProScan [Jones et al., 2014] est appliqué à chacune des séquences pro-
téiques pour trouver les domaines Interpro associés. Interpro est une base de données intégrées de domaines protéiques utilisée pour la classification et l'annotation automatique de protéines. Ensuite, le graphe est construit en utilisant la composition en domaines des protéines.

Il convient de mentionner que l'ordre des domaines n'est pas maintenu lors du calcul de l'indice de similarité Jaccard. La composition de domaine pour chaque protéine contient l'ensemble des signatures InterPro uniques trouvées dans la séquence.

### 2.2.2 Annotation fonctionnelle de protéines par des numéros EC

Une fois le graphe construit à partir des protéines examinées, il peut être utilisé pour l'annotation de nouvelles séquences de protéines. Un algorithme de propagation d'étiquettes basé sur le voisinage est conçu pour effectuer la tâche d'annotation. Étant donné les domaines constitutifs d'une séquence de protéines d'entrée, toutes ses protéines voisines et leurs annotations sont extraites du graphe. Une fois les voisins obtenus, la fréquence pondérée des étiquettes est calculée à l'aide de la formule suivante : $f_u^i = \frac{\sum_{v \in N(u)} W_{u,v} \delta(v^i, i)}{\sum_{v \in N(u)} W_{u,v}}$, où $f_u^i$ est le score pondéré de la fonction candidate i pour la protéine de requête u et $\delta(v^i, i)$ vaut 1 si la fonction $v^i$ de la protéine v est identique à la fonction i, sinon 0. Les détails de l'algorithme de propagation de l'étiquette sont décrits dans l'algorithme 1.

Explicitement, pour une séquence d'entrée donnée, l'annotation fonctionne selon l'organi-
gramme illustré dans la Figure 2.1.

Considérons une protéine requête P avec un ensemble de domaines D=(d5,d6,d101). Notre objectif est d'annoter cette protéine avec un numéro EC en suivant l'algorithme de propagation de l'étiquette, comme illustré dans la Figure 2.2.

Sur la base de la similarité de domaine, la protéine P aura une connexion avec les protéines P2 et P4 dans le graphe d'exemple en cours d'exécution. Les lignes pointillées montrent les liens de P à P2 et P4 dans le graphe avec les poids associés. Par conséquent, la protéine P aura P2 et P4 comme voisins. Après avoir trouvé les voisins, les annotations fonctionnelles de tous les voisins sont propagées avec les poids correspondants. Toutes les annotations fonctionnelles sont classées en fonction de leurs poids cumulés. La fonction la mieux classée est sélectionnée comme la meilleure annotation fonctionnelle pour la protéine P. Dans cet exemple, les annotations pondérées pour P sont EC3, EC5, EC6, EC1, EC2 avec des poids cumulés de 0,70, 0,50, 0,50,
<caption>**Algorithm 1** Label Propagation in a protein graph</caption>

1: **Input** : A weighted undirected protein graph (Section 2.2), $G = (V, E)$, Minimum Jaccard Similarity Index, $\theta$, and a query protein $u$ with domain composition $d$
2: **Output** : Weighted EC Annotations
3: **procedure** LABEL PROPAGATION
4:     Annotations $\leftarrow \emptyset$
5:     $N' \leftarrow \text{FilterNeighbors}(N(u), \theta)$
6:     ECs $\leftarrow$ list of distinct ECs present among the neighbors $N'$ **for** each $i \in \text{ECs}$ **do**
7:         $f_u^i = \frac{\sum_{v \in N'} W_{u,v} \delta(v^i, i)}{\sum_{v \in N'} W_{u,v}}$
8:         Annotations $\leftarrow$ Annotations $\cup \{f_u^i\}$
9:     10:         Rank the Annotations
11:     12:         Select the top ranked annotations and assign it to the protein $u$
13:     14:         **end Procedure**
15:     16:         $N' \leftarrow \emptyset$ **for** each $v \in N(u)$ **do**
17:             $W_{u,v} \leftarrow \theta$
18:             $N' \leftarrow N' \cup \{v\}$
19:     20:             **end for**
21:     21:             **return** $N'$
<figure><img src="image_5.png" /><figcaption>FIGURE 2.2 – Exemple d'annotation par des numéros EC. [Sarker et al., 2020b]</figcaption></figure>

0,20 et 0,20, respectivement. Par conséquent, l'annotation fonctionnelle pour la protéine P est EC3 car elle a le poids le plus élevé parmi les marqueurs propagés. Il est clair qu'il est possible de sélectionner plus d'une annotation fonctionnelle à score élevé si l'on souhaite proposer plus d'une annotation candidate. De plus, les nœuds voisins pourraient être sélectionnés d'autres manières pour refléter les exigences du problème à résoudre.

### 2.2.3 Annotation fonctionnelle de protéines par des termes GO

GrAPFI a été initialement proposé pour la prédiction de la fonction des protéines par des numéros EC. Dans la suite de la thèse de Bishnu Sarker [Sarker, 2021], nous avons étendu et adapté la méthode GrAPFI pour l'annotation automatique des protéines avec des termes d'on-tologie génique (GO) en la renommant GrAPFI-GO [Sarker et al., 2022]. GrAPFI-GO explore divers types de mesures de similarité basées sur des voisins communs dans le graphe de protéines construit par GrAPFI. De plus, les termes GO sont hiérarchisés selon les relations sémantiques parent-enfant. Par conséquent, nous proposons une technique d'élagage et de post-traitement efficace qui intègre à la fois la similarité sémantique et les relations hiérarchiques entre les termes GO. GrAPFI-GO effectue l'annotation par des termes GO à l'aide de GrAPFI combinée à un
post-traitement hiérarchique pour tirer parti de l'organisation hiérarchique de l'ontologie GO. Essentiellement, il y a deux parties dans le pipeline : (1) prédire l'ensemble des termes GO à l'aide de *GrAPFI*, et (2) élaguer l'ensemble d'annotations à l'aide de la similarité sémantique et du post-traitement hiérarchique.

Ainsi, le principe de propagation s'illustre comme suit : pour une protéine requête, nous cherchons toutes ses protéines voisines et leurs annotations dans le graphe pondéré en se basant sur sa composition en domaines. Après avoir obtenu les voisins, toutes les étiquettes des protéines voisines sont pondérées avec le poids des liens que ces voisins présentent avec la protéine de requête. Lors de la récupération des voisins, il est possible de sélectionner uniquement les voisins qui répondent à un certain seuil de similarité. Cela signifie que les liens peuvent être filtrés en fonction d'un poids de coupure prédéfini. Pour chaque annotation candidate, *GrAPFI-GO* fournit un score de confiance, nommé score du modèle (MS), qui est calculé ainsi :

$$MS(u, i) = \frac{\sum_{v \in N(u)} W_{u,v} \sum_{j \in L(v)} \delta(j, i)}{\sum_{v \in N(u)} W_{u,v}} \qquad (2.1)$$

où $MS(u, i)$ est le score pondéré de la fonction candidate i pour la protéine de requête u. Et $\delta(j, i)$ vaut 1 si la fonction j de la protéine v est la même que la fonction candidate i, sinon 0.

Pour illustrer le processus d'annotation de *GrAPFI-GO*, prenons une protéine P non annotée avec un ensemble de domaines $D = (d5, d6, d101)$. Selon la similarité de Jaccard, P est connecté avec P2 et P4 dans le graphe de similarité de domaine. Par conséquent, la protéine P aura P2 et P4 comme voisins, c'est-à-dire $N(P) = P2, P4$. Dès que $N(P)$ est calculé, les annotations GO des protéines voisines sont propagées avec les poids correspondants calculés à l'aide de l'équation. 2.1. Lors de la propagation de l'étiquette, nous ne comptons pas les protéines non annotées qui apparaissent dans $N(P)$. Toutes les annotations fonctionnelles sont classées en fonction de leurs poids cumulés. Les annotations les mieux classées sont sélectionnées comme les meilleures annotations fonctionnelles pour la protéine P.

Il est important de mentionner que *GrAPFI-GO* ainsi que la plupart des outils d'annotation par des termes GO [Radivojac and et al., 2013] [Jiang and et al., 2016] produisent un grand nombre de prédictions. En raison de ce grand nombre d'annotations prédites pour chaque protéine, la précision du modèle diminue tandis que le rappel augmente. Cependant, les résultats
de ces approches soulèvent une grande inquiétude sur les faux positifs dans les prédictions. Par conséquent, nous avons besoin d'une méthode qui améliore la précision du modèle, et donc diminue les faux positifs dans l'ensemble prédit. Pour résoudre ce problème, nous avons adopté une technique d'élagage naïf en identifiant et en éliminant les annotations aberrantes à l'aide de la similarité sémantique. La mesure de la similarité sémantique entre les termes GO a toujours été une étape essentielle dans la recherche en bioinformatique fonctionnelle. Dans un ensemble d'annotations GO prédites pour une protéine, la similarité sémantique par paires entre les termes GO peut montrer à quel point ces termes sont liés les uns aux autres et pas seulement à la protéine. Nous avons utilisé la méthode GOGO [Zhao and Wang, 2018] pour calculer le score de similarité fonctionnelle (SS) entre les termes GO et l'avons donc utilisé pour calculer le score d'appartenance de chaque terme GO prédit.

## 2.3 Résultats

### 2.3.1 Préparation de données pour la prédiction des numéros EC

Nous avons collecté plus de 262 milles protéines à partir de la version de mars 2018 de la base de données Uniprot-KB/SwissProt [Consortium, 2015] en utilisant les règles suivantes : (1) chaque protéine doit contenir au moins une signature InterPro et (2) elle doit être annotée avec au moins une annotation EC. Après avoir obtenu les données protéiques de chacune des protéines, nous avons extrait la composition en domaines InterPro et les annotations EC. Ensuite, nous avons construit le graphe de protéines comme décrit dans la Section 2.3.3. Chaque protéine forme son propre nœud dans le graphe. Nous n'avons pas prétraité les données d'apprentissage pour supprimer la redondance. Au contraire, lors de l'annotation, *GrAPFI* ignore la même protéine si elle apparaît dans le voisinage. Par exemple, pour une protéine de requête q, *GrAPFI* collectera les voisins satisfaisant un score de similarité Jaccard maximum. Lorsque la similarité Jaccard maximale est inférieure à 1,0, *GrAPFI* omet les voisins avec exactement la même composition de domaine.

Le graphe d'apprentissage couvre 25 classes EC de niveau 2, 31 de niveau 3 et 408 de niveau 4 à partir de 41,618 oxydoréductases, 70,530 transférase, 100,027 hydrolases, 14,677 lyases, 25,551 isomérase et 29,735 ligases qui sont liées à l'aide de 10,866 signatures InterPro.
Dans le graphe d'apprentissage, il y a :

1. 4.3 % des protéines sont des protéines à domaine unique, c'est-à-dire des protéines n'ayant qu'un seul domaine dans leur composition de domaine,

2. 5.7 % des protéines ont plus d'un numéro EC associés à eux

3. Environ 15% des nœuds d'entraînement ont des annotations EC incomplètes, c'est-à-dire que les numéros EC attribués à ces protéines n'ont pas les quatre chiffres.

Pour valider *GrAPFI*, nous avons utilisé six protéomes de référence de Uniprot-KB/SwissProt comme ensemble de test. Les protéomes de référence sont les suivants : (1) Rattus norvegicus (UP000002494) contenant 1,953 protéines, (2) Mus musculus (UP000000589) contenant 3,682 protéines, (3) Saccharomyces cerevisiae (UP000002311) contenant 1,581 protéines, (4) Homo sapiens (UP000005640) contenant 3,843 protéines, et (5) Arabidopsis thaliana (UP000006548) contenant 5,352 protéines. (6) E. Coli (UP000000625) contenant 1,465 protéines. Pour chacun des protéomes de référence, nous avons collecté les domaines InterPro et les numéros EC de Uniprot-KB/SwissProt. Nous n'avons conservé que les protéines qui ont au moins un domaine InterPro et sont annotées avec un seul numéro EC.

## 2.3.2 Préparation de données pour la prédiction des termes GO

Nous avons utilisé un jeu de données de 1000 protéines appelé MetaGo [Zhang et al., 2018]. Nous construisons le graphe en utilisant les données d'entraînement de la 3ème édition de la compétition CAFA (CAFA3)<fnref n="3" />. CAFA3 est une compétition bien connue qui vise à annoter des séquences de protéines. Habituellement, CAFA3 fournit des séquences cibles et d'entraînement pour créer des modèles d'annotation. Dans cette étude, pour construire le réseau, nous avons utilisé des séquences d'entraînement CAFA3 et nous avons collecté des informations sur le domaine et la famille de ces protéines auprès d'UniprotKB. Ensuite, nous avons construit le graphe des protéines d'entraînement CAFA3. Ce graphe contient environ 65,000 nœuds sous forme de protéines et une moyenne de 16 termes GO de vérité terrain par protéine.

Pour préparer l'ensemble de test, nous avons utilisé des séquences de référence MetaGO [Zhang et al., 2018] et exécuté l'outil InterProScan pour identifier les domaines et les informations

<footnote n="3">3. https://biofunctionprediction.org/cafa/</footnote>
sur la famille à partir de la séquence. En utilisant les domaines et les informations sur la famille des protéines de test, nous exécutons GrAPFI-GO et d'autres outils d'annotation sur toutes les protéines de test et récupérons les annotations prédites. Nous appliquons ensuite ou non la méthode d'élagage sémantique et nous comparons l'efficacité de l'annotation à l'aide de métriques standards.

### 2.3.3 Analyse des performances des annotations EC

Pour valider les performances d'annotation de GrAPFI, nous avons calculé la précision, la macro-précision, le macro-rappel et le score macro-F1 à différents niveaux de numéro EC. Pour chaque séquence de requête, nous avons sélectionné uniquement l'annotation la mieux classée. La méthode de validation que nous avons utilisée est similaire à la méthode de validation croisée. Pour chaque protéome, lors de l'annotation d'une protéine, nous avons supprimé cette protéine de l'ensemble d'apprentissage afin qu'une cartographie directe ne soit pas présente. La formule suivante (telle qu'utilisée dans [Li et al., 2018a]) a été utilisée pour calculer les scores d'évaluation :

$$ accuracy(y, y') = \frac{1}{N} \sum_{i=0}^{N-1} 1(y_i = y'_i), \qquad (2.2) $$

Ici, y et y' sont respectivement la liste des vérités terrain et des annotations prédites. La précision est calculée pour chaque niveau d'annotation EC. Comme il s'agit d'un problème de classification multi-classes, nous avons calculé le score de macro-précision, de macro-rappel et de macro-F1 comme suit :

$$ Macro - precision(y, y') = \frac{1}{|M|} \sum_{l \in M} precision(y_l, y'_l), \qquad (2.3) $$

$$ Macro - recall(y, y') = \frac{1}{|M|} \sum_{l \in M} recall(y_l, y'_l), \qquad (2.4) $$

$$ Macro - F1(y, y') = \frac{1}{|M|} \sum_{l \in M} F1\ measure(y_l, y'_l), \qquad (2.5) $$

Ici, $y_l$ est la partie de y avec l'étiquette l et $y'_l$ est la partie de y' avec l'étiquette l. M est
l'ensemble des classes. En général, la précision, le rappel et la mesure F1 sont calculés comme suit lorsque deux ensembles A et P sont donnés :

$$precision = \frac{|A \cap P|}{|P|}, \qquad (2.6)$$

$$recall = \frac{|A \cup P|}{|A|}, \qquad (2.7)$$

$$F1\text{-}measure = \frac{2 \times precision \times recall}{precision + recall}. \qquad (2.8)$$

Ici, A est l'ensemble des vérités de terrain et P est l'ensemble des prédicitions. Comme les numéros EC sont hiérarchiques avec 4 niveaux, nous rapportons la précision, le rappel et la mesure F1 par niveau. Le niveau 1 désigne la classe principale, le niveau 2 la sous-classe, le niveau 3 la sous-sous-classe et le niveau 4 la sous-sous-sous-classe. Nous rapportons également la couverture qui est calculée selon Coverage = M/T, où T est le nombre total de protéines dans l'ensemble de test et M est le nombre de protéines pour lesquelles au moins un numéro EC est prédit. Pour chaque séquence de requête, nous considérons l'annotation la plus élevée. À des fins d'évaluation, nous avons divisé l'annotation EC à 4 chiffres en ses éléments constitutifs. Ensuite, pour le niveau 1, nous considérons le premier chiffre, pour le niveau 2, nous prenons les 2 premiers chiffres, pour le niveau 3, nous prenons les 3 premiers chiffres et enfin pour le niveau 4, nous prenons les quatre chiffres ensemble.

Pour l'ensemble de données de validation, GrAPFI a été exécuté en ajustant différents indices de similarité allant de 0,05 à 0,5, et en fixant une limite supérieure de similarité à 1 ou moins de 1.

La Figure 2.3 montre les performances de GrAPFI pour le protéome de référence d'A. thaliana.

Dans la Figure 2.3, nous montrons la précision des annotations (axe Y) par rapport à différents seuils de similarité Jaccard (axe X) pour les protéomes respectifs. Nous avons considéré des seuils de similarité allant de 0,05 à 0,5 car la couverture des annotations chute significativement après 0,5. Pour chacun des seuils, nous présentons la précision de la prédiction des chiffres EC-1, EC-2,
<figure><img src="image_6.png" /><figcaption>FIGURE 2.3 – Performances et couvertures en fonction de divers seuils des indices de similarité de Jaccard pour le protéome de référence *A. thaliana*. [Sarker et al., 2020b]</figcaption></figure>

EC-3 et EC-4, respectivement en vert, bleu, orange et noir. Parallèlement à la précision, nous présentons également la couverture de l'annotation (courbe rouge). Pour chacune des figures, nous avons deux parties. La première partie montre la précision et la couverture en considérant uniquement les voisins qui ont une similarité Jaccard inférieure ou égale à 1. La deuxième partie considère la similarité Jaccard strictement inférieure à 1. On peut voir à partir de ces chiffres que *GrAPFI* fonctionne très bien pour tous les cas avec une bonne couverture.

Pour comparer *GrAPFI* avec d'autres méthodes, nous avons considéré trois méthodes basées sur l'apprentissage automatique, à savoir ECPred [Dalkiran et al., 2018], DEEPre [Li et al., 2018a] et SVMProt [Cai et al., 2003]. Les performances sont comparées sur la base du benchmark COFACTOR [Roy et al., 2012] comportant 318 séquences. Les résultats de la prédiction SVMProt couvrent trois conditions différentes : (1) en utilisant SVM uniquement, (2) en utilisant KNN uniquement et (3) en utilisant SVM, KNN et PNN combinés. La Figure 2.4 montre l'analyse des performances pour la prédiction de niveau EC-1 et de niveau EC-2. Les résultats présentés ici sont obtenus en utilisant une valeur d'indice de similarité Jaccard entre 0,3 et 1. Un seuil de similarité beaucoup plus bas engendre des faux positifs qui réduisent considérablement la précision. Sur la base des résultats obtenus, un indice de similarité de 0,3 permet d'obtenir un bon compromis entre précision et couverture.
<figure><img src="image_7.png" /><figcaption>FIGURE 2.4 – La partie 2.4(a) montre une comparaison des performances de *GrAPFI* avec *SVMProt* (SVM, KNN et mixte), *DEEPre* et *ECPred* pour les codes à 2 chiffres. Prédictions du nombre EC. La partie 2.4(b) montre la comparaison de précision de *GrAPFI* avec *DEEPre* et *ECPred* pour les 4 niveaux de prédiction EC. La partie 2.4(c) montre la couverture des méthodes considérées. [Sarker et al., 2020b]</figcaption></figure>

Étant donné que toutes les méthodes ne peuvent pas faire de prédictions pour les quatre niveaux EC, nous avons comparé *GrAPFI* uniquement avec *ECPred* et *DEEPre* pour les nombres EC à 4 chiffres, comme le montre la Figure 2.4(b). Sur la Figure 2.4(c), nous montrons la couverture d'annotation des méthodes considérées ici. Elle montre qu'*ECPred* a une couverture supérieure par rapport aux autres méthodes. La raison pour laquelle *GrAPFI* ne parvient pas à atteindre la couverture la plus élevée est due au fait qu'il s'agit d'une méthode d'annotation basée sur le voisinage. *GrAPFI* effectue la propagation des étiquettes en filtrant les voisins faiblement liés et déterminés par un seuil de similarité minimum. En raison de cette action de filtrage, dans quelques cas, *GrAPFI* ne parvient pas à suggérer une annotation appropriée pour les protéines de requête. Cela réduit la couverture totale des annotations. Cependant, d'un autre côté, *GrAPFI* augmente la précision en considérant des voisins fortement liés. Comme le montrent les figures 2.4(b) et 2.4(c), *GrAPFI* a une meilleure précision par rapport à *ECPred* et *DEEPre*, mais il offre une couverture légèrement inférieure à *ECPred*.

Les performances de *GrAPFI* pour les protéomes de référence d'Homo sapiens, S. cerevisiae, Mus musculus, Rattus norvegicus et E. Coli ainsi qu'une évaluation des performances de *GrAPFI* pour la classification binaire (enzyme ou non) des protéines peuvent être consultées dans l'article [Sarker et al., 2020a].
### 2.3.4 Analyse des performances des annotations GO

Nous avons évalué l'effet de l'ajout des étapes d'élagage sémantique et de post-traitement sur les performances d'annotation de *GrAPFI-GO* et des autres outils d'annotation facilement disponibles, à savoir PANNZER et DeepGOPlus [Kulmanov and Hoehndorf, 2020].

<table><caption>TABLE 2.1 – Effet de la méthode d'élagage et de post-traitement sur les performances de *GrAPFI-GO* et de deux autres outils d'annotation automatique. La précision moyenne, le rappel et le score F1 sont calculés pour chaque méthode dans quatre situations. Pas de post-traitement : sans post-traitement ni élagage ; SS-max : élagage en utilisant le SS le plus élevé comme seuil ; SS-5 : élagage en utilisant le 5ème SS le plus élevé comme seuil ; SS-5-MS-max/2 : élagage en utilisant le 5ème SS le plus élevé et (MS maximum)/2 comme seuils. [Sarker et al., 2022]</caption><thead><tr><th>Méthode</th><th>Post-traitement</th><th>Précision</th><th>Rappel</th><th>Mesure F1</th></tr></thead><tbody><tr><td rowspan="4">GrAPFI</td><td>Sans post-traitement</td><td>0.165</td><td>0.108</td><td>0.107</td></tr><tr><td>SS-max</td><td><strong>0.573</strong></td><td>0.115</td><td>0.175</td></tr><tr><td>SS-5</td><td>0.445</td><td>0.380</td><td>0.376</td></tr><tr><td>SS-5-MS-max/2</td><td>0.440</td><td><strong>0.391</strong></td><td><strong>0.379</strong></td></tr><tr><td rowspan="4">PANNZER</td><td>Sans post-traitement</td><td>0.547</td><td><strong>0.942</strong></td><td>0.668</td></tr><tr><td>SS-max</td><td><strong>0.637</strong></td><td>0.225</td><td>0.301</td></tr><tr><td>SS-5</td><td>0.634</td><td>0.515</td><td>0.536</td></tr><tr><td>SS-5-MS-max/2</td><td>0.603</td><td><strong>0.689</strong></td><td><strong>0.609</strong></td></tr><tr><td rowspan="4">DeepGOPlus</td><td>Sans post-traitement</td><td>0.053</td><td><strong>0.653</strong></td><td>0.095</td></tr><tr><td>SS-max</td><td><strong>0.249</strong></td><td>0.120</td><td>0.138</td></tr><tr><td>SS-5</td><td>0.186</td><td>0.182</td><td>0.160</td></tr><tr><td>SS-5-MS-max/2</td><td>0.167</td><td>0.233</td><td><strong>0.1725</strong></td></tr></tbody></table>

Nous exécutons les trois outils d'annotation sélectionnés sur les données de référence MetaGO et obtenons des ensembles de termes GO prédits. Ces ensembles prédits sont ensuite élagués à l'aide de la similarité sémantique et enrichis par un post-traitement hiérarchique. Les résultats sont présentés dans le tableau 2.1. Ici, nous présentons les métriques d'évaluation sans les catégoriser en aspects GO, car la méthode d'élagage et de post-traitement en plusieurs étapes prend énormément de temps pour produire l'ensemble d'annotations prédit. Pour chaque protéine de test, le score du modèle (MS, fourni par chaque méthode) et le score de similarité sémantique (SS, calculé avec notre implémentation de GOGO) sont obtenus pour tous les termes prédits pour cette protéine. Différents seuils de ces deux scores sont utilisés pour l'analyse. L'ensemble final de termes prédits est comparé à la vérité terrain du benchmark. Pour chaque outil d'annotation, le tableau 2.1 montre les performances d'annotation dans quatre cas : (1) sans aucun
type d'élagage ni de post-traitement, (2) lorsque le score SS le plus élevé est le seuil pour SS, (3) lorsque le 5ème score SS le plus élevé est le seuil pour SS et (4) lorsque le 5ème score SS le plus élevé et la moitié du score MS maximal sont les seuils pour SS et MS respectivement.

Les résultats expérimentaux montrent clairement que l'approche de post-traitement qui utilise la similarité sémantique des termes GO prédits pour élaguer l'ensemble prédit ainsi que l'enrichissement par les ancêtres, améliore considérablement les performances globales de la méthode *GrAPFI-GO*. En particulier, elle améliore la précision de plusieurs plis, passant de 16,5 % à 57,3 % lors de l'utilisation de SS-max comme coupure lors du post-traitement. De même, cette approche proposée améliore considérablement la précision de PANNZER et DeepGOPlus. Des expérimentations supplémentaires sont disponibles dans l'article [Sarker et al., 2022].

## 2.4 Discussion et conclusions

L'utilisation des graphes pour représenter les protéines est une approche intéressante, car la structure riche des graphes permet de relier non seulement les protéines qui interagissent, mais aussi celles qui partagent des informations similaires. La représentation des protéines avec des graphes permet aussi d'appliquer une panoplie d'algorithmes de graphes sur des données protéiques. Dans le contexte de ce travail, les algorithmes *GrAPFI* et *GrAPFI-GO* pour la propagation d'étiquettes ont été appliqués sur un graphe de protéines pour pouvoir annoter des protéines par des propriétés fonctionnelles décrivant leurs fonctions. Cette tâche d'annotation automatique des fonctions des protéines est un sujet important pour la communauté scientifique dans le domaine de la bioinformatique, en raison du manque d'annotation des protéines et en raison des coûts élevés et de la nature chronophage de l'annotation fonctionnelle manuelle.

Dans la Section 2.2.1, nous avons présenté la nouvelle façon de connecter les protéines sur la base de domaines potentiellement liés à leurs fonctions. Nous avons présenté dans la Section 2.3 les résultats expérimentaux qui motrent l'efficacité des méthodes proposées (*GrAPFI* et *GrAPFI-GO*) pour annoter des protéines avec des numéros EC ou par des termes GO. Cela signifie finalement que les méthodes d'annotation proposées sont biologiquement significatives. L'un des principaux avantages de l'utilisation de ces méthodes pour annoter les protéines est qu'ils produisent des annotations automatiques de qualité et explicables avec un pipeline d'an-
notation relativement à la portée de nos investigations et contributions. Bien que les méthodes d'annotation proposées dans le cadre de la thèse de Bishnu Sarker [Sarker, 2021] fonctionnent bien, leur utilisation présente quelques inconvénients. Par exemple, l'étape cruciale de construction du graphe de protéines se base sur la recherche de domaines des protéines qui doit être réalisée à l'aide d'un autre outil. En plus, ces méthodes ne peuvent pas être utilisées avec des protéines dépourvues d'informations sur le domaine et pour les protéines à domaine unique. Dans la plupart des cas, ces méthodes ne parviennent pas à trouver les annotations appropriées. Pour résoudre ce problème de dépendance de ces approches aux domaines protéiques, nous avons tenté, dans le cadre d'un travail de recherche, d'explorer les autres attributs tels que les voies biologiques, le génotype, le phénotype, le taxon qui pourraient incorporer des informations importantes dans le processus d'annotation. Plus particulièrement, nous avons construit un graphe de connaissances (KG) pour intégrer diverses sources de données et nous avons proposé une méthode préliminaire appelée Prot-A-GAN basée sur les réseaux antagonistes génératifs (GAN) [Goodfellow et al., 2014] pour l'annotation des protéines. En suivant les terminologies du GAN, nous formons d'abord un discriminateur en utilisant un échantillonnage négatif adaptatif au domaine pour discriminer les triplets positifs et négatifs, puis nous formons un générateur pour guider une marche aléatoire sur le graphe de connaissances qui identifie les chemins entre les protéines et les annotations GO [Sarker et al., 2021]. Bien qu'il s'agisse d'une méthode de preuve de concept, les résultats préliminaires de la méthode Prot-A-GAN sont prometteurs et ouvrent plusieurs pistes de recherche dans le domaine de la prédiction des fonctions de protéines en utilisant les graphes de connaissances et les techniques d'apprentissage profond [Sarker et al., 2021].
# Chapitre 3

# Prédiction de liens dans des graphes de connaissances complexes

## 3.1 Introduction

Dans sa forme la plus générale, un graphe est constitué d'un ensemble de nœuds représentant des objets ou des entités et d'un ensemble de liens représentant les relations entre les paires d'entités. Les graphes peuvent encoder de riches informations sur les nœuds et leurs relations complexes. Par exemple, le graphe d'amitié dans un réseau social, où les nœuds sont des personnes, les liens sont des amitiés entre des couples de personnes ; le réseau d'interaction protéine/protéine (PPI), où les nœuds sont des protéines, et les liens sont des interactions entre des paires de protéines. Les graphes peuvent contenir des informations plus descriptives sur les nœuds, comme les types, les attributs et aussi sur les liens, comme les noms des liens. Ces types de graphes sont généralement connus sous le nom de graphes de connaissances (KG). Les directions et les noms sont deux exigences obligatoires des liens dans les graphes de connaissances. Ces graphes supportent des liens multiples entre une paire de nœuds ainsi que des boucles. Par conséquent, les graphes de connaissances encodent plus d'informations sémantiques que les graphes simples.

La plupart des graphes du monde réel sont de grande taille. Par exemple, le graphe HI-III PPI [Kovacs et al., 2019] est constitué de 18,000 protéines humaines et de 35,500 interactions protéine-protéine ; le graphe de connaissances Freebase [Google, 2013] contient près
de 44 millions de nœuds représentant des entités de divers domaines (par exemple, des per-
sonnes, des lieux, des religions, des entreprises) et 2,4 milliards de liens représentant des
relations nommées entre des paires d'entités. Cependant, ces graphes sont loin d'être com-
plets. Le lieu de naissance et la nationalité sont manquants pour environ 78,5 % et 93,8 %
des personnes, respectivement, dans le graphe de connaissances Freebase [Min et al., 2013]. Le
problème de la prédiction des liens manquants ou de l'inférence de nouveaux liens dans un
graphe est communément appelé le problème de prédiction de liens [Lü and Zhou, 2011]. For-
mellement, la prédiction de liens est la tâche de prédire la probabilité d'un lien entre deux
nœuds en se basant sur les informations topologiques et/ou structurelles disponibles d'un
graphe [Xu et al., 2016]. Les approches de prédiction de liens permettent de découvrir des re-
lations complexes dans un graphe, ce qui nous aide à prendre de meilleures décisions. Par
exemple, la tâche de reprogrammation/repositionnement de médicaments peut être formulée
comme une tâche de prédiction de liens dans un graphe biologique où les liens non observés
entre les nœuds de médicaments (approuvés/essayés cliniquement) et de maladies sont pré-
dits [Somolinos et al., 2021, Fiscon et al., 2021, Kanatsoulis and Sidiropoulos, 2021]. Les experts
peuvent ensuite procéder à la validation expérimentale de ces paires médicament-maladie pré-
dites afin de trouver de nouveaux médicaments efficaces et/ou appropriés pour la maladie en
question.

Le développement d'une approche de prédiction de liens pour les graphes soulève deux défis majeurs. Le premier défi est de fournir des performances de prédiction élevées sur des graphes provenant de différents domaines. Le second défi est de fournir une explication suffisante des résultats pour apporter de la fiabilité à l'approche.

La prédiction de liens dans les graphes de connaissances est plus difficile que dans les graphes simples, car les graphes de connaissances contiennent des relations complexes entre les nœuds. Les approches de prédiction de liens pour les graphes de connaissances sont soit basées sur des règles logiques, soit basées sur les plongements. Des études montrent que les approches de prédiction de liens basées sur les plongements offrent de meilleures performances de prédiction et une meilleure évolutivité que les approches traditionnelles basées sur des règles. Cependant, les approches basées sur les plongements ne sont pas explicables. En fait, les approches de prédiction de liens basées sur les plongements dans les graphes de connaissances soulèvent deux nouveaux défis en
plus de la performance de prédiction élevée et de l'explicabilité. Le premier est la génération d'exemples négatifs de haute qualité, car ils ne sont pas facilement disponibles. Le second est le passage à l'échelle des approches de prédiction de liens, car les graphes de connaissances représentant le monde réel sont de taille énorme. Bien qu'il existe de nombreuses approches pour la prédiction de liens dans les graphes, il est remarquable que les approches existantes ne sont pas assez bonnes pour offrir des solutions satisfaisantes. Dans ce contexte, l'état de l'art de la prédiction de liens dans les graphes de connaissances appelle deux orientations de recherche : (1) la génération d'exemples négatifs de haute qualité pour les approches basées sur les plongements, (2) l'explication de la prédiction de liens basée sur les plongements.

Dans ce chapitre, je présente tout d'abord notre contribution pour la génération d'exemples négatifs de bonne qualité avec nos approches basées sur les plongements. Ensuite, je présente notre méthode générique à base de règles pour l'explication des résultats des méthodes de prédiction de liens dans les graphes de connaissances. À la fin de ce chapitre, je présente notre application des méthodes proposées pour le repositionnement de médicaments pour le COVID-19.

## 3.2 Échantillonnage négatif simple (SNS)

Au cours de l'apprentissage de plongement (ou embedding) efficace de graphe de connaissances, l'échantillonnage de triplets négatifs a été mis en évidence comme une étape importante, car les graphes de connaissances ne contiennent que des triplets positifs. Dans le cadre de la thèse de Kamrul Islam [Islam, 2022], nous avons proposé une nouvelle méthode efficace d'échantillonnage négatif simple (SNS pour Simple Negative Sampling) pour échantillonner des triplets négatifs de haute qualité dans les graphes de connaissances.

Dans cette section, nous décrivons d'abord un modèle de plongement géométrique de graphe de connaissances, puis notre méthode SNS. Dans ce qui suit, nous utilisons $\mathbb{E}$ pour désigner l'ensemble de toutes les entités, $\mathbb{R}$ pour désigner l'ensemble de toutes les relations, $\mathbb{S}$ pour désigner l'ensemble de triplets positifs d'entrainement, $\mathbb{D}$ pour désigner l'ensemble de triplets de test positifs, $\mathbb{Q}$ pour désigner l'ensemble de tous les triplets positifs, $\mathcal{D}$ pour désigner la taille de la dimension du plongement, $m$ pour désigner la taille du lot, $S_m$ et $S'_m$ pour désigner un lot de
triplets positifs et négatifs respectifs.

Le modèle de KGE géométrique commence par initialiser les plongements d'entités et de relations de manière aléatoire à partir de distributions uniformes/gaussiennes [Wang et al., 2017]. Pour l'apprentissage du modèle, un lot de triplets d'entraînement positifs $S_m$ est extrait de l'ensemble de triplets d'entraînement, $\mathbb{S}$. Une méthode d'échantillonnage négatif est ensuite utilisée pour générer un lot de triplets négatifs $S'_m$ pour le lot de triplets positifs $S_m$. Les lots de triplets positifs et négatifs sont ensuite utilisés par la méthode d'apprentissage par paires (ou pairwise learning) [Menon and Elkan, 2011] pour apprendre les plongements. Dans l'apprentissage par paires, le modèle tente d'attribuer un score de plausibilité plus élevé à un triplet positif qu'à son triplet négatif correspondant. La perte par paires (ou pairwise loss) pour un triplet positif $(h, r, t) \in S_m$ et son triplet négatif correspondant $(h', r, t') \in S'_m$ est définie dans l'équation 3.1 [Wang et al., 2017].

$$L(f(h, r, t), f(h', r, t')) = [\lambda - f(h, r, t) + f(h', r, t')]_+ \quad (3.1)$$

$L$ est la fonction de perte, $f$ est la fonction de score du modèle de plongement, $\lambda$ est la marge et $[\cdot]_+ = \max(0, \cdot)$ est la fonction de perte (ou hinge function). L'objectif de l'apprentissage est d'optimiser les plongements d'entités et de relations pour minimiser la perte totale par paires par l'équation 3.2.

$$\min_{\Theta} \sum_{\forall (h,r,t) \in S_m, (h',r,t') \in S'_m} L(f(h,r,t), f(h',r,t')) + \lambda \mathrm{reg}(\Theta) \quad (3.2)$$

$L$ est la fonction de perte, $f$ est la fonction de score du modèle de plongement, $\lambda$ est la marge, $reg(\Theta)$ est le terme de régularisation, $(h, r, t) \in S_m$ est un triplet positif et $(h', r, t') \in S'_m$ est le triplet négatif correspondant.

Le processus de mise à jour des plongements est répété pour tous les lots de triplets positifs, et l'ensemble du processus d'apprentissage est répété pendant T fois/époques (ou epochs). Le processus d'entraînement du modèle est similaire à un entraînement du modèle de plongement géométrique traditionnel, sauf que nous adaptons notre méthode d'échantillonnage négatif.
La méthode SNS vise à générer des triplets négatifs de haute qualité tout en évitant le problème de «vanishing-gradient» de l'échantillonnage aléatoire uniforme, le problème complexe d'optimisation des paramètres de l'échantillonnage basé sur les GANs et les problèmes de consommation excessive de mémoire de NSCaching. La Figure 3.1(a) montre les étapes éssentielles de l'échantillonnage avec SNS. Les étapes pour chaque triplet positif sélectionné $q = (h, r, t) \in \mathbb{S}$ sont décrites ci-dessous.

**Étape 1. Génération initiale d'un ensemble de triplets négatifs** : Comme illustré dans la Figure 3.1(a), SNS commence par générer un ensemble initial de triplets négatifs pour le triplet positif ($q$) par perturbation. Cette étape est similaire aux autres méthodes d'échantillonnage. Avec la méthode de perturbation, la tête ($h$)/queue ($t$) du triplet positif est corrompue en remplaçant la tête/queue par d'autres entités de l'ensemble d'entités ($\mathbb{E}$). En même temps, on vérifie que l'ensemble négatif ne contient aucun triplet positif.

Pour des raisons de simplification, nous considérons uniquement la perturbation de la queue. Par conséquent, corrompre la queue ($t$) donne l'ensemble négatif initial $q'_0(t) = \{(h, r, t') \notin \mathbb{Q} | t' \in \mathbb{E}\}$.

<figure><img src="image_8.png" /><figcaption>FIGURE 3.1 – La méthode d'échantillonnage SNS. [Islam et al., 2022]</figcaption></figure>
**Étape 2. Génération de l'ensemble de triplets candidats** : Généralement, la taille de l'ensemble $q'_0(t)$ est grande car le graphe de connaissances contient un grand nombre d'entités. Il a été démontré que seuls certains des négatifs initiaux de l'ensemble sont de bonne qualité [Zhang et al., 2019]. Comme nous avons besoin de peu de négatifs pour chaque triplet positif, nous échantillonnons aléatoirement $N_1$ triplets à partir de $q'_0(t)$ pour générer l'ensemble de triplets négatifs candidat $q'_1(t)$ (c'est-à-dire, $q'_1(t) \subseteq q'_0(t)$) pour le paramètre défini par l'utilisateur $N_1$.

Au fur et à mesure de l'apprentissage, on souhaite que la qualité des triplets négatifs pour l'étape suivante soit meilleure ou proche de la qualité du négatif ou des négatifs de l'étape en cours. À cette fin, les triplets négatifs échantillonnés pour chaque triplet positif de l'époque actuelle sont stockés dans une structure de données appelée LRS (pour *Least Recently Selected*). Supposons que $LRS_q = (h - LRS_q) \cup (t - LRS_q)$ stocke les triplets négatifs pour le triplet positif (q) où $h - LRS_q$ et $t - LRS_q$ sont les triplets négatifs échantillonnés par perturbation de la tête et de la queue respectivement à l'époque précédente. Les triplets négatifs enregistrés sont utilisés dans l'étape en cours pour échantillonner des triplets négatifs de haute qualité. Comme décrit par le processus de génération de triplets négatifs par perturbation de la queue, $t - LRS_q$ est ajouté à l'ensemble de triplets négatifs candidat, $q'_1(t)$, c'est-à-dire, $q'_1(t) := q'_1(t) \cup t - LRS_q$. Le but de l'utilisation de LRS est de favoriser le comportement d'exploration de la méthode SNS et de garantir que la qualité des triplets négatifs à l'étape en cours est meilleure ou au moins proche de la qualité des triplets négatifs à l'étape précédente.

**Étape 3. Calcul de la probabilité d'échantillonnage** :

Dans cette étape, nous calculons la probabilité d'échantillonnage de chaque triplet négatif dans l'ensemble de triplets négatifs candidats $q'_1(t)$. Les triplets négatifs avec des probabilités plus élevées sont considérés comme des triplets négatifs de haute qualité. La probabilité est définie en fonction du score de distance de chaque triplet négatif. Le score de distance entre un triplet négatif $(h, r, t'_i) \in q'_1(t)$ et le triplet positif associé $(q = (h, r, t))$, est calculé comme la distance
entre l'entité corrompue (t) et la nouvelle entité (t') (voir formule 3.3).

$$d((h, r, t), (h, r, t'_i)) = \|\mathbf{t} - \mathbf{t}'_i\| \quad (3.3)$$

où, $\mathbf{t}$ et $\mathbf{t}'_i$ sont les plongements des entités $t$ et $t'_i$. Une fonction softmax est ensuite utilisée pour calculer le score de probabilité d'échantillonnage de chaque triplet négatif candidat $(h, r, t'_i) \in q'_1(t)$ comme illustré par la formule 3.4.

$$P(h, r, t'_i) = \frac{\exp\left(\frac{1}{d(t, t'_i)}\right)}{\sum_{j=1}^{N_1} \exp\left(\frac{1}{d(t, t'_j)}\right)} \quad (3.4)$$

La fonction softmax calcule une probabilité d'échantillonnage plus élevée pour les triplets négatifs candidats avec un score de distance faible pour étayer notre hypothèse.

## Étape 4. Échantillonnage de triplets négatifs et mise à jour de LRS :

Les triplets de l'ensemble des candidats négatifs, $q'_1(t)$ sont classés par ordre décroissant de leurs probabilités et $k$ triplets négatifs sont échantillonnés. Un choix naturel pourrait être d'échantillonner top-k ($k=1$ pour l'apprentissage par paires, $k > 1$ pour l'apprentissage par maximum de vraisemblance) triplets négatifs. Cependant, l'échantillonnage des triplets négatifs classés parmi les k premiers pourrait poser deux problèmes. Premièrement, il y a une chance d'échantillonnage répété du ou des mêmes triplets négatifs (même dans des étapes consécutives) car l'ensemble de triplets négatifs candidats actuel comprend également le ou les triplets négatifs de haute qualité échantillonnés récemment (LRS). Cela affecterait la capacité d'exploration de l'échantillonnage de la méthode SNS. Deuxièmement, l'existence de faux triplets négatifs n'est pas ignorable car les triplets négatifs et positifs ont des scores élevés [Wang et al., 2017]. Pour minimiser ces problèmes, SNS échantillonne au hasard k triplets négatifs à partir de $N_2$ triplets les mieux classés dans $q'_1(t)$ comme $q'_t = \{(h, r, t'_i)|\text{rank}_{(h,r,t'_i)\le N_2}\}$ pour un paramètre défini par l'utilisateur $N_2$ où $N_2 > k$. Comme SNS échantillonne des triplets négatifs à partir de $N_2$ triplets négatifs les mieux classés, SNS évite les faux triplets négatifs les mieux classés pour de nombreux triplets positifs.

SNS répète les étapes décrites ci-dessus (de la génération initiale de l'ensemble de triplets négatifs à la génération suivante).
gatifs à l'échantillonnage de k triplets négatifs) pour la corruption de tête(h) également pour
échantillonner k triplets négatifs comme $q'_h$ pour le triplet positif, q. Le LRS$_q$ est mis à jour avec
les triplets négatifs échantillonnés de haute qualité 2k comme $h - LRS_q = q'_h$, $t - LRS_q = q'_t$.
Enfin, nous échantillonnons au hasard k triplets négatifs de haute qualité comme $q'_{h,r,t}$ à partir
de 2k triplets négatifs dans $q'_h \cup q'_t$ (Figure 3.1(b)). Le ou les k triplets négatifs échantillonnés,
$q'$ et le triplet positif correspondant, q sont ensuite ajoutés à l'ensemble d'apprentissage pour les
modèles de plongement de graphes de connaissances.

Il est important de mentionner que la méthode SNS est générale et injectable à n'importe
quelle méthode de plongement géométrique de graphes de connaissances pour échantillonner les
triplets négatifs.

3.3 Explication des prédictions

L'applicabilité des approches de prédiction de liens dans des graphes de connaissances est
souvent limitée en raison de leur incapacité à expliquer les prédictions. Nous avons proposé dans
le cadre de la thèse de Kamrul Islam [Islam, 2022], une nouvelle méthode pour apprendre des
règles de haute qualité basées sur un graphe de connaissances et ses plongements appris. Ensuite,
nous utilisons une stratégie abductive pour expliquer les prédictions faites par la méthode des
plongements basée sur l'instanciation des règles extraites pour trouver des chemins explicatifs
pour les prédictions.

Pour extraire des règles à partir d'un graphe de connaissances, nous considérons différents
modèles de chemins existants dans le graphe. La Figure 3.2 illustre quatre types de chemins de
longueur 2 dans le graphe 'Family', un graphe de connaissances, où les relations sont les relations
familiales entre les personnes [Kok and Domingos, 2007, Sadeghian et al., 2019]. Les méthodes
existentes d'extraction de règles basées sur les plongements ne gèrent que le premier type, c'est-
à-dire, chemin fermé (Figure 3.2(a)) et les trois autres types (Figures 3.2(b),3.2(c),3.2(d)) ne
sont pas gérés.

Nous nous concentrons sur les règles qui consistent en une relation de tête H et une séquence
<figure><img src="image_9.png" /><figcaption>FIGURE 3.2 – Différents types de chemins pour définir des règles de longueur 2. [Islam et al., 2022]</figcaption></figure>

de relations de corps $B_1, B_2, \dots, B_n$ sous la forme suivante :

$$B_1(e_0, e_1) \wedge B_2(e_1, e_2) \wedge \dots \wedge B_n(e_{n-1}, e_n) \rightarrow H(e_0, e_n)$$

où $e_i$ est une variable d'entité, $H$ est la relation tête/cible de $e_0$ à $e_n$ et $B_1, B_2, \dots, B_n$ sont la séquence des relations de corps. Dans le corps de la règle, $B_i(e_{i-1}, e_i)$ est soit une relation $(c'est-à-dire, (e_{i-1}, r_i, e_i))$ soit son inverse $(c'est-à-dire, (e_{i-1}, r_i^{-1}, e_i))$.

Un chemin simple est une séquence de triplets dans laquelle une entité commune apparaît entre deux triplets consécutifs sans cycle. Nous accordons plus d'importance aux chemins courts qu'aux longs. Nous calculons le score d'un chemin P comme le score moyen sur tous les triplets composant le chemin, pénalisé par la longueur du chemin. Nous définissons la fonction de score de chemin PS comme défini dans l'équation 3.5.

$$PS(P) = \frac{1}{l^{1+\alpha}} \sum_{i=1}^{l} f(h_i, r_i, t_i) \qquad (3.5)$$

où $f$ est la fonction de score de plongement, $l$ est la longueur du chemin, $\alpha$ est le facteur pénalisant et $0 \le \alpha \le 1$. $\alpha = 0$ signifie que nous considérons tous les chemins de la même manière quelle que soit leur longueur alors que des valeurs plus grandes donnent plus d'importance aux chemins plus courts. Nous supposons qu'un chemin avec un score élevé est un bon chemin par rapport au plongement en question.
Dans ce qui suit, nous décrivons la procédure d'extraction de règles qui commence par la génération de graphes et se poursuit par l'échantillonnage de triplets et la fouille de règles.

## 3.3.1 Génération d'un graphe bidirectionnel

Pour faciliter la recherche des chemins à utiliser dans les corps de règles, nous générons un graphe bidirectionnel $G$ à partir des triplets appris à partir du graphe de connaissances. Pour chaque triplet $(h, r, t) \in G$, on ajoute un triplet avec une relation inversée, c'est-à-dire, $G \leftarrow G \cup (t, r^{-1}, h)$ s'il n'y a pas de relation de $t$ à $h$. De cette façon, nous transformons le graphe bidirectionnel de sorte que pour chaque triplet, la queue soit accessible depuis la tête ainsi que la tête soit accessible depuis la queue. Cette transformation nous aide à extraire divers types de chemins.

## 3.3.2 Fouille de règles

Nous schématisons la procédure de fouille de règles pour une relation spécifique $r$ dans la Figure 3.3. Dans ce qui suit, nous décrivons les différentes étapes de la procédure.

<figure><img src="image_10.png" /><figcaption>FIGURE 3.3 – Fouille de règles pour une relation cible $r$. [Islam et al., 2022]</figcaption></figure>

### Étape 1 : Échantillonnage de triplets

Pour extraire des règles, nous sélectionnons aléatoirement un sous-ensemble de triplets de la relation cible $r$.

### Étape 2 : Fouille d'un ensemble de règle initial

La procédure initiale de fouille des règles pour une relation $r$ est illustrée dans la Figure 3.3 (en bleu).

#### — Étape 2.1 : Récupération d'un triplet
La procédure commence par la récupération du triplet arrivé (h, r, t). Notez qu’un seul triplet est extrait à la fois et que le triplet suivant est extrait après le traitement complet du triplet actuel.

### — Étape 2.2 : Extraction de chemins

Après avoir récupéré le triplet, les relations r de h à t et son inverse($r^{-1}$) (si elle existe) sont temporairement supprimées du graphe. Ensuite, un ensemble de chemins simples jusqu'à une longueur, MaxL de h à t sont extraits. Ici, MaxL est la longueur de corps maximale prédéfinie, ou simplement la longueur de règle maximale. Après avoir extrait l'ensemble de chemins, les relations supprimées entre h et t sont à nouveau ajoutées au graphe.

### — Étape 2.3 : Calcul des scores et des classements des chemins

Les scores de tous les chemins extraits sont calculés à l'aide de la fonction de score des chemins dans l'équation 3.5. Notez qu'un chemin peut contenir la relation inverse de la forme ($h_i, r_i^{-1}, t_i$). Dans ce cas, le score du triplet est calculé comme $f(t_i, r_i, h_i)$. Ce calcul nous permet d'inclure tous les cas de la Figure 3.2.

Les chemins sont ensuite classés par ordre décroissant de leur score. Un meilleur classement d'un chemin signifie une meilleure chance que le chemin génère une bonne règle.

### — Étape 2.4 : Définition des règles à partir des chemins

Nous définissons les chemins les mieux classés comme des supports solides pour le triplet actuel où k est un paramètre défini par l'utilisateur. Dans cette étape, un chemin est transformé en règle en remplaçant les entités de triplets par des variables. Si la tête et la queue d'un triplet ($h_i, r_i, t_i$) sont remplacées par les variables $e_{i-1}$ et $e_i$ alors le triplet est transformé en la relation de corps sous la forme $r_i(e_{i-1}, e_i)$. Une relation inverse ($h_i, r_i^{-1}, t_i$) est transformée sous la forme $r_i(e_i, e_{i-1})$.

### — Étape 2.5 : Mise à jour de l'ensemble de règles

Si une règle de haute qualité, *Rule*, n'existe pas dans l'ensemble initial de règles, *Rule_set* d'une relation, alors elle est ajoutée en initialisant sa structure comme suit :

$$ 
\begin{aligned}
\textit{Rule.count} &\leftarrow 1 \\
\textit{Rule.energy} &\leftarrow 1.0 + \gamma
\end{aligned}
 $$

La variable 'count' de la règle représente le nombre d'occurrences de la règle et la variable
d'énergie prend l'énergie complète et un taux de décroissance supplémentaire ($\gamma$) comme énergie initiale. La règle est ensuite ajoutée au jeu de règles initial, $Rule\_set$ c'est-à-dire, $Rule\_set \leftarrow Rule\_set \cup Rule$. Dans le cas où la règle Rule existe déjà dans le $Rule\_set$, alors son ordre ainsi que sa valeur d'énergie sont mises à jour comme suit :

$$Rule\_set[Rule].count \leftarrow Rule\_set[Rule].count + 1$$

$$Rule\_set[Rule].energy \leftarrow 1.0 + \gamma$$

## Étape 2.6 : Identification et suppression des règles bruyantes

Les règles qui ne sont pas utiles pour extraire des règles de haute qualité pour une relation sont identifiées comme bruyantes et supprimées immédiatement. Cette suppression réduit la consommation inutile de mémoire et de temps de calcul. Dans notre méthode, une règle relève de l'une des trois lois.

- Une règle 'potentielle' a une énergie positive et ordre égal à 1,

- une règle "stable" a un ordre supérieur à 1, et

- une règle bruitée a un ordre égal à 1 et une énergie négative.

Une règle 'potentielle' peut devenir 'stable' ou 'bruyante' plus tard. A chaque fois qu'un triplet est extrait de l'ensemble de triplets échantillonné, l'énergie de chaque règle potentielle, Rule du $Rule\_set$ est diminuée du taux de décroissance $\gamma$ comme suit :

$$Rule\_set[Rule].energy \leftarrow Rule\_set[Rule].energy - \gamma$$

Habituellement, le taux de décroissance est $0 < \gamma < 1$. Une petite valeur de $\gamma$ signifie que les règles potentielles seront vivantes plus longtemps avant de mourir si elles ne durent pas longtemps. Généralement, le nombre de chemins entre deux entités est élevé dans un graphe de connaissances dense et faible dans un graphe éparse. Par conséquent, nous soutenons que la possibilité de présence de règles bruitées pour une relation est élevée dans un graphe dense et faible dans un graphe éparse. Toutes les règles potentielles avec des énergies négatives sont identifiées comme des règles bruyantes et immédiatement supprimées de la mémoire.

## Étape 3 : Extraction finale de l'ensemble de règles
Les processus de fouille de règles ci-dessus (étapes 2.1 à 2.6) sont répétés jusqu'à ce que tous les triplets de l'ensemble de triplets échantillonné soient traités. En fin de traitement, le *Rule_set* contient des règles 'stables' et quelques règles 'potentielles'. Le jeu de règles final ne contient que les règles "stables".

L'algorithme 2 décrit les étapes d'extraction de l'ensemble de chemins classés et l'algorithme 3 décrit les étapes de fouille de l'ensemble de règles en fonction de l'ensemble de chemins extraits.

<caption>**Algorithm 2 Extract_paths : Extracting paths for a given triple**</caption>

1 G ← G-{h,r,t} // temporarily remove the relation from h to t
2 Path_Scores ← ∅ Ranks ← ∅ Paths = all_simple_paths (G, source = h, target = t, cutoff = MaxL) 4 /* extract all simple paths from h to t with maximum path length, MaxL */
3 foreach P ∈ Paths do
4 Score_P ← Score of the path, P // using equation 3.5
5 Path_Scores ← Path_Scores ∪ Score_P
6 Ranks ← Ranks of paths based on Path_Scores // in decreasing order of path scores
7 G ← G ∪ {h,r,t}

<caption>**Algorithm 3 Learn_rule : Learning rules for a relation**</caption>

8 $T'_r \leftarrow$ Randomly sample ($|T_r| * \beta$) triples from $T_r$ **foreach** $(h,r,t) \in T'_r$ **do**
9 &nbsp;&nbsp;&nbsp;&nbsp;Paths, Ranks =Extract_paths(G,(h,r,t), MaxL) // Call Algorithm 2 to extract paths
10 &nbsp;&nbsp;&nbsp;&nbsp;/* If a path exists then update its info, otherwise add the path to PathMetaInfo if it is ranked in
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;top-k */
12 &nbsp;&nbsp;&nbsp;&nbsp;**foreach** $P \in$ Paths **do**
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rule=Transform_path_to_rule(P) // replace entities with literals
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if Rule $\in$ Rule_set then
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rule_set[Rule].Count $\leftarrow$ Rule_set[Rule].Count + 1 // increment counter
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rule_set[Rule].Energy $\leftarrow$ 1 + $\gamma$ // reset energy to full and additional $\gamma$
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/* add a new rule */
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if Ranks[Rule]$\le$top-k then
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rule.Count $\leftarrow$ 1 Rule.Energy $\leftarrow$ 1 + $\gamma$ Rule_set[Rule]$\leftarrow$ Rule_set $\cup$ Rule
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/* Identify the noisy rules */
22 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**foreach** Rule $\in$ Rule_set **do**
23 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rule.Energy$\leftarrow$Rule.Energy - $\gamma$ if Rule.Energy $\le$ 0 & Rule.Count$\le$ 1 then
24 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rule_set=Rule_set - Rule // remove the noisy rule
25 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;/* generate the final rule set by removing potential rules */
26 &nbsp;&nbsp;&nbsp;&nbsp;**foreach** Rule $\in$ Rule_set **do**
27 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if Rule.Count$\le$ 1 then
28 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Rule_set=Rule_set - Rule // remove the potential rule

**Input:** Target relation (r), Bidirectional Knowledge graph (G), Triple set ($T_r$) with r, Decay rate ($\gamma$), Sampling rate ($\beta$), Top-k, maximum path length (MaxL)
**Output:** *Rule_set*
### 3.3.3 Abduction pour la prédiction de lien explicable

Une fois les règles générées, elles peuvent être exploitées pour fournir des explications plausible à l'appui de certaines prédictions. Nous proposons une procédure inspirée du raisonnement abductif sur les règles pour déduire la ou les meilleures explications d'une prédiction. En effet, le raisonnement abductif utilisant une règle *body* → *head* nous permet de déduire (ou au moins de supposer) que le corps est satisfait à chaque fois que la tête est observée. Donc étant donné une prédiction comme une observation, on cherche des règles dont la tête correspond à la prédiction. Chaque instanciation de règle (utilisant les chemins de graphe bidirectionnels) constitue alors une explication plausible de la prédiction. Ainsi, nous avons un moyen de classer davantage les prédictions top-k en fonction de leur explicabilité [Islam et al., 2022].

## 3.4 Repositionnement de médicaments explicable avec évaluation au niveau moléculaire pour COVID-19

Dans un contexte de graphe de connaissances, le repositionnement des médicaments est formulé comme une tâche de prédiction de lien où la probabilité d'une relation *Treat* est calculée à partir d'un composé approuvé (tête) vers une maladie (queue) c'est-à-dire, calculer la probabilité d'un triplet (*Composé*, *Treat*, *Maladie*). Sur la base de cette formulation, il existe plusieurs approches de repositionnement de médicaments dans la littérature. Peu d'entre elles sont génériques [Mohamed et al., 2020, Zhu et al., 2022a] et les autres sont spécifiques à certaines maladies [Gao et al., 2022, Sosa et al., 2019, Zhu et al., 2020, Ioannidis et al., 2020].

La pandémie de COVID-19, causée par le syndrome respiratoire aigu sévère (SARS-CoV-2), a coûté la vie à près de 6 millions de personnes en 2020 et 2021, et elle continue toujours. À la connaissance de la communauté scientifique et médicale, aucun médicament spécifique n'est disponible à ce jour contre le COVID-19. Il existe un certain nombre d'études de repositionnement de médicaments pour le COVID-19 [Ioannidis et al., 2020, Zhang et al., 2021, Yan et al., 2021a, Kanatsoulis and Sidiropoulos, 2021, Choudhary et al., 2021].

La plupart des approches utilisent des méthodes traditionnelles de plongement de graphes de connaissances pour apprendre les plongements d'entités et de relations dans des graphes
de connaissances biologiques centrés sur le COVID-19, comme le graphe "Drug Repurposing Knowledge Graph" (DRKG) [Ioannidis et al., 2020], puis utilisent les plongements dans la tâche de repositionnement de médicaments. L'évaluation des prédictions par rapport aux médicaments en cours d'essai pour le COVID-19 est le seul moyen d'évaluer l'efficacité de ces approches.

Dans ce travail, nous proposons une étude pour le repositionnement des médicaments pour la maladie COVID-19 tout en expliquant les résultats de l'étude. L'architecture de la méthode proposée est illustrée dans la Figure 3.4 [Islam et al., 2023]. Nous commençons par collecter et nettoyer le graphe DRKG. Ensuite, nous proposons une nouvelle approche pour générer un ensemble de plongements de haute qualité du graphe DRKG en utilisant trois méthodes de plongement traditionnelles et la méthode d'analyse en composantes principales (ACP). Les plongements sont utilisées pour former un modèle de prédiction basé sur un réseau neuronal profond (DNN). Le modèle formé est utilisé pour prédire la probabilité de tous les triplets (Composé, Treat, COVID-19) non observés où COVID-19 est représenté par 27 protéines associées au SARS-CoV-2. Les triplets sont ensuite classés par ordre décroissant de leurs valeurs de probabilité et les 100 meilleurs composés sont prédits comme composés potentiels pour le COVID-19. Les 100 meilleures prédictions sont évaluées sur la base de deux groupes de méthodes : (1) l'appariement croisé avec des médicaments en cours d'essai pour le COVID-19 et (2) l'évaluation moléculaire basée sur les structures des composés et des protéines. Outre ces évaluations, nous apprenons des règles de haute qualité au sein du DRKG et fournissons des explications possibles pour les prédictions sélectionnées basées sur nos méthodes de fouille et d'explication de règles décrites dans la Section 3.3).

Cette étude se distingue des approches de l'état de l'art sur trois points majeurs. Premièrement, les études existantes dépendent d'un seul modèle de plongement de graphes de connaissances ignorant le fait qu'un seul modèle ne peut apprendre qu'un bon plongement de certains types de relations [Rossi et al., 2021, Wang et al., 2021]. Au contraire, nous proposons une approche d'ensemble combinant de multiples plongements afin de plonger différents aspects complémentaires des relations du graphe de connaissance. Deuxièmement, les approches existantes évaluent uniquement leurs prédictions par rapport aux médicaments en cours d'essai et ne fournissent aucune évaluation moléculaire de leurs prédictions. Nous fournissons une évaluation moléculaire de nos prédictions par comparaison avec des ligands connus des cibles COVID-19. Enfin,
<figure><img src="image_11.png" /><figcaption>FIGURE 3.4 – Flux de travail global de l'étude ; les principales étapes sont numérotées. Étape 1 (boîte jaune) ; nettoyage d'un graphe de connaissances pour le repositionnement des médicaments centré sur le COVID-19 (DRKG). Étape 2 (boîte grise) : apprentissage d'ensembles de plongements de haute qualité. Étape 3 (boîte bleue) : prédire et classer les médicaments potentiels pour les cibles de la maladie COVID-19. Étape 4 (boîte violette) : évaluation des 100 meilleurs composés sur la base du croisement avec des médicaments en cours d'essai (panneau supérieur) et évaluation moléculaire des composés ciblant la protéine nsp13 du SRAS-CoV-2 (panneaux inférieurs). Étape 5a (encadré vert clair) : fouille d'un ensemble de règles d'explication à partir de DRKG. Étape 5b (encadré vert foncé) : extraction des chemins explicatifs instanciant les règles pour des paires d'intérêt données (Composés, Maladie). [Islam et al., 2023]</figcaption></figure>

alors que les explications des prédictions dérivées du KG manquent dans la plupart des approches existantes, nous fournissons des explications basées sur des règles extraites du graphe de connaissance et cela contribue à améliorer la fiabilité de nos prédictions.
## 3.5 Résultats

### 3.5.1 Évaluation de l'échantillonnage négatif SNS

Pour évaluer l'efficacité de l'échantillonnage SNS, nous connectons SNS à un modèle de plongement géométrique de graphes de connaissances. Les modèles de plongement géométrique sont généralement classés en deux catégories principales : (1) les modèles translationnels (translational models) et (2) les modèles de correspondance sémantique (semantic matching models) [Wang et al., 2017]. Les modèles translationnels considèrent chaque relation comme une translation dans l'espace de représentation : ajouter une relation à la tête donne une position proche de la queue [Bordes et al., 2013]. D'autre part, les modèles de correspondance sémantique définissent la plausibilité d'un triplet en faisant correspondre les représentations des entités et des relations incarnées dans leurs plongements [Wang et al., 2017]. En ce qui concerne l'évaluation de la méthode SNS, nous avons choisi TransH [Wang et al., 2014] pour représenter les modèles translationnels et DistMult [Yang et al., 2015] pour représenter le modèle de correspondance sémantique car ce sont des bases de référence populaires pour la tâche de prédiction de lien dans les graphes de connaissances. Chacun des modèles est évalué en combinaison avec trois méthodes d'échantillonnage (random-uniform, modèle basé sur les GANs, self-adversarial et NSCaching) et avec la méthode SNS. Pour la méthode basée sur les GANs, nous choisissons KBGAN car il s'agit du seul échantillonnage basé sur le GAN dont la mise en oeuvre est accessible au public.

Dans nos expérimentations, nous utilisons cinq jeux de données/graphes de connaissances de référence largement utilisés : FB15K, FB15K-237, WN18, WN18RR, YAGO3-10 pour la tâche de prédiction de lien [Bordes et al., 2013, Cai and Wang, 2018, Zhang et al., 2019]. WN18, WN18RR ont été dérivés de WordNet, FB15K, FB15K-237 ont été extraits de Freebase et YAGO3-10 a été extrait des connaissances YAGO. Le jeu de données Family est un petit graphe de connaissances, où les relations sont les relations familiales entre les personnes [Kok and Domingos, 2007, Sadeghian et al., 2019].

Nous construisons les modèles de KGE à partir de zéro pour chacune des méthodes d'échantillonnage, aléatoire-uniforme, KBGAN, NSCaching, SNS. Pour le paramétrage, nous suivons les recommandations de l'article original ([Zhang et al., 2019] pour NSCaching, [Cai and Wang, 2018] pour KBGAN). Les performances de la méthode SNS sont présen-
tées dans le tableau 3.1. Compte tenu du modèle translationnel (TransH), la méthode d'échantillonnage SNS proposée montre sans aucun doute les meilleures métriques de prédiction parmi toutes les méthodes d'échantillonnage négatives par rapport à la plupart des métriques de prédiction dans la plupart des ensembles de données KG. Dans les ensembles de données WordNet (WN18RR, WN18), NSCaching est la deuxième meilleure méthode et les performances sont améliorées de 2 à 5% avec l'échantillonnage SNS en tenant compte des métriques Hit@k (voir Section 1.3.2) lorsqu'elles sont utilisées avec TransH. Nous trouvons les meilleurs résultats de l'échantillonnage SNS pour l'ensemble de données FB15K où les scores Hit@k sont améliorés de 5 à 8% par rapport à la deuxième meilleure méthode d'échantillonnage NSCaching. Pour les deux autres ensembles de données, SNS reste également le meilleur ou le deuxième meilleur en ce qui concerne presque toutes les métriques. Lorsque les méthodes d'échantillonnage sont utilisées avec le modèle *DistMult*, les scores hit@10 et hit@3 chutent dans tous les ensembles de données. L'entrainement du modèle avec plus d'époques pourrait améliorer les métriques. Cependant, notre intention n'est pas de comparer différents modèles de prédiction, mais plutôt différentes méthodes d'échantillonnage.

### 3.5.2 Évaluation de l'explicabilité

Nous calculons les performances de prédiction de notre méthode de fouille de règles basée sur les plongements appris par notre méthode SNS et nos stratégies d'échantillonnage aléatoire. Le tableau 3.2 présente les scores de rappel avec leurs nombres moyens, minimum et maximum pour les jeux de données Family, WN18RR et FB15K-237. Le tableau 3.3 répertorie les scores des métriques de qualité avec leurs nombres moyens, minimum et maximum pour les mêmes ensembles de données.

Dans l'ensemble, notre méthode de fouille de règles génère plus de règles lorsque les plongements sont générés à l'aide de *DistMult* et avec SNS comme méthode d'échantillonnage négatif. Mais nous ne voyons aucune différence significative entre les scores de performance des ensembles de règles générées. Nous voyons que le nombre moyen de règles extraites par relation est le plus élevé pour les graphes denses FB15K-237 et le plus bas pour les graphes éparses WN18RR. Ceci est attendu car une valeur élevée de degré moyen des nœuds d'un graphe conduit à générer plus de chemins entre une paire de nœuds et donc plus de règles pour décrire la relation entre la
<table><caption>TABLE 3.1 – Résultats de prédiction de liens (LP) : MRR et Hit@z de différentes méthodes d'échantillonnage négatif (NS) avec différentes méthodes de KGE. Random et Self-Adv représentent respectivement les méthodes d'échantillonnage aléatoire-uniforme et "self-adversarial". Les meilleures et deuxièmes meilleures métriques pour chaque méthode d'échantillonnage avec chaque méthode de plongement sont marquées en gras et soulignées, respectivement. [Islam et al., 2022]</caption><thead><tr><th rowspan="2">KGE model</th><th rowspan="2">NS method</th><th colspan="4">WN18RR</th><th colspan="4">WN18</th></tr><tr><th>MRR</th><th>hit@10</th><th>hit@3</th><th>hit@1</th><th>MRR</th><th>hit@10</th><th>hit@3</th><th>hit@1</th></tr></thead><tbody><tr><td rowspan="5">TransH</td><td>Random</td><td>0.1520</td><td>32.27</td><td>23.72</td><td>0.11</td><td>0.3199</td><td>79.43</td><td>64.25</td><td>11.85</td></tr><tr><td>NSCaching</td><td>0.1713</td><td>40.68</td><td>31.43</td><td>0.93</td><td>0.4171</td><td>88.65</td><td>74.05</td><td>17.48</td></tr><tr><td>KBGAN</td><td>0.1708</td><td>40.08</td><td>29.35</td><td>0.10</td><td>0.4183</td><td>87.34</td><td>73.67</td><td>18.09</td></tr><tr><td>Self-Adv</td><td>0.1709</td><td>41.18</td><td>31.16</td><td>0.89</td><td>0.4191</td><td>89.48</td><td>75.84</td><td>7.08</td></tr><tr><td>SNS</td><td><strong>0.1852</strong></td><td><strong>43.04</strong></td><td><strong>33.82</strong></td><td><strong>1.80</strong></td><td><strong>0.448</strong></td><td><strong>91.47</strong></td><td><strong>79.30</strong></td><td><strong>19.28</strong></td></tr><tr><td rowspan="5">DistMult</td><td>Random</td><td>0.1918</td><td>32.16</td><td>23.88</td><td>14.22</td><td>0.3453</td><td>52.82</td><td>37.33</td><td>25.75</td></tr><tr><td>NSCaching</td><td>0.2262</td><td>37.37</td><td><strong>29.11</strong></td><td><strong>17.84</strong></td><td>0.3772</td><td>56.85</td><td><strong>42.18</strong></td><td>29.04</td></tr><tr><td>KBGAN</td><td>0.2285</td><td>33.42</td><td>27.23</td><td>17.34</td><td>0.3791</td><td>57.28</td><td>41.97</td><td>28.39</td></tr><tr><td>Self-Adv</td><td>0.2279</td><td>36.23</td><td>26.34</td><td>17.05</td><td><strong>0.3940</strong></td><td><strong>58.43</strong></td><td>41.31</td><td>31.29</td></tr><tr><td>SNS</td><td><strong>0.2333</strong></td><td><strong>37.83</strong></td><td>25.12</td><td><strong>18.49</strong></td><td>0.3931</td><td>56.46</td><td>42.13</td><td><strong>31.38</strong></td></tr><tr><td rowspan="5">TransH</td><td>Random</td><td>0.1988</td><td>36.68</td><td>22.50</td><td>11.50</td><td>0.3115</td><td>52.88</td><td>36.68</td><td>19.58</td></tr><tr><td>NSCaching</td><td>0.2476</td><td>40.39</td><td>26.59</td><td><strong>17.33</strong></td><td>0.3926</td><td>61.22</td><td>44.99</td><td>25.50</td></tr><tr><td>KBGAN</td><td>0.2162</td><td>40.58</td><td>23.52</td><td><strong>15.23</strong></td><td>0.3228</td><td>53.67</td><td>38.34</td><td>20.52</td></tr><tr><td>Self-Adv</td><td>0.2350</td><td>41.01</td><td>26.49</td><td>14.73</td><td>0.3883</td><td>61.09</td><td>44.05</td><td>25.74</td></tr><tr><td>SNS</td><td><strong>0.2514</strong></td><td><strong>42.90</strong></td><td><strong>29.44</strong></td><td>15.18</td><td><strong>0.4360</strong></td><td><strong>66.72</strong></td><td><strong>51.52</strong></td><td><strong>30.58</strong></td></tr><tr><td rowspan="5">DistMult</td><td>Random</td><td>0.1918</td><td>31.82</td><td>20.71</td><td>12.96</td><td>0.2188</td><td>33.25</td><td>21.84</td><td>12.95</td></tr><tr><td>NSCaching</td><td>0.2205</td><td>34.87</td><td>25.69</td><td>15.72</td><td>0.2327</td><td>39.89</td><td>27.41</td><td>16.19</td></tr><tr><td>KBGAN</td><td>0.2282</td><td>36.23</td><td><strong>27.23</strong></td><td>13.02</td><td>0.2203</td><td>35.54</td><td>23.12</td><td>15.92</td></tr><tr><td>Self-Adv</td><td>0.2400</td><td>37.09</td><td>25.82</td><td>17.34</td><td>0.2493</td><td>39.80</td><td>28.38</td><td>18.53</td></tr><tr><td>SNS</td><td><strong>0.2471</strong></td><td><strong>38.18</strong></td><td>26.97</td><td><strong>17.80</strong></td><td><strong>0.2937</strong></td><td><strong>45.62</strong></td><td><strong>32.66</strong></td><td><strong>20.79</strong></td></tr><tr><td rowspan="5">TransH</td><td>Random</td><td>0.0850</td><td>18.96</td><td>9.05</td><td>1.24</td><td>0.3164</td><td>88.77</td><td>48.67</td><td>3.43</td></tr><tr><td>KBGAN</td><td>0.1467</td><td>26.08</td><td>16.03</td><td>8.34</td><td><strong>0.3742</strong></td><td>90.21</td><td><strong>57.12</strong></td><td><strong>8.63</strong></td></tr><tr><td>Self-Adv</td><td>0.1443</td><td>26.46</td><td><strong>17.34</strong></td><td><strong>9.92</strong></td><td>0.3510</td><td>89.58</td><td>56.36</td><td>8.08</td></tr><tr><td>NSCaching</td><td>0.1431</td><td><strong>26.76</strong></td><td>15.97</td><td>7.49</td><td>0.3434</td><td>90.34</td><td>55.04</td><td>4.65</td></tr><tr><td>SNS</td><td><strong>0.1488</strong></td><td><strong>26.72</strong></td><td>16.23</td><td>8.87</td><td><strong>0.4146</strong></td><td><strong>92.97</strong></td><td><strong>62.39</strong></td><td><strong>13.12</strong></td></tr><tr><td rowspan="5">DistMult</td><td>Random</td><td>0.0533</td><td>10.59</td><td>5.44</td><td>2.35</td><td>0.5002</td><td>77.36</td><td>60.14</td><td>37.45</td></tr><tr><td>KBGAN</td><td>0.0712</td><td>13.98</td><td>7.79</td><td>3.19</td><td>0.5120</td><td>78.01</td><td>60.75</td><td>38.01</td></tr><tr><td>Self-Adv</td><td>0.0868</td><td>16.04</td><td>8.74</td><td>5.07</td><td>0.5122</td><td>78.59</td><td>60.95</td><td><strong>38.33</strong></td></tr><tr><td>NSCaching</td><td><strong>0.0875</strong></td><td>14.22</td><td><strong>8.86</strong></td><td><strong>5.64</strong></td><td><strong>0.5274</strong></td><td>78.55</td><td><strong>61.34</strong></td><td>38.07</td></tr><tr><td>SNS</td><td>0.0804</td><td><strong>16.72</strong></td><td>8.39</td><td>4.98</td><td><strong>0.5190</strong></td><td><strong>79.32</strong></td><td>61.02</td><td>37.98</td></tr></tbody></table>

paire de nœuds. Le nombre élevé de règles pour les jeux de données Family et FB15K-237 donne des scores de rappel élevés dans ces deux graphes de connaissances. En regardant les scores de rappel minimum, nous voyons que les jeux de données, à l'exception de Family, donnent un score minimum de 0. En étudiant le rappel par rapport aux relations, nous constatons que la qualité des règles extraites pour une relation avec un faible nombre d'ensembles d'apprentissage est très faible et dans certains cas, aucune règle n'est générée pour quelques relations de ce type. Cette situation affecte les scores de performance ainsi que la qualité globale de l'ensemble de règles d'une relation. Dans le tableau 3.3, nous voyons les pires métriques de qualité des règles pour WN18RR. Le degré moyen de WN18RR est faible, ce qui réduit le nombre de chemins entre deux entités pour générer des règles. C'est la raison la plus probable est que notre méthode extrait les
règles de longueur 2 de faible qualité pour WN18RR.

<table><caption>TABLE 3.2 – Métriques de performance des règles : #Rules représente le nombre total de règles extraites de longueur 2. La métrique de rappel est donnée dans le format (score minimum, score moyen, score maximum) sont calculés sur toutes les relations dans un graphe de connaissances. 'DistMult' est testée avec deux méthodes d'échantillonnage différentes : SNS et la méthode aléatoire (Random). [Islam et al., 2022]</caption><thead><tr><th rowspan="2">KGs</th><th colspan="2">Random</th><th colspan="2">SNS</th></tr><tr><th>#Rule</th><th>Recall (min.,avg., max., std)</th><th>#Rules</th><th>Recall (min.,avg., max.,std)</th></tr></thead><tbody><tr><td>Family</td><td>235</td><td>(0.569, 0.908, 1.0, 0.157)</td><td>242</td><td>(0.586, 0.910, 1.0, 0.150)</td></tr><tr><td>WN18RR</td><td>69</td><td>(0.0, 0.184, 0.487, 0.162)</td><td>76</td><td>(0.0, 0.185, 0.487, 0.164)</td></tr><tr><td>FB15K-237</td><td>8490</td><td>(0.0, 0.684, 1.0, , 0.262)</td><td>8559</td><td>(0.0, 0.689, 1.0, 0.258)</td></tr></tbody></table>

<table><caption>TABLE 3.3 – Scores de qualité des règles : HC et SC désignent respectivement la couverture de la tête et les mesures de confiance standard. Les métriques sont données au format (score minimum, score moyen, score maximum) sont calculées sur toutes les relations d'un graphe de connaissances. 'DistMult' est testée avec deux méthodes d'échantillonnage différentes : SNS, aléatoire (Random). [Islam et al., 2022]</caption><thead><tr><th rowspan="2">KGs</th><th colspan="2">Random</th><th colspan="2">SNS</th></tr><tr><th>HC(min., avg., max.)</th><th>SC(min., avg., max.)</th><th>HC(min., avg., max.)</th><th>SC(min., avg., max.)</th></tr></thead><tbody><tr><td>Family</td><td>(0.135, 0.208, 0.241)</td><td>(0.325, 0.523, 0.674)</td><td>(0.119, 0.205, 0.254)</td><td>(0.285, 0.531, 0.695)</td></tr><tr><td>WN18RR</td><td>(0.0, 0.0337, 0.098)</td><td>(0.0, 0.0569, 0.179)</td><td>(0.0, 0.0311, 0.0869)</td><td>(0.0, 0.0689, 0.1433)</td></tr><tr><td>FB15K-237</td><td>(0.0, 0.176, 0.969)</td><td>(0.0, 0.196, 0.905)</td><td>(0.0, 0.175, 0.969)</td><td>(0.0, 0.199, 0.905)</td></tr></tbody></table>

Dans la liste de nos priorités, nous cherchons à étudier comment la qualité des plongements affecte la qualité de l'ensemble de règles extraites ainsi que les performances de prédiction dans le jeu de données WN18RR. Nous avons choisi WN18RR, car les métriques de prédiction globales et les métriques de qualité des règles de ce jeu de données sont les plus basses. Nous sélectionnons les règles de longueur-2 extraites sur la base du plongement généré par *DistMult* avec l'échantillonnage SNS. Nous voyons que les résultats sont presque cohérents avec les résultats de prédiction par la méthode basée sur les plongements présentés dans le tableau 3.4. Nous voyons qu'aucune règle n'est extraite pour la relation *similar_to* car la relation a un nombre insuffisant de triplets dans l'ensemble d'apprentissage.

Pour voir comment les performances de fouille de règles changent avec différents pourcentages de règles, nous échantillonnons toutes les règles de longueur-2, les top-75%, les top-50%, les top-25% et les top-10% pour chaque relation dans le graphe Family (voir Figure 3.5). Les règles
<table><caption>TABLE 3.4 – Performances (relation-wise) des règles de longueur 2 extraites dans le jeu de données WN18RR : les plongements sont appris par *DistMult* avec un échantillonnage SNS. Les paramètres des méthodes de fouille de règles sont définis sur les valeurs par défaut, sauf que la longueur maximale de la règle est fixée à 2. Les relations avec des scores de rappel supérieurs à la moyenne (0,184) sont indiquées en gras. [Islam et al., 2022]</caption><thead><tr><th>Relations</th><th>#Rule</th><th>Recall</th><th>HC</th><th>SC</th></tr></thead><tbody><tr><td>hypernym</td><td>9</td><td>0.089</td><td>0.045</td><td>0.009</td></tr><tr><td>derivationally <u>related</u> <u>form</u></td><td>12</td><td>0.224</td><td>0.087</td><td>0.019</td></tr><tr><td>instance <u>hypernym</u></td><td>5</td><td>0.197</td><td>0.017</td><td>0.028</td></tr><tr><td>also <u>see</u></td><td>7</td><td>0.214</td><td>0.048</td><td>0.040</td></tr><tr><td>member <u>meronym</u></td><td>6</td><td>0.099</td><td>0.013</td><td>0.016</td></tr><tr><td>synset <u>domain</u> <u>topic</u> <u>of</u></td><td>15</td><td>0.447</td><td>0.143</td><td>0.032</td></tr><tr><td>has <u>part</u></td><td>10</td><td>0.238</td><td>0.057</td><td>0.023</td></tr><tr><td>member <u>of</u> <u>domain</u> <u>usage</u></td><td>2</td><td>0.042</td><td>0.131</td><td>0.043</td></tr><tr><td>member <u>of</u> <u>domain</u> <u>region</u></td><td>2</td><td>0.00</td><td>0.142</td><td>0.015</td></tr><tr><td>verb <u>group</u></td><td>8</td><td>0.487</td><td>0.006</td><td>0.087</td></tr><tr><td>similar <u>to</u></td><td>0</td><td>0.000</td><td>0.00</td><td>0.00</td></tr></tbody></table>

d'une relation sont classées par ordre décroissant de leurs valeurs de support. Comme les règles de rang inférieur ne sont pas prises en compte, les règles de déclenchement de quelques triplets seront manquantes. En conséquence, on observe sur la Figure 3.5(a) que les scores de rappel pour les deux méthodes d'échantillonnage diminuent quand le nombre de règles diminue. En revanche, comme les règles de faible qualité sont supprimées, les scores moyens de qualité des règles s'améliorent (voir Figure 3.5(b)).

<figure><img src="image_12.png" /><figcaption>FIGURE 3.5 – Changement des performances et de la qualité des prédictions avec différents pourcentages de règles extraites de longueur 2 dans le graphe Family. [Islam et al., 2022]</figcaption></figure>

Dans le tableau 3.5, nous tabulons les 5 règles extraites les mieux classées pour la relation "Father" dans le graphe Family. En examinant la couverture de la tête et les scores de confiance
standard, nous constatons que notre méthode est capable de calculer de meilleurs classements pour les règles de meilleure qualité.

<table><caption>TABLE 3.5 – Top-5 des règles de longueur-3 pour la relation 'père' : les rangs sont calculés dans l'ordre décroissant des valeurs de support des règles. [Islam et al., 2022]</caption><thead><tr><td>Rank</td><td>Rules</td><td>HC</td><td>SC</td></tr></thead><tbody><tr><td>1</td><td>husband(A, B) ∧ mother(B, C) – > father(A, C)</td><td>0.765</td><td>0.882</td></tr><tr><td>2</td><td>father(A, B) ∧ brother(B, C) – > father(A, C)</td><td>0.599</td><td>0.407</td></tr><tr><td>3</td><td>father(A, B) ∧ son(B, C) ∧ mother(C, D) – > father(A, D)</td><td>0.550</td><td>0.298</td></tr><tr><td>4</td><td>husband(A, B) ∧ mother(B, C) ∧ brother(C, D) – > father(A, D)</td><td>0.546</td><td>0.386</td></tr><tr><td>5</td><td>father(A, B) ∧ sister(B, C) – > father(A, C)</td><td>0.524</td><td>0.420</td></tr></tbody></table>

### 3.5.3 Évaluation de la prédiction de médicaments pour le COVID-19

Le modèle de prédiction que nous avons proposé a été entraîné avec un ensemble de 261,080 paires d'entraînement de type (Composé, Maladie) et validé sur 5,800 paires de test. Nous trouvons une erreur quadratique moyenne (MSE ou Mean Squared Error) de 0,037 sur l'ensemble de test pour le modèle de prédiction formé. Le modèle formé est ensuite utilisé pour calculer les rangs des composés candidats en fonction de leurs valeurs de probabilité par rapport aux entités de la maladie COVID-19. Il est important de mentionner que les 100 meilleures prédicitions ne correspondent pas à une cible unique mais plutôt à plusieurs cibles de la maladie COVID-19. Pour des raisons de simplicité, nous ne fournissons que les 20 composés les plus prédits dans le tableau 3.6. Nous fournissons également la meilleure cible de maladie pour chaque composé. Nous constatons que les classements des composés en cours d'essai pour le COVID-19 sont sensiblement améliorés par rapport aux approches de pointe (voir Tableau 3.6).

Pour évaluer l'efficacité de notre approche proposée de repositionnement des médicaments, il est important d'évaluer nos prédictions par rapport aux médicaments recommandés ou en cours d'essai. Nous effectuons deux types d'évaluation pour nos 100 composés les mieux classés : le croisement avec des médicaments en cours d'essai pour le COVID-19 et des évaluations moléculaires (uniquement pour la cible de la maladie SARS-CoV-2-nsp13).
## Croisement avec des médicaments en cours d'essai

Lorsque nous avons croisé les 100 principaux composés avec les 31 composés en cours d'essai pour le COVID-19 [Islam et al., 2023], nous constatons que les 10 composés les mieux classés sont en fait des composés à l'essai pour le COVID-19 (voir Tableau 3.6). Nous trouvons 10/31 médicaments en cours d'essai dans les 100 meilleures prédictions de notre approche, ce qui est remarquable par rapport à la plupart des approches existantes.

<table><caption>TABLE 3.6 – Top 20 des médicaments classés : les composés en cours d'essai sont surlignés en bleu, - représente l'indisponibilité du rang d'un médicament, * met en évidence les médicaments en cours d'essai trouvés uniquement par notre approche, les cinq dernières colonnes donnent le rang ou la prédiction (✓) de composés par différentes approches. [Islam et al., 2023]</caption><thead><tr><th>Compound</th><th>Disease target</th><th>Our approach</th><th>Tex-Graph|Kanatsoulis and Sidiroopoulos, 2021</th><th>TransE-DRKG|Ioannidis et al., 2020</th><th>ENSIGN|Leggas et al., 2021</th><th>PERM|Choudhary et al., 2021</th></tr></thead><tbody><tr><td>Dexamethasone</td><td>SARS-CoV-2-nsp6</td><td>1</td><td>1</td><td>4</td><td>✓</td><td>✓</td></tr><tr><td>Methylprednisolone</td><td>SARS-CoV-2-nsp6</td><td>2</td><td>6</td><td>16</td><td>✓</td><td>-</td></tr><tr><td>Rizolitimib*</td><td>SARS-CoV-2-nsp13</td><td>3</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Colchicine</td><td>SARS-CoV-2-nsp6</td><td>4</td><td>48</td><td>8</td><td>-</td><td>-</td></tr><tr><td>Thalidomide</td><td>SARS-CoV-2-nsp5_C145A</td><td>5</td><td>18</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Chloroquine</td><td>SARS-CoV-2-nsp5_C145A</td><td>6</td><td>68</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Azithromycin</td><td>SARS-CoV-2-nsp6</td><td>7</td><td>13</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Leucartin</td><td>SARS-CoV-2-nsp13</td><td>8</td><td>41</td><td>-</td><td>✓</td><td>-</td></tr><tr><td>Baricitinib*</td><td>SARS-CoV-2-nsp5_C145A</td><td>9</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Hydroxychloroquine</td><td>SARS-CoV-2-nsp5_C145A</td><td>10</td><td>47</td><td>-</td><td>-</td><td>✓</td></tr><tr><td>Protirelin (DB09421)</td><td>SARS-CoV-2-nsp13</td><td>11</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Telavancin (DB06402)</td><td>SARS-CoV-2-nsp13</td><td>12</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Propiomazine (DB00777)</td><td>SARS-CoV-2-nsp14</td><td>13</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Hydroxyzine (DB00557)</td><td>SARS-CoV-2-nsp13</td><td>14</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Indinavir (DB00224)</td><td>SARS-CoV-2-nsp5_C145A</td><td>15</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Naficillin (DB00607)</td><td>SARS-CoV-2-nsp5_C145A</td><td>16</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Bifonazole (DB04794)</td><td>SARS-CoV-2-nsp13</td><td>17</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Obeticholic acid (DB05990)</td><td>SARS-CoV-2-nsp13</td><td>18</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Mechizine (DB00737)</td><td>SARS-CoV-2-nsp13</td><td>19</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Lovastatin (DB00227)</td><td>SARS-CoV-2-nsp6</td><td>20</td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>

Le plus grand nombre de composés (40) dans le top 100 correspond à la cible SARS-CoV-2-nsp13. Parmi ces 40 composés, 2 sont en essai et 38 sont nouveaux. Nous avons choisi de concentrer nos évaluations moléculaires sur ces nouveaux composés.

## Évaluation moléculaire de composés pour SARS-CoV-2-nsp13

Pour les évaluations moléculaires, nous comparons nos 38 composés prédits avec 86 composés connus pour se lier à la cible SARS-CoV-2-nsp13 (38 de la littérature et 48 de la base de données PDB [Berman et al., 2000]). Nous fournissons des évaluations moléculaires basées sur des structures de ligand ou de cible et celles-ci sont nommées évaluations basées sur le ligand ou basées sur la cible, respectivement.

**Évaluation basée sur les ligands.** Cette évaluation consiste à regrouper les ligands prédits et connus en fonction de leur similarité structurelle mesurée avec le coefficient de Tanimoto. Nous trouvons un total de treize clusters. Parmi ces clusters, dix contiennent à la fois des ligands prédits et connus et leur contenu est répertorié dans le tableau 3.7. Nous fournissons également
le poids moléculaire (MW) de la sous-structure commune maximale (MCS) des ligands dans chaque groupe. Le premier cluster contient 10 ligands dont 6 sont connus de la littérature et 4 sont de nouveaux composés prédits. De plus, ce cluster affiche le MCS le plus élevé, révélant ainsi une bonne similarité moléculaire entre tous ces composés. Sur la base des valeurs de MCS qui affichent une diminution importante entre les clusters 6 et 7, on pourrait retenir tous les nouveaux composés des clusters 1 à 6 (i.e., 18 composés) comme potentiels ligands intéressants pour la cible nsp13. Cet ensemble de 18 composés comprend le Fosinopril qui apparaîtra également dans l'évaluation basée sur les cibles.

**Évaluation basée sur les cibles.** Cette évaluation consiste à réaliser un docking (ou "amarrage") moléculaire des 38 ligands prédits et 86 connus dans le site actif de la structure nsp13 à l'aide du logiciel GOLD. Le docking moléculaire est une approche numérique de modélisation moléculaire. Elle cherche à identifier la meilleure orientation entre 2 molécules sur la base de leur coordonnées dans des états pris séparément. [Yang et al., 2022]. Le tableau 3.8 répertorie les 20 meilleurs ligands en ce qui concerne l'amarrage moléculaire. Il est important de mentionner que 4/38 ligands prédits sont présents dans cette liste, avec des scores d'amarrage supérieurs à 70. En particulier, Fosinopril se démarque et se classe en deuxième position, avec un score (78,86) très similaire au ligand de premier rang Diosmine (79.04), identifié comme ligand nsp13 par White *et al.* [White et al., 2020]. Les trois autres ligands prédits : Macitentan, Eprosartan et Dinoprostone sont classés en position 12 à 14, avec des scores allant de 70,76 à 71,76 malgré leur MW variable, excluant ainsi un effet de leur taille sur le nombre d'interactions avec la cible.

Le tableau 3.8 affiche également la meilleure cible de maladie pour chaque ligand et le score de probabilité des triplets formés entre les ligands et les cibles de maladie COVID-19, à l'exception de quatre d'entre eux (marqués d'un astérisque) qui ne sont pas présents dans DRKG. Lorsque la meilleure cible de la maladie n'est pas nsp13, les informations pour la deuxième meilleure cible sont fournies uniquement s'il s'agit de nsp13. Étonnamment, le meilleur ligand amarré Diosmine n'affiche pas nsp13 comme meilleure ou deuxième meilleure cible.

Nous avons ensuite analysé nos résultats d'amarrage en explorant les cartes d'interaction de nos quatre composés les mieux classés et en les comparant à Diosmine (ligand connu avec le meilleur score Gold), Ergotamine et Risperdal (ligands connus avec les deux scores de probabilité les plus élevés avec nsp13 dans DRKG) pour vérifier leurs similitudes de liaison. La Figure 3.6
<table><caption>TABLE 3.7 – Clustering des 100 meilleurs ligands prédits et connus (d'après la littérature et le PDB) : le nombre entre () donne un poids moléculaire entier. Les clusters sont numérotés dans l'ordre décroissant de leur poids maximum de sous-structure commune (MCS). Les ligands connus de la base de données PDB sont désignés par leur abréviation PDB. Les noms complets correspondants sont fournis dans [Islam et al., 2023]</caption><thead><tr><td>No</td><td>Predicted ligands</td><td>Known ligands</td><td>MW (g/mol) for MCS</td></tr></thead><tbody><tr><td>1</td><td>Fosinopril(563), Griseofulvin(352), Telavancin(1755), Ridaforolimus(990)</td><td>Simeprevir(749), Dihydroergota-mine(583), Paritaprevir(765), Ergo-loid(611), Grazoprevir(766), Ergota-mine(581)</td><td>120</td></tr><tr><td>2</td><td>Protirelin(362), Teripar-tide(4117), Tiagabine(375)</td><td>NUA(193), HR5(207), VWM(187)</td><td>105</td></tr><tr><td>3</td><td>Binimetinib(441), Niflu-mic_acid(282), Moxifloxa-cin(401)</td><td>Picrasidine N(490), Irinotecan(586), Ne-tupitant(578), Lumacaftor(452), Bana-nin(327), Picrasidine M(490), Niloti-nib(529), Zelboraf(489)</td><td>98</td></tr><tr><td>4</td><td>Mesoridazine(386), Perphena-zine(403), Oxcarbazepine(252), Tizanidine(253)</td><td>SSYA10-001(308), NY7(194), VVD(197), VW7(204), S7G(190), UVA(185), N0E(241), NZG(197), JHJ(243), LJA(193), EJQ(222), VXD(198)</td><td>93</td></tr><tr><td>5</td><td>Meclizine(390), Flunarizine(404), Remoxipride(371), Hydroxy-zine(374)</td><td>Lifitegrast(615), Emend(534), UR7(203), JOV(227), VWD(200), NX7(211), VWA(153), UQS(191), UXG(239), VW4(199)</td><td>92</td></tr><tr><td>6</td><td>Darifenacin(426), Tetrabena-zine(317), Oxybutynin(357), Ritodrine(287), Oxymor-phone(301), Naloxone(327), Hydrocodone(299), Tofiso-pam(382)</td><td>Tubocurarine(609), Cepharanthine(606), Differin(412), Isorhoeadine(383), Epiex-celsin(414), Enjuvia(350), Homova-nillic acid(182), K2P(206), VXG(233), VVY(205), STV(243), VW1(190)</td><td>89</td></tr><tr><td>7</td><td>Lamotrigine(256)</td><td>K34(152), JG4(150)</td><td>67</td></tr><tr><td>8</td><td>Carisoprodol(260)</td><td>Clavulanic acid(199), Acetylcy-steine(163), VWV(221)</td><td>59</td></tr><tr><td>9</td><td>Macitentan(588), Famoti-dine(337), Eprosartan(424)</td><td>Cefoperazone(645), Cefpiramide(612), Risperdal(410), Cordycepin(251), Priteli-vir(402), Dpnh(665), VX4(224)</td><td>50</td></tr><tr><td>10</td><td>Risedronic acid(283), Cincho-caine(343), Bifonazole(310)</td><td>RYM(233), NYV(189), VWJ(175), O2A(174), UVJ(203), MUK(199), S7J(191), UJK(203), VWG(188)</td><td>50</td></tr></tbody></table>

montre la superposition des ligands (4 prédits contre 3 connus) extraits des meilleures poses d'amarrage correspondantes et le tableau 3.9 compare la liste des résidus nsp13 concernés par
<table><caption>TABLE 3.8 – Liste des 20 meilleurs ligands ancrés (docked) classés selon le Gold Score dé-
croissant. * signifie que le ligand n’est pas présent dans DRKG. Les résultats pour les ligands
de nos prédictions sont mis en évidence en couleur bleu clair. Les valeurs de prédiction dans
DRKG sont également indiquées avec la meilleure cible de maladie et le score de probabilité
correspondant. Lorsque la meilleure cible n’est pas nsp13, la deuxième meilleure cible et son
score de probabilité ne sont indiqués que s’il s’agit de nsp13. [Islam et al., 2023]</caption><thead><tr><th>Docking rank</th><th>Ligand name</th><th>Gold score</th><th>MW (g/mol)</th><th>Best predicted target</th><th>Predicted probability score</th><th>Predicted rank</th><th>Reference</th></tr></thead><tbody><tr><td>1</td><td>Diosmin</td><td>79.04</td><td>608.5</td><td>nsp9</td><td>0.169</td><td>6091</td><td>White et al. (2020) [White et al., 2020]</td></tr><tr><td>2</td><td>Fosinopril</td><td>78.86</td><td>563.7</td><td>nsp13</td><td>0.964</td><td>29</td><td>This study</td></tr><tr><td>3</td><td>Nilotinib</td><td>76.55</td><td>529.5</td><td>nps6/nsp13</td><td>0.860/0.796</td><td>101</td><td>White et al. (2020) [White et al., 2020]</td></tr><tr><td>4</td><td>Chromone-4c*</td><td>76.17</td><td>417.4</td><td>NA</td><td>NA</td><td>NA</td><td>Perez-Lemus et al. (2022) [Perez-Lemus et al., 2022]</td></tr><tr><td>5</td><td>Dpnh</td><td>76.04</td><td>665.4</td><td>nsp9</td><td>0.146</td><td>6361</td><td>White et al. (2020) [White et al., 2020]</td></tr><tr><td>6</td><td>Cromolyn</td><td>75.7</td><td>468.4</td><td>nsp13</td><td>0.619</td><td>1751</td><td>White et al. (2020) [White et al., 2020]</td></tr><tr><td>7</td><td>Picrasidine_N*</td><td>74.55</td><td>490.5</td><td>NA</td><td>NA</td><td>NA</td><td>Vivel-Ananth et al. (2022) [Vivek-Ananth et al., 2022]</td></tr><tr><td>8</td><td>Picrasidine_M*</td><td>74.52</td><td>490.5</td><td>NA</td><td>NA</td><td>NA</td><td>Vivel-Ananth et al. (2022) [Vivek-Ananth et al., 2022]</td></tr><tr><td>9</td><td>Dihydroergotamine</td><td>74.13</td><td>583.7</td><td>nsp13</td><td>0.796</td><td>475</td><td>White et al. (2020) [White et al., 2020]</td></tr><tr><td>10</td><td>Ergotamine</td><td>72.83</td><td>581.7</td><td>nsp13</td><td>0.805</td><td>361</td><td>White et al. (2020) [White et al., 2020]</td></tr><tr><td>11</td><td>Simeprevir</td><td>72.68</td><td>749.9</td><td>nsp6/nsp13</td><td>0.537/0.139</td><td>2076</td><td>Gurung (2020) [Gurung, 2020]</td></tr><tr><td>12</td><td>Macitentan</td><td>71.76</td><td>588.3</td><td>nsp13</td><td>0.95</td><td>49</td><td>This study</td></tr><tr><td>13</td><td>Eprosartan</td><td>71.33</td><td>424.5</td><td>nsp13</td><td>0.878</td><td>71</td><td>This study</td></tr><tr><td>14</td><td>Dinoprostone</td><td>70.76</td><td>352.5</td><td>nsp13</td><td>0.959</td><td>38</td><td>This study</td></tr><tr><td>15</td><td>Cefoperazone</td><td>70.24</td><td>645.7</td><td>nsp13</td><td>0.599</td><td>1816</td><td>White et al. (2020) [White et al., 2020]</td></tr><tr><td>16</td><td>Scutellarin*</td><td>70.19</td><td>462.4</td><td>NA</td><td>NA</td><td>NA</td><td>Gurung (2020) [Gurung, 2020]</td></tr><tr><td>17</td><td>Irinotecan</td><td>70.11</td><td>586.7</td><td>nsp6/nsp13</td><td>0.824/0.796</td><td>249</td><td>White et al. (2020) [White et al., 2020]</td></tr><tr><td>18</td><td>Paritaprevir</td><td>69.61</td><td>765.9</td><td>orf8</td><td>0.099</td><td>6990</td><td>Gurung (2020) [Gurung, 2020]</td></tr><tr><td>19</td><td>Risperdal</td><td>68.76</td><td>410.5</td><td>nsp6/nsp13</td><td>0.807/0.807</td><td>349</td><td>White et al. (2020) [White et al., 2020]</td></tr><tr><td>20</td><td>Ergoloid</td><td>68.59</td><td>611.7</td><td>nsp13</td><td>0.584</td><td>1888</td><td>White et al. (2020) [White et al., 2020]</td></tr></tbody></table>

des interactions avec tous ces ligands.

<table><caption>TABLE 3.9 – Liste des résidus d’acides aminés dans la structure nsp13 qui interagissent avec les ligands répertoriés (les ligands prédits sont surlignés en bleu clair, les autres correspondent à des ligands connus). Les ligands sont classés comme dans le tableau 3.8. L’étiquette et la position des résidus sont en gras lorsqu’elles correspondent à des résidus délimitant le site de liaison à l’ATP. Toutes les cartes d’interaction sont disponibles dans [Islam et al., 2023].</caption><thead><tr><th>Ligands</th><th>GLY285</th><th>GLY287</th><th>LYS288</th><th>SER289</th><th>HIS290</th><th>LYS320</th><th>GLU375</th><th>ARG442</th><th>GLY538</th><th>GLU540</th></tr></thead><tbody><tr><td>Diosmin</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td></td><td>X</td><td>X</td><td>X</td></tr><tr><td>Fosinopril</td><td>X</td><td>X</td><td>X</td><td>X</td><td></td><td>X</td><td>X</td><td>X</td><td></td><td>X</td></tr><tr><td>Ergotamine</td><td>X</td><td></td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td></td><td></td></tr><tr><td>Eprosartan</td><td></td><td></td><td>X</td><td>X</td><td></td><td>X</td><td></td><td></td><td></td><td></td></tr><tr><td>Macitentan</td><td></td><td></td><td></td><td></td><td>X</td><td>X</td><td></td><td>X</td><td></td><td></td></tr><tr><td>Dinoprostone</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td></td><td>X</td><td></td><td></td></tr><tr><td>Risperdal</td><td></td><td></td><td>X</td><td>X</td><td>X</td><td>X</td><td>X</td><td></td><td>X</td><td>X</td></tr></tbody></table>

Ces données montrent que les composés prédits partagent avec les ligands connus plusieurs
éléments structuraux et deux d'entre eux (Fosinopril et Dinoprostone) interagissent avec 6/7
<figure><img src="image_13.png" /><figcaption>FIGURE 3.6 – Superposition des poses de liaison avec la cible nsp13 pour Fosinopril (en vert), Macitentan (en bleu foncé), Eprosartan (en rouge) et Dinoprostone (en magenta) contre Diosmine (en bleu clair), Ergotaminine (en gris) et Risperdal (en marron). Les ligands le long de l'axe vertical sont les ligands prédits, tandis que ceux le long de l'axe horizontal sont les ligands connus. [Islam et al., 2023]</figcaption></figure>

résidus d'acides aminés du site actif nsp13.

## 3.6 Discussion et conclusions

Bien que nos approches de prédiction de liens fournissent des résultats satisfaisants pour la prédiction de liens explicables dans les graphes de connaissances, nous identifions quelques limitations ainsi que des perspectives intéressantes à explorer. En particulier, nous comptons étudier l'utilisation des techniques d'apprentissage profond telles que les réseaux de neurones convolutifs et les réseaux de neurones récurrents pour la prédiction de liens dans les graphes de connaissances. Il est important de mentionner que la modélisation des relations complexes entre les entités et les concepts peut être difficile, et les modèles de prédiction de liens peuvent être sensibles aux erreurs de données et au sur-apprentissage. Il y a donc encore beaucoup de travail à faire pour améliorer les performances et la robustesse des approches de prédiction de liens dans
les graphes de connaissances.

Comme discuté dans la Section 3.4, nous avons appliqué des approches de prédiction de liens pour le repositionnement de médicaments en identifiant des associations entre les médicaments et les maladies qui n'ont pas encore été explorées. Cependant, ces approches de prédiction de liens pour le repositionnement de médicaments sont confrontées à plusieurs défis :

- Données insuffisantes : Les données sur les médicaments et les maladies sont souvent limitées et fragmentaires, ce qui peut rendre difficile la prédiction de nouvelles associations entre les médicaments et les maladies.

- Variabilité des données : Les données sur les médicaments et les maladies peuvent être très variables, car elles proviennent de différentes sources et peuvent avoir été mesurées de différentes manières. Cela peut rendre difficile la comparaison et l'intégration des données.

- Complexité des relations : Les relations entre les médicaments et les maladies peuvent être très complexes et impliquer de nombreux facteurs interdépendants. Cela peut rendre difficile la modélisation de ces relations et la prédiction de nouvelles associations.

- Hétérogénéité des populations : Les populations de patients peuvent varier considérablement selon les maladies, les groupes d'âge et les origines géographiques. Cela peut rendre difficile la généralisation des résultats et la prédiction de l'efficacité d'un médicament dans une population donnée.

- Validation expérimentale : Les prédictions doivent être validées expérimentalement avant de pouvoir être utilisées pour le repositionnement de médicaments. Cependant, la validation expérimentale peut être coûteuse et prendre du temps.
# Deuxième partie

## Calcul distribué et grands graphes
complexes
<figure><img src="image_14.png" /></figure>
# Chapitre 4

## Approches distribuées pour l'analyse de
grands graphes dynamiques

### 4.1 Introduction

Au cours de la dernière décennie, le domaine du traitement distribué des graphes à grande échelle a attiré une attention considérable [Inoubli et al., 2018] [Aridhi and Mephu, 2016] [Inoubli et al., 2022]. Cette attention a été motivée non seulement par la taille croissante des données de graphes, mais aussi par leur grand nombre d'applications. Dans ce contexte, de nombreux systèmes de traitement de graphes distribués/parallèles ont été proposés, tels que Pregel [Malewicz et al., 2010], Ray [Moritz et al., 2018b], GraphLab [Low et al., 2012] et Trinity [Shao et al., 2013]. Ces systèmes peuvent être divisés en trois catégories : (1) approches centrées sur les sommets (ou Vertex-centric), (2) approches centrées sur les blocs (ou Block-centric) et (3) approches de type Gather-Apply-Scatter (GAS) [Xin et al., 2013]. Les approches centrées sur les sommets divisent les graphes d'entrée en partitions et utilisent un modèle de programmation "Think like a vertex" pour prendre en charge le calcul itératif des graphes [Malewicz et al., 2010] [Tian et al., 2013]. Chaque sommet correspond à un processus, et des messages sont échangés entre les sommets. Dans les approches centrées sur les blocs [Yan et al., 2014], l'unité de calcul est un bloc (un sous-graphe connexe du graphe) et les échanges de messages se produisent entre les blocs. Les approches centrées sur les sommets se sont avérées utiles pour de nombreux al-
gorithms de graphes. Cependant, ils ne fonctionnent pas toujours efficacement, car ils ignorent
les informations vitales sur les partitions de graphe, qui représentent des sous-graphes réels du
graphe d'entrée d'origine, au lieu d'une collection de sommets non liés. Les approches de type
GAS sont similaires aux approches basées sur les sommets et le programme qui s'exécute dans
chaque sommet à chaque itération est divisé en trois sous-fonctions : *gather*, apply et *scatter*.
Dans la fonction *gather*, le sommet courant obtient des informations de ses sommets voisins et
éventuellement les agrège en une seule valeur $\sigma$. Dans la fonction *apply*, l'état du sommet est mis
à jour en fonction de la valeur $\sigma$, et probablement des caractéristiques spécifiques des sommets
voisins. Enfin, dans la fonction *scatter*, chaque sommet partage son nouvel état avec ses sommets
voisins. Ensuite, chaque programme implémenté doit être modélisé comme trois fonctions qui
manipulent les valeurs $\sigma$ afin de changer l'état du sommet ou d'arrêter le programme.

Il est important de mentionner que les systèmes présentés ci-dessus ne traitent que des graphes
statiques et ne considèrent pas la question du traitement des graphes évolutifs et dynamiques.
Durant ces dernières années, nous nous sommes intéressés non seulement à la distribution de
certaines tâches sur des graphes simples et/ou complexes à grande échelle mais aussi à la pro-
position de plateformes génériques pour le traitement de grands graphes dynamiques. Dans ce
chapitre, je présente d'abord nos travaux d'état de l'art sur les plateformes de calcul distribué
et je me focaliserai sur les plateformes spécifiquement conçues pour le traitement et l'analyse de
grands graphes. Ensuite, je présente nos contributions pour le calcul distribué et le clustering
incrémental dans des grands graphes dynamiques.

## 4.2 Plateformes de calcul distribué : état de l'art

L'étude des approches d'analyse de grands graphes est essentielle pour exploiter tout le po-
tentiel des données massives représentées sous forme de graphes. Cela permet de découvrir des
connaissances, de prendre des décisions éclairées et de résoudre des problèmes complexes dans
divers domaines. Dans ce contexte, nous avons mené une étude comparative des plateformes exis-
tantes d'analyse de données de type graphe [Aridhi and Mephu, 2016] [Inoubli, 2021] et d'analyse
de gros volumes de données ou de Big Data en général [Inoubli et al., 2018].
<table><caption>TABLE 4.1 – Graph processing frameworks comparative study [Inoubli, 2021].</caption><thead><tr><th>Framework</th><th>Programming model</th><th>Distributed /Centralized</th><th>Communication</th><th>Dynamic/Static graph</th></tr></thead><tbody><tr><td>Pregel</td><td>Vertex-centric</td><td>Distributed</td><td>Message passing</td><td>Static</td></tr><tr><td>GraphX</td><td>GAS</td><td>Distributed</td><td>Shared memory</td><td>Static</td></tr><tr><td>BLADYG</td><td>Block-Centric</td><td>Distributed</td><td>Hybrid</td><td>Dynamic</td></tr><tr><td>Giraph</td><td>Vertex-centric</td><td>Distributed</td><td>Message passing</td><td>Static</td></tr><tr><td>GraphIn</td><td>I-GAS</td><td>Centralized</td><td>Message passing</td><td>Dynamic</td></tr><tr><td>GraphMat</td><td>GAS</td><td>Centralized</td><td>Message passing</td><td>Static</td></tr><tr><td>PowerGraph</td><td>GAS</td><td>Distributed</td><td>Shared memory</td><td>Static</td></tr><tr><td>GraphLab</td><td>GAS</td><td>Distributed</td><td>Shared memory</td><td>Static</td></tr><tr><td>Blogel</td><td>Block-Centric</td><td>Distributed</td><td>Message passing</td><td>Static</td></tr><tr><td>Mezan</td><td>Vertex-centric</td><td>Distributed</td><td>Message passing</td><td>Static</td></tr><tr><td>GPS</td><td>Vertex-centric</td><td>Distributed</td><td>Message passing</td><td>Static</td></tr><tr><td>Trinity</td><td>GAS</td><td>Distributed</td><td>Shared memory</td><td>Static</td></tr><tr><td>Hama</td><td>Vertex-centric</td><td>Distributed</td><td>Message passing</td><td>Static</td></tr><tr><td>Pegasus</td><td>MapReduce</td><td>Distributed</td><td>no communication</td><td>Static</td></tr><tr><td>Giraph++</td><td>Vertex-centric</td><td>Centralized</td><td>Message passing</td><td>Static</td></tr><tr><td>GRACE</td><td>Vertex-centric</td><td>Centralized</td><td>message passing</td><td>Static</td></tr></tbody></table>

### 4.2.1 Catégorisation des plateformes de calcul distribué sur des graphes

Il existe plusieurs plateformes de calcul distribué spécifiquement conçues pour le traitement et l'analyse de grands graphes. Dans le contexte d'un travail d'analyse critique de ces plateformes, nous avons présenté dans [Aridhi and Mephu, 2016] et dans [Inoubli, 2021] les architectures et les spécificités des plateformes populaires d'analyse de grands graphes. Le tableau 4.1 présente quelques plateformes de traitement de graphes les plus populaires. Pour chaque plateforme, nous listons le modèle de programmation, la méthode de communication utilisée et si le framework permet de traiter des graphes dynamiques ou non.

Tous les frameworks présentés dans le tableau 4.1 visent à fournir une interface de programmation facile à utiliser pour l'analyse de graphes qui peut ensuite être exécutée en utilisant les
ressources fournies. Nous mentionnons que la plupart des frameworks de traitement de graphes permettent des algorithmes asynchrones et distribués. Il est aussi important de mentionner que la plupart des frameworks distribués de traitement de graphes présentés traitent des graphes statiques et seul BLADYG (notre proposition, voir Section 4.3) considère les graphes évolutifs et dynamiques.

Une description détaillée des plateformes décrites dans le Tableau 4.1 ainsi qu'une catégorie de quelques approches de fouille de graphes distribuées selon l'entrée, la sortie de chaque approche et le modèle de programmation utilisé sont disponibles dans [Aridhi and Mephu, 2016] et [Inoubli, 2021].

### 4.2.2 Catégorisation des plateformes de Big Data

Dans le cadre du travail de thèse de Wissem Inoubli [Inoubli, 2021], nous avons commencé par une étude théorique et expérimentale des plateformes de Big Data. Nous présentons dans le tableau 4.2 une comparaison des plateformes d'analyse de gros volumes de données en fonction de leurs principales caractéristiques. Ces caractéristiques clés sont : (1) le modèle de programmation, (2) les langages de programmation pris en charge, (3) le type de sources de données et (4) la capacité de permettre un traitement itératif des données, (5) la compatibilité de la plateforme avec les bibliothèques d'apprentissage automatique et (6) la stratégie de tolérance aux pannes.

Comme indiqué dans le tableau 4.2, Hadoop, Flink et Storm utilisent le format clé-valeur pour représenter leurs données. Ceci est motivé par le fait que le format clé-valeur permet d'accéder à des données hétérogènes. Pour Spark, le concept de "Resilient Distributed Dataset" (RDD), une collection d'éléments partitionnés et distribués à travers les nœuds d'un cluster, et le format clé-valeur sont utilisés pour permettre un accès rapide aux données. Nous avons également classé les frameworks Big Data étudiés selon deux modes de fonctionnement : (1) mode batch/lot et (2) mode flux. Nous avons montré dans le tableau 4.2 que Hadoop traite les données en mode batch, alors que les autres frameworks permettent le mode de traitement en flux. En termes d'architecture physique, on constate que tous les frameworks étudiés sont déployés dans une architecture en cluster, et chaque framework utilise un gestionnaire de cluster spécifique. Notons que la plupart des frameworks utilisent YARN comme gestionnaire de cluster. D'un point de vue technique, nous mentionnons que tous les frameworks présentés fournissent des API pour
<table><caption>TABLE 4.2 – Comparative study of popular Big Data frameworks. [Inoubli et al., 2018]</caption><thead><tr><th></th><th>Hadoop</th><th>Spark</th><th>Storm</th><th>Flink</th><th>Samza</th></tr></thead><tbody><tr><th>Data format</th><td>Key-value</td><td>Key-value, RDD</td><td>Key-value</td><td>Key-value</td><td>Events</td></tr><tr><th>Processing mode</th><td>Batch</td><td>Batch and Stream</td><td>Stream</td><td>Batch and Stream</td><td>Stream</td></tr><tr><th>Data sources</th><td>HDFS</td><td>HDFS, DBMS and Kafka</td><td>HDFS, HBase and Kafka</td><td>Kafka, Kinesis, message queues, socket streams and files</td><td>Kafka</td></tr><tr><th>Programming model</th><td>Map and Reduce</td><td>Transformation and Action</td><td>Topology</td><td>Transformation</td><td>Map and Reduce</td></tr><tr><th>Supported programming languages</th><td>Java</td><td>Java, Scala and Python</td><td>Java</td><td>Java</td><td>Java</td></tr><tr><th>Cluster manager</th><td>YARN</td><td>Standalone, YARN and Mesos</td><td>YARN or Zookeeper</td><td>Zookeeper</td><td>YARN</td></tr><tr><th>Comments</th><td>Stores large data in HDFS</td><td>Gives several APIs to develop interactive applications</td><td>Suitable for real-time applications</td><td>Flink is an extension of MapReduce with graph methods</td><td>Based on Hadoop and Kafka</td></tr><tr><th>Iterative computation</th><td>Yes (by running multiple MapReduce jobs)</td><td>Yes</td><td>Yes</td><td>Yes</td><td>Yes</td></tr><tr><th>Interactive Mode</th><td>No</td><td>Yes</td><td>No</td><td>No</td><td>No</td></tr><tr><th>Machine learning compatibility</th><td>Mahout</td><td>SparkMLlib</td><td>Compatible with SAMOA API</td><td>FlinkML</td><td>Compatible with SAMOA API</td></tr><tr><th>Fault tolerance</th><td>Duplication feature</td><td>Recovery technique on the RDD objects</td><td>Checkpoints</td><td>Checkpoints</td><td>Data partitioning</td></tr></tbody></table>

plusieurs langages de programmation comme Java, Scala et Python. Chaque framework fournit un ensemble de fonctions abstraites qui sont utilisées pour définir le calcul souhaité. Nous avons également présenté dans le tableau 4.2 le fait que la plateforme permet d'exécuter des algorithmes d'apprentissage automatique ou non. Nous remarquons que Spark et Flink fournissent leurs propres bibliothèques d'apprentissage automatique, tandis que les autres frameworks ont une certaine compatibilité avec d'autres outils, tels que SAMOA<fnref n="5" /> [De Francisci Morales, 2013] pour Samza et Mahout<fnref n="6" /> [Anil et al., 2020] pour Hadoop.

Comme le montre le tableau 4.2, l'importance de Spark réside dans sa capacité d'utiliser la mémoire centrale d'une façon efficace et ses capacités de traitement par micro-lots, en particulier dans les cas de traitements itératifs [Bajaber et al., 2016]. Nous remarquons aussi que Spark est

<footnote n="5">5. https://samoa-project.net/</footnote>

<footnote n="6">6. https://mahout.apache.org/</footnote>
connu pour être très rapide dans certains types d'applications en raison du concept de RDD.

Flink partage des similitudes et des caractéristiques avec Spark. Il offre de bonnes performances de traitement lorsqu'il s'agit de structures de données complexes comme les graphes. Bien qu'il existe d'autres solutions pour le traitement de graphes à grande échelle, Flink et Spark sont enrichis de librairies et outils spécifiques pour l'apprentissage automatique, l'analyse prédictive et l'analyse de flux de graphes.

Une étude expérimentale approfondie des plateformes décrites dans le tableau 4.2 ainsi qu'un ensemble de bonnes pratiques liées à l'utilisation de ces plateformes dans plusieurs domaines d'application sont disponibles dans [Inoubli et al., 2018]. Dans cette étude, nous avons comparé les performances des plateformes étudiées pour plusieurs types de données (graphes, tweets, textes, etc) et dans deux scénarios différents : (1) traitement par lot et (2) traitement des données en flux.

## 4.3 Approche générique pour le calcul distribué sur des grands graphes dynamiques

Dans ce travail de recherche, nous considérons les questions d'échelle et de dynamisme dans le cas des approches centrées sur les blocs [Yan et al., 2014]. En particulier, nous étudions les grands graphes connus par leur nature évolutive et décentralisée. Par exemple, la structure d'un grand réseau social change au fil du temps (par exemple, les utilisateurs établissent de nouvelles relations et communiquent avec différents amis). Nous présentons *BLADYG*<sup>7</sup>, un framework centré sur les blocs qui aborde la question du dynamisme dans les graphes à grande échelle. *BLADYG* peut être utilisé non seulement pour calculer les propriétés communes de grands graphes, mais aussi pour maintenir les propriétés calculées lorsque de nouvelles arêtes et nœuds sont ajoutés ou supprimés dans le graphe. L'idée clé est d'éviter le re-calculation des propriétés du graphe à partir de zéro lorsque le graphe est mis à jour. *BLADYG* limite le calcul à un petit sous-graphe en fonction de la tâche considérée. Nous présentons un ensemble d'abstractions pour *BLADYG* qui peuvent être utilisées pour concevoir des algorithmes pour n'importe quelle tâche de graphes distribués.

<footnote n="7">7. http://bladyg.loria.fr/</footnote>
<figure><img src="image_15.png" /><figcaption>FIGURE 4.1 – Architecture de BLADYG [Aridhi et al., 2017]</figcaption></figure>

La Figure 4.1 fournit une vue d'ensemble de l'architecture du framework *BLADYG*. Le calcul dans *BLADYG* commence en collectant les données du graphe à partir de diverses sources de données, notamment des fichiers locaux, des systèmes de fichiers distribués comme le Hadoop Distributed File System (HDFS) et Amazon Simple Storage Service (Amazon S3). Dans *BLADYG*, la collecte de données de graphes peut être effectuée à l'aide d'outils de collecte open source existants comme Kafka [Narkhede et al., 2017], NIFI [Blokdyk, 2020]<fnref n="8" />, Flume [Chambers et al., 2010] et Fluentd [Singh, 2016]. Après avoir collecté les données du graphe, *BLADYG* partitionne le graphe d'entrée en plusieurs partitions, chacune d'entre elles étant affectée à une machine esclave (appelée aussi *worker*) différente. Chaque partition/bloc est un sous-graphe connexe du graphe d'en-

<footnote n="8">8. https://nifi.apache.org/</footnote>
trée. Cette étape de partitionnement est effectuée par un worker qui prend en charge plusieurs types de techniques de partitionnement prédéfinies telles que le partitionnement par hachage, le partitionnement aléatoire, le egde-cut et le vertex-cut. Ces techniques de partitionnement sont présentées ainsi :

- Dans le partitionnement par hachage, les arêtes sont réparties sur les machines selon une fonction de hachage définie par l'utilisateur;

- Dans le partitionnement aléatoire, les arêtes sont réparties sur les machines de manière aléatoire;

- Dans le partitionnement vertex-cut, les arêtes sont uniformément réparties sur les machines dans le but de minimiser le nombre de sommets répliqués;

- Dans le partitionnement edge-cut, les sommets d'un graphe sont divisés en clusters joints de taille presque égale, tandis que le nombre d'arêtes, qui s'étendent sur des clusters séparés, est minimum.

En plus des techniques de partitionnement fournies, les utilisateurs de *BLADYG* peuvent déployer des techniques de partitionnement de graphe existantes, notamment Metis [Karypis and Kumar, 1998a] et JaBeJa [Karypis and Kumar, 1998b]. Les utilisateurs de *BLADYG* peuvent également implémenter leurs propres méthodes de partitionnement. Il est important de mentionner que *BLADYG* permet de traiter de grands graphes déjà répartis sur un ensemble de machines. Ceci est motivé par le fait que la majorité des grands graphes existants sont déjà stockés de manière distribuée, soit parce qu’ils ne peuvent pas être stockés sur une seule machine en raison de leur taille, soit parce qu’ils sont traités et analysés avec des techniques décentralisées, qui les obligent à être répartis entre un ensemble de machines. Chaque machine worker charge son bloc et effectue des calculs locaux et distants, et ensuite l'état des blocs est mis à jour. La machine master orchestre l'exécution de *BLADYG* afin de gérer les mises à jour sur les données d'entrée. En fonction de l'algorithme de graphe, le master construit un plan d'exécution qui consiste en une liste ordonnée de calculs locaux et distants à exécuter par les workers.

Chaque worker effectue deux types d'opérations, comme suit :

1. Calcul *intra-bloc* : dans ce cas, le worker effectue un calcul local sur son bloc (partition)
associé et modifie soit l'état du bloc et/ou les états des nœuds à l'intérieur du bloc.

2. Calcul *inter-blocs*: dans ce cas, le worker demande aux workers distants de faire le calcul et après avoir reçu les résultats, il met à jour le statut de son bloc associé.

Le framework *BLADYG* fonctionne selon trois modes de calcul. En mode *Master2Worker*(*M2W*) et mode *Worker2Master*(*W2M*), les échanges de messages entre la machine maître (appelée aussi *master*) et tous les machines workers sont autorisées. Le maître/master utilise ce mode pour demander à un worker distant de rechercher des nœuds candidats, c'est-à-dire des nœuds qui doivent être mis à jour en fonction de la tâche considérée. Le worker utilise ce mode pour envoyer l'ensemble des nœuds candidats calculés au maître. En mode *Worker2Worker* (*W2W*), les échanges de messages entre workers sont autorisés. Les workers utilisent ce mode afin de propager la recherche de nœuds candidats à un ou plusieurs workers distants. En mode local, seul le calcul local est autorisé. Ce mode est utilisé par le worker/maître pour effectuer des calculs locaux.

Un calcul *BLADYG* typique consiste en : (1) un graphe d'entrée, (2) un ensemble de modifications/mises à jour, (3) une séquence d'opérations de worker ou de maître, et (4) une sortie.

## 4.4 Clustering distribué et incrémental des grands graphes dynamiques

Dans ce travail, nous nous sommes intéressés au clustering incrémental de graphes à grande échelle. Nous présentons *DISCAN*, une méthode distribuée et incrémentale de clustering de graphes basée sur les algorithmes de clustering structurel et en particulier l'algorithme *SCAN* décrit dans la Section 1.3.2. D'un point de vue architectural, *DISCAN* est basé sur un modèle maître/esclave et elle est implémentée sur la base du framework *BLADYG* décrit dans la Section 4.3. Dans ce framework, les esclaves (des machines de type worker) sont responsables de l'exécution d'un calcul spécifique sous le contrôle de la machine maître. De même, les données d'entrée doivent être divisées en sous-graphes. Dans ce qui suit, nous présentons les trois étapes principales de *DISCAN* : (1) le partitionnement de graphes, (2) le clustering distribué de graphes, et (3) la prise en compte des mises à jour.
### 4.4.1 Partitionnement de graphes distribués

Dans cette étape, DISCAN commence par la division du graphe d'entrée G en plusieurs partitions $P1, P2, \dots, P_n$ tout en maintenant la cohérence des données (structure globale du graphe). Pour garantir la propriété de cohérence lors de la division du graphe d'entrée, nous devons identifier une liste d'arêtes de coupe permettant d'obtenir une vue globale de G. Habituellement, le problème de partitionnement des graphes est classé dans la famille des problèmes NP-difficiles, qui doivent évaluer toutes les combinaisons pour obtenir le meilleur résultat de partitionnement. Pour cette raison, nous avons proposé un algorithme de partitionnement approximatif et distribué comme étant une étape préliminaire pour notre algorithme de clustering distribué. Dans l'étape de partitionnement, la machine maître divise de manière équitable le fichier du graphe d'entrée en sous-fichiers en fonction du nombre d'arêtes. Puis, elle envoie ces derniers à tous les workers. Chaque worker obtient une liste d'arêtes et de sommets de son sous-fichier. Il reçoit également la liste des sommets de workers voisins par la machine maître. Ceci est utile pour la détermination des sommets en frontière et donc pour l'identification des arêtes de coupe. Notons que ces dernières dénotent les arêtes ayant au moins un sommet en frontière.

### 4.4.2 Clustering distribué

Après avoir divisé le graphe d'entrée G en sous-graphes répartis entre les workers, DISCAN déclenche l'étape de clustering distribué (voir Algorithme 4). Cette étape est divisée à son tour en deux parties fondamentales : (1) le clustering local et (2) l'agrégation des résultats intermédiaires. Dans ce qui suit, nous décrivons en détail le principe de fonctionnement de ces dernières parties ainsi que le lien entre elles.

**Étape 1 (Clustering local) :** Le graphe d'entrée G est fragmenté en plusieurs sous-graphes/partitions (P), chacun d'eux est affecté à une machine esclave (ou *worker*). L'étape de partitionnement est effectuée conformément au nombre de machines esclaves. Pour éviter la perte d'informations au cours de l'étape de partitionnement (les arêtes reliant des sommets dans les différentes partitions), les sommets de frontière sont dupliqués dans les partitions voisines. Ensuite, pour chaque partition $P_i$, le clustering local est effectué sur les différentes partitions des machines esclaves. Nous considérons les cas où plusieurs conflits entre deux partitions P1 et P2
<caption>**Algorithm 4 Distributed Clustering**</caption>

Input : Graph G, parameters (μ, ε, α)
Output: Clusters, Bridges, Outliers

/* Divide G into subgraphs G = {G₁G₂..Gα} according to parameter α */
24 P ← Partition (G,α)

/* In parallel */
25 foreach Pᵢ ∈ P do
26   Assign Pᵢ to Wᵢ

/* In parallel */
/* Step 1: Local clustering */
27 foreach Worker Wᵢ ∈ W do
28   Let Pᵢ the current partition
       Find the frontier vertices in Pᵢ and duplicate them into neighbor partitions

/* In parallel */
29 foreach Worker ∈ W do
30   Compute the structural similarity of a partition Pᵢ using Vf list
       Retrieve local Cores and Borders in Pᵢ
       Build local clusters in Pᵢ
       Find local Bridges and Outliers in Pᵢ

/* Step 2: Merging */
All workers exchange theirs local clusters between them; using Worker2Worker message
foreach Worker Wᵢ ∈ W do
31   if (C₁ ∩ C₂ ∩ .. ∩ Cα = V; and ∃Vᵢ ∈ Core then
32     C ← Merge(C₁, C₂, ..Cα)
     Send C to the master
33   else
34     Send local clusters to master
35   for Vᵢ IN Outliers do
36     if (Vᵢ ∈ Core ∪ Border ∪ Bridges) then
37       Remove Vᵢ from the list of Outliers
38   for Vᵢ IN Outliers do
39     NbConnections ← 0
40     for Cᵢ IN Clusters do
41       if (N(Vᵢ) ∩ Cᵢ ≠ ∅) then
42         NbConnections ++
43       if (NbConnections ≥ 2) then
44         Add Vᵢ to Bridges
45         Remove Vᵢ from Outliers
46   Send Clusers, Bridges, Outliers to the master using Worker2Master message
ont eu lieu.

**Étape 2 (Fusion) :** En comparaison avec l'algorithme de référence SCAN, la distribution du calcul de similarité et l'étape de clustering local peuvent réduire le temps de réponse de DISCAN. Cependant, nous devons prendre en compte l'exactitude des résultats renvoyés. Pour garantir les mêmes résultats que SCAN, nous avons défini un ensemble de scénarios pour assurer l'étape de la fusion. Ces scénarios seront appliqués sur toutes les partitions de G. Ils sont répétés jusqu'à ce que toutes les partitions soient combinées. Pour chaque paire de partitions $Pi$ et $Pj$, une fonction de fusion doit être exécutée pour combiner les résultats locaux de $Pi$ et $Pj$. Ces résultats sont stockés dans des variables globales au niveau de la machine maître. L'Algorithme 4 présente plusieurs scénarios pour résoudre les éventuels conflits rencontrés.

**Lemme 4.4.1. (Fusion de clusters locaux)** Soit $C_1$ et $C_2$ deux ensembles de clusters locaux dans différentes partitions $P_1$ et $P_2$, respectivement. $∃c_1 ∈ C_1$ and $∃c_2 ∈ C_2$, $Core(c_1) ∩ Core(c_2) ≠ ∅$.

*Démonstration.* Soit $C_i$ un cluster qui regroupe un ensemble de sommets de type bordure ou noyau. Si $C_i$ partage au moins un sommet noyau $c$ avec un autre cluster $C_j$, alors $c$ a un ensemble de bordures dans $C_i$ et $C_j$. De même, tous les sommets dans $C_i$ et $C_j$ peuvent être accessibles à partir de $c$. D'où, $C_i$ et $C_j$ devraient être fusionnés en un même cluster. □

**Lemme 4.4.2. (De bruit à pont)** Soit $C_1$ et $C_2$ deux ensembles de clusters locaux dans les deux partitions $P_1$ et $P_2$, respectivement. $∃ c_1$ et $c_2$ deux clusters qui appartiennent aux deux ensembles de clusters différents $C_1$ et $C_2$. De plus, $∃ o$ un sommet de type bruit dans les deux partitions $P_1$ et $P_2$ et $N(o) ∩ c_1 ≠ ∅$ et $N(o) ∩ c_2 ≠ ∅$.

*Démonstration.* Si $c_i$ et $c_j$ ($i ≠ j$) partagent un sommet de type bruit $o$, cela signifie que $o$ est faiblement connecté aux deux clusters $c_i$ et $c_j$. Conformément à la Définition 1.3.7, $o$ devrait être changé à un sommet de type pont. □

**Lemme 4.4.3. (De Pont à bruit)** Soit $c_1$ et $c_2$ deux clusters locaux respectivement dans les deux partitions $P_1$ et $P_2$. $∃$ un pont $b$ en fonction uniquement de deux clusters $c_1$ et $c_2$. Lorsque $c_1$ et $c_2$ seront fusionnés en un seul cluster (pendant l'étape de fusion), $b$ devrait être changé à un sommet de type bruit.
Démonstration. Soit $c_i$ et $c_j$ deux clusters qui ont un ensemble de sommets (bordures ou noyaux) et un ensemble de ponts avec d'autres clusters locaux et $\exists b$ un sommet de pont uniquement en fonction des deux clusters $c_i$ et $c_j$ où $i \neq j$. Dans l'étape de fusion et selon le Lemme 4.4.1, si un ou plusieurs clusters partagent au moins un sommet noyau, nous les fusionnons en un même cluster. Dans ce cas ($c_i, c_j$) ⇒ C ce qui rend b faiblement connecté à un seul cluster C. Ainsi, selon la Définition 1.3.8, alors b devrait changer son statut de pont à bruit. □

### 4.4.3 Mise à jour du clustering

Considérons un grand graphe dynamique $G$, qui subira plusieurs modifications au fil du temps, telles que l'ajout ou la suppression d'arêtes et/ou de sommets. Lorsqu'un clustering est effectué, les approches classiques relancent le clustering à partir de zéro, ce qui est évidemment très coûteux surtout dans les grands graphes. Dans ce travail, nous proposons un algorithme incrémental et distribué pour le clustering de grands graphes dynamiques. L'idée principale de notre approche est de déterminer à chaque mise à jour les sommets et les arêtes concernés par cette mise à jour, et en fonction de cela, nous appliquons les nouvelles mises à jour sur les anciens résultats de clustering.

Supposons que $G = (V, E)$ va subir plusieurs mises à jour $U$ au fil du temps. $U$ peut ajouter/supprimer des sommets ou des arêtes de/vers $G$. Ces modifications peuvent affecter les valeurs de similarité et certains statuts de nœuds du graphe (bordure, noyau, etc.). Par conséquent, le schéma de clustering peut être affecté dans plusieurs situations.

**Définition 4.4.1.** Chaque sommet $u_i \in U$ génère des modifications de plusieurs similarités structurelles, qui sont définies comme les arêtes affectées $E_A$. Ces sommets changent également le statut de plusieurs sommets et sont notés comme sommets affectés $V_A$.

**Définition 4.4.2.** (Arêtes affectées) Lors de l'ajout d'un sommet $v_{new}$ lié à un sommet existant $v_{old}$, une nouvelle arête ($v_{new}, V_{old}$) sera créée et un ensemble d'arêtes noté $E_A$ sera marqué comme arêtes affectées et doit être mis à jour.

Notez que $e = (u,v) \in E_A$, où $u \in V_{old}$ et $v \in N(V_{old})$. Dans le cas de la suppression d'un sommet $V_{TBD}$, un ensemble d'arêtes noté $E_{TBD}$ doit être supprimé de G. Ainsi, un $V_C$ de sommets est concerné par cette mise à jour. Ici $V_C = (u,v) \in E_{TBD} \setminus V_{TBD}$ et, d'après $V_C$, les
arêtes affectées sont $E_A = E_i \subset G$ et $E_i = (u, v) / \{u, v\} \in V_c$.

Lors de l'ajout ou de la suppression d'une arête $(v_i, v_j)$, la liste des voisins des deux sommets $v_i$ et $v_j$ sera modifiée, ce qui peut produire plusieurs autres arêtes. Les arêtes affectées mettent à jour leurs similitudes structurelles. $E_A$ est un ensemble d'arêtes $(u, v) \in E$ et $v_i = u$ ou $v_j = v$.

**Définition 4.4.3.** (nœuds affectés) Pour chaque mise à jour sur $G$, certaines similarités structurelles peuvent être modifiées. Ainsi, certains sommets changent de statut (bordure, sommets noyaux). Ces sommets sont définis comme des sommets affectés $V_A$. $V_A$ peut être divisé en deux sous-ensembles : (i) directement affectés $V_{AD}$, qui mettent à jour leur statut en fonction directement de $E_A$, (ii) indirectement affectés $V_{ID}$ qui dépendent du statut de $V_{AD}$. Par exemple, lorsqu'un sommet noyau change son statut en valeur aberrante ou bordure, tous ces sommets bordures seront affectés indirectement en fonction de cette mise à jour. Soit $E_A=(v_1, v_2)$ suivant une mise à jour $V_{AD} = V_{AD} \cup v_1 \cup v_2$, tandis que $V_{AI}$ sont tous voisins de $V_{AD}$. D'autres sommets peuvent être affectés indirectement par plusieurs mises à jour et dépendent des clusters modifiés. Ces sommets sont définis comme les ponts affectés et notés $V_{AB}$. $V_{AB}$ est la liste des valeurs aberrantes ou des ponts qui sont connectés aux clusters affectés décrits dans la Définition 4.4.4.

**Définition 4.4.4.** (Clusters affectés) Les sommets affectés dans plusieurs situations peuvent affecter le schéma de clustering. Les clusters affectés (concernés) représentent le sous-ensemble de clusters qui contiennent un ou plusieurs sommets affectés, désignés par $C_{affected}$.

$C_{affected} = c \in \mathbb{C}$ tel que $v \in (v_{AD} \cup v_{ID})$ et $v \in c$.

**Lemme 4.4.4.** *Changement de similarité structurelle des arêtes affectées*

Les arêtes affectées $E_A$ dépendent principalement de la Définition 1.3.1. La valeur de similarité est basée sur les voisins des deux sommets d'une arête. Ainsi, chaque mise à jour (ajout/suppression d'une arête/sommet) peut modifier la liste des voisins de certains sommets. En conséquence, certaines arêtes doivent changer leur similarité structurelle.

**Lemme 4.4.5.** *Modification de l'état du sommet affecté*

Selon les définitions 1.3.4 et 1.3.3, pour certaines mises à jour dans la similarité structurelle, lorsque la valeur de similarité dépasse ou diminue le seuil $\epsilon$ le statut de cette arête peut être modifié à une connexion forte ou faible. Ainsi, ce changement peut affecter le statut de chaque
sommet $v \in V_{AD}$. Par conséquent, selon la définition 1.3.5, le $V_{DA}$ peut modifier indirectement le statut d'autres sommets qui sont définis comme des sommets indirectement affectés $V_{IA}$. Rationnellement, ces changements peuvent affecter le mappage des clusters, et plusieurs clusters peuvent être modifiés. Ainsi, selon la définition 1.3.7, un sommet $v \in B$ où $v$ ne dépend que de deux clusters $c_1$ et $c_2$. Lorsque $c_1$ et $c_2$ seront fusionnés en un cluster $c_{new}$, $v$ sera faiblement connecté avec seulement $c_{new}$. Dans ce cas et selon la définition 1.3.7, $v$ sera un sommet aberrant. De la même manière, lorsque nous avons un cluster $c$ et que $v$ est une valeur aberrante à $c$ avec deux connexions faibles liées à $v_1$ et $v_2$, après quelques mises à jour, $c$ est divisé en deux clusters $c_1$ et $c_2$ lorsque $v_1$ et $v_2$ sont respectivement dans $c_1$ et $c_2$. Dans ce cas, $v$ devient un pont entre les nouveaux clusters $c_1$ et $c_2$ selon la connexion de $v$ avec $v_1$ et $v_2$.

**Algorithm 5 Algorithme DISCAN**

**Input** : Initial graph $G$ as a text file, parameter ($NP$ number of partitions), a new update $U$
**Output**: $C, B, O$

/* Global affected vertices and clusters in each worker */

31 GlobalAffectedVertices=Ø GlobalAffectedClusters=Ø /* Step 1: Graph maintenance */
/* Update the initial graph in each new update and get the affected vertices and
the affected clusters */

32 Master machine : send a new update $u$ to all workers /* In parallel */

33 **foreach** Worker$_i$ $w_i \in W$ **do**

34 | Update the current partition according to $U$ Get $E_A$ Recompute the similarities of $E_A$
35 | Get the immediately affected vertices $V_I$ Share the immediately affected vertices $V_I$ with all
36 | workers Get the indirectly affected vertices $V_{Ind}$, and the affected clusters $C_A$

/* Step 2: Local clustering schema maintenance */

/* Update the old local clustering schema according to the global affected
vertices */

35 **foreach** Worker$_i$ $w_i \in W$ **do**

36 | Check Core vertices from GlobalAffectedVertices Check Border vertices from GlobalAffected-
37 | Vertices Check affected clusters Check affected bridges

/* Step 3: Merge the new updates */

37 **foreach** Worker$_i$ $w_i \in W$ **do**

38 | Merge all affected clusters from all workers Check new Bridge vertices according to the new
39 | clusters Check the remaining outlier vertices

/* Reset the global affected vertices and clusters in each worker */

39 GlobalAffectedVertices=Ø GlobalAffectedClusters=Ø

40 Send $C, B, O$ to master using Worker2Master message

L'algorithme 5 décrit les principales étapes de DISCAN. La méthode DISCAN fournit une
maintenance du graphe en temps réel et un clustering par micro-lots (ou micro-batch). De
plus, DISCAN effectue le nouveau clustering après plusieurs modifications, afin d'optimiser le clustering incrémental. Nous vous présentons, ci-dessous, les principales étapes de DISCAN :

**Étape 1 : Maintenance du graphe.** Dans cette étape, DISCAN exécute des opérations de maintenance sur le graphe en temps réel. A chaque mise à jour $u \in U$, il (1) met à jour la structure du graphe $G$, (2) vérifie les arêtes affectées $E_A$, et (3) recalcule les similarités de $E_A$ (lignes 4-12 de l'algorithme 5). Ensuite, il récupère $V_A$ en fonction de $E_A$ afin de les mémoriser dans une variable globale. Comme discuté dans la définition 4.4.4, $V_A$ peut affecter plusieurs clusters dans la partition actuelle ou dans d'autres partitions. Ainsi, chaque worker partage son $V_A$ avec tous les workers afin que chacun détermine les clusters concernés et les sauvegarde. Une fois les clusters affectés fixés, ils affectent certains ponts ou sommets aberrants. Les ponts concernés doivent donc être ajoutés à la liste des sommets concernés à vérifier à l'étape suivante.

**Étape 2 : Clustering local incrémental.** Cette étape est effectuée en mode de traitement par micro-batch, après un certain nombre de mises à jour ou en utilisant une fenêtre temporelle (ou un intervalle de temps). Dans chaque lot/batch, DISCAN vérifie d'abord les sommets principaux. La vérification est effectuée uniquement sur les sommets affectés $V_A$, où en général les $|V_A| \ll |V|$. Ensuite, DISCAN vérifie les sommets de bordure comme dans le premier clustering local (Algorithme 4) mais en utilisant seulement $E_A$, puisque les sommets de bordure dépendent des connexions fortes avec les sommets du noyau. Pour cette raison, DISCAN vérifie les sommets principaux selon $E_A$ uniquement. Après cela, les noyaux et les bordures mis à jour modifieront le schéma de clustering en fonction des sommets affectés (sommets noyaux, bordures) comme décrit dans la définition 4.4.4. Il y a cinq cas possibles en raison de chaque mise à jour d'un graphe : (1) diviser un cluster en petits clusters, (2) supprimer un cluster existant, (3) créer de nouveaux clusters, (4) mettre à jour les clusters existants et (5) fusionner deux clusters ou plus.

Considérons un ensemble de noyaux et leurs bordures, et les noyaux ont de fortes connexions entre eux. Après la suppression d'une connexion forte entre deux cœurs $c_1$ et $c_2$, les clusters doivent être divisés en sous-clusters en fonction de $c_1$ et $c_2$. Pour le cas (2), chaque cluster est construit sur une liste de nœuds noyaux et leurs bordures. Si un cluster a un sommet noyau, il doit être supprimé. Parfois, une nouvelle mise à jour crée un sommet aberrant vers un sommet
principal $c_{new}$. Si ce sommet a une connexion forte avec tout autre ancien noyau $c$, il rejoint
le cluster de $c$, comme dans le cas (4). Si $c_{new}$ a des connexions fortes avec un autre noyau,
il construit un nouveau cluster, comme dans le cas (3). Dans le dernier cas (5), s'il existe une
nouvelle connexion forte entre deux sommets noyaux dans deux clusters différents, alors on
fusionne ces derniers.

Afin de traiter tous les cas mentionnés, nous procédons à la suppression de tous les clusters
affectés, puis nous effectuons un nouveau clustering de la même manière que celui présenté dans la
définition 1.3.6, en utilisant uniquement les sommets affectés (c'est-à-dire les sommets noyaux et
les bordures). Ce nouveau clustering est réalisé uniquement sur les sommets modifiés. DISCAN
utilise ensuite les nouveaux clusters ainsi que les sommets affectés restants pour vérifier s'ils
représentent de nouveaux sommets de bordure.

Étape 3 : Fusionner les nouvelles mises à jour. Après chaque lot/batch, chaque worker commence à fusionner les nouvelles mises à jour (voir Algorithme 5 lignes 19-23). La machine maître obtient tous les sommets affectés de tous les workers afin de faciliter la combinaison des nouveaux changements. Ici, certains clusters doivent être vérifiés. Dans chaque lot, le maître ne conserve que les clusters passés inchangés et demande à tous les workers d'obtenir les clusters modifiés. Ainsi, tous les workers combinent les clusters mis à jour, y compris éventuellement de nouveaux clusters. Dans l'étape de fusion, DISCAN utilise les mêmes scénarios que dans le premier clustering (voir Lemme 4.4.1). Si au plus un cluster partage au moins un sommet noyau, ils peuvent être fusionnés en un seul cluster. À l'étape suivante, après avoir obtenu les nouveaux clusters, la machine maître demande à tous les workers d'obtenir leurs sommets de type bordure. Ensuite, chaque worker filtre uniquement les sommets affectés qui appartiendront à ses ponts locaux, et les envoie au maître. Le reste des sommets affectés sera ajouté à la liste globale des valeurs aberrantes. Enfin, DISCAN initialise les sommets et les clusters affectés globalement dans des listes vides qui seront utilisés dans le prochain lot.
## 4.5 Résultats

### 4.5.1 Temps de réponse du clustering distribué initial

DISCAN est conçu pour traiter les graphes dynamiques. Cependant, il commence par effectuer un clustering initial du graphe d'entrée. Ensuite, il traite des changements dans le graphe. Nous avons évalué l'accélération de la première étape de DISCAN et nous l'avons comparée avec le SCAN de base et ses variantes [Inoubli et al., 2022].

<figure><img src="image_16.png" /><figcaption>FIGURE 4.2 – Impact de la taille du graphe sur le temps de traitement des variantes SCAN et DISCAN. [Inoubli et al., 2022]</figcaption></figure>

Comme le montre la Figure 4.2, notre approche est plus lente que les autres algorithmes, dans le cas de petits graphes (G1, G2 et G3). De plus, il y a un très grand écart entre DISCAN et les autres algorithmes, en particulier avec pSCAN et ppSCAN. Cet écart se réduit lorsque la taille du graphe augmente (cas du jeu de données G4). Le diagramme à bâtons de la Figure 4.2, montre un écart de 12x entre DISCAN et SCAN de base avec le jeu de données G1 et 2x uniquement avec le jeu de données G4. Nous remarquons que l'écart entre DISCAN et ppSCAN dépend principalement de la taille du jeu de données utilisé. Par exemple, avec le jeu de données G1, l'écart entre DISCAN et ppSCAN atteint 20x, alors qu'il est réduit à 11x avec le jeu de données G4. Cela peut s'expliquer par l'étape d'élagage de pSCAN, qui dispense plusieurs calculs de similarité lors de l'étape de clustering. Il est important de mentionner que DISCAN est une implémentation distribuée de SCAN, ce qui n'est pas le cas des autres algorithmes
étudiés, car ils sont centralisés. Cela entraîne des coûts supplémentaires liés à la distribution des données, à la synchronisation et à la communication. La Figure 4.2 montre également qu'avec des configurations matérielles modestes, seul DISCAN peut passer à l'échelle avec de grands graphes comme G5 et G6.

### 4.5.2 Temps de réponse et clustering incrémental

Dans un premier temps, nous avons commencé par exécuter tous les algorithmes sur les graphes utilisés. Ensuite, nous avons périodiquement ajouté de nouveaux lots de mises à jour de différentes tailles. La Figure 4.3 montre le temps d'exécution des algorithmes testés avec différents graphes. Dans tous les graphes utilisés, DISCAN est surpassé par les autres algorithmes, à l'exception de pSCAN qui ne supporte pas le graphe G5. Malgré que pSCAN et ppSCAN réexécutent le clustering à partir de zéro, ils sont plus rapides que DISCAN dans le cas de G2, et ont un temps proche dans le cas de G3. Dans le cas de G4, DISCAN présente initialement un meilleur comportement que pSCAN et ppSCAN. En fait, ppSCAN et pSCAN sont plus rapides que DISCAN, mais l'écart de temps d'exécution commence à se réduire entre G2 et G4. Cependant, lorsque nous ajoutons un nouveau lot aux graphes initiaux, DISCAN devient plus rapide que pSCAN et ppSCAN. Dans le cas de G3, la Figure 4.3 montre un écart de 2x entre DISCAN et pSCAN et un temps d'exécution presque proche de DISCAN et ppSCAN. De plus, l'écart entre DISCAN et pSCAN commence à augmenter, pour finalement atteindre 3x, et 10% entre DISCAN et ppSCAN.

### 4.5.3 Scalabilité de DISCAN

La Figure 4.4 montre la scalabilité de DISCAN par rapport au nombre de nœuds de calcul, avec les ensembles de données G2 et G3, et pour différents lots de mise à jour en utilisant les paramètres par défaut ($\epsilon$=0,5 et $\mu$=3).

Dans l'ensemble, le nombre de workers affecte le temps d'exécution en fonction de la taille de l'ensemble de données utilisé et du nombre de mises à jour. Dans la Figure 4.4 avec le jeu de données G2, toutes les courbes ont presque la même forme. Le temps de réponse est faible avec 2 à 4 workers, mais ce n'est pas toujours valable, car cette amélioration dépend du nombre de
<figure><img src="image_17.png" /><figcaption>FIGURE 4.3 – Impact du nombre de mises à jour sur le temps de traitement de *pSCAN*, *ppSCAN* et *DISCAN* ($\epsilon$=0.5, $\mu$=3). [Inoubli et al., 2022]</figcaption></figure>

mises à jour. Les améliorations sont comprises entre 10% et 50%, respectivement, pour les mises
à jour 2000 et 10000. Ensuite, les courbes croissent jusqu'à 8 workers, puis redescendent. Dans
le cas du jeu de données G3, la scalabilité devient très élevée. Le temps de réponse diminue en
fonction du nombre de workers. Cette amélioration est d'environ 30% et 40% selon le nombre
de mises à jour. Ce comportement peut s'expliquer par le nombre de sommets et de clusters
affectés. Lorsque ce nombre est petit, les ressources nécessaires (par exemple, les workers) sont
petites. Néanmoins, avec de nombreux workers, le temps de traitement de DISCAN devient élevé
en raison du coût de communication.

Des expérimentations supplémentaires de la méthode DISCAN (exactitude de la méthode, impact du partitionnement, impact de la taille du lot et des types d'arêtes de mise à jour sur les performances de la méthode) sont accessibles dans [Inoubli et al., 2022].

## 4.6 Discussion et conclusions

Dans ce chapitre, nous avons présenté nos approches distribuées d'analyse de grands graphes complexes et dynamiques. Tout d'abord, nous avons présenté BLADYG, une approche générique pour le calcul distribué sur des grands graphes dynamiques. BLADYG a montré son efficacité et son applicabilité pour la résolution de plusieurs problèmes comme le clustering distribué et
<figure><img src="image_18.png" /><figcaption>FIGURE 4.4 – Impact du nombre de workers sur le temps de traitement de DISCAN (ε=0.5, μ=3). [Inoubli et al., 2022]</figcaption></figure>

incrémental des grands graphes (voir Section 4.4), la recherche des régions les plus cohérentes dans des graphes dynamiques [Aridhi et al., 2016a] et le partitionnement de graphes dynamiques à grande échelle [Sakouhi et al., 2016]. Cependant, BLADYG présente certaines limitations comme la quantité importante de données/messages échangés entre les machines distribuées ou aussi sa dépendance aux méthodes de partitionnement de graphes existantes.

Nous avons présenté aussi dans ce chapitre la méthode DISCAN pour le clustering distribué et incrémental des grands graphes. DISCAN a été évaluée et comparée avec des méthodes de clustering à grande échelle et a montré son efficacité. Cependant, DISCAN présente quelques limitations comme la méthode de partitionnement utilisée qui peut engendrer un nombre très élevé de nœuds en frontière et donc un temps de traitement plus important. Une autre piste d'amélioration de DISCAN consiste à utiliser une mémoire partagée à la place d'une communication par transmission de messages entre les workers dans le but de diminuer la consommation de ressources de bande passante et par conséquent diminuer le temps de calcul.
# Chapitre 5

## Apprentissage de plongements dans les grands graphes de connaissances distribués

### 5.1 Introduction

En raison de la taille importante des graphes de connaissances (KG) du monde réel, une seule unité de calcul n'est pas suffisante pour stocker un KG et apprendre les plongements en un temps raisonnable. Dans ce contexte, il serait intéressant d'implémenter des méthodes de plongement de graphes de connaissances (ou Knowledge Graph Embedding (KGE)) dans un environnement distribué où un KG est distribué sur un ensemble de machines et les plongements seront appris sur les machines en parallèle. À ce jour, quelques frameworks distribués existent dans la littérature pour l'apprentissage de plongements géométriques, tels que GraphVite [Zhu et al., 2019], Pytorch-BigGraph (PBG) [Lerer et al., 2019] et DGL-KE [Zheng et al., 2020]. GraphVite et PBG utilisent l'API PyTorch-Distributed pour mettre en oeuvre un réseau de communication et d'échange de données. Cependant, l'utilisation des APIs de bas niveau est une tâche difficile pour le développement et le déploiement [Sheikh et al., 2022a]. Récemment, Moritz et al. [Moritz et al., 2018a] ont développé la plateforme Ray pour faciliter le développement et le déploiement d'applications distribuées de manière simple en masquant les détails de bas niveau du développement et du