Scaling up graph homomorphism for classification via sampling
arXiv:2104.04040
Abstract
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.
17 pages, 1 figure
References in corpus (9)
- Scikit-learn: Machine Learning in Python
- Geometric deep learning: going beyond Euclidean data
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- A Survey on Graph Kernels
- TUDataset: A collection of benchmark datasets for learning with graphs
- Benchmarking Graph Neural Networks
- OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphs
- Peregrine: A Pattern-Aware Graph Mining System
- Graph Homomorphism Convolution