Deep Homomorphism Networks
Authors: Takanori Maehara
Hoang NT
Venue: NeurIPS 2024 poster (2024)
Keywords: graph homomorphism
subgraph counting
graph neural network expressivity
Primary area: graph_neural_networks
TL;DR: We study parameterized multi-layers graph homomorphism networks where homomorphism mappings acted as convolutional kernels. The proposed multi-layers graph homomorphism can be understood by using rooted graph product homormorphism.

Abstract: Many real-world graphs are large and have some characteristic subgraph patterns, such as triangles in social networks, cliques in web graphs, and cycles in molecular networks.
Detecting such subgraph patterns is important in many applications; therefore, establishing graph neural networks (GNNs) that can detect such patterns and run fast on large graphs is demanding.
In this study, we propose a new GNN layer, named \emph{graph homomorphism layer}.
It enumerates local subgraph patterns that match the predefined set of patterns $\mathcal{P}^\bullet$, applies non-linear transformations to node features, and aggregates them along with the patterns. 
By stacking these layers, we obtain a deep GNN model called \emph{deep homomorphism network (DHN)}.
The expressive power of the DHN is completely characterised by the set of patterns generated from $\mathcal{P}^\bullet$ by graph-theoretic operations;
hence, it serves as a useful theoretical tool to analyse the expressive power of many GNN models.
Furthermore, the model runs in the same time complexity as the graph homomorphisms, which is fast in many real-word graphs.
Thus, it serves as a practical and lightweight model that solves difficult problems using domain knowledge.

Deep Homomorphism Networks
Takanori Maehara" Roku, Inc. Cambridge, UK tmaehara@roku..co com
Hoang NT University of Tokyo Tokyo, Japan
hoangnt&g. ecc. u-tokyo. ac jp
Abstract
Many real-world graphs are large and have some characteristic subgraph patterns, such as triangles in social networks, cliques in web graphs. and cycles in molecular networks. Detecting such subgraph patterns is important in many applications; therefore, establishing graph neural networks (GNNs) that can detect such patterns and run fast on large graphs is demanding. In this study, we propose a new GNN layer, named graph homomorphism layer. It enumerates local subgraph patterns that match the predefined set of patterns P applies non-linear transformations to node features, and aggregates them along with the patterns. By stacking these layers, we obtain deep GNN model called deep homomorphism network (DINN. The expressive power the DHN is completely characterised by the set of patterns generated from P by graph-theorees theoretical tool to analyse the expressive power of many GNN models. Furthermore, the model runs in the same time complexity the graph homomorphisms, which is fast in many real-word graphs. Thus, it serves as a practical and lightweight model that solves difficult problems using domain knowledge.
operations; hence, it serves useful
Introduction
1.1 Background
Graph neural network (GNN) is type of neural network that takes graph as input. It has been applied to many problems in various domains, such influence prediction in social networks [60], page ranking in web graphs (5), and chemical prediction biological networks See textbooks [46]
32
71
for the basics of GNN.
The expressive power of GNNs is the central research topic in GNN 63
recent interest in this topic is the detectability of subgraph patterns. Many graphs that appear in practice have typical subgraph patterns. For example, social networks have many triangles, which indicates the clustering structure of the society. Web graphs have many cliques that represent clusters of websites, such as link farms. Molecular networks have benzene structures. Since detecting these subgraph patterns is common strategy in network science [52] and graph data mining [155, we expect that GNNs applied these fields equip expressive power to detect such patterns. Furthermore, since the graphs in these applications are typically large, we also expect that the GNNs applied in these fields run fast.
Unfortunately, most of the existing GNN models do meet these expectations. The commonly used GNNs, called message-passing GNNs (MPGNNs), do not meet the expectation of expressive power, they can only detect tree-shaped patterns 72 19]. More complex GNNs can detect subgraph patterns, but typically do not meet either expectation: Higher-order GNNs assign values to k-tuples of nodes instead of nodes [53 50 36). They have the same expressive power the k-dimensional
Authors are listed in alphabetical order.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Weisfeiler- (k- WL- tes which detects subgraphs of treewidth at most & [23;; however, their complexity typically Q(n which is not applicable to large graphs. Subgraph GNNs take a small subgraph for each node and apply GNN to compute an embedding [77]. Its expressive power depends on the choice of the subgraph selection policy and the base GNN, and the standard choice of the policy and the base GNN, it is strictly more expressive than the 1-WL test but less expressive than the 2-WL or 3-WL tests 77 225, which is often insufficient to capture the patterns of interest.
One promising direction is explicit pattern detection, which explicitly scans the patterns in the graph and uses that information. This approach has been studied and applied in practice for a long time before the GNN era [5] 52, 69 26], and recent studies combine them with GNN [4 [56 78 49
[57]. This approach requires domain knowledge (or "subgraph feature engineering") (" of what patterns will be important, but often provides a more effective and efficient solution.
Amongst multiple notions of pattern enumeration, here focus graph homomorphisms, which is the sajacenccy-reservvnng definition). We focus on the following two theoretical GNN studies based on graph homomorphisms. The first is by NT and Machara [56], who extended the homomorphism number to graphs with features and proposed using them as features of downstream models such as support vector machines. The limitation of this approach is that it is inefficient in achieving a higher expressive power - Their approach specifies a set of patterns and computes the generalised homomorphism number for each P E P. This detects all P E P (finite number of patterns) using S((PP)) time. On the other hand, MPGNNs such as GIN detect all T E T, where T is the set of trees (infinite set of patterns) without incurring a time complexity of (2(TT) The second is by Barceló et al. (4) who proposed to add the precomputed rooted homomorphism numbers from the specified patterns pp* as node features of the graph and to apply MPGNN. The important finding is that such simple approach boosts that the model detects all F F where where F is a set of graphs obtained by attaching a pattern P P to nodes of tree (called p*-trees) while keeping the time complexity of O((P*)) instead of O(FF"). This approach cannot capture the features of the patterns, which are important in many GNN applications, and the patterns it captures are limited.
mappings from a pattern to the target graph (see Section (22 for the
Our goal is to establish a connection with the GNN architecture and homomorphisms by extending this line of studies. We observe that, according to the proof of [4], the method of [56) is inefficient
in achieving a higher expressive power because it is not "deep" (see Remark 5.4). Therefore, our
strategy to achieve more expressive GNNs is to deeply stack homomorphism- based layers.
1.2 Our Contribution
In this study, we propose generalised rooted graph homomorphism number, which applies a non-linear transform to node features and then aggregates them along with graph homomorphisms (Section 33). We then propose graph homomorphism layer that computes the generalised rooted homomorphism numbers with learnable non-linear transforms from set of patterns P specified as a hyperparameter. We refer to a GNN that stacks this layer deep homomorphism network (DHN or P*HHHN to clarify the patterns). See Figure T for illustration and Section for the details of our model.
By construction, our layer is trained and evaluated in the same time complexity as the generalised rooted homomorphism numbers. Computing the homomorphism number is W[I]-hard in general [17] however, in many practical cases, such as bounded degree graphs and bounded degeneracy graphs, we can obtain faster algorithms by using the technique in graph homomorphisms (Section 4.2
The expressive power of the model is analysed using a methodology similar to that in Let P be a set of graphs obtained by iteratively attaching p e P to the singleton (e.g., the set of trees is obtained from an edge by this construction). Then, we can show that the expressive power p DDDN is characterised by the J'-hommmopphism distinguishability (Theorem 5.2). This characterisation is useful for establishing the expressive power hierarchy of the GNN models. In particular, we can discuss its relationship with k-GNN and subgraph GNNs using the underlying homomorphism patterns. Another important consequence of this theorem is that it reveals the advantage of stacking multiple GNN layers. Simply put, adding one layer corresponds to adding base patterns to each node in the current set of patterns. Hence, GNN can detect exponentially many patterns and linearly deeper patterns with respect to the number of GNN layers (Remark [5.4 in Section 5.I..
'There are few definitions of WL tests with inconsistent dimension counts. We follow which is also called the folklore SeaffelerrLehmaae test.
13 's definition,
2

---

DHN-(G, G)
hom Cj. G)
hom C2 G)
output
input graphs
layer 1
receptive fild
layer
(entogsiaalle
Figure I: Example Deep Homomorphism Network (DHN) built from two P ph-hommmorphism layers: C3 and Cg. By stacking different homomorphism patterns. DHN can detect new patterns without explicit specifications. This figure demonstrates that the "spoon" pattern can be detected by stacking C3 and C2 homomorphism layers.
Essentially, P'-DHN is "deep" version of NT and Machara [56] 's method. Barceló et al. 4''s method is DHN that uses the pp*hhomomorphism layer for the first layer and the MPGNN layer for the subsequent layers. This generalisation elucidates the relationship between the GNN architecture and the corresponding homomorphisms, thereby facilitating better understanding of the expressive power hierarchy among different GNN architectures (Section 5.3).
The DHN model takes advantage of pattern enumeration and deep learning. Hence, we expect the model solve difficult graph problems that require the capture of subgraph patterns reason- able computational costs. We conducted experiments and observed that the DHN solved difficult benchmark problems (CSL, EXP, and SR25) with fewer parameters than the existing models. For real-world datasets, the proposed model showed promising results, but was still not competitive to the Mate-of-theeard models that involve lot of engineering (see Section 6 for discussion).
Preliminaries
2.1 Graphs
is pair of nodes V(G) and edges E(G). We denote by c (u, v) an edge between u and v e and N N(u) {u: (u, v) E E(G)) the neighbours of An isomorphism from G, to G2 is a bijection =: ((G.) - ((22) such that (u,, E E(G1) if and only if (((u)),((v))
A graph G = (V))),
E(G)) (V),),
E(G2). Two graphs Gi and G2 are isomorphic if there exists isomorphism.
We fix a compact set X' s dd for the feature space. A graph with features is pair (G, of graph G and collection [a. E :u:ue V(G)] s (V) of node features. Two graphs with features, (1) and (G2, x22, are isomorphic if there is an isomorphism æ from G₁ G2 such that vi,,, (2,)(uu)) for all E V(Gi).
In this study, we mainly consider the node classification as it is building block of all other GNN applications. We employ rooted graph formulation [47 [56]. A rooted graph G" is a graph G = (G),,,()) with distinguished node r V(G). We denote by G* if there is no need to specify the name of the root node. Two rooted graphs GT and G are isomorphic if there is an isomorphism from G2 G2 such that 72 = T (r1). The isomorphism of rooted graphs with features is defined similarly. A function f that takes rooted graph with features (G, and produces some quantity said be equivariant if f((G), 21)) f((G), x2)) if (G1, 21) and (G x22 are isomorphic. This study only considers equivariant functions because it is a natural and desirable property for
the task (otherwise, the output depends on a synthetic ordering of nodes). Note that if we drop the
equivariance, it is easy to construct arbitrary expressive models (5 64 43 [8]
Remark 2.1 (Advantage of Rooted Graph Formulation). Many existing studies formulate node classification function as function that takes graph G as input and produces R xV) matrix as an output. Therefore, mathematically, its codomain is the disjoint union UGeg TR (G) where G is
We consider simple undirected graphs, which is the standard setting in the theory of graph homomorphisms. The proposed method can be easily extended to nonsimple directed graphs.

---

the set of all graphs. Existing studies mitigated such a complex codomain by assuming that all G share the same node set, ((G) = {i..... n), but this creates a limitation on the number of nodes. The rooted graph formulation has no such issue as the domain is the set of rooted graphs and the codomain is Rd Note that the statement for rooted graphs is easily converted to non-rooted graphs.
2.2 Graph Homomorphism
A graph homomorphism from graph F to graph G is mapping :: V(F) - V(G) such that (1,j) E (() implies (T()), (()) E(G); we refer F as paltern graph and G as host graph. As each homomorphism defines subgraph of G as homomorphism image π (FF) S G, we can recognise that a homomorphism represents a F F-patteem in G.
We denote by Hom(F, G) the set of graph homomorphisms from F. to G and hom G) by its cardinality, called graph homomorphism number. If we know hom F, G) for multiple F, we can obtain lot of information on the structure of G. For example. hom(C, G1) = hom C, G2) for all cycles C' means that G₁ and G2 are cospectral and hom (, G1) hom F, Gi2) for all graphs F means that 1₁ and G2 are isomorphic [44), See Hell and Nesetril 33 for the basics of graph homomorphisms.
For rooted graphs F" and G", a rooted graph homomorphism is a homomorphism from F to G that maps r s. We denote by Hom[F", G²)) the set of rooted homomorphisms from F to G*
2.3
Weisfeiler-Lehmaan Test
The (one-dimensional) Weisfeiler-Lehman test (WL test or 1-WL test) is a procedure to identify whether given two graphs (with features) are non-isomorphic or potentially isomorphic [30.. The WL-test calculates the "colour Cu, of nodes u using the following recursive procedure:
c (k+1)= (c(k), ( Hclt)
: UuE N(w))).
(1)
where [ denotes the multiset. Here, each colour is nested tuple of vectors and multisets; practical implementation applies a hash function to them, but they are equivalent in theory. Let (G) (k) uu E V(G) B
be the multiset of colours in the k-th step. If c(x) (G1) * (G2) for some k, then G1 and G2 are not isomorphic. Dvořák [23] proved that two graphs G1 and G2 are indistinguishable by the WL-test and only if hom(T, G1) = hom G2) for all trees T..
2.4 Graph Neural Networks
Graph neural network (GNN) is neural network that takes graph as input. The most commonly used GNN is a message-passineg GNN (MPGNN), which computes the node values by
(0) = (Iu),
1 (k+1) = -p (H++1 1) (R), (1)) (fl ( : UUE UE N(w
(2)
where (k) learnable function and (k) is a (lcarnable) multi-set function, i.c., a permutation- invariant function for the arguments, for each k. It is easy to see that the MPGNN defines equivariant functions. typical implementation of MPGNN graph isomorphism network (GIN) (72). which
uses the summation for (()))
Due to the similarity between the WL test TT) and the MPGNN (2. it can be proved that the expressive power of the MPGNN is identical to the WL test [72]. As the WLLinnistinguishaaillty is equivalent to the commoorphismmindiitinnge indistinguishability from all trees, as mentioned above, we can conclude that
MPGNN can only detect thee-shaped patterns.
3 Generalised Homomorphism Numbers for Rooted Graphs with Features
A pattern graph with transformations is pair (F+ ()) of a rooted graph F and a collection of continuous functions μ {1pp : p V(F*)) defined on the nodes of F*, where each Mp maps their
Paul-Pena and Seshadhri [88 called this vertex homomorphism.

---

(G', .z)) from a pattern graph with transformations (F*, (.) to a rooted graph with features (G*, . then defined by hom( .,),, (G", (G',,),, ,r)) = Σ
inputs to R The generalised rooted homomorphism number hom [F* p)), (G)(GG:
II xeHom ,G') PEV(F*)
Mp(Za(n))
where the product in the right-hand side is the element-wise product. Note that NT and Maehara [56]'s ' generalised homomorphism is our special case, which uses the same transformation to all nodes.
A generalised homomorphism number maps a graph with features to a real vector (not necessarily number). By definition, two isomorphic graphs with features have the same generalised homomor- phism numbers for any pattern graph with transformations. Here, the converse also holds.
Theorem 3.1. Let (G1, x1) and (G2, 322) be rootdd graphs with with features. (G1, &1) and (G x22 are isomorphic if and only if hom((F [**, 1d), (G),,1)) hhmm(F* .p), (G2, z2)) for any pattern graphs with transformations (F*, ,1).
Proof Sketch. We use the Lovasz theorem that any finite relational structure is determined from the number of homomorphisms 44 First, we recognise graphs with features as a relational structure consists of the adjacency relation and feature value relation. Then, we show that the number of homomorphisms as the relational structure (i.e., the number of mappings that preserve the edges and feature values) is computed using our generalised homomorphism by suitably choosing js.
Let JF be a set of pattern graphs with transformations. We say that two rooted graphs with fea- tures, (G1. 211 and (G2, T2). F -hhmooorrphhim indistinguishable if hom((F 1)), (G1, x1)) hom((F* p)). (G5, for all (F*, (4) F*; Theorem 3.1 states that F sr-hhommmorhhism indistin- guishability coincides with the isomorphism if F* is the set of all pattern graphs with transformations. forms an equivalence relation.
In general, homomorphism indistinguishabite
Remark 3.2. In graph homomorphism literature, weighted homomorphism number 45 is studied more frequently. It is essentially generalised homomorphism number with linear transformations, and it cannot distinguish some non-isomorphic graphs [12 (7). However, as shown in the above, our generalised homomorphism mitigates this issue by introducing the non-linearity of μ.
4 Deep Homomorphism Networks
4.1 Definition
Let P be a set of rooted graphs. A graph homomorphism layer with respect to P is GNN layer defined using the generalised homomorphism number as follows:
GHT.p- ((G", x); fur- : P* E pP))) p (hom((P" prr)), (G", x)) P* E P*),
(4)
where (G", 2)) is the input rooted graph with features, and p and pPp , for all p* P and e ((P*) are neural networks. We often omit neural network parameters and write it as GHLp. [(G x))) The input dimensionality of p the sum of the output dimensionalities of pp*... and the input dimensionality of ,u is the dimensionality of the input h. The layer defines an equivariant function since the graph homomorphism numbers are equivariant functions.
Deep homomorphism network (DHN) is a neural network obtained by "deeply" stacking the graph homomorphism layers follows:
(0) x, (k+1) = GHL ((G))
(5)
We denote by (P(1). p(2). DHHN if we want to emphasize the pattern sets, and denote
"'*DHN for (P*, pp,.... " -DHN, By definition, a DHN is an equivariant function. The number of parameters in DHN proportional the number of nodes in the pattern graphs.
Example 4.1 (DHN generalises MPGNN). Let P = (-
of be the patterns consisting of
single-node and single-edge graphs. Here, we see that the -HH a MPGNN.
We first consider the single-node graph . There is the unique homomorphism from to GM given by
u; hence,
hom((... ( (1), (G",z)) = (xw))
(6)
5

---

We then consider the single-edge graph o. As the set of homomorphisms from - to G corresponds to the set of edges incident to u. we have
hom((- o, -o, (//l-=,,,,//--,,00) (G" (x))
Σ
Me-o, (Tu)
vEN(u)
By setting (x) = I, Me (x) = 1, and (o_o,o()) = x for some Ho. we obtain the MPGNN:
G(I,)-(GG",)))) P Ius
(8)
VE.V
DHN generalises several existing models. We review such results in Sections 5.2
4.2 Computational Complexity
Evaluating graph homomorphism layer with respect to P on (G, x)) takes the same time complexity evaluating hom((P", (p) (G), for all pa E " and V(G); therefore, its computational complexity is at least that of hom G) for some P E p We cannot expect a linear-time algorithm evaluate this quantity without any assumption because computing hom (P, G) a W[1]- hard problem parameterised by [V[)] [29]. However, there are several cases that admit efficient algorithms for computing hom P, G). We see that these results can be generalised to our generalised homomorphism numbers as follows.
Case 1: P has bounded treewidth Treewidth is parameter that represents how far the graph is from being a tree; see [21] about treewidth. If has a bounded treewidth, we can compute hom( P. G) in O(n (n()((1++1 time using the dynamic programming algorithm 220]. The algorithm is easily extended to generalised rooted graph homomorphism numbers; Section A.T Hence, can evaluate the graph homomorphism number in polynomial time in this situation.
Case 2: G has bounded degree In some examples, such as molecular networks, the host graph G has a small maximum degree. In this case, we can enumerate Hom P* G*) in constant time by brute-force enumeration. Therefore, we can evaluate the graph homomorphism layer in linear time.
Case G has a bounded degeneracy and P has bounded DAG-treewidth A graph G has degeneracy at most k if there is an ordering of nodes U,,..., Un such that Ki u, E N(u)), > 2B1 & le for all i 1,..., n practically important to have algorithms that run fast on graphs of bounded degeneracy. Bressan [10] introduced DAG-treewidth, and proposed an algorithm for computing the homomorphisms number in (ndat(w(P)) time using the dynamic programming algorithm. An important special case is that P has no induced cycles of length greater than five. In this case, the DAG treewidth is one (58) (the converse also true); hence, we can evaluate the homomorphism numbers in linear time, To clarify the procedure, we put a linear-time algorithm for the quadrangle Ca; see Section A.2 in Appendix.
Many real-world graphs have small degeneracy 77. Hence, is
5 Theoretical Analysis of DDD Model
5.1 Expressive Power of P*D Model
In Example 4.1, we observed that a DHN with simple patterns (o, - o} contains a MPGNN. Here, we focus to the phenomenon that, although it aggregates local information along with such simple patterns, it has a great expressive power specified as the 1-WL test [72), which distinguishes all T aanoomopphism-diiiiggushhaaae
graphs, where T is the set of all trees 23 The goal of this section
is to generalise this relation to arbitrary patterns.
Let F and pr be rooted graphs. The rooted product of F and pr p V(F*) is the rooted graph
obtained by attaching r at p, i.e., F* *, Pr := F. J pr [[, (28): see Figure 2 for an example. Let F and p be sets of rooted graphs. We denote by F p' {F* P E V (FF)) the set of all rooted products. We denote by p Ur-a, ...) l the set of all graphs obtained by the iterated rooted products, where (P* =0 (o) and (Po)*l po.... p (1 times). We can easily verify the following example.

---

Figure 2: Rooted product of two graphs, the triangle and the edge, at p.
Example 5.1. {o of is the set of all rooted trees T*
Now Example 4. and Example 5.1 lead to the conjecture that the expressive power of P*-DHN is characterised by the iterated rooted product pa of the pattem graph. We prove this follows, which the main theorem in this paper.
Theorem 5.2. Let p be set of rooted graphs. For any rooted graphs with features (G1 #1)
and (G2, T2), the following are equivalent.
1. For any -*- lt, have h(G1, 1uGG, 12).
2. x1) and (G x22) are
( P"-homomorphism indistinguishable.
The key lemma to prove this theorem is the following lemma, which decomposes the homomorphism from rooted product into the homomorphisms from the factors.
Lemma 5.3 (Chain Rule). Let F be a rooted graph obtained by taking the rooted product of P and Fr at node p for each p V(P)). Then, for any there exists Pp such that
hom((F* ..,, x))
Σ
IT
hom((FF; Pp), (G*(p) ,2))
TEHom(P* ( PEV
for any rooted graph with features (G'.z).
Proof Sketch of Theorem 5.2 Instead of proving the equivalence between and 2, we introduce a variant of WL-test, named -WL tesí, and introduce the third statement: (G,, (11 and (G2,4z) x2) are -L indistinguishable, and prove the equivalence of 1, 2, and Here, = 2 is clear from the definition of the PL test, which is similar to that of [72].
2 is straightforward by seeing that generalised homomorphism from any F E P is expressed by a DHN. To prove 2 > 3, we prove that the colour assigned by -L test is uniquely identified by evaluating suitably-chosen pattern graphs F* p with transformations. This part similar a basic results from multi- mylte--ymmetric polynomials.
but we use the chain rule above and
Remark 5,4. Establishing deeper GNN models is a central challenge in GNN community
Although deeper models do not necessarily perform well in practice (37 62 in theory, Theorem 5.2 and its proof clearly show the advantage of deeper GNNs in terms of the number of pattern graphs From the proof of Theorem 5.2 we that l-layer DHN models count homomorphisms from 20()) different patterns. In this sense, could say that "the expressive power of GNN grows exponentially in the number of layers."
Relationship with Existing Models
In this section, we review the relationship between the proposed DHN and some existing models.
Example 5.5 (DHN generalises NT and Machara (56)). Our first-motivated paper, NT and Machara (56), proposed to compute (their version of) generalised homomorphism number and use it feature of downstream models for graph classification. By definition, our DHN can be seen as a multi-layer version of their approach.
Example 5.6 (DHN generalises Barceló et al. [4] Our second motivated paper, Barceló et al. [4] proposed to append homomorphism numbers from arbitrary pattern p as node features. This can be seen as a DHN that uses an arbitrary pattern p in the first layer and the MPGNN pattern ( o}
the subsequent layers, i.e., it is the (P* (.. o), ( ...... -DHN. They showed that their model can detect graphs called pa pptterrss which is obtained by attaching Pd to nodes of tree. This follows from our theorem, as the t -pttttreess are exactly the graphs obtained by the rooted
product to tree and P
7

---

Example 5.7 (DHN generalises Paolino et al. (57]) Recently, Paolino et al. [57] proposed a GNN that aggregates information over cycles. Their model DHN that uses the set of cycles C {Ci...., C of lengths at most I as pattern set, i.e., it is the C; CDDHHN. They showed that their model can detect cactus graphs with maximum eycle length of l. This follows from our theorem since C7 are the set of such cactus graphs.
Example 5.8 (DHN generalises the most expressive subgraph GNNs). For each layer. a subgraph GNN takes the 1-hop neighbours and applies GNN to compute the value of the root node [77]. The most expressive GNN in this class uses the universal GNN on the subgraph. If the underlying graphs have a bounded degree, such a GNN an instance of DHN - Let 93, the set of all rooted graphs of degree at most d and radius at most I. Then, the ر homomorphisms identify GJ [4.. Therefore, - has the same expressive power the subgraph GNN with universal GNN if the underlying graphs have degree at most d.
5.3 Applications: Expressive Power Hierarchy
Theorem 5.2 is a powerful tool for comparing the expressive power of different GNN models. Let A and B be two GNN models. We say that A is more expressive than B (denoted by A 2 B) h hB((G5,
x2)) for all hB B, and A is strictly more expressive than B (denoted by A 2 B) if the A B but B + A. To prove A & B, we typically show that A can implement B, and find a pair of instances (Gi, x1), (G2, 22), separating these classes. However, finding such a pair often requires nontrivial work.
( x1)) = ha((G), x2)) for all hA E A implies hn((GT, x1))
Theorem 5.2 reduces the expressive power of -DHN model to pommmommoophism indistinguishabil- ity, and allows us to use lots existing work established in graph theory literature [44] 19 61 [5 31). For example, after some preparation (Section D.6), unified way. See also Figure D.6 in Appendix showing hierarchy of some models.
easily prove the following hierarchy in
Corollary 5.9. Let Ct be set of cycles of size most k (where identify the cycles of length one and two as a singleton and an edge, respectively), KG be the set of cliques of size at most k. and St be the set of connected graphs of size most k. Then, the following holds.
CD-DHN model : -DHN model, KH-DHN model $ -DHN model, and S model I S -DHN model for all l: 3 2.
Ct- CN-DHN model = SDH model for all k 3 4, and SHDDHN model is incomparable with -DHN model for all k 3.
-HHDHN model % S S model for all k 3 4, and S model is incomparable with - model for k >
* CH-DHN model and KH-DHN model are incomparable for h > 4.
We also prove the relations of expressive powers of existing architectures using our framework as follows. See Section B in the Appendix for a detailed discussion of the existing models.
S pa and P contains a graph with a cycle, then the P*-DHN model is strictly more expressive than the MPGNN model.
Corollary 5.10.
Corollary 5.11. the maximum treewidth of p* p is k, then the PDHDIN model is less expressive than the &-WL equivalent models such as (k 1NNGNN and (k + 1)-IGN models.
Corollary 5.12. If the maximum chordless cycle length of p P is finite, then PDHDNN model is incomparable with 2-WL equivalent models such as 3-GNN and 3-IGN models.
Corollary 5.13. The subgraph GNN model using the k-hop egograph selection policy and universal GNN as base encoder is strictly more expressive than St SDD model, and is incomparable with WL models such as 3-GNN and 3-IGN models.
Remark 5.14. Recently, [78 provided homomorphism characterisation of GNN models based on
k-WL-like tests for l: 2 2. As all of these models can capture arbitrary long cycles, they are not less expressive than any DHN model.
8

---

5.4 Continuity and universality of DHN
One of the desired properties of graph algorithms is the continuty. Graphs appear in network science applications are often very large and almost impossible to obtain the full structure. In a such case, we usually sample a smaller graph, conduct analysis, and expect the outcome approximates for the original graph [38]. The continuity guarantees the validity of such a procedure so that the outcomes of the original graph and the sampled graph are close. Such property is referred to as the size generalisability in GNN literature 73
Different sampling procedure introduces different notion of continuity (i.e., topology) in the graph space [48]. Here, we consider the BFS sampling, which randomly samples a node, performs k-hop breadth-first search (BFS), and select the subgraph induced by the nodes. The topology induced by the BFS sampling is called Benjamini-Schrame topology 6 68). We claim that PD is continuous with respect to this topology.
Formally, we consider the set 9 of rooted graphs with features whose degrees are at most d. Let G be the Cauchy completion of 9 with respect to the Benjamini-Schrame distance; see Appendix for the precise definition. Then, we can prove the following.
Lemma 5.15. For any finile Pt, PDHN is continuous function on B2 with respect to the Bejnamini Bejnanini-Scrramm topology.
This lemma has some applications. The first one is the universal approximation. We say that function is F -homomorphism indistinguishbble if [(GG, m)) = [((C),, .2)) for any J J**hhommorphism indistinguishable (G1, (1) and (2). We can show that any P Pr-hhommpphiim indistinguishable function is arbitrary accurately approximated by the DHN model as follows, which guarantees the validity of using P*-DHN model for tasks that p substructure is relevant.
Theorem 5.16. For any integer d and finite pt, the P*DDHN model is dense in the set of all P -i-iiiiiinguushable continuous functions on Gy--
Another application is the comparison with existing GNN models as follows.
Example 5.17 (DHN is incomparable with Zhang et al. (76).. Recently, Zhang et al. 76 observed that many linear-time GNN models could not detect biconnectivity, and they proposed a new model that can detect biconnectivity. Their observation is true because the biconnectivity is not a continuous property in the Benjamini-Schrame continuous in this topology. That is, for any continuous model, there are sufficiently close biconnected graph G1 and non-biconnected graph G2 such that the continuous model fails to detect their difference. Conversely, any model that can detect the biconnectivity must be non-continuous in the Benjamini- Schramm topology. Therefore, such models might not have size- saau-ennraaiiabbiityy which is not suitable for large graph applications.
topology, and most linear-time models, including DHN, are
6 Experiments
Experimental Setting We present the experimental results the three most common synthetic benchmark datasets for GNN expressivity and two real-world graph classification datasets. The Circular Skip Links (CSL) dataset consists of 150 undirected regular graphs of degree four (54). EXP I and SR25 12 36) are datasets not distinguishable by 1-WL (EXP) and 3-WL (SR25). The
ENZYMES 66 g and PROTEINS 88 22) datasets represent the protein function prediction task formulated as the graph classification problem We set the same experimental setting as previous works [ 34 24] see the Appendix foor more details of these datasets. For our DHN, we use two sets of patterns as the building blocks. Cu. (Ci,..., Cj} denotes the sets of cycles of lengths i to j. Similarly, Kıj
(K..... . K₁) denotes the set of cliques of size to j. We use 3-layer ML.ss for both p and H1p for the homomorphism layer (Fq. (4 ). In Table I we present the models' configurations inside the single brackets. For example, DHN (CgK(C. C2K3.5) means the model has two layers, and each layer consists of 4 kernels: C2 K3, K1, and KG. Note that K₁ has the treewidth of four; hence, the DHN with K₁ is incomparable with PPGN, I2-NNN, and N2-GNN.
Results Overall, we see that the performance of DHN depends on the choice of the pattern graphs. For suitable choice (i.e., the last row), it can solve all the benchmark problems. CSL is easy and
"These datasets are parts of the TUDataset collection.

---

Table 1: Experimental results on synthetic and real-world datasets for GNN expressivity (Acc.
#params
CSL
EXP
SR25
ENZYMES
PROTEINS
MPNN (4 layers)
72
27k
0
54.6 4.5
72.0 : 4.0
PPGN (4 layers)
ST
96k
100
100
0
5.7
77.2
I--NNN (4 laycrs) 34
143k
100
100
100
N2-GNN (4 layers)
24
355k
100
100
100
DHN (C=:1)
5k
100
50
0
64.3
+
76.5 = 3.0
DHN C2.5)
7k
100
81
0
63.7 5,4
77.0 = 3.2
DHN- (C2100)
27k
100
98
0
58.0
78.5 2.5
DHN- (C2 K3.))
7k
100
53
63.3
76.0 2.7
DHN DHN-(C2.4, C2)
8k
100
50
0
5.9
77.1 2.8
DHN C2:5 C2)
11k
0
62.0 5.5
77.0 + 2.5
DINN C2:5. C25)
36k
100
99
0
59.9
5.2
76.7 + 3.3
DHN- Cano. C2)
27k
100
100
0
63.5
6.1
78.2 = 3,3
DHN-
DHN- MIN-(C2K3s
(C2K355, C2K36)
36k
100
100
100
57.5
6.6
77.4 3.4
can be solved with any model (except the MPNN, aka. GIN). EXP is not co-spectral; hence, we can detect the difference by using eycles; shown in the table, using more cycles improves the performance. An important observation here is that stacking layer often boosts the expressive power of the DHN models the single-layer model DHN-(C2.s) can only achieve 81% while adding one extra layer, DHN-(C2:5- C2) achieves 99% accuracy. The same phenomenon is observed in other models except DHN--C2-4). SR25 is co-spectral; hence, adding cycles does not help solve the problem. Experimentally, we found that adding K3.5 solved the problem. Furthermore, stacking layers helped both in training convergence and achieving better results. In general, the DHN models have fewer parameters than the existing highly expressive GNNs because they are designed to capture limited of patterns, which leads fast and low-memory training
We report the stratified 10-fold cross- vols-valiit accuracies for ENZYMES and PROTEINS datasets in Table I Our proposed models performed comparably to other much larger high-expressivity models on these real-world datasets. Although our results are still far from the reported state-of-the-a results (78% for ENZYMES and 84% for PROTEINS), we believe DHN has the potential to be improved beyond the theoretical context of this paper.
7 Conclusion
In this study, we developed parameterised by a set of base patterns Pa, which is typically specified by the domain knowledge and computational complexity. The expressive power of the model is completely characterised by the homomorphism numbers from any patterns generated from P Moreover, the model is evaluated efficiently in several cases, including the patterns having bounded treewidth, graphs having bounded degree, the patterns having bounded DAG-treewidth, and the graphs having bounded degeneracy.
GNN named deep homomorphism network (DHN). DHN is
Limitation
The DHN model is motivated by network science applications that involve large and sparse graphs. Therefore, it might not be suitable for other applications. More specifically, using DHN might not be competitive in the following situations: (1) when the graphs are small so that O(n²) time complexity of k-WL graph neural networks is acceptable. This is commonly seen in graph classification tasks. (2) when the graphs dense so that pattern enumeration takes 2(n*) time. Simple models such as MPGNN would be more suitable for such case.
Future Work Essentially, our DHN is a "homomorphism extension" of the MPGNN model; therefore, it is fundamentally impossible to capture arbitrary long cycles. A promising future work to establish the corresponding theory for the local k-GNN for l > 2, which allows us to capture arbitrary long cycles attached small complex patterns which appear in biological networks. Such work will require combining our construction on top of the recently established homomorphism characterisation of local WL.s (78
'The source code for DHN is provided at httttttss//gttiii haaua//gar/dhh
10

---

References
[1] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surpris- ing power of graph neural networks with random node initialization. In International Joint Conference on Artificial Intelligence (IJCA121), 2021.
[2] Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning, pages 599-608. PMLR, 2021.
[3] Albert-László Barabási. The new science of networks. Cambridge MA. Perseus, 2002.
[4] 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.
[5] Paul Beaujean, Florian Sikora, and Florian Yger. Graph homomorphism features: Why not sample? In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 216-222. Springer, 2021.
[6] Itai Benjamini and Oded Schramm. Recurrence of distributional limits of finite planar graphs. Selected Works of Oded Schramm, pages 533-545, 2011.
[7] Suman K Bera, Amit Chakrabarti, and Prantar Ghosh. Graph coloring via degeneracy in streaming and other space-conscious models. In 47th International Colloquium Automata, Languages, and Programming (ICALP 2020). Baallos-Dagstthl-Leitttte Zentrum für Informatik, 2020.
[8] Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21 (suppl_ 1):47__)):7--i5661 2005.
[9] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(11) (5(())6677666) 2022.
[10] Marco Bressan. Faster subgraph counting in sparse graphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Schloss Baailoss-Dagsuuh--eeibbi Zentrum für Informatik, 2019.
[11] Emmanuel Briand. When is the algebra of multisymmetric polynomials generated by the elementary multisymmetric polynomials? Beiträge zur Algebra und Geometrie: Contributions to Algebra and Geometry, 45 (2), 353-368,, 2004.
[12] Jin-Yr Cai and Artem Govorov. On a theorem of lovász that (&sdot, h) determines the isomor- phism type of h. ACM Transactions on Computation Theory (TOCT), 13(2):1-25 2021.
[13] Jin-Ye Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992.
[14] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal computing, 14(1):210-223; 1985.
[15] Diane Cook and Lawrence B Holder. Graph-based data mining. IEEE Intelligent Systems and Their Applications, 15(2):32 41, 2000.
[16] Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory Computing, pages 210-223, 2017.
[17] Victor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theoretical Computer Science, 329(1-3)331533 323, 2004.
[18] George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, pages 2126-211 2132, 2021.
[19] Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets weisfeiler and leman. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Siaituull-LeibiizZZeente fuer Informatik, 2018.

---

[20] Josep Díaz, Maria Serna, and Dimitrios M Thilikos. Counting h-colorings of partial k-trees. Theoretical Computer Science, 281(1-2):2913300 2002.
[21]
Reinhard Diestel. Graph Theory. Springer, 2017.
[22] Paul D Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
[23] Zdenčk Dvořák. On recognizing graphs by numbers of homomorphisms. Journal of Graph Theory, 64(4)3330-342, 2010.
[24] Jiarui Feng, Lecheng Kong, Hao Liu, Dacheng Tao, Fuhai Li, Muhan Zhang, and Yixin Chen. Extending the design space of graph neural networks by rethinking folklore weisfeiler-lehman. Advances in Neural Information Processing Systems, 36, 2024.
[25] Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph gnms by rethinking their symmetries. Advances in Neural Information Processing Systems, 35:31376- 31390, 2022.
[26] Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kemels: Hardness results and efficient alternatives. In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003, Proceedings, pages 129-143. Springer, 2003.
[27] Floris Geerts. The expressive power of kth-order invariant graph networks. arXiv preprint arXiv:2007. 2035, 2020.
[28] CD Godsil and BD McKay, A new graph product and its spectrum. Bulletin of the Australian Mathematical Sociery, 18(1):21-28, 1978.
[29] Martin Grohe The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM (JACM), 54(1):1-24, 2007.
[30] Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. Color refinement and its applications. Van den Broeck. G.; Kersting, K.; Natarajan, S, 30, 2017.
[31] Martin Grohe, Moritz Lichter, Daniel Neuen, and Pascal Schweitzer. Compressing cfi graphs and lower bounds for the weisfeiler- refinements. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 798-809, IEEE, 2023.
[32] William L Hamilton. Graph representation learning. Morgan & Claypool Publishers, 2020.
[33] Pavol Hell and Jaroslav Nesetril. Graphs and homomorphisms, volume 28, OUP Oxford, 2004.
[34] Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with i In The Eleventh International Conference on Learn- ing Representations, 2023. URL httttstssspppeeeeeeeeeeeee
[35] Emily Jin, Michael Bronstein, Ismail Ilkan Ceylan, and Matthias Lanzinger. Homomorphism counts for graph neural networks: All about that basis. arXiv preprint arXiv:2402.08595, 2024.
[36] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
[37] Thomas N. Kipf and Max Welling, suni-supervieed classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https
//openrviiew
[38] Eric D Kolaczyk and Gábor Csárdi. Statistical analysis of network data with R, volume 65. Springer, 2014.
[39] Rui Li, Xin Yuan, Mohsen Radfar, Peter Marendy, Wei Ni, Terrence J O' O'Brien, and Pablo M Casillas Essinosa. Graph signal processing, graph neural network and graph learning on biological data: systematic review. IEEE Reviews in Biomedical Engineering, 16:109-135, 2021.
[40] Shouheng Li, Dongwoo Kim, and Qing Wang. Generalization of graph neural networks through the lens of homomorphism. arXiv preprint arXiv:2403.06079 2024.
[41] Don R Lick and Arthur White. k-degenerate graphs. Canadian Journal of Mathematics, 22 15):00821 1970.
12

---

[42] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 338-348 2020.
[43]
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020.
[44]
László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):311328, 1967.
[45] László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc.,
2012.
[46] Yao Ma and Jiliang Tang. Deep learning on graphs. Cambridge University Press, 2021.
[47] Takanori Maehara and Hoang NT. A simple proof of the universality of invariant/equivariant graph neural networks. arXiv preprint 1.XXV:19900088000 2019.
[48] Takanori Maehara and Hoang NT. Learning on random balls is sufficient for estimating (some) graph parameters. Advances in Neural Information Processing Systems, 34: 12111111111 27411141, 2021.
[49] Shmoolik Mangan and Uri Alon. Structure and function of the feed-forward loop network motif. Proceedings of the National Academy of Sciences, 100(21): 10022)):11980-11
1980-199111111 11985, 2003.
[50] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018.
[51] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[52] Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298(5594):824-88) 827, 2002.
[53] 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.
[54] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663-4673. PMLR, 2019.
[55] Daniel Neuen. Homomoophisn--iisinngiihhh closedness for graphs of bounded trec-width. arXiv preprint arXiv:2304.070// 2023.
[56] Hoang NT and Takanori Machara. Graph homomorphism convolution. In International Conference Machine Learning (ICML), Proceedings of Machine Learning Research. PMLR, 2020.
[57] Raffaele Paolino, Sohir Maskey, Pascal Welke, and Gitta Kutyniok. Weisfeiler and leman go loopy: A new hierarchy for graph representational learning. arXiv preprint 1377:9243..37749 2024.
[58] Daniel Paul-Pena and C Seshadhri. dichotomy theorem for linear time homomorphism orbit counting in bounded degeneracy graphs. arXiv preprint arXiv:2211.08605, 2022.
[59] Omri Puny, Derek Lim, Bobak T. Kiani, Haggai Maron, and Yaron Lipman. Equivariant polynomials for graph neural networks, 2023.
[60] Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2110-2119, 2018
[61] David E Roberson. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree. arXiv preprint arXiv:2206. 00..22000.0321, 2022.
[62] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph ncural networks. arXiv preprint arXiw:2303.10993 2023.
[63] Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078 2020.
13

---

[64] 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.
[65] Franco Scarselli, Sweah Liang Yong, Marco Gori, Markus Hagenbuchner, Ah Chung Tsoi, and Marco Maggini. Graph neural networks for ranking web pages. In The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI'05), pages 666-672. IEEE, 2005.
[66] Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research,
2004.
[67] Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. The power of recursion in graph neural networks for counting substructures. In International Conference on Artificial Intelligence and Statistics, pages 1023-11042. PMLR, 2023.
[68] Remco Van Der Hofstad. Random graphs and complex networks. Cambridge university press. 2024.
[69] S Vichy N Vishwanathan, Nicol Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 11: 11:1201-1242, 2010.
[70] Hinrikus Wolf, Luca Oeljeklaus, Pascal Kühner, and Martin Grohe Structural node embeddings with homomorphism counts. arXiv preprint arXiv:2308. 15283, 2023.
[71] Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recom- mender systems: a survey, ACM Computing Surveys, 55(5):1-37, 2022.
[72] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2018.
[73] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures to size generalization in graph neural networks. In International Conference on Machine Learning, pages 11955-11886 PMLR, 2021.
[74]
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. Advances in Neural Information Processing Systems, 34:19665-19679, 2021.
[75] Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, and Zhong Liu. The expressive power of graph neural networks: A survey. arXiv preprint arXiv:2308.000 08235, 2023.
[76] Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. In The Eleventh International Conference Learning Representations, 2022.
[77] Bohang Zhang, Guhao Feng. Yiheng Du, Di He, and Liwei Wang. complete expres- siveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. arXiv preprint arXiv:2302.077 07090, 2023.
[78] Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: A quantitative framework for GNN expressiveness. In The Twelfth International Conference on Learning Representations, 2024. URL httttttt/pppeeroeett wtwp:eeviiiiieeeeoornnen net/forum? id=HSKaG017Ar
[79] Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 34:15734-15745 2021.
[80] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations, 2021.
14

---

Algorithm Algorithm for tree pattern P.
1: procedure RECURSION(P* P* p)
2: dp,,uu] - for all u E V(G)
3: for E children(p) do
4: dp, RECURSION( P ,4)
5: dpplu] dpplu] + (x( > Nv)) dpylo] for all u V(G)
6: end for
7: return dpp
8:
end procedure
A Algorithms
A.1 Algorithm for Bounded Treewidth Pattern
If the pattern graphs have the bounded treewidth, we can compute the generalised homomorphism numbers in a polynomial time. Since describing the general case requires some preparation about tree decomposition, we here present the algorithm for tree patterns in Algorithm [ We emphasise that this algorithm just for an illustrative purpose because tree patterns are generated from c so the standard message passing GNNs can capture these patterns.
As preprocessing, we make the pattern pa directed toward the root. Let p*P be the subtree of p rooted at p. The procedure RECURSION [P*, ,p) computes the array [hom((P'*) (u), (G", e V[G) By the chain rule (Lemma 5.3 we have the following recursive formula.
hom (P pb), (G", ,2) (p(
Σ
hom( xz)).
(10)
gechildren(p) (EN(
For each node p. RECURSION(P:: P. p) is invoked exactly once. Thus, the complexity of the procedure is ((IV(P))[ which is linear in G.
The generalisation the bounded tree-width case straight-forward we just run similar dynamic programming algorithm where the states are bags. As we need to maintain the mapping from V(G) to the states, the complexity becomes ((G) See (20
A.2 Algorithm for Bounded DAG-Treewidth Pattern and Bounded Degeneracy Graph
the pattern Pa has the bounded DAG-treewidth and has the bounded degeneracy, we can compute the generalised homomorphism number in polynomial time. Since describing the general case requires lots of preparation about DAG-tree decomposition, we here present the linear- time algorithm for the simplest case that the pattern is the quadrange (aka. four cycle) Ca. This result is non-trivial because there will be ((n²) quadrangles in graph of bounded degeneracy (imagine the complete bipartite graph K2,,, which has left nodes and right nodes, has the degeneracy of two but has O(n²) quadrangles); hence, any naive enumeration algorithm requires ((n²) time.
We can observe that all quadrangles that have u and as the opposite nodes is represented "compressed" format, (u, v. (wi..... w meaning that there are (t) quadrangles by choosing any two W/ and Wy in addition to and v. For example, in the above-mentioned K₂,, case, we have only three tuples (u, u, [ur,..... w,))), (u, U, (wi,... ........ wn)).. and (v, v, (wi,..., (.,)) }) to represent all quadrangles in the graph. Chiba and Nishizeki (14) observed that if the graph has bounded degeneracy, we obtain a linear-size compressed representation for all quadrangles in the graph. Their algorithm is presented in Algorithm 2
Suppose we have a compressed representation of quadrangles (u, v, (wis.... wzz)). Then, we can compute their contributions to node u as
Σ Mz (1 ) (1 (H) = (I(w)) Σ (aa(tre)) pa(ct) Σ Emalewe)) (11)
15

---

Algorithm 2 Chiba-Nishizeki algorithm for enumerating all homomorphic images of quadrangle compressed format.
Initialise set[u] Ø for all u V(G)
for E V(G) in the decreasing order of the degree do
for w E N(u)) do
for v (w) do
Insert to the set[w]
end for end for
for v with set[u] * Ø do
Report (u, set[u]) set[u] Ø
end for
Remove u from G end for
Algorithm 3 Algorithm for evaluating hom((C4, (1) (G", .:)) for all
for (u, v, (Wi...., wx}) produced by Algorithm| in Appendix do Compute Wp == Σg (p( for 3,4 4.
Zu < Zu + 111 W2Ha (2,) W
2v Zy ja W2
Sw - Zu + pn (w A2 Fr (3)4((F))
end for Report 2u as (Com((4,, (G)
which is evaluated in O(k) time. The same procedure is applied to the contributions to node v. We can also compute the contributions w, by
(
Emacors))
(Fw
(12)
Here, the Twy factors common in all wy can evaluate them for all i in O(k) time in total. This procedure summarised in Algorithm 3
The general case (bounded DAG-treewidth and bounded degeneracy) is far generalisation of the above idea [00 188. Let P be an DAG orientation of P. Then, DAG tree decomposition of P is tree of bags such that (1) each bag B is a subset of source nodes (nodes without incoming edges), and (2) the union of bags covers all source nodes, and (3) if B lies the unique path between B1 and B2, then reachable( B1) n reachable( B2) S reachable(B) The maximum size the bag is The dynamic programming algorithm the DAG tree decomposition
called the similar to that on the tree decomposition case but enumerates all compressed representations of homomorphisms instead of the homomorphisms; see [10]. For example, C2 (1, 2, 3, 4) has DAG tree decomposition with two bags {1} and (3), and the dynamic programming with respect to this DAG tree decomposition produces Nishizkiss compressed representation of all quadrangles. This dynamic programming is easily converted to compute the generalised homomorphism numbers.
B Related Work and Comparison with Our Model
There are multiple GNN models that attain the intermediate complexity between the universal GNN and the MPGNN. Here, we review some of these models and describe their relationship with our model.
B.1 k-GNNs
The k-GNNs 5 or PPGN 51
assign values to k-tuples of nodes (instead the nodes itself as equivariant lincar layers defined by k-th order tensors. They
in MPGNN), and the I-IGNs 50
16

---

have the same expressive power as the k-dimensional WL test (72,27], which is equivalent to the Ts-homomorphism indistinguihaabiiiy where Ty: is the graphs of treewidth at most [23]. A recent variant [24] reduced the space complexity to O(n²) while keeping the expressive hierarchy to the graph isomorphism problem; we used this model (N²-GNN) our Experiment. These models are
often used in molecular biology applications as the input graphs are small.
The homomorphism characterisation mentioned above proves that P* model is not more expressive than k-GNN and k-IGN models as in Corollary 5.11 and Corollary 5.12 On the other hand, k-GNN and k-IGN might require (2(n") time as they have to aggregate information over k-tuples globally. Hence, they are not suited for large graphs as there will be millions or billions of nodes.
B.2 Subgraph GNN
Subgraph GNNs 79 74 80 25
are designed to capture local structures of each node. A single layer of a subgraph GNN takes subgraph for each node and applies a base GNN. The expressive power of the subgraph GNNs varies on the subgraph selection policy and the base GNN model. The
common subgraph selection policies include k- k-hop egographs, node/edge marking, and node/edge deletion, and the common base GNN is the MPGNN. In this case, Frasca et al. [25] proved that its expressive power is bounded by 3-WL test. Zhang et al. [77] analysed the expressive power of the subgraph GNNs by introducing subgraph WL-test, which basically runs the WL test on each selected subgraphs. Huang et al. [34 analysed the expressive power of the subgraph GNNs and showed that if we use MPGNN as the base encoder, it cannot count cycles of length more than four. Huang al. [34] then developed variant of mode-marking GNN that can count least 6 cycles while maintaining a linear time complexity on graphs of bounded degree; we used this model in our Experiment (N2-GNN). Tahmasebi et al. (67] showed recursive subgraph selection policy has higher expressive power learning all local functions.
In general, subgraph GNNs do not fit the homomorphism framework. However, we can still analyse their properties using the homomorphism framework. Let us consider the subgraph GNN model that uses k-hop egograph selection and universal GNN; this model is more expressive than any subgraph GNN model that uses h-hop egograph selection policy. Let 13% be the graphs of the radius from at most A Then, as homomorphism numbers from 8 to G characterise k-hop neighbours of u, the above model has the same expressive power the B -DHN model. This characterisation proves Corollary 5.13 which was already known in 777 Theorem 7.1].
Subgraph GNNs perform local computation; hence, they run in O(n) time on bounded degree graphs. However, they are still not suitable for large sparse graphs in the real world as these graphs contain few nodes with very large degrees (power-law property) and a small diameter (small-world property) In such graphs, building k-hopp egographs for all nodes may take M(n)) time.
B.3 GNN with explicit pattern detection
Using the numbers of subgraphs (incl. homomorphisms) as features is a traditional approach in network science and graph data mining 15
69 26 Recently, several researchers tried to integrate
this technology in GNNs [4 56
78.
As we mentioned in Section 1 our work is strongly motivated by the model of NT and Maehara 56
and the theoretical analysis of 4 The resulting model (or layer) provides a building block of GNNs
that perform local aggregation.
Using graph neural network Applying the homomorphism theory (or subgraph enumeration) in GNN is a relatively new approach. These are classified as follows.
Models based on graph homomorphisms To the best of our knowledge, NT and Machara 56 is the only study that explicitly uses graph homomorphisms as building block of machine learning model in a GNN context. Beaujean et al. (5) proposed to sample homonorphisms to estimate homo- morphism numbers to accelerate the computation. Related studies include the GNN with equivariant polynomials 36 59 since the homomorphism numbers define equivariant polynomials [4] 59
"E is infinite of graphs. Thus, need to consider each degree d independently.
17

---

Recently, Paolino et al. [57 proposed a GNN architecture that uses eycles for aggregation. They proved that their model can count cactus graphs of bounded cycle lengths. Their model is a special case of our DHN using Cga : (. Cx) as the patterns, and the set of cactus graphs of bounded cycle lengths is exactly the set of graphs generated from Cg&: using the rooted product. this sense, our method can be seen as generalisation of their methods for arbitrary patterns. One minor but crucial difference is that they didn't use the feature transformation. This means that their model cannot distinguish homogeneous cycle (adjacent nodes have similar features) and heterogeneous cycle (adjacent nodes have dissimilar features). See also Remark 3.2 about the importance feature transformation in theory.
Injecting homomorphisms numbers and/or subgraph counts features Barceló et al. proposed injecting bomomorphism numbers into the node features and Bouritsas et al. [9] proposed injecting subgraph counting into the node features. As these numbers are connected by the Mobius transformation [])], their expressive powers are not so different if we consider multiple patterns. Jin et al. [35] studied the difference and identified the effective set of patterns to be injected. We believe that their findings are useful for selecting the set of patterns pe in our DHN model.
Analysing expressive power by homomorphisms Traditionally, the expressive powers of GNNs have been studied using the Weisfeiler-Lehmant test (72). As the Weisfeiler- test has the homomorphism characterisation [99, it is natural to extend this discussion more expressive GNNs. The above-mentioned studies of injecting counts Barceló et al. [4). Bouritsas et al. [9], Jin al. 35 studied the expressive power of homomorphism numbers and/or subgraph counts-injected models via homomorphism numbers. Zhang et al. (78) identified the homomorphism characterisation of the expressive power of local WL-based GNNS. The pattern sets are characterised using ear decomposition. Li et al. [40] evaluated a generalised error of a GNN using homomorphism entropy. We believe that their analysis could be used evaluate the generalisation error of our DHN model as well.
C Experiment Details
C.1 Model Configurations
All DHN models in Table have 20 hidden units MLP layers; these MLP blocks (3 layers) correspond to functions in Equation 3 Each homomorphism kernel is embedded in 10 dimensions. The DHN models are trained using the Adam optimizer with an initial learning rate of 0.001. We do not use any learning rate scheduling or advanced regularization techniques, as the expressivity benchmark datasets can be learned with default hyperparameters.
Homomorphism mappings are pre-computed for each input graph and loaded to DHN like the edge list is loaded Pytorch Geometric's 's API. The homomorphism enumeration can be run in linear time and parallelizable for large graphs; hence, this pre-computation step is negligible compared to the training process. All our experiments can be run on CPU machine due to the small model size (M3 chip with 24GB of memory shared with the operating system or CPU-type Google Colab instance). The reported results are obtained on a single GPU machine that houses an RTX4090 with 24GB of GPU memory.
C.2 Datasets and Evaluations
Fach experiment is run for a maximum of 1200 epochs. Early stopping on train set accuracy with patience of 10 epochs is used for ENZYME and PROTEINS. For CSL, EXP, and SR25, since they expressivity benchmark datasets, the model is trained until train loss converged to zero
Table 2 describes the three synthetic expressivity benchmark datasets commonly utilized in Graph Neural Network (GNN) research to assess and benchmark the expressive power of various GNN architectures. The CSL (Circular Skip Links) dataset consists of 150 regular graphs that cannot be distinguished by simple MPGNN. EXP graphs are crafted to be isomorphic under the 1-WL test, meaning that traditional GNNs limited by the WL test's discriminative power may fail to distinguish them. The EXP dataset is a benchmark for whether GNNs can surpass the WL test limitations by capturing higher-order structural information, distinguishing between -oniisomopphic but 1-WL.- indistinguishable graphs. The SR25 (also named Paulus Graphs) dataset consists of strongly regular
18

---

Table 2: Expressivity Benchmark Datasets
Dataset
[
[V(G]
[E())
CSL
150
41.0
164.0
EXP
1200
44.4
110.2
SR25
15
25.0
300.0
Table 3: Real-world Graph Classification Datasets
Dataset
[9]
[|V(G))
B] E()]
#node features
#classes
PROTEINS
1113
39.06
72.82
ENZYMES
600
41.0
164.0
21
6
and co-spectral graphs, which require high expressivity GNNs to distinguish. Essentially, model that performs perfectly on the train set of this dataset would perform well on the test because both sets have the same isomorphism classes. Except for SR25, which needed 800 epochs to converge, EXP and CSL training converged less than 20 epochs our experiments.
J the real-world datasets commonly utilized in Graph Neural Network (GNN) research to assess the practicality of graph neural network. These datasets come from the TUDatasets collection, and due to their small size, it is conventional to report their 10-fold cross-validation results. The PROTEINS dataset consists of 1113 graphs, where the nodes and edges of each graph contain information about the secondary structure of the protein. The ENZYME dataset contains 600 graphs, each corresponding to protein enzyme. The nodes signify amino acids, and the edges represent chemical interactions or spatial proximities between these amino acids. The dataset is divided into six classes, each corresponding to one of the top-level enzyme categories defined by the Enzyme Commission (EC) numbers: oxidoreductases, transferases, hydrolases, lyases, isomerases, and ligases. Nodes are annotated with attributes capturing physicochemical properties relevant to protein function.
D Proofs
D.1 Proof of Theorem 3.1 Generalised Homomorphism Determines Isomorphism
We use the following generic theorem.
Theorem D.1 (Theorem 3.6 in Lovasz 44
Any finite relational structure is uniquely identified by
the homomorphism numbers.
Proof. The "if" direction is clear. Thus, we prove the "only-if" direction.
V(G1)) (m2ng u2 V(G2)) and associate unique labels to them. We denote by l(x) for the label associated with x. Then, the input graphs are the instances of finite relational structure, where the relations are the root relation (u is the root), adjacency relation (u and v have edges), and the feature value relation (u has the feature value .r).
We first enumerate the relevant feature vectors (Zing
The isomorphism (Gi, .1) (Ga, x2) of rooted featured graphs coincides with the isomorphism of the relational structure introduced the above. By the Lovasz theorem, if the input graphs are not isomorphism, there exists a relational structure (F*,1) such that the homomorphism numbers from this structure distinguishes the input graphs. Because the homomorphism number of this relational structure can be computed by the generalised homomorphism number, by setting (a smoothed version of) (p(x) [[((z) = 4p]. Therefore, we obtain the result.
19

---

D.2 Remark 5.8; DHN generalises the most expressive subgraph GNNs
Suppose h. f(h, we H"). Let p be the graph isomorphic to H Then, we have
hu )Aut(G")
Σ
(hy :ee:UuTTTH) (H)))
(13)
TEAut(Gu)
Σ
f (ba(p) :pE P*)
(14)
Hemoomiee (m)) (P*,G")
Σ
II Hp(hir(p))
(15)
rr 00 P ..)) pE
=p =p <hooom
hhm (ini) ((P", (G",))))))))
(16)
because the first equality follows from the equivariance of the layer, where Aut(G") is the set of automorphisms (isomorphisms itself) of G", the second proportionality follows because each automorphism induces an injective homomorphism, and the third equality follows by taking Up(x) := exp ((O,... .., 0, x, ..................... O]) and :(:.,...::!P0.. := s(log Ep pp P*).
should be noted that this does not cover strategies like node marking in subgraph GNNs as such strategies (tentatively) break isomorphisms improve their expressive power. To cover such strategies, we might need higher-order theory of DHN.
D.3 Proof of Theorem 5.2 Expressive power of DHN
To prove the theorem, introduce variant of the WL test as follows. The P*--iiseeiler Lehman test performs the following colour-refinemen procedure. the O-th step, we assign the node features the colour. In the (k 1)-th step, for each V(G), it enumerates all patterns p and all rooted homomorphisms E Hom P*; G, and associates the colours based on the colours in the k-th step. Formally, is given follows.
Lu
(+++)
(El
(k) T(p) :PE)(P)) : Hom(P"
.G) ,G' p PPEP))
(17)
Then, it determines the non-isomorphism using the obtained colours, like the WL test.
Example D.2. ( ---WL WL test coincides with the standard WL test.
Now, state main theorem about the expressive power of the DHN model.
Theorem D.3. Let Pa be set of rooted graphs. For two rooted graphs with features (Gf, .i) and (G5, 22), the following are equivalent.
1. The -I- does not distinguish (G), and (G2, 22).
2. For any P h, we have a1) = x2).
3. (1) and (G2, x2) are p"-hoommorphhis indistinguishable.
(1 = 2). This part is generalisation of Theorem 3 in [72]. This is trivial from the definitions because the WL-colouring contains all information that needed compute the DHN.
(2 = 3).
show that, for all F E J and μ, there exists a P-DHN h such that hom(((F p), (G",z)) h(w), which immediately proves this claim. We prove this claim by the induction about the construction of F.
Base Case The base case is that F' is pattern graph, i.e., F= for some Pe P. This case is trivial from the definition of the DHN model.
Induction Case Induction case is that F is obtained by attaching smaller subpatterns Fi,..., Fx F to some P P. By the product rule and the chain rule, we can represent hom ((F, n), G)) by the sum and product of hom((F,, p4), G), which are represented by the DHN by the inductive hypothesis.
20

---

As the DHN is closed under sum and product (Lemma D.6,, hom((F, G) is also represented by DHN.
(3 => 1). This claim generalisation of 19). Here, we provide "direct" proof of this claim. We prove that P.-WL colouring of step k is identified from the values hom((F), pg); G*) for some (Fi, (4) F. In the proof, we extensively use the following lemma.
Lemma D.4. The values of the mulli-symmetric power sum polynomials,
d
Σ
(18)
uniquely determine the multiset of vectors
(a.1..... aid) à 1.....
(19)
Here, each is bounded by a constant that depends on and d.
Proof. This is extension of the famous "fundamental theorem of symmetric polynomials" and follows from the basic results of the invariant theory; see 11. Theorem 3J.
First of all, is because all the nodes that appeared in the computation are contained in a sufficiently large homomorphic image F. and by putting (p(x) 11, " we have
assume that we know all the values pe relevant the computation. This
(F. Gu)
Σ
II II (=(T())))
(20)
reHom(F...o (FV(F)) je[d]
Therefore, by Lemma D.4
uniquely reconstruct the set
X == [Tm(p) D V(P")), which tells all the possible values that appeared in the computation.
(21)
Now, we prove the claim by the induction about the depth of the pattern expansion.
Base Case
The case is trivial.
Induction Case
We first identify the number of children with respect to P by computing
hom((P, (om((PPiig..ol v(ry)s GD)
(22)
for (p(P)) that satisfies
Ma #
PEV(P)
Tp. 24 ................................ TPiv(P) Dijy(P))
(23)
Such y can be constructed by projecting vectors into [V(P) dimensional space.
Next, we identify the colour of the substructures below e V(P). By the induction hypothesis, there exist patterns with transformations (Fi, pı),..., (FM pM) such that their homomorphisms identify the colour of steps less than k. Using these patterns with transformations, we define a new set of patterns with transformations as follows.
For each E V(F), we attach Fi ep,1 times, F2 pp2 times, and so on, by the rooted product.
By definition, this pattern is in F. By the chain rule of homomorphism numbers, we have the following.
hom((F G))
Σ
II
Nom((F;.pa)) Gr(n))en.
(24)
Te (o.....))) (PV(P).
1_1...,M
By Lemma D.4 we can uniquely reconstruct the multiset of vectors
(homm(Fi,,A)) ( hom (FM, Par), (=(n(())))) (ee
(25)
Therefore, identify the colour of each p in each child.
21

---

D.4 Proof of Lemma 5.3 Chain Rule
Proof. Any rooted homomorphism e HommF", G*) identified as concatenation of homomor- phisms To Hom(P", G*) and Tp E HommF p. Gr(r)) for each p. Hence,
hom((F" p)), (G", (G*,,) x))
(26)
Σ
II
Mp(#x(p))
(27)
rEHomm(P P G*) (EV(
Σ
π
Σ
Il Mg (g(
(28)
ToE .O)) pe (PP)
op HFoom G (eV(FF)
Σ
I
hom((F) plv(F))) (Gm(P),
(29)
ToeHom (P* G*) peV(Pt)
D.5 Proof of Theorem 5.16; Universality
This is a direct application of the Stone- Weierstrass theorem:
Theorem D.5 (Stone-Weet Weierstrass Theorem). Let M be compact Hausdorff space and A be set of continuous functions. If A forms an algebra, contains the constant function and separates points, then A is dense in the space of uniformly continuous functions on M.
We first check that DHN forms an algebra.
Lemma D.6. The P-DHN model is closed under sum, product, and scalar multiplication.
Proof. The claim is clear for scalar multiplication. To prove the claim for sum and product, we observe that the stacking of two models, i.c., h(( tt) == [h](u), h2 [u)], is in the DHN as it is implemented by stacking every i and p. The sum and product obtained by modifying the last layer of the stacking model.
We then check the topological condition. Let 9j be the of all rooted graphs with features such that the maximum degree is at most d. We introduce the metric in this space as follows. Without loss of generality, we assume that maxe, #2EX | x2l where the norm associated with X.
First, for each integer r, we define
(1.
G x G?.
d,((Ci x1), (Gg,
(30)
mmnn((1/n)) En |2 - #2((1)]l
otherwise
where 7 runs over the isomorphism between Gf and Giz, and n, is the maximum number nodes of graphs of diameter and degree d. We then define
d(GGi, (G), = 2 (G), (2))
(31)
where [NN, is the graph with features whose graph part is the subgraph of G* induced by the r-neighbourhood of the root and the feature part is the restriction on N,.. Note that this induces the standard Benjamini-Schramm topology if the graphs have no features (68]. We prove Theorem 5.16 5.16 with respect to this topology.
Lemma D.7. G is totally bounded Hausdorff.
Proof. It is easy to see the space is Hausdorff because, (((G),,)), (G2, x2)) 0 implies their r-neighbourhood are isomorphic for all r. By choosing r sufficiently large as it covers whole G and Gø, we obtain G 2 G?. By definition, there exists that satisfies Tia = T2m(u) for all u. This indicates that m1) (2).
Now we prove that the space is totally bounded by constructing an Oee)-net for any > 0. We choose To (1/e) and enumerate all rooted graphs of diameter at most ro and degree at most d. There are O(2d"") graphs and each of them have ((d')) nodes. Then, for each rooted graph, we enumerate all the rooted graphs with features by assigning node features from the e-net of X. Then, obtain the e-net of Ga.
D
22

---

Corollary D.8. The covering number of ---iipschitee on 9a is 21/6))
Proof. By counting the size of O(c)-net in the above proof, that the covering number is (1/e)()))oc))) Therefore, the covering number of I-Lipschitz continuous functions is 2(1e))0//00))
Lemma D.9. Any P-DHN h is uniformly continuous on 92.
Proof. By definition, there exists finite such that the r-neighbour of the root determines the value of h. We choose 6 sufficiently small so that (G1 x1), (G5, x2)) < indicates that the r-neighbour of Gf and G are topologically isomorphic. In this case, h((G), x1)) and h((Gz, x2)) only differ at the feature values. Therefore, for any > 0, by choosing å sufficiently small, we can make [N((G), 21)) h((G2, x2))l for all (G1, 21) and a2) with d((G), #1), (G2, < 6. L
Remark D.10. In this study, we only discuss the universality of the graphs of arbitrary sizes. We can easily prove the universality for graphs of fixed size, which is more often discussed in previous studies (see [64] 75),, by the same proof strategy without any complicated topology discussion. However, we believe that such universality is not useful in practice as we usually apply GNNs to
graphs of different number of nodes.
D.6 Proof of Corollary 5.9 Comparison of Models
Let Pt and P3 be two of patterns. Our goal is understand the relationship between the equivalence relation of the 77 -pmoomooopph indistinguishabblity and ? ho-mmoopphiss indistin- guishability, Here, we provide a tool to identify their relationship.
Roberson 61 introduced concept called homomorphism hiiiiiiiiii-istiiiniiiinnnn closed. A set of graphs F is
closed if a graph satisfies hom H, G₁) = hom(H, G2) for all G1 and G2 with hom F, G1) hom F, G2) for all F e F then H F.
Here, we use the rooted graph variant as follows. A set of rooted graphs F is homomorphismn distinguishing closed if a rooted graph H satisfies homi H GT) hom "T*, for all G and G with hom(F G homi F G for all F F then H F By the definition, if Jt S F2 and they are pewpomorphiimmdsstgsssshhee Fj leads a strictly finer equivalence relation than that of Jí. For a set of rooted graphs F the closure is the smallest homomorphism distinguishing set including F, which is well-defined. By definition, J and cl(FF) leads the same equivalence relation.
closed, then the
of
The following is the key lemma of connecting the honomophism--disingguihih closedness on graphs with features and graphs without features.
Theorem
Let F be hommomrrpiisn--iiitnnuuuuhh F if and only if there exists (G) and (G2, such that hom((F* (G for all F hom (V), (G, (1) # hom((H, D), (G), for some v.
D.11. H'
closed set of rooted
graphs.
hom( F p)) (G. (Gf,
FF and μ but
The "only-if" direction is easy: H $ F guarantees the existence of G1 and G2; thus, the claim holds for x) and (G2,z) where x takes the same value at all nodes.
To prove the "if" direction, we use the following lemma.
Lemma D.12. Let (F+, be a rooted graph with transformations. hom((F (F*, p.) (G², # hom((F" ,H), (), (2), for some (G), and (G2, Then, there exist G and G7zz such that
Suppose
1. hom F*, "TG * hommF",
2. For any rooted graph F'a hom F G!+)) is the sum of ho ,1²),, (G; (G), finitely many yl.
Proof. To simplify the presentation, we prove the same claim for non-rooted graphs. We first construct node-weighter graphs (K;, w:) for i 1,2 by defining V(K,) ((u,,)) 4) u; V(G.), p E V(F)) and E(K,) [[(u, (v, q)) (w,, v.) E(G.). We then put node weight
23

---

by = (Tp where fnp E ((F)) are algebraically independent numbers. Then, we have hom F, 1 wi)) hom F. (K2; w2)) since the II "p term of hom F, (K,, w,)) is hom((F, p), z;)).
We then construct unweighted graphs H; for i = 1,2. We take scale parameter and define Ky by ((K))= {(ra,) s) z, V E {1..... [aw((z)) and E(H,) {((2,, s), (y,, t)) 22 V),.) Then, by construction, we see a hom F. H/a implies that for sufficiently large we have hom( F, Hp) * hom F, H2). This shows the first condition.
hom( F, (K,, we)). This
These H satisfy the second condition as follows:
hom(F" (F,, ,H = hom F", (K,, (ow,))
(32)
Σ ED
Σ
II (Mtro(
(33)
xeHom hom((F', (G,,,,
(34)
where yí' is defined by u = [M for each :: V(F') - V(F).
We can easily modify the above proof rooted graphs by only duplicating non-rooted nodes, although the notation will get messy.
Proof of Theorem D.IT (if direction). Suppose there exist (G1, x1) and (G5. 22) such that hom((F* ,1),, (G)) (2)) for all F E F and Mr, but hom (H".u2) .22 (22,((C x1)) * hom( p2), (G), 82)). We take G and G constructed in
hom(( [ p1), (G1, (1,21)
Lemma D.12 Then, by the first condition, we have hom F2 Gf) o hom C.)) Also, by
the second condition, we have hom Ff, Gf) hom Pf. G for all Fi E J.. Therefore, as F
homomorphism gumnommrphismmdiitiggiiiiinn distinguising closed, we have H F*
To compare the expressive powers of two DHN models with respect to patterns Pt and Pg. we have to compare cP()) and cl However, it is not easy to characterise the homomorphism- distinguishing closure of given set. Here, instead of characterising their closures, we try to find another homomorphisn--eppaaaing set H that "separates" Pt and F2 using the following lemma.
Lemma D.13. Let Fi and F2 be sets of rooted graphs. If there is homomorrhiss-ddiiiiiggiisiss closed set H such that Fi E H. and F3 $ H., then cl(FT) $ cl(F)).
Proof. This is clear from the closure property.
In the literature on homomoprhism distinguishability, we have several examples of homomorphism- distinguishing closed sets. Here, we use the following two examples toomommpphismmisstiiuuiiiing closed sets.
The set To of graphs of treewidth at most 61 55
Thee set CC2 of graphs of maximum chordless cycle length at most & [61].
As their hwtpanoooppiiiiiiiiiiiiussailiii the corresponding result for rooted graphs. We use the following lemma, which guarantees that the rooted counterparts, Tx and CC2, , are homomorphism distinguishing saammmoppisnnddisiigiinnnnggn closed.
are proved for non-rooted graphs, we have to prove
Lemma D.14. Let F be product (luking any node as root) and contains a single edge o, then F is homomorphism- distinguishing closed, where F (F> F E F, u V(F)) is the graphs obtained by picking each node as root.
closed set. If F is closed under the rooted
To prove this lemma. we use the following to connect the homomorphism number and the rooted homomorphism number.
Lemma D.15. Let F be a set of rooted graphs containing + o. Suppose is connected. Then, we can identify hom(F, G) for any F E F by hom H" GO) for several H.
24

---

Proof. To identify hom (F, G), we construct Hi F as follows. We first construct a path of length k by attaching edges. Then, for each node i, we attach edges (so is a caterpillar graph). Finally, we attach ek+1 copies of F the tail (farthest point from the root) of the caterpiller. Then, we have
hom(H H Ric: G
Σ
de hom F", (ut
(35)
(14 (Mi Jowalk from
Hence, by Lemma D.4
obtain the following quantity:
hom(F" .(*))
Σ
(36)
dus du....dus
(112 J:walk from
Let W = D-11 be the random-walk matrix of G. Then, the above quantity is written as e. W*[hom(F* G") u V(G)], where e, is the unit vector. Therefore, we can also obtain G*): u E V(G)J. As (I + W)/2 defines irreducible aperiodic random walk, e, ((I W)/2) converges to the stationary distribution 1/n. Therefore, can estimate I' ['homm F G") u E V(G) = hommF, F, G) arbitrarily accurately.
all the values e. ((1 [)/2)*[hom))
n
Proof of Lemma D.14 Let H be rooted graph. Suppose there exists connected rooted graphs G and G5 such that hom F Gi) hfm, ,G) for all F F but hom H G * hom( H! Gg). By Lemma D.15 the former condition yields hom(F, Gi) hom [F, G2) for
all E F and the latter condition yields hom H, G1) * hom H, G2). Therefore, by the homomorphism comommophism-ddstingguiinnn closedness of F, we have H & F. Therefore, H F
Proof of Corollary 5.9 We say that 7 separates PI from F3 if they satisfy the condition in Lemma D.13 In this case, by Theorem 5.2] we can conclude that PI-DHN model is not more easily observe the following.
expressive than PDHHHN model. Here,
MPGNN model is the (+ oo--)-DHN model and T separates ( -} from p.
2-GNN model is the -DHN model. Let be the longest chordless cycle length in P*. Then, CC 1+1 separates P from T
CC2 separates C% from k+1 To separates K from k+1 Tk separates St from St k+1'
T separates Ct from St. since any graph in C has treewidth at most two. CC separates St from T% as no graph in St has chordless cycle of length k.
CC3 separates K from St since no graph K2 has chordless cycle of length more than three. T. separates St from KC since every graph AG has the treewidth at most k.
The above proof works for separating C and Ki.
25

---

Figure 3: Hierarchy of GNN models. Only showing WL variants, Cg-DHN, and Kg-DHN. Models without (transitive) arrows means they are not comparable, e.g. 2- WL and DHN with & 4 cliques are incomparable.
4-WL (5-IGL, 5-GNN)
3-WL 4-GNN)
DHN with & 5-cliques
2-WL (3-IGL, 3-GNN)
DHN with & 4-cliques
DHN with & 4-cycles
DHN with & 3-cycles
DHN with & 3-cliques
1-WL (MPGNN)
DHN with an edge
26

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The theoretical claims are proved in Section 5.1 The experiment is shown in
Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made 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.
It is fine to include aspirational goals as motivation as long as is 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]
27

---

Justification:
We discussed the assumptions in our theory and the trade-offs in experiments.
Guidelines:
The answer NA means that the 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 in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect 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 on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 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 the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of 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 complete (and correct) proof?
Answer: [Yes]
Justification:
We provided self-comtained proof's for all theorems in Appendix.
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 or referenced 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 short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: This is a theory paper; thus, the experiment conducted to verify the theory. All datasets used in the paper are publicly available.
Guidelines:
28

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a 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 to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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 it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provided an anonymous prototype on Google Colab. The datasets are publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "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 (https
/ //nips.ccppulic//guue http:///cc/giiee//eeeuuubiiiiiin
for more details.
The authors should provide instructions on 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 new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
29

---

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) is 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: This is theory paper the experiment is just conducted verify our claim. The short description in Section 6 the details with additional experiments are provided in Section in Appendix.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Due to the nature of the expressivity benchmark datasets, the results are consistent across multiple runs the experiment. We omit reporting the standard deviation because they are zero.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
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.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 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 to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain 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 on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Type of computing resources reported in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or 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 experimental runs well estimate the total compute.
30

---

The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpp:://euurii: httpp///bb.///iiiccciiieeeeeeeee
Answer: [Yes]
Justification: The research did not involve human subjects or participants. We only used datasets that had no concerns listed in the guideline. As theory paper, has no risks on societal impact and potential harmhul consequence.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The paper has no risks on societal impacts because this is a theory paper
analysing mathematical properties of neural network models.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This a theory paper analysing mathematical properties neural network models. The datasets used in this paper had no such risks.
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:
We provided citations and links to the codes used in the experiment.
Guidelines:
existing assets. The authors should cite the original paper that produced the code package dataset.
The answer NA means that the paper does
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwwpppaiitthooe thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is 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:
We provided codes as assets.
31

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the datasct/codc/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: We do not involve research with crowdsourcing and human subjects.
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 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: We do not involve research with human subjects.
32


Reviews:
[{"review_id": "dgaStuyNk2", "reviewer": "Reviewer_X5N6", "summary": "The authors propose a new neural network architecture for graph data, namely “Deep Homomorphism Network” (DHN). This is constructed as a stacking of “Graph Homomorphism layers”, which compute learnable, generalised homomorphism counts for a set of predefined input patterns.\n\nDHNs extend the following previous works: (i) the approach by NT and Maehara which precompute extended homomorphism counts on attributed graphs and use them to define hand-crafted features for downstream models such as kernel methods; (ii) the approach by Barceló et al. which propose to add rooted homomorphism counts for a bank of patterns as initial features for downstream message-passing neural networks. With respect to (i), DHNs are `deep`, and can distinguish graphs beyond the homomorphism-distinguishability of the predefined set of input patterns. In relation to (ii), DHNs can account for features, and fully subsume the approach of Barceló et al. which can be considered as a special DHN whereby deeper layers only consider a bank made up of the single node and single edge patterns.\n\nAfter expanding on preliminaries and model definitions, the authors interestingly show how the model fully capture msg-passing neural networks with a simple bank design, and then turn into discussing computational complexity, showing that, in some noteworthy settings, this grows linearly or polynomially.\n\nA section on expressive power follows. The authors characterise the expressive power of their model in terms of homomorphism indistinguishability w.r.t. a bank of patterns obtained by the \"closure\" of a \"kernel bank\" w.r.t. rooted graph product. Next, a series of precise results are obtained in terms of typical bank choices (cycles, cliques, connected graphs of a certain size), and in contrastive terms w.r.t. known expressive models.\n\nFinally, the authors practically experiment with their architecture on synthetic benchmarks for node disambiguation, in an attempt to empirically verify the discriminative power of their model. Results validate how this depends on the choice of the pattern bank and, importantly, the depth of the architecture.", "questions": "- (Q1 - minor) Line 116: what are domain and co-domain for $f$? Can the authors specify? I think it would help towards a better comprehension of the following lines.\n\n- (Q2 - minor) Line 149: Why do the authors use the first-plural pronoun? Would it be more correct to use an impersonal “it is possible to show”?\n\n- (Q3) Theorem 3.3: Is it essentially a consequence of Lovász’s theorem? It would help if the authors referred (already in the main corpus) to previous works and their proof in the appendix.\n\n- (Q4) What is $\\mu$ in Eqs. 6, 7?\n\n- (Q5) In Example 5.1, is the single vertex not needed? What is the intuition behind?\n\n- (Q6) The authors refer to the k-WL test as the “Folklore” type, right? If so, shouldn’t 2-GNNs and 2-IGNs be, instead, 3-GNNs and 3-IGNs (page 8)\n\n- (Q7) What is, concretely, the task solved in the experimental setting? Is discrimination cast as multi-way classification? Can the authors provide more details on that?", "limitations": "The authors mention limitations in the last paragraph of their manuscript (main paper). They could expand as per hinted in (W3), should other limitations emerge.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- (S1) The present manuscript proposes a new, valid, interesting approach for expressive graph neural models. It builds on top of known works, but extend them in meaningful and concrete ways.\n\n- (S2) The proposed architecture is comprehensively studied in terms of its expressiveness, and its complexity is additionally discussed. The results on expressive power are precise and informative.\n\n- (S3) DHNs meaningfully subsume some known architectures, offering a new, interesting perspective on how a deep graph neural model can be structured beyond message-passing and combinatorial approaches.", "weaknesses": "- (W1) The presentation of the paper could be improved in some parts. For example, the authors extensively refer to the graph rooted product around Lemma 3.1, but this is only introduced in Section 5.1 (almost two pages later). Some other parts could be improved as well by either giving better intuitions or by providing additional visual support. This would help the reader especially in technical and theoretical parts. This can be true, for example, around  Lemma 3.1 — why does it hold, is it trivial that one can decompose homomorphism $\\pi$ into $\\pi_0$ and $\\pi_p$, how would the two look like on a visual example?. As another example, a figure explaining Example 5.1. or the hierarchies/relations in Corollary 5.6 would help. An illustrative aid could also support the comprehension of the formula in Eq. 3.\n\n- (W2) The authors do not experiment at all on real-world benchmarks. Why is it the case? What would the reader expect on those? One interesting aspect of of DHNs is that they can (easily) account for node features; this kind of real-world experimentation would help gathering a signal on how important this architectural feature is.\n\n- (W3) The authors do not position well enough their contribution in the broader landscape of GNN research beyond expressive power. What is the impact that we should expect from these new architectures? Will they find a strong real-world application in a certain setting? Should they rather considered as an approach of purely theoretical interest?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reading our manuscript carefully. We revise our manuscript to improve the clarify and readability by addressing your concern. Below, we reply to each comment/question.\n\n# Weakness \n\n**(W1) The presentation of the paper could be improved**\n> graph rooted product around Lemma 3.1\n\nWe'll re-organise Section 3 as follows: We move Lemma 3.1 to Section 5. We also elaborate Theorem 3.3 by adding a remark to clarify **[W1]** of Reviewer AtgF.\n\n> Some other parts could be improved as well by either giving better intuitions or by providing additional visual support. \n\nWe will add illustrations to Lemma 3.1 and Hierarchy of Corollaries. \n\nThe decomposition in Lemma 3.1 is straight-forward. For example, let's take the spoon graph $F$. The nodes are $\\\\{r, a, b, c\\\\}$, where $r$ is the root, $\\\\{r,a,b\\\\}$ forms a triangle, and $\\\\{b,c\\\\}$ forms an edge. Let $\\pi$ be an arbitrary homomorphism from $F$. Then, $\\pi$ is decomposed into $\\pi_0$ that maps the triangle $\\\\{r,a,b\\\\}$ rooted at $r$ and $\\pi_b$ that maps the single-edge graph $\\\\{b,c\\\\}$ rooted at $b$. They are the restrictions of $\\pi$ on these subsets. As $F$ is obtained by attaching the edge to the triangle, this construction is one-to-one. We will add an illustration to show this construction, which may help to understand the decomposition at a glance.\n\n**(W2)** We understand your concern; based on our expressivity results, the reader should expect our model to perform better than less expressive baselines but not better than highly engineered SOTA models on real-world datasets. We report such results in the global rebuttal.\n\n**(W3)** This paper is on the line of studies of GNN expressive power, although we are motivated by practical large graph applications that involve subgraph feature engineering. In this sense, this paper itself doesn't immediately provide SOTA-level GNN architecture. The important missing part is how to design patterns and optimize the architecture accordingly. Although our model with basic patterns worked well on benchmark datasets in the manuscript and real-world datasets in the global rebuttal, we think the practical DHN architecture requires further work. We will mention this limitation in the updated manuscript. \n\n# Questions\n\n**(Q1 - minor)** This is a great point. For an invariant function $f$ (line 116), the domain of $f$ is the set of all graphs with features. The codomain is arbitrary, but usually $R^d$. On the other hand, for an equivariant function $f$ (line 119), the situation is very complicated. As in the invariant case, the domain is all graphs. However, the codomain depends on the input since for each $G$, $f(G)$ is indexed by $V(G)$ as $f(G)_u$. So, mathematically speaking, the codomain of an equivariant function is $\\bigcup_G \\mathbb{R}^{d \\times V(G)}$. This \"irregular codomain issue\" makes analysis difficult. Hence, we are consistently working on rooted graphs in this paper (this is the idea in https://arxiv.org/abs/1910.03802). For rooted graphs, we have $f(G^r) \\in R^d$ so its codomain is $R^d$ regardless of the input graph. This is explained in line 120--122, but we will elaborate to clarify the reasoning.\n\nNote that most existing GNN studies didn't have this issue because they worked on graphs of fixed number of nodes. However, in many applications we often compare the function values on two different size graphs $G$ and $G'$ (see also Response to **[Q5]** of Reviewer 2WwS). Hence, we decided to employ the rooted graph formulation.\n\n**(Q2 - minor)** We'll fix this.\n\n**(Q3)** Yes, this is an immediate consequence of Lovasz 1967's classical theorem (https://www.cs.elte.hu/~lovasz/scans/opstruct.pdf), which says that any relational structure (not limited to graph) is uniquely (up to isomorphism) identified by the homomorphism numbers. We just need to confirm that our generalised homomorphism can count the homomorphisms as graphs-with-features, but this is also straight-forward. This is written in the proof in Appendix, but we will add the idea to the main body of the paper. See also Response to **[W1]** of Reviewer AtgF.\n\n**(Q4)** Thank you for pointing out the imprecise presentation. $\\mu$ is a set of functions defined on nodes, $\\mu = \\\\{ \\mu_p: R^{d_i} \\to R^{d_o} : p \\in V(F) \\\\}$, transfers node features, which are the parameters of the model. In this specific case, the precise definition is in the Response to [W2] of Reviewer AtgF. We will put these precise definitions to avoid confusion in the manuscript.\n\n**(Q5)** The singleton is included by the definition of the closure (0-th power is the singleton); see line 237.\n\n**(Q6)** No, we meant k-WL original version.\n\n**(Q7)** Indeed, in our experiments, distinguishing isomorphism classes is cast as multi-class graph classification and experimental settings for each synthetic dataset followed the literature. Each input graph belongs to an isomorphism class, and the task is to detect these classes in the test set. For example, SR25 is a set of strongly regular and co-spectral graphs belonging to 15 different isomorphism classes; the task is to correctly detect these isomorphism classes.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h5DLN39tye", "reviewer": "Reviewer_2WwS", "summary": "The authors introduce Deep Homomorphism Networks (DHNs), which generalize Message Passing Neural Networks (MPNNs) and previous Homomorphism Networks. DHNs explicitly count the number of homomorphisms from pattern graphs to the input graph, calculate representations based on these counts, and update node features accordingly. MPNNs are a subset of DHNs when patterns are limited to single nodes and edges. Previous Homomorphism Networks are equivalent to one-layer DHNs. The authors extend known results about the homomorphism expressivity of these networks, demonstrating that DHNs can count a broader range of homomorphisms. This lays the foundation for quantitative expressivity results.", "questions": "- What is the predictive performance of DHNs on real-world tasks? Are explicit subgraph/homomorphism counts optimal for these tasks?\n- There is one related work [Paolino, Raffaele, et al. \"Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning.\" arXiv preprint arXiv:2403.13749 (2024).], and I believe the relation could be really interesting. Paolino et al. only consider injective homomorphism, while their color refinement algorithm is more complex in the sense that representations for the homomorphism are calculated. If I understand correctly DHNs can homomorphism count exactly cactus graphs (with limited cycle length) if the patterns contain cycles. Could you discuss the relationship?\n- For which classes of patterns is the homomorphism-expressivity maximal in the sense that the set of patterns that DHNs can count is maximal. See also \n- Why focus on feature homomorphisms? This approach seems more restrictive and domain-dependent, requiring prior knowledge of the existence of these featured patterns. When is it better to focus on feature homomorphisms versus general homomorphisms?\nwhy are the graphs $G_1$ and $G_2$ in Theorem 5.3 rooted?\n- The authors mention very shortly the continuity wrt BS distance. However, it's not clear why this is desirable. While it leads to learnability one can derive learnability also without it. At the same time, it strictly limits its expressivity as discussed in Remark 5.14.: Is continuity desirable? If yes, can you show that DHNs can approximate non-continuous graph invariants like biconnectivity?", "limitations": "It would be beneficial to add that the predictive performance is unclear. Also domain-knowledge might be needed to not worsen generalization performance/predictive performance.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The construction of DHNs is elegant, effectively generalizing standard MPNNs and other homomorphism networks.\n- The theoretical contributions are interesting, intuitive, and non-trivial, providing a solid foundation for further research on the expressivity of GNNs.", "weaknesses": "- The paper lacks evidence of improved predictive performance on real-world tasks. While the theoretical contributions are valuable, it is unclear in which real-world tasks DHNs would be advantageous. Clarification/Ablations on whether domain knowledge is necessary to predefine patterns and whether including irrelevant patterns can harm predictive performance would be beneficial.\n- The computational complexity of DHNs is not convincingly addressed (as a limitation). For example, 3-WL has cubic complexity and can count homomorphisms of all graphs with tree-width 2 at this complexity. DHNs are less expressive unless patterns include graphs with tree-width 3 or higher. Therefore, to surpass 3-WL, DHNs must match or exceed its complexity. The advantages of DHNs over 3-WL or its local variants, like subgraph GNN or local 2-FWL, need to be clearly stated.\n- The motivation for using labeled patterns is unclear, as this adds complexity and increases the need for domain knowledge. The benefits of using labeled patterns over blank patterns without features must be better explained.\n\n\nMinor: \n- Some proofs could be more detailed. For instance, in Theorem 5.3, item 2 to item 3 is not clearly justified. The proof shows that there exists a function $h$ that satisfies $h(u)=hom((F, \\mu), (G^u, x))$ for every $u$ and a fixed graph $G$. If the construction of $h$ depends on the graph, this is not sufficient for the proof. More clarity and detail in this and other proofs would strengthen the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the thoughtful review and comments.\n\n# Questions\n\n- **[Q1]** Since real-world dataset comments are common among all reviewers, please refer to our global rebuttal.\n\n- **[Q2]** Thank you very much for giving us a pointer to (Paolino et al., 2024); we will cite and discuss the relationship in the updated related work. Their model is a special case of ours with patterns $\\\\{C_k: k = 1, \\ldots, r \\\\}$. Hence, ours can also count cactus graphs of bounded cycle length using these patterns. One important difference is that they used a permutation-invariant aggregation on cycles (Eq (3)); thus, they cannot distinguish two cycles of the same set of features that are ordered differently (e.g., $[a,a,b,b]$ vs $[a,b,a,b']$), while ours can.\n\n- **[Q3]** [Note: Please let us know if we misunderstood your question (since we don't see after \"See also\")]. In general, it's difficult to answer. A theoretically correct answer (but not very related to DHN) is that the set of all graphs of size at most n is maximally expressive since it determines the isomorphism class of graphs of size at most n. Finding smaller but isomorphism-characterising patterns is a central research question in the field of homomorphism distinguishability; see (Dvorak, 2010) and (Roberson, 2022).\n\n- **[Q4]** Could you elaborate on \"general homomorphisms\" and \"feature homomorphisms\" in this question? We might misunderstand your question. It is true that the method requires some domain knowledge about what patterns are useful. However, we believe it is better than the classical graph learning approach in which we have hand-crafted subgraph patterns as we need to take a larger but tractable set and ask DHN to learn the important patterns (this might be similar to classical hand-crafted features in computer vision versus CNN). Our model is more restrictive than those with higher expressive power (e.g., k-WL equivalent models). However, the non-restrictive are expensive (say, O(n^k)) and not applicable to large graphs. In this sense, we are restricting our model to satisfy the needs of computational complexity. \n\n  - Graphs G1 and G2 in Theorem 5.3 are rooted because we consistently work on rooted graphs for technical reasons. Please refer to our rebuttal **[Q1-minor]** to reviewer X5N6. Note that it is easy to derive the result from the rooted version to the non-rooted version because the non-rooted version can be stated as \"there is a bijection pi from $V(G_1)$ to $V(G_2)$ such that each pair of graphs $G_1^u$ and $G_2^{\\pi(u)}$ rooted by $u$ and $\\pi(u)$ are equivalent\"\n\n- **[Q5]** First, DHN (or any BS-continuous GNNs) cannot approximate the biconnectivity of all graphs because there exists a pair of graphs $G, G'$ such that they're arbitrarily close in the BS topology but have different biconnectivity so the model fails to predict the biconnectivity of $G$ or $G'$. Models that can approximate biconnectivity must be non-continuous in the BS topology. Intuitively, if a function f is BS-continuous, $G$ is large, and $G'$ is a snowball sampling of $G$, then $f(G)$ and $f(G')$ are close (see Czumaj 2019). It is useful in large graph applications: We want to estimate a property on a large graph (e.g., Twitter networks) but only have a small sample $G'$. Here, the BS continuity guarantees that $f(G')$ approximates $f(G)$. If we use a non-continuous model, we have to discuss the validity of estimating $f(G)$ from $f(G')$, which is usually non-trivial. In this sense, ours is useful in large graph applications but loses the approximability of non-continuous properties. In contrast, the non-continuous one is useful in small graphs but loses the generic applicability in large graphs. We will add the above-mentioned intuition of BS continuity and the reasoning why it is useful. This discussion is not specific to our DHN model, but it clarifies why we consider BS continuity, which improves the readability of the manuscript.\n\n# Weaknesses\n- **[W1]** Thank you for pointing out the necessity of some intuitions on real-world datasets. We quickly added some experiments in the global rebuttal and will update our manuscript following your comment.\n\n- **[W2]** In terms of patterns, DHN captures \"locally complex but globally tree (i.e., treewidth = 1)\" patterns, while k-FWL (or (k+1)-WL)-equivalent models capture \"globally tree-like (i.e., treewidth = k)\" patterns. Therefore, they are essentially incomparable (one cannot surpass the other). We expand line 35 and add a Remark after the Corollaries to state when the proposed method is better than k-WL-type methods in such applications.\n\n- **[W3]** Here, we interpret the term \"labelled pattern\" as the patterns with functions. Please let us know if our understanding is wrong. First, how to aggregate node features over patterns without functions needs more exploration. A simple idea is to multiply the feature values in each coordinate and sum them up. This gives the weighted homomorphisms on each coordinate. However, adding/multiplying raw features might not necessarily make sense to us (although many papers are doing so), and it has a mathematical issue, as mentioned by Reviewer AtgF. Hence, we decided to apply functions to features. Second, in practical applications, the importance of nodes in patterns might differ (e.g., nodes closer to the root could be more important). Thus, we decided to use node-dependent functions.\n\n- **[W4]** We will improve our presentation of the proofs.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gO4IROskTw", "reviewer": "Reviewer_AtgF", "summary": "The authors propose a deep graph learning architecture where each layer consists of two key components: (i) the computation of homomorphism count vectors relative to a set of graph patterns, and (ii) a subsequent non-linear transformation. The homomorphisms computed in a layer incorporate features from the previous layer. Within this framework, the authors examine its expressive power, providing a characterization in terms of a variant of Weisfeiler-Leman and homomorphism indistinguishability related to an expanded set of graph patterns. Additionally, a brief section discusses the architecture's continuity properties and \nuniversality. Preliminary experimental results are also presented.", "questions": "I would appreciate it if the authors could respond to the weak points **W1**, **W2** and **W5**.", "limitations": "This has been addressed in a satisfactory way by the authors.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "**S1 Architecture** \nThe proposed architecture generalizes standard MPNNs while enhancing their expressive power. Furthermore, by incorporating different graph patterns in each layer, it extends the approach taken by Barceló et al. [4], resulting in a significant increase in expressive power. The elegant idea involves combining the computation of weighted homomorphism counts of patterns in each layer, treating the host graph as being augmented with features computed from previous layers.\n\n**S2 Versatility**\nBy appropriately selecting graph patterns, the proposed architecture demonstrates exceptional flexibility in capturing various kinds of subgraph information.\n\n**S3 Analysis**\nTheorem 5.3 is a notable result, clearly illustrating the expressive power of the proposed method.\n\n**S4 Theoretical Connections**\nTo provide insights into the properties of the proposed architecture, the authors leverage a wide range of theoretical results and connect their work to recent developments in the field.", "weaknesses": "**W1 Incorrect statement** Unless there is a misunderstanding, Theorem 3.3 is known **not to be true**. That is, the classical result relating isomorphisms and hom counts is known not to generalize to weighted graphs. A recent reference for this is https://arxiv.org/pdf/2308.15283 (but this was observed before). \n\n*W1 has been dispelled by the authors due to a misunderstanding of my part*\n\n**W2 Imprecise formalizations**\n- When defining the notion of generalized homomorphism, it is worth pointing out that this is not a new concept. Weighted homomorphisms have been studied before. Now, the definition on page 4 is not very clear: \nYou mention “continuous” but with respect to which topology? The input and output of the functions $\\mu_p$ only becomes clear later on. Please define this more precisely. I also understand that $\\mu_p$ maps into a $d$-dimensional space. What is the product in this space? You use this in equation (3) without explaining how to multiply two vectors. I assume you use Hadamard (pointwise) product?\n\n- In section 4.1., and in particular in the crucial definition Equation (5) of a homomorphism layer, you use $h$ without saying what it is. Please make this more clear.\n\n- Example 4.1 is hard to decipher. What is $\\circ$ in $x_{\\pi(\\circ)}$ in Equation (6)? I was expecting a product in Equation (7) since the graph pattern has two vertices? I am also not sure what is going on l193. What are these sets $\\mu$? Since this example is supposed to illustrate your main architecture, this should be clear and consistent with the introduced notation and definitions.\n\n- In the definition of your version of WL, in Equation (11), shouldn’t the homomorphisms $\\pi$ used also take colors from previous iterations into account?\n\n**W3 Universality**\nThe results about universality in Section 5.3 are of less interest, since no quantitative bounds are given about the size of networks needed to approximate any function to arbitrary precision. Furthermore, the topology used needs more motivation and explanation.\n\n**W4 Heavy reliance on results in theoretical CS**\nMany of the theoretical results and observations are heavily influenced (and are oftentimes restated versions of) results known in the literature. An example is section 4.2, but also many proofs are close to existing ones. Similarly, the results in section 5.2 all rather easily follow from recent advances in TCS, especially from the work of Roberson et al, and from previous work in the ML community.\n\n**W5 Experiments**\nThe experiments appear very preliminary and do not give much insight into how much the flexibility of the proposed architecture is needed to obtain good accuracy. Indeed a very limited number of patterns and two layers suffice? Also, it is unclear why the number of parameters varies when changing graph patterns? It would make a more fair comparison if parameters were fixed? Also, there is no comparison with the work by Barceló et al and NT and al, which served as the motivation for the current paper. What is the reason for this?\n\n**W6 Unclear sentences** \n- L38 “for a common choice” what do you mean by this?\n- L87 “expressive power is .... exponential in the number of GNN layers” it is unclear what it means for the expressive power to be exponential in something.\n- Figure 1 should be improved. It is unclear what is going on in this figure at this point in the paper.\n- L125 “although sacrificing invariance ...” Why would you want to consider functions that can distinguish isomorphic graphs? This would indicate that you want to learn something depending on the specific encoding of the graphs?\n- L196-L198: It is unclear what these sentences intend to convey (even after consulting the appendix).\n- L202 and onwards, you mention that your model is an algebra. Please detail what you mean by this and why this is important (e.g., universality).\n\n**W7 Minor comments** \n- L141 The results in Dell et al was previously shown in “On recognizing graphs by numbers of homomorphisms” by Z. Dvořák.\n- L146 Why does $\\phi^{(\\star)}$ need to be permutation invariant. It is defined as function which takes a multiset as input so it is permutation invariant by definition?\n- L149 “We can prove”-> “One can prove” (since it is already shown by others)\n- L152 “where $\\cal T$ is the set of all trees” -> Should be removed here I assume?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reading our manuscript. In particular, we are pleased to have a review from a specialist of homomorphisms. Below, we address your questions and comments. Especially, we claim our Theorem 3.3 is correct (**[W1]**) because of our definition of generalised homomorphism. Since all your major concerns (W1, W2, and W5) all related to the definition of our generalized homomorphism, we hope our answer clarifies your concern and you will reconsider the evaluation of our work.\n\n# Questions\n\n**[W1]** As you mentioned, **weighted** graph homomorphisms can only distinguish weighted graphs without twins (https://arxiv.org/abs/1909.03693). However, our **generalised** homomorphism circumvents this issue by introducing non-linear transformations $\\mu$ on node features. For instance, Example 4 in your reference is distinguished by setting $\\mu_p(x) = 1$ for all $p$ and $x$. This transformation gives the homomorphism number of the underlying unweighted graphs so it detects the isomorphism of the underlying graph.\n\nThe proof of this theorem is in the Appendix. The key point is that our generalised homomorphism can count the graphs-with-features's homomorphisms (i.e., mappings that preserve the adjacency and feature values) by suitably choosing non-linear transformations (say, $\\mu_p(x) = 1[x = a_p]$ for the relation that node $p$ has a feature $a_p$.). This observation with the classical Lovasz theorem for general relational structure (https://www.cs.elte.hu/~lovasz/scans/opstruct.pdf) proves the theorem. \n\n**[W2]**\n\n> When defining the notion of generalized homomorphism, it is worth pointing out that this is not a new concept.\n\nWeighted homomorphism is a classical concept, but we believe our version that applies non-linear transformation is new, and it is best-suited for GNNs. One significant difference between weighted and our generalised appeared in Theorem 3.3 above.\n\n---\n> In section 4.1., and in particular in the crucial definition Equation (5) of a homomorphism layer, you use h without saying what it is.\n\nIt's the node feature of $G$ as we wrote as $(G^u, h)$. We will add this clarification in the updated manuscript.\n\n---\n\n> Example 4.1 is hard to decipher.\n\nSorry for the imprecise presentation. The right-hand side of Eq (7) is by definition $\\sum_{v \\in N(u)} \\mu_\\bullet(x_u) \\mu_\\circ(x_v)$. In line 193, what we wanted to convey was:\n\n- For a single-node pattern (node: $\\bullet$), $\\mu_\\bullet(x)$ is arbitrary\n- For a two-node pattern (nodes: $\\bullet$ and $\\circ$), $\\mu_\\bullet(x) = 1$ and $\\mu_\\circ$ is arbitrary.\n\nThis shows Eq (6) and (7). We update this part as the above.\n\n---\n> shouldn’t the homomorphisms $\\pi$ used also take colors from previous iterations into account?\n\nIt takes colours from previous iterations into account, since it aggregates the colour of node $\\pi(p)$ at k-th step. We might have misunderstood your question, so please elaborate.\n\n**[W5]** Please refer to the global rebuttal for a general remark about the real-world dataset experiment. About the number of parameters, our model has transformation $\\mu = \\\\{ \\mu_p : p \\in V(F) \\\\}$ on each node in each pattern. We implement them as neural networks. Therefore, the number of parameters is basically the number of patterns times the number of parameters in each neural network.\n\n# Weaknesses\n\n**[W3]** In principle, we agree the universality/BS-continuity doesn't add much value. But, we think it's an important property, esp., in the large graph applications. Also, it gives a brief comparison with the Zhang 2023's seminal model that captures the bi-connectivity (ICLR'23 outstanding paper) as \"ours is continuous, theirs is not\". See also **2WsS [Q5]**.\n\n**[W4]** We also, in principle, agree that our theorems are easily followed from the TCS results. However, our goal here is not to prove new TCS results, but is to state the relationship between the GNN architecture (layer-wise aggregation) and the expressive power of the model (pattern graphs for hom) to extend the GNN expressive power study, and suggests a generic framework how to build a GNN architecture suitable for tasks.\n\n**[W6]** We revise our manuscript to clarify all the points raised here.\n\n> L38\n\nThis means \"Several existing GNN papers used such architectures.\" \n\n> L87 \n\nWe identify the expressive power as the set of captured patterns. In this sense, this means \"k layer GNN can count patterns in $F^0 \\cup ... \\cup F^k$ (having k-th power in terms of the rooted products)\" as \"exponential in k\". The numbers of the patterns is also exponential in k (by assuming |F| = O(1)). \n\n> Figure 1\n\nWe updated Figure 1 to clarify the meaning.\n\n> L125 \n\nWe **don't want** to consider functions that can distinguish isomorphic graphs; it is clearly written as \"we stay with invariant functions as it is a natural requirement to represent graph properties\" in the same paragraph. This is just a note that some existing studies claiming higher expressive power are sacrificing invariance. So our is incomparable with them as we/they are studying different classes of functions.\n\n> L196-L198\n\nWe wanted to say DHN is a very wide class of GNN that aggregates local information, i.e., (1) we think Eq (9) is the most generic GNN that aggregates information locally, and (2) it is expressible in DHN. \n\n> L202\n\nThanks. As you pointed out, it is important in the proof of the universality. We will update our manuscript accordingly.\n\n> L141\n\nThank you very much for pointing out the right reference. \n\n> L146\n\nYou are mathematically correct. This is just to emphasize the permutation invariance of the function, just be sure. Note that several GNN papers (e.g., Xu et a 2019 https://arxiv.org/abs/1810.00826) also mentioned a function is permutation-invariant even though it takes a multiset as an argument.\n\n> L149\n> L152\n\nWe will update them accordingly.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
First, we thank all three reviewers for their time and detailed comments on our work. Given the submission volume in our community, we are truly grateful that all three reviewers have clearly given our manuscript deep consideration.

In this global rebuttal, we would like to address a common concern from all reviewers regarding real-world experimental results. 

**Experimental result on ENZYMES and PROTEINS**. We run some representative DHN models on TUDataset's ENZYMES and PROTEINS datasets. These bioinformatic datasets are cast as graph classification problems. ENZYMES consists of 600 graphs and 6 classes; each node has 3 tags and 18 features. PROTEINS dataset consists of 1113 graphs belonging to 2 classes; each node has 3 tags and 1 feature. We report the classification accuracy using a stratified 10-fold cross-validation method similar to the literature. We will update Table 1 in the manuscript as follows. 

| Model               | #params | CSL | EXP | SR25 | ENZYMES      | PROTEINS    |
|---------------------|---------|-----|-----|------|--------------|-------------|
| MPNN (4 layers)     | 27k     | 0   | 0   | 0    | 54.6 ± 4.5   | 72.0 ± 4.0  |
| PPGN (4 layers)     | 96k     | 100 | 100 | 100  | 58.2 ± 5.7   | 77.2 ± 3.7  |
| DHN (C2:4)          | 5k      | 100 | 50  | 0    | 64.3 ± 5.5 | 76.5 ± 3.0 |
| DHN (C2:10)         | 27k     | 100 | 98  | 0    | 58.0 ± 5.3 | 78.5 ± 2.5 | 
| DHN (C2:4, C2)      | 8k      | 100 | 50  | 53   | 64.4 ± 5.9 | 77.1 ± 2.8 | 
| DHN (C2K3:5, C2K3:5)  | 36k     | 100 | 100 | 100  | 57.5 ± 6.6   | 77.4 ± 3.4 |

Note that the SOTA result for ENZYMES is around 78%, and for PROTEINS, it is around 84%. However, we do not intend to compete with the SOTA results in this work. 

The result above emphasizes the necessity of specific considerations for each real-world dataset. The expressivity experiments (CSL, EXP, SR25) clearly distinguish each architecture; however, real-world dataset results are often comparable among different architectures. Achieving SOTA might be attributed to engineering efforts rather than novel model architecture.

The lack of real-world benchmarks is indeed a shortcoming of our current manuscript. Our work aims to focus on the method's theoretical foundation and novelty, so we did not put much effort into experimentation except for the synthetic expressivity datasets. While our model performed well compared to basic baselines, it is still quite far from SOTA result due to the lack of engineering. For example, the SOTA model for ENZYMES (DSGCN-allfeat) computes the spectrum for each graph, which is highly engineered toward this particular dataset. It is clear that there is a gap between our theoretical proof of concept model and a truly applicable one, and we think there is potential. Still, more engineering work is needed before we can bridge the theory-practice gap. That being said, based on the reviewers' comments, we understand that readers have some expectations for real-world benchmarks, so we will include some results for a subset of the graph classification TUDataset in the final version of the manuscript.

Meta-review: The paper proposes a new graph neural network (GNN) layer based on local subgraph patterns using homomorphisms. This yields a GNN that can be used to study the expressive power of GNNs that locally aggregate information. The relationships to existing works are well explained.

The paper received three very detailed reviews. All reviewers participated in the discussion and recommend to accept the paper. 

They mentioned the missing consideration of real-world datasets as one main weakness of this work. The authors provided such results in the rebuttal but obtained only decent performance. I consider closing these gaps as challenge for future research.

Overall, I recommend to accept the paper.
Decision: Accept (poster)