Booth Id:
SOFT018
Category:
Systems Software
Year:
2021
Finalist Names:
He, Xuerui (School: No. 2 High School of East China Normal University)
Abstract:
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 Won:
NC State College of Engineering: Alternates
Fourth Award of $500