$O(p \log d)$ Subgraph Isomorphism using Stigmergic Swarming Agents

Abstract

Subgraph isomorphism compares two graphs (sets of nodes joined by edges) to determine whether they contain a common subgraph. Many applications require identifying the subgraph, not just deciding its existence. A particularly common use case, using graphs with labeled nodes, seeks to find instances of a smaller pattern graph with $p$ nodes in the larger data graph with $d$ nodes. The problem is NP-complete, so that naïve solutions are exponential in $p + d$. A wide range of heuristics have been proposed, with the best complexity $O(p^2d^2)$. This paper outlines ASSIST (Approximate Swarming Subgraph Isomorphism through Stigmergy), inspired by the ant colony optimization approach to the traveling salesperson problem. ASSIST is linearithmic, $O(p \log d)$, and also supports matching problems (such as temporally ordered edges, inexact matches, and missing nodes or edges in the data graph) that frustrate other heuristics.