  Network alignment, or the task of finding corresponding nodes in different
networks, is an important problem formulation in many application domains. We
propose CAPER, a multilevel alignment framework that Coarsens the input graphs,
Aligns the coarsened graphs, Projects the alignment solution to finer levels
and Refines the alignment solution. We show that CAPER can improve upon many
different existing network alignment algorithms by enforcing alignment
consistency across multiple graph resolutions: nodes matched at finer levels
should also be matched at coarser levels. CAPER also accelerates the use of
slower network alignment methods, at the modest cost of linear-time coarsening
and refinement steps, by allowing them to be run on smaller coarsened versions
of the input graphs. Experiments show that CAPER can improve upon diverse
network alignment methods by an average of 33% in accuracy and/or an order of
magnitude faster in runtime.
