Experimental Investigation of Neural and Weisfeiler-Lehman-Kernel Graph Representations for Downstream SVM-Based Classification

0546251 - ÚI 2022 RIV DE eng C - Conference Paper (international conference)
Borisov, S. - Dědič, M. - Holeňa, Martin
Experimental Investigation of Neural and Weisfeiler-Lehman-Kernel Graph Representations for Downstream SVM-Based Classification.
Proceedings of the 21st Conference Information Technologies – Applications and Theory (ITAT 2021). Aachen: Technical University & CreateSpace Independent Publishing, 2021 - (Brejová, B.; Ciencialová, L.; Holeňa, M.; Mráz, F.; Pardubská, D.; Plátek, M.; Vinař, T.), s. 130-139. ISSN 1613-0073.
[ITAT 2021: Information Technologies - Applications and Theory /21./. Heľpa (SK), 24.09.2021-28.09.2021]
R&D Projects: GA ČR(CZ) GA18-18080S
Institutional support: RVO:67985807
Keywords : graph representation learning * graph neural networks * message-passing networks * Weisfeiler-Lehman isomorphism test * Weisfeiler-Lehman subtree kernel
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://ics.upjs.sk/~antoni/ceur-ws.org/Vol-0000/paper50.pdf

Graphs are one of the most ubiquitous kinds of data. However, data analysis methods have been developed primarily for numerical data, and to make use of them, graphs need to be represented as elements of some Euclidean space. An increasingly popular way of representing them in this way are graph neural networks´(GNNs). Because data analysis applications typically require identical results for isomorphic graphs, the representations learned by GNNs also need to be invariant with respect to graph isomorphism. That motivated recent research into the possibilities of recognizing nonisomorphic pairs of graphs by GNNs, primarily based on the Weisfeiler-Lehman (WL) isomorphism test. This paper reports the results of a first experimental comparison of four variants of two important GNNs based on the WL test from the point of view of graph representation for downstream classification by means of a support vector machins (SVM). Those methods are compared not only with each other, but also with a recent generalization of the WL subtree kernel. For all GNN variants, two different representations are included in the comparison. The comparison revealed that the four considered representations of the same kind of GNN never significantly differ. On the other hand, there was always a statistically significant difference between representations originating from different kinds of GNNs, as well as between any representation originating from any of the considered GNNs and the representation originating from the generalized WL kernel.
Permanent Link: http://hdl.handle.net/11104/0322814