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

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

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-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.

Original language	English
Title of host publication	The Second Learning on Graphs Conference
Number of pages	641
Volume	231
Publication date	2023
Pages	231:7:1-7:11
Publication status	Published - 2023
Event	2nd Learning on Graphs Conference, LOG 2023 - Virtual, Online Duration: 27 Nov 2023 → 30 Nov 2023

Conference

Conference	2nd Learning on Graphs Conference, LOG 2023
City	Virtual, Online
Period	27/11/2023 → 30/11/2023

Series	Proceedings of Machine Learning Research
ISSN	2640-3498

Access to Document

https://proceedings.mlr.press/v231/bainson24a/bainson24a.pdf

Cite this

@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",

}

Bainson, AB, Boyarski, A, Hermanns, J, Petsinis, P, Aavad, N, Larsen, CD, Swayne, T, Mottin, D, Bronstein, AM & Karras, P 2023, Spectral Subgraph Localization. in The Second Learning on Graphs Conference. vol. 231, Proceedings of Machine Learning Research, pp. 231:7:1-7:11, 2nd Learning on Graphs Conference, LOG 2023, Virtual, Online, 27/11/2023. <https://proceedings.mlr.press/v231/bainson24a/bainson24a.pdf>

TY - GEN

T1 - Spectral Subgraph Localization

AU - Bainson, Ama Bembua

AU - Boyarski, Amit

AU - Hermanns, Judith

AU - Petsinis, Petros

AU - Aavad, Niklas

AU - Larsen, Casper Dam

AU - Swayne, Tiarnan

AU - Mottin, Davide

AU - Bronstein, Alex M

AU - Karras, Panagiotis

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85193477872&partnerID=8YFLogxK

M3 - Article in proceedings

VL - 231

T3 - Proceedings of Machine Learning Research

SP - 231:7:1-7:11

BT - The Second Learning on Graphs Conference

T2 - 2nd Learning on Graphs Conference, LOG 2023

Y2 - 27 November 2023 through 30 November 2023

ER -

Spectral Subgraph Localization

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this