Spectral Subgraph Localization

Ama Bembua Bainson, Amit Boyarski, Judith Hermanns, Petros Petsinis, Niklas Aavad, Casper Dam Larsen, Tiarnan Swayne, Davide Mottin, Alex M Bronstein, Panagiotis Karras

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

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.

OriginalsprogEngelsk
TitelThe Second Learning on Graphs Conference
Antal sider641
Vol/bind231
Publikationsdato2023
Sider231:7:1-7:11
StatusUdgivet - 2023
Begivenhed2nd Learning on Graphs Conference, LOG 2023 - Virtual, Online
Varighed: 27 nov. 202330 nov. 2023

Konference

Konference2nd Learning on Graphs Conference, LOG 2023
ByVirtual, Online
Periode27/11/202330/11/2023
NavnProceedings of Machine Learning Research
ISSN2640-3498

Fingeraftryk

Dyk ned i forskningsemnerne om 'Spectral Subgraph Localization'. Sammen danner de et unikt fingeraftryk.

Citationsformater