Boosting Graph Alignment Algorithms

Alexander Frederiksen Kyster, Simon Daugaard Nielsen, Judith Hermanns, Davide Mottin, Panagiotis Karras

CIKM 2021

pdf | video | code

The performance of graph alignment algorithms vary a lot by changing small parts of the computation

The performance of graph alignment algorithms vary a lot by changing small parts of the computation

TL;DR

Study graph alignment algorithms as modular, by:

  • Noticing that some parts of the algorithm (e.g., the matching step) can be easily substituted
  • Performing an experimental evaluation showing that the performance vary a lot with some small changes
  • Introducing enhanced versions of each algorithms
  • Opening to the possibility of modularizing graph alignment in a unified framework

In this paper:

  • We study ways to enhance each part of this modular framework.
  • We interpret three modular alignment algorithms, REGAL, CONE-Align, and GRASP in terms of the framework.
  • We propose improvements on the two most recent algorithms, CONE-Align and GRASP, interchanging, enhancing, and adding to framework components.
  • We compare CONE-Align and GRASP to each other for the first time, and show that our enhancements improve upon the state-of-the-art effectiveness with nearly no impact on efficiency.