Message Passing on the Edge: Going Beyond Triangles

Abstract

Edge-based graph neural networks (EB-GNNs), introduced by Barceló et al. in 2025, propose a novel message-passing approach in which edges and triangles are used for message propagation as opposed to nodes. We extend this efficient and scalable architecture by incorporating 4-cycles into its message-passing mechanism and generalize the framework to support different triangle–4-cycle combinations. We evaluate two alternative approaches for propagating 4-cycle information and evaluate four resulting EB-GNN architectures across synthetic and real-world datasets. Our best-performing model, which leverages both motifs, surpasses its triangle-only predecessor by achieving higher realized expressive power on two expressivity benchmarks and improved performance on multiple real-world tasks. We further analyze the increased computational and memory costs of our models on 4-cycle–rich graphs and discuss mitigation strategies that preserve their scalability. Finally, we highlight the importance of identifying task-relevant motifs and understanding their structural contributions to graph learning.