Mentor: Dr. Andrew McCallum (CICS, UMass Amherst)
A knowledge graph (KG) is formed by the entities as nodes and relations between entities as directed edges. KG completion is the problem of answering queries of the type (
r, ?) i.e. given a query entity
e and query relation
r, find the entity
e_ans that has the relation
e. As you can imagine, this task is used to complete partial KGs by guessing missing edges.
Given a new problem, a Case-based Reasoning system:
- Retrieves similar cases seem in the past
- Reuses solutions to previously solved cases
- Revises solutions to apply to the current query
- Retains modified solutions as new cases
We adapt this system for knowledge graph completion by using the training graph as the store of solved cases. Similar entities are found by nearest neighbors using a simple one-hot representation based on connected relations (this captures the notion of entity types). Solutions are paths (sequence of relations) that reach the answer node. Then starting from the query entity, we traverse the graph using the paths collected. If such a system can achieve high accuracy, it is appealing owing to its simplicity, interpretability, and scalability.
We demonstrated that this simple system is highly performant in
A Simple Approach to Case-Based Reasoning in Knowledge Bases.
After performing an error analysis on this system, we then imposed a probabilistic structure to allow the system to weight the answers. Concretely, we use the prior probability of a path reaching the tail entity for the given query relation and the precision of that path type to downweight spurious paths. We use clustering to help aggregate probabilitities. We demonstrated in
Probabilistic Case-based Reasoning for Open-World Knowledge Graph Completion that this systems matches/outperforms baselines on FB122, WN18RR and Nell-995. Moreover, we demonstrated that this method can be applied to dynamic growing KGs with minimal overhead whereas the best embedding based methods deteriorate with successive KG updates.
Future Work: We are experimenting with extending this reasoning strategy to question answering systems. A lot of challenges arise with moving from the structured world of knowledge graphs to unstructured text.