  Many algorithms formulate graph matching as an optimization of an objective
function of pairwise quantification of nodes and edges of two graphs to be
matched. Pairwise measurements usually consider local attributes but disregard
contextual information involved in graph structures. We address this issue by
proposing contextual similarities between pairs of nodes. This is done by
considering the tensor product graph (TPG) of two graphs to be matched, where
each node is an ordered pair of nodes of the operand graphs. Contextual
similarities between a pair of nodes are computed by accumulating weighted
walks (normalized pairwise similarities) terminating at the corresponding
paired node in TPG. Once the contextual similarities are obtained, we formulate
subgraph matching as a node and edge selection problem in TPG. We use
contextual similarities to construct an objective function and optimize it with
a linear programming approach. Since random walk formulation through TPG takes
into account higher order information, it is not a surprise that we obtain more
reliable similarities and better discrimination among the nodes and edges.
Experimental results shown on synthetic as well as real benchmarks illustrate
that higher order contextual similarities add discriminating power and allow
one to find approximate solutions to the subgraph matching problem.

Computer Vision and Pattern Recognition