Improving fine-grained expressivity of graph neural networks
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
| Power graph | |||||
|---|---|---|---|---|---|
| GNN Layer | |||||
| Pair a | Maximal I-GGNN | 50% | 100% | 100% | |
| SchNet [ SSK+18c ] | 50.0 ± 0.0 | 100.0 ± 0.0 | 100.0 ± 0.0 | ||
| DimeNet [ GGG20c ] | 100.0 ± 0.0 | 100.0 ± 0.0 | 100.0 ± 0.0 | ||
| SphereNet [ LWL+21c ] | 100.0 ± 0.0 | 100.0 ± 0.0 | 100.0 ± 0.0 | ||
| SchNet 3.6.1 | 100.0 ± 0.0 | 100.0 ± 0.0 | 100.0 ± 0.0 | ||
| Drugs | Kraken | BDE | |||||||
| Category | Model | IP | EA | L | BE | ||||
| 1D | Random Forest | 0.4987 | 0.4747 | 0.2732 | 0.4760 | 0.4303 | 0.2758 | 0.1521 | 3.0335 |
| LSTM | 0.4788 | 0.4648 | 0.2505 | 0.4879 | 0.5142 | 0.2813 | 0.1924 | 2.8279 | |
| Transformer | 0.6617 | 0.5850 | 0.4073 | 0.9611 | 0.8389 | 0.4929 | 0.2781 | 10.0771 | |
| 2D | GIN | 0.4354 | 0.4169 | 0.2260 | 0.3128 | 0.4003 | 0.1719 | 0.1200 | 2.6368 |
| GIN+VN | 0.4361 | 0.4169 | 0.2267 | 0.3567 | 0.4344 | 0.2422 | 0.1741 | 2.7417 | |
| ( -chains) | Number of layers | |||||
|---|---|---|---|---|---|---|
| GNN Layer | ||||||
| Equiv. | GWL | 50% | 100% | 100% | 100% | 100% |
| E-GNN [ SHW21g ] | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | 100.0 ± 0.0 | |
| GVP-GNN [ JES+20c ] | 50.0 ± 0.0 | 100.0 ± 0.0 | 100.0 ± 0.0 | 100.0 ± 0.0 | 100.0 ± 0.0 | |
| TFN [ TSK+18j ] | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | 80.0 ± 24.5 | 85.0 ± 22.9 | |
| MACE [ BKS+22c ] | 50.0 ± 0.0 | 90.0 ± 20.0 | 90.0 ± 20.0 | 95.0 ± 15.0 | 95.0 ± 15.0 | |
| ( -chains) | Number of layers | ||||||
|---|---|---|---|---|---|---|---|
| GNN Layer | |||||||
| Equiv. | Maximally expressive E-GGNN | 50% | 100% | 100% | 100% | 100% | |
| E-GNN [ SHW21g ] | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | 95 ± 15.0 | ||
| GVP-GNN [ JES+20c ] | 50.0 ± 0.0 | 50.0 ± 0.0 | 60.0 ± 20.0 | 50.0 ± 0.0 | 60.0 ± 20.0 | ||
| TFN [ TSK+18j ] | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | ||
| MACE [ BKS+22c ] | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | 50.0 ± 0.0 | ||
| Model | Hard1 | Hard2 | Hard3 | Harder |
|---|---|---|---|---|
| GramNet | 1.000 | 1.000 | 1.000 | 1.000 |
| GeoEGNN | 0.998 | 0.970 | 0.850 | 0.899 |
| EGNN | 0.500 | 0.500 | 0.500 | 0.500 |
| LinearEGNN | 1.000 | 1.000 | 1.000 | 0.500 |
| MACE | 1.000 | 1.000 | 1.000 | 1.000 |
| TFN | 0.500 | 0.500 | 0.550 | 0.500 |
| Category | Model | IP | EA | B 5 | L | BurB 5 | BurL | BDE | |
|---|---|---|---|---|---|---|---|---|---|
| 1D | Random Forest | 0.4987±0.0037 | 0.4747±0.0022 | 0.2732±0.0031 | 0.4760±0.0041 | 0.4303±0.0090 | 0.2758±0.0180 | 0.1521±0.0149 | 3.03±0.27 |
| 1D | LSTM | 0.4788±0.0024 | 0.4648±0.0002 | 0.2505±0.0050 | 0.4879±0.0280 | 0.5142±0.0411 | 0.2813±0.0041 | 0.1924±0.0028 | 2.82±0.07 |
| 1D | Transformer | 0.6617±0.0023 | 0.5850±0.0031 | 0.4073±0.0006 | 0.9611±0.0813 | 0.8389±0.0431 | 0.4929±0.0369 | 0.2781±0.0207 | 10.08±0.64 |
| 2D | GIN | 0.4354±0.0029 | 0.4169±0.0032 | 0.2260±0.0017 | 0.3128±0.0264 | 0.4003±0.0341 | 0.1719±0.0031 | 0.1200±0.0040 | 2.63±0.22 |
| 2D | GIN-VN | 0.4361±0.0059 | 0.4169±0.0083 | 0.2267±0.0002 | 0.3567±0.0031 | 0.4344±0.0416 | 0.2422±0.0033 | 0.1741±0.0109 | 2.74±0.24 |
| 2D | ChemProp | 0.4595±0.0028 | 0.4417±0.0045 | 0.2441±0.0012 | 0.4850±0.0068 | 0.5452±0.0454 | 0.3002±0.0086 | 0.1948±0.0138 | 2.66±0.14 |
| Method | Time (s) |
|---|---|
| SchNet [ SSK+18c ] | |
| DimeNet [ GGG20c ] | |
| SphereNet [ LWL+21c ] | |
| EGNN [ SHW21g ] | |
| GVP [ JES+20c ] | |
| TFN [ TSK+18j ] |
| Threshold | Drugs | Kraken | BDE |
|---|---|---|---|
| Model | ||
|---|---|---|
| Siamese | 48% | 28% |
| DSS | 97.5% | 92.0% |
| SchurNet (Ours) | 100.0% | 97.0% |
| Dataset | Input size | SchurNet | NProductNet |
|---|---|---|---|
| noisy-sphere-3 | 0.0389 | 0.0460 | |
| 0.1026 | 0.1580 | ||
| noisy-sphere-6 | 0.0217 | 0.0150 | |
| 0.0795 | 0.0490 | ||
| uniform | 0.0974 | 0.0970 | |
| 0.1043 | 0.1089 |
| Model | MNIST | CIFAR10 | ||
|---|---|---|---|---|
| Acc(↓) | Loss (↓) | Acc(↓) | Loss (↓) | |
| SchurNet (Ours) | 1.25e-5 | 0.251346 | 0.0 | 1.7822 |
| Siamese | 1.5e-5 | 0.262913 | 1.0e-4 | 1.7876 |
| Ground set size | |||
|---|---|---|---|
| Input multiset size | |||
| , | Not possible | ||
| Model | Bedding | Feeding | MSWEB | MSNBC |
|---|---|---|---|---|
| DeepSets | 0.51 | 0.50 | 0.88 | 0.67 |
| Set Transformer | 0.77 | 0.79 | 0.90 | 0.94 |
| FlexSubNet | 0.88 | 0.85 | 0.92 | 0.91 |
| Neural SFE | 0.52 | 0.53 | 0.88 | 0.66 |
| MASNet - ReLU | 0.98 | 0.98 | 0.99 | 0.97 |
| MASNet - Hat | 0.94 | 0.93 | 0.97 | 0.95 |
| Model | MAE |
|---|---|
| DeepSets | |
| Set Transformer | |
| MASNet - ReLU | |
| MASNet - Hat |
| Model | bedding | feeding | MSWEB | MSNBC |
|---|---|---|---|---|
| Shallow-ReLU | 0.69 | 0.36 | 0.92 | 0.93 |
| Shallow- MASNet - | 0.83 | 0.76 | 0.94 | 0.95 |
| Shallow- MASNet - Hat | 0.89 | 0.77 | 0.97 | 0.96 |
| Shallow- MASNet -INT | 0.90 | 0.91 | 0.92 | 0.95 |
| (Deep) MASNet - ReLU | 0.95 | 0.93 | 0.97 | 0.97 |
| Deep- MASNet - | 0.92 | 0.93 | 0.98 | 0.96 |
| Model | bedding | feeding | MSWEB | MSNBC |
|---|---|---|---|---|
| DeepSets | 0.91 | 0.90 | 0.93 | 0.97 |
| DeepSets, monotone | 0.90 | 0.91 | 0.94 | 0.93 |
| MASNet - ReLU | 0.95 | 0.93 | 0.97 | 0.97 |
| MASNet - Hat | 0.91 | 0.92 | 0.95 | 0.97 |
| MASNet - Hat (No division) | 0.87 | 0.92 | 0.92 | 0.94 |
| Dataset | peptides-func (AP ) | peptides-struct (MAE ) |
|---|---|---|
| GINE | 0.6621 0.0067 | 0.2473 0.0017 |
| GCN | 0.6860 0.0050 | 0.2460 0.0007 |
| GatedGCN | 0.6765 0.0047 | 0.2477 0.0009 |
| SortMPNN | 0.6914 0.0056 | 0.2494 0.0021 |
| FSW-GNN | 0.6864 0.0048 | 0.2489 0.00155 |
| SOTA | 0.73 | 0.242 |
| Model | MUTAG | Protein |
|---|---|---|
| GIN [ XHLJ18g ] | ||
| GCN | ||
| GraphSAGE | ||
| SortMPNN | ||
| AdaptMPNN | ||
| FSW-GNN |
| Dataset | Cora | Cite. | Pubm. | Cham. | Squi. | Actor | Corn. | Texa. | Wisc. | MUTAG |
|---|---|---|---|---|---|---|---|---|---|---|
| # Nodes | 2708 | 3327 | 19717 | 2277 | 5201 | 7600 | 183 | 183 | 251 | 17.93 |
| # Edges | 5429 | 4732 | 44338 | 36101 | 217073 | 33544 | 295 | 309 | 499 | 19.79 |
| # Features | 1433 | 3703 | 500 | 2325 | 2089 | 931 | 1703 | 1703 | 1703 | 7 |
| # Classes | 7 | 6 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 2 |
| Avg. Degree | 4 | 2 | 4 | 31 | 83 | 8 | 3 | 3 | 4 | 8 |
| Density | 0.0007 | 0.0009 | 0.0001 | 0.0159 | 0.0161 | 0.0012 | 0.0177 | 0.0184 | 0.0041 | 0.0422 |
| Dataset | Peptides-Func | Peptides-Struct |
|---|---|---|
| # Graphs | 15,535 | 15,535 |
| # Nodes (Avg.) | 150.94 | 150.94 |
| # Edges (Avg.) | 2.04 | 2.04 |
| Avg. Degree | 2.04 | 2.04 |
| Density | ||
| # Classes | - | 10 |
| Model | Avg Time per Testing |
|---|---|
| GIN | 0.09 |
| GCN | 0.08 |
| GAT | 0.09 |
| GGNN | 0.08 |
| GraphSAGE | 0.07 |
| FSW-GNN | 0.11 |
GNN Expressivity
Graph neural network expressivity studies which graph structures and functions a model can distinguish or represent, and how its design shapes those limits.
See all 65 papers