Many real-world graphs are temporal, for example, in a social network, persons only interact at specific points in time. This temporal information directs dissemination processes on the graph, such as the spread of rumors, fake news, or diseases. However, the current state-of-the-art methods for supervised graph classification are mainly designed for static graphs and may not capture temporal information. Hence, they are not powerful enough to distinguish between graphs modeling different dissemination processes. We introduce a framework to lift standard graph kernels and graph-based neural networks to the temporal domain to address this. We explore three different approaches and investigate the trade-offs between loss of temporal information and efficiency. Moreover, to handle large-scale graphs, we propose stochastic variants of our kernels with provable approximation guarantees. We evaluate our methods, both kernel and neural architectures, on various real-world social networks to validate our theoretical findings. Our methods beat static approaches by a large margin in terms of accuracy while still being scalable to large graphs and data sets. Moreover, we show that our framework reaches high classification accuracy in scenarios where most of the dissemination process information is incomplete.
Keywords: classification; graph neural networks; kernels; temporal graphs.