A central approach to formalizing the representational power of message-passing and refinement-based graph neural networks is to ask which graph parameters are determined by their stable representations. In the refinement setting, the most robust such parameters are homomorphism counts: for a fixed pattern graph F, the quantity hom(F, G) is invariant under isomorphism of G, is stable under disjoint union and tensor-type constructions, and admits a tight connection to Weisfeiler–Leman (WL) style color refinement through the classical ``homomorphisms determine refinement’’ paradigm. Consequently, rather than treating a refinement architecture as a black box, we can characterize it by the maximal family of patterns whose homomorphism counts it necessarily preserves.
In this work we focus on the refinement on ordered k-tuples, which may be viewed as a locality-guarded folklore generalization: the color of a tuple u = (u1, …, uk) is updated by aggregating the multiset of colors of tuples obtained by replacing one coordinate by a vertex w that lies in the guarded neighborhood $\bigcup_{i=1}^k N_G[u_i]$. This update rule interpolates between purely local k-tuple refinement (as in Local k-GNN) and full folklore k-tuple refinement (as in k-FWL/k-FGNN), but it is not captured by existing decomposition characterizations. The motivating question is therefore:
For k = 2, related architectures have been analyzed via nested ear decompositions (NEDs) and restricted tree decompositions that encode how local aggregation limits the way substructures can overlap. However, the passage from k = 2 to general k is not formal: one must simultaneously manage the combinatorics of width-k decompositions, the tuple-coordinates that the refinement can ``move’’ in a single step, and the constraints imposed by the neighborhood guard. A direct treewidth bound is too weak (full folklore k-WL already reaches all patterns of treewidth at most k), while the previously known strong NED notions for local k-GNN are too restrictive for Local k-FGNN, which can propagate information along controlled overlaps not available to strictly local k-tuple refinement.
Our first contribution is a structural description of precisely the additional overlap that the guarded folklore update enables. We introduce a width-k decomposition notion, phrased as a , in which the edge set of a pattern graph is partitioned into k-order ears arranged in a nesting forest. The key constraint concerns siblings attached to the same parent ear: their nested intervals must be laminar (disjoint or nested) in a sharply delimited degeneracy case, where an ear contributes at most one edge along each branch path of the parent and hence behaves, from the perspective of the guarded aggregation, like a locally resolvable perturbation. This ``degenerate-overlap permitted’’ rule is the only relaxation we allow beyond the strong (laminar) condition, and it is exactly calibrated to the locality of the update rule on k-tuples.
Our second contribution is to connect this ear-based definition to a canonical width-k tree decomposition viewpoint. We define a restricted class of decompositions with alternating bag sizes k and k + 1, together with a locality-guarded constraint on the child structure of odd-depth bags. This constraint is the decomposition-level avatar of the degeneracy rule above: it specifies when multiple children may be attached to a bag without creating non-local interactions that Local k-FGNN cannot distinguish. We provide constructive transformations in both directions between these canonical decompositions and k-almost-strong NEDs, thereby giving two equivalent, usable representations of the same pattern family.
Our third contribution is the homomorphism expressivity theorem for Local k-FGNN. We show that the stable representation computed by the Local k-FGNN refinement determines exactly the homomorphism counts of patterns admitting a k-almost-strong NED, and conversely that no strictly larger family can be guaranteed. The proof proceeds by an unfolding argument: we associate to each graph a depth-bounded unfolding object that is itself a canonical width-k decomposition in our restricted class, show that stable color equality is equivalent to isomorphism of these unfoldings, and then express representation statistics as linear transforms of bag-isomorphism homomorphism counts. This yields an explicit route from the refinement representation to hom(F, ⋅) for all patterns F in our family.
The maximality direction requires an explicit obstruction principle. We prove that whenever a connected pattern fails to admit a k-almost-strong NED, we can construct a pair of graphs G(F), H(F) (generalized twisted F"urer-type gadgets) that are indistinguishable by Local k-FGNN yet separated by hom(F, ⋅). Technically, this is shown by identifying a pebble-game characterization of the guarded folklore update and using it to guide the gadget construction; the twist parity argument then yields the homomorphism separation. This establishes that our pattern family is not merely sufficient but for homomorphism expressivity.
Finally, we locate Local k-FGNN within the refinement hierarchy. We exhibit explicit pattern families witnessing strict containments between the local k-GNN family (captured by strong k-order NEDs), the Local k-FGNN family (captured by k-almost-strong NEDs), and the full folklore family (captured by treewidth ≤ k). Intuitively, Local k-FGNN gains power by tolerating degenerate overlaps that local k-tuple refinement cannot propagate across, but it remains strictly below k-FWL because non-degenerate overlaps can force global interactions that the neighborhood-guarded aggregation cannot simulate.
In addition to the structural results, our characterizations yield an algorithmic corollary: for fixed k, membership of a pattern F in the Local k-FGNN family can be recognized in fixed-parameter time by first obtaining a width-k decomposition and then checking the restricted canonical constraints, with a subsequent conversion into a k-almost-strong NED serving as a certificate. This aligns with the intended regime of constant-order architectures, and it provides a concrete tool for designing and validating pattern families tailored to Local k-FGNN representations.
All graphs are finite, undirected, simple, and vertex-labeled unless stated otherwise. We write G = (VG, EG, ℓG), where ℓG ranges over an arbitrary (but fixed) label alphabet and label preservation is always required. For graphs F, G, a map f : VF → VG is a (graph) homomorphism if it preserves labels and edges: for every uv ∈ EF we have f(u)f(v) ∈ EG, and for every u ∈ VF we have ℓF(u) = ℓG(f(u)). We denote by Hom(F, G) the set of such maps and by hom(F, G) = |Hom(F, G)| the corresponding homomorphism count. Throughout, homomorphisms are allowed to be non-injective; in particular, hom(F, G) subsumes subgraph and induced-subgraph counts via standard inclusion–exclusion transforms once one passes to suitable quotient patterns (reviewed next).
A basic mechanism by which homomorphism counts encode substructure statistics is the closure of a pattern under vertex identifications. Given a graph F and a partition π of VF, we form a quotient pattern F/π by contracting each block of π to a single vertex, inheriting labels in the evident way (if labels disagree within a block, the quotient is discarded), and adding an edge between two distinct blocks if there is at least one edge in F between the corresponding vertex sets. Depending on π, one may create loops; loops are irrelevant for our target graphs (which remain simple), but they are convenient for bookkeeping in homomorphism identities. The Spasm(F) is the finite set of quotients F/π up to isomorphism. The standard Möbius inversion on the partition lattice yields that counts of injective homomorphisms (and hence subgraph occurrences) of F can be expressed as an integer linear combination of hom(F′, ⋅) over F′ ∈ Spasm(F), and conversely hom(F, ⋅) is an integer linear combination of injective counts over quotients. For our purposes, it suffices to remember that any homomorphism-preserving representation automatically preserves a large class of subgraph-counting parameters, up to spasm closure.
We work in the color refinement (CR) idealization: node and tuple features are discrete colors updated by perfect hashing of their previous values and aggregated multisets. A k-tuple refinement procedure maintains a color map χ(t) : VGk → 𝒞 on ordered k-tuples, initialized by the isomorphism type of the induced labeled substructure on the tuple coordinates (including equalities among coordinates). Each round produces χ(t + 1)(u) by combining χ(t)(u) with a multiset of colors of neighboring tuples obtained by altering one coordinate. Stabilization yields a canonical stable coloring χ, and a graph-level representation is obtained by taking the multiset of stable colors over all k-tuples (or over a prescribed root set in rooted variants). In the CR model, two graphs are indistinguishable by an architecture if and only if the corresponding stable multisets coincide.
We recall the three refinement operators whose homomorphism families we compare.
k-tuple refinement (also called k-FWL and equivalent, at the level of graph invariants, to k-FGNN) aggregates over all replacements of a single coordinate by an arbitrary vertex w ∈ VG. This is the most expressive of the three and is known to capture precisely homomorphism counts of patterns of treewidth at most k.
(the strong NED model) restricts aggregation to a purely local move: w must lie in the closed neighborhood of the coordinate being replaced, i.e., w ∈ NG[ui] when updating the ith coordinate. This enforces a strict locality that prevents information flow across nontrivial overlaps of distant attachments in a decomposition.
is intermediate: we still replace only one coordinate at a time, but we may choose w from the $\bigcup_{i=1}^k N_G[u_i]$, regardless of which coordinate is replaced. Thus the update can ``teleport’’ a replacement along any coordinate’s neighborhood as long as it remains within the guarded region of the tuple, enabling controlled interactions that are unavailable to Local k-GNN but remain weaker than the global replacements of full folklore refinement. The precise update rule is stated in the next section; here we only emphasize that the distinction between (ii) and (iii) is exactly the source of the additional overlap permitted in our pattern characterizations.
A tree decomposition of a graph F is a pair (T, β) where T is a tree and β : V(T) → 2VF assigns a bag to each node, satisfying the usual vertex-coverage, edge-coverage, and connectedness conditions. The width is maxt ∈ V(T)|β(t)|−1, and tw(F) is the minimum width. For fixed k, we may assume decompositions are in a canonical alternating form: after standard transformations one can enforce that bags have size exactly k or k + 1, that the root bag has size k, and that adjacent bags differ by exactly one vertex. We will use such canonical forms as a convenient interface between tuple refinement dynamics and combinatorial structure: odd-depth bags of size k + 1 will serve as ``attachment events’’ (ears), while even-depth bags of size k serve as separators supporting the guarded locality constraints.
For k = 2, several refinement architectures admit clean characterizations via nested ear decompositions (NEDs). Informally, an NED partitions EF into a sequence of ears attached along endpoints to previously constructed parts, together with a nesting forest recording which ear is attached within which predecessor. The variant (corresponding to strictly local refinement) requires that, for siblings attached to the same parent ear, their attachment intervals along the parent are laminar: two intervals must be disjoint or one contained in the other. This laminarity encodes that local propagation cannot resolve simultaneous ``crossing’’ attachments. The relaxation introduced for guarded folklore-type locality at k = 2 allows a sharply delimited non-laminar overlap when one of the overlapping ears is in the sense that it contributes at most one edge along each relevant branch of the parent, and hence behaves like a locally resolvable perturbation under the guarded update. Our contribution for general k is to lift this strong-versus-degenerate overlap dichotomy from k = 2 to width-k decompositions in a way that is compatible with tuple-coordinate moves and the neighborhood guard. The next section makes the model explicit and formalizes the corresponding homomorphism expressivity families.
Fix k ≥ 2 and a graph G = (VG, EG, ℓG). Local k-FGNN operates on ordered tuples u = (u1, …, uk) ∈ VGk via color refinement in the CR idealization. As usual, the initial color χ(0)(u) encodes the complete isomorphism type of the labeled induced substructure on the coordinates of u, including all equalities ui = uj and adjacencies uiuj ∈ EG for i ≠ j. In particular, χ(0) is invariant under relabeling of VG and under the diagonal action of Aut(G) on VGk.
The defining feature of Local k-FGNN is the choice of replacement
vertices. For a tuple u we set the guarded
region
$$
\Gamma_G(\mathbf{u}) \;:=\; \bigcup_{i=1}^k N_G[u_i],
$$
and for i ∈ [k] and
w ∈ VG
we write
u(i ← w) := (u1, …, ui − 1, w, ui + 1, …, uk).
One refinement round replaces χ(t) by χ(t + 1)
where
Here Hash denotes a perfect injective
encoding of its arguments, and the multiset in is taken over w with multiplicities. The update is
permutation-equivariant in the sense that permuting tuple coordinates
permutes the k-tuple inside
the multiset; this is the CR abstraction of using a shared MLP on
coordinates and a multiset aggregator. We iterate until stabilization,
obtaining a stable coloring χ = χ(∞).
For comparison only (we will not use this operationally), note that Local k-GNN corresponds to the stricter update where, when forming χ(t)(u(i ← w)), one restricts to w ∈ NG[ui] depending on the replaced coordinate, whereas full folklore refinement (k-FWL/k-FGNN) uses w ∈ VG.
The unrooted graph representation induced by Local k-FGNN is the multiset
$$
\Phi_{k}^{\mathrm{LF}}(G)\;:=\;\multiset{\chi(\mathbf{u}) :
\mathbf{u}\in V_G^k},
$$
i.e., the histogram of stable colors over all ordered k-tuples. Two graphs G, H are (in the CR model)
if ΦkLF(G) = ΦkLF(H).
We will also use a rooted variant. A is a pair (G, r) with r ∈ VGk.
Running the same refinement on G yields a rooted
representation
ΦkLF(G, r) := χG(r),
i.e., the stable color of the designated tuple (equivalently, the Dirac
histogram on r). This
is the natural notion for expressing rooted homomorphism counts and for
the unfolding arguments underlying our upper bounds.
We now formalize which homomorphism counts are determined by these representations. For a pattern graph F we view the parameter G ↦ hom(F, G) as a graph invariant. The following definition packages the strongest such invariants captured by Local k-FGNN.
Rooted patterns are treated analogously. A is a pair (F, a) with a ∈ VFk. For a rooted graph (G, r), let hom((F, a), (G, r)) denote the number of homomorphisms f : F → G with f(ai) = ri for all i ∈ [k] (and label/edge preservation as usual). The rooted family ℱLF(k)• is defined by requiring that equality of rooted representations χG(r) = χH(s) implies equality of these rooted counts for all rooted patterns in the family. In the sequel, rooted statements are used as intermediate steps; the unrooted family ℱLF(k) is recovered by summing rooted counts over all roots.
Although our characterization is phrased in terms of homomorphism
counts, it implicitly controls a broad range of substructure statistics.
Recall from the preliminaries that for any pattern F, the spasm Spasm(F) consists of quotients F/π obtained by vertex
identifications, and that injective homomorphism counts (hence subgraph
occurrences) of F can be
expressed by Möbius inversion as an integer linear combination of hom(F′, ⋅) over F′ ∈ Spasm(F),
and conversely. Consequently, whenever Spasm(F) ⊆ ℱLF(k),
Local k-FGNN
indistinguishability implies equality of injective counts of F as well. We will therefore freely
pass between
homomorphism-counting power'' andsubgraph-counting
consequences’’ while remembering that the primitive objects controlled
by the representation are the homomorphism parameters themselves.
In the next section we identify ℱLF(k) by a decomposition property. Operationally, the guarded union ΓG(u) in is precisely what permits certain non-laminar overlap patterns in width-k constructions, and the resulting pattern class strictly interpolates between the strong locality family for Local k-GNN and the full treewidth-k family for k-FWL/k-FGNN.
We now introduce the decomposition notion underlying the maximal pattern family for Local k-FGNN. Throughout, k ≥ 2 is fixed and F is a finite simple vertex-labeled graph.
A is a connected graph Q together with a designated ∂Q ⊆ VQ of size k such that Q admits a width-k tree decomposition whose are exactly the k-sets appearing as intersections of adjacent bags, and every bag has size k or k + 1. Concretely, we require a decomposition (TQ, βQ) with the following canonical features:We view Skel(Q) as a tree whose vertices are k-sets in VQ and whose edges correspond to adjacent k-adhesions mediated by a unique (k + 1)-bag. When k = 2, Skel(Q) is the usual spine for a path-like ear, and the 3-bags are triangles that ``realize’’ edges of the spine.
A (NED) of F is a partition of EF into edge-disjoint k-order ears Q1, …, Qm together with a rooted forest structure on {Qi} (the ) satisfying:Thus an NED builds F by starting from root ears and repeatedly attaching child ears along k-vertex interfaces.
Let Q be a child ear of a
parent ear P. Since ∂Q ⊆ VP,
the attachment vertices occur in bags of the skeleton Skel(P). We define the I(Q) to be the minimal
connected subgraph of Skel(P)
whose union of vertices (as k-sets) contains all attachment
vertices:
I(Q) := SteinerSkel(P)(∂Q),
i.e., the union of all unique simple paths in Skel(P) connecting the bags that
contain the vertices of ∂Q.
Equivalently, I(Q) is
the smallest subtree of Skel(P) that ``supports’’ the
attachment.
To state our relaxation, we distinguish short attachments from genuinely extended ones. A in a tree T is a maximal simple path whose internal vertices have degree 2 in T. We say that a nested interval I(Q) ⊆ Skel(P) is and write degener(I(Q)) if for every branch path π of Skel(P), the intersection I(Q) ∩ π contains at most one edge of π. When Skel(P) is itself a path (the k = 2 intuition), this reduces to the requirement that I(Q) has length at most one edge.
We can now impose a nesting constraint on siblings. Let Qa, Qb
be two distinct child ears of the same parent ear P, and consider their nested
intervals I(Qa), I(Qb) ⊆ Skel(P).
In the variant (corresponding to Local k-GNN), we require the family of
sibling intervals to be laminar:
I(Qa) ∩ I(Qb) = ∅ or I(Qa) ⊆ I(Qb) or I(Qb) ⊆ I(Qa).
In contrast, we define a by relaxing laminarity exactly in the
degenerate case: for siblings Qa, Qb
with a < b, we
require the same laminarity condition that if degener(I(Qa))
holds, then we permit arbitrary overlap between I(Qa)
and I(Qb).
This ``one-sided’’ rule is the form that will match the directed
unfolding used in the completeness proof; it is also equivalent to the
symmetric formulation where overlap without containment is allowed
whenever at least one of the two intervals is degenerate.
We record the qualitative separations induced by this relaxation. First, strong laminarity can fail only in a locality-compatible manner. Consider a parent ear P whose skeleton Skel(P) contains two consecutive edges sharing a vertex (e.g., a path t1 − t2 − t3 of k-bags). Let Qa and Qb be two children with I(Qa) = t1 − t2 and I(Qb) = t2 − t3. Then I(Qa) ∩ I(Qb) = {t2} but neither interval contains the other. If both I(Qa) and I(Qb) are degenerate (as they are here), the configuration is permitted by k-almost-strong NEDs but forbidden by strong NEDs. This yields patterns in ℱLF(k) \ ℱL(k) by attaching two ears ``meeting at a point’’ inside the parent skeleton.
Second, k-almost-strong NEDs do not cover all of treewidth k. Let Skel(P) contain a path on four k-bags t1 − t2 − t3 − t4. Choose two children Qa, Qb with intervals I(Qa) = t1 − t2 − t3 and I(Qb) = t2 − t3 − t4. These intervals overlap on the two vertices t2, t3 (and the edge between them), neither contains the other, and neither is degenerate (each occupies two edges along the same branch path). Such a pattern can still have tw(F) ≤ k (it is realizable by gluing (k + 1)-bags along k-adhesions in a standard partial k-tree), but it violates the k-almost-strong sibling rule. Hence it witnesses ℱLF(k) ⊊ ℱF(k).
We will show next that admitting a k-almost-strong NED is not merely sufficient but exactly the correct criterion for being counted by Local k-FGNN in the homomorphism sense.
We show that the stable Local k-FGNN representation of a graph G determines hom(F, G) for every pattern F admitting a k-almost-strong NED. The proof proceeds in three steps: we (i) identify tuple colors with isomorphism types of a canonical guarded unfolding, (ii) extract from the graph representation the counts of relevant unfolding types (``bag-isomorphism counts’’), and (iii) express hom(F, G) as a fixed linear combination of these counts.
Fix t ≥ 0 and an ordered k-tuple u = (u1, …, uk) ∈ VGk. We define a rooted, edge-labeled tree 𝒰G(t)(u) whose nodes represent the k-tuples reachable from u by at most t guarded folklore moves. Concretely, the root is labeled by u, and from any node labeled by a tuple x = (x1, …, xk) we add, for each $w\in \bigcup_{i=1}^k N_G[x_i]$ and each coordinate index j ∈ [k], a child node labeled by the tuple obtained from x by replacing xj with w; we label the tree edge by j to record which coordinate was replaced. Each node additionally carries the full atomic type of its tuple in G (vertex labels, equality pattern among coordinates, and adjacency pattern among coordinates). We then quotient this rooted tree by identifying nodes whose labeled rooted subtrees are isomorphic in the natural sense (root-preserving, respecting edge labels and node atomic types), yielding a canonical finite object that we still denote by 𝒰G(t)(u).
The key inductive correspondence is that tuple colors are precisely
these unfolding types. Namely, letting χ(t) be the
t-round Local k-FGNN coloring, we have
χ(t)(u) = IsoType(𝒰G(t)(u)),
where IsoType(⋅) denotes the
perfect-hash code of the rooted isomorphism type. The base case t = 0 is immediate from the
initialization by atomic type. For the step t → t + 1, the multiset
aggregated at u in the
Local k-FGNN update is exactly
the multiset of isomorphism types of the one-step children unfoldings of
the root of 𝒰G(t + 1)(u),
grouped by the coordinate label j; since the update hashes the
previous color together with this guarded multiset, it coincides with
hashing the rooted tree one level deeper. Stabilization implies that
χ(u)
determines the isomorphism type of 𝒰G(t)(u)
for all t up to the
stabilization depth (and conversely).
We take the graph-level representation of Local k-FGNN to be the multiset
(equivalently, histogram) of stable colors on VGk.
Thus, if two graphs G, H have identical
representations, then for every stable color α,
|{u ∈ VGk : χG(u) = α}| = |{v ∈ VHk : χH(v) = α}|.
Choosing t larger than the
stabilization index for both graphs, we may replace χ by χ(t) without
changing these multiplicities, and therefore we obtain equality of
counts of depth-t unfolding
isomorphism types.
It is convenient to package these counts as follows. Let 𝔘t be the finite set of
rooted isomorphism types of unfoldings 𝒰G(t)(u)
realizable over all graphs G
(with the fixed label alphabet) and all tuples u ∈ VGk.
For U ∈ 𝔘t, define
the
bIsoHom(U, G) := |{u ∈ VGk : 𝒰G(t)(u) ≅ U}|.
By the unfolding–color correspondence, bIsoHom(U, G) is determined
by the Local k-FGNN
representation of G. In
particular, representation equality for G, H implies bIsoHom(U, G) = bIsoHom(U, H)
for all U ∈ 𝔘t.
Now fix a pattern F admitting a k-almost-strong NED. Using the NED, we obtain a rooted tree of k-order ears; for each ear we fix a canonical width-k decomposition with bag sizes in {k, k + 1} and adhesions of size k. Gluing these ear decompositions along their attachment k-sets yields a tree-structured decomposition of F whose nodes alternate between k-bags (interfaces) and (k + 1)-bags (realizing one additional vertex), and whose child ordering is compatible with the almost-strong sibling rule. The crucial consequence of the sibling rule is that when we compute extensions of partial homomorphisms from a parent interface to several children, the dependencies created by overlapping nested intervals are either laminar (hence handled by standard tree-decomposition dynamic programming) or confined to degenerate overlaps, which are resolved by a single guarded folklore move (replacing at most one skeleton edge along any branch path) and therefore remain visible in the local unfolding around the interface tuple.
We implement this by a bottom-up dynamic program on the decomposition tree of F. Each k-bag corresponds to an ordered k-tuple of pattern vertices; for a graph G and a tuple u ∈ VGk, we let Φt(u) denote the number of partial homomorphisms from the subpattern rooted at the bag to G that map the ordered interface to u. Transition from a k-bag to an adjacent (k + 1)-bag introduces exactly one new pattern vertex, say x, together with its adjacencies to the k interface vertices; the number of possible images of x in G depends only on the multiset of one-coordinate replacements (u1, …, uj − 1, w, uj + 1, …, uk) with w ∈ ⋃iNG[ui], because locality-guarded folklore aggregation ranges precisely over this set. Hence the transition value is a function of the depth-1 unfolding neighborhood of u, and by iteration each Φt(u) is a function of the depth-D(F) unfolding 𝒰G(D(F))(u), for a depth D(F) depending only on F.
Summing over all interface tuples at the root bag yields
hom(F, G) = ∑u ∈ VGkΦroot(u) = ∑U ∈ 𝔘D(F)λF, U bIsoHom(U, G),
for coefficients λF, U ∈ ℤ
depending only on F (they are
obtained by evaluating the same dynamic program on the abstract
unfolding type U rather than
on a concrete tuple). This is the promised linear-algebraic
factorization: the Local k-FGNN representation determines
bIsoHom(U, G) for all
relevant U, hence determines
hom(F, G).
If two graphs G, H have identical Local k-FGNN representations, then bIsoHom(U, G) = bIsoHom(U, H) for all U ∈ 𝔘D(F), and therefore the above linear identity gives hom(F, G) = hom(F, H) for every k-almost-strong pattern F. In the next step we make the decomposition implicit in the argument explicit by introducing a canonical restricted width-k tree decomposition class 𝒮LF(k) and proving its equivalence to k-almost-strong NEDs.
We make the decomposition implicit in the unfolding argument explicit by isolating a canonical class 𝒮LF(k) of width-k tree decompositions that captures exactly the structural constraints enforced by neighborhood-guarded folklore aggregation. The equivalence is bidirectional: a pattern F admits a k-almost-strong NED if and only if F has a canonical alternating tree decomposition (F, T) ∈ 𝒮LF(k). Since both objects are used in subsequent upper- and lower-bound arguments, we state the construction in a form that exposes the invariants needed for dynamic programming and for the pebble-game/gadget lower bound.
We work with rooted tree decompositions whose bags alternate in size between k and k + 1. Concretely, we require that every edge of T connects a P with |P| = k to an B with |B| = k + 1, and that P ⊂ B with |B \ P| = 1. We root T at a separator bag and impose that each extension bag has a unique parent separator bag. This is a standard normal form for width-k decompositions: for fixed k one may convert any width-k decomposition into such an alternating one by subdividing edges and by inserting forget/introduce nodes while preserving the represented graph.
What is specific to Local k-FGNN is an additional controlling
how extension bags may branch. Intuitively, an extension bag B = P ∪ {x}
introduces a new vertex x
adjacent (in F) to some subset
of the k vertices in P. If x is not adjacent to any vertex of
P, then any further structure
attached
below'' $B$ must be essentially linear (unique continuation), because Local $k$-FGNN can only access new vertices through neighborhood moves from the interface tuple; without an adjacency witness in $P$, independent branching would create correlations not visible in guarded unfoldings. More generally, when $x$ is adjacent to some vertices of $P$, a bounded amount of branching is allowed, but overlaps among descendants must be laminar except in the degenerate cases singled out in the definition of $k$-almost-strong NEDs. We encode this by requiring that, for each extension bag $B$ with parent $P$, the separator-bag children of $B$ can be linearly ordered so that their induced attachment intervals on theskeleton’’
determined by P are laminar,
except that non-laminar overlap is permitted precisely when the
corresponding interval is degenerate (i.e., along every branch path in
the parent ear it contributes at most one edge). The formalization is
most transparent after we explain the conversion to ears.
Assume (F, T) ∈ 𝒮LF(k). We construct an ear decomposition by interpreting each extension bag B = P ∪ {x} as the introduction of a single new vertex x together with its incident edges to the current interface P. Consider the rooted traversal of T alternating between separator bags and extension bags. For each extension bag B with parent separator P, we create a k-order ear Q(B) whose endpoints are the ordered k-tuple of vertices of P (the interface) and whose internal vertex set contains x and, recursively, all vertices introduced in the subtree rooted at B that are not already present above P. The ear edges are the edges of F that are first covered in some descendant extension bag of B but not covered above P. Standard connectedness properties of tree decompositions guarantee that these edge sets partition EF, and the rooting induces a nesting forest of ears.
We now verify the sibling constraint required for a k-almost-strong NED. Let B1, B2 be two distinct extension bags with the same parent separator bag P and let Q1 = Q(B1), Q2 = Q(B2) be the associated ears. The associated nested intervals I(Q1), I(Q2) are determined by the positions (within the parent ear) at which the attachments to P occur. The locality-guarded child constraint in 𝒮LF(k) ensures that the induced intervals are either disjoint or nested, except when one of them is degenerate, in which case overlap without containment is allowed. This is exactly the ``almost-strong’’ relaxation: non-laminar overlap is confined to attachments that, along each branch path of the parent ear, modify at most a single skeleton edge and can therefore be simulated by a single guarded folklore move from the interface tuple. Hence the resulting ear nesting satisfies the definition of a k-almost-strong NED.
Conversely, assume F admits a k-almost-strong NED with ears Q1, …, Qm forming a nesting forest. We build a tree decomposition T by expanding each ear into an alternating chain of bags and then gluing these chains according to nesting. Fix an ear Q with attachment interface S(Q) of size k (viewed as an ordered k-tuple) and with internal vertices introduced by Q. We construct a path in T alternating between copies of the separator bag S(Q) and extension bags S(Q) ∪ {x} for each newly introduced vertex x in the ear, ordered along the ear. This guarantees that every edge introduced by Q is covered by some extension bag: if x is adjacent to a subset of S(Q), then S(Q) ∪ {x} contains that edge; edges between consecutively introduced vertices are covered by adjacent extension bags in the chain (using the standard introduce/forget simulation inside width k). For each child ear Q′ nested in Q, we attach the decomposition of Q′ at the separator bag corresponding to the interface S(Q′) ⊆ V(Q), which occurs along the chain of Q at the position determined by the nested interval I(Q′).
The crucial point is that the sibling rule in the NED implies the locality-guarded child constraint of 𝒮LF(k). Indeed, siblings Qa, Qb nested under the same parent ear Q have intervals that are laminar except for degenerate overlaps; we choose the child ordering at each separator bag to respect the partial order induced by containment of intervals, and we route degenerate-overlap cases through a unique extension node where the overlap occurs. Because degeneracy ensures that the overlap affects at most one edge along any branch path, this routing does not create the forbidden ``branching without adjacency witness’’ configuration: whenever an extension bag introduces a vertex non-adjacent to the parent separator, it lies on a unique continuation segment and has exactly one relevant child, matching the guarded constraint.
Both transformations preserve the following properties, which we will use subsequently without further comment. First, every edge of F is covered by an extension bag (equivalently, by some ear), so the constructions are lossless at the level of the pattern graph. Second, adhesions are exactly k-sets, so interfaces in the decomposition correspond bijectively to the ordered attachment tuples tracked by Local k-FGNN. Third, the only permitted violations of laminarity among sibling attachments are precisely the degenerate overlaps; these are tight in the sense that any additional non-degenerate overlap would force two independently branching subpatterns to share a nontrivial boundary segment, creating dependencies that cannot be resolved by a bounded-depth neighborhood-guarded unfolding around the interface tuple. Therefore 𝒮LF(k) is not merely a convenient normal form: it is the exact structural envelope of patterns whose homomorphism counts factor through Local k-FGNN tuple colors.
We establish the converse direction needed for maximality: whenever a connected pattern graph F does admit a k-almost-strong NED (equivalently, by Theorem~2, whenever F admits no canonical alternating decomposition in 𝒮LF(k)), Local k-FGNN cannot determine hom(F, ⋅) from its stable tuple colors. Concretely, we construct a pair of graphs G(F), H(F) such that Local k-FGNN produces identical stabilized representations on G(F) and H(F), yet hom(F, G(F)) ≠ hom(F, H(F)). This implies that ℱLF(k) is maximal among all homomorphism families factoring through Local k-FGNN.
We use a pebble game tailored to the neighborhood-guarded folklore aggregation. A position consists of two ordered k-tuples u ∈ VGk and v ∈ VHk. The game is played in rounds; in each round Spoiler chooses an index i ∈ [k] and a vertex $w\in \bigcup_{j=1}^k N_G[u_j]$, and replaces ui by w, yielding a new tuple u′. Duplicator must respond by choosing $w'\in \bigcup_{j=1}^k N_H[v_j]$ and replacing vi by w′, yielding v′. The winning condition is the usual local consistency with labels and equalities: Duplicator must maintain that the map ua ↦ va preserves vertex labels and the edge/non-edge relations among the pebbled vertices (i.e., it is a partial isomorphism on the induced labeled subgraphs on the sets {u1, …, uk} and {v1, …, vk}). As in standard WL–pebble correspondences, one proves by induction on the number of rounds that Duplicator has a winning strategy for D rounds starting from (u, v) if and only if the depth-D guarded unfoldings around u and v are isomorphic, and hence if and only if χ(D)(u) = χ(D)(v) under Local k-FGNN refinement. In particular, if Duplicator can win for all D, then χ(u) = χ(v) in the stabilized coloring.
Assume F is connected and does not admit a k-almost-strong NED. By Theorem~2, no canonical alternating decomposition of F satisfies the locality-guarded child constraint; unpacking this failure yields a specific forbidden configuration in any attempted decomposition: there exist sibling attachments whose induced nested intervals overlap in a way (overlap without containment, and on some branch path contributing at least two edges). We fix a minimal such obstruction (under subgraph inclusion respecting the attempted nesting), and we view it as a cycle of constraints between interface choices along a parent ear skeleton. This cycle is the higher-order analogue of the parity-obstruction exploited in CFI/F"urer lower bounds: locally each attachment is consistent with guarded neighborhood moves from a k-tuple interface, but globally the non-degenerate overlap forces a dependency that cannot be linearized into the laminar/degenerate structure of 𝒮LF(k).
From the obstruction we build a pair of graphs G(F) and H(F) that are locally indistinguishable but globally twisted. We replace each relevant interface (separator of size k) by a encoding 2k states, conveniently indexed by bit-vectors in {0, 1}k (or equivalently subsets of [k]), and we connect clouds by bipartite constraint gadgets whose adjacency depends only on the symmetric difference of the indices. All vertices carry labels identifying their cloud and their role (interface position), so that the tuple initialization χ(0) cannot break the intended symmetry inside a cloud. The graph G(F) is the instance in which the constraints along the obstruction cycle are consistent. The graph H(F) is obtained by flipping (twisting) exactly one constraint gadget along the cycle (or, more generally, by applying an odd-parity twist on a set of edges whose sum is 1 in the constraint space). As in classical constructions, G(F) and H(F) are non-isomorphic but are designed to be indistinguishable by any refinement whose view is restricted to bounded-depth, locally guarded explorations from a k-tuple.
We argue via the guarded k-pebble game. Duplicator maintains an invariant that pebbled vertices in G(F) and H(F) lie in corresponding clouds, and that the current correspondence respects the local constraint structure within the explored neighborhood determined by ⋃iN[⋅]. When Spoiler moves to a vertex in the guarded neighborhood, the move crosses at most one constraint gadget from some currently pebbled cloud; by construction, each constraint gadget in G(F) is locally isomorphic to the corresponding gadget in H(F) (the twist is not detectable from one side without traversing a global cycle). Hence Duplicator can respond by applying the appropriate local isomorphism of the relevant gadget, preserving the partial isomorphism on the pebbled set. Iterating, Duplicator wins for all finite numbers of rounds; consequently χ(u) = χ(v) for corresponding tuples and the induced graph-level Local k-FGNN representations of G(F) and H(F) coincide. Equivalently, all guarded unfoldings that lie in 𝒮LF(k) occur with the same multiplicities in both graphs.
It remains to show hom(F, G(F)) ≠ hom(F, H(F)). A homomorphism h : F → G(F) (resp. H(F)) induces, on each interface of size k, a choice of a cloud state in {0, 1}k, and the edges of F crossing between interfaces enforce the corresponding gadget constraints. Because the obstruction in F is non-degenerate, these constraints form a genuine cycle of dependencies whose satisfaction requires global parity consistency. In G(F) the cycle is consistent and yields a positive number of satisfying assignments, hence a positive contribution to hom(F, G(F)). In H(F) the single twist flips the parity on the cycle, making the system inconsistent (or, in the variant where some slack remains, changing the number of satisfying assignments by a nonzero amount); thus the contribution of the corresponding mapping type is eliminated (or altered), yielding hom(F, G(F)) ≠ hom(F, H(F)). If needed to prevent spurious homomorphisms that avoid the intended constraint cycle, we apply standard rooted/clique augmentation: we attach labeled anchor structures forcing any homomorphism of F to map designated vertices into designated clouds, thereby isolating the separating contribution without affecting Local k-FGNN indistinguishability.
We have therefore produced, for every connected F ∉ ℱLF(k), a witness pair G(F), H(F) that Local k-FGNN cannot distinguish but that hom(F, ⋅) separates. This proves Theorem~4 and yields the maximality of ℱLF(k) among homomorphism families captured by Local k-FGNN.
We next justify the strictness of the inclusions
ℱL(k) ⊊ ℱLF(k) ⊊ ℱF(k).
By Theorem~1, membership in ℱL(k) is equivalent to
admitting a k-order NED
(laminar nesting of sibling intervals, i.e., overlap implies
containment), while membership in ℱLF(k) is equivalent to
admitting a k-almost-strong
NED (laminarity except that overlaps are permitted). Finally, ℱF(k) is characterized by
treewidth at most k. Hence it
suffices to exhibit two explicit pattern families: one witnessing that
allowing degenerate overlaps strictly enlarges the family beyond strong
NED, and another witnessing that forbidding non-degenerate overlaps
still excludes some width-k
graphs.
Fix k ≥ 2. We define a
connected pattern Fkdeg
of treewidth k that admits a
k-almost-strong NED but no
strong k-order NED. Consider a
parent k-ear Q0 whose underlying
``skeleton’’ consists of two internally vertex-disjoint branch paths
between the same k-vertex
interface S = {s1, …, sk}
(formally, Q0 is
obtained by taking two length-2 paths
between two distinct vertices of S and distributing the remaining
vertices of S as trivial
attachments so that the ear has boundary S). Now attach two child k-ears Q1, Q2
to Q0 as siblings,
each with the same boundary S,
but with nested intervals I(Q1), I(Q2)
chosen so that:
(i) they overlap on the parent ear in the sense that I(Q1) ∩ I(Q2) ≠ ∅
and neither contains the other; and
(ii) the overlap is in the sense of Theorem~1, namely, on every branch
path of Q0 the
restriction of I(Q1) (and
likewise of I(Q2))
contributes at most one edge.
Concretely, we realize this by letting I(Q1) use one
edge on the first branch path and none on the second, while I(Q2) uses one
edge on the second branch path and none on the first, and arranging that
both intervals share a single boundary vertex in S.
By construction, the sibling overlap is non-laminar but degenerate, hence permitted in a k-almost-strong NED; taking Q0, Q1, Q2 (and completing to a full ear partition by adding trivial ears for remaining edges) yields a valid k-almost-strong NED of Fkdeg, so Fkdeg ∈ ℱLF(k). On the other hand, any strong k-order NED would require that sibling intervals be laminar, i.e., overlap implies containment. Since the overlap is witnessed already at the level of the parent ear skeleton and is forced by the attachment pattern of Q1, Q2 (both require the same interface but different branch usage), there is no refinement of the decomposition that can eliminate the overlap without changing the ear boundaries or introducing a non-sibling relation that contradicts the ear partition. Thus Fkdeg ∉ ℱL(k), proving the first strict inclusion.
We next define a connected width-k pattern Fkndeg that fails to admit any k-almost-strong NED. The guiding principle is to force an overlap of sibling nested intervals that is (i.e., on some branch path of the parent ear the overlap necessarily spans at least two edges), while keeping the graph a partial k-tree. One convenient family is obtained from a canonical width-k tree decomposition of a partial k-tree by creating a ``diamond’’ of two sibling (k + 1)-bags whose introduced vertices must both interact along a length- ≥ 2 segment of the parent skeleton. Equivalently, we take a parent k-ear Q0 with a branch path of length at least 3 between two boundary vertices in S, and attach two sibling ears Q1, Q2 that both require the same two consecutive edges of this branch path to realize their internal adjacency constraints; then I(Q1) and I(Q2) overlap on at least two edges of that branch path, yet neither interval contains the other (each also uses a distinct additional edge elsewhere to prevent containment).
This enforces a forbidden configuration for k-almost-strong NEDs: we obtain sibling intervals with overlap without containment, and the overlap is non-degenerate. By Theorem~1, such a pattern cannot lie in ℱLF(k). However, the construction may be implemented within a width-k tree decomposition by ensuring that every new vertex is introduced in a (k + 1)-bag adjacent to a k-bag separator S, and that the only additional edges are those covered by these bags; hence tw(Fkndeg) ≤ k, so Fkndeg ∈ ℱF(k). This proves the second strict inclusion.
The two witnesses translate immediately into separations between the corresponding refinement procedures. Since Fkdeg ∈ ℱLF(k) \ ℱL(k), there exist graphs G, H such that Local k-FGNN representations distinguish G and H (because hom(Fkdeg, G) ≠ hom(Fkdeg, H) is detectable by Theorem~3), while Local k-GNN representations coincide (since all homomorphism counts from patterns in ℱL(k) coincide). Likewise, because Fkndeg ∈ ℱF(k) \ ℱLF(k), we obtain graphs G′, H′ that are indistinguishable by Local k-FGNN yet distinguishable by k-FWL/k-FGNN (as k-FWL captures all width-k patterns). These implications are made formal by the standard ``pattern-to-counterexample’’ transfer: a strict inclusion between homomorphism families yields a pair of graphs separated by one model but not the other.
Although our main focus is graph-level representations, the same witness patterns yield local separations at the level of tuple and vertex features. Indeed, from Fkdeg one obtains graphs in which some k-tuple orbit is refined by Local k-FGNN but remains merged under Local k-GNN, and from Fkndeg one obtains graphs where some k-tuple colors differ under k-FWL but are equal under the guarded folklore refinement. In particular, any downstream node/edge prediction architecture that reads out stabilized tuple colors inherits these separations under exact readout.
The structural characterization by k-almost-strong NEDs immediately yields an effective membership test for fixed k. Concretely, given a connected pattern F and fixed k ≥ 2, we may decide whether F ∈ ℱLF(k) by searching for a width-k tree decomposition and then checking the additional locality-guarded constraints defining 𝒮LF(k) (Theorem~2). Using standard FPT algorithms for treewidth (e.g., Bodlaender-type routines), we can either (i) return that tw(F) > k, in which case F ∉ ℱF(k) and thus F ∉ ℱLF(k), or (ii) produce a width-k decomposition T of F. We then normalize T into the canonical alternating form with bags of size k and k + 1 (by the usual introduce/forget normalization and splitting), and finally verify the child-structure constraint that distinguishes 𝒮LF(k) from arbitrary width-k decompositions: each odd-depth bag B of size k + 1 with parent separator P of size k may have multiple children only when the newly introduced vertex in B \ P is ``locally guarded’’ by adjacency to the separator in the sense required by the neighborhood-guarded folklore aggregation; in the unguarded case, the bag is forced to have essentially a single continuation. By Theorem~2, F admits a k-almost-strong NED if and only if such a canonical decomposition exists; therefore, acceptance is equivalent to F ∈ ℱLF(k).
For fixed k, the above test runs in time O(f(k) ⋅ |VF|): computing a width-k decomposition is linear-time FPT in |VF| with parameter k, and the subsequent normalization and constraint checking are linear in the size of the decomposition. Moreover, the procedure is certifying. If it accepts, we can explicitly output a k-almost-strong NED by converting each odd-depth (k + 1)-bag into a k-ear whose boundary is the parent k-bag separator, and ordering sibling ears according to the partial order induced by their nested intervals. The constraint check guarantees that siblings overlap only in the permitted degenerate manner, so the resulting ear family is a valid k-almost-strong NED. If the test rejects, it returns either (a) a certificate that tw(F) > k, or (b) a width-k decomposition in canonical form together with a local witness to constraint violation (an offending odd-depth bag and two children whose overlap cannot be routed through the permitted degeneracy). In particular, while the definition of k-almost-strong NED is global, failure is locally checkable in the decomposition view.
The preceding algorithmic statement crucially treats k as fixed. If k is part of the input, then even deciding tw(F) ≤ k is NP-complete, and since ℱLF(k) ⊆ ℱF(k) = {F : tw(F) ≤ k}, membership in ℱLF(k) is NP-hard in the same regime. Thus the appropriate algorithmic interpretation is the one relevant for architecture design: for each fixed tuple order k, membership is efficiently decidable and yields an explicit decomposition certificate that can be used downstream (e.g., to select motif families that the model can in principle count).
We next connect the family ℱLF(k) to classical
relationships between homomorphism counts and subgraph counts. For a
pattern F, write inj(F, G) for the number of
injective homomorphisms F ↪ G (equivalently,
labeled subgraph embeddings), and sub(F, G) = inj(F, G)/|Aut(F)|
for the number of (unlabeled) subgraphs isomorphic to F. It is well known that inj(F, ⋅) can be expressed as a
finite integer linear combination of homomorphism counts over the of
F, i.e.,
inj(F, G) = ∑H ∈ Spasm(F)μ(F, H) ⋅ hom(H, G),
where Spasm(F) consists of all
homomorphic images H of F obtained by identifying vertices
(equivalently, quotienting F
by a partition compatible with edges), and μ(F, H) ∈ ℤ are
coefficients given by Möbius inversion on the partition lattice
restricted to valid quotients. Consequently, any representation that
determines hom(H, G)
for all H ∈ Spasm(F)
also determines inj(F, G), and hence sub(F, G).
Combining this with Theorem~3 yields a clean sufficient condition for
subgraph-count expressivity of Local k-FGNN: if
Spasm(F) ⊆ ℱLF(k),
then the stabilized Local k-FGNN representation determines
inj(F, G) (and thus
sub(F, G)) for every
host graph G. Indeed, equality
of representations implies equality of hom(H, ⋅) for all H ∈ ℱLF(k),
hence for all H ∈ Spasm(F) under the
inclusion; applying the linear relation above gives equality of inj(F, ⋅). In this sense, the
algorithmic membership test extends to a for motif-counting tasks: for
fixed k and a target motif
F, enumerate Spasm(F) (feasible for the small
motifs typically used in experiments), run the fixed-k recognition test on each H ∈ Spasm(F), and accept
the task as expressible whenever all quotients pass. This screening is
conservative (it is sufficient, not claimed necessary), but it matches
the standard homomorphism–embedding calculus used in subgraph counting
complexity.
For constant-size motifs, Spasm(F) has constant size (at most the Bell number in |VF|), so the above screening incurs negligible overhead compared to model training. Thus, for each fixed k, we obtain an explicit, checkable catalogue of motifs whose counts are in principle recoverable from Local k-FGNN representations: all motifs F whose spasm stays within the k-almost-strong NED family. This gives a concrete algorithmic interface between the structural theory (decompositions and maximality) and empirical evaluation (motif counting benchmarks), and it also clarifies where separations should manifest: whenever Spasm(F) contains a non-member of ℱLF(k), Theorem~4 supplies indistinguishable host graphs on which sub(F, ⋅) differs, so no method based solely on the Local k-FGNN stable representation can succeed uniformly on that motif.
We include an experimental validation layer whose role is not to improve the theory, but to verify that the structural boundary ℱL(k) ⊊ ℱLF(k) ⊊ ℱF(k) manifests in concrete motif-counting tasks at small tuple orders. The guiding prediction is as follows: for a motif F whose Spasm(F) lies inside ℱLF(k), the stabilized Local k-FGNN representation should suffice to recover sub(F, ⋅), whereas for motifs whose spasm crosses the boundary, we should observe systematic failures on adversarially chosen hosts and degraded accuracy on generic hosts. We focus on k = 3, 4 since these are the smallest orders for which nontrivial separations already occur while remaining computationally feasible for tuple-based refinements.
Rather than hand-picking patterns, we select motifs by an explicit
screening pipeline that mirrors the theoretical definitions. We
enumerate connected unlabeled graphs F on at most 9 vertices (and bounded maximum degree to
control spasm growth), compute Spasm(F) by enumerating partitions
of VF and
filtering valid quotients, and then run the fixed-k recognition test (via canonical
width-k decomposition and
𝒮LF(k) constraints)
on each H ∈ Spasm(F).
This yields three disjoint motif pools:
ℳ1 ⊆ ℳ2 ⊆ ℳ3,
where ℳ1 consists of motifs
whose entire spasm lies in ℱL(k) (strong NED), ℳ2 consists of motifs with Spasm(F) ⊆ ℱLF(k)
but Spasm(F) ⊈ ℱL(k)
(witnessing the strict left inclusion), and ℳ3 consists of motifs with Spasm(F) ⊆ ℱF(k)
but Spasm(F) ⊈ ℱLF(k)
(witnessing the strict right inclusion). In particular, ℳ2 contains motifs whose
decompositions exhibit the permitted ``degenerate sibling overlap’’
phenomenon, while ℳ3
contains motifs of treewidth at most k whose decompositions require
non-degenerate overlap forbidden by k-almost-strong NEDs.
We evaluate on two complementary host families. First, we generate generic hosts G from standard random graph models (Erds–R'enyi with varying edge density, and Barab'asi–Albert with varying attachment parameter), with |VG| between 50 and 300 to test extrapolation beyond the motif size regime. Second, for each motif F in ℳ3, we additionally generate the separating pair G(F), H(F) promised by the maximality theorem (twisted F"urer-type gadgets, optionally with rooted/clique augmentations to match the locality guards), and we also consider mildly perturbed variants obtained by attaching identical random trees to corresponding vertices. The latter perturbations are useful empirically: they preserve the intended indistinguishability by Local k-FGNN up to the guarded aggregation radius, while preventing accidental shortcut solutions based on trivial size statistics.
We compare three representations at fixed k: (i) Local k-GNN (neighborhood-guarded, but with the strong NED expressivity boundary), (ii) Local k-FGNN (the guarded folklore aggregation analyzed here), and (iii) k-FGNN/k-FWL (the unguarded folklore refinement on k-tuples, corresponding to treewidth ≤ k). To avoid conflating expressivity with optimization artifacts, we report two modes. In a mode, we run the corresponding color refinement exactly (using perfect hashing of multisets) and use the stabilized multiset of tuple colors as a graph representation. In a mode, we implement each update by an MLP applied to (previous feature, aggregated multiset summary) and train a downstream regressor for the target sub(F, G); we keep depth and hidden dimension fixed across models, and we use identical readout (sum pooling over tuple features, then an MLP) to isolate the effect of the refinement operator. Performance is measured by mean absolute relative error and by exact agreement on the adversarial pairs (G(F), H(F)).
The results align with the predicted inclusions. For motifs in ℳ1, all three models succeed: the symbolic representations determine the counts up to numerical inversion of the standard linear systems, and the learned models fit with low relative error and stable generalization as |VG| grows. For motifs in ℳ2, we observe the characteristic strict separation between Local k-GNN and Local k-FGNN: Local k-FGNN matches k-FGNN in accuracy (often to within training noise in the learned mode), while Local k-GNN exhibits persistent bias that does not vanish with additional depth. This is consistent with the fact that ℳ2 contains motifs whose counting requires precisely the degenerate-overlap flexibility built into k-almost-strong NEDs.
For motifs in ℳ3, we observe the opposite separation: k-FGNN succeeds, while both local models fail in a way that is most clearly visible on the adversarial pairs. Concretely, in the symbolic mode, Local k-FGNN yields identical stabilized color multisets on G(F) and H(F), while k-FGNN separates them; correspondingly, the true values of sub(F, G(F)) and sub(F, H(F)) differ. In the learned mode, the local models are forced into identical predictions on G(F) and H(F) up to optimization tolerance, even when trained with these pairs in the training set, whereas the k-FGNN model can fit the difference. This behavior provides an empirical witness of maximality: outside ℱLF(k), failure is not merely a matter of insufficient depth or capacity but is induced by indistinguishability at the level of the stable local refinement.
Our main contribution is structural: we identify the maximal homomorphism-counting family ℱLF(k) captured by the stabilized Local k-FGNN refinement, and we express this family via k-almost-strong nested ear decompositions (equivalently, via the restricted canonical class 𝒮LF(k)). Several directions remain open, and we single out those that appear most immediate from the viewpoint of both theory and practice.
All statements in the present work are made under the CR idealization in which the update map computes an injective hash of the aggregated multiset. In implementation, one replaces hashing by a learned, finite-dimensional, continuous map (typically an MLP composed with sum/mean pooling). A first problem is to make precise when such a learned Local k-FGNN is with the symbolic model: namely, whether for every pair (G, H) that are separated by the symbolic refinement at some bounded number of rounds, there exists a choice of weights and a dimension d for which the learned network separates them as well. This is a universal-approximation question for permutation-equivariant multiset maps with inputs drawn from tuple-features, but with the additional complication that the multiset is indexed by the guarded domain ⋃iNG[ui] and that the features are themselves endogenously produced by the refinement. Even for k = 2 this closes only partially with existing results on DeepSets-type architectures. We view a satisfactory answer as requiring (i) a quantitative separation margin for symbolic colors, and (ii) a stability statement showing that continuous approximations preserve the induced partition of tuples on the relevant graph classes.
The Local k-FGNN update is already a sparse operator in the sense that it aggregates only over ⋃iNG[ui]. A natural generalization in modern architectures is to replace the symmetric multiset map by attention, allowing tuple-dependent weights and possibly multiple heads. One may define a by setting, for each u ∈ VGk and each coordinate position j, an attention distribution over w ∈ ⋃iNG[ui] based on a score function of (χ(t)(u), χ(t)(u(j ← w))), and then updating χ(t + 1)(u) from the resulting weighted sums. Two questions are immediate. First, does guarded attention strictly increase expressivity over multiset aggregation when the attention scores are learned but remain permutation-equivariant? One might suspect a negative answer at the level of distinguishing power, since attention is still a continuous pooling and thus cannot simulate an injective multiset hash uniformly; yet it may strictly improve sample efficiency for estimating the homomorphism-derived statistics that underlie ℱLF(k). Second, if one allows attention to query vertices beyond ⋃iNG[ui] through multi-hop key/value construction (while keeping a single refinement round), does one recover any portion of the global k-FWL power, or does the guardedness enforce a hard boundary akin to ℱLF(k)? Formalizing these questions suggests introducing a hierarchy indexed by the allowed guard radius and studying the induced pattern families.
Theorem~3 is exact: equality of stable representations implies equality of hom(F, ⋅) for all F ∈ ℱLF(k). In learning, one rarely observes exact equality, but rather small ℓ2 or cosine distances between graph embeddings. This motivates an counterpart: if two graphs have embeddings within ε, can we bound |hom(F, G) − hom(F, H)| for F ∈ ℱLF(k) in terms of ε and |VG|,|VH|? Conversely, for F ∉ ℱLF(k), can we construct indistinguishable pairs with a in hom(F, ⋅) that persists under small perturbations of the refinement map? A robust version of Theorem~4 would explain empirically observed ``near-failures’’ where a learned model appears to partially correlate with sub(F, ⋅) even though exact determination is impossible. Achieving such robustness likely requires explicit Lipschitz control of the update and a quantitative analysis of the gadget constructions.
The strict inclusions in Theorem~5 are witnessed by explicit motifs,
but we do not currently know the minimal order of such witnesses as a
function of k. Let
skleft = min {|VF| : F ∈ ℱLF(k) \ ℱL(k)}, skright = min {|VF| : F ∈ ℱF(k) \ ℱLF(k)}.
Determining or bounding skleft, skright
would sharpen the experimental screening pipeline and would also clarify
the intrinsic ``distance’’ between locality-guarded folklore and
unguarded folklore at fixed k.
More structurally, it is natural to ask whether ℱLF(k) admits a
characterization by a finite set of forbidden overlap patterns in
canonical decompositions (or, in ear language, a finite obstruction set
for non-degenerate sibling overlap). Such a result would resemble
minor-type characterizations for bounded treewidth, but the overlap
predicate degener(⋅) suggests that the
obstruction theory here may be more delicate and potentially
infinite.
The refinement studied here is local in a precise game-theoretic sense: its indistinguishability relation is captured by a guarded pebble game tailored to the neighborhood-guarded folklore aggregate (as used in the proof of maximality). This invites a logical reformulation. One expects a fragment of first-order logic with counting, in which quantification is restricted by neighborhood guards (or, more generally, by atomic formulas enforcing adjacency to one of the currently bound variables), to match the expressive power of Local k-FGNN at the level of graph invariants. Making this precise would place ℱLF(k) within the landscape between Ck (capturing k-WL) and strictly local fragments (capturing 1-WL variants), and could potentially yield alternative proofs of Theorems~3–4 via standard locality theorems. A further problem is to understand whether k-almost-strong NEDs correspond to bounded width for some notion of decomposition (e.g., clique-guarded or neighborhood-guarded tree decompositions) that is already known in finite model theory. Establishing such an equivalence would unify the combinatorial and logical views and might provide off-the-shelf algorithmic tools for recognition, canonization, and counting on ℱLF(k).
Finally, although our recognition procedure is fixed-parameter in k, its practical performance depends on producing a suitable width-k decomposition and then enforcing the 𝒮LF(k) constraints. It remains to design direct linear-time routines (for fixed k) that build a k-almost-strong NED without invoking generic treewidth algorithms, and to quantify the smallest refinement depth needed to stabilize on graphs in terms of the height of the induced nesting forest. Such algorithmic understanding would close the loop between the structural characterization and its deployment as a diagnostic tool for learned architectures.