Graph Pattern Mining and Learning through User-defined Relations (Extended Version)
This work addresses graph pattern mining for applications like graph neural networks and motif counting, offering incremental improvements in efficiency and scalability.
The authors tackled the problem of graph pattern mining by proposing R-GPM, a parallel framework that generalizes traditional methods through user-defined subgraph relations, achieving up to 3-orders-of-magnitude computational cost reduction and near-linear speedups on 44 cores.
In this work we propose R-GPM, a parallel computing framework for graph pattern mining (GPM) through a user-defined subgraph relation. More specifically, we enable the computation of statistics of patterns through their subgraph classes, generalizing traditional GPM methods. R-GPM provides efficient estimators for these statistics by employing a MCMC sampling algorithm combined with several optimizations. We provide both theoretical guarantees and empirical evaluations of our estimators in application scenarios such as stochastic optimization of deep high-order graph neural network models and pattern (motif) counting. We also propose and evaluate optimizations that enable improvements of our estimators accuracy, while reducing their computational costs in up to 3-orders-of-magnitude. Finally,we show that R-GPM is scalable, providing near-linear speedups on 44 cores in all of our tests.