Spectral Subgraph Localization

Ama Bembua Bainson, Judith Hermanns, Petros Petsinis, Niklas Aavad, Casper Dam Larsen, Tiarnan Swayne, Amit Boyarski, Davide Mottin, Alex M. Bronstein, Panagiotis Karras
Proceedings of the Second Learning on Graphs Conference, PMLR 231:7:1-7:11, 2024.

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 this Paper

BibTeX
@InProceedings{pmlr-v231-bainson24a, 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}, pages = {7:1--7:11}, year = {2024}, editor = {Villar, Soledad and Chamberlain, Benjamin}, volume = {231}, series = {Proceedings of Machine Learning Research}, month = {27--30 Nov}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v231/bainson24a/bainson24a.pdf}, url = {https://proceedings.mlr.press/v231/bainson24a.html}, 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.} }
Endnote
%0 Conference Paper %T Spectral Subgraph Localization %A Ama Bembua Bainson %A Judith Hermanns %A Petros Petsinis %A Niklas Aavad %A Casper Dam Larsen %A Tiarnan Swayne %A Amit Boyarski %A Davide Mottin %A Alex M. Bronstein %A Panagiotis Karras %B Proceedings of the Second Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2024 %E Soledad Villar %E Benjamin Chamberlain %F pmlr-v231-bainson24a %I PMLR %P 7:1--7:11 %U https://proceedings.mlr.press/v231/bainson24a.html %V 231 %X 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.
APA
Bainson, A.B., Hermanns, J., Petsinis, P., Aavad, N., Larsen, C.D., Swayne, T., Boyarski, A., Mottin, D., Bronstein, A.M. & Karras, P.. (2024). Spectral Subgraph Localization. Proceedings of the Second Learning on Graphs Conference, in Proceedings of Machine Learning Research 231:7:1-7:11 Available from https://proceedings.mlr.press/v231/bainson24a.html.

Related Material