Structural Encoding via Orthogonal Code Broadcast for Graph Neural Networks

Graph neural networks aggregate neighbor messages, entangling individual contributions into a single representation. This limits interpretability and exacerbates over-smoothing in deep architectures. Inspired by the code-division multiple access mechanism from communications, we propose OCMSE (Orthogonal Code based Multi-Scale Structural Encoding), a plug-and-play framework that enables both structured integration and individual separation of multi-source signals during message propagation. Specifically, selected source nodes are assigned orthogonal codewords and broadcast probe signals that traverse the graph via a learnable, edge-modulated mechanism. At each receiving node, correlation detection recovers each source's individual contribution, producing a structural imprint that jointly encodes decomposed source-wise signals and global structural context. Unlike distance-based anchor methods that rely on single-path information, OCMSE captures richer multi-path information without per-node code assignment. Theoretically, OCMSE provides injective structural fingerprints for generic graphs, with strict source separation preserved under refinement. Extensive experiments show that OCMSE consistently improves various backbone GNN architectures on node and graph classification benchmarks, delivering up to 21% relative improvement on symmetric graphs. Our anonymous code is available at https://anonymous.4open.science/r/OCMSE-BFFB.