Enhanced Subgraph Learning in 2-FWL GNNs via Local Connectivity, Spectral, and Distance Encodings

Despite the theoretical expressiveness of 2-dimensional Folklore Weisfeiler-Lehman (2-FWL) Graph Neural Networks (GNNs), a significant gap persists between their theoretical capacity and their practical performance. To bridge this gap, we identify a critical limitation in current Graph Structural Encodings (GSEs): insufficient sensitivity to subtle structural variations, particularly in local connectivity, spectral features, and distance-based patterns. We show that widely used GSEs-such as Relative Random Walk Probability (RRWP) and monomial-based methods-lack full sensitivity across spectral frequency bands and long-range distances. Moreover, they fail to capture fine-grained local connectivity, which is essential for identifying cut nodes, biconnected components, and other higher-order structures that 2-FWL GNNs theoretically encode. To address these limitations, we propose CSDGSE (Connectivity, Spectral, and Distance Graph Structural Encoding), a novel GSE framework that jointly enhances sensitivity to: (1) exact local connectivity via hierarchical graph decomposition(2) full-frequency spectral features using expressive graph polynomials (e.g., Chebyshev), and (3) full-range distance interactions. A key innovation is our scalable divide-and-conquer algorithm for computing exact local connectivity across all node pairs, enabling efficient integration into modern GSEs. Extensive experiments show that CSDGSE outperforms existing GSEs in capturing complex structural patterns, achieving state-of-the-art results on molecular property prediction benchmarks like ZINC. Our work sets a new standard for GSEs by aligning theoretical expressiveness with practical effectiveness through enhanced structural sensitivity.