Uncertainty-aware efficient subgraph isomorphism using graph topology

Subgraph isomorphism, also known as subgraph matching, is typically regarded as an NP-complete problem. This complexity is further compounded in practical applications where edge weights are real-valued and may be affected by measurement noise and potential missing data. Such graph matching routinely arises in applications such as image matching and map matching. Most subgraph matching methods fail to perform node-to-node matching under presence of such corruptions. We propose a method for identifying the node correspondence between a subgraph and a full graph in the inexact case without node labels in two steps - (a) extract the minimal unique topology preserving subset from the subgraph and find its feasible matching in the full graph, and (b) implement a consensus-based algorithm to expand the matched node set by pairing unique paths based on boundary commutativity. To demonstrate the effectiveness of the proposed method, a simulation is performed on the Erdos-Renyi random graphs and two case studies are performed on the image-based affine covariant features dataset and KITTI stereo dataset respectively. Going beyond the existing subgraph matching approaches, the proposed method is shown to have realistically sub-linear computational efficiency, robustness to random measurement noise, and good statistical properties. Our method is also readily applicable to the exact matching case without loss of generality. • Matching a subgraph to a graph with measurement noise and randomly missing nodes arises in many real-world applications, like template matching and 3D registration. We introduce an analytical method that robustly matches graphs and subgraphs amidst uncertainties using topological constraints. • We employ a two-stage approach whereby initially, we match a minimum topological unit between a subgraph and a full graph and in the second step, we perform consensus-based searching. • We employ massively parallelizable pairwise edge matching operations along with topological constraints to provide fast and robust solutions in both steps. • We provide theoretical justifications for the steps of the algorithm and computational complexity measure. • We provide real-life examples of template matching and stereo-matching along with simulation study to show the efficacy of the approach.