Knowledge Graph & Relational Embeddings

The paper presents a unified neural embedding framework that generalizes multiple existing knowledge base embedding models including NTN and TransE.

“We show that most existing models, including NTN […] and TransE […], can be generalized under a unified learning framework, where entities are low-dimensional vectors learned from a neural network and relations are bilinear and/or linear mapping functions.”◌ not checked against the paper’s text as it now stands

The paper demonstrates that a simple bilinear formulation achieves state-of-the-art embedding performance for link prediction compared to more complex models.

“We show that a simple bilinear formulation achieves new state-of-the-art results for the task (achieving a top-10 accuracy of 73.2% vs. 54.7% by TransE on Freebase).”◌ not checked against the paper’s text as it now stands

The paper shows that relation embeddings learned from bilinear objectives capture compositional semantics through matrix multiplication, enabling the extraction of logical rules.

“We find that embeddings learned from the bilinear objective are particularly good at capturing relational semantics, and that the composition of relations is characterized by matrix multiplication.”◌ not checked against the paper’s text as it now stands

The paper introduces an embedding-based rule extraction approach that outperforms state-of-the-art confidence-based rule mining methods for compositional reasoning.

“we demonstrate that our embedding-based rule extraction approach successfully outperforms a state-of-the-art confidence-based rule mining approach in mining Horn rules that involve compositional reasoning.”◌ not checked against the paper’s text as it now stands

This paper proposed compositionalized vector space models where entity sets are represented as real vectors and edge traversal is driven by vector-to-vector transformations to answer path queries on knowledge graphs.

“We propose performing path queries such as tad_lincoln/parents/location (Where are Tad Lincoln's parents located?) in a parallel low-dimensional vector space. Here, entity sets (boxed) are represented as real vectors, and edge traversal is driven by vector-to-vector transformations (e.g., matrix multiplication).”◌ not checked against the paper’s text as it now stands

This paper developed a compositional training objective that trains embedding models on path queries of multiple lengths rather than just single edges, which substantially improves path query answering performance.

This paper showed that embedding models can be compositionalized by interpreting them as soft edge traversal operators that recursively apply to predict paths of length greater than one.

“we interpret the base vector space model as implementing a soft edge traversal operator. This operator can then be recursively applied to predict paths. Our interpretation suggests a new compositional training objective that encourages better modeling of paths.”◌ not checked against the paper’s text as it now stands

This paper proposes holographic embeddings that use circular correlation as a compositional operator to create vector space representations of knowledge graphs.

“In this work, we propose holographic embeddings to learn compositional vector space representations of entire knowledge graphs. The proposed method is related to holographic models of associative memory in that it employs circular correlation to create compositional representations.”◌ not checked against the paper’s text as it now stands

This paper demonstrates that circular correlation achieves computational efficiency with linear memory complexity and quasilinear runtime complexity compared to the quadratic complexity of tensor product methods.

This paper shows that holographic embeddings outperform state-of-the-art methods for link prediction on knowledge graph benchmark datasets.

“Experimentally, we show that holographic embeddings are able to outperform state-of-the-art methods for link prediction on knowledge graphs and relational learning benchmark datasets.”◌ not checked against the paper’s text as it now stands

This paper establishes connections between the circular correlation compositional operator and holographic models of associative memory that store and retrieve associations.

The paper reviews latent feature models such as tensor factorization for statistical analysis of knowledge graphs.

“The first is based on latent feature models such as tensor factorization and multiway neural networks.”◌ not checked against the paper’s text as it now stands

The paper discusses how embeddings can be represented as latent vectors for objects in machine learning.

“This could be class labels, a regression score, or an unsupervised cluster id or latent vector (embedding).”◌ not checked against the paper’s text as it now stands

The paper models knowledge graphs using tensor representations where entries correspond to binary relationships between entities.

“All possible triples in E×R×E can be grouped naturally in a third-order tensor (three-way array) ∈{0,1}^××, whose entries are set such that y_ijk = 1, if the triple (e_i, r_k, e_j) exists”◌ not checked against the paper’s text as it now stands

LINE introduced a novel network embedding method designed to preserve both first-order and second-order proximity in large-scale information networks.

LINE proposed an edge-sampling algorithm that addresses gradient explosion problems caused by high variance in edge weights during stochastic gradient descent optimization.

“To address this, we propose a novel edge-sampling method, which improves both the effectiveness and efficiency of the inference. We sample the edges with the probabilities proportional to their weights, and then treat the sampled edges as binary edges for model updating. With this sampling process, the objective function remains the same and the weights of the edges no longer affect the gradients.”◌ not checked against the paper’s text as it now stands

LINE demonstrated the ability to scale to very large networks with millions of nodes and billions of edges efficiently on a single machine.

“The algorithm is very efficient, which is able to learn the embedding of a network with millions of vertices and billions of edges in a few hours on a typical single machine.”◌ not checked against the paper’s text as it now stands

The paper introduces complex-valued embeddings as a representation for knowledge graph entities and relations in link prediction.

“However, here we make use of complex valued embeddings.”◌ not checked against the paper’s text as it now stands

The paper demonstrates that complex embeddings using the Hermitian dot product can effectively handle both symmetric and antisymmetric relations while maintaining linear time and space complexity.

“The composition of complex embeddings can handle a large variety of binary relations, among them symmetric and antisymmetric relations.”◌ not checked against the paper’s text as it now stands

The paper provides a reformulation showing complex embeddings can be expressed using only real-valued vectors with real and imaginary parts separated.

“To give a clear comparison with respect to existing approaches using only real numbers, we also present an equivalent reformulation of our model that involves only real embeddings.”◌ not checked against the paper’s text as it now stands

The paper empirically shows that complex embeddings consistently outperform state-of-the-art embedding methods on standard link prediction benchmarks.

This survey provides a comprehensive structured analysis of graph embedding techniques by categorizing them into three main approaches: factorization methods, random walks, and deep learning.

The survey formally defines graph embedding as a mapping function that preserves proximity measures while representing nodes in low-dimensional vector space.

“(Graph embedding) Given a graph G=(V,E), a graph embedding is a mapping f:v_i →y_i∈ℝ^d ∀ i ∈ [n] such that d ≪ |V| and the function f preserves some proximity measure defined on graph G.”◌ not checked against the paper’s text as it now stands

The paper identifies and addresses key challenges in embedding including scalability, choice of dimensionality, and which graph properties should be preserved.

“We first introduce the embedding task and its challenges such as scalability, choice of dimensionality, and features to be preserved, and their possible solutions.”◌ not checked against the paper’s text as it now stands

The survey developed GEM, an open-source Python library that implements all presented graph embedding algorithms within a unified interface.

“We finally present the open-source Python library we developed, named GEM (Graph Embedding Methods, available at <https://github.com/palash1992/GEM>), which provides all presented algorithms within a unified interface to foster and facilitate research on the topic.”

This paper embeds items as points in a transition space where sequential relationships are modeled through translation operations.

“Items are embedded as points in a (latent) `transition space'; each user is represented as a `translation vector' in the same space.”◌ not checked against the paper’s text as it now stands

This paper represents each item with an embedding vector in the transition space to capture item characteristics and relationships.

“we learn a transition space Φ = ℝ^K, where each item i is represented with a point/vector γ⃗_i ∈Φ.”◌ not checked against the paper’s text as it now stands

This paper uses distance-based embeddings that naturally satisfy the triangle inequality property for better generalization in sparse data.

“Note that we are uncovering a metric space where (1) neighborhood captures the notion of similarity and (2) translation encapsulates various semantically complex transition relationships amongst items. In both cases, the inherent triangle inequality assumption plays an important role in helping the model to generalize well”◌ not checked against the paper’s text as it now stands

The paper proposes ConvKB, a novel embedding model that uses convolutional neural networks to capture global relationships among same dimensional entries of entity and relation embeddings.

“In ConvKB, each entity or relation is associated with an unique k-dimensional embedding. Let v_h, v_r and v_t denote k-dimensional embeddings of h, r and t, respectively. For each triple (h, r, t), the corresponding triple of k-dimensional embeddings (v_h, v_r, v_t) is represented as a k×3 input matrix. This input matrix is fed to the convolution layer where different filters of the same 1×3 shape are used to extract the global relationships among same dimensional entries of the embedding triple.”◌ not checked against the paper’s text as it now stands

The paper demonstrates that ConvKB's embedding approach achieves better link prediction performance than previous state-of-the-art embedding models on benchmark datasets.

The paper shows that ConvKB generalizes the transitional characteristics used in transition-based embedding models by modeling relationships among same dimensional entries.

“ConvKB models the relationships among same dimensional entries of the embeddings. This implies that ConvKB generalizes transitional characteristics in transition-based embedding models.”◌ not checked against the paper’s text as it now stands

The paper uses R-GCN encoders to compute entity embeddings that are then scored by a decoder function for link prediction.

“The encoder maps each entity v_i ∈𝒱 to a real-valued vector e_i ∈ℝ^d. The decoder reconstructs edges of the graph relying on the vertex representations; in other words, it scores (subject, relation, object)-triples through a function s: ℝ^d ×ℛ×ℝ^d →ℝ.”◌ not checked against the paper’s text as it now stands

The paper demonstrates that R-GCN encoder representations improve link prediction performance compared to using fixed entity embeddings alone.

“Whereas most previous approaches use a single, real-valued vector e_i for every v_i ∈𝒱 optimized directly in training, we compute representations through an R-GCN encoder with e_i = h_i^(L), similar to the graph auto-encoder model introduced in […] for unlabeled undirected graphs.”◌ not checked against the paper’s text as it now stands

The paper shows that entity representations computed by R-GCNs enable effective entity classification through softmax classifiers applied to the embedded node representations.

“Our entity classification model, similarly to […], uses softmax classifiers at each node in the graph. The classifiers take node representations supplied by a relational graph convolutional network (R-GCN) and predict the labels.”◌ not checked against the paper’s text as it now stands

RippleNet proposes a preference propagation technique that learns entity and relation embeddings through knowledge graph embedding to explore user interests.

“we propose a preference propagation technique to explore users' potential interests in his ripple sets. As shown in Figure […], each item v is associated with an item embedding v∈ℝ^d”◌ not checked against the paper’s text as it now stands

RippleNet learns user embeddings by combining multiple-order responses from iterative preference propagation across knowledge graph hops.

“The embedding of user u with respect to item v is calculated by combining the responses of all orders: u = o_u^1 + o_u^2 +... + o_u^H”◌ not checked against the paper’s text as it now stands

RippleNet uses a unified embedding approach that combines entity embeddings, relation embeddings, and item embeddings under the same tensor factorization model.

“the scoring functions of entity-entity pairs in KGE and item-entity pairs in preference propagation can thus be unified under the same calculation model.”◌ not checked against the paper’s text as it now stands

RippleNet learns entity and relation embeddings through a three-way tensor factorization method applied to knowledge graph triples.

The paper applied knowledge base embedding techniques to learn representations of heterogeneous entities in a user-item knowledge graph for recommendation.

“Inspired by the above motivation, in this paper, we design a novel collaborative filtering framework over knowledge graph. The main building block is an integration of traditional CF and knowledge-base embedding technology.”◌ not checked against the paper’s text as it now stands

The paper projected entities and relations into a unified low-dimensional embedding space using a translation-based approach.

“Inspired by […], we project each entity and relation into a unified low-dimensional embedding space. Intuitively, the embedding of a tail entity should be close to its translated head entity embedding.”◌ not checked against the paper’s text as it now stands

The paper demonstrated that structured knowledge graph embeddings significantly outperform methods that do not use structured representations for recommendation.

“Because both BPR and CFKG_buy only used the user purchase information, this observation verifies the effectiveness of using structured knowledge graph embeddings for recommendation.”◌ not checked against the paper’s text as it now stands

TuckER uses entity and relation embeddings as rows of matrices in a Tucker decomposition to score knowledge graph triples.

“We propose a model that uses Tucker decomposition for link prediction on the binary tensor representation of a knowledge graph, with entity embedding matrix 𝐄 that is equivalent for subject and object entities, i.e. 𝐄 = 𝐀 = 𝐂∈ℝ^n_e × d_e and relation embedding matrix 𝐑 = 𝐁∈ℝ^n_r × d_r”◌ not checked against the paper’s text as it now stands

TuckER encodes learned knowledge partly in embeddings and partly in a core tensor that is shared across entities and relations through multi-task learning.

“By having the core tensor 𝒲, unlike simpler models such as DistMult, ComplEx and SimplE, TuckER does not encode all the learned knowledge into the embeddings; some is stored in the core tensor and shared between all entities and relations through multi-task learning.”◌ not checked against the paper’s text as it now stands

TuckER requires entity embeddings of dimensionality equal to the number of entities and relation embeddings equal to the number of relations to achieve full expressiveness.

“Given any ground truth over a set of entities ℰ and relations ℛ, there exists a TuckER model with entity embeddings of dimensionality d_e=n_e and relation embeddings of dimensionality d_r=n_r, where n_e=|ℰ| is the number of entities and n_r = |ℛ| the number of relations, that accurately represents that ground truth.”◌ not checked against the paper’s text as it now stands

The paper uses embeddings as the core representation mechanism for learning translational relationships between users and items in the recommendation model.

“it automatically induces a preference for a user-items pair, and learns the embeddings of preference 𝐩, user 𝐮 and item 𝐢, satisfying 𝐮+𝐩≈𝐢.”◌ not checked against the paper’s text as it now stands

The paper transfers entity and relation embeddings learned from the knowledge graph to enhance the user-item interaction modeling.

“we transfer the relation embeddings as well as entity embeddings learned from KG to TUP, simultaneously training the KG completion and recommendation tasks.”◌ not checked against the paper’s text as it now stands

The paper learns joint embeddings of users, items, entities, and relations through a multi-task architecture combining recommendation and knowledge graph completion.

“KTUP is able to output not only g(u,i;p), but also a score f(e_h, e_t, r) indicating how possible the fact is true, based on the jointly learned embeddings of users 𝐮, items 𝐢, preferences 𝐩,𝐰_p, entities 𝐞 and relations 𝐫,𝐰_r.”◌ not checked against the paper’s text as it now stands

The paper proposes RotatE, which models relations as rotations in complex vector space to embed knowledge graphs for link prediction.

“Specifically, the RotatE model defines each relation as a rotation from the source entity to the target entity in the complex vector space.”◌ not checked against the paper’s text as it now stands

The paper demonstrates that RotatE can model all three important relation patterns: symmetry/antisymmetry, inversion, and composition.

The paper introduces a self-adversarial negative sampling technique to improve training of embedding models.

“we propose a novel self-adversarial negative sampling technique for efficiently and effectively training the RotatE model.”◌ not checked against the paper’s text as it now stands

The paper evaluates embeddings on four large knowledge graph benchmarks and shows RotatE significantly outperforms existing state-of-the-art embedding models.

“Experimental results on multiple benchmark knowledge graphs show that the proposed RotatE model is not only scalable, but also able to infer and model various relation patterns and significantly outperform existing state-of-the-art models for link prediction.”

The paper proposes KGAT which updates node embeddings by recursively propagating embeddings from neighboring nodes to capture high-order connectivities.

“It recursively propagates the embeddings from a node's neighbors (which can be users, items, or attributes) to refine the node's embedding, and employs an attention mechanism to discriminate the importance of the neighbors.”◌ not checked against the paper’s text as it now stands

The paper uses embedding propagation layers that update node representations by aggregating messages from connected neighbors in the knowledge graph.

“Specifically, we devise an attentive embedding propagation layer, which updates the representation of each node (it can be user, item, and entity) by aggregating messages from the connected neighbors.”◌ not checked against the paper’s text as it now stands

The paper's method transfers knowledge into the embedding space by propagating embeddings recursively along high-order relational connectivity paths.

“Instead of extracting paths, we design a neural network, Knowledge-Graph Attention Network (KGAT), to propagate knowledge embeddings recursively on the collaborative knowledge graph. It essentially passes messages along high-order relational connectivity in the embedding space.”◌ not checked against the paper’s text as it now stands

This paper surveyed knowledge graph embedding by organizing it from four aspects of representation space, scoring function, encoding models, and auxiliary information.

“Knowledge graph embedding is organized from four aspects of representation space, scoring function, encoding models, and auxiliary information.”◌ not checked against the paper’s text as it now stands

This paper reviewed representation learning methods that map entities and relations into low-dimensional vectors while capturing their semantic meanings.

“Recent advances in knowledge-graph-based research focus on knowledge representation learning (KRL) or knowledge graph embedding (KGE) by mapping entities and relations into low-dimensional vectors while capturing their semantic meanings~.”◌ not checked against the paper’s text as it now stands

This paper provided a full-view categorization of KRL into four scopes including representation space, scoring function, encoding models, and auxiliary information.

“This section reviews recent advances on distributed representation learning with rich semantic information of entities and relations form four scopes including representation space (representing entities and relations, }), scoring function (measuring the plausibility of facts, }), encoding models (modeling the semantic interaction of facts, }), and auxiliary information (utilizing external information, }).”