cs.LGOct 29, 2026

Nonlinear Maps Between Irreducible Representations in Graph Neural Networks

Authors: Mani Shayestehfar

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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

InterpretationSpecht typeDimension
Global variationL0=S(n)L_{0}=S^{(n)}11
Vertex-level variationL1=S(n−1,1)L_{1}=S^{(n-1,1)}n−1n-1
Pair-level variationL2=S(n−2,2)L_{2}=S^{(n-2,2)}n(n−3)/2n(n-3)/2
Triple variationL3=S(n−3,3)L_{3}=S^{(n-3,3)}n(n−1)(n−5)/6n(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.
Figure 1. The four SnS_{n} -orbits on ordered pairs (T,T′)(T,T^{\prime}) of unordered triples, classified by their intersection size ∣T∩T′∣|T\cap T^{\prime}| . These relations generate the Johnson scheme J(n,3)J(n,3) and hence the complete linear SnS_{n} -equivariant algebra on Vn,3V_{n,3} .
ModelResidual paramsAggregateDiameterAlg. connectivity
GIN–0.091320.117200.06543
Control Triple8840.076400.104920.04787
Projector Control8840.069370.100810.03794
Specht Triple8840.061710.086450.03696
Table 2. Mean standardised test MSE over ten paired seeds. The primary comparison is Specht Triple versus Projector Control . All residuals have 884884 trainable parameters.
Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

 L0L_{0}L1L_{1}L2L_{2}L3L_{3}
L0L_{0}1000
L1L_{1}1110
L2L_{2}1121
L3L_{3}1122
Appendix
Figure 2. Degree-resolved interaction multiplicities for V20,3V_{20,3} . Matrix form avoids the direction and label ambiguity of dense arrow diagrams.
ItemFixed setting
Primary targetsgraph diameter, algebraic connectivity
Graph orders15≤n≤2415\leq n\leq 24 , exact- nn representation in every batch
FamiliesErdős–Rényi, Barabási–Albert, Watts–Strogatz, two-block SBM
Train/validation/test8,000/2,000/4,0008{,}000/2{,}000/4{,}000 graphs
Backbonefive-layer GIN, width 6464 , frozen before residual training
ResidualsControl Triple , Projector Control and Specht Triple , 884884 parameters each
Appendix
Table 3. Experimental setup.
FamilyParametersRange
Erdős–Rényiedge probability ppp∼U(0.08,0.34)p\sim U(0.08,0.34)
Barabási–Albertattachments mmm∈{1,2,3,4}m\in\{1,2,3,4\}
Watts–Strogatzdegree kk , rewiring β\betak∈{2,4,6}k\in\{2,4,6\} , β∼U(0.05,0.45)\beta\sim U(0.05,0.45)
Two-block SBMblock cut, pin,poutp_{\mathrm{in}},p_{\mathrm{out}}cut in middle third; U(0.18,0.55)U(0.18,0.55) ; U(0.02,0.18)U(0.02,0.18)
Appendix
Table 4. Graph-generator parameters. Uniform intervals are sampled independently for each graph.
ComponentSpecht TripleEither control
node projection384384
edge-count embedding2424
source/route or Johnson mixing24+15624+156144+6144+6
layer normalisation2424
residual head272302
Total884884
Appendix
Table 7
SeedGINControl TripleProjector ControlSpecht Triple
110.093070.081390.081510.06383
230.090190.070120.058130.06492
370.087330.076030.087140.06515
530.093740.076370.065410.06288
710.088610.072540.079170.06023
890.090020.075330.054300.05728
Appendix
Table 5. Aggregate standardised test MSE by optimisation seed.
 GINControl TripleSpecht Triple
Residual parameters–884884884884
Incremental training time (s)–30.09±0.3830.09\pm 0.38147.35±2.53147.35\pm 2.53
Peak training memory (GiB)–0.167±0.0010.167\pm 0.0010.679±0.0010.679\pm 0.001
Test-set inference time (s)0.0291±0.00070.0291\pm 0.00070.0508±0.00110.0508\pm 0.00110.2042±0.00730.2042\pm 0.0073
Latency (ms / graph)0.00727±0.000170.00727\pm 0.000170.01271±0.000290.01271\pm 0.000290.05105±0.001830.05105\pm 0.00183
Throughput (graphs / s)137,538±3,184137{,}538\pm 3{,}18478,722±1,72178{,}722\pm 1{,}72119,609±66319{,}609\pm 663
Appendix
Table 6. Computational cost over the ten optimisation seeds. Inference time is for the complete 4,0004{,}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.
 1\mathbf{1}ε\varepsilonρ1\rho_{1}ρ2\rho_{2}ρ3\rho_{3}
1\mathbf{1}0∞\infty∞\infty∞\infty∞\infty
ε\varepsilon01∞\infty∞\infty∞\infty
ρ1\rho_{1}04123
ρ2\rho_{2}02∞\infty1∞\infty
ρ3\rho_{3}04321
Appendix
Table 10
Figure 3. The graded Hom graph for RC8\mathbb{R}C_{8} . Edge labels give the first degree at which the corresponding symmetric-power Hom space becomes nonzero.
Figure 4. Cumulative construction of the coordinatewise ReLU interaction graph on RC8\mathbb{R}C_{8} . ReLU retains degrees 00 , 11 and positive even degrees, so the degree-three red routes never enter.
More in this topic

Equivariant GNNs

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

See all 48 papers

Explore similar work

CardsList

  1. Graded Representation Theory of Equivariant Neural Networks

    Sep 22, 2026Mani ShayestehfarEquivariant Neural NetworksEquivariant Representation Learning

  2. Piecewise Linear Equivariant Maps for Compact Groups

    Aug 21, 2026Valeriano Aiello

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

    Sep 29, 2026Bizu Feng, Zhimu Yang, Shuming Wang +4Residual Learning

    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