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

CREATORJingchu Gai, Yiheng Du, Bohang Zhang, Haggai Maron, Liwei Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE170 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00485

Browse the full library · About the Tower of Babel