Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
Authors: Arie Soeteman
Balder ten Cate
Venue: NeurIPS 2025 poster ()
Keywords: Graph Neural Networks
Hybrid Logic
Individualization-Refinement
Primary area: deep_learning
TL;DR: We study the separating power of Hierarchical Ego GNNs through graded hybrid logic characterizations.

Abstract: We propose and study Hierarchical Ego Graph Neural Networks (HE-GNNs), an expressive extension of graph neural networks (GNNs) with hierarchical node individualization, inspired by the Individualization-Refinement paradigm for isomorphism testing. HE-GNNs generalize subgraph-GNNs and form a hierarchy of increasingly expressive models that, in the limit, distinguish graphs up to isomorphism. We show that, over graphs of bounded degree, the separating power of HE-GNN node classifiers equals that of graded hybrid logic. This characterization enables us to relate the separating power of HE-GNNs to that of higher-order GNNs, GNNs enriched with local homomorphism count features, and color refinement algorithms based on Individualization-Refinement. Our experimental results confirm the practical feasibility of HE-GNNs and show benefits in comparison with traditional GNN architectures, both with and without local homomorphism count features.

Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
Arie Soeteman' Balder ten Cate Institute for Logic, Language and Computation University of Amsterdam
Abstract
We propose and study Hierarchical Ego Graph Neural Networks (HE-GNNs), an expressive extension of graph neural networks (GNNs) with hierarchical node individualization, inspired by the Individualization Refinement morphism testing. HE-GNNs generalize subgraph-GNNg and form hierarchy increasingly expressive models that, in the limit, distinguish graphs up to iso- morphism. We show that, graphs of bounded degree, the expressive power of HE-GNN node classifiers equals that of graded hybrid logic. This characterization enables relate the separating power of HE-GNNs to that of higher-order GNNs, GNNs enriched with local homomorphism count features, and color refine- ment algorithms based Individualization-Reeneee Refinement. Our experimental results confirm the practical feasibility of HE-GNNs and show benefits in comparison with traditional GNN architectures, both with and without local homomorphism count features.
-efiiiaiiittiooneReeeeeent paradigm for iso-
Introduction
Graph neural networks (GNNs), and specifically message-passing neural networks 22 25 dominant approach for representation learning on graph-structured data [49] 55). Since the expressive power of GNNs within the message-passing framework is limited by the one-dimensional Weisfeiler- Leman test (WL) (38 (5). numerous architectures have been proposed with increased separating power-the ability distinguish pairs of nodes graphs. The separating power of deterministic isomorphism invariant GNN architectures can be studied logically. Morris et al. (38) and Barcelo et
al. [6. building on earlier results by Cai et al. (9) gave logical characterizations of the separating power of standard message- passing GNNs, which matches Graded Modal Logic. Higher-order order k-GNNs (38] have the separating power of (k- 1)-WL [38], which equals that of First-Order Logic with à variables and counting quantifiers. This yields hierarchy of increasingly expressive models that separate nodes in graphs of size n up to isomorphism when n. The logical study of GNNs
has addressed fundamental questions about their expressive power 1
23 26 46].
convergence
behavior (2 decidability 77, and explainability (48).
In this work, we introduce Hierarchical Ego GNNs (HE-GNNs), fully isomorphism-invarin graph learning model inspired by the individualization--eeieenn isomorphism solvers, where node individualization is alternated with simple passsage-pasingg We study the separating power of HE-GNN in detail through a logical lens, and make explicit connections with IR and existing expressive GNNs. Our main contributions are:
(IR) paradigm used by graph
We characterize the separating power of HE-GNNs with and without subgraph restrictions. Specifically, we provide logical characterizations in graded hybrid logic, situate the separating power of HE-GNNS within the WI. hierarchy and show that HE-GNNs constitute strict hierarchy in terms of their nesting depth d. HE-GNNs are able to separate nodes in graphs of size n to isomorphism when d > n, like higher-order GNNs, but at lower cost in terms of space complexity.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

We prove that the graph separating power of HE-GNNs with depth d is lower bounded by IR with rounds of invidualization, and show that common Sigraph-GNNY. are special cases of depth-1 HE-GNNs, so that our results characterize the separating power of subgraph models. We further identify a class of graphs with "small ego-rank" from which low-depth HE-GNNS can compute homomorphism counts. These results generalize and shed new light on known relations between subgraph-GNN, higher-order GNNs and homomorphism count vectors from tree-like graphs.
We confirm empirically that HE-GNNs up to depth 2 improve performance ZINC-12K and can distinguish strongly regular graphs beyond the reach of 3-GNNs, common subgraph GNNs and probabilisticc IR methods.
Our results add foundational insights for understanding GNNs from logical perspective, guiding the development of models with improved expressiveness.
Related work Numerous deterministic peessag-passinng architectures have been developed that implement isomorphism-invarinn graph learning with increased separating power. Notable examples are higher-order networks [33 37 [8), subgraph-GNN, [33 51 53) and GNNs augmented with
homomorphism counts [5] 29]. These models allow for extensive analyses in terms of separating
power and comparison with isomorphism invariant classifiers such as logics and the WL hierarchy (see (36],, and we compare them in detail with HE-GNNs in section 5.
In another line of work, node embeddings representing structural information are added before passage-passing often with probabilistic methods, Examples are positional encodings from Laplacian random sampling I 45 and random walks (4). GNNs with randomly sampled features have complete separating power but are only isomorphism invariant in expectation: isomorphic graphs do not yield the same output but only the same distribution. Relevant to the current work are node embeddings inspired by IR, such as random traversals of IR trees [1] and Tinhofer orderings (24 [4).. These methods use non-determinism sparingly, yielding isomorphism-invann -nnvarianc for WL distinguishable graphs and compact graphs respectively. Another graph learning model in the IR paradigm was developed by Dupty and Lee (15). which includes several strong approximations that improve efficiency at the expense of invariance.
eigenvectors [66 18 27
2 Background and notation
For set X, we denote by M(X) the collection of all finite multisets of elements of X. We write @ for vector concatenation, and day for Kronecker's delta (i.e., day is I if x y and 0 otherwise).
Graphs Fix set P of binary node features. By graph will mean triple G (V, E, lab) where V is set of nodes, F C V x V is a symmetric and irreflexive edge relation, and lab V + 2 The degree of a node v in graph G (V, E, lab) is {u | (v, u) E EHl and the degree of graph is the maximum degree of its nodes. A pointed graph is pair (G, v) where G is a graph and v node of G. An isomorphism between graphs G = (V, E, lab) and G' = (V', E", lab')) is (v, u) E E} and such that, for all v E V. lab' (f)( = lab(v). We write G = G' if such a bijection exists. An isomorphism between pointed graphs (G, v) and (G', o') is defined similarly, with the additional requirement that f(v) = . By a node classifier we will mean a function cls from pointed graphs to {0, 1} that is isomorphism invariant (i.e., such that cls(G, v) = cls(G", ,')) whenever v)) and (G', o²) are isomorphic).
bijection f V + V' such that E' = {(f(v),
Graph neural networks Let D, D' E N. graph neural network with input dimension D and output dimension D' (henceforth: (D, D')-GNN) is tuple ((COM)) (AGG,) with
L 2 1, where, for 1 < i < L, COM; 2RD, + R P1, AGG; MMR + R: with D2 = D. D, 2 1, and Dr+ = D'. Each such GNN induces a mapping from embeddings to embeddings. More precisely, by D-dimensional embedding for graph G = (V, E, lab) we will mean function emb : V - DDD A (D, D')-GNN A defines a function run,4 from graph with a D-dimensional embedding to D' -dimennsional embedding as follows:
2

---

1: function run (G,
2: emb : emb
3: for i 1, L do
4: emb = {v: (em, ((o) @ AGG, (aeo(((emb'-(r (e, E EB) NE
5: return emb*
Every D')GGN A with D = [P| and D' naturally gives rise to a node classifier cls To define it, for graph G (V, lab), let its multi-hot label encoding be the |P' |Plldimensional embedding embe given by emb = (ri,...,,T, Tn) with r; = 1 if p; E lab(u) and r; = 0 otherwise. Then A u) 1 if a (mG)) > 0, and cl v) = otherwise. We denote the set of all such node classifiers C also by GNN.
The above definition of GNNs does not specify how the functions COM, and AGG; are specified. In practice, there are a few common choices for AGG, namely Sum, Min, Max and Mean. These have the expected, point-wise, definition. For instance, Sum maps multisets of TR. -tppls to IR -tuples by summing point-wise. As for the functions COM, these are commonly implemented by a fully- connected feed-forward neural network (FFNN) using activation function such ReLU. Some of our results apply to GNNs with specific aggregation and combination functions, in which case this will be explicitly indicated. Otherwise, the results apply all GNNs.
Graded modal logic The formulas of graded modal logic (GML) are given by the recursive grammar Φ : p T Φ A tf -6 02* where p E P and k N. Satisfaction of such formula at node in graph G (denoted: G, v + Φ) is defined inductively, as usual, where
G, v F iff E lab(u). the Boolean operators have the standard interpretation, and G, v += 02* iff Ku (u, u) E and G, == e 2 k. We use Q as shorthand for Q and we use [6 shorthand for -Q Every GML-formul à gives rise to a node classifier cls, where cls v) = 1 if G. v + and (G,
otherwise.
Example 2.1. Consider the GML-formula 6 = 022T A Dp. Then cls (G, u) = precisely if the node has at least two successors and all its successors labeled p.
Weisfeiler Leman Fix a countably infinite set of colors C. A node coloring for a graph G (V. E, lab) is a map col: V + C. A coloring is discrete if for all v in V col colored graph we mean graph together with coloring. The Weisfeiler Leman (WL.) algorithm takes as input a colored graph (G, col) and an integer d 2 0. It produces a new coloring for the same graph as follows, where HASH a perfect hash function onto the space of colors:
= V. By a
1: function WLIG, col,
2: coll col
3: for i = 1,...,d d do
4: col' == {v HASH(col (v), {col'
5: return col"
For graph G (V, E, lab), by the initial coloring of G we will mean the coloring cole given by (u) = (lab(laa(e)). We write WL(G, d) as shorthand for WL(G, colg, d). In other words, WL(GG, d) denotes the coloring obtained by starting with the initial coloring and applying d iterations of the algorithm. Two pointed graphs (G, v), (G', 1') are said to be WL- iL-indistinguushalle (denoted also (G, v) EwI. (G', )') if and e' receive the same color after d iterations for d max ( [G], [ -tht is, if (l.(G,)(())
The WL algorithm gives rise to node classifier for each d 2 0 and subset S C C, where cl, v)= if WL(G, (v) E S and wis v) otherwise. Note that, by definition, such classifiers cannot distinguish WL-indistinguishabl pointed graphs.
why equivalence Given a collection of node classifiers (e.g., all GNN-based node clas- sifiers), we denote by ((C) the equivalence where ((G, (G', E p(C) if and only if, for all cls E C. cls(G,v) v) cls(G', v'). In other words, p(C) captures the expressive power of C as measured by the ability to distinguish different inputs.
3

---

Theorem 2.2. P(GNN) = PGGL) = (WL)
The equivalence in separating power between GNNs and WL was proven independently by Xu et al. [50] and Morris et al. (38]. Their equivalence with GML was shown by Barcelo et al. [6]. Indeed, it was shown in [6] that for every GML-formula, there is GNN that implements the same node classifier:
Proposition 2.3. ((0)) For every GMI-formula & there a GNN such that cls - cls Moreover, the GNN in question only uses Sum as aggregation and a single ReLU-FFNN as combination cembinatien.function.
The converse does not hold in general, but does when we bound the degree of the input graph:
Proposition 2.4. Let be (D, D')-GNN with D [P], let N > 0, and let
X fru (m) G = EV, E, lab) is a graph of degree at most N and u E V).
In other words X S RDD is the set of all node embeddings that A can produce when run on graph of degree at most N. Then X is a finite set, and for each x E X, there is a GML-formula 6x such that for every pointed graph (G, v) of degree at most N, it holds that G, u F Φx iff a (m) x. In particular, for each GNN- -alasssss C there is GML-formula 6 such that cls,(G, v) = a v) for all pointed graphs (G, v) of degree at most N.
Proofs for these two propositions are provided in the appendix, as we will build on them.
3 Hierarchical Ego GNNs
In this section, we introduce and study the basic model of Hierarchical Ego GNNs (HE-GNNss). In the next section, we will further refine the model by means of subgraph restrictions.
Hierarchical Ego GNNs
(D, of nesting depth is simply a (D, D')-GNN.
A (D, -'E-HE-N of nesting depth d > O is a pair (B, C) where B is (D + +,, HHEHH of nesting depth d and C is a (D + D" D'N-GNN.
A HE-GNN A
(B. C') detines a function A from embedded graphs to embeddings as follows:
function (u, emb) for each node u of G do
2:
3: emb' (u) == emb(v) @ rung(G, (u: emb(u) @ 8uv u E (v)
4:
return runc (G,,'m))
In other words, for each node v, we run B after extending the node embeddings to uniquely mark v, and concatenate the resulting embedding for to its original embedding. After constructing new embedding for each we run C. On a graph with n nodes a HE-GNN with depth d and I layers at each depth generates O(na) graphs with different unique labelings. Since an layer GNN sends at most 7- nn2 messages, HE-GNN with depth d and / layers at each depth sends O d+22 messages. Applying the individualizations in depth-first order, (d + 1) n node embeddings are stored, which is bounded by n²a Naturally the time and space complexity depend on the embedding dimension and the chosen aggregation and combination functions. Just as in the case of GNNs, each (D, D'D-DD--HGHREE HE-GNN A with D Pl and D' = 1 naturally gives rise to node classifier A-
Example 3.1. Let B be a 3 layer (2, 2NNN with element-wise sum as aggregation and the identity map as combination. Let C be a trivial (2, 2)-NN that doesn't I change the input. Then A = (B, C) (HE2)-NEGGNN of depth such that run x v) & ( v') for the graphs in figure 7
This shows that BE-GNN with nesting depth 1 has strictly more separating power than GNN. Let HE-GNN-d denote all classifiers C where A is HE-GNN of nesting depth d. As will see below, HE-GNN-d in fact forms an infinite hierarchy with respect to separating power for increasing values of d. To show this we first give logical characterization of HE-GNN-d.

---

Graded hybrid logic Graded hybrid logic (henceforth GML(JJ) extends GML with variables and the variable binder 4. To be precise, the formulas of GMI.(J) are generated by the grammar é : о T Φ A sb 12 tx.Ø. We restrict attention sentences, i.e., formulas without free variables. The definition of satisfaction for GML-formula at node of graph G as follows:
(G, v)
(G',
(V, l.b), extends naturally GML(L)- G. v. + z. if G(æ + v). v -= 6. where G|æ + v] denotes copy of G which x is treated at By the J-nesting-depth of a GMI-(L) we will mean the maximal nesting of + operators in the sentence. We denote with GML (4") all sentences with maximal J-nesting-depth d.
Figure 1: Two non-isomorphic pointed graphs that are WL- indistinguishable.
binary node feature true only
Example 3.2. The sentence o = x. zz,00z, which has J-nesting- 1, is satisfied by a pointed graph (G, u) precisely if e lies on a triangle. In particular, considering the example in Figure distinguishes (G, v) from (G', v'). This also shows that GML(4) is more expressive than GML.
Example 3.3. Building on the above example, the sentence tb fr.0( 0( O6 A Vo x))). teething-depth
which has l-nesting depth 2, is satisfied by (G, v) precisely if lies (homomorphically) on a cycle of length 4 consisting of nodes that each lie on a triangle.
In the literature, hybrid logies often include an @ operator, where a states that & holds the world denoted by the variable x. Over undirected graphs, however, every GMI,(I, @i) -sentence is already equivalent to a
of the same l-nesting-depth.
The connection between GNNs and GML described in the previous section extends to a connection between HE-GNNs and GJL(
Theorem 3.4. p(HE-GNN) (L)ML())). Moreover, for 2 P(HE-GNN-d) (GGML()))
The proof, given in the appendix, is along the lines of Propositions 2.3 and Indeed, there is translation from GMII(L.-seetennee to HE-GNNs, and, conversely, over bounded-degres inputs, there a translation from HE-GNNs to GML( (MM(())ssentnnce Both translations preserve nesting depth. In Section 5 put this logical characterization to use to obtain number of further results.
4 Hierarchical Ego GNNs with subgraph restriction
Since HE-GNNs generate an exponential number of graphs in make the models more manage- able by restricting subgraphs to a fixed radius around the uniquely marked node, in line with the common approach for subgraph-GNNs (20 5T 52 53
Hierarchical Ego Subgraph-GNNs
A (D, (D,D') D')--'D--HOOE GNNN of depth 0 is simply a (D, D'N-GNN.
A D') -NNN of depth >> O is a triple (B, r) where is a (D + HEESHNNN of depth d 1, C is a (D D", D')-GNN, and r is positive integer.
Given a graph G (V, E, lab), node u E V. and a positive integer r, we will denote by G the induced subgraph of G containing the radius-r neighborhood of v.
1: function (un_A(G, emb)
For A (B,C,r)
2:
for each node v of G do
3: emb' (v) emb(v) @ rung(Gr, {u emb(u) @ 8 | uu ())(v)
4:
return runc(G, emb')
There is only one change compared to the previous version: G got replaced by G line 3. Now a HES-GNN with depth radius and at most / layers applied to a graph with degree k, generates O( (k" + 11)mar(U,d-1)) graphs, sends at most 1 n² times as many messages and stores + d. (R' + 1) embeddings. Each (D, D')- A again gives rise to a node classifier A. We denote with HEES-NNN- the set of such classifiers for radius r and with HES HES-GNN-(d.. the restriction nesting depth d.
5

---

Graded hybrid subgraph logic GML(J. W) further extends GML()) with a "within" operator W inspired by temporal logies with forgettable past T The formulas of GML(,. W) are generated by ::= p - Φ A 1 * fx. W Φ The definition of satisfaction for GMI-())-sentence extended by letting G, u = W G v = Φ. We will use Lw- x.4 as a shorthand for x. Φb We denote with GML (+w) the fragment of GML (J. W) in which 4 and W can only be used in this specific combination with each other, and denote with GML (+w-) (for specific integers and r), the further fragment with radius r and where kw- can be nested at most d times. terms separating power, GML(4w) is equivalent to GML(4), but pairing variable binders with subgraph restrictions of a specific radius serves to decrease expressive power. The connection between HE-GNN and GML(L) established in Theorem 3.4 now extends the case with subgraph restrictions:
Theorem 4.1.
(HHES-GNN) = p(GML(UW)) (00l:/>)))P(GGGMLOO P(GML(J) P(HE-GNN).
2. ((HES-GNN-r) = p(GML()W--). Moreover, O(HES-GNN-C (CNNN((d)==((GML((()))) P(GML(U
=
This is established again through a uniform translation from GML(4W-) sentences to HES-GNN-(d.7) classifiers and a converse uniform translation over bounded degree inputs from HES (ES-GNN-(d,r)) classifiers to GML(UW->) sentences.
The separating power of HES- (NS-GGN--(d.r) classifiers strictly increases with d and Note that p(X) & p(Y) means that has strictly more separating power than Y:
Theorem 4.2. For d 2 1, 2 0, p(HEE-GNN-(dr 1)) & p(HES-GNN-(d,,
Theorem 4.3. For d 2 0 and r 2 3, p(HES-GNN-(d 1,r)) & p(HES-GNN-((rr)
Comparison with other models
In this section, build on the logical characterizations from the previous sections to obtain number of technical results, drawing connections between isomorphism testing and several GNN architectures by comparing their expressive power with that of HE-GNNs and HES-GNNS.
5.1 Relationship with
The individualization and refinement (IR) paradigm is applied by all state-of-the-arr graph isomor- phism solvers [14, 30 34 41). In its usual presentation (e.g. [35)), color refinement, cell-selection and individualization procedures are applied in alternating fashion, resulting in tree whose nodes labeled by increasingly refined colorings of the input graph, with discrete colorings the leafs. In practice, some further optimizations are typically implemented, exploiting symmetries to further reduce the size of the tree, but these optimizations do not affect the result of the equivalence test, and we do not consider them here. In order to make a precise comparison, we define WL-IR:
1: function WL-IRIG, col, d)
2: col' ;= WL(G, col, [G])
3: if' col' is discrete or then
4:
return (col')
5:
else
Let be the least color with |col' (c)) 2 2, and co) = For each i S n, let col, := {v: HASH(col (v), dve,) [v
6:
col'
7: return
co, - 1)
WL.II[GG, d -1
Here we use WI. as the refinement procedure (which is indeed common practice) and apply simple cell-selection procedure that assumes an order on the of colors and picks the least non-singleton color. We include an extra input parameter d that controls the number of individualization steps

---

the algorithm can perform. WL-IR is guaranteed to produce discrete colorings when choosing 2 [G]. We write WL-IR(G, d) as shorthand for WL-IR(G, colg,d). d). We can now compare two graphs by choosing suitable d and testing if WI.-IR(G,, d) and WL--IR('', d) yield isomorphic trees. Let G I G' if and only if this comparison does not distinguish G from G'. For d = 0, clear that -I-IR-d corresponds simply to indistinguishability by the Weisfeiler Leman test. If d is sufficiently large, on the other hand, each leaf of the tree is labeled by a discrete coloring, so that WL-IR distinguishes graphs up to isomorphism:
Proposition 5.1. Let G, G' be graphs and d Z min( |G'). Then G =WL-IR G' iff G
Thus, by varying d we obtain family of increasingly refined equivalence relations for graphs. In order relate these equivalence relations those induced by HE-GNNs of different nesting depths, we must first overcome a technical issue. WL-IR is designed to compare graphs. not nodes, Let G cds G' if {f [cls(G. 8)
V = (cls v) | V. and G =c G' if G cds G' for all classifiers cls in C. The graph separating power of WL-IR with depth 0 matches that of GNN.
Proposition 5.2. G $WLIR-O G' if and only if G FONN G'
The graph separating power of WL-IR-d a lower bound to that of HE-GNN-d for 2 0 Theorem 5.3. For 2 O, if #WL-I-d G", then G FHE-GNN-d G'
In fact, for connected graphs, and with depth d + 1, HE-GNN node classifiers already suffice, since the separating power of local message- -aassaggg matches global message-passingg over connected individualized graphs [52]:
Theorem 5.4. Let (G, v). (G', e²) be connected pointed graphs and let d 2 0. IfG AWL-IRdd G², there exists depth d + HE-GNN such that A v) & A v').
Proposition 5.1 and theorems 5.3 5.4 show that for sufficiently large d, HE-GNN-d classifiers distinguish graphs up isomorphism. Contrary to WL-IR, HE-GNNs combine individualized graphs hierarchically. We show this increases separating power when d = 1:
Theorem 5.5. There exist G, G' such that G =WL-IR-1 G' but G FHE-GNN-1 G'
Using recent results by Rattan and Seppelt 44 theorem 5.5 implies that HE-GNN-1 strictly more separating than cospectrality of adjacency, Laplacian and Seidel matrices. In addition, this shows that the hierarchical geessage-passinggg scheme of HE-GNN- adds to expressive power, compared to aggregating over all individualized graphs in parallel. It remains open if the same holds for all d 2 1.
5.2 Relationship with homomorphism count enriched GNNs
In |5) the authors assume a finite set of rooted graphs 3 = (Fi,.... ... } and, given an input graph G. for each node v. they add the finite homomorphism count vector hom (G, v)) the initial embedding of before rumning GNN. Here, by rooted graph we mean a pointed graph (F, u) that connected, i.e.. such that every node of F is reachable from u. Note that the input dimensionality of the GNN is thus assumed to be PP| & instead of IP|. This increases the expressive power of the model. For example, the non-isomorphic nodes Figure [ can be distinguished from each other by including the cycle of length 3 (with a distinguished node) as pointed graph in S. We will refer to GNN that runs over a 3 enriched graph simply as 3-GNN.
Theorem 5.6. Let be any finite set of rooted graphs each with at most nodes. Then there is (IP), PI + HHE-NNG A of nesting depth d such that, for all pointed graphs (G, v),
(G))(G)(v) emba(v) @ hom (G,v))
The HE-GNN in question only uses Sum as aggregation and Relu-FFNNs combination functions.
In particular, this shows that every 3-GNN is equivalent to HE-GNN. The practical value of the above result, however, is limited by the fact that it requires high nesting depth. As it turns out, for many choices of 3. very small nesting depth suffices.
'Theorem 5.4 in | is somewhat related as it states that the node separating power of homomorphism counts from all rooted graph is captured by hybrid logic (with @ -peerrtoor but without counting modalities).
7

---

We will call rooted graph (F, u) c-acyclic if every cycle of F passes through u. C-acyclicity a relaxation of acyclicity, and c-acyclic rooted graphs can be thought of as trees with back-edges. Our next result will imply that when & consists of e-acyclic structures, a nesting depth of 1 suffices. In order to state it in full generality, we need to introduce some further terminology.
dep
dep
dep:
particular, we introduce the notion of ego-rank.
dep u1
dep ug
Given a rooted graph (G, v), let dep
V + V U be a partial function from nodes nodes and let deps(u) (dep(u). (ep(dep(u)).....
Figure 2: Rooted 5 5x2-grid
{1} J be the (finite) set of nodes u transi-
(root: d1)
tively "depends on".. We require of the function dep that:
1. dep(u)
= 1.
(w,,) E, then dep(w)= dep(u) or w E deps(u) or u deps(w).
3. Every set of nodes with the same dep-value induces acyclic subgraph.
The ego-rank of (G, v) the smallest value of the maximum node rank, where the node rank of node is [deps(u),, u)], across all ways to choose the function dep subject to the above constraints. Proposition 5.7. For all rooted graphs (G,v) with G EV, lab).
tree-width(G) S ego-rank(C., v) S [V] ego-rank((G: v) if and only if G acyclic.
ego-rank(G, v) whenever (G, v) is e-acyelic.
The ego-rank of a rooted graph is not
by any function in its tree-width, and can be exponential in its tree-depth, follows from the following example:
Example 5.8. The rooted graph consisting of an n 2-grid, with one of its corners as the root, as depicted in Figure 2 has ego-rank
for 2 1.
Theorem 5.9. Let 3 be any finite set of rooted graphs, let = max-ego-rank u) (F,u) E 3).
HEE-GNN AA of nesting depth such that, for all pointed graphs (G, v). (G) (m @ hom( (3, (G, u)). The HE-GNN uses multiplication in the combination functions.
Then there is ( (IP), |P| + (8)
For each N > there is (IP),)P) HEI)-HEGGNN A of nesting depth d such that, for pointed graphs (G, v) of degree at most N, a = emb ① hom (G, The HE-GNN uses only Sum as aggregation and ReLu-FFNNY as combination functions.
follows that, in mon-onnnniet non-uniform sense, every 3-GNN is equivalent to a HE-GNN of nesting depth max(ego-rank (F, u) (F, u) E 3) using only Sum and ReLu-FFNNs.
5.3 Relationship with higher-order GNNs
k-GNNs, as proposed by Morris al. 38). apply message-passing between node subsets of size k, where subsets are adjacent when they share exactly 1 nodes. The separating power of these models is characterized by the k-variable fragment of first-order logic with counting quantifiers C
Theorem 5.10
99 38
p(k-GNN) = ((C))
k-GNNs become strictly more expressive with larger k, and distinguish graphs of size S k up to isomorphism. As such, they have proven to be a useful yardstick for the development of expressive GNN architectures. The model proposed by Morris et al. requires exponential space and time since maintains & features in memory, and applies message passing over =+1 edges. Maron et al. [33] proposed k-IGNs with ( space complexity and O(n²) time complexity, which were shown by Azizian and LeLarge and Geerts 21 to have the same separating power as k-GNNs.
HE- GE-G constitute an alternative hierarchy, where nesting depth d yields classifiers that distinguish graphs of size n S d up to isomorphism (Theorem 5.3). HE-GNNs perform simple message passing on nd graphs, but they can do this in sequence and hence need to store only n² node features. Using the logical characterizations we show the separating power of HE-GNNs with nesting depth is most that of + 2-GNNs, equivalently the d + 1-WL algorithm.
8

---

Theorem 5.11. For d 2 O, p((d 1)-WL) = p((d+ ) S p(HE -NN-G-
This generalizes a recent result by Frasca et al. (20]. who showed that the separating power of many common subgraph- N is bounded by that of 2-WL. We further show that this result is optimal, in the sense that HE-GNNs with nesting depth d can distinguish nodes that d + 1-GNNs can not:
Theorem 5.12. For d 2 0, HES-GNN-(d.3) can distinguish pointed graphs that cannot be distin- guished by d-WL, or equivalently, by a (d I)-GNN.
Given the difference in the number of stored embeddings, one would expect that for d 2 O, p((d + 1)-WL) & p(HE-GNN-d). We leave this as an open conjecture.
5.4 Relationship with other variants of subgraph-GNNs
Numerous recent studies 20 51
have proposed variants of subgraph-GNNs. where
message passing is applied to a collection of subgraphs. Subgraph-GNN show state-of-lie performance on real-world benchmarks such as ZINC molecular property prediction 88] 20 54 In particular, a variant of subgraph- Doprrapp-GNNss GNNs in which nodes receive neighborhood embeddings based on
ofate-of-thhearr -he-trr
their radius r neighborhood with distinguished center node label, also known as "ego-networks",
have become prominent as simple yet expressive subgraph-GNN architecture (20 51 53.
ID-GNNs 51 HES-GNNs (B,C) with nesting depth 1, where C is trivial GNN that doesn't apply
any message passing. Nested GNNs (53] do not use individualization, but perform global pooling over subgraphs followed by message passing over the input graph. Since local aggregation with individualization is strictly more expressive than global aggregation over connected subgraphs (52), the separating power of nested GNN is strictly less than that of HES-GNT with nesting depth Theorem 4.1 thus provides logical upper bound to the separating power of these models.
Several other generalizations of subgraph-GNi have recently been proposed 33 42 Most related to this work, Qian et al. introduced Ordered Subgraph Aggregation networks that apply message passing on | copies of G, each labeled with the atomic type of h size subgraph, and perform aggregation over representations for predefined selection of the |G| subgraphs. Like HE-GNN this constitutes a strict hierarchy with separating power upper bounded by k + 1-WL, but not by k-WL. It is not immediately clear whether OSAN yields more expressive node classifiers than HE-GNN, since OSAN performs global aggregation over arbitrary sets of subgraphs, while HE-GNN uses local mussage-passing hierarchically.
6 Experiments
We apply BES-GNN to ZINC-12K [17 28 and compare with standard GCN 33
GIN 50 and
PNA [1) layers, as well as GINs augmented with random identifiers (GNN+RID) 1 45 Tinhofer orderings (GNN+T) [40] and homomorphism counts from cycles of size 3 to 10 (N-GNN) (.. We use feature dimension 256 for all models for a maximum of 1000 epochs on single 20GB gpu. All code used for the experiments is available on git Table shows the achieved mean absolute error after 10 runs and validation score selection. HES-GNNs with depth 1 outperform J-GNN even though ZINC has cycle counts in its target function. HES-GNN-(2.3) performs equally well as F-HES-GNN-(133 a depth 1 model augmented with homomorphisms counts.
Figure shows the performance of HE-GHE EE-GNN and HES-GNN on distinguishing strongly regular graphs. We use synthetic datasets, each containing 30 random isomorphisms of 10 strongly regular graphs for specific choice of parameters (v, k, X, J1) 47 Since strongly regular graph are indistinguishable by 2-W1. and hence by 3-GNNs, depth HE-GNN and ID-GNN [51 perform at chance level. Adding cycle counts doesn't 't alleviate this, in line with theorem 5.9 Tinhofer orderings fully individualize all
nodes to yield maximal separating power, resulting in 100% precision on the test set. However, since these orderings to the test set. Depth 2 HE-GNNs distinguish the strongly regular graphs and generalize to unseen isomorphisms, even with restricted subgraph radius. Figure 4 shows time and memory usage of HE-GNNs with varying depth and radius on ZINC for a single forward pass.
not catnoorhism-invvviien over the tested graphs, T-GNN does not generalize
https//ggthhbbboom/nssseeeeemm/n

---

0.3
Train
Test
Precision
Chance level
0.6
ID-GNN
GNGNN
0.4
T-GNN
HES-GNN(2,) 1)
HE-GNN(2)
(26, 10, 3, 41
129. 14, 6.
(36, 14, 4, 6)
(40, 12, 2.
Figure 3: Precision on isomorphism classification of strongly regular graphs for four settings of
(v, k. M)) Models from left to right: ID-GNN [SI]. 3-GNN with counts from C3.... C10 [3], GNN with Tinhofer labelings 40)
HES-GNI with 2, r and HE-GNN with d 2.
40
r=2
6
Table Mean absolute error on
r=3
ZINC-12K, test scores after 10 runs.
30
r=4
5
r=4
r=
1=5
Model
ZINC (MAE)
4
E
GCN
0.216
20
3
GIN
0.193
PNA
12
0.207
GNN+1
0.199
GNN Frandom ID
45
0.226
10
GNN
0.154
1
(d.1)
0 0
0
HES-GNN
(1.1)
0.191
2
(1.2)
0.189
(1.3)
0.149
(2.1)
0.188
Figure 4: Time (left) and memory (right) per sample of single forward pass HES-GNNN-(,,)) on ZINC This does not include gradients. Experiments with batch size 20 and feature dimension 256.
(2.2)
0.183
(2,3)
0.140
H-HES-GNN
(1.3)
0.140
7 Limitations and directions for further research
Efficiency Compared to k-GNNs, HE-GNNs store |G|2 instead of |G| node features. Nevertheless, they still require exponential amount of message passing steps in the nesting depth d, rendering implementations infeasible for large d. IR-based graph isomorphism tests typically reduce tree size via informed cell selection and automorphism pruning, whereas Dupty and Lee (15) address scalability in a learning setting through compressed approximate trees. Further study is needed to explore how techniques from isomorphism testing can be adapted graph representation learning, and how these optimizations affect expressive power.
Expressive power Some questions regarding separating power are left open by our results. In particular, we gave sufficient conditions for graphs from which HE-GHN can count homomorphisms in terms of size and ego-ranks, but have not shown these conditions are necessary. Our results also limited in scope by the fact that they concern separation power and not the uniform expressibility of functions. Several uniform expressibility results have recently been obtained for GNNs (both relative to first-order logic [6. and in terms of Presburger logic (7). and remains to be seen if these results can be extended HE-GNNs.
Beyond expressive power The empirical success GNNs cannot be understood through expressive power alone, as it also depends on trainability aspects such as convergence and generalization. These remain be explored more extensively, across GNN architectures and in the context HE-GNNs.
10

---

Acknowledgements
We thank Martin Grohe, Ronald de Haan, and Carsten Lutz for valuable discussions that contributed to the development of this work.
References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The sur- prising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01173 179, 2020.
[2] Sam Adam-Day, Michael Benedikt, Ismail Ceylan, and Ben Finkelshtein. Almost surely asymptotically constant graph neural networks. Advances Neural Information Processing Systems, 37:124833-124886 1248866, 2024.
[3] Rajeev Alur, Marcelo Arenas, Pablo Barcelo, Kousha Etessami, Neil Immerman, and Leonid Libkin. First-order and temporal logics for nested words. In Proceedings of the 22nd Annual IEEE Symposium on Logic in Computer Science, LICS '07, page 151-160, USA, 2007. IEFE Computer Society.
[4] W. Azizian and M. Lelarge. Characterizing the expressive power of invariant and equivariant graph neural networks. CoRR, abs/2006. 15646, 2020.
[5] Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. Advances in Neural Information Processing Systems, 34:25280- 25293, 2021.
[6] Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Pabn- Silva. The logical expressiveness of graph neural networks. 8th International Conference on Learning Representations (ICLR 2020), 2020.
[7] Michael Benedikt, Chia-Hsuan Lu, Boris Motik, and Tony Tan. Decidability of Graph Neural Networks via Logical Characterizations, In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informaties (LIPlcs), pages 127:1-127:20, Dagstuhl, Germany, 2024. Schloss Dagstuhl Leibniz-Zentrum für Informatik.
[8] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.
[9] Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-41 -400, 1992.
[10] Balder ten Cate and Lue Segoufin. Transitive closure logic, nested tree walking automata, and XPath. J. ACM, 57(3), March 2010.
[11] Jesse Comer. Lovász theorems for modal languages. In Agata Ciabattoni, David Gabelaia, and Igor Sedlár. editors, Advances in Modal Logic, AiML 2024, Prague, Czech Republic, August 19-23, 2024, pages 269-292. College Publications, 2024.
[12] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liō, and Petar Veličkovié. Principal neighbourhood aggregation for graph nets. Advances in neural information processing systems, -11172 2020.
[13] Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph representations. Advances in Neural Information Processing Systems, 34:1713-1726, 2021.
[14] Paul Darga, Hadi Katebi, Mark Liffiton, Igor L.. Markov, and Karem Sakallah. Saucy3. n.d. Software package.
http://vlsicad eecs umi ch.

---

[15] Mohammed Haroon Dupty and Wee Sun Lee. Graph representation learning with individualiza- tion and refinement. arXiv preprint arXiv:2203.09144, 2022.
[16] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprini arXiv:2012.09669, 2020.
[17] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1 48, 2023.
[18] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint 1.Xiv:210000787: 2021.
[19] Billy Joe Franks, Markus Anders, Marius Kloft, and Pascal Schweitzer. A systematic approach to universal random features in graph neural networks. Transactions on Machine Learning Research, 2023.
[20] Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph GNNs by rethinking their symmetries. Advances in Neural Information Processing Systems, 35:31376-31399, 2022.
[21] Floris Geerts. The expressive power of kth-order invariant graph networks. arXiv preprint arXiv:2007. 12035, 2020.
[22] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. International conference on machine learning. pages 1263-1272. PMLR, 2017.
[23] Martin Grohe. The descriptive complexity of graph neural networks. In Proceedings of the Thirty eighth Annual IEEE Symposium on Logic in Computer Science (LICS 2023), pages 1-14. IEEE Computer Society Press, June 2023.
[24] Alan J. X. Guo, Qing-Hu Hou, and Ou Wu, Improving the expressive power of graph neural network with tinhofer algorithm, 2021.
[25] William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull,, 40(3):52-74, 2017.
[26] Stan P Hauke and Przemyslaw Andrzej Walega, Aggregate-commine--rddde gnns are more expressive than logic c2. arXiv preprint wwxiv:2508.0609) 2025.
[27] Yinan Huang, William Lu, Joshua Robinson, Yu Yang. Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graphs. In The Twelfth International Conference Learning Representations, 2024.
[28] John Irwin, Teague Sterling. Michael M Mysinger, Erin Bolstad, and Ryan G Coleman. Zinc: free tool to discover chemistry for biology. Journal of chemical information and modeling, 1277)1157711668 2012.
[29] Emily Jin, Michael Bronstein, Ismail IIkan Ceylan, and Matthias Lanzinger. Homomorphism counts for graph neural networks: All about that basis. arXiv preprint arXiv:2402.08595 2024.
[30] Tommi Junttila and Petteri Kaski. Engineering an efficient canonical labeling tool for large and sparse graphs. In 2007 Proceedings of the Ninth Workshop on Algoritium Engineering and Experiments (ALENEX), pages 135-149. SIAM, 2007.
[31] Charilaos Kanatsoulis, Evelyn Choi, Stefanie Jegelka, Jure Leskovec, and Alejandro Ribeiro. Learning efficient positional encodings with graph neural networks. In The Thirteenth Interna- tional Conference on Learning Representations, 2025.
[32] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
12

---

[33] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[34] Brendan D. McKay and Adolfo Piperno. Nauty and traces user guide, https://ca anu anu.edu edu
mn/people/Brendaat MMw..MKKaaayya MKckaa/nauty//ug2222 pdf] 2014. Accessed: 2025-04-24.
[35] Brendan D McKay and Adolfo Piperno. Practical graph isomorphism, ii. Journal of symbolic computation, 60:94-112, 2014.
[36] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. Journal of Machine Learning Research, 24(333): 2023.
[37] Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 08:28244-1180, 2020.
[38] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
[39] Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network extensions. In International Conference on Machine Learning, pages 17323-17345. PMLR. 2022.
[40] Paolo Pellizzoni, Till Hendrik Schulz, Dexiong Chen, and Karsten Borgwardt, On the expressiv- ity and sample complexity of node-individuualzzed graph neural networks. Advances Neural Information Processing Systems, 37:120221-12023 2024.
[41] Adolfo Piperno. Search space contraction in canonical labeling of graphs. arXiv preprint arXiv:0804.4883 2008.
[42] Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered subgraph aggregation networks, Advances in Neural Information Processing Systems, 35:21030-
2 21045, 2022.
[43] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-14515 2022.
[44] Gaurav Rattan and Tim Seppelt. Weisfeiler-leman and graph spectra. In Proceedings of the 2023 Annual ACM-SIAN Symposium on Discrete Algorithms (SODA), pages 2268-22632 2288. SIAM, 2023.
[45] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM international conference on data mining (SDM), pages 333-341. SIAM, 2021.
[46] Moritz Schönherr and Carsten Lutz. Logical characterizations of gnns with mean aggregation. arXiv preprini arXiv: 18145, 2025.
[47] E. Spence. Strongly regular graphs at most 64 vertices. htttps://www.matie gla.ac..... acku// "es/ /es//rrraphs.... php n.d. Accessed: 2025-05-10.
[48] DJ Tena Cucala, B Cuenca Grau, Egor V Kostylev, and Boris Motik. Explainable gan-based models over knowledge graphs. 2022.
[49] Petar Veličković. Everything is connected: Graph neural networks. Current Opinion in Structural Biology, 19:102338, 2023.
[50] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
13

---

[51] Jiaxuan You, Jonathan M Gomes-Selman Rex Ying, and Jure Leskovec. Identity-awan graph neural networks. Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 10737-10745, 2021.
[52] Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehmnn tests. In International Conference on Machine Learning, pages 41019 400197 PMLR, 2023.
[53] Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34:15734-15747, 2021.
[54] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. International Conference on Learning Representations, 2022.
[55] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: review of methods and applications. Al open, 1:57-81, 2020.
14

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Abstract and introduction have been written represent the paper's scope and contributions clearly and accurately as possible.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
A limitation section including open problems is provided the end of the paper.
Guidelines:
The answer NA means that paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results to vi- olations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested a few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
15

---

All theorems are formulated with the objective of preventing ambiguity in terms of what proven and what assumed. All proofs are included in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide a short proof sketch to provide intuition.
Inversely, any informal proof provided the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data provided not)?
Answer: [Yes]
Justification: ZINC-12K is publicly available, and the description of the synthetic dataset should be sufficient for reproduction. The applied algorithm is explained in pseudocode. Code used to run these experiments will be made publicly available on git.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g.. in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e-g., a large language model), then there should either be a way to access this model for reproducing the results or way reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but should be possible for other researchers to have some path to reproducing or verifying the results.
Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
16

---

Answer: [Yes]
Justification: Code will be made publicly available and a link will be included in the paper after the reviewing process, prevent breaching anonimity. All used data is publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines hhttps::/niis..ccppull
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines pettpa://nise
cwssssiiinoocyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. If only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits. hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
Main settings such as hidden dimension and the number of runs are listed in the experiments section. Details such as data splits and hyperparameters are not mentioned in the paper itself, but all details provided in the form of code git.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that necessary to appreciate the results and make sense them.
The full details can be provided either with the code, in appendix, or as supplemental material.
Experiment statistical significance d
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Standard deviations are included for the result on strongly regular graphs. Results on ZINC-12K are optimal results selected by validation scores, explained in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
17

---

The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or figures
If error bars are reported tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Experiments were run on single 20GB gpu for 1000 epochs, stated in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
Code of ethics
Does the research conducted the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification: All data used is publicly available and doesn't 't contain sensitive information. We intend that this work will aid the scientific community in understanding graph learning models, and do not foresee harmful consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consideration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We do not foresee direct (negative or positive) societal impact of this work, apart from aiding the scientific community in the development of graph learning methods.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address socictal impact.
18

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could he used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We do not release any new data. Our method focuses improving expressive power for graph learning tasks and not applicable to high-risk domains such as language generation or image synthesis.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Explicit references made to the used datasets. All code is developed by the authors.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL..
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcaae thoode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
19

---

For existing datasets that are re- ee-ackaaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code git contains package for hierarchical ego gnns including documenta- tion. The details of the algorithm are given pseudocode in the paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: This project did not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This project did not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
20

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: No LLMs were part of the core development of this work as an important or non-standard component.
Guidelines:
The answer NA means that the core method development this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy hattps://neut auttpeee/beerrrrseccc//ffffeerrr should or should not be described.
for what
21

---

Missing proofs
A Proofs for section 2
Proposition 2.3. (16)) For every GML-formula & there is a GNN A such that cls = clsg. Moreover, the GNN in question only uses Sum as aggregation and a single ReLU-FFNN combination function.
Proof. Let & be the smallest set of GML-formulas containing & that is closed under taking subfor- mulas. The operator depth of GML-formula is defined follows: depth(p) 0, depth(-6) (Ø) + 1, depth( A 1b) max max(depth( (de d + (epth(@2"g) = depth( + Let | k and let I. be the maximal operator depth of formula in $ Let
A ((COM)) (AGG:))=1....)
where
COM : R - I given by COM 31.
U1...... (pP)) = (21,...,22) 2x) with 2; zz if
di is of the form Pj and 2; otherwise.
For i > 1, COM; 2 + R is given by COM CoM,( The .1.... Vke) (21,..., 2x) with
22
if Φ; is the form p
2j
if Φb is of the form ~0j
2j
m2 km
if Φb. is of the form 6) om
if yJ 2 n. otherwise
if Φb. is of the form 22" 0j
Each AGG, is (pointwise) sum.
It is not difficult to see that COM; can be implemented by two-layer feed-forward network using the ReL.U activation function. particular, max [xr [m can be expressed as ReI.U(x, + Fm 1) and "I if yj 2 n, O otherwise" can be expressed as ReLU(( ReL.U(n y:))-
can be shown by a straightforward induction on d, that, for all d 2 for all & of operator depth d, and for all > d, (b)(() is 1 if G, - d, and 0 otherwise.
In order to turn A into a classifier, finally, we extend cOM,, with one additional linear layer of dimensionality (k: 1) that takes vector (Ii.-.., and outputs I;, where Φ; = Φb
n
Proposition 2.4. Let A be (D, D')-GN with D = [P], let N > 0, and let X = f (m) G = (V, E, lab) is graph of degree at most N and v E V).
In other words X C RDD is the set of all node embeddings that A can produce when run on a graph of degree most N. Then X is a finite set, and for each Øx such that for every pointed graph (G, v) of degree at most N, it holds that G,v }= Φx iff run a (G, (m) x. In particular, for each GNN-classifier cls A there is GML-formula o such that cls,(G, v) = A ()),,)),,n)) for all pointed graphs (G, v) of degree at most N.
X, there is a GML-formula
Proof. Let A (CCOM))==1.... (mb where, for each 0.. L. emb's V -> R D. is given by
By definition, (mbb)))) is equal to
embo embe
emb {v: : (emb) (v) @ AGG, (fembb (u) | (v. u) E EB)) v E V) for 0
The main statement can therefore be restated as saying that the set
X (emb((x) G = (V, F,, lab) is graph of degree at most N and E V) is finite and there is a defining GML-formula ox for each x E X1, (over pointed graphs of degree at most N). We proceed by induction on L.
For I 0. emb equals emba- In this case, X is equal to the set of all multi-hot encodings, i.e., X = D, and for every x = (.i,...., #D) E Xz. we can simply choose Φx = 0n A... A o'p where ag pi if 2; 1 and a; -p, if 2;, 0.
22

---

Next, let >>> O. By induction hypothesis, the claim holds for X Let us consider pairs (z, 2) where Z 1 and Z is a multiset of vectors belonging to X such that Z has cardinality at most N. Note that there are at most finitely many such pairs. For any such pair let ((z be the GML--ormula
Φ
(02 -02++
occars with cardinality
We now define our formula dx as the disjunction of (z..2) for all pairs (z, 2) for which holds that COM2 (z AGGz(Z) = It follows from the construction that (G,v) } dx if and only if emb/(0) x.
B Proofs of logical characterizations in sections 3 and 4
We prove several lemmas building up to uniform translation from HES-GNN-(d., to GML W
(theorem [B.5) and a converse uniform translation for graphs with bounded degree (theorem B.6). The logical characterizations in theorems 3.4 4 and 4.1 follow with small additions adjustments to the proofs. We will use Ox for 0
-Mene)-sentencee Proposition B.1. Every GML(1, @ sentencc is equivalent to a GML(() sentence of the same J-nesting- depth over unordered graphs.
Proof. Let & be GMI.(4. @) -entennce. Let n be the modal depth Φ that is, the maximal nesting depth of the modal operators in the sentence, and let ø' be the sentence obtained from ø by replacing every subformula of the form @₂ e by
V O= 222 length
O (0.-
Clearly, o' has the same J-nesting-depth as Φ. A straightforward induction proof shows that á and d' are equivalent on unordered graphs. Intuitively, this because all variables in & are bound, and bounds the distance between nodes in the subgraph that the formula á can "see".
Proposition B.2 (Canonical Form). Let Nd (+) be the number of W operators in $ that have sb in
their scope. For each GML(WW-) sentence á there exists an equivalent GML(4W-) sentence up such that for every subformula of the form 4 x. W'W V', i = d Na (w²). We call such v canonical.
Proof. We assume the proposition holds for d and apply induction over formula construction in ) ). Let Φ1 E GML(UW-). and & = L x. WT Let t/ be the canonical form of Φ1 and construct of substituting free occurrences of x; in the by ra+1- Then:
1/ 4. Ai
Clearly / = Φ. and for every subformula 4 x.. W v6 in ub we have j= = Now (w)). Canonical form is maintained under construction with the other connectives 02k).
Lemma B.3. Given a finite tuple (A?,...." where S m, A is a (D, (D,D'N,,NN, there exists (D,m- D'N-GNN A such that (G))( A ( Moreover, all A
15$5m
use the same pointwise aggregation function, then uses the same aggregation function, and if all A use ReLU-FFNNs as combination functions, functioon the same holds for A.
Proof. For each j let A = ((COM)) (AGO))==1..... L,). Without loss of general- ity all A' have the same number of layers L'. Let L = L' +1 ((CoM)) (AGG:):=1.....)) The first layer copies each embedding m times, ie. for v, v' R:
1. We construct A
COM (OM(() = + (v).
1575m
23

---

Given combination functions COM let COM apply each COM; on the associated subspace: SSim
COM (o) Um..Um) @ (uf ..... mm) =
(COM) (v, ① vf))
15i5m
Similarly, given aggregation functions AGG let AGG 1535m
behave as:
AGG (M) = mm
(M)))
Sm
Here, for AGG, M( + R M is a multiset embeddings Risssmm D3 and Mj the multiset of embeddings in &D,, obtained by restricting each embedding in to indices Ey Dy', Ejyy Dyr. Note that if each AGG, is the same point-wise aggregation function (e.g.
sum), then AGG the same point-wise aggregation function on the concatenated space. ms
We define the remaining layers of A as:
A/ > 1: AGG; = AGG1-1 15f5m
W 1: COM: COMI-1
15j$m
Corollary B.A. Given a finite tuple (A' ....AA)) where for 1 j m. A is (D, (D)--EES-GN with nesting depth d and radius there exists (D, 10 D')- A with nesting depth d and
radius r such that (G) = + (run (G), Moreover, if all A use the same pointwise 15ism
aggregation function, then A uses the same aggregation function, and if all A use ReLU-FFNNS as combination fianctions, the same holds for A.
Proof. For d = O the claim follows from the above lemma. For d > 0 and A = (Bi,C) construct A (B, C) where rung(G)(u)
+ 15jsm
(rungs (G).
C follows the construction of the above lemma, with the exception that the first combination function does not copy the complete vertex embedding m times. Instead, COM, now receives vertex embedding u + (Uz). where the original vertex embedding and by is the output of B) and
Isjsm
produces output
v.))
15ssm
Theorem B.5. Given a finie tuple (#1...., (0m) where for 1 S S m, 6j is a GML(W sentence with propositions in P, there exists (PP) HH--GGGNN A with nesting depth d and radius such that for all G labeled with (G) = ① (cls,, (G, u)).
Proof. For = O, following the uniform translation from GML to GNN of proposition 2.3 there exist a GNN A, such that run,,, cls By lemma B.3 there then exists a GNN A that produces the concatenation of outputs for each Aj.
We apply induction over d. It suffices to show that any single sentence ø in GML(U is implemented by single HE-GNN A, since we can construct a HE-GNN with concatenated outputs following corollary B.4
By lemma B.2 we can assume is canonical, hence for every maximal subformula + x; ..,W" (W)) in 6, i d. Let I Fa. W "h....,4 Z.. Wh be all such maximal subformulas. By the semantics of GMI ). for all < Kjs S k:
G v H WT (1b)) iff
G H u/.
1bj
24

---

Now when is treated as binary node feature, by is sentence in GML(WW-)) There thus exists HE-GNN Bj such that
rung, (Z u1) cls,, (G + u), cls t,,, W (r) (G,
We construct single HE-GNN with nesting depth 1 that outputs the concatenated outputs for all such Bj, following corollary B.4
rung (C ol)(v)
cls (et)) 15i5m
Now construct 6² from by substituting each L.a.WWa,, by with proposition qy- Given G (V, E, lab), let G (V, lab),, where lab extends lab so that q lab (u) lab((u) Tg. W. Then:
iff G,u F
cls v) cls (G".")
Note that 6" GML. Hence by proposition 2.3 there exists GNN C such that for A (B,C):
cls (G', = ruma(G" (G*, v))
(G,
Theorem B.6. Let A be (D, with D [P], nesting depth d, radius Let N and
X= (mm))) (V, E, is a graph of degree at most N and v E V}
Then X is finite set, and for euch x E X there is a GML( sentence tx such that for every pointed graph (G, v) of degree at most N it holds that G, -o Øx iff (un)(G)(v) = x. In particular, for each HES GNN-(d,r) classifier cls there is a GML(W sentence & such that cls cls v) for all pointed graphs (G, of degree most N.
Proof. We apply induction over d. The case d = 0 reduces to the translation from GNN to GML of proposition 2.4 Let (B, C)) be HES-GNN with depth d and radius r. is finite since B has finitely many output embeddings by the induction hypothesis, and C produces finitely many output features on graphs with finitely many input embeddings as shown in the proof of proposition 2.4
Let emb" = (emb(u') @ 8 u'' E Vj. then for each x E X:
run (G) iff
runc (emba(w) @ """, u E (v) iff
(Gnc(G")
Where given G (V, E. lab), G (V, E, lab") and lab* extends lab with propositions for all output features of B. Specifically, let Yg (y1,...-yys be this finite set of output features and introduce .t...q/all such that Øj E lab" (u) if and only if (ung(G",,eml emb") (u) Yj-
By proposition 2.4 there exists sentence in GML such that:
G --, = iff (G)) =
Then let dx = S(..a.WWrr " W /q.................... ........0 qyal]-
Here all 1z L. are sentences in GML(L by the induction hypothesis, that the same holds for dx-
Small adaptations be made to the proofs of theorems B.5 and B.6 show (HHF-GNN-d) p(GML(4)) where now all operators 4 are removed and no subgraph restrictions are applied. Since HE-GNN = U22oHE-GNN-J and GMI.(L) = GMI follows that p(HF-GNN)) = p(GML())). That is:
25

---

Theorem 3.4. ((HE-GNN) - PL)ML(L)). Moreover. for d 2 O. p(HE-GNN-d) = P(GML(J"))
Lemma B.7. Letr 2 O, then p(GML(()) S p(GML((
Proof. Let di E GML(LW.)) We define sentence &, which only holds at vertices of distance S r to T4:
{ = -
V 15
O5z,
Now take minimal subformula of the form Warh in Φ. We substitute this for equivalent subformula tr,,t', where 6 in de is replaced by (E* 7) to produce vir.
Applying this transformation recursively to subformulas in 6 yields an equivalent GML(4 sentence.
Theorem 4.1.
O(HES-GNN) = p(GML(Uw)) =
1 p(GML(J) = p(HE-GNN).
2. p(HES-GNN-r) p(GML((W-)). Moreover P(HES-GNN-(dr)) p(GML()(r-))
Proof. Theorems B.5 and B.6 yield ((HES-GNN-d.))) - p(GML( for all d, 2
Since HE-GNN-r U4zo (222HEES-NNN-CA GN.- and GMI.(Ww.) U22o GML point (2) follows.
Similarly, taking the union over all r 2 0 yields ((HES-GNN) = ((GML(W)) Finally, to see that p(GML(4w)) - p(GML(4)) note that when two pointed graphs are separated by sentence in GML(4) they are also separated by a GML(4w-) sentence where r is the size of the largest of the two graphs. Using lemma B.7 then ((MML(W)) p(GML()))
C Proofs of hierarchy results in section 4
Theorem 4.2. For d 2 1, 2 0, p(HES-GNN-(drr+ + 1)) & ((HES-GNN-((L))
The construction of lemma B.7 also shows ol GML S (GML for d > 1,r > 0. Us- ing the logical characterization theorem 4.1 then p(HES-GNN-CL) GNN- + 1)) S p(HHES-GNN-CAE
Now to show (HN---GN-(ddr--- + 1)) * pHEES- ([HES-GGN-(ddr))) consider graphs G₁ Car+6 and G2 consisting of two disjoint cycles C2r+3, where all vertices are labeled with the empty set.
Let U1, U2 be nodes in G1, G2 and Φ = wrr+++ (0r+1(-022))) Then:
G1 11 } 0
G2, 1/ #
Again applying thcorem 4.1 (G1,v1) and (G2, U2) can be separated by HES-GNN-(dr + 1) for d 1 1.
However, the marked induced subgraphs with radius around U1, U2 are isomorphic and hence cannot be separated by any HE-GNN. Since (G1, v1). (G2, U2) are further indistinguishable by WL:
AP 2 0: ((G1, v1), (G2, v2)) E ((HES-GNN-(..)))
Theorem 4.3. For d 2 0 and r 2 3, p(HES THEES-GN-(dd + 1.r)) ((HES-GNN-(dr)))
This follows from
p((d + 2)-GNN) C ((HH-GNN-)) S ((HES-GNN-(dr)) p((d + 2))-GNN) & ((HEESGNNN(d+ 1.r))
Theorem
Theorem 5.12
26

---

D Proofs of relations with other models in section 5
5.1. Indriidualizatioo-RRiennne
Proposition D.1 ((38, 50 Let n, D E N. Then there exists a GNN A such that for all fea- tured graphs (G, emb), (G", emb') of size < and with embeddings in RD, if WfLLG, n)(v) + WL(G', n)(x') then A (G)(o) o run (G") We call such GNN sufficiently separating
Lemma D.2. Let n. d, D E N. Then there exists a sufficiently separating HE-GNN A with nesting depth d such that for all featured graphs (G, emb), (G', emb') of size S n and with embeddings in IR, if ((G, v), (G','') & p(HE-GNN-d) then (u)nx((G(()) * run (G') we call such a HE-GNN sufficiently separating.
Proof. When d = 0 this reduces to proposition D.1 Suppose d > O. Let B be a sufficiently separating HE-GNI for n, d - 1, D and let C' be a sufficiently separating GNN for D', where D' is the output dimension of B We define A C
Now suppose HE-GNN A'' (B', .C') with nesting depth d separates (G, v) from (G', w²). Since Ca sufficiently separating, (B', C*) least as separating as C"). Since Ca has the separating power of WL. up to size and since 3 has at least the separating power of B², (B*, C*) is at least as separating as (B',C*)
Notation Assume an injective map f from the infinite set of colors C to an infinite set of binary node labels (propositions) P. Given a graph G (V, F,, lab) we write GwL for = (V; E, lab'), where lab' is obtained by first computing the coloring col WL(G, (G]) and then labeling each node V E with ((co(())).
Lemma D.3. Let (G, v), (G', v²) be pointed graphs such that |G| = |G'| If ((G, (G', (HE-GNN--) then ((GwL, v), (GwL,)')) E p(HE-GNN-d).
Proof. We apply induction over d. For d note that p(HE-GNN-O) P(GNN) p(WL). Let v), (G', u') be of size n, with labels in P, such that ((G, v), (G', E p(HE-GNN-d) for > 0.
By lemma D.2 there exists sufficiently separating HE-GNN A -B*,C*) We show (GwL, v). (GWL, 0') E A()
Suppose for nodes in G and u' in G², are given the same output by 1 after individualizing w'. By the induction hypothesis, the same holds for u in GwL and u' in Gw.. Since C is sufficiently separating and since the input embeddings given by C are not more separating for GwL. Gw. than for G, G", it follows that (GwL, v), (GwL, v') E ((HE-GNN-d).
We apply the following lemma from Zhang et al.
52
Lemma D.4. Let G = (V, E, lab), G' = (V', E', lab') be finite connected graphs with o E V, e V' uniquely marked. Then:
(L(G)(o) = (V' iff (WL(()) nEVE= (WW((" I''ev'
Theorem 5.3. For d 2 0, ifG FIL. G¹, then G #HE.ONN.d G"
Proof. We apply induction over d. At O, the claim follows since p(GNN) = (WL.. Suppose for graphs G, G' with labels in P and d 0, G FNE G², then |G] = |G". We show
G EWL-IR(d) G..
By lemma D.2 there exists a sufficiently separating HE-GNN A =B8", (B*,C). Since:
{rum (G, v) | e E VB = AI (G', (G','') E V'B
there is bijection f between the two multisets, such that for all V and for unique proposition g: rung- Lung:(Glo-oa) (G(o rung- ((
Let C (if( be the connected components containing u and (u). By lemma D.4
[rung- ((C)) (w)))))))))))))) w C"B frung- ((C/(() (()) (w) w E cf()) }
27

---

Since these connected components then also obtain the same multiset of output embeddings without unique marking, this equality extends to the full graphs G, G":
{ ruung (Gi w V frung- (C f(a))
V"B
It follows that G, G' are indistinguishable by WL-IIR(d 1) after marking and f (u) and applying WL:
frung (Q-((o))))L(((r w E VB Krung. (G (W))))))))))))))))))))))) w E V'B (Lemma D.3
)WL -HE-GNN-(d (G (o-+S(w))
(Lemma D.2
(G/g-zu) WL- (d- fg)+)
(Induction hypothesis)
Since WL-IR(G, d) obtains the same depth
subtrees as WL-IR(G", d), G WWL-R-- G".
Theorem 5.4. Let (G, v). (G', e²) be connected pointed graphs and let d 2 0. IfG FWL-IRdd G², there exists depth d HE-GNN such that cls A v) + Als v').
Proof. Let d 2 0. Suppose (G, v) =HE-GNN- + (G', v'). We show WL-IR-d G'. For sufficiently separating HE-GNN A ( with nesting depth + 1:
r-
Thus, for unique label g:
rung- (Gig)o)) s- (Gi (v))
Then since G, G' are connected:
frung- (G (w) u E V = Krung (G (o()))))) | EV
(Lemma
D.4
G HEEGNN-d G
(Lemma D.2
G ERL-IR-d G'
(Theorem
5.3
U2
F2
G
G
Figure 5: Two graphs that are distinguished by depth HE-GNN, but not by WL-IR-1. All nodes in both graphs have an empty labeling.
Theorem 5.5. There exist G, G' such that G =WL-IR11 G' but G #HE-GNN-1 G'
Proof. We use two graphs G, G' introduced by Rattan and Seppelt [44, and shown in Figure 5 G has square U1, U2, U3, U4, where i1 connected to nodes two triangles, the same holds for и4 and two different triangles, and uz2 U3 are connected to all nodes in two distinct 6 cycles. G' is constructed similarly with a central square U1, 12, V3, U4, where now ej and vg are each connected to two triangles and 02, Ei connected to distinct 6 cycles.
28

---

To see G -WL-IR-1 G' note firstly that the two graphs are WL equivalent. Furthermore, there is a bijection f between nodes of G and G', where for each node in G, applying WL G after individualizing yields the same coloring as applying WI. to G' after individualizing f(u). We let f(w1) 11, fu2)
02: [ = 03, f((4)) 14, map every node in a triangle G to a node in triangle in G' and do the same for nodes in the 6 cycles of G and G'. One can easily check that this gives the desired result so that G -WL-IR-1 G".
We now show there a GML(WW=) formula v that satisfied by un but not by any node in G'.
Φ = (228(T) A 04 (= (T) ( ( (x))))
= O 00
Here, & expresses having degree least and being connected to a node on 3 cycle that doesn't pass node with degree at least 8. u1, u4, v/ and are the only nodes in G, G' that satisfy d. Thus G, U1 + v. while no node in G" satisfies v. By the logical characterization in theorem 3.4 there exists HE-GNN A such that G FasA G¹.
5.2. Homomorphism count enriched GNNs
The definitions of homomorphisms and homomorphism counts were omitted from the paper due lack of space. They are as follows: homomorphism from pointed graph (F, u) to pointed graph (G, v) is map from the vertex of F to the vertex set of G such that
1. for each edge (w, w') of F, (h(w), h(w)))
) is an edge of G.
2. for each vertex of F, (wb)(w) C (aba(((w)) and
3. h(u)=
Homomorphisms are defined similarly for unpointed graphs G, where we simply omit condition (ii). We use hom((F, ((FF u), (G,v) to denote the number of homomorphism from (F, u) to (G, v). In addition, if h is partial map from the vertex set of to the vertex set of G, then we denote by hom,, (F, G) the number of homomorphism that extend h. In particular, (w.) G) hom((F, (F, u), (G,v)).
For set of pointed graphs 3 {(Fi, 2n ..... (F., }m)} and pointed graph (G, v), denote by h8m (G, v)) the vector of homomorphism counts
(hom((F1, u1), (G,,)))..,,,,(((( um), (G, u)))
(assuming some ordering the members of 3).
Theorem 5.6. Let $ be any finite set of rooted graphs each with at most nodes. Then there is a (IP), PI + -EE--NG A of nesting depth d such that, for all pointed graphs (G, v).
(G) embg(v) hom (3, (G,u)) v))
The HE-GNN in question only uses Sun as aggregation and 4-FNNs as combination functions.
Proof. We consider the case where & consists of single rooted graph (F, u) with d nodes. The proof extends naturally to the case with multiple such rooted graphs.
We will prove the following stronger statement:
(*) For all sequences (ui...., u&) of distinct nodes of F (with & > 0), there is (D k 1) HE-GNN A of nesting depth d - k, such that, for all graph and maps h {ui...., 2x] + VG.
run (G,,G.,mb.) (embt))(((u) (h(u))) home (F,
where emb:? +hh {w embo(w) @ (Dwrt(n))) .... B(ch(w)))) | VG).
Observe that the special case of (*) with & = 1 and = yields 1, B of nesting depth 1 such that
rung emb'))
hom( u), (G,
where emb', = {w emba(w) (w) (fw)(1)) w E VaJ. Let C be the trivial (|P|+1, PP that implements the identity function. then follows that AA (B, C), which is 1) of nesting depth d, has the desired behavior.
29

---

It remains to prove (*). The proof proceeds by induction on the d - k. When k = d, the partial function h is in fact a total function from the node set of F to that of G. It easy to implement GNN that, in this case, outputs 1 if h is homomorphism and outputs 0 otherwise. Indeed, this can be done using only ReI.U-FFNN combination functions and Sum aggregation, and using at most |Vel many rounds of message passing. We omit the details, as they are straightforward.
Next, let 0 k d and assume that (*) holds for + We will show that it then also holds for k. Since > 0, there are nodes of J' that do not belong to the sequence (ui,...,,, uz). It follows from this, by the connectedness of F, that there is an edge of connecting some u, (with i k) some As a basic fact about homomorphism counts, we have
u' & (uI..... )
hom, (F, G)
Σ
n' e'EV such that (M(M)) "
We now apply induction hypothesis to (u1..... Ug, 2²). obtaining a (IP) + 1.1--EE-GN B. Let C be (IPI + 1, IP] + 1)-GNN that performs one round of message passing using Sum aggregation and using the combination function
COM
x', 21 Sp|+ z²)) = (x , TIPH+:)
(i.e. summing up the values in the Pl + h: + 1-th position across all neighbors, and keeping the other values in the vector the same). Let (B, C). It follows from the construction that
r (G, emb e (h(())) = hom, (F,
In other words, after running A. "node h(u,) knows the answer". All that remains complete the construction, is to "pass this information from h(u)) to h(ug). This can be done by augmenting C with |Vpl more layers message passing (because lu())) and h(uu)) ) are at most [Fl distance apart).
We omit the details which are straightforward
Lemma D.5. For every pointed graph (F, u) of ego-rank there is a witnessing dep-function (i.e., with maximum node rank 1)) such that
1. dep is well-founded, ie,, v + (v) for all v and n 2 1.
for all nodes v, every connected component of the subgraph induced by dep- contains a neighbor u. Equivalently, when dep(w) = 0, there is path from e passing only though nodes w' with dep(w')
Proof.
1. If dep is not well-founded, there is cycle
U1 U2, D3....,
where dep(u:) vi+1 for i < and (V,) e1. Note that, in this case, deps(11) deps(1z) deps(ux) = (UI,..., J.
Fix such cycle, and let dep' be identical to dep except that (i) dep' (v.) = 1, and (ii) for all v & (ui,..., J, dep(v) {u1,..., Un then dep'(v) (v) = V1. Note that, in this way, deps' (v) = deps(u) for all u of (Vi,..., ).
We claim that dep' still satisfies the conditions given in the definition of ego-rank. Indeed.
(u) is still 1.
Let (w, v) E E be an edge. Then one of the following three cases holds:
(a) dep(w) = dep(e). Then the same holds for dep', except possibly if w & fri...., } dep(w) E (ui,..., and e E (uI...., U,)). However, in this case, we have that dep' (w) = and hence u deps'(w = (vi,...,th} "n).
(b) w E deps(v). It follows from the construction of dep' that, for all v E {r). Un } deps'(v) (v) deps(r). Therefore, we only have to consider the case that v E (VI,..., ). If E (ui....,
......,,), )n then we have either w E deps'(r (v) or E deps' (w) (note that + w). Otherwise, by construction, dep' Uj and hence E deps' (w).
30

---

11
U2
143
24
U6
11
04
Figure 6: Rooted 5 x grid
(c) E deps(w). This case is symmetric to the above.
Finally, we must show that, for each V VU {L), the subgraph induced by dep' (v) is acyclic.
For each node u o U1, we have that de) C dep--(w), and hence, since dep (v) is acyelic, so is (v). Therefore, it remains only to consider dep'-1(1) and dep' (11).
Suppose there were cycle in the subgraph induced by dep'-1(L), node U1, while all other nodes u on the cycle satisfy dep(u) = L. However, it is easy to see that there can be edge connecting ei such node u.
(LL.. This cycle must contain the
Finally, suppose there were a cycle
Wi...., wk
in the subgraph induced by (e1) If dep(w)) = dep(w2) _... dep(wx) = us then the subgraph induced by (c:) would already have cycle, which we have assumed is not the case. Therefore, the cycle must include an edge connecting nodes w; and w1+1 where dep(w:) of dep(w:+1). Note that w;, W;+1 & fei..... Un and that dep(w;), dep(w;+1) E (uI...., }. Such an edge cannot exist as it fails satisfy the second property in the definition of ego-rank.
2. We assume dep satisfies property 1. Let dep(w) = e and suppose that property fails, i.e., there node with dep(w)
such that node w' reachable from in the subgraph induced by (w) is adjacent to e. Let dep' be identical to dep except that, for all w' reachable from w in the subgraph induced by dep- (ep) and hence the net effect of this change is that deps'(w") deps(w") \ {v}. We claim that deps' still satisfies all requirements from the definition of ego-rank. Indeed:
set dep' (w') = dep(v). Note that, by property & deps(v)
dep' (u) is still L.
Let (w1, w2) E be an edge. Then one of the following conditions holds:
(a) dep(w1) = dep(wz). Then the same holds for dep' (note that wi and wy belong to the same connected component of dep ((dep(w])))
(b) E deps(w2) or vice versa. It is easy to see that, in this case, the same still holds for deps'.
Finally, we must show that, for each æ E V [1L) the subgraph induced by (x) is acyelic. suffices to consider the case where x = dep(v), because, for all other we have that dep'=1 (I) C dep- (z). Therefore, let dep(v) and suppose for the sake of contradiction that dep' (1(() (z) contains cycle. Since dep (x) and dep-'(e (v) were both acyclic, this cycle must include an edge (W1, W2) such that dep(w,) = and dep(w>) = r. It must then be the case that u2 E deps( (1). and, indeed, must be the case that w2 v, a contradiction since the connected component of wi in dep-11 (v) was not supposed to be connected to v.
By repeating this operation, we obtain a dep-function satisfying property 2.
Proposition D.6. The rooted n x 2-grid (with n 2 1) as depicted Figure has ego-rank
Proof. For the n upper bound, a witnessing dep-function is already depicted in Figure 2 for the special case of n = 5, and it can be modified in the obvious way for the general case (note that there are also other choices for the dep function that yield the same ego rank). In what follows, we prove the n 1 lower bound.
VUR (T] be any function satisfying the requirements in the definition of ego-rank. We may assume that it also satisfies the properties described in Lemma D.5
Let dep
Recall that is the root of the rooted graph. We show there is sequence
(1 n2 ..., mT)
31

---

where U1, and for i >> the following holds:
1. n; Uu
2. Either (i) dep((Ts) 7i-1 or (ii) dep(ass T/-1 and dep?( a/-11
u4-1 if T4-1 U4-1
where x/-1
0i-1 Ti=1 Wi-1
We apply induction over > It follows from the induction hypothesis that deps( doesn't t contain any uj. Vi with j 2 i 1. Suppose w.l.o.g. that x;-1 u;-1- Note firstly that either u4-1 E (eps(1;-1) or u E deps(u.). For, if this would not hold then, by definition of dep, dep(u;-1) = dep( = dep(u,). which by well-foundedness leaves no possibility for dep(w;).
Since every connected component of dep-1(ug-1 is connected to u4-1 it follows that u4-1 dep(u,) or - dep(v;-1). In the first case we let Ti U4.
Suppose then that u;-1 dep(u=-),. then either u;-1 dep(us) (s) w;-1 deps(u:) In the second case, by well-foundedness and the connectedness of dep dep- (m:-1) to U/-1 1 follows that 0:-1 dep(e:). In both cases we let T, Us, completing the induction.
Since [deps(T.) [T.) 2
the lower bound follows.
Lemma D.7. Let (F, u) be a rooted graphs and > O. Then there exists number M such that, for all pointed graphs (G, u) of degree most N, hom u), (G, v)) M.
Proof. Let r be the maximal distance from any other node of F. The radius-r neighborhood of v in G contains at most (N + 1)" nodes. It follows that there can be at most M = ((N + 1)") homomorphisms from (F) to (G, v), where is the number of nodes of F.
Lemma D.8. ReLU-FFNNs can multiply small natural numbers. That is, for each N > and > 0, there is ReLU-FFNN with input dimension l and output dimension that, input (Z1..... 2x)
with < I; I N, outputs II
Proof. This is well-known (and holds not only for ReLU but also for other common non-linear activation functions). For the sake of completeness with a ReLU-FFNN, for a given natural number æ, whether 2 m. Indeed, if this holds and otherwise. Furthermore, the Boolean operators of conjunction and negation can be implemented by ReLU-FFNNs as well (cf. the proof of Proposition 2.3 It follows that the function
sketch proof. First, for fixed m, test
(m (11, (11,.... FR) {1
if 2; m; for all i S k
otherwise
can also implemented by ReLU-FFNN. Using this, we can represent the product Iı, by the linear expression
Σ [Imm . fmm....me) (x) (21..... 224)
0Sm1
Note that the IIm; factors are viewed as constant integer coefficient here.
Proposition 5.7. For all rooted graphs (G,u) with G = (V, E, lab), ego-rank(G,, v) S [V].
1. (ree-witth(G)
2. ego-rank(G,, 0 if and only G is acyelic.
3. ego-rank(G,
whenever (G, v) is c-acyelic.
Proof. For the first part of the first claim, let dep be function witnessing that (G, v) has ego-rank k. We define a tree decomposition as follows:
The nodes of the tree decomposition are (i) all nodes of the graph G, and (ii) all edges (w, v) of the graph G satisfying dep(w) (w) = dep(v). The bag associated each w is (w) U deps(w)) and the bag associated to each edge (w, v) is (w, v) U deps(w).
32

---

The edges of the tree decomposition are pairs where one node is node of G and the other is an edge of G in which the node participates.
Note that, in this way, every edge of G' is indeed contained in a bag. Furthermore, the third condition in the definition of dependency functions guarantees that this tree decomposition is indeed tree.
Consider any path in the tree decompositions of the form
wi (wi, W2) w2 (W2, Wa) .... (w,-1: w,) Wn.
where dep(w;; dep(w,; for all i < < n, and hence w, * w for all < < n (because the subgraph induced by dep (dep( (w;) ) is acyclic). Suppose, now, that some graph vertex belongs to the bag of wi as well as to the bag of Wp. In this case, z must belong to deps(w:) (w1) and to deps( (w,) and hence it belongs that start or end with an edge. This shows that the constructed tree decomposition is indeed a valid tree-decomposition. Moreover, the maximal bag size k + Therefore, the tree-width of G is
the bag of each node on the path. similar argument applies for paths
most k + 1.
For the second part of the first claim, it suffices to choose arbitrary enumeration v1, U2.... Un of the nodes of G. where U) = v, and set dep(11) v1) ) = I and dep((e+1) U/S
The second claim follows immediately from the definition of ego-rank. For the third claim, it suffices take dep(e) 1 and dep(v') for all o' +
The next theorem is not stated in the body of the paper, but it's a special case of Theorem 5.9 below, and it serves as a warming up towards the proof of Theorem 5.9
Theorem D.9. Let 3 be any finite set of acyclic rooted gruphs. There is a (IP). + [ A such that, for all pointed graphs (G, v), (G))v)))u) = embg(v) @ hom(3, v)). The GNN in question uses multiplication in the combination function.
Proof. In what follows, we will refer to acyclic rooted graphs (F,, u) also as trees, where we think of u as the root of the tree. By an immediate subtree of tree (F,, u) we will mean a rooted graph (F", u²) where is a neighbor of u and where F' is the induced subgraph of F consisting of all nodes whose shortest path to contains u'. We will write (F, (F", u²) to indicate that (F", u') an immediate subtree of (F, u). By the depth of a tree (F, we will mean the maximum. over all nodes u' of F, of the distance from to u'. Note that (F,u) has depth zero if and only if it has immediate subtrees, and that the depth of an immediate subtree of (F, u) is always strictly smaller than the depth of uF,u).
We may assume without loss of generality that 3 is closed under taking immediate subtrees. The general case then follows by adding one additional layer on top that projects the resulting embedding vectors to subset of 3.
Let 8
[(F1, u1). (Fu, ux)} and let L be the maximal depth of a rooted graph in 3. Let
A ((COM)) (AGG.);=1....)
where
COM : RR2[P| - IR Pl+ given by COM (x P|p) ..... pp) = (81, -1p1))))))) with
= 2g for i < PP] and with
4| {
F; has depth 0 and x = for each pj E lab" (u:)
otherwise
For i > 1, COM; ((+()) PI+ given by (Z), 2 ,1pp4)))))))))))
(yi...., ((P with y, x, for i < [P]. and with
II
(2114))) if xg = 1 for each pa E lab Ri (u))
U|P1+
Fy with F; > F3
0
otherwise
Each AGG, is (pointwise) sum.
33

---

It is not difficult to see that COM, can be implemented by FFNN using ReLU and multiplicattio. It follows from the above construction, and by induction d, that, for all d 2 0 and for all (F), uz) E 8 of depth d, (m) + hom,(F) uy), (G, v)) for >> d. Furthermore, it is immediately clear from the construction that emb)gu) embo(v)()) for all j j= IP].
Theorem 5.9. Let & be any finite set of rooted graphs, let = (ggoreg--ann(( F, u) (F,u)
1. Then there is (1 [P| + 1 HEE-GNN A of nesting depth d such that, for all pointed graphs (G, v). (G) (u) + hom (G, v)). The HE-GNN uses multiplication in the combination functions.
2. For each N > O, there is (IPI, + (81) -IE---EEGNN A of nesting depth d such that, for pointed graphs (G. v) of degree most N, ( = embç(u) @ hom (G, v)). The HE-GN HE-GNN uses only Sum as aggregation and ReLu- as combination functions.
Proof. We prove the first statement. The proof of the second statement is identical, except that replace the use of multiplication by a ReLU-FFNN due to the fact that the numbers being multiplied are bounded by constant (ef. Lemma D.7 and Lemma D.8p.
We may assume that consists of single rooted graph (F, u). Let dep the dependency function witnessing the fact that (F, u) has ego-rank d. By Lemma D.5 we may assume that dep is well- founded, and that for each node w, if dep-- (w) is non-empty, then each connected component of the subgraph induced by (w) contains neighbor (in the original graph F)) of
By the dependency depth of a node w of F, we will mean the largest number for which is the case that w - dep' (w') for some w'. Note that this is a finite number.
For node w, will denote by Fw the subgraph of F induced by the set of nodes deps- U {w} U deps(w), where deps - (ww) is the set of nodes w' for which w E deps(w).
We will now prove the following claim:
(*) For each node of dependency depth f 2 with deps(w) fwi,-... w there is (IP) k - 1, 1)-HE-GNN Aw of nesting depth L - 1 such that for all graphs G with vertices Vo and maps h {w} U deps(w)) VG.
A ( th ( home (f G)
where emb +h {0'= (mb @ (8oth(11): ..... o ul E VG).
Recall that hom, (Fw, G') denotes the number of homomorphisms from Fwr to G extending the partial function h. Also, note that the embedding vectors of emb by construction, include features that uniquely mark the h-image of each w' E deps(w) as well as w.
We will first prove (*) by induction on the dependency depth l > 1 of w, and then show that it implies the main statement of our theorem.
The subgraph Fw can be decomposed as described in Figure 7 By Lemma D.5 each connected component of the subgraph induced by dep of F includes at least one neighbor of w. Let (F", be the rooted tree that consists of the subgraph induced by {w} U dep (w). after removing, for each connected component of dep '(w). all but one (arbitrarily chosen) connecting edge w. Note that, as explained in the caption of Figure 7 there may be more than one edge between w and given connected component of dep--((w) but we only keep one in order to ensure that F" is a tree rooted at w. We refer to the edges connecting w to nodes in dep (w) that we did not add, as well as edges connecting nodes in deps(wt (w) to nodes in dep (ww as "back-edges".
Now, by construction, for every function h {w) U deps(w) + VG. we have that
homa G)
Σ
II
homnu((ee. (F G)
hamomopphisms f (F., k(w)) Edep ((n)
Note that the fact that we omitted the back-edges from F' does not impact the above equation. Indeed, if a function f (F', w) - (G, hww)) fails to preserve a back-edge will simply not extend to a homomorphism from Fw.; to G. and hence will not contribute to the above sum.
34

---

deps (wa)
deps - (wa)
deps (w))
W2
W3
W
dep (ep-((w)
deps (w1)
W1
W
deps(w)
Figure 7: Decomposition of the subgraph Fw induced by deps(w) U {w) U (wps= when w has dependency depth greater than 1. The gray circles are disjoint. In addition to the edges drawn in the picture, there may also be additional edges connecting nodes in deps deps-1(w) to nodes in {w} U de) We omitted such edges from the drawing order clutter the picture.
Now if l 1, ho ((=))) Fey G) is either 1 or 0 since every vertex of Fw, in the domain of h U {ww,, / (w:)). ).. Since all nodes in the range of this function are uniquely marked, this can be computed by a (IPI + 1) GNN Cu,, i.e. HE-GNN of nesting depth 0. More precisely, for each o' G:
run (G, e thul(w))')) (o')
((w, (Fary G)
These can combined using Lemma B.3 into a single GNN C computing their concatenation. We now add layers, exactly as in the proof of Theorem D.9 that run through the tree (F', w) and aggregate the respective counts according to the above equation to compute hom,, (Fw, G.).
If [ > 1 we can apply the induction hypothesis (*) to obtain a (IP) + k + 2, 1)- HE---GNN Bw, of nesting depth at most 2 for each w; E above equation. Now for each v' E G:
calculating the corresponding factor in the
r.n (G, emb thu((,,
=om) (Fw. G)
These be combined using Lemma B.4 into single HE-GNN (B, of nesting depth e computing their concatenation. Now similarly to the case for 1, we add layers to C that run through the tree (F" w) and aggregate the respective counts according the above equation and call the result C", Let Z be a trivial GNN. Then A = ((B, C'), is (IP) + 1, 1)-HE-GNN of nesting depth f- that computes hom,, (Fww G), concluding the proof by induction of (*).
Finally, we must show that (*) implies the main statement of our theorem. Let (F", u) be the induced subgraph of F with nodes in dep (L). Then again:
(IF, u), (G,o))
Σ
II hom ((o))) (Fw,, G) WFE
homomorphisms, f (F', 1) (G.v)
The argument now is very similar the dependency depth at most d, by (*) and theorem D.9 we obtain for each w; E F', a (|P) 1, HHF GNN Bw: of nesting depth d - computing the corresponding factor in the above equation. These can be combined using Lemma B.4 into a single (P + 1, [FI))-H--NN
used in the inductive step. Since each w; E F² has
(B, C) of nesting depth d 1 computing their concatenation. We again add layers C' as in the proof of Theorem[D.9] run through the tree (F", u) and aggregate the respective counts according to the above equation, and call this GNN C'. Then for trivial GNN I, It follows that A ((B, C'),I) (1P), 1)-HE-GNN of nesting depth that computes homm(P: u), (G, v)).
5.3. Higher order GNNS
Theorem 5.11. For d 2 0, p((d+ 1)-WL) p((d+2)-GNN S p(HE-GNN-d). (
35

---

Proof. Let A be HE-GNN with depth d such that cls) + ( v7). By theorem 3.4 there exists GML(1 GML(L")-eentnnc" -eentencce & such that (Gs&(G, u) # cls, v'")
is equivalent to sentence that uses most d variables æ;. Hence there exists equivalent formula & in the d + 2-variable fragment of first-order logic with counting quantifiers (cf. Table 2 By
theorem 5.10 there then exists (d + 2)-GNN B such that cls o) & clsu(G,, v')..
We apply a lemma by Morris et al. [37]. which was slightly adjusted by Qian et al.
42
Definition D.10. For graph G = (V, E, lab), S S V forms distance 2 clique if any two nodes in are connected by a path of length 2. We say colorful for all v, of E S, lab(e) = lab(v') iff
Lemma D.11. For d there exist graphs Ga, Ha such that:
Ga (dd1))-w Ha
There exists a colorful distance 2 clique of size + 1 in Ga-
There does not exist colorful distance clique of size + in Ha.
Table Translation from GML(()-fomula & containing variables ; to
(Ø) containing variables 2, y, 21, . 2k.
(p:)
Pi(x))
tra(p))
Pi(x)
(ra
T. = 24
try(z;)
y=
(r A vp)
= tra(0) A (t))
(r)(
= tra(d) A (ty
(-
(t)
(-x(-))
try(
(02())))) }2"y( A (r)(d))
bry(02"d)
]2"x A (0))
(ra(t
= 3zi(zi = x A (r>(0)
= =Ja(zz = A (ry
Theorem 5.12. For d 2 O. HES-GNN-(d.3) can distinguish pointed graphs that cannot be distin- guished by d-WL, or equivalently, by a (d + 1)-GNN.
Proof. We show there exist formula E GMI.(L#s) and node e in Ga+1 such that G U but Ha+1, H é for all w in Ha-1-
Let be in distance 2 colorful clique S of size d + and let a1... ... aa-2 be conjunctions of literals matching the distinct labelings of nodes in S. Thus v' only satisfy the same if lab(v) = lab(v'). Further let G 01.
We let:
= WL 4 I32. x.. W W v) ...)))
....)))
& ensures that all I; have distinct values matching labeling specified by an.... Od, and form colorful distance clique of size
E = A (a,,
(00x;)))
15i5d
1SF$d.jii
v ensures that there are two more connected vertices with labelings matching ad+1, 0d+2 that have edges to all the z;z
s = 00(aat11 A A (90x,) A 00(aa42 A A (00x,))
ISiSA
ISiSa
Now Gat1, v - o and any node Haf1 satisfying would be in a distance colorful clique. Hence for all u' in Ha+1:
Ga+1, v FOMI(LC, Hat1, v'
We apply the logical characterization of HES-GNN (Theorem 4.1). the WL characterization of higher order GNNs and the fact that G4+1 (d-1)) WL. Hat1 to obtain the theorem:
p((d + 1)-GNN) (d-WL.) & (GMM))))))) = (HES GNN-(d3))
36


Reviews:
[{"review_id": "95xq7QLQax", "reviewer": "Reviewer_Gw3G", "summary": "This paper introduces Hierarchical Ego Graph Neural Networks (HE-GNNs), a class of GNNs inspired by the individualization-refinement (IR) paradigm used in graph isomorphism testing. The authors provide a logical characterization of HE-GNNs (and a subgraph-restricted variant), relate their expressive power to higher-order GNNs, subgraph-GNNs, and GNNs with homomorphism counts, and demonstrate empirically that shallow HE-GNNs offer improved separating power over traditional GNNs. The authors conducted experiments on ZINC-12k and synthetic regular graphs.", "questions": "- Could you please conduct experiments on a broader set of real-world datasets and compare HE-GNNs with additional, recently proposed expressive GNN baselines? I leave the choice of datasets and baselines to the authors’ discretion, but a more comprehensive empirical evaluation would greatly strengthen the paper.\n\n- The reference list is very weak. Please conduct a thorough literature review. Some related works can be found below:\n\nHuang, Yinan, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. \"On the stability of expressive positional encodings for graphs.\" arXiv preprint arXiv:2310.02579 (2023).\n\nKanatsoulis, Charilaos I., Evelyn Choi, Stephanie Jegelka, Jure Leskovec, and Alejandro Ribeiro. \"Learning Efficient Positional Encodings with Graph Neural Networks.\" arXiv preprint arXiv:2502.01122 (2025).\n\nBlack, Mitchell, Zhengchao Wan, Gal Mishne, Amir Nayyeri, and Yusu Wang. \"Comparing graph transformers via positional encodings.\" arXiv preprint arXiv:2402.14202 (2024).\n\nKanatsoulis, Charilaos, and Alejandro Ribeiro. \"Counting graph substructures with graph neural networks.\" In The twelfth international conference on learning representations. 2024.\n\nLim, Derek, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. \"Sign and basis invariant networks for spectral graph representation learning.\" arXiv preprint arXiv:2202.13013 (2022).\n\nNerem, Robert R., Samantha Chen, Sanjoy Dasgupta, and Yusu Wang. \"Graph neural networks extrapolate out-of-distribution for shortest paths.\" arXiv preprint arXiv:2503.19173 (2025).", "limitations": "Please see previous sections", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n- Theoretical framework is rigorous and unifies connections to higher-order GNNs, subgraph-GNNs, and homomorphism-count GNNs.\n- Logical analysis is novel and deepens understanding of GNN expressiveness.\n\n**Weaknesses**\n\n- Experimental validation is quite limited, focusing only on ZINC-12k and small synthetic datasets. There is no evaluation on larger or more diverse real-world benchmarks, nor ablations on computational overhead or scalability.\n- There are limited comparisons with related literature and several omitted works. Please see next section for more details", "was_revised": true, "final_justification": "The authors have addressed most of my concerns and have committed to expanding their experimental evaluation. Assuming these improvements are incorporated into the final version, I believe the paper will be sufficiently strengthened and is worthy of publication as a borderline paper.", "rebuttal": "We thank the reviewer for their constructive feedback and have addressed all comments in our revised manuscript. We appreciate the reviewer's assessment that our theoretical framework deepens the understanding of GNN expressiveness and unifies several existing architectures, which we indeed consider to be the core contribution of this work.\n\n**Experimental validation**\n\nWe have presented HE-GNN primarily as a foundational model, and recognize that further experimental validation would strengthen the paper. Addressing the first weakness and question raised by the reviewer, we aim to expand the experimental section as follows:\n\n1. We will compare performance with more existing architectures. Specifically, we aim to complement the SRG experiments with another Individualization-Refinement technique such as Tinhofer, and to compare performance on ZINC with other modern node-marking-based subgraph GNNs.\n\n2. We will add an ablation study varying $d$ and $r$, illustrating how HES-GNN transitions from standard message-passing networks to more expressive architectures in terms of both accuracy and running time.\n\n**Literature review**\n\nIn response to the second weakness and question raised by the reviewer, we have added a *Related work* section, covering part of the literature listed by the reviewer, as well as suggestions from other reviewers. Four of the references cited by the reviewer use positional encodings derived from the Laplacian of the input. This approach differs from the line of work leading up to our paper and addresses slightly different questions, such as perturbation stability. The work by Black et al. is closest to ours, since it analyzes separating power via extensions of the WL algorithm, and we agree that exploring further connections between these two approaches is valuable and interesting."}, {"review_id": "ZA4NkpsHSU", "reviewer": "Reviewer_et5K", "summary": "The authors study the expressivity of graph neural networks (GNNs) with hierarchical node individualisation. For that they propose a new model of GNNs that they name Hierarchical Ego Graph Neural Networks (HE-GNNs) and show how its expressivity can be captured by graded hybrid modal logic. The expressivity characterisation follows the line of work initiated by Barcelo et at. [4] where the expressivity of GNNs was related to graded modal logic. Hence the main contribution of the authors here is to extend this connection to GNNs with node initialisation, which is in the logical side represented by the binder operator of hybrid logic. They also study a variant of HE-GNNs, where message passing related to node initialisations is restricted to some k-hop neighbourhood of the initialised node and obtain a related logical characterisation to that model, and an expressivity hierarchy related to k and initialisation depth d.\n\nIn addition the authors introduce a variant of the 1-WL algorithm with node initialisation (WL-IR) and show that the separating power of depth d HE-GNNs is limited below by the separating power of WL-IR with d node initialisations (WL-IR-d). Note that, over graphs of size at most d, WL-IR-d is able to separate all non-isomorphic graphs.\n\nThey empirically confirm that depth 2 HE-GNNs have improved performance to distinguish strongly regular graphs in comparison to common subgraph architectures.", "questions": "1. What is the benefit or difference of your HE-GNNs of depth d compared to a simpler variant that would simply run a GNN on the |G|^d many copies of the graph with all possible and then have some aggregation via a GNN. That is, what is the benefit of the d-layer recursive definition.\n\n2. Could you say something on the topic of training  HE-GNNs of depth d. Can this be done in practise?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The topic of the paper is timely and the results are interesting. The paper is very well written. I did not find any major technical issues, though I did not check all the details from the appendix. \n\n\nWeaknesses:\n- The presentation of HE-GNNs is quite compact. A worked out example of a simple HE-GNNs  would have been nice to have.\n- There is not much discussion whether their GNN model is useful in practice. \n- In isolation the results are not that surprising, but the authors have done a comprehensive job in developing matching models of GNNs, logic, and WL-algorithm.\n\n\nMinor comments:\n\n- l. 151. Typo: \"in in\"\n- l. 161. Technically, in GML formulas with free nominals, you cannot eliminate the \"@\" operator. \n- l. 186. Typo: Period missing after the syntax of the logic.", "was_revised": true, "final_justification": "This is a solid well written paper that advances our understanding in the expressivity of GNNs and contributes to the growing literature connecting logics and neural networks. The results are not ground breaking, and as mentioned by others, the experimental part is quite limited. Hence, I think the rating of borderline accept is well justified.", "rebuttal": "We thank the reviewer for their constructive feedback, and have revised our manuscript accordingly. We appreciate that the reviewer considers the paper to be well-written, interesting, and sound.\n\n**Response to weaknesses**\n\n- We will add a simple example of a HE-GNN.\n\n- We have focused on formalizing and presenting the capacity of HE-GNN to express existing architectures, but this expressive power also leads to performance gains in practice. We will convey this more clearly by firstly adding a more precise complexity analysis, and secondly by extending the *Experiments* section. Specifically, we will attempt to compare performance on ZINC with other modern subgraph GNNs.  \n\n- We thank the reviewer for spotting the typos, which have been resolved.  \nThe reviewer correctly notes that @ cannot be eliminated in formulas with free variables. The paper only considers sentences (line 148), and we have clarified the claim on line 161 accordingly.  \n\n**Response to questions**\n\n**Question 1**\n\nThe first question asks for the distinction between HE-GNN and running a GNN on the $|G|^d$ many copies of the graph with all possible colorings, and aggregating via a GNN.\n\nThis is an interesting remark that ties into the discussion at the end of Section 5.4, since the model suggested by the reviewer can be implemented as an OSAN. It is not directly clear how the two models differ in terms of separating power, which also depends on the exact method used to aggregate over all colorings. We appreciate the question, which deserves further investigation.  \n\nA crucial difference is that combining features derived from $|G|^d$ colorings with a GNN requires exponential space complexity in $d$, while our hierarchical message-passing scheme requires only a constant number of stored features in $d$.  \n\n**Question 2**\n\nThe second question asks whether HE-GNNs can be trained in practice.  \n\nThis is partly answered by the experimental section. We train HES-GNNs with $d \\leq 2$, going beyond the separating power of $3$-GNNs on a single GPU. For larger $d$, the runtime behavior requires restricting the radius $r$.  \n\nWe will further address this question quantitatively in the paper by adding an ablation study, comparing the runtime and performance of HES-GNN for varying $d$ and $r$."}, {"review_id": "rPbkF6GtUE", "reviewer": "Reviewer_bFLP", "summary": "This paper introduces Hierarchical Ego GNNs (HE-GNNs), which augment standard message-passing GNNs by recursively “individualiing” a chosen node, marking it uniquely, and re-running a base GNN to capture increasingly fine-grained local structure. By nesting this individuation process to depth $d$, HE-GNNs form a strict hierarchy: at depth $d$, they match the distinguishing power of $d$-nested graded hybrid logic with variable binders, and as $d\\to\\infty$, they can separate any pair of non-isomorphic graphs. The authors provide rigorous logical characterizations showing that depth-1 HE-GNNs subsume common subgraph-based GNNs, that $d$ rounds of HE-GNN individuation lower-bound $d$ steps of the Individualization-Refinement paradigm, and that with sufficient nesting they can simulate homomorphism-count-augmented GNNs. An illustrative experiment on ZINC-12k and graph isomorphism testing capabilities concludes the paper.", "questions": "1. How does the recursive individualization in HE-GNNs compare to the Individualization–Refinement framework used in “A Systematic Approach to Random Data Augmentation on Graph”?  https://arxiv.org/abs/2112.04314 \n2. Are there known expressiveness or complexity results for graded hybrid modal logics with variable binders that you can leverage? Grounding HE-GNN’s logical characterization in a well-studied fragment would broaden its impact.", "limitations": "Yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n1. The paper is very well written, with precise definitions and a coherent, logical progression.\n2. Prior approache are surveyed thoroughly and compared clearly.\n3. Adopting graded hybrid modal logic's variable binders to model node individualization is elegant and conceptually well motivated.\n4. The paper delivers an extensive number of expressiveness results—characterizing HE-GNNs by depth $d$ and radius $r$ and situating them relative to competing paradigms.\n\n**Weaknesses**\n1. The modal-logic characterization focuses on graph distinguishability; proving uniform expressiveness (i.e., the ability to compute arbitrary logical queries) would significantly strengthen the contribution.\n2. Theorem 5.10 (relating HE-GNNs to higher-order GNNs) may also be derived via the Geerts & Reutter ICLR 2022 analysis. It remains unclear whether the logic perspective offers insights beyond serving as an alternative proof technique.\n3. While Section 5.4 sketches the relationship, a tighter, perhaps quantitative, comparison to state-of-the-art subgraph-augmented GNNs would be valuable.\n4. The empirical evaluation, though illustrative, remains limited. More diverse benchmarks or ablations (e.g., varying $d$, $r$) would bolster confidence in practical gains.", "was_revised": true, "final_justification": "In its favour, the paper stands out in clarity and formal rigor, and it offers an elegant use of logic to model hierarchical message passing, which is then grounded in a corresponding neural architecture. However, this logical framework yields fewer theoretical (and practical) insights than prior hybrid‐logic approaches, since little of the hybrid logic world seems transferable to the neural setting. Coupled with a rather weak experimental evaluation (the work’s primarily theoretical focus) these factors lead me to recommend a weak accept.", "rebuttal": "We thank the reviewer for their feedback. We have considered all comments and revised our manuscript accordingly. We note that the reviewer values the extensive theoretical comparison of HE-GNN with existing paradigms and the introduction of hybrid modal logic characterizations. Indeed, we intend this work as opening up questions in graph learning to the logic community.\n\n**Uniform characterizations**\n\nAddressing the first raised weakness, we agree with the reviewer that uniform translations are essential in understanding expressive power. Our work does in fact provide uniform translations from GML$(\\downarrow)$ to HE-GNN and from GML$(\\downarrow_W)$ to HES-GNN, showing that the graph learning architectures can compute arbitrary logical queries in their characterizing languages. This is explained below theorems 3.3 and 4.1.\n\nIn the converse direction, we provide a uniform translation only over bounded degree graphs. General uniform translations from the learning architectures to the logics as we defined them do not exist. For example, a GNN can compute whether a node has an odd number of neighbors, which is not expressible in first-order logic. It would be interesting to develop a logic that can (uniformly) represent HE-GNN classifiers by allowing richer forms of arithmetic, following Grohe [1] and Benedikt et al. [2], or to obtain uniform characterizations relative to first-order logic.\n\n[1] Grohe, M. (2024). The descriptive complexity of graph neural networks. TheoretiCS, 3.\n\n[2] Benedikt, M., Lu, C. H., & Tan, T. (2024). Decidability of graph neural networks via logical characterizations. arXiv preprint arXiv:2404.18151.\n\n**Alternative approach for 5.10**\n\nIn the second raised weakness the reviewer remarks that 5.10 might also be derived via the Tensor-Language analysis from Geerts & Reutter. Writing a HE-GNNd$(d)$ update as a TL-expression with $d+1$ variables would yield the same subsumption of separating power by that of $d$-GNN.\n\nWe expect that a proof in this direction is possible, but not trivial. A TL expression describing a single HE-GNNd$(d)$ update must include message-passing sequences on $|G|^d$ distinct graphs, aggregated hierarchically. Conversely, with the GML$(\\downarrow)$ characterization in hand the standard translation to first-order logic directly yields the desired result, benefiting from the longstanding relations between modal and first-order logic. \n\nWe note that logical characterizations have yielded significant insights in graph learning. For example, Abboud et al. [3] proved the universal separating power of GNNs with random initialization using a logical characterization by Barceló et al. [4], Tena Cucala et al. [5] used conjunctive query characterizations of monotonic GNNs to generate automatic explanations for predictions, and Adam-Day et al. [6] obtained various convergence laws for GNNs via term languages.\n\n[3] Abboud et al. *The surprising power of graph neural networks with random node initialization.* IJCAI 2021.\n\n[4] Barceló, P., Kostylev, E. V., Monet, M., Pérez, J., Reutter, J., & Silva, J. P. (2020, April). *The logical expressiveness of graph neural networks.* In 8th International Conference on Learning Representations (ICLR 2020).\n\n[5] Tena Cucala, D. J., Cuenca Grau, B., Kostylev, E. V., & Motik, B. (2022). *Explainable GNN-based models over knowledge graphs.*\n\n[6] Adam-Day, S., Benedikt, M., Ceylan, I., & Finkelshtein, B. (2024). *Almost surely asymptotically constant graph neural networks.* Advances in Neural Information Processing Systems, 37, 124843–124886.\n\n**Empirical validation**\n\nWe have presented HE-GNN primarily as a foundational model, unifying existing architectures in terms of separating power. We recognize that further experimental validation would strengthen the paper and aim to expand the experimental section as follows:\n\n1. We will compare performance on ZINC with other node-marking based subgraph GNNs, addressing weakness 3 raised by the reviewer.\n\n2. We will provide more results with varying $d,r$, to show how HES-GNNs transition from standard message-passing networks to more expressive architectures in terms of runtime and accuracy, in response to weakness 4 raised by the reviewer.    \n\n**Response to questions**\n\n**Relation to Franks et al., 2022**\n\nThe reviewer asks how our work differs from that of Franks et al., who also study GNNs with node encodings derived from individualization. Their approach uses random walks to probabilistically sample a path in an Individualization-Refinement tree, trading full isomorphism equivariance for equivariance in expectation in order to gain tractability. In contrast, our method applies recursive message-passing to aggregate over all leaves of the IR-tree in a fully equivariant manner.\n\nThe approach by Franks et al. is hence less suited for comparison with equivariant classifiers, such as those defined by the WL hierarchy or logics. The authors accordingly investigate function approximation rather than separating power.\n\nWe now make this distinction clear in a new *Related work* section.\n\n**Applicable results in graded hybrid modal logic**\n\nThe reviewer asks if graded hybrid modal logic is a well-studied fragment, so that the characterization of HE-GNN in this logic yields additional results.\n\nThe decidability and complexity of reasoning tasks have been studied in detail for hybrid logics. Although the satisfiability problem for hybrid logics is undecidable, it can be made decidable by either forbidding certain specific syntactic nesting patterns, or through semantic restrictions. See ten Cate & Franceschet [7]. While these results apply to hybrid formulas without graded modalities, we believe the analyses can be extended to the case with graded modalities as well. Therefore, as suggested by the reviewer our logical characterizations may indeed generate additional insight into sources of complexity when it comes to reasoning about GNNs.\n\nWe have added this viewpoint to the introduction as further justification for our approach.\n\n[7] Ten Cate, B., & Franceschet, M. (2005, August). *On the complexity of hybrid logics with binders.* In International Workshop on Computer Science Logic (pp. 339–354). Berlin, Heidelberg: Springer Berlin Heidelberg."}, {"review_id": "U8DHiIBBSv", "reviewer": "Reviewer_ZB9j", "summary": "In this paper, the authors propose a graph neural network (GNN) architecture HE-GNN that goes beyond the expressivity limitations (i.e. 1-WL) of vanilla GNNs. This is then extended by allowing the model to consider only ego-nets of radius r, which improves the computational complexity. In particular, the proposed methods exploit the paradigm of Individualization-Refinement used by many subgraph isomorphism solvers. Most of the theoretical results on the graph separating power of the proposed architecture are obtained via logical characterizations, and the results are compared to some of the existing literature on higher-order GNNs and subgraph GNNs. Finally, some proof-of-concept experimental results are provided.", "questions": "- the authors should argue why a logic-based approach was chosen to describe the expressivity of the proposed architecture. \n- can you discuss the memory and time complexity of the proposed method?\n\n---\nFinally, I wish to remark that if the authors address my concerns (missing related work, more justification for logic-based approach, and more thorough experimental evaluation), I would be willing to increase my score.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths: \n- the theoretical results seem to be correct. Moreover, the use of logic, while it has already been used in some works on GNNs, is an interesting approach, and the graph learning community can benefit from it. \n- The introduction of bounded radius ego-nets is an interesting and effective approach to reduce the model complexity.\n- The comparison with higher-order and subgraph GNNs is well written and provides interesting insights. \n- Code is provided and will be made public. \n\nWeaknesses:\n- The literature review is largely insufficient, as the work is not situated within the quite rich literature of individualization-refinement approaches in graph learning. I name a few here:\n    - [1] provides a very general framework (IRNI) for endowing GNNs with individualization-refinement features, allowing to obtain full graph separating power. This work (and [2]) should be discussed thoroughly, as it is the closest to what the present work proposes.\n    - [2] provides a learning-theoretic analysis of methods that individualize nodes as a way of improving expressivity, and proposes the Tinhofer encoding (based on the individualization-refinement framework) as a compromise between expressivity and generalization. Moreover, the work proposed a bounded-radius ego-net architecture EGO-NN. What are the differences with HES-GNNs?\n    - [Haroon Dupty and Lee] (cited but discussed too briefly) and [3] provide methods to integrate the individualization refinement framework into GNN architectures. \n    - [4] studies the expressive power of GNNs endowed with individualization methods from the prespective of logic, like the present work. The differences in the two approaches should be highlighted. \n    - Several other works propose methods to individualize nodes to improve expressivity. This technique was first introduced in [5], and for other works check related work sections of [1] and [2].\n- The use of logic to prove graph separation results, while interesting, is not properly justified. I suspect that easier proofs with tools that are more accessible to the machine learning and graph learning community could lead to the same results. Therefore, the authors should argue why a logic-based approach is to be preferred in this case. \n- The high memory costs (quadratic) and time complexity (exponential in the depth d) make this architecture, while inteesting from the theory perspective, unlikely to be adopted in practice. Moreover, these time and space complexities should be discussed directly in the methods sections, rather than only in the limitations. \n- The experimental validation is quite unsatisfactory. \n    - The experimental framework is not properly defined neither in the main paper nor in the appendix. For example: does the test set include the same isomorphism classes of the training set in the strongly regular experiment? If so, why is there is a gap between train and test performance? \n    - On the strongly regular dataset, it would be interesting to compare HES-GNNs to other individualization-refinement methods such as the Tinhofer encoding [2] or IRNI [1]. \n    - Only one real-world dataset (ZINC) is used, and the proposed baselines are quite weak. Comparing to the aforementioned methods or to node-marking-based subgraph GNNs would be interesting. \n- The definition of HE-GNNs and HES-GNNs by bullet points is somewhat imprecise. Saying that a HE-GNN of nesting depth $d>0$ is a tuple $(B, C)$ with $B$ a HE-GNN of nesting depth $d-1$ and $C$ a GNN is not really enough. If the model just ignored $B$, we would get a normal GNN. I think run_A should be included in the definition (something like “a HE GNN of nesting depth $d>0$ is a tuple $(B,C)$ […] such that embeddings are updated according to run_A“)\n\n---\n\n- [1] Franks et al. A Systematic Approach to Universal Random Features in Graph Neural Networks. TMLR 2023.\n- [2] Pellizzoni et al. On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks. NeurIPS 2024. \n- [3] Guo et al. Improving the Expressive Power of Graph Neural Network with Tinhofer Algorithm. 2021. (preprint)\n- [4] Abboud et al. The surprising power of graph neural networks with random node initialization. IJCAI 2021.\n- [5] Sato et al. Random features strengthen graph neural networks. SDM 2021.", "was_revised": true, "final_justification": "Overall, I am quite convinced by the rebuttal. The authors agreed to fix some clarity issues, improve the lacking literature review and perform some additional experiments (although they have not yet reported the results). I will raise my score from 3 to 4.", "rebuttal": "We thank the reviewer for their constructive feedback, and have revised our manuscript to address the points raised. We appreciate that the reviewer considers our logical approach and comparison with existing architectures insightful and beneficial to the graph learning community.\n\n**Literature review**\n\nThe reviewer points to several relevant references that warrant a detailed comparison. We have added a *Related work* section, making our contribution in relation to these references precise. Below, we give an overview of the distinctions between our work and [1–4], as requested by the reviewer.\n\nCrucially, these works all cover probabilistic architectures, trading full isomorphism equivariance for equivariance in expectation in order to gain tractability and expressivity. As a result, models presented in [1–4] are less suited for comparison with isomorphism-equivariant classifiers, such as those defined by the WL hierarchy or logics.\n\nThe results in these works hence cover different questions than ours. Franks et al. [1] investigate function approximation, while Pellizzoni et al. [2] analyze bounds on VC-dimension. Guo et al. [3] provide experimental validation but no theoretical results. [1], [2], and [3] all use node individualization, but do so by selecting a single path in the Individualization-Refinement tree using a probabilistic method such as Tinhofer. None of these approaches use a recursive message-passing procedure similar to HE-GNNs, which aggregate over all leaves of an IR-tree in a fully equivariant manner.\n\n**Use of logic**\n\nWe find that logical characterizations provide a formal and explainable perspective on graph learning, which has yielded several results in recent years.\n\nOne example of this is given in reference [4] listed by the reviewer. Here, Abboud et al. prove the universal separating power of GNNs with random node initialization using a logical characterization by Barcelo et al. [6]. Additional examples are given by Tena Cucala et al. [7], who use conjunctive query characterizations of monotonic GNNs to generate automatic explanations, and Adam-Day et al. [8], who obtain convergence laws for GNNs via term languages.\n\nIn addition, logical characterizations can allow for intuitive proofs. For example, in Theorem 5.11 we distinguish HES-GNN from $k$-GNN by showing that the former can recognize colorful distance-2 cliques. Reasoning in terms of nested message-passing aggregations would be tedious here. Instead, we give a single intuitive GML$(\\downarrow_W)$ formula, of which one can directly verify that it recognizes such a clique.\n\nWe take this comment seriously, as it may be shared by more researchers in the graph learning community, and have added further justification for our logical approach in the introduction.\n\n- [6] Barceló, P., Kostylev, E. V., Monet, M., Pérez, J., Reutter, J., & Silva, J. P. (2020, April). *The logical expressiveness of graph neural networks.* In 8th International Conference on Learning Representations (ICLR 2020).\n- [7] Tena Cucala, D. J., Cuenca Grau, B., Kostylev, E. V., & Motik, B. (2022). *Explainable GNN-based models over knowledge graphs.*\n- [8] Adam-Day, S., Benedikt, M., Ceylan, I., & Finkelshtein, B. (2024). *Almost surely asymptotically constant graph neural networks.* Advances in Neural Information Processing Systems, 37, 124843–124886.\n\n**Experimental validation**\n\nIn the SRG experiment, train and test sets indeed include the same isomorphism classes. The reviewer has identified an issue due to an unexpected interaction with PyTorch `.eval()`. The issue has been resolved. Train and test performance now match, and the manuscript explains the experimental setup more clearly. Our conclusion from this experiment is not affected.\n\nWe have focused on formalizing and presenting the capacity of HE-GNN to express existing architectures, and recognize that further experimental validation would strengthen the paper. We will expand the experimental section as follows:\n\n1. We will compare performance with more existing architectures. We note that [1] does not provide code for comparison, but comparison with Tinhofer is feasible. We will do our best to compare performance on ZINC with more node-marking based subgraph GNNs.\n\n2. We will provide more results with varying $d, r$, to show how HE-GNNs transition from standard message-passing networks to more expressive architectures in terms of both accuracy and running time.    \n\n**Final remarks**\n\nWe have made the definition of HE-GNN more explicit. Further, we have made the complexity analysis of HE-GNN more precise, and moved it from the comparison with higher-order GNN to the section that defines the model. We note that the crucial distinction with higher-order GNNs in terms of complexity is made in section 5.3. HE-GNNs with depth $d$ store at most $|G|^2$ features, but they perform $O(|G|^d)$ rounds of message-passing."}, {"review_id": "41p6MnWdgh", "reviewer": "Reviewer_Ru4p", "summary": "This paper introduces Hierarchical Ego Graph Neural Networks (HE-GNNs), a novel class of GNNs that enhance expressive power through a mechanism inspired by the Individualization-Refinement (IR) paradigm from graph isomorphism testing. HE-GNNs iteratively individualize nodes and apply message-passing, resulting in a hierarchy of models where increasing the nesting depth increases expressive power. The authors provide a tight logical characterization of HE-GNNs using graded hybrid logic (GML($\\downarrow$)) and its subgraph-restricted variant (GML($\\downarrow$,W)). They show that HE-GNNs match or surpass existing expressive models such as higher-order GNNs, subgraph-GNNs, and homomorphism-based GNNs. The theoretical results are backed by empirical experiments showing HE-GNNs can distinguish graphs that standard GNNs fail on, including strongly regular graphs and graphs in datasets like ZINC.", "questions": "1. Have you considered evaluating HE-GNNs on synthetic isomorphism benchmarks like SR25, CSL, or EXP to better demonstrate expressiveness in challenging graph distinction tasks?\n2. Can you provide empirical evidence on how performance and computational cost scale with increased nesting depth $d$ and radius $r$?\n3. Theorem 4.1: Could you elaborate on how the quantifier radius in GML($\\downarrow$, W) corresponds exactly to the radius-$r$ subgraphs in HES-GNNs? Are there cases where the logical quantification covers more nodes than the subgraph accessible by radius-$r$ message passing?\n4. Theorem 4.3: Is the strict increase in expressiveness dependent on the existence of graphs where node distinctions require radius > $r$ neighborhoods? Could you provide such a minimal pair of graphs or clarify how often such cases occur in real-world datasets?\n5. While you show that 2-WL and Nested GNNs are subsumed by HES-GNNs under certain conditions, could you clarify whether this inclusion is strict in all cases or only under specific configurations of depth and radius?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. HE-GNNs is a compelling and novel approach that generalizes and unifies various expressive GNN architectures under the lens of logic. The integration of hybrid logic to describe the expressive capabilities of GNNs is particularly innovative.\n2. The paper is rigorous in its formalism. The equivalence theorems connecting HE-GNNs with graded hybrid logic (Theorems 3.3, 4.1) are carefully proved and grounded in prior foundational results (e.g., Barcelo et al., Morris et al.). The use of logical tools for characterization, such as nesting-depth correspondence, is both insightful and technically strong.\n3. This work is foundational, it provides a formal framework to measure and compare the expressive power of advanced GNN architectures. The logical perspective opens new research directions for designing more powerful and interpretable models. Also, HE-GNNs offer a scalable alternative to higher-order GNNs with bounded memory overhead.\n\n**Weaknesses**\n1. The experimental validation is relatively limited in breadth. While the ZINC and SRG evaluations support the theory, inclusion of synthetic benchmarks like CSL, EXP, and SR25 could offer a clearer picture of the model's capabilities in distinguishing structurally similar yet non-isomorphic graphs.\n2. The empirical evaluation lacks diversity in real-world benchmarks. The model is only evaluated on a single real-world dataset (ZINC), with no experiments on large-scale and widely used benchmarks such as the OGB datasets. This limits the ability to assess the practical effectiveness, scalability, and generalizability of HE-GNNs in more complex and varied real-world scenarios.\n3. Although HE-GNNs are presented as more efficient than higher-order GNNs, no detailed comparison of runtime, memory, or practical training complexity is provided.\n4. The impact of depth $d$ and radius $r$ in HES-GNNs is not fully analyzed in experiments (missing ablation study). A study on how performance and runtime vary with $d$ and $r$ would strengthen the claims.", "was_revised": true, "final_justification": "I appreciate the authors' thorough and well-reasoned responses. I am convinced by most of the clarifications provided in the rebuttal. Additionally, the promised ablation studies, runtime analysis, and the inclusion of synthetic isomorphism benchmarks are positive steps toward strengthening the empirical side of the paper. Thus, I will raise my score accordingly.", "rebuttal": "We thank the reviewer for their constructive feedback, and have revised our manuscript to address the points raised. We appreciate that the reviewer considers the paper to be foundational, allowing for comparison of existing GNN architectures and opening up new research directions, since this is precisely what we aim to achieve with this work.\n\n**Experimental validation**\n\nWe have focused on formalizing and presenting the capacity of HE-GNN to express existing architectures, and recognize that further experimental validation would strengthen the paper. We vouch to:\n\n- Attempt comparison on an additional synthetic dataset like CSL, addressing question 1.\n\n- Do our best to compare performance on ZINC with other modern node-marking based subgraph GNNs.\n\n- Provide an ablation study with results for varying $d,r$, to show how HES-GNNs transition from standard message-passing networks to more expressive architectures in terms of both accuracy and running time, addressing question 2.\n\nIn addition, we have made the complexity analysis and comparison with higher-order GNNs more precise.\n\n**Further responses to questions**\n\n**Response to question 3**\n\nIn question 3 the reviewer asks how the quantifier radius $r$ in GML$(\\downarrow_W)$ corresponds to the subgraph radius in HE-GNN. We can confirm that both notions refer to the same subgraph: the graph induced by all nodes reachable in $r$ steps. However, if a specific HE-GNN has fewer than $r$ message-passing iterations, not all nodes in this subgraph are included in the computation. This corresponds to evaluating a GML$(\\downarrow_W)$ with bounded $\\diamond$ depth.\n\n**Response to question 4**\n\nIn question 4, the reviewer asks whether we can provide a pair of graphs that require a minimal neighborhood radius to be separated by HES-GNN($d$,$r$), making the strictness of theorem 4.3 concrete.\n\nSuch a pair of graphs is provided in the proof of theorem 5.11. For each $d$, there exists a GML$(\\downarrow^d_{W^3})$ formula that can recognize a ‘colorful distance 2 clique’ of size $d+2$. No such formula exists with smaller radius, since a radius $2$ subgraph cannot contain this structure. Further, no such formula exists with smaller depth, as established by theorem 5.10.\n\n**Response to question 5**\n\nIn question 5 the reviewer asks if HES-GNN strictly subsumes 2-WL either in general, or under specific $d$ and $r$.\n\n Theorem 5.11 shows that HES-GNN with depth $d$ can separate graphs that $d$-WL cannot separate. This result holds for any $r \\geq 3$, and we are not aware of a construction with smaller subgraph radius. We have not shown however that HES-GNN with any $d$ or $r$ subsumes the separating power of 2-WL. \n\nNote that we use WL for what some authors name Folklore-WL, as opposed to Oblivious-WL (see e.g. Morris et al. [1]). If the reviewer refers to 2-Oblivious-WL, then theorem 5.11 indeed show that HES-GNN($d$,$r$) strictly subsumes this test for $d \\geq 1$, $r \\geq 3$.\n\n[1] Morris, C., Lipman, Y., Maron, H., Rieck, B., Kriege, N. M., Grohe, M. & Borgwardt, K. (2023). Weisfeiler and leman go machine learning: The story so far. Journal of Machine Learning Research, 24(333), 1-59."}]

Author rebuttal:

Meta-review: The paper examines the expressive power of Graph Neural Networks (GNNs) utilizing node individualization. It introduces a new model, analyzes its logical expressive power, and establishes interesting connections to previous expressive models, such as subgraph GNNs. Several issues were raised during the discussion, all of which were resolved satisfactorily. In the reviewer–area chair discussion, a consensus was reached that the paper is a valuable addition to the conference. I am pleased to recommend its acceptance and encourage the authors to include all the materials requested by the reviewers.
Decision: Accept (poster)