betaFeedback

WorksComputer Science

Improving fine-grained expressivity of graph neural networks

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.

Research Thesis

in partial fulfillment of the requirements for the degree of Doctor of Philosophy

Submitted to the Senate of the Technion — Israel Institute of Technology

Tishrei 5787  Haifa  September 2026

The Research Thesis Was Done in the Interdisciplinary Program in Applied Mathematics Under the Supervision of Prof. Nadav Dym.

Parts of the research presented in this thesis have appeared in the publications listed below. For each publication, its status and the author’s contribution are stated.

  1. Yonatan Sverdlov and Nadav Dym. On the expressive power of sparse geometric MPNNs. In International Conference on Learning Representations (ICLR), 2025. Status: Published at ICLR 2025. Yonatan Sverdlov’s contribution: Yonatan was involved in the work throughout the project, from its initial stages to the final version. He contributed to the development and proofs of the theoretical results, developed and implemented the code, and contributed substantially to the scientific writing of the paper.

  1. Yonatan Sverdlov, Ido Springer, and Nadav Dym. Revisiting multi-permutation equivariance through the lens of irreducible representations. In International Conference on Learning Representations (ICLR), 2025. Status: Published at ICLR 2025. Yonatan Sverdlov and Ido Springer contributed equally to this work. Yonatan contributed to the development and proofs of the theoretical results, developed and implemented the code, and contributed substantially to the scientific writing of the paper.

  1. Soutrik Sarangi, Yonatan Sverdlov, Nadav Dym, and Abir De. Monotone and separable set functions: characterizations and neural models. In Advances in Neural Information Processing Systems (NeurIPS), 2025. Status: Published at NeurIPS 2025. Soutrik Sarangi and Yonatan Sverdlov contributed equally to this work. Yonatan was substantially involved in both the theoretical and computational aspects of the work. He contributed to the development and proofs of the theoretical results, to the development and implementation of the code, and to the scientific writing of the paper.

  1. Yonatan Sverdlov, Yair Davidson, Nadav Dym, and Tal Amir. FSW-GNN: a bi-Lipschitz WL-equivalent graph neural network. In Learning on Graphs Conference (LoG), 2025. Status: Published at LoG 2025. Yonatan was substantially involved in both the theoretical and computational aspects of the work. He contributed to the development and proofs of the theoretical results, to the development and implementation of the code, and to the scientific writing of the paper.

The author of this thesis states that the research, including the collection, processing and presentation of data, addressing and comparing to previous research, etc., was done entirely in an honest way, as expected from scientific research that is conducted according to the ethical standards of the academic world. Also, reporting the research and its results in this thesis was done in an honest and complete manner, according to the same standards.

The generous financial help of the Technion and the Israeli Science Foundation grant no. 272/23 is gratefully acknowledged.

Notation and Abbreviations

G=(V,E,X)G = (V, E, X)A vertex-featured graph, with vertex set VV, edge set EE, and node-feature matrix XX. In the geometric-graph chapter, the equivalent notation G=(A,X)G = (A, X) is also used
VVThe vertex set of a graph. In the set-function chapter, VV instead denotes the ground set from which multiset elements are drawn
EEThe edge set of a graph
n=∣V∣n = \lvert V\rvertNumber of vertices in a graph
NNAn upper bound on the number of vertices in a graph, when a bounded-size graph space is considered
AAAdjacency matrix of a graph
xv∈Rdx_v \in\mathbb{R}^{d}Feature vector associated with node vv; in geometric graphs this may be the position of the node
XXMatrix collecting node features or geometric node positions
Ω⊆Rd\Omega\subseteq\mathbb{R}^{d}Domain from which node features are drawn
N(v)\mathcal{N}(v)Set of neighbors of node vv
hv(t)h_v^{(t)}Hidden representation of node vv after tt message-passing iterations
[n]={1,…,n}[n] = \{1, \ldots, n\}The set of the first nn positive integers
{{x1,…,xn}}\{\{x_1, \ldots, x_n\}\}A multiset: an unordered collection in which repeated elements are allowed
P<∞(V)\mathcal{P}_{<\infty}(V)The collection of all finite multisets whose elements belong to the ground set VV
S,TS, TSets or multisets under comparison
cS(v)c_S(v)Multiplicity of the element vv in the multiset SS
S⊆TS \subseteq TSet or multiset containment; for multisets, cS(v)≤cT(v)c_S(v) \leq c_T(v) for every ground-set element vv
u≤vu \leq vCoordinatewise partial order on vectors: ui≤viu_i \leq v_i for every coordinate ii
Rd\mathbb{R}^{d}dd-dimensional Euclidean space
2-IGNsecond-order invariant graph network (second-order invariant graph network)

Table 1.

G\mathcal{G}

A symmetry group acting on a feature space in the equivariance chapters. In the FSW-GNN paper, G\mathcal{G} is locally reused for a graph space

g⋅xg \cdot x

Action of a group element g∈Gg \in\mathcal{G} on an element xx of the representation space

U,V,W\mathcal{U}, \mathcal{V}, \mathcal{W}

Finite-dimensional vector spaces carrying group representations

VG\mathcal{V}^{\mathcal{G}}

Fixed-point subspace of a representation: vectors v∈Vv \in\mathcal{V} satisfying g⋅v=vg \cdot v = v for all g∈Gg \in\mathcal{G}

SnS_n

Symmetric group of permutations of nn elements

G≀Sk\mathcal{G} \wr S_k

Wreath-product symmetry for a set of kk unaligned objects, each carrying a G\mathcal{G}-symmetry

PP

Permutation matrix representing a relabeling of elements or graph vertices

O(d)O(d)

Group of orthogonal transformations of Rd\mathbb{R}^{d}, including rotations and reflections

x↦Qx+tx \mapsto Qx + t

Rigid transformation with Q∈O(d)Q \in O(d) and translation t∈Rdt \in\mathbb{R}^{d}

G≅HG \cong H

Geometric graphs GG and HH differ only by vertex relabeling and a rigid transformation

F(G)F(G)

Invariant finite-dimensional representation of a graph GG

ρ(G,H)\rho(G,H)

Metric or pseudometric measuring the distance between two input graphs

c,Cc, C

Bi-Lipschitz constants satisfying 0<c≤C<∞0 < c \le C < \infty and cρ(G,H)≤∥F(G)−F(H)∥≤Cρ(G,H)c\rho(G,H) \le\lVert F(G) - F(H) \rVert\le C\rho(G,H)

G≤N(Ω)\mathcal{G}_{\le N}(\Omega)

Space of vertex-featured graphs with at most NN vertices and node features in Ω\Omega; used in the FSW-GNN chapter

G≡WLHG \equiv_{\mathrm{WL}} H

Graphs GG and HH are not distinguished by the corresponding Weisfeiler–Leman procedure

DS

doubly stochastic graph metric (doubly stochastic graph metric)

DWS

Deep Weight Space (Deep Weight Space)

E-GGNN

equivariant geometric graph neural network (equivariant geometric graph neural network)

EGenNet

equivariant geometric message-passing architecture introduced for generic separation (equivariant geometric message-passing architecture introduced for generic separation)

FSW

Fourier Sliced-Wasserstein (Fourier Sliced-Wasserstein)

FSW-GNN

graph neural network using Fourier Sliced-Wasserstein aggregation (graph neural network using Fourier Sliced-Wasserstein aggregation)

GNN

graph neural network (graph neural network)

I-GGNNinvariant geometric graph neural network (invariant geometric graph neural network)
MASmonotone and separable (monotone and separable)
MASNetneural architecture for weakly MAS set representations (neural architecture for weakly MAS set representations)
MLPmultilayer perceptron (multilayer perceptron)
MPNNmessage passing neural network (message passing neural network)
TMDTree Mover’s Distance (Tree Mover’s Distance)
WLWeisfeiler–Leman; unless otherwise stated, the graph chapter primarily uses 1-WL (Weisfeiler–Leman; unless otherwise stated, the graph chapter primarily uses 1-WL)

Preamble

Background: Symmetries, Sets, and Graphs

In this section, we introduce the main notions used throughout the thesis for learning on structured data. We first formalize symmetry through group actions and define invariant and equivariant functions. We then review permutation-invariant set representations, message-passing neural networks, and their connection to the Weisfeiler–Leman test. Finally, we discuss stronger notions of expressivity based on separation and quantitative preservation of information.

Learning with Symmetries

Let G\mathcal{G} be a group acting on a set X\mathcal{X}. A group action is a map

G×X→X,(g,x)↦g⋅x,\mathcal{G} \times\mathcal{X} \to\mathcal{X}, \qquad(g,x) \mapsto g \cdot x,

satisfying

e⋅x=x,g1⋅(g2⋅x)=(g1g2)⋅x,e \cdot x = x, \qquad g_1 \cdot(g_2 \cdot x) = (g_1g_2) \cdot x,

for every x∈Xx \in\mathcal{X} and g1,g2∈Gg_1, g_2 \in\mathcal{G}.

The orbit of xx is

O(x)={g⋅x:g∈G}.\mathcal{O}(x) = \{g \cdot x : g \in\mathcal{G}\}.

In many learning problems, elements in the same orbit correspond to different representations of the same underlying object.

Suppose that G\mathcal{G} acts on both an input space X\mathcal{X} and an output space Y\mathcal{Y}. A function f:X→Yf : \mathcal{X} \to\mathcal{Y} is called G\mathcal{G}-equivariant if

f(g⋅x)=g⋅f(x)f(g \cdot x) = g \cdot f(x)

for every g∈Gg \in\mathcal{G} and x∈Xx \in\mathcal{X}.

It is called G\mathcal{G}-invariant if

f(g⋅x)=f(x).f(g \cdot x) = f(x).

for every g∈Gg \in\mathcal{G} and x∈Xx \in\mathcal{X}. Thus, an invariant function gives the same output for all equivalent representations of an object, whereas an equivariant function transforms its output consistently with the input. Building these constraints directly into an architecture is a standard way to encode known structure and reduce the need to learn symmetry from data [CW16; RSP17].

A typical example is graph learning. Relabeling the nodes of a graph should not affect a graph-level prediction, such as graph classification, and hence such a prediction should be invariant. On the other hand, node-level predictions should be permuted together with the nodes, and are therefore equivariant.

Symmetry, however, specifies only which inputs must be treated as equivalent. It does not by itself determine whether an architecture can separate inputs that are not related by the symmetry. This distinction between symmetry and expressive power will be central throughout the thesis.

Sets, Multisets, and Permutation-Invariant Embeddings

Consider a collection of vectors

X=(x1,…,xn),xi∈Ω⊆Rd.X = (x_1, \ldots, x_n), \qquad x_i \in\Omega\subseteq\mathbb{R}^d.

The symmetric group SnS_n acts by permuting the elements:

π⋅X=(xπ−1(1),…,xπ−1(n)).\pi\cdot X = (x_{\pi^{-1}(1)}, \ldots, x_{\pi^{-1}(n)}).

If the ordering carries no information, a function of XX should be invariant to this action.

We use

S={{x1,…,xn}}S = \{\{x_1, \ldots, x_n\}\}

to denote a multiset: an unordered collection in which repetitions are allowed. Multisets arise naturally throughout this thesis, particularly when aggregating the features of neighboring nodes in a graph. Let Ω\Omega be a ground set, and denote by M(Ω)\mathcal{M}(\Omega) the collection of all finite multisets with elements in Ω\Omega.

A multiset embedding is a map

Φ:M(Ω)→Rm.\Phi: \mathcal{M}(\Omega) \to\mathbb{R}^m.

Equivalently, multiset functions correspond to permutation-invariant functions on multisets.

A basic and widely used construction is the DeepSets from [ZKR+17]

Φ(S)=ρ(∑x∈Sϕ(x))\Phi(S) = \rho\left(\sum_{x \in S} \phi(x)\right)

where ϕ\phi and ρ\rho are learned functions. More generally, one can use any permutation-invariant aggregation operator,

Φ(S)=ρ(AGG⁡{{ϕ(x):x∈S}}).\Phi(S) = \rho\left(\operatorname{AGG}\{\{\phi(x) : x \in S\}\}\right).

Graphs and Message Passing Neural Networks

A vertex-featured graph is represented as

G=(V,E,X),G = (V, E, X),

where

V={v1,…,vn}V = \{v_1, \ldots, v_n\}

is the vertex set,

E⊆{{vi,vj}:i,j∈[n]}E \subseteq\{\{v_i, v_j\} : i, j \in[n]\}

is the edge set, and

X=(x1,…,xn),xi∈Rd,X = (x_1, \ldots, x_n), \qquad x_i \in\mathbb{R}^d,

contains the node features.

We denote the neighborhood of a node vv by

N(v)={u∈V:{u,v}∈E}.\mathcal{N}(v) = \{u \in V : \{u, v\} \in E\}.

Equivalently, a graph may be represented by an adjacency matrix A∈{0,1}n×nA \in\{0,1\}^{n \times n} and a node-feature matrix XX. Given a permutation matrix PP, a relabeling of the vertices transforms the graph representation according to

(A,X)↦(PAPT,PX).(A, X) \mapsto(PAP^{\mathsf{T}}, PX).

Two graphs are isomorphic when their representations are related by such a relabeling. A graph-level function should therefore satisfy

F(PAPT,PX)=F(A,X),F(PAP^{\mathsf{T}}, PX) = F(A, X),

whereas a node-level function should satisfy

F(PAPT,PX)=PF(A,X).F(PAP^{\mathsf{T}}, PX) = PF(A, X).

Message passing. Message Passing Neural Networks (MPNNs) construct node representations by iteratively aggregating information from neighboring nodes [GSR+17].

Starting from

hv(0)=xv,h_v^{(0)} = x_v,

a general message-passing layer has the form

mv(t)=AGG⁡t({{Mt(hv(t−1),hu(t−1)):u∈N(v)}}),m_v^{(t)} = \operatorname{AGG}_t\left(\left\{ \left\{ M_t\left(h_v^{(t-1)}, h_u^{(t-1)}\right) : u \in\mathcal{N}(v) \right\} \right\}\right),

followed by

hv(t)=Ut(hv(t−1),mv(t)).h_v^{(t)} = U_t\left(h_v^{(t-1)}, m_v^{(t)}\right).

The aggregation operator is permutation invariant, ensuring that the overall network is equivariant to node relabeling.

For graph-level tasks, the final node representations are combined using an invariant readout,

hG=READOUT⁡({{hv(T):v∈V}}).h_G = \operatorname{READOUT}\left(\left\{ \left\{ h_v^{(T)} : v \in V \right\} \right\}\right).

After TT iterations, the representation of a node can depend only on its TT-hop neighborhood.

Examples of MPNN architectures. Many popular graph neural networks are special cases of the message-passing framework.

  • Graph Convolutional Network (GCN). A GCN layer performs a normalized average over neighboring features [KW17]:

hv(t)=σ(Wt∑u∈N(v)∪{v}1d~vd~uhu(t−1)),h_v^{(t)} = \sigma\left(W_t \sum_{u \in\mathcal{N}(v)\cup\{v\}} \frac{1}{\sqrt{\widetilde{d}_v\widetilde{d}_u}}h_u^{(t-1)}\right),

where d~v\widetilde{d}_v is the degree after adding self-loops.

  • GraphSAGE. GraphSAGE aggregates neighboring features and combines them with the current node representation [HYL17]:

hv(t)=σ(Wt[hv(t−1)∥AGG⁡({{hu(t−1):u∈N(v)}})]).h_v^{(t)} = \sigma\left(W_t\left[h_v^{(t-1)} \mathbin\Vert\operatorname{AGG}\left(\left\{ \left\{h_u^{(t-1)} : u \in\mathcal{N}(v)\right\}\right\}\right)\right]\right).
  • Graph Attention Network (GAT). GAT assigns learned attention weights to the neighbors [VCC+18]:

References

  1. [1]Tal Amir and Nadav Dym. Fourier sliced-wasserstein embedding for multisets and measures. In ICLR, 2025.
  2. [2]Tal Amir, Steven Gortler, Ilai Avni, Ravina Ravina, and Nadav Dym. Neural injective functions for multisets, measures and graphs via a finite witness theorem. In NeurIPS, 2023.arxiv.org/abs/2306.06529
  3. [3]Hamzeh Agahi. Choquet functional and it’s applications in information theory. Information Sciences, 2018.DOI
  4. [4]Lynton Ardizzone, Jakob Kruse, Carsten Rother, and Ullrich Köthe. Analyzing inverse problems with invertible neural networks. In ICLR, 2019.arxiv.org/abs/1808.04730
  5. [5]Maria Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. Learning valuation functions. In COLT, 2012.
  6. [6]Radu Balan, Naveed Haghani, and Maneesh Singh. Permutation invariant representations with applications to graph deep learning. arXiv preprint arXiv:2203.07546, 2022.arxiv.org/abs/2203.07546
  7. [7]Avrim Blum and Ronald Rivest. Training a 3-node neural network is np-complete. NeurIPS, 1988.
  8. [8]Nader H. Bshouty. Exact learning boolean functions via the monotone theory. Information and Computation, 1995.
  9. [9]Andreïs Bruno, Jeffrey Ryan Willette, Juho Lee, and Sung Ju Hwang. Mini-batch consistent slot set encoder for scalable set encoding. In NeurIPS, 2021.arxiv.org/abs/2103.01615
  10. [11]Gustave Choquet. Theory of capacities. Annales de l’Institut Fourier, 1954.DOI
  11. [12]Abir De and Soumen Chakrabarti. Neural estimation of submodular functions with applications to differentiable subset selection. NeurIPS, 2022.arxiv.org/abs/2210.11033
  12. [13]Yair Davidson and Nadav Dym. On the hölder stability of multiset and graph neural networks. In ICLR, 2025.arxiv.org/abs/2406.06984
  13. [14]Ben Dushnik and Edwin W Miller. Partially ordered sets. American journal of mathematics, 1941.DOI
  14. [15]Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. In STOC, 2005.
  15. [16]Joshua Engels, Benjamin Coleman, Vihan Lakshman, and Anshumali Shrivastava. DESSERT: an efficient algorithm for vector set search with vector set queries. In NeurIPS, 2023.
  16. [17]Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio mathematica, 1935.
  17. [18]Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM Journal on Computing, 2009.
  18. [19]Abraham Gale and Amélie Marian. Explaining monotonic ranking functions. Proc. VLDB Endow., 2020.DOI
  19. [20]Michel Grabisch. Set Functions, Games and Capacities in Decision Making. Springer, 2016.
  20. [22]Nikolaos Karalias, Joshua David Robinson, Andreas Loukas, and Stefanie Jegelka. Neural set function extensions: learning with discrete functions in high dimensions. In NeurIPS, 2022.
  21. [23]Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: a framework for attention-based permutation-invariant neural networks. In ICML, 2019.
  22. [24]Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. In Proceedings of the 3rd ACM conference on Electronic Commerce, 2001.
  23. [25]Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: a view from the width. In NeurIPS, 2017.
  24. [26]Ming Li, Chenyi Zhang, and Qin Li. Monotonic learning in the pac framework: a new perspective. arXiv preprint arXiv:2501.05493, 2025.
  25. [28]Ryan O’Donnell and Rocco A. Servedio. Learning monotone functions from random examples in polynomial time.
  26. [29]Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: deep learning on point sets for 3d classification and segmentation. In CVPR, 2017.
  27. [30]Indradyumna Roy, Rishi Agarwal, Soumen Chakrabarti, Anirban Dasgupta, and Abir De. Locality sensitive hashing in fourier frequency domain for soft set containment search. In NeurIPS, 2023.
  28. [31]Yonatan Sverd­lov, Yair Davidson, Nadav Dym, and Tal Amir. FSW-GNN: a bi-lipschitz WL-equivalent graph neural network. In LoG, 2025.
  29. [32]Joseph Sill. Monotonic networks. In NeurIPS, 1997.
  30. [33]Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A Osborne. On the limitations of representing functions on sets. In ICML, 2019.arxiv.org/abs/1901.09006
  31. [34]Antoine Wehenkel and Gilles Louppe. Unconstrained monotonic neural networks. NeurIPS, 2019.arxiv.org/abs/1908.05164
  32. [35]Jeffrey Willette, Seanie Lee, Bruno Andreis, Kenji Kawaguchi, Juho Lee, and Sung Ju Hwang. Scalable set encoding with universal mini-batch consistency and unbiased full set gradient approximation. In ICML, 2023.arxiv.org/abs/2208.12401
  33. [37]Peihao Wang, Shenghao Yang, Shu Li, Zhangyang Wang, and Pan Li. Polynomial width is sufficient for set representation with high-dimensional features. In ICLR, 2024.arxiv.org/abs/2307.04001
  34. [38]Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.arxiv.org/abs/1810.00826
  35. [39]Seungil You, David Ding, Kevin Canini, Jan Pfeifer, and Maya R. Gupta. Deep lattice networks and partial monotonic functions. In NeurIPS, 2017.arxiv.org/abs/1709.06680

Paper details

vlnc:W_wfmfrdg5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents