  The alignment of two similar graphs from different domains is a well-studied
problem. In many practical usages, there is no reliable information or labels
over the vertices or edges, leaving structural similarity as the only
information available to match such a graph. In such cases, one often assumes a
small amount of already aligned vertices -- called a seed. Current
state-of-the-art scalable seeded alignment algorithms are based on percolation.
Namely, aligned vertices are used to align their neighbors and gradually
percolate in parallel in both graphs. However, percolation-based graph
alignment algorithms are still limited in scale-free degree distributions. We
here propose `IRMA' -- Iterative Repair for graph MAtching to show that the
accuracy of percolation-based algorithms can be improved in real-world graphs
with a limited additional computational cost, and with lower run time when used
in a parallel version. IRMA starts by creating a primary alignment using an
existing percolation algorithm, then it iteratively repairs the mistakes in the
previous alignment steps. We prove that IRMA improves on single-iteration
algorithms. We then numerically show that it is significantly better than all
state-of-the-art seeded graph alignment algorithms on the graphs that they
tested. In scale-free networks, many vertices have a very low degree. Such
vertices have a high probability of erroneous alignments. We show that
combining iterations with high recall but low precision in the alignment leads
in the long run to higher recall and precision for the entire alignment.
