Cover Image

Message Passing on the Edge: Towards Scalable and Expressive GNNs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Barceló, Pablo, Jogl, Fabian, Kozachinskiy, Alexander, Lanzinger, Matthias, Neumann, Stefan, Rojas, Cristóbal
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Artificial Intelligence
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Ehrenfeucht-Haussler Rank and Chain of Thought
by: Barceló, Pablo, et al.
Published: (2025)

Lower bounds on transformers with infinite precision
by: Kozachinskiy, Alexander
Published: (2024)

Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations
by: Barceló, Pablo, et al.
Published: (2025)

Message-Passing GNNs Fail to Approximate Sparse Triangular Factorizations
by: Trifonov, Vladislav, et al.
Published: (2025)

MLGIB: Multi-Label Graph Information Bottleneck for Expressive and Robust Message Passing
by: Wu, Chaokai, et al.
Published: (2026)

Beyond Message Passing: A Symbolic Alternative for Expressive and Interpretable Graph Learning
by: Geng, Chuqin, et al.
Published: (2026)

How Hard Is It for Message-Passing GNNs to Simulate One Weisfeiler-Lehman Color-Refinement Step?
by: Cui, Guanyu, et al.
Published: (2024)

Language Generation: Complexity Barriers and Implications for Learning
by: Arenas, Marcelo, et al.
Published: (2025)

On the Expressive Power of GNNs for Boolean Satisfiability
by: Peltonen, Saku, et al.
Published: (2026)

On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters
by: Lanzinger, Matthias, et al.
Published: (2023)

A completely uniform transformer for parity
by: Kozachinskiy, Alexander, et al.
Published: (2025)

Simple online learning with consistent oracle
by: Kozachinskiy, Alexander, et al.
Published: (2023)

Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models
by: Pasten, Hector, et al.
Published: (2025)

Towards Understanding the Expressive Power of GNNs with Global Readout
by: Funk, Maurice, et al.
Published: (2026)

What Expressivity Theory Misses: Message Passing Complexity for GNNs
by: Kemper, Niklas, et al.
Published: (2025)

Graph Unitary Message Passing
by: Qiu, Haiquan, et al.
Published: (2024)

Parity, Sensitivity, and Transformers
by: Kozachinskiy, Alexander, et al.
Published: (2026)

Distributed Conformal Prediction via Message Passing
by: Wen, Haifeng, et al.
Published: (2025)

Neural-Symbolic Message Passing with Dynamic Pruning
by: Zhang, Chongzhi, et al.
Published: (2025)

Link Prediction with Untrained Message Passing Layers
by: Qarkaxhija, Lisi, et al.
Published: (2024)

Connectivity-Guided Sparsification of 2-FWL GNNs: Preserving Full Expressivity with Improved Efficiency
by: Chen, Rongqin, et al.
Published: (2025)

How Expressive are Knowledge Graph Foundation Models?
by: Huang, Xingyue, et al.
Published: (2025)

Strassen Attention, Split VC Dimension and Compositionality in Transformers
by: Kozachinskiy, Alexander, et al.
Published: (2025)

Enhancing Graph Representations with Neighborhood-Contextualized Message-Passing
by: Lim, Brian Godwin, et al.
Published: (2025)

Could Chemical LLMs benefit from Message Passing
by: Xie, Jiaqing, et al.
Published: (2024)

Next Level Message-Passing with Hierarchical Support Graphs
by: Vonessen, Carlos, et al.
Published: (2024)

GraphEdge: Dynamic Graph Partition and Task Scheduling for GNNs Computing in Edge Network
by: Xiao, Wenjing, et al.
Published: (2025)

Dual-channel Heterophilic Message Passing for Graph Fraud Detection
by: Zhang, Wenxin, et al.
Published: (2025)

How Particle System Theory Enhances Hypergraph Message Passing
by: Ma, Yixuan, et al.
Published: (2025)

PANDA: Expanded Width-Aware Message Passing Beyond Rewiring
by: Choi, Jeongwhan, et al.
Published: (2024)

Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
by: Liu, Meng, et al.
Published: (2022)

Optimal bounds for dissatisfaction in perpetual voting
by: Kozachinskiy, Alexander, et al.
Published: (2024)

Transformers from Diffusion: A Unified Framework for Neural Message Passing
by: Wu, Qitian, et al.
Published: (2024)

Improving Subgraph-GNNs via Edge-Level Ego-Network Encodings
by: Alvarez-Gonzalez, Nurudin, et al.
Published: (2023)

The Logical Expressiveness of Temporal GNNs via Two-Dimensional Product Logics
by: Sälzer, Marco, et al.
Published: (2025)

Training-Free Message Passing for Learning on Hypergraphs
by: Tang, Bohan, et al.
Published: (2024)

Unlink to Unlearn: Simplifying Edge Unlearning in GNNs
by: Tan, Jiajun, et al.
Published: (2024)

RelGNN: Composite Message Passing for Relational Deep Learning
by: Chen, Tianlang, et al.
Published: (2025)

GMP-AR: Granularity Message Passing and Adaptive Reconciliation for Temporal Hierarchy Forecasting
by: Zhou, Fan, et al.
Published: (2024)

Enhancing Topological Dependencies in Spatio-Temporal Graphs with Cycle Message Passing Blocks
by: Lee, Minho, et al.
Published: (2024)