Tesi: "Embedding de graph"

1

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.

Testo completo

Abstract (sommario):

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 contextuels
Word 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

Gli stili APA, Harvard, Vancouver, ISO e altri

2

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

3

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

4

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

5

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

6

MONDAL, DEBAJYOTI. "Embedding a Planar Graph on a Given Point Set". Springer-Verlag Berlin, 2012. http://hdl.handle.net/1993/8869.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

7

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

8

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

9

Tahraoui, Mohammed Amin. "Coloring, packing and embedding of graphs". Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00995041.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

10

Okuno, Akifumi. "Studies on Neural Network-Based Graph Embedding and Its Extensions". Kyoto University, 2020. http://hdl.handle.net/2433/259075.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

11

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

12

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

13

PALUMBO, ENRICO. "Knowledge Graph Embeddings for Recommender Systems". Doctoral thesis, Politecnico di Torino, 2020. http://hdl.handle.net/11583/2850588.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

14

Boyer, John M. "Simplified O(n) algorithms for planar graph embedding, Kuratowski subgraph isolation, and related problems". Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2001. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp05/NQ62507.pdf.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

15

Chen, Xiaofeng. "Plane Permutations and their Applications to Graph Embeddings and Genome Rearrangements". Diss., Virginia Tech, 2017. http://hdl.handle.net/10919/77535.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

16

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

17

Luqman, Muhammad Muzzamil. "Fuzzy multilevel graph embedding for recognition, indexing and retrieval of graphic document images". Thesis, Tours, 2012. http://www.theses.fr/2012TOUR4005/document.

Testo completo

Abstract (sommario):

Cette thèse aborde le problème du manque de performance des outils exploitant des représentationsà base de graphes en reconnaissance des formes. Nous proposons de contribuer aux nouvellesméthodes proposant de tirer partie, à la fois, de la richesse des méthodes structurelles et de la rapidité des méthodes de reconnaissance de formes statistiques. Deux principales contributions sontprésentées dans ce manuscrit. La première correspond à la proposition d'une nouvelle méthode deprojection explicite de graphes procédant par analyse multi-facettes des graphes. Cette méthodeeffectue une caractérisation des graphes suivant différents niveaux qui correspondent, selon nous,aux point-clés des représentations à base de graphes. Il s'agit de capturer l'information portéepar un graphe au niveau global, au niveau structure et au niveau local ou élémentaire. Ces informationscapturées sont encapsulés dans un vecteur de caractéristiques numériques employantdes histogrammes flous. La méthode proposée utilise, de plus, un mécanisme d'apprentissage nonsupervisée pour adapter automatiquement ses paramètres en fonction de la base de graphes àtraiter sans nécessité de phase d'apprentissage préalable. La deuxième contribution correspondà la mise en place d'une architecture pour l'indexation de masses de graphes afin de permettre,par la suite, la recherche de sous-graphes présents dans cette base. Cette architecture utilise laméthode précédente de projection explicite de graphes appliquée sur toutes les cliques d'ordre 2pouvant être extraites des graphes présents dans la base à indexer afin de pouvoir les classifier.Cette classification permet de constituer l'index qui sert de base à la description des graphes etdonc à leur indexation en ne nécessitant aucune base d'apprentissage pré-étiquetées. La méthodeproposée est applicable à de nombreux domaines, apportant la souplesse d'un système de requêtepar l'exemple et la granularité des techniques d'extraction ciblée (focused retrieval)
This thesis addresses the problem of lack of efficient computational tools for graph based structural pattern recognition approaches and proposes to exploit computational strength of statistical pattern recognition. It has two fold contributions. The first contribution is a new method of explicit graph embedding. The proposed graph embedding method exploits multilevel analysis of graph for extracting graph level information, structural level information and elementary level information from graphs. It embeds this information into a numeric feature vector. The method employs fuzzy overlapping trapezoidal intervals for addressing the noise sensitivity of graph representations and for minimizing the information loss while mapping from continuous graph space to discrete vector space. The method has unsupervised learning abilities and is capable of automatically adapting its parameters to underlying graph dataset. The second contribution is a framework for automatic indexing of graph repositories for graph retrieval and subgraph spotting. This framework exploits explicit graph embedding for representing the cliques of order 2 by numeric feature vectors, together with classification and clustering tools for automatically indexing a graph repository. It does not require a labeled learning set and can be easily deployed to a range of application domains, offering ease of query by example (QBE) and granularity of focused retrieval

Gli stili APA, Harvard, Vancouver, ISO e altri

18

Siameh, Theophilus. "Graph Analytics Methods In Feature Engineering". Digital Commons @ East Tennessee State University, 2017. https://dc.etsu.edu/etd/3307.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

19

Zhu, Xiaoting. "Systematic Assessment of Structural Features-Based Graph Embedding Methods with Application to Biomedical Networks". University of Cincinnati / OhioLINK, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1592394966493963.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

20

Shanmugam, Sakthivadivel Saravanakumar. "Fast-NetMF: Graph Embedding Generation on Single GPU and Multi-core CPUs with NetMF". The Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1557162076041442.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

21

Frimodig, Matilda, e Sivertsson Tom Lanhed. "A Comparative study of Knowledge Graph Embedding Models for use in Fake News Detection". Thesis, Malmö universitet, Institutionen för datavetenskap och medieteknik (DVMT), 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:mau:diva-43228.

Testo completo

Abstract (sommario):

During the past few years online misinformation, generally referred to as fake news, has been identified as an increasingly dangerous threat. As the spread of misinformation online has increased, fake news detection has become an active line of research. One approach is to use knowledge graphs for the purpose of automated fake news detection. While large scale knowledge graphs are openly available these are rarely up to date, often missing the relevant information needed for the task of fake news detection. Creating new knowledge graphs from online sources is one way to obtain the missing information. However extracting information from unstructured text is far from straightforward. Using Natural Language Processing techniques we developed a pre-processing pipeline for extracting information from text for the purpose of creating knowledge graphs. In order to classify news as fake or not fake with the use of knowledge graphs, these need to be converted into a machine understandable format, called knowledge graph embeddings. These embeddings also allow new information to be inferred or classified based on the already existing information in the knowledge graph. Only one knowledge graph embedding model has previously been used for the purpose of fake news detection while several new models have recently been developed. We compare the performance of three different embedding models, all relying on different fundamental architectures, in the specific context of fake news detection. The models used were the geometric model TransE, the tensor decomposition model ComplEx and the deep learning model ConvKB. The results of this study shows that out of the three models, ConvKB is the best performing. However other aspects than performance need to be considered and as such these results do not necessarily mean that a deep learning approach is the most suitable for real world fake news detection.

Gli stili APA, Harvard, Vancouver, ISO e altri

22

Fowler, Joe. "Unlabled Level Planarity". Diss., The University of Arizona, 2009. http://hdl.handle.net/10150/195812.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

23

Reiß, Susanna. "Optimizing Extremal Eigenvalues of Weighted Graph Laplacians and Associated Graph Realizations". Doctoral thesis, Universitätsbibliothek Chemnitz, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-93599.

Testo completo

Abstract (sommario):

This thesis deals with optimizing extremal eigenvalues of weighted graph Laplacian matrices. In general, the Laplacian matrix of a (weighted) graph is of particular importance in spectral graph theory and combinatorial optimization (e.g., graph partition like max-cut and graph bipartition). Especially the pioneering work of M. Fiedler investigates extremal eigenvalues of weighted graph Laplacians and provides close connections to the node- and edge-connectivity of a graph. Motivated by Fiedler, Göring et al. were interested in further connections between structural properties of the graph and the eigenspace of the second smallest eigenvalue of weighted graph Laplacians using a semidefinite optimization approach. By redistributing the edge weights of a graph, the following three optimization problems are studied in this thesis: maximizing the second smallest eigenvalue (based on the mentioned work of Göring et al.), minimizing the maximum eigenvalue and minimizing the difference of maximum and second smallest eigenvalue of the weighted Laplacian. In all three problems a semidefinite optimization formulation allows to interpret the corresponding semidefinite dual as a graph realization problem. That is, to each node of the graph a vector in the Euclidean space is assigned, fulfilling some constraints depending on the considered problem. Optimal realizations are investigated and connections to the eigenspaces of corresponding optimized eigenvalues are established. Furthermore, optimal realizations are closely linked to the separator structure of the graph. Depending on this structure, on the one hand folding properties of optimal realizations are characterized and on the other hand the existence of optimal realizations of bounded dimension is proven. The general bounds depend on the tree-width of the graph. In the case of minimizing the maximum eigenvalue, an important family of graphs are bipartite graphs, as an optimal one-dimensional realization may be constructed. Taking the symmetry of the graph into account, a particular optimal edge weighting exists. Considering the coupled problem, i.e., minimizing the difference of maximum and second smallest eigenvalue and the single problems, i.e., minimizing the maximum and maximizing the second smallest eigenvalue, connections between the feasible (optimal) sets are established.

Gli stili APA, Harvard, Vancouver, ISO e altri

24

Sun, Jiankai. "Directed Graph Analysis: Algorithms and Applications". The Ohio State University, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=osu1565797455907422.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

25

Damay, Gabriel. "Dynamic Decision Trees and Community-based Graph Embeddings : towards Interpretable Machine Learning". Electronic Thesis or Diss., Institut polytechnique de Paris, 2024. http://www.theses.fr/2024IPPAT047.

Testo completo

Abstract (sommario):

L'apprentissage automatique est le domaine des sciences informatiques dont le but est de créer des modèles et des solutions à partir de données sans savoir exactement les instructions qui dirigent intrinsèquement ces modèles. Ce domaine a obtenu des résultats impressionnants mais il est l'objet le sujet d'inquiétudes en raison notamment de l'impossibilité de comprendre et d'auditer les modèles qu'il produit. L'apprentissage automatique interprétable propose une solution à ces inquiétudes en créant des modèles qui sont interprétables de façon inhérante. Cette thèse contribue à l'apprentissage automatique interprétable de deux façons.Tout d'abord, nous étudions les arbres de décision. Il s'agit d'un groupe de méthodes d'apprentissage automatique très connu et qui est interprétable par la façon même dont il est conçu. Cependant, les données réelles sont souvent dynamiques et peu d'algorithmes existent pour maintenir un arbre de décision quand des données peuvent à la fois être ajoutées et supprimées de l'ensemble d'entrainement. Nous proposons un nouvel algorithme nommé FuDyADT pour résoudre ce problème.Ensuite, quand les données sont représentées sous forme de graphe, une technique d'apprentissage automatique très commune, nommée "embedding", consiste à projeter les données sur un espace vectoriel. Ce type de méthodes est cependant non-interprétable en général. Nous proposons un nouvel algorithme d'embedding appelé Parfaite, qui est basé sur la factorisation de la matrice de PageRank personnalisé. Cet algorithme est conçu pour que ses résultats soient interprétables.Nous étudions chacun de ces algorithmes sur un plan à la fois théorique et expérimental. Nous montrons que FuDyADT est au minimum comparable aux algorithmes à l'état de l'art dans les conditions habituelles, tout en étant également capable de fonctionner dans des contextes inhabituels comme dans le cas où des données sont supprimés ou dans le cas où certaines des données sont numériques. Quant à Parfaite, il produit des dimensions d'embedding qui sont alignées avec les communautés du graphe, et qui sont donc interprétables
Machine Learning is the field of computer science that interests in building models and solutions from data without knowing exactly the set of instructions internal to these models and solutions. This field has achieved great results but is now under scrutiny for the inability to understand or audit its models among other concerns. Interpretable Machine Learning addresses these concerns by building models that are inherently interpretable. This thesis contributes to Interpretable Machine Learning in two ways.First, we study Decision Trees. This is a very popular group of Machine Learning methods for classification problems and it is interpretable by design. However, real world data is often dynamic, but few algorithms can maintain a decision tree when data can be both inserted and deleted from the training set. We propose a new algorithm called FuDyADT to solve this problem.Second, when data are represented as graphs, a very common machine learning technique called "embedding" consists in projecting them onto a vectorial space. This kind of method however is usually not interpretable. We propose a new embedding algorithm called Parfaite based on the factorization of the Personalized PageRank matrix. This algorithm is designed to provide interpretable results.We study both algorithms theoretically and experimentally. We show that FuDyADT is at least comparable to state-of-the-art algorithms in the usual setting, while also being able to handle unusual settings such as deletions of data and numerical features. Parfaite on the other hand produces embedding dimensions that align with the communities of the graph, making the embedding interpretable

Gli stili APA, Harvard, Vancouver, ISO e altri

26

Bläsius, Thomas [Verfasser], e D. [Akademischer Betreuer] Wagner. "New Approaches to Classic Graph-Embedding Problems - Orthogonal Drawings & Constrained Planarity / Thomas Bläsius. Betreuer: D. Wagner". Karlsruhe : KIT-Bibliothek, 2015. http://d-nb.info/1075809401/34.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

27

Kilinc, Ismail Ozsel. "Graph-based Latent Embedding, Annotation and Representation Learning in Neural Networks for Semi-supervised and Unsupervised Settings". Scholar Commons, 2017. https://scholarcommons.usf.edu/etd/7415.

Testo completo

Abstract (sommario):

Machine learning has been immensely successful in supervised learning with outstanding examples in major industrial applications such as voice and image recognition. Following these developments, the most recent research has now begun to focus primarily on algorithms which can exploit very large sets of unlabeled examples to reduce the amount of manually labeled data required for existing models to perform well. In this dissertation, we propose graph-based latent embedding/annotation/representation learning techniques in neural networks tailored for semi-supervised and unsupervised learning problems. Specifically, we propose a novel regularization technique called Graph-based Activity Regularization (GAR) and a novel output layer modification called Auto-clustering Output Layer (ACOL) which can be used separately or collaboratively to develop scalable and efficient learning frameworks for semi-supervised and unsupervised settings. First, singularly using the GAR technique, we develop a framework providing an effective and scalable graph-based solution for semi-supervised settings in which there exists a large number of observations but a small subset with ground-truth labels. The proposed approach is natural for the classification framework on neural networks as it requires no additional task calculating the reconstruction error (as in autoencoder based methods) or implementing zero-sum game mechanism (as in adversarial training based methods). We demonstrate that GAR effectively and accurately propagates the available labels to unlabeled examples. Our results show comparable performance with state-of-the-art generative approaches for this setting using an easier-to-train framework. Second, we explore a different type of semi-supervised setting where a coarse level of labeling is available for all the observations but the model has to learn a fine, deeper level of latent annotations for each one. Problems in this setting are likely to be encountered in many domains such as text categorization, protein function prediction, image classification as well as in exploratory scientific studies such as medical and genomics research. We consider this setting as simultaneously performed supervised classification (per the available coarse labels) and unsupervised clustering (within each one of the coarse labels) and propose a novel framework combining GAR with ACOL, which enables the network to perform concurrent classification and clustering. We demonstrate how the coarse label supervision impacts performance and the classification task actually helps propagate useful clustering information between sub-classes. Comparative tests on the most popular image datasets rigorously demonstrate the effectiveness and competitiveness of the proposed approach. The third and final setup builds on the prior framework to unlock fully unsupervised learning where we propose to substitute real, yet unavailable, parent- class information with pseudo class labels. In this novel unsupervised clustering approach the network can exploit hidden information indirectly introduced through a pseudo classification objective. We train an ACOL network through this pseudo supervision together with unsupervised objective based on GAR and ultimately obtain a k-means friendly latent representation. Furthermore, we demonstrate how the chosen transformation type impacts performance and helps propagate the latent information that is useful in revealing unknown clusters. Our results show state-of-the-art performance for unsupervised clustering tasks on MNIST, SVHN and USPS datasets with the highest accuracies reported to date in the literature.

Gli stili APA, Harvard, Vancouver, ISO e altri

28

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

29

Boschin, Armand. "Machine learning techniques for automatic knowledge graph completion". Electronic Thesis or Diss., Institut polytechnique de Paris, 2023. http://www.theses.fr/2023IPPAT016.

Testo completo

Abstract (sommario):

Un graphe de connaissances est un graphe orienté dont les nœuds sont des entités et les arêtes, typées par une relation, représentent des faits connus liant les entités. Ces graphes sont capables d'encoder une grande variété d'information mais leur construction et leur exploitation peut se révéler complexe. Historiquement, des méthodes symboliques ont permis d'extraire des règles d'interaction entre entités et relations, afin de corriger des anomalies ou de prédire des faits manquants. Plus récemment, des méthodes d'apprentissage de représentations vectorielles, ou plongements, ont tenté de résoudre ces mêmes tâches. Initialement purement algébriques ou géométriques, ces méthodes se sont complexifiées avec les réseaux de neurones profonds et ont parfois été combinées à des techniques symboliques antérieures.Dans cette thèse, on s'intéresse tout d'abord au problème de l'implémentation. En effet, la grande diversité des bibliothèques utilisées rend difficile la comparaison des résultats obtenus par différents modèles. Dans ce contexte, la bibliothèque Python TorchKGE a été développée afin de proposer un environnement unique pour l'implémentation de modèles de plongement et un module hautement efficace d'évaluation par prédiction de liens. Cette bibliothèque repose sur l'accélération graphique de calculs tensoriels proposée par PyTorch, est compatible avec les bibliothèques d'optimisation usuelles et est disponible en source ouverte.Ensuite, les travaux portent sur l'enrichissement automatique de Wikidata par typage des hyperliens liant les articles de Wikipedia. Une étude préliminaire a montré que le graphe des articles de Wikipedia est beaucoup plus dense que le graphe de connaissances correspondant dans Wikidata. Une nouvelle méthode d'entrainement impliquant les relations et une méthode d'inférence utilisant les types des entités ont été proposées et des expériences ont montré la pertinence de l'approche, y compris sur un nouveau jeu de données.Enfin, le typage automatique d'entités est exploré comme une tâche de classification hiérarchique. Ceci a mené à la conception d'une fonction d'erreur hiérarchique, utilisée pour l'entrainement de modèles tensoriels, ainsi qu'un nouveau type d'encodeur. Des expériences ont permis une bonne compréhension de l'impact que peut avoir une connaissance a priori de la taxonomie des classes sur la classification. Elles ont aussi renforcé l'intuition que la hiérarchie peut être apprise à partir des données si le jeu est suffisamment riche
A knowledge graph is a directed graph in which nodes are entities and edges, typed by a relation, represent known facts linking two entities. These graphs can encode a wide variety of information, but their construction and exploitation can be complex. Historically, symbolic methods have been used to extract rules about entities and relations, to correct anomalies or to predict missing facts. More recently, techniques of representation learning, or embeddings, have attempted to solve these same tasks. Initially purely algebraic or geometric, these methods have become more complex with deep neural networks and have sometimes been combined with pre-existing symbolic techniques.In this thesis, we first focus on the problem of implementation. Indeed, the diversity of libraries used makes the comparison of results obtained by different models a complex task. In this context, the Python library TorchKGE was developed to provide a unique setup for the implementation of embedding models and a highly efficient inference evaluation module. This library relies on graphic acceleration of tensor computation provided by PyTorch, is compatible with widespread optimization libraries and is available as open source.We then consider the automatic enrichment of Wikidata by typing the hyperlinks linking Wikipedia pages. A preliminary study showed that the graph of Wikipedia articles is much denser than the corresponding knowledge graph in Wikidata. A new training method involving relations and an inference method using entity types were proposed and experiments showed the relevance of the combined approach, including on a new dataset.Finally, we explore automatic entity typing as a hierarchical classification task. That led to the design of a new hierarchical loss used to train tensor-based models along with a new type of encoder. Experiments on two datasets have allowed a good understanding of the impact a prior knowledge of class taxonomy can have on a classifier but also reinforced the intuition that the hierarchy can be learned from the features if the dataset is large enough

Gli stili APA, Harvard, Vancouver, ISO e altri

30

Fang, Chunsheng. "Novel Frameworks for Mining Heterogeneous and Dynamic Networks". University of Cincinnati / OhioLINK, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1321369978.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

31

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

32

Helmberg, Christoph, Israel Rocha e Uwe Schwerdtfeger. "A Combinatorial Algorithm for Minimizing the Maximum Laplacian Eigenvalue of Weighted Bipartite Graphs". Universitätsbibliothek Chemnitz, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-175057.

Testo completo

Abstract (sommario):

We give a strongly polynomial time combinatorial algorithm to minimise the largest eigenvalue of the weighted Laplacian of a bipartite graph. This is accomplished by solving the dual graph embedding problem which arises from a semidefinite programming formulation. In particular, the problem for trees can be solved in time cubic in the number of vertices.

Gli stili APA, Harvard, Vancouver, ISO e altri

33

Lee, Zed Heeje. "A graph representation of event intervals for efficient clustering and classification". Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-281947.

Testo completo

Abstract (sommario):

Sequences of event intervals occur in several application domains, while their inherent complexity hinders scalable solutions to tasks such as clustering and classification. In this thesis, we propose a novel spectral embedding representation of event interval sequences that relies on bipartite graphs. More concretely, each event interval sequence is represented by a bipartite graph by following three main steps: (1) creating a hash table that can quickly convert a collection of event interval sequences into a bipartite graph representation, (2) creating and regularizing a bi-adjacency matrix corresponding to the bipartite graph, (3) defining a spectral embedding mapping on the bi-adjacency matrix. In addition, we show that substantial improvements can be achieved with regard to classification performance through pruning parameters that capture the nature of the relations formed by the event intervals. We demonstrate through extensive experimental evaluation on five real-world datasets that our approach can obtain runtime speedups of up to two orders of magnitude compared to other state-of-the-art methods and similar or better clustering and classification performance.
Sekvenser av händelsesintervall förekommer i flera applikationsdomäner, medan deras inneboende komplexitet hindrar skalbara lösningar på uppgifter som kluster och klassificering. I den här avhandlingen föreslår vi en ny spektral inbäddningsrepresentation av händelsens intervallsekvenser som förlitar sig på bipartitgrafer. Mer konkret representeras varje händelsesintervalsekvens av en bipartitgraf genom att följa tre huvudsteg: (1) skapa en hashtabell som snabbt kan konvertera en samling händelsintervalsekvenser till en bipartig grafrepresentation, (2) skapa och reglera en bi-adjacency-matris som motsvarar bipartitgrafen, (3) definiera en spektral inbäddning på bi-adjacensmatrisen. Dessutom visar vi att väsentliga förbättringar kan uppnås med avseende på klassificeringsprestanda genom beskärningsparametrar som fångar arten av relationerna som bildas av händelsesintervallen. Vi demonstrerar genom omfattande experimentell utvärdering på fem verkliga datasätt att vår strategi kan erhålla runtime-hastigheter på upp till två storlekar jämfört med andra modernaste metoder och liknande eller bättre kluster- och klassificerings- prestanda.

Gli stili APA, Harvard, Vancouver, ISO e altri

34

Liang, Jiongqian. "Human-in-the-loop Machine Learning: Algorithms and Applications". The Ohio State University, 2018. http://rave.ohiolink.edu/etdc/view?acc_num=osu1523988406039076.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

35

Bertoni, Eleonora. "Apprendimento non supervisionato di rappresentazioni e legami di similarità tra eventi menzionati nella letteratura biomedica". Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2021. http://amslaurea.unibo.it/24748/.

Testo completo

Abstract (sommario):

L'estrazione automatica degli eventi biomedici dalla letteratura scientifica ha catturato un forte interesse nel corso degli ultimi anni, dimostrandosi in grado di riconoscere interazioni complesse e semanticamente ricche espresse all'interno del testo. Purtroppo però, esistono davvero pochi lavori focalizzati sull'apprendimento di embedding o di metriche di similarità per i grafi evento. Questa lacuna lascia le relazioni biologiche scollegate, impedendo l'applicazione di tecniche di machine learning che potrebbero dare un importante contributo al progresso scientifico. Approfittando dei vantaggi delle recenti soluzioni di deep graph kernel e dei language model preaddestrati, proponiamo Deep Divergence Event Graph Kernels (DDEGK), un metodo non supervisionato e induttivo in grado di mappare gli eventi all'interno di uno spazio vettoriale, preservando le loro similarità semantiche e strutturali. Diversamente da molti altri sistemi, DDEGK lavora a livello di grafo e non richiede nè etichette e feature specifiche per un determinato task, nè corrispondenze note tra i nodi. A questo scopo, la nostra soluzione mette a confronto gli eventi con un piccolo gruppo di eventi prototipo, addestra delle reti di cross-graph attention per andare a individuare i legami di similarità tra le coppie di nodi (rafforzando l'interpretabilità), e impiega dei modelli basati su transformer per la codifica degli attributi continui. Sono stati fatti ampi esperimenti su dieci dataset biomedici. Mostriamo che le nostre rappresentazioni possono essere utilizzate in modo efficace in task quali la classificazione di grafi, clustering e visualizzazione e che, allo stesso tempo, sono in grado di semplificare il task di semantic textual similarity. Risultati empirici dimostrano che DDEGK supera significativamente gli altri modelli che attualmente detengono lo stato dell'arte.

Gli stili APA, Harvard, Vancouver, ISO e altri

36

Bloyet, Nicolas. "Caractérisation et plongement de sous-graphes colorés : application à la construction de modèles structures à activité (QSAR)". Thesis, Lorient, 2019. http://www.theses.fr/2019LORIS546.

Testo completo

Abstract (sommario):

Dans le domaine de la chimie, il est intéressant de pouvoir estimer des propriétés physico- chimiques de molécules, notamment pour des applications industrielles. Celles-ci sont difficiles à estimer par simulations physique, présentant une complexité temporelle prohibitive. L'émergence des données (publiques ou privées) ouvre toutefois de nouvelles perspectives pour le traitement de ces problèmes par des méthodes statistiques et d'apprentissage automatique. La principale difficulté réside dans la caractérisation des molécules : celles-ci s'apparentent davantage à un réseau d'atomes (autrement dit un graphe coloré) qu'à un vecteur. Or, les méthodes de modélisation statistiques traitent usuellement avec des observations encodées comme telles, d'où la nécessité de méthodes spécifiques, nommées relations structures-activité, traitant des observations encodées sous forme de graphes. Le but de cette thèse est de tirer parti des corpus publics pour apprendre les meilleures représentations possibles de ces structures, et de transférer cette connaissance globale vers des jeux de données plus restreints. Nous nous inspirons pour ce faire de méthodes utilisées en traitement automatique des langages naturels. Pour les mettre en œuvre, des travaux d'ordre plus théorique ont été nécessaires, notamment sur le problème d'isomorphisme de graphes. Les résultats obtenus sur des tâches de classification/régression sont au moins compétitifs avec l'état de l'art, voire meilleurs, en particulier sur des jeux de données restreints, attestant des possibilités d'apprentissage par transfert sur ce domaine
In the field of chemistry, it is interesting to be able to estimate the physicochemical properties of molecules, especially for industrial applications. These are difficult to estimate by physical simulations, as their implementation often present prohibitive time complexity. However, the emergence of data (public or private) opens new perspectives for the treatment of these problems by statistical methods and machine learning. The main difficulty lies in the characterization of molecules: these are more like a network of atoms (in other words a colored graph) than a vector. Unfortunately, statistical modeling methods usually deal with observations encoded as such, hence the need for specific methods able to deal with graphs- encoded observations, called structure-activity relationships. The aim of this thesis is to take advantage of public corpora to learn the best possible representations of these structures, and to transfer this global knowledge to smaller datasets. We adapted methods used in automatic processing of natural languages to achieve this goal. To implement them, more theoretical work was needed, especially on the graph isomorphism problem. The results obtained on classification / regression tasks are at least competitive with the state of the art, and even sometimes better, in particular on restricted data sets, attesting some opportunities for transfer learning in this field

Gli stili APA, Harvard, Vancouver, ISO e altri

37

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.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

38

Chennupati, Nikhil. "Recommending Collaborations Using Link Prediction". Wright State University / OhioLINK, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=wright1621899961924795.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

39

Cassagnes, Cyril. "Architecture autonome et distribuée d’adressage et de routage pour la flexibilité des communications dans l’internet". Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14600/document.

Testo completo

Abstract (sommario):

Les schémas de routage locaux basés sur des coordonnées prises dans le plan hyperbolique ont attiré un intérêt croissant depuis quelques années. Cependant, les solutions proposées sont toutes appliquées à des réseaux au topologie aléatoire et au nombre de nœuds limités. Dans le même temps, plusieurs travaux se sont concentrés sur la création de modèle topologique basé sur les lois de la géométrie hyperbolique. Dans ce cas, Il est montré que les graphes ont des topologies semblables à Internet et qu'un routage local hyperbolique atteint une efficacité proche de la perfection. Cependant, ces graphes ne garantissent pas le taux de réussite du routage même si aucune panne ne se produit. Dans cette thèse, l'objectif est de construire un système passant à l'échelle pour la création de réseau recouvrant capable de fournir à ses membres un service d'adressage et de routage résilient dans un environnement dynamique. Ensuite, nous étudions de quelle manière les réseaux P2PTV pourraient supporter un nombre d'utilisateur croissant. Dans cette thèse, nous essayons de répondre à cette question en étudiant les facteurs d'efficacité et de passage à l'échelle dans un système de diffusion vidéo P2P typique. Au travers des données fournies par Zattoo, producteur de réseau P2PTV, nous réalisons des simulations dont les résultats montrent qu'il y a encore des obstacles à surmonter avant que les réseaux P2P de diffusion vidéo puissent dépendre uniquement de leurs utilisateurs
Local routing schemes based on virtual coordinates taken from the hyperbolic plane have attracted considerable interest in recent years.However, solutions have been applied to ad-hoc and sensor networks having a random topology and a limited number of nodes. In other hand, some research has focused on the creation of network topology models based on hyperbolic geometric laws. In this case, it has been shown that these graphs have an Internet-like topology and that local hyperbolic routing achieves a near perfect efficiency. However, with these graphs, routing success is not guaranteed even if no failures happen. In this thesis, we aim at building a scalable system for creating overlay networks on top of the Internet that would provide reliable addressing and routing service to its members in a dynamic environment.Next, we investigate how well P2PTV networks would support a growing number of users. In this thesis, we try to address this question by studying scalability and efficiency factors in a typical P2P based live streaming network. Through the use of the data provided by Zattoo a production P2PTV network, we carry out simulations whose results show that there are still hurdles to overcome before P2P based live streaming could depend uniquely of their users

Gli stili APA, Harvard, Vancouver, ISO e altri

40

Simonovsky, Martin. "Deep learning on attributed graphs". Thesis, Paris Est, 2018. http://www.theses.fr/2018PESC1133/document.

Testo completo

Abstract (sommario):

Le graphe est un concept puissant pour la représentation des relations entre des paires d'entités. Les données ayant une structure de graphes sous-jacente peuvent être trouvées dans de nombreuses disciplines, décrivant des composés chimiques, des surfaces des modèles tridimensionnels, des interactions sociales ou des bases de connaissance, pour n'en nommer que quelques-unes. L'apprentissage profond (DL) a accompli des avancées significatives dans une variété de tâches d'apprentissage automatique au cours des dernières années, particulièrement lorsque les données sont structurées sur une grille, comme dans la compréhension du texte, de la parole ou des images. Cependant, étonnamment peu de choses ont été faites pour explorer l'applicabilité de DL directement sur des données structurées sous forme des graphes. L'objectif de cette thèse est d'étudier des architectures de DL sur des graphes et de rechercher comment transférer, adapter ou généraliser à ce domaine des concepts qui fonctionnent bien sur des données séquentielles et des images. Nous nous concentrons sur deux primitives importantes : le plongement de graphes ou leurs nœuds dans une représentation de l'espace vectorielle continue (codage) et, inversement, la génération des graphes à partir de ces vecteurs (décodage). Nous faisons les contributions suivantes. Tout d'abord, nous introduisons Edge-Conditioned Convolutions (ECC), une opération de type convolution sur les graphes réalisés dans le domaine spatial où les filtres sont générés dynamiquement en fonction des attributs des arêtes. La méthode est utilisée pour coder des graphes avec une structure arbitraire et variable. Deuxièmement, nous proposons SuperPoint Graph, une représentation intermédiaire de nuages de points avec de riches attributs des arêtes codant la relation contextuelle entre des parties des objets. Sur la base de cette représentation, l'ECC est utilisé pour segmenter les nuages de points à grande échelle sans sacrifier les détails les plus fins. Troisièmement, nous présentons GraphVAE, un générateur de graphes permettant de décoder des graphes avec un nombre de nœuds variable mais limité en haut, en utilisant la correspondance approximative des graphes pour aligner les prédictions d'un auto-encodeur avec ses entrées. La méthode est appliquée à génération de molécules
Graph is a powerful concept for representation of relations between pairs of entities. Data with underlying graph structure can be found across many disciplines, describing chemical compounds, surfaces of three-dimensional models, social interactions, or knowledge bases, to name only a few. There is a natural desire for understanding such data better. Deep learning (DL) has achieved significant breakthroughs in a variety of machine learning tasks in recent years, especially where data is structured on a grid, such as in text, speech, or image understanding. However, surprisingly little has been done to explore the applicability of DL on graph-structured data directly.The goal of this thesis is to investigate architectures for DL on graphs and study how to transfer, adapt or generalize concepts working well on sequential and image data to this domain. We concentrate on two important primitives: embedding graphs or their nodes into a continuous vector space representation (encoding) and, conversely, generating graphs from such vectors back (decoding). To that end, we make the following contributions.First, we introduce Edge-Conditioned Convolutions (ECC), a convolution-like operation on graphs performed in the spatial domain where filters are dynamically generated based on edge attributes. The method is used to encode graphs with arbitrary and varying structure.Second, we propose SuperPoint Graph, an intermediate point cloud representation with rich edge attributes encoding the contextual relationship between object parts. Based on this representation, ECC is employed to segment large-scale point clouds without major sacrifice in fine details.Third, we present GraphVAE, a graph generator allowing to decode graphs with variable but upper-bounded number of nodes making use of approximate graph matching for aligning the predictions of an autoencoder with its inputs. The method is applied to the task of molecule generation

Gli stili APA, Harvard, Vancouver, ISO e altri

41

Sarker, Bishnu. "On Graph-Based Approaches for Protein Function Annotation and Knowledge Discovery". Electronic Thesis or Diss., Université de Lorraine, 2021. http://www.theses.fr/2021LORR0094.

Testo completo

Abstract (sommario):

Les progrès des technologies de séquençage génomique ont conduit à une croissance exponentielle du nombre de séquences protéiques dans les bases de données publiques. Il est important d’exploiter cette énorme quantité de données pour décrire les êtres vivants au niveau moléculaire, et ainsi mieux comprendre les processus pathologiques humains et accélérer la découverte de médicaments. Une condition préalable, cependant, est que toutes ces protéines soient annotées avec des propriétés fonctionnelles telles que les numéros de commission enzymatique (EC) ou les termes de l’ontologie « Gene Ontology » (GO). Aujourd’hui, seule une petite fraction des protéines est annotée fonctionnellement et examinée manuellement par des experts car c’est une tâche coûteuse, lente et chronophage. Le développement d’outils d’annotation automatique des protéines est la voie à suivre pour réduire l’écart entre séquences protéiques annotées et non annotées et produire des annotations fiables. Aucun outil déjà développés n’est pleinement satisfaisant. Seuls quelques-uns utilisent les approches à base de graphes et tiennent compte de la composition en domaines des protéines qui sont des régions conservées à travers les séquences protéiques de la même famille. Dans cette thèse, nous concevons et évaluons des approches à base de graphes pour effectuer l’annotation automatique des fonctions protéiques et nous explorons l’impact de l’architecture en domaines sur les fonctions protéiques. La première partie est consacrée à l’annotation de la fonction des protéines à l’aide d’un graphe de similarité de domaines et de techniques de propagation d’étiquettes (ou de labels) améliorées. Tout d’abord, nous présentons GrAPFI (« Graph-based Automatic Protein Function Inference ») pour l’annotation automatique des protéines par les numéros EC et par des termes GO. Nous validons les performances de GrAPFI en utilisant six protéomes de référence dans UniprotKB/SwissProt, et nous comparons les résultats de GrAPFI avec des outils de référence. Nous avons constaté que GrAPFI atteint une meilleure précision et une couverture comparable ou meilleure par rapport aux outils existants. La deuxième partie traite de l’apprentissage de représentations pour les entités biologiques. Au début, nous nous concentrons sur les techniques de plongement lexical (« word embedding »), utilisant les réseaux neuronaux. Nous formulons la tâche d’annotation comme une tâche de classification de textes. Nous construisons un corpus de protéines sous forme de phrases composées de leurs domaines respectifs et nous apprenons une représentation vectorielle à dimension fixe. Ensuite, nous portons notre attention sur l’apprentissage de représentations à partir de graphes de connaissances intégrant différentes sources de données liées aux protéines et à leurs fonctions. Nous formulons le problème d’annotation fonctionnelle des protéines comme une tâche de prédiction de liens entre une protéine et un terme GO. Nous proposons Prot-A-GAN, un modèle d’apprentissage automatique inspiré des réseaux antagonistes génératifs (GAN pour « Generative Adversarial Network »). Nous observons que Prot-A-GAN fonctionne avec des résultats prometteurs pour associer des fonctions appropriées aux protéines requêtes. En conclusion, cette thèse revisite le problème crucial de l’annotation automatique des fonctions protéiques à grande échelle en utilisant des techniques innovantes d’intelligence artificielle. Elle ouvre de larges perspectives, notamment pour l’utilisation des graphes de connaissances, disponibles aujourd’hui dans de nombreux domaines autres que l’annotation de protéines grâce aux progrès de la science des données
Due to the recent advancement in genomic sequencing technologies, the number of protein entries in public databases is growing exponentially. It is important to harness this huge amount of data to describe living things at the molecular level, which is essential for understanding human disease processes and accelerating drug discovery. A prerequisite, however, is that all of these proteins be annotated with functional properties such as Enzyme Commission (EC) numbers and Gene Ontology (GO) terms. Today, only a small fraction of the proteins is functionally annotated and reviewed by expert curators because it is expensive, slow and time-consuming. Developing automatic protein function annotation tools is the way forward to reduce the gap between the annotated and unannotated proteins and to predict reliable annotations for unknown proteins. Many tools of this type already exist, but none of them are fully satisfactory. We observed that only few consider graph-based approaches and the domain composition of proteins. Indeed, domains are conserved regions across protein sequences of the same family. In this thesis, we design and evaluate graph-based approaches to perform automatic protein function annotation and we explore the impact of domain architecture on protein functions. The first part is dedicated to protein function annotation using domain similarity graph and neighborhood-based label propagation technique. We present GrAPFI (Graph-based Automatic Protein Function Inference) for automatically annotating proteins with enzymatic functions (EC numbers) and GO terms from a protein-domain similarity graph. We validate the performance of GrAPFI using six reference proteomes from UniprotKB/SwissProt and compare GrAPFI results with state-of-the-art EC prediction approaches. We find that GrAPFI achieves better accuracy and comparable or better coverage. The second part of the dissertation deals with learning representation for biological entities. At the beginning, we focus on neural network-based word embedding technique. We formulate the annotation task as a text classification task. We build a corpus of proteins as sentences composed of respective domains and learn fixed dimensional vector representation for proteins. Then, we focus on learning representation from heterogeneous biological network. We build knowledge graph integrating different sources of information related to proteins and their functions. We formulate the problem of function annotation as a link prediction task between proteins and GO terms. We propose Prot-A-GAN, a machine-learning model inspired by Generative Adversarial Network (GAN) to learn vector representation of biological entities from protein knowledge graph. We observe that Prot-A-GAN works with promising results to associate ap- propriate functions with query proteins. In conclusion, this thesis revisits the crucial problem of large-scale automatic protein function annotation in the light of innovative techniques of artificial intelligence. It opens up wide perspectives, in particular for the use of knowledge graphs, which are today available in many fields other than protein annotation thanks to the progress of data science

Gli stili APA, Harvard, Vancouver, ISO e altri

42

Zhu, Ruifeng. "Contribution to graph-based manifold learning with application to image categorization". Thesis, Bourgogne Franche-Comté, 2020. http://www.theses.fr/2020UBFCA015.

Testo completo

Abstract (sommario):

Les algorithmes d'apprentissage de représentation de données à base de graphes sont considérés comme une technique puissante pour l'extraction de caractéristiques et la réduction de dimensionnalité dans les domaines de la reconnaissance de formes, la vision par ordinateur et l'apprentissage automatique. Ces algorithmes utilisent les informations contenues dans les similitudes d’échantillons (par paire) et la matrice du graphe pondéré pour révéler la structure géométrique intrinsèque de données. Ces algorithmes sont capables de récupérer une structure de faible dimension à partir de données de dimension élevée. Le travail de cette thèse consiste à développer des techniques d'apprentissage de représentation de données à base de graphes, appliquées à la reconnaissance de formes. Plus précisément, les expérimentations sont conduites sur des bases de données correspondant à plusieurs catégories d'images publiques telles que les bases de visages, les bases de scènes intérieures et extérieures, les bases d’objets, etc. Plusieurs approches sont proposées dans cette thèse : 1) Une nouvelle méthode non linéaire appelée inclusion discriminante flexible basée sur un graphe avec sélection de caractéristiques est proposée. Nous recherchons une représentation non linéaire et linéaire des données pouvant convenir à des tâches d'apprentissage génériques telles que la classification et le regroupement. En outre, un résultat secondaire de la méthode proposée est la sélection de caractéristiques originales, où la matrice de transformation linéaire estimée peut-être utilisée pour le classement et la sélection de caractéristiques. 2) Pour l'obtention d'une représentation non linéaire flexible et inductive des données, nous développons et étudions des stratégies et des algorithmes qui estiment simultanément la représentation de données désirée et une pondération explicite de caractéristiques. Le critère proposé estime explicitement les poids des caractéristiques ainsi que les données projetées et la transformation linéaire de sorte que la régularité des données et de grandes marges soient obtenues dans l'espace de projection. De plus, nous introduisons une variante à base de noyaux du modèle afin d'obtenir une représentation de données non linéaire inductive proche d'un véritable sous-espace non linéaire pour une bonne approximation des données. 3) Un apprentissage profond flexible qui peut surmonter les limites et les faiblesses des modèles d'apprentissage à une seule couche est introduit. Nous appelons cette stratégie une représentation basée sur un graphe élastique avec une architecture profonde qui explore en profondeur les informations structurelles des données. Le cadre résultant peut être utilisé pour les environnements semi-supervisés et supervisés. De plus, les problèmes d'optimisation qui en résultent peuvent être résolus efficacement. 4) Nous proposons une méthode semi-supervisée pour la représentation de données qui exploite la notion de convolution avec graphes. Cette méthode offre une nouvelle perspective de recherche sur la représentation de données non linéaires et établit un lien avec le traitement du signal sur les méthodes à base de graphes. La méthode proposée utilise et exploite les graphes de deux manières. Tout d'abord, il déploie une régularité des données sur les graphes. Deuxièmement, son modèle de régression est construit sur l'utilisation conjointe des données et de leur graphe en ce sens que le modèle de régression fonctionne avec des données convolutées. Ces dernières sont obtenues par propagation de caractéristiques
Graph-based Manifold Learning algorithms are regarded as a powerful technique for feature extraction and dimensionality reduction in Pattern Recogniton, Computer Vision and Machine Learning fields. These algorithms utilize sample information contained in the item-item similarity and weighted matrix to reveal the intrinstic geometric structure of manifold. It exhibits the low dimensional structure in the high dimensional data. This motivates me to develop Graph-based Manifold Learning techniques on Pattern Recognition, specially, application to image categorization. The experimental datasets of thesis correspond to several categories of public image datasets such as face datasets, indoor and outdoor scene datasets, objects datasets and so on. Several approaches are proposed in this thesis: 1) A novel nonlinear method called Flexible Discriminant graph-based Embedding with feature selection (FDEFS) is proposed. We seek a non-linear and a linear representation of the data that can be suitable for generic learning tasks such as classification and clustering. Besides, a byproduct of the proposed embedding framework is the feature selection of the original features, where the estimated linear transformation matrix can be used for feature ranking and selection. 2) We investigate strategies and related algorithms to develop a joint graph-based embedding and an explicit feature weighting for getting a flexible and inductive nonlinear data representation on manifolds. The proposed criterion explicitly estimates the feature weights together with the projected data and the linear transformation such that data smoothness and large margins are achieved in the projection space. Moreover, this chapter introduces a kernel variant of the model in order to get an inductive nonlinear embedding that is close to a real nonlinear subspace for a good approximation of the embedded data. 3) We propose the graph convolution based semi-supervised Embedding (GCSE). It provides a new perspective to non-linear data embedding research, and makes a link to signal processing on graph methods. The proposed method utilizes and exploits graphs in two ways. First, it deploys data smoothness over graphs. Second, its regression model is built on the joint use of the data and their graph in the sense that the regression model works with convolved data. The convolved data are obtained by feature propagation. 4) A flexible deep learning that can overcome the limitations and weaknesses of single-layer learning models is introduced. We call this strategy an Elastic graph-based embedding with deep architecture which deeply explores the structural information of the data. The resulting framework can be used for semi-supervised and supervised settings. Besides, the resulting optimization problems can be solved efficiently

Gli stili APA, Harvard, Vancouver, ISO e altri

43

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.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

44

Islam, Md Kamrul. "Explainable link prediction in large complex graphs - application to drug repurposing". Electronic Thesis or Diss., Université de Lorraine, 2022. http://www.theses.fr/2022LORR0203.

Testo completo

Abstract (sommario):

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

Gli stili APA, Harvard, Vancouver, ISO e altri

45

Turner, Bethany. "Embeddings of Product Graphs Where One Factor is a Hypercube". VCU Scholars Compass, 2011. http://scholarscompass.vcu.edu/etd/2455.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

46

Ngwobia, Sunday C. "Capturing Knowledge of Emerging Entities from the Extended Search Snippets". University of Dayton / OhioLINK, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=dayton157309507473671.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

47

Yelle, Céline. "Stack Number, Track Number, and Layered Pathwidth". Thesis, Université d'Ottawa / University of Ottawa, 2020. http://hdl.handle.net/10393/40348.

Testo completo

Abstract (sommario):

In this thesis, we consider three parameters associated with graphs : stack number, track number, and layered pathwidth. Our first result is to show that the stack number of any graph is at most 4 times its layered pathwidth. This result complements an existing result of Dujmovic et al. that showed that the queue number of a graph is at most 3 times its layered pathwidth minus one (Dujmovic, Morin, and Wood [SIAM J. Comput., 553–579, 2005]). Our second result is to show that graphs of track number at most 3 have layered pathwidth at most 4. This answers an open question posed by Banister et al. (Bannister, Devanny, Dujmovic, Eppstein, and Wood [GD 2016, 499–510, 2016, Algorithmica, 1–23, 2018]).

Gli stili APA, Harvard, Vancouver, ISO e altri

48

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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

49

Hayashi, Kazuki. "Reinforcement Learning for Optimal Design of Skeletal Structures". Doctoral thesis, Kyoto University, 2021. http://hdl.handle.net/2433/263614.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

50

Cooley, Oliver Josef Nikolaus. "Embedding Problems for Graphs and Hypergraphs". Thesis, University of Birmingham, 2010. http://etheses.bham.ac.uk//id/eprint/766/.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

Tesi sul tema "Embedding de graph"

Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili