Invertible Graph Aggregation Can Increase ReLU Readout Width

Hiroyasu Usami; Masanori Tsukamoto; Kohei Hashiguchi

cs.LGNov 1, 2026

Invertible Graph Aggregation Can Increase ReLU Readout Width

Authors: Hiroyasu Usami, Masanori Tsukamoto, Kohei Hashiguchi

Organizations: Department of Computer Science, Faculty of Engineering, Chubu University, Kasugai, Japan · Department of Systemic Management for Dentistry, Kagoshima University Hospital, Kagoshima, Japan

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\ge4$ , 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.

Figures & tables

Fig. 1: Readout width on the degree-three tree, shown for

N=12

. Helpers form a path, each with one leaf. Circles and squares denote labels

+1

and

-1

. Panel (c) separates the full aggregate axis from the expanded leaf axis; the shaded band locates the expanded interval. Raw features need one ordinary ReLU unit. One lazy mean creates

N+1

label transitions and requires

N

units, while retaining distinct aggregate rows and condition number at most 8.

Fig. 2: Exact minimum error in

\mathcal{H}_{m}

, which includes an uncounted affine term. Open markers are independent dynamic-programming checks. The raw affine separator has zero error already in

\mathcal{H}_{0}

. For ordinary heads

\mathcal{O}_{m}

, the aggregate curve is a lower bound and the exact zero-error width is

N

; the raw ordinary width is 1.

Fig. 3: Controlled readout fits. Large symbols show means over three paired data/initialization seeds; faint points show individual seeds. Panels (a)–(c) use sixteen evaluation realizations per seed; (a) and (b) repeat the noiseless training table. Panel (d) uses 4,096 fresh whole-graph realizations per seed with continuous primary and nuisance noise. Only widths 1 and 16 are fitted there; bars show seed SD. Its dotted curve is the population lower bound from ( 11 ). Black stars show fixed explicit

N

-unit scores.

$\alpha$	$\kappa_{2}$ , $N=8$	$\kappa_{2}$ , $N=16$	Transitions	Error (%)
0.25	1.54	1.54	1/1	0.00/0.00
0.49	3.12	3.18	7/13	25.00/18.75
0.50	3.25	3.33	9/17	25.00/25.00
0.51	3.40	3.49	7/13	25.00/25.00
0.75	49.16	1329.67	7/15	33.33/33.33

TABLE I: Mixing-strength controls on unchanged noiseless features. Transition counts and aggregated-head mean width-1 errors are listed as

N=8/N=16

. Condition numbers are numerical diagnostics of the actual

M_{\alpha}

Fig. 4: Held-out public results over ten official splits. Top: validation-selected test metric, with the mean and sample SD across splits. Parameter-budget concatenation uses the reduced width defined in the text. Bottom: change in the mixed-minus-raw gap from width 8 to 128. Positive values mean that the mixed advantage grows with width. Circles and squares show validation-selected states and final endpoints of the same runs; dashed lines show their means.

Dataset	Checkpoint	Gap at width 8	Gap at width 128	Width interaction
Roman-empire	Selected	$+2.66\pm 0.59$	$+5.25\pm 0.43$	$+2.59\pm 0.39$
Roman-empire	Final	$+3.14\pm 0.73$	$+6.37\pm 0.44$	$+3.23\pm 0.86$
Tolokers	Selected	$+3.17\pm 0.84$	$+3.85\pm 0.97$	$+0.67\pm 0.74$
Tolokers	Final	$+3.27\pm 0.71$	$+3.11\pm 0.70$	$-0.16\pm 0.72$

TABLE II: Mixed-minus-raw gaps and width interaction, in percentage points (mean

\pm

sample SD over ten overlapping splits). Roman-empire uses accuracy; Tolokers uses ROC AUC. “Final” denotes the final training checkpoint of the validation-chosen run.

Graph Neural Networks

Graph Neural Networks learn from graph-structured data by combining information across connected nodes, edges, and larger structures.

See all 751 papers

Closed-Form Node Classification with Exact Graph Unlearning
May 25, 2026Aditya Gaur, Charu SharmaGraph Representation Learning Privacy-Preserving ML
Machine Learning Lab · IIIT Hyderabad
Implicit Bias of SGD in Multivariate ReLU Networks: Effective Width Collapse
Jul 3, 2026Shuang Liang, Tom Jacobs, Guido MontúfarShallow Neural Networks ReLU Neural Networks
Department of Statistics & Data Science University of California, Los Angeles Los Angeles, CA 90095, USA · CISPA Helmholtz Center for Information Security · Departments of Mathematics and Statistics & Data Science University of California, Los Angeles; and Max Planck Institute for Mathematics in the Sciences
Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks
Aug 24, 2026Itay SafranShallow Neural Networks ReLU Neural Networks
Stein Faculty of Computer and Information Science, Ben-Gurion University of the Negev

May 25, 2026J/K move · Enter open · S save

Closed-Form Node Classification with Exact Graph Unlearning

Aditya Gaur, Charu Sharma

Machine Learning Lab · IIIT Hyderabad

Graph Representation Learning Privacy-Preserving ML Machine Unlearning Node Classification Graph Unlearning

Open paper AskPDF arXiv

Graph neural networks for node classification are typically trained by gradient descent over hundreds or thousands of epochs. Recent work has shown that, when properly tuned, classic GCN/SAGE/GAT architectures can match graph transformers on many node-classification benchmarks. We ask a complementary question: how much of this performance can be recovered by deterministic closed-form solvers, and what guarantees does this enable? We introduce a routed closed-form framework selected by adjusted homophily. For assortative graphs, we use SGC-style propagation followed by Ridge regression; for heterophilous graphs, we introduce LCF-Net, a layer-wise closed-form graph feature-refinement network whose per-layer Ridge solves are capped by a Gaussian kernel-Ridge head. Across 14 benchmarks, including ogbn-arxiv and ogbn-proteins, our closed-form predictors match or beat the best vanilla 2-layer GCN/SAGE/GAT on 9 of 9 measured datasets, tie tuned deep recipes within one standard deviation on 9 of 12 small benchmarks, and exceed the OGB-leaderboard plain GCN on both large graphs. The remaining heterophilous gap closely tracks the gain from vanilla 2-layer to deep SAGE, suggesting that the residual difference is primarily architectural. Because our predictors are explicit solutions of deterministic linear systems, modified graph inputs can be re-solved to obtain retrain-equivalent parameters. We formalize exact graph-object unlearning for label, feature, edge, node, and subgraph modifications, prove K-hop locality for Ridge components, and verify exactness across 109 configurations. On ogbn-arxiv, localized updates give

21

45\times

speedups over full re-solving and roughly

10^{6}\times

speedups over gradient retraining. Structural-inversion experiments further quantify the privacy floor of exact retraining and the additional leakage of approximate graph-unlearning methods.

Abstract

Graph Neural Networks

Explore similar work

Closed-Form Node Classification with Exact Graph Unlearning

Implicit Bias of SGD in Multivariate ReLU Networks: Effective Width Collapse

Every Layer Counts: An Exponential L2L_2L2​ Depth Hierarchy for ReLU Networks

Every Layer Counts: An Exponential $L_2$ Depth Hierarchy for ReLU Networks