PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Exploit Long-term Relational Dependencies in Knowledge Graphs

Lingbing Guo, Zequn Sun, Wei Hu

arXiv:1905.04914v1cs.AIcs.CLcs.LG

TL;DR

KG embedding methods based mainly on triples have limited ability to capture long-term relational dependencies and propagate information across KGs. The paper proposes recurrent skipping networks with residual learning over relational paths within an end-to-end framework, achieving superior entity-alignment performance and competitive KG-completion results.

  • Problem

    Triple-level KG embedding lacks long-term relational modeling and efficient semantic-information propagation, especially for cross-KG embedding.

  • Method

    RSNs combine recurrent neural networks with residual learning to model relational paths, using biased random walks within an end-to-end framework for different KG embedding tasks.

  • Results

    RSNs significantly outperformed several state-of-the-art embedding-based methods for entity alignment and achieved competitive performance for KG completion.

  • Takeaways & Limitations

    Path-level learning with RSNs provides superior entity-alignment performance and competitive KG-completion performance within one framework.

  • Takeaways & Limitations

    RSNs perform better on entity alignment than KG completion because their focus on long paths limits performance on triple-based prediction.

Abstract

from arXiv · show

We study the problem of knowledge graph (KG) embedding. A widely-established assumption to this problem is that similar entities are likely to have similar relational roles. However, existing related methods derive KG embeddings mainly based on triple-level learning, which lack the capability of capturing long-term relational dependencies of entities. Moreover, triple-level learning is insufficient for the propagation of semantic information among entities, especially for the case of cross-KG embedding. In this paper, we propose recurrent skipping networks (RSNs), which employ a skipping mechanism to bridge the gaps between entities. RSNs integrate recurrent neural networks (RNNs) with residual learning to efficiently capture the long-term relational dependencies within and between KGs. We design an end-to-end framework to support RSNs on different tasks. Our experimental results showed that RSNs outperformed state-of-the-art embedding-based methods for entity alignment and achieved competitive performance for KG completion.

1. Introduction

Knowledge graph embedding methods often learn from local triples, limiting long-term relational modeling and information propagation. The paper proposes RSNs and an end-to-end path-level framework to address these limitations across KG tasks.

  • Existing KG Embedding: KG embedding commonly assumes that similar entities have similar relational roles and learns embeddings from triples and 1-hop neighbors.This triple-level paradigm includes translational, compositional, and neural models.
  • Limitations: Triple-level learning has limited expressiveness for entities with shared local neighbors or few relational triples.The latter are long-tail entities whose embeddings receive limited attention.
  • Limitations: Triple-level propagation across KGs depends on seed alignments, limiting information transfer to long-tail entities and entities far from seeds.Multi-hop propagation through separate mini-batches can also reduce efficiency in cross-KG embedding.
  • Proposed Method: RSNs learn from relational paths, which provide richer relational dependencies than triples while retaining local entity information.The method additionally creates reverse relations to enhance path connectivity.
  • Proposed Method: RSNs use residual learning from direct subject entities to preserve local information that conventional RNN path modeling can overlook.This design addresses the problem of hidden states mixing prior context and obscuring the subject entity.
  • Framework and Results: The end-to-end framework samples paths with biased random walks and supports different KG embedding tasks.The walks control path depth and cross-KG bias; type-based noise-constrained estimation is also introduced for path-based negative sampling.
  • Framework and Results: RSNs significantly outperformed several state-of-the-art embedding methods for entity alignment and achieved competitive performance for KG completion.The framework is evaluated across different KG embedding tasks.

2. Related Work

Prior KG embedding work includes path-based, network-walk, translational, complex-valued, rotational, neural, and entity-alignment methods. The paper distinguishes RSNs from approaches that use paths only to enhance triple-level learning.

  • Path-level Embedding: PTransE incorporates relation inferences from paths into KG embedding but still ignores entity-level relational dependencies.It therefore remains a triple-level learning method.
  • Network Embedding: Network embedding methods such as DeepWalk and node2vec sample paths, with node2vec introducing biased random walks to control exploration.These methods model network paths with Skip-Gram rather than the RSN approach for KG relational paths.
  • KG Embedding: TransE models triples translationally, while TransH and TransR improve its treatment of complex relations.Other approaches include complex-space models such as ComplEx and rotational models such as RotatE.
  • Entity Alignment: KG embedding methods have also been applied to entity alignment, including MTransE's transition between separately trained KG spaces and JAPE's unified embedding space with attributes.These methods extend KG embedding beyond single-KG completion.

3. Recurrent Skipping Networks

RSNs model knowledge graphs through relational paths rather than isolated triples, combining recurrent processing with skipping and residual learning. Their design distinguishes entities from relations and emphasizes local triple structure while retaining longer-range dependencies.

  • Preliminaries: A knowledge graph is represented as entities connected by labeled relations, supporting tasks including entity alignment and KG completion.Entity alignment identifies cross-graph entities referring to the same real-world object, while KG completion predicts missing entities in triples.
  • Relational Paths: Relational paths alternate entities and relations, and reverse relations are added to enhance graph connectivity.The path representation captures multi-hop relational dependencies while retaining local relational information.
  • RNNs: Traditional RNNs inadequately model relational paths because they treat entities and relations identically and overlook the triple structure.The paper argues that the subject and relation in a current triple should receive greater emphasis when predicting the next entity.
  • Semantic Enhancement with Skipping Mechanism: RSNs refine RNNs with a skipping mechanism that lets an input entity directly participate in predicting its object entity.The mechanism explicitly distinguishes entity and relation roles and focuses on each triple in the path.
  • Insight of RSNs: Unlike conventional residual networks and RRNs, RSNs use the subject entity as the residual subtrahend rather than the previous hidden state.This design targets the residual between the next object and the current subject, which the paper argues may be easier to learn.
  • Insight of RSNs: The paper reports that RSNs add only a few parameters while offering an efficient way to address sequence-modeling problems in relational paths.Experiments are described as demonstrating advantages in performance and convergence speed.

4. Architecture of RSNs

The RSN framework samples deep and cross-KG relational paths, models them with recurrent skipping networks, and optimizes predictions using type-based noise contrastive estimation. Biased random walks favor deeper paths and paths crossing two KGs while retaining randomness for graph coverage.

  • The framework combines biased random-walk sampling, recurrent skipping networks, and type-based noise contrastive estimation for entity alignment and KG completion.The three modules respectively generate paths, learn KG embeddings, and evaluate RSN outputs efficiently.
  • Deep relational paths capture more relational dependencies than triples, while cross-KG paths bridge two KGs to deliver alignment information.
  • Biased random walks efficiently explore deep and cross-KG paths because enumerating all possible paths in large KGs is impractical.The method samples paths on a single KG and across two KGs rather than enumerating every path.
  • Depth-biased walks use the previous entity and current entity to favor next entities farther from the previous one, with α > 0.5 favoring deeper paths.The shortest-path distance d(e_i−1, e_i+1) ranges over {0, 1, 2}, and the depth bias uses α when the distance is 2 and 1 − α otherwise.
  • Cross-KG bias favors transitions connecting different KGs, with β > 0.5 making cross-KG moves more likely than within-KG moves.In the example, µ_c(e1, e3) = β and µ_c(e1, e4) = 1 − β, so the walk prefers e3.
  • Randomness is retained because biased walks aim to sample all graph features rather than rank paths with similar features.
  • RSN outputs are trained by predicting each next path element with noise-contrastive estimation using a small number of negative samples.Negative samples are entities or relations according to the target type, with noise probabilities based on KG frequency.

5. Experiments and Results

Experiments evaluated RSNs on entity alignment and KG completion using real-world datasets, including normal and dense entity distributions. RSNs outperformed existing embedding-based entity-alignment methods and achieved competitive KG-completion performance.

  • Experimental Setup: RSNs were evaluated on entity alignment and KG completion using real-world datasets and comparisons with state-of-the-art methods.The evaluation used four couples of entity-alignment datasets with normal and dense distributions, plus FB15K and WN18 for KG completion.
  • Entity Alignment Results: RSNs outperformed all existing embedding-based entity-alignment methods on both normal and dense datasets.The results attributed this advantage to capturing long-term dependencies through relational paths; biased random walks also improved performance over RSNs without biases.
  • Entity Alignment Results: Entity-alignment performance was significantly lower on normal datasets than dense datasets for all methods, yet RSNs retained considerable advantages.Dense datasets contain richer relational triples, while relational paths preserve more semantics than triples.
  • Entity Alignment Results: RSNs showed larger superiority on Hits@1 and MRR, which emphasize first-position and top-ranked correct entities.The paper connects these results to richer information from relational paths for identifying aligned entities.
  • KG Completion Results: On FB15K and WN18, RSNs achieved comparable KG-completion performance, outperforming translational models while trailing RotatE on FB15K.RotatE performed best on FB15K, followed by RSNs; performance gaps narrowed on WN18.
  • Explanations of the Results: Performance patterns differed across tasks: methods strong on KG completion did not necessarily retain their advantages on entity alignment.The paper suggests this may reflect whether methods model triples or learn relational dependencies in KG embeddings.
  • Explanations of the Results: RSNs performed better on entity alignment than KG completion because their focus on long paths limits performance on triple-level prediction.Sophisticated structures designed for triples can improve KG completion more directly.

6. Further Experiments

Further experiments examined convergence and random-walk length. RSNs converged faster than alternative recurrent networks, while longer paths improved Hits@1 until performance approached saturation.

  • Comparison with Alternative Networks: RSNs achieved better performance with only 1/30 epochs than RNNs and RRNs.RNNs and RRNs converged slowly because they did not consider local structures of relational paths; simply adding residual learning to RNNs provided little improvement.
  • Random-Walk Length: Hits@1 increased sharply as random-walk length grew from 5 to 15 across all eight entity-alignment datasets.This indicates that modeling longer relational paths can improve KG-embedding performance.
  • Random-Walk Length: Performance approached saturation from random-walk lengths 15 to 25.The results may indicate that RSNs reached the maximum path length at which they capture dependencies efficiently; the main experiments therefore used length 15.

7. Concluding Remarks

The paper presents RSNs as a path-level KG-embedding approach that uses biased random walks and an end-to-end framework. Experiments found superior entity-alignment performance and competitive KG-completion results.

  • Concluding Remarks: RSNs learn KG embeddings from relational paths to address limitations of sequence models for path learning.The framework samples desired paths with biased random walks and models them using RSNs.
  • Concluding Remarks: The proposed method obtained superior performance for entity alignment and competitive results for KG completion.The conclusion summarizes the paper’s reported outcome across its two evaluated tasks.

Supplementary Material for Learning to Exploit Long-term Relational Dependencies in Knowledge Graphs

The framework is introduced through an entity-alignment example and then specifies how biased random walks sample relational paths.

  • Framework Details: The framework architecture is illustrated using entity alignment as the example task.The section first explains the architecture before presenting path-sampling details.
  • Framework Details: Biased random walks are used to sample relational paths for the proposed framework.The sampling algorithm follows the architectural overview.

A.1. Architecture

For entity alignment, RSNs jointly assemble two KGs, sample relational paths with biased random walks, and learn embeddings through RSNs and type-based NCE.

  • A.1. Architecture: RSNs first assemble two KGs into a joint KG, then repeatedly sample relational paths for entity alignment.The generated paths are converted into embedding sequences and modeled by RSNs.
  • A.1. Architecture: Biased random walks control path depth and cross-KG bias while sampling from each triple rather than each entity.Precomputed depth and cross-KG biases support repeated sampling up to a maximum path length.
  • A.1. Architecture: The implementation uses two-layer LSTMs with dropout, batch normalization, Xavier initialization, and Adam optimization.These settings are used for both entity alignment and KG completion.

B. Entity Alignment Datasets

The entity-alignment datasets are sampled to represent either original or denser KG degree distributions, using degree-grouped PageRank sampling and biased random walks.

  • B. Entity Alignment Datasets: Random PageRank sampling is performed separately within degree-based entity groups to reduce its preference for high-degree entities.Group number and size may be adjusted to meet the desired sampled-data distribution.
  • B. Entity Alignment Datasets: The biased random walk algorithm initializes a path from each triple and extends it by sampling entities and relations until reaching the maximum length.Transition probabilities incorporate precomputed depth and cross-KG biases.
  • B. Entity Alignment Datasets: The normal sampled datasets best approximate the original KGs, while dense datasets are constructed to have doubled average degree.Dense datasets remove low-degree entities before sampling and resemble datasets used by prior methods.

C.1. KG Completion Results on FB15K-237

On FB15K-237, RSNs ranked behind RotatE and ConvE but remained competitive with methods focused specifically on KG completion. Additional seed-alignment experiments found RSNs more stable than BootEA as supervision decreased.

  • C.1. KG Completion Results on FB15K-237: FB15K-237 removes one side of symmetric relation pairs, producing unbalanced subject- and object-prediction results.The authors report about 10% Hits@1 for subject prediction versus about 30% for object prediction and question the dataset’s suitability.
  • C.1. KG Completion Results on FB15K-237: RotatE achieved the best FB15K-237 results, followed by ConvE and RSNs.RSNs nevertheless achieved comparable or better performance than many methods specifically designed for KG completion.
  • C.1. KG Completion Results on FB15K-237: RSNs lost 7.4%, 8.2%, 16.5% and 30.2% on Hits@1 across four seed-alignment proportion intervals on the normal dataset.The corresponding BootEA losses were 11.8%, 12.0%, 22.3% and 49.8%.
  • C.1. KG Completion Results on FB15K-237: At 10% seed alignment, RSNs achieved almost twice BootEA’s Hits@1 result on the normal dataset.The authors interpret this as evidence that path modeling helps propagate identity information across KGs and reduces dependence on seed-alignment proportion.
Loading 1905.04914v1…