Homomorphism Expressivity of Spectral Invariant Graph Neural Networks
Jingchu Gai, Yiheng Du, Bohang Zhang, Haggai Maron, Liwei Wang · 2025
Read Homomorphism Expressivity of Spectral Invariant Graph Neural Networks by Jingchu Gai, Yiheng Du, Bohang Zhang, Haggai Maron, Liwei Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00485.txt.
Introduction
Graph spectra — the eigenvalues of a graph's matrices — are popular features for graph neural networks, but how much counting power they actually add was unclear. Jingchu Gai and co-authors measured in 2025 that power through homomorphism counting.
They prove spectral-invariant networks count exactly a class of tree-like graphs they call parallel trees. The result ranks different architectures in a quantitative hierarchy, explains how network depth matters, and clarifies which subgraphs such networks can count. It extends earlier work and settles its open questions. A generalization to higher-order networks answers another open question from the literature.
Catalog record
| CREATOR | Jingchu Gai, Yiheng Du, Bohang Zhang, Haggai Maron, Liwei Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 170 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-00485