PaperlayerView exact revision on arXiv

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.16097v1cs.LG

TL;DR

Graph neural network architectures have multiplied faster than the language used to compare their computations. This paper introduces a seven-component common layer equation with checkable reductions and uses it to organize architectural variation, derive component-level conclusions, and define coverage boundaries.

  • Problem

    Family-specific equations and notation make the hundreds of graph neural network architectures difficult to compare and can conflate changes in support, transmitted values, mixing, and updating.

  • Method

    The paper represents covered graph neural layers with seven components and function-valued fillings, separating information movement through propagation banks from transmitted values through message maps.

  • Results

    The framework provides checkable reductions of canonical layers, spans seven architectural families, and shows that operator support bounds one-layer dependencies under endpoint-local messages and node-local updates.

  • Takeaways & Limitations

    The decomposition supports component-wise comparison and structurally consistent architecture generation while connecting propagation choices to oversmoothing, oversquashing, heterophily, and expressivity.

  • Takeaways & Limitations

    The coverage boundary excludes several cases involving non-commutative walk mixing, feature-dependent reindexing, sampled sequence processing, search spaces rather than layers, and relation-specific knowledge-graph operations.

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 unifies fragmented GNN layer descriptions through seven computational components, separating information movement from transmitted values. This shared representation supports comparison, coverage analysis, architecture generation, and component-level theoretical results.

  • Motivation: Family-specific GNN notation obscures shared computations and makes architectural comparisons difficult across hundreds of designs.Existing abstractions do not uniformly factor support and weighting from transmitted values.
  • Unified representation: The common layer uses seven components: update domain, channel set, propagation bank, message maps, mixing operator, ego/residual map, and update map.The propagation bank specifies where information moves, while message maps specify what moves.
  • Unified representation: A fixed slot discipline assigns operations by computational role, making component-wise comparisons meaningful despite equivalent factorizations.The framework also names a coverage boundary based on matrix linear-value channels or invariant pairwise-message aggregation.
  • Taxonomy: The framework organizes more than 200 architectures into seven nonexclusive, component-anchored families.Families primarily vary propagation, channels, update domains, or geometric message and update maps, and hybrids may occupy multiple families.
  • Consequences: Component exposure yields theoretical results on dependency support, global mixing, channel identifiability, and relationships to oversmoothing, oversquashing, heterophily, and expressivity.Under stated locality assumptions, propagation support bounds one-layer dependencies, while one-layer global mixing requires a full effective operator row.
  • Consequences: The component inventory supports structurally consistent architecture generation, but selecting the best fillings remains an empirical inverse problem.The surrounding system’s training loss, task pipeline, deployment system, and several temporal or generative mechanisms remain outside the formal layer scope.

2 Preliminaries

The preliminaries establish graph, feature, propagation, task, and symmetry notation for interpreting the unified layer. They distinguish spatial and spectral views while motivating propagation choices through sparsity, homophily, and expressivity constraints.

  • Graph notation: A graph G=(V,E) contains nodes and relations, with adjacency and degree matrices encoding connectivity and aggregation structure.Graphs may be directed or undirected, and weighted or unweighted.
  • Propagation operators: Self-loop normalization produces ˆA, while the symmetric normalized Laplacian Lsym defines the default spectral basis and filtering language.The reference propagation Laplacian for self-loop-normalized support is distinguished from Lsym.
  • Computational setting: Real-world graph sparsity makes local message passing tractable, whereas all-pairs graph Transformer attention often requires sparsification or kernelization.Sparse graphs satisfy m ≪ n^2 in the stated setting.
  • Representations: Node features are stored in X, hidden states evolve from H(0)=X, and a GNN layer transforms H(ℓ) into H(ℓ+1) through feature transformation and graph propagation.The update domain can generalize beyond nodes to tuples, subgraphs, simplices, cells, or motifs.
  • Graph structure: Homophily and heterophily describe whether connected nodes tend to share or differ in attributes or labels, affecting which propagation operators perform well.Standard propagation implicitly assumes homophily and can degrade when it is absent.
  • Unified layer view: The unified layer treats ⊞ as channel mixing and represents each channel through either a matrix product or aggregated per-edge messages.Four families primarily specialize Pk, while other families vary channels, domains, or message and update maps.
  • Expressivity: Equivariant message passing is no more powerful than 1-WL for distinguishing non-isomorphic graphs, motivating higher-order refinements.The paper develops this expressivity ceiling alongside substructure-counting and higher-order results.

3 The Unified Layer Equation for Graph Neural Networks

The unified layer equation represents covered graph neural layers through seven components, separating propagation support and weights from transmitted messages. A fixed slot discipline makes architectural differences checkable while exposing coverage boundaries, theoretical invariants, and canonical reductions.

  • Unified equation: The seven components are the update domain X, channel set K, propagation bank {P_k}, message maps {Ψ_k}, mixing operator ⊞, ego/residual map B_ℓ, and update map ϕ_ℓ.The pipeline specifies updated objects, channel branches, transmitted values, propagation locations and weights, channel combination, residual input, and state update.
  • Theoretical consequences: Under endpoint-local messages and node-local updates, the union of propagation supports bounds one-layer dependencies; changing other slots cannot create dependence outside that support.Under the stated hypotheses, one-layer global mixing requires a full effective operator row.
  • Coverage boundary: The framework covers matrix linear-value and pairwise-message channels, but five named cases fall outside the stated primitives and alternative representations require additional primitives.The boundary includes non-commutative walk mixing, learned sorting or sequence processing, search spaces, and static triple-scoring embeddings.
  • Slot discipline: A fixed slot discipline assigns scalar edge and channel weights to P_k, vector- or matrix-valued messages to Ψ_k, channel combination to ⊞, ego inputs to B_ℓ, and updating to ϕ_ℓ.The convention makes component-wise comparisons meaningful despite equivalent factorizations, but normalized placements remain convention-dependent.
  • Theoretical consequences: In the linear additive regime, raw channel count is not identifiable because channels can split or cancel without changing the layer function; minimum Kronecker separation rank is the invariant.The relevant rank may be constrained by support or equivariance requirements.
  • Unified equation: The central factorization separates where information moves, encoded by P_k, from what moves, encoded by Ψ_k, while ⊞, B_ℓ, and ϕ_ℓ handle mixing and updating.The separation makes spectral, spatial, attention, and multi-hop layers directly comparable.
  • Canonical reductions: Worked reductions recover canonical layers including GCN, GraphSAGE, GAT, and GIN by assigning their propagation, message, ego, mixing, and update choices to the slots.GCN uses fixed normalized adjacency, while GAT uses learned state-dependent scalar weights and GIN places the self term inside the MLP input.

4 Generated Architectures from the Unified Equation

The unified equation supports three levels of architecture generation: recombining existing fillers, introducing new fillers, and extending the schema with typed components. Generated layers are audited against structural conditions, and six architectures survive the procedure.

  • Generation levels: Level 1 recombines compatible existing fillers across families while keeping the equation and inventory fixed.It is the only level described as neural architecture search because it selects from a finite inventory.
  • Generation procedure: The controller proposes functional forms using the unified equation, slot definitions, admissible inventory, and level-specific constraints, then audits type, symmetry, dimensional, inventory, and reduction conditions.Only proposals passing the checks are retained and recorded with their closest existing method and differing component.
  • Generated results: Six generated architectures survive the audit: five at Levels 1–2 and one Sequential Co-Lifted Node–Edge Layer at Level 3.Together they instantiate all three generation levels.
  • Generation levels: Level 2 replaces one existing slot filling with a new admissible filler without changing the seven-component inventory.The new filler must respect the slot type and avoid reducing to an existing method.
  • Generation levels: Level 3 adds a typed computational component, preserving permutation equivariance and recovering the base equation when the added slot is removed.The Sequential Co-Lifted Node–Edge Layer adds an execution schedule that orders edge and node updates.
  • Generated examples: Spectrally-Gated Propagation replaces a fixed per-order coefficient with a node-adaptive coefficient, producing spatially modulated polynomial propagation.The resulting operator is not generally a scalar spectral multiplier with a globally defined passband because the gate need not commute with the polynomial operator.

5 GNN Propagation: Limits, Expressivity, and Remedies

The propagation analysis localizes oversmoothing, oversquashing, heterophily, and expressivity limits within the unified layer, while identifying remedies and assumptions that qualify them. It shows that propagation spectra and topology constrain information flow, but architecture-specific choices can preserve or reshape informative signals.

  • Oversmoothing: Repeated propagation suppresses non-dominant spectral components, causing node features to collapse toward the degree-dominated subspace when ¯sµ⋆<1.The collapse is exponential with depth and independent of labels.
  • Oversmoothing: State-dependent attention can still oversmooth through joint-product contraction under connectivity, non-bipartiteness, positivity, and boundedness assumptions.The contraction factor is the joint spectral radius of the changing operator sequence.
  • Oversmoothing: Residuals, initial-residual teleportation, multiple operators, and weight normalization can slow or alter collapse, but their benefits remain distribution-, mechanism-, or diagnostic-dependent.Rank may reveal degradation more faithfully than Dirichlet energy, while finite aggregation depth can improve learning before eventual collapse.
  • Oversquashing: Local propagation expands receptive fields with depth, but distant signals crossing narrow topological bottlenecks become compressed, producing oversquashing and quantitative capacity limits.Nodes beyond L hops cannot interact under the stated local-support assumptions.
  • Heterophily: Repeated normalized propagation suppresses non-dominant components, so fixed low-pass filters may remove heterophilous signal even while favoring low-frequency discrimination.Polynomial channels can realize low-pass, band-pass, or high-pass responses, including high-pass configurations that retain designated high-frequency components.
  • Heterophily: Sheaf-based operators can preserve nonconstant signals and increase the number of linearly separable limiting classes with stalk dimension, addressing heterophily and oversmoothing jointly.This conclusion applies to the analyzed non-trivial sheaf constructions.
  • Trade-offs: Changing the operator spectrum or topology affects oversmoothing and oversquashing through a conductance-linked trade-off rather than independently improving both under the stated operator family and assumptions.The result is not an impossibility theorem for all fixed-topology architectures or interventions.

6 Benchmark Properties in the Component Vocabulary

Benchmark evidence can be translated into the component vocabulary, but protocol validity and interacting components constrain what such evidence can establish.

  • Interpretation: Benchmark properties identify potentially relevant components without isolating propagation from features, messages, updates, or evaluation choices.The translation is descriptive and does not attribute performance to a single component.
  • Benchmark findings: Industrial and temporal benchmarks show that realistic temporal or inductive shifts can substantially reduce performance, while simple baselines may remain strong.GraphLand reports strong graph-augmented tree baselines, and TGB findings include simple methods outperforming temporal graph models on some dynamic tasks.
  • Protocol validity: Protocol validity precedes component attribution because splits, duplicates, normalization, metrics, and tuning can change apparent architectural gaps.These factors can reverse rankings, invalidate comparisons, or substantially reduce reported differences.
  • Evaluation design: Controlled datasets can vary connectivity while holding other factors fixed, whereas realistic benchmarks combine multiple sources of variation.LRGB suggests long-range dependence but does not claim a provable long-range requirement.
  • Evaluation design: Equal-resource benchmarking and best-attainable performance are distinct targets, and tuned conventional models can match or exceed recent Graph Transformers on 17 of 18 node-classification datasets.The 17-of-18 result concerns the datasets studied by Luo et al. (2024b).
  • Component translation: Benchmark properties generally map many-to-many onto components, so the decomposition identifies interacting component sets while separating external evaluation choices.Long-range, heterophilous, and temporal tasks can involve multiple layer components and downstream or protocol factors.

7 Open Problems and Challenges

The paper frames open problems around selecting, scaling, and extending component fillings while preserving valid attribution, efficiency, transfer, and trustworthy evaluation.

  • Search and selection: No validated, causal map currently connects measurable graph or task properties to component choices that generalize under distribution shift.Existing architecture search remains empirical, dataset-specific, and vulnerable to non-causal correlations.
  • Propagation scaling: Scaling propagation raises an expressivity–efficiency problem at Pk, with no universal sparsifier or method dominating the accuracy–efficiency frontier.A reported global-convolution result achieves a 169× speedup on a two-million-node synthetic graph, but its sacrificed expressivity is not characterized.
  • Foundation models: Foundation-model development requires primitives that transfer across feature- and structure-heterogeneous graphs, alongside scalable pre-training and trustworthy evaluation.Current unified text-attributed spaces cover only classification on text-rich graphs.
  • Trustworthy graph learning: Propagation entangles privacy, robustness, fairness, uncertainty, and accuracy because sensitive attributes, perturbations, and structural bias travel through the same operator.A single adversarial edge can affect an entire receptive field, while heterophily may amplify or mask effects.
  • Geometric learning: Geometric GNNs face an expressivity–scalability–symmetry trade-off, and exact equivariance cannot distinguish symmetry-equivalent outcomes.Learnable relaxation is identified as one candidate approach, while task alignment determines when equivariance helps in matched-capacity settings.
  • Personalization: Personalization needs user-conditioned Pk and Ψk that remain effective under sparsity and preference drift while supporting personalized generation.Shared operators with static user embeddings struggle with cold starts, drift, and non-stationary inputs.
  • Language agents: Task-conditioned communication graphs require principled topology selection and credit assignment, but current approaches remain empirical and lack an expressivity account for language-message routing.The proposed target is a task-conditioned Pk and Ψk over an operation domain X.
  • Evaluation: Evaluation must isolate individual fillings while preserving realistic data and equal tuning effort, because current benchmarks can overrepresent small molecules and marginal accuracy.The paper separates protocol validity, fair comparison, and component attribution as distinct requirements.

8 Conclusion

The paper unifies graph neural layers with seven components and uses the resulting factorization for comparison and analysis. It concludes that selecting suitable fillings remains an empirical inverse problem requiring controlled evidence and robust descriptors.

  • Unified representation: The framework represents covered graph neural layers through an update domain, channel set, propagation bank, message maps, mixing operator, ego/residual map, and update map.Function-valued fillings span local, attention, spectral, global, relational, higher-order, and geometric architectures.
  • Comparison framework: A fixed slot discipline makes component assignments comparable despite equivalent factorizations and preserves differences in architectural roles.Functional equivalence can still depend on internal mechanisms and component interactions beyond the displayed granularity.
  • Component-level analysis: Operator support bounds one-layer dependencies under endpoint-local messages and node-local updates, while one-layer global mixing requires a necessary full effective operator row.In the linear additive regime, raw channel count is non-identifiable but minimum Kronecker channel rank is invariant.
  • Open direction: Choosing the best filling for a dataset remains an empirical inverse problem requiring controlled evidence and robust descriptors because common statistics such as homophily are fragile.The unified equation and comparison tables provide a shared language for pursuing this problem.

Appendix A Notation

Appendix A defines the standard graph, spectral, feature, label, and learning notation alongside the seven-component unified layer vocabulary. It also records how domains, channels, propagation, messages, fusion, ego states, updates, pooling, and readouts fit together.

  • Notation: Table 10 separates standard graph and spectral symbols from the unified layer-slot notation of Eq. (3).Part I covers graph objects, matrices, spectral quantities, features, and learning conventions; Part II covers the unified layer slots.
  • Graph objects: Graph notation includes nodes V, edges E, adjacency A, degree matrix D, neighborhoods N(v), and node and edge counts n and m.The notation also distinguishes self-loop-augmented and normalized adjacency matrices.
  • Spectral quantities: Spectral notation defines Laplacians, eigenbases, eigenvalues, graph Fourier transforms, and polynomial filters used for frequency-domain propagation.The normalized Laplacian Lsym and its eigendecomposition support graph-frequency analysis, while degree-K polynomial filters avoid eigendecomposition and localize to K-hop neighborhoods.
  • Unified layer slots: The unified layer updates a domain X through channels K, propagation operators Pk, message maps Ψk, fusion ⊞, ego map Bℓ, and update map ϕℓ.The pipeline constructs channel messages, propagates them, fuses contributions, carries the ego or residual state, and produces the new state.
  • Extensions: Higher-order and geometric models generalize the update domain beyond nodes, while positional encodings enter the message map or external initial state without creating a new slot.The domain may index tuples, subgraphs, simplices, cells, or motifs; geometric features may be scalar, vector, or tensor valued.

B.2 Graph Rewiring and Virtual Nodes

Graph rewiring changes the communication operator to address structural bottlenecks, while virtual nodes provide a global communication route under suitable conditions. Residuals, normalization, and related operations are assigned to specific unified-layer slots, with composition constrained when edits share a slot.

  • Rewiring: Rewiring changes which nodes communicate and with what weights by modifying propagation support or scalar coefficients.It may be static preprocessing or dynamic per-layer modification, and can also change the domain when new nodes are added.
  • Virtual nodes: A virtual node opens a global communication channel, but information reaches another node after two synchronous layers unless the virtual state was already aggregated.Under suitable depth, width, and update capacity, it can simulate global interaction, but one token is not generally equivalent to arbitrary pairwise attention.
  • Caveats: Rewiring is justified by a diagnosed bottleneck because it can trade improved information flow against faithfulness to the input topology.Removing edges without connectivity safeguards can disconnect components or isolate nodes.
  • Residuals: Residual connections primarily edit Bℓ, preserve earlier states, and can counter vanishing signals and oversmoothing in deep propagation.Initial residuals anchor each node away from the degree-dominated limit, while reversible residuals trade recomputation for memory.
  • Composition: Operations sharing a primary component require explicit reconciliation rather than independent composition.Both residual schemes write Bℓ, while virtual nodes, rewiring, and sampling act on {Pk}; different primary locations provide only prima facie compatibility.
  • Normalization: Normalization usually belongs to ϕℓ, but pre-normalization can make Pk and Ψk state-dependent; cross-node normalization requires the generalized equivariant update assumptions.Row-wise results do not automatically extend to PairNorm, GraphNorm, or other normalizations coupling node rows.

B.6 Continuous-Depth and ODE Views

Continuous-depth views reinterpret residual layers as discretized dynamical systems, with propagation operators supplying the vector field and the integrator determining depth evolution. The catalog distinguishes this narrow reinterpretation from augmented dynamics and from training-time sampling operations.

  • ODE interpretation: A residual update H(ℓ+1) = H(ℓ) + h f(H(ℓ)) is an explicit Euler step for the ODE Ḣ(t) = f(H(t)).The standard residual corresponds to unit step size h = 1, while depth becomes integration time.
  • Slot assignment: In the narrow continuous-depth reinterpretation, the propagation bank supplies the right-hand-side dynamics and only the integrator changes.This is why the paper classifies the reinterpretation as an operation on ϕℓ rather than as a new family.
  • Augmented dynamics: Augmented dynamics enlarge the per-object state, such as by appending velocity, and may modify Ψk, Pk, or ϕℓ without changing the domain X.Such cases are classified as broader multi-slot edits rather than the narrow integrator reinterpretation.
  • Examples: Diffusion-based models integrate graph diffusion as heat-flow smoothing, whereas oscillator-based models add second-order terms to avoid collapse to the diffusion fixed point.The oscillator construction is described as a continuous-depth response to oversmoothing.
  • Scope caveat: The paper does not claim equivalence in expressiveness or stability between continuous-depth models and discrete counterparts.Those properties depend on the specific vector field and integrator, and the operation-versus-family classification is explicitly a modeling choice here.
  • Sampling: Sampling restricts where {Pk} is evaluated without changing the layer’s functional form, so it remains a training-time operation rather than a generation move.Node-wise, layer-wise, and subgraph sampling trade exact propagation for tractable memory and runtime; reweighting can yield an unbiased estimate of full propagation.

Appendix C Theoretical Analysis

Appendix C analyzes how the unified slots constrain layer equivalence, global mixing, spectral filtering, expressivity, aggregation, and permutation symmetry. Its results are stated under explicit linear, graph, locality, and equivariance assumptions, making design consequences traceable to particular components.

  • Identifiability: The decomposition makes channel rank identifiable even though raw channel count is not identifiable in the linear regime.This is one of the central consequences of exposing the propagation bank and channel decomposition.
  • Oversmoothing: Initial residuals and spectral fillings provide distinct slot-level mechanisms for escaping oversmoothing.The initial-residual iteration converges to a personalized-PageRank fixed point whose energy remains above a fraction of anchor energy under the stated assumptions.
  • Global mixing: A single layer needs a full effective operator row to mix all other nodes under endpoint-local messages and node-local updates.A dense operator or suitable rewiring can satisfy this condition, whereas a virtual node generally needs two layers.
  • Spectral filtering: Polynomial filters of degree at most q −1 can realize any frequency response over q distinct eigenvalues of the propagation operator.When the operator has distinct eigenvalues and the signal misses no frequency, such filters reach every vector in R^n.
  • Heterophily: A high-pass response that zeros the smoothing direction can retain class signal carried by a discriminative high-frequency band under heterophily.The result applies when the corresponding response is realizable inside Pk; the band need not contain all class signal.
  • Expressivity: A node-domain stack with no identifiers and restricted one-hop operators is bounded by 1-WL, while domain, message, or structure-aware operator mechanisms can lift that ceiling.The proposition restricts the update, fusion, and readout to isolate the listed escape mechanisms.
  • Aggregation: Injective neighbor-sum aggregation combined with an injective root-state merge attains the 1-WL ceiling, whereas mean and max aggregation cannot be made injective.The raw sum alone is not injective on multisets, and injective neighbor aggregation alone does not suffice.
  • Permutation symmetry: Equivariant operators, messages, mixing, ego maps, updates, and optional pooling yield an equivariant stack and an invariant graph function with invariant readout.The theorem includes shared row-wise and pairwise specializations.

C.1 Subsumption: families as slot choices

The framework recovers named spectral and attention architectures as specific fillings of propagation and message components, while exposing non-identifiability in channel decompositions.

  • Spectral and attention subsumption: Named spectral and attention models are exact fillings of Pk and Ψk within the linear specialization.The factorization assigns attention weights to Pk and transmitted values to Ψk.
  • Spectral and attention subsumption: ChebNet, SGC, GPR-GNN, BernNet, and APPNP are recovered by substituting their defining propagation choices into Pk.These substitutions reproduce each model’s own layer equation without relabeling beyond component names.
  • Mixing and identifiability: Concatenation is represented as additive channel mixing, with each block supported on a disjoint feature partition.The same mixing interpretation extends to multi-head channels.
  • Mixing and identifiability: GAT and GATv2 differ within the factorization through the functional form of the state-dependent entries in P1.Edge features can instead enter Ψ1, or both components, depending on whether they modify scores or transmitted values.
  • Mixing and identifiability: The number of channels is not identifiable in the linear regime because decompositions with the same summed operator define the same function.Splitting terms or adding canceling pairs changes K without changing the layer map; minimum Kronecker channel rank remains well defined.

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

Under local-message and node-local-update assumptions, propagation support determines one-layer dependency locality; one-layer global mixing requires every off-diagonal position in the effective operator row.

  • Locality: Under endpoint-local messages and node-local updates, the union of supports of {Pk} fixes the support-level envelope of one-layer dependencies.Changing Ψk, ⊞, Bℓ, or ϕℓ alone cannot create dependence outside that support.
  • Locality: Local computation bounds an L-layer receptive field to the L-hop neighborhood.The induction relies on endpoint-local messages and propagation restricted to one-hop support.
  • Globality: A single fixed-operator layer can mix every other node only if each off-diagonal entry of the target row is nonzero in at least one channel.The necessity follows because node-local ego and update maps add no cross-node dependence.
  • Globality: Generically, a full off-diagonal row is also sufficient when the update is message-faithful, apart from exceptional channel cancellations.The claim assumes fixed operators and node-wise messages; state-dependent operators introduce additional derivative paths.
  • Globality: Return probabilities appear as structural diagonal self-weights in multi-hop propagation operators such as normalized powers of the self-loop adjacency.The diagonal entry equals the corresponding k-step return probability of the self-loop random walk.

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

The framework connects smoothing and its escape mechanisms to the spectral response of Pk and the initial residual term Bℓ, including realizable high-frequency responses for heterophilic signals.

  • Smoothing: Repeated low-pass propagation contracts Dirichlet energy and drives representations toward a degree-dominated subspace.The layerwise bound is E(H(L)) ≤ (s̄ μ⋆)^(2L) E(H(0)).
  • Smoothing escapes: The ego/residual map Bℓ can preserve energy above a fixed floor through the initial residual.The associated affine propagation is a contraction with a unique fixed point under the stated conditions.
  • Spectral filtering: Spectral fillings of Pk can realize arbitrary responses across distinct eigenvalues using polynomials of degree at most q − 1.Interpolation supplies the required polynomial coefficients.
  • Heterophily: A high-pass response can assign zero weight to the smoothing direction ν = 1 while retaining nonzero responses on discriminative high-frequency components.This realizes a heterophilic configuration when class-discriminative signal is carried by those eigenvectors.
  • Spectral filtering: Under a distinct-spectrum hypothesis, polynomial filters can map any input with nonzero spectral coefficients to every coefficient vector in R^n.The Vandermonde system makes the spectral responses independently selectable.

C.4 Expressivity boundary and symmetry

The framework places expressivity and symmetry boundaries on specific components: structure-blind node-domain stacks remain bounded by 1-WL, while equivariance requires coordinated transformations across all slots.

  • Expressivity: A structure-blind node-domain stack cannot exceed the 1-WL ceiling under the stated refinability assumptions.The ceiling can be exceeded by lifting the domain, enriching initial features, or making Pk depend on structure beyond incident colors.
  • Symmetry: Permutation equivariance requires consistent relabeling of domains and channels, equivariant Pk and Ψk, and permutation-commuting ⊞, Bℓ, and ϕℓ.Shared row maps are sufficient for some map-valued components but are not necessary for the full equation.
  • Expressivity: A triangle-count-weighted one-hop operator separates the triangular prism K3 □ K2 from K3,3 despite their identical 1-WL color histograms.The operator is nonzero on prism triangle edges and vanishes on the triangle-free bipartite graph.
  • Expressivity: Matching 1-WL requires injective neighbor aggregation together with an injective root–aggregate update.The framework represents these roles through the message/channel construction, separate ego term Bℓ, and injective ϕℓ.
  • Component attribution: The decomposition expresses theoretical results through component roles rather than named architectures alone.Subsumption, locality, smoothing, expressivity, and equivariance are each attributed to particular slots or interactions among them.

D.1 Assignment rules for primary families

Primary family assignment places each method in the family whose dominant mechanism best describes its cited layer update, while recording other mechanisms as cross-references or boundary notes. The component tables distinguish how spatial, attention, spectral, and out-of-template methods fit the declared comparison scheme.

  • Primary family assignment follows the dominant mechanism of the cited layer update, with other mechanisms recorded as cross-references or boundary notes.
  • Family 1. Spatial Message-Passing GNNs: Spatial message-passing decompositions treat neighbor aggregation as pairwise channel contributions before mixing, with degree and scaling terms absorbed into Pk.
  • Family 2. Attention-Based GNNs: Attention-based decompositions place scalar attention weights in Pk, edge-conditioned values in Ψk, and node-wise gates or residuals in the update.
  • Coverage boundary: Several listed architectures remain outside the single-stage channel template because they use whole-neighborhood mixers, sequence routing, or multi-stage control flow.Examples include GraphHyperConv's whole-neighborhood mixer and NLGNN's hard reindexing followed by sequence convolution.
  • Family 3. Spectral, Diffusion, and Compatibility-Aware Graph Operators: Spectral, diffusion, and compatibility-aware decompositions absorb spectral or channel coefficients into Pk while retaining restart and residual terms in the update.

P GRUh(P )

The family tables extend the component assignment scheme across global, tokenized, heterogeneous, and geometric architectures while marking methods that do not reduce to one synchronous layer. The coverage boundary is explicit for search procedures, staged pipelines, stochastic token constructors, and ordered sequence mixers.

  • Family 4. Graph Transformers: Graph Transformer decompositions assign attention to Pk, structural biases to attention scores, input encodings to X, and head or branch fusion to ⊞.Pair-dependent values retain their explicit neighbor contraction, while typed token axes can record learned mixing.
  • Coverage boundary: NeuralWalker falls outside the spine because its stochastic walk constructor and ordered sequence mixer do not reduce to fixed matrix powers or a synchronous seven-component layer.Optional local or global message-passing blocks refine the tokenized representation afterward.
  • Family 5. Heterogeneous and Multi-Relational GNNs: Heterogeneous and multi-relational decompositions index channels by relation types, meta-paths, or typed heads, assigning scalar supports to Pk and typed values to Ψk.Mixing combines completed relation or head contributions, while nonlinear selection is shown directly rather than forced into a fixed matrix product.
  • Coverage boundary: Architecture search and multi-stage pipelines are listed for coverage rather than treated as ordinary fillings of one fixed closed-form layer.MR-GNAS searches relation-aware cells, while Spexphormer trains a score estimator before sampling a sparse graph and training the wide model.
Loading 2608.16097v1…