Graph classification has long been a focus of net-work mining, with graph kernel methods and representation learning at the forefront. Despite their success, many of these studies require heavy computation, making them impractical for large-scale datasets. In this paper, we design a novel structural feature extraction technique that leverages node subsets and random walk probabilities, presenting a scalable, unsupervised, and easily interpretable alternative. Initially, we partition each graph based on the structural roles of nodes. This process creates soft alignments of node subsets across graphs of varying sizes. Then, we measure the connection strengths within and between these subsets, which form the fingerprints for graph classification. Additionally, this technique can seamlessly incorporate node features. Through empirical assessment encompassing a broad range of graph datasets, we demonstrate that our method achieves high levels of computational efficiency while maintaining robust classification accuracy. Code and data are available at https://github.com/KXDY233/RWF.

Top