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

Citation

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

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.

Keywords
Common-sense reasoning; Subgraph matching; GPU computing; CUDA

Journal
Cognitive Computation: Volume 8, Issue 6