Can strong structural encoding reduce the importance of Message Passing?

Floor Eijkelboom, Erik J. Bekkers, Michael M. Bronstein, Francesco Di Giovanni

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.

Table 1: Performance on Peptides-struct (MAE). Note the robustness of RW-Tensor models when message passing is removed (no MP) compared to RW-Concat.

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.

Table 2: Performance on ZINC (MAE). Tensor-based encodings consistently outperform concatenation-based counterparts when message passing is restricted or removed.

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

Abstract

The most prevalent class of neural networks operating on graphs are message passing neural networks (MPNNs), in which the representation of a node is updated iteratively by aggregating information in the 1-hop neighborhood. Since this paradigm for computing node embeddings may prevent the model from learning coarse topological structures, the initial features are often augmented with structural information of the graph, typically in the form of Laplacian eigenvectors or Random Walk transition probabilities. In this work, we explore the contribution of message passing when strong structural encodings are provided. We introduce a novel way of modeling the interaction between feature and structural information based on their tensor product rather than the standard concatenation. The choice of interaction is compared in common scenarios and in settings where the capacity of the message-passing layer is severely reduced and ultimately the message-passing phase is removed altogether. Our results indicate that using tensor-based encodings is always at least on par with the concatenation-based encoding and that it makes the model much more robust when the message passing layers are removed, on some tasks incurring almost no drop in performance. This suggests that the importance of message passing is limited when the model can construct strong structural encodings.
BibTeX
@inproceedings{eijkelboom2023can,
  author = {Floor Eijkelboom and Erik J. Bekkers and Michael M. Bronstein and Francesco Di Giovanni},
  title = {{Can strong structural encoding reduce the importance of Message Passing?}},
  booktitle = {TAG-ML},
  year = {2023},
  url = {https://openreview.net/forum?id=5YqJvBtAo9},
}
Figure