@inproceedings{
bommakanti2024fugal,
title={{FUGAL}: Feature-fortified Unrestricted Graph Alignment},
author={Aditya Bommakanti and Harshith Reddy Vonteri and Konstantinos Skitsas and Sayan Ranu and Davide Mottin and Panagiotis Karras},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=SdLOs1FR4h}
}
The necessity to align two graphs, minimizing a structural distance metric, is prevalent in biology, chemistry, recommender systems, and social network analysis. Due to the problem’s NP-hardness, prevailing graph alignment methods follow a modular and mediated approach, solving the problem by restricting to the domain of intermediary graph representations or products like embeddings, spectra, and graph signals. Restricting the problem to this intermediate space may distort the original problem and are hence predisposed to miss high-quality solutions. In this paper, we propose an unrestricted method, FUGAL, which finds a permutation matrix that maps one graph to another by directly operating on their adjacency matrices with judicious constraint relaxation. Extensive experimentation demonstrates that FUGAL consistently surpasses state-of-the-art graph alignment methods in accuracy across all benchmark datasets without encumbering efficiency.
FUGAL: Feature-fortified Unrestricted Graph Alignment
Aditya Bommakanti Harshith Reddy Vonteri Konstantinos Skitsas Sayan Ranu Davide Mottin Panagiotis Karras