Towards GPU-Based Common-Sense Reasoning: Using Fast Subgraph Matching

Tran, Ha-Nguyen; Cambria, Erik; Hussain, Amir

Abstract

Background/Introduction
Common-sense reasoning is concerned with simulating cognitive human ability to make presumptions about the type and essence of ordinary situations encountered every day. The most popular way to represent common-sense knowledge is in the form of a semantic graph. Such type of knowledge, however, is known to be rather extensive: the more concepts added in the graph, the harder and slower it becomes to apply standard graph mining techniques.

Methods
In this work, we propose a new fast subgraph matching approach to overcome these issues. Subgraph matching is the task of finding all matches of a query graph in a large data graph, which is known to be a non-deterministic polynomial time-complete problem. Many algorithms have been previously proposed to solve this problem using central processing units. Here, we present a new graphics processing unit-friendly method for common-sense subgraph matching, termed GpSense, which is designed for scalable massively parallel architectures, to enable next-generation Big Data sentiment analysis and natural language processing applications.

Results and Conclusions
We show that GpSense outperforms state-of-the-art algorithms and efficiently answers subgraph queries on large common-sense graphs.

Citation

Tran, H.-N., Cambria, E., & Hussain, A. (2016). Towards GPU-Based Common-Sense Reasoning: Using Fast Subgraph Matching. Cognitive Computation, 8(6), 1074-1086. https://doi.org/10.1007/s12559-016-9418-4

• Journal Article Type: Article
• Acceptance Date: Jun 2, 2016
• Online Publication Date: Aug 8, 2016
• Publication Date: 2016-12
• Deposit Date: Oct 4, 2019
• Journal: Cognitive Computation
• Print ISSN: 1866-9956
• Electronic ISSN: 1866-9964
• Publisher: BMC
• Peer Reviewed: Peer Reviewed
• Volume: 8
• Issue: 6
• Pages: 1074-1086
• DOI: https://doi.org/10.1007/s12559-016-9418-4
• Keywords: Common-sense reasoning; Subgraph matching; GPU computing; CUDA
• Public URL: http://researchrepository.napier.ac.uk/Output/1792766