acceptodds
Under review as a conference paper at ICLR 2027

Structural Encoding via Orthogonal Code Broadcast for Graph Neural Networks

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph neural network, structural encoding, code-division multiple access, message aggregation, learnable propagation

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_jGvWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a novel graph neural network (GNN) message aggregation framework called OCMSE . Its core idea is to draw inspiration from CDMA technology in communication by assigning orthogonal codewords to selected "source nodes" and allowing these signals to propagate hop-by-hop on the graph with learning capabilities, thereby generating a structural imprint for each node that enhances the expressive power of downstream GNNs.

Critical strengths

1.This paper presents an interesting perspective on the design of GNNs. 2.This paper conducts extensive experiments.

Critical weaknesses

1.Theoretical evidence seems to be disconnected from the expressive power of GNN, and discussions are focused on the properties of OCMSE. 2.The experiment lacks a comparison of similar works from an information theory perspective.

Questions for authors

1.Can FDMA or other similar mechanisms be combined with GNN design? The author can have a discussion. 2.Can the author add some theoretical analysis of the expressive power of GNNs?

Reviewer_5DVVOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

In this paper, the authors propose the Orthogonal Code based Multi-Scale Structural Encoding (OCMSE) technique, which can be integrated with many GNN structures, for improving the accuracy performance. Extensive experiments have been provided for verifying the effectiveness of their method.

Critical strengths

S1: The technique of this paper seems to be very generic, which can be combined with other GNN models.

S2: The experimental results with many GNN structures demonstrate the good performance of having this technique.

S3: The technical contribution of this paper seems to be solid.

Critical weaknesses

W1: GNN structures have been extensively studied in the literature. I just wonder whether this encoding technique be applied to all these GNN structures. Are there any conditions that should be satisfied before we can apply this encoding technique into those GNN structures.

W2: I see that the authors have adopted some baseline methods in the experimental evaluation. However, those methods are mainly from 2017 to 2019 (only one paper was published in 2025). Therefore, I wonder why the authors do not test whether the combination of those recent papers with this technique. Is it because it can only be applied for those GNN structures with some conditions that are satified (following W1).

W3: Assume that it really has some conditions, can we still provide some experimental results that demonstrate that those old GNN structures with this encoding technique can still achieve better performance compared with those recent GNN structures.

W4: Figure 1 can be confusing. I see that the bottom arrows (the two figures on the left) point to nothing.

Questions for authors

Q1: What are the limitations of this encoding technique?

Q2: Can this encoding technique be applied to all GNN structures?

Q3: Can the authors provide some additional results with the recent GNN structures (especially for those GNN papers published in 2024 - 2026)?

Reviewer_oNknOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces OCMSE, a plug-and-play framework designed to overcome the indiscriminate mixing of neighbor messages in standard GNNs, which often degrades interpretability and exacerbates over-smoothing. Inspired by CDMA in communications, OCMSE assigns mutually orthogonal Hadamard codewords to k landmark source nodes selected via the k-center algorithm. These sources broadcast probe signals across T hops via a learnable, edge-modulated recurrent mechanism. At each receiving node, correlation detection extracts the individual contribution from each source alongside the superimposed global signal to form a multi-scale structural imprint. The imprints are subsequently refined via a global source-level attention module and concatenated with node features for downstream GNN backbones. The authors provide theoretical analyses on orthogonality preservation, injectivity, and over-smoothing prevention, and demonstrate empirical improvements when augmenting several GNN backbones across node and graph classification benchmarks.

Critical strengths
  1. The paper is the first to apply CDMA-style message aggregation into GNNs, which provides a novel perspective on structural encoding and how message-passing can be improved.

  2. The authors conduct experiments on multiple benchmarks, and the proposed OCMSE consistently improves the performance on various baselines, which provides strong evidence of the superiority of OCMSE.

Critical weaknesses
  1. In Eq. (7) and Eq. (11), the structural imprint vector concatenates source dimensions in a sequential order. However, the greedy k-center algorithm selects an unordered set of nodes. Any renumbering of nodes or tie-breaking variation changes the sis_is' ordering and their allocated Hadamard rows. Because z^u\hat{\mathbf{z}}_u is concatenated directly to node features and fed into an MLP or downstream GNN, the model output is sensitive to source ordering, and is therefore not permutation equivariant.

  2. In Section 5.3 and Table 6, the overhead analysis evaluates only Increased Reasoning Time and memory during inference. It omits the computational time and memory required for the k-center BFS landmark selection and the two-stage pre-training phase, which may represent the primary computational bottlenecks of the framework.

Questions for authors

Please refer to weaknesses # 1-2 for the main questions. Some other questions are listed below:

  1. The proposed OCMSE successfully improves the performance of multiple baselines. However, the experiments lack comparisons with some established structural encoding baselines, such as LapPE [1], RWPE [2] and SignNet/BasisNet [3]. Is it possible to compare your method with some of these baselines in the experiments?

  2. While over-smoothing and over-squashing serve as key motivations, and Proposition 6 theoretically claims that OCMSE prevents representation collapse, there is no direct empirical verification for either issue. Could you provide depth-scaling evaluations to demonstrate resistance to over-smoothing, or long-range benchmark tasks to verify relief from over-squashing?

  3. The results of GAT on Citeseer, and both GCN and GAT on ogbn-arxiv seem to be significantly lower than established results in other literature. Can you explain why these performance gaps exist?

  4. Some minor issues: Phrases such as 'hop by hop' (in the contributions section) and 'Orthogonal Code based' (throughout the paper) should be hyphenated as 'hop-by-hop' and 'Orthogonal Code-based'.

[1] Dwivedi, V. P., & Bresson, X. A generalization of transformer networks to graphs. DLG-AAAI'21.

[2] Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., & Bresson, X. Graph neural networks with learnable structural and positional representations. ICLR'22.

[3] Lim, D., Robinson, J., Zhao, L., Smidt, T., Sra, S., Maron, H., & Jegelka, S. Sign and basis invariant networks for spectral graph representation learning. ICLR'23.

Reviewer_CLSsOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes a method to improve neighbor messaging in GNN, focusing on message aggregation. The authors claim that their method is inspired by CDMA, a channel coding method in the communications field, which I understand very well. The proposed method takes k nodes, assigns each a code, then propagates the code through the graph with a weighted sum over neighbors and correlates the results. Although the proposed mechanism sounds like a basic CDMA function, the authors never justify the similarity in their motivations. Key CDMA characteristics are not discussed. The advantages of the methods are not proven. The baselines are weak. The correctness of the theorems is questionable.

Critical strengths

The primary strength of this paper is its inspiration from CDMA in message aggregation in GNN. However, their claims of preventing over-smoothing and improving interpretability are not established in the theoretical work.

Critical weaknesses

CDMA is used to address some specific issues in communications and offers some specific advantages (with some shortcomings). The authors never discuss such a similarity. There is no analysis or comparison. CDMA helps increase throughput by sharing channels, but there is no shared channel in the proposed method. Therefore, the application of a CDMA-like method is not convincing. There is no experiment to study depth, over-smoothing or interpretability, which are claimed main advantages in the paper.

Questions for authors

How can you prove the over-smoothing, interpretability, and symmetric-graph claims?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.