Scaling up graph homomorphism for classification via sampling

Autor:	Beaujean, Paul, Sikora, Florian, Yger, Florian
Rok vydání:	2021
Předmět:	Computer Science - Machine Learning Computer Science - Data Structures and Algorithms I.5.1 I.5.2
Druh dokumentu:	Working Paper
Popis:	Feature generation is an open topic of investigation in graph machine learning. In this paper, we study the use of graph homomorphism density features as a scalable alternative to homomorphism numbers which retain similar theoretical properties and ability to take into account inductive bias. For this, we propose a high-performance implementation of a simple sampling algorithm which computes additive approximations of homomorphism densities. In the context of graph machine learning, we demonstrate in experiments that simple linear models trained on sample homomorphism densities can achieve performance comparable to graph neural networks on standard graph classification datasets. Finally, we show in experiments on synthetic data that this algorithm scales to very large graphs when implemented with Bloom filters. Comment: 17 pages, 1 figure
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2104.04040 Zobrazit plný text záznamu View this record from Arxiv