Nonlinear Maps Between Irreducible Representations in Graph Neural Networks

Mani Shayestehfar

cs.LGOct 29, 2026

Nonlinear Maps Between Irreducible Representations in Graph Neural Networks

Authors: Mani Shayestehfar

Abstract

Equivariant linear maps cannot mix non-isomorphic irreducible representations, whereas nonlinear activations can. We develop a degree-resolved version of this nonlinear interaction picture and use the resulting block inventory to construct Specht Triple, a residual on unordered graph triples. On a synthetic structural benchmark with a frozen GIN backbone, Specht Triple reduces aggregate standardised test MSE by 11.05% relative to a parameter-matched Projector Control using the same irreducible projectors and complete linear equivariant space. The results support irreducible decomposition as an inductive bias for nonlinear higher-order equivariant processing.

Figures & tables

Interpretation	Specht type	Dimension
Global variation	$L_{0}=S^{(n)}$	$1$
Vertex-level variation	$L_{1}=S^{(n-1,1)}$	$n-1$
Pair-level variation	$L_{2}=S^{(n-2,2)}$	$n(n-3)/2$
Triple variation	$L_{3}=S^{(n-3,3)}$	$n(n-1)(n-5)/6$

Table 1. The irreducible components of the unordered-triple permutation module. The descriptions are an interpretation of the subset-module filtration.

Panel of Figure 1 — Figure 1. The four $S_{n}$ -orbits on ordered pairs $(T,T^{\prime})$ of unordered triples, classified by their intersection size $|T\cap T^{\prime}|$ . These relations generate the Johnson scheme $J(n,3)$ and hence the complete linear $S_{n}$ -equivariant algebra on $V_{n,3}$ .

Model	Residual params	Aggregate	Diameter	Alg. connectivity
GIN	–	0.09132	0.11720	0.06543
Control Triple	884	0.07640	0.10492	0.04787
Projector Control	884	0.06937	0.10081	0.03794
Specht Triple	884	0.06171	0.08645	0.03696

Table 2. Mean standardised test MSE over ten paired seeds. The primary comparison is Specht Triple versus Projector Control . All residuals have

884

trainable parameters.

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

	$L_{0}$	$L_{1}$	$L_{2}$	$L_{3}$
$L_{0}$	1	0	0	0
$L_{1}$	1	1	1	0
$L_{2}$	1	1	2	1
$L_{3}$	1	1	2	2

Appendix

Figure 2. Degree-resolved interaction multiplicities for

V_{20,3}

. Matrix form avoids the direction and label ambiguity of dense arrow diagrams.

Item	Fixed setting
Primary targets	graph diameter, algebraic connectivity
Graph orders	$15\leq n\leq 24$ , exact- $n$ representation in every batch
Families	Erdős–Rényi, Barabási–Albert, Watts–Strogatz, two-block SBM
Train/validation/test	$8{,}000/2{,}000/4{,}000$ graphs
Backbone	five-layer GIN, width $64$ , frozen before residual training
Residuals	Control Triple , Projector Control and Specht Triple , $884$ parameters each

Appendix

Table 3. Experimental setup.

Family	Parameters	Range
Erdős–Rényi	edge probability $p$	$p\sim U(0.08,0.34)$
Barabási–Albert	attachments $m$	$m\in\{1,2,3,4\}$
Watts–Strogatz	degree $k$ , rewiring $\beta$	$k\in\{2,4,6\}$ , $\beta\sim U(0.05,0.45)$
Two-block SBM	block cut, $p_{\mathrm{in}},p_{\mathrm{out}}$	cut in middle third; $U(0.18,0.55)$ ; $U(0.02,0.18)$

Appendix

Table 4. Graph-generator parameters. Uniform intervals are sampled independently for each graph.

Component	Specht Triple	Either control
node projection	384	384
edge-count embedding	24	24
source/route or Johnson mixing	$24+156$	$144+6$
layer normalisation	24	24
residual head	272	302
Total	884	884

Appendix

Table 7

Seed	GIN	Control Triple	Projector Control	Specht Triple
11	0.09307	0.08139	0.08151	0.06383
23	0.09019	0.07012	0.05813	0.06492
37	0.08733	0.07603	0.08714	0.06515
53	0.09374	0.07637	0.06541	0.06288
71	0.08861	0.07254	0.07917	0.06023
89	0.09002	0.07533	0.05430	0.05728

Appendix

Table 5. Aggregate standardised test MSE by optimisation seed.

	GIN	Control Triple	Specht Triple
Residual parameters	–	$884$	$884$
Incremental training time (s)	–	$30.09\pm 0.38$	$147.35\pm 2.53$
Peak training memory (GiB)	–	$0.167\pm 0.001$	$0.679\pm 0.001$
Test-set inference time (s)	$0.0291\pm 0.0007$	$0.0508\pm 0.0011$	$0.2042\pm 0.0073$
Latency (ms / graph)	$0.00727\pm 0.00017$	$0.01271\pm 0.00029$	$0.05105\pm 0.00183$
Throughput (graphs / s)	$137{,}538\pm 3{,}184$	$78{,}722\pm 1{,}721$	$19{,}609\pm 663$

Appendix

Table 6. Computational cost over the ten optimisation seeds. Inference time is for the complete

4{,}000

-graph test set. Values are mean

\pm

standard deviation across seeds. Training quantities for the two higher-order models are incremental to the frozen GIN backbone.

	$\varepsilon$	$\rho_{1}$	$\rho_{2}$	$\rho_{3}$
$\mathbf{1}$	$\infty$	$\infty$	$\infty$	$\infty$
$\varepsilon$	1	$\infty$	$\infty$	$\infty$
$\rho_{1}$	4	1	2	3
$\rho_{2}$	2	$\infty$	1	$\infty$
$\rho_{3}$	4	3	2	1

Appendix

Table 10

Panel of Figure 3 — Figure 3. The graded Hom graph for $\mathbb{R}C_{8}$ . Edge labels give the first degree at which the corresponding symmetric-power Hom space becomes nonzero.

Panel of Figure 4 — Figure 4. Cumulative construction of the coordinatewise ReLU interaction graph on $\mathbb{R}C_{8}$ . ReLU retains degrees $0$ , $1$ and positive even degrees, so the degree-three red routes never enter.

Equivariant GNNs

Equivariant graph neural networks encode how node and edge features transform under symmetries to make geometry-aware predictions.

See all 48 papers

Sep 22, 2026

Graded Representation Theory of Equivariant Neural Networks

Nonlinear activations can create equivariant interactions between irreducible representations that linear maps cannot. We use the Gaussian degree decomposition to extend ordinary polynomial degree to such nonlinear maps, and prove that for a fixed coordinatewise equivariant layer each degree factors into a polynomial determined by the linear maps and a scalar determined by the activation. This separates three distinct obstructions, coming from symmetry, coordinates, and activation.

Mani Shayestehfar

Equivariant Neural Networks Equivariant Representation Learning Neural Network Expressivity

Ask PDF

Aug 21, 2026

Piecewise Linear Equivariant Maps for Compact Groups

Motivated by equivariant neural networks, we study piecewise linear equivariant maps between finite-dimensional real representations of compact groups. We show that all genuinely non-linear piecewise linear behaviour is confined to the subspaces on which the identity component of the group acts trivially, while equivariance forces linearity on the corresponding orthogonal complements. As a consequence, we obtain a compact-group analogue of the finite-group existence criterion of Gibson--Tubbenhauer--Williamson for non-zero equivariant piecewise linear maps between irreducible representations, with the identity component giving rise to a rigidity phenomenon absent from the finite-group case.

Valeriano Aiello

Topic pending

Ask PDF

Sep 29, 2026

Task-Relevant Null-Space Residuals for Non-Injective Neural Mappings

Non-injective mappings in neural networks map distinct inputs to the same representation, thereby implicitly inducing equivalence relations in the input space. However, the input differences eliminated by these mappings may still be required by downstream tasks, creating a mismatch between operator-induced indistinguishability and task-required distinctions. For non-injective linear operators realized in the current forward pass, their null spaces exactly characterize these invisible input variations. We propose Task-Relevant Null-Space Residuals (NSR), a general residual framework for non-injective linear mappings. NSR combines null-space component extraction from pre-mapping representations, member-level encoding and gating, and application-specific integration to exploit potentially task-relevant information under downstream supervision while preserving the original aggregation or merging rules. We evaluate NSR in two structurally different settings: token merging and graph aggregation. In token merging, NSR achieves higher semantic segmentation performance than the corresponding compressed baselines in 34 out of 36 evaluated configurations, with a maximum observed gain of 31.51 mIoU points under strong compression. In graph aggregation, NSR achieves 100% training accuracy on Tree-NeighborsMatch at depths d=2--6 across three backbones, alongside gains on heterophilic node classification and molecular graph regression. Together, these results support null-space residuals as a practical complement to non-injective linear mappings, enabling downstream models to learn from input distinctions invisible in the original operator's output.

Bizu Feng, Zhimu Yang, Shuming Wang +4

Institute of Artificial Intelligence Innovation and Industry, Fudan University, Shanghai, China · Shanghai Academy of AI for Science, Shanghai, China · Human Phenome Institute, Fudan University, Shanghai, China +1

Residual Learning

Ask PDF

Abstract

Equivariant GNNs

Explore similar work

Graded Representation Theory of Equivariant Neural Networks

Piecewise Linear Equivariant Maps for Compact Groups

Task-Relevant Null-Space Residuals for Non-Injective Neural Mappings