Invertible Graph Aggregation Can Increase ReLU Readout Width
Abstract
An invertible graph aggregation preserves the complete feature table, but can increase the size of a classifier that reads one node at a time. For every even N≥4, we construct a labeled tree with 2N vertices and maximum degree three. A shared one-hidden-layer rectified linear unit (ReLU) classifier needs one hidden unit on the raw scalar features and exactly N units after one lazy neighborhood mean. All aggregate values are distinct, and the mixing matrix has condition number at most 8. We determine the complete error curve for heads with a free affine term. The width separation persists under scalar perturbations. Under a specified bounded uniform-noise model with one nuisance coordinate, every one-unit aggregate head has expected error at least 1/12, while a fixed N-unit head has zero error. Controlled fits compare trained heads with these explicit feasible scores. On Roman-empire and Tolokers, aggregation improves fitted prediction, and retaining raw features helps at the largest tested parameter budget. Training-only diagnostics include conditional output-layer optimality bounds for eight fixed runs.
Related
- Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width
- Monadically Dependent Graph Classes Have Almost Bounded Merge-Width
- Graph Representation Learning via Adaptive Expectile Aggregation
- Weighted boundedness of maximal operator associated with invertible linear transformations on variable Lebesgue spaces
- Invertible non-cyclic functions in the little Bloch space
BibTeX
@misc{usami2026invertible,
title = {{Invertible Graph Aggregation Can Increase ReLU Readout Width}},
author = {Hiroyasu Usami and Masanori Tsukamoto and Kohei Hashiguchi},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02274},
eprint = {2611.02274},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02274},
}
RIS
TY - UNPB
TI - Invertible Graph Aggregation Can Increase ReLU Readout Width
AU - Hiroyasu Usami
AU - Masanori Tsukamoto
AU - Kohei Hashiguchi
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.02274
UR - https://arxiv.org/abs/2611.02274
AB - An invertible graph aggregation preserves the complete feature table, but can increase the size of a classifier that reads one node at a time. For every even N≥4, we construct a labeled tree with 2N vertices and maximum degree three. A shared one-hidden-layer rectified linear unit (ReLU) classifier needs one hidden unit on the raw scalar features and exactly N units after one lazy neighborhood mean. All aggregate values are distinct, and the mixing matrix has condition number at most 8. We determine the complete error curve for heads with a free affine term. The width separation persists under scalar perturbations. Under a specified bounded uniform-noise model with one nuisance coordinate, every one-unit aggregate head has expected error at least 1/12, while a fixed N-unit head has zero error. Controlled fits compare trained heads with these explicit feasible scores. On Roman-empire and Tolokers, aggregation improves fitted prediction, and retaining raw features helps at the largest tested parameter budget. Training-only diagnostics include conditional output-layer optimality bounds for eight fixed runs.
ER -