Thumbnail - No thumbnail

Graph Homomorphism Features: Why Not Sample?

Beaujean, Paul; Sikora, Florian; Yger, Florian (2022), Graph Homomorphism Features: Why Not Sample?, Machine Learning and Principles and Practice of Knowledge Discovery in Databases, Springer International Publishing : Berlin Heidelberg, p. 216–222. 10.1007/978-3-030-93736-2_17

Type
Communication / Conférence
External document link
https://hal.archives-ouvertes.fr/hal-03583713
Date
2022
Conference title
International Workshops of ECML PKDD 2021
Conference date
2021-09
Conference city
Bilbao
Conference country
Spain
Book title
Machine Learning and Principles and Practice of Knowledge Discovery in Databases
Publisher
Springer International Publishing
Published in
Berlin Heidelberg
ISBN
978-3-030-93735-5
Number of pages
882
Pages
216–222
Publication identifier
Metadata
Show full item record
Author(s)
Beaujean, Paul cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lehrstuhl Bioinformatik Jena
Yger, Florian cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
Recent research in the domain of computed graph embeddings has shown that graph homomorphism numbers constitute expressive features that are well-suited for machine learning tasks such as graph classification. In this work-in-progress paper, we attempt to make this methodology scalable by obtaining additive approximations to graph homomorphism densities via a simple sampling algorithm. We show in experiments that these approximate homomorphism densities perform as well as homomorphism numbers on standard graph classification datasets. Moreover, we show that, unlike algorithms that compute homomorphism numbers, our sampling algorithm is highly scalable to larger graphs.
Subjects / Keywords
Graph embedding; Graph homomorphism; Graph classification