Unifying Graph Neural Networks Through a Common Layer Equation

Sai Karthik Navuluru; Siddhartha Shankar Das; Bo Ni; Hongjie Chen; Yu Wang; Baris Coskunuzer; Nesreen K. Ahmed; Franck Dernoncourt; Mahantesh Halappanavar; Tyler Derr; Ryan A. Rossi; Lakshman Tamil

Source-linked AI summary

Unifying Graph Neural Networks Through a Common Layer Equation

Sai Karthik Navuluru, Siddhartha Shankar Das, Bo Ni, Hongjie Chen, Yu Wang, Baris Coskunuzer, Nesreen K. Ahmed, Franck Dernoncourt, Mahantesh Halappanavar, Tyler Derr, Ryan A. Rossi, Lakshman Tamil

arXiv:2608.16097v1Aug 17, 2026cs.LG

TL;DR

Family-specific motivations and notation make graph neural network architectures difficult to compare. The paper unifies covered layers in a seven-component equation and demonstrates checkable coverage through canonical reductions and representative fillings across seven families.

Problem
Family-specific motivations and notation make graph neural network designs difficult to compare.
Source: §1 · p. 4
Method
The paper represents covered graph layers with a seven-component equation whose function-valued fillings span seven architectural families.
Source: §8 · p. 55
Results
Worked reductions of four canonical layers and representative fillings across all seven families make the framework’s coverage checkable.
Source: §8 · p. 55
Takeaways & Limitations
Under endpoint-local messages and node-local updates, propagation-operator support bounds one-layer dependencies, while global mixing requires a full effective operator row.
Source: §1 · p. 4, §5.6 · p. 42
The framework excludes five named boundary cases that fall outside its channel primitives.
Source: §3.2 · p. 22

Abstract

from arXiv · show

Graph neural networks are commonly described through family-specific equations whose notation obscures shared computations and structural differences. We introduce a common layer equation that represents covered architectures through seven components: an update domain, channel set, propagation bank, per-channel message maps, channel-fusion operator, ego/residual map, and update map. The central factorization separates where information moves, encoded by the propagation bank, from what moves, encoded by the message maps. Function-valued fillings extend the same equation across local message passing, attention, spectral filtering, global communication, relation-specific channels, higher-order domains, and geometric messages. We make this unification explicit and checkable through worked reductions of canonical layers and component assignments spanning seven nonexclusive architectural families. A fixed slot discipline assigns operations by computational role and defines the framework's coverage boundary. The decomposition also yields component-level theoretical insights: under endpoint-local messages and node-local updates, operator support bounds one-layer dependencies, and one-layer global mixing requires a full effective operator row under the stated hypotheses. The resulting framework organizes more than 200 architectures in a common design space, enables component-wise comparison and generation of structurally consistent architectures, and connects propagation choices to oversmoothing, oversquashing, heterophily, and expressivity. It further exposes the empirical inverse problem of mapping measurable graph and task properties to validated component choices.

1 Introduction

The paper presents a component-based framework for comparing covered GNN layers, organizing architectural families, and analyzing how layer components shape computation. It also defines the framework’s scope and frames architecture selection as an empirical inverse problem.

1 Introduction

The paper unifies covered GNN layers with seven slots—domain, channels, propagation, messages, mixing, ego/residual, and update—separating where information moves from what moves.A fixed slot discipline assigns operations by computational role and supports worked reductions of four canonical layers.Source: §1 · pp. 4, 7, §1.1 · p. 8
Fixed component coordinates expose computational differences obscured by paper-specific notation and reveal unrepresented combinations that can guide structurally consistent architecture generation.The framework supports comparison through the components an architecture changes.Source: §1 · p. 8, §1.1 · p. 9

1.1 Contributions

Available comparisons do not establish a context-free ranking of component fillings, motivating the inverse problem of mapping measurable graph and task properties to validated choices.Rankings depend on heterophily, tuning, and evaluation protocol; the paper does not claim a no-free-lunch theorem or rule out dominance on a specified distribution class.Source: §1 · p. 8, §1.1 · p. 9
The framework organizes more than 200 architectures into seven nonexclusive families anchored to their primary component variation.Spatial, attention, spectral, and Graph Transformer families primarily vary propagation; heterogeneous, higher-order, and geometric families primarily vary channels, domain, or message and update maps.Source: §1 · p. 5, §1.1 · p. 9, §1.2 · p. 9
Under node-local updates, propagation support localizes one-layer dependencies and a full effective operator row is necessary for one-layer global mixing; raw channel count is non-identifiable in the linear additive regime.Minimum Kronecker channel rank is an invariant of the summed layer operator; the paper also connects component interactions to oversmoothing, oversquashing, heterophily, expressivity, and permutation symmetry.Source: §1 · p. 4, §1.1 · p. 9

1.2 Scope and Terminology

The equation covers single-layer graph computation, not complete training or deployment pipelines; reusable operations and problem settings are distinguished from architectural families.Temporal memory, pre-training objectives, generative decoders, retrieval systems, and other surrounding machinery remain outside its formal scope, while constituent layers and heterogeneous or geometric data adaptation remain in scope.Source: §1.2 · pp. 9–10

2 Preliminaries

This section establishes notation for graph structure, data, tasks, propagation, and symmetry, while defining the layer slots and spatial and spectral views for comparing graph neural network architectures. It also points ahead to the paper’s unified equation and seven-family literature organization.

2.1 Basic Graph-Theoretic Objects

A graph is represented by nodes, edges, adjacency, and degree; normalized adjacency and Laplacians define propagation supports, while sparse graphs make message passing tractable.The section distinguishes self-loop-normalized adjacency from the self-loop-free normalized adjacency used in spectral analysis.Source: §2.1 · p. 10

2.2 Graph Data and Notation

Node features, edge features, and optional graph features accompany layer representations; the unified update domain can index nodes or higher-order objects such as tuples, subgraphs, simplices, cells, or motifs.Hidden states default to the input features, and the final pre-prediction representation is denoted Z.Source: §2.2 · pp. 10–11

2.3 Learning Tasks on Graphs

The layer designs primarily target node, edge/link, graph, community/clustering, and combinatorial-optimization tasks.Graph generation and temporal/dynamic graph tasks are noted for completeness rather than treated as layer designs here.Source: §2.3 · p. 11

2.4 Homophily and Heterophily

Homophily describes similarity among connected nodes, but global averages can hide mixed neighborhoods, and standard propagation may degrade when homophily is absent.Edge homophily is sensitive to class count and balance, so raw comparisons across datasets can be unreliable; adjusted homophily corrects for this.Source: §2.4 · pp. 11–12

2.5 Message Passing Intuition

Message passing aggregates and transforms neighbor information, yielding an L-hop receptive field after L layers unless multi-hop propagation, rewiring, or global tokens extend reach.Repeated propagation can cause oversmoothing, oversquashing, and difficulty with long-range dependencies; later architectures modify propagation, aggregation, or graph structure to control information flow.Source: §2.5 · p. 12

2.6 Layer Slots in the Unified Equation

The seven-slot layer equation separates the update domain and channels from propagation operators, message maps, channel mixing, ego/residual maps, and updates.Channel contributions include aggregation where needed; channel mixing combines those contributions, and the update combines the mixed message with an ego or residual term. The seven families specialize different slots or their sub-properties.Source: §2.6 · pp. 12–13

2.7 Spectral and Spatial Perspectives

Spectral filtering and spatial propagation coincide for operators acting as scalars on each Lsym eigenspace, which can then be represented by Laplacian polynomials.Polynomial filters avoid eigendecomposition and are localized: Lsym^k x depends on nodes at most k hops away. The equivalence need not hold for general operators such as data-dependent attention or per-relation operators.Source: §2.7 · p. 14

2.8 Symmetry, Invariance, and Equivariance

Graph-level predictions should be permutation invariant and node-level predictions equivariant; equivariant sum-aggregation message passing is no more powerful than 1-WL at distinguishing non-isomorphic graphs.For higher-order domains, equivariance follows the induced permutation action; geometric models combine it with additional group symmetries such as translation or rotation.Source: §2.8 · pp. 14–15
Section 3 develops the unified equation and organizes the literature into seven families, while Appendix A, Table 10 collects the notation for reference.Source: §2.8 · p. 15

3 The Unified Layer Equation for Graph Neural Networks

The section presents a seven-component layer equation that separates where information propagates from what messages transmit, assigning computation by consistent roles to compare architectures and clarify the framework’s coverage boundary. It also derives conditional claims about layer coverage, permutation symmetry, dependency support, and channel identifiability, while treating task-specific component selection as an empirical problem.

3.1 Coverage, Claims, and the Seven Families

Under endpoint-local messages and node-local updates, the union of propagation supports bounds one-layer dependencies, while one-layer global mixing requires a full effective operator row under Proposition 5’s assumptions.Changing message maps, channel mixing, ego handling, or updates alone cannot create dependence outside the propagation-support envelope.Source: §3.1 · p. 16
In the linear additive regime, displayed channel count is not identifiable from the layer function; the minimum Kronecker separation rank is invariant.Channels may be split or added in cancelling pairs without changing the function, so different head, relation, or polynomial-term counts alone do not establish functional difference.Source: §3.1 · pp. 16–17, §3.2 · p. 19
The seven-slot equation covers matrix-value and pairwise-message channels, with full-layer decompositions distinguished from exact slices and named boundaries.A fixed slot discipline makes component placements checkable, but alternative conventions may relocate differences; the slots are not claimed to be orthogonal or to guarantee trainability, stability, scalability, or expressivity. Selecting fillings for a new task remains an empirical inverse problem.Source: §3.1 · pp. 15, 17, 18
Under the stated hypotheses, node-domain and graded layers and optional pooling are permutation equivariant; an invariant readout yields a permutation-invariant graph function.The row-wise update condition is sufficient but stronger than necessary; equivariant cross-node normalizations can be included by requiring equivariance of the relevant maps.Source: §3.1 · pp. 17–18

3.2 Setup and Notation

The notation separates propagation support and weights from channel values, channel mixing, prior-state handling, and updating, with matrix products and pairwise aggregation covering distinct message forms.Linear sums or means may fold into propagation operators, whereas pairwise messages and nonlinear aggregators remain explicit; the convention places GIN’s MLP in the update and GAT’s state dependence in propagation.Source: §3.2 · pp. 18, 20
Multi-head concatenation is additive mixing into disjoint output blocks, and in the linear case matches additive mixing only after projection to a common target width.The heads may have different widths, so raw summation need not be defined; downstream projection can preserve or erase the head separation.Source: §3.2 · p. 19
The seven-component equation assigns propagation, messages, channel mixing, ego input, and updating distinct roles, while treating the domain and channel set as the objects and branches being updated.For a multi-order bank Pk = Â^k, the diagonal entry [Â^k]ii is the k-step return probability, giving node i a structural self-weight through closed walks.Source: §3.2 · pp. 21–22
Coverage excludes order-dependent walk mixing, learned hard-sorting and sampled-sequence pipelines, search spaces, and static triple-scoring embeddings because they do not fit the stated channel primitives or layer-wise update.The named cases are NeuralWalker, NLGNN, GPNN, MR-GNAS, and TransE/DistMult-style embeddings; these failures of the reductions do not establish that no equivalent representation exists.Source: §3.2 · p. 22

3.3 Slot Discipline

The slot discipline assigns scalar weights and support to Pk, vector- or matrix-valued transformations to messages, and self, residual, teleport, and skip inputs to the ego map.The update map combines ego and mixed-channel inputs; the convention places self-loops in Pk when they follow the same scalar-weighting and shared-message rules as neighboring edges.Source: §3.3 · p. 23

3.4 Discriminating Axes

The discriminating axes record the operator bank and coefficient constraints, message-map type, and ego handling, preserving operational distinctions such as fixed support versus a polynomial basis.The family split is operational rather than a claim of theoretical separation in realizable functions.Source: §3.4 · p. 23

3.5 Worked Reductions for the Canonical Models

Worked reductions recover GCN’s fixed normalized self-loop update, GraphSAGE’s neighbor mean with separate ego input, GAT’s state-dependent scalar weights, and GIN’s scaled ego sum.These assignments locate the distinctions in operator normalization and weight dependence, as well as in whether ego state is concatenated or added inside an MLP.Source: §3.5 · pp. 24–25
A single-head layer with scalar state-dependent neighbor weights on linear values fits the framework’s state-dependent operator and message slots; multiple heads mix over the head index.In the single-head, edge-feature-free case, GAT and GATv2 differ only in the functional form of the attention weight.Source: §3.5 · p. 25

3.6 Graded Extension for Higher-Order Models

The graded extension updates higher-order objects through generally rectangular inter-rank operators and covers tuple domains and cell complexes, but NGNN’s inner GNN and pooling do not fit a one-layer filling.The pairwise branch also extends to geometric and edge-conditioned messages; the dense-tuple PPGN bilinear product fits the inter-rank linear branch using one state-dependent scalar operator per output channel.Source: §3.6 · pp. 25–26

4 Generated Architectures from the Unified Equation

The unified equation defines three increasingly open ways to generate structurally checkable architectures, while their empirical performance remains untested. Six architectures pass the audit, including a Level 3 layer that adds an execution schedule.

4.1 Procedure for Generated Architectures

A language-model controller proposes functional forms for three levels, and retained proposals must satisfy level-specific type, symmetry, dimensional, inventory, and reduction checks.Level 1 recombines catalogued fillers; Level 2 proposes a new filler within the seven slots; Level 3 adds a typed component while preserving the base equation when removed.Source: §4.1 · p. 26, Figure 3 · p. 27
Six generated architectures pass the level-specific audit: five are Levels 1–2, and the Level 3 Sequential Co-Lifted Node–Edge Layer adds a schedule that orders graded updates.The schedule distinguishes sequential writeback from synchronous graded coupling.Source: §4.1 · p. 26, §4.2 · p. 27

4.2 Generated Architectures

The six generated architectures comprise five controlled changes to existing fillers and a Sequential Co-Lifted Node–Edge Layer; Relation-Equivariant Network indexes its message by relation.The first four architectures recombine existing fillers across families.Source: §4.2 · p. 27
Spectrally-Gated Propagation replaces GPR-GNN’s global per-order coefficient with a node-adaptive coefficient, yielding state-dependent, spatially modulated polynomial propagation.Because the node-wise diagonal gate need not commute with the polynomial operator, the result is not generally a scalar spectral multiplier with a global passband.Source: §4.2 · p. 27

5 GNN Propagation: Limits, Expressivity, and Remedies

This section examines propagation-related limits and trade-offs, including oversmoothing, oversquashing, and heterophily, and how structural information and propagation choices shape expressivity. It also considers how these limits constrain architecture generation, states conditions for one-layer global mixing, and discusses the limits of an operator-only account.

5.1 Oversmoothing: collapse under repeated propagation

When the layer-norm bound satisfies s̄μ⋆ < 1, repeated low-pass propagation contracts features toward the dominant subspace, with decay jointly dependent on the nontrivial spectrum, feature-map norms, and activation.For connected graphs with self-loop normalized adjacency, the subspace is degree-dominated; the spectral radius μ⋆ includes negative eigenvalues, so substituting a Laplacian-gap quantity needs additional assumptions.Source: §5.1 · pp. 31–32
Oversmoothing has qualifications and remedies: input-dependent attention can still contract under stated assumptions, while residual benefits are distribution-dependent and initial-residual teleport can preserve an energy floor.Rank collapse may be a more faithful degradation signature than Dirichlet energy; finite aggregation depth can help before eventual collapse, and backward smoothing or gradient expansion can impair training.Source: §5.1 · pp. 32–33

5.2 Oversquashing: sensitivity, curvature, and effective resistance

With locally supported propagation, endpoint-local messages, and node-local updates, depth-L representations depend only on the L-hop ball; topological bottlenecks then constrain distant-signal sensitivity.Effective resistance relates transition weights to a graph-level oversquashing budget, and guaranteeing fixed interaction can force depth and weight norms to grow with commute time; depth below source-target distance causes underreaching.Source: §5.2 · pp. 33–34

5.3 Heterophily: a spectral mismatch

Repeated normalized-adjacency propagation suppresses non-dominant frequencies, so fixed low-pass filters can remove class signal; polynomial channels can realize any frequency response and match its discriminative band.A high-pass response that zeros the smoothing direction is realizable when class signal lies at high frequencies, though heterophily alone does not establish that location.Source: §5.3 · p. 35

5.4 The oversmoothing-oversquashing trade-off

Under the analyzed operator family and assumptions, increasing the normalized-Laplacian spectral gap accelerates mixing and relieves oversquashing but also speeds energy decay, selecting a trade-off rather than independently improving both.The gap interpretation of the sharper smoothing rate applies only when μ₂ ≥ 0 and |μ₂| ≥ |μₙ|; this is not an impossibility theorem for all architectures or interventions.Source: §5.4 · p. 36
The spectral gap λ2 couples oversquashing and oversmoothing: raising it eases bottleneck compression but accelerates homogenization, trading one pathology for the other.The account treats this as a first-order organizing principle, not a universal law: separability, feature distributions, and pass-band mismatch also matter.Source: Figure 7 · p. 38, §5.4 · p. 38

5.5 Expressivity: the WL ladder and substructure counting

Under stated node-domain, shared-map, and structure-blind assumptions, message passing is bounded by 1-WL; structural escapes change the domain, input, or propagation operator.The three listed escapes are not exhaustive: structure-aware maps, fusion, or readout can also exceed 1-WL, while changing a component need not help if its encoding remains 1-WL-refinable.Source: §5.5 · p. 39
Attaining the 1-WL ceiling requires injective neighbor aggregation and an injective update combining the aggregate with the root state; mean and max aggregation lose multiplicity information.An injective encoding followed by neighbor summation can preserve bounded-size multisets, but injective aggregation alone is insufficient without an injective root-and-aggregate update.Source: §5.5 · p. 40
Expressivity spans distinct WL, subgraph, counting, and spectral capabilities, which should not be read as one total ordering.On a fixed graph, polynomial filters reach every one-dimensional target with distinct eigenvalues and nonzero signal projection on every eigenvector; this is not graph-distinguishing universality. Spatial message passing paired with bounded spectral filters can widen receptive fields and mitigate oversquashing without added message-passing depth.Source: §5.5 · pp. 40–41, Table 7 · p. 41

5.6 Global attention as a propagation channel

Under fixed-operator and node-local hypotheses, one-layer global mixing requires every off-diagonal entry in the effective operator row; a virtual node generally needs two propagation steps.A virtual-node MPNN approximates linear attention at O(1) depth and width, while full softmax attention requires either O(nd_in) width at O(1) depth or O(1) width at O(n) depth.Source: §5.6 · p. 42, Figure 8 · p. 43

5.7 Constraining Generated Architectures by Propagation Limits

Propagation limits can guide architecture generation by favoring component choices that avoid diagnosed spectral-gap or pass-band problems, but which limit binds is empirical.The operator-level account is partial: node separability and feature distributions are not determined by the spectrum, and benchmark evidence is related without causal attribution.Source: §5.7 · p. 43

6 Benchmark Properties in the Component Vocabulary

The section translates documented benchmark properties and protocols into the layer-component vocabulary, identifying where models can respond without attributing performance to a single component or predicting the best design. It argues that valid protocols and controlled comparisons are prerequisites for component-level conclusions.

Node-classification benchmarks

Cora, Citeseer, and Pubmed are homophilous, while heterophilous benchmarks implicate several possible components and do not isolate any one choice.Adjusted homophily is more comparable across class counts and imbalance, while label informativeness aligns more closely with performance in controlled experiments (Platonov et al., 2023a); duplicates in Chameleon and Squirrel distort comparisons.Source: §6 · p. 44

Benchmark collections and controlled protocols

OGB, TUDataset, and Benchmarking-GNNs serve different purposes: realistic standardized evaluation, dataset access, and controlled model comparison, respectively.OGB spans tasks and domains; TUDataset contains more than 120 graph-classification and regression datasets; Benchmarking-GNNs matches parameter budgets and infrastructure.Source: §6 · p. 44

Long-range and distribution-shift benchmarks

LRGB suggests long-range dependence without proving it, while GOOD’s component interpretation depends on whether each split shifts features, structure, or input–label relationships.Later LRGB reevaluation found that stronger tuning could greatly reduce or eliminate the reported GNN–Transformer gap (Tönshoff et al., 2024).Source: §6 · p. 44

Industrial and temporal evaluation

GraphLand and TGB show that temporal and inductive evaluation can change performance, while temporal tasks may involve layer extensions and evaluation choices beyond the base equation.GraphLand reports strong graph-augmented gradient-boosted-tree baselines, particularly for regression; TGB finds simple methods can outperform temporal graph models on dynamic node-property tasks, and EdgeBank can be strong for dynamic link prediction.Source: §6 · pp. 44–45

What benchmark evidence permits component-level conclusions

Protocol validity comes before component attribution: splits, training choices, benchmark defects, and evaluation errors can distort comparisons or reverse model rankings.Duplicate-node leakage, missing normalization, metric errors, tuning, repeated edges, and negative sampling can each alter apparent model performance.Source: §6 · p. 46
Component validation should pair controlled tasks with realistic benchmarks and report both matched-resource comparisons and comparisons with equal tuning effort.Controlled tasks can isolate mechanisms, whereas realistic datasets test performance under deployment-relevant variation; equal-resource and best-attainable comparisons answer different questions.Source: §6 · p. 46

Boundaries of the component reading

Benchmark properties map many-to-many onto components, and component attribution requires controlled changes while holding architecture, resources, splits, heads, and protocols fixed.Readouts, pairwise scoring, sampling, scale, negative sampling, and evaluation choices can lie outside the seven-component layer; interaction claims require factorial comparisons.Source: §6 · pp. 43, 46

7 Open Problems and Challenges

The section identifies an unresolved inverse problem: selecting component fillings from measurable data, task, or deployment properties, with no generally validated solution. It also considers surrounding systems that the base-layer equation does not fully represent.

7.1 Generalization and optimization theory beyond expressivity

A joint theory linking expressivity, generalization, and optimization is still needed to identify task-useful slot fillings without prohibitive complexity.Existing worst-case bounds can inflate with added expressivity; a hierarchical optimal-transport result offers generalization guarantees for one metric, but does not establish coexistence for arbitrary fillings or cheaper propagation operators.Source: §7.1 · p. 49

7.2–7.4 Distribution shift, dataset-adaptive selection, and architecture generation

Transfer, slot selection, and architecture search lack reliable structural signals: relevant invariants vary by shift, homophily is fragile, and causal data-conditioned search remains open.The needed mapping must connect graph properties to choices such as Pk, Ψk, and X, and search must generalize under shift rather than learn distribution-specific correlations.Source: §7.2 · p. 49, §7.3 · p. 50, §7.4 · p. 50

7.5–7.6 Propagation scaling and temporal graphs

Efficient global propagation and temporal memory remain unresolved: sub-quadratic operators’ expressivity is unclear, while B(t) must preserve event identity and shift-invariant temporal structure.Practical scaling also depends on model–system co-design; temporal GNNs lack a settled expressivity ladder, and the tuple’s temporal roles include time-varying Pk(t) and event-preserving Ψk.Source: §7.5 · p. 50, §7.6 · p. 51

7.7–7.8 Readout and graph foundation models

Across 17 pooling methods and 28 datasets, no method consistently dominates and unpooled baselines match most; foundation models face negative transfer, while a priori compatibility and predictive scaling remain unresolved.The required vocabulary spans H(0), X, Pk, and Ψk.Source: §7.7 · p. 51, §7.8 · p. 51

7.9–7.10 Trustworthy GNNs and symmetry

Propagation entangles robustness, privacy, fairness, uncertainty, and accuracy, while symmetry constraints must balance task-aligned equivariance against expressivity and scale.The section calls for architecture-aware certification, topology-aware debiasing, verifiable forgetting, and graph-native uncertainty; task-aligned symmetry relaxation remains untested directly for graphs.Source: §7.9 · p. 52, §7.10 · p. 52

7.11.1–7.11.2 Retrieval and personalization

Retrieval and personalization need operators conditioned on the query or user, rather than heuristic subgraph choices or shared propagation that fails under sparsity and drift.For retrieval, the target is joint query-conditioned selection of X and Pk to reduce hallucination for a fixed decoder; personalization also requires user-conditioned Pk and Ψk for generation.Source: §7.11.1 · p. 53, §7.11.2 · p. 53

7.11.3–7.11.5 Reasoning, agent, and weight-space graphs

Reasoning and communication graphs lack task-grounded topologies and attributable gains, while weight-space GNNs still need symmetry-correct operators that scale to large models.The open targets include task-inferred reasoning structure with measurable links to quality, task-conditioned communication with credit assignment, and parameter editing or generation at language-model scale.Source: §7.11.3 · p. 53, §7.11.4 · p. 53, §7.11.5 · p. 54

7.12 The evaluation crisis and whether progress can be measured

Reliable progress requires leakage-free, shift-aware, application-grounded evaluation that isolates component effects; the spectral–spatial distinction may also depend on task.The section also calls for controlling the architecture and evaluation pipeline, and notes that spectral propagation may not be theoretically distinct from spatial message passing for node classification.Source: §7.12 · p. 54

8 Conclusion

The paper unifies covered graph neural layers through a seven-component equation whose function-valued fillings span diverse architectural families and make coverage checkable. It also uses this decomposition for component-level analysis while framing dataset-specific component selection as an empirical inverse problem.

8 Conclusion

A seven-component equation unifies covered graph neural layers, with function-valued fillings spanning seven architectural families and worked reductions making coverage checkable.The components are update domain, channel set, propagation bank, per-channel message maps, channel-mixing operator, ego/residual map, and update map.Source: §8 · p. 55
A fixed slot discipline supports consistent component assignments, while functional equivalence also requires agreement in internal mechanisms and component interactions that determine inductive bias.The seven primary-axis families are nonexclusive and distinct from reusable operations and problem settings.Source: §8 · p. 55
Under endpoint-local messages and node-local updates, operator support bounds one-layer dependencies; in the linear additive regime, minimum Kronecker channel rank is invariant despite raw channel-count non-identifiability.The framework also gives a necessary full-row condition for one-layer global mixing.Source: §8 · p. 55
Propagation-bank spectral and topological properties connect propagation choices to oversmoothing, oversquashing, heterophilic failure, and expressivity limits, while the shared vocabulary supports component-wise remedies and architecture generation.Generated architectures are formally specified candidates for empirical evaluation, and documented benchmark evidence is translated descriptively into component choices.Source: §8 · p. 55
Selecting the best component filling for a dataset remains an empirical inverse problem requiring controlled evidence and robust graph and task descriptors.Common statistics such as homophily are fragile; the unified equation, families, and comparison tables provide a shared language for pursuing validated mappings.Source: §8 · p. 55

Appendix A Notation · Appendix B Operations: Composable Modules · B.1 Positional and Structural Encodings

Appendix A establishes the paper’s graph, spectral, feature, and layer-slot notation. Appendix B treats positional and structural encodings as reusable operations assigned to existing components or external locations, rather than as architecture families.

Appendix A Notation

The notation covers graph structure, adjacency and Laplacian variants, spectral quantities, and node features and states used throughout the paper.It distinguishes, for example, self-loop-augmented from self-loop-free normalized adjacency and defines graph signals and spectral filters.Source: Appendix A · p. 89
The unified layer equation assigns computation to seven slots, separating the update domain and channels from propagation, message maps, fusion, ego/residual processing, and update.The notation also distinguishes the optional pooling map and post-stack readout from the seven per-layer components.Source: Appendix A · p. 90
Family tables display the seven components in six columns, folding scalar coefficients into propagation and reporting ego/residual and update components together.For a single channel, fusion is the identity; for pairwise channels, neighbor aggregation defines each contribution before cross-channel fusion.Source: Appendix A · p. 90

Appendix B Operations: Composable Modules

Operations are reusable edits across architecture families, and their primary slot assignments suggest compatibility without guaranteeing independence across components.Edits targeting the same component require an explicit combination rule; even different-slot operations can interact indirectly.Source: Appendix B · p. 91

B.1 Positional and Structural Encodings

Positional encodings depend on a node’s graph position and structural encodings on its local subgraph; either can break indistinguishability of nodes with isomorphic rooted attributed L-hop neighborhoods.Whether an encoding separates such nodes depends on the descriptor used.Source: §B.1 · p. 91
Node-level encodings primarily enter the message map or external initial state, while pairwise attention biases modify propagation and pairwise value features modify messages.A node-level encoding preserves a fixed structural operator, but can affect a state-dependent operator indirectly through attention scores.Source: §B.1 · p. 91
Representative encodings include Laplacian eigenvectors, random-walk return probabilities, and distance-to-anchor descriptors.Laplacian eigenvectors have sign and repeated-eigenspace basis ambiguities; random-walk return probabilities include backtracking walks, and anchor selection must preserve permutation equivariance. Random-walk SE is described by Dwivedi et al. (2022a).Source: §B.1 · pp. 91–92
PE/SE modules are family-agnostic, and adding a cataloged encoding or a genuinely new learned encoding maps to different architecture-generation levels.Concatenating an existing encoding into a family is a level 1 move; supplying a learned or graph-adaptive encoding not in the inventory is level 2 if the layer does not reduce to an existing method. Pairwise encodings are classified by the operator slot they edit.Source: §B.1 · p. 92

B.2 Graph Rewiring and Virtual Nodes … B.5 Pooling and Readout

These sections map rewiring, residuals, normalization, and pooling to the common layer equation while distinguishing their computational roles and limitations. They explain how these choices affect information flow, training, equivariance, and graph-level readout.

B.2 Graph Rewiring and Virtual Nodes

Rewiring changes communication support and operator weights to ease oversquashing, but may not relieve bottlenecks and can sacrifice fidelity to the input graph.Static rewiring modifies support once before rebuilding a fixed operator bank; dynamic rewiring changes support per layer. Importing a catalogued operator is a Level 1 move, while a new curvature-gated propagation filler is Level 2.Source: §B.2 · pp. 92–93
Spectral rewiring targets the lazy or absolute spectral gap, while virtual nodes enable two-hop global paths rather than one-hop pairwise mixing.A larger gap can accelerate smoothing, so reducing oversquashing and oversmoothing can trade off; a virtual node can simulate global interaction under suitable depth, width, and update capacity, but is not generally equivalent to arbitrary pairwise attention.Source: §B.2 · pp. 92–93

B.3 Skip and Residual Connections

Initial residuals re-inject each node’s transformed initial representation to help preserve an anchor during deep propagation, but generic residuals do not guarantee escape from smoothing.The energy-floor result applies specifically to the initial-residual PPR iteration; reversible residuals instead constrain the ego and update maps to make the forward map invertible, trading recomputation for memory.Source: §B.3 · pp. 93–94
Cross-layer skips extend the ego map to read earlier states, and dense jumping-knowledge aggregation can instead be deferred to readout.The mixing maps must preserve permutation equivariance; combining initial and dense skips requires an explicit rule because both occupy the ego/residual slot. Reusing an existing residual is Level 1, whereas a new combination rule is Level 2.Source: §B.3 · pp. 93–94

B.4 Normalization

Normalization most often belongs in the update map, but pre-normalizing states before propagation also changes the operator and message maps.PairNorm and related cross-node normalizations require a generalized permutation-equivariant update rather than the stricter node-local specialization; reusing an existing rule is Level 1, while a new rule can be Level 2.Source: §B.4 · p. 94
PairNorm counteracts contraction by fixing aggregate pairwise distance, GraphNorm normalizes each graph with a learned mean shift, and DropEdge perturbs the operator bank rather than exactly normalizing it.Because degree normalization is nonlinear, the expected operator after edge dropping need not equal a constant rescaling of the clean operator.Source: §B.4 · p. 94

B.5 Pooling and Readout

Flat pooling produces a graph-level vector through an invariant readout, and a specially chosen sum encoding can be injective on bounded-size multisets over a countable state space.A raw sum is not itself injective; GIN’s expressiveness relies on a suitable injective encoding and an injective post-map.Source: §B.5 · p. 95
Hierarchical pooling changes the domain between layers through an equivariant node-to-cluster map, while the final readout acts once on the resulting domain.An existing coarsening scheme is a Level 1 recombination and a new equivariant map is Level 2; flat readout design is orthogonal to the three generation levels.Source: §B.5 · p. 95

B.6 Continuous-Depth and ODE Views · B.7 Mini-Batch Sampling

The sections distinguish continuous-depth reinterpretations from broader ODE architectures, and explain how mini-batch sampling changes the support on which graph layers are evaluated. Together, they characterize which architectural components change, what sampling estimates, and where the framework’s classifications have limits.

B.6 Continuous-Depth and ODE Views

A residual layer is an explicit Euler step of its corresponding ODE, making depth integration time while retaining the propagation operators that define the dynamics.The standard residual corresponds to step size h = 1; in the narrow reinterpretation, the integrator changes while the propagation operators and message maps are reused.Source: §B.6 · p. 95
The narrow continuous-depth reinterpretation is classified as an operation on the update map, not a family; equivalence in expressiveness or stability is not claimed.The operation-versus-family boundary is a modeling choice, since some readers may treat the integrator as the defining computation.Source: §B.6 · pp. 95–96
Augmented ODE dynamics can enlarge per-node state and alter message, update, or propagation components; a new filler may qualify as generation level 2, but not level 3.Appending a velocity channel does not change the object domain; level 3 is reserved for an added, typed, separately removable component.Source: §B.6 · pp. 95–96
Diffusion-based models integrate graph diffusion as heat flow, while oscillator models add second-order dynamics to avoid collapse to the diffusion fixed point (Rusch et al., 2022).The cited diffusion-based examples are Chamberlain et al. (2021b), Xhonneux et al. (2020), Chamberlain et al. (2021a), Choi et al. (2023), and Zhao et al. (2023b).Source: §B.6 · p. 96

B.7 Mini-Batch Sampling

Full-batch training can be infeasible at scale, so mini-batch sampling restricts each step to a subgraph in exchange for tractable memory and runtime.Sampling changes the support on which a layer function is evaluated, not its functional form, and is usually a training-time operation.Source: §B.7 · p. 96
Importance-weighted sampling can make the propagated pre-activation an unbiased estimate of the full aggregate, but a nonlinear update generally makes the layer output biased.In general, E[σ(bm)] ≠ σ(E[bm]), so neighbor and cluster sampling approximate rather than reproduce the full-graph forward pass.Source: §B.7 · p. 96
Node-wise, layer-wise, and subgraph sampling differ in sampled support and estimator; unbiasedness depends jointly on the sampling distribution, estimator, and importance or normalization weights.These approaches respectively sample neighbors per node and layer, a shared node set per layer, or induced subgraphs; subgraphs need not always be connected.Source: §B.7 · p. 96
Different primary component assignments suggest prima facie compatibility, while shared assignments require reconciliation; this heuristic is not a guarantee, especially for cross-component operations.Sampling itself is not a generation move, and architectures at any generation level can be trained with node-wise, layer-wise, or subgraph sampling.Source: §B.7 · pp. 96–97, Table 11 · p. 97

Appendix C Theoretical Analysis

Appendix C studies what the propagation bank and surrounding slots can identify, express, and preserve under stated assumptions. It establishes boundaries for one-layer reach and global mixing, depth-wise smoothing, structural discrimination, and permutation consistency.

C.1

Channel count is not recoverable from the layer representation; channel rank is the invariant.The passage associates this result with the channel propagation terms k ⊗ Pk.Source: Appendix C · p. 99

C.2

For fixed operators, one-layer mixing of all other nodes requires a full off-diagonal support row and is generically sufficient.A virtual node therefore needs two layers for global mixing; globally state-dependent operators are not covered by this necessity claim.Source: Appendix C · p. 99

C.3

Initial-residual iteration converges to a personalized-PageRank fixed point with energy above a fraction of anchor energy, while polynomial filters can retain non-smoothing signals.The energy condition requires nonzero non-DC anchor content; a high-pass response zeroing the smoothing direction is realizable at degree at most q −1, and distinct-eigenvalue polynomial filters reach every vector when the signal misses no frequency.Source: Appendix C · p. 99

C.4

Without identifiers, a node-domain stack with structure-blind node-wise maps and operators weighted only by incident 1-WL colors is bounded by 1-WL.The domain, input message, or structure-aware operator can lift the ceiling; an uninformative filling need not help.Source: Appendix C · p. 99
Injectively encoded neighbor messages summed with P = A and combined injectively with the root attain the 1-WL ceiling; mean and max aggregation cannot be made injective.Raw summation is not injective on multisets, and injective neighbor aggregation alone does not suffice.Source: Appendix C · p. 99
Equivariant operators, messages, mixing, ego and update maps, and optional pooling yield an equivariant stack and, with invariant readout, an invariant graph function.The theorem includes shared row-wise or pairwise specializations.Source: Appendix C · p. 99

C.1 Subsumption: families as slot choices

Named spectral and attention models are recovered as exact fillings of the common layer slots, while the factorization clarifies channel mixing and the limits of identifying channel count. It also permits hybrid slot choices beyond the fixed choices of named models.

C.1 Subsumption: families as slot choices

ChebNet, SGC, GPR-GNN, BernNet, and APPNP recover their defining equations through fixed spectral slot choices, while the framework also permits hybrid coupled and decoupled channels.The choices distinguish propagation operator and basis, coefficient constraints, and whether messages use the evolving state or a layer-independent signal.Source: §C.1 · p. 100
Attention coefficients occupy the propagation bank and values the message maps; multi-head concatenation is additive mixing, and edge features can alter scores, messages, or both.Final-layer head averaging rescales each contribution by 1/M, which can be absorbed into its propagation operator; GAT and GATv2 differ in the score-producing form.Source: §C.1 · p. 100
In the linear regime, channel count is not identifiable from the layer map, whereas the minimum number of Kronecker summands representing the total operator is well-defined as channel rank.Linearity makes the function depend only on the sum of channel terms; splitting a term or adding a canceling pair changes the count without changing that sum.Source: §C.1 · pp. 100–101

C.2 Locality and globality: properties of the support of Pk

Under local-computation or fixed-operator hypotheses, the support of propagation operators determines which node states can reach a target: it bounds multi-layer locality, constrains one-layer global mixing, and gives multi-hop channels structural self-weights. Globally state-dependent operator entries fall outside this support-only account.

C.2 Locality and globality: properties of the support of Pk

With endpoint-local messages and node-local updates, depth L limits a node’s receptive field to its L-hop ball.The bound follows inductively from the propagation support; globally state-dependent operators are outside this support-only result.Source: §C.2 · p. 101
For fixed operators, one-layer dependence on every other node requires a full off-diagonal row, which generically suffices with message-faithful updates.This support condition does not apply to globally state-dependent operators, whose entries can depend on nodes absent from the corresponding support positions.Source: §C.2 · pp. 101–102
A multi-hop propagation channel contributes return-probability mass to its diagonal, creating a structural self-weight.For the conjugated normalized adjacency operator, the diagonal entry equals the corresponding self-loop random walk’s k-step return probability.Source: §C.2 · pp. 101–102

C.3 Smoothing, homophily, and heterophily: spectral filling of Pk

This section analyzes oversmoothing through spectral propagation and presents residual and spectral-filter mechanisms for preserving or selecting node signals. Under the stated spectral conditions, spectral filters can retain heterophilic signal and attain every output.

C.3 Smoothing, homophily, and heterophily: spectral filling of Pk

An initial residual preserves energy above a strict floor under the stated self-loop spectral conditions, while its affine update converges to a unique fixed point.The contraction uses η ∈ (0, 1); self-loops exclude the eigenvalue −1, which is needed for the strict floor.Source: §C.3 · pp. 102–103
Across L low-pass layers, E(H(L)) ≤ (s̄ μ⋆)^(2L)E(H(0)), showing how repeated propagation bounds Dirichlet energy.The layerwise bound is E(H(ℓ+1)) ≤ (sℓ μ⋆)^2E(H(ℓ)); the stack bound uses s̄ = maxℓ sℓ.Source: §C.3 · p. 102
A degree-(q−1) spectral filter can zero the smoothing direction while retaining nonzero response wherever discriminative signal lies, including under heterophily.Polynomial interpolation allows independently assigned responses across the graph’s distinct eigenvalues.Source: §C.3 · pp. 102–103
With a distinct spectrum and nonzero input coefficients in every eigenvector direction, polynomial filtering can attain every output in R^n.The degree-at-most-(n−1) filter assigns arbitrary responses at the n distinct eigenvalues.Source: §C.3 · pp. 102–103

C.4 Expressivity boundary and symmetry · Appendix D Per-Family Comparison Tables

The framework ties expressivity and permutation symmetry to explicit component-level conditions, clarifying both the limits of structure-blind node-domain stacks and the ways those limits can be exceeded. It also locates broader design properties in components or their interactions rather than architecture names.

C.4 Expressivity boundary and symmetry

Structure-blind node-domain stacks cannot exceed 1-WL; reaching that ceiling requires injective neighbor aggregation and an injective root–aggregate update.The update must distinguish the root from the aggregate; channel-fusion ⊞ is not the component responsible for this injectivity.Source: §C.4 · pp. 103–104
Permutation equivariance requires consistent relabeling and equivariant propagation, messages, channel mixing, ego/residual maps, and updates.Shared row-wise maps are sufficient, not necessary; equivariant row-coupled maps are also covered.Source: §C.4 · pp. 103–104
The 1-WL ceiling depends on structure-blind propagation: changing the colored object, enriching input features, or using structure-dependent operators can exceed it.A one-hop operator weighted by per-edge triangle counts separates the 1-WL-indistinguishable triangular prism and K3,3: it is nonzero on prism triangle edges and vanishes on K3,3.Source: §C.4 · pp. 103–104
Injective sum-based neighbor encodings alone do not attain 1-WL if the update loses root identity; mean and max aggregation also collapse distinct multisets.A separate ego term and injective update over the root–aggregate pair provide the needed distinction; the (1 + ϵ) self-weight is one suitable construction under appropriate conditions.Source: §C.4 · p. 104
The equivariance conditions extend to graded domains and pooling when operators transform across ranks and coarsened graphs are constructed equivariantly.A permutation-invariant readout then produces an invariant graph output.Source: §C.4 · pp. 104–105
The framework locates channel-rank identifiability, one-layer globality, and principal smoothing escapes in specific component interactions.In the linear regime, channel dependence is through T = Pk ⊗ Ψk; one-layer globality requires a full effective operator row under the stated hypotheses, while two smoothing escapes lie in Bℓ and the spectral filling of Pk.Source: §C.4 · p. 105

D.1 Assignment rules for primary families

Primary families are assigned by the rule that best describes a layer update’s dominant mechanism, while other mechanisms are recorded as cross-references or boundary notes. The family decompositions apply a fixed component-slot discipline and mark machinery outside the declared layer when relevant.

Assignment rule

A method’s primary family is the one whose rule best describes its cited layer update’s dominant mechanism; other mechanisms are cross-referenced or noted as boundaries.This assignment rule is listed in family order.Source: Table 13 · p. 105

Family 1: Spatial Message-Passing GNNs

Spatial message-passing decompositions place scalar degree and scaler terms in Pk, form pairwise channel contributions before mixing, and leave selection, routing, and readout machinery external unless shown.The table marks covered slices for one JKNet base layer and the Graph Network node update.Source: Table 14 · p. 106, §D.1 · p. 106

Family 2: Attention-Based GNNs

Attention decompositions assign scalar attention weights to Pk, edge-conditioned values to Ψk, and node-wise gates or residuals to the update, with pairwise aggregation before head or branch mixing.DAGNN† reports one update in its sequential topological scan.Source: Table 15 · p. 109
GraphHyperConv’s whole-neighborhood generated mixer is not one endpoint-local pairwise-message channel, while NLGNN’s hard sorting and sequence convolution form a multi-stage operator.For NLGNN, score sorting alone does not imply failure of relabeling equivariance; tied scores require an equivariant tie rule.Source: §D.1 · p. 111
GPNN’s pointer, convolution, and pooling pipeline is not one declared channel contribution, and its BFS enumeration, truncation, and LSTM pointer are generally sequence-order-sensitive.The method selects an ordered subsequence from a sampled multi-hop neighborhood and produces a non-local vector.Source: §D.1 · p. 111

Family 3: Spectral, Diffusion, and Compatibility-Aware Graph Operators

Spectral and channel coefficients are absorbed into Pk, while restart and residual terms remain in the update; pairwise aggregation precedes cross-channel mixing.Rows marked † report source-supported slices of signal-dependent, recurrent, selected, or composite operators without imposing a false fixed factorization.Source: Table 16 · p. 111

P GRUh(P )

This section applies the common-component framework to graph Transformers and heterogeneous, higher-order/subgraph, and geometric GNNs, distinguishing communication patterns, token or relation channels, attention normalization, lifted domains, message fusion, and symmetry structure. It also marks where token construction, sequence processing, or training control flow falls outside a single synchronous layer, and distinguishes fixed layer fillings from architecture-search or component-level cases.

3c Compatibility-aware / non-smoothing (heterophily) channels

Compatibility-aware channels represent heterophily through signed or high-pass responses, learned compatibility, or state-dependent support.Examples listed include H2GCN, FAGCN, RFA-GNN, ACM-GCN, GGCN, EvenNet, CPGNN, and BM-GCN.Source: P GRUh(P ) · p. 115

4b Hybrid local + global communication

Hybrid local and global communication can fuse, sequence, or co-train local and global branches.The table flags these alternatives as distinct compositions.Source: Table 17 · p. 118

4c Scalable / sparse-global attention

Scalable or sparse-global attention restricts global coupling through kernelization, expander sparsity, energy constraints, or hubs and landmarks.These are alternative sparse-global attention mechanisms in the graph Transformer family.Source: Table 17 · p. 118, P GRUh(P ) · p. 120

4d Tokenized: typed axis T with learned mix

Tokenized Transformer layers use a typed token axis and learn a mix over tokens constructed or sampled by the paper’s method.The decomposition assigns the learned token-axis mix to the layer while treating token construction separately.Source: Table 17 · p. 118, P GRUh(P ) · p. 121
GQT and SwapGT’s defining sequence constructors and associated control flow do not fit within one seven-component synchronous layer.GQT uses an ordered top-k PPR sequence constructor; SwapGT uses top-k token sampling and stochastic token swapping before readout.Source: P GRUh(P ) · p. 122
NeuralWalker’s stochastic walk-token constructor and ordered sequence mixer mark the named Family 4 boundary; Spexphormer’s learned sparsification is a two-stage training process outside one synchronous layer.NeuralWalker’s walk tokens are occurrence-averaged back to nodes, while Spexphormer trains a score estimator, samples a sparse graph per layer, then trains the wide model.Source: P GRUh(P ) · p. 122

5 Heterogeneous and Multi-Relational GNNs

Heterogeneous and multi-relational layers use relation types, meta-paths, or typed heads as channels, with supports and attention scores in Pk and typed projections or composed values in Ψk.Mixing combines completed relation or head contributions, and nonlinear selection is represented directly rather than forced into a fixed matrix product.Source: Table 18 · p. 122

5b Meta-path supports

Meta-path-support channels may use learned or fixed meta-paths, followed by semantic-level mixing.The table’s examples include HAN, MAGNN, GTN, FastGTN, SeHGNN, and HPN.Source: Table 18 · p. 122, P GRUh(P ) · p. 123

Heterogeneous GNNs

HetSANN jointly softmaxes over incoming typed edges including self-loops, whereas ie-HGCN combines row normalization without added self-loops with type-level softmax including self.These examples distinguish edge-level from type-level attention normalization.Source: P GRUh(P ) · p. 124
HetGNN uses type-grouped RWR selection with BiLSTM sets, while HINormer applies a partial sampled-token slice on fixed sampled context.HetGNN's selected support is not a fixed linear support.Source: P GRUh(P ) · p. 125

Outside the PkΨk template

H2G-former is described as a component-level HGT modification, while MR-GNAS searches a relation-aware supernet rather than specifying a single fixed layer equation.H2G-former replaces 1-hop attention with a k-hop mask and adds masked-label encoding and a type-specific FFN; MR-GNAS is listed as outside the template's fixed-layer boundary.Source: P GRUh(P ) · p. 125

Family 6. Higher-Order and Subgraph GNNs

Higher-order and subgraph GNNs lift X to tuples, subsets, rooted subgraphs, bags, or cells, aggregating within objects before cross-channel mixing.Some use transient lifted routing while persistent state stays on nodes; pooling, sampling, and readout may remain external.Source: Table 19 · p. 126

Family 7. Geometric and Equivariant GNNs

Geometric layers place geometric context in X and fuse typed channel contributions by tuples, direct sums, or concatenation, preserving source-established symmetry groups.The family includes coordinate-, distance-, angle-, vector-, tensor-, and algebra-valued layers.Source: Table 20 · p. 129, P GRUh(P ) · p. 130