  Network alignment, or the task of finding meaningful node correspondences
between nodes in different graphs, is an important graph mining task with many
scientific and industrial applications. An important principle for network
alignment is matched neighborhood consistency (MNC): nodes that are close in
one graph should be matched to nodes that are close in the other graph. We
theoretically demonstrate a close relationship between MNC and alignment
accuracy. As many existing network alignment methods struggle to preserve
topological consistency in difficult scenarios, we show how to refine their
solutions by improving their MNC. Our refinement method, RefiNA, is
straightforward to implement, admits scalable sparse approximation, and can be
paired post hoc with any network alignment method. Extensive experiments show
that RefiNA increases the accuracy of diverse unsupervised network alignment
methods by up to 90%, making them robust enough to align graphs that are 5x
more topologically different than were considered in prior work.
