Introduction
The Message Passing Neural Network (MPNN) is the cornerstone of modern graph learning. By aggregating neighbor information, MPNNs learn local structures. However, they face fundamental limitations in expressivity—often bounded by the 1-WL graph isomorphism test—and suffer from "over-squashing" when modeling long-range dependencies. While Structural Encodings (SE), such as Laplacian eigenvectors or random walk probabilities, are frequently added to mitigate these issues, they are typically combined with node features via simple concatenation. This paper investigates whether a more sophisticated "entanglement" of features and structure can reduce the reliance on the message-passing paradigm itself.
Methodology: Tensor-Product Encodings
The core innovation presented is the use of the Kronecker (tensor) product ($h_i \otimes p_i$) to combine node features ($h_i$) and structural information ($p_i$). Unlike standard concatenation, which treats these as independent vectors, the tensor product allows every feature dimension to interact with every structural dimension. This creates a high-dimensional initial representation where a node's identity is inextricably linked to its topological context.
To evaluate the necessity of message passing, the authors also developed a method to sparsify MPNN layers. By decomposing linear projections into smaller matrices, they can precisely control the "capacity" of message passing, allowing for a rigorous comparison between models with full, partial ($K=10, K=1$), or zero message-passing layers.
Empirical Evaluation
The approach was tested on benchmarks requiring structural and long-range understanding, including the Long Range Graph Benchmark (LRGB) and the ZINC molecular dataset.
Robustness to Message Passing Removal
The most significant finding is the robustness of tensor-based encodings when message-passing layers are removed. In the Peptides-struct task, which involves predicting 3D structural properties, standard concatenation-based GCNs fail catastrophically when message passing is disabled, with Mean Absolute Error (MAE) jumping from 0.255 to 0.643. In contrast, the tensor-based GCN maintains nearly identical performance, moving only from 0.252 to 0.268.
Similar trends were observed in the ZINC dataset. While the performance gap between full MP and no MP is larger than in Peptides-struct, tensor-based models consistently provide a much stronger baseline in the "no MP" regime than concatenation-based models.
Discussion and Conclusion
These results suggest that much of the "heavy lifting" traditionally attributed to message-passing layers can be offloaded to a sufficiently expressive initial encoding. By "entangling" features and structure at the input stage, models can capture complex topological relationships that would otherwise require many layers of message passing to resolve.
While the high dimensionality of tensor products presents a scaling challenge, this work opens new avenues for efficient, shallow graph models and provides a potential blueprint for better structural integration in Graph Transformers. The findings challenge the community to reconsider the balance between architectural depth and representational strength at the input level.
Summary updated