The focus of this work is on developing fast and memory-efficient algorithms for solving large-scale versions of the standard network alignment problem.  For this problem, the goal is to find an approximate isomorphism between two large labeled graphs with over 200,000 vertices.  Our alignment objective is an edge-preserving mapping with high similarity between labels of mapped vertices.

Finding an optimum such mapping is an NP-hard problem.  We develop a distributed algorithms based on belief propagation (BP) and show that it outperforms existing heuristics for solving large instances of this problem.  The algorithm is fast and runs in minutes or seconds.  

Our main motivation for this research is to compare the Wikipedia category structure with the Library of Congress subject headings (LCSH) database.  These two databases were developed in completely different fashions.  Nevertheless, the network aligning algorithm finds a matching between the two databases, which provides evidence that their structures are similar!  Such similarity implies that the matching should help enrich both databases by suggesting missing entries and connections.