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

cs.LGAug 17, 2026

Unifying Graph Neural Networks Through a Common Layer Equation

Authors: Sai Karthik Navuluru, Siddhartha Shankar Das, Bo Ni, Hongjie Chen, Yu Wang, Baris Coskunuzer, Nesreen K. Ahmed, Franck Dernoncourt,

Organizations: University of Texas at Dallas · Pacific Northwest National Laboratory · Vanderbilt University · Dolby Laboratories ·

Abstract

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.

Figures & tables

Figure 1: Our unified GNN design space. We organize seven previously fragmented architectural families around one common layer. Read the figure from left to right: family-specific formulations are translated into seven shared components: the update domain $\mathcal{X}$ , channel set $\mathcal{K}$ , propagation bank $\{\mathbf{P}_{k}\}$ , message maps $\{\Psi_{k}\}$ , mixing operator $\boxplus$ , ego/residual map $\mathcal{B}_{\ell}$ , and update map $\phi_{\ell}$ . They then become directly comparable and recombinable. The key split is intuitive: $\mathbf{P}_{k}$ specifies where information moves, while $\Psi_{k}$ specifies what moves.

Method	$\bm{\mathcal{X}}$	$\bm{\mathcal{K}}$	Propagation $\bm{\mathbf{P}_{k}^{(\ell)}}$	Message $\bm{\Psi_{k}^{(\ell)}}$	Mixing $\bm{\boxplus^{(\ell)}}$	Ego/Update $\bm{(\mathcal{B}_{\ell},\phi_{\ell})}$
1 Spatial local support in $\mathbf{P}_{k}$ with differences in aggregation and ego/update
GCN Kipf and Welling ( 2017 )	$V$	$\{1\}$	$\hat{\mathbf{A}}$	$\mathbf{H}^{(\ell)}\mathbf{W}^{(\ell)}$	$\mathbf{P}_{1}\Psi_{1}$	$\sigma(\widetilde{\mathbf{H}}^{(\ell)})$
GraphSAGE- Mean Hamilton et al. ( 2017 )	$V$	$\{1\}$	$\mathbf{D}^{-1}\mathbf{A}$	$\mathbf{H}^{(\ell)}$	$\mathbf{P}_{1}\Psi_{1}$	$\operatorname{norm}(\sigma([\mathbf{H}^{(\ell)}\\|$ $\widetilde{\mathbf{H}}^{(\ell)}]\mathbf{W}^{(\ell)}))$
GIN Xu et al. ( 2019b )	$V$	$\{1\}$	$\mathbf{A}$	$\mathbf{H}^{(\ell)}$	$\mathbf{P}_{1}\Psi_{1}$	$\MLP^{(\ell)}((1{+}\epsilon_{\ell})\mathbf{H}^{(\ell)}{+}$ $\widetilde{\mathbf{H}}^{(\ell)})$
2 Attention state-dependent $\alpha_{ij}(\mathbf{H}^{(\ell)})$ in $\mathbf{P}_{k}$
GAT Veličković et al. ( 2018 )	$V$	$\{1,\dots,M\}$	$\operatorname{softmax}_{j\in\widetilde{\mathcal{N}}(i)}\!\big($ $\operatorname{LReLU}([{\bm{h}}_{i}\mathbf{W}_{m}\\|$ ${\bm{h}}_{j}\mathbf{W}_{m}]\mathbf{a}_{m})\big)$	$\mathbf{H}^{(\ell)}\mathbf{W}_{m}^{(\ell)}$	$\mathbf{C}_{m}=\mathbf{P}_{m}\Psi_{m};$ $\widetilde{\mathbf{H}}=\\|_{m}\mathbf{C}_{m}$ (avg. at final layer)	$\mathcal{B}_{\ell}=0;$ $\sigma(\widetilde{\mathbf{H}}^{(\ell)})$

Table 1: Our seven-family taxonomy expressed in one common layer. Each colored band is one family, and its three anchor methods show how familiar architectures fill the same seven components. Read each row from left to right: what objects are updated (

\mathcal{X}

), which channels are used (

\mathcal{K}

), where information moves (

\mathbf{P}_{k}

), what information moves (

\Psi_{k}

), how channel contributions are combined (

\boxplus

), and how the result updates the state (

(\mathcal{B}_{\ell},\phi_{\ell})

). The six displayed columns combine the distinct ego/residual and update maps in the final Ego/Update column. Full source-grounded decompositions and conventions appear in Table 14 –Table 20 and Sections 3.2 – 3.6 . Here

\mathrm{cg}

denotes the Clebsch–Gordan tensor product.

Formalism	Canonical computational objects	Not separately exposed	Exact relation or boundary
MPNN ( Gilmer et al., 2017 )	Node states, a pairwise message $M_{\ell}(h_{i},h_{j},e_{ij})$ , summation over neighbors, a node update $U_{\ell}$ , and a graph-level readout $R$	The canonical equations expose a single neighbor-aggregated message $m_{i}=\sum_{j\in\mathcal{N}(i)}M_{\ell}(\cdot)$ . They do not separately expose a channel index set, a decomposition of propagation support from message values, a distinct cross-channel mixing operator, or an independently named ego/residual construction	Exact node-domain specialization of the pairwise branch with $\mathcal{K}=\{1\}$ , $[\mathbf{P}_{1}]_{ij}=\mathbf{1}_{\{j\in\mathcal{N}(i)\}}$ , $\Psi_{1}=M_{\ell}$ , $\operatorname*{Agg}=\sum$ , $\boxplus=\mathrm{id}$ , $\mathcal{B}_{\ell}(\mathbf{H}^{(\ell)},\mathbf{H}^{(0)})=\mathbf{H}^{(\ell)}$ , and $\phi_{\ell}=U_{\ell}$ . The graph-level readout $R$ lies outside the base-layer equation
Graph Network block ( Battaglia et al., 2018 )	A graph $(\mathbf{u},V,E)$ ; edge update $\phi^{e}$ ; edge-to-node aggregation $\rho^{e\to v}$ ; node update $\phi^{v}$ ; edge-to-global and node-to-global aggregations $\rho^{e\to u}$ and $\rho^{v\to u}$ ; and global update $\phi^{u}$	The GN formalism explicitly types edge , node, and global domain updates and aggregations, but it does not separately parameterize them by a channel inventory $\mathcal{K}$ with distinct support operators $\mathbf{P}_{k}$ , value maps $\Psi_{k}$ , and a cross-channel mixing operator $\boxplus$	Its node-update slice is represented exactly by taking edge incidence as the support of $\mathbf{P}_{1}$ , $\Psi_{1}=\phi^{e}$ , $\operatorname*{Agg}=\rho^{e\to v}$ , $\boxplus=\mathrm{id}$ , $\mathcal{B}_{\ell}({\bm{h}}_{i})=({\bm{h}}_{i},\mathbf{u})$ , and $\phi_{\ell}=\phi^{v}$ , with $\mathbf{u}$ supplied as shared context. A full GN block additionally updates edge and global states: in the canonical ordering, $\phi^{v}$ consumes aggregated updated edges and $\phi^{u}$ consumes aggregated updated edges and updated nodes. Representing the full block therefore requires multiple typed domains and staged updates rather than a single node-domain base-layer application
Augmented message-passing view ( Veličković, 2022 )	Pairwise message passing applied to a suitably augmented computational graph, where features, connectivity, or represented entities may be modified so that a richer computation is realized through pairwise communication	This is a broad representational viewpoint rather than a prescribed layer tuple. It does not require an explicit channel inventory, support value factorization, or separately named cross channel mixing component	Broader in representational scope. A computation is captured by one seven-component base-layer application only when the relevant synchronous step admits the stated channel-wise normalization. Computations requiring graph augmentation, replicated entities, multiple dependent stages, or other transformations may still fall within augmented message passing while requiring more than one base-layer application or an augmented computational graph
Seven-component equation (this work)	$\mathcal{X}$ , $\mathcal{K}$ , $\{\mathbf{P}_{k}\}$ , $\{\Psi_{k}\}$ , $\boxplus$ , $\mathcal{B}_{\ell}$ , and $\phi_{\ell}$	The training objective, post-stack readout, external domain transitions such as pooling, and multi-stage control flow are outside the base layer	A typed reporting form for the covered layer class. It refines the canonical MPNN description by separately exposing support, channel-wise value computation, mixing, and base-state construction. It captures the node-update slice of a Graph Network block but not an entire staged edge node global block in one node-domain application, and it is intentionally narrower than the broader augmented-message-passing viewpoint

Table 3: Comparison with prior message-passing abstractions.

Figure 2: The unified equation, slot by slot. Each channel separates where information propagates, set by the propagation operator $\mathbf{P}_{k}^{(\ell)}$ , from what information is transmitted, set by the message map $\Psi_{k}^{(\ell)}$ . Combining the two gives the channel contribution $\mathbf{C}_{k}^{(\ell)}$ . The channel-mixing operator $\boxplus$ mixes the contributions from every channel into the mixed message $\widetilde{\mathbf{H}}^{(\ell)}$ (written $\widetilde{\mathbf{H}}^{(\ell)}$ in the text). The update map $\phi_{\ell}$ then combines $\widetilde{\mathbf{H}}^{(\ell)}$ with the residual/ego pathway $\mathcal{B}_{\ell}(\mathbf{H}^{(\ell)},\mathbf{H}^{(0)})$ , which carries the node’s own prior state, to produce the next-layer intermediate state $\overline{\mathbf{H}}^{(\ell+1)}$ (Eq. ( 3 )). Architectures differ only in how each of these seven components is filled. The domain $\mathcal{X}$ and channel set $\mathcal{K}$ determine the objects and indexed branches shown in the diagram.

Figure 3: Generated architectures at three levels. The fixed inventory in Levels 1–2 contains the seven components $(\mathcal{X},\mathcal{K},\mathbf{P}_{k},\Psi_{k},\boxplus,\mathcal{B}_{\ell},\phi_{\ell})$ . Level 1 recombines compatible existing fillings across families. Level 2 replaces the filling of an existing component (illustrated for $\mathbf{P}_{k}$ ) without changing that inventory. Level 3 extends the schema with a compatible new computational component. The generic labels $f_{\bullet}$ denote component fillings and do not imply that the set-valued components $\mathcal{X}$ and $\mathcal{K}$ are functions. Removing the added slot recovers Eq. ( 3 ) on the node domain, or, for a graded-domain Level 3 layer, first the synchronous graded form Eq. ( 5 ) and then Eq. ( 3 ) at its rank-zero case. The sequential node–edge example instantiates Level 3 with a schedule that makes the edge update precede the node update.

Panel of Figure 6 — Prompt 1 The generation protocol supplied to a language-model controller. It comprises the unified equation ( 3 ), the slot inventory and admissible fillers, and the per-level validity conditions a generated layer must satisfy, for recombining fillers, introducing a new filler, or expanding the equation.

Method	$\bm{\mathcal{X}}$	$\bm{\mathcal{K}}$	Propagation $\bm{\mathbf{P}_{k}^{(\ell)}}$	Message $\bm{\Psi_{k}^{(\ell)}}$	Mixing $\bm{\boxplus^{(\ell)}}$	Ego/Update $\bm{(\mathcal{B}_{\ell},\phi_{\ell})}$	New Slot $\bm{\mathcal{S}_{\ell}}$
Level 1 Recombination equation and inventory fixed, with fillers combined across families
Spectrally-Gated Propagation	$V$	$\{1,\ldots,$ $K\}$	$\Diag\!\bigl(\bm{\gamma}_{k}($ $\mathbf{H}^{(\ell)})\bigr)^{\!\star}$ ${}\cdot T_{k}(\tilde{\mathbf{L}}_{\mathrm{ch}})$ (node-adaptive)	$\mathbf{H}^{(\ell)}\mathbf{W}_{k}$	$\displaystyle\sum_{k=1}^{K}\mathbf{P}_{k}\Psi_{k}$	$\sigma\!\bigl(\mathbf{H}^{(\ell)}\mathbf{W}_{0}$ ${}+\widetilde{\mathbf{H}}^{(\ell)}\bigr)^{\dagger}$	–
Relation- Equivariant Network	$V$ $(s,v)$	$\mathcal{R}$ (relations)	$\hat{\mathbf{A}}_{r}$	$\Psi_{r}^{\star}\!\bigl(\mathbf{h}_{i},\mathbf{h}_{j},$ $\lVert\mathbf{x}_{i}-\mathbf{x}_{j}\rVert\bigr)$ (equiv. $(s,v)$ )	$\mathbf{C}_{r,i}=\operatorname*{Agg}$ ${}_{j\in\mathcal{N}_{r}(i)}[\mathbf{P}_{r}]_{ij}\Psi_{r},$ $\widetilde{\mathbf{H}}_{i}=\displaystyle\sum_{r\in\mathcal{R}}\mathbf{C}_{r,i}$	$\phi^{s},\phi^{v}$ (scalar/vector)	–
Subgraph- Attentive Layer	$\mathcal{S}$ (subgr.)	$\{1,\ldots,$ $H\}$ (heads)	$\mathrm{softmax}\!\bigl($ $\mathbf{Q}_{h}\mathbf{K}_{h}^{\top}\bigr)^{\!\star}$ (state-dependent)	$\mathbf{H}_{\mathcal{S}}^{(\ell)}\mathbf{W}_{V,h}$	$\displaystyle\big\\|_{h}\mathbf{P}_{h}\Psi_{h}$	$\MLP(\widetilde{\mathbf{H}}^{(\ell)})$ ${}+\mathbf{H}_{\mathcal{S}}^{(\ell)}$ (external $\mathbf{Q}_{\ell}$ fold $\mathcal{S}\!\to\!V$ )	–
Spectral-Biased Transformer	$V$	$\{1\}$ (global)	$\mathrm{softmax}\!\bigl($ $\mathbf{Q}\mathbf{K}^{\top}/\sqrt{d}$ ${}+\mathbf{B}_{\mathrm{spec}}^{\star}\bigr)$	$\mathbf{H}^{(\ell)}\mathbf{W}_{V}$	$\mathbf{P}_{1}\Psi_{1}$	$\MLP(\widetilde{\mathbf{H}}^{(\ell)})$ ${}+\mathbf{H}^{(\ell)}$	–
Level 2 New fillers equation fixed, with a filler introduced that the inventory lacks

Table 4: Generated architectures from the unified equation. Architectures retained by the procedure of Section 4 . Levels 1–2 use the seven components in six base columns, while Level 3 adds the new slot

\mathcal{S}_{\ell}

. The Mixing and Ego/Update columns follow the conventions of Section 3.2 . Here

\mathbf{B}_{\mathrm{spec}}=\sum_{k=0}^{K}\beta_{k}T_{k}(\tilde{\mathbf{L}}_{\mathrm{ch}})

is the learned spectral bias. The symbol ⋆ marks the component changed relative to the closest method, and † identifies the two rows using the linear-specialization update

\sigma(\mathbf{H}^{(\ell)}\mathbf{W}_{0}+\widetilde{\mathbf{H}}^{(\ell)})

of Eq. ( 2 ).

Figure 4: Repeated propagation leads to oversmoothing. Repeated application of the propagation operator $\mathbf{P}_{k}$ progressively suppresses non-dominant (high-frequency) modes. As propagation depth $L$ increases, initially distinct node representations become increasingly mixed and eventually converge toward the dominant invariant subspace, producing oversmoothing (rank collapse).

Figure 5: Local propagation through a bottleneck leads to oversquashing. Repeated application of $\mathbf{P}_{k}$ expands the receptive field of target node $v$ with depth $L$ . Once distant nodes become reachable, increasingly many signals must traverse the same narrow topological bottleneck, compressing their individual influence on $v$ .

Figure 6: Matching the operator’s pass-band to the signal. In the illustrated heterophilic setting, the class-discriminative signal occupies frequencies attenuated by standard low-pass propagation. Consequently, repeated propagation suppresses these informative components, causing the class representations to become less distinguishable, as characterized in Corollary 2 . An adaptive band-selective $\mathbf{P}_{k}$ instead shapes its spectral response to retain the informative frequency band and thereby preserve discriminative information.

Remedy class (instance)	Targets	Slot	Quantity moved (trade-off)	Key refs
Curvature rewiring (SDRF, BORF)	oversquashing	$\mathbf{P}_{k}$ support/weights	raises $(\widehat{\mathbf{S}}^{t})_{vu}$ on negative-curvature edges; pruning can slow smoothing	Topping et al.,2022 ; Nguyen et al.,2023 ; Liu et al.,2023a
Spectral-gap rewiring (FoSR, GTR)	oversquashing	$\mathbf{P}_{k}$ support; relation channels	raises $\lambda_{2}$ / lowers $R_{\mathrm{tot}}$ ; relational split avoids induced smoothing	Karhadkar et al.,2023 ; Black et al.,2023
Spectral pruning (Braess)	squashing and smoothing	$\mathbf{P}_{k}$ support/weights	selected edge deletions can raise $\lambda_{2}$ and co-mitigate both under the cited criterion	Jamadandi et al.,2024 ; Liang et al.,2025
Learned rewiring (PR-MPNN)	oversquashing, underreaching	$\mathbf{P}_{k}$ sampled support	differentiable $k$ -subset edges; conditions for ${>}$ random rewiring	Qian et al.,2024
Virtual / global channel (MPNN ${+}$ VN)	oversquashing, long-range	$\mathcal{X}$ and $\mathbf{P}_{k}$ for VN; $\mathbf{P}_{k}$ for dense attention	VN adds a two-edge path (two synchronous propagation steps); classical VN forces uniform importance	Southern et al.,2025b ; Cai et al.,2023
Signed / high-pass bank (FAGCN, GPR-GNN, BernNet, ChebNetII)	heterophily, oversmoothing	$\mathbf{P}_{k}$ bank ( $\gamma_{k}$ folded in)	shifts the response high or uses signed $\gamma_{k}$ ; can suppress the dominant smoothing response	Bo et al.,2021 ; Chien et al.,2021 ; He et al.,2021 ; He et al.,2022b

Table 5: Remedies are interventions on a named slot. Each remedy class, the pathology it targets, the unified-equation slot ( 3 ) it modifies, and the operator/topology quantity it moves (with the trade-off it incurs). Architectures are instances.

Figure 7: The spectral-gap trade-off. Oversquashing and oversmoothing are governed by the same spectral gap $\lambda_{2}$ in opposite directions. A low-conductance graph with a bottleneck edge (left) has a small $\lambda_{2}$ . Long-range messages compress through the bottleneck, so oversquashing is severe while repeated propagation barely mixes the graph. A high-conductance, densely connected graph (right) has a large $\lambda_{2}$ . Mixing is fast, relieving oversquashing, but the same speed drives high-frequency components to decay as $\exp(-\lambda_{2}k)$ , so node embeddings homogenize just as quickly. The Cheeger bound $\lambda_{2}/2\leq h_{G}\leq\sqrt{2\lambda_{2}}$ ties both effects to the same graph conductance $h_{G}$ . Moving $\lambda_{2}$ trades one pathology for the other rather than fixing both independently.

Phenomenon	Diagnostic measure	Governing quantity (and bound)	Key refs
Oversmoothing (forward)	Dirichlet energy $E$ ; MAD (Mean Average Distance); numerical rank	largest nontrivial eigenvalue magnitude: $d_{\mathcal{M}}(\mathbf{H}^{(\ell)}){\leq}(\bar{s}\mu_{\star})^{\ell}$ ; $E(\mathbf{H}^{\prime}){\leq}(s\mu_{\star})^{2}E(\mathbf{H})$ under Theorem 2 ; rank ${\to}1$ under the cited conditions	Oono and Suzuki,2020 ; Cai and Wang,2020 ; Roth and Liebig,2024 ; Zhang et al.,2026b
Oversharpening (dual)	high-frequency energy growth	sign of channel-mixing eigenvalues: most-negative dominant ${\Rightarrow}$ repulsion	Giovanni et al.,2023b
Oversmoothing (backward)	smoothness of backprop. error; flat high-loss regions	linear backward smoothing; per-layer Lipschitz bound	Keriven,2026 ; Park and Kim,2024
Oversquashing	Jacobian $\lVert\partial{\bm{h}}_{v}^{(t)}/\partial{\bm{h}}_{u}^{(0)}\rVert$ ; mixing	$(\widehat{\mathbf{S}}^{t})_{vu}$ ; $R_{uv}{=}\tau(u,v)/(2\|\mathcal{E}\|)$ ; capacity ${\gtrsim}\tau(u,v)$	Topping et al.,2022 ; Giovanni et al.,2023a ; Black et al.,2023 ; Giovanni et al.,2024
Underreaching	receptive radius ${<}$ task distance	depth $t{<}d(u,v)$ : $(\widehat{\mathbf{S}}^{t})_{vu}{=}0$	Giovanni et al.,2023a ; Errica et al.,2025
Heterophily / band mismatch	aggregation homophily; Contextual Stochastic Block Model (CSBM) Bayes error	pass-band of $\mathbf{P}_{k}$ vs. signal band; low-pass response of $\hat{\mathbf{A}}$ is $(1{-}\lambda_{i})$	NT and Maehara,2019 ; Luan et al.,2022 ; Ma et al.,2022 ; Luan et al.,2023

Table 6: Propagation diagnostics and their assumptions. Each pathology, the measure that detects it, and the operator, topology, capacity, or optimization quantity that governs it (with the inequality direction where available).

\mathbf{L}_{\mathrm{ref}}

is the self-loop-normalized reference Laplacian of Section 2 ,

\lambda_{2}

the relevant normalized-Laplacian spectral gap in the cited result,

\widehat{\mathbf{S}}

the normalized sensitivity/support operator,

R_{uv}

effective resistance, and

\tau

commute time.

Model class (instance)	WL power	Counting power	Memory	Key refs
Mean/max/attention-aggregation MPNN (GCN, GraphSAGE-mean, GAT)	${\leq}\,1$ -WL (strict for mean/max)	loses multiset multiplicities (mean/attention) or repeats (max)	$O(n{+}\|\mathcal{E}\|)$	Xu et al.,2019b
Injective sum-aggregation MPNN (GIN)	${=}\,1$ -WL (the ceiling, attained iff aggregate and readout are injective)	stars only; no induced connected pattern ${\geq}3$ nodes; no girth/diameter/ $k$ -clique/biconnectivity	$O(n{+}\|\mathcal{E}\|)$	Xu et al.,2019b ; Chen et al.,2020c ; Garg et al.,2020 ; Zhang et al.,2023b
Polynomial spectral GNN (GPR-GNN, BernNet, ChebNetII)	${\leq}\,1$ -WL under the structure-blind node-domain hypotheses of Proposition 4 ; fixed-graph reachability is a separate axis	filter-band dependent; reaches any $1$ -D target on one fixed graph if the spectrum is simple and no frequency is missing	$O(K\|\mathcal{E}\|)$	Wang and Zhang,2022
Spectral-invariant GNN (eigenbasis invariants)	strictly between $1$ -WL and the subgraph-GNN band above it	homomorphism-counts (hom-counts) exactly “parallel trees”; class grows with depth	$O(n^{2})$	Gai et al.,2025
Hom-count-augmented MPNN ( $F$ -MPNN; spasm basis)	${=}\,F$ -WL; gain over $1$ -WL depends on $F$ ; for every fixed $k$ some $F$ escapes $k$ -WL	counts patterns via $\mathrm{sub}(Q,G){=}\sum_{F\in\mathrm{spasm}(Q)}\alpha_{F}\hom(F,G)$	$O(n)$	Barceló et al.,2021 ; Jin et al.,2024
Node-based subgraph GNN (ESAN, GNN-AK, SUN, SSWL)	${>}\,1$ -WL, ${<}\,2$ -FWL ( $=3$ -WL) for the six ordered classes	the analyzed subgraph-MPNN class node-counts cycles only through length $4$	$O(n(n{+}\|\mathcal{E}\|))$	Frasca et al.,2022 ; Zhang et al.,2023a

Table 7: Slot-aware expressivity hierarchy. Each row places a model class (architectures in parentheses are instances) on the relevant Weisfeiler–Leman or orthogonal expressivity axis and states the substructure/homomorphism count it can or cannot achieve. Rows on incomparable axes should not be read as a total bottom-to-top ordering.

Figure 8: Global mixing in one layer versus two. A dense propagation operator (row $i$ full) lets node $i$ depend on every other node ${\bm{h}}_{j}^{(\ell)}$ after a single application of $\mathbf{P}_{k}$ (Proposition 5 ). A virtual node instead adds only a one-hop path to a shared hub. Node $i$ reads the hub’s pre-update state, but the hub itself must first collect from every real node, so a signal from $j$ reaches $i$ only after two propagation steps, $j\to v\to i$ . The same one-layer/two-layer gap holds for any support that leaves row $i$ short of full.

Benchmark family	Task / domain	Documented design or finding	Component-level reading	Key refs
Citation networks (Cora, Citeseer, Pubmed; Planetoid splits)	Citation graphs	Node classification on homophilous graphs. Adjusted homophily is preferable for cross-dataset comparison, label informativeness agrees more closely with GNN performance, and rankings depend on splits and tuning	$\mathbf{P}_{k}$ encodes topology, but no layer component is isolated	Yang et al.,2016 ; Shchur et al.,2018 ; Platonov et al.,2023a ; Luo et al.,2024b
OGB node / link ( ogbn , ogbl )	Multiple domains and tasks	Large datasets with application-specific splits, metrics, and standardized pipelines. Scale and out-of-distribution generalization are common challenges	Dataset- and task-dependent; scale, split, and prediction head †	Hu et al.,2020a
Heterophily suite, legacy (Geom-GCN: Texas, Wisconsin, Cornell, Actor, Chameleon, Squirrel)	Node classification	Geom-GCN evaluated geometric aggregation on this suite. Duplicate nodes in Chameleon and Squirrel create train–test leakage and materially change results when removed	No reliable component attribution; $\mathbf{P}_{k},\mathcal{K},$ and $\mathcal{B}_{\ell}$ are relevant design axes	Pei et al.,2020 ; Platonov et al.,2023b
Heterophily suite, corrected (Roman-empire, Amazon-ratings, Minesweeper, Tolokers, Questions)	Node classification	Diverse heterophilous graphs without the identified duplicate-node leakage. Standard GNNs are strong baselines, and connectivity is better characterized jointly by adjusted homophily and label informativeness	$\mathbf{P}_{k},\mathcal{K},\mathcal{B}_{\ell},$ and $\mathbf{H}^{(0)}$ are relevant but not isolated	Platonov et al.,2023b ; Platonov et al.,2023a
Large non-homophilous (LINKX datasets)	Social and web node classification	Substantially larger non-homophilous graphs. Existing scalable and mini-batch methods degrade on these datasets	$\mathbf{P}_{k},\mathcal{K},\mathbf{H}^{(0)}$ ; scale and mini-batching †	Lim et al.,2021
TUDataset	Graph classification and regression across more than 120 datasets	A repository with standardized loaders, baselines, and evaluation rather than a controlled test of one architectural mechanism	Dataset-dependent; graph-level readout $\rho^{\dagger}$	Morris et al.,2020a

Table 8: Benchmark evidence in the component vocabulary. The documented design or finding column summarizes claims made by the cited benchmark papers. The component reading is our translation into Eq. ( 3 ) and does not attribute performance to a component. The symbol

\mathbf{H}^{(0)}

denotes the input representation. A

\dagger

marks a task head or readout, scale or sampling concern, distribution split, or temporal extension outside the seven base-layer components.

Open problem	Why it is hard	What would count as progress	Slot	Key refs
Generalization beyond expressivity	More expressive fillings provably inflate the complexity term (WL classes bound Rademacher complexity), and no theory ties SGD implicit bias to generalization	Non-vacuous, structure-aware bounds naming which statistics control error at a reasonable computational cost, valid for sparse unbounded-size graphs, and connected to scaling the operator (Section 7.5 )	$\mathbf{P}_{k},\Psi_{k},\boxplus,\phi_{\ell}$	Morris et al.,2024 ; Vasileiou et al.,2025 ; Carrasco et al.,2025 ; Amran et al.,2026 ; Rauchwerger et al.,2025
Distribution / size shift	Failure is a shift over local structure. Causal-invariance remedies rest on unverifiable assumptions, and rankings reverse across shift types	A measurable predictor of which statistic governs transfer and validated environment-free causal-subgraph discovery	$\mathbf{P}_{k},\mathcal{X}$	Yehudai et al.,2021 ; Li et al.,2025b ; Loveland et al.,2024 ; Chen et al.,2022c ; Gui et al.,2022
Dataset-adaptive slot selection	Homophily is sensitive to class count/balance and unreliable for model selection. No mechanistic property-to-slot map exists	A robust measured property predicting the right $\mathbf{P}_{k}/\Psi_{k}$ across datasets	$\mathbf{P}_{k},\Psi_{k},\mathcal{X}$	You et al.,2020 ; Platonov et al.,2023a ; Luan et al.,2026 ; Kormann et al.,2026
Slots as a search space (graph neural architecture search, graph-NAS)	Graph-NAS learns shift-fragile non-causal maps, is non-reproducible without a shared space, and uses language-model controllers that lack guarantees	Causal, data-conditioned search whose discovered tuple generalizes under shift	all seven components	Wang et al.,2022b ; Qin et al.,2022 ; Li et al.,2025c ; Gao et al.,2025
Scaling the operator $\mathbf{P}_{k}$	Whether dense attention is even needed is unproven. It is unknown how much expressivity sub-quadratic attention sacrifices, sparsification and condensation guarantees do not transfer, and no clean long-range benchmark exists	A characterized expressivity-efficiency frontier and a structured $O(n)$ operator provably matching dense attention	$\mathbf{P}_{k},\mathcal{X}$	Deng et al.,2024 ; Sancak et al.,2025 ; Chen et al.,2023d ; Tönshoff et al.,2024 ; Gupta et al.,2026
Temporal / time-indexed carry slot	Dominant temporal families are incomparable, standard messages cannot express moving averages, and component-to-gain links are untested	A temporal WL/counting ladder and a principled continuous-time memory operator with known limits	$\mathcal{B}(t),\mathbf{P}_{k}(t),\Psi_{k}$	Souza et al.,2022 ; Tjandra et al.,2024 ; Cong et al.,2023 ; Li et al.,2025a ; Tieu et al.,2025

Table 9: Open problems in graph neural network design. Each row names a problem, why it resists current methods, and what would count as progress. The slot column marks the part of the unified equation ( 3 ) (or the named extension) the problem stresses. The key-reference column gives a curated, representative subset of the citations discussed in the corresponding subsection, not the full set. Rules separate the thematic clusters.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
Part I \| Standard notation. Graph objects, matrices, spectral quantities, features, and learning conventions following established usage in spectral graph theory and graph neural networks.
Graph structure
$\mathcal{G}=(\mathcal{V},\mathcal{E})$	Graph with node set $\mathcal{V}$ and edge set $\mathcal{E}$
$n=\|\mathcal{V}\|$ , $m=\|\mathcal{E}\|$	Number of nodes and edges
$\mathcal{N}(v)$	Neighborhood of node $v$
$d_{v}$	Degree of node $v$

Appendix

Table 10: Notation used throughout the paper. Part I lists standard graph, spectral, and learning symbols; Part II lists the unified layer-slot notation of Eq. ( 3 ).

Operation	Primary location	Time	Effect
Positional / structural encoding	$\Psi_{k}$ ; external input $\mathbf{H}^{(0)}$ for pre-stack encoding; $\mathbf{P}_{k}$ for pairwise score biases	infer	Adds position/structure descriptors; can break neighborhood-isomorphism symmetry.
Rewiring / virtual node	$\{\mathbf{P}_{k}^{(\ell)}\}$ (support/weights; $\mathcal{X}$ if nodes added)	infer	Changes which nodes communicate; can relieve oversquashing bottlenecks.
Skip / residual	$\mathcal{B}_{\ell}$	infer	Re-injects earlier state; enables depth, can counter oversmoothing.
Normalization	$\phi_{\ell}$ primarily; $\mathbf{P}_{k},\Psi_{k}$ for state pre-norm	infer	Rescales/recenters states; stabilizes training, can oppose collapse.
Pooling / readout	external $\rho$ for flat readout; $\mathcal{X}$ / $\{\mathbf{P}_{k}^{(\ell)}\}$ via external $\mathbf{Q}_{\ell}$ if hierarchical	infer	Produces graph-level vector; coarsens support in stages.
Continuous-depth / ODE	$\phi_{\ell}$ primarily; $\Psi_{k},\mathbf{P}_{k}$ for augmented dynamics; $\mathcal{X}$ only if objects are added	infer	Reads depth as integration time over a chosen graph vector field.

Appendix

Table 11: Operations mapped to their primary location : a component of Eq. ( 3 ), an external input/between-layer map, or the post-stack readout

\rho

. Different primary component assignments suggest compatibility; edits sharing a component require reconciliation. “Time” marks whether the edit is typically active at inference or mainly during training.

Result	Reference	Description
Spectral subsumption	(Lemma 1 )	A layer applying scalar functions of a fixed shift operator through its spectral calculus is the unified equation with $\mathbf{P}_{k}=g_{k}(\mathbf{S})$ ; ChebNet, SGC, APPNP, GPR-GNN, and BernNet are each an exact special case, separated by the operator/basis, the coefficient constraint, and the coupled-versus-decoupled message slot.
Concatenation is additive mixing	(Prop. 1 )	Multi-head concatenation equals a sum of head outputs embedded into disjoint output blocks, introducing no separate mixing mechanism beyond summation.
Concatenation expressivity	(Cor. 1 )	In the linear regime concatenation matches additive mixing only after projection to a common width; concatenation itself creates explicit head separation in disjoint coordinates, and downstream weights (or a blockwise nonlinearity) decide whether it is exploited or erased.
Attention subsumption	(Lemma 3 )	A single-head layer whose neighbor weight is a scalar function of node states times a linear value is the unified equation with a state-dependent operator; restricted to the single-head, edge-feature-free case, GAT and GATv2 differ only in the score inside $\mathbf{P}_{k}$ .
Channel count not identifiable	(Prop. 2 )	The linear pre-activation depends only on $\mathbf{T}=\sum_{k}\mathbf{W}_{k}^{\top}\otimes\mathbf{P}_{k}$ , so the channel count is not recoverable and the invariant is the channel rank.
Receptive field and underreaching	(Prop. 3 )	Locally computed one-hop channels confine the depth- $L$ receptive field to the $L$ -hop ball, so a node output is independent of inputs farther than $L$ hops; a globally state-dependent operator escapes this even at one-hop support.

Appendix

Table 12: Summary of the main theoretical results.

Order	Primary family	Assignment rule	How secondary mechanisms are handled
1	Family 1. Spatial message passing	Choose this family when the layer is best described as ordinary neighbor aggregation with shared message and update maps, and no more specific rule below is dominant.	Fixed-point solvers, readouts, sampling procedures, and routing loops are marked as external machinery when they are not one synchronous layer update.
2	Family 2. Attention and adaptive weighting	Choose this family when the main contribution is state-dependent attention, adaptive edge weights, learned masks, gates, routing coefficients, or generated aggregation weights.	Spatial supports and relation features remain secondary unless another family better describes the cited contribution.
3	Family 3. Spectral and diffusion	Choose this family when the main contribution is a Laplacian or adjacency polynomial, spectral filter, diffusion kernel, hop basis, signed propagation basis, or learned graph filter.	Ordinary neighbor aggregation is treated as the implementation of an operator basis rather than the primary family.
4	Family 4. Graph transformer	Choose this family when the defining layer performs global token mixing, transformer self-attention, structural attention biasing, sparse global attention, or tokenized graph communication.	Positional encodings, structural encodings, and local message passing are treated as supporting components.
5	Family 5. Heterogeneous and multi-relational	Choose this family when typed nodes, typed edges, relation channels, meta-paths, or knowledge-graph relation states define the update.	Attention over relations remains secondary when relation typing is the defining axis.
6	Family 6. Higher-order and subgraph	Choose this family when the updated objects are tuples, rooted subgraphs, simplices, cells, hyperedges, motifs, or another lifted domain rather than ordinary nodes alone.	Attention or spectral operations on the lifted domain are treated as secondary mechanisms.

Appendix

Table 13: Primary family assignment rules. The rules are listed in family order. A method is placed in the family whose rule best describes the dominant mechanism of the cited layer update. Other mechanisms are recorded as cross-references or boundary notes.

Method	${\color[rgb]{1,1,1}\bm{\mathcal{X}}}$	${\color[rgb]{1,1,1}\bm{\mathcal{K}}}$	Propagation $\bm{\mathbf{P}_{k}^{(\ell)}}$	Message $\bm{\Psi_{k}^{(\ell)}}$	Mixing $\bm{\boxplus^{(\ell)}}$	Ego/Update $\bm{(\mathcal{B}_{\ell},\phi_{\ell})}$
1a Anchor models fixed one-hop spatial propagation
GCN Kipf and Welling (2017)	$V$	$\{1\}$	$\hat{\mathbf{A}}$	$\mathbf{H}^{(\ell)}\mathbf{W}^{(\ell)}$	$\begin{gathered}\widetilde{\mathbf{H}}^{(\ell)}=\mathbf{P}_{1}\Psi_{1}\\ {\scriptstyle(\boxplus:\mathrm{id})}\end{gathered}$	$\sigma(\widetilde{\mathbf{H}}^{(\ell)})$
GraphSAGE-Mean Hamilton et al. (2017)	$V$	$\{1\}$	$\mathbf{D}^{-1}\mathbf{A}$	$\mathbf{H}^{(\ell)}$	$\begin{gathered}\widetilde{\mathbf{H}}^{(\ell)}=\mathbf{P}_{1}\Psi_{1}\\ {\scriptstyle(\boxplus:\mathrm{id})}\end{gathered}$	$\begin{gathered}\operatorname{norm}\!\big(\sigma([\mathbf{H}^{(\ell)}\\|\\ \widetilde{\mathbf{H}}^{(\ell)}]\\ \mathbf{W}^{(\ell)})\big)\end{gathered}$
GIN Xu et al. (2019b)	$V$	$\{1\}$	$\mathbf{A}$	$\mathbf{H}^{(\ell)}$	$\begin{gathered}\widetilde{\mathbf{H}}^{(\ell)}=\mathbf{P}_{1}\Psi_{1}\\ {\scriptstyle(\boxplus:\mathrm{id})}\end{gathered}$	$\begin{gathered}\MLP^{(\ell)}\!\big((1+\epsilon_{\ell})\\ \mathbf{H}^{(\ell)}+\widetilde{\mathbf{H}}^{(\ell)}\big)\end{gathered}$
MPNN Gilmer et al. (2017)	$V$	$\{1\}$	$\mathbf{A}$	$\begin{gathered}\Psi_{\ell}({\bm{h}}_{i}^{(\ell)},{\bm{h}}_{j}^{(\ell)},\\ {\bm{e}}_{ij})\end{gathered}$	$\begin{gathered}\mathbf{C}_{1,i}\\ {}=\textstyle\sum\nolimits_{j\in\mathcal{N}(i)}\\ \Psi_{\ell}\bigl({\bm{h}}_{i}^{(\ell)},\\ {\bm{h}}_{j}^{(\ell)},{\bm{e}}_{ij}\bigr),\\ \widetilde{\mathbf{H}}_{i}=\mathbf{C}_{1,i}\\ {\scriptstyle(\boxplus:\mathrm{id})}\end{gathered}$	$\begin{gathered}\phi_{\ell}\bigl(\\ {\bm{h}}_{i}^{(\ell)},\\ \widetilde{\mathbf{H}}_{i}^{(\ell)}\bigr)\end{gathered}$
1b Aggregators, gates, message maps, and implicit fixed points one-hop support with nonlinear message or update maps

Appendix

Table 14: Family 1. Spatial Message-Passing GNNs. Unified-component decompositions of local message-passing layers. Neighbor aggregation forms each pairwise channel contribution before

\boxplus

mixes channels; scalar degree and scaler terms are absorbed into

\mathbf{P}_{k}

. Markers identify covered slices: † is one JKNet base layer and ‡ the Graph Network node update. Fixed-point, sampled-depth, action-selection, routing, and readout machinery is external unless shown.

Method	$\bm{\mathcal{X}}$	$\bm{\mathcal{K}}$	Propagation $\bm{\mathbf{P}_{k}^{(\ell)}}$	Message $\bm{\Psi_{k}^{(\ell)}}$	Mixing $\bm{\boxplus^{(\ell)}}$	Ego/Update $\bm{(\mathcal{B}_{\ell},\phi_{\ell})}$
2a Query–key attention static and dynamic attention operators
GAT Veličković et al. (2018)	$V$	$\{1,\dots,M\}$	${\scriptscriptstyle\begin{gathered}\operatorname{softmax}_{j\in\widetilde{\mathcal{N}}(i)}\!\bigl(\\ \operatorname{LReLU}\!\bigl(\\ [{\bm{h}}_{i}\mathbf{W}_{m}\\|{\bm{h}}_{j}\mathbf{W}_{m}]\\ \mathbf{a}_{m}\bigr)\bigr)\end{gathered}}$	$\mathbf{H}^{(\ell)}\mathbf{W}_{m}^{(\ell)}$	$\begin{gathered}\mathbf{C}_{m}=\mathbf{P}_{m}\Psi_{m},\\ \widetilde{\mathbf{H}}^{(\ell)}=\big\\|_{m}\mathbf{C}_{m}\\ {\scriptstyle(\boxplus:\\|,}\\ {\scriptstyle\mathrm{avg.\ at\ final\ layer})}\end{gathered}$	$\begin{gathered}\mathcal{B}_{\ell}=0,\\ \sigma(\widetilde{\mathbf{H}}^{(\ell)})\end{gathered}$
GATv2 Brody et al. (2022)	$V$	$\{1,\dots,M\}$	${\scriptscriptstyle\begin{gathered}\operatorname{softmax}_{j\in\widetilde{\mathcal{N}}(i)}\!\bigl(\\ \operatorname{LReLU}\!\bigl(\\ {\bm{h}}_{i}\mathbf{W}_{q,m}\\ {}+{\bm{h}}_{j}\mathbf{W}_{k,m}\bigr)\\ \mathbf{a}_{m}\bigr)\end{gathered}}$	$\mathbf{H}^{(\ell)}\mathbf{W}_{k,m}^{(\ell)}$	$\begin{gathered}\mathbf{C}_{m}=\mathbf{P}_{m}\Psi_{m},\\ \widetilde{\mathbf{H}}^{(\ell)}=\big\\|_{m}\mathbf{C}_{m}\\ {\scriptstyle(\boxplus:\\|,}\\ {\scriptstyle\mathrm{avg.\ at\ final\ layer})}\end{gathered}$	$\begin{gathered}\mathcal{B}_{\ell}=0,\\ \sigma(\widetilde{\mathbf{H}}^{(\ell)})\end{gathered}$
GAT-POS Ma et al. (2021)	$V$	$\{1,\dots,M\}$	${\scriptscriptstyle\begin{gathered}\operatorname{softmax}_{j\in\widetilde{\mathcal{N}}(i)}\!\bigl(\\ \operatorname{LReLU}\!\bigl(\\ [{\bm{h}}_{i}\mathbf{W}_{m}{+}p_{i}\mathbf{U}_{m}\\ {}\\|{\bm{h}}_{j}\mathbf{W}_{m}{+}p_{j}\mathbf{U}_{m}]\\ \mathbf{a}_{m}\bigr)\bigr)\end{gathered}}$	$\mathbf{H}^{(\ell)}\mathbf{W}_{m}^{(\ell)}\ {\scriptstyle(\text{no }p)}$	$\begin{gathered}\mathbf{C}_{m}=\mathbf{P}_{m}\Psi_{m},\\ \widetilde{\mathbf{H}}^{(\ell)}=\big\\|_{m}\mathbf{C}_{m}\\ {\scriptstyle(\boxplus:\\|,}\\ {\scriptstyle\mathrm{avg.\ at\ final\ layer})}\end{gathered}$	$\begin{gathered}\mathcal{B}_{\ell}=0,\\ \sigma(\widetilde{\mathbf{H}}^{(\ell)})\end{gathered}$
AGNN Thekumparampil et al. (2018)	$V$	$\{1\}$	${\scriptscriptstyle\operatorname{softmax}_{j\in\widetilde{\mathcal{N}}(i)}(\beta_{\ell}\cos({\bm{h}}_{i},{\bm{h}}_{j}))}$	$\mathbf{H}^{(\ell)}$	$\begin{gathered}\widetilde{\mathbf{H}}^{(\ell)}=\mathbf{P}_{1}\Psi_{1}\\ {\scriptstyle(\boxplus:\mathrm{id})}\end{gathered}$	$\begin{gathered}\mathcal{B}_{\ell}=0,\\ \phi_{\ell}(\widetilde{\mathbf{H}})=\widetilde{\mathbf{H}}\end{gathered}$
GaAN Zhang et al. (2018)	$V$	$\{1,\dots,M\}$	${\scriptscriptstyle\begin{gathered}\operatorname{softmax}_{j\in\mathcal{N}(i)}\langle{\bm{h}}_{i}{\scriptstyle\mathbf{W}_{xa}^{(m)}},\\ {\bm{h}}_{j}{\scriptstyle\mathbf{W}_{za}^{(m)}}\rangle\end{gathered}}$	$\operatorname{FC}_{\theta_{v}^{(m)}}^{h}({\bm{h}}_{j})$	$\begin{gathered}\mathbf{C}_{m,i}=\mathbf{P}_{m}\Psi_{m},\\ \widetilde{\mathbf{H}}_{i}^{(\ell)}=\big\\|_{m}g_{i}^{(m)}\mathbf{C}_{m,i}\\ {\scriptstyle(\boxplus:\\|\ \text{with head gates})}\end{gathered}$	$\begin{gathered}{\scriptstyle\mathcal{B}_{\ell,i}={\bm{h}}_{i}^{(\ell)},}\\ {\scriptstyle\mathbf{q}_{i}={\bm{h}}_{i}\\|}\\ {\scriptstyle\max_{j\in\mathcal{N}(i)}\operatorname{FC}_{m}({\bm{h}}_{j})}\\ {\scriptstyle{}\\|\operatorname{mean}_{j\in\mathcal{N}(i)}{\bm{h}}_{j},}\\ {\scriptstyle\mathbf{g}_{i}=\sigma(\operatorname{FC}(\mathbf{q}_{i})),}\\ \operatorname{FC}\bigl(\\ \mathcal{B}_{\ell,i}\\|\widetilde{\mathbf{H}}_{i}^{(\ell)}\bigr)\\[3.0pt] \end{gathered}$

Appendix

Table 15: Family 2. Attention-Based GNNs. Unified-component decompositions of attention-based message passing. Scalar attention weights belong to

\mathbf{P}_{k}

, edge-conditioned values to

\Psi_{k}

, and node-wise gates or residuals to the update. Pairwise aggregation forms each channel contribution before head or branch mixing. DAGNN † reports one update in its sequential topological scan.

Method	$\bm{\mathcal{X}}$	$\bm{\mathcal{K}}$	Propagation $\bm{\mathbf{P}_{k}^{(\ell)}}$	Message $\bm{\Psi_{k}^{(\ell)}}$	Mixing $\bm{\boxplus^{(\ell)}}$	Ego/Update $\bm{(\mathcal{B}_{\ell},\phi_{\ell})}$
3a Explicit spectral and polynomial filters fixed/learned filter banks, linear in the signal
SpectralCNN Bruna et al. (2014)	$V$	$\{(p,q)\}$	$\mathbf{U}\Diag(\bm{\theta}_{pq})\mathbf{U}^{\top}$ (input/output channel pair)	$\mathbf{H}^{(\ell)}_{:,p}\mathbf{e}_{q}^{\top}$	$\textstyle\sum\nolimits_{p,q}\mathbf{P}_{pq}\Psi_{pq}$	$\sigma(\widetilde{\mathbf{H}}^{(\ell)})$
ChebNet Defferrard et al. (2016)	$V$	$\{0,\dots,K{-}1\}$	$T_{k}(\tilde{\mathbf{L}}_{\mathrm{ch}})$ ( $[-1,1]$ -rescaled $\mathbf{L}_{\mathrm{sym}}$ , distinct from $\tilde{\mathbf{L}}$ )	$\mathbf{H}^{(\ell)}\bm{\Theta}_{k}$	$\textstyle\sum\nolimits_{k}\mathbf{P}_{k}\Psi_{k}$	$\sigma(\widetilde{\mathbf{H}}^{(\ell)})$
CayleyNet Levie et al. (2019)	$V$	$\begin{gathered}\{0\}\cup\\ \{(j,p,q):\\ 1{\leq}j{\leq}r\}\end{gathered}$	$\begin{gathered}\mathbf{P}_{0}{=}c_{0}\mathbf{I},\\ \mathbf{P}_{j,p,q}{=}c_{j,pq}\mathbf{C}_{h}^{j},\\ \mathbf{C}_{h}\\ {}=(h\bm{\Delta}{-}i\mathbf{I})\\ \mathbin{\cdot}(h\bm{\Delta}{+}i\mathbf{I})^{-1}\end{gathered}$	$\begin{gathered}\Psi_{0}{=}\mathbf{H}^{(\ell)}\bm{\Theta}_{0},\\ \Psi_{j,p,q}\\ {}=\mathbf{H}^{(\ell)}_{:,p}\mathbf{e}_{q}^{\top}\end{gathered}$ (complex coefficients folded into $\mathbf{P}$ )	$\begin{gathered}\mathbf{P}_{0}\Psi_{0}\\ {}+2\mathrm{Re}\!\textstyle\sum\nolimits_{j,p,q}\\ \mathbf{P}_{j,p,q}\Psi_{j,p,q}\end{gathered}$	$\sigma(\widetilde{\mathbf{H}}^{(\ell)})$
GWNN Xu et al. (2019a)	$V$	$\{(p,q)\}$	$\bm{\psi}_{s}\,\Diag(\mathbf{f}_{pq})\,\bm{\psi}_{s}^{-1}$ (wavelet; input/output channel pair)	$\mathbf{H}^{(\ell)}_{:,p}\mathbf{e}_{q}^{\top}$	$\textstyle\sum\nolimits_{p,q}\mathbf{P}_{pq}\Psi_{pq}$	$\sigma(\widetilde{\mathbf{H}}^{(\ell)})$
LanczosNet Liao et al. (2019)	$V$	$\begin{gathered}\mathcal{S}_{\mathrm{sh}}\\ {}\cup\mathcal{S}_{\mathrm{lo}}\end{gathered}$	$\begin{gathered}\mathbf{S}^{s}\hskip 8.19447pt\text{or}\\ \rho_{i,q}(\mathcal{I})\\ {}=f_{i}\!\bigl(r_{q}^{I_{1}},\dots,\\ r_{q}^{I_{\|\mathcal{I}\|}}\bigr),\\ \widehat{\mathbf{L}}_{i}(\mathcal{I})\\ {}=\textstyle\sum_{q}\rho_{i,q}(\mathcal{I})\\ \mathbf{v}_{q}\mathbf{v}_{q}^{\top}\end{gathered}$ (Ritz)	$\mathbf{H}^{(\ell)}$	$\big\\|_{k}\mathbf{P}_{k}\Psi_{k}$	$\sigma(\widetilde{\mathbf{H}}^{(\ell)}\mathbf{W})$

Appendix

Table 16: Family 3. Spectral, Diffusion, and Compatibility-Aware Graph Operators. Unified-component decompositions of spectral, diffusion, and compatibility-aware operators. Spectral and channel coefficients are absorbed into

\mathbf{P}_{k}

, while restart and residual terms remain in the update. Pairwise aggregation precedes cross-channel mixing. Rows marked

\dagger

report the source-supported slice of signal-dependent, recurrent, selected, or composite operators without imposing a false fixed factorization.

Method	$\bm{\mathcal{X}}$	$\bm{\mathcal{K}}$	Propagation $\bm{\mathbf{P}_{k}^{(\ell)}}$	Message $\bm{\Psi_{k}^{(\ell)}}$	Mixing $\bm{\boxplus^{(\ell)}}$	Ego/Update $\bm{(\mathcal{B}_{\ell},\phi_{\ell})}$
4a Dense global attention with structural bias full or subgraph all-pairs softmax; bias inside the operator Graph Trans. Dwivedi and Bresson (2021) is the one exception, restricting $\mathbf{P}_{k}$ to $\mathcal{N}(i)$ (genuinely local, not all-pairs), grouped here for its Transformer-block lineage rather than its support
Graph-BERT Zhang et al. ( 2020 )	$\begin{gathered}g_{i}=(V_{i},\emptyset)\\ V_{i}=\{v_{i}\}\\ {}\cup\Gamma(v_{i})\\ {}+\mathrm{WL}\\ {}+\mathrm{PPR}\mathrm{rank}\\ {}+\mathrm{hop}\end{gathered}$	$\{1\}$	$\begin{gathered}\operatorname{softmax}(\mathbf{Q}\mathbf{K}^{\top}/\sqrt{d})\\ \text{on linkless context }V_{i}\end{gathered}$	$\mathbf{H}_{i}^{(\ell)}\mathbf{W}^{V}$	$\mathbf{P}\Psi$	$\begin{gathered}\widetilde{\mathbf{H}}_{i}+\mathrm{G\text{-}Res}(\mathbf{H}_{i},\mathbf{X}_{i});\\ {\scriptstyle z_{i}=\mathrm{Fusion}(H_{i}^{D})\text{ external}}\end{gathered}$
Graph Trans. Dwivedi & Bresson ( 2021 )	$V{+}\mathrm{LapPE}$	$\{1,\dots,M\}$	$\begin{gathered}\operatorname{softmax}_{j\in\mathcal{N}(i)}\!\Bigl((\mathbf{Q}_{m}{\bm{h}}_{i})\!\cdot\\ (\mathbf{K}_{m}{\bm{h}}_{j})/\sqrt{d}\Bigr)\end{gathered}$	$\mathbf{H}^{(\ell)}\mathbf{W}_{m}^{V}$	$\mathbf{W}_{\!O}\big\\|_{m}\mathbf{P}_{m}\Psi_{m}$	$\begin{gathered}\MLP+\text{res}+\text{Norm}\\ {\scriptstyle\text{requires }V\cup E}\end{gathered}$
Graphormer Ying et al. ( 2021 )	$\begin{gathered}V\cup\{v_{g}\}\\ {}+\mathrm{deg}\end{gathered}$	$\{1,\dots,M\}$	$\begin{gathered}\operatorname{softmax}\!\bigl(\mathbf{Q}_{m}\mathbf{K}_{m}^{\top}/\sqrt{d}\\ {}+b_{\phi(i,j)}+c_{ij}^{\mathrm{SP-edge}}\bigr)\end{gathered}$	$\mathbf{H}^{(\ell)}\mathbf{W}_{m}^{V}$	$\big\\|_{m}\mathbf{P}_{m}\Psi_{m}$	$\begin{gathered}H^{\prime}=\operatorname{MHA}(\operatorname{LN}H)+H;\\ H^{+}=\operatorname{FFN}(\operatorname{LN}H^{\prime})+H^{\prime}\end{gathered}$
SAN $\dagger$ Kreuzer et al. (2021)	$\begin{gathered}V\\ {}+\mathrm{LPE}_{\theta}\\ (\lambda,\phi)\end{gathered}$	$\{1,\dots,M\}$	$\begin{aligned} a_{ij}^{m}&=\textstyle\sum_{d}\hat{w}_{ij,d}^{m},\\[2.0pt] P^{m}_{E,ij}&=\tfrac{1}{1+\gamma}\,\operatorname{softmax}_{E(i)}(a_{ij}^{m}),\\[2.0pt] P^{m}_{\bar{E},ij}&=\tfrac{\gamma}{1+\gamma}\,\operatorname{softmax}_{\bar{E}(i)}(a_{ij}^{m}),\\[2.0pt] \hat{\mathbf{w}}_{ij}^{m}&=(Q_{m}h_{i})\circ(K_{m}h_{j})\\[-1.0pt] &\hskip 8.19447pt{}\circ(E_{m}e_{ij})\end{aligned}^{\otimes}$	$\mathbf{H}^{(\ell)}\mathbf{W}_{m}^{V}$	$\mathbf{W}_{\!O}\big\\|_{m}\mathbf{P}_{m}\Psi_{m}$	$\begin{gathered}\text{Norm}+\text{res}\\ {}+\operatorname{FFN};\\[2.0pt] \text{LPE Transformer}\\[-1.0pt] \text{is a preceding stage}\end{gathered}$
GraphiT Mialon et al. (2021)	$\begin{gathered}V\\ {}+\mathrm{LapPE}\\ {}+\mathrm{GCKN}\end{gathered}$	$\begin{gathered}\{1,\dots,M\}\\[1.0pt] {\scriptstyle(\text{single-head})}\end{gathered}$	$\begin{aligned} \mathbf{D}^{-1/2}\operatorname{rownorm}\!\Bigl(&\\[-5.0pt] \exp(\mathbf{Q}_{m}\mathbf{Q}_{m}^{\top}/\sqrt{d})&\odot\mathbf{K}_{r}\Bigr)\end{aligned}^{\otimes}$	$\mathbf{H}^{(\ell)}\mathbf{W}_{m}^{V}$	$\big\\|_{m}\mathbf{P}_{m}\Psi_{m}$	$\begin{gathered}\mathbf{H}^{(\ell)}+\widetilde{\mathbf{H}}^{(\ell)};\\ \text{Transformer MLP/LN}\end{gathered}$

Appendix

Table 17: Family 4. Graph Transformers. Unified-component decompositions of graph Transformer layers. Attention defines

\mathbf{P}_{k}

; operator-level structural biases enter its score, input encodings enter

\mathcal{X}

, and

\boxplus

combines heads or branches. Pair-dependent values retain their explicit neighbor contraction, and Block 4d records learned mixing over typed token axes. Flags denote gates ⊗ , softmax-free operators ∘ , dynamic boundaries ♮ , hierarchical folds ▽ , sequential stages † , staged composites ⋆ , and local–global token concatenation ‡ .

Method	$\bm{\mathcal{X}}$	$\bm{\mathcal{K}}$	Propagation $\bm{\mathbf{P}_{k}^{(\ell)}}$	Message $\bm{\Psi_{k}^{(\ell)}}$	Mixing $\bm{\boxplus^{(\ell)}}$	Ego/Update $\bm{(\mathcal{B}_{\ell},\phi_{\ell})}$
5a Per-relation operators and weights explicit per-relation supports, weights, and relation/KG scoring
R-GCN Schlichtkrull et al. (2018)	$V$	$\mathcal{R}$	$\begin{gathered}\tfrac{1}{c_{i,r}}\mathbf{A}_{r}\\ {\scriptstyle\text{(per-rel.\ norm.)}}\end{gathered}$	$\mathbf{H}^{(\ell)}\mathbf{W}_{r}$	$\textstyle\sum\nolimits_{k\in\mathcal{K}}\mathbf{P}_{k}\Psi_{k}$	$\begin{gathered}\sigma\!\big(\mathbf{H}^{(\ell)}\mathbf{W}_{0}+\\ \widetilde{\mathbf{H}}^{(\ell)}\big)\end{gathered}$
RGAT Busbridge et al. (2019)	$V$	$\begin{gathered}\{(r,m):\\ r\in\mathcal{R},\\ 1{\leq}m{\leq}M\}\end{gathered}$	$\begin{gathered}\alpha_{ij}^{(r,m)}(\mathbf{H})\,\mathbf{A}_{r}\\ {\scriptstyle\text{WIR: softmax over }j\text{ per }r;}\\ {\scriptstyle\text{AR: softmax over }(j,r)}\end{gathered}$	$\mathbf{H}^{(\ell)}\mathbf{W}_{r,m}$	$\begin{aligned} \mathbf{C}_{m}&=\textstyle\sum_{r\in\mathcal{R}}\\ &\hskip 8.19447pt\mathbf{P}_{r,m}\Psi_{r,m},\\ \widetilde{\mathbf{H}}&=\big\\|_{m=1}^{M}\mathbf{C}_{m}\end{aligned}$	$\begin{gathered}\mathbf{H}^{\prime}=\big\\|_{m=1}^{M}\sigma(\mathbf{C}_{m})\\ {\scriptstyle(M=1:\ \text{base rule})}\end{gathered}$
CompGCN Vashishth et al. (2020)	$V\sqcup\mathcal{R}$	$\begin{gathered}\mathcal{R}\cup\mathcal{R}^{-1}\\ {}\cup\{\top\}\end{gathered}$	$\begin{gathered}\mathbf{A}_{r}\\ {\scriptstyle\text{direct/inverse/}}\\ {\scriptstyle\text{self support;}}\\ {\scriptstyle\text{unnormalized}}\end{gathered}$	$\begin{gathered}\xi({\bm{h}}_{j},{\bm{r}}_{r})\\ {}\mathbf{W}_{\lambda(r)}\\ {\scriptstyle\text{(entity--rel.\ comp.;}}\\ {\scriptstyle\lambda(r)\in\{O,I,S\}\text{)}}\end{gathered}$	$\textstyle\sum\nolimits_{k\in\mathcal{K}}\mathbf{P}_{k}\Psi_{k}$	$\begin{gathered}{\bm{h}}_{v}^{(k+1)}=f(\widetilde{\mathbf{H}}_{v}^{(k)});\\ {\bm{r}}_{r}^{(k+1)}={\bm{r}}_{r}^{(k)}\mathbf{W}_{\mathrm{rel}}^{(k)}\end{gathered}$
KBGAT Nathani et al. (2019)	$\begin{gathered}V\\ {\scriptstyle(\text{node slice;})}\\ {\scriptstyle\mathcal{R}\text{ updated}}\\ {\scriptstyle\text{separately}}\end{gathered}$	$\begin{gathered}\{(r,m):\\ r\in\mathcal{R},\\ 1{\leq}m{\leq}M\}\end{gathered}$	$\begin{gathered}\big[\alpha_{ijr}^{(m)}(\mathbf{H},\mathbf{G})\\ {}(\mathbf{A}_{r})_{ij}\big]_{ij}\\ {\scriptstyle\text{(softmax jointly over}}\\ {\scriptstyle\text{incoming }(j,r)\text{)}}\end{gathered}$	$\begin{gathered}{\bm{c}}_{ijr}^{(m)}=\\ [{\bm{h}}_{i}\\|{\bm{h}}_{j}\\ {}\\|{\bm{g}}_{r}]\\ \mathbf{W}_{1}^{(m)}\end{gathered}$	$\begin{gathered}\widehat{\bm{h}}_{i,m}=\textstyle\sum_{r}\sum_{j\in\mathcal{N}_{r}(i)}\\[-2.0pt] \alpha_{ijr}^{(m)}{\bm{c}}_{ijr}^{(m)},\\ \widetilde{\mathbf{H}}_{i}=\big\\|_{m}\widehat{\bm{h}}_{i,m}\end{gathered}$	$\begin{gathered}\sigma(\cdot);\\ \boxplus_{m}=\\|_{m}\text{ hidden},\\ M^{-1}\sum_{m}\text{ final};\\ \mathbf{G}^{(\ell+1)}\\ {}=\mathbf{G}^{(\ell)}\mathbf{W}_{R};\\ {\scriptstyle\text{printed residual:}}\\ \end{gathered}$
5b Meta-path supports channels are (learned or fixed) meta-paths; semantic-level mixing

Appendix

Table 18: Family 5. Heterogeneous and Multi-Relational GNNs. Source-grounded decompositions of heterogeneous and multi-relational layers. Relation types, meta-paths, and typed heads index channels; scalar supports and attention scores belong to

\mathbf{P}_{k}

, while typed projections and composed values belong to

\Psi_{k}

. Mixing combines completed relation or head contributions, and nonlinear selection is shown directly rather than forced into a fixed matrix product. Boundary and architecture-search rows report only the source-supported layer components.

Method	$\bm{\mathcal{X}}$	$\bm{\mathcal{K}}$	Propagation $\bm{\mathbf{P}_{k}^{(\ell)}}$	Message $\bm{\Psi_{k}^{(\ell)}}$	Mixing $\bm{\boxplus^{(\ell)}}$	Ego/Update $\bm{(\mathcal{B}_{\ell},\phi_{\ell})}$
6a Tuple-based ( $k$ -order / $k$ -WL) models states over $k$ -tuples; equivariant linear maps and FWL
IEGN Maron et al. (2019b)	$V^{k}\!\to V^{l}$	$[n]^{k+l}/\!\sim$	$\mathbf{B}_{\pi}$ (equality-pattern equivariant basis; $\|\Pi_{k,l}\|=b(k{+}l)$ )	$\mathbf{H}^{(\ell)}\mathbf{W}_{\pi}^{(\ell)}$	$\begin{gathered}\textstyle\sum_{\pi}\mathbf{B}_{\pi}\Psi_{\pi}+\\ \textstyle\sum_{\lambda}\mathbf{C}_{\lambda}\mathbf{b}_{\lambda}\end{gathered}$ (including equivariant bias basis)	$\sigma(\widetilde{\mathbf{H}}^{(\ell)})$
$k$ -GNN Morris et al. (2019)	$[V]^{k}$	$\{1\}$ (or optional loc/glob split)	$\mathbf{P}$ (support $N_{L}(s)\cup N_{G}(s)$ ; local variant uses $N_{L}$ only)	$\mathbf{H}^{(\ell)}\mathbf{W}_{2}^{(\ell)}$	$\mathbf{P}\Psi$ (optional loc/glob split sums channel contributions)	$\sigma\!\big(\mathbf{H}_{r}^{(\ell)}\mathbf{W}_{1}+\widetilde{\mathbf{H}}^{(\ell)}\big)$
PPGN Maron et al. (2019a)	$V^{2}$	$\{c=1{:}b\}$ (product channels; shown as $\times$ )	$\MLP_{1}(\mathbf{H}^{(\ell)})$ (state-dep. operator; matrix prod. $=$ 2-FWL)	$\MLP_{2}(\mathbf{H}^{(\ell)})$	$\mathbf{P}_{\times}\Psi_{\times}$	$\big[\MLP_{3}(\mathbf{H}^{(\ell)})\,\\|\,\widetilde{\mathbf{H}}^{(\ell)}\big]$ ( $\MLP_{3}$ gives $B_{\ell}$ ; concat in $\phi_{\ell}$ )
Ring-GNN Chen et al. (2019) (partial slice)	$V^{2}$	$\{1,\times\}$	$\begin{gathered}\{L_{\alpha}(\cdot),\\ L_{\beta}(\cdot)\}\end{gathered}$ (equiv. linear maps; biases included)	$\begin{gathered}\{1,\\ L_{\gamma}(\cdot)\}\end{gathered}$	$\begin{gathered}\mathbf{C}_{1}\\|\mathbf{C}_{\times}\\ {\scriptstyle\mathbf{C}_{1}=L_{\alpha}(A),}\\ {\scriptstyle\mathbf{C}_{\times}=L_{\beta}(A)L_{\gamma}(A)}\end{gathered}$	$\begin{gathered}k_{1}\sigma(\mathbf{C}_{1})\\ {}+k_{2}\sigma(\mathbf{C}_{\times})\\ {\scriptstyle\text{branchwise }\sigma\text{ and}}\\ {\scriptstyle\text{post-}\sigma\text{ scalars}}\end{gathered}$
$\delta$ - $k$ -LGNN Morris et al. (2020b)	$V^{k}$	$\{j=1{:}k\}$	$\mathbf{P}_{j}^{\delta}$ (selects $\phi_{j}(\mathbf{v},w)$ with $w\in N(v_{j})$ )	$\Psi_{j}(\mathbf{H})=\mathbf{H}$ (value ${\bm{h}}_{\phi_{j}(\mathbf{v},w)}^{(\ell)}$ )	$\mathrm{id}$ (replacement multisets feed joint tuple aggregation)	$\begin{gathered}f_{\rm mrg}^{\mathbf{W}_{1}}\!\big(\\ {\bm{h}}_{\mathbf{v}}^{(\ell)},\\ f_{\rm agg}^{\mathbf{W}_{2}}\!\big(\\ \{\!\{\Psi_{1}\}\!\},\ldots,\\ \{\!\{\Psi_{k}\}\!\}\big)\big)\end{gathered}$

Appendix

Table 19: Family 6. Higher-Order and Subgraph GNNs. Source-grounded decompositions in the graded extension, with

\mathcal{X}

lifted to tuples, subsets, rooted subgraphs, bags, or cells. Within-object aggregation forms a channel contribution before cross-channel mixing. Rows marked § use transient lifted routing while persistent state remains on nodes; ‡ marks schematic multi-stage subgraph constructions whose pooling, sampling, and readout remain external.

Method	$\bm{\mathcal{X}}$	$\bm{\mathcal{K}}$	Propagation $\bm{\mathbf{P}_{k}^{(\ell)}}$	Message $\bm{\Psi_{k}^{(\ell)}}$	Mixing $\bm{\boxplus^{(\ell)}}$	Ego/Update $\bm{(\mathcal{B}_{\ell},\phi_{\ell})}$
7a Invariant (distance / angle / torsion) messages $G$ -invariant scalars; coordinates enter $\mathcal{X}$ only through invariants
MoNet Monti et al. ( 2017 )	$\begin{gathered}V;\\ u_{ij}\\ {\scriptstyle(\text{pseudo-coord.})}\end{gathered}$	$\{1,\dots,J\}$	$\begin{gathered}{}[\mathbf{P}_{m}]_{ij}=\\ \mathds{1}[j\in\mathcal{N}(i)]\\ {}\cdot w_{m}(u_{ij})\\ {\scriptstyle(\text{Gaussian})}\\ {\scriptstyle(\text{pseudo-coordinate})}\\ {\scriptstyle(\text{kernel})}\end{gathered}$	${\bm{h}}_{j}^{(\ell)}\mathbf{W}_{m}^{(\ell)}$	$\textstyle\sum_{m}\mathbf{C}_{m}$	$\begin{gathered}\mathcal{B}_{\ell}=0,\\ \phi_{\ell}=\sigma(\widetilde{\mathbf{H}}^{(\ell)})\end{gathered}$
SchNet Schütt et al. ( 2017 ) $E(3)$	$\begin{gathered}V;\\ r_{ij}\end{gathered}$	$\{1\}$	$\begin{gathered}{}[\mathbf{P}_{1}]_{ij}=1\\ {\scriptstyle(\text{atom-pair support})}\end{gathered}$	$\begin{gathered}({\bm{h}}_{j}^{(\ell)}\mathbf{W}_{\rm in})\\ {}\odot W_{\theta}\!\big(\\ \mathrm{RBF}(r_{ij})\big)\\ {\scriptstyle(\text{cont.-filter msg})}\end{gathered}$	$\begin{gathered}\mathrm{id}\\ C_{1,i}=\\ \sum_{j}P_{ij}\Psi_{ij}\end{gathered}$	$\begin{gathered}\mathcal{B}_{\ell}={\bm{h}}_{i}^{(\ell)},\\ \phi_{\ell}(b,\widetilde{\mathbf{H}})=\\ b+\MLP(\widetilde{\mathbf{H}})\end{gathered}$
DimeNet Gasteiger et al. ( 2020 ) $E(3)$	$\begin{gathered}E^{\rightarrow};\\ \big(d_{ji},d_{kj},\\ \angle kji\big)\end{gathered}$	$\{1\}$	$\begin{gathered}{}[\mathbf{P}_{1}]_{(ji),(kj)}=\\ \mathds{1}\big[k\in\mathcal{N}(j)\\ {}\setminus\{i\}\big]\\ {\scriptstyle(\text{edge-line support})}\end{gathered}$	$\begin{gathered}\Psi_{\ell}\big(\\ m_{kj}^{(\ell-1)},\\ e_{\mathrm{RBF}}^{(ji)},\\ a_{\mathrm{SBF}}^{(kj,ji)}\big)\end{gathered}$	$\begin{gathered}\mathrm{id}\\ C_{1,ji}=\\ \sum_{k}P\Psi\end{gathered}$	$\begin{gathered}\mathcal{B}_{\ell}=m_{ji}^{(\ell-1)},\\ \phi_{\ell}=\\ f_{\mathrm{upd}}^{(\ell)}(\mathcal{B}_{\ell},\widetilde{\mathbf{H}})\\ {\scriptstyle(\text{edge update})}\end{gathered}$
SphereNet Liu et al. ( 2022b ) $SE(3)$ ; chirality-sensitive	$\begin{gathered}E^{\rightarrow};\\ (d,\theta,\phi)\\ {\scriptstyle(\text{edge slice})}\end{gathered}$	$\{1\}$	$\begin{gathered}{}[\mathbf{P}_{1}]_{k,h}=\\ \mathds{1}[h\in E_{s_{k}}]\\ {\scriptstyle(\text{edge-neighbor})}\\ {\scriptstyle(\text{support})}\end{gathered}$	$\begin{gathered}\Psi_{\ell}\big(e_{h}^{(\ell)},\\ \Psi(d),\\ \Psi(d,\theta),\\ \Psi(d,\theta,\phi)\big)\end{gathered}$	$\begin{gathered}\mathrm{id}\\ C_{1,k}=\\ \sum_{h}P\Psi\end{gathered}$	$\begin{gathered}\mathcal{B}_{\ell}=e_{k}^{(\ell)},\\ \phi_{\ell}=\text{residual edge update}\end{gathered}$
GemNet Gasteiger et al. ( 2021 ) $SE(3)$ ; apart from reflections	$\begin{gathered}\{V,E^{\rightarrow}\};\\ (\varphi_{cab},\\ \varphi_{abd},\theta_{cabd})\\ {\scriptstyle(\text{graded})}\end{gathered}$	$\{\mathrm{Q},\mathrm{T},\mathrm{A}\}$	$\begin{gathered}\mathbf{P}_{Q}:\ \text{quadruplets}\\ \mathbf{P}_{T}:\ \text{triplets}\\ \mathbf{P}_{A}:\ \text{atom-to-edge}\end{gathered}$	$\begin{gathered}\Psi_{Q}\big(m_{db},e_{\rm RBF},\\ e_{\rm CBF},e_{\rm SBF}\big)\\ \Psi_{T}\big(m_{ba},e_{\rm RBF},\\ e_{\rm CBF}\big)\\ \Psi_{A}\big(h_{a},h_{c},\\ e_{\rm RBF}\big)\end{gathered}$	$\begin{gathered}\displaystyle\sum_{k\in\{Q,T,A\}}\\ \mathbf{C}_{k}\end{gathered}$	$\begin{gathered}\mathcal{B}_{\ell}=\\ (m_{ca}^{(\ell-1)},h_{a}^{(\ell-1)}),\\ \phi_{\ell}=\\ \text{edge/atom}\\ \text{residual updates}\end{gathered}$

Appendix

Table 20: Family 7. Geometric and Equivariant GNNs. Source-grounded decompositions of coordinate-, distance-, angle-, vector-, tensor-, and algebra-valued geometric layers. Geometric context enters

\mathcal{X}

; typed channel contributions are fused by tuples, direct sums, or concatenation rather than forced scalar sums. The stated symmetry group is exactly the one established by the source. Rows marked ♮ preserve that source-level group claim, while ‡ reports only the supported slice of discrete-orientation or sequential geometric constructions.

Graph Neural Networks

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

See all 714 papers

Jun 25, 2026

Graph Neural Networks Applications Across Domains: All Insights You Need

Graph neural networks have moved from a niche representation-learning technique to the default model class wherever data carry relational structure. The interesting question is no longer whether message passing helps on a given dataset, but where graph structure earns its computational cost and where it does not. This survey organises the field around a single design space, derives the spectral and spatial formulations from shared first principles, and connects expressive power to the Weisfeiler-Leman hierarchy with explicit statements of what current architectures can and cannot separate. Against that methodological backbone we examine twelve application domains, among them recommendation and social networks, knowledge graphs and language-model integration, drug discovery and molecular property learning, healthcare and neuroscience, computer vision, traffic and urban computing, power and renewable-energy systems, wireless and sixth-generation networks, fraud and cybersecurity, industrial prognostics, materials science, and climate modelling. For each domain we specify the graph-construction choices and their costs, identify which architecture families dominate and why, and separate reported gains from artefacts of weak baselines or favourable splits. A cross-domain comparison exposes recurring patterns: heterophily and scale undercut the same models almost everywhere, temporal graphs remain harder than their static counterparts, and the architectures that top public leaderboards are seldom the ones that reach deployment. We treat over-smoothing, over-squashing, robustness, distribution shift, fairness, and explainability not as a closing checklist but as the constraints that decide adoption.

Abderaouf Bahi

Computer Science and Applied Mathematics Laboratory (LIMA), Faculty of Science and Technology, Chadli Bendjedid University, P.O. Box 73, El Tarf 36000, Algeria

Graph Neural Networks Over-Squashing GNN Expressivity Oversmoothing

Ask PDF

Mar 16, 2026

Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (MP-GNN) model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is super-exponential (in number of vertices). Adding a familiar perspective, we observe that merely 2 iterations of Color Refinement (CR) induce at least an exponential number of equivalence classes, making the aforementioned MP-GNNs relatively infinitely weaker. Previous studies state that sum-aggregation MP-GNNs match full CR however they consider a weak, 'non-uniform', notion of distinguishing-power where each graph size may require a different MP-GNN to distinguish graphs up to that size. Our results concern both distinguishing between non-equivariant vertices and distinguishing between non-isomorphic graphs.

Eran Rosenbluth

RWTH Aachen University

Graph Neural Networks GNN Expressivity Message Passing Neural Networks

Ask PDF

Sep 27, 2026

Reachability is not enough: Diagnosing long-range behavior in GNNs

Graph neural networks (GNNs) are often called long-range because their architecture can connect distant nodes, but this does not show whether they use distant information correctly. We introduce a framework that measures how strongly inputs at each graph distance affect predictions and separates limitations due to architecture, finite approximation, training, and numerical execution. Our analysis shows that local message-passing can spread influence slowly, so a finite implementation may rely mainly on nearby inputs even when the ideal computation uses the whole graph. We also explain why mathematically equivalent filters can differ in how easily they are learned and how reliably they run. Across controlled tasks, models with similar architectural reach use distant information very differently, while low average error can hide failures on distant interactions. Together, these results show that long-range capability depends on learning to use information at the distances required by the task and preserving that use during computation.

Filippo Maria Bianchi

UiT The Arctic University of Norway · NORCE Norwegian Research Centre

Graph Neural Networks GNN Expressivity Message Passing Neural Networks Long-Range Graph Learning

Ask PDF

Abstract

Graph Neural Networks

Explore similar work

Graph Neural Networks Applications Across Domains: All Insights You Need

Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

Reachability is not enough: Diagnosing long-range behavior in GNNs