To see the other types of publications on this topic, follow the link: Graph embeddings.
Dissertations / Theses on the topic 'Graph embeddings'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Graph embeddings.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Labelle, François. "Graph embeddings and approximate graph coloring." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0031/MQ64386.pdf.
Full text
2
Djuphammar, Felix. "Efficient graph embeddings with community detection." Thesis, Umeå universitet, Institutionen för fysik, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-185134.
Full textAbstract:
Networks are useful when modeling interactions in real-world systems based on relational data. Since networks often contain thousands or millions of nodes and links, analyzing and exploring them requires powerful visualizations. Presenting the network nodes in a map-like fashion provides a large scale overview of the data while also providing specific details. A suite of algorithms can compute an appropriate layout of all nodes for the visualization. However, these algorithms are computationally expensive when applied to large networks because they must repeatedly derive relations between every node and every other node, leading to quadratic scaling. Also, the available implementations compute the layout from the raw data instead of the network, making customization difficult. In this thesis, I introduce a modular algorithm that removes the need to consider all node pairs by approximating groups of pairwise relations. The groups are determined by clustering the network into densely connected groups of nodes with a community-detection algorithm. The implementation accepts a network as input and returns the layout coordinates, enabling modular and straightforward integration in a data analysis pipeline. The approximations improve the new algorithm's scaling to an order of 2N1.5 compared to the original N2. For a network with one million nodes, this scaling improvement gives a 500-fold performance boost such that a computation that previously took one week now completes in about 20 minutes.
3
PALUMBO, ENRICO. "Knowledge Graph Embeddings for Recommender Systems." Doctoral thesis, Politecnico di Torino, 2020. http://hdl.handle.net/11583/2850588.
Full text
4
Jenkins, Peter. "Partial graph design embeddings and related problems /." [St. Lucia, Qld.], 2005. http://www.library.uq.edu.au/pdfserve.php?image=thesisabs/absthe18945.pdf.
Full text
5
Turner, Bethany. "Embeddings of Product Graphs Where One Factor is a Hypercube." VCU Scholars Compass, 2011. http://scholarscompass.vcu.edu/etd/2455.
Full textAbstract:
Voltage graph theory can be used to describe embeddings of product graphs if one factor is a Cayley graph. We use voltage graphs to explore embeddings of various products where one factor is a hypercube, describing some minimal and symmetrical embeddings. We then define a graph product, the weak symmetric difference, and illustrate a voltage graph construction useful for obtaining an embedding of the weak symmetric difference of an arbitrary graph with a hypercube.
6
Zhang, Zheng. "Explorations in Word Embeddings : graph-based word embedding learning and cross-lingual contextual word embedding learning." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS369/document.
Full textAbstract:
Les plongements lexicaux sont un composant standard des architectures modernes de traitement automatique des langues (TAL). Chaque fois qu'une avancée est obtenue dans l'apprentissage de plongements lexicaux, la grande majorité des tâches de traitement automatique des langues, telles que l'étiquetage morphosyntaxique, la reconnaissance d'entités nommées, la recherche de réponses à des questions, ou l'inférence textuelle, peuvent en bénéficier. Ce travail explore la question de l'amélioration de la qualité de plongements lexicaux monolingues appris par des modèles prédictifs et celle de la mise en correspondance entre langues de plongements lexicaux contextuels créés par des modèles préentraînés de représentation de la langue comme ELMo ou BERT.Pour l'apprentissage de plongements lexicaux monolingues, je prends en compte des informations globales au corpus et génère une distribution de bruit différente pour l'échantillonnage d'exemples négatifs dans word2vec. Dans ce but, je précalcule des statistiques de cooccurrence entre mots avec corpus2graph, un paquet Python en source ouverte orienté vers les applications en TAL : il génère efficacement un graphe de cooccurrence à partir d'un grand corpus, et lui applique des algorithmes de graphes tels que les marches aléatoires. Pour la mise en correspondance translingue de plongements lexicaux, je relie les plongements lexicaux contextuels à des plongements de sens de mots. L'algorithme amélioré de création d'ancres que je propose étend également la portée des algorithmes de mise en correspondance de plongements lexicaux du cas non-contextuel au cas des plongements contextuelsWord embeddings are a standard component of modern natural language processing architectures. Every time there is a breakthrough in word embedding learning, the vast majority of natural language processing tasks, such as POS-tagging, named entity recognition (NER), question answering, natural language inference, can benefit from it. This work addresses the question of how to improve the quality of monolingual word embeddings learned by prediction-based models and how to map contextual word embeddings generated by pretrained language representation models like ELMo or BERT across different languages.For monolingual word embedding learning, I take into account global, corpus-level information and generate a different noise distribution for negative sampling in word2vec. In this purpose I pre-compute word co-occurrence statistics with corpus2graph, an open-source NLP-application-oriented Python package that I developed: it efficiently generates a word co-occurrence network from a large corpus, and applies to it network algorithms such as random walks. For cross-lingual contextual word embedding mapping, I link contextual word embeddings to word sense embeddings. The improved anchor generation algorithm that I propose also expands the scope of word embedding mapping algorithms from context independent to contextual word embeddings
7
Krombholz, Martin Rudolf Arne. "Proof theory of graph minors and tree embeddings." Thesis, University of Leeds, 2018. http://etheses.whiterose.ac.uk/20834/.
Full textAbstract:
This thesis explores metamathematical properties of theorems appearing in the Graph Minors series. A number of these theorems have been known to have very high proof-theoretic strength, but an upper bound on many of them, including the graph minor theorem, had never been proved. We give such upper bounds, by showing that any proofs in the Graph Minors series can be carried out within a system of Pi^1_1-comprehension augmented with induction and bar-induction principles for certain classes of formulas. This establishes a narrow corridor for the possible proof-theoretic strength of many strong combinatorial principles, including the graph minor theorem, immersion theorem, theorems about patchwork containment, and various restrictions, extensions and labelled versions of these theorems. We also determine the precise proof-theoretic strength of some restrictions of the graph minor theorem, and show that they are equivalent to other restricted versions that had been considered before. Finally, we present a combinatorial theorem employing ordinal labelled trees ordered by embedding with gap-condition that may additionally have well-quasi-ordered labels on the vertices, which turns out not to be provable in the theory Pi^1_1-CA. This result suggests a potential for raising the lower bounds of the immersion theorem, and the thesis concludes by outlining this possibility and other avenues for further research.
8
Brunet, Richard Carleton University Dissertation Mathematics. "On the homotopy of polygons in graph embeddings." Ottawa, 1993.
Find full text
9
Potter, John R. "Pseudo-triangulations on closed surfaces." Worcester, Mass. : Worcester Polytechnic Institute, 2008. http://www.wpi.edu/Pubs/ETD/Available/etd-021408-102227/.
Full text
10
Brooks, Eric B. "On the Embeddings of the Semi-Strong Product Graph." VCU Scholars Compass, 2015. http://scholarscompass.vcu.edu/etd/3811.
Full textAbstract:
Over the years, a lot has been written about the three more common graph products (Cartesian product, Direct product and the Strong product), as all three of these are commutative products. This thesis investigates a non-commutative product graph, H, G, we call the Semi-Strong graph product, also referred in the literature as the Augmented Tensor and/or the Strong Tensor. We will start by discussing its basic properties and then focus on embeddings where the second factor, G, is a regular graph. We will use permutation voltage graphs and their graph coverings to compute the minimum genus for several families of graphs. The results follow work started first by A T White [12], extended by Ghidewon Abay Asmerom [1],[2], and follows the lead of Pisanski [9]. The strategy we use starts with an embedding of a graph H and then modifying H creating a pseudograph H*. H* is a voltage graph whose covering is HxG. Given the graph product HxG, where G is a regular graph and H meets certain conditions, we will use the embedding of H to study topological properties, particularly the surface on which HxG is minimally embedded.
11
Jagtap, Surabhi. "Multilayer Graph Embeddings for Omics Data Integration in Bioinformatics." Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPAST014.
Full textAbstract:
Les systèmes biologiques sont composés de biomolécules en interaction à différents niveaux moléculaires. D’un côté, les avancées technologiques ont facilité l’obtention des données omiques à ces divers niveaux. De l’autre, de nombreuses questions se posent, pour donner du sens et élucider les interactions importantes dans le flux d’informations complexes porté par cette énorme variété et quantité des données multi-omiques. Les réponses les plus satisfaisantes seront celles qui permettront de dévoiler les mécanismes sous-jacents à la condition biologique d’intérêt. On s’attend souvent à ce que l’intégration de différents types de données omiques permette de mettre en lumière les changements causaux potentiels qui conduisent à un phénotype spécifique ou à des traitements ciblés. Avec les avancées récentes de la science des réseaux, nous avons choisi de traiter ce problème d’intégration en représentant les données omiques à travers les graphes. Dans cette thèse, nous avons développé trois modèles à savoir BraneExp, BraneNet et BraneMF pour l’apprentissage d’intégrations de noeuds à partir de réseaux biologiques multicouches générés à partir de données omiques. Notre objectif est de résoudre divers problèmes complexes liés à l’intégration de données multiomiques, en développant des méthodes expressives et évolutives capables de tirer parti de la riche sémantique structurelle latente des réseaux du monde réelBiological systems are composed of interacting bio-molecules at different molecular levels. With the advent of high-throughput technologies, omics data at their respective molecular level can be easily obtained. These huge, complex multi-omics data can be useful to provide insights into the flow of information at multiple levels, unraveling the mechanisms underlying the biological condition of interest. Integration of different omics data types is often expected to elucidate potential causative changes that lead to specific phenotypes, or targeted treatments. With the recent advances in network science, we choose to handle this integration issue by representing omics data through networks. In this thesis, we have developed three models, namely BraneExp, BraneNet, and BraneMF, for learning node embeddings from multilayer biological networks generated with omics data. We aim to tackle various challenging problems arising in multi-omics data integration, developing expressive and scalable methods capable of leveraging rich structural semantics of realworld networks
12
Wappler, Markus. "On Graph Embeddings and a new Minor Monotone Graph Parameter associated with the Algebraic Connectivity of a Graph." Doctoral thesis, Universitätsbibliothek Chemnitz, 2013. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-115518.
Full textAbstract:
We consider the problem of maximizing the second smallest eigenvalue of the weighted Laplacian of a (simple) graph over all nonnegative edge weightings with bounded total weight.
We generalize this problem by introducing node significances and edge lengths.
We give a formulation of this generalized problem as a semidefinite program.
The dual program can be equivalently written as embedding problem. This is fifinding an embedding of the n nodes of the graph in n-space so that their barycenter is at the origin, the distance between adjacent nodes is bounded by the respective edge length, and the embedded nodes are spread as much as possible. (The sum of the squared norms is maximized.)
We proof the following necessary condition for optimal embeddings. For any separator of the graph at least one of the components fulfills the following property: Each straight-line segment between the origin and an embedded node of the component intersects the convex hull of the embedded nodes of the separator.
There exists always an optimal embedding of the graph whose dimension is bounded by the tree-width of the graph plus one.
We defifine the rotational dimension of a graph. This is the minimal dimension k such that for all choices of the node significances and edge lengths an optimal embedding of the graph can be found in k-space.
The rotational dimension of a graph is a minor monotone graph parameter.
We characterize the graphs with rotational dimension up to two.
13
Ragusa, Giorgio. "Graph designs." Doctoral thesis, Università di Catania, 2013. http://hdl.handle.net/10761/1314.
Full text
14
Whalen, Peter. "Pfaffian orientations, flat embeddings, and Steinberg's conjecture." Diss., Georgia Institute of Technology, 2014. http://hdl.handle.net/1853/52207.
Full textAbstract:
The first result of this thesis is a partial result in the direction of Steinberg's Conjecture. Steinberg's Conjecture states that any planar graph without cycles of length four or five is three colorable. Borodin, Glebov, Montassier, and Raspaud showed that planar graphs without cycles of length four, five, or seven are three colorable and Borodin and Glebov showed that planar graphs without five cycles or triangles at distance at most two apart are three colorable. We prove a statement that implies the first of these theorems and is incomparable with the second: that any planar graph with no cycles of length four through six or cycles of length seven with incident triangles distance exactly two apart are three colorable.
The third and fourth chapters of this thesis are concerned with the study of Pfaffian orientations. A theorem proved by William McCuaig and, independently, Neil Robertson, Paul Seymour, and Robin Thomas provides a good characterization for whether or not a bipartite graph has a Pfaffian orientation as well as a polynomial time algorithm for that problem. We reprove this characterization and provide a new algorithm for this problem. In Chapter 3, we generalize a preliminary result needed to reprove this theorem. Specifically, we show that any internally 4-connected, non-planar bipartite graph contains a subdivision of K3,3 in which each path has odd length. In Chapter 4, we make use of this result to provide a much shorter proof using elementary methods of this characterization.
In the fourth and fifth chapters we investigate flat embeddings. A piecewise-linear embedding of a graph in 3-space is flat if every cycle of the graph bounds a disk disjoint from the rest of the graph. We provide a structural theorem for flat embeddings that indicates how to build them from small pieces in Chapter 5. In Chapter 6, we present a class of flat graphs that are highly non-planar in the sense that, for any fixed k, there are an infinite number of members of the class such that deleting k vertices leaves the graph non-planar.
15
Prutkin, Roman [Verfasser], and D. [Akademischer Betreuer] Wagner. "Graph Embeddings Motivated by Greedy Routing / Roman Prutkin ; Betreuer: D. Wagner." Karlsruhe : KIT-Bibliothek, 2018. http://d-nb.info/1153828650/34.
Full text
16
Chen, Xiaofeng. "Plane Permutations and their Applications to Graph Embeddings and Genome Rearrangements." Diss., Virginia Tech, 2017. http://hdl.handle.net/10919/77535.
Full textAbstract:
Maps have been extensively studied and are important in many research fields. A map is a 2-cell embedding of a graph on an orientable surface. Motivated by a new way to read the information provided by the skeleton of a map, we introduce new objects called plane permutations. Plane permutations not only provide new insight into enumeration of maps and related graph embedding problems, but they also provide a powerful framework to study less related genome rearrangement problems.
As results, we refine and extend several existing results on enumeration of maps by counting plane permutations filtered by different criteria. In the spirit of the topological, graph theoretical study of graph embeddings, we study the behavior of graph embeddings under local changes. We obtain a local version of the interpolation theorem, local genus distribution as well as an easy-to-check necessary condition for a given embedding to be of minimum genus. Applying the plane permutation paradigm to genome rearrangement problems, we present a unified simple framework to study transposition distances and block-interchange distances of permutations as well as reversal distances of signed permutations. The essential idea is associating a plane permutation to a given permutation or signed permutation to sort, and then applying the developed plane permutation theory.Ph. D.
17
Yandrapally, Aruna Harini. "Combining Node Embeddings From Multiple Contexts Using Multi Dimensional Scaling." University of Cincinnati / OhioLINK, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1627658906149105.
Full text
18
Peng, Richard. "Algorithm Design Using Spectral Graph Theory." Research Showcase @ CMU, 2013. http://repository.cmu.edu/dissertations/277.
Full textAbstract:
Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. Laplace’s equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics. Due to the recent discovery of very fast solvers for these equations, they are also becoming increasingly useful in combinatorial optimization, computer vision, computer graphics, and machine learning.
In this thesis, we develop highly efficient and parallelizable algorithms for solving linear systems involving graph Laplacian matrices. These solvers can also be extended to symmetric diagonally dominant matrices and M-matrices, both of which are closely related to graph Laplacians. Our algorithms build upon two decades of progress on combinatorial preconditioning, which connects numerical and combinatorial algorithms through spectral graph theory. They in turn rely on tools from numerical analysis, metric embeddings, and random matrix theory.
We give two solver algorithms that take diametrically opposite approaches. The first is motivated by combinatorial algorithms, and aims to gradually break the problem into several smaller ones. It represents major simplifications over previous solver constructions, and has theoretical running time comparable to sorting. The second is motivated by numerical analysis, and aims to rapidly improve the algebraic connectivity of the graph. It is the first highly efficient solver for Laplacian linear systems that parallelizes almost completely.
Our results improve the performances of applications of fast linear system solvers ranging from scientific computing to algorithmic graph theory. We also show that these solvers can be used to address broad classes of image processing tasks, and give some preliminary experimental results.
19
Wappler, Markus [Verfasser], Christoph [Akademischer Betreuer] Helmberg, and Franz [Gutachter] Rendl. "On Graph Embeddings and a new Minor Monotone Graph Parameter associated with the Algebraic Connectivity of a Graph / Markus Wappler ; Gutachter: Franz Rendl ; Betreuer: Christoph Helmberg." Chemnitz : Universitätsbibliothek Chemnitz, 2013. http://d-nb.info/1214245757/34.
Full text
20
Muller, Carole. "Minor-closed classes of graphs: Isometric embeddings, cut dominants and ball packings." Doctoral thesis, Universite Libre de Bruxelles, 2021. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/331629.
Full textAbstract:
Une classe de graphes est close par mineurs si, pour tout graphe dans la classe et tout mineur de ce graphe, le mineur est ́egalement dans la classe. Par un fameux th ́eor`eme de Robertson et Seymour, nous savons que car- act ́eriser une telle classe peut ˆetre fait `a l’aide d’un nombre fini de mineurs exclus minimaux. Ceux-ci sont des graphes qui n’appartiennent pas `a la classe et qui sont minimaux dans le sens des mineurs pour cette propri ́et ́e.Dans cette thèse, nous étudions trois problèmes à propos de classes de graphes closes par mineurs. Les deux premiers sont reliés à la caractérisation de certaines classes de graphes, alors que le troisième étudie une relation de “packing-covering” dans des graphes excluant un mineur.Pour le premier problème, nous étudions des plongements isométriques de graphes dont les arêtes sont pondérées dans des espaces métriques. Principalement, nous nous intêressons aux espaces ell_2 et ell_∞. E ́tant donné un graphe pondéré, un plongement isométrique associe à chaque sommet du graphe un vecteur dans l’autre espace de sorte que pour chaque arête du graphe le poids de celle-ci est égal à la distance entre les vecteurs correspondant à ses sommets. Nous disons qu’une fonction de poids sur les arêtes est une fonction de distances réalisable s’il existe un tel plongement. Le paramètre f_p(G) détermine la dimension k minimale d’un espace ell_p telle que toute fonction de distances réalisable de G peut être plongée dans ell_p^k. Ce paramètre est monotone dans le sens des mineurs. Nous caractérisons les graphes tels que f_p(G) a une grande valeur en termes de mineurs inévitables pour p = 2 et p = ∞. Une famille de graphes donne des mineurs inévitables pour un invariant monotone pour les mineurs, si ces graphes “expliquent” pourquoi l’invariant est grand.Le deuxième problème étudie les mineurs exclus minimaux pour la classe de graphes avec φ(G) borné par une constante k, où φ(G) est un paramètre lié au dominant des coupes d’un graphe G. Ce polyèdre contient tous les points qui, composante par composante, sont plus grands ou égaux à une combination convexe des vecteurs d’incidence de coupes dans G. Le paramètre φ(G) est égal au membre de droite maximum d’une description linéaire du dominant des coupes de G en forme entière minimale. Nous étudions les mineurs exclus minimaux pour la propriété φ(G) <= 4 et montrons une nouvelle borne sur φ(G) en termes du “vertex cover number”.Le dernier problème est d’un autre type. Nous étudions une relation de “packing-covering” dans les classes de graphes excluant un mineur. Étant donné un graphe G, une boule de centre v et de rayon r est l’ensemble de tous les sommets de G qui sont à distance au plus r de v. Pour un graphe G et une collection de boules donnés nous pouvons définir un hypergraphe H dont les sommets sont ceux de G et les arêtes correspondent aux boules de la collection. Il est bien connu que dans l’hypergraphe H, le “transversal number” τ(H) vaut au moins le “packing number” ν(H). Nous montrons une borne supérieure sur ν(H) qui est linéaire en τ(H), résolvant ainsi un problème ouvert de Chepoi, Estellon et Vaxès.A class of graphs is closed under taking minors if for each graph in the class and each minor of this graph, the minor is also in the class. By a famous result of Robertson and Seymour, we know that characterizing such a class can be done by identifying a finite set of minimal excluded minors, that is, graphs which do not belong to the class and are minor-minimal for this property.In this thesis, we study three problems in minor-closed classes of graphs. The first two are related to the characterization of some graph classes, while the third one studies a packing-covering relation for graphs excluding a minor.In the first problem, we study isometric embeddings of edge-weighted graphs into metric spaces. In particular, we consider ell_2- and ell_∞-spaces. Given a weighted graph, an isometric embedding maps the vertices of this graph to vectors such that for each edge of the graph the weight of the edge equals the distance between the vectors representing its ends. We say that a weight function on the edges of the graph is a realizable distance function if such an embedding exists. The minor-monotone parameter f_p(G) determines the minimum dimension k of an ell_p-space such that any realizable distance function of G is realizable in ell_p^k. We characterize graphs with large f_p(G) value in terms of unavoidable minors for p = 2 and p = ∞. Roughly speaking, a family of graphs gives unavoidable minors for a minor-monotone parameter if these graphs “explain” why the parameter is high.The second problem studies the minimal excluded minors of the class of graphs such that φ(G) is bounded by some constant k, where φ(G) is a parameter related to the cut dominant of a graph G. This unbounded polyhedron contains all points that are componentwise larger than or equal to a convex combination of incidence vectors of cuts in G. The parameter φ(G) is equal to the maximum right-hand side of a facet-defining inequality of the cut dominant of G in minimum integer form. We study minimal excluded graphs for the property φ(G) <= 4 and provide also a new bound of φ(G) in terms of the vertex cover number.The last problem has a different flavor as it studies a packing-covering relation in classes of graphs excluding a minor. Given a graph G, a ball of center v and radius r is the set of all vertices in G that are at distance at most r from v. Given a graph and a collection of balls, we can define a hypergraph H such that its vertices are the vertices of G and its edges correspond to the balls in the collection. It is well-known that, in the hypergraph H, the transversal number τ(H) is at least the packing number ν(H). We show that we can bound τ(H) from above by a linear function of ν(H) for every graphs G and ball collections H if the graph G excludes a minor, solving an open problem by Chepoi, Estellon et Vaxès.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
21
Sabo, Jozef. "Aplikace metody učení bez učitele na hledání podobných grafů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2021. http://www.nusl.cz/ntk/nusl-445517.
Full textAbstract:
Goal of this master's thesis was in cooperation with the company Avast to design a system, which can extract knowledge from a database of graphs. Graphs, used for data mining, describe behaviour of computer systems and they are anonymously inserted into the company's database from systems of the company's products users. Each graph in the database can be assigned with one of two labels: clean or malware (malicious) graph. The task of the proposed self-learning system is to find clusters of graphs in the graph database, in which the classes of graphs do not mix. Graph clusters with only one class of graphs can be interpreted as different types of clean or malware graphs and they are a useful source of further analysis on the graphs. To evaluate the quality of the clusters, a custom metric, named as monochromaticity, was designed. The metric evaluates the quality of the clusters based on how much clean and malware graphs are mixed in the clusters. The best results of the metric were obtained when vector representations of graphs were created by a deep learning model (variational graph autoencoder with two relation graph convolution operators) and the parameterless method MeanShift was used for clustering over vectors.
22
GARBARINO, DAVIDE. "Acknowledging the structured nature of real-world data with graphs embeddings and probabilistic inference methods." Doctoral thesis, Università degli studi di Genova, 2022. http://hdl.handle.net/11567/1092453.
Full textAbstract:
In the artificial intelligence community there is a growing consensus that real
world data is naturally represented as graphs because they can easily incorporate complexity at several levels, e.g. hierarchies or time dependencies. In this context, this thesis studies two main branches for structured data.
In the first part we explore how state-of-the-art machine learning methods can be extended to graph modeled data provided that one is able to represent graphs in vector spaces. Such extensions can be applied to analyze several kinds of real-world data and tackle different problems. Here we study the
following problems: a) understand the relational nature and evolution of websites which belong to different categories (e-commerce, academic (p.a.) and encyclopedic (forum)); b) model tennis players scores based on different game surfaces and tournaments in order to predict matches results; c) analyze preter-
m-infants motion patterns able to characterize possible neuro degenerative disorders and d) build an academic collaboration recommender system able to model academic groups and individual research interest while suggesting possible researchers to connect with, topics of interest and representative publications to external users.
In the second part we focus on graphs inference methods from data which present two main challenges: missing data and non-stationary time dependency. In particular, we study the problem of inferring Gaussian Graphical
Models in the following settings: a) inference of Gaussian Graphical Models when data are missing or latent in the context of multiclass or temporal network inference and b) inference of time-varying Gaussian Graphical Models
when data is multivariate and non-stationary. Such methods have a natural application in the composition of an optimized stock markets portfolio. Overall this work sheds light on how to acknowledge the intrinsic structure
of data with the aim of building statistical models that are able to capture the actual complexity of the real world.
23
Gronemann, Martin [Verfasser], Michael [Akademischer Betreuer] Jünger, Markus [Akademischer Betreuer] Chimani, and Bettina [Akademischer Betreuer] Speckmann. "Algorithms for Incremental Planar Graph Drawing and Two-page Book Embeddings / Martin Gronemann. Gutachter: Michael Jünger ; Markus Chimani ; Bettina Speckmann." Köln : Universitäts- und Stadtbibliothek Köln, 2015. http://d-nb.info/1076864759/34.
Full text
24
Holmström, Oskar. "Exploring Transformer-Based Contextual Knowledge Graph Embeddings : How the Design of the Attention Mask and the Input Structure Affect Learning in Transformer Models." Thesis, Linköpings universitet, Artificiell intelligens och integrerade datorsystem, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-175400.
Full textAbstract:
The availability and use of knowledge graphs have become commonplace as a compact storage of information and for lookup of facts. However, the discrete representation makes the knowledge graph unavailable for tasks that need a continuous representation, such as predicting relationships between entities, where the most probable relationship needs to be found. The need for a continuous representation has spurred the development of knowledge graph embeddings. The idea is to position the entities of the graph relative to each other in a continuous low-dimensional vector space, so that their relationships are preserved, and ideally leading to clusters of entities with similar characteristics. Several methods to produce knowledge graph embeddings have been created, from simple models that minimize the distance between related entities to complex neural models. Almost all of these embedding methods attempt to create an accurate static representation of each entity and relation. However, as with words in natural language, both entities and relations in a knowledge graph hold different meanings in different local contexts. With the recent development of Transformer models, and their success in creating contextual representations of natural language, work has been done to apply them to graphs. Initial results show great promise, but there are significant differences in archi- tecture design across papers. There is no clear direction on how Transformer models can be best applied to create contextual knowledge graph embeddings. Two of the main differences in previous work is how the attention mask is applied in the model and what input graph structures the model is trained on. This report explores how different attention masking methods and graph inputs affect a Transformer model (in this report, BERT) on a link prediction task for triples. Models are trained with five different attention masking methods, which to varying degrees restrict attention, and on three different input graph structures (triples, paths, and interconnected triples). The results indicate that a Transformer model trained with a masked language model objective has the strongest performance on the link prediction task when there are no restrictions on how attention is directed, and when it is trained on graph structures that are sequential. This is similar to how models like BERT learn sentence structure after being exposed to a large number of training samples. For more complex graph structures it is beneficial to encode information of the graph structure through how the attention mask is applied. There also seems to be some indications that the input graph structure affects the models’ capabilities to learn underlying characteristics in the knowledge graph that is trained upon.
25
Prouteau, Thibault. "Graphs,Words, and Communities : converging paths to interpretability with a frugal embedding framework." Electronic Thesis or Diss., Le Mans, 2024. http://www.theses.fr/2024LEMA1006.
Full textAbstract:
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 sensRepresentation 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
26
Trouillon, Théo. "Modèles d'embeddings à valeurs complexes pour les graphes de connaissances." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM048/document.
Full textAbstract:
L'explosion de données relationnelles largement disponiblessous la forme de graphes de connaissances a permisle développement de multiples applications, dont les agents personnels automatiques,les systèmes de recommandation et l'amélioration desrésultats de recherche en ligne.La grande taille et l'incomplétude de ces bases de donnéesnécessite le développement de méthodes de complétionautomatiques pour rendre ces applications viables.La complétion de graphes de connaissances, aussi appeléeprédiction de liens, se doit de comprendre automatiquementla structure des larges graphes de connaissances (graphes dirigéslabellisés) pour prédire les entrées manquantes (les arêtes labellisées).Une approche gagnant en popularité consiste à représenter ungraphe de connaissances comme un tenseur d'ordre 3, etd'utiliser des méthodes de décomposition de tenseur pourprédire leurs entrées manquantes.Les modèles de factorisation existants proposent différentscompromis entre leur expressivité, et leur complexité en temps et en espace.Nous proposons un nouveau modèle appelé ComplEx, pour"Complex Embeddings", pour réconcilier expressivité etcomplexité par l'utilisation d'une factorisation en nombre complexes,dont nous explorons le lien avec la diagonalisation unitaire.Nous corroborons notre approche théoriquement en montrantque tous les graphes de connaissances possiblespeuvent être exactement décomposés par le modèle proposé.Notre approche, basées sur des embeddings complexesreste simple, car n'impliquant qu'un produit trilinéaire complexe,là où d'autres méthodes recourent à des fonctions de compositionde plus en plus compliquées pour accroître leur expressivité.Le modèle proposé ayant une complexité linéaire en tempset en espace est passable à l'échelle, tout endépassant les approches existantes sur les jeux de données de référencepour la prédiction de liens.Nous démontrons aussi la capacité de ComplEx àapprendre des représentations vectorielles utiles pour d'autres tâches,en enrichissant des embeddings de mots, qui améliorentles prédictions sur le problème de traitement automatiquedu langage d'implication entre paires de phrases.Dans la dernière partie de cette thèse, nous explorons lescapacités de modèles de factorisation à apprendre lesstructures relationnelles à partir d'observations.De part leur nature vectorielle,il est non seulement difficile d'interpréter pourquoicette classe de modèles fonctionne aussi bien,mais aussi où ils échouent et comment ils peuventêtre améliorés. Nous conduisons une étude expérimentalesur les modèles de l'état de l'art, non pas simplementpour les comparer, mais pour comprendre leur capacitésd'induction. Pour évaluer les forces et faiblessesde chaque modèle, nous créons d'abord des tâches simplesreprésentant des propriétés atomiques despropriétés des relations des graphes de connaissances ;puis des tâches représentant des inférences multi-relationnellescommunes au travers de généalogies synthétisées.À partir de ces résultatsexpérimentaux, nous proposons de nouvelles directionsde recherches pour améliorer les modèles existants,y compris ComplExThe explosion of widely available relational datain the form of knowledge graphsenabled many applications, including automated personalagents, recommender systems and enhanced web search results.The very large size and notorious incompleteness of these data basescalls for automatic knowledge graph completion methods to make these applicationsviable. Knowledge graph completion, also known as link-prediction,deals with automatically understandingthe structure of large knowledge graphs---labeled directed graphs---topredict missing entries---labeled edges. An increasinglypopular approach consists in representing knowledge graphs as third-order tensors,and using tensor factorization methods to predict their missing entries.State-of-the-art factorization models propose different trade-offs between modelingexpressiveness, and time and space complexity. We introduce a newmodel, ComplEx---for Complex Embeddings---to reconcile both expressivenessand complexity through the use of complex-valued factorization, and exploreits link with unitary diagonalization.We corroborate our approach theoretically and show that all possibleknowledge graphs can be exactly decomposed by the proposed model.Our approach based on complex embeddings is arguably simple,as it only involves a complex-valued trilinear product,whereas other methods resort to more and more complicated compositionfunctions to increase their expressiveness. The proposed ComplEx model isscalable to large data sets as it remains linear in both space and time, whileconsistently outperforming alternative approaches on standardlink-prediction benchmarks. We also demonstrateits ability to learn useful vectorial representations for other tasks,by enhancing word embeddings that improve performanceson the natural language problem of entailment recognitionbetween pair of sentences.In the last part of this thesis, we explore factorization models abilityto learn relational patterns from observed data.By their vectorial nature, it is not only hard to interpretwhy this class of models works so well,but also to understand where they fail andhow they might be improved. We conduct an experimentalsurvey of state-of-the-art models, not towardsa purely comparative end, but as a means to get insightabout their inductive abilities.To assess the strengths and weaknesses of each model, we create simple tasksthat exhibit first, atomic properties of knowledge graph relations,and then, common inter-relational inference through synthetic genealogies.Based on these experimental results, we propose new researchdirections to improve on existing models, including ComplEx
27
Lisena, Pasquale. "Knowledge-based music recommendation : models, algorithms and exploratory search." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS614.
Full textAbstract:
Représenter l'information décrivant la musique est une activité complexe, qui implique différentes sous-tâches. Ce manuscrit de thèse porte principalement sur la musique classique et étudie comment représenter et exploiter ses informations. L'objectif principal est l'étude de stratégies de représentation et de découverte des connaissances appliquées à la musique classique, dans des domaines tels que la production de base de connaissances, la prédiction de métadonnées et les systèmes de recommandation. Nous proposons une architecture pour la gestion des métadonnées de musique à l'aide des technologies du Web Sémantique. Nous introduisons une ontologie spécialisée et un ensemble de vocabulaires contrôlés pour les différents concepts spécifiques à la musique. Ensuite, nous présentons une approche de conversion des données, afin d’aller au-delà de la pratique bibliothécaire actuellement utilisée, en s’appuyant sur des règles de mapping et sur l’interconnexion avec des vocabulaires contrôlés. Enfin, nous montrons comment ces données peuvent être exploitées. En particulier, nous étudions des approches basées sur des plongements calculés sur des métadonnées structurées, des titres et de la musique symbolique pour classer et recommander de la musique. Plusieurs applications de démonstration ont été réalisées pour tester les approches et les ressources précédentesRepresenting the information about music is a complex activity that involves different sub-tasks. This thesis manuscript mostly focuses on classical music, researching how to represent and exploit its information. The main goal is the investigation of strategies of knowledge representation and discovery applied to classical music, involving subjects such as Knowledge-Base population, metadata prediction, and recommender systems. We propose a complete workflow for the management of music metadata using Semantic Web technologies. We introduce a specialised ontology and a set of controlled vocabularies for the different concepts specific to music. Then, we present an approach for converting data, in order to go beyond the librarian practice currently in use, relying on mapping rules and interlinking with controlled vocabularies. Finally, we show how these data can be exploited. In particular, we study approaches based on embeddings computed on structured metadata, titles, and symbolic music for ranking and recommending music. Several demo applications have been realised for testing the previous approaches and resources
28
Rocha, Mário. "The embedding of complete bipartite graphs onto grids with a minimum grid cutwidth." CSUSB ScholarWorks, 2003. https://scholarworks.lib.csusb.edu/etd-project/2311.
Full text
29
Bekkouch, Imad Eddine Ibrahim. "Auxiliary learning & Adversarial training pour les études des manuscrits médiévaux." Electronic Thesis or Diss., Sorbonne université, 2024. http://www.theses.fr/2024SORUL014.
Full textAbstract:
Cette thèse se situe à l'intersection de la musicologie et de l'intelligence artificielle, et vise à exploiter l'IA pour aider les musicologues dans leur travail répétitif, comme la recherche d'objets dans les manuscrits du musée. Nous avons annoté quatre nouveaux ensembles de données pour l'étude des manuscrits médiévaux : AMIMO, AnnMusiconis, AnnVihuelas et MMSD. Dans la deuxième partie, nous améliorons les performances des détecteurs d'objets en utilisant des techniques de Transfer learning et de Few Shot Object Detection.Dans la troisième partie, nous discutons d'une approche puissante de Domain Adaptation, qui est auxiliary learning, où nous formons le modèle sur la tâche cible et une tâche supplémentaire qui permet une meilleure stabilisation du modèle et réduit le over-fitting.Enfin, nous abordons l'apprentissage auto-supervisé, qui n'utilise pas de méta-données supplémentaires en tirant parti de l'approche de adversarial learning, forçant le modèle à extraire des caractéristiques indépendantes du domaineThis thesis is at the intersection of musicology and artificial intelligence, aiming to leverage AI to help musicologists with repetitive work, such as object searching in the museum's manuscripts. We annotated four new datasets for medieval manuscript studies: AMIMO, AnnMusiconis, AnnVihuelas, and MMSD. In the second part, we improve object detectors' performances using Transfer learning techniques and Few Shot Object Detection.In the third part, we discuss a powerful approach to Domain Adaptation, which is auxiliary learning, where we train the model on the target task and an extra task that allows for better stabilization of the model and reduces over-fitting.Finally, we discuss self-supervised learning, which does not use extra meta-data by leveraging the adversarial learning approach, forcing the model to extract domain-independent features
30
Besomi, Ormazábal Guido Andrés. "Tree embeddings in dense graphs." Tesis, Universidad de Chile, 2018. http://repositorio.uchile.cl/handle/2250/164009.
Full textAbstract:
Magíster en Ciencias de la Ingeniería, Mención Matemáticas AplicadasMemoria para optar al título de Ingeniero Civil Matemático
En 1995 Komlós, Sárközy y Szemerédi probaron que para cualquier $\delta>0$ y cualquier entero positivo $\Delta$, todo grafo $G$ de orden $n$, con $n$ suficientemente grande, que satisfaga $\delta(G)\geq (1+\delta)\frac{n}{2}$, contiene como subgrafo a todo árbol de $n$ vértices y grado máximo acotado por $\Delta$. En esta memoria se presentan dos posibles generalizaciones de este resultado, estableciendo condiciones suficientes para el \textit{embedding} de árboles de orden $k$ en grafos con grado mínimo al menos $(1+\delta)\frac{k}{2}$, donde $k$ es lineal en el orden del grafo anfitrión. En 1963 Erd\H{o}s y Sós conjeturaron que, dado un entero $k$, un grafo $G$ con grado promedio mayor que $k-1$ debería contener todos los árboles en $k$ aristas como subgrafos. Como consecuencia de uno de los resultados principales de esta memoria, se demuestra una versión parcial de la conjetura de Erd\H{o}s-Sós. Siguiendo la linea del \textit{embedding} de árboles en grafos con condiciones de grado mínimo, Havet, Reed, Stein y Wood conjeturaron el 2016 que todo grafo con grado mínimo al menos $\lfloor\frac{2k}{3}\rfloor$ y grado máximo al menos $k$ contiene todo árbol con $k$ aristas como subgrafo. Las técnicas aquí desarrolladas permiten, adicionalmente, probar una versión parcial de esta conjetura.
CMM - Conicyt PIA AFB170001
31
Ahmed, Algabli Shaima. "Learning the Graph Edit Distance through embedding the graph matching." Doctoral thesis, Universitat Rovira i Virgili, 2020. http://hdl.handle.net/10803/669612.
Full textAbstract:
Els gràfics són estructures de dades abstractes que s’utilitzen per modelar problemes reals amb dues entitats bàsiques: nodes i vores. Cada
node o vèrtex representa un punt d'interès rellevant d'un problema i cada vora representa la relació entre aquests punts. Es poden atribuir
nodes i vores per augmentar la precisió del model, cosa que significa que aquests atributs podrien variar des de vectors de característiques fins
a etiquetes de descripció. A causa d'aquesta versatilitat, s'han trobat moltes aplicacions en camps com la visió per ordinador, la biomèdica i
l'anàlisi de xarxa, etc., la primera part d'aquesta tesi presenta un mètode general per aprendre automàticament els costos d'edició que
comporta l'edició de gràfics. Distància. El mètode es basa en incrustar parells de gràfics i el seu mapeig de node a node de veritat terrestre en un
espai euclidià. D’aquesta manera, l’algoritme d’aprenentatge no necessita calcular cap concordança de gràfics tolerant als errors, que és
l’inconvenient principal d’altres mètodes a causa de la seva intrínseca complexitat computacional exponencial. No obstant això, el mètode
d’aprenentatge té la principal restricció que els costos d’edició han de ser constants. A continuació, posem a prova aquest mètode amb diverses
bases de dades gràfiques i també l’aplicem per realitzar el registre d’imatges. A la segona part de la tesi, aquest mètode es particularitza a la
verificació d’empremtes dactilars. Les dues diferències principals respecte a l’altre mètode són que només definim els costos d’edició de
substitució als nodes. Per tant, suposem que els gràfics no tenen arestes. I també, el mètode d’aprenentatge no es basa en una classificació
lineal sinó en una regressió lineal.Los gráficos son estructuras de datos abstractas que se utilizan para modelar problemas reales con dos entidades básicas: nodos y aristas. Cada nodo o vértice representa un punto de interés relevante de un problema, y cada borde representa la relación entre estos puntos. Se podrían atribuir nodos y bordes para aumentar la precisión del modelo, lo que significa que estos atributos podrían variar de vectores de características a etiquetas de descripción. Debido a esta versatilidad, se han encontrado muchas aplicaciones en campos como visión por computadora, biomédicos y análisis de redes, etc. La primera parte de esta tesis presenta un método general para aprender automáticamente los costos de edición involucrados en la Edición de Gráficos Distancia. El método se basa en incrustar pares de gráficos y su mapeo de nodo a nodo de verdad fundamental en un espacio euclidiano. De esta manera, el algoritmo de aprendizaje no necesita calcular ninguna coincidencia de gráfico tolerante a errores, que es el principal inconveniente de otros métodos debido a su complejidad computacional exponencial intrínseca. Sin embargo, el método de aprendizaje tiene la principal restricción de que los costos de edición deben ser constantes. Luego probamos este método con varias bases de datos de gráficos y también lo aplicamos para realizar el registro de imágenes. En la segunda parte de la tesis, este método se especializa en la verificación de huellas digitales. Las dos diferencias principales con respecto al otro método son que solo definimos los costos de edición de sustitución en los nodos. Por lo tanto, suponemos que los gráficos no tienen aristas. Y también, el método de aprendizaje no se basa en una clasificación lineal sino en una regresión lineal.
Graphs are abstract data structures used to model real problems with two basic entities: nodes and edges. Each node or vertex represents a relevant point of interest of a problem, and each edge represents the relationship between these points. Nodes and edges could be attributed to increase the accuracy of the model, which means that these attributes could vary from feature vectors to description labels. Due to this versatility, many applications have been found in fields such as computer vision, biomedics, and network analysis, and so on .The first part of this thesis presents a general method to automatically learn the edit costs involved in the Graph Edit Distance. The method is based on embedding pairs of graphs and their ground-truth node-tonode mapping into a Euclidean space. In this way, the learning algorithm does not need to compute any Error-Tolerant Graph Matching, which is the main drawback of other methods due to its intrinsic exponential computational complexity. Nevertheless, the learning method has the main restriction that edit costs have to be constant. Then we test this method with several graph databases and also we apply it to perform image registration. In the second part of the thesis, this method is particularized to fingerprint verification. The two main differences with respect to the other method are that we only define the substitution edit costs on the nodes. Thus, we assume graphs do not have edges. And also, the learning method is not based on a linear classification but on a linear regression.
32
Carroll, Douglas Edmonds. "Embedding parameterized graph classes into normed spaces." Diss., Restricted to subscribing institutions, 2007. http://proquest.umi.com/pqdweb?did=1324389171&sid=1&Fmt=2&clientId=1564&RQT=309&VName=PQD.
Full text
33
Tahraoui, Mohammed Amin. "Coloring, packing and embedding of graphs." Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00995041.
Full textAbstract:
In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.
34
Cooley, Oliver Josef Nikolaus. "Embedding Problems for Graphs and Hypergraphs." Thesis, University of Birmingham, 2010. http://etheses.bham.ac.uk//id/eprint/766/.
Full textAbstract:
This thesis deals with the problem of finding some substructure within a large graph or hypergraph. In the case of graphs, we consider the substructures consisting of fixed subgraphs or families of subgraphs, perfect graph packings and spanning subgraphs. In the case of hypergraphs we consider the substructure consisting of a hypergraph whose order is linear in the order of the large hypergraph. I will show how these problems are extensions of more basic and well-known results in graph theory. I will give full proofs of three new embedding results, two for graphs and one for hypergraphs. I will also discuss the regularity lemma for graphs and hypergraphs, an important tool which underpins these and many similar embedding results. Finally, I will also discuss graph and hypergraph Ramsey numbers, since two of the embedding results have important applications to Ramsey numbers which improve upon previously known results.
35
Treglown, Andrew Clark. "Embedding problems in graphs and hypergraphs." Thesis, University of Birmingham, 2011. http://etheses.bham.ac.uk//id/eprint/1345/.
Full textAbstract:
The first part of this thesis concerns perfect matchings and their generalisations. We determine the minimum vertex degree that ensures a perfect matching in a 3-uniform hypergraph, thereby answering a question of Hàn, Person and Schacht. We say that a graph \(G\) has a perfect \(H\)-packing (also called an \(H\) - factor) if there exists a set of disjoint copies of \(H\) in \(G\) which together cover all the vertices of \(G\). Given a graph \(H\), we determine, asymptotically, the Ore-type degree condition which ensures that a graph \(G\) has a perfect \(H\)-packing. The second part of the thesis concerns Hamilton cycles in directed graphs. We give a condition on the degree sequences of a digraph \(G\) that ensures \(G\) is Hamiltonian. This gives an approximate solution to a problem of Nash-Williams concerning a digraph analogue of Chvatal's theorem. We also show that every sufficiently large regular tournament can almost completely be decomposed into edge-disjoint Hamilton cycles. More precisely, for each \(\eta\) >0 every regular tournament \(G\) of sufficiently large order n contains at least (1/2- \(\eta\))n edge-disjoint Hamilton cycles. This gives an approximate solution to a conjecture of Kelly from 1968.
36
Randby, Scott P. "Embedding K? in 4-connected graphs /." The Ohio State University, 1991. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487759055158486.
Full text
37
Erten, Cesim. "Simultaneous embedding and visualization of graphs." Diss., The University of Arizona, 2004. http://hdl.handle.net/10150/290066.
Full textAbstract:
Graph embedding and visualization problems arise in relational information visualization. The two primary goals in graph visualization are drawings that convey the relationships in the underlying data and drawings that are aesthetically pleasing. Often, we have a series of related graphs that we would like to compare. In such cases it is also important to preserve the mental map between the drawings of different graphs so that the relationship between the graphs is clearly visible. For simultaneous drawing of graphs, we first present a linear-time algorithm to simultaneously embed a planar graph and its dual on an integer grid, so that the dual vertices are placed inside their corresponding primal faces and the dual edges cross their primal edges. The area of the display grid is (2n - 2) x (2n - 2) where n is the number of vertices in the graphs. We then present the problem of simultaneous embedding of planar graphs defined on the same set of vertices. In this case we would like to embed the graphs so that the matched vertices of the graphs are placed at the exact same locations and the individual drawings of the graphs are crossing-free. First we consider restricted classes of planar graphs such as paths, cycles, and caterpillars. We provide algorithms to embed two such graphs on small-area grids. We then show that there are some classes of planar graphs for which simultaneous embedding is not possible. We also consider a version of the problem where there is no mapping between the vertices of the graphs and we provide an algorithm to embed a planar graph and an outerplanar graph on an O(n²) x O(n²) grid. We provide heuristic algorithms for simultaneously embedding general graphs and the visualization tecniques we employ to display them. We present three heuristic embedding algorithms and three different visualizations suitable for each of the embedding algorithms. We describe our system that implements these algorithms and techniques. As a technique that helps simultaneous visualization of graphs we describe morphing. We discuss the disadvantages of a commonly used morphing technique, linear morphing, in terms of mental map preservation. Then we provide our algorithm to morph a source planar drawing into a target planar drawing smoothly and without creating any edge-crossings throughout the morph. This technique helps preserve the mental map between the different drawings.
38
Dube, Matthew P. "An Embedding Graph for 9-Intersection Topological Spatial Relations." Fogler Library, University of Maine, 2009. http://www.library.umaine.edu/theses/pdf/DubeMP2009.pdf.
Full text
39
MONDAL, DEBAJYOTI. "Embedding a Planar Graph on a Given Point Set." Springer-Verlag Berlin, 2012. http://hdl.handle.net/1993/8869.
Full textAbstract:
A point-set embedding of a planar graph G with n vertices on a set S of n points is a planar straight-line drawing of G, where each vertex of G is mapped to a distinct point of S. We prove that the point-set embeddability problem is NP-complete for 3-connected planar graphs, answering a question of Cabello [20]. We give an O(nlog^3n)-time algorithm for testing point-set embeddability of plane 3-trees, improving the algorithm of Moosa and Rahman [60]. We prove that no set of 24 points can support all planar 3-trees with 24 vertices, partially answering a question of Kobourov [55]. We compute 2-bend point-set embeddings of plane 3-trees in O(W^2) area, where W is the length of longest edge of the bounding box of S. Finally, we design algorithms for testing convex point-set embeddability of klee graphs and arbitrary planar graphs.
40
Mitropolitsky, Milko. "On the Impact of Graph Embedding on Device Placement." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-280435.
Full textAbstract:
Modern neural network (NN) models require more data and parameters in or- der to perform ever more complex tasks. When an NN model becomes too massive to fit on a single machine, it may need to be distributed across multi- ple machines. What policies should be used when distributing an NN model, and more concretely how different parts of the model should be disseminated across the various machines is called the device placement problem. Tackling the matter is the focus of this thesis.Previous approaches have required the placement policies to be created manually by human experts. Since that method does not scale well, the cur- rent efforts to tackling the device placement problem focus on automating the process using reinforcement learning (RL). Most of the RL systems contain different kinds of graph embedding modules.Our work tries to increase the knowledge about how to tackle the device placement problem by measuring and assessing the impact of graph embed- dings on the quality of the device placement policies. We compare the dif- ferent approaches in two main ways: runtime improvement and computation time. The former is a metric of how much faster is the new placement policy compared to a baseline. The latter describes how much time is required by the system to achieve that runtime improvement. In this thesis, we build on previous efforts in the device placement field in order to explore how different state-of-the-art graph embedding architectures affect device placement poli- cies. The graph embedding architectures we compare are Placeto (used as a baseline), GraphSAGE and P-GNN.In terms of runtime improvement, we achieve an increase of 23.967% when using P-GNN compared to Placeto, and 31.164% absolute improvement from the initial placement. GraphSAGE produces 1.165% better results than Placeto with the same setup. Regarding computation time, GraphSAGE has a gain of 11.560% compared to Placeto, whereas P-GNN is 6.950% slower than the baseline.Given our results, we can confirm that graph embedding architecture can have a significant impact on device placement policies and their performance. More complex graph embedding architectures that capture more data about the graph and its topology provide better runtime improvements. However, that complexity may come at the cost of the computation time required to train the placement system.Moderna neurala nätverk (NN) -modeller kräver mer data och parametrar för att utföra allt mer komplexa uppgifter. När en NN-modell blir för stor för att rymmas på en dator, kan den behöva distribueras över flera datorer. Vilka vil- kor som ska användas vid distributionen av en NN-modell, och mer konkret hur olika delar av modellen ska spridas över olika datorer kallas enhetsplats- problemet. Avhandlingen kommer att fokusera på detta problem. Tidigare till- vägagångssätt har krävt att placeringspolicyn skapas manuellt av människor med expertis i detta område. Eftersom den metoden inte går att skala upp fo- kuserar man på att hantera enhetsplaceringsproblemet genom att automatisera processen med reinforcement learning (RL). De flesta av RL-systemen inne- håller olika typer av grafinbäddningsmoduler.I arbetet försöker vi öka kunskapen om hur man hanterar problem med enhetsplacering genom att mäta och bedöma effekterna av grafinbäddningar på kvaliteten på villkoren för enhetsplacering. Vi jämför de olika metoderna på två sätt: runtime improvement and computation time. Den förstnämnda är ett värde för hur mycket snabbare den nya placeringspolicyn är i jämförelse med en baslinje. Det andra beskriver hur mycket tid som krävs av systemet för att uppnå den förbättrade runtime.Den här avhandlingen bygger på tidigare forskning inom området av enhetsplacering för att undersöka hur olika topp- moderna metoder till enhetsplaceringsprinciper. Grafinbäddningsarkitekturer som vi jämför i avhandlignen är Placeto (används som en baslinje), Graph- SAGE och P-GNN.Vi uppnår en förbättring av runtime med en ökning på 23.967% när vi använder P-GNN jämfört med Placeto och 31.164% ökning från baslinjen. GraphSAGE ger 1.165% bättre resultat än Placeto med samma installation. När det gäller beräkningstiden har GraphSAGE en förbättring på 11.560% jämfört med Placeto, medan P-GNN är 6.950% långsammare än baslinjen.Med resultaten kan vi bekräfta att grafinbäddningsarkitektur kan ha en be- tydande inverkan på enhetsplaceringsprinciper och deras prestanda. Desto mer invecklad grafinbäddningsarkitekturer fångar mer data om grafen och dess to- pologi ger runtime improvment. Däremot blir kan komplexiteten kosta i com- putation time på grund av det tid som krävs för att utbilda placeringssystemet.
41
Behzadi, Lila. "An improved spring-based graph embedding algorithm and LayoutShow, a Java environment for graph drawing." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/mq43368.pdf.
Full text
42
Fowler, Joe. "Unlabled Level Planarity." Diss., The University of Arizona, 2009. http://hdl.handle.net/10150/195812.
Full textAbstract:
Consider a graph G with vertex set V in which each of the n vertices is assigned a number from the set {1, ..., k} for some positive integer k. This assignment phi is a labeling if all k numbers are used. If phi does not assign adjacent vertices the same label, then phi partitions V into k levels. In a level drawing, the y-coordinate of each vertex matches its label and the edges are drawn strictly y-monotone. This leads to level drawings in the xy-plane where all vertices with label j lie along the line lj = {(x, j) : x in Reals} and where each edge crosses any of the k horizontal lines lj for j in [1..k] at most once. A graph with such a labeling forms a level graph and is level planar if it has a level drawing without crossings.We first consider the class of level trees that are level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). We describe which trees are ULP and provide linear-time level planar drawing algorithms for any labeling. We characterize ULP trees in terms of two forbidden subdivisions so that any other tree must contain a subtree homeomorphic to one of these. We also provide linear-time recognition algorithms for ULP trees. We then extend this characterization to all ULP graphs with five additional forbidden subdivisions, and provide linear-time recogntion and drawing algorithms for any given labeling.
43
Knox, Fiachra. "Embedding spanning structures in graphs and hypergraphs." Thesis, University of Birmingham, 2013. http://etheses.bham.ac.uk//id/eprint/4027/.
Full textAbstract:
In this thesis we prove three main results on embeddings of spanning subgraphs into graphs and hypergraphs. The first is that for log⁵⁰ n/n \ ≤ p ≤ 1-n⁻¹/⁴ log⁹ n, a binomial random graph G ~ G_n,p contains with high probability a collection of └δ(G)/2┘ edge disjoint Hamilton cycles (plus an additional edge-disjoint matching if δ(G) is odd), which confirms for this range of p a conjecture of Frieze and Krivelevich. Secondly, we show that any 'robustly expanding' graph with linear minimum degree on sufficiently many vertices contains every bipartite graph on the same number of vertices with bounded maximum degree and sublinear bandwidth. As corollaries we obtain the same result for any graph which satisfies the Ore-type condition d(x) + d(y) ≥ (1 + η)n for non-adjacent vertices x and y, or which satisfies a certain degree sequence condition. Thirdly, for γ > 0 we give a polynomial-time algorithm for determining whether or not a k-graph with minimum codegree at least (1/k + γ)n contains a perfect matching. This essentially answers a question of Rodl, Rucinski and Szemeredi. Our algorithm relies on a strengthening of a structural result of Keevash and Mycroft. Finally and additionally, we include a short note on Maker-Breaker games.
44
Okuno, Akifumi. "Studies on Neural Network-Based Graph Embedding and Its Extensions." Kyoto University, 2020. http://hdl.handle.net/2433/259075.
Full text
45
Ehard, Stefan [Verfasser]. "Embeddings and decompositions of graphs and hypergraphs / Stefan Ehard." Ulm : Universität Ulm, 2021. http://d-nb.info/1224969421/34.
Full text
46
Wåhlin, Lova. "Towards Machine Learning Enabled Automatic Design of IT-Network Architectures." Thesis, KTH, Matematisk statistik, 2019. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-249213.
Full textAbstract:
There are many machine learning techniques that cannot be performed on graph-data. Techniques such as graph embedding, i.e mapping a graph to a vector, can open up a variety of machine learning solutions. This thesis addresses to what extent static graph embedding techniques can capture important characteristics of an IT-architecture graph, with the purpose of embedding the graphs in a common euclidean vector space that can serve as the state space in a reinforcement learning setup. The metric used for evaluating the performance of the embedding is the security of the graph, i.e the time it would take for an unauthorized attacker to penetrate the IT-architecture graph. The algorithms evaluated in this work are the node embedding methods node2vec and gat2vec and the graph embedding method graph2vec. The predictive results of the embeddings are compared with two baseline methods. The results of each of the algorithms mostly display a significant predictive performance improvement compared to the baseline, where the F1 score in some cases is doubled. Indeed, the results indicate that static graph embedding methods can in fact capture some information about the security of an IT-architecture. However, no conclusion can be made whether a static graph embedding is actually the best contender for posing as the state space in a reinforcement learning framework. To make a certain conclusion other options has to be researched, such as dynamic graph embedding methods.Det är många maskininlärningstekniker som inte kan appliceras på data i form av en graf. Tekniker som graph embedding, med andra ord att mappa en graf till ett vektorrum, can öppna upp för en större variation av maskininlärningslösningar. Det här examensarbetet evaluerar hur väl statiska graph embeddings kan fånga viktiga säkerhetsegenskaper hos en IT-arkitektur som är modellerad som en graf, med syftet att användas i en reinforcement learning algoritm. Dom egenskaper i grafen som används för att validera embedding metoderna är hur lång tid det skulle ta för en obehörig attackerare att penetrera IT-arkitekturen. Algorithmerna som implementeras är node embedding metoderna node2vec och gat2vec, samt graph embedding metoden graph2vec. Dom prediktiva resultaten är jämförda med två basmetoder. Resultaten av alla tre metoderna visar tydliga förbättringar relativt basmetoderna, där F1 värden i några fall uppvisar en fördubbling. Det går alltså att dra slutsatsen att att alla tre metoder kan fånga upp säkerhetsegenskaper i en IT-arkitektur. Dock går det inte att säga att statiska graph embeddings är den bästa lösningen till att representera en graf i en reinforcement learning algoritm, det finns andra komplikationer med statiska metoder, till exempel att embeddings från dessa metoder inte kan generaliseras till data som inte var använd till träning. För att kunna dra en absolut slutsats krävs mer undersökning, till exempel av dynamiska graph embedding metoder.
47
Mihalisin, James Edward. "Polytopal digraphs and non-polytopal facet graphs /." Thesis, Connect to this title online; UW restricted, 2001. http://hdl.handle.net/1773/5760.
Full text
48
Gibert, Domingo Jaume. "Vector Space Embedding of Graphs via Statistics of Labelling Information." Doctoral thesis, Universitat Autònoma de Barcelona, 2012. http://hdl.handle.net/10803/96240.
Full textAbstract:
El reconeixement de patrons és la tasca que pretén distingir objectes entre diferents classes. Quan aquesta tasca es vol solucionar de forma automàtica un pas crucial és el com representar formalment els patrons a l'ordinador. En funció d'aquests formalismes, podem distingir entre el reconeixement estadístic i l'estructural. El primer descriu objectes com un conjunt de mesures col·locats en forma del que s'anomena un vector de característiques. El segon assumeix que hi ha relacions entre parts dels objectes que han de quedar explícitament representades i per tant fa servir estructures relacionals com els grafs per codificar la seva informació inherent. Els espais vectorials són una estructura matemàtica molt flexible que ha permès definir diverses maneres eficients d'analitzar patrons sota la forma de vectors de característiques. De totes maneres, la representació vectorial no és capaç d'expressar explícitament relacions binàries entre parts dels objectes i està restrigida a mesurar sempre, independentment de la complexitat dels patrons, el mateix nombre de característiques per cadascun d'ells. Les representacions en forma de graf presenten la situació contrària. Poden adaptar-se fàcilment a la complexitat inherent dels patrons però introdueixen un problema d'alta complexitat computational, dificultant el disseny d'eines eficients per al procés i l'anàlisis de patrons.
Resoldre aquesta paradoxa és el principal objectiu d'aquesta tesi. La situació ideal per resoldre problemes de reconeixement de patrons seria el representar-los fent servir estructures relacionals com els grafs, i a l'hora, poder fer ús del ric repositori d'eines pel processament de dades del reconeixement estadístic. Una solució elegant a aquest problema és la de transformar el domini dels grafs en el domini dels vectors, on podem aplicar qualsevol algorisme de processament de dades. En altres paraules, assignant a cada graf un punt en un espai vectorial, automàticament tenim accés al conjunt d'algorismes del món estadístic per aplicar-los al domini dels grafs. Aquesta metodologia s'anomena graph embedding.
En aquesta tesi proposem de fer una associació de grafs a vectors de característiques de forma simple i eficient fixant l'atenció en la informació d'etiquetatge dels grafs. En particular, comptem les freqüències de les etiquetes dels nodes així com de les aretes entre etiquetes determinades. Tot i la seva localitat, aquestes característiques donen una representació prou robusta de les propietats globals dels grafs. Primer tractem el cas de grafs amb etiquetes discretes, on les característiques són sencilles de calcular. El cas continu és abordat com una generalització del cas discret, on enlloc de comptar freqüències d'etiquetes, ho fem de representants d'aquestes. Ens trobem que les representacions vectorials que proposem pateixen d'alta dimensionalitat i correlació entre components, i tractem aquests problems mitjançant algorismes de selecció de característiques. També estudiem com la diversitat de diferents representacions pot ser explotada per tal de millorar el rendiment de classificadors base en el marc d'un sistema de múltiples classificadors. Finalment, amb una extensa evaluació experimental mostrem com la metodologia proposada pot ser calculada de forma eficient i com aquesta pot competir amb altres metodologies per a la comparació de grafs.Pattern recognition is the task that aims at distinguishing objects among different classes. When such a task wants to be solved in an automatic way a crucial step is how to formally represent such patterns to the computer. Based on the different representational formalisms, we may distinguish between statistical and structural pattern recognition. The former describes objects as a set of measurements arranged in the form of what is called a feature vector. The latter assumes that relations between parts of the underlying objects need to be explicitly represented and thus it uses relational structures such as graphs for encoding their inherent information. Vector spaces are a very flexible mathematical structure that has allowed to come up with several efficient ways for the analysis of patterns under the form of feature vectors. Nevertheless, such a representation cannot explicitly cope with binary relations between parts of the objects and it is restricted to measure the exact same number of features for each pattern under study regardless of their complexity. Graph-based representations present the contrary situation. They can easily adapt to the inherent complexity of the patterns but introduce a problem of high computational complexity, hindering the design of efficient tools to process and analyze patterns. Solving this paradox is the main goal of this thesis. The ideal situation for solving pattern recognition problems would be to represent the patterns using relational structures such as graphs, and to be able to use the wealthy repository of data processing tools from the statistical pattern recognition domain. An elegant solution to this problem is to transform the graph domain into a vector domain where any processing algorithm can be applied. In other words, by mapping each graph to a point in a vector space we automatically get access to the rich set of algorithms from the statistical domain to be applied in the graph domain. Such methodology is called graph embedding. In this thesis we propose to associate feature vectors to graphs in a simple and very efficient way by just putting attention on the labelling information that graphs store. In particular, we count frequencies of node labels and of edges between labels. Although their locality, these features are able to robustly represent structurally global properties of graphs, when considered together in the form of a vector. We initially deal with the case of discrete attributed graphs, where features are easy to compute. The continuous case is tackled as a natural generalization of the discrete one, where rather than counting node and edge labelling instances, we count statistics of some representatives of them. We encounter how the proposed vectorial representations of graphs suffer from high dimensionality and correlation among components and we face these problems by feature selection algorithms. We also explore how the diversity of different embedding representations can be exploited in order to boost the performance of base classifiers in a multiple classifier systems framework. An extensive experimental evaluation finally shows how the methodology we propose can be efficiently computed and compete with other graph matching and embedding methodologies.
49
Henderson, Matthew James. "Embedding Symmetric Latin Squares and Edge-Coloured graphs." Thesis, University of Reading, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.485356.
Full textAbstract:
In this thesis the closely related problems of embedding symmetric latin rectangles and embedding properly edge-coloured complete graphs are considered. The thesis is divided into three parts. The first part is an introductio~ and survey about completing partial latin squares and embedding latin rectangles. The second part is a proof of a former conjecture of Dugdale and Hilton about embedding edge-coloured complete graphs and the third and final part is a partial generalisation of the second part to the problem of embedding symmetric latin squares.
50
Siameh, Theophilus. "Graph Analytics Methods In Feature Engineering." Digital Commons @ East Tennessee State University, 2017. https://dc.etsu.edu/etd/3307.
Full textAbstract:
High-dimensional data sets can be difficult to visualize and analyze, while data in low-dimensional space tend to be more accessible. In order to aid visualization of the underlying structure of a dataset, the dimension of the dataset is reduced. The simplest approach to accomplish this task of dimensionality reduction is by a random projection of the data. Even though this approach allows some degree of visualization of the underlying structure, it is possible to lose more interesting underlying structure within the data. In order to address this concern, various supervised and unsupervised linear dimensionality reduction algorithms have been designed, such as Principal Component Analysis and Linear Discriminant Analysis. These methods can be powerful, but often miss important non-linear structure in the data. In this thesis, manifold learning approaches to dimensionality reduction are developed. These approaches combine both linear and non-linear methods of dimension reduction.