Overview
Four papers (2010-2015) developing the Path Ranking Algorithm (PRA), a foundational approach to relational learning and inference in knowledge graphs using constrained random walks. All from the CMU Machine Learning Department, primarily by Ni Lao and William W. Cohen.
The Core Idea
Knowledge bases can be represented as labeled directed graphs. PRA defines similarity/inference as a learned combination of “path experts” — constrained random walkers that follow specific sequences of edge labels. Each path corresponds to a Horn clause in logical inference.
Example: To infer AthletePlaysInLeague(HinesWard, NFL), PRA learns that the path AthletePlaysForTeam → TeamPlaysInLeague is a high-weight feature.
Paper 1: Relational Retrieval (Machine Learning, 2010)
The foundational PRA paper. Introduces path-constrained random walks for relational retrieval in scientific literature graphs. Significantly outperforms standard Random Walk with Restart models. Tested on 8 biology tasks.
Paper 2: Random Walk Inference in NELL (EMNLP 2011)
Applies PRA to NELL’s 500K-belief knowledge base extracted from the web. Nearly doubles precision at rank 100 compared to NELL’s earlier Horn-clause inference. Demonstrates PRA’s robustness to noisy extracted knowledge.
Paper 3: Fast Query Execution (KDD 2010)
Addresses PRA’s computational expense through fingerprinting, particle filtering, and truncation strategies. Achieves 2-100x speedups with little accuracy loss on two large scientific publication corpora.
Paper 4: Backward Random Walks (Cor-PRA)
Introduces Cor-PRA: models longer relational rules and first-order rules with constants using backward random walks for efficient feature discovery. Dramatic improvements on named entity extraction from parsed text.
Significance
PRA became the basis for knowledge graph inference in systems like NELL and Google’s Knowledge Vault, and influenced later embedding-based approaches to knowledge graph completion.
Related
- never-ending-language-learner — NELL system where PRA was applied for web-scale KB inference
- proppr-scalable-kb-inference — ProPPR: PRA’s successor connecting random walks to personalized PageRank for probabilistic logic