@inproceedings{4721260671cf4444940c31f62902126b,
title = "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.",
author = "Bainson, {Ama Bembua} and Amit Boyarski and Judith Hermanns and Petros Petsinis and Niklas Aavad and Larsen, {Casper Dam} and Tiarnan Swayne and Davide Mottin and Bronstein, {Alex M} and Panagiotis Karras",
year = "2023",
language = "English",
volume = "231",
series = "Proceedings of Machine Learning Research",
publisher = "MLResearch Press",
pages = "231:7:1--7:11",
booktitle = "The Second Learning on Graphs Conference",
note = "2nd Learning on Graphs Conference, LOG 2023 ; Conference date: 27-11-2023 Through 30-11-2023",
}