Academic literature on the topic 'Graphes embeddings'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Graphes embeddings.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Graphes embeddings"
1
BOZKURT, ILKER NADI, HAI HUANG, BRUCE MAGGS, ANDRÉA RICHA, and MAVERICK WOO. "Mutual Embeddings." Journal of Interconnection Networks 15, no. 01n02 (March 2015): 1550001. http://dx.doi.org/10.1142/s0219265915500012.
Full textAbstract:
This paper introduces a type of graph embedding called a mutual embedding. A mutual embedding between two n-node graphs [Formula: see text] and [Formula: see text] is an identification of the vertices of V1 and V2, i.e., a bijection [Formula: see text], together with an embedding of G1 into G2 and an embedding of G2 into G1 where in the embedding of G1 into G2, each node u of G1 is mapped to π(u) in G2 and in the embedding of G2 into G1 each node v of G2 is mapped to [Formula: see text] in G1. The identification of vertices in G1 and G2 constrains the two embeddings so that it is not always possible for both to exhibit small congestion and dilation, even if there are traditional one-way embeddings in both directions with small congestion and dilation. Mutual embeddings arise in the context of finding preconditioners for accelerating the convergence of iterative methods for solving systems of linear equations. We present mutual embeddings between several types of graphs such as linear arrays, cycles, trees, and meshes, prove lower bounds on mutual embeddings between several classes of graphs, and present some open problems related to optimal mutual embeddings.
2
Trisedya, Bayu Distiawan, Jianzhong Qi, and Rui Zhang. "Entity Alignment between Knowledge Graphs Using Attribute Embeddings." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 297–304. http://dx.doi.org/10.1609/aaai.v33i01.3301297.
Full textAbstract:
The task of entity alignment between knowledge graphs aims to find entities in two knowledge graphs that represent the same real-world entity. Recently, embedding-based models are proposed for this task. Such models are built on top of a knowledge graph embedding model that learns entity embeddings to capture the semantic similarity between entities in the same knowledge graph. We propose to learn embeddings that can capture the similarity between entities in different knowledge graphs. Our proposed model helps align entities from different knowledge graphs, and hence enables the integration of multiple knowledge graphs. Our model exploits large numbers of attribute triples existing in the knowledge graphs and generates attribute character embeddings. The attribute character embedding shifts the entity embeddings from two knowledge graphs into the same space by computing the similarity between entities based on their attributes. We use a transitivity rule to further enrich the number of attributes of an entity to enhance the attribute character embedding. Experiments using real-world knowledge bases show that our proposed model achieves consistent improvements over the baseline models by over 50% in terms of hits@1 on the entity alignment task.
3
GUPTA, AJAY K., and GARRISON W. GREENWOOD. "APPLICATIONS OF EVOLUTIONARY STRATEGIES TO FINE-GRAINED TASK SCHEDULING." Parallel Processing Letters 06, no. 04 (December 1996): 551–61. http://dx.doi.org/10.1142/s0129626496000492.
Full textAbstract:
Embedding task graphs onto hypercubes is a difficult problem. When the embedding is one-to-one, schedule length is strongly influenced by dilation. Therefore, it is desirable to find low dilation embeddings. This paper describes a heuristic embedding technique based upon evolutionary strategies. The technique has been extensively investigated using task graphs which are trees, forests, and butterflies. In all cases the technique has found low dilation embeddings.
4
Mohar, Bojan. "Combinatorial Local Planarity and the Width of Graph Embeddings." Canadian Journal of Mathematics 44, no. 6 (December 1, 1992): 1272–88. http://dx.doi.org/10.4153/cjm-1992-076-8.
Full textAbstract:
AbstractLet G be a graph embedded in a closed surface. The embedding is “locally planar” if for each face, a “large” neighbourhood of this face is simply connected. This notion is formalized, following [RV], by introducing the width ρ(ψ) of the embedding ψ. It is shown that embeddings with ρ(ψ) ≥ 3 behave very much like the embeddings of planar graphs in the 2-sphere. Another notion, “combinatorial local planarity”, is introduced. The criterion is independent of embeddings of the graph, but it guarantees that a given cycle in a graph G must be contractible in any minimal genus embedding of G (either orientable, or non-orientable). It generalizes the width introduced before. As application, short proofs of some important recently discovered results about embeddings of graphs are given and generalized or improved. Uniqueness and switching equivalence of graphs embedded in a fixed surface are also considered.
5
Kalogeropoulos, Nikitas-Rigas, Dimitris Ioannou, Dionysios Stathopoulos, and Christos Makris. "On Embedding Implementations in Text Ranking and Classification Employing Graphs." Electronics 13, no. 10 (May 12, 2024): 1897. http://dx.doi.org/10.3390/electronics13101897.
Full textAbstract:
This paper aims to enhance the Graphical Set-based model (GSB) for ranking and classification tasks by incorporating node and word embeddings. The model integrates a textual graph representation with a set-based model for information retrieval. Initially, each document in a collection is transformed into a graph representation. The proposed enhancement involves augmenting the edges of these graphs with embeddings, which can be pretrained or generated using Word2Vec and GloVe models. Additionally, an alternative aspect of our proposed model consists of the Node2Vec embedding technique, which is applied to a graph created at the collection level through the extension of the set-based model, providing edges based on the graph’s structural information. Core decomposition is utilized as a method for pruning the graph. As a byproduct of our information retrieval model, we explore text classification techniques based on our approach. Node2Vec embeddings are generated by our graphs and are applied in order to represent the different documents in our collections that have undergone various preprocessing methods. We compare the graph-based embeddings with the Doc2Vec and Word2Vec representations to elaborate on whether our approach can be implemented on topic classification problems. For that reason, we then train popular classifiers on the document embeddings obtained from each model.
6
Hu, Ganglin, and Jun Pang. "Relation-Aware Weighted Embedding for Heterogeneous Graphs." Information Technology and Control 52, no. 1 (March 28, 2023): 199–214. http://dx.doi.org/10.5755/j01.itc.52.1.32390.
Full textAbstract:
Heterogeneous graph embedding, aiming to learn the low-dimensional representations of nodes, is effective in many tasks, such as link prediction, node classification, and community detection. Most existing graph embedding methods conducted on heterogeneous graphs treat the heterogeneous neighbours equally. Although it is possible to get node weights through attention mechanisms mainly developed using expensive recursive message-passing, they are difficult to deal with large-scale networks. In this paper, we propose R-WHGE, a relation-aware weighted embedding model for heterogeneous graphs, to resolve this issue. R-WHGE comprehensively considers structural information, semantic information, meta-paths of nodes and meta-path-based node weights to learn effective node embeddings. More specifically, we first extract the feature importance of each node and then take the nodes’ importance as node weights. A weighted random walks-based embedding learning model is proposed to generate the initial weighted node embeddings according to each meta-path. Finally, we feed these embeddings to a relation-aware heterogeneous graph neural network to generate compact embeddings of nodes, which captures relation-aware characteristics. Extensive experiments on real-world datasets demonstrate that our model is competitive against various state-of-the-art methods.
7
Peng, Yanhui, Jing Zhang, Cangqi Zhou, and Shunmei Meng. "Knowledge Graph Entity Alignment Using Relation Structural Similarity." Journal of Database Management 33, no. 1 (January 1, 2022): 1–19. http://dx.doi.org/10.4018/jdm.305733.
Full textAbstract:
Embedding-based entity alignment, which represents knowledge graphs as low-dimensional embeddings and finds entities in different knowledge graphs that semantically represent the same real-world entity by measuring the similarities between entity embeddings, has achieved promising results. However, existing methods are still challenged by the error accumulation of embeddings along multi-step paths and the semantic information loss. This paper proposes a novel embedding-based entity alignment method that iteratively aligns both entities and relations with high similarities as training data. Newly-aligned entities and relations are used to calibrate the corresponding embeddings in the unified embedding space, which reduces the error accumulation. To reduce the negative impact of semantic information loss, the authors propose to use relation structural similarity instead of embedding similarity to align relations. Experimental results on five widely used real-world datasets show that the proposed method significantly outperforms several state-of-the-art methods for entity alignment.
8
Chen, Mingyang, Wen Zhang, Zhen Yao, Yushan Zhu, Yang Gao, Jeff Z. Pan, and Huajun Chen. "Entity-Agnostic Representation Learning for Parameter-Efficient Knowledge Graph Embedding." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 4 (June 26, 2023): 4182–90. http://dx.doi.org/10.1609/aaai.v37i4.25535.
Full textAbstract:
We propose an entity-agnostic representation learning method for handling the problem of inefficient parameter storage costs brought by embedding knowledge graphs. Conventional knowledge graph embedding methods map elements in a knowledge graph, including entities and relations, into continuous vector spaces by assigning them one or multiple specific embeddings (i.e., vector representations). Thus the number of embedding parameters increases linearly as the growth of knowledge graphs. In our proposed model, Entity-Agnostic Representation Learning (EARL), we only learn the embeddings for a small set of entities and refer to them as reserved entities. To obtain the embeddings for the full set of entities, we encode their distinguishable information from their connected relations, k-nearest reserved entities, and multi-hop neighbors. We learn universal and entity-agnostic encoders for transforming distinguishable information into entity embeddings. This approach allows our proposed EARL to have a static, efficient, and lower parameter count than conventional knowledge graph embedding methods. Experimental results show that EARL uses fewer parameters and performs better on link prediction tasks than baselines, reflecting its parameter efficiency.
9
Zhou, Houquan, Shenghua Liu, Danai Koutra, Huawei Shen, and Xueqi Cheng. "A Provable Framework of Learning Graph Embeddings via Summarization." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 4 (June 26, 2023): 4946–53. http://dx.doi.org/10.1609/aaai.v37i4.25621.
Full textAbstract:
Given a large graph, can we learn its node embeddings from a smaller summary graph? What is the relationship between embeddings learned from original graphs and their summary graphs? Graph representation learning plays an important role in many graph mining applications, but learning em-beddings of large-scale graphs remains a challenge. Recent works try to alleviate it via graph summarization, which typ-ically includes the three steps: reducing the graph size by combining nodes and edges into supernodes and superedges,learning the supernode embedding on the summary graph and then restoring the embeddings of the original nodes. How-ever, the justification behind those steps is still unknown. In this work, we propose GELSUMM, a well-formulated graph embedding learning framework based on graph sum-marization, in which we show the theoretical ground of learn-ing from summary graphs and the restoration with the three well-known graph embedding approaches in a closed form.Through extensive experiments on real-world datasets, we demonstrate that our methods can learn graph embeddings with matching or better performance on downstream tasks.This work provides theoretical analysis for learning node em-beddings via summarization and helps explain and under-stand the mechanism of the existing works.
10
Cui, Yuanning, Yuxin Wang, Zequn Sun, Wenqiang Liu, Yiqiao Jiang, Kexin Han, and Wei Hu. "Lifelong Embedding Learning and Transfer for Growing Knowledge Graphs." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 4 (June 26, 2023): 4217–24. http://dx.doi.org/10.1609/aaai.v37i4.25539.
Full textAbstract:
Existing knowledge graph (KG) embedding models have primarily focused on static KGs. However, real-world KGs do not remain static, but rather evolve and grow in tandem with the development of KG applications. Consequently, new facts and previously unseen entities and relations continually emerge, necessitating an embedding model that can quickly learn and transfer new knowledge through growth. Motivated by this, we delve into an expanding field of KG embedding in this paper, i.e., lifelong KG embedding. We consider knowledge transfer and retention of the learning on growing snapshots of a KG without having to learn embeddings from scratch. The proposed model includes a masked KG autoencoder for embedding learning and update, with an embedding transfer strategy to inject the learned knowledge into the new entity and relation embeddings, and an embedding regularization method to avoid catastrophic forgetting. To investigate the impacts of different aspects of KG growth, we construct four datasets to evaluate the performance of lifelong KG embedding. Experimental results show that the proposed model outperforms the state-of-the-art inductive and lifelong embedding baselines.
Dissertations / Theses on the topic "Graphes embeddings"
1
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.
Full textAbstract:
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établesMachine 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
2
Muller, Carole. "Minor-closed classes of graphs: Isometric embeddings, cut dominants and ball packings." Doctoral thesis, Universite Libre de Bruxelles, 2021. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/331629.
Full textAbstract:
Une classe de graphes est close par mineurs si, pour tout graphe dans la classe et tout mineur de ce graphe, le mineur est ́egalement dans la classe. Par un fameux th ́eor`eme de Robertson et Seymour, nous savons que car- act ́eriser une telle classe peut ˆetre fait `a l’aide d’un nombre fini de mineurs exclus minimaux. Ceux-ci sont des graphes qui n’appartiennent pas `a la classe et qui sont minimaux dans le sens des mineurs pour cette propri ́et ́e.Dans cette thèse, nous étudions trois problèmes à propos de classes de graphes closes par mineurs. Les deux premiers sont reliés à la caractérisation de certaines classes de graphes, alors que le troisième étudie une relation de “packing-covering” dans des graphes excluant un mineur.Pour le premier problème, nous étudions des plongements isométriques de graphes dont les arêtes sont pondérées dans des espaces métriques. Principalement, nous nous intêressons aux espaces ell_2 et ell_∞. E ́tant donné un graphe pondéré, un plongement isométrique associe à chaque sommet du graphe un vecteur dans l’autre espace de sorte que pour chaque arête du graphe le poids de celle-ci est égal à la distance entre les vecteurs correspondant à ses sommets. Nous disons qu’une fonction de poids sur les arêtes est une fonction de distances réalisable s’il existe un tel plongement. Le paramètre f_p(G) détermine la dimension k minimale d’un espace ell_p telle que toute fonction de distances réalisable de G peut être plongée dans ell_p^k. Ce paramètre est monotone dans le sens des mineurs. Nous caractérisons les graphes tels que f_p(G) a une grande valeur en termes de mineurs inévitables pour p = 2 et p = ∞. Une famille de graphes donne des mineurs inévitables pour un invariant monotone pour les mineurs, si ces graphes “expliquent” pourquoi l’invariant est grand.Le deuxième problème étudie les mineurs exclus minimaux pour la classe de graphes avec φ(G) borné par une constante k, où φ(G) est un paramètre lié au dominant des coupes d’un graphe G. Ce polyèdre contient tous les points qui, composante par composante, sont plus grands ou égaux à une combination convexe des vecteurs d’incidence de coupes dans G. Le paramètre φ(G) est égal au membre de droite maximum d’une description linéaire du dominant des coupes de G en forme entière minimale. Nous étudions les mineurs exclus minimaux pour la propriété φ(G) <= 4 et montrons une nouvelle borne sur φ(G) en termes du “vertex cover number”.Le dernier problème est d’un autre type. Nous étudions une relation de “packing-covering” dans les classes de graphes excluant un mineur. Étant donné un graphe G, une boule de centre v et de rayon r est l’ensemble de tous les sommets de G qui sont à distance au plus r de v. Pour un graphe G et une collection de boules donnés nous pouvons définir un hypergraphe H dont les sommets sont ceux de G et les arêtes correspondent aux boules de la collection. Il est bien connu que dans l’hypergraphe H, le “transversal number” τ(H) vaut au moins le “packing number” ν(H). Nous montrons une borne supérieure sur ν(H) qui est linéaire en τ(H), résolvant ainsi un problème ouvert de Chepoi, Estellon et Vaxès.A class of graphs is closed under taking minors if for each graph in the class and each minor of this graph, the minor is also in the class. By a famous result of Robertson and Seymour, we know that characterizing such a class can be done by identifying a finite set of minimal excluded minors, that is, graphs which do not belong to the class and are minor-minimal for this property.In this thesis, we study three problems in minor-closed classes of graphs. The first two are related to the characterization of some graph classes, while the third one studies a packing-covering relation for graphs excluding a minor.In the first problem, we study isometric embeddings of edge-weighted graphs into metric spaces. In particular, we consider ell_2- and ell_∞-spaces. Given a weighted graph, an isometric embedding maps the vertices of this graph to vectors such that for each edge of the graph the weight of the edge equals the distance between the vectors representing its ends. We say that a weight function on the edges of the graph is a realizable distance function if such an embedding exists. The minor-monotone parameter f_p(G) determines the minimum dimension k of an ell_p-space such that any realizable distance function of G is realizable in ell_p^k. We characterize graphs with large f_p(G) value in terms of unavoidable minors for p = 2 and p = ∞. Roughly speaking, a family of graphs gives unavoidable minors for a minor-monotone parameter if these graphs “explain” why the parameter is high.The second problem studies the minimal excluded minors of the class of graphs such that φ(G) is bounded by some constant k, where φ(G) is a parameter related to the cut dominant of a graph G. This unbounded polyhedron contains all points that are componentwise larger than or equal to a convex combination of incidence vectors of cuts in G. The parameter φ(G) is equal to the maximum right-hand side of a facet-defining inequality of the cut dominant of G in minimum integer form. We study minimal excluded graphs for the property φ(G) <= 4 and provide also a new bound of φ(G) in terms of the vertex cover number.The last problem has a different flavor as it studies a packing-covering relation in classes of graphs excluding a minor. Given a graph G, a ball of center v and radius r is the set of all vertices in G that are at distance at most r from v. Given a graph and a collection of balls, we can define a hypergraph H such that its vertices are the vertices of G and its edges correspond to the balls in the collection. It is well-known that, in the hypergraph H, the transversal number τ(H) is at least the packing number ν(H). We show that we can bound τ(H) from above by a linear function of ν(H) for every graphs G and ball collections H if the graph G excludes a minor, solving an open problem by Chepoi, Estellon et Vaxès.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished
3
Trouillon, Théo. "Modèles d'embeddings à valeurs complexes pour les graphes de connaissances." Thesis, Université Grenoble Alpes (ComUE), 2017. http://www.theses.fr/2017GREAM048/document.
Full textAbstract:
L'explosion de données relationnelles largement disponiblessous la forme de graphes de connaissances a permisle développement de multiples applications, dont les agents personnels automatiques,les systèmes de recommandation et l'amélioration desrésultats de recherche en ligne.La grande taille et l'incomplétude de ces bases de donnéesnécessite le développement de méthodes de complétionautomatiques pour rendre ces applications viables.La complétion de graphes de connaissances, aussi appeléeprédiction de liens, se doit de comprendre automatiquementla structure des larges graphes de connaissances (graphes dirigéslabellisés) pour prédire les entrées manquantes (les arêtes labellisées).Une approche gagnant en popularité consiste à représenter ungraphe de connaissances comme un tenseur d'ordre 3, etd'utiliser des méthodes de décomposition de tenseur pourprédire leurs entrées manquantes.Les modèles de factorisation existants proposent différentscompromis entre leur expressivité, et leur complexité en temps et en espace.Nous proposons un nouveau modèle appelé ComplEx, pour"Complex Embeddings", pour réconcilier expressivité etcomplexité par l'utilisation d'une factorisation en nombre complexes,dont nous explorons le lien avec la diagonalisation unitaire.Nous corroborons notre approche théoriquement en montrantque tous les graphes de connaissances possiblespeuvent être exactement décomposés par le modèle proposé.Notre approche, basées sur des embeddings complexesreste simple, car n'impliquant qu'un produit trilinéaire complexe,là où d'autres méthodes recourent à des fonctions de compositionde plus en plus compliquées pour accroître leur expressivité.Le modèle proposé ayant une complexité linéaire en tempset en espace est passable à l'échelle, tout endépassant les approches existantes sur les jeux de données de référencepour la prédiction de liens.Nous démontrons aussi la capacité de ComplEx àapprendre des représentations vectorielles utiles pour d'autres tâches,en enrichissant des embeddings de mots, qui améliorentles prédictions sur le problème de traitement automatiquedu langage d'implication entre paires de phrases.Dans la dernière partie de cette thèse, nous explorons lescapacités de modèles de factorisation à apprendre lesstructures relationnelles à partir d'observations.De part leur nature vectorielle,il est non seulement difficile d'interpréter pourquoicette classe de modèles fonctionne aussi bien,mais aussi où ils échouent et comment ils peuventêtre améliorés. Nous conduisons une étude expérimentalesur les modèles de l'état de l'art, non pas simplementpour les comparer, mais pour comprendre leur capacitésd'induction. Pour évaluer les forces et faiblessesde chaque modèle, nous créons d'abord des tâches simplesreprésentant des propriétés atomiques despropriétés des relations des graphes de connaissances ;puis des tâches représentant des inférences multi-relationnellescommunes au travers de généalogies synthétisées.À partir de ces résultatsexpérimentaux, nous proposons de nouvelles directionsde recherches pour améliorer les modèles existants,y compris ComplExThe explosion of widely available relational datain the form of knowledge graphsenabled many applications, including automated personalagents, recommender systems and enhanced web search results.The very large size and notorious incompleteness of these data basescalls for automatic knowledge graph completion methods to make these applicationsviable. Knowledge graph completion, also known as link-prediction,deals with automatically understandingthe structure of large knowledge graphs---labeled directed graphs---topredict missing entries---labeled edges. An increasinglypopular approach consists in representing knowledge graphs as third-order tensors,and using tensor factorization methods to predict their missing entries.State-of-the-art factorization models propose different trade-offs between modelingexpressiveness, and time and space complexity. We introduce a newmodel, ComplEx---for Complex Embeddings---to reconcile both expressivenessand complexity through the use of complex-valued factorization, and exploreits link with unitary diagonalization.We corroborate our approach theoretically and show that all possibleknowledge graphs can be exactly decomposed by the proposed model.Our approach based on complex embeddings is arguably simple,as it only involves a complex-valued trilinear product,whereas other methods resort to more and more complicated compositionfunctions to increase their expressiveness. The proposed ComplEx model isscalable to large data sets as it remains linear in both space and time, whileconsistently outperforming alternative approaches on standardlink-prediction benchmarks. We also demonstrateits ability to learn useful vectorial representations for other tasks,by enhancing word embeddings that improve performanceson the natural language problem of entailment recognitionbetween pair of sentences.In the last part of this thesis, we explore factorization models abilityto learn relational patterns from observed data.By their vectorial nature, it is not only hard to interpretwhy this class of models works so well,but also to understand where they fail andhow they might be improved. We conduct an experimentalsurvey of state-of-the-art models, not towardsa purely comparative end, but as a means to get insightabout their inductive abilities.To assess the strengths and weaknesses of each model, we create simple tasksthat exhibit first, atomic properties of knowledge graph relations,and then, common inter-relational inference through synthetic genealogies.Based on these experimental results, we propose new researchdirections to improve on existing models, including ComplEx
4
Liu, Jixiong. "Semantic Annotations for Tabular Data Using Embeddings : Application to Datasets Indexing and Table Augmentation." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS529.
Full textAbstract:
Avec le développement de l'Open Data, un grand nombre de sources de données sont mises à disposition des communautés (notamment les data scientists et les data analysts). Ces données constituent des sources importantes pour les services numériques sous réserve que les données soient nettoyées, non biaisées, et combinées à une sémantique explicite et compréhensible par les algorithmes afin de favoriser leur exploitation. En particulier, les sources de données structurées (CSV, JSON, XML, etc.) constituent la matière première de nombreux processus de science des données. Cependant, ces données proviennent de différents domaines pour lesquels l'expertise des consommateurs des données peut être limitée (knowledge gap). Ainsi, l'appropriation des données, étape critique pour la création de modèles d'apprentissage automatique de qualité, peut être complexe.Les modèles sémantiques (en particulier, les ontologies) permettent de représenter explicitement le sens des données en spécifiant les concepts et les relations présents dans les données. L'association d'étiquettes sémantiques aux ensembles de données facilite la compréhension et la réutilisation des données en fournissant une documentation sur les données qui peut être facilement utilisée par un non-expert. De plus, l'annotation sémantique ouvre la voie à des modes de recherche qui vont au-delà de simples mots-clés et permettent l'expression de requêtes d'un haut niveau conceptuel sur le contenu des jeux de données mais aussi leur structure tout en surmontant les problèmes d'hétérogénéité syntaxique rencontrés dans les données tabulaires. Cette thèse introduit un pipeline complet pour l'extraction, l'interprétation et les applications de tableaux de données à l'aide de graphes de connaissances. Nous rappelons tout d'abord la définition des tableaux du point de vue de leur interprétation et nous développons des systèmes de collecte et d'extraction de tableaux sur le Web et dans des fichiers locaux. Nous proposons ensuite trois systèmes d'interprétation de tableaux basés sur des règles heuristiques ou sur des modèles de représentation de graphes, afin de relever les défis observés dans la littérature. Enfin, nous présentons et évaluons deux applications d'augmentation des tables tirant parti des annotations sémantiques produites: l'imputation des données et l'augmentation des schémasWith the development of Open Data, a large number of data sources are made available to communities (including data scientists and data analysts). This data is the treasure of digital services as long as data is cleaned, unbiased, as well as combined with explicit and machine-processable semantics in order to foster exploitation. In particular, structured data sources (CSV, JSON, XML, etc.) are the raw material for many data science processes. However, this data derives from different domains for which consumers are not always familiar with (knowledge gap), which complicates their appropriation, while this is a critical step in creating machine learning models. Semantic models (in particular, ontologies) make it possible to explicitly represent the implicit meaning of data by specifying the concepts and relationships present in the data. The provision of semantic labels on datasets facilitates the understanding and reuse of data by providing documentation on the data that can be easily used by a non-expert. Moreover, semantic annotation opens the way to search modes that go beyond simple keywords and allow the use of queries of a high conceptual level on the content of the datasets but also their structure while overcoming the problems of syntactic heterogeneity encountered in tabular data. This thesis introduces a complete pipeline for the extraction, interpretation, and applications of tables in the wild with the help of knowledge graphs. We first refresh the exiting definition of tables from the perspective of table interpretation and develop systems for collecting and extracting tables on the Web and local files. Three table interpretation systems are further proposed based on either heuristic rules or graph representation models facing the challenges observed from the literature. Finally, we introduce and evaluate two table augmentation applications based on semantic annotations, namely data imputation and schema augmentation
5
Boudin, Marina. "Approche computationnelle pour le repositionnement de médicament au travers d’une perspective holistique avec les graphes de connaissances (OREGANO)." Electronic Thesis or Diss., Bordeaux, 2025. http://www.theses.fr/2025BORD0019.
Full textAbstract:
La découverte de médicaments est un processus long et coûteux. Le repositionnement de médicaments est une alternative prometteuse qui consiste à trouver de nouvelles indications pour des médicaments existants. En comparant de grandes quantités d’informations sur les médicaments qui ont échoué aux dernières phases des essais cliniques ou qui ont obtenu une autorisation de mise sur le marché, et donc commercialisés, il est possible de trouver des médicaments candidats au repositionnement capables de traiter une affection pour laquelle ils n’ont pas été développés initialement. Pour comparer tous ces médicaments, les méthodes computationnelles s’appuyant sur de grandes bases de données sont privilégiées pour leur efficacité, leur rapidité et leur capacité à croiser de grandes quantités d’informations. Les graphes de connaissances sont des structures appropriées pour intégrer ces informations de nature hétérogène. Un graphe de connaissances organise ces informations en triplets composés d’un sujet, d’un objet et d’un prédicat explicitant la relation entre le sujet et l’objet. Ce graphe, combiné à des techniques de plongement de nœuds (apprentissage automatique), permet de prédire de nouvelles relations entre sujets et objets (qui sont des nœuds du graphe). Il est donc possible de transformer le problème de repositionnement en un problème de découverte de nouveaux liens dans un graphe. Cette thèse s’intéresse à ces problématiques dans le cadre du projet OREGANO visant à construire un large graphe de connaissances sur les médicaments et à appliquer des techniques de plongement de nœuds pour le repositionnement de médicaments. Ces techniques "projettent" le graphe dans un espace vectoriel où chaque entité est représentée par un vecteur. Une des innovations apportées par OREGANO est également d’inclure des données sur des composés naturels dont les propriétés médicinales sont exploitées dans de nombreux pays et dont les potentialités de repositionnement ont été peu explorées. Dans un premier temps, nous présentons la manière dont nous avons conçu le graphe de connaissances OREGANO, en considérant deux approches d’intégration distinctes. Nous exposons ensuite les évolutions qui ont été apportées au graphe au fil des versions. Dans un troisième temps, nous exposons la capacité du graphe de connaissances OREGANO à prédire de nouveaux liens grâce à des techniques de plongement de nœuds. Les prédictions sont évaluées avec les métriques habituelles et empiriquement dans le cadre du repositionnement de médicaments. Le graphe OREGANO ainsi que les développements des algorithmes et du code sont disponibles pour la communauté scientifique à l’adresse suivante : https://gitub.u-bordeaux.fr/erias/oreganoDrug discovery is a long and costly process. Drug repositioning is a promising alternative which involves finding new indications for existing drugs. By comparing large quantities of information on drugs that have failed in the final phases of clinical trials, or that have been granted marketing authorization and are now on the market, it is possible to find candidate repositioning drugs capable of treating a condition for which they were not initially developed. To compare all these drugs, computational methods, based on large databases, are favored for their efficiency, speed and ability to analyze large quantities of information. Knowledge graphs are ideal structures for integrating this heterogeneous information. A knowledge graph organizes its information into triplets consisting of a subject, an object and a predicate explaining the relationship between the subject and the object. This graph, combined with embedding techniques (machine learning), can be used to predict new relationships between subjects and objects (which are nodes in the graph). It is therefore possible to transform the problem of repositioning into a problem of discovering new links in a graph. This thesis addresses these issues in the context of the OREGANO project, which aims to build a large knowledge graph on drugs and apply node-plotting techniques for drug repositioning. These techniques “project” the graph into a vector space where each entity is represented by a vector. One of OREGANO’s innovations is also to include data on natural compounds whose medicinal properties are exploited in many countries, and whose repositioning potential has been little explored. First, we present the way in which we designed the OREGANO knowledge graph, considering two distinct integration approaches. We then describe the evolutions that have been made to the graph over the years. Thirdly, we demonstrate the ability of the OREGANO knowledge graph to predict new links using embedding techniques. Predictions are evaluated with the usual metrics and empirically in the context of drug repositioning. The OREGANO graph as well as the algorithm and code developments are made available to the community at https://gitub.u-bordeaux.fr/erias/oregano
6
Le, coz Corentin. "Separation and Poincaré profiles Separation profiles, isoperimetry, growth and compression Poincaré profiles of lamplighter diagonal products." Thesis, université Paris-Saclay, 2020. http://www.theses.fr/2020UPASM014.
Full textAbstract:
Ce manuscrit de thèse récapitule mes travaux de recherche sur les profils de séparation et de Poincaré. Le profil de séparation est apparu en 2012 dans un l'article fondateur de Benjamini, Schramm et Timár. La définition donnée tirait ses origines dans des travaux antérieurs, dans le domaine du calcul formel : principalement des études de Lipton et Trajan concernant les graphes planaires, et de Miller, Teng, Thurston et Vavasis concernant des graphes d'intersection. Le profil de séparation est maintenant utilisé en théorie géométrique des groupes, mon domaine de recherche, à cause de sa propriété de monotonie par plongements grossiers. Il a été généralisé par Hume, Mackay et Tessera en 2019 en une gamme continue de profils, appelés profils de PoincaréThe goal of this thesis report is to present my research concerning separation and Poincaré profiles. Separation profile first appeared in 2012 in a seminal article written by Benjamini, Schramm and Timár. This definition was based on preceding research, in the field of computer science, mainly work of Lipton and Trajan concerning planar graphs, and of Miller, Teng, Thurston and Vavasis concerning overlap graphs. The separation profile plays now a role in geometric group theory, where my personal interests lies, because of its property of monotonicity under coarse embeddings. It was generalized by Hume, Mackay and Tessera in 2019 to a spectrum of profiles, called the Poincaré profiles
7
Prouteau, Thibault. "Graphs,Words, and Communities : converging paths to interpretability with a frugal embedding framework." Electronic Thesis or Diss., Le Mans, 2024. http://www.theses.fr/2024LEMA1006.
Full textAbstract:
L'apprentissage de représentations au travers des méthodes de plongements de mots (word embedding) et de graphes (graph embedding) permet des représentations distribuées de l'information. Ces représentations peuvent à leur tour être utilisées en entrée d'algorithmes d'apprentissage automatique. Au cours des deux dernières décennies, les tâches de plongement de nœuds et de mots sont passées d'approches par factorisation matricielle qui pouvaient être réalisées en quelques minutes à de grands modèles nécessitant des quantités toujours plus importantes de données d’apprentissage et parfois des semaines sur de grandes architectures matérielles. Toutefois, dans un contexte de réchauffement climatique où la durabilité est une préoccupation essentielle, il peut être souhaitable de revenir à des méthodes plus frugales comme elles pouvaient l’être par le passé. En outre, avec l'implication croissante des plongements dans des applications sensibles de l’apprentissage automatique (système judiciaire, santé), le besoin de représentations plus interprétables et explicables s'est manifesté. Pour favoriser l'apprentissage de représentations efficaces et l'interprétabilité, cette thèse présente Lower Dimension Bipartite Graph Framework (LDBGF), un framework de plongements de nœuds capable d’extraire une représentation vectorielle avec le même pipeline de traitement, à condition que les données proviennent d’un graphe ou de texte issu de grands corpus représentés sous forme de réseaux de cooccurrence. Dans ce cadre, nous présentons deux implémentations (SINr- NR, SINr-MF) qui tirent parti de la détection des communautés dans les réseaux pour découvrir un espace latent dans lequel les éléments (nœuds/mots) sont représentés en fonction de leurs liens avec les communautés. Nous montrons que SINr-NR et SINr-MF peuvent rivaliser avec des approches de plongements concurrentes sur des tâches telles que la prédiction des liens manquants dans les réseaux (link prediction) ou certaines caractéristiques des nœuds (centralité de degré, score PageRank). En ce qui concerne les plongements de mots, nous montrons que SINr-NR est un bon candidat pour représenter les mots en utilisant les réseaux de cooccurrences de mots. Enfin, nous démontrons l'interprétabilité de SINr-NR sur plusieurs aspects. Tout d'abord, une évaluation humaine montre que les dimensions de SINr-NR sont dans une certaine mesure interprétables. Ensuite, nous étudions la parcimonie des vecteurs. Notamment, combien un nombre réduit de dimensions peut permettre d'interpréter comment ces dernières se combinent et permettent de dégager un sensRepresentation learning with word and graph embedding models allows distributed representations of information that can in turn be used in input of machine learning algorithms. Through the last two decades, the tasks of embedding graphs’ nodes and words have shifted from matrix factorization approaches that could be trained in a matter of minutes to large models requiring ever larger quantities of training data and sometimes weeks on large hardware architectures. However, in a context of global warming where sustainability is a critical concern, we ought to look back to previous approaches and consider their performances with regard to resources consumption. Furthermore, with the growing involvement of embeddings in sensitive machine learning applications (judiciary system, health), the need for more interpretable and explainable representations has manifested. To foster efficient representation learning and interpretability, this thesis introduces Lower Dimension Bipartite Graph Framework (LDBGF), a node embedding framework able to embed with the same pipeline graph data and text from large corpora represented as co-occurrence networks. Within this framework, we introduce two implementations (SINr-NR, SINr-MF) that leverage community detection in networks to uncover a latent embedding space where items (nodes/words) are represented according to their links to communities. We show that SINr-NR and SINr-MF can compete with similar embedding approaches on tasks such as predicting missing links in networks (link prediction) or node features (degree centrality, PageRank score). Regarding word embeddings, we show that SINr-NR is a good contender to represent words via word co-occurrence networks. Finally, we demonstrate the interpretability of SINr-NR on multiple aspects. First with a human evaluation that shows that SINr-NR’s dimensions are to some extent interpretable. Secondly, by investigating sparsity of vectors, and how having fewer dimensions may allow interpreting how the dimensions combine and allow sense to emerge
8
Tahraoui, Mohammed Amin. "Coloring, packing and embedding of graphs." Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00995041.
Full textAbstract:
In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.
9
Lisena, Pasquale. "Knowledge-based music recommendation : models, algorithms and exploratory search." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS614.
Full textAbstract:
Représenter l'information décrivant la musique est une activité complexe, qui implique différentes sous-tâches. Ce manuscrit de thèse porte principalement sur la musique classique et étudie comment représenter et exploiter ses informations. L'objectif principal est l'étude de stratégies de représentation et de découverte des connaissances appliquées à la musique classique, dans des domaines tels que la production de base de connaissances, la prédiction de métadonnées et les systèmes de recommandation. Nous proposons une architecture pour la gestion des métadonnées de musique à l'aide des technologies du Web Sémantique. Nous introduisons une ontologie spécialisée et un ensemble de vocabulaires contrôlés pour les différents concepts spécifiques à la musique. Ensuite, nous présentons une approche de conversion des données, afin d’aller au-delà de la pratique bibliothécaire actuellement utilisée, en s’appuyant sur des règles de mapping et sur l’interconnexion avec des vocabulaires contrôlés. Enfin, nous montrons comment ces données peuvent être exploitées. En particulier, nous étudions des approches basées sur des plongements calculés sur des métadonnées structurées, des titres et de la musique symbolique pour classer et recommander de la musique. Plusieurs applications de démonstration ont été réalisées pour tester les approches et les ressources précédentesRepresenting the information about music is a complex activity that involves different sub-tasks. This thesis manuscript mostly focuses on classical music, researching how to represent and exploit its information. The main goal is the investigation of strategies of knowledge representation and discovery applied to classical music, involving subjects such as Knowledge-Base population, metadata prediction, and recommender systems. We propose a complete workflow for the management of music metadata using Semantic Web technologies. We introduce a specialised ontology and a set of controlled vocabularies for the different concepts specific to music. Then, we present an approach for converting data, in order to go beyond the librarian practice currently in use, relying on mapping rules and interlinking with controlled vocabularies. Finally, we show how these data can be exploited. In particular, we study approaches based on embeddings computed on structured metadata, titles, and symbolic music for ranking and recommending music. Several demo applications have been realised for testing the previous approaches and resources
10
Bekkouch, Imad Eddine Ibrahim. "Auxiliary learning & Adversarial training pour les études des manuscrits médiévaux." Electronic Thesis or Diss., Sorbonne université, 2024. http://www.theses.fr/2024SORUL014.
Full textAbstract:
Cette thèse se situe à l'intersection de la musicologie et de l'intelligence artificielle, et vise à exploiter l'IA pour aider les musicologues dans leur travail répétitif, comme la recherche d'objets dans les manuscrits du musée. Nous avons annoté quatre nouveaux ensembles de données pour l'étude des manuscrits médiévaux : AMIMO, AnnMusiconis, AnnVihuelas et MMSD. Dans la deuxième partie, nous améliorons les performances des détecteurs d'objets en utilisant des techniques de Transfer learning et de Few Shot Object Detection.Dans la troisième partie, nous discutons d'une approche puissante de Domain Adaptation, qui est auxiliary learning, où nous formons le modèle sur la tâche cible et une tâche supplémentaire qui permet une meilleure stabilisation du modèle et réduit le over-fitting.Enfin, nous abordons l'apprentissage auto-supervisé, qui n'utilise pas de méta-données supplémentaires en tirant parti de l'approche de adversarial learning, forçant le modèle à extraire des caractéristiques indépendantes du domaineThis thesis is at the intersection of musicology and artificial intelligence, aiming to leverage AI to help musicologists with repetitive work, such as object searching in the museum's manuscripts. We annotated four new datasets for medieval manuscript studies: AMIMO, AnnMusiconis, AnnVihuelas, and MMSD. In the second part, we improve object detectors' performances using Transfer learning techniques and Few Shot Object Detection.In the third part, we discuss a powerful approach to Domain Adaptation, which is auxiliary learning, where we train the model on the target task and an extra task that allows for better stabilization of the model and reduces over-fitting.Finally, we discuss self-supervised learning, which does not use extra meta-data by leveraging the adversarial learning approach, forcing the model to extract domain-independent features
Books on the topic "Graphes embeddings"
2
Paulheim, Heiko, Petar Ristoski, and Jan Portisch. Embedding Knowledge Graphs with RDF2vec. Cham: Springer International Publishing, 2023. http://dx.doi.org/10.1007/978-3-031-30387-6.
Full text
3
Cai, Jiazhen. Counting embeddings of planar graphs using DFS trees. New York: Courant Institute of Mathematical Sciences, New York University, 1992.
Find full text
4
L, Miller Gary, and Langley Research Center, eds. Graph embeddings and Laplacian eigenvalues. Hampton, Va: National Aeronautics and Space Administration, Langley Research Center, 1998.
Find full text
5
L, Miller Gary, and Langley Research Center, eds. Graph embeddings and Laplacian eigenvalues. Hampton, Va: National Aeronautics and Space Administration, Langley Research Center, 1998.
Find full text
6
Guattery, Stephen. Graph embedding techniques for bounding condition numbers of incomplete factor preconditioners. Hampton, Va: Institute for Computer Applications in Science and Engineering, NASA Langley Research Center, 1997.
Find full text
7
Center, Langley Research, ed. Graph embedding techniques for bounding condition numbers of incomplete factor preconditioners. Hampton, Va: National Aeronautics and Space Administration, Langley Research Center, 1997.
Find full text
9
Riesen, Kaspar. Graph classification and clustering based on vector space embedding. New Jersey: World Scientific, 2010.
Find full text
10
Embedding Planar Graphs. United States: University of Illinois, 2016. http://dx.doi.org/10.4135/9781529773132.
Full textBook chapters on the topic "Graphes embeddings"
1
Krause, Franz, Kabul Kurniawan, Elmar Kiesling, Jorge Martinez-Gil, Thomas Hoch, Mario Pichler, Bernhard Heinzl, and Bernhard Moser. "Leveraging Semantic Representations via Knowledge Graph Embeddings." In Artificial Intelligence in Manufacturing, 71–85. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-46452-2_5.
Full textAbstract:
AbstractThe representation and exploitation of semantics has been gaining popularity in recent research, as exemplified by the uptake of large language models in the field of Natural Language Processing (NLP) and knowledge graphs (KGs) in the Semantic Web. Although KGs are already employed in manufacturing to integrate and standardize domain knowledge, the generation and application of corresponding KG embeddings as lean feature representations of graph elements have yet to be extensively explored in this domain. Existing KGs in manufacturing often focus on top-level domain knowledge and thus ignore domain dynamics, or they lack interconnectedness, i.e., nodes primarily represent non-contextual data values with single adjacent edges, such as sensor measurements. Consequently, context-dependent KG embedding algorithms are either restricted to non-dynamic use cases or cannot be applied at all due to the given KG characteristics. Therefore, this work provides an overview of state-of-the-art KG embedding methods and their functionalities, identifying the lack of dynamic embedding formalisms and application scenarios as the key obstacles that hinder their implementation in manufacturing. Accordingly, we introduce an approach for dynamizing existing KG embeddings based on local embedding reconstructions. Furthermore, we address the utilization of KG embeddings in the Horizon2020 project Teaming.AI (www.teamingai-project.eu.) focusing on their respective benefits.
2
Chartrand, Gary, Heather Jordon, Vincent Vatter, and Ping Zhang. "Embeddings." In Graphs & Digraphs, 251–82. 7th ed. Boca Raton: Chapman and Hall/CRC, 2023. http://dx.doi.org/10.1201/9781003461289-10.
Full text
3
Yang, Cheng, Chuan Shi, Zhiyuan Liu, Cunchao Tu, and Maosong Sun. "Network Embedding for Heterogeneous Graphs." In Network Embedding, 119–32. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-031-01590-8_9.
Full text
4
Yang, Cheng, Chuan Shi, Zhiyuan Liu, Cunchao Tu, and Maosong Sun. "Network Embedding for Large-Scale Graphs." In Network Embedding, 99–117. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-031-01590-8_8.
Full text
5
Aggarwal, Manasvi, and M. N. Murty. "Embedding Graphs." In Machine Learning in Social Networks, 89–104. Singapore: Springer Singapore, 2020. http://dx.doi.org/10.1007/978-981-33-4022-0_5.
Full text
6
Kamiński, Bogumił, Paweł Prałat, and François Théberge. "Embedding Graphs." In Mining Complex Networks, 231–38. Boca Raton: Chapman and Hall/CRC, 2021. http://dx.doi.org/10.1201/9781003218869-9.
Full text
7
Yang, Cheng, Chuan Shi, Zhiyuan Liu, Cunchao Tu, and Maosong Sun. "Network Embedding for Graphs with Node Contents." In Network Embedding, 59–73. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-031-01590-8_5.
Full text
8
Mann, Genivika, Alishiba Dsouza, Ran Yu, and Elena Demidova. "Spatial Link Prediction with Spatial and Semantic Embeddings." In The Semantic Web – ISWC 2023, 179–96. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-47240-4_10.
Full textAbstract:
AbstractSemantic geospatial applications, such as geographic question answering, have benefited from knowledge graphs incorporating information regarding geographic entities and their relations. However, one of the most critical limitations of geographic knowledge graphs is the lack of semantic relations between geographic entities. The most extensive knowledge graphs specifically tailored to geographic entities are extracted from unstructured sources, with these graphs often relying on datatype properties to describe the entities, resulting in a flat representation that lacks entity relationships. Therefore, predicting links between geographic entities is essential for advancing semantic geospatial applications. Existing neural link prediction methods for knowledge graphs typically rely on pre-existing entity relations, making them unsuitable for scenarios where such information is absent. In this paper, we tackle the challenge of predicting spatial links in sparsely interlinked knowledge graphs by introducing two novel approaches: supervised spatial link prediction (SSLP) and unsupervised inductive spatial link prediction (USLP). These approaches leverage the wealth of literal values in geographic knowledge graphs through spatial and semantic embeddings. To assess the effectiveness of our proposed methods, we conduct evaluations on the WorldKG geographic knowledge graph, which incorporates geospatial data extracted from OpenStreetMap. Our results demonstrate that the SSLP and USLP approaches substantially outperform state-of-the-art link prediction methods.
9
Rutter, Ignaz. "Simultaneous Embedding." In Beyond Planar Graphs, 237–65. Singapore: Springer Singapore, 2020. http://dx.doi.org/10.1007/978-981-15-6533-5_13.
Full text
10
Pflueger, Maximilian, David J. Tena Cucala, and Egor V. Kostylev. "GNNQ: A Neuro-Symbolic Approach to Query Answering over Incomplete Knowledge Graphs." In The Semantic Web – ISWC 2022, 481–97. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-19433-7_28.
Full textAbstract:
AbstractReal-world knowledge graphs (KGs) are usually incomplete—that is, miss some facts representing valid information. So, when applied to such KGs, standard symbolic query engines fail to produce answers that are expected but not logically entailed by the KGs. To overcome this issue, state-of-the-art ML-based approaches first embed KGs and queries into a low-dimensional vector space, and then produce query answers based on the proximity of the candidate entity and the query embeddings in the embedding space. This allows embedding-based approaches to obtain expected answers that are not logically entailed. However, embedding-based approaches are not applicable in the inductive setting, where KG entities (i.e., constants) seen at runtime may differ from those seen during training. In this paper, we propose a novel neuro-symbolic approach to query answering over incomplete KGs applicable in the inductive setting. Our approach first symbolically augments the input KG with facts representing parts of the KG that match query fragments, and then applies a generalisation of the Relational Graph Convolutional Networks (RGCNs) to the augmented KG to produce the predicted query answers. We formally prove that, under reasonable assumptions, our approach can capture an approach based on vanilla RGCNs (and no KG augmentation) using a (often substantially) smaller number of layers. Finally, we empirically validate our theoretical findings by evaluating an implementation of our approach against the RGCN baseline on several dedicated benchmarks.
Conference papers on the topic "Graphes embeddings"
1
Bourgaux, Camille, Ricardo Guimarães, Raoul Koudijs, Victor Lacerda, and Ana Ozaki. "Knowledge Base Embeddings: Semantics and Theoretical Properties." In 21st International Conference on Principles of Knowledge Representation and Reasoning {KR-2023}, 823–33. California: International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/kr.2024/77.
Full textAbstract:
Research on knowledge graph embeddings has recently evolved into knowledge base embeddings, where the goal is not only to map facts into vector spaces but also constrain the models so that they take into account the relevant conceptual knowledge available. This paper examines recent methods that have been proposed to embed knowledge bases in description logic into vector spaces through the lens of their geometric-based semantics. We identify several relevant theoretical properties, which we draw from the literature and sometimes generalize or unify. We then investigate how concrete embedding methods fit in this theoretical framework.
2
Singer, Uriel, Ido Guy, and Kira Radinsky. "Node Embedding over Temporal Graphs." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/640.
Full textAbstract:
In this work, we present a method for node embedding in temporal graphs. We propose an algorithm that learns the evolution of a temporal graph's nodes and edges over time and incorporates this dynamics in a temporal node embedding framework for different graph prediction tasks. We present a joint loss function that creates a temporal embedding of a node by learning to combine its historical temporal embeddings, such that it optimizes per given task (e.g., link prediction). The algorithm is initialized using static node embeddings, which are then aligned over the representations of a node at different time points, and eventually adapted for the given task in a joint optimization. We evaluate the effectiveness of our approach over a variety of temporal graphs for the two fundamental tasks of temporal link prediction and multi-label node classification, comparing to competitive baselines and algorithmic alternatives. Our algorithm shows performance improvements across many of the datasets and baselines and is found particularly effective for graphs that are less cohesive, with a lower clustering coefficient.
3
Bai, Yunsheng, Hao Ding, Yang Qiao, Agustin Marinovic, Ken Gu, Ting Chen, Yizhou Sun, and Wei Wang. "Unsupervised Inductive Graph-Level Representation Learning via Graph-Graph Proximity." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/275.
Full textAbstract:
We introduce a novel approach to graph-level representation learning, which is to embed an entire graph into a vector space where the embeddings of two graphs preserve their graph-graph proximity. Our approach, UGraphEmb, is a general framework that provides a novel means to performing graph-level embedding in a completely unsupervised and inductive manner. The learned neural network can be considered as a function that receives any graph as input, either seen or unseen in the training set, and transforms it into an embedding. A novel graph-level embedding generation mechanism called Multi-Scale Node Attention (MSNA), is proposed. Experiments on five real graph datasets show that UGraphEmb achieves competitive accuracy in the tasks of graph classification, similarity ranking, and graph visualization.
4
Luo, Gongxu, Jianxin Li, Hao Peng, Carl Yang, Lichao Sun, Philip S. Yu, and Lifang He. "Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural Networks." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/381.
Full textAbstract:
Graph representation learning has achieved great success in many areas, including e-commerce, chemistry, biology, etc. However, the fundamental problem of choosing the appropriate dimension of node embedding for a given graph still remains unsolved. The commonly used strategies for Node Embedding Dimension Selection (NEDS) based on grid search or empirical knowledge suffer from heavy computation and poor model performance. In this paper, we revisit NEDS from the perspective of minimum entropy principle. Subsequently, we propose a novel Minimum Graph Entropy (MinGE) algorithm for NEDS with graph data. To be specific, MinGE considers both feature entropy and structure entropy on graphs, which are carefully designed according to the characteristics of the rich information in them. The feature entropy, which assumes the embeddings of adjacent nodes to be more similar, connects node features and link topology on graphs. The structure entropy takes the normalized degree as basic unit to further measure the higher-order structure of graphs. Based on them, we design MinGE to directly calculate the ideal node embedding dimension for any graph. Finally, comprehensive experiments with popular Graph Neural Networks (GNNs) on benchmark datasets demonstrate the effectiveness and generalizability of our proposed MinGE.
5
Angonese, Silvio Fernando, and Renata Galante. "Processing Heterogeneous Graphs within Heterogeneous Data Type Embeddings to Enhance Recommender Systems." In Anais Estendidos do Simpósio Brasileiro de Banco de Dados, 137–43. Sociedade Brasileira de Computação - SBC, 2024. http://dx.doi.org/10.5753/sbbd_estendido.2024.243731.
Full textAbstract:
Embeddings represent a viable solution to address the challenge of data and information generation in heterogeneous graphs. This research presents our approach for generating and processing heterogeneous embeddings (AGHE), which are built from various data types such as text, images, and subgraphs embedded in nodes. AGHE comprises several stages, from graph creation to the generation of embedding compositions based on node features and metapaths. In the conducted experiments, simple and embedding compositions were used as input data for the Node Classification task in Recommender Systems, investigating effectiveness metrics. The outcomes achieved in our experiments are encouraging, demonstrating superior results compared to the baseline used.
6
Veira, Neil, Brian Keng, Kanchana Padmanabhan, and Andreas Veneris. "Unsupervised Embedding Enhancements of Knowledge Graphs using Textual Associations." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/725.
Full textAbstract:
Knowledge graph embeddings are instrumental for representing and learning from multi-relational data, with recent embedding models showing high effectiveness for inferring new facts from existing databases. However, such precisely structured data is usually limited in quantity and in scope. Therefore, to fully optimize the embeddings it is important to also consider more widely available sources of information such as text. This paper describes an unsupervised approach to incorporate textual information by augmenting entity embeddings with embeddings of associated words. The approach does not modify the optimization objective for the knowledge graph embedding, which allows it to be integrated with existing embedding models. Two distinct forms of textual data are considered, with different embedding enhancements proposed for each case. In the first case, each entity has an associated text document that describes it. In the second case, a text document is not available, and instead entities occur as words or phrases in an unstructured corpus of text fragments. Experiments show that both methods can offer improvement on the link prediction task when applied to many different knowledge graph embedding models.
7
Zanon, André Levi, Leonardo Rocha, and Marcelo Garcia Manzato. "O Impacto de Estratégias de Embeddings de Grafos na Explicabilidade de Sistemas de Recomendação." In Proceedings of the Brazilian Symposium on Multimedia and the Web, 231–39. Sociedade Brasileira de Computação - SBC, 2024. http://dx.doi.org/10.5753/webmedia.2024.241857.
Full textAbstract:
Explanations in recommender systems are essential in improving trust, transparency, and persuasion. Recently, using Knowledge Graphs (KG) to generate explanations gained attention due to the semantic representation of information in which items and their attributes are represented as nodes, connected by edges, representing connections among them. Model-agnostic KG explainable algorithms can be based on syntactic approaches or graph embeddings. The impact of graph embedding strategies in generating meaningful explanations still needs to be studied in the literature. To fill this gap, in this work, we evaluate the quality of explanations provided by different graph embeddings and compare them with traditional syntactic strategies. The quality of explanations was assessed using three metrics from the literature: diversity, popularity and recency. Results indicate that the embedding algorithm chosen impacts the quality of explanations and generates more balanced results regarding popularity and explanation diversity compared to syntactic approaches.
8
Fatemi, Bahare, Perouz Taslakian, David Vazquez, and David Poole. "Knowledge Hypergraphs: Prediction Beyond Binary Relations." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/303.
Full textAbstract:
Knowledge graphs store facts using relations between two entities. In this work, we address the question of link prediction in knowledge hypergraphs where relations are defined on any number of entities. While techniques exist (such as reification) that convert non-binary relations into binary ones, we show that current embedding-based methods for knowledge graph completion do not work well out of the box for knowledge graphs obtained through these techniques. To overcome this, we introduce HSimplE and HypE, two embedding-based methods that work directly with knowledge hypergraphs. In both models, the prediction is a function of the relation embedding, the entity embeddings and their corresponding positions in the relation. We also develop public datasets, benchmarks and baselines for hypergraph prediction and show experimentally that the proposed models are more effective than the baselines.
9
Chen, Muhao, Yingtao Tian, Mohan Yang, and Carlo Zaniolo. "Multilingual Knowledge Graph Embeddings for Cross-lingual Knowledge Alignment." In Twenty-Sixth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/209.
Full textAbstract:
Many recent works have demonstrated the benefits of knowledge graph embeddings in completing monolingual knowledge graphs. Inasmuch as related knowledge bases are built in several different languages, achieving cross-lingual knowledge alignment will help people in constructing a coherent knowledge base, and assist machines in dealing with different expressions of entity relationships across diverse human languages. Unfortunately, achieving this highly desirable cross-lingual alignment by human labor is very costly and error-prone. Thus, we propose MTransE, a translation-based model for multilingual knowledge graph embeddings, to provide a simple and automated solution. By encoding entities and relations of each language in a separated embedding space, MTransE provides transitions for each embedding vector to its cross-lingual counterparts in other spaces, while preserving the functionalities of monolingual embeddings. We deploy three different techniques to represent cross-lingual transitions, namely axis calibration, translation vectors, and linear transformations, and derive five variants for MTransE using different loss functions. Our models can be trained on partially aligned graphs, where just a small portion of triples are aligned with their cross-lingual counterparts. The experiments on cross-lingual entity matching and triple-wise alignment verification show promising results, with some variants consistently outperforming others on different tasks. We also explore how MTransE preserves the key properties of its monolingual counterpart.
10
Wan, Hai, Yonghao Luo, Bo Peng, and Wei-Shi Zheng. "Representation Learning for Scene Graph Completion via Jointly Structural and Visual Embedding." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/132.
Full textAbstract:
This paper focuses on scene graph completion which aims at predicting new relations between two entities utilizing existing scene graphs and images. By comparing with the well-known knowledge graph, we first identify that each scene graph is associated with an image and each entity of a visual triple in a scene graph is composed of its entity type with attributes and grounded with a bounding box in its corresponding image. We then propose an end-to-end model named Representation Learning via Jointly Structural and Visual Embedding (RLSV) to take advantages of structural and visual information in scene graphs. In RLSV model, we provide a fully-convolutional module to extract the visual embeddings of a visual triple and apply hierarchical projection to combine the structural and visual embeddings of a visual triple. In experiments, we evaluate our model on two scene graph completion tasks: link prediction and visual triple classification, and further analyze by case studies. Experimental results demonstrate that our model outperforms all baselines in both tasks, which justifies the significance of combining structural and visual information for scene graph completion.