cs.LGNov 15, 2026

Improving fine-grained expressivity of graph neural networks

Authors: Yonatan Sverdlov

Organizations: Technion — Israel Institute of Technology, Haifa

Abstract

This thesis investigates the expressive power of neural networks for structured data, focusing on graph neural networks and symmetry-aware architectures. We present four main contributions. First, we characterize the generic expressive power of geometric message-passing neural networks on sparse graphs and introduce EGenNet, an architecture achieving the corresponding guarantees. Second, we use representation theory to characterize linear layers equivariant to multiple permutations, including wreath-product symmetries. Third, we study permutation-invariant set representations that preserve containment, establish dimensional bounds and impossibility results, and introduce MASNet. Finally, we propose FSW-GNN, a message-passing architecture combining strong expressivity and bi-Lipschitz stability guarantees with strong empirical performance on long-range graph-learning tasks. Together, these results provide a broader understanding of how neural architectures can preserve the geometric, algebraic, order-theoretic, and metric structure of their inputs.

Figures & tables

Explore similar work

CardsList
  1. Invariant-Stratified Propagation for Expressive Graph Neural Networks

    Mar 2, 2026Asela Hevapathige, Ahad N. Zehmakan, Asiri Wijesinghe +1Over-Smoothing in GNNsHigher-Order GNNs

  2. Invariant-Based Weight Sharing for Message Passing

    May 25, 2026Florian SeiffarthGraph Neural NetworksGNN Expressivity

  3. Graph Neural Networks Applications Across Domains: All Insights You Need

    Jun 25, 2026Abderaouf BahiGraph Neural NetworksOver-Squashing