Homomorphism Expressivity of Spectral Invariant Graph Neural Networks
Authors: Jingchu Gai
Yiheng Du
Bohang Zhang
Haggai Maron
Liwei Wang
Venue: ICLR 2025 Oral (2025)
Keywords: Graph Neural Network
Expressive Power
Spectral Invariant
Graph Homomorphism
Weisfeiler-Lehman
Primary area: learning on graphs and other geometries & topologies
TL;DR: We analyze the expressive power of spectral invariant graph neural networks from the perspective of graph homomorphisms.

Abstract: Graph spectra are an important class of structural features on graphs that have shown promising results in enhancing Graph Neural Networks (GNNs). Despite their widespread practical use, the theoretical understanding of the power of spectral invariants --- particularly their contribution to GNNs --- remains incomplete. In this paper, we address this fundamental question through the lens of homomorphism expressivity, providing a comprehensive and quantitative analysis of the expressive power of spectral invariants. Specifically, we prove that spectral invariant GNNs can homomorphism-count exactly a class of specific tree-like graphs which we refer to as \emph{parallel trees}. We highlight the significance of this result in various contexts, including establishing a quantitative expressiveness hierarchy across different architectural variants, offering insights into the impact of GNN depth, and understanding the subgraph counting capabilities of spectral invariant GNNs. In particular, our results significantly extend \citet{arvind2024hierarchy} and settle their open questions. Finally, we generalize our analysis to higher-order GNNs and answer an open question raised by \citet{zhang2024expressive}.

Published as a conference paper at ICLR 2025
HOMOMORPHISM EXPRESSIVITY OF SPECTRAL IN- VARIANT GRAPH NEURAL NETWORKS
Jingchu Gai
Yiheng Du
Bohang Zhang'* Haggai Maron 2,3 Liwei Wang'
Peeknng University TTchhioo "NVIDIA Rescarch
gai ji ngchu@stu. pk..puu..uuu..... cn, zhangbohang@pko. edu.cn, buyihang@stu.pku hma imarcn@nvi aia. com, wangl whnplll@pku..ccco
ABSTRACT
Graph spectra are an important class of structural features on graphs that have shown promising results in enhancing Graph Neural Networks (GNNs). Despite their widespread practical use, the thcoretical understanding of the power of spec- tral invariants - particularly their contribution to GNNs remains incomplete. In this paper, we address this fundamental question through the lens of homomor- phism expressivity, providing a comprehensive and quantitative analysis the expressive power of spectral invariants. Specifically, we prove that spectral invari- exactly a class of specific tree-like graphs which we refer to as parallel trees. We highlight the significance of this result in various contexts, including establishing a quantitative expressiveness hierarchy across different architectural variants, offering insights into the impact of GNN depth, and understanding the subgraph counting capabilities of spectral invariant GNNs. In particular, our results significantly extend Arvind al. (2024) and tle their open questions. Finally, we generalize our analysis to higher-order GNNs and answer an open question raised by Zhang et al. (2024b).
ant GNNs can homomorphism-comme
INTRODUCTION
The graph spectrum, defined as the eigenvalues of graph matrix, is an important class of graph invariants. encapsulates rich graph structural information including the graph connectivity, bi- partiteness, node clustering patterns, diameter, and more (Brouwer & Haemers, 2011). Besides eigenvalues, generalized spectral information may also include projection matrices, which further encodes node relations such as distances and random walk properties, enabling the definition of more fine tine-graied graph invariants (Fürer, 2010). These spectral invariants possesses strong expres- sive power. For example, well-known conjecture raised by Van Dam & Haemers (2003); Haemers & Spence (2004) claimed that almost all graphs can be uniquely determined by their spectra up to isomorphism. The rare exceptions, known cospectral graphs, tend to be highly similar in their structure and continue to be an active area of research in graph theory (Lorenzen, 2022).
In the machine learning community, spectral invariants have recently gained increasing popularity in designing Graph Neural Networks (GNNs) (Bruna et al., 2013; Defferrard et al., 2016; Lim et al., 2023; Huang al., 2024; Feldman al., 2023; Zhang et al., 2024b; Black al., 2024), owing to several reasons. From a practical perspective. graph spectra have been shown to be closely related certain practical applications such as molecular property prediction (Bonchev, 2018). Moreover, a recent line of works (Xu et al., 2019; Morris et al., 2019; Li et al., 2020; Chen et al., 2020: Zhang al., 2023b) has pointed out that the expressive power of classic message-pant paaaggg GNNs (MPNNs) are inherently limited, and cannot encode important graph structure like connectivity or distance. Incorporating spectral invariants into the design of MPNNs can naturally alleviate the limitations.
Therefore, from both theoretical and practical perspectives, it is beneficial to give a systematic un- derstanding of the power of spectral invariants and their corresponding GNNs. The earliest study in this area may be traced back to Fürer (2010), who first linked the power of several spectral invariants test (Weisfeiler & Lehman, 1968) by proving that these invariants
to the classic Weisfeiler-Lehmie upper bounded by 2-FWL. More recently, Rattan & Seppelt (2023) further revealed a strict
PPooecc lead.

---

Published as a conference paper at ICLR 2025
expressivity gap between Fürer's spectral invariants and 2-FWL. Zhang et al. (2024b) and Arvind et al. (2024) analyzed refinement-based spectral invariants, which offer insights into the power of real GNN architectures. Yet, all of these works study expressiveness through the lens of Weisfeiler- Lehman tests, which has inherent limitations. So far, there remains a lack of comprehensive under- standing of the practical power of spectral invariants and their corresponding GNN architectures.
Current work. In this paper, we investigate the aforementioned questions via a novel perspective called graph homomorphism. Specifically, Zhang et al. (2024a) recently proposed homomorphism expressivity as a quantitative framework to better understand the expressive power of various GNN architectures. As homomorphism expressivity is fine-grained and practical measure, it naturally addresses several limitations of the WL test. However, extending this framework to other archi- tectures, such as spectral invariant GNNs, poses significant challenges. In fact, whether homomor- phism expressivity exists for a given architecture remains an open research direction (see Zhang et al. (2024a)). In our context, this problem becomes even challenging since homomorphism and spectral invariants correspond to two orthogonal branches in graph theory. Here, we provide affir- mative answers to all these questions by formally proving that the homomorphism expressivity for spectral invariant GNNs exists and can be elegantly characterized (Theorem 3.3). This offers deep insights into a series of previous studies, extending their results and answering several open questions. We summarize our results below:
special class of parallel trees
Separation power of spectral invariants/GNNSs We offer a new proof that projection-based spectral invariants and corresponding GNNs are strictly bounded by 2-FWL (Corollary 3.4). Moreover, we establish quantitative hierarchy among raw spectra information, projection, refinement-based spectral invariant, and various combinatorial variants of WL tests (see Fig- ure 4). This (i) recovers and extends results Rattan Seppelt (2023), and (ii) provides clear insights into the hierarchy established in Zhang al. (2024b).
The power of refinement. We offer a systematic understanding of the role of refinement in spectral invariant GNNs. We show increasing the number of iterations always leads to strict improvement in expressive power (Corollary 3.1 thus settling a key open question raised in Arvind et al. (2024). Morcover, our counterexamples establish a tight lower bound on the number of iterations required to achieve maximal expressivity, which is in the same order of graph size. This advances a line of research regarding iteration numbers in WL tests (Fürer, 2001; Kiefer & Schweitzer, 2016; Lichter et al., 2019).
Substructure counting power of spectral invariants/GNNs. On the practical side, we pre- cisely characterize the power of spectral invariants/GNNS in counting certain subgraphs as well as the required iterations. For example, they count all cycles within 7 vertices, while using itcration already suffices to count all cycles within 6 vertices (Corollary 3.15).
Empirically, a set of experiments on both synthetic and real-world tasks validate our theoretical results, showing that the homomorphism expressivity of spectral invariant GNNs well reflects their performance in down-stream tasks.
PRELIMINARIES
Notations. We use } and Hf } to denote sets and multisets, respectively. The cardinality of given (multi)set S' is denoted as SS. In this paper, we consider finite, undirected, simple graphs with no self-loops or repeated edges, and without loss of generality we only consider connected graphs. Let G = (Va, be a graph with vertex set VG and edge set Eg, where each edge in EG is a set {u, w) C VG of cardinality two, The neighbors of vertex u denoted as No(u) := {u E Valku, o} E Eg). A walk of length k is a sequence of vertices up. uo. Uu E VG such that {w,-1, u.] E Eg for all [k). It is further called a path if u, # u, for all < j. and it is called a cycle if up. -1- is a path and uo = ut.. The shortest path distance between two nodes u, v E VG, denoted as dis (u, v). is the minimum length of walk from u to v. A graph F= (Vr, EF) is a subgraph of G if VF C Va and EF C Eg. We use P. (resp. C,)) to denote graph corresponding to a path (resp. cycle) of n vertices. A graph is called a tree if is connected and contains cycle of a rooted tree I" is defined as dep(T")) = max,ev, disr (r, u), and the depth of T is defined as dep(T) min,ev, dep(T").
subgraph. We denote by T" the rooted tree T with root r. The depth
2

---

Published as a conference paper at ICLR 2025
2.1 SPECTRAL INVARIANT GNNS
Let G be graph of n. vertices where Va = [n], and denote by A E [0, the adjacency matrix of G. The spectrum of G is defined as the multiset of all eigenvalues of A. In addition to cigenvalues, cigenspaces also provide important spectral information. Formally, the eigenspace associated with some eigenvalue can be characterized by its projection matrix Px. It follows that there exist a unique set of orthogonal projection matrices { {PA)AEA where A is the set of all distinct eigenvalues of A, such that A = Σxe XPx, and the following conditions hold: Σx Px I, PxPx- 0 for + X, and AP, A for all À E A. Combining the projection matrices with the associated eigenvalues naturally define an invariant between node pairs, which we denote by P:
P(u, v) == (A, (u e)) E AB for u, E VG.
Then, one can define the so-called "spectral invariant" of graph as follows. Consider the following color refinement process by treating P(u, 2) as the edge feature between vertices and e::
(pec,(d+1) (u) = hash (xG XG
Spec,(d) (v)) P(u, u))lo E Vo.B for u E Vo, N+ (dec, (u), (0)):((. (xG
Spec.(0) (u) (u E Va) are constant in initialization, and hash is perfect hash (pec.(d) induces an equivalence relation over vertex set function. For each iteration d, the mapping XG
where all colors XG
VG, and the relation gets refined with the increase of d. Therefore, with sufficiently large number Sppet
of iterations d S |Va| the relations get stable. The spectral invariant XG
(G) is then defined to Spec.(d) (G) to be the multiset of node (1) (G) is exactly the Fürer's
be the multiset of stable node colors. We can similarly define XG colors after d iterations (Arvind et al., 2024). We remark that XG (weak) spectral invariant proposed in Fürer (2010).
Owing to the relation between GNNs and color refinement algorithms, one can easily transform the above refinement process into GNN architecture by replacing hash function with continuous, non-linear, parameterized function, while maintaining the same expressive power (Xu et al., 2019; Morris al., 2019). We call the resulting architecture Spectral Invariant GNNs (see Zhang et al. (2024b) for concrete implementations of spectral invariant GNN layer). Without ambiguity, we may (dec.(d) (G) the graph representation computed by d-layer spectral invariant GNN. also refer XG
2.2 HOMOMORPHISM EXPRESSIVITY
Given two graphs F and G. homomorphism from F to G is a mapping f VF - VG that preserves edge relations, i.e., { ff)..(()) E EG for all {u. ta E Ep. We denote by Hom (, G) the set of all homomorphisms from F to G' and define hom(F, G) |omm(F, G)), which counts the number of homomorphisms. If is further surjective on both vertices and edges of G, we call G a homomorphic image of F, A mapping f: Vr VG is called isomorphism if f is bijection and both f and its inverse f-i are homomorphisms. We denote by sub(F, G) the number of subgraphs of G that is isomorphic F.
In Zhang et al. (2024a), the authors introduced the concept the homomorphism expressivity to quan- tify the expressive power of a color refinement algorithm (or GNN). is formally defined as follows:
Definition 2.1. Let M be a color refinement algorithm (or GNN) that outputs graph invariant XG
M (G) given graph G. The homomorphism expressivity of M, denoted by JrM is a family of
connected graphs' satisfying the following conditions:
For any two graphs G, H, xa (G) =M (H) iff' hom(F, G) hom(F, H) for all F E FM; b) J-M is maximal, i.e., for any connected graph F & JMM there exists pair of graphs G, H such that xa (G) = Xf (H) and hom G) A hom H)).
By characterizing the set J for different GNN models M, one can quantitatively understand the expressivity gap between two models by simply computing their set inclusion relation and set differ- ence. Zhang et al. (2024a) examines several representative GNNs under this framework, including
'For simplicity, we focus connected graphs in this paper. The results can be easily generalized to dis- connected graphs following Seppelt (2024).
3

---

Published as a conference paper at ICLR 2025
(a) A parallel edge with endpoints (u, v) Figure I: Illustration of parallel edge with endpoints (u,v) v) in (a) and parallel tree with its skeleton on the right in (b).
(b) An example of parallel tree and its tree skeleton
the standard MPNNS and Folklore GNNs (Maron et al., 2019; Azizian Lelarge, 2021). and recent architectures such as Subgraph GNN (Bevilacqua et al., 2022: Qian et al., 2022; Cotta et al., 2021) and Local GNN (Morris et al., 2020; Zhang et al., 2023a). However, one implicit challenge not reflected in Definition 2. (a) is that the set F may not even exist for a general GNN M. Proving existence corresponds to an involved research topic known as homomorphism distinguishing closedness (Roberson, 2022: Seppelt, 2024; Neuen, 2023), which is highly non-trivial. In the next section, we will give affirmative results showing that the homomorphism expressivity of spectral invariant GNNs does exist and give elegant description of the graph family.
3 HOMOMORPHISM EXPRESSIVITY OF SPECTRAL INVARIANT GNNs
In this section, we investigate the homomorphism expressivity of spectral invariants and the cor- responding GNNs. We will provide a complete characterization of the set (d) for arbitrary model depth d E {2o). This allows us to analyze spectral invariants in a novel perspective, significantly extending prior research and resolving previously unanswered questions.
3.1
MAIN RESULTS
Our idea is motivated by the previous finding that the homomorphism expressivity of MPNNs is exactly the family of all trees (Zhang et al., 2024a). Note that in the definition of spectral invariant GNN, if one replaces P(u, u) by the standard adjacency Auv. the resulting architecture just an MPNN. Such relationship perhaps implies that the homomorphism expressivity of spectral invari- ant GNNs also comprises "tree-like" graphs. We will show this indeed true. To present our results, 1et us define special class of graphs, referred to as parallel trees:
Definition 3.1 (Parallel Edge). A graph G is called a parallel edge if there exist two different vertices u, u E VG such that the edge set EG can be partitioned into sequence simple paths Pl,..., Pm m. where all paths share endpoints (u, v). We refer to (u, v) the endpoints of G.
Definition 3.2 (Parallel Tree). graph F called parallel tree if there exists can be obtained from T by replacing each edge {u, d) E Er with parallel edge that has endpoints {u, v). We refer T as the parallel tree skeleton of graph F. Given a parallel tree F, define the parallel tree depth of F as the minimum depth of any parallel tree skeleton of F.
T such that F
We give an illustration of parallel edge and parallel tree in Figure 1. With the above definitions, we are ready to state our main theorem:
Theorem 3.3. For any N, the homomorphism expressivity of spectral invariant GNNs with d iterations exists and can be characterized as follows:
SSpec,(d) = {F| F has parallel tree depth at most d}.
Specifically, the following properties hold:
Spec,(d) Spec,(d) (G) XH (H) () if and only if. for all connected graphs F with parallel tree depth at most d, hom G) hom(F. H).
Given any graphs G and H, XG
(d) is maximal; that is, for any connected graph F &. Sd), there exist graphs G and (pec.(d)
H such that XG (G) (G) XH (H)
Spec.(d) (H) and hommF.c # hom (,, H).
We will present concise proof sketch of Theorem 3.3 in Section 3.3. Next, in Section 3.2, will interpret this result in the context of GNNs and discuss its significance, including how it extends previous findings and addresses open problems identified in earlier studies.
4

---

Published as a conference paper at ICLR 2025
3.2 IMPLICATIONS
Our theory has a wide range of applications, which will be separately discussed in detail below.
3.2.1
COMPARISON WITH 2-FWL
Firstly, we compare the expressive power of spectral invariant GNNs with the expressive power of the standard Weisfeiler-Lehman (WL) test. It immediately follows that the expressive power of spectral invariant GNNs strictly lies between the expressive power of 1-WL and 2-FWL test.
Corollary 3A. The expressive power of spectral invariant GNNs strictly stronger than 1-WL and strictly weaker than 2-FWL.
Proof. According to Zhang et al. (2024a), the homomorphism expressivity of 2-FWL encompasses the set all graphs with treewidth at most 2. classical result in graph theory states that any subgraph of any series- series-paralee graph has treewidth at most 2 (Diestel, 2017). Since any parallel tree is clearly subgraph of some series-pase series-parallel graph, its treewidth is at most 2. It follows that the homomorphism expressivity of parallel trees is contained within that of the 2-FWI.. To show the gap, we give counterexample graph in Figure 2. This implies that the expressive power of spectral invariant GNNs is strictly weaker than that of the 2-FWL. The proof for the case of 1-WL is similar and we omit it for clarity.
Figure 2: A coun- terexample graph in F² F2-FWL; x
3.2.2 HIERARCHY
Theorem 3.3 not only provides insights into the relationship between the expressive power of spec- tral invariant GNNs and 2-FWL, but also allows for comparison with wide range of graph in- variants and the corresponding GNNs. Specifically, similar to the analysis in Corollary 3.4, for any GNN models A and B such that their homomorphism expressivity exists, if F ç FB, then A is strictly weaker than B in expressive power. We now use this property to establish comprehensive hierarchy by linking spectral invariant GNNs to other fundamental graph invariants and GNNs.
Corollary 3.5. Spectral invariant GNN with 1 iteration is strictly weaker than subgraph GNN (also referred to as (1, WL Rattan & Seppelt (2023)).
Proof. According to Zhang et al. (2024a), the homomorphism expressivity of subgraph GNNs con- tains all graphs that become a forest upon the deletion of specific vertex. On the other hand, Theorem 3.3 states that the homomorphism expressivity of spectral invariant GNNs with one itera- tion contains all parallel trees of depth 1. Since any parallel tree of depth 1 becomes forest when deleting the root vertex, have proved that (1)pe.(1)) is subset of that of subgraph GNNs. Finally, one can easily construct a counterexample graph to prove the strict separation.
upon
Remark 3.6. Our result recovers and strengthens the main result in Rattan & Seppelt (2023). which only studied spectral invariants with iteration (Fürer's weak spectral invariant). We will next show this result actually does not hold in case of more than 1 iterations.
Corollary 3.7. Spectral invariant GNNs with 2 iterations are incomparable to subgraph GNNs.
We provide a counterexample in Figure 3. Nevertheless, we can still bound the expressive power of spectral invariant GNNs with multiple iterations that of Local 2-GNN, stated in the following:
Corollary 3.8. For any d E [oo), spectral invariant GNNs with d iterations are strictly weaker than Local 2-GNN (Morris et al., 2020; Zhang et al., 2024a).
Proof. According to Zhang et al. (2024a), the homomorphism expressivity of Local 2-GNNs con- tains all graphs that admit strong nested ear decomposition. Since any parallel edge can be par- titioned into ears with the same endpoints, one can easily construct a nested ear decomposition for any parallel tree. This shows (d) is a subset of that of Local 2-GNN. The expressivity gap can be seen using the same counterexample graph in Figure 2.
5

---

Published as a conference paper at ICLR 2025
(a) Counterexample Corollary 3.7
(b) Counterexample for Corollary 3.11
Figure 3: Counterexample for Corollary 3.7 and Corollary 3.11
Remark 3.9. Corollaries 3.7 and 3.8 significantly extend the findings of Arvind et al. (2024, Theo- rem 17) and provide additional insights into Zhang et al. (2024b, Theorem 4.3).
The power of projection. We next conduct a fine- fine-grained analysis by separating eigenvalues and projections to better understand their individual contributions to enhancing the expressive power of GNN models. We first prove the following theorem:
Theorem 3.10. The homomorphism expressivity of graph spectra is the set of all cycles Cn (n 3) plus paths Pi and P2, i.e., {Ca|n 2 (P,
The proof of Theorem 3.10 3.10 is provided Appendix C, which has the same structure as that of Theorem 3.3. Previously, Van Dam & Haemers (2003); Dell et al. (2018) have proved that the spectra of two graphs G and are identical if and only if for every cycle F, hom (F, G) = hom F, H). We extend their result by further proving the maximal property (Definition 2b)())) which only adds two trivial graphs P1 and Pg to the homomorphism expressivity. From this result, one can easily see that using eigenvalues alone can already improve the expressive power of an MPNN since the homomorphism expressivity of MPNN contains only trees (but not cycles).
To understand the role of projection, one can compare the set (C.,In 2 (P, P2) with SSpec.(1) (the homomorphism expressivity of Fürer's spectral invariant). Clearly, the of all parallel trees of depth 1 is strictly larger than {C./In 2 3) [P,, P2), confirming that adding projection information significantly enhances the expressive power beyond graph spectra.
The power of refinement. We finally investigate the power of iterations d (or number of GNN layers) in enhancing the model's expressive power. We have the following result:
Corollary 3.11. For any d N, spectral invariant GNNs with iterations are strictly more powerful than spectral invariant GNNs with d iterations.
Proof. For any h E N, we can construct a counterexample formed by replacing each edge in the path graph P22+2 with a parallel edge. We illustrate the construction in Figure 3(b). One can easily see that the resulting graph is in J J=Spec.(k++1 but not (S)pcc,())
Remark 3.12. Corollary 3.11 addresses the key open question posed in Arvind al. (2024), who conjectured that spectral invariant GNNs converge within constant iterations. Specifically, the au- thors questioned whether, for d 2 4, spectral invariant GNNs with + iterations are as powerful as those with d iterations. We disproved this conjecture by providing a family of example graphs that cannot be distinguished iterations but can distinguished in d' + iterations.
Our counterexamples further leads to the following result:
Corollary 3.13. For any N+, There exist graphs with (d)) vertices such that spectral invariant GNNs require at least d iterationns to distinguish between them.
Corollary 3.13 establishes a tight bound on the number of layers needed for spectral invariant GNNs to reach maximal expressivity, showing that it scales with the order of graph size. This advances an important research topic that aims to study the relation between expressiveness and iteration number of color refinement algorithms (Fürer, 2001; Kiefer & Schweitzer, 2016; Lichter et al., 2019).
To summarize all the above results, we illustrate the hierarchy established for spectral invariant GNNs and other mainstream GNNs in Figure
3.2.3 SUBGRAPH COUNT
In fact, our results go beyond the WL framework and reveal the expressive power of spectral invariant GNNs in a more practical perspective. As an example, we will show below how Theo- rem 3.3 can be used to understand the subgraph counting capabilities of spectral invariant GNNs.

---

Published as a conference paper at ICLR 2025
Subgraph GNN
2- GNN
2-FWL
strict
strict
incomparable
strict
strict
strict
Eigenvalue
strict
Spectrai Iteration
strict
Spectral
strict
Spoctral IGN
2 Iteration
co iteration
Figure 4: Hierarchy of spectral invariant GNN (abbreviated as Spectral IGN) and other mainstream GNNs. Each arrow points to the strictly stronger architecture.
Given any graph F, we say GNN model M can subgraph-coud count substructure F if for any graphs G and H, the condition XG (G) XH (H) implies sub (,, G) sub(F, H). Denote by Spasm(F) the set of all homomorphic images of F. Previous results have proved that, if the homomorphism ex- pressivity F.M exists for model M, then M can subgraph-count F if and only if Spasm (F) JrM (Seppelt, 2023; Zhang et al., 2024a). This allows us to precisely analyze which substructure can be subgraph-counted by spectral invariant GNNs.
Corollary 3.14. Spectral invariant GNN can count cycles and paths with up to 7 vertices.
Proof. For cycles or paths with at most vertices, one can check by enumeration that their homo- morphic images are all parallel trees. For cycles or paths with at least 8 vertices, the 4-clique is valid homomorphic image but is not parallel tree.
We can further strengthen the above results by studying the number of iterations needed to count substructures. We have the following results:
Corollary 3.15. The following holds:
Spectral invariant GNNs can subgraph-con count all cycles up to 7 vertices within 2 iterations.
2. The above upper bound is tight: spectral invariant GNNs with only 1 iteration (i.e., Füirer's weak spectral invariant) cannot subgraph-count 7-cycle.
3. Spectral invariant GNNs with 1 iteration suffice to subgraph-count all cycles to 6 vertices.
Remark 3.16. The subgraph counting power of spectral invariant has long been studied the liter- ature. Cvetkovic et al. (1997) proved that the graph angles (which can be determined by projection) can subgraph-count all cycles of length no more than In comparison, our results significantly extend their findings, which
match the cycle counting power of 2-FWL (Arvind et al., 2020). Moreover, we show that Fürer's weak spectral invariant can already count 6-cycles, thus extending the work of Fürer (2017).
3.3 PROOF SKETCH
In this section, we provide proof sketch of Theorem 3.3, with the complete proof presented in the Appendix. We begin by demonstrating that the information encoded by spectral invariants closely related encoding walk information the aggregation process GNNs. This corresponds the following lemma (proved in Appendix B.2, see also Arvind et al. (2024)):
Lemma 3.17. (Equivalence of encoding walk and encoding spectral information) Let (Vo, Ea) be a graph, with its adjacency matrix denoted by A. For vertices x, E Ve. define wag (x. 3) = A for all i E {0,1,2.... [Vll. which represents the number of k-walks from vertex to vertex y. Define the tuple (z. y) = (w&g(x (x, v),...,
w n- 1x, v)), where
n [Val. Define the walk-encoding GNN with the following update rule:
Xa (dak.((+1)(x)) hash(xc (dlk,(d)
(x), (W (x,, y), XG
Walk,(d)
(v)) y Vall).
The walk-encoding GNN outputs a representation XG (alk,(d)
(alk, (G) = fixe
(alk, (u)lu E Voll For any Spec. (H). (H).
graphs G, H, we have XG
Walk,(d) (G) XH (H) if and only if XG
(poc, XH
Walk, (H) iff, for all graphs Walk, (d) (G) XH
Our next step aims prove that for graphs G and H, XG F with parallel tree depth at most d, hom(F. G) = hom(F, (F, This will yield the first property outlined in Theorem 3.3. The proof has similar structure to that in Zhang al. (2024a), which

---

Published as a conference paper at ICLR 2025
is based on the tools of rre-ddecomposed graphs and algebraic graph theory (see Theorems B.14 and B.20 and Lemma B.17). This part corresponds to Appendix B.3.
Now, it remains to prove that the set F is maximal (the second property in Theorem 3.3)- To achieve this, we leverage the technique known as pebble game (Cai et al., 1992), which was originally used to construct counterexample graphs that cannot be distinguished by the k-FWL test. We extend the framework and define the pebble game for spectral invariant GNNs as follows:
Definition 3.18. (Pebble game for spectral invariant GNNs) The pebble game is conducted on two graphs G = (Va, EG) and H = (VH, Eg). Without loss of generality, we assume VG = VH. Initially, each graph is equipped with two distinct pebbles denoted u. and v, which initially lie outside the graphs. The game involves two players: the spoiler and the duplicator. The game process is described as follows:
The spoiler first selects a non-empty subset V$ from either Vo or VH, and the duplicator responds with a subset VD from the other graph, ensuring that | = |V Then, the spoiler places the pebble u on some vertex in V/D and the duplicator places the correspond- ing pebble on some vertex in V Similarly, the spoiler and duplicator repeat the process to place two pebbles v. After the initialization, all pebbles will lie on the two graphs
Initialization:
Main Process:
The game iteratively repeats the following steps, where in each iteration the spoiler may choose freely between the following two actions:
1. Action 1 (moving pebble v). The spoiler first selects non-empty subset V/ from either Va or Vn,, and the duplicator responds with subset VD from the other graph, ensuring that |V0 |VS]. The spoiler then moves pebble
some vertex in V0, and the duplicator moves the corresponding pebble v to some vertex in V/S.
Action 2 (moving pebble u). This action is similar to the above one except that both players move pebble instead of pebble c.
Termination:
The spoiler wins if, after a certain number of rounds, wi v) for graph G differs (u,
from WHr (u, v) for graph H. Conversely, the duplicator wins if the spoiler is unable to win after any number of rounds.
With the above definition, we can now prove the equivalence between the outcome of a pebble game and the ability to distinguish non-isomorphic graphs using spectral invariant GNNs:
Lemma 3.19. (Equivalence of pehble game and spectral invariant GNNs) Given graphs G and H and the number of steps d E N, the spoiler cannot win the pebble game in d steps iff XG
(dte, (G) = XH
Sppe.(d+1)) (H).
We give proof in Appendix B.4. Next, to identify counterexamples G and H for any F & (d) such that XG
Specc(()) (G) X# X (d) (H) and hom G7 & hom(F, H), we draw inspiration from a special class of graphs called Fürer graphs (Fürer, 2001). which is principled approach to con- structing pairs of non-isomorphic but structurally similar graphs. If graphs G and H are the Fürer graph and twisted Fürer graph constructed from the same base graph F, show that the pebble game can be significantly simplified. Importantly, the simplified pebble game will be played on the base graph F instead of the complex Fürer graphs, making the subsequent analysis much easier. Due to space constraints, a detailed description of the simplified pebble game is provided in Ap- pendix B.5. We then establish the following lemma, which relates the simplified pebble game to spectral invariant GNNs:
Lemma 3.20. (Fquivalence of pebble game on Fürer graphs and spectral invariant GNNs) Given a base graph F, let GF)) and (F) be the Füver graph and twisted Fürer graph of F, respectively. Then, the spoiler cannot win the simplified pebble game on F in d steps iff XG Spec.(d+1) (F)).). XH
Spec. (d+1) (G(F) =
Note that for any connected graph F, hom (F, F.F)) + hom (F, (F))) (Roberson, 2022; Zhang al., 2024a). Furthermore, we demonstrate that the spoiler has winning strategy on F in d steps if and only if F is a parallel tree with parallel tree depth at most d 11 (see Appendix B.6). By combining these results with Lemma 3.20, we establish the following lemma:
Lemma 3.21. For any F & FSpecc(d)) the spoiler cannot win the simplified pebble game on F. Consequently, XG
Spec.(d) (G(F)) XHI
(d) (H())).
8

---

Published as a conference paper at ICLR 2025
This yields the second property in Theorem 3.3 and concludes the proof.
3.4 EXTENSIONS
So far, this paper mainly analyzes the standard spectral invariant GNNs, which refines node features based projection information. In this subsection, we will show the flexibility of our proposed homomorphism expressivity framework, which can also be used to analyze other spectral-based GNN models such as higher-order spectral invariant GNNs.
3.4.1 HIGHER ORDER
Let us consider generalizing Section 2.1 1 higher order spectral invariant GNNs. A natural update rule of higher order spectral invariant GNN can be defined as follows:
Definition 3.22 (Higher-Order Spectral Invariant GNN), For any N4, the k-order spectral k-Spec
invariant GNN maintains a color XG (u) for each vertex k-tuple = (uI,..., ux) E Va Ini- k <Spee,(0)) (u) = (P(u1, U2), .... P(u1, uk)...., P(uk-1, uz)). In each iteration + 1, the tially, XG
color is updated as follows:
A (t+), (u) = hash(XG & Spec,()) X
(u), l(xx &Spc,,(1)) (u, U2, P(u,, ()) : Vali... ((x Mx (t) (u,, u2,..,, "k. (,,,,,),uuu Plun, u)) : Voll).
Denote the stable color of vertex tuple E VV as XG (w). The graph representation is defined SSep SpSpec (G) = d (u) u B.
as XG
One can that when k = 1, the above definition degenerates to the standard spectral invariant GNN defined in Section 2.1. To illustrate the homomorphism expressivity of higher-order spectral invariant GNNs,
extend the concept of strong nested decomposition (NED) introduced by Zhang et al. (2024a) and define the parallel strong NED. Our main result is stated below:
Theorem 3.23 (informal). gruph F is said to have a parallel k-order strong nested ear decompo- sition (NED) if there exists graph G such that G admits strong NED and F can be obluined from G by replacing each edge {u, v) E EG with a parallel edge that has endpoints (u, v). Then, the homomorphism expressivity of k-order spectral invariant GNNs is the set of all graphs that admit parallel k-order strong NED.
Due to space constraints, we leave the formal definition of k-order strong NED and the technical proof of Theorem 3.23 to the Appendix.
3.4.2 SYMMETRIC POWER
To generalize spectrum and projection to higher order, another classic approach in the literature is use the symmetric power of a graph (also called the loken graph). Audenaert al. (2005) first introduced the graph symmetric power to generalize eigenvalues into higher-order graph invariants. The formal definition of the symmetric k-th power presented as follows:
Definition 3.24 (Symmetric Power). For any
N4, and graph G, the symmetric k-th power of G. denoted by (()) is graph where its vertices are k-subsets of Va, and two subsets adjacent and only their symmetric difference is an edge in G.
Our homomorphism expressivity framework can be used study the ability of mainstream GNNs to encode the symmetric power of graphs. Our main result is stated as follows:
Theorem 3.25. The Local 2N-GNN defined in Morris et al. (2020); Zhang et al. (2024a) can encode the symmetric k-th power. Specifically, for given graphs G and H, if G and H have the same representation under Local 2k- ON-GNN, then G() and H (R) have the same representation under the spectral invariant GNN defined in Section 2.1.
Discussions with prior work. Regarding the expressive power of symmetric power, Alzaga et al. (2008); Barghi& & Ponomarenko (2009) gave the first upper bound, showing that if 2k-FWL fails to distinguish between isomoooiep graphs, then their symmetric k-th powers cospectral.

---

Published as a conference paper at ICLR 2025
Table 1: Experimental results on homomorphism counting, real-world tasks and substructure count.
Task
Homomorphism Count
ZINC.
Suhstructure Count
Model
N
X
Subset
Full
MPNN
300
.261
.276
.233
.31
.138 4 .006 .030 4 .002
.358
.208
1188
.16
.261
205
Spectral Invariant GNN
045
.046
.053
.048
.303
103
1. .006 .088 1 .003
.072
.072
.089
.089
.060
.09
Subgraph GNN
.011
.013
.010
.015
260
1110
+ 0007 .028
+ .002
.010
.020
004
.046
.007
.027
Local 2-GNN
008
.006
.008
.008
.122
.069
4 0011 0224 4 0002
.008
.011
.177
003
.007
.066
However, it remains unclear whether the conclusion extends to the more powerful projection infor- mation (beyond eigenvalues), or if the stated upper bound is tight. These open questions are further highlighted in Zhang et al. (2024b). Our result answers both questions by bounding the stronger refinement-basee spectral invariant for the k-th symmetric power graphs to Local 2k-GNN, which is strictly weaker than 2k-FWL (Zhang et al., 2024a). This offers deeper understanding of the capability of mainstream GNNs in encoding higher-order spectral information.
4 EXPERIMENT
In this section, we validate our theoretical findings through empirical experiments. We evaluate the performance of GNN models both synthetic and real-world tasks. For the synthetic tasks, assess the homomorphic counting power and subgraph counting power of the GNN models. These experiments serve to confirm our theoretical results, including Theorem 3.3 and Corollary 3.14. In addition, for the real-world task, we focus on molecular reaction prediction, specifically evaluat- ing GNN performance to achieve SOTA results but to validate our theoretical findings. We compare the performance of spectral invariant GNNs to both MPNNs and subgraph GNNs on the ZINC dataset. Details about model architectures are in Appendix D.
the ZINC dataset (Dwivedi al., 2020). Our primary objective is not
Homomorphism Count We use the benchmark dataset from Zhao et (2022) to evaluate the ho- momorphism expressivity of four mainstream GNN models. The reported performance is measured by the normalized Mean Absolute Error (MAB) on the test set. The empirical results are presented in Table 1. We can see that concerning homomorphism: (i) MPNN is unable to encode any of the five substructures, and none of the five substructures is a tree; (ii) Spectral invariant GNN can only encode the 1st and 2nd substructures; (iii) Subgraph GNN can encode the 1st, 2nd, and 3rd sub- structures; and (iv) Local 2-GNN can encode the 1st, 2nd, 3rd, and 4th substructures. The empirical results basically align with our theoretical findings.
Subgraph Count Cycle counting is a fundamental problem in chemical and biological tasks. Fol- lowing the settings in Frasca et al. (2022); Zhang et al. (2023a); Huang et al. (2023), evaluate the cycle counting power of four GNNs. The empirical results in Table demonstrate that the spectral invariant GNN can accurately count 3-, 4- 5-, and 6-cycles, indicating its strong performance in cycle counting tasks. This empirical result is also consistent with our theoretical predictions.
Real-World Task We evaluate our GNN models on the ZINC-subset and ZINC-full dataset (Dwivedi et al., 2020). Following the standard configuration, all models are constrained to 500K parameter budget. The results show that the spectral invariant GNN outperforms MPNN while demonstrating comparable performance to the subgraph GNN on the real-world task. These find- ings are consistent with our theoretical predictions.
CONCLUSION
In this work, we investigate the expressive power of spectral invariant graph neural networks (GNNs). By leveraging the framework of homomorphism expressivity, we give a precise charac- terization the homomorphism expressivity of these networks. We then establish a comprehensive hierarchy of spectral invariant GNNs relative to other mainstream GNNs based on their homomor- phism expressivity. Additionally, we analyze the subgraph counting capabilities spectral invariant GNNs, with focus their ability to count essential substructures. Our results are extended to higher-order contexts and address additional problems related to spectral structures using our homo- morphism framework. We demonstrate the significance of our findings by showing how our results extend previous work and address open problems identified in the literature. Finally, we conduct experiments to validate theoretical results.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
This work is supported by National Science and Technology Major Project (2022DD014900)andd National Science Foundation of China (NSFC92470123, NSFC62276005),
REFERENCES
Alfredo Alzaga, Rodrigo Iglesias, and Ricardo Pignol. Spectra of symmetric powers of graphs and the weisfeiler-lehman refinements 2008. URL /atxiiv////iivva//a http:p/s//aaaii..rrr//////////// 00w..//Bc1.2200 2322.
Vikraman Arvind, Frank Fuhlbrücck, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sci- ences, 11::42-59 59, 2020.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On hierarchy spec- tral invariants for graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Schloss Degstuhl-Lciiniz-Zenntee
für Informatik, 2024.
Koenraad Audenaert, Chris Godsil, Gordon Royle, and Terry Rudolph. Symmetric squares of graphs, 2005. URL https: /tatpa://arxvv...o wttp/viivvvv./////a///aaa org/ haab:/math/one 0507251..
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural net- works. In International Conference on Learning Representations, 2021.
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 Con- ference Machine Learning, pp. 599-608. PMLR, 2021.
Amir Rahnamai Barghi and llya Ponomarenko. Non-isomorphic graphs with cospectral symmetric powers. the electronic journal of combinatorics, pp. RI R120-R120, 2009.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation net- works. In International Conference on Learning Representations, 2022.
Mitchell Black, Zhengchao Wan, Gal Mishne, Amir Nayyeri, and Yusu Wang. Comparing graph transformers via positional encodings. arXiv preprint arXiv:2402.14202. 2024.
Danail Bonchev. Chemical graph theory: introduction and fundamentals. Routledge, 2018.
Andries E Brouwer and Willem H Haemers. Spectra of graphs. Springer Science & Business Media, 2011.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint arXiv: 1312.6202, 2013.
Jin-Yi Cai, Martin Fürer,, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count sub- structures? In Proceedings of the 34th International Conference on Neural Information Process- ing Systems, pp. 10383-10395, 2020.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. In Advances in Neural Information Processing Systems, volume 34, pp. 1713-1726, 2021.
Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 210-223, 2017.
Dragos Cvetkovic, Dragoš M Cvetković, Peter Rowlinson, and Slobodan Simic. Eigenspaces of graphs. Cambridge University Press, 1997.
11

---

Published as a conference paper at ICLR 2025
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in neural information processing systems, volume 29, 2016.
Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets weisfeiler and leman. 45th lernational Colloquium Automata, Languages, and Programming (ICALP 2018), volume 107, pp. 40. Schloss Dagstuhl-Leibniz-zennte fuer Informatik, 2018
Reinhard Diestel. Graph Theory. Springer Publishing Company, Incorporated, 5th edition, 2017.
ISBN 3662536218.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982. 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint 1rX0v:21 2021.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1-48, 2023.
Or Feldman, Amit Boyarski, Shai Feldman, Dani Kogan, Avi Mendelson, and Chaim Baskin. Weis- feiler and leman go infinite: Spectral and combinatorial pre-colorings. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. In Advances in Neural Information Processing Systems, 2022.
Martin Fürer. Weisfeiler-lehman refinement requires at least linear number of iterations. In Inter- national Colloquium on Automata, Languages, and Progrumming, pp. pp. 322-333. Springer, 2001.
Martin Fürer. On the power of combinatorial and spectral invariants. Linear algebra and its appli- cations, 432(9))2373-253 2380, 2010.
Martin Fürer. On the combinatorial power of the weisfeiler-lehman algorithm. In International Conference Algorithms and Complexity, pp. 260-271. Springer, 2017.
Floris Geerts and Juan Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2022.
Willem H Haemers and Edward Spence. Enumeration of cospectral graphs. European Journal of Combinatorics, 25(2):199-211 2004.
Yinan Huang. Xingang Peng. Jianzhu Ma, and Muhan Zhang. Boosting the eycle counting power of graph neural networks with 25-NNS. In The Eleventh International Conference on Learning Representations, 2023.
Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graphs. In The Twelfth International Conference on Learning Representations, 2024.
Charilaos Kanatsoulis and Alejandro Ribeiro. Counting graph substructures with graph neural net- works. In The Twelfth International Conference on Learning Representations.
Sandra Kiefer and Pascal Schweitzer. Upper bounds on the quantifier depth for graph differentia- tion in first order logic. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 287-296, 2016.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. In Advances in Neural Information Process- ing Systems, volume 34, 2021.
12

---

Published as a conference paper at ICLR 2025
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1):97-109, 2018.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: design provably more powerful neural networks for graph representation learning. In Proceedings of the 34th International Conference on Neural Information Processing Systems, pp.
2020.
Moritz Lichter, Ilia Ponomarenko, and Pascal Schweitzer. Walk refinement, walk logic, and the iteration number of the weisfeiler-leman algorithm. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-13. IEEE, 2019.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning, In The Eleventh International Conference on Learning Representations, 2023.
Kate Lorenzen. Cospectral constructions for several graph matrices using cousin vertices. Special Matrices, 10(1):9-22, 2022.
László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in neural information processing systems, volume 32, pp. 2156-2167, 2019.
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, pp. 4602-4609, 2019.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: towards scalable higher-order graph embeddings. Proceedings of the 34th International Conference on Neural Information Processing Systems, pp.
2020.
Daniel Neuen. Homoonorphisn--iiiiiggiiihhii closedness for graphs of bounded tree-width. arXiv preprint arXiv:2304.07011 2023.
Chendi Qian, Gaurav Rattan, Floris Geerts, Mathias Niepert, and Christopher Morris. Ordered subggaph aggregation networks. In Advances in Neural Information Processing Systems, 2022.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances Neural Information Processing Systems, 35: 55:14501114515, 2022.
Gaurav Rattan and Tim Seppelt. Weisfeiler-leman and graph spectra. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2268 228522285.22 SIAM, 2023.
David E Roberson. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree. arXiv preprint 2xXi:2200611322 2022.
Tim Seppelt. Logical equivalences, homomorphism indistinguishability. and forbidden minors. arXiv preprint 1rXiv:2302.112000 2023.
Tim Seppelt. Logical equivalences, homomorphism indistinguishability, and forbidden minors. In- formation and Computation, pp. 105224, 2024.
Edwin R Van Dam and Willem H Haemers. Which graphs are determined by their spectrum? Linear Algebra and its applications, 373:241-272, 2003.
Boris Weisfeiler and Andrei Lehman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu. Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
13

---

Published as a conference paper at ICLR 2025
Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph GNNs via subgraph weisfeiler-lemman tests. International Conference Machine Learning, volume 202, pp. 41019-41077. PMLR, 2023a.
Bohang Zhang, Shengjie Luo, Di He, and Liwei Wang. Rethinking the expressive power of gnns via graph biconnectivity. In International Conference on Learning Representations, 2023b.
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 Confer- ence on Learning Representations, 2024a.
Bohang Zhang, Lingxiao Zhao, and Haggai Maron. On the expressive power of spectral invariant graph neural networks. arXiv preprint arXiv:2406.04336, 2024b.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gmn with local structure awareness. In International Conference on Learning Representations, 2022.
14

---

Published as a conference paper at ICLR 2025
Appendix
Table of Contents
A Additional Related Work
16
B Proof of Theorem 3.3
17
B.1 Preparation: Parallel Tree and Unfolding Tree
17
B.2 Step I: Equivalence Encoding Walk information and Spectral Information
18
Step 2: Finding Homomorphie Expressivity
20
B.4 Step 3: Finding Pebble Game for Spectral Invariant GNN
26
B.5 Step 4: Introducing Fürer graphs
28
B.6 Step 5: Proving the Maximality of Homomorphism Expressivity
31
C Proof of Theorem 3.10
34
Experimental Details
35
E
Higher Order Spectral Invariant GNN
36
E.1
Update Rule of Higher- Order Spectral Invariant GNN Homomorphism Expressivity of Higher-Order Spectral Invariant GNN
36
E.2
36
E.3 Proof of Theorem E.6
37
F
Proof for Symmetric Power
39
Properties of Local &- GNN
39
F2 Main Result
40
F3 Proof of Theorem F.5
40
15

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RELATED WORK
Spectral Based Graph Neural Network. Spectral invariants refer to eigenvalues, projection ma- trices, and other generalized spectral information. In recent studies, spectral invariants have gained significant attention in the fields of graph learning and graph theory (Fürer, 2010; Van Dam & Haemers, 2003; Haemers & Spence, 2004). For instance, a well-known conjecture proposed by Van Dam & Haemers (2003); Haemers & Spence (2004) posits that almost all graphs can be uniquely determined by their spectra, up to isomorphism. Given the importance and widespread application of graph spectral information (Bonchev, 2018), the machine learning community has also focused on analyzing the ability of graph neural networks (GNNs) to encode spectral information and on de- signing GNN models that incorporate more spectral features. As a result, several recent works have concentrated on the spectral based design of GNNs (Bruna et al., 2013; Defferrard et al., 2016; Lim et al., 2023; Huang et al., 2024; Feldman et al., 2023; Zhang et al., 2024b). Specifically, Dwivedi et al. (2023; 2021); Kreuzer et al. 1) Rampášek et al. (2022) have designed spectral GNNs by encoding Laplacian eigenvectors as absolute positional encodings. A key drawback of using Lapla- cian cigenvectors is the ambiguity in choosing eigenvectors; thus, follow-up works have sought to design GNNs that are invariant to the choice of eigenvectors. Lim et al. (2023) introduced BasisNet, which achieves spectral invariance for the first time using projection matrices. Huang et al. (2024) further generalized BasisNet by proposing the Spectral Projection Encoding (SPE), which performs soft aggregation across different eigenspaces, as opposed to the hard separation implemented in BasisNet.
In addition to the design of spectral-based GNNs, several recent works have also focused an- alyzing the expressive power of spectral GNNs and comparing them with other mainstream GNN models. Balcilar et al. (2021) investigate the relationship between ChebNet (Defferrard et al., 2016) and the 1-WL test, demonstrating that for graphs with similar maximum eigenvalues, ChebNet is as expressive as 1-WL. Geerts & Reutter (2022) revisit this analysis and prove that CaleyNet (Levie et al., 2018) is bounded by the 2-WL test.
Black et al. (2024) introduced several new WL algorithms based on absolute and relative positional encodings (PE). The authors further established bunch of equivalence relationships among these algorithms. Notably, there exists a strong connection between the proposed "stack of power of ma- trices" PE and Spectral Invariant GNNs. We can prove that the proposed (I, L. _ -WL (see Theorem 4.6 in Black et al. (2024)) is as expressive as spectral invariant GNNs with matrix L, and similarly, (I, A.... 1 is expressive as spectral invariant GNNs with the ordinary adjacency matrix. Therefore, all results in our paper can be used to understand the power of these WL variants. Since Zhang et al. (2024b) has shown that the expressive power of RD-WL bounded by Spectral Invariant GNNs, it follows that the proposed L (see Theorem 4.6 in Black et al. (2024)) is also bounded in expressive power by Spectral Invariant GNNs. This conclusion repro- duces their key result (Theorem 4.4 in Black et al. (2024)).
Homomorphism Count and Subgraph Count. Subgraph counting is fundamental problem in chemical and biological tasks, as the ability to count subgraphs is strongly correlated with the per- formance of GNN in molecular prediction tasks. Kanatsoulis & Ribeiro studies subgraph counting power for a novel GNN framework, where classic messagg--assinng GNNs are enhanced with ran- dom node features, and the GNN output is computed by taking the expectation over the introduced randomness. The paper demonstrates that such GNNs can learn to count various substructures, including cycles and cliques. These findings share similarities with our work, as both studies char- acterize the cycle-counting power of certain GNN models. Notably, the GNN framework proposed in Kanatsoulis & Ribeiro can count more complex substructures, such as 4-cliques and 8-cycles, which exceed the expressive power of 2-FWI.
Moreover, based on the foundational theory of Lovász (2012); Curticapean et al. (2017), it follows that the subgraph counting power of a GNN can be inferred from its ability to count homomor- phisms (Seppelt, 2023; Zhang et al., 2024a). Consequently, recent research has also focused on the homomorphism counting power of GNNs. Dell et al. (2018) demonstrates that two graphs have the same representation under the k-WL algorithm and only if the number of homomorphisms to the two graphs from any substructure with bounded tree width k is equal. Additionally, Zhang et al. (2024a) introduce the concept of homomorphism expressivity as a quantitative framework for assessing the expressive power of GNNs. This paper specifically focuses on the subgraph counting
16

---

Published as a conference paper at ICLR 2025
power of spectral invariant GNNs. Related works in this area include Cvetkovic al. (1997), which shows that the graph angles (which can be determined through projection) are capable of counting all cycles of length up to 5, and Lim al. (2023), which demonstrates that GNNs can count cycles with up to 5 vertices. detailed comparison of our results with these previous studies is provided in the main text.
B PROOF OF THEOREM 3.3
B.1 PREPARATION: PARALLEL TREE AND UNFOLDING TREE
B.1.1 ADDITIONAL EXPLANATION FOR PARALLEL TREE
For the reader's convenience, we begin by restating the definition of the parallel tree, introduced in the main paper.
Definition B.1 (Parallel Edge:). We denote graph G as a parallel edge if there exist vertices u U E Ve such that the edge set Eg can be partitioned into a sequence of simple paths PI..... ......,Pm. Pms where each path has endpoints (u, r)). We refer to (u, F) the endpoints of the parallel edge G.
Definition B.2 (Parallel Tree:). We define graph F as parallel tree if there exists tree T such that we can obtain a graph isomorphic to F by replacing each edge (u, v) E ET with parallel edge having endpoints (u, v). We refer T as the parallel tree skeleton of the graph F. Additionally, denote the minimum depth of any parallel tree skeleton of F as the parallel tree depth of F.
We further define parallel tree decomposition for any parallel tree as follows:
Definition B.3 (Parallel tree decomposition). For parallel tree F (Vp, EF), its parallel tree decomposition involves constructing a rooted tree T = (Vrr, Err)) along with mapping functions 8r- and "/r- that satisfy the following conditions:
1. The label function for nodes, 31 Vi - VF, maps each node in T" to a unique vertex in F. 2. Let Ep denote the union of all paths in the graph F. The edge label function, Tr" Er - 2 satisfies the condition that for all (f1, E Err, each P E "r- (t1, 12) is a path connecting Er, there exists a unique tuple (41, 12, P).
(1)( and 8T (12). Moreover, for each edge (1/1,22) L2), such that e lies on the path P. where (4, (2) E VT x VT and P E (r(,,,
We denote 7" (Vrr, ErT,, (T-) the decomposition skeleton of graph F, and the ordered pair (F, as a parallel-tree decomposed graph.
Let Spt denote the set of all parallel trees, and we use Shr to denote the set of all parallel trees whose parallel tree skeleton has depth at most
B.1.2 UNFOLDING TREE OF SPECTRAL INVARIANT GNN
We now introduce process of constructing parallel tree from any vertex of given graph.
Definition B.4 (Constructing an unfolding tree of spectral invariant GNN). Given a graph G, vertex VG) and a non-negative integer d, the depth-d spectral GNN unfolding tree of graph G at vertex u, denoted as (F(() (u). T(d) (u)), is parallel-tree decomposed graph constructed as follows: At the beginning, F {u), and only has a root node r with 3r (r) = (u). We can define mapping Vy Va as (u)
For each leaf node t in T", do the following procedure: Let (t) v. For each w E Vo, add a fresh node tn to T and designate f as its parent. Then, consider the following case:
1. If w * Txx), add x.. to F and extend ι with (I.,) = w. We define 3T (tw. = Tw. For every we introduce
walk = UI, .2,..., Un = Tx)) with < [Val, where Vı Tx)), Un path Tez Feg..... V., linking Fa and x to graph F, where Vey = I,, Te, = Tw. We can also extend mapping with ((z.,) = U1 TZx,,) = u...... (... be the set of all path Fe, Tegy..., Je, connecting x and ww introduced this step.
Un. We define Yr" (t, tw) to
2. If Tœ), with n < Val. we introduce a loop 2 Frgs Tr,,..., to graph F, where Fe, = x. = I We can also extend mapping with 7 (Fo,)) ) = u1, n ( 02.... .-- x (x...) Un. We define
define (tw(tw)
Similarly, for every walk w 21, 02, ..... Un T(x)
17

---

Published as a conference paper at ICLR 2025
Yrr tw) be the set of all path Zei Pogs... Lv. connecting and Tw introduced in this step.
We terminate the process once T" becomes complete tree of depth d.
The following fact is straightforward from the construction the unfolding tree:
Fact B.5. For any graph G, any vertex Va, and any non-negative integer D, there is homo- morphism from F ((D)(u) (u) to G.
With additional Explanation for parallel tree and construction of unfolding tree, we are ready to prove Theorem 3.3 step by step.
B.2 STEP I: EQUIVALENCE OF ENCODING WALK INFORMATION AND SPECTRAL INFORMATION
In this section, we aim to prove Lemma 3.17. The key idea is to use the Cayley- Cayley-Hamilton theorem demonstrate that the walk-encoding GNN, as defined in Lemma 3.17, equivalent the spectral invariant GNN.
B.2.1 PROOF OF LEMMA 3.17
Lemma B.6. Let = (Va, Ea) be graph, with its adjacency matrix denoted by A. For A for all k 20.., which rep-
vertices z,y VG. define wā( resents the number of k-walks from vertex (wy (z, y), w))((, (), ,.....,u" (x, (I, where n |Val. Define the walk-encoding GNN with the following update rule:
vertex y. Define the tuple wā(a, v)
Walk,(d+1) (x) hash(XG (alk,(d) (x), (W) y), XG XG (alk,(d) (G) = HXG (alk. (u)lu E VaB.
Walk,(d) (y)) (EVEHH)
XG
The walk-encoding GNN outputs a graph invariant XG Walk.(d) (G) XH (H) if and only if XG
(alk,(d)
Spec,(d) (G) =
For any graphs and H, we have XG (dec.(d) (H).
XH
Proof. We begin by proving the following statement: If the spectra of graph G and graph H are identical (denoted as (A1, Xg ..., Am))) then for x, u E VG and y, v E VH. P(x, u) Ply, v) and only if wig (2, u) = Wir v).
1. First, we prove that if P(x, u) Py, v), then w1 u) wir 2). By the properties of diagonalizable matrices, for any k E 21, Vol}. we have:
wz Pa, + X P2(x, u) + .... + Nrx Pa.. (2,
Therefore, if
PA u) = (u, Vr [m],
it follows that:
(I, u) Σ (2,)) Σ (2. (
Thus, we have proven the first direction of the statement.
2. Now, we prove that if (z, u) w (u. v). then P(z, u) Ply,))
Let Ag and Ab denote the adjacency matrices of graphs and H, respectively. By the Cayley- Hamilton theorem, the minimal annihilating polynomial of matrix Ag is given by:
f()) (2 A1)(A A2) ... (2 Am))
For each E (1,2....., m). the eigenspace corresponding to eigenvalue X, is Ker(), -GG) Since:
R" Ker(Au - AA) Ker(AaI - Ker(Am Ac),
18

---

Published as a conference paper at ICLR 2025
for each r 21, the projection matrix onto the kernel space Ker(A, -Ac) is:
fA())
II (c) = PA
jfr
Therefore, there exist coefficients c). -m such that:
Px, (I, = c w u) + w u) + cm-1 WG m- (2, u),
Ps (v, =
w/t (v. u)
+ +
w
6n-1 - wa-1 (y,
Finally, conclude that if w u) = wHy (v. v), then P(r, u) Ply. for all z, E Va and y, v E Vи.
Armed with the statement proven above, are now prepared to prove Lemma 3.17. We will prove the two directions of the lemma separately as follows:
Spec (H), then XG (G) xWal (H). To do so, it suffices 1. First, prove that if Spec (G) XH
XG
(teck (u) = XH (pec,( (v) for all (u, v) E Vo x Vn, then
to show that for all t E N. if XG (t)
XG
(u) XH
(alk.((((v)) (v).
We prove this by induction. Initially, the statement holds trivially for I = 0. We then assume the (dpc,(d+1) (d)) Spec. (d+ (v),
statement holds for t d and aim prove it for = d + 1. If XG then the following conditions are satisfied:
XH
Spec.(d) (u) XH XG XG
(dec,(d) (c),
(1)
(P((u, Spec, (d) (x)) x Voll (((((V v). XH
XG
Spec.
(p)) 1 E VH EVEH
(v))
For any Va and y VH. if (P(u, v), XG previous result and the induction hypothesis, we have:
(pec,(d) (a)) (P(u, v), (dec, (y)), then by
(alk.(d) (x)) = (wH (v,y). XH (we (u, XG
Walk,(d)
(y)).
(2)
By combining equation and equation 2, we conclude: (dlk.(d)
XG
(u) XH
(alk,(d) (v),
(W))(u, XG
(alk,(d)) (x)) 1 E VG = (1, 4). XH (all(((())) y Vn B.
Thus, we conclude that XG
(alk, (v). Therefore, we have proven that (alk, (u) XHI
XG (G) = XH (H))(H)) implies xa Walk (G) = XH
Spec
Spec
(H)
2. Now, we prove the converse: if X (G) XH xWalk (H)), then XG
XH (H). Initially, Walk (G)- xH Walk (H)) implies Hxo (1)k (w) | u VoB lxx (1)k,(1) (v) v Vn If
Spec (G) Spec
XG
Walk. (w) XH walk.(1)()) (v), then w u) (1, This leads to:
XG
(w u) |uE Vo = (1, VE Vn:).
Hence, we derive that for all k E [n]:
tr (A = Σ (u, = Σ (u, = Σ (c, Σ (0, = =r (A
KEVO
VeVe
VEVR
VEVY
By standard results from linear algebra, the spectra of graphs G and H must be identical.
Similar to the first direction, we now prove that for all E N, if XG Stec,(t) (v).
Walk. (1a)..()(u) X (olk,(((v) for
Walk
all (u, v) VG VH, then XG
(tpec.() (x) XH
We again proceed by induction. Initially, the statement holds trivially for t = 0. Assuming the statement holds for / = d, we aim to prove it for / = d If XG we have:
(dlk. (u) X
Walk (d+k),d+)) (v),
XG (alk.(d) (u) = XH
(dlk.(d) (v),
((wG(u,
(alk,(d) (x)) x Vol ((wi)
v), XH
Walk,(d) (v)) 1yE V.
19

---

Published as a conference paper at ICLR 2025
According to the statement proven earlier, for any Va and y E VH, (x, (v.
implies that P(u,2) x) = P(u, y). Thus, we obtain:
Spec,(d) (u) = XH XG
Spec,(d) (v),
(P(uu, 1), XG
(d)
(x)) x E V&Bl = ((P((e, yH XH
Spec, (v)) e VHB.
Therefore, conclude that XG (poc (u)
1pec,(d+1) (v). Finally, we have proven that XH
Walk (G) XH Walk ()) implies XG (G) XH
Spec
SpeE(() (H). (H).
Spec
XG
By combining both directions, we conclude that for any two graphs G and H, XG if and only if Spec
Walk (G) = XH Walk (H)
XG (G) XH (H). Hence, the walk-encoding GNN is as expressive as the spectral- invariant GNN.
Spec
B.3 STEP 2: FINDING THE HOMOMORPHIC EXPRESSIVITY
We first define the isomorphism between parallel-tree treee decomposed graphs.
Definition B.7. Given two parallel-tree decomposed graphs (F,T") and (F; ("), pair of mappings
(p,T) is called an isomorphism from (F,T") to (F, ""), denoted by (F,T") = (F,T") if the following hold:
1. p is an isomorphism from F F, while is isomorphism from T" T (ignoring labels and 7).
2. For any E VTr, p(3r- (T(()( Moreover, for any (4, 12) E Err, p (2)) "rr (T(11,t2)
Theorem B.8. For any two graphs G, H, any vertices u E Va, x E Vn,and any non-negative inte- ger D. XG Walk,(P) (u) =X Walk.(D) (x) iff there exists an isomorphism (p. T) from (F (u), T (u))
(D)
to (F (x), T(D) (x)) (x)) such that p(u) x.
Proof. The proof proceeds by induction D. The base case is straightforward: for D 0, the theorem holds trivially. Now assume the theorem holds for all D S d, and we will prove for D = d 1.
(dlk (x) implies the existence of isomorphism (alk,(d+1)( (u) XHr
We first prove that XG
(p.7) from (F(4t1) (u), T(d+t)) (u)) to (F(d+1)(x)) (x), (((++)(())))) (x)) such that p(u) = x. Given that
XG (u) = XH
(d+1)
(z). (d+1)(z). follows that:
(d+1)
(w v), XG (alk,(d)) (v))keeve = U! (2, (x,8), XH
Walk.(d) (y) BUEVE-
Let Vol = [rrl, and denote Vo = (mi, U2, u2,..., J. ). Vn = (v1, .2.. Vn such that:
w v;) wiy (Ir, yi), Xa (alk. (v:) XHI (dlk, (y:) for all i [n].
By the definition of tree unfolding, we have:
(Urd U (w), ( = ( (w)) U Fif (a),
((d+))())
where we use U to represent graph union. By the inductive hypothesis, there exists an isomor- phism (pt, T4) from (F(d) To),Ta (v:))
(w)) to (F (ux) (y:)) such that pr(1;) y4- Addition- ally, since w (u, vx) = wiy(a (z. y:). (()(() is isomorphic to Ff.(()). Therefore, by merging all approximate mapping between tree nodes at depth no (x)) it follows that (p, 7) is a well-defined isomorphism from (F(d+1) (x), T (z:)), satisfying p(u) x.
ps and r; into á and 7, and constructing
more than 1 in (edt1) (u) and ((d+1) (x)).
H
T((+1) (u)) (w),
Next, we prove that if there exists an isomorphism (p, between the parallel-tree decom-
posed graphs (Fid+1) (u), To ((d+t)(w)) and (F(d+1)(a) (2:), T(d+1)
(z:) such that p(u) 2r, then
20

---

Published as a conference paper at ICLR 2025
XG (alk (u) Xis (alk.(d+11) (x)). Since is isomorphism from Te rr(d+1)( (u) (u) to gpld11
(z)) it maps all depth-1 nodes in TG T(a+t)(u) (u) to depth-1 nodes in T T((+1) (x). Let $1, 82,.... Sn be the depth-1 nodes in Te(++)) (u), and L1, ,,, be the corresponding nodes in T((+1) (x). For i [n], we de- note the subtree induced by s, and its descendants T (u), and similarly, the subtree induced by and its descendants G,t, (x)). Additionally, we define the subgraph of FG F(++"(u)
(u) induced (u). Likewise, we define the subgraph of Hи F(d-1) (u) induced by T Til+1) (u)
Tel+D(u) (u) as F( by G.s.
as P pld+)) (u). Without loss of generality, we assume the following:
7 an isomorphism from the subtree T. 1) (u) to T ((++1))))))
For all s E Vi
Gis (w) P(ayger (u) (s)) = Breat (x) (T())).
For all e E P (w) Pl (m) (e)) = "Tp (T(e)).
p is an isomorphism between the subgraphs F G,s, (u) and pid+1) (z).
p(d+1)
HH:
According to our assumption, (F(it)) (u), (w), T(d+1) (u)) is isomorphic to (F (d)+1) G.+;
H.N (x), H.,
Tld+ (x))-
Additionally, by the definition of the unfolding tree, (u), T (u)) (u)) is isomorphic to the depth-d unfolding tree (Pda (v=), (
for some v; E Va. Similarly, (1 (nld+))(a) (x), TH. (x)+ is isomorphic to (r(d (v.), (T(d) (v+)) for some ye E VH. By induction, we know that XG Walk.(d)) (ys) and wi (u, v²) = w/ (z, vi). Therefore, we conclude:
walk,(d) (v:)
Xи
(wg (a),xe (dlk. (1)))
(w (I. (1, v.), XH
Walk,(d) (vs)
for all E [n]. implying that:
{l (w, u.).xG (al (vs) BUEvVo = |l (W (I, v1). X/ (vi) BLLVV. XG
(3)
It remains prove that XG (alk, (u) XH (alk,(d))x)) (x)). To prove this, note that equation 3 implies that Al (wE (u, X3 (alk,(d") (v:)) Bueve = -f (w (z. vi), XH (dlk, (v:)) }1 B.VE
holds for all 0 S d' I d. Combined this with the fact that XG
(w)k = XH (alk, (z), we can
incrementally prove that XGi Walk,(d') (u) X" Walk,(d") (x) for all d' S d 1. We have thus concluded the proof. Thus, the proof complete.
Definition B.9. Given graph G and parallel-tree decomposed graph (F, T"), we define the function treeCount((F, T"), G) as the number of ordered pairs (u, d) E VG x N such that the depth-d unfolding tree (P(() (u), T(d) (u)) at vertex is isomorphic to (F,T").
Corollary B.10. For any graph G, H, XG (G) xil (H) iff treeCount((F,TT))) treeCount((F) J", H) holds for all parallel-tree decomposed graph (F,T").
X (G) walk Walk (H), then treeCount((FTT)) G) treeCount((F,T"), H). If XG (G) = XH (H), then VH B. For each color in the above multiset, pick Walk (u) = c. It follows that if (F,T") u E Va with XG
Proof. We first prove one direction of the corollary. We aim prove that if Walk Walk(G)
XH
L lxo Walk u VaB = Xx (x))
(F (w), T (w)) for some D, then Walk (w) = cHI = x E Vu : xH(x) = cB = treeCount((A)) T"), H) by Theorem B.8. On the other hand, if (F, T") # (F( (u), (w)) for all u E Va and all D, then clearly treeCount((F,TT))..) = treeCount H) = 0.
treeCount((F) (F,T"), T"), G) = Iffu E VG
X
We then aim to prove the second direction of the corollary. If (FFT)) FreeCount((F,T") ((FF")), H) holds for all parallel-tree decomposed graph (F,T"), it clearly holds for Vo and sufficiently large D. This guarantees that for all color Ku Va -G (u) =cHl af[= E Vn xH Walk = c]I by Theorem B.8. Therefore, (x Walk (w)) uuc E Vall (aak(())) x E Vn B. concluding the proof.
all (P(P) (u), (r(P)())) with
Walk
21

---

Published as a conference paper at ICLR 2025
Definition B.11. For parallel-tree decomposed graph )",, (T"( to denote the depth of tree T. For any tree note t E Vr, we use depy(t) to denote the depth node in T".
Using techniques similar to those in Corollary B.10, we can derive a inniteiteraatin version of Corol- lary B.10 as follows:
Corollary B.12. For any graphs G and H, XG (alk = XH treeCount ((F,T)) G) = treeCount (F,T", H) holds for all parallel-tree decomposed graphs (F,T") with (Tp(TT) S d.
(al (H) if and only if
In the following theorem, we will bridge homomorphic count with unfolding tree count. Before presenting the result, we first introduce some notations used to present the theorem.
Definition B.13. Given two parallel-tree decomposed graphs (F, TT) and (F, pair of map- pings (p. T) is called strong homomorphism from (F.T") to (F,T*) if it satisfies the following conditions: First, T is a homomorphism from T to T. ignoring the labels and 7 and is depth- preserving, i.c., depy (t) = (T(() for all t E Vr. Additionally, is a homomorphism from (t1, to (71)) (ft))) Finally, the depth of T" is equal the depth of T
We use str (F,, (") denote the set of all strong homomorphism from (F,T") to (F,T", and let (athhom((F,T)) Theorem B.14. Let (F,T") be parallel- decomposed graph and let G be graph. We have
(F,
T")) |strHom((F,TT", (F T-))). (F)
hom (F, ()
Σ
strhom (IF (F, (F,T*)) treeCount( (F,T*)) ,
(F.Tr)ES
for T"), and the depth of (F,T*) is d. Let E Va be any vertex in G, and denote (P(() (x), (e) (x)) as the depth-d unfolding tree x. We define Si (ar) as the set of all homomorphisms from F to G that map the vertex I E Vg. Furthermore, we define S2(x) as the set of strong homomorphisms (p. from (F,T")
Proof. We assume that (r-(r)
Vp to
to (F( (1r), ( (x)), such that p(u) = Then Theorem 1.14 is equivalent to the following equation: ΣxeVa [S1(z) Exeva (S2(z)). We will prove that |S] (x)] = S2(2)] for all x Vo.
Given x Ve, according to Fact B.5, there exists a homomorphism æ from F(()) (x) to graph G. Define mapping such that (p, 7) p for all (p.r) E S2 It suffices to prove that a is
bijection from 52(x) to (z).
We first prove that a is a mapping from S2(x) to S1 Since p is a homomorphism from F to Fll and π is homomorphism from F(d) to G. The composition of homomorphism is still a homomorphism. Therefoore... π o p is a homomorphism from to graph G.
We then prove that a is a surjection. For all g E (1 we define a mapping (p, from (F, T") to (Fid) (x), T(e) (x)) as follows. First define p(u)
and set r(r) be the root of (F(d)) (x), Ih (z)). Let U1, ....... Um E Vy- be the tree nodes of depth 1. Similarly, by definition of the unfolding tree, let 91, .2.....9hh Un E V Vidd(()) be tree nodes of depth 1. For all i [m]] we denote (Pa, Pie.... Pio. YT (u, v.). be the paths associated with edge (u, (u,v,) Er Sim- ilarly, for i E In] we denote (Pa,, P:....., P.s.. -r-(at (2, y:) to be the paths associated with edge (I, wi) E (a) Since and π are both homomorphism, we have:
For every (i E [m]), there exists yj (j E [n]), such that ((Tr = (2) for some ž, E Vg.
(1;)) =2
For every path Pix yu-(u, vz) (k (a:]) linking and By (U:), there exists P3 (1 [b,]] linking x and (, (2;) such that g( (P).).
We then define ((:r-(v:)) = (rgg" (m) (15) and pl p(Pa)) = P3, for each i E [m] and E [a.]. Based on the above two items, can easily define such that each node in T of depth
22

---

Published as a conference paper at ICLR 2025
is mapped by r node 1 in To (x) of the same depth, such that ((BT((8) Brod (x) (1) and p(rr (r) "irf" (w) (z, (). Continuing, we denote the subtree of T induced by and all its descendants as Th, and the subgraph of F' induced by T as Fs- Similarly, we denote the subtree of I (z) induced by r(s) and its descendants as I G.r(s) (z), and the subgraph of FG (x) induced by T-d) (z) as pld) (G,((a) (ar). We can recursively define the image of p on F, for each tree node of depth I, following the same construction described above. This recursive definition holds because remains homomorphism from (K, to G, and remains homomorphism from G.r(s) (4), (x)) to G. with ((3r(()) = x xBr1"( (T()))). By recursively applying this procedure, we can construct (p. r) such that it becomes strong homomorphism (denoted strHom) from (F, to (F( (x). (I)). Therefore, we have shown that for any S1(z), there exists a preimage (0,7) r) E (2(x)) such that (p, 7) =9.
Finally, we prove that or is an injection. Ti).
Let TI), (P2, T2) E S2(x) such that π PI π o P2. Similar to previous item, we define v1, 02, ........... Um E VT- to be the tree nodes of depth 1. Similarly, by definition of the unfolding tree, let yı, ;
V (T))
be tree nodes of depth 1.
For all E [m], we denote {Pa, Piz...., Pia, = =-T- vi). to be the paths associated with edge (u, v.) E ET.. Similarly, for E [n]] we denote Pr........... Pa. = YT (x, ys) to be the (x) For each [m], let (1) and j2(1) be indices
paths associated with edge (z. yb) Exg"
satisfying P1 (w()) (i) and p2(ws) Tza(()- It follows that π (2), x (x))())) By the
definition of unfolding tree, we must have (1) (2)(()) and thus pi (w:: p2(w)).
For each & E [a:], P.x E PTr-(u, vz). let (A)) and (2)) be indices satisfying pi (Pa)) PJIC)) and p2(Pxt) Pytannn where we use j to denote j = ji (i) - f2))). With similar analysis as the previous item, we have x (P3u6)) (P))21))) By the definition of the unfolding tree, we must have P) = P)tat)) and thus p: (Pus) = p2 P.x).
Next, recursively apply the previously described procedure to the subtree induced by the tree node s at depth and its descendants, following the same steps outlined earlier. Through this process, we can ultimately demonstrate that p1 = p2. Consequently, a is injective.
Combining the above three parts completes the proof.
Theorem B.15. Let (F,T") be parallel-tree decomposed graph with Dep(T") I d and let G be graph. We have
hom(F, (F,G)
Σ
strhom (IF,T), (F,TT)) treeCount( (F.Tt).).)) ,)
(F.T))EST
Proof. According to the third condition in Definition B.13, for (F,7") E Sat and (F, (r)) E Sut, if strhom((F, T"), (,, TT)) A O, then Dep(?T) Dep(T"). Therefore, we have (f. TT) E spt Thus, the conclusion of the lemma follows.
Definition B.16. Given two parallel-tree decompased graphs (F,T") and (F,T") along with a strong homomorphism T), we define (p. as a surjective strong homomorphism both and т are surjective mappings, and as an injective strong homomorphism if both p and T are injective mappings. We denote the set of all surjective strong homomorphisms from (F,T") to (T) ) by (F (F,T")) T")), and further define strsurj((F, (,,"")) = (strrurj((F,TT) (F, T-))- Similarly, we denote the set of all injective strong homomorphisms from (F.T") to (F, T") by strlnj((F,TT), "")")), and further define strinj((F, (F, TT) = (F,, (F,T"))
We now present the following lemma regarding the relationships between strong homomorphisms, surjective strong homomorphisms, and injective strong homomorphisms.
23

---

Published as a conference paper at ICLR 2025
Lemma B.17. For any parallel-tree decomposed graph (F,T") and (F, T"). we have
strsurj (F,TT), [, (T) ssrinj ( (E,TT) (F,T*)
strhom (ITTT), (F.TT)) (F,F")ES
aut (F,TM)
where aut(F. ft) denotes the number of automorphism of (F. fT). Here, the summation ranges over all non con-isomo (parallel-tree decomposed) graphs in Set and is well-defined as there are only a finite number of graphs making the value in the summation non-zero.
Proof. We initially define the set S as the set of triples ((F,T"), (), (b,))) (b)) that satisfy (F,T*) E
Sut, (p,7) E ssrSSur(( ("), (F, Ti)) and (ò, +b) E Strlnn((FF, (F,)(((F,,,)FF)) (F, )))) We define a mapping a such that ((F,, T"), (p. r). (6. + = (Øop. T)T) for all ((F, T",, (p.T). (0, v)) E S. Our goal is to prove that a is mapping from S to (FF,T (F, T)) Moreover, we aim to show that ((F1,, T ), (p1, (01, 141) a[((2, ), (p2: 72). (d2, (52)) if and only if there exists an isomorphism (ő, F) from (Fi, (()) to (F2, (22 such that po p1 = p2. toT T2. Φ1 22 o p. and 1/1 = 1/2 f.
We will prove these statements one by one. We first prove that is mapping from S to st (F) This simply follows from the fact that strSurj and strinj are both strHom, and the composition of two strHoms are still a strHom.
we define Next, we will prove that a is surjective. Given (P, E (FHHom((FTT).C) (F, )") (p.T). and (ø, v)) as follows:
1. We define F the subgraph of F induced by p(Vr), and we define 7 as the subgraph of T induced by (VV)). We clearly have (F, TT) E Spt.
2. Let p= ~ and r = 7. Obviously, (p, is a strSurj from (F, to (F,T".
3. Define identity mappings d(u)) for all Vp for v1) for all & Vg- Obviously,
(ø. is strinj from (F,T*) to (",
We clearly have f 0 and 1/ r. Thus, is a surjection.
We will now prove that T1 ), (pI. (n..Ti) (0), 2 ((F,, TT-), (p2, T2), ($2, 12)) iff there exist an isomorphism (ò. f) from (Fi, T() to (T)) such that p o fn = P2. o TI 1/2 o f. It suffices to prove only one direction, namely,
72, Φ1 22 P. th1 ((Fi, (PI, TI), (0i, ( 12), (02, 12), (02, th2)) implies that there exist an isomor-
phism (p. +) from (Fi, f to (F2, T(e) such that pop1- = foTI =22, Φ1 = 2200, u = o2
1. We first prove that F = fn and Tht = T.c For any u, u E Vp, if (u() # pi (v). then Φ1 o pz (u) & Φ1 (1()) since is an injection. Therefore, d2 o p2(u) o d2 o p2())) and thus p2(u) * P2(w). By symmetry, we also have that p2(u) # P2(U) implies pı(u) # (v() This (v) iff pa(u)= p2(u). For any u E Vp, if (pl Pi()) E EA Ep since P1 is a surjection. Therefore, (pa(u),p2(U)
proves that pi (u( then (u, v) homomorphism.
Ep, since P2 is a
By symmetry, it follows that if (2(w)) E F.g. then (pr(u), P(()) E E.. Therefore, we conclude that A = fz.. Similarly, it follows that Th = f/e..
2. Consequently, there exist isomorphism و and i such that 6o = p2. foT = T2. For any node q V7. p(87, (1)( = po (1( p2(Br( By, (T2(1) = Brg ( r2))).
Moreover, for any (2),92} Fr. p( ((((1192))) = 6o p1(11 9e)) = p2(1r(11110) q2)) = 7 (T2(91. = T7, (f T (g1 92)).
Since n. is surjective, 7I (g) ranges over all nodes in Art when ranges over Vy, and π (q1,
ranges over all edges in 7h2x when 42) ranges over ET. We thus conclude that (p, 7) is an isomorphism from (fi T( to (f2, ?/3)
24

---

Published as a conference paper at ICLR 2025
3. We finally prove that Φ1 O2 o á and 111 =/2 f. Pick any Vp, we have 02 o (pI(u) @2 o P2(") @1 o pi (1)) Since P1 is surjective, Φ1 (w) ranges over all vertices in F1 when ranges over Vp. This proves that Φ1 = Ø2 o p. Following the same procedure, we can prove that
ti1 = 1/2
Combining the above three items concludes the proof.
From Lemma 1.17, also obtain the finite-itration version of Lemma B.17 as follows:
Lemma B.18. For any parallel-tree decomposed graph (F,T") Sh and (F I
Spt,
have
strsurj (F,TT), (F,T") strinj (( (E,Tt), (F,T*)
strhom (I,TT), (F, (I.T)).f,,+)))
aut [ TM (F,
(F,TE)S
Proof. According to the third condition in Definition B.13, for (F, E Sut, strsuri((F, (F, (-)) strinj((F,, T"), (") # O, it follows that (F,TT) (r,T) E S Therefore, the conclusion of the lemma is immediate.
Definition B.19. We can list all non-isomorhpic parallel-tree decomposed graphs into an infinite sequence (F1, (F), (F2, TT"),.. with the following order.
The order requires |Vr, & |Vrs| for any < j. If Vr;1 |Vri| for any < j. then Fr.l s |Fr
Then we define following function matrix and function vector based on the order defined above.
1. Let :SE S N be any mapping. Define the associated matrix M NN+xN,, where AL, f (. T))). Similarly, we consider the finite-iteration version. Let f SSt x 5th 4 N be any mapping. Define the associated matrix M E NM+ where M =f ((F,, (F)).
2. Let g : S x G + be any mapping. Given a graph G E G. define the (infinite) vector I6 EN+, where 12,, g ((F,, ). G). For the finite-iteration version, let : S x 9 + N (9.(d) ()) NN+, where (9.(d) G2
be any mapping. Given graph G G, define the (infinite) vector 10
whhre
g ((F,,T)),
3. Leth GXG + N be any mapping. Given graph G E G, define the (infinite) vector 1/ E N++, where l2, h(FF, G). In the finite-iteration setting, let h 9 G - N be any mapping. Given
graph G E G, define the (infinite) vector (h.(d) NN+ where G
(d.(d) G)F
hom( (F.T"), parallel-tree tree decomposed graphs (F,T") ) iff treeCount((,.T""...O G) = hom (F. T"), ). ff all
Theorem B.20. For any two graphs G and H, we have hom
= treeCount( ((F, T,), H) for all parallel-tree decomposed graphs. Similarly, in the finite-iteration setting, hom (F, "T,"", G) hom((F) FF, )"), ), H) holds for all (F,T*) E Sat iff tftreCouun((P (F,T") G) = treeCount((P) T"), H) for all (", E St.
Proof. We consider each direction separately.
1. First, we prove that if FreeCount((F)) (F G) = treeCount((F, T"), H) for all parallel-tree hom((F,T"). H) for all such graphs (F,T") According to Theorem B.14, this result can be expressed in matrix form thom = M 1t Coree for all parallel trees F. This directly implies that ItreeCount ItreeCount leads to thom rhom. Similarly, in the finite-iteration setting, the result H
decomposed graphs, then hom ( (F,T")
G prreCoount and hom strroom
G
from Theorem B.15 can be rewritten matrix form as t hom = Mstrhom.(d)) 1 (d))
Therefore, if 1
(d)) 1 (d) it follows that (d)) 11
hom
25

---

Published as a conference paper at ICLR 2025
2. For the second direction of the lemma, it suffices prove the finite-iteration setting, as the general case directly follows. According to Lemma B.18, we have the following equations:
(strhom M -Mstrini(dd) (M) -1
(rreCCount,dd)
G
GG
(ttroom(d) H
M (ttrsirj.(d)) stt (M) H
preeCount,(d)
By simple observation, Maut is diagonal matrix where all diagonal elements are positive integers. Moreover, M is an upper triangular matrix with positive diagonal elements, This holds because strinj( : (F,, )) ) > 0 only when Vr, S [Vr, Since Mrstrsuri.d)) is lower triangular matrix with positive diagonal elements, it is invertible. Thus,
Mrtrinj.(d)
prreeCount = MMstrinj.(d) preeCount,(d))
GG
Additionally, by the definition of an unfolding tree, there are only finitely many non-zero el- ements in both fG freeeCount(d)) and ftreeCount.(d), and the corresponding non-zero indices are !!
stricted to fixed (finite) set. In this case, the upper triangular matrix = reduces to
finite-dimensional matrix, so we conclude that lG (treeCount,(d) freeCount,(d)) By enumerating over all d 2 we obtain that ItreeCount ItreeCount G =
Combining item 1 and item 2, we finish the proof of the lemma.
B.4 STEP 3: FINDING PEBBLE GAME FOR SPECTRAL INVARIANT GNN
In this section, we introduce the pebble game and demonstrate its equivalence the expressive power of spectral invariant GNN.
B.4.1 PEBBLE GAME
We first formally define the rules of pebble game.
Definition B.21 (Pebble game for spectral invariant GNN), The pebbling game is conducted on two graphs G (Vc, EG) and H (VH, Eạ). Initially, each graph is equipped with two distinct pebbles, denoted as and v, which start off outside the graphs. The game involves two players: the Spoiler and the duplicator. We now describe the procedure of the game as follows:
Initialization: Theee Spoiler first selects non-empty subset V from either Ve or Vn. and the duplicator responds with a subset DD from the other graph, ensuring that ||' = | The duplicator loses the game if no feasible choice is available. The Spoiler places pebble vertex in VD, and the duplicator places a corresponding pebble in VS. Similarly, the Spoiler and duplicator repeat the process to place two pebbles, Specifically, the Spoiler selects non-empty subset VS from either VG or VH. and the duplicator responds by selecting a subset VD from the other graph, maintaining |V |V The Spoiler then places on vertex in VD, while the duplicator places the corresponding v in Vs.
Main Process:
The game iteratively repeats the following steps, where, in each iteration, the Spoiler may choose freely between the following two actions:
Action 1 (moving pebble v): The Spoiler first selects non-empty subset Ss from either Ve or VH, and the duplicator responds with a subset DD from the other graph, ensuring that [V | The Spoiler then moves pebble moves the corresponding pebble to vertex in VSS
vertex in VD, and the duplicator
2. Action 2 (moving pebble u): The Spoiler first selects non-empty subset S from either VG or VH, and the duplicator responds with a subset DD from the other graph, ensuring that | |/ The Spoiler then moves pebble to vertex in pD, and the duplicator moves the corresponding pebble u to a vertex in 5S_
Termination:
The Spoiler wins if, after certain number of rounds, (u, v) for graph G differs from wjy (u, v) for graph H. Conversely, the duplicator wins if the Spoiler is unable to achieve win after any number of rounds.
26

---

Published as a conference paper at ICLR 2025
B.4.2 EQUIVALENCE BETWEEN SPECTRAL GNNS AND PEBBLING GAMES
Lemma B.22. Let 1 E N be any integer. For any vertices uG, vg Ve and uh, vh VH, if Walk.(0) (v), then the Spoiler can win the game in 1 - rounds when the two pebbles initially placed on verfices ug E Va and un E Vu in graphs G and H, respectively.
Walk,(() (u) # XH
XG
Proof. The proof proceeds by induction on 1. First, consider the base case where I = 0. In this case, the statement trivially true.
Now, assume that the lemma holds for all I S I,, and consider the case where = I. + 1. Suppose (L) (wH), (wn)) then by the inductive
Walk,(L++)) (uG) + Xи hypothesis, Spoiler wins. Otherwise, we have
Walk,(L++)) (wH). If X
(L) (uc) + XH
XG
vo E VoB + HWW UH). Walk.(L) vH E VH B. I (WG vG), Walk,(1) (uc))
Therefore, there exists color and E RlVol such that (Ca(u,,,,)) # (CH(uH, c, 2)), where
Ca(ua, = {{ vC E Va XG Walk,(")) = e, (uqa uG) =
If Ca(uc, c, x)] > [CH(UH, x.). the Spoiler can select the vertex subset V = Ca c, x) C Ve- Regardless of how the Duplicator responds with subset VD C Vn, there exists vertex UH VD such that (w (u uH); Walk.(()) (alk.(())vw))))
xx):)>alk(()))) (vH)) # (r, e). The Spoiler then selects this vertex x.5 VH and no matter how the Duplicator responds with x = UG E vs, we have either wy vG) # Walk,(()) (va)) If (GG, vG) WTy vh), the Spoiler wins (Llk,(L) (VG) + XH Walk,(() (wn). the remainder of the game is equivalent the game immediately. If XG
wi (un, UH) XG (alk (vG) # XH
to one where the two pebbles are initially placed on eg VG and Vn E VH in graphs G and H respectively. By the inductive hypothesis, the Spoiler wins the game.
If [Ca(uc, c,)) < (CH( c, Spoiler can select the vertex subset Vs =CH(HH, c,2) C VH. and the conclusion follows analogously.
Walk,((+3) (uG) XH
(L1k, (wH).
Lemma B.23. For any vertices ug VG and un VH. if XG then the Spoiler cannot win the game within rounds when the two pebbles are initially placed on vertices uG E Ve and uh E VH in graphs G and H, respectively.
Proof. The proof proceeds by induction on l. The base case = 0 is trivially true. Now, assume
(alk, (uG) =
the statement holds for < L, and consider the case = L + 1. Suppose XG Walk,(L+2) Then, XH
Il (wā (ua, va), Xa Walk, (Valk.(L+))((cc)) (va)) vo E VoB = II (Wwi un). XH
(alk,((+)) (wH)) un E VVH.
If Spoiler selects a subset Vs, and if vs c Va. Duplicator can respond with subset V c Vu such that ((w) (ua, va), Xa
Walk, (ta))))))) : va vSB Il (WH vH) XH Walk (L)I)))))) : uH E VDJ.
Similarly, if 8 c Vn. Duplicator can respond with subset VD C VG such that
Ul (wā (ug, vc), (L1k, (va)) vG E EV = Hl (wir(uH, (H), XH Waakkll)))(
E VSJ.
In both cases, is clear that |VS| = | Next, regardless of how Spoiler moves the pebble v to a vertex S VV, Duplicator can always respond by moving the corresponding pebble v to a vertex ID E VS, such that
(wr(ua, ia), Xa
Walk, (Llk, (5a) =wwjj (uH, ūH), XH
where (ōg, uH) represents the new positions of the pebbles. The remaining game is then equivalent to game in which the two pebbles are initially placed vertices Py Ve and in Vn in graphs G and H. respectively.
27

---

Published as a conference paper at ICLR 2025
Combining previous two lemmas, have the following result:
Lemma B.24. Given graph G and H, Spoiler cannot wins the pebble game in d steps iff Sdec.(d)
XG
(G) XH
(pec.(d) (H).
Therefore, we have proven Lemma 3.19 in the main paper.
B.5 STEP 4: INTRODUCING FÜRER GRAPHS
To continue, we draw introduce Fürer graphs, and we further prove that pebble games restricted on Fürer graphs can be greatly simplified.
B.5.1 PROPERTIES OF FÜRER GRAPHS
We first introduce the definition of Fürer graphs, introduced by Fürer (2001).
Definition B.25 (Connected components). Let F' (Vr,Ep) be connected graph, and let C VP be a set of vertices, referred to as separation vertices. We define two edges vu. {2, y) Ep as belonging the same connected component if there exists simple path ({v: Vi (2) U.)..... fyk-1. 91 } such that (yo. // = {u, v). f1k- 1.k = {z. y), and y: & U for forall: i E [1,k=1] is straightforward verify that this relation between edges induces an equiv- alence relation. Consequently, the edge set Ep can be partitioned into disjoint subsets, denoted by CC=(U)= = [P: Definition B.26 (Fürer graphs). Given any connected graph F (Vp, EF), the Fürer graph G(F) = (VoLF), FG(F)) is constructed as follows:
[m]]. where each P: C. Ep represents a connected component for some m.
Va(r) = ()) : VE, X C NF(x), |X] mod 2 = 0}, EG(F) = [[(x (v, Y)} c Va: (2,y) E Ep, (r E ++ X)).
Here, Y + E X holds when either (æ E Y and y E X) or (x & Y and & X) holds. For each x E Vp, denote the set
(etar(x) X(x X c NF(x), mod 2 0},
(4)
which is called the meta vertices of G(F) associated to Note that VG(F) Usevo Metar(z).
We next define an operation called "twist":
Definition B.27 (Twist). Let G(F)) (Va(P), ()) be the Fürer graph of F = (Vp, Er, (F), and let fz, y} E Ep be an edge of F. The twisted Fürer graph GFF) for edge {x. y}, constructed follows: (wist(G(F), {ar, y}) (VG(F), FFw)s)((()) where
((F)) = A((En) : Metap(z), E Metar(y)).
and is the symmetric difference operator, i.c., A&B = (A) U (B\A). For an edge set {er, ex} Ep, we further define
twist(G(F), == twist(... .. tw)sstt((ssssiiiiii ....,. (x).
Note that Equation (5) is well-defined as the resulting graph does not depend on the order of edges e1.-.. Ck for twisting.
The following result is well-known (see e.g. Zhang et al., 2023a, Corollary I.5 and Lemma I.7)):
Theorem B.28. For any connected graph F and any set S1. S2 C Ep, twist(G(F), = (wis iff [S [S2] (mod2).
We now present an essential property of Fürer graphs in terms of walk number:
Theorem B.29, Let G(F) (Va, Ea) be the Fürer graph of F (VF,EF), and let H(F) Dwist(G(F)) for some C Er. Given (x,X), X)), 3. (y.)) E Ve, and a connected component P E CCe((x, v)) with Png 1, the number of n-walks from (x. (y,)), passing through Me)a( Meta(x2).... Meta(x,) sequentially in G(F), is equal to the number of such walks in H (F) for all E N+ and vertices .1...., In on P. iff P is a path.
28

---

Published as a conference paper at ICLR 2025
Proof. If P is path, we denote P follows that the number of n-walks starting from (a, and ending at ))) passing through ( Meta(z,,) sequentially on G(F), is not equal to the number of such walks on H (F). Thus, one direction of the lemma is established.
{{11, ...,....................... f2,-1, 10. } with 21 and In y-
If P is not path, then there exists least degree is greater than 2. We define wn wC(F) [(x, X'), Mettl:a)...,,MM(((=.=.). (y. and win H(F) ((x, X)), Meta(a2),... Meta(zn- (y, (1)) as the number of n-walks starting from (I, X), ending at (y.)), ) and passing through Metay (21 (2))...... Metay sequentially in G(F) and (F), respectively. We use the notation (t) to denote the degree of vertex in the graph F. We proceed by induction on n to prove the following stronger statement: If the degrees of ,2, not all less than equal 2, then there exists function f
vertex, besides and y, P whose Meta(xx-1),
VF - N such that
" ((F) ((1, Meta(zz), (eeaar))).,,,Mt((z._)_) (1, (v.
= =w ( X2,, (2ta ..... (Mta((nn-))) 1), (v. 3/)) =f fn for all n E N. (z. X) Meta( (r), and (y. 3) Meta(y).
We first consider the case when n = 2. In this case, we can straightforwardly define the function fF as (1 (T,, xa) 2de3(
Next, assume that the statement holds for S N. We now consider the case when N + 1, and analyze two separate cases:
1. Not all degrees of 23, 24...., -n-1 are less than equal 2.
The n-walk passing Metap((1)..... Metay sequentially can be decomposed into a a1 1-walk from (ar, X) to (x22) followed by an n 1-walk passing Metay (x, sequentially and ending at (v.3). According to the induction hypothesis, the number of (n 1a-kal passing Metar Metar( Metar sequentially and ending at (y, Since the number of 1-walks from (x, to Metar(xa) 2x0gr(
equals (12, (1,,,.,.....
equals 2d0gr(22)-2 we can define the function f as fh (2.,, f (12,, Ta).
2. All degrees of 53, T4,...: In- less than equal 2. In this case, have deg, (x22) 2 3.
The number of (n 1a-wal passing Metay(zz) (x2),.... ........ Metap (In) sequentially and ending at
(y. is either 1 or O. Therefore, we can define the function f as ff = 2
Combining the two cases, we conclude that if the degrees of 222 Tz, 2n-1 are not all equal to 2, then there exists function J.. V(F)" N such that
wn ((F) Meta(xa),......... (tttazz))...,MMt((r..)) (y,
=w ((x, Meta(xz), ... Meta(Zn-1) (v. = ff
for all X E ( E (v))), and any & C EF.
By combining all previous analyses, we have proven the result of the theorem.
B.5.2 SIMPLIFIED PEBBLE GAME ON FÜRER GRAPHS
Definition B.30 (Simplified Pebble Game). The simplified pebble game is defined follows. Let F = (Vp, Ep) represent the base graph of a proper Fürer graph. The game is played on F with two pebbles, u and v, each of a different type. Initially, both pebbles are placed outside the graph F. The game begins with Spoiler placing pebble u any vertex of F, while pebble remains outside the graph. The game then proceeds in cycles, following these steps: Spoiler places pebble v on any vertex of F, swaps the positions of u and and then places pebble back outside the graph. Duplicator, on the other hand, maintains a subset Q of connected components, where Q C CCs currently placed.
and S is the set of vertices in F where pebbles u and
When Spoiler places a pebble on a vertex of F, one of two scenarios occurs. If CCs(F) remains unchanged, Duplicator takes no action. However, if the new pebble placement causes connected
29

---

Published as a conference paper at ICLR 2025
component to split into smaller regions, Duplicator updates Q by replacing any original component C EF that splits into PI.....PP Pk (where U P. P) with a subset of the newly formed components. That is, Q - (2) P) U (Pr.....,P,, Pi.} for some ji.... :Ji E [k], ensuring that [Q] 1 (mod 2). In other words, Duplicator removes the old component P (if present) and adds some of the new components while preserving the parity of [2). When Spoiler removes a pebble and places it outside the graph, two cases arise. If (P) remains unchanged, Duplicator again takes no action. However, if the removal of the pebble causes multiple connected components Pı.....PP Pk to merge into a larger component P = U P,, Duplicator updates Q by either removing the smaller components, i.e., Q - 2 (P1,-.. PkJ. or adding the merged component, i.e., Q - (2 (Pi....: P))) U,P depending on which option preserves [Q] = (mod 2). When Spoiler swaps the positions of the two pebbles, the connected components (C)(F) do not change, so Duplicator does not modify Q
Spoiler wins the game if, after any round, Q contains a connected component that forms a path. Duplicator wins if Spoiler is unable to achieve this outcome after any number of rounds.
Lemma B.31. Given a base graph F, Spoiler cannot win the simplified pebble game on F in d steps (d+1) (F)))
iff XG
Spec,(d+1) (G(F)) XH
The proof of Lemma B.31 follows similar structure to the proof of Theorem 17 in Zhang et al. (2023a), and thus we omit the details here for the sake of simplicity. Notably, the main idea behind the proof is to show that the original pebble game is equivalent to the following 'hill-iimplified" version of the game:
Let F (Vp, EF) be the base graph of proper Fürer graph. This version of the pebble game is also played on F., with two pebbles u and v. Initially, both pebbles are outside the graph F.
First, we describe the rules for the Spoiler. Spoiler maintains subset Q1 C CCs(F) of connected components, where the set S consists of the vertices in F currently occupied by the pebbles u and v. (If pebble is outside F, then S contains only the vertex where u is placed.) Initially, Spoiler places u on any vertex of F and leaves e outside the graph, maintain- ing 0 = }. Then, the game proceeds cyclically as follows:
- Spoiler places v on any vertex of F. Two cases arise for maintaining Q1: if CC& does not change. Spoiler leaves Qi unchanged. Otherwise, the new pebble may split some con- nected components into smaller regions. For each original component P C E that splits into PI...., Pk with U P.- = P, Spoiler updates Q1 to ② = (Q) (P) Prc. where j1, ........... Ri E [A]] and Ó1 = 0 (mod 2). This ensures that the parity of | remains unchanged.
Spoiler swaps the positions of u and v, leaving Q1 unchanged.
Spoiler removes e from the graph, leaving it outside F. Again, two cases arise for maintain- ing Q1: if CCs(F) does not change, Spoiler does nothing. Otherwise, several connected components P1, .....; Pe may merge into a larger component P U Pe. Spoiler then updates 2 to either é = ( Px or 2 = -2) (Qi)(Pr, (P.,..., PuP)UP, whichever (mod 2).
satisfics |011
Next, we describe the rules for the Duplicator, which are analogous to the Spoiler's rules but with a key difference: Duplicator maintains subset Q C CCs(F) where the parity of Q2 is always odd. Initially, Q2 = {Ef}, }, and throughout the game, Duplicator performs the following updates:
- When Spoiler places a pebble, Duplicator updates Q2 in the same manner as Q1, but ensur- ing [221 = (mod 2).
When Spoiler removes a pebble, Duplicator updates 2₂ as in the previous case, ensuring that the parity of Q2l remains odd.
-
-hhe Spoiler swaps the pebbles, Duplicator does nothing, as CCs(P) remains unchanged.
The result of the game is determined as follows: Suppose that pebbles u and v are placed on vertices of F. Spoiler maintains the subset Q1, and Duplicator maintains 2z. We then construct two twisted
Fürer graphs: ((F)= twist(G(F)) E) and G(F)) = twist(G(FF) E). where [ 1Qil and, for each P E Q1, select single edge & En? P 1. Similarly, |ف| = [22.. and for each P E 22.
30

---

Published as a conference paper at ICLR 2025
select a single edge E P = 1. Spoiler wins if the walk vector satisfies w ((F) ((u (), (v. 0)) * " "G(e) ((u, 0). (v, 0)), meaning that there exists an n-walk in ((F) from (u, 9) to (u. 0) that differs from the corresponding n-walk in G(F). By following a similar analysis to that in Theorem 17 of Zhang et al. (2023a), we can demonstrate that the 'half-simplified" pebble game is equivalent the original pebble game. Specifically, the Spoiler can win in d steps in the original pebble game if and only if they can win in d steps in the half-simplified pebble game. Furthermore, since it clear that the silpff-ipliiieed game is equivalent to the simplified game, we can conclude that the original game and the simplified game are equivalent on Fürer graphs.
B.6 STEP 5: PROVING THE MAXIMALITY OF HOMOMORPHISA EXPRESSIVITY
Before presenting the proof, we redefine the concept of the game state graph for clarity in the tech- nical exposition. Notably, there is slight difference between the definition of the game state graph here and the one in the previous section: we only consider game states with a single pebble in the game state graph.
Definition B.32. We define the game state (u, 2) as in the previous section, where u E Vp repre- sents the position of the pebble, and Q is the connected component maintained by the Duplicator. The game state graph is formed by all game states (u, Q). There is an edge from (u, Q) to (ū, Q) if there exists game transition from (u, Q) to ((û, 8), Q). followed by transition from ((ú, 0), Q) to (ū, ②), for some connected component set Q C EF and vertex ē VF.
Definition B.33. A game state (u, 2) is called a terminal game state if there is a transition from (u, 2) to a game state ((u, ū), 2) for some connected component set Q C. EF and vertex Vp, such that Q consists only of a single path. In this case, the game state (u, Q) called a terminal game state. It is straightforward to see that the Spoiler can win in the terminal state.
Definition B.34. Given game state graph G state (u, Q) is termed "'contracted" if, for any transition (u, Q) - (u', Q') E Egs, it holds that Q' C Q. The state is called "strictly contracted" if, for any transition (u, Q) + (ul, Q') Egs, it holds that Q' & Q.
Definition B.35. A game state (u, Q) is defined as "unreachable" if any path starting from the initial state (0, EF) and ending at (u, 2) passes through a terminal state.
We do not need to consider unreachable states since the Spoiler always wins before reaching them.
Lemma B.36. For any graph F, if the Spoiler can win the pebble game on F, then there exists a game state graph GS corresponding and non-terminal states are strictly contracted.
winning strategy for the Spoiler such that all reachable
Proof. 1. First, we prove that there exists a strategy for the Spoiler such that every reachable and non-terminal state is contracted. Since the Spoiler win the pebble game, they can win at any reachable state (u, Q). Consider any strategy where (u, Q) is not contracted. Note that the game state graph induced by all reachable states is Directed Acyclic Graph (DAG), can choose a state (u, Q) such that no path from the initial state (0. ( (Er}) to (u, Q) passes through any intermediate state that is not contracted. Next, we construct a new strategy to make the state (u, @) unreachable. We clearly have u + O. Without loss of generality, assume there is a transition (u, Q) + (u', Q') such that Q' L Q. Let (2y, (uz, 2I),.., (wr, 2r) be any path from the initial state (V. {Ep}) to (u, Q). We modify the strategy as follows: at state (WT-1, Q)-1). the Spoiler places the pebble Pa on u', swaps the pebbles
and v, and then removes P. from the graph. This process can be repeated for every path from the initial state (0, Fr) to the state (u, Q). In the new strategy, (u, Q) will become unreachable. However, the state (WT-1, Qr-1) may now violate the contraction condition. In this case, we recursively apply the above procedure to (WT-1, 1)- Note that this process will terminate after a finite number of steps, as the length of the path from the initial state to (wr-1, Qr-1) is strictly shorter than the path to (u, Q).
2. Next, we prove that every reachable and non non-terminal state can be strietly contracted. Suppose, for contradiction, that (u, Q) is reachable and non-terminal, but not strictly contracted. Then there exists transition ((u, ②) (u', 2')) Eeg. Since is at the boundary of all connected
31

---

Published as a conference paper at ICLR 2025
components, have u'. This implies that the game state graph is not acyclic, which contradicts the assumption that it is a DAG.
Combining the above two points, conclude that for any given graph F, if the Spoiler can win the pebble game on F, then there exists a game state graph GS corresponding to a winning strategy for the Spoiler such that every reachable and non-terminal state is strictly contracted.
Lemma B.37, Given any connected graph F, if the Spoiter can win the pebble game on F, then F is a parallel tree. Specifically, there exists a tree skeleton T (VTr, ETv, BTr, TT") such that (F,T") Spt.
Proof. Let G be the game state graph satisfying Lemma B.36. For each game state 8, denote nextos (s) as the set of states s' such that (8,s²) is a transition in GS and s' contains only a single component, i.e., s' has the form (u.(P)). By definition, next (0, {E = {(u, Q1). (u, Qm)} for some u E VF. where Q1.... Qm is the finest partition of CCr((u)).
The tree T will be recursively constructed as follows. First, create the tree root r with (r(r)
As will be explained later, the root node will be associated with the set of states ((r) == nextas (0, {Er}). We then proceed with the following procedure:
Let t be a leaf node in the current tree associated with a non-empty set of game states S(t) such that (P),EE)))(( Pl > 1. For each state (u, {P]) E S(1), create a new node i and set its parent to be l. Pick any state (v, (P')) E next (u, [P)), and set BT(() = u. Then, node E will be associated with the set of states S(t) = {(v, (P)) (v, (P}) E nextas (u, [P])}.
We now prove that T is indeed a valid tree skeleton for F. By definition of parallel tree, when constructing T" and defining the label function 37 Vi -> Vp, we can naturally define the label function for edges YTT ET: + 28r, For any edge (t1,t2) 12) E ET-, there exist only paths connecting (4,) and (T(22) in F. Therefore, the image of (t1, (2) is naturally defined as the set of paths connecting (r(t) and 3r Since 37 is already defined for the nodes of T", it remains to prove that for every edge (t1, t2) E Er,, there exist only paths connecting 37 (t1) and Br in F.
We revisit the construction of TT. Let be a leaf node associated with the game states S(t). For each game state (u, (P}) E S(t), create new node and set its parent to t. Pick any state (v, (P')) E nextas (u, (P)), and set Br = v. Since (u, (P')) E next (u, (P}), the transition ((u, (PH). (c, (P')) is legal move in the pebble game.
Moreover, since we assume that GS satisfies Lemma B.36, we can conclude that the game state (u, (P)) is strictly contracted. In other words, P C P. This implies that when the Spoiler places the pebble P. on vertex e E VF, the Duplicator can only choose a strictly contracted connected component set. Hence, we deduce that there are only paths connecting and Consequently, there exist only paths connecting (1) and (r)
By recursively applying this analysis throughout the construction of T", we conclude that for every edge (f1,t2) E ET", there exist only paths connecting (r1))) ) and (r in graph F.
We now prove finite-iteration version of Lemma B.37 as follows:
Lemma B.38. Given any base graph F, Spoiler can win the simplified pebble game on F in d steps iff there exsits a parallel tree skeleton T of F such that T" has depth at most d + 1.
Proof. Initially, it is evident that if F is parallel tree with a tree skeleton of depth at most d + 1, then the Spoiler has a winning strategy in d steps. Therefore, we are left to consider the converse direction of the lemma. Now, consider the case where, for a base graph F. the Spoiler has winning strategy in d steps. According to the analysis in Lemma B.36, if the Spoiler has a winning strategy in d steps, then he guarantee that all reachable non-terminal states in the game state graph G are strictly contracted. We will prove this statement by induction. The statement trivially holds for d 1. Assume that if the Spoiler has winning strategy in d steps, then the base graph is
32

---

Published as a conference paper at ICLR 2025
parallel tree with tree skeleton of depth most d. Now, consider the case where the Spoiler can win in steps.
By Lemma B.37, the Spoiler can win the game F, implying that F is parallel tree. Let T" be the tree skeleton of F. At the beginning of the game, we first consider the case where the Spoiler places pebble
vertex such that & {u Et Vr, (t) = v). We assume that the Duplicator selects connected component P (since F is a parallel tree, the Duplicator can only select one connected component in this case). Assume further that there exist t, E VT such that is on a path connecting 3T (t) and BT We now consider two separate cases:
If there is placing the pebble on u does not split F, and it remains as one connected component. In this case, we can directly eliminate (u, P) from the game state graph, and the remaining game state graph still represents winning strategy for the Spoiler.
than one path connecting (T( and (T') in F, i.e., hrr(t, ("]
then
If there is only one path connecting 31 (t) and (t') in F, i.e.,, Irr t')l 1, then placing the pebble on u splits the base graph F into two connected components. In this case, we replace the game state (u, (P)) in the game state graph with {u', (u'({P")) {P')), where u' E (rr((), and P'.
Following this discussion, we only need to consider the case where, at the beginning of the game, the Spoiler places the pebble on vertex E Vp such that there exists t E VT and u. (t( Without loss of generality, assume u = 3r(r), and the children of r are , (n). Further, assume that among all subtrees induced by 12. the subtree induced by l E Vr has the greatest depth. We now consider the case where the Duplicator picks the connected component formed by the subtree induced by t and the path in (r, t1). If the Spoiler must ensure that the subsequent game state is strictly contracted, he must place the pebble on 41- The remaining game now reduces game played on the graph induced by the subtree formed by all descendants of 4-- By the induction hypothesis, the subtree induced by & has depth at most d. Thus, 1"d has depth at most +
We now prove Lemma 3.21 from the main paper.
Lemma B.39. For any F & (Seee,,d), the Spoiler cannot win the simplified pebble game on F in 1 steps. Consequently, XG
(pec,(d) (G(F)) = XH
(d)e,(d) (H(F)).
Proof. By Lemma B.38, since F & JSSpec.(d), the Spoiler cannot win the simplified pebble game on the base graph F. Thus, by Lemma 3,20, we conclude that XG
Spec,(d) (G(F)) = XH (H (F)). O
(p)
Combining all the results from steps 1 through 5, we now conclude the proof of our main theorem.
Theorem B.40. The homomorphism expressivity of spectral invariant GNNs with d iterations can be charucterized as follows:
(Ser (F) F has parallel tree depth most d).
Specifically, the following properties hold:
X For graphs G and H, Spec.(d) (G) ) Spec,(d) (H) if and only for all graphs F' with parallel
XHI
tree depth at most d, hom (o,(FG hom H).
(d) is maximal; that for any graph & JSSpec(()), there exist graphs G and H such (pee,(() (H) and hom(h, G7 + ho,(F,H)
Spec,(d) (G) = =XH
that XG
Proof. By Theorem B.20 and Corollary B.10, we obtain that for graphs G and Ht, Spec.(d) (G) XG
Spec. (H) if and only if, for all graphs F with parallel tree depth at most d, hom G) XH
hom F, H). Furthermore, by Lemma 3.21, there exist counterexamples G and H for any F (pec,(d) (H) and hom G) * hom(F, H). Thus, we conclude
(d) such that X Spec.((i) (G) = X the proof of the main theorem.
33

---

Published as a conference paper at ICLR 2025
C PROOF OF THEOREM 3.10
In this section, we provide the proof of Theorem 3.10 from the main paper. Theorem C.1. The homomorphism expressivity of graph spectra is the set of all cycles On (n 2 3) plus paths P1 and P2, i.e., {Cn In U (PP.PP).
Proof. We separately prove that the set of all cycles satisfies the two conditions of homomorphism expressivity. For a graph G. we denote Ag E R/Va|x x Val as the adjacency matrix of G, and Spec(G) = (AG,1, ... :G. } as the spectrum of G.
We first prove that for any two graphs G and H. their spectra are identical if and only if for every F {Cn/In 330 ( P. hom(F, G) hom(F, H). Let C, denote cycle with vertices. For any graph G, we have hom Cn, G) tr( (r() for all n E N2s. and for n = 2, we denote C2 P2. Moreover, by a basic result from linear algebra, we further obtain:
hom(Cp,
hom(Cn, G) tr(A NO,1 + 1o.2 + X V.
Therefore, if hom, G) = hC,, H) for all n E N then we have:
Na. + 12 + ..... + No. Xii + Xii + +... + X H for all n E N
Thus, Spec(G) = Sp)c(H)) Conversely, if we are given that Spec(G) Spec(H), then:
hom G) = tr(AA) = tr(A;; = hom(Cn, H), for all n e N
Therefore, we have proven that for any two graphs and H. their spectra are identical if and only if for every F E [C,, 2 3) J (PI. P2), hom (F, G) hom(F, H).
We now prove that for any graph F that is not a cycle nor path, there exists pair of graphs G and H such that their spectra are identical, but hom(F. F, G) * hom F, H). Specifically, we show that for any graph that not a cycle. (pec(G(F)) = Spec( holds, where ((F) and H (F) denote the pair of Fürer graphs constructed with F as the base graph.
If F not nor a path, then there exist vertices x, y E VF such that the degree of x is greater 2. We then consider the Fürer graph G(F) and the twisted Fürer graph (FF) twist (FFs {x, y}). According to ??, for vertices v, 02 ....,,..................... In E VE and C VF, the num- ber of n-walks passing through (r. V), Meta Meta(xz), ..... Meta(I,),, (v, V) sequentially in G(F) and (FF) is unequal. Specifically, T2,.... Fn satisfy the following properties:
1. (v, 22); (12, ..., (In-1, (zin; v) E Ep.
2. The degree of T2.... ......... Zn is 2 in the base graph F.
3. Let 21 Intl U, then:
1( 1= 1,2, 1.2....... mn [(
(mod 2).
From this, we deduce that v x, and we have:
Σ COLF) ((v, V"), x2,.... .,, mn)=
Σ
CH V'), ,2,...,
(6)
(veta))Metar)))
(v, (e)ete))))()))
where for any vertex (v, V*) Meta(v), we use notations CGr ((v, V"), 22...... x.n)
and Cnrcyy ((u, V²), I2.... Øn) to denote the number of n-walks passing through (v, V"), Meta Meta( (v. V") in G(F) and H(F), respectively. If I2,..., In do
not satisfy the above properties, then for all (v, V²) " E Meta(v), the number of n-walks passing through (v. V"), Meta(r2),... Meta(zn), (v. V") in G(F) and HFF) is equal. Thus, equation 6 holds for all v, 22. En E Vp. Consequently, we observe the following property in terms of walk counts:
Σ (v, Meeeaa))))
w
E Meeea)))))
Winpy V'), V")).
where W ((v, V", (v, V') and (F) ((v, V"), (v. V`)) denote the number of n-walks start- ing and ending at (v, V`) in G(F) and H (F)), respectively. This holds for all N+ and
34

---

Published as a conference paper at ICLR 2025
(a) Counterexample for Theorem 3.10 (Graph G) (b) Counterexample for Theorem 3.10 (Graph H) Figure 5: Counterexample for Theorem 3.10
all (v, V) E (v) Thus, we conclude that tr(A = tr(A H(F)) for all n E N. By basic result from linear algebra, this implies that Spec(G((F) Spec( How- ever, since hom(F,
+ hom(F, H(F)), we have proven that for any graph F that is not a cycle, there exists pair of graphs G and H such that their spectra are identical, but hom(F, G) * hom H).
We now prove that for any path F of length least 2, there exist graphs G and H such that hom( F. G) hom F, H). A pair of counterexamples provided in Figure 5. Initially, we observe that the two graphs are cospectral. Furthermore, for any path P of length k (k: > 2), hom(F, F, G) = 4 2* + 2. For the graph H, let the number of k-walks starting from the vertex with degree be denoted ag. We then have the following recurrence relation:
ag d= + 2 ak-2-
du d1 = 3.
From this relationship, we can deduce that:
44 +22h + 1 (22R+3 + +1),
02k+1 -226+1 -22k+1_
+ 2 ao =1= -1
022 22
1 (22k+3 -1) (22k+2-1) -1).
Therefore, the total number of homomorphisms from path of length 2k + 1 to H is given by:
hom(P2442) H) =4 4- d2k + 2-2-00 02k+1
(2 226+3 4) (2 (2.2 2262+ +2) +
(4 22-+3 -
Similarly, the total number of homomorphisms from path of length 2k 2 to H is:
hom( (om(P2x+2: H) =4 02k++ + a2k+2
22 1) + (4 22h45 2)
=3 22k+5
Thus, for all 2 3, we conclude that:
hom Px. G) * hom(Pk. H), for all x23 3.
Combining the previous three results, have proven that homomorphic expressivity is {C,|n (Pr.
D EXPERIMENTAL DETAILS
In this section, we provide details on the experiments in Section 4. For dataset setup and training parameters, we follow Zhang et al. (2024a). We also use exactly the same model architecture for MPNN, subgraph GNN, and local 2-GNN as Zhang et al. (2024a) did.
Model architecture spectral invariant GNN. For spectral invariant GNN, we use the same feature initialization and final pooling layer other models. The feature propogation in each layer is implemented to incorporate the cigenvalues and their projection matrices of the graph. Specifically, suppose (A, (A B are all eigenvalues and eigenvectors of the input graph, h (u) E Rd is the
35

---

Published as a conference paper at ICLR 2025
feature vector of node in layer I. Then, the feature in next layer + 1 is updated according to the following rule:
h (u) ReLU(BN (MLP + f()))
8 (u)
Σ (e) + Σ (AP
WEV
where 1LP1,2 are two-layer feed-forward networks with batch normalization in the hidden layer.
Similar to Zhang et (2024a), for graphs with edge features, we maintain learnable edge embed- ding, g0 (u, v). for each type of edges, and add them the aggregation rule (()... The number of layers and hidden dimensions is set to match MPNN, such that all four models have roughly the same, and obey the 500K parameter budget in ZINC, as Zhang et (2024a) did.
E
HIGHER ORDER SPECTRAL INVARIANT GNN
E. UPDATE RULE OF HIGHER- SPECTRAL INVARIANT GNN
A natural update rule for oigher-order spectral invariant GNNs is as follows:
Definition E.1 (Higher-Order Spectral Invariant GNN), For any & E N4, the k-order spectral invariant GNN maintains a color XG
J-Spec (u) for each vertex k-tuple = (ui,..., ux) E V.g Ini- (Spee,(()) (u) = (P(u1, U2), .... P(u1, ua)...,, P(ux-1; un)). each iteration + 1, the tially, X
color is updated as follows:
(t+ (w) = hash(Xc S-Spec,(t) (u), (1xx (-Spec,()) (v, U2,...,, ux). P(u1, u)) : Val..., [ & (t), (u1, ug...... uk-1. v), P(ux, v)) e Vell).
XG
Denote the stable color of vertex tuple E VV as XG (u). The graph representation is defined (G) &-eec (u) u B.
k- Spee
as XG
E.2 HOMOMORPHISM EXPRESSIVITY OF NIGHER-ORDER SPECTRAL INVARIANT GNN
To describe the homomorphism expressivity of higher-order spectral invariant GNNs, we draw in- spiration from the concept of "strong nested ear decomposition" from Zhang et al. (2024a). For the reader's convenience, restate the relevant definitions here:
Definition E.2 (k-order Ear). A k-order ear is graph G formed by the union of k paths Pı,.... PR (possibly zero length), along with an edge set Q, satisfying the following conditions:
For each path Pt, let its two endpoints be (outer endpoint) and (inner endpoint). All edges in Q are between inner endpoints, i.e., Q C {(r, v;} S i,j k, 02 vz).
Any two distinct paths P: and Pj intersect only at their inner endpoints (if t2 03).
G is a connected graph.
The endpoints of the o-order ear are the outer endpoints u1.-.- Ugg
Definition E.3 (Nested Interval). Let G and be two k-order ears with inner(G) = for.... Uxx ) outer(G) {wi:
U&) and outer H)) = ...,..., w.), where each {u,, Uz} corresponds the endpoints of a path P. E pa) We say H nested on G if at least one endpoint w, of H E [k) lies on the path P.. and all other vertices of H are part of G. The nested interval is defined as the union of the subpaths subpath,, (w,, v.) for all i E [k] such that lies on P..
Definition E.4 (k-Order Strong Nested Ear Decomposition (NED)). A k-order strong NED P of graph G is partition of the edge set FG into sequence of edge sets Q1,... Qm. satisfying the following conditions:
Each Q: is k-order
Any two cars Q; and Q, with indices 1 < < S do not intersect, where c is the number of connected components of G.
36

---

Published as a conference paper at ICLR 2025
For each Qj with index
it is nested on some k-order ear Q2 with index 1 I i j. Moreover, except for the endpoints of 2 on Qi no other vertices in Q2 belong to any previous ear Q2 for 1 S k <
Denote by (Q₂) C Qi the nested interval of Q, in Qg. For all Q3 and Qx with e < < m, if 2 and Qs are nested on the same ear, then ((2)) C (QQ)).
Definition E.5 (Parallel k-Order Strong NED). A graph F'ss is said to have parallel k-order strong nested ear decomposition (NED) if there exists graph G such that F can be obtained from G by replacing each edge (u, v) E EG with parallel edge that has endpoints (u, v).
With the definition of parallel k-order strong NED, we now state the homomorphism expressivity of k-spectral invariant GNN as follows:
Theorem E.6. The homomorphism expressivity of a k-spectral invariant GNN is characterized by the set of all graphs that possess a parallel k-order strong NED.
E.3 PROOF OF THEOREM E.6
The proof of Theorem E.6 follows a similar structure to the analysis of Theorem 3.3 and Theorem 3.4 in Zhang et al. (2024a). Therefore, we provide only brief sketch, emphasizing the key differences between the proof of Theorem E.6 and the previous analyses.
Lemma E.7. For any given graphs G and H, we have XG for every graph that has a parallel k-order strong NED, hom G) = (F,
k--ppe (G)
k Sp-Sp (H) if and only if. XH
Proof. We first define parallel tree decomposition, which is a variant of the standard tree de- composition. Given a graph G = (Vg. Ec), its tree decomposition is represented as tree T" Er, ).). The label functions ST Vr - 2% and WT VTT + 2na are defined, where Pa denotes the set of paths in G. The tree T = (Vr, Fr,, Br. Br.TT) satisfies the following conditions:
1. Each tree node & VT is associated with a non-empty subset of vertices (r) C VG in G, referred to as a bag. Each node VT is also associated with a set of paths 7r called a sub-bag, which includes paths in G that begin and end with vertices in (().). We say that a tree node contains a vertex if u E (t),,, and contains path p if E (t).
2. For each path (11, u2...., . un)) with u, E VG for i E [ni], there exists tree node Vr that contains the path, i.c. (u.....; u,)) E (r()).
3. For each vertex E Vo, the set of tree nodes t that contain u, denoted by Br(u) {t Vr u E (t)) forms non-empty connected subtree T.
4. The depth of T is even, i.e., maxiev, depthy- (t) is even number.
5. [Br( = if depthy- (t) is even, and (tr = k + 1 if depthy- (t) is odd.
6. For all tree edges {s,t] E Er, where depthy- (s) is even and depthr- is odd, we have
(r(s) C (r()).
We refer to (G,TT) parallel tree-decomposed graph and k as the width of G's parallel tree decomposition. The set of parallel tree-decomposed graphs with width at most & is denoted as S Spec
Similar to the low-dimensional case, we define the unfolding tree of a k-spectral invariant graph neural network as follows. Given graph G, vertex k-tuple (uI,..., (u......k)) V and a non-negative integer D, the depth-2D spectral k-spectral invariant tree of G at u, denoted (F& SD)ec.((( T (D) (u)), is parallel tree-decomposed graph (F,T") E Sk-Spec con- structed as follows:
1. Initialization. Initialize F = Glu]. and T with root node such that Br(r) = {ui..... u Define a mapping π Ve - Ve by setting T(u) = u. For all i, E [k] with i # j and u4 and U, Uy add path
[rd], if there exists an r-length walk (V1,..., v..) with (w....., W,) with wi = u, and w, uy to F, and include (w....., w.) in the sub-bag (r). Moreover, extend æ by setting π (w:; = ez for all i [r].
37

---

Published as a conference paper at ICLR 2025
2. Iterate for D rounds. For each leaf node t T", execute the following for each [n]]: (a) If & (T(U)),...) x (ux)]. add a new vertex & to F and extend и by setting T(2) = w. Set Br(tw) = (t(() U {z}.
Initialize (r(tw) = "r (t). For all i E [k] and E [n), if there exists a path of length r, (VI,...,Upl) Up)) where 81 = w and vy r(w;), we construct a corresponding path (wI,...,,,, W,), with (b) wf = tu,) for some E [k). set (r(tw) Br(t) U }u,} without modifying F.
and w, ui, and include (wi,... w,) in the sub-bag (tw))
For each tw. add a child node t' to T", designate tu as its parent, and update (r(w")) based on the following cases:
(a) If & (T(w)),... .. T (ux)], set (r {u1, 111............................. "1-1, U5+1. Uz.. (b) If (u,)) for some E [k), set B (t,)) {uI..... Uj-1 1: ur. Mj+l. U1
Finally, set (twe) as the set of all paths in F that connect pairs of vertices in (tw))
Following similar analysis as in the low-dimensional setting, can first prove that for any k- k-Spec
two graphs G and H, XG treeCount* S-ppec ((F,T", H) holds for all (F,T") E Sk- Spec, We define
R S-Spec (G) (G) XH (H) if and only if SreeCount--Spe((FF, (FFTT),,
Spec ((F,T"). {
3D E N such that (Fa- (u), To Sptp-Seee. (u)) = (ET)) u V
With similar arguments in Theorem 3.4 in Zhang al. (2024a), we can further prove that for any two graphs G and H. decomposed graphs (F, T") and only if hom(F, G) hom(F, H) holds. We now prove that a graph F has a parallel tree decomposition with width at most k if and only if F admits a parallel k-order strong NED. We prove each direction separately. First, we use induction on the number of vertices in F to show that for any (F, 7") E Spec with 3r(r)= = (u1, U2,..., } there exists graph F' with a strong NED such that (u1,..., 4x} are the endpoints of the first ear. We can construct F by replacing edges in F with parallel edges. For the converse direction, assume that F admits parallel k-order strong NED. We aim to prove that there exists a parallel tree decomposition I" of F' such that (F, Spee We proceed by induction on the number of vertices and prove a stronger statement. For any connected graph F, if F can be constructed by replacing edges in a graph F with parallel edges, where F has a k-order strong NED and the endpoints of the first ear are {ur, u2..... 3 then there exists tree decomposition T" of F. This decomposition satisfies (F.T") E Sk-Spec, and (r(r)= = {ui, u2,... ) By combining the proofs for both directions, we conclude the proof of the lemma.
(FF.on(((FFT)))) G) = treeCount( (F, T"), ) H) holds for all tree-
We then prove the maximality of homomorphism expressivity follows. Lemma E.8. For any connected graph F $ jkkSppec there exist graphs G and H. such that k-Spec
hom F. G) & hom(F, F, H) and XG S--pec((G) (G) = XH k-Spee((H)
Proof. As in the www-iimensional case, we consider a pebble game between two players, the Spoiler and the Duplicator. The game involves graph F and several pebbles. Initially, all pebbles placed outside the graph. During the course of the game, some pebbles are placed on the vertices of F, which divides the edges Er into connected components. In each round, the Spoiler updates the position of the pebbles, while the Duplicator manages a subset of connected components, ensuring that the number of selected components odd. There are three main types of operations:
1. Adding a pebble p: the Spoiler places a pebble (which was previously outside the graph) some vertex of F. If adding this pebble does not change the connected components, the Duplicator does nothing. Otherwise, some connected component P is divided into several com- ponents P Use|m. P. for some m. the Duplicator updates his selection as follows: if P was selected, he removes and adds a subset of (P,.... Pm)) while ensuring that the total number of selected components remains odd.
2. Removing a pebble p: the Spoiler removes a pebble from a vertex. If this action does not alter the connected components, the Duplicator again does nothing. Otherwise, several connected
38

---

Published as a conference paper at ICLR 2025
components Pi...., Pm merge into single component P= Uve[m! P.. the Duplicator updates his selection by removing all selected P. and optionally adding P. while ensuring the total number of selected components is odd.
3. Swapping two pebbles and p': the Spoiler swaps the positions of two pebbles, which does not affect the connected components, and therefore the Duplicator does nothing.
the Spoiler wins the game if, any point, there exists path p such that both of its endpoints covered by pebbles and the connected component containing (p} is selected by the Duplicator. If the Spoiler cannot achieve this throughout the game, the Duplicator wins. In the Pv. Initially, all pebbles are placed
of the k-spectral
invariant GNN, there are A - pebbles, denoted p....... Pug. outside the graph. the Spoiler first sequentially adds the pebbles Pur..... ... Pus, (using operation 1). The game proceeds in cyclical manner. In each round, Spoiler selects an E [kc] and freely chooses one of the following two actions:
For r = 1,2,.... k. Spoiler removes pebble Pu, (operation 2), and then re-adds it (operation 1).
For r 1,2,.... k. Spoiler adds pebble Pw (operation 1) adjacent to Pu,, swaps Pu, with Pa (operation 3), and then removes P (operation 2).
For given graph F, let G(F) and H (F) denote the Fürer graph and the twisted Fürer graph with respect to F. Using similar reasoming as in the low-dimensional case, we can show that if the Spoiler cannot win the pebble game on F, then XG(P) k-Sper (G(F)"(((FF)
S-Sper (H)).. Furthermore, XH(F) analogous the analysis of Lemma B.37, we can conclude that if the Spoiler wins the pebble game on F. then there exists parallel tree decomposition T of F such that (F, TT) E Sk- Thus, for any connected graph F Jk-Spec, there exist graphs G(F) and HFF) such that hom (F, G(F)) * hom(F, F, (F)) and XG
k k-Spec (H()).. This completes the proof the lemma. k-Spee Speep (G(F)) = XH
Finally, the proof of Theorem E.6 is completed by combining the results from Lemma E.7 and Lemma E.8.
F PROOF FOR SYMMETRIC POWER
F.1 PROPERTIES OF LOCAL K-GNN
In this section, we review key properties of the local k-GNN as presented in previous works. We begin by formally introducing the update rule for the local k-GNN.
Definition F.1. Local k-GNN maintains color XG
L(k) (u. for each vertex k-tuple Vg. Initially,
L(K))(0) (u) = atp (w), called the isomorphism type of vertex k-tuple u, where (tp is the XG
atomic type of u. Then, in each iteration & ++1
L(0).00 (u), fXx ((R).(+11) (w) = hash Xx XG
100)(0 (b): UE ( (u)B, ... fxx
L00.000 (v) u (w)B
(8)
where (((i (w) = {(u),.. "1-1,,1, Mj+11 ".):: w E No(u,)). Denote the stable color as L(k)
Lik) XG (u). The representation of graph G is defined Xa (G) fixG (u) V
L(k)
Definition F.2 (Canonical Tree Decomposition). Given graph G (Vg. Eg). canonical tree decomposition of width l a rooted tree T = =Vr, E,, Br) satisfying the following conditions:
1. The depth of T is even, i.e., max depr. (t) is even;
2. Each tree node t e Vy is associated to multiset of vertices 3r) C. Ve. called a bag. More- over, (t) 1 if dep (t) is even and [3)(t) = k + 1 if depy- (t) is odd;
3. For all tree edges {s, f} E Ey where depy. (s) is even and dep (t) is odd, (r(s) C (x()) (where "C" denotes the multiset inclusion relation):
4. For each edge {u, 0} E Va, there exists at least one tree node t E Vy that contains the edge, i.e., (u, v) C (r(();
39

---

Published as a conference paper at ICLR 2025
5. For each vertex VG, all tree nodes whose bag contains u form (non-empty) collection.
We further define set SL(k) as follows:
Definition F.3. (F, E SL(k) iff (F,T") satisfies F.2 with width k and any tree node of odd depth has only one child. Moreover, all vertex of contained in at least one node of t.
Then, we can obtain the following theorem of the homomorphic expressivity of Local k-GNN. Theorem F.4. Any graph G and H huve the same representation under Local k G-GNN (i.e.
L(R)
L(k) (G) =X (H)) iff hom(o, G) = hom for all (F,T*) E SL(H)
XG
F.2 MAIN RESULT
Since 2k-local GNN is strictly weaker than 2k-WL, aim to extend previous result by showing that 2o-local GNN can encode k-symmetric power of a graph. We state our main result as follows:
Theorem F.S. The Local 2k-GNN defined in Morris et al. (2020); Zhang et al. (2024a) can encode the symmetric k-th power. Specifically, for given graphs G and H, if G and have the same representation under Local 2k- CN-G then G and (R) have the same representation under the spectral invariant GNN defined in Section 2.1.
F.3 PROOF OF THEOREM F.5
Definition F.6. Let μ1 H22
jm represent the distinct eigenvalues of the k-th order sym- metric power matrix a graph G. Let Es denote the eigenspace corresponding to μ4, and P. the or- thogonal projection matrix from R onto E,. For ú1, U2,...., U2k VG, if both (fu1, U2...., U4 U2x Bt are multisets
and Kf (1 U.42.....
distinct vertices, then we define
(S S2) (P (S1, (2), P (S1,52) S2)),
where S1 I U1, U2. ........ us H and S2 = 1f [1+++1 uk+2 U2k B. Otherwise, we define
0. P. (H ... us Hf Kuk+1, u......., U2k }1
We encode the spectral information of the symmetric power into the aggregation of local 2k-GNN, resulting in variant of the local 2k-GNN, defined as follows:
Definition F.7. A local 2k-GNN with symmetric power maintains a color XG 2k-tuple u E V Initially, the color is defined as
SL((k) (u) for each vertex
SL(22),(0) (w) (f ... u.B. ((u+1,,... ,uz "ict:.."",,,BB,.aappp.." atpp XG
Then, at each iteration + 1, the update rule is given by: (L-2
(u) = hash (Xo SL(26),(1)
(u). fixo SL(28),00) (v) u
XG
(9)
XxG (128),(0) (v) : NO (w))
where N₂6 (u) = {(11, 1, w, 41 un) No(u))) SL)))
The stable color is denoted as XG (w). The graph representation is then defined as
SL()) XG (G) lxo SL(k)
(u) v22B.
Next, we define the concept of a k-dimensional path as follows: Definition F.8. For graph G and vertices un...., Vo. we define the neighboring multiset of [ [11, ug,..., ... Uk D as:
k
NG (ur, U2
uk ))
(1 ... 1r-1, Mr+1, U 1=1
uk w No(u)))
é-dimensional walk of length n defined as a sequence (S1, S2..... .......... Sa), where each Si...., Sp multiset of i elements, and for all r In 11, S, E (S( If the path further satisfies the condition that for all u E S, with r E 32.3..... n - 1} and e E Va. u E No(w) implies u E S, for some E (r 1,r,r 1}, then denote (S,.... S.,) k-dimensional path of length
40

---

Published as a conference paper at ICLR 2025
We then define set (SL(R) base on the definition of set Sk(A)
Definition F.9. (F,T") E SSL(2)) iff (F,T") satisfies definition F.2 with width 2k, and any tree node 1 of odd depth has only one child. Furthermore, for tree node t E Vr if depy- (t) is even, we further associate with a set of d-dimensional path (r((),, called sub-bag. Specifically, for node t Vr, let (t) H Kui.... U22 B. then (t) contains k-dimensional path linking fui,.... Up B and HuR+1..... U2x H. Each vertex of F is contained in at least one node of T", either in bags or sub-baag bub-bags.
Lemma F.10. Any graph G and H have the same representation under Local 2k-GNN with sym- metric power if hom F,, G) hom(F, F. H) for all (F, (") E SSL(2k)
Proof. To prove the theorem, we first define unfolding tree of local 2k-GNN with symmetric power. Given a graph G. 2k-tuple u E v and a non-negative integer D, the depth-D unfolding tree of graph G at tuple u. denoted (L (L)) ( (u) (P) (u)) (u)) is constructed follows:
1. Initialization. We assume multiset u = Nu, u2 U2a B- At the beginning, F GlA u1 u2. u2k BI, and T only has root node with (r) Define a mapping क : VE + Va as T(u)) = uy Vi E [2k]. For every k-dimensional walk fu...... Ux B
fuu, ug.... U2z B}-
S Sp fuu+I,.... Ugh H with n IVol*. we introduce (uk+1,-. W2x and we add
a k-dimensional path H Ku,,....u ........)]. = S/
(2,,, 5x) sub-bag (rrb-bagr(r)))))) (r()).
2. Loop for D rounds. For each leaf node t in T", do the following procedure for all i E [2k]]
Let BT(()= = (ui,..., U2h B. For each w E Va. add a fresh child node tu ' and designate t as its parent. Then, consider the following two cases:
(a) If www& & ((((u))..... ...))..... * (w2x) }. then add fresh vertex = to F and extend with T(=) w. Define (r((w) = (t( U 22B. Then, add edges between x and (r) so that π is an isomorphism from F1 (tw)) ] to ([r(Br(t)))
(b) If w ( 7 (uzx) B. let w w-tw=nt mu,)). Then, we simply set (t (r(t)U((u, without modifying graph F.
Next, add fresh child node by in 7r, designate Ln as its parent, and set 3T(1k) and 7r (1w) based on the following two cases:
(a) If w É (m())...... (u2)) every k-dimensional walk linking (S and π (S,)) of length (n I [Vll), ). we in- troduce h dimeennsional path S S Sy.., Sy = Sn.. If i < k, then S = fui..... 11 2...., u& B. If k, then S Hur ................................ 4-11 BB. while if i k then S = Hui..... ux B. We denote S2- = Hl Hui..... "4 4411. U2 \ S1. We add (S,, S2 S .. into sub-bag 7r (Kw))
(ug)))))))))))))))))))) D. then (1/) f uu..... 1; 2, U U2a B- For
(b) Conversely, if w (T(u)).... T (u2x)) H. we assume that w Tu,). Then 3T((%))
"ur.... 1; My Ui+1...., U2 For every k-dimensional walk linking π (S1) and (SS,) of length n (n S Vo. we introduce ks -i-imennioonl path S₁ S. Sy...... S.
S,. If i k, then S = (uI.... -,,,,,;111 ur..... Ux B. If f = k. then S [ui,..., U1 u, B. while if [u 11 My, Ui+1,..., u22 B \S. We add (8, 5 ...... 8.) into sub-bag 7T (lnm).
kt then S
{( (w.,..... UR B- We denote S2
We can see from the construction of unfolding tree that for all k-tuple u E Va and D > 0, (F (w), (SLPD)())) SSL(2)), Given (F,T"), (F, Th) SSL(2R), we define pair of mapping (p.T) as an isomorphism from (F,T") (F, (")) denoted by (F,T) = (F, } if the following hold:
1. p an isomorphism from F to
2. is an isomorphism from T to T" (ignoring 33 and 7)-
3. For any t E Vyr, p(Br- = Bg. (T()),, and p(Tr-(t)) = 9p. (T(I)).
With similar analysis as Theorem B.8 we obtain that for any k-tuple u E V/ and v E Vs. SL(2))(D) (u) XH
(L(2A)( (v) if there exists isomorphism (p, from (F (u), (u), (SL()) (u))
XG
41

---

Published as a conference paper at ICLR 2025
(I (V)) (v), TH (T)DD(()) (v)). Given graph G and (F,T") E S5L(2K), we define
treeCount SL(2k) ((F, T", = { e V AD E N4s.1 ( (FSLID) (u), T (m) (FTT))
Therefore, we can obtain that if treeCount (L(z)) ((F, T"),)
PreeoonttSLea (FF,T)) H)
SL(2K) (G) = XH SL(2K) (I.). Additionally, with similar anal- for all (P,TT) E SSL(28), then XG ysis Theorem B.20 and Theorem B.14, can obtain that treeCount ((F PreeCountSu(28)( T"), H) for all (F,T") E (2L(2)) if and only if hom (F.T). (o for all (F,T") E S5L(26), Therefore, we can obtain that if ho SL(2k)
ho
SL(2k) (H). Thus, we finish the (G) = XH hom( ((F,(( H) for all (F,T") E SSL(2k), then XG (t)22)()) proof of the lemma.
Lemma F.1. For all k 2 I, we have SL(2k) SSL(26),
Proof. We can directly that gL(2k) S5L(2k), so it is sufficed to prove that for all (F, T*) SSL(2k), there exists alternative tree decomposition 7" such that (F, (F,T") E SSL(24), We will prove that for (F, (") E SSL(26), if max:evy- |nr(1)] 2 1, then we can construct 9' such that max [t) < maX |TT(()]. For (F,T") E S5L(2k), let t = arg maxie Vy- / (8) and suppose k-dimensional path S2...., S.) E (t().. We apply the following modification T" to construct 7
1. We construct tree node 1 2,...., fn-1 and E,, f2. such that 37((,) = Sp+1 USS and (,,(t,) S,+1 U.S. for all [n 1].
2. We add f, as the child node of t, for all [n 1] and add t, as the child node of f for all E (2, - 1]. Eventually, we add i as the child node of 6.
n.......11111
3. We delete k-dimensional path from (r(() and keep the bags of all vertices in VT \ {t} unchanged. Namely, we assume that (t) = (r(() \ ((S),..... Sn)) Morcover, (t) = (t) for all E VT and (t( (t) for all Vr (t).
VT and sub-bags of
With the procedure above we can obtain (F, E SSL(2R) such that max hn(( < maxeer hyr (t)). If we recursively apply this procedure to modify T", we can eventually obtain 1"r such that max,eft (t)] 0. Therefore, (F,"") E SL(2k), Eventually, we have proven that for all (F, T") E SSL(2k), there exists an alternative decomposition 7"' such that (F, Tr) E (L(2)) Thus, for all k 2 1, SL(2k) = SSL(2)),
Finally, we can finish the proof of Theorem F.5.
Theorem F.12. The Local GNN defined in Morris et al. (2020); Zhang et al. (2024a) can encode the symmetric k-th power. Specifically, for given graphs G and H, if G and H have the same representation under Local 2k- GN-, then GK) and (k) have the same representation under the spectral invariant GNN defined in Section 2.1.
Proof. According to Lemma F.11, the homomorphism expressivity of the vanilla Local 2k-GNN is equivalent to that of the Local 2k-GNN with symmetric power. Hence, the expressive power of the Local 2k-GNN is the same as that of the Local 24-GNN with symmetrie power. If there exist L(k)
graphs G and H such that X (G) = XH (L(()).(0) (H), meaning that the symmetric k-th powers
sL(k) (H). L(k) (H), then it must follow that XG (G) XH
SL(k)
(L(A). (G) = X#
Therefore, we also have XG of G and Hl are cospectral. Moreover, it is straightforward that if graphs G and H have the same Moreover,
representation under a Local 2k-GNN with symmetric power, then (()) and H (8) also have the same representation under the spectral invariant GNN. Thus, the proof of the theorem is complete.
42


Reviews:
[{"review_id": "o3TxUU5fEx", "reviewer": "Reviewer_MN8L", "summary": "The paper investigates the expressive power of spectral-invariant GNNs through the homomorphism expressivity perspective. The authors prove the followings: (1) projection-based spectral invariants and corresponding GNNs are strictly bounded by 2-FWL, and establish a quantitative hierarchy among spectral invariants and a family of WL-test variants; (2) increasing numbers of iterations can improve expressive power with an upper-bound; (3) substructure counting capabilities of certain spectral invariant GNNs. Experiments on synthetic and real-world datasets are conducted.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper is well-organized. The theoretical contributions are significant, addressing several remaining open questions including existence of homomorphism expressivity of certain GNN architectures. The paper quantitatively characterizes the expressivity of spectral invariant GNNs through parallel tree, establishes connections with k-FWL hierarchy, proves counting abilities of several substructures, and extends to higher-order spectral invariant GNNs. I check with proofs and they are solid.", "weaknesses": "While the paper is theoretically grounded, the experimental part could be strengthened. (1) The expressivity of spectral-invariant GNNs can be further validated on classical benchmarks of GNN expressivity, e.g., EXP, CSL, SR25, and BREC [1]. (2) The study on real-world datasets is insufficient. In many circumstances, expressive power does not necessarily determine the empirical performance on real-world datasets, so the authors should carry more extensive experiments on more benchmarks with careful tuning.\n\n[1] Wang, Y., & Zhang, M. (2023). Towards better evaluation of gnn expressiveness with brec dataset. arXiv preprint arXiv:2304.07702.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "UKMrbLvyqk", "reviewer": "Reviewer_9NdD", "summary": "The paper investigates the expressive power of spectral invariants in GNNs by employing a homomorphism-based approach. The authors theoretically demonstrate that spectral invariant GNNs can homomorphism-count certain tree-like structures, thus providing a quantitative hierarchy of expressiveness across different GNN architectures. This hierarchy assesses the influence of spectral invariants on the capability of counting substructures, such as small cycles. Empirical results test how homomorphism expressivity is related with performance in downstream tasks.", "questions": "Please see weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and organized. The key concepts, such as spectral invariants, homomorphism expressivity, and the hierarchy of expressiveness, are presented in a manner that facilitates readability.\n\nThis analysis introduces a novel perspective, providing an alternative theoretical framework for examining the expressive power and function approximation capabilities of GNNs.", "weaknesses": "I am concerned about the significance of the paper's contributions. The work presents a limited set of novel results and falls short in advancing our understanding of the expressive power of message-passing and spectral invariant GNNs. While the paper is well-written and accessible, it does not substantially enhance our knowledge of GNN architecture or provide actionable insights for designing more efficient models.\n\nSome important related work is missing:\n\nKanatsoulis, C. and Ribeiro, A., Counting Graph Substructures with Graph Neural Networks. In The Twelfth International Conference on Learning Representations.\n\nBlack, M., Wan, Z., Mishne, G., Nayyeri, A. and Wang, Y., Comparing Graph Transformers via Positional Encodings. In Forty-first International Conference on Machine Learning.\n\nHow does the submitted paper compare to these previous works?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "epROLB2Xrk", "reviewer": "Reviewer_58aL", "summary": "This paper explores the expressive power of spectral invariant GNNs through the concept of homomorphism expressivity. The authors provide a framework for characterizing the homomorphism expressivity of spectral invariant GNNs and prove that such GNNs can accurately count homomorphisms for parallel trees. They establish a hierarchy comparing the expressive power of spectral invariant GNNs with other GNN architectures and demonstrate that, while these GNNs have greater expressivity than 1-WL but are bounded by 2-FWL. The paper also extends these results to understand the subgraph counting capabilities of spectral invariant GNNs.", "questions": "* How does the eigen-decomposition described in sec 2.1 work? What are the methods to compute it? Complexity and is it guranteed to find these projection matrices?\n* How is spectral invariant GNN relate to other spectral GNNs? Does the results in this paper apply to these GNNs?\n(happy to raise score if these concerns are addressed)", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper provides a rigorous theoretical framework for understanding the expressive power of spectral invariant GNNs, using the novel concept of homomorphism expressivity. By introducing the concept of parallel trees, authors show how spectral invariant GNNs can count homomorphisms for such structures. The authors position spectral invariant GNNs between 1-WL and 2-FWL in terms of expressive power.", "weaknesses": "* The sec 2.1, the definition of spectral invariant GNN uses a not so standard eigen-decomposition involves projection matrices. The projection matries need to be idempotent which is an extra constraint. I would expect a more detailed description of this somewhere in the paper.\n* As the spectral invariant GNNs is defined differently to existing spectral GNNs such as ChebNet, GCN, etc. The connection to these classical spectral GNNs are not discussed in the paper. If they are not related, the contribution of this paper could be further limited as the results are only applicable to this GNN which can be expensive to run in practice (as it requires full eigendecomposition).\n* Dicussion on related work is limited and scattered across multiple places, making it harder to understand the position of this paper in literature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "OxiQryopVs", "reviewer": "Reviewer_i3cu", "summary": "This paper is a theoretical work, which studies the homorphism expressivity of spectral invariant GNNs, and proves the fundamental conjecture that 'spectral invariant GNNs converge within constant iterations'. Specifically, the authors show that the homomorphism expressivity of spectral invariant GNNs can be characterized by the set of parallel trees, which bridges between homomorphism and spectral invariants. The authors proves the strict order of the expressiveness of MPNN, spectral GIN, subgraph GNN, and Local 2-GNN with both theories and experiments.", "questions": "I wonder whether the proposed homomorphism expressiveness can help discriminating between different GNN models (w.r.t both model weights and architectures), so that one can design learning algorithms to improve the training and architecture design of GNN. Or whether this expressiveness can guide GNN designing, e.g. finding GNN paradigm that 'enjoys a larger set of  homomorphism expressiveness'.  \n\nMay the authors add some illustrations on how can the proposed quantifiable expressiveness benefit GNN learning and design? This can help audiences that do not have a learning theory / GNN expressiveness background to better feel the impact of the series of this work.", "limitations": "", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors develop new theoretical tools, e.g. the parallel tree decomposition (Def. A.3) and pebble game for spectral IGN (Def. 3.18), to identify the quantifiable expressiveness of spectral IGNs.\n2. The authors conduct empirical experiments in validating the expressiveness inequality / order of mainstream GNN structures (Table 1 and Section 3.2).", "weaknesses": "The weakness listed below does not compromise the contribution of this paper.\n\nAlthough the authors have characterized the homomorphism expressivity of spectral IGNs, there still exists a gap between such expressiveness and the approximation error and generation error of practical spectral IGNs (or other GNN architectures) in machine learning practice (e.g. graph / node / edge prediction). 'Whether we can predict or bound the training / generalization error based on the proven homorphsim expressivity' seems to be a challenging open question (which is out of the scope of this paper). From my perspective, this requires to consider the homomorphism complexity of the data distribution, while this paper only focus on the expressiveness of the hypothesis set / GNN backbone.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "eA9TMd4RD3", "reviewer": "Reviewer_B3EZ", "summary": "The present manuscript tackles the theoretical understanding of the power of spectral invariants over graphs, in particular linking such power to the expressive power of GNNs built accordingly. The paper provides a comprehensive analysis of the expressive power of such invariants by exploiting the concept of homomorphism expressivity, which characterizes class of graphs in term of pseudo-isomorphism test algorithms, such as coloring algorithms. An experimental framework is also provided to validate the theoretical findings.", "questions": "Corollaries 3.11 and 3.13 state that increasing the number of iterations would make the spectral invariant GNNs more powerful. How would the authors relate such a theoretical statement with the known issues of over smoothing and gradient vanishing in GNNs? A comment in this regard would be insightful.\n\nI wonder how the datasets used for the experimental validation were selected. Is there a particular criterion?", "limitations": "", "rating": 10, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The manuscript presents an impressive comprehensive overview over the expressive power of spectral invariants, bridging together many elements from the literature and providing answers to open problems on the topic. \nThe presentation of the paper is well structured and made very clear to the reader.", "weaknesses": "I do not find any particular flaw in the manuscript. The argumentations seem solid and the scientific analysis is carried on in a proper way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Oral)