Tesi sul tema "Plongements de graphes"

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes
This Ph. D. Manuscript is built around the notion of graph embedding. An embedding of a graph G is an application mapping the vertices of G to elements of another structure, and preserving some properties of G. There are two types of embeddings. The combinatorial embeddings map the vertices of a graph G to the vertices of a graph H. The usual property that is preserved is the adjacency between vertices. In this thesis, we consider the isometric embeddings, preserving in addition the distances between vertices. We give some structural characterizations for families of graphs isometrically embeddable in hypercubes or Hamming graphs. The topological embeddings aim at drawing a graph G on some surface. Vertices are mapped to distinct points of the surface and the edges are represented by continuous curves linking these points. Is it possible to draw a graph G so that the edges do not cross eachother ? If not, what is the minimum number of crossings of a drawing of G ? We deal with these questions on different surfaces, or in relation with some graph operations as direct product or zip product

Cette thèse s'articule autour de la notion de plongement de graphe. Un plongement de graphe consiste à envoyer les sommets d'un graphe dans une autre structure par une application qui conserve certaines propriétés à déterminer. Nous pouvons distinguer deux grandes familles de plongements. D'une part les plongements purement combinatoires qui envoient les éléments d'un graphe G dans un autre graphe H. La propriété la plus naturelle à conserver est la notion d'adjacence entre les sommets. Nous nous intéressons à la conservation d'une propriété supplémentaire : la distance entre les sommets. Nous caractérisons plusieurs familles de graphes se plongeant de cette façon dans les hypercubes ou les graphes de Hamming. Les plongements topologiques visent à représenter un graphe G sur une surface quelconque. Les sommets sont envoyés vers des points d'une surface et les arêtes vers des courbes continues entre ces points. Comment représenter un graphe afin de minimiser le nombre de croisements d'arêtes ? Nous nous posons ces questions à travers l'étude de la planarité et des nombres de croisements de certains graphes.

Executer un algorithme parallele sur un reseau de processeurs, emuler une architecture par une autre, representer des structures de donnees ou realiser physiquement en vlsi un reseau logique sont des problemes qui sont en general modelises par des problemes de plongement de graphes. En effet, un algorithme parallele peut etre represente par un graphe dans lequel les sommets representent les taches et les aretes les communications necessaires aux calculs. De la meme maniere, une architecture parallele distribuee peut etre representee par un graphe. L'objectif de la these est de proposer des algorithmes de plongements d'arbres quelconques et dynamiques dans les architectures communement utilisees telles que les grilles, les hypercubes et les reseaux de stations de travail. La these est composee des trois parties suivantes : - plongement d'arbres binaires complets et statiques : nous presentons des algorithmes de plongement d'arbres binaires dans une grille bidimensionnelle. Ces methodes de plongements concernent les arbres complets et statiques, c'est a dire dont on connait a priori la taille et la forme. - plongement deterministe d'arbres quelconques et dynamiques : nous presentons des algorithmes de plongement d'arbres quelconques et dynamiques. En d'autres termes, le plongement d'un arbre est effectue sans connaitre a priori ni sa forme ni sa taille. - plongement aleatoire d'arbres quelconques et dynamiques : les algorithmes de plongement proposes dans cette partie sont probabilistes. Afin d'analyser le comportement aleatoire de ces algorithmes, nous avons utilise des outils mathematiques issus de la theorie des chaines de markov et des resultats d'analyse numerique sur les iterations des matrices carrees. Cette analyse nous a permis la mise en uvre d'algorithmes de plongement d'arbres quelconques dans des topologies arbitraires.

Une image obtenue par IRM, c'est plus de 60 000 pixels. La plus grosse protéine connue chez l'être humain est constituée d'environ 30 000 acides aminés. On parle de données en grande dimension. En réalité, la plupart des données en grande dimension ne le sont qu'en apparence. Par exemple, de toutes les images que l'on pourrait générer aléatoirement en coloriant 256 x 256 pixels, seule une infime proportion ressemblerait à l'image IRM d'un cerveau humain. C'est ce qu'on appelle la dimension intrinsèque des données. En grande dimension, apprentissage rime donc souvent avec réduction de dimension. Il existe de nombreuses méthodes de réduction de dimension, les plus récentes pouvant être classées selon deux approches.Une première approche, connue sous le nom d'apprentissage de variétés (manifold learning) ou réduction de dimension non linéaire, part du constat que certaines lois physiques derrière les données que l'on observe ne sont pas linéaires. Ainsi, espérer expliquer la dimension intrinsèque des données par un modèle linéaire est donc parfois irréaliste. Au lieu de cela, les méthodes qui relèvent du manifold learning supposent un modèle localement linéaire.D'autre part, avec l'émergence du domaine de l'analyse statistique de formes, il y eu une prise de conscience que de nombreuses données sont naturellement invariantes à certaines symétries (rotations, permutations, reparamétrisations...), invariances qui se reflètent directement sur la dimension intrinsèque des données. Ces invariances, la géométrie euclidienne ne peut pas les retranscrire fidèlement. Ainsi, on observe un intérêt croissant pour la modélisation des données par des structures plus fines telles que les variétés riemanniennes. Une deuxième approche en réduction de dimension consiste donc à généraliser les méthodes existantes à des données à valeurs dans des espaces non-euclidiens. On parle alors d'apprentissage géométrique. Jusqu'à présent, la plupart des travaux en apprentissage géométrique se sont focalisés sur l'analyse en composantes principales.Dans la perspective de proposer une approche qui combine à la fois apprentissage géométrique et manifold learning, nous nous sommes intéressés à la méthode appelée locally linear embedding, qui a la particularité de reposer sur la notion de barycentre, notion a priori définie dans les espaces euclidiens mais qui se généralise aux variétés riemanniennes. C'est d'ailleurs sur cette même notion que repose une autre méthode appelée barycentric subspace analysis, et qui fait justement partie des méthodes qui généralisent l'analyse en composantes principales aux variétés riemanniennes. Ici, nous introduisons la notion nouvelle de plongement barycentrique, qui regroupe les deux méthodes. Essentiellement, cette notion englobe un ensemble de méthodes dont la structure rappelle celle des méthodes de réduction de dimension linéaires et non linéaires, mais où le modèle (localement) linéaire est remplacé par un modèle barycentrique -- affine.Le cœur de notre travail consiste en l'analyse de ces méthodes, tant sur le plan théorique que pratique. Du côté des applications, nous nous intéressons à deux exemples importants en apprentissage géométrique : les formes et les graphes. En particulier, on démontre que par rapport aux méthodes standard de réduction de dimension en analyse statistique des graphes, les plongements barycentriques se distinguent par leur meilleure interprétabilité. En plus des questions pratiques liées à l'implémentation, chacun de ces exemples soulève ses propres questions théoriques, principalement autour de la géométrie des espaces quotients. Parallèlement, nous nous attachons à caractériser géométriquement les plongements localement barycentriques, qui généralisent la projection calculée par locally linear embedding. Enfin, de nouveaux algorithmes d'apprentissage géométrique, novateurs dans leur approche, complètent ce travail
An MRI image has over 60,000 pixels. The largest known human protein consists of around 30,000 amino acids. We call such data high-dimensional. In practice, most high-dimensional data is high-dimensional only artificially. For example, of all the images that could be randomly generated by coloring 256 x 256 pixels, only a very small subset would resemble an MRI image of a human brain. This is known as the intrinsic dimension of such data. Therefore, learning high-dimensional data is often synonymous with dimensionality reduction. There are numerous methods for reducing the dimension of a dataset, the most recent of which can be classified according to two approaches.A first approach known as manifold learning or non-linear dimensionality reduction is based on the observation that some of the physical laws behind the data we observe are non-linear. In this case, trying to explain the intrinsic dimension of a dataset with a linear model is sometimes unrealistic. Instead, manifold learning methods assume a locally linear model.Moreover, with the emergence of statistical shape analysis, there has been a growing awareness that many types of data are naturally invariant to certain symmetries (rotations, reparametrizations, permutations...). Such properties are directly mirrored in the intrinsic dimension of such data. These invariances cannot be faithfully transcribed by Euclidean geometry. There is therefore a growing interest in modeling such data using finer structures such as Riemannian manifolds. A second recent approach to dimension reduction consists then in generalizing existing methods to non-Euclidean data. This is known as geometric learning.In order to combine both geometric learning and manifold learning, we investigated the method called locally linear embedding, which has the specificity of being based on the notion of barycenter, a notion a priori defined in Euclidean spaces but which generalizes to Riemannian manifolds. In fact, the method called barycentric subspace analysis, which is one of those generalizing principal component analysis to Riemannian manifolds, is based on this notion as well. Here we rephrase both methods under the new notion of barycentric embeddings. Essentially, barycentric embeddings inherit the structure of most linear and non-linear dimension reduction methods, but rely on a (locally) barycentric -- affine -- model rather than a linear one.The core of our work lies in the analysis of these methods, both on a theoretical and practical level. In particular, we address the application of barycentric embeddings to two important examples in geometric learning: shapes and graphs. In addition to practical implementation issues, each of these examples raises its own theoretical questions, mostly related to the geometry of quotient spaces. In particular, we highlight that compared to standard dimension reduction methods in graph analysis, barycentric embeddings stand out for their better interpretability. In parallel with these examples, we characterize the geometry of locally barycentric embeddings, which generalize the projection computed by locally linear embedding. Finally, algorithms for geometric manifold learning, novel in their approach, complete this work

L'objet de cette thèse est d'obtenir une description des plongements élémentaires (au sens de la logique du premier ordre) dans un groupe hyperbolique sans torsion. Le résultat principal décrit ces plongements en terme d'une structure définie par Sela dans sa solution au problème de Tarski: la structure de tour hyperbolique. Ainsi, si H est plongé élementairement dans un groupe hyperbolique sans torsion G, on peut obtenir G en amalgamant successivement des groupes de surfaces à bord à un produit libre de H avec des groupes libres et des groupes de surfaces sans bord. Ceci permet en corollaire de montrer qu'un sous-groupe plongé élémentairement dans un groupe libre de type fini est un facteur libre. Les techniques utilisées pour obtenir cette description sont essentiellement géométriques: actions sur des arbres réels ou simpliciaux, existence de décompositions JSJ. On s'appuie également sur des résultats d'existence d'ensembles de factorisation qui affirment que pour certains groupes A de type fini, étant donné un groupe hyperbolique sans torsion G, il existe un ensemble fini de quotients de A tel que tout morphisme non injectif de A vers G se factorise par l'un de ces quotients après précomposition par un automorphisme de A. On expose une preuve de ces résultats, y compris une version complète et détaillée du shortening argument de Rips et Sela. Le shortening argument montre, grâce à l'analyse de Rips des actions sur des arbres réels, que si une suite d'action d'un groupe A sur des espaces hyperboliques converge vers un A-arbre réel d'un certain type, alors une infinité de ces actions peuvent être raccourcies.

Ce manuscrit de thèse récapitule mes travaux de recherche sur les profils de séparation et de Poincaré. Le profil de séparation est apparu en 2012 dans un l'article fondateur de Benjamini, Schramm et Timár. La définition donnée tirait ses origines dans des travaux antérieurs, dans le domaine du calcul formel : principalement des études de Lipton et Trajan concernant les graphes planaires, et de Miller, Teng, Thurston et Vavasis concernant des graphes d'intersection. Le profil de séparation est maintenant utilisé en théorie géométrique des groupes, mon domaine de recherche, à cause de sa propriété de monotonie par plongements grossiers. Il a été généralisé par Hume, Mackay et Tessera en 2019 en une gamme continue de profils, appelés profils de Poincaré
The goal of this thesis report is to present my research concerning separation and Poincaré profiles. Separation profile first appeared in 2012 in a seminal article written by Benjamini, Schramm and Timár. This definition was based on preceding research, in the field of computer science, mainly work of Lipton and Trajan concerning planar graphs, and of Miller, Teng, Thurston and Vavasis concerning overlap graphs. The separation profile plays now a role in geometric group theory, where my personal interests lies, because of its property of monotonicity under coarse embeddings. It was generalized by Hume, Mackay and Tessera in 2019 to a spectrum of profiles, called the Poincaré profiles

Il s'agit de generaliser aux graphes plonges dans une surface de genre quelconque des resultats connus pour les cartes planaires. Les principaux resultats sont: une bijection entre les cartes de genre donne ayant n aretes et une famille de diagrammes de meme genre ayant n cordes. L'enumeration des diagrammes non isomorphes de genre 1. L'enumeration des diagrammes non isomorphes de genre maximal

L'apprentissage de représentations au travers des méthodes de plongements de mots (word embedding) et de graphes (graph embedding) permet des représentations distribuées de l'information. Ces représentations peuvent à leur tour être utilisées en entrée d'algorithmes d'apprentissage automatique. Au cours des deux dernières décennies, les tâches de plongement de nœuds et de mots sont passées d'approches par factorisation matricielle qui pouvaient être réalisées en quelques minutes à de grands modèles nécessitant des quantités toujours plus importantes de données d’apprentissage et parfois des semaines sur de grandes architectures matérielles. Toutefois, dans un contexte de réchauffement climatique où la durabilité est une préoccupation essentielle, il peut être souhaitable de revenir à des méthodes plus frugales comme elles pouvaient l’être par le passé. En outre, avec l'implication croissante des plongements dans des applications sensibles de l’apprentissage automatique (système judiciaire, santé), le besoin de représentations plus interprétables et explicables s'est manifesté. Pour favoriser l'apprentissage de représentations efficaces et l'interprétabilité, cette thèse présente Lower Dimension Bipartite Graph Framework (LDBGF), un framework de plongements de nœuds capable d’extraire une représentation vectorielle avec le même pipeline de traitement, à condition que les données proviennent d’un graphe ou de texte issu de grands corpus représentés sous forme de réseaux de cooccurrence. Dans ce cadre, nous présentons deux implémentations (SINr- NR, SINr-MF) qui tirent parti de la détection des communautés dans les réseaux pour découvrir un espace latent dans lequel les éléments (nœuds/mots) sont représentés en fonction de leurs liens avec les communautés. Nous montrons que SINr-NR et SINr-MF peuvent rivaliser avec des approches de plongements concurrentes sur des tâches telles que la prédiction des liens manquants dans les réseaux (link prediction) ou certaines caractéristiques des nœuds (centralité de degré, score PageRank). En ce qui concerne les plongements de mots, nous montrons que SINr-NR est un bon candidat pour représenter les mots en utilisant les réseaux de cooccurrences de mots. Enfin, nous démontrons l'interprétabilité de SINr-NR sur plusieurs aspects. Tout d'abord, une évaluation humaine montre que les dimensions de SINr-NR sont dans une certaine mesure interprétables. Ensuite, nous étudions la parcimonie des vecteurs. Notamment, combien un nombre réduit de dimensions peut permettre d'interpréter comment ces dernières se combinent et permettent de dégager un sens
Representation learning with word and graph embedding models allows distributed representations of information that can in turn be used in input of machine learning algorithms. Through the last two decades, the tasks of embedding graphs’ nodes and words have shifted from matrix factorization approaches that could be trained in a matter of minutes to large models requiring ever larger quantities of training data and sometimes weeks on large hardware architectures. However, in a context of global warming where sustainability is a critical concern, we ought to look back to previous approaches and consider their performances with regard to resources consumption. Furthermore, with the growing involvement of embeddings in sensitive machine learning applications (judiciary system, health), the need for more interpretable and explainable representations has manifested. To foster efficient representation learning and interpretability, this thesis introduces Lower Dimension Bipartite Graph Framework (LDBGF), a node embedding framework able to embed with the same pipeline graph data and text from large corpora represented as co-occurrence networks. Within this framework, we introduce two implementations (SINr-NR, SINr-MF) that leverage community detection in networks to uncover a latent embedding space where items (nodes/words) are represented according to their links to communities. We show that SINr-NR and SINr-MF can compete with similar embedding approaches on tasks such as predicting missing links in networks (link prediction) or node features (degree centrality, PageRank score). Regarding word embeddings, we show that SINr-NR is a good contender to represent words via word co-occurrence networks. Finally, we demonstrate the interpretability of SINr-NR on multiple aspects. First with a human evaluation that shows that SINr-NR’s dimensions are to some extent interpretable. Secondly, by investigating sparsity of vectors, and how having fewer dimensions may allow interpreting how the dimensions combine and allow sense to emerge

De nombreux systèmes complexes du monde réel peuvent être représentés par des graphes, où les nœuds représentent des entités et les liens des relations entre les paires de nœuds. La prédiction de liens (LP) est l'un des problèmes les plus intéressants et les plus anciens dans le domaine de l'exploration de graphes ; elle prédit la probabilité d'un lien entre deux nœuds non connectés. Cette thèse étudie le problème LP dans les graphes simples et les graphes de connaissances (KGs). La première partie de cette thèse se concentre sur le problème LP dans les graphes simples. Dans la première étude, des approches basées sur la similarité et sur l'encastrement sont évaluées et comparées sur des graphes simples de différents domaines. L'étude a également identifié la difficulté de fixer le seuil du score de similarité pour calculer la métrique de précision des approches basées sur la similarité et a proposé une nouvelle méthode pour calculer la métrique. Les résultats ont montré la supériorité attendue des approches basées sur l'intégration. Cependant, chaque approche basée sur la similarité s'est avérée compétitive sur des graphes aux propriétés spécifiques. Nous avons pu vérifier expérimentalement que les approches basées sur la similarité sont explicables mais manquent de généralisation, tandis que les approches basées sur l'encastrement sont générales mais non explicables. La deuxième étude tente de surmonter la limitation de l'inexplicabilité des approches basées sur l'encastrement en découvrant des connexions intéressantes entre elles et les approches basées sur la similarité. La troisième étude démontre comment les approches basées sur la similarité peuvent être assemblées pour concevoir une approche LP supervisée explicable. Il est intéressant de noter que l'étude montre des performances LP élevées pour l'approche supervisée sur différents graphes, ce qui est très satisfaisant. La deuxième partie de la thèse se concentre sur les LP dans les KGs. Un KG est représenté comme une collection de triplets RDF, (head,relation,tail) où les entités head et tail sont reliées par une relation spécifique. Le problème de LP dans un KG est formulé comme la prédiction de la tête ou de la queue manquante dans un triplet. La LP basée sur l'incorporation de KG est devenue très populaire ces dernières années, et la génération de triplets négatifs est une tâche importante dans les méthodes d'incorporation. La quatrième étude traite d'une nouvelle méthode appelée SNS pour générer des triplets négatifs de haute qualité. Nos résultats montrent une meilleure performance LP lorsque SNS est utilisé que lorsque d'autres méthodes d'échantillonnage négatif sont utilisées. La deuxième étude traite d'une nouvelle méthode d'extraction de règles neuro-symboliques et d'une stratégie d'abduction pour expliquer les LP par une approche basée sur l'intégration en utilisant les règles apprises. La troisième étude applique notre LP explicable pour développer une nouvelle approche de repositionnement des médicaments pour COVID-19. L'approche apprend un ensemble d'enchâssements d'entités et de relations dans un KG centré sur COVID-19 pour obtenir un meilleur enchâssement des éléments du graphe. Pour la première fois à notre connaissance, des méthodes de criblage virtuel sont ensuite utilisées pour évaluer les prédictions obtenues à l'aide des embeddings. L'évaluation moléculaire et les chemins explicatifs apportent de la fiabilité aux résultats de prédiction et sont de nouvelles méthodes complémentaires et réutilisables pour mieux évaluer les molécules proposées pour le repositionnement. La dernière étude propose une architecture distribuée pour l'apprentissage des KG embeddings dans des environnements distribués et parallèles. Les résultats révèlent que l'apprentissage dans l'environnement distribué proposé, par rapport à un apprentissage centralisé, réduit considérablement le temps de calcul des méthodes d'incorporation KG sans affecter les performances des LP
Many real-world complex systems can be well-represented with graphs, where nodes represent objects or entities and links/relations represent interactions between pairs of nodes. Link prediction (LP) is one of the most interesting and long-standing problems in the field of graph mining; it predicts the probability of a link between two unconnected nodes based on available information in the current graph. This thesis studies the LP problem in graphs. It consists of two parts: LP in simple graphs and LP knowledge graphs (KGs). In the first part, the LP problem is defined as predicting the probability of a link between a pair of nodes in a simple graph. In the first study, a few similarity-based and embedding-based LP approaches are evaluated and compared on simple graphs from various domains. he study also criticizes the traditional way of computing the precision metric of similarity-based approaches as the computation faces the difficulty of tuning the threshold for deciding the link existence based on the similarity score. We proposed a new way of computing the precision metric. The results showed the expected superiority of embedding-based approaches. Still, each of the similarity-based approaches is competitive on graphs with specific properties. We could check experimentally that similarity-based approaches are fully explainable but lack generalization due to their heuristic nature, whereas embedding-based approaches are general but not explainable. The second study tries to alleviate the unexplainability limitation of embedding-based approaches by uncovering interesting connections between them and similarity-based approaches to get an idea of what is learned in embedding-based approaches. The third study demonstrates how the similarity-based approaches can be ensembled to design an explainable supervised LP approach. Interestingly, the study shows high LP performance for the supervised approach across various graphs, which is competitive with embedding-based approaches.The second part of the thesis focuses on LP in KGs. A KG is represented as a collection of RDF triples, (head,relation,tail) where the head and the tail are two entities which are connected by a specific relation. The LP problem in a KG is formulated as predicting missing head or tail entities in a triple. LP approaches based on the embeddings of entities and relations of a KG have become very popular in recent years, and generating negative triples is an important task in KG embedding methods. The first study in this part discusses a new method called SNS to generate high-quality negative triples during the training of embedding methods for learning embeddings of KGs. The results we produced show better LP performance when SNS is injected into an embedding approach than when injecting state-of-the-art negative triple sampling methods. The second study in the second part discusses a new neuro-symbolic method of mining rules and an abduction strategy to explain LP by an embedding-based approach utilizing the learned rules. The third study applies the explainable LP to a COVID-19 KG to develop a new drug repurposing approach for COVID-19. The approach learns ”ensemble embeddings” of entities and relations in a COVID-19 centric KG, in order to get a better latent representation of the graph elements. For the first time to our knowledge, molecular docking is then used to evaluate the predictions obtained from drug repurposing using KG embedding. Molecular evaluation and explanatory paths bring reliability to prediction results and constitute new complementary and reusable methods for assessing KG-based drug repurposing. The last study proposes a distributed architecture for learning KG embeddings in distributed and parallel settings. The results of the study that the computational time of embedding methods improves remarkably without affecting LP performance when they are trained in the proposed distributed settings than the traditional centralized settings

Le but principal de ce manuscrit est de montrer que certaines familles de graphes sont des graphes plongeables dans l'hypercube. Un problème d'une autre nature sera traité, il concerne la partition de l'hypercube en des cycles sommet-disjoints de longueur paires. Nous prouvons que l'hypercube de dimension n peut être partitionné en k cycles sommet-disjoints si k