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.

Questions

[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.

The 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.

[W2]

When defining the notion of generalized homomorphism, it is worth pointing out that this is not a new concept.

Weighted 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.

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.

It's the node feature of $G$ as we wrote as $(G^u, h)$. We will add this clarification in the updated manuscript.

Example 4.1 is hard to decipher.

Sorry 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:

• For a single-node pattern (node: $\bullet$), $\mu_\bullet(x)$ is arbitrary
• For a two-node pattern (nodes: $\bullet$ and $\circ$), $\mu_\bullet(x) = 1$ and $\mu_\circ$ is arbitrary.

This shows Eq (6) and (7). We update this part as the above.

shouldn’t the homomorphisms $\pi$ used also take colors from previous iterations into account?

It 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.

[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.

Weaknesses

[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].

[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.

[W6] We revise our manuscript to clarify all the points raised here.

L38

This means "Several existing GNN papers used such architectures."

L87

We 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)).

Figure 1

We updated Figure 1 to clarify the meaning.

L125

We 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.

L196-L198

We 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.

L202

Thanks. As you pointed out, it is important in the proof of the universality. We will update our manuscript accordingly.

L141

Thank you very much for pointing out the right reference.

L146

You 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.

L149 L152

We will update them accordingly.

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.

Weakness

(W1) The presentation of the paper could be improved

graph rooted product around Lemma 3.1

We'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.

Some other parts could be improved as well by either giving better intuitions or by providing additional visual support.

We will add illustrations to Lemma 3.1 and Hierarchy of Corollaries.

The 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.

(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.

(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.

Questions

(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.

Note 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.

(Q2 - minor) We'll fix this.

(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.

(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.

(Q5) The singleton is included by the definition of the closure (0-th power is the singleton); see line 237.

(Q6) No, we meant k-WL original version.

(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.

Thank you very much for the thoughtful review and comments.

Questions

• [Q1] Since real-world dataset comments are common among all reviewers, please refer to our global rebuttal.

• [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.

• [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).

• [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.

  • 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"

• [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.

Weaknesses

• [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.

• [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.

• [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.

• [W4] We will improve our presentation of the proofs.