Distance based canonical labeling algorithms with applications to graph matching

Abstract

Graphs are mathematical structures that encode pairwise relationships between objects, which are usually identified with labels. However, graphs can represent relationships between any kind of objects and a fundamental problem is to determine if two graphs are equivalent from a structural point of view. This classic problem from graph theory, called graph isomorphism, can be tackled by canonical labeling algorithms, that label the graph nodes completely based on the graph structure and independent of the nodes’ original labels. A more recent question is on how to align the nodes of two graphs that have a similar structure, a problem known as graph matching. This dissertation approaches this problem with canonical labeling algorithms. In particular, it proposes a novel approach based solely on distances, that solve the graph matching problem under some conditions while always solving graph isomorphism. Two variations are considered and both are implemented and evaluated on random graph models and real networks, under a simple edge removal model. Classic canonical labeling algorithms are also evaluated and compared to the proposed distance-based approach, which tends to be superior in aligning two similar graphs.