GRASP: Graph Alignment through Spectral Signatures

Judith Hermanns, Anton Tsitsulin, Marina Munkhoeva, Alex Bronstein, Davide Mottin, Panagiotis Karras

APWeb-WAIM 2021

pdf | code

With a few removed edges, REGAL, an alignment method based on localfeatures, fails to correctly align the distorted Karate club graph to the original; GRASPidentifies most of nodes (correctly aligned nodes in green).

With a few removed edges, REGAL, an alignment method based on localfeatures, fails to correctly align the distorted Karate club graph to the original; GRASPidentifies most of nodes (correctly aligned nodes in green).

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 propose GRASP, a graph alignment method based on spectral graph characteristics
  • We show GRASP effectiveness in recovering real-graph align-ments
  • GRASP delivers higher accuracy as the state of the art in comparable time
  • We release the code for further comparisons