Efficient and Expressive Knowledge Base Completion Using Subgraph Feature Extraction

We explore some of the practicalities of using random walk inference methods, such as the Path Ranking Algorithm (PRA), for the task of knowledge base completion. We show that the random walk probabilities computed (at great expense) by PRA provide no discernible benefit to performance on this task, so they can safely be dropped. This allows us to define a simpler algorithm for generating feature matrices from graphs, which we call subgraph feature extraction (SFE). In addition to being conceptually simpler than PRA, SFE is much more efficient, reducing computation by an order of magnitude, and more expressive, allowing for much richer features than paths between two nodes in a graph. We show experimentally that this technique gives substantially better performance than PRA and its variants, improving mean average precision from .432 to .528 on a knowledge base completion task using the NELL KB.

• Publication year

  2015

• Venue

  Conference on Empirical Methods in Natural Language Processing

• Publication date

  2015-09-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.18653/v1/D15-1173
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Compositional Vector Space Models for Knowledge Base Completion

  2015influential reference
• Scalable Semantic Parsing with Partial Ontologies

  2015cited by this paper
• Combining Vector Space Embeddings with Symbolic Logical Inference over Open-Domain Text

  2015cited by this paper
• Never-Ending Learning

  2015influential reference
• Reducing the Rank in Relational Factorization Models by Including Observable Patterns

  2014cited by this paper
• Knowledge Graph Embedding by Translating on Hyperplanes

  2014cited by this paper
• Incorporating Vector Space Similarity in Random Walk Inference over Knowledge Bases

  2014influential reference
• Knowledge base completion via search-based question answering

  2014cited by this paper
• Knowledge vault: a web-scale approach to probabilistic knowledge fusion

  2014influential reference
• Effective Blending of Two and Three-way Interactions for Modeling Multi-relational Data

  2014cited by this paper
• Typed Tensor Decomposition of Knowledge Bases for Relation Extraction

  2014cited by this paper
• Semantic Parsing on Freebase from Question-Answer Pairs

  2013cited by this paper
• Programming with personalized pagerank: a locally groundable first-order probabilistic logic

  2013cited by this paper
• Relation Extraction with Matrix Factorization and Universal Schemas

  2013cited by this paper
• Improving Learning and Inference in a Large Knowledge-Base using Latent Syntactic Cues

  2013cited by this paper
• Connecting Language and Knowledge Bases with Embedding Models for Relation Extraction

  2013cited by this paper
• Reasoning With Neural Tensor Networks for Knowledge Base Completion

  2013cited by this paper
• Translating Embeddings for Modeling Multi-relational Data

  2013cited by this paper
• Advances in Automated Knowledge Base Construction

  2013cited by this paper
• DBpedia: A Multilingual Cross-domain Knowledge Base

  2012cited by this paper
• Reading The Web with Learned Syntactic-Semantic Inference Rules

  2012cited by this paper
• Multi-instance Multi-label Learning for Relation Extraction

  2012cited by this paper
• Weakly Supervised Training of Semantic Parsers

  2012cited by this paper
• Efficient Random Walk Inference with Knowledge Bases

  2012cited by this paper
• A Three-Way Model for Collective Learning on Multi-Relational Data

  2011cited by this paper
• Random Walk Inference and Learning in A Large Scale Knowledge Base

  2011influential reference
• Knowledge-Based Weak Supervision for Information Extraction of Overlapping Relations

  2011influential reference
• Learning Structured Embeddings of Knowledge Bases

  2011cited by this paper
• Relational retrieval using a combination of path-constrained random walks

  2010cited by this paper
• Distant supervision for relation extraction without labeled data

  2009cited by this paper
• Freebase: a collaboratively created graph database for structuring human knowledge

  2008influential reference
• Markov logic networks

  2006cited by this paper

• EXP-GNN: Towards expressive propagation function design for graph neural network-based knowledge graph completion

  2026cites this paper
• Knowledge graph reasoning: Mainstream methods, applications and prospects

  2025cites this paper
• Fact Checking Knowledge Graphs - A Survey

  2025influential citation
• StruProKGR: A Structural and Probabilistic Framework for Sparse Knowledge Graph Reasoning

  2025cites this paper
• A Survey of Task-Oriented Knowledge Graph Reasoning: Status, Applications, and Prospects

  2025cites this paper
• Research hypothesis generation over scientific knowledge graphs

  2025cites this paper
• GC-PTransE: multi-step attack inference method based on graph convolutional neural network and translation embedding

  2025cites this paper
• Substitutability-Based Graph Node Pricing

  2025cites this paper
• Improving plant functional annotation from knowledge graphs using Graph Neural Networks

  2025cites this paper
• From data to insights: the application and challenges of knowledge graphs in intelligent audit

  2024cites this paper
• xLP: Explainable Link Prediction for Master Data Management

  2024cites this paper
• HybridFC: A Hybrid Fact-Checking Approach for Knowledge Graphs

  2024cites this paper
• Leveraging Non-Parametric Reasoning With Large Language Models for Enhanced Knowledge Graph Completion

  2024cites this paper
• Empowering Large Language Model Reasoning : Hybridizing Layered Retrieval Augmented Generation and Knowledge Graph Synthesis

  2024cites this paper
• Structure-Information-Based Reasoning over the Knowledge Graph: A Survey of Methods and Applications

  2024influential citation
• GUSTAVO PADILHA POLLETI EXPLANATION GENERATION FOR CONVERSATIONAL RECOMMENDATION SYSTEMS BASED ON KNOWLEDGE EMBEDDINGS

  2023influential citation
• LogicDP: Creating Labels for Graph Data via Inductive Logic Programming

  2023cites this paper
• Automatic Extraction of Effective Relations in Knowledge Graph for a Recommendation Explanation System

  2023cites this paper
• Application of graph neural network and feature information enhancement in relation inference of sparse knowledge graph

  2023cites this paper
• A Survey of Advanced Information Fusion System: from Model-Driven to Knowledge-Enabled

  2023cites this paper
• Knowledge Graph Completion with Counterfactual Augmentation

  2023cites this paper
• TemporalFC: A Temporal Fact Checking Approach over Knowledge Graphs

  2023cites this paper
• Comprehensible Artificial Intelligence on Knowledge Graphs: A survey

  2023cites this paper
• Knowledge graph and knowledge reasoning: A systematic review

  2022cites this paper
• Explainable Knowledge Graph Embedding: Inference Reconciliation for Knowledge Inferences Supporting Robot Actions

  2022cites this paper
• Learning Cyber Threat Intelligence Knowledge Graph Embedding with Heterogeneous Relation Networks Based on Multi-Head Relational Graph Attention

  2022cites this paper
• Recent Advances in Neural-symbolic Systems: A Survey

  2022cites this paper
• Relational Context Enhanced Dual Path Reasoning for Fact Prediction in Knowledge Graph

  2022cites this paper
• A survey of hybrid knowledge reasoning oriented to KG

  2022cites this paper
• A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs

  2022cites this paper
• Completing Scientific Facts in Knowledge Graphs of Research Concepts

  2022influential citation
• Discover Important Paths in the Knowledge Graph Based on Dynamic Relation Confidence

  2022cites this paper
• Rescue decision via Earthquake Disaster Knowledge Graph reasoning

  2022cites this paper
• Learning explainable templated graphical models

  2022influential citation
• Learning Rules With Attributes and Relations in Knowledge Graphs

  2022cites this paper
• A comprehensive overview of knowledge graph completion

  2022cites this paper
• Construction and application of COVID-19 infectors activity information knowledge graph

  2022cites this paper
• Explaining automatic answers generated from knowledge base embedding models.

  2022cites this paper
• Enriching Relation Extraction with OpenIE

  2022cites this paper
• Learning to Efficiently Propagate for Reasoning on Knowledge Graphs

  2022cites this paper
• An Embedding-Based Approach to Rule Learning in Knowledge Graphs

  2021cites this paper
• Knowledge Inference and Knowledge Completion Methods using Neuro-Symbolic Inductive Rules

  2021influential citation
• Capacity and Bias of Learned Geometric Embeddings for Directed Graphs

  2021cites this paper
• Transductive Data Augmentation with Relational Path Rule Mining for Knowledge Graph Embedding

  2021cites this paper
• Modeling path information for knowledge graph completion

  2021cites this paper
• Reproducing and Explaining Entity and Relation Embeddings for Link Prediction in Knowledge Graphs

  2021cites this paper
• A path-based relation networks model for knowledge graph completion

  2021cites this paper
• CAFE: Knowledge graph completion using neighborhood-aware features

  2021cites this paper
• Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction

  2021cites this paper
• Overview of Knowledge Graph Completion Algorithms Based on Representation Learning

  2021cites this paper
• Semantic Relations Between Nominals, Second Edition

  2021cites this paper
• IFTA: Iterative filtering by using TF-AICL algorithm for Chinese encyclopedia knowledge refinement

  2021cites this paper
• Competitive Relationship Prediction for Points of Interest: A Neural Graphlet Based Approach

  2021cites this paper
• On Training Knowledge Graph Embedding Models

  2021cites this paper
• Graph-based service recommendation in Social Internet of Things

  2021cites this paper
• Temporal knowledge completion with context-aware embeddings

  2021cites this paper
• Learning Symbolic Rules for Interpretable Deep Reinforcement Learning

  2021cites this paper
• Application and evaluation of knowledge graph embeddings in biomedical data

  2021cites this paper
• REMOD: Relation Extraction for Modeling Online Discourse

  2021cites this paper
• A Schema-Driven Synthetic Knowledge Graph Generation Approach With Extended Graph Differential Dependencies (GDDxs)

  2021cites this paper
• A survey on neural-symbolic learning systems

  2021cites this paper
• Predicting Polypharmacy Side-effects Using Knowledge Graph Embeddings.

  2020influential citation
• Scrutinizer

  2020cites this paper
• Guiding Graph Embeddings using Path-Ranking Methods for Error Detection innoisy Knowledge Graphs.

  2020cites this paper
• A Review of Inference Methods Based on Knowledge Graph

  2020cites this paper
• Reliable Knowledge Graph Path Representation Learning

  2020cites this paper
• Error detection in Knowledge Graphs: Path Ranking, Embeddings or both?

  2020cites this paper
• Continuous and Interactive Factual Knowledge Learning in Verification Dialogues

  2020cites this paper
• IntKB: A Verifiable Interactive Framework for Knowledge Base Completion

  2020cites this paper
• Efficient Rule Learning with Template Saturation for Knowledge Graph Completion

  2020cites this paper
• Modeling relation paths for knowledge base completion via joint adversarial training

  2020cites this paper
• Biological applications of knowledge graph embedding models

  2020cites this paper
• Computational Fact Validation from Knowledge Graph using Structured and Unstructured Information

  2020cites this paper
• A survey of embedding models of entities and relationships for knowledge graph completion

  2020cites this paper
• Hybrid reasoning in knowledge graphs: Combing symbolic reasoning and statistical reasoning

  2020cites this paper
• A Graph-Based Framework for Structured Prediction Tasks in Sanskrit

  2020cites this paper
• Distributed representation of knowledge graphs with subgraph-aware proximity

  2020cites this paper
• Path-based reasoning approach for knowledge graph completion using CNN-BiLSTM with attention mechanism

  2020cites this paper
• Semantic Relations and Deep Learning

  2020cites this paper
• Knowledge Graphs: An Information Retrieval Perspective

  2020cites this paper
• Explanations within Conversational Recommendation Systems: Improving Coverage through Knowledge Graph Embeddings

  2020cites this paper
• Link Prediction using Graph Neural Networks for Master Data Management

  2020cites this paper
• A review: Knowledge reasoning over knowledge graph

  2020cites this paper
• CAFE: Fact Checking in Knowledge Graphs using Neighborhood-Aware Features

  2020influential citation
• Towards Learning Instantiated Logical Rules from Knowledge Graphs

  2020cites this paper
• Interactive Factual Knowledge Learning in Dialogues

  2020cites this paper
• Automatic detection of relation assertion errors and induction of relation constraints

  2020cites this paper
• Learn to Explain Efficiently via Neural Logic Inductive Learning

  2019cites this paper
• Exploiting Explicit Paths for Multi-hop Reading Comprehension

  2019cites this paper
• MMKG: Multi-Modal Knowledge Graphs

  2019cites this paper
• Debiasing Vandalism Detection Models at Wikidata

  2019cites this paper
• Knowledge Base Completion by Inference from Both Relational and Literal Facts

  2019cites this paper
• Relation path feature embedding based convolutional neural network method for drug discovery

  2019cites this paper
• Link Prediction Using Multi Part Embeddings

  2019cites this paper
• Drug target discovery using knowledge graph embeddings

  2019cites this paper
• Learning Temporal Rules from Knowledge Graph Streams

  2019cites this paper
• Abstract Graphs and Abstract Paths for Knowledge Graph Completion

  2019cites this paper
• Discovering Patterns for Fact Checking in Knowledge Graphs

  2019influential citation
• Path Ranking with Attention to Type Hierarchies

  2019influential citation
• AYNEC: All You Need for Evaluating Completion Techniques in Knowledge Graphs

  2019cites this paper