PaperlayerView exact revision on arXiv

Source-linked AI summary

A Review of Relational Machine Learning for Knowledge Graphs

Maximilian Nickel, Kevin Murphy, Volker Tresp, Evgeniy Gabrilovich

arXiv:1503.00759v3stat.MLcs.LG

TL;DR

The paper reviews how statistical relational learning can be trained on large knowledge graphs to predict missing facts, addressing the challenge of extracting useful structure from massive relational data. It surveys latent-feature and observable-pattern models, their combination, and integration with Web information extraction; in the Knowledge Vault example, combining models improves link-prediction performance.

  • Problem

    Large knowledge graphs require scalable methods for learning relational structure and predicting missing facts, while automatically constructed graphs must combine noisy extracted information with relational evidence.

  • Method

    The paper reviews latent-feature models, observable graph-pattern models, methods combining them, and their integration with text-based information extraction for knowledge-base construction.

  • Results

    Combining ER-MLP and PRA increased AUC-ROC from 0.882 and 0.884 individually to 0.911 on a Freebase subset.

  • Takeaways & Limitations

    Statistical relational learning can support large-scale knowledge-graph completion and help construct machine-interpretable knowledge repositories from Web-extracted facts.

Abstract

from arXiv · show

Relational machine learning studies methods for the statistical analysis of relational, or graph-structured, data. In this paper, we provide a review of how such statistical models can be "trained" on large knowledge graphs, and then used to predict new facts about the world (which is equivalent to predicting new edges in the graph). In particular, we discuss two fundamentally different kinds of statistical relational models, both of which can scale to massive datasets. The first is based on latent feature models such as tensor factorization and multiway neural networks. The second is based on mining observable patterns in the graph. We also show how to combine these latent and observable models to get improved modeling power at decreased computational cost. Finally, we discuss how such statistical models of graphs can be combined with text-based information extraction methods for automatically constructing knowledge graphs from the Web. To this end, we also discuss Google's Knowledge Vault project as an example of such combination.

I. INTRODUCTION

Knowledge graphs represent entities and typed relationships as directed, relational data, enabling statistical relational learning to predict missing facts. This review surveys scalable methods for learning from such graphs and combining them with information extraction.

  • Statistical relational learning represents objects together with their relationships, producing graph-structured data rather than independent feature vectors.
  • Large knowledge graphs contain millions of nodes and billions of edges, motivating scalable methods with time at most linear in graph size.
  • SRL models learn from existing graph facts to predict new facts, including missing edges, and can be combined with Web information extraction.The paper illustrates using related facts about an entity to assess a noisy extracted fact.
  • The review distinguishes latent-variable models from statistical models that capture correlations through observable graph properties.
  • Knowledge representation: Knowledge graphs encode facts as subject-predicate-object triples, where subjects and objects are entities and predicates specify relations.Triples can be combined into a directed multigraph whose nodes are entities and whose labeled edges represent relationships.
  • Open vs. closed world assumption: Under the open world assumption, a missing triple is unknown rather than false because knowledge graphs are incomplete.The paper contrasts this with the closed world assumption, which treats non-existing triples as false.

C. Knowledge base construction

Knowledge bases can be constructed through curated, collaborative, semi-structured, or unstructured automated approaches, each balancing accuracy, scalability, and schema structure. Knowledge graphs support search, question answering, and domain-specific decision support.

  • Construction methods: Knowledge base construction methods include curated, collaborative, automated semi-structured, and automated unstructured approaches.The automated approaches extract triples using rules, regular expressions, machine learning, or natural language processing.
  • Construction methods: Curated construction typically produces highly accurate knowledge bases but does not scale well because it depends on human experts.
  • Construction methods: Collaborative construction scales better than expert curation but still leaves substantial omissions, including missing birth-place attributes for 71% of Freebase people.
  • Schemas: Semi-structured extraction has produced large, highly accurate graphs such as YAGO and DBpedia, while schema-free representations leave entity and relation meanings ambiguous.OpenIE examples may not establish whether differently named entities or relations refer to the same concepts.
  • Schemas: The paper focuses on schema-based knowledge bases, which use globally unique identifiers and a fixed vocabulary of predefined relations.
  • Uses: Knowledge graphs power entity disambiguation, semantically enriched search, exploratory search, question answering, and biomedical decision support.

E. Main tasks in knowledge graph construction and curation

Knowledge-graph curation includes predicting missing links, resolving duplicate entities, and clustering entities using both features and graph links. Statistical relational learning represents possible triples in an adjacency tensor and must handle enormous, sparse, incomplete, and noisy graphs efficiently.

  • Main tasks: Link prediction, also called knowledge-graph completion, predicts missing or possibly incorrect typed edges from graph structure.Relational models that use entity relationships can significantly outperform non-relational machine-learning methods on this task.
  • Main tasks: Entity resolution identifies objects that refer to the same underlying entity, with relational decisions propagating collectively through the graph.It can match extracted surface names to entities stored in a knowledge graph.
  • Main tasks: Link-based clustering groups entities using similarity in both their features and their links.Similarity can propagate through the knowledge graph, adding relational information to clustering.
  • Representation: Each possible entity-relation-entity triple is represented as a binary variable in a third-order adjacency tensor.The tensor encodes triple existence, while the model estimates a distribution over possible knowledge-graph worlds from observed triples.
  • Scalability: Large knowledge graphs contain enormous numbers of possible triples, most of which are false, so models must exploit sparsity while scaling at most linearly with graph size.The stated scaling target is linear in entities, relations, and observed triples.

B. Statistical properties of knowledge graphs

Knowledge graphs contain deterministic rules alongside softer statistical regularities, including homophily, block structure, and long-range dependencies. The review organizes relational models around latent features, observable graph features, and local interactions, emphasizing scalable probabilistic and score-based formulations.

  • Graph regularities: Knowledge graphs combine deterministic rules such as type constraints and transitivity with softer statistical patterns that have predictive power.These patterns are useful despite not being universally true.
  • Graph regularities: Homophily is the tendency for entities with similar characteristics to be related, while block structure groups entities with similar cross-group relationships.In multi-relational graphs, homophily is also called autocorrelation.
  • Graph regularities: Relational graphs can contain global, long-range dependencies spanning multiple entities and relation types.A birth-city path can statistically connect a person’s birthplace to citizenship through intermediate relations.
  • Caveat: Statistical models applied to incomplete knowledge graphs can be affected by skewed input distributions and therefore require appropriately cautious interpretation.Wikipedia-derived graphs inherit distributional skew from Wikipedia itself.
  • Model classes: The review distinguishes latent-feature models, observed-graph-feature models, and Markov random fields as three ways to model correlations among triples.It mainly focuses on the first two families and their combination, while treating Markov random fields separately.
  • Model formulations: Probabilistic models use a score function and conditional-independence assumptions, whereas score-based models optimize criteria such as the margin between existing and non-existing triples.Probabilities can be derived from score-based models using Platt scaling.
  • Latent models: Latent-feature models explain triples through interactions among latent representations of entities and relations.The review notes that inferred latent features are typically difficult to interpret.

A. RESCAL: A bilinear model

RESCAL models triples through bilinear interactions between shared latent entity representations and relation-specific weights. Its tensor structure supports global dependency modeling, efficient estimation, scalable prediction, and several relational learning applications.

  • RESCAL scores each triple by a weighted sum of pairwise interactions between the latent features of its two entities.The relation-specific matrix W_k specifies interactions between latent features for relation k.
  • Shared entity representations let RESCAL propagate information across triples and capture global dependencies during joint parameter learning.The same entity representation is used across subject and object roles and across relation types.
  • RESCAL’s tensor factorization connects it to matrix-based representations, recommendation systems, and traditional tensor factorization methods.For relation k, all scores can be written as F_k = E W_k E^T.
  • After training, triple-score prediction takes O(H_e^2) time and is independent of graph size, while training still captures global dependencies.This decouples prediction cost from the number of entities and edges in the graph.
  • RESCAL has achieved state-of-the-art results across relationship prediction, entity resolution, link-based clustering, and taxonomy creation.Reported applications include large knowledge graphs such as YAGO and DBpedia.

C. Matrix factorization methods

Matrix factorization alternatives reshape knowledge-graph tensors or construct neural composite representations. These choices trade information preservation, parameter count, scalability, and expressive interaction modeling.

  • Matrix factorization methods: Matrix factorizations that reshape adjacency tensors into matrices lose relational information and can require O(N_e^2 H_e + N_r H_e) parameters.Subject-object or subject–relation/object reshaping can discard shared-object structure and increase memory requirements.
  • Matrix factorization methods: RESCAL instead requires O(N_e H_e + N_r H_e^2) parameters, preserving shared entity representations across relations.This comparison explains the parameter advantage of tensor factorization over the described matrix formulations.
  • Neural composite models: E-MLP forms composite entity-pair representations with concatenation and an additive hidden layer before predicting relation existence.The hidden layer combines weighted components of the two entity representations and applies a nonlinear function.
  • Neural composite models: Unlike RESCAL’s all-pairs tensor product, E-MLP learns adaptive feature interactions, potentially reducing parameters when many relations exist.The adaptive interaction matrices do not model every possible latent-feature pair explicitly.
  • Neural composite models: ER-MLP embeds relations and uses a global weight vector, requiring fewer parameters than E-MLP because its intermediate matrix is relation-independent.The paper reports ER-MLP’s use in the Knowledge Vault project.
  • Neural composite models: ER-MLP places semantically related relations near one another in embedding space, including parents, spouse, and birthplace near children.This example comes from a 60-dimensional model trained on Freebase.

E. Neural tensor networks

Neural tensor networks combine bilinear interactions with additive neural layers, while distance and translation models encode relations through transformed or offset latent representations. Their expressive power involves parameter and modeling trade-offs.

  • Neural tensor networks: Neural tensor networks combine traditional MLP layers with bilinear relation-specific interactions.Their bilinear hidden layer is formed from weighted multiplicative terms, alongside the additive layer from E-MLP.
  • Neural tensor networks: NTN generalizes RESCAL and adds E-MLP’s additive layer, but its larger parameter count can cause overfitting on relatively small datasets.The cited results report overfitting for the datasets studied in those papers.
  • Distance and translation models: Latent distance models assign higher relationship probability when entities’ latent representations are closer under a distance measure.This approach originated in uni-relational social-network modeling before extension to multiple relations.
  • Distance and translation models: Structured Embedding transforms global entity representations with relation-specific matrices learned so linked pairs rank closer than non-linked pairs.The transformations are learned using a ranking loss.
  • Distance and translation models: TransE reduces parameters relative to Structured Embedding by translating entity representations with relation-specific offsets instead of matrix multiplications.Its triple score is defined from the distance between the translated subject representation and the object representation.

G. Comparison of models

Observable graph models use neighborhoods, paths, random walks, or mined rules to predict links directly from graph structure. Their central trade-off is predictive reach versus computational cost, with PRA providing an interpretable multi-relational approach.

  • Similarity-based models: Local similarity indices are fast and neighborhood-scalable but cannot capture long-range or global dependencies.Their features depend only on the direct neighborhoods of the entities involved.
  • Similarity-based models: Global similarity indices often predict better than local indices but require greater computational cost because they use all paths or random walks.Quasi-local indices bound path or walk length to balance predictive accuracy and complexity.
  • Rule mining: Rule-mining systems extract logical rules from observed graph variables and use them to infer new links, with interpretability as a key advantage.AMIE handles the open-world assumption and has been reported up to three orders of magnitude faster than ALEPH on large knowledge graphs.
  • Path Ranking Algorithm: PRA uses probabilities of bounded relation paths as features and predicts missing-edge probabilities with logistic regression.Its path features can be obtained by enumerating type-consistent paths or by random sampling when relations are numerous.
  • Path Ranking Algorithm: PRA’s learned paths are interpretable as weighted Horn-rule bodies, such as inferring a person’s college from drafting and school relations.The rule weight indicates how predictive the path body is for the target relation.
  • Path Ranking Algorithm: 0.884 AUC-ROC for PRA was nearly identical to ER-MLP’s 0.882 on Knowledge Vault link prediction.The paper also reports PRA outperforming FOIL on link prediction in NELL.

VI. COMBINING LATENT AND GRAPH FEATURE MODELS

Latent feature and graph feature models capture complementary relational patterns, so combining them can improve prediction while reducing computational cost. The section reviews joint and stacked ways to combine these model families.

  • Latent feature models capture global relational patterns, whereas graph feature models capture local and quasi-local patterns.
  • Tensor factorization can be inefficient for relations with many strongly connected components, while graph models can exploit observable relational structure.For marriedTo, the reverse edge or shared children can support prediction.
  • Combining latent and graph-based models can increase predictive performance and typically speed training.
  • ARE combines RESCAL with PRA so the latent model learns residual errors, enabling lower latent dimensionality and faster training.The combined model also reports increased accuracy.
  • Stacking fits prediction systems separately and feeds their outputs into a fusion model, but the individual models cannot cooperate during training.Separate RESCAL and PRA models may require more latent features than jointly trained models.

VII. TRAINING SRL MODELS ON KNOWLEDGE GRAPHS

Training SRL models on knowledge graphs requires handling incomplete positive-only data, choosing negative examples or ranking objectives, and exploiting scalable optimization methods.

  • Knowledge graphs usually provide positive triples without explicit false facts, making all-positive training prone to overgeneralization.
  • The closed-world assumption labels all type-consistent triples absent from the graph as false, but incompleteness can violate this assumption.
  • Type, value-range, and functional constraints can generate negative examples that are certainly false when they violate hard constraints.
  • The local-closed-world assumption treats missing objects as false for observed subject-predicate pairs, fitting functional but not set-valued relations.
  • Pairwise ranking compares observed triples with assumed-false triples without requiring the latter to be genuinely negative.It permits arbitrary scoring functions whose larger values indicate more likely-correct triples.
  • Stochastic gradient descent scales by sampling one positive and one negative example per iteration, whereas alternating least squares can be faster for suitable squared-loss models.

D. Model selection

Graphical models represent dependencies among possible facts, but unrestricted relational dependencies are intractable; templates and approximations make learning more manageable.

  • Without conditional independence, each possible fact may depend on nearly every other fact, making joint-distribution estimation quickly intractable.
  • Template-based graphical models restrict dependencies to a small fraction of possibilities to obtain tractable models.
  • Dependency graphs connect random variables representing possible facts, rather than representing the facts themselves as knowledge graphs do.
  • Markov random fields use clique potentials and a partition function to define a probability distribution over possible worlds.
  • Markov logic grounds logical formulae over type-consistent entity assignments, with formula weights favoring satisfied or violated worlds according to their sign.

B. Inference

Inference in graphical models is difficult to scale, whereas Knowledge Vault combines SRL priors with Web extraction to construct and score large knowledge bases. Its latent–graph model combination improves link prediction and increases high-confidence triples.

  • B. Inference: Graphical-model inference is generally intractable, so approximate methods are required.
  • D. Discussion: MRF approaches are flexible but harder to scale for inference and learning than observable- or latent-feature models.
  • KNOWLEDGE VAULT: RELATIONAL LEARNING FOR: Knowledge Vault extracts facts from Web text, tables, page structure, and human annotations, then uses an SRL prior to score new edges.
  • KNOWLEDGE VAULT: RELATIONAL LEARNING FOR: Knowledge Vault combines ER-MLP and PRA through stacking for link prediction.
  • KNOWLEDGE VAULT: RELATIONAL LEARNING FOR: AUC-ROC increased from 0.882 for ER-MLP and 0.884 for PRA to 0.911 for their combination.
  • KNOWLEDGE VAULT: RELATIONAL LEARNING FOR: High-confidence triples increased from 100M using extractors alone to 271M using extractors plus the prior.

X. EXTENSIONS AND FUTURE WORK

The paper extends knowledge-graph modeling beyond binary relations and addresses constraints, scalability, querying, extraction quality, and the broader limits of current knowledge graphs.

  • Non-binary relations: Unary relations can be learned jointly with binary relations through tensor-matrix factorization using a shared latent representation of entities.The likelihood function may be modified to accommodate binary and unary data types.
  • Non-binary relations: Higher-arity relations can be represented with auxiliary nodes or higher-order tensors, while YAGO2 explicitly models temporal and spatial information in SPOTL format.Auxiliary nodes preserve correspondence among participants in a relation; higher-order tensor and neural-network models generalize RESCAL to these settings.
  • Temporal and spatial information: Temporal facts remain challenging because inferring a fact’s duration from text is not necessarily related to the source timestamp.The Knowledge Vault was planned to model temporal facts, but the paper characterizes this extension as non-trivial.
  • Constraints: Ontology-based materialization can be computationally demanding, while hard constraints are often violated in real-world data; machine learning can tolerate contradictory evidence.Approximate type constraints can instead be learned from observed subject and object types, but standard models do not explicitly enforce functional constraints.
  • Querying and extraction: RESCAL and Knowledge Vault support probabilistic triple queries, but join queries involving existentially quantified variables are expensive in probabilistic databases.Automatically constructed knowledge bases also depend on source quality, and automatic extraction can violate the assumption that sources explicitly state the extracted facts.
  • Future work: Knowledge graphs support question answering and search applications, yet current systems still lack many common-sense and procedural facts.Representing, learning, and reasoning with these forms of knowledge is identified as a next frontier for AI and machine learning.

XII. APPENDIX

The appendix establishes that RESCAL is a special case of the neural tensor network by matching its bilinear structure to the NTN formulation.

  • RESCAL is a special case of NTN: RESCAL is a special case of the neural tensor model (NTN).The appendix derives this relationship by specializing the NTN’s components.
  • RESCAL is a special case of NTN: The appendix uses matrices B_k to select corresponding entries from entity representations when expressing the RESCAL interaction.B_k contains zeros except for a single 1-position structure that extracts the relevant entries.
  • RESCAL is a special case of NTN: Setting the NTN’s additional matrix component to empty and its activation function to the identity yields the RESCAL form.This specialization removes the additional nonlinear contribution from the NTN equation.
Loading 1503.00759v3…