Spectral Subgraph Localization
Abstract
Several graph analysis problems are based on some variant of subgraph isomorphism: Given two graphs, G and Q, does G contain a subgraph isomorphic to Q? As this problem is NP-complete, past work usually avoids addressing it explicitly. In this paper, we propose a method that localizes, i.e., finds the best-match position of, Q in G, by aligning their Laplacian spectra and enhance its stability via bagging strategies; we relegate the finding of an exact node correspondence from Q to G to a subsequent and separate graph alignment task. We demonstrate that our localization strategy outperforms a baseline based on the state-of-the-art method for graph alignment in terms of accuracy on real graphs and scales to hundreds of nodes as no other method does.
Cite
Text
Bainson et al. "Spectral Subgraph Localization." Proceedings of the Second Learning on Graphs Conference, 2023.Markdown
[Bainson et al. "Spectral Subgraph Localization." Proceedings of the Second Learning on Graphs Conference, 2023.](https://mlanthology.org/log/2023/bainson2023log-spectral/)BibTeX
@inproceedings{bainson2023log-spectral,
title = {{Spectral Subgraph Localization}},
author = {Bainson, Ama Bembua and Hermanns, Judith and Petsinis, Petros and Aavad, Niklas and Larsen, Casper Dam and Swayne, Tiarnan and Boyarski, Amit and Mottin, Davide and Bronstein, Alex M. and Karras, Panagiotis},
booktitle = {Proceedings of the Second Learning on Graphs Conference},
year = {2023},
pages = {7:1-7:11},
volume = {231},
url = {https://mlanthology.org/log/2023/bainson2023log-spectral/}
}