An Untrained Neural Model for Fast and Accurate Graph Classification

Navarin, N., Pasa, L., Gallicchio, C., Sperduti, A. (2023). An Untrained Neural Model for Fast and Accurate Graph Classification. In: Iliadis, L., Papaleonidas, A., Angelov, P., Jayne, C. (eds) Artificial Neural Networks and Machine Learning – ICANN 2023. ICANN 2023. Lecture Notes in Computer Science, vol 14257. Springer, Cham. doi: 10.1007/978-3-031-44216-2_23

ABSTRACT: Recent works have proven the feasibility of fast and accurate time series classification methods based on randomized convolutional kernels [5, 32]. Concerning graph-structured data, the majority of randomized graph neural networks are based on the Echo State Network paradigm in which single layers or the whole network present some form of recurrence. This paper aims to explore a simple form of a randomized graph neural network inspired by the success of randomized convolutions in the 1-dimensional domain. Our idea is pretty simple: implement a no-frills convolutional graph neural network and leave its weights untrained. Then, we aggregate the node representations with global pooling operators, obtaining an untrained graph-level representation. Since there is no training involved, computing such representation is extremely fast. We then apply a fast linear classifier to the obtained representations. We opted for LS-SVM since it is among the fastest classifiers available. We show that such a simple approach can obtain competitive predictive performance while being extremely efficient both at training and inference time.