홈 › Papers

Message Passing on the Edge: Towards Scalable and Expressive GNNs

2025-10-15 · Pablo Barceló, Fabian Jogl, Alexander Kozachinskiy, Matthias Lanzinger, Stefan Neumann, Cristóbal Rojas arxiv

Graph neural networks (GNNs) are widely used in graph learning and most architectures propagate information by passing messages between vertices. In this work, we shift our attention to GNNs that perform message passing on edges and introduce EB-1WL, an edge-based color-refinement test, and a corresponding architecture, EB-GNN. Our EB-GNN architecture is inspired by the classic triangle-counting algorithm of Chiba and Nishizeki and passes messages along edges and triangles. Our contributions are as follows: (1) Theoretically, we show that EB-1WL is significantly more expressive than 1WL. We provide a complete logical characterization of EB-1WL in first-order logic, along with distinguishability results via homomorphism counting. To the best of our knowledge, EB-GNN has the strongest theoretical expressivity guarantees among edge-based message-passing GNNs in the literature. (2) Unlike many GNN architectures that are more expressive than 1WL, we prove that EB-1WL and EB-GNN admit near-linear time and memory usage on practical graph learning workloads. (3) We show in experiments that EB-GNN is a highly efficient general-purpose architecture: it substantially outperforms simple MPNNs and remains competitive with task-specialized state-of-the-art GNNs at substantially lower computational cost.

📄 PDF Abstract BibTeX arXiv:2510.13615

Code (0)

등록된 구현이 없습니다.

Tasks

Graph Learning

Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs

2025-08-31 · Arman Gupta, Govind Waghmare, Gaurav Oberoi, Nitish Srivastava arxiv

In heterophilic graphs, where neighboring nodes often belong to different classes, conventional Graph Neural Networks (GNNs) struggle due to their reliance on local homophilous neighborhoods. Prior studies suggest that m…

Node Classification Graph Learning

Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information

2024-06-27 · Tianjun Yao, Yiongxu Wang, Kun Zhang, Shangsong Liang

Graph neural networks (GNNs) have become the \textit{de facto} standard for representational learning in graphs, and have achieved state-of-the-art performance in many graph-related tasks; however, it has been shown that…

Identity-aware Graph Neural Networks

2021-01-25 · Jiaxuan You, Jonathan Gomes-Selman, Rex Ying, Jure Leskovec

Message passing Graph Neural Networks (GNNs) provide a powerful modeling framework for relational data. However, the expressive power of existing GNNs is upper-bounded by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism …

Graph Classification Graph Property Prediction Link Prediction Node Clustering+1

Expressive Power of Temporal Message Passing

2024-08-19 · Przemysław Andrzej Wałęga, Michael Rawson

Graph neural networks (GNNs) have recently been adapted to temporal settings, often employing temporal versions of the message-passing mechanism known from GNNs. We divide temporal message passing mechanisms from literat…

EDEN: A Plug-in Equivariant Distance Encoding to Beyond the 1-WL Test

2022-11-19 · Chang Liu, Yuwen Yang, Yue Ding, Hongtao Lu

The message-passing scheme is the core of graph representation learning. While most existing message-passing graph neural networks (MPNNs) are permutation-invariant in graph-level representation learning and permutation-…

Graph Representation Learning Representation Learning