Graph Self-Supervised Learning with Learnable Structural and Positional Encodings

Traditional Graph Self-Supervised Learning (GSSL) struggles to capture complex structural properties well. This limitation stems from two main factors: (1) the inadequacy of conventional Graph Neural Networks (GNNs) in representing sophisticated topological features, and (2) the focus of self-supervised learning solely on final graph representations. To address these issues, we introduce GenHopNet, a GNN framework that integrates a k -hop message-passing scheme, enhancing its ability to capture local structural information without explicit substructure extraction. We theoretically demonstrate that GenHopNet surpasses the expressiveness of the classical Weisfeiler-Lehman (WL) test for graph isomorphism. Furthermore, we propose a structural-and positional-aware GSSL framework that incorporates topological information throughout the learning process. This approach enables the learning of representations that are both sensitive to graph topology and invariant to specific structural and feature augmentations. Comprehensive experiments on graph classification datasets, including those designed to test structural sensitivity, show that our method consistently outperforms the existing approaches and maintains computational efficiency. Our work significantly advances GSSL's capability in distinguishing graphs with similar local structures but different global topologies. 1 Introduction Graph Neural Networks (GNNs) are powerful deep learning networks for graph-structured data, employed by various tasks [36, 68, 88, 83, 65, 98, 79, 37, 57, 32, 2, 43, 18]. While most GNNs focus on semi-supervised learning, Self-Supervised Learning (SSL) learns graph representations without human annotations. Graph Self-Supervised Learning (GSSL) often outperforms supervised methods in both node-level and graph-level downstream tasks [82, 106, 100, 94, 104, 102, 95, 93, 97]. In this paper, we focus on graph classification, a crucial graph-level task with significant applications in areas such as molecular property prediction, social network analysis, and protein function classification [25, 83, 22, 96, 103]. Graph classification presents unique challenges compared to node-level tasks as it must capture global structural information across different graphs, not just local neighborhoods. Graphs can vary significantly in size and structure, demanding more flexible and expressive models. To obtain effective graph-level representations, models must aggregate information from all nodes and edges while preserving discriminative structural features. Despite GSSL's success, they often fail to fully leverage the expressive power of GNNs, by not utilizing both topological and positional information for graph classification. This paper is accepted by The World Wide Web Conference (WWW) 2025.