Beyond Coordinates: Encoding Graph Structure via Contextual Distribution and Relational Similarity

The Message Passing Neural Networks (MPNNs) and Graph Transformers (GTs) have emerged as two dominant paradigms for graph representation learning. However, the expressive power of standard MPNNs is fundamentally bounded by the 1-dimensional Weisfeiler-Lehman (1-WL) test, while GTs lack the inductive bias for graph structure. To enhance structural representation, existing methods typically resort to subgraph-based aggregation or coordinate-based positional encodings. However, the former suffers from prohibitive computational memory overheads, while the latter is limited by rigid reference frames that fail to distinguish fine-grained local topology. To address these limitations, we introduce a novel structural encoding framework based on contextual distributions. Specifically, we move beyond fixed coordinate systems to capture intrinsic local topology by encoding structural information through a compact distributional statistic, i.e., the entropy of the node context. Furthermore, instead of relying on relative positioning, we introduce a kernelized mechanism to encode relational similarity by quantifying the structural affinity between node contexts. Extensive experiments on both synthetic and real-world datasets demonstrate that the proposed framework achieves superior performance, striking a favorable balance between effectiveness and efficiency.