Accession Number:



Exact Subgraph Matching using Massively Parallel Graph Exploration and Linear Algebra: FY19 Information, Computation and Exploitation Line-Supported Program

Descriptive Note:

Technical Report

Corporate Author:

MIT Lincoln Laboratory Lexington United States

Personal Author(s):

Report Date:


Pagination or Media Count:



Exact subgraph matching, which is a well-studied algorithmic kernel that is critical for many scientific and commercial applications, is an NP-complete problem. Over the years, multiple heuristic-based and approximation-based techniques have been proposed to help alleviate this complexity. In order to apply these techniques for analysis of graphs that contain millions to billions of edges, distributed systems have provided computational scalability through search parallelization. One recent approach for leveraging computational parallelism is through the linear algebra formulation using the matrix multiply operation, which provides a mechanism for performing parallel graph traversal. Benefits of this approach are 1 a mathematically precise and concise representation, and 2 the ability to leverage specialized linear algebra accelerators and optimized libraries for high-performance analysis of large graph datasets. In this paper, we design a multi-stage, linear algebra representation and methodology for exact subgraph matching. This formulation provides a stateless discovery mechanism to explore the graph starting at multiple vertices simultaneously and performing this exploration in a massively parallel fashion. We present a preliminary analysis of the approach and demonstrate key advantages of the proposed formulation.

Subject Categories:

  • Numerical Mathematics

Distribution Statement: