TL;DR

We propose GRASP, short for GRaph Alignment through SPectral Signatures, a principled approach towards detecting a good alignment among graphs, grounded on their spectral characteristics, i.e., eigenvalues and eigenvectors of their Laplacian matrices.

In this paper, we extend our previously published GRASP as follows:

• We extensively discuss the modular graph alignment framework and possible enhancements to GRASP.
• We include the recently proposed graph alignment methods S-GWL and CONE.
• We examine and provide additional experimental insights on the effects of parameter choice in GRASP, including the parameter k, i.e., the number of eigenvectors used for computations and q, i.e., the number of corresponding functions used.
• We conduct new experiments on real-world data, namely two temporal proximity networks and different variants of a PPI-network.
• We provide additional experiments examining scalability in the number of nodes in a graph.