Conclusions

We have presented a novel, computationally efficient approach to many-to-many matching of directed graphs. To match two graphs, we begin by constructing metric tree representations of the graphs. Next, we embed them in a geometric space with low distortion using a novel encoding of the graph's vertices, called spherical codes. Many-to-many graph matching now becomes a many-to-many geometric point matching problem, for which the Earth Mover's Distance algorithm is ideally suited. Moreover, by mapping a node's geometric and structural ``context'' in the graph to an attribute vector assigned to its corresponding point, we can extend the technique to deal with hierarchical graphs that represent multi-scale structure. We evaluate the technique on two major image databases, using a multi-scale image representation that captures coarse image structure, and include a set of structural perturbation experiments to show the algorithm's robustness to graph ``noise''.