https://doi.org/10.1140/epjs/s11734-025-02011-1
Regular Article
A topological graph kernel based on Q-analysis of clique complexes
1
Baltic Center of Neurotechnology and Artificial Intelligence, Immanuel Kant Baltic Federal University, Alexandra Nevskogo 14, 236041, Kaliningrad, Russia
2
Research Institute of Applied Artificial Intelligence and Digital Solutions, Plekhanov Russian University of Economics, 36 Stremyannyy Ln., 115093, Moscow, Russia
a
This email address is being protected from spambots. You need JavaScript enabled to view it.
Received:
6
August
2025
Accepted:
1
October
2025
Published online:
18
October
2025
Abstract
Graph classification methods struggle to capture higher-order network structures beyond pairwise links, as many approaches are bounded by the 1-dimensional Weisfeiler-Lehman test and cannot distinguish graphs with similar local neighborhoods but different global topologies. We propose the Q-Analysis Kernel (QAK), which follows a systematic pipeline: input graphs are transformed into maximal clique simplicial complexes using the Bron–Kerbosch algorithm, then Q-analysis extracts topological feature vectors including the First Structure Vector (FSV), Third Structure Vector (TSV), and Topological Entropy. These vectors quantify the multi-scale connectivity of higher-order structures and are used with a cosine kernel for SVM classification. Experimental evaluation on TUDataset benchmarks demonstrates that QAK achieves classification performance comparable to established graph kernels, with competitive accuracies on social network datasets (73.7% on IMDB-BINARY, 75.4% on REDDIT-BINARY) compared to Weisfeiler–Lehman and Shortest Path kernels. The method provides a novel, interpretable graph representation rooted in algebraic topology, where each feature component corresponds to quantifiable topological properties. This enables feature importance analysis to reveal which structural scales (q-levels) are most discriminative for classification decisions.
Copyright comment Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
© The Author(s), under exclusive licence to EDP Sciences, Springer-Verlag GmbH Germany, part of Springer Nature 2025
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
