A Two-Step Approach to Effectively Find Analogies in Knowledge Graphs

Overview

Analogy-making is a cognitive process of transferring information or meaning from a particular subject to another. By making analogies, we find similarities between two subjects, which helps us better understand novel concepts. In this paper, we tackle the problem of finding matching entities in knowledge graphs for a given query entity. This task can be formulated as a graph isomorphism problem, where we identify subgraphs in the entire knowledge graph that are isomorphic to a given query graph. Established methods of finding isomorphic graphs are NP-hard. Recently, state-of-the-art papers have proposed vector embeddings, random walks, and neural networks to decrease time complexity, but they are generally less accurate when edges are labeled and directed. Because of these problems, we propose a two-step approach: First, we use an iterative algorithm to calculate an entity matching matrix, which indicates the similarity scores for all node pairs (v, v') where v is in the knowledge graph and v' is in the query graph. Then, we binarize the entity matching matrix to a valid entity matching scheme while maximizing the total score. We conduct experiments on ConceptNet, a well-known commonsense knowledge graph. Our code is available on Github[1]. Results demonstrate that our method is able to efficiently find subgraphs analogous to the query graph, thus imitating the process of making analogies. [1] https://github.com/A3NC/Finding_Analogies_In_Knowledge_Graph

Awards (2)

• Fourth Award of $500 $500
• NC State College of Engineering: Alternates

Competition history

• ISEF 2021 Systems Software · Entry SOFT018

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.