Cover Image

What Expressivity Theory Misses: Message Passing Complexity for GNNs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kemper, Niklas, Wollschläger, Tom, Günnemann, Stephan
Format:	Preprint
Published:	2025
Subjects:	Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Expressivity and Generalization: Fragment-Biases for Molecular GNNs
by: Wollschläger, Tom, et al.
Published: (2024)

Message Passing on the Edge: Towards Scalable and Expressive GNNs
by: Barceló, Pablo, et al.
Published: (2025)

Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustness
by: Campi, Francesco, et al.
Published: (2023)

Energy-based Epistemic Uncertainty for Graph Neural Networks
by: Fuchsgruber, Dominik, et al.
Published: (2024)

Uncertainty Estimation for Heterophilic Graphs Through the Lens of Information Theory
by: Fuchsgruber, Dominik, et al.
Published: (2025)

Improving the Expressiveness of $K$-hop Message-Passing GNNs by Injecting Contextualized Substructure Information
by: Yao, Tianjun, et al.
Published: (2024)

Expressive Power of Temporal Message Passing
by: Wałęga, Przemysław Andrzej, et al.
Published: (2024)

The Illusion of Certainty: Uncertainty Quantification for LLMs Fails under Ambiguity
by: Tomov, Tim, et al.
Published: (2025)

Localized Randomized Smoothing for Collective Robustness Certification
by: Schuchardt, Jan, et al.
Published: (2022)

Diffusion LLMs are Natural Adversaries for any LLM
by: Lüdke, David, et al.
Published: (2025)

Uncertainty for Active Learning on Graphs
by: Fuchsgruber, Dominik, et al.
Published: (2024)

Polarized Direct Cross-Attention Message Passing in GNNs for Machinery Fault Diagnosis
by: Shi, Zongyu, et al.
Published: (2026)

Lift Your Molecules: Molecular Graph Generation in Latent Euclidean Space
by: Ketata, Mohamed Amine, et al.
Published: (2024)

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

Attacking Large Language Models with Projected Gradient Descent
by: Geisler, Simon, et al.
Published: (2024)

Certifiably Robust Encoding Schemes
by: Saxena, Aman, et al.
Published: (2024)

Discrete Randomized Smoothing Meets Quantum Computing
by: Wollschläger, Tom, et al.
Published: (2024)

Solving Oversmoothing in GNNs via Nonlocal Message Passing: Algebraic Smoothing and Depth Scalability
by: Guan, Weiqi, et al.
Published: (2025)

ITEM: Improving Training and Evaluation of Message-Passing based GNNs for top-k recommendation
by: Karmim, Yannis, et al.
Published: (2024)

Adversarial Alignment for LLMs Requires Simpler, Reproducible, and More Measurable Objectives
by: Schwinn, Leo, 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)

Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs
by: Heeg, Franziska, et al.
Published: (2025)

Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks
by: Scholten, Yan, et al.
Published: (2023)

REINFORCE Adversarial Attacks on Large Language Models: An Adaptive, Distributional, and Semantic Objective
by: Geisler, Simon, et al.
Published: (2025)

On the Expressive Power of GNNs to Solve Linear SDPs
by: Qian, Chendi, et al.
Published: (2026)

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

The Geometry of Refusal in Large Language Models: Concept Cones and Representational Independence
by: Wollschläger, Tom, et al.
Published: (2025)

Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs
by: Gupta, Arman, et al.
Published: (2025)

Chordless Structure: A Pathway to Simple and Expressive GNNs
by: Pan, Hongxu, et al.
Published: (2025)

Rethinking the Expressive Power of GNNs via Graph Biconnectivity
by: Zhang, Bohang, et al.
Published: (2023)

Higher-Order Causal Message Passing for Experimentation with Complex Interference
by: Bayati, Mohsen, et al.
Published: (2024)

Provably Reliable Conformal Prediction Sets in the Presence of Data Poisoning
by: Scholten, Yan, et al.
Published: (2024)

Heterophily-informed Message Passing
by: Wang, Haishan, et al.
Published: (2025)

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

Graph Coarsening with Message-Passing Guarantees
by: Joly, Antonin, et al.
Published: (2024)

Towards Dynamic Message Passing on Graphs
by: Sun, Junshu, et al.
Published: (2024)

Adversarial Attacks on Graph Neural Networks via Meta Learning
by: Zügner, Daniel, et al.
Published: (2019)

Beyond Canonicalization: How Tensorial Messages Improve Equivariant Message Passing
by: Lippmann, Peter, et al.
Published: (2024)