Rethinking the Expressive Power of GNNs via Graph Biconnectivity
Authors: Bohang Zhang
Shengjie Luo
Liwei Wang
Di He
Venue: ICLR 2023 notable top 5% (2023)
Keywords: Graph Neural Networks
Expressive Power
Weisfeiler-Lehman test
Graph Transformer
Biconnectivity

Abstract: Designing expressive Graph Neural Networks (GNNs) is a central topic in learning graph-structured data. While numerous approaches have been proposed to improve GNNs with respect to the Weisfeiler-Lehman (WL) test, for most of them, there is still a lack of deep understanding of what additional power they can systematically and provably gain. In this paper, we take a fundamentally different perspective to study the expressive power of GNNs beyond the WL test. Specifically, we introduce a novel class of expressivity metrics via graph biconnectivity and highlight their importance in both theory and practice. As biconnectivity can be easily calculated using simple algorithms that have linear computational costs, it is natural to expect that popular GNNs can learn it easily as well. However, after a thorough review of prior GNN architectures, we surprisingly find that most of them are not expressive for any of these metrics. The only exception is the ESAN framework (Bevilacqua et al., 2022), for which we give a theoretical justification of its power. We proceed to introduce a principled and more efficient approach, called the Generalized Distance Weisfeiler-Lehman (GD-WL), which is provably expressive for all biconnectivity metrics. Practically, we show GD-WL can be implemented by a Transformer-like architecture that preserves expressiveness and enjoys full parallelizability. A set of experiments on both synthetic and real datasets demonstrates that our approach can consistently outperform prior GNN architectures.

Published as a conference paper at ICLR 2023
RETHINKING THE EXPRESSIVE POWER OF GNNs VIA GRAPH BICONNECTIVITY
Bohang Zhang' Shengjie Luo'
Liwei Wang
Di He
"National Key Laboratory of General Artificial Intelligence. School of Intelligence Science and Technology. Peking University
*Center for Data Science, Peking University zhangbchang@pku edu. cn, ]uos]3stu. wku..ppku.cco...
www.ppp..cccco edu, cn, {wanglw, diw./ppku.ccuuiiiiieco cdu..n
ABSTRACT
Designing expressive Graph Neural Networks (GNNs) central topic in learn- ing graph-structured data. While numerous approaches have been proposed to improve GNNs in terms of the Weisfeiler-Lehman (WL) test, generally there is still lack of deep understanding of what additional power they can systematically and provably gain. In this paper, we take a fundamentally different perspective to study the expressive power of GNNs beyond the WL test. Specifically, we intro- duce a novel class of expressivity metrics via graph biconnectivity and highlight their importance in both theory and practice. As biconnectivity culated using simple algorithms that have linear computational costs, it is natural expect that popular GNNs can learn it easily as well. However, after thorough review of prior GNN architectures, we surprisingly find that most of them are not expressive for any of these metrics. The only exception the ESAN framework (Bevilacqua et al., 2022), for which we give theoretical justification of its power. We proceed to introduce a principled and more efficient approach, called the Gen- eralized Distance Weisfeiler-Lehman (GD-WL), which is provably expressive for biconnectivity metrics. Practically, we show GD-WL can implemented by a Transformer- like architecture that preserves expressiveness and enjoys full paral- lelizability. A set of experiments on both synthetic and real datasets demonstrates that our approach consistently outperform prior GNN architectures.
be easily cal-
INTRODUCTION
Graph neural networks (GNNs) have recently become the dominant approach for graph representa- tion learning. Among numerous architectures, message- message-passing neural networks (MPNNs) are ar- guably the most popular design paradigm and have achieved great success in various fields (Gilmer et al., 2017; Hamilton et al., 2017; Kipf & Welling, 2017; Veličković et al., 2018). However, one major drawback of MPNNs lies in the limited expressiveness: as pointed out by Xu al. (2019); Morris et al. (2019), they can never be more powerful than the classic I-dimensional Weisfeiler- Lehman (I-WL) test in distinguishing non-isomorphic graphs (Weisfeiler & Leman, 1968). This inspired variety of works to design provably more powerful GNNs that go beyond the 1-WL test.
One line of subsequent works aimed to propose GNNs that match the higher-order WL variants (Morris et al., 2019; 2020; Maron et al., 2019c;a; Geerts & Reutter, 2022). While being highly expressive, such an approach suffers from severe computation/memoory costs. Moreover, there have been concerns about whether the achieved expressiveness is necessary for real-world tasks (Veličković, 2022). In light of this, other recent works sought to develop new GNN architectures with improved expressiveness while still keeping the message-passing framework for efficiency (Bouritsas et al., 2022; Bodnar et al., 2021b;a; Bevilacqua et al., 2022; Wijesinghe & Wang, 2022, and see Appendix A for more recent advances). However, most of these works mainly justify their expressiveness by giving toy examples where WL algorithms fail to distinguish, e.g., by focusing on regular graphs On the theoretical side, it is quite unclear what additional power they can system- atically and provably gain. More fundamentally, to the best of our knowledge (see Appendix D.I), there is still a lack of principled and convincing metrics beyond the WL hierarchy to formally mea- sure the expressive power and to guide the design of provably better GNN architectures.
"Equal Contribution.

---

Published as a conference paper at ICLR 2023
F.
C.DI
D
(D.EF.I)
(D.E.F.))
F.H.
(A.B.C)
M
(AB..C))
(IJJ)
(J.K.L,,,)
(JKLL)
(J.M.N)
(a) Original graph
(b) Block cut-edge tree
(c) Block cut-vertex tree
Figure I: An illustration of edge-biconnectivity and vertex binex-bbconnectivityy Cut vertices/edges are
outlined in bold red. Gray nodes in (b)/(c) are edge/vertex-biconneeci components, respectively.
In this paper, we systematically study the problem of designing expressive GNNs from a novel perspective of graph biconnectivity. Biconnectivity has long been central topic in graph theory (Bollobás, 1998). It comprises a series of important concepts such as cut vertex (articulation point), cut edge (bridge), biconnected component, and block cut tree (see Section 2 for formal definitions). Intuitively, biconnectivity provides structural description of graph by decomposing it into disjoint sub-components and linking them via cut vertices/edges to form a tree structure (cf. Figure 1(b,c)). As can be seen, biconnectivity purely captures the intrinsic structure of graph.
The significance of graph biconnectivity can be reflected in various aspects. Firstly, from a theo- retical point of view, it is basic graph property and is linked to many fundamental topics in graph theory, ranging from path-related problems to network flow (Granot & Veinott Jr, 1985) and span- ning trees (Kapoor& & Ramesh, 1995), and is highly relevant to planar graph isomorphism (Hopcroft & Tarjan, 1972). Secondly, from a practical point of view, cut vertices/edges have substantial values in many real applications. For example, chemical reactions are highly related to biggebbbonnectiviity of the molecule graph, where the breakage of molecular bonds usually occurs at the cut edges and each biconnected component often remains unchanged after the reaction. As another example, social networks are related to vertex vertex-biconnectivityy where cut vertices play an important role in linking between different groups of people (biconnected components). Finally, from a computational point of view, the problems related to biconnectivity (e.g., finding cut vertices/edges or constructing block cut trees) can all be efficiently solved using classic algorithms (Tarjan, 1972), with computation complexity equal to graph size (which is the same as an MPNN). Therefore, one may naturally ex- pect that popular GNNs should be able to learn all things related biconnectivity without difficulty.
Unfortunately, we show this is not the case. After a thorough analysis of four classes of representa- tive GNN architectures in literature (see Section 3)1,, we find that surprisingly, none of them could even solve the easiest biconnectivity problem: to distinguish whether a graph has cut vertices/edges or not (corresponding to a graph-level binary classification). As result, they obviously failed in the following harder tasks: (i) identifying all cut vertices (a node-level task); (ii) identifying all cut edges (an edge-level task); (fii) the graph-level task for general biconnectivity problems, e.g., distinguishing pair of graphs that have non- non-isomorphic block cut trees. This raises the following question: can we design GNNs with provable expressiveness for biconnectivity problems?
We first give an affirmative answer to the above question. By conducting a deep analysis of the recently proposed Equivariant Subgraph Aggregation Network (ESAN) (Bevilacqua et al., 2022), we prove that the DSS-WL& algorithm with node marking policy can precisely identify both cut vertices and cut edges. This provides a new understanding as well as a strong theoretical justification for the expressive power of DSS-WL and its recent extensions (Frasca et al., 2022). Furthermore, we give a -ra-inr analysis of several key factors in the framework, such as the graph generation policy and the aggregation scheme. by showing that neither (i) the ego-network policy without marking nor (ii) variant of the weaker DS- WI. algorithm can identify cut vertices.
However, GNNs designed based on DSS-WIL are usually sophisticated and suffer from high com- putation/memory costs. The main contribution in this paper is then to give a principled and effi- cient way to design GNNs that are expressive for biconnectivity problems. Targeting this question, we restart from the classic I-WL algorithm and figure out major weakness in distinguishing bi- connectivity: the lack of distance information between nodes. Indeed, the importance of distance information is theoretically justified in our proof for analyzing the expressive power of DSS-WL. To this end, we introduce a novel color refinement framework, formalized as Generalized Distance Reisfeiler-Lehmanr (GD-WL., by directly encoding general distance metric into the WI. aggrega-
2

---

Published as a conference paper at ICLR 2023
Table 1: Summary of theoretical results on the expressive power of different GNN models for various biconnectivity problems. We also list the time/space complexity (per WL iteration) for each WL. algorithm, where n and m are the number of nodes and edges of a graph, respectively.
Section 3.1
Section 3.2
Section
Model
MPNN
GSN CWN GraphSNNN
ESAN
Ours
3-IGN
WL variant
1-WL
SC-WL
CWL OS-WL
DSS-WL
DS-WL
WL
SPD-WL GD-WI
2-FWL
Cut vertex
X
X
X
X
X
/
Cut edge
X
X
Unknown
/
/
BCVTree
Unknown
X
BCETree
X
X
X
/
Unknown
/
/
Ref. Theorem
3.1
C.12
C.13
3.2
C.16
4.1
4.2,
4.3
4.6
Time
11 11-- mm
Y2 Y
YO(re +-))
vo(re m))
Y1"
Y2"
Space'
17"
n2.
tion procedure. We first prove that as a special case, the Shortest Path Distance WL (SPD-WL) is expressive for all bigneeiconnettivitty problems, thus providing a novel understanding of its empiri- cal success. However, it still cannot identify cut vertices. We further suggest an alternative called the Resistance Distance WL (RD-WL) for pertex-biconnectivit To sum up, all biconnectivity problems can be provably solved within our proposed GD-WI. framework.
Practical Implementation. The main advantage of GD-WI. lies in its simplicity, efficiency and parallelizabiliiy. We show it can be easily implemented using Transformer-like architecture by injecting the distance into Multi-head Attention (Vaswani et al., 2017), similar to Ying et al. (202 Importantly, we prove that the resulting Graph Transformer (called Graphormer-GDD is as expressive as GD-WL. This offers strong theoretical insights into the power and limits Graph Transformers. Empirically, we show Graphormer-GDD not only achieves perfect accuracy in detecting cut vertices and cut edges, but also outperforms prior GNN achitectures on popular benchmark datasets.
2 PRELIMINARY
Notations. We use } to denote sets and use {f } to denote multisets. The cardinality of (multi)set S is denoted (S]. The index set is denoted as [n] == f1....,m) .n). Throughout this paper, consider simple undirected graphs G = (V,E) with no repeated edges or self-loops. Therefore, each edge (u, v) & can be expressed a of elements. For node E V, denote its neighbors as Na(u)) == {rr E V {u, v} E E} and denote its degree as dega(u) = [Wa(u)]. A path P = (ug.-. ... ua) is a tuple of nodes satisfying {u-11, 3 E E for all [d]. and its length is denoted as PP| == d. A path P is said to be simple if it does not go through a node more than once, i.c. u, f ú, for of j. The shortest path distance between two nodes and is denoted be disa(u, (u, v) == min [ P is a path from u to w). The induced subgraph with vertex subset S C V defined as G[S] (S, Es) where Es- == ffu, e) E : u, U.U E S).
We next introduce the concepts of connectivity, vertex- biconnectivity and edge- seaee--cconnetviit... Definition 2.1. (Connectivity)
graph G connected if for any two nodes u, u E V, there is a path from u to A vertex set S C V is connected component of G if G[S] is connected and for any proper superset T T22 S, G[T] is disconnected. Denote CC(G) as the set of all connected com- ponents, then CC(G) forms partition of the vertex set V. Clearly, G connected iff |CC(G) = 1. Definition 2.2. (Biconnectivityy A node v E V is a cul vertex (or articulation point) of G if re- moving v increases the number of connected components, i... |CC[G[V) {v]]) > (CC(G)). A graph is vertex- vertex-hicomneeted component of if GJS) certex-biconnectte and for any proper super- set T 2 S, G(T) is not vertex-bicon cuttex-biconnected. We can similarly define the concepts of cut edge (or bridge) and adge-biconnected component (we omit them for brevity). Finally, denote BCCV (G) (resp. BCCF(G)) as the set of all vertex- biconneeddd (resp. edge- biconneeed))) components.
if it is connected and does not have any cut vertex. A vertex set S C V
Two adjaadjacent nodes u, v E V are in the same vertex vertex- biconnected component iff there are two paths from u to e that do not intersect (except at endpoints). Two nodes u, u are in the same edge- biconnected component iff there are two paths from u to e that do not share an edge, On the other components, any path between them
hand, if two nodes are in different catte//edgebbcconnedd
'The space complexity of WI. algorithms may differ from the corresponding GNN models in training, e.g. for WT- and GD-WL., due the need to store intermediate results for hack-propagation.
3

---

Published as a conference paper at ICLR 2023
must go through some cut vertex/edge. Therefore, cut vertices/edges can be regarded as "hubs" in a graph that link different subgraphs into a whole. Furthermore, the link between cut vertices/edges and biconnected components forms a tree structure, which are called the block cut tree (ef. Figure I).
Definition 2.3. (Block cut-edge tree) The block cut-edge tree of graph G (V,E) is defined as follows: BCETTree(G) (BCC (G), E where
E == (() S1, S2 E BCC (G), 3u E S1, U. E S2, s.t. {u, v) E E
Definition 2.4. (Block cut-vertex tree) The block cut-vertex tree of graph G = (V.E) is defined as follows: BCVTTee((G) := (BCC (G) U yout, ) where yCut C V is the set containing all cut vertices of G and
gx : [[S,e} S CCC)(G), E yCur , WES].
The following theorem shows that all concepts related to biconnectivity can be efficiently computed. Theorem 2.5. (Tarjan, 1972) The problems related to biconnectivity, including identifying all cut vertices/edges, finding all biconnected components (BCC) (G) and BCC and building block trees (BCVTTree(C) G) and BCETree (G)) can all be solved using the Depth-First Search algo- rithm, within a computation complexity linear in the graph size, i.e. O(1] + (E)).
Isomorphism and color refinement algorithms. Two graphs G = (Va, Ec) and H = (VH, Eh) are isomorphic (denoted as G = H)) if there is an isomorphism (bijective mapping) f : VG - VH E Va. {u,v} E &a iff f()), E εµ. A color refinement
such that for any nodes algorithm is an algorithm that outputs a color mapping XG VV + C when taking graph G as input, where C is called the color set. A valid color refinement algorithm must preserve invariance under isomorphism, i.e., Xc(u)= = (J)) for isomorphism ʃ and node u E Vc. As a result, it can be used necessary test for graph isomorphism by comparing the multisets ((xo(u): {xH(")= : u E VHl Bb. which we call the graph representations. Similarly, Xa(u) can be seen as the node feature of u Vo. and (xc(u), XG (x)) corresponds the edge feature of {u, v} Eg. All algorithms studied in this paper fit the color refinement framework, and please refer to Appendix B for a precise description of several representatives (e.g., the classic 1-WL and FWF algorithms).
VaB B and
Problem setup. This paper focuses on the following three types of problems with increasing diffi- culties. Firstly, we say a color refinement algorithm can distinguish whether a graph vertex/edge- biconnected, if for any graphs G, H where G is representations are different, i.e. (xa(u)= : u E V3 * (x)(())= u E Vи B- Secondly, we say a color refinement algorithm can identify cut vertices if for any graphs G, H and nodes u E Va, v E VH where u is a cut vertex but v is not, their node features are different, i.c. Xa(u) * (H Similarly, it can identify cut edges if for any {u, o} E EG and {w,x} } E EH where {u, v) is cut edge but (w, x} is not, their edge features are different, i.e. ffxa(u) (w). xa(u)) + distinguish block cut-vertex/edge trees, if for any
biconnected but H is not, their graph
XH (x) B-
Finally, we say a color refinement algorithm graphs G, H satisfying BCVTree (G) &e BCVTree( H)) (or BCETree(G) & BCETree( H)), their graph representations are different, i.e. (xa(u)) E Voll # (xn(u): : u E Vn
INVESTIGATING KNOWN GNN ARCHITECTURES VIA BICONNECTIVITY
In this section, we provide a comprehensive investigation of popular GNN variants in literature, including the classic MPNNs, Graph Substructure Networks (GSN) (Bouritsas et al., 2022) and its variant (Barceló et al., 2021), GNN with lifting transformations (MPSN and CWN) (Bodnar al., 2021b;a), GraphSNN (Wijesinghe & Wang, 2022), and Subgraph GNNs (e.g.. Bevilacqua et al. (2022)). Surprisingly, we find most of these works are not expressive for any biconnectivity prob- lems listed above. The only exceptions are the ESAN (Bevilacqua et al., 2022) and several variants, where we give rigorous justification of their expressive power for both vertex/edge-bicomecciin biconnectivity.
3.1 COUNTEREXAMPLES
1-WL/MPNNs. We first consider the classic 1-WL. We provide two principled class of counterex- amples which are formally defined in Examples C.9 and C.10, with a few special cases illustrated in Figure 2. For each pair of graphs in Figure 2, the color of each node is drawn according to the 1-WL color mapping. It can be seen that the two graph representations are the same. Therefore, 1-WL cannot distinguish any biconnectivity problem listed in Section 2.
4

---

Published as a conference paper at ICLR 2023
(a)
(b)
(c)
(d)
Figure 2: Illustration of four representative counterexamples (see Examples C.9 and C.10 for general
definitions). Graphs the first row have cut vertices (outlined bold red) and some also have cut edges (denoted as red lines), while graphs in the second row do not have any cut vertex cut edge.
Substructure Counting WL/GSN. Bouritsas et al. (2022) developed principled approach to boost the expressiveness of MPNNS by incorporating substructure counts into node features or the 1- WL aggregation procedure. The resulting algorithm, which we call the SC-WL, is detailed in Ap- pendix B.3. However, we show no matter what sub-structures are used, the corresponding GSN still cannot solve any biconnectivity problem listed in Section 2. We give proof in Appendix C.2 for the general case that allows arbitrary substructures, based on Examples C.9 and C.10. We also point that negative result applies to the similar GNN variant in Barceló et al. (2021).
Theorem 3.1. Let H {H1,... ........ H&). H; (V,, E,) be any set of connected graphs and denote max [Pl. Then SC-WL (Appendix B.3) using the substructure set cannot solve any problem listed in Section 2. Moreover, there exist counterexample graphs whose sizes (both in terms of vertices and edges) are (n).
GNNs with lifting transformations (MPSN/CWN), Bodnar al. (2021b;a) considered another approach to design powerful GNNs by using graph lifting transformations. In a nutshell, these ap- proaches exploit higher-order graph structures such as cliques and cycles to design new WL aggre- gation procedures. Unfortunately, we show the resulting algorithms, called the SWL and CWL, still cannot solve any biconnectivity problem. Please Appendix C.2 (Proposition C.12) for details.
Other GNN variants. In Appendix C.2, we discuss other recently proposed GNNs, such as Graph- SNN (Wijesinghe & Wang, 2022), GNN-AK (Zhao al., 2022), and NGNN (Zhang & Li, 2021). Due to space limit, we defer the corresponding negative results Propositions C.13, C.15 and C.16.
3.2 PROVABLE EXPRESSIVENESS OF ESAN AND DSS-W WL.
We next switch our attention to new type of GNN framework proposed in Bevilacqua al. (2022), called the Equivariant Subgraph Aggregation Networks (ESAN). The central algorithm in EASN is called the DSS-WD WL. Given a graph G, DSS- WL first generates a bag of vertex-she shared (sub)graphs B3 G ... Gm Bt according to graph generation policy и. Then in each iteration f, the algorithm refines the color of each node in each subgraph G, by jointly aggregating neighboring colors in the own subgraph and across all subgraphs. The aggregation formula can be written as:
XG, (v) hash (Xa, (v), Hxa. (u) : e No, (v)B. Xo (v), (x) NG(u))),
(1)
(v(v) == hash (fxx, (v) : [m]}),
(2)
where hash perfect hash function. DSS-WL terminates when X induces stable vertex parti- tion. In this paper, we consider node-based graph generation policies, for which each subgraph is associated to a specific node, i.e. B HG, AND, node marking TNM. d-ego-networrk TEGO(K): and its node marking version TEGOM(K)- A full description of DSS-WIL WI as well as different policies can found Appendix B.4 (Algorithm 3).
VB. Some popular choices are node deletion
A fundamental question regarding DSS-WL is how expressive it is. While straightforward analysis shows that DSS-WI WL is strictly more powerful than 1-WL, an in in-depth understanding on what addi- tional power DSS-WI, gains over 1-WL is still limited. The only new result is the very recent work of Frasca et al. (2022), who showed 3- 3-WL upper bound for the expressivity of DSS- WL. Yet, such result actually gives limitation of DSS-WT WL rather than showing its power. Moreover, there is large gap between the highly strong 3- WL and the weak 1-L In the following, we take a different perspective and prove that DL. is expressive for both types of biconnectivity problems.
5

---

Published as a conference paper at ICLR 2023
Theorem 3.2. Let G (Ve,EG) and H CH) be two graphs, and let XG and Xи be the corresponding DSS- WL color mapping with node marking policy. Then the following holds:
VG and VH. if xa(w)) = xH( (2), then is cut vertex if and only if x is a cut vertex.
For any two nodes
For any two edges {wi, W2} E Eg and [2) E Ed. if Xxa((r).xxcwx)) (xH(z1), X (x2) B. then {wi, w2} is a cut edge if and only if (x1, F2) is a cut edge.
The proof of Theorem 3.2 highly technical and is deferred to Appendix C.3. By using the basic results derived in Appendix C.I. we conduct a careful analysis of the DSS-WL color mapping and discover several important properties. They give insights on why DSS-WL can succeed in distin- will discuss below.
guishing biconnectivity,
How can DSS- WL distinguish biconnectivity? We find that a crucial advantage of DSS-WL over the classic 1-WL is that DSS-WL color mapping implicitly encodes distance information (see Lemma C. C.19(e 19)) and Corollary C.24). For example, two nodes u E VG, u E Vn will have dif- ferent DSS-WL. colors if the distance set ([diso (u, w) w E VG differs from ([dis (v, w) : w E VH B. Our proof highlights that distance information plays a vital role in distinguishing edge- biconnectivity when combining with color refinement algorithms (detailed in Section 4), and also helps distinguish vertex-biconee biftn--biconnectviiyy (see the proof of Lemma C.22). Consequently, our analysis provides a novel understanding and strong justification for the success of DSS-WL WL in two aspects: the graph representation computed by DSS-WL intrinsically encodes distance and biconnectivity information, both of which are fundamental structural properties of graphs but are lacking in I-WL.
Discussions on graph generation policies. Note that Theorem 3.2 holds for node marking policy. In fact, the ability of DSS-W/ WL to encode distance information heavily relies on node marking as shown in the proof of Lemma C.19. In contrast, prove that the ego-network policy TEGO(K) cannot distinguish cut vertices (Proposition C.14), using the counterexample given in Figure 2(c). Therefore, our result shows inherent advantage of node marking than the ego-network policy in distinguishing a class of non-isomorphic graphs, which is raised as an open question in Bevilacqua et al. (2022, Section 5). It also highlights theoretical limitation of TFGo(K) compared with its node marking version TBGOM(*). a subtle difference that may not have received sufficient attention yet. For example, both the GNN-AK and GNN-AK-etx architecture (Zhao et al., 2022) cannot solve vertex- biconnectivity problems since it is similar to TEGO(K) (see Proposition C.15). On the other hand, the GNN-AK+ does not suffer from such a drawback although it also uses TEGO())) because it further adds distance encoding in each subgraph (which is more expressive than node marking).
Discussions on DS-WL. Bevilacqua et al. (2022); Cotta et al. (2021) also considered a weaker ver- sion of DSL called the DS-WL, which aggregates the node color in each subgraph without interaction across different subgraphs (see formula (10)). We show Proposition C.16 that unfor- tunately, DS-WI. with common node-based policies cannot identify cut vertices when the color of each node is defined as its associated subgraph representation G This theoretically reveals the importance of cross-graph aggregation and justifies the design of DSS-WL. Finally, we point out that Qian et al. (2022) very recently proposed an extension of DS-WL that adds a final tross-graph aggregation procedure, for which our negative result may not hold. It may be interesting direction to theoretically analyze the expressiveness of this type of DS-WL in future work.
4 GENERALIZED DISTANCE WEISFEILER-LEHMAS TEST
After an extensive review of prior GNN architectures, in this section we would like to formally study the following problem: can we design a principled and efficient GNN framework with provable ex- pressiveness for biconnectivity? In fact, while Section 3.2 we have proved that DSS-WL can solve biconnectivity problems, it is still far from enough. Firstly, the corresponding GNNs based on DSS-WL is usually sophisticated due to the complex aggregation formula (I), which inspires us to study whether simpler architectures exist. More importantly, DSS-WL suffers from high computa- tional costs in both time and memory. Indeed, it requires (n²2) space and e (nm) time per iteration (using policy TNM) compute node colors for graph with nodes and m edges, which is times costly than L-W.. Given the theoretical linear lower bound in Theorem 2.5, one may naturally raise the question of how to close the gap by developing more efficient color refinement algorithms.

---

Published as a conference paper at ICLR 2023
We approach the problem by rethinking the classic 1-WL test. We argue that major weakness of 1-WL is that it is agnostic to distance information between nodes, partly because each node can only "see" its neighbors in aggregation. On the other hand, the DSS-WL color mapping implicitly encodes distance information as shown in Section 3.2, which inspires us to formally study whether incorporating distance in the aggregation procedure is crucial for solving biconnectivity problems. To this end, we introduce a novel color refinement framework which we call Generalized Distance Weisfeiler-Lehman (GD-WL). The update rule of GD-WL very simple and can be written as:
(c( == hash (f (do((v u), XG (u)) : E VB)
where de can be an arbitrary distance metric. The full algorithm is described in Algorithm 4.
SPD-WL for edge-biconnecttvity. As special case, when choosing the shortest path distance
dg = disc, we obtain an algorithm which we call SPD-WL. It can be equivalently written as
xc(v) (v) := hash (xaa (v), Xxx
: u (v) fx (u) disa(v, u) = =BB,
(4)
#xxe (w) disg u) - n- BB
: (1, u) = oo))
From (4) it is clear that SPD-WL is strictly more powerful than I-WL since it additionally aggre- gates the k-hop neighbors for all A > 1. There have been several prior works related to SPD-WL, including using distance encoding as node features (Li et al., 2020) or performing h-hop aggrega- tion for some small & (see Appendix D.2 for more related works and discussions). Yet, these works either purely empirical or provide limited theoretical analysis (e.g., by focusing only on regular graphs). Instead, we introduce the general and more expressive SPD-WI. framework with a rather different motivation and perform a systematic study on its expressive power. Our key result confirms that SPD-WL is fully expressive for all cdge-biconnectivity problems listed in Section? 2.
Theorem 4.1. Let G EVe,Eg) and H (Vn, En) be two graphs, and let XG and Xu be the corresponding SPD-WL color mapping. Then the the following holds:
Foor any two edges {wi, W2] E EG and [2 E Eg. if Hxc(w1),xccws)) (xH()1) Xa (x2) B. then {W1, w2} is a cut edge if and only if (æ1, x2] is cut edge. If w E V&B = Hxx(w) : w E VH B. then BCETree(G) BC))
Theorem 4.1 is highly non-trivial and perhaps surprising at first sight, as it combines three scemingly unrelated concepts (i.c., SPD, biconnectivity, and the WL test) into unified conclusion. We give a proof in Appendix C.4, which separately considers two cases: X Xw(w) # x x<(w)) and XG xc(w)) Xa (w2) (see Figure 2(b,d) for examples). For each case, the key technique in the proof is to construct an auxiliary graph (Definitions C.26 and C.34) that precisely characterizes the structural relationship between nodes that have specific colors (see Corollaries C.31 and C.40). Finally, we highlight that the second item of Theorem 4.1 may be particularly interesting: while distinguishing general non- isomorphic graphs are known to be hard (Cai et al., 1992; Babai, 2016). we show distinguishing non-isomorphic graphs with different block cut-edge trees can be much easily solved by SPD-WL.
RD-WL for vertex- bintnetbiconntttivity.. Unfortunately, while SPD-WL is fully expressive for edge- biconnectivity, not expressive for vertex- bicrneeticonettiiiity.. We give a simple counterexample in Figure 2(c), where SPD-WL cannot distinguish the two graphs. Nevertheless, we find that by using a different distance metric, problems related to vertex-biconnectiviin can also be fully solved. We propose such a choice called the Resistance Distance (RD) (denoted as g) Like SPD, RD is also basic metric in graph theory (Doyle & Snell, 1984; Klein & Randić, 1993) and has been widely used to characterize the relationship between nodes (Sanmartin et al., 2022; Velingker et al., 2022). Formally, the value of (u, v) is defined to be the effective resistance between nodes u and v when treating G an electrical network where each edge corresponds to a resistance of one ohm.
RD has many elegant properties. First, it is a valid metric: indeed, RD is non-negative, semidefinite, symmetric, and satisfies the triangular incquality (see Appendix E.2). Morcover, similar to SPD, R (u, 1, and dis (u. v) = disg (u, v) if G is a tree. In Appendix E.2,
we also have 0 I dis u, v) we further show that RD is highly related to the graph Laplacian and can be efficiently calculated.
Theorem 4.2. Let G = (Ve, and H (Vn, Eu) be two graphs, and let xG and Xи be the corresponding RD-WL color mapping. Then the following holds:
For any two nodes w VG and Vn. if xx((w)= = xu(x)) (x), then is cut vertex if and only if x is a cut vertex.
If (w)) : w Voll = (w)( : w E VnB. then BCVTree(G) = BCVTree(F) (H).
7

---

Published as a conference paper at ICLR 2023
The form of Theorem 4.2 exactly parallels Theorem 4.1, which shows that RD-WL is fully expres- sive for bitexxbbconneetivitty We give proof of Theorem 4.1 in Appendix C.3. In particular, the proof of the second item is highly technical due to the challenges in analyzing the (complex) struc- ture of the block cut-vertex tree. It also highlights that distinguishing non-isomorphic graphs that have different BCVTrees is much easier than the general case.
Combining Theorems 4.1 and 4.2 immediately yields the following corollary, showing that all bi- connectivity problems can be solved within our proposed GD-WL framework.
Corollary 4.3. When using both SPD and RD (i.e., by setting da(u, v) := (disa (u, v), disg (u, v))), the corresponding GD-WL is fully expressive for both bertex-biconneclivity and edge-bicommectivity
Computational cost. The GD-WL framework only needs a complexity of ((n) space and (n²²) time per-iteration for a graph of n nodes and m edges, both of which are strictly less than DSS-WI In particular, GD-WL has the same space complexity as 1-WL, which can be crucial for large-scale tasks. On the other hand, one may ask how much computational overhead there is in preprocessing pairwise distances between nodes. We show in Appendix E that the computational cost can be trivially upper bounded by ((n)) for SPD and (nn)) for RD. Note that the preprocessing step only needs to be executed once, and we find that the cost is negligible compared to the GNN architecture.
Practical implementation. One of the main advantages of GD-WL is its high degree of paralleliz- ability. In particular, we find GD-WL can be easily implemented using a Transformer-lik architec- ture by injecting distance information into Multi-head Attention (Vaswani et al., 2017), similar to the structural encoding in Graphormer (Ying et al., 2021a). The attention layer can be written as:
Y = [ (D) ④ softmax (X (XW)) T + 22 (D)) XW
(5)
where X E R is the input node features of the previous layer, D E Rox" is the distance matrix such that Duv du v). W W W Rddd are learnable weight matrices of the h-th head, of and di are elementwise functions applied to D (possibly parameterized), and @ denotes the elementwise multiplication. The results Y Ruxdd across all heads h are then combined and projected to obtain the final output Y = Σn Y Y where W E Rdd xd We call the resulting architecture Graphormer- GD, and the full structure of Graphormer- is provided in Appendix E.3.
It is easy to see that the mapping from X to Y in (5) is equivariant and simulates the GD-WL aggregation. Importantly, we have the following expressivity result, which precisely characterizes the power and limits of Graphormer-Gil We give a proof in Appendix E.3.
Theorem 4.4. Graphormer-Gre GD is at most as powerful as GD-WI. in distinguishing non-isomorphic graphs. Moreover, when choosing proper functions ot and db and using a sufficiently large number of heads and layers, Graphormer-GB is as powerful as GD-WL.
On the expressivity upper bound of GD-WL. To complete the theoretical analysis, we finally provide an upper bound of the expressive power for our proposed SPD-WL and RD-WL. by studying the relationship with the standard 2-FWL (3-WL) algorithm.
Theorem 4.5. The 2-FWL algorithm is more powerful than both SPD- WL and RD-WL. Formally, the 2-FWI. color mapping induces a finer vertex partition than that of both SPD-WL and RD-WI.
We give proof in Appendix C.6. Using Theorem 4.5, we arrive at the concluding corollary: Corollary 4.6. The 2-FWL is fully expressive for both verreex-iiconnectvvc and edge-biccomecctvityy
5 EXPERIMENTS
In this section, we perform empirical evaluations of our proposed Graphormer-Gi. We mainly con- sider the following two sets of experiments. Firstly, we would like to verify whether Graphormer- GD can indeed learn biconneetivity-relate metrics casily as our theory predicts. Secondly, we would like investigate whether GNNs with sufficient expressiveness for biconnectivity can also help real-world tasks and benefit the generalization performance as well. The code and models will be made publicly available at https: hiithub.. com/ls /2408/ Grrapharrerrrrraa
Synthetic tasks. To test the expressive power of GNNs for biconnectivity metrics, we separately consider two tasks: (1) Cut Vertex Detection and (ii) Cut Edge Detection. Given GNN model
8

---

Published as a conference paper at ICLR 2023
that outputs node features, add learnable prediction head that takes each node feature (or two node features corresponding to each edge) as input and predicts whether it is a cut vertex (cut edge) or not. The evaluation metric for both tasks is the graph-level accuracy, i.c., given a graph, the model prediction is considered correct only when all the cut vertices/edges are correctly identified. construct challenging dataset that comprises various types of
To make the results convincing, hard graphs, including the regular graphs with cut vertices/edges and also Examples C.9 and C.10 mentioned in Section 3. We also choose several GNN baselines with different levels of expres- sive power: (i) classic MPNNs (Kipf & Welling, 2017; Veličković et al., 2018; Xu et al., 2019); (ii) Graph Substructure Network (Bouritsas al., 2022); (iii) Graphormer (Ying et al., 2021a). The details of model configurations, dataset, and training procedure are provided in Appendix F.I.
The results are presented in Table 2. It can be seen that baseline GNNs can- not perfectly solve these synthetic tasks. In contrast, the Graphormer-GD achieves 100% accuracy on both tasks, implying that it can easily learn biconnectivity met- rics even in very difficult graphs. More- over, while using only SPD suffices identify cut edges, it is still necessary to further incorporate RD identify cut ver- tices. This is consistent with our theoreti- cal results in Theorems 4. 4.2 and 4.4.
Table 2: Accuracy on cut vertex (articulation point) and cut edge (bridge) detection tasks.
Cut Vertex Detection
Cut Edge Delection
Model
GCN (Kipl & Welling, 2017)
31.5%.11..%
62.4%.11.88
GAT (Veličković et al., 2018)
52.0%
62.8%.11.99
GIN (Xu et al., 2019)
53.9%++1.7%
63.1%++2.2%%
GSN (Bouritsas et al., 2022)
60.1%++1..9%
70.7%++-2. 1.1%
Graphonmer (Ying et al., 202
76.4%
84.5%.13.3%
Graphomeer-GD (ours)
100%
100%
w/o. Resistance Distance
83.3%+22.799
100%
Real-world tasks. We further study the empirical performance of our Graphormer-GD on the real- world benchmark: ZINC from Benchmarking GNNs (Dwivedi et al., 2020). To show the scalability of Graphormer- GD, we train our models on both ZINC-Full (consisting of 250K molecular graphs) and ZINC-Subset (12K selected graphs). We comprehensively compare our model with prior ex- pressive GNNs that have been publicly released. For a fair comparison, we ensure that the parameter budget of both Graphormer- GD and other compared models are around 500K, following Dwivedi et al. (2020). Details of baselines and settings are presented in Appendix F.2.
The results are shown in Table 3, where our score is averaged over four experiments with differ- ent seeds. We also list the per-epoch training time of different models ZINC-subset well as their model parameters. It can be seen that Graphormer- GD surpasses or matches all compet- itive baselines the test of both ZINC-Subset and ZINC-FulI. Furthermore, we find that the empirical performance of compared models align with their expressive power measured by graph biconnectivity. For example, Subgraph GNNs that are expressive for biconnectivity also consistently outperform classic MPNNs by a large margin. Compared with Subgraph GNNs, the main advan- tage of Graphormer-Gi is that is simpler to implement, has stronger parallelizability, while still achieving better performance. Therefore, we believe our proposed architecture is both effective and efficient and can be well extended to more practical scenarios like drug discovery.
6 CONCLUSION
In this paper, we systematically investigate the expressive power of GNNs via the perspective of graph biconnectivity. Through the novel lens, we gain strong theoretical insights into the power and limits of existing popular GNNs. We then introduce the principled GD-WL framework that is fully expressive for all biconnectivity metrics. We further design the Graphormer-GD architecture that is provably powerful while enjoying practical efficiency and parallelizability. Experiments on both synthetic and weal-world datasets demonstrate the effectiveness of Graphormer-Gr
There are still many promising directions that have not yet been explored. Firstly, it remains an important open problem whether biconnectivity can be solved more efficiently in o(n?) time using equivariant GNNs. Secondly, a deep understanding of GD-WL. is generally lacking. For example, we conjecture that RD-WL can encode graph spectral (Lim et al., 2022) and is strictly more powerful than SPD-WL in distinguishing general graphs. Thirdly, it may be interesting to further investigate more expressive distance (structural) encoding schemes beyond RD-WI and explore how to encode them in Graph Transformers. Finally, one can extend biconnectivity to a hierarchy of higher-order variants (e.g., trinconnectivity). which provides a completely different view parallel to the WL hier- archy study the expressive power and guide designing provably powerful GNNs architectures.
9

---

Published as a conference paper at ICLR 2023
Table 3: Mean Absolute Error (MAE) on ZINC test set. Following Dwivedi et al. (2020), the
parameter budget of compared models is set to 500k. We use to indicate the best performance.
Test MAE
Method
Model
Time (s)
Params
ZINC-Subset
ZINC-Full
GIN (Xu et al., 2019)
8.05
509,549
0.526110.051
0.088.10.002
GraphSAGE (Hamilton et al., 2017)
6,02
505,341
0.398110.002
0.126:10.003
GAT (Veličković et al., 2018)
8.28
531,345
0.384+00.007
0.111+00002
MPNNs
GCN (Kipl & Welling, 2017)
5.85
505,079
0.367:10.01
0.113:10.002
MoNet (Monti al., 2017)
7.19
504,013
0.292110.006
0.090110.002
BAnedGGCN-P((Breseee MPNN(sum) (Gilmer et al., 2017)
& Laurent, 2017)
10.74
505,011
0.214++0.006
480,805
0.145:+:0.00
PNA (Corso et al., 2020)
387,155
0. 0.14000.010
Higher-order GNNs
RingGNN (Chen et al., 2019)
178.03
527,283
0.353-10.019
3WLGNN (Maron et al., 2019a)
179.35
507,603
0.303=20.008
Substructure-
GSN (Bouritsas al., 2022)
5000
001000000010
hased GNNs
IN-lmall (Bodnar et al., 202
1000
0.004++0.004
0.044+0.003
NGNN (Zhang & Li, 2021)
~500k
0.11 1.111=0.005
0.029=0.001
DSS-GNN (Bevilacqua et al., 2022)
445,709
0.097:10.006
Suhgraph GNNs
GNN-AK (Zhao ct al., 2022)
~5500k
0.105
GNN-AK+ (Zhao et al., 2022)
~550k
0.091+00001
SUN (Frusca al., 2022)
15.04
526,489
0.083:10.003
GT (Dwivedi & Bresson, 2021)
588,929
0.206:10.014
Graph
SAN (Kreuzer et al., 2021)
508,577
0.139:10.006
Transforners
Graphormer (Ying al., 2021a)
12.26
489,321
0.122++0.006
0.052+0.005
URPE (Luo al., 2022h)
12.40
491,737
0.006
0.028++0.002
GD-WL
Graphormer- GD (ours)
12.52
502,793
0.081
0.02510..00
ACKNOWLEDGMENTS
Bohang Zhang grateful Ruichen Li for his great help in discussing and checking several of the main results in this paper, including Theorems 3.1, 3.2, 4.1 and C.58. In particular, after the initial submission, Ruichen Li discovered simpler proof of Lemma C.28 and helped complete the proof of Theorem C.58. Bohang Zhang would also thank Yiheng Du, Kai Yang amd Ruichen Li for correct- ing some small mistakes in the proof of Lemmas C.20 and C.45. We also thank all the anonymous reviewers for the careful reviews and the valuable suggestions. Their help has further enhanced our work. This work is supported by National Key R&D Program of China (2022ZD01 and National Science Foundation of China (NSFC62276005).
REFERENCES
Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth Inter- national Joint Conference Artificial Intelligence, IJCAI-21, pp. 1112-2118, 2021.
Ralph Abboud, Radoslav Dimitrov, and Ismail IIkan Ceylan. Shortest path networks for graph property prediction. In The First Learning on Graphs Conference, 2022.
Robert Ackland et al. Mapping the us political blogosphere: Are conservative bloggers more promi- nent? In Blog Downunder 2005 Conference, Sydney. BlogTalk Downunder 2005 Conference, Sydney, 2005.
Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-233 1997.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sci- ences, 11::2--9,, 2020.
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural net- works. In International Conference on Learning Representations, 2021.
10

---

Published as a conference paper at ICLR 2023
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
László Babai. Graph isomorphism in quasipolynomial time. In Proceedings of the forty-eighth annual ACM symposium Theory of Computing, pp. 684-697, 2016.
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 on Machine Learning, pp. 608. PMLR, 2021.
Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. In Advances in Neural Information Processing Systems, volume 34, pp- 25280-25293, 2021.
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.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montufar, and Michael M. Bronstein. Weisfeiler and lehman go cellular: CW networks. In Advances in Neural Information Processing Systems, volume 34, 2021a
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In International Conference on Machine Learning, pp. 1026-1037. PMLR, 2021b.
Béla Bollobás. Modern graph theory, volume 184. Springer Science & Business Media, 1998.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P 7afeirio, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Xavier Bresson and Thomas Laurent. arXiv:1711.07553, 2017.
Residual gated graph convnets.
arXiv preprint
Jin-Yi Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, (2(4):3894410 1992.
Ashok K Chandra, Prabhakar Raghavan, Walter Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of graph captures its commute and cover times. computational com- plexity, 6(4):312-340, 1996.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count sub- structures? Proceedings of the 34th International Conference on Neural Information Process- ing Systems, pp. 10383-10395 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33: 33:13260-13271 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.
Pim de Haan, Taco Cohen, and Max Welling, Natural graph networks. In Proceedings of the 34th International Conference Neural Information Processing Systems, volume 33, pp. 3636-3646, 2020.
Peter Doyle and J Laurie Snell. Random walks and electric networks, volume 22. American Mathematical Soc., 1984.
11

---

Published as a conference paper at ICLR 2023
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint 2rX11:2003.00098, 2020.
Or Feldman, Amit Boyarski, Shai Feldman, Dani Kogan, Avi Mendelson, and Chaim Baskin. We- isfeiler and leman go infinite: Spectral and combinatorial pre-colorings. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022.
Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. arXiv preprint arXiv:2205.1333333 2022.
Robert W Floyd. Algorithm 97: shortest path. Communications of the ACM, 5(6):345, 1962.
Fabrizio Frasca, Beatrice Bevilacqua, Michael Bronstein, and Haggai Maron. Understanding and extending subgraph gnns by rethinking their symmetries. arXiv preprint arXiiv2206.111140) 2022.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pp. 3419-3430. PMLR, 2020.
Floris Geerts and Juan Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2022.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Frieda Granot and Arthur F Veinott Jr. Substitutes, complements and ripples in network flows. Mathematics of Operations Research, 10(3):471-497, 1985.
Ivan Gutman and W Xiao. Generalized inverse of the laplacian matrix and some applications. Bul- letin (Académie serbe des sciences el des arts. Classe des sciences mathématiques et naturelles. Sciences mathématiques), pp. 15-23, 2004.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31 International Conference on Neural Information Processing Systems, volume 30, pp. 1025-1035, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and patlern recognition, pp- 770-778, 2016.
John E Hoperoft and Robert Endre Tarjan. Isomorphism of planar graphs. In Complexity of computer computations, pp. 131-152. Springer, 1972.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borg- wardt. Topological graph neural networks. In International Conference on Learning Representa- tions, 2022.
Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. Boosting the cycle counting power of graph neural networks with 2S-GNN.. In International Conference Learning Represen- tations, 2023.
Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. In Complexity theory retrospective, pp. 59-81. Springer, 1990.
Sanjiv Kapoor and Hariharan Ramesh. Algorithms for enumerating all spanning trees of undirected and weighted graphs. SIAM Journal on Computing. 24(2):247-265. 1995.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 7092-7101, 2019.
12

---

Published as a conference paper at ICLR 2023
Sandra Kiefer. Power and limits the Weisfeiler-Leman algorithm. PhD thesis, Dissertation, RWTH Aachen University, 2020.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14t216482, 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Douglas J Klein and Milan Randić. Resistance distance. Journal of mathematical chemistry, 12(1): 81-95, 1993.
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.
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. 1465-4475 2020.
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202. 13011 2022.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Con- ference on Learning Representations, 2020.
Shengjie Luo, Tianlang Chen, Yixian Xu, Shuxin Zheng, Tie- Yan Liu, Liwei Wang, and Di He. One transformer can understand both 2d & 3d molecular data. arXiv preprint 10.01222, 2022a.
Shengjie Luo, Shanda Li, Shuxin Zheng, Tie-Yar Liu, Liwei Wang, and Di He. Your transformer may not as powerful as you expect. arXiv preprint arXiv:2205. 13401, 2022b.
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, 2019a.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019b.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference on machine learning, pp. 4363-4371. PMLR, 2019c.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 5115-5124, 2017.
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 the
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. 21824-21840, 2020.
Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprint arXiv:21 12..2.2..999999 2021.
Christopher Morris, Gaurav Rattan, Sandra Kiefer, and Siamak Ravanbakhsh. Speqnets: Sparsity- aware permutation permutation-eqqiiarian graph networks. In International Conference on Machine Leam- ing, pp. 16017-16042. PMLR, 2022.
13

---

Published as a conference paper at ICLR 2023
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673. PMLR. 2019.
Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network exten- sions. arXiv preprint arXiv:2201. 12884, 2022.
Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: random dropouts increase the expressiveness of graph neural networks. In Advances Neural Infor- mation Processing Systems, volume 34, pp. 21997-22009, 2021.
Chendi Qian, Gaurav Rattan, Floris Geerts, Christopher Morris, and Mathias Niepert. Ordered subgraph aggregation networks. arXiv preprint arXiv:2206. 11168, 2022.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 385-394, 2017.
Enrique Fita Sanmartun, Sebastian Damrich, and Fred Hamprecht. The algebraic path problem for graph metries. In International Conference on Machine Learning, pp. 19178-19204. PMLR, 2022.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.0400 04077 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Proceedings of the 33rd International Conference Neural Information Processing Systems, pp. 4081-4090, 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp.
SIAM, 2021.
Bernhard Scholkopf, Kah-Kay Sung, Christopher JC Burges, Federico Girosi, Partha Niyogi, Tomaso Poggio, and Vladimir Vapnik. Comparing support vector machines with gaussian kernels to radial basis function classifiers. IEEE transactions on Signal Processing, 45(11):2758-2765 1997.
Yu Shi, Shuxin Zheng, Guolin Ke, Yifei Shen, Jiacheng You, Jiyan He, Shengjie Luo, Chang Liu, Di He, and Tie Yan Liu. Benchmarking graphormer large-scale molecular modeling datasets. 2022.
arXiv preprint arXiv:2203.0443
Rajat Talak, Siyi Hu, Lisa Peng, and Luca Carlone. Neural trees for learning on graphs. In Advances in Neural Information Processing Systems, volume 34, pp. 26395-26408, 2021.
Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2): 146-160, 1972.
Erik Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism- based graph neural nets. In Advances in Neural Information Processing Systems, volume 34, pp. 29922-299342 2021.
Jan Toenshoff, Martin Ritzert, Hinrikus Wolf, and Martin Grohe. Graph learning with 1 convolu- tions on random walks. arXiv preprint arXiv:2102.08788. 2021.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M.
Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In Interna- tional Conference on Learning Representations, 2022.
Edwin R van Dam, Jack Koolen, and Hajime Tanaka. Distance-regular graphs. arXiv preprint arXiv:1410.66 6294, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, volume 30, 2017.
14

---

Published as a conference paper at ICLR 2023
Petar Veličković. Message passing all the way up. arXiv preprint arXtv:2202.11097, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Ameya Velingker, Ali Kemal Sinop, Ira Ktena, Petar Veličković, and Sreenivas Gollapudi. Affinity- aware graph networks. arXiv preprint arXiv:2206. 1941, 2022.
Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passingg In Proceedings of the 34th International Con- ference Neural Information Processing Systems, pp. 18143-14155 2020.
Boris Weisfeiler and Andrei Leman. The reduction of graph canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Asiri Wijesinghe and Qing Wang. A new perspective on" how graph neural networks go beyond weisfeiler-lehman?" In International Conference on Learning Representations, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34, 2021a.
Chengxuan Ying, Mingqi Yang, Shuxin Zheng, Guolin Ke, Shengjie Luo, Tianle Cai, Chenglin Wu, Yuxin Wang, Yanming Shen, and Di He. First place solution of kdd cup 2021 ogb large-scale challenge graph-level track. arXiv preprint arXiv:2106.08279, 2021b.
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Raphael Yuster and Uri Zwick. Finding even cycles even faster. SIAM Journal on Discrete Mathe- matics, 10(2):209-222, 1997.
Muhan Zhang and Pan Li. Nested graph neural networks. In Advances in Neural Information Processing Systems, volume 34, pp. 15734-15747, 2021.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations, 2022.
15

---

Published as a conference paper at ICLR 2023
Appendix
Table of Contents
A Recent advances in expressive GNNs
17
B The Weisfeller-Lehmarl Algorithms and Recently Proposed Variants
18
B.1
1-WL Test
18
B.2
k-FWL Test
19
with Substructure Counting (SC-WL)
B.4 Equivariant Subgraph Aggregation WL (T.)-WT.)
20
B.5 Generalized Distance WL (GD-WL)
21
C Proof of Theorems
22
C.I Properties of color refinement algorithms
22
C.2 Counterexamples
23
Proof Theorem
26
C.4 Proof of Thcorem 4.1
................................
31
C.5 Proof of Theorem 4.2
40
C.6 Proof of Theorem 4.5
45
C.7 Regarding distance-regular graphs
48
D Further Discussions with Prior Works
51
D.1 Known metrics measuring the expressive power GNNs
51
GNNs with distance encoding
E
Implementation of Generalized Distance Weisfciler-Lchman
52
E.1
Preprocessing Shortest Path Distance
53
E.2
Preprocessing Resistance Distance
53
E.3
Transformer-basel implementation
55
F Experimental Details
F.1 Synthetic Tasks
56
F2
Real-world Tasks
57
F3 More Tasks
58
F4 Efficiency Evaluation
59
16

---

Published as a conference paper at ICLR 2023
A RECENT ADVANCES IN EXPRESSIVE GNNS
Since the seminal works of Xu et al. (2019); Morris et al. (2019), extensive studies have devoted to developing new GNN architectures with better expressiveness beyond the 1-WL test. These works can be broadly classified into the following categories.
Higher-order GNNs. One straightforward way to design provably more expressive GNNs is in- spired by the higher-order WL tests (see Appendix B.2). Instead of performing node feature ag- gregation, these higher-order GNNs calculate a feature vector for each k-tuple of nodes (k 2 2) and perform aggregation between features of different tuples using tensor operations (Morris al., 2019; Maron et al., 9b;c;;; Keriven & Peyré, 2019; Azizian & Lelarge, 2021; Geerts & Reutter, 2022). In particular, Maron al. (2019a) leveraged equivariant matrix multiplication to design net- work layers that mimic the 2-FWI. aggregation. Due to the huge computational cost of higher-order GNNs, several recent works considered improving efficiency by leveraging the sparse and local na- ture of graphs and designing a "local" version of the k-WL aggregation, which comes at the cost of some expressiveness (Morris et al., 2020; 2022). The work of Vignac et al. (2020) can also be seen as local 2-order GNN and its expressive power is bounded by 3-IGN (Maron et al., 2019c).
Substructure-basee GNNs. Another way to design more expressive GNNs is inspired by studying the failure cases of 1-WL. test. In particular, Chen et al. (2020) pointed out that standard MPNNs cannot detect/count common substructures such as cycles, cliques, and paths. Based on this finding, Bouritsas et al. (2022) designed the Graph Substructure Network (GSN) by incorporating substruc- ture counting into node features using a preprocessing step. Such an approach was later extended by Barceló et al. (2021) based homomorphism counting. Bodnar et al. (2021b;a) Thiede et al. (2021); Horn et al. (2022) further developed novel WL aggregation schemes that take into account these substructures (e.g., cycles cliques). Toenshoff et al. (2021) considered using random walk techniques to generate small substructures.
Subgraph GNNs. In fact, the graphs indistinguishable by 1-WL. tend to possess high degree of symmetry (e.g.. see Figure 2). Based on this observation, a variety of recent approaches sought to break the symmetry by feeding subgraphs into an MPNN. To maintain equivariance, a set of subgraphs is generated symmetrically from the original graph using predefined policies, and the final output aggregated across all subgraphs. There have been several subgraph generation policies in prior works, such as node deletion (Cotta et al., 10, edge deletion (Bevilacqua et al., 2022), node marking (Papp & Wattenhofer, 2022). and eeo-networks (Zhao al., 2022; Zhang & Li, 2021; You et al., 2021). These works also slightly differ in the aggregation schemes. In particular, Bevilacqua et al. (2022) developed a unified framework, called ESAN, which includes per-layer aggregation across subgraphs and thus enjoys better expressiveness. Very recently, Frasca et al. (2022) further extended the framework based on a more relaxed symmetry analysis and proved an upper bound of its expressiveness to be 3-W Qian et al. (2022) provided theoretical analysis of how subgraph GNNs relate to F-FWL and also designed an approach to learn policies.
Non-equivariant GNNs. Perhaps of the simplest way to break the intrinsic symmetry of 1-WL aggregation is to use non-equivariant GNNs. Indeed, Loukas (2020) proved that if each node in a GNN is equipped with unique identifier, then standard MPNNs can already be Turing universal. There have been several works that exploit this idea to build powerful GNNs, such as using port numbering (Sato et al.. 2019), relational pooling (Murphy al., 2019), random features (Sato al., 2021; Abboud et al., 2021), or dropout techniques (Papp et al., 2021). However, since the resulting architectures cannot fully preserve equivariance, the sample complexity required for training and generalization may not be guaranteed (Garg et al., 2020). Therefore, in this paper we only focus on analyzing and designing equivariant GNNs.
Other approaches. Wijesinghe & Wang (2022); de Haan et al. (2020) designed novel variants of MPNNs based on more powerful neighborhood aggregation schemes that are aware of the local graph structure, rather than simply treating neighboring nodes as set. Li et al. (2020); Velingker et al. (2022) incorporated distance encoding into node/edge features to enhance the expressive power of MPNNs. Balcilar et al. (2021); Feldman et al. (2022) utilized spectral information of graphs to achieve better expressiveness beyond 1-WL. Talak et al. (2021) proposed the Neural Tree Network that performs message passing between higher-order subgraphs instead of node-level aggregation.
Finally, for a comprehensive survey on expressive GNNs, we refer readers to Sato (2020) and Morris et al. (2021).
17

---

Published as a conference paper at ICLR 2023
B THE WEISFEILER-LEMMAN ALGORITTMS AND RECENTLY PROPOSED VARIANTS
In this section, we give precise description on the family of Ceisfeiler-Lehmaee algorithms and several recently proposed variants that are studied in this paper. We first present the classic 1-WL algorithm (Weisfeiler & Leman, 1968) and the more advanced k-FWL (Cai et al., 1992; Morris et al., 2019). Then we present several recently proposed WL. variants, including WL with Substructure Counting (SC-WL.) (Bouritsas al., 2022), Overlap Subgraph WL (OS-WL) (Wijesinghe & Wang, 2022), Equivariant Subgraph Aggregation WL (DSS-WL) (Bevilacqua et al., 2022) and Generalized Distance WL (GD-WL).
Throughout this section, we assume hash : X + C is an injective hash function that can map "arbitrary objects" to color in where C is an abstract set called the color set. Formally, the domain X' comprises all the objects we are interested in:
R X' and C C
For any finite multiset M with elements in X, M X; For any tpple e x* of finite dimension & No, E X.
B.1
1-WL TEST
Given graph G = EV, the I-dimensional Weisfeiler-Lehman algorithm (1-WL., also called the color refinement algorithm, iteratively calculates a color mapping XG from each vertex v E V to a color (v) E C. The pseudo code of 1-WL is presented in Algorithm 1. Intuitively, at the beginming the color of each vertex is initialized to be the same. Then in each iteration, 1-WL algorithm updates each vertex color by combining its own color with the neighborhood color multiset using hash function. This procedure is repeated for a sufficiently large number of iterations T,, e.g. T = V..
Algorithm 1: The 1-dimensional Weisfeiler-Lehman Algorithm Input Graph G = (V, E) and the number of iterations T
Output: Color mapping Xa : + C
Initialize: Pick a fixed (arbitrary) element co C. and let x²) == co for all v e v
for I 4-++ to do
for each u E V do (v) = hash (xo lxx u No())))
Return: xa
At each iteration, the color mapping X induces partition of the vertex set V with an equivalence relation ~ defined to be u ~x V + Xa((u) = (v) for u, v E V. We call each equivalence
class color class with an associated color E C, denoted as -x == {u E V (1) c). The corresponding partition is then denoted as Pt = ((x2) (c) e E Ct) where C₁ = (x)
E V} is the color set containing all the presented colors of vertices in G.
An important observation is that each 1-WL iteration refines the partition Pt to finer partition Pt because for any u, U E V. u +4 v implics u ~xx e. Since the number of vertices [V] finite, there must exist an iteration Taabl < [V] such that PT = P. It follows that Pd Pfint for all t > Titable i.e. the partition stabilizes. We thus denote Pg := Pl as the stable partition induced by the 1-WL algorithm, and denote XG as any stable color mapping (i.e. by picking any X& with / > T.mblee. We can similarly define the inverse mapping Xa mapping XG serves as a node feature extractor so that xa(w) is the representation of node e E V. Correspondingly, the multiset (xx(v): v VB can serve as the representation of graph G.
-1 The
The 1-WL algorithm can be used to distinguish whether two graphs G and are isomorphic, by comparing their graph representations {xx(()) multisets are not equivalent, then G and H are clearly non-isomorphic. Thus 1-WL a necessary condition to test graph isomorphism. Nevertheless, the 1-WL test fails when (fx((v) (x) v E Vß but and H are still -somooooc (see Figure for a counterexample). This motivates the more powerful higher-order WI tests, which are illustrated in the next subsection.
E VE and [xH(v))
E VB. If the two
E VB
18

---

Published as a conference paper at ICLR 2023
B.2 k-FWL TEST
In this section, we present a family of algorithms called the k-dimensional Folklore Weisfeiler- Lehman algorithms (k-FWL). Instead of calculating node color mapping, k-FWL computes color mapping on each k-tuple of nodes. The pseudo code of k-FWL (k 2 2) is presented in Algorithm 2.
Algorithm 2: The k-dimensional Folklore Weisfeiler-Lehman Algorithm
Input Graph G (V, E) and the number of iterations T Output: Color mapping XG : Vk - C
Initialize: Pick three fixed different elements co, ci Cuode E C, let (t) hash(veo(A
for each y where A a E Ck is matrix with elements
Cnode
if 0; = 0j if vs vy and (1a U/ & E
Ai
Co
(6)
C1
if vs # og and (1 U/ } E E
for t f- to do
for each v E y
xc(u) == hash (xg 1-1 (v), ((x60((11m ,X (N VH)
where (; u) (1), .. U1-1, U, 11 ,8)
Return: xa
Intuitively, the beginning, the color of each vertex tuple v encodes the full structure (i.e. iso- mophism type) of the subgraph induced by the ordered vertex set {w, : E [}]]] by hashing the "adjacency" matrix A " defined in (6). Then in each iteration, k-FWL algorithm updates the color of each vertex tuple by combining its own color with the "neighborhood" color using a hash func- tion. Here, the neighborhood of tuple v is all the tuples that differ v by exactly one element. These k x [V] neighborhood colors are grouped into a multiset of size [V] where each element is k-tuple Finally, the update procedure repeated for sufficiently large number of iterations T, e.g. T= =
Simiar 1-WL, the k-FWI. color mapping XG induces a partition of the set of vertex k-tuples y and each k-FWL iteration refines the partition of the previous iteration. Since the number of vertex k-tuples | is finite, there must exist an iteration Taable < |V/ such that the partition no longer changes after / 2 Tamble. We denote the stable color mapping as Xa by picking any xa with I 12 Taable.
The k-FWI. algorithm can be used to distinguish whether two graphs and H are isomorphic, by comparing their graph representations (x)(v)= proved that k-FWL is strictly more powerful than 1-WL in distinguishing non-isomorphic graphs, and (I: + F)LF is strictly more powerful than FWF for all k 2 2 (Cai et al., 1992).
y and (x)(v)) v E V B. It has been
Moreover, the FFFWL algorithm can also be used to extract node representations as with 1-WL. To do this, can simply define (c(e) (v, vv) the vertex color of the k-FWL algorithm (without abuse of notation), which induces a partition Pa over vertex set V. has been shown that this partition is finer than the partition induces by 1-WL., and also the vertex partition induced by (I: + 1)-FWL is finer than that of k-FWL (Kiefer, 2020).
B.3 WL WITH SUBSTRUCTURE COUNTING (SC-WL)
Recently, Bouritsas al. (2022) proposed a variant of the 1-WI. algorithm by incorporating the so- called substructure counting into WL aggregatn procedure. This yields algorithm that is provably powerful than the original I-WL test.
To describe the algorithm, (VH, Eh ), an automorphism of is a bijective mapping f Vи > VH such that for any two vertices E VH, {u, v) En = {f(u), fu)) E EH. It follows that all automorphisms of H form a group under function composition, which is called the automorphism group and denoted as Aut(F) (H).
first need the notation of automorphism group. Given graph H
19

---

Published as a conference paper at ICLR 2023
The automorphism group (H) yields partition of the vertex set V. called orbits. Formally, given a vertex v E VH. define its orbit (r) = =fu E Vи : 3f E H.), = v}. The set of all orbits H' AH)(H)
Vir is called the quotient of the automorphism. ,dm Denote dæ I/ Aut(H) and denote the elements in 11) Aut(Ii) as - We are now ready to describe the procedure of SC-WL.
{Orby(e)
Pre-processing. Depending on the tasks, one first specify set of (small) connected graphs H {H1,-.. H. which will be used for sub-structure counting in the input graph G. Popular choices of these small graphs are cycles of different lengths (e.g,, triangle or square) and cliques. Given graph G = Ec), for each vertex E calculated:
VG and each graph H E H. the following quantities are
(7) where fa[s)-V is any isomorphism that maps the vertices of graph G[S] to those of graph H. Intuitively, (v) counts the number of induced subgraphs of G that is isomorphic to H and contains node v, such that the orbit of e is similar to the orbit OY,-- The counts corresponding to different orbits Oy, H2 and different graphs H are finally combined and concatenated into a vector:
=HH((0) == {G[S): S G = H, E S. Sc (v) E = [ddr
x (v())= [2 (v) ,.. HB (v) IT E
where the dimension of xV (V) is D Eielh d,-
Message Passing. The message passing procedure is similar to Algorithm 1, except that the aggre- gation formula (Line 4) is replaced by the following update rule:
(w), which incorporates the substructure counts (7, 8). Note that the update rule (9) is slightly simpler than the original paper (Bouritsas et al., 2022, Section 3.2), but the expressive power of the two formulations are the same.
(u( == hash (Xo x V ((v),
u E (a)
Finally, we note that the above procedure counts substructures and calculates features xV for each vertex of G. One can similarly consider calculating substructure counts for each edge of G. and the conclusion in this paper (Theorem 3.1) still holds. Please refer to Bouritsas et al. (2022) for more details on how to calculate edge features.
B.4 EQUIVARIANT SUBGRAPH AGGREGATION WL IDSS-WL)
Recently, Bevilacqua et al. (2022) developd a new type of graph neural networks, called Equivariant Subgraph Aggregation Networks, as well as a new WL variant named DSS-WL. Given a graph G = (V,E), DIL first generates a bag of graphs B& vertices, i.c. G. = VVE,), but differ in the edge sets &, Here π denotes the graph generation policy which determines the edge set E, for each graph G, The initial coloring Xa. (v) for each node e E V in graph G; is also determined by л and can be different across different nodes and graphs. In each iteration, the algorithm refines the color of each node by jointly aggregating its neighboring colors in the own graph and across different graphs. This procedure is repeated for a sufficiently large iterations T' to obtain the stable color mappings XG, and Xa- The pseudo code of DSS-WL is presented in Algorithm 3.
[G .. }} which share the
0
The key component in the DSS-WL algorithm is the graph generation policy π which must maintain symmetry, i.c., be equivairant under permutation of the vertex set. We list several common choices below:
Node marking policy π = NNM- In this policy, we have B7 = {... : E VB where G. = G, i.e., there are [V] graphs in B5 whose structures are the completely the same. The difference, however, lies in the initial coloring which marks the special node v in the following way: x&. (v) = e₁ and xa. (u) = cg for other nodes u o v, where Co, C E are two different colors.
Node deletion policy π AND. The bag of graphs for this policy is also defined as B (G. : v E VB. but each graph G, = (V. has a different edge set E := ffff w) ..)())) Intuitively, it removes all edges that connects to node and thus makes an 0 isolated node. The initial coloring is chosen as a constant X2, (v) = co for all o E V and G E B& for some fixed color co E C.
20

---

Published as a conference paper at ICLR 2023
Algorithm 3: DSS Weisfeiler-Lchman Algorithm
Input : Graph G= E), the number of iterations T, and graph selection policy क Output: Color mapping XG +
Initialize: Generate a bag of graphs B = (G. G = =VV,i) and initial coloring 0
XG; for
E [m] according to policy π
Let (v) == hash (1xcc (v) :ie [m]]) for each v E
for t < to do
for each v E V do
for 4- to m do
Xc. (v) hash (v), 1x Ne. (o), e
xo(u)= = hash (fxx, (v) :E [m]})
Return: xe
Ego network policy x TEGo())- In this policy, we also have B8 = (G., : uE VB. G.
(V,E.). The edge & is defined as & := ((u, w) } E & (1, v) S k, dis s k}. which corresponds to a subgraph containing all the k-hop neighbors of v and isolating other nodes. The initial coloring chosen as Xa, (v)
co for all E and G2 B where co E C is a constant. One can also consider the ego network policy with marking π [EG by marking the initial color of the special node for each G...
We note that for all the above policies, | V/. There other choices such the edge deletion policy (Bevilacqua et al., 2022), but we do not discuss them in this paper. A straightforward analysis yields that DSS-WL with any above policy is strictly powerful than the classic 1-WL algorithm. Also, node marking policy has been shown to be not less powerful than the node deletion policy (Papp & Wattenhofer, 2022).
Finally, we highlight that Bevilacqua et al. (2022); Cotta et al. (2021) also proposed weaker version of DLS called the DS- WL algorithm. The difference that for DS- WL, Lines 6 and 7 in Algorithm 3 are replaced by simple 1-WL. aggregation:::
Xc. (v) == hash (XG,' (x) : u Nc(u)B)
(10)
However, the original formulation of DS-WL. (Bevilacqua et al., 2022) only outputs a graph repre- sentation If flxx, (v)
VB : G, B& rather than outputs each node color, which does not suit the node-level tasks (e.g., finding cut vertices). Nevertheless, there are simple adaptations that
makes DS-WL output color mapping Xc. We will study these adaptations in Appendix C.2 (see the paragraph above Proposition 16) and discuss their limitations compared with DSS-WL.
B.5 GENERALIZED DISTANCE WL (GD-WL)
In this paper, we study new variant of the color refinement algorithm, called the Generalized Dis- tance WL (GD-WL), The complete algorithm is described below. As special case, when choosing de = disg, the resulting algorithm is called the Shortest Path Distance WL (SPD-WL), which is strictly powerful than the classic 1-WL.
Algorithm 4: The Genealized Distance Weisfeiler-Lehmann Algorithm
Input Graph G = (V,E), distance metric de VV V R4, and the number of iterations T
Output: Color mapping Xa : V +
Initialize: Pick fixed (arbitrary) element co C, and let xa (v) co for all v E y
for +- to T do for each u E V do
L (v) == hash (((da(1,u))xt (w) VB)
Return: xa
21

---

Published as a conference paper at ICLR 2023
C PROOF OF THEOREMS
This section provides all the missing proofs this paper. For the convenience of reading, we will restate each theorem before giving proof.
C.I PROPERTIES OF COLOR REFINEMENT ALGORITHMS
In this subsection, we first derive several important properties that are shared by general class of color refinement algorithms. They will serve as key lemmas in our subsequent proofs. Here, general color refinement algorithm takes graph G = (Va,E)) as input and calculates a color mapping Xa : VG + C. We first define a concept called the WL-condition.
Definition C.1. color mapping XG Vc + C' is said to satisfy the WL-condition if for any two vertices e with the same color (i.e. xa(u) = (c)))) and any color e E C,
(Na(u) nxa (c) = [N((v) Nxx (c)(.
-1 is the inverse mapping of xc- where XG
Remark C.2. The WL-condition can be further generalized to handle two graphs. Le : Vc - C and XH VH + C be two color mappings obtained by applying the same color refinement algorithm for graphs G and H, respectively. XG and Xи are said to jointly satisfy the WL-condition, if for any two vertices u VG and v Vи with the same color (Xa(u) (u)) and any color E C,
(W((u) O (x)((e) (W) xxxx (c)l-
It clearly implies Definition C.1 by choosing G H.
is easy to see that the classic 1-WL. algorithm (Algorithm 1) satisfies the WL-condition. fact, will show below, such
many of the presented algorithms in this paper satisfy such condition as DSS-WL WL (Algorithm 3), SPD-WL (Algorithm 4 with do = disc), and k-FWL (Algorithm 2).
Proposition C.3. Consider the DIS-WI. algorüthm (Algorithm 4) with arbitrary graph selection policy Let XG and XH be the color mappings for graphs G and H, and let fxG, i E [ma]] and HxH [m=]] be the color mapping for subgraphs generated by x. Then,
XG and XH jointly satisfy the WL-condition;
XG, and Xı,, jointly satisfy the WL-condition for any i [ma] and E [mrr].
Proof. We first prove the second bullet of Proposition C.3, By definition of the DSS-WL a
procedure (Line 6 in Algorithm 3), XG, (u) = XHI, (v) already implies (xa.(w) w E No, Kxn, (w) : w E Nn, (v)B- Namely, [w w E (w) n (c) = [[ w E N (v) XH, (c)} holds for any C.
We then turn to the first bullet. (u( = (u). then fx.. E [mal] f X (c)
j [mx] B (Line 7 in Algorithm 3). Then there exists pair of indices [me] and j E [ma]
such that XG, (w) = XH, (v). By definition of the DSS-WL aggregation, it implies [xa(w) w Na(u)) B = (w)
E (NH( and concludes the proof.
O
Proposition C.4. Let Xa and be two mappings returned by SPD-WL (Algorithm 4 with de = disc) for graphs G and H, respectively. Then XG and XH jointly satisfy the WL-condition.
Proof. If (x( (v) for some nodes u, v, then by the update rule (Line 4 in Algorithm 4)
(diso w),, xa(w)) w E VB = (ddisa w). xc(w)) w E VD.
Since E (N) if and only diso w) 1, we have
Hxo(w): w E AN = ([x((w) : E No(v)
Therefore, for any E C, ((w: : W Na(u) n xa (c)) = l( : E (a(()) (c))
Proposition C.5. Let XG and Xu be two vertex color mappings returned by the k-FWL algorithm (k > 2). Then XG and X jointly satisfy the WI--condition.
22

---

Published as a conference paper at ICLR 2023
Proof. Let (c) (=(v) for some u Ve and v Vy- By the update formula (Line 4 in Algorithm 2). (xxauu... :.. u, w) : w E VcB = (0, .... U, w) w E VH H. Note that for any nodes w1 E VG, W2 E Vn and any 21 E (N ). I2 NNn(w2), one has XG (w 1 21) * X (w2, .. ,,,,,,,,, 22). This is obtained by the definition of the initialization mapping xa and the fact that XG refines X8- Consequently, fxx(uu... U, (,) w E [N)
v, v,w)) w E (v) B. Next, we can use the fact that if xa ... u. w1) = Xc(u, ... v w2) for some w1, uog E V. then Xa (w]) = Xa (w2) (see Lemma C.6). Therefore, (xx(w) w E No(()) (xx((w) w E (x) B. which concludes the proof.
(xx(u,
To complete the proof of Proposition C.5, it remains to prove the following lemma:
Lemma C.6. Let XG and XH be color mappings for graphs G and H in the k-FWL algorithm (k 2 2). Denote
cat x) = (w, (....., W R.
times
timer
Then for any i E [R: 1] and any nodes u, w E VG. v Vn, if xo(cat= (,a w)) XH
then XG (c w)) = Xm(cats-i-1sH1((,0)) Consequently.
xc(w)= = (x)
Proof. By the update formula (Line 4 in Algorithm 2), xc(call-is(u, = (m( (v,x)) implies that Axc(calg---1,.fff y: w)) : y E VeB
y, x)) :y E Vn D-
Note that for any j E [k- 1] and any z E Vg. z' E v/ with 2, = 2-+1 but 2/3 * #2/+1= one has (=)=) # (=)) This is obtained by the definition of the initialization mapping x& and the fact that XG refines Xo- Therefore, we have Xa (c(aat--i-1.t (u, w)) Xir (c( (1, x)). as desired.
Equipped with the concept of WL-condition, we now present several key results. In the following, let XG: : VG - C and XH VH + C be two color mappings jointly satisfying the WL-condition.
Lemma C.7. Let (Uu....,uu)) be any path (not necessarily simple) of length d in graph G. Then for any node uo E XH (xa(vo)) in graph H, there exists a path (uo. ,u) of the same length d starting at ug, such that XH (u.) = xa(1;) holds for all E [d].
Proof. The proof is based on induction over the path length d. For the base case of d = 1, if the conclusion does not hold, then there exists two vertices u E Vo, v E VH with the same color (i.c. (u) = Xtr (v)) and color
xx((1) ) such that Na(u) Nxa (c) a 0 but but (N) (c) 0. This obviously contradicts the WL-condition. For the induction step on the path length d, one can just split it by two parts (No,
va-1) and (Ma-1, va). Separately using induction yields two paths (uo, ... 1 and (ua-1, ua) such that (u:) = xa(1:) for all i E [d]. By linking the two paths have completed the proof.
... (No....
Finally, let us define the shortest path distance between node u and vertex set S as disa S) = minges disc(u, v). The above lemma directly yields the following corollary:
Corollary C.8. For any color e E (xa(w): e Va3 and any two vertices u E VG. v VH with the same color (i.e. xa(u)= = (=())), disc(u, Xa ( (c)) = disn (U. (c)).
C.2 COUNTEREXAMPLES
We provides the following two families of counterexamples, which most prior works cannot distin- guish.
Example C.9. Let G1 &V,&) and G2 = (V,E2) be a pair of graphs with n 2km + 1 nodes where m. k are two positive integers satisfying mk 2 3. Denote y = [n] and define the edge sets as follows:
E (Li, (i 2km) + 1} : E [24m]] } U ([n, : e [2km]] i mod 0)
Eg = (fi, modd km) + +1} : E [km]] U {(i + km, moo km) + lm + 1} E [km]]] U
((n, () : [2km], mod m = 0).
23

---

Published as a conference paper at ICLR 2023
See Figure 2(a-c) for an illustration of three cases: (i) m = 2, 2; (ii) 4, 1; (iii)
m = 1, = 4. It is easy to see that regardless of the chosen of m and k. G1 always has no cut vertex but G2 do always have cut vertex with node number n. The case of k 1 is more special, for which G2 actually has three cut vertices with node number m, 2m, and n, respectively, and it even has two cut edges [m.n) and (2m, n (Figure 2(b)).
Example C.10. Let G1 = (V.E1) and G = (V, (2) be a pair of graphs with n = 2m nodes where m 2 is arbitrary integer. Denote V = [n] and define the edge sets as follows:
E = [(2, (1) + 1} : i E [n]] U { 2m
Eg = {(, (oood m) + 13 : E [m]] U (fi + m, (i (imodm) + m + 1] : E [m]} U {[m, 2m]}.
See Figure 2(d) for illustration of the case 8. It is easy to see that C₁ does not have any cut vertex or cut edge, but G2 do have two cut vertices with node number m and 2m, and has a cut edge {m, 2m).
Theorem C.11. Let H = {H,,.... Ha), H, = EV),E)) be any set of connected graphs and denote ny = maX [V.l. Then SC-WL (Appendix B.3) using the substructure set H. can neither distin- guish whether a given graph has cut vertices nor distinguish whether has cut edges. Moreover, there exist counterexample graphs whose size (both in terms of vertices and edges) is O(wv).
Proof. We would like to prove that SC-WI. cannot distinguish both Examples C.9 and C.10 when ny < m (m is defined in these examples). First note that for both examples, any cycle in both 1₁ and G2 has length of at least m. Since the number of nodes in H, is O(wy), if H; contains cycles, will not occur in both G1 and G2, thus taking no effect in distinguishing the two graphs. As a result, we can simply assume all graphs in H. are trees (connected graphs with no cycles). Below, we provide a complete proof for Example C.9, which already yields the conclusion that SC-WL can neither distinguish cut vertices nor cut edges. We omit the proof for Example C.10 since the proof technique is similar.
Proof for Example C.9. Let H; be a tree with less than m vertices where m is defined in Exam- ple C.9. By symmetry of the two graphs G1 and G2. suffices to prove the following two types of
V equations: 26, (n) oya (n) and aG, (i) x2, (i) for all m < i S 2m, where x is defined in (8). We first aim to prove that 26 (v) x3, (v) for {m + 1,... 2m3. Consider an induced sub- graph G][S] which isomorphic to H; and contains node v. Define the set T == {jm j E [4]]nn. For ease of presentation, we define an operation cir(æ, a, b) that outputs an integer y in the range of (a, b] such that y has the same remainder as (mod b a). Formally, cir(r, b) = y if y S b and x = y (mod b- - b-a).
If n & S, then it is easy to see that G][S] is chain, i.c., no vertices have a degree larger than 2. We define the following mapping Is S + [n]] such that cir(u, m, 2m) cir(u, 0, km) if 2
gs (u) = {{
k
In this way, the chain G1 G][S] is mapped to chain of G2 that contains v. Concretely, denote (S) {gs(u): u E S). then G2[gs (S) ~ Gi[S] H₁, and obviously the orbit of in G2))s(S)) matches the orbit of v in G1 See Figure 3(a,b) for an illustration of this case.
If n S. then it is easy to see that the set T + 0. We will similarly construct mapping gs: : S + [n] that maps S to 9s(S) satisfying (s(v)= = which is defined as follows. For each u E S) (m)) we find a unique vertex w,, in T such that disc (u, w.) is the minimum.
Note that the node w,, is well-defined since T * 0 and any path G GS] from u node
in T goes through w., Define
cir(u, m, 2m)
if k: and W. Wes
gs(u) cir(u, O, m)
if k 1 and w. * was
cir(u, 0, km)
if k: > and w. < kmn,
cir(u, km, 2km)
if k >> 1 and w. km.
We also define gn(n) = n. Such definition guarantees that for any 21,22 E S, (2), e Ea, + {g5( gs (12)) E Egg. Therefore, G2]gs(S)] ~ G ~ H.. Moreover, observe that (u) = (mod m)) always holds, and thus it is easy to see that the orbit of e in G2lgs (S)) matches the orbit of in G See Figure 3(c,d) for an illustration of this case.
24

---

Published as a conference paper at ICLR 2023
4m
Am
2m
2y
2m
2m
3/1
3m
3m
3m
m
m
m
172
M
3m
m
3m
mm+1
12++2
2
112 +
m
2m +1 2m
2m +1
2m
21n
2m
2m
2m
2m
2m
2m
2m +1
On
m
m
m
2
3m
300
(a) n $ 1
(b) c S, l
(c) ( k
(d) n E S,
Figure 3: Illustration of the proof of Theorem 3.1. The trees (2)(()) are outlined by orange.
Finally, note that for any two different sets S₁ and S2 such that Gi [St] [ H, have gs, (Si) * Is, (S2), which guarantees that the mapping
{S C [n] Gi = H; E S} {S C [m] G2[S] = Hg, S) defined be g(S) Is(S) is injective. One can further check that the mapping is also surjective, and thus it is bijective. This means 26 (v) 2², (v) for u {m.... 2m 1). The proof for = (n) =x, (n) is almost the same, so we omit it here. Noting that under classic 1-WL, the colors XG, (v) = XG, (v) are also the same. Therefore, adding the features x V (v) does not help distinguish the two graphs. We have finished the proof for Example C.9.
Using similar cycle analysis as the above proof, we have the following negative result for Simplicial WL (Bodnar et al., 2021b) and Cellular WL (Bodnar al., 2021a):
Proposition C.12. Consider the SWL algorithm (Bodnar et al., 2021b), or more generally, the CWL algorithms with either k-Cl, k-IC, or k-C as lifting maps (k 2 is an integer) (Bodnar et al., 202 la, Definition 14). These algorithms can neither distinguish whether given graph has cut vertices nor distinguish whether has cut edges.
Proof. Observe that the counterexample graphs in both Examples C.9 and C0 do not have cliques. Therefore, SWI. (or CWL. with k-CL) reduces to the classic 1-WL. and thus fails to distinguish them. Since the lengths of any cycles in these counterexample graphs are at least m (m is defined in Examples C.9 and C.1O), we have that CWL with k-IC or k-C also reduces to 1-WL when m > k. Therefore, there exists graphs whose size is O(k) such that CWL can neither distinguish cut vertices nor cut edges.
Finally, we point out that even if l is not a constant (i.e., can scale to the graph size), CWL with k-IC still fails to distinguish whether a given graph has cut vertices. This is because for Example C.9 with k 2 (e.g. Figure 2(b.e)), CWL with IC still outputs the same graph representation for both G2 and G2. This happens because all the 2-dimensional cells in these examples are cycles of an equal length of m + and one can easily check that they have the same CWL color.
We finally turn to the case of subgraph-based WL variants.
Proposition C.13. The Overlap Subgraph WL (Wijesinghe & Wang, 2022) using any subgraph mapping w can neither distinguish whether given graph has cul vertices nor distinguish whether it has cut edges.
Proof. An important limitation of OS-WL is that if graph does not contain triangles, then any over- lap subgraph S... between two adjacent nodes u, will only have one edge {u, v). Consequently, the subgraph mapping w does not take effect can OS- WL reduces to the classic 1-WL. Therefore, Example C.9 with > 1 and Example C. with do not contain triangles (see Figure 2(a,,.d)). Moreover, Example C.9 with m = (see Figure 2(c)) is also counterexample discussed in Wijesinghe & Wang (2022, Figure 2(a)).
3 still apply here since the graphs G1 and G2
n
25

---

Published as a conference paper at ICLR 2023
Proposition C.14. The DSS-W. WL with ego network policy without marking cannot distinguish the graphs in Example C.9 with m = (Figure 2(c)).
Proof. First note that for any two vertices in either G1 or G2 defined in Example C.9, their shortest path distance does not exceed 2. Thus we only need to consider the ego network policy TECO(I) and TEGO(2)-
For TEGO(2). the ego graphs of all nodes are simply the original graph and thus all graphs in the bag B and equal. Thus DSS-W SL reduces to the classic 1-WL and cannot distinguish G and G2.
For TEGO(1), the ego graph of each node v * n is graph with 5 edges, having a shape of two triangles sharing one edge. These ego graphs are clearly isomorphic. The ego graph of the special node is the original graph containing all edges. It is easy to see that the vertex partition of DSS-WL becomes stable only after one iteration, and the color mapping of G and G2 is the same. Therefore, DSS- WL cannot distinguish G1 and G2-
We thus conclude the proof.
Proposition C.15. The GNN-AK architecture proposed in Zhao et al. (2022) cannot distinguish whether given graph has cut vertices.
Proof. The GNN-AK architecture is quite similar to DSS-WL using the ego network policy but is weaker. There is also a subtle difference: GNN-AK adds the so-called centroid encoding. However, unlike node marking that is performed before the WL procedure, centroid encoding is performed after the WI. procedure. The subtle difference causes GNN-AK to be unable to distinguish between the two graphs 11 and G2-
We finally consider the DS-WL algorithm proposed in Cotta et al. (2021); Bevilacqua et al. (2022). As discussed in Appendix B.4, the original DI. formulation only outputs graph representation rather than node colors. There are two simple ways to define nodes colors for DS-WI:
If the graph generation policy и node-based, then each subgraph in B% = { is umiquely associated to a specific node E V. We can thus use the graph representation of each subgraph G; as the color of each node. This strategy has appeared in prior works, e.g- Zhao et al. (2022).
For a general graph generation policy there longer exists explicit bijective mapping between nodes and subgraphs. In this case, another possible way is to define (c()) := (x (v) G2 E B. similar to DSS-WI.. This approach is recently introduced by Qian et al. (2022). However, such a strategy loses the memory advantage of DS-WI. (i.e., needing ( memory complexity rather than @(V|+1 (B)()), [)), and is less expressive than DSS- WL. We thus do not study this variant in the present work.
Proposition C.16. The DS- algorithm with node marking/deletion policy cannot distinguish cut vertices when each node's color is defined as its associated subgraph representation.
Proof. One can similarly check that for Example C.9 with m = 1 (see Figure 2(c)), the color of node n will be the same for both graphs G₁ and G2. Therefore, DL cannot identify cut vertices. O
Finally, using a similar proof technique, the NGNN architecture proposed Zhang Li (2021) (with shortest path distance encoding) cannot identify cut vertices.
C.3 PROOF OF THEOREM 3.2
Theorem C.17. Let = (V,Ea) and = (V,EH) be two graphs, and let XG and Xu be the corresponding DSS-WL. color mapping with node marking policy. Then the following holds:
For any two nodes w E V in G and x E V in H. if xxx(w)= XH (z), then w is a cut vertex vertex in graph H.
in graph G if and only if is
For any two edges (wi w2} E Ea and {x1,22} E Eq,, if (xa(wi). (c())) = (xn(x1), xu (x(2))) B. then (wi, w2) ) is cut edge if and only if (x1, 222) is cul edge.
26

---

Published as a conference paper at ICLR 2023
Proof. We divide the proof into two parts in Appendices C.3.1 and C.3.2, separately focusing proving each bullet of Theorem 3.2. Before going into the proof, we first define several notations. Denote (V) the color of node under the DSS-W WL algorithm when marking node. By definition of DSS-WI. (Line 7 in Algorithm 3), XG(u) hash (+x E V))). We similarly define the inverse mappings (xx)
special
We first present a lemma which can help us exclude the case of disconnected graphs.
Lemma C.18. Given a node w, ler Sc(w) C. V be the connected component in graph G that comprises node For any two nodes V in G and x V in H, if xc(w) Xu (z), then XG]Sa(w]](W) = (H)Sx(t)(T)).
Proof. We first prove that if Xc(w)= = (x)),, then (x)(w) a E = : u E (z(2)B H. First note that for any nodes u, in G and v, in H, if u So(w) but v & (x)), then Xo (w) * (z). This is because DSS-WI only performs neighborhood aggregation, and the marking cannot propagate to node x while the marking u can propagate to node w. By definition we have
xc(w) = hash (fxū(w) : u Sc(w)B U (xū(w) : So(w)R))
Similarly,
(=) = hash (x) : u Sn(2)) u (x) :0 Sn())))
Since Xc(w) (z),), we have fxă : :ue Sa(w)) = {xū : u E SH This clearly Su(²)] and thus (G(So(w](())
implies [XG[Sa(u) E Sc(w)] [xH(sm(a)
(x)
Note that wr is a cut vertex in G implies w a cut vertex in G[Sa(w)). Therefore, based on Lemma C.18, can restrict our attention to subgraphs C[Sc(w) and H[SH(x)) (z:] instead of the original (potentially disconnected) graphs. In other words, in the subsequent proof we can simply assume that both graphs G and H are connected.
We next present several simple but important properties regrading the DSS-WI WL color mapping as well as the subgraph color mappings.
Lemma C.19. Let be two nodes in connected graph G and v, be two nodes in connected graph H. Then the following holds:
(a) If w and + v, then xā + (x)(x);
(b) If (w) = Xir (x), then xa(w) = XH (z);
=xir (c) (x)(()) = xxi((a) (1),, then xa( (n);;;
(d) xo(w) = (x) if and only if xā x (x);
(e) If (x) = Xi((), (r), then disc (u, w) dis (v.z)
Proof. Item (a) holds because in DLS-WL, the node with marking cannot have the same color as node without marking. This can be rigorously proved by induction over the iteration t in the DSS-WL algorithm (Line in Algorithm 3).
Item (b) simply follows by definition of the DSS-WI. aggregation procedure since the color (w) encodes the color of (c(w).
We next prove item (c), which follows by using the WL-condition of DSS-WL algorithm (Proposi- tion C.3). Since is connected, there is a path from w to u. Therefore, in graph H there is also a path from x to some node v' satisfying xa (u) Xi, (v') (Lemma C.7). Now using item (a), it can only be the case o' = u and thus (u) = (e). Finally, by item (b) we obtain the desired result.
We next prove item (d). On the one hand, item (b) already shows that (w) xo(x) Xo (o(w) = (x). On the other hand, by definition of the DSS-WL algorithm,
Xa(w) = hash (w)) B U (x)(w): : a (())))) Xu(x) (x) hash (=) U (x)(())
27

---

Published as a conference paper at ICLR 2023
Since Xo (w) (x) and (x + (x) holds for all v Wx (by item (a)), obtain (G(w)= = (((w))x((T)).
We finally prove item (c), which again can be derived from the WL-condition of DSS-WL al- gorithm. If (((w) = (x), then by Corollary C.8 we have disc (w, (xt) (xx (u)) = Using item (a),
have XH (1') o XH (v). Therefore, it can only be the case that (X22 (x²))(((()) = {o} and (0)
disu (z. (xH) (44)((m)) (xx((x
fu} and for any e' # v,
(T) This yields diso(u, w) disc(u, (U, x) and concludes the proof.
C.3.1 PROOF FOR THE FIRST PART OF THEOREM 3.2
The following technical lemma is useful in the subsequent proof:
Lemma C.20. Let u, v E V be two nodes in connected graphs G and H, respectively, If x²) = (v), then (xū(w)= w VB (x) w E VB.
Proof. Let (u( = {w E V dusc(u, w) d} be the d-hop neighbors of node in graph G, and denote Cg. (xx(w)
E (n) the multiset containing the color of all nodes with distance d to node u. We can similarly denote N (c) C₁2, (bxi(w))
{w disu (u, w) d) and (H) B. It suffices prove that for all d N., Cd Cj/-
We will prove the above result by induction. The case d = is trivial. Now suppose the case of d is true (i.e., C. = CHt and we want to prove Cd+1 = Cd+1 Note that for any nodes 3 ø2 satisfying (x1) = Xir (12). (xā(w) w E No((1)) (x)((w) E (22) Therefore, by the induction assumption C9 Ca.
U (xx w E No(x) (E
U (xi(w) : (H) xEN
We next claim that Cg n cg = 0 for any d + d'. This because for any nodes wi and we with the same color (ww) Xo (w2), by Lemma C.19(e) we have disG(wi, u) = disc (w2, u). Using this property, we obtain
U (xo(w) : w NN = U (xk(w): : :e NN (v) (M)
(w)B.
It is equivalent to the following equation:
U (xū(w) (Na(w) -())) wENd+"(w) (u)
U (x)(w)) ( wEAd (v)
where (feB x m is multiset containing m repeated elements Finally, observe that if (( = Xis (w2) for some nodes wi and W2, then (Wa(w1) n (w)
(w2) n N (v) (because
Cd n Cd' 0 for any d & d'). Consequently, (x) Ad+ (v)) namely cd+1 CH We have thus completed the proof of the induction step.
N (v) (xir(w)
We now present the following key result, which shows an important property of the color mapping for BLS
Corollary C.21. Let E V be two nodes in connected graph G with the same DSS- WL color, i.e. Xa(u)= = Xc(v). Then for any color e e C. (xx(w)) : w E X (c) = (xx((w) w E Xa (c)
xe(r), then (a) (v) (by Lemma (.)) Con- sequently, (w) w E VB = (x)) w E VB holds by Lemma C.20. If (x) : w E X (c) # (x)(w) w E X (c).. then there must exist two nodes wi E X (c) and & X2 (c), such that (8))) ((z)) Therefore, by Lemma C9 we have xa(w)) = xa (2), yielding a contradiction.
Proof. First observe that if xG(u)
In the subsequent proof, assume the connected graph G is not vertex biconeeic and let E V be a cut vertex in G. Let { (m 2 2) be the partition of the vertex set V V(fu), representing each connected component after removing node
28

---

Published as a conference paper at ICLR 2023
5
Q
P
(a) Proof of Lemma C.22
(b) Proof of Lemma C.23
Figure 4: Several illustrations to help understand the lemmas.
Lemma C.22. There is at most one set S satisfying St O XG (xa(u)) # 0. In other words, if S, Sxxxalxxcu)) (xa(u)) + 0 for some i E [m]) then any E [m]] and j + i, S, n xee (xa(u)) O.
Proof. When Ix=' (xx(u))) 1, the conclusion clearly holds. Ixa (xa()) > 1, then we can pick node un E XG (xa(u)) that maximizes the shortest path distance disc (ii, u). Let un S for some i [m]] If the lemma does not hold, then we can pick another node u2 Xx (xx(u)) and u2 & St Since U1 and u2 are in different connected component after removing u, diso U2) dis u) + disa(U2, u). See Figure 4(a) for an illustration of this paragraph.
By Corollary C.21, Hxe (w) w E X (xc(u))B = (x)(w) w E Xa (xa(()) There- fore, there must exist a node Uy E X (xa(u)) satisfying Xa (uz) = Xo(uz). We thus have disg(u2, u1) disg (ug, u) by Lemma C.19(e). On the other hand, by definition of the node u1, disa(u) u) 2 disc (u3, u). Therefore, disa u2, un) disa (ui, u) + discruu, u) > disa(us, w). This yields contradiction and concludes the proof.
Lemma C.23. For all ue E XG (xa(u)), u' is a cut vertex of G.
Proof. When Ixa (x)(u)) = 1, the conclusion clearly holds. Now assume (xa > 1. Since u is a cut vertex in G, by Lemma C.22, there exists a set Sj such that Sj Nx (xa(u) = 0. Pick any node E Sj. then (w( A (w). Let u' be any node with color Xc(u)) - xa(w)) follows that (u) = x² (u') by Lemma (.1)(d). Based on the WL-condition of the mappings Xa and Xa by Lemma C.7 there exists a node w' with color Xa (w") (ww (because there is path from node u to w). See Figure 4(b) for an illustration this paragraph.
Suppose u' is not cut vertex. Then there is path P from w' to u without going through node u' It follows that Xa (x;) * Xo (u') for all
Denote P = (Zo, ... Ia) where To w' and i [d] (by Lemma C.)). Again by using the WL-condition, there exists a path = (yo. ................................ Ma) satisfying 3o = w and (3)) = xa (a,) ) for all i E [d]. particular, Xa (ya) = xa (u), which implies (v(ya) = xo by using Lemma 19(b). By the definition of w and Lemma C.22, any path from to Ya Xa x (xa()) must go through node u, implying that (x.) (²) for some i E [d]. However, we have proved that (w (xx) contradiction. Therefore, u' is cut vertex.
(x:) # xod(')) x²). yielding
Li
Using a similar proof technique as the one in Lemma C.23, we can prove the first part of Theo- rem 3.2. Suppose u' XH (xa(u) and want to prove that u' is cut vertex of graph H. Observe that Ixa (xa(u))
Ix (x))))) (A simple proof is as follows: xa(u) = (H()) implies (²) = x (u') by Lemma C.19(d), and thus using Lemma C.20 we have (x) w e FB [xx (w) w E vB and finally obtain (xo(w) : w E vB [xx(w)) : w E VB by
Lemma C.)9(b).)
We first consider the case when \xa (xa(4)) = Ixe (xH (w)) > 1. Following the above proof, similarly pick w E S, in G and w' in H satisfying (c(w) # (u) and xy (w') xā Since (xo(u)) > pick node un E X x (xo(u) in H such that un w'. If x/ is
29

---

Published as a conference paper at ICLR 2023
Graph
Graph
Graph
Graph H
S
Si
Q
Q
S
w
(a) Proof the main theorem (Ixa' (xo(u)) >
(b) Proof the main theorem (xaa (xa(u)))
Figure 5: Several illustrations to help understand the main proof of Theorem 3.2.
not a cut vertex, then there path P = (To, ... ,a.) ) in H where vn = w' and di = uss such that
x/ X (a:) * xy (u') for all i E [d] (by Lemma C.19(a)). Using the WL-condition, there exists path Q (Yo.... ya) in G satisfying yo and (² XH (zx) for all i [d]. In particular, X xo(( x (ww), which implies Xa(Ua) xa(uw) by using Lemma C.19(b). However, any path from wr to ya E xGx (xx()) must go through node u, implying that XG (w:) = (u) for some i [d]. This yields a contradiction because ((())) (x:) + Xa (1)) = x² (u). See Figure 5(a) for illustration of this paragraph.
We finally consider the case when Ix (xa())) = Ixū (x)( = 1. Let w E S] and æ E S2 be two nodes in G' that belongs to different connected components when removing node u, then (c(w) * (u( and (x) # Xc(u). Since (u) = (=")), by the WL-condition (Lemma C.7) there is a node w' E Xir X (xx((=)) in H. Consequently, xx xi (w') (Lemma C.19(d)). Again by the WL-condition, there is a node x' E (because they have different colors). If u is not a cut vertex, then there is path / = (yo, ... Dd) in H such that You x', Ya w' and yi * u' for all e [d]. It follows that for all E [d], X# (3i) * X (u') by our assumption lx (x)( = 1, and thus X (ys) # X (u') (by Lemma 19b) Since Xa (x) w/ (x'), by the WL-condition (Lemma C.7), there is a path Q (=0. ,a) in G satisfying 20 and 2 (xx) (v4) for i E [d]. See Figure 5(b) for an illustration of this paragraph.
H. Clearly, w' * u/ and x' * w'
Clearly, we have 2d = w using (Z(z = x (w') and Lemma C.19(a). On the other hand, by Lemma C. (2,) = X#f (y:) implies XG(x) X# (y:) and thus xa(4)) # (=("') ) (a( holds for all i E [d] and thus 2; * u. In other words, we have found path from x to without going through node u, which yields contradiction as u is cut vertex. We have thus finished the proof.
w'
C.3.2 PROOF FOR THE SECOND PART OF THEOREM 3.2
The proof is based on the following key result:
Corollary C.24. Let w and x be two nodes connected graph G with the same DSS- WL color, i.e. Xa(w) (x(x). Then for any color C.
(diso (w, v) : E xa (c)] = -[diiis v) : u
Proof. By Corollary C.21, we have (v) v X (c) } = (xx(()) : E X (c)}. Since for any nodes u, v, (u) (v) implies disc(u, w) disc(v, (by Lemma C.19(e)), have obtained the desired conclusion.
Equivalently, the above corollary says that if xa(w) = (x), then the following two multisets are equivalent:
H (disc(w, v). xo())) VB (diso (2. v), (x)) v VB.
Therefore, it guarantees that the vertex partition induced by the DSS-WL WL color mapping is finer than that of the SPD-WI WL (Algorithm 4 with de = disg). We can thus invoke Theorem 4.1, which directly concludes the proof (due to Proposition C.56).
30

---

Published as a conference paper at ICLR 2023
C.4 PROOF OF THEOREM 4.1
Theorem C.25. Let G = (V,Ea) and H = (V,HH) ) be two graphs, and let Xa and Xu be the corresponding SPD-WL color mapping. Then the following holds:
For any two edges {wr, w2} E &a and {I1, 22) E En. if (xa(wi))xx(w>)) = (xH(z1), (x2)) then {wi, w2) is a cut edge if and only if (21, is cut edge.
If the graph representations of G and H are the same under SPD-WL, then their block cul-edge trees (Definition 2.3) are isomorphic. Mathematically, [xa(w)) : w E VB [x)(w)= w E VB implies that BCETree(G)) BCETrre(H))
Proof Sketch. The proof of Theorem 4.1 is highly non-trivial and is divided into three parts (pre- sented in Appendices C.4.1 to C.4.3, respectively). We first consider the special setting when both G and H are connected and (xx(w)) w E VB = fx cege-biconnnected, and let {u, &g be cut edge in G. We separately consider two cases: (a(u) # xa(()) (Appendix C.4.1) and Xc(u) = Xc(u) (Appendix C.4.2), and prove that any edge {u', v'3 E Eh satisfying (xx(u).
w E VB- Assume G is not
= (x)("'), (H() is also cut edge of H. This basically finishes the proof of the first bullet in the theorem. Finally, we consider the general setting where graphs G, H can be disconnected and their representation is not the same in Appendix C.4.3, and complete the proof of Theorem 4.
Without abuse of notation, throughout Appendices C.4.1 and C.4.2 we redefine the color set C == (xa(w)= w E )} (x (w)) w E V) to focus only on colors that are present in G (or H), rather than all (irrelevant) colors in the range of a hash function.
C.4.1 THE CASE OF (u( # (v) FOR CONNECTED GRAPHS
We first define several notations. Throughout this case, denote {Sw, S. as the partition of V, rep- resenting the two connected components after removing the edge {u, o} such that u E S., v E S... S, nss = 0 and S. U.S = V. We then define an important concept called the color graph.
Definition C.26. (Color graph) Define the auxiliary color graph G (C, Ege) where Ege (w) xx((x))) ( xu) E Ea). Note that G can have self loops, so each edge is denoted as a multiset with two elements.
Lemma C.27. Let S = Xa (xx( Uxe (xa(v)) be the set containing vertices with color (u( or Xa(u). Then either S S.S, = {u} or S ns, = [v].
Proof. Assume the lemma does not hold, i.. Sal > 1 and [S > 1. We first prove that XG (xx( # @ and Xa (xa(v)) ns, * 0. By symmetry, we only need to prove the former. Suppose XG (xa(u)) n ns, = 0, then (x (xa(v)) (.) * 0 (because |S n Sal > 1), and thus there exists 2' E S,. v' * v such that Xa((") (x)()) Note that v' must connect to a node u' with (u') = (u). Since {u, v) is cut edge in G. u' E S, Therefore, x (x) + 0, yielding contradiction. This paragraph is illustrated in Figure 6(a).
We next prove that at least one of the following two conditions holds (which are symmetric): (i) (xa' (xa(x)) n (u) * 0: (ii) (x (xa(u)) n S,) * 0. Based on the above paragraph, there exists o' E S, satisfying Xo (o(u). condition (i) does not hold, i.c. xa S = {u]. then e' must connect to u. This means [Wa(u)) O X2 xxxx(xx())) (xa(v)) > 2. Again using Xo (xa(w)) n... + 0 (the above paragraph), we can pick such node u' XG (x)( n S... By the WL-condition (Proposition C.4), (Nc(w)) n Xa (xa())) 2 2, which implies |S, Xo
Xo(e). Note that e' must connect to a node with color
xax (xa(()) 2 2. Thus (xa'(xai (v)(v)) n S.Me * 0
holds, which is exactly the condition (ii). This paragraph is illustrated in Figure 6(b).
Based the above two paragraphs, by symmetry we can without loss of generality assume Xe (xa(u)) n. # 0 and (x (xo(w) (S)) + 0. We are now ready to derive a contradic- tion. To do this, pick u arg max wEx" (xa(a)) (xxa(xxa()) disc(u, w) and separately consider the following
two cases:
u E Sn. Then by picking a node x E S, n xa (xa(u),, it follows that dis (z, ū) = diso(I, v) + diso(u, ū) disa(u, ū).
31

---

Published as a conference paper at ICLR 2023
Su
S.
5u
(a)
S.
P
Pa
Su
S.
P2
(b)
@
Figure 7: Illustration of the proof of
Figure 6: Illustration of the proof of Lemma C.27.
Lemma C.28.
û E S.. Then by picking a node x E (Sw nxa disg(1, u) + disc (u, ū) (us ü).
(Xanxx'xxxuu)) (xa(4))) follows that disg (z, ù) 2
In both cases, x and u cannot have the same color under SPD-WL. because
max disc(u, w) = disc(u, (2, ū) < disa(r, ū) wEXe (xa(w)
max wExa (xa(u))
disa (2, w).
This yields a contradiction and concludes the proof.
Based Lemma C.27, in the subsequent proof we can without loss of generality assume XG (xa(u)) nS, = {u} and xxa(()))) ns, 0. This leads to the following lemma:
Lemma C.28. For any u1, u2 XG (xo(u)), in # u2 any path from u1 to u2 goes through node v E Xo X (xc(v)).
Proof. Note that XG (xa(u)) n ns = (u]. If (xo()) n Syl I 1, the conclusion is clear since any path from #j to u2 goes through v. Now suppose Ixo (xa(u)) n S.l and the lemma does not hold. Then there exist two different nodes u/, th XG (xc(u) n S, and path from wf to u/ without going through any node in the set Xa (xo(t)) Pick ut, u2 and P such that the length PP is minimal. Split P into two parts Pi and P2 with endpoints {ur, w] and {w, u2} such that |P| S [Pg S IP1 tui,ug] & Eg (otherwise u cannot have the same color as #1 because X (u) n S, {u)). Therefore, w * and w * U2. Also note that XG(w) * xa(u) since PI is minimal. Since SPD-WL satisfies the WL-condition (Proposition C.4), there is path (not necessarily simple) from to some w' XG (xo(w)) of length [P without going through nodes in the set XG (XG(v)) (according to Lemma C.7). Therefore, w/ E S.. See Figure 6 for illustration of this paragraph.
and IPI + P2 = |Pl. Note that [P] 2 2 since
We next prove that dusg(u, w') = PP First, we obviously have disg (u, w') S |Pll. Moreover, since w', E S2 and xa (xa(()) nS,, S2 = 0 (Lemma C.27), any shortest path from w' to u does not go through nodes in the set Xa (x)( Again using the WL-condition. there exists path P3 (not necessarily simple) from to some U3 XG (xa(u)) of length [Ps disc(u, w') without going through nodes in the set Xa (xx())) (according to Lemma C.7). It follows that uy Sg. Consider the following two cases:
If Ug u1, by the minimal length of P we have PP S |&l diss (u, w/) $ |Ps| and thus disc (u, w²) P-
If us # u1, by linking the path P1 and Ps. there will be path of length |P + |Psl from to ug without going through nodes in XG (xc())). Since P has the minimal length,
P + Pa < P Pal. Therefore, [P S Pg = dis w²) and thus by definition
P Pa < disc w') PP.. Therefore, [Pl PPal disc(u, w').
32

---

Published as a conference paper at ICLR 2023
Now define the set (zx) ful d' E XG (x)()), disc (2. u²) < P21].. Let focus the
cardinality of the sets ((w) and D(w'). It follows that D(w") = {u], because for any other node u' E XG (xa(u)), u' * u, we have u' E S, and thus
disa(w', u²) discr(ut ,)) - disc(w' u) +1 |P| 2 Pa-.
Therefore, (D(w")]
1. On the other hand, we clearly have [P(w) > 2 since both #1 u2 D(w). Consequently, and w' cannot have the same color under the SPD-WL algorithm because [D(w')] + [D(w")] This yields contradiction and completes the proof.
The next lemma presents an important property of the color graph G (defined in Definition C.26).
Lemma C.29. GC has a cut edge ([xc(u), xc(v)
Proof. Suppose (xa(u). Xx( B is not cut edge of GC, Then there is simple cycle (cI.-... C.2) where = (G(u), Cm xx(() and m > 2. Namely, there exists a simple path from to cm with length 2 2. By the definition of G and the WL.-condition, there exists a sequence of nodes of G {w; i=1 where w1 and x(w:) = such that (w;, wi+1} } Eg. E [m - 1]. Note that w; & for (2..... .m) and w2 & because (C1, , ,.,, ) is a simple path. Therefore, w; E Sn for all i [m]. However, it contradicts |S (Sn Sul = 1 (Lemma C.27) since (u()m) Xa(e).
Combining Lemmas C.27 to C.29, arrived at the following corollary:
Corollary C.30. For all u' E Xa (xa(u)) and v' xxx (xo())). if (u', E Ea, then it is cut edge of G.
Proof. If {u', 3'} is not a cut edge, there is a simple cycle going through ful, v/}. Denote it as W(n)) (wi,".., where wi ut, Wm = v', m 2. By Lemma C.27, w2 xo(u), otherwise u' will connect to at least two different nodes W2, Wm E XG (xx(v)) and thus u' and u cannot have the same color under SPD-WL. L j be the index such that j = min E [m] Xa(wy) = xa(u)), then j 2. Consider the path (wi,... ; wyy. It follows that xc(w)) * xa(u) for all k E (2...... . by Lemma C.28 (otherwise there is path from node wi to some node w, Xa (xa(u) (2......)) that does not go through nodes in the set XG (x)())) a contradiction). Therefore, (xx(w)),-- Xa(w,)) )) is path of length 2 in GC from (a to (v(v) (not necessarily simple), without going through the edge Exx(u), (u))x This contradicts Lemma C.29, which says that (xa(u), (c(v) B is a cut edge in GO
Based on Lemma C.29, the cut edge (xx)()), (G(D partitions the vertices C of the color graph Go into two classes. Denote them as {Cu. C.) where (a(u) E C, and (a(v) E C.. The next corollary characterizes the structure of the node colors calculated in SPD-WL.
Corollary C.31. For any w satisfying Xc(w) E C.. there exists cut edge fu', u' e Xo (xx( v' E X2 (xc(v)), that partitions V into two classes Sw USS, u' E Sy, v' Sv, such that Xa (xa(u') S. {u'} and X (xa(v') U... 0.
Remark C.32. Corollary C.31 can be seen W E S., one can pick u' = u and v' = v. Then X (xx((')) S.r = {u'} and Xa (x)(v)) U S., 1 hold due to Lemma C.27. In general, Corollary C.31 says that all the cut edges with color (xG(u), xG(x)) play an equal role: Lemma C.27 applies for any chosen cut edge {u', v'). An illustration of Corollary C.31 is given in Figure 8(a).
generalized version of Lemma C.27. Indeed, when
Proof. By the definition of Cu, any node e E C, in the color graph can reach the node (a(u) without going through Xc)v). Therefore, there exists some u' E Xx (xa(()) such that there exists a path Pt from w to u' without going through nodes in the set XG (xa(v)). Also, there exists a node o' E (u')') with xo(v)= (t) due to the color of u'. By Corollary C.30, ful, v/} is a cut edge of G. Clearly, w E Sar.
We next prove the following fact: for any E Sw, (x(x) C.. Otherwise, I E S.. with color (x) E C, Consider the shortest path between nodes x and u', denoted (y1,". ". ,9m) where y1 x and you w'. It follows that yi E S, for all i E [m]. Denote
can pick node
33

---

Published as a conference paper at ICLR 2023
S
S+
P
(a) Figure 8: Illustration of Corollary C.31 I and its proof.
(b)
= E [m]] Then (cI, ,Cm Now pick the index j max E [m] Cj E C.3 (which is well-defined because ei E C.). It follows that j < m (since ym E Cu), Cj (v) and cj+1 = Xc(u) ) (because (x((u))xx(v) is a cut edge that partitions the color graph GC into C. and C.). Consider the following twO cases (see Figure 8(b) for an illustration):
} is a path (not necessarily simple) in the color graph GO
j = m - 1. Then u' connects to both nodes yj and v' with color (v;) Xa = Xc(e). This contradicts Lemma C.27 since only connects to one node with color XG()).
j < m - 1. Then Ms+1 * u' because the path (y1.... Fm) is simple. Howover, one has (a( # Xc(v) for all E [i+1,.... .m by definition j. This contradicts Lemma C.28.
This completes the proof that for any x Sw, xa(x) Cu. Therefore, Xa' (xa(("))) 0.
{u'). If not, pick w" Xa (xc(u)) and u" + u' By Lemma C.28, the shortest path between u' and u" goes through some node e" with color (c().. Clearly, v" Sg, which contradicts the above paragraph and concludes the proof.
We finally prove that X X (x
We have already fully characterized the properties of cut edges {ud, v/} with color (xa(u), xa(u)); Now we switch our focus to the graph H. We first prove general result that holds for arbitrary H.
Lemma C.33. Let {w1, w2} Eh and is a path with the minimum length from wi to wz withous going through edge (w1, ).,, In other words, linking path P with the edge {wi, w2 forms simple cycle Q. Then for any two nodes Iı, T2 in Q, dish (I1, x2) = disq (2))
Proof. Split the cycle Q into two paths QI and Q2 with endpoints {#1, where Q1 contains the edge {wi, 32} } and Q2 does not contain {wi, W2). Assume the above lemma does not hold and diss (w, x) < dis (w, x). means that there exists a path R in H from #1 to 22 for which I < min([Qal. Q2)). Note that the edge {u, r occurs at most once in R. Separately consider two cases:
{wi, ( occurs in R. Then linking R with Q2 forms cycle that contains {w1, W2) exactly once;
[wi, }2} does not occur in R. Then linking R with Q1 forms cycle that contains {w,, w. exactly once.
In both cases, the eycle has length less than IQ]- This contradicts the condition that P is path with minimum length from wi to Wy without passing edge {w1, w2).
We can similarly consider the color graph H = (Ho defined in Definition C.26. Note that we have assumed that the graph representations of G and H are the same, i.e. {xa(w)= E VB [ (x) : w E VB. It follows that HC isomorphic to GC and the identity vertex mapping is an isomorphism i.e., (c1, cut edge of H (Lemma C.29) that splits the vertices C into two classes C,, C, Since the vertex labels of H are not important, we can without abuse of notation let u, v be nodes such that
Ege = ffc,, o2 E Enc. Therefore, (()) (c()) is
34

---

Published as a conference paper at ICLR 2023
Syle
S/
w
(a) Graph H
(b) Graph G
Figure 9: Illustrations to help understand the proof of the main result.
{u, E EH, (H())= = =xc(u), (v) = Xo(r), and (=(u) E Cu. XH(U) E C.. We similarly
define Xii (c) {w E V: xH(ww = c}. Define a mapping h : C + (xm(();xx(u)) where
h(c) = {
Xu(uu) if dis (c. Xxr(u)) < disgo (cr (V) if disyo (c, (u)) dis (c, (u)).
(1I)
Note that it never happens that ge e (c, xu(()) disge (c, (x))) because (xx(w), xm(() is a cut edge of H²C
Assume (u, v) is not cut edge in H. Then there exists a path (wi,,.., W.n) in H with wi and Wm = v without going through {u, v}. We pick such a path with the minimum length, C. and h(xH(v))
C., there is a minimum index j E [m - 1] such that h(xu (w,)) E Cu and ((xH(w)+1) E C.. By definition of Cu, C. and the cut edge x (u), X# (v)B. B. it follows that (H())) = XH(") (u) and Xar (W)+11)
then the path is simple. Since h(xH(u))
X# (v). Denote u' : wy. Note that * 1 and * 2, otherwise either connects to two nodes W2 and tim with color X (w22) = X (Wm)
(H), or connects to the node u' with color (u') = X (w), contradicting X (u) = Xa(u). Pick k []. By Lemma C.33, (wi, wy) is the shortest path between u and wk. and (urk ........ wy) is the shortest path between Wi and u'. We give an illustration of the structure of H in Figure 9()) based on this paragraph.
Since the graph representations of and H are the same under SPD-WL, there exists a node w' with color xa(w") Xa (wk) and two different nodes u/, u/ with color xa())) xa(u,) = Xa (u( such that tus ut) = dis (wy, u1) and disg(w', ug) = disæ (Wk, u2). In particular, Idiso(w', w() - dws u6]l 1. Note that by the definition of indices j and k. in the color graph Ho there is path from Xa (wx) to (u) without going through nodes in the set Xi (xx(e)), so XH (wx) E Cu. namely Xa(w") E C... By Corollary C.31, there is a cut edge {u e that partitions G into two vertex sets S. S with w', ui, E Sug. Uny S Note that ui, # u/ and u/a, * u/ (otherwise by Corollary C.31 any path from w' to node u' * u/y with color Xa (u') = Xa(u) must first go through u/ and then go through o/ implying that |disa (w', [()) disc(w' (w', ub) > 2 and yielding a contradiction). Therefore, disa (wo w/) > disc (w', viw)) and diso (w," un) > disa(w', ("))) We give an illustration of the structure of G in Figure 9(b) based on this paragraph.
Pick any Uh E Xir (u) satisfying dis (Cw,, wx) = disc w'). Denote the operation dropmin(S) = S S (min SB that takes a multiset S and removes one of the minimum elements in S. We have
dropmin ((diso (w', ua)= : ua E x (xo(1))
dropmin (diss (w', v(()) + diso uc): ug Xae xa" (x)
(w's
(by Corollary C.31)
= dropmin diss (we, vw) + diss (Vw, uH) : up E x xx (u))))
and also
dropmin (f disa(w', uc) ug E Xo (xo(u))) dropmin ((dis (wx, un) : un x (x)(
due to the same color xa(w)) = (ww). Combining the above two equations and noting that dis (Wk, vw) + dis (ww un) 2 disn(ws, war), we obtain the following result: for any
35

---

Published as a conference paper at ICLR 2023
uH Xи (x= for which diss (W), (w) + dis (Bws Ux) > disc disc(w', uhe), dis (Wk, Uw)) +
dis (Uw, uH) = dis (wy,, uz). In particular,
disæ (ws; wi) = Liss(ww, uw) + dis (vo) w1), dis (wk, wy) dis (Wk, vw) + diss (Uws wy).
Therefore,
diss wy) = diss usk) + disH (wk, wz)
2dis (wk, tw) + dis (ww, w1) + dis (Var, Wy)
2 2dis (wrk, Uw) dis (wi wz):
implying wk = Uw- However, (wx) E C. while X (vw) E Co, yielding a contradiction.
C.4.2 THE CASE OF xo(u)= = (a(v) FOR CONNECTED GRAPHS
We first define several notations. Define the mapping fa : V + (u,0} x C as follows: fa(w) = (o((w) where
ha(w) = { u if (ws v) = disg (w: u) + 1,
(12)
if disg (w, u) disc (w, v) + 1.
is easy to see that he is well-defined for all w E V because {u, b} is cut edge of G. We further define the following auxiliary graph:
Definition C.34. (Auxiliary graph) Define the auxiliary graph GA = (Vaa, Ega) where Van == {u, v} x and EGa == { { fa(r), fa(w2)) {wi, w2) E Ec). Note that G can have self loops, so each edge is denoted as multiset with two elements.
It is straightforward to see that there is only one edge in GA with the form ((u, (v, e2) E Ega for some G1, 02 C since {u, #} is cut edge of G. Therefore, the only edge (u, xc))),, (v, xG(()) and is cut edge in G.A.
We also define fG as the inverse mapping of fa. i.e. fo (2,e) fw E V: fo(() = (2,c)), We first prove that f is well-defined on the domain Vea.
Lemma C.35. Ja is surjection.
Proof. Suppose that fc is not a surjection. Then there exists a color E C such that either fo (u, c) or fō (u,c) is empty set. Without loss of generality, assume (v, 0, then (u, + V. Pick any E Ja (u, c). Obviously, A u (otherwise fa (v. xa)))) = 0, a contradiction). Then we claim that for any I Na((w,, f (u,(x)) empty. Note that x E (u, the claim does not hold, take x' E fōr (v, (z)).) Since x connects (x) = (x()), x' must also connect to node with color c. Denote the node that connects to a! with color as w'. Then w' E f (v,c), yielding a contradiction.
If node with color e and
By induction, for any such that there exists a path from x to w without going through the edge {u, v}, we have fe (v. (v, x=(x)) [[]]] = 0. This finally implies fø (v. (a())) 0, leading to contra- diction. Therefore, / is a surjection.
Lemma C.36. 16 (u. xa(u))l = -If IV, (cx))())))=1
Proof. Pick u' = arg max = disc(u, u') and similarly pick v'. It follows that any path between u' and o' goes through edge {u, v). Therefore, (us v') diso(u, +dig o')+1. Since all nodes u, u', U, o' have the same color under SPD-WL, there exists node w E Xa (u)) satisfying disc(u, w) = disc(u' v') and thus disc(u, w) > (u, u'). By definition of the node u'. f * (u, x(1)) and thus fa(w) = (v, x()).. Therefore, disc(u, w) = disc(v, w) + 1, which implies that
disc(v, w) = disc (v, e') + disc (u, u').
Since disg(v, w) I dis (v, v²), we have dis w) = dis u²) and u = w. A similar argument yields v., finishing the proof.
36

---

Published as a conference paper at ICLR 2023
We can now prove some useful properties of the auxiliary graph G based on Lemmas C.35 and C.36. Corollary C.37. For any C2 E C, ((u, (u, &Ør if and only (1,)))
Ega.
E Egg, then there exists two vertices w1 E fo (u, a) and w2 E fa (u, 62) such that (wi, w2] E Eg. By Lemma C.36, either XG(w1) + (a( xc(w2) # xa(u). Without loss of generality, assume e # xe(u). By Lemma C.35, there exists 21 E fo ct). Since Xa(x1) = xa(w1), I1 must also connect to node 22 with x2((2) = Cz. The edge (2) + {u, o because (c(x1) = aj # Xa(u). Therefore, f(22) = (v, o2), namely (((e, (2, E Eg.
Proof. By definition of Eg. if
The following lemma establishes the distance relationship between graphs G and GA, Lemma C.38. The following holds:
For any w, w' E V, disc(w, w²) 2 (f(s) f(w)))
For any E E VA and any node w E (G)( there exists a node wt E S SC'(5") such that disg(w, w') = disga (E.
Proof. The first bullet is trivial since for all fw, w'} Ec. KS(w), E EGg by Defini- tion C.34. We prove the second bullet in the following. Note that G can have self-loops, but for any 5.5' E VA, the shortest path between & and e will not go through self-loops. We only need to prove that for all (EE, E EA, & * &' and all that fw, w'} E Eg. This will imply that (w, w²) I (Es and completes the proof by combining the first bullet in Lemma C.38.
(=()). fc (E), there exists w' fo (5') such
The case of &E = (u, Xx(u)), (v. Xa( is trivial. Now assume that K * ((u, xa())), (U)))( H. By Definition C.34, there exists x E fo and x' E (f'((5)) such that x0 E Eg. Note that ho(x) = ha(x') because {x,x²) * (u, Since Xa(2) = Xe(w), there exists w E Xx (xa(x)) such that {w, w/) E EG. It must hold that he(w) ho(w') (otherwise {w, w') = (u, and thus E = ((u, (v, xa()))). Therefore, ha(w") = ha (w) he(z) = ha()") and thus fa(w") = fa("") namely w' E fc (5').
Lemma C.38 leads to the following corollary: Corollary C.39. The following holds:
For any w, wt E V satisfying Xc(w) = xc(w") and ha(w) ha(w") (Le fa(w) fa(w')), (u, w) = disc(u, w²) and disalv, w) disa(v, w');
For any w, w/ E V satisfying Xa(w) xa(w") and ha(w) * ha(w"), disa(u, w) disa(v, w') and disc(v, w) = disa(u,
Proof. Proof of the first bullet: by Lemma C.38. there exists two nodes u1, U2 fo. (fa(u)) such that disc duiso(11)) w) = disga (fa (fa(w), faw)) and disc(ug, w²) = disga (fa fa(w")) Therefore, (ui, w) disc (u2, w'). However, by Lemma C.36 and the condition (w)) ho(w"), it must be 01 = U2 = u, namely dis w) = disa w²). The proof of disa(v, w) = disc (u', w') similar.
Proof of the second bullet: Let xc(w) = Xa(w)=== =c. Without loss of generality, assume fa(w) = (u,c) and J(w') (v,c). By Lemma C.38, it suffices to prove that disçA ((u, xa(()), (u,c))
disga ((v, (x())) (v, c)). By the definition of GA and its cut edge ((,,, (a(),, (v. (o())))) the shortest path between (u, (u)) and (u, c) must only go through nodes in the set ((u, q e C). and similarly the shortest path between (c, Xo(e)) and (v.c) must only go through nodes in {(v, (2) C2 E C). Finally, Corollary C.37 says that for Cı, 02 C, (((,,))) (2, (1, E GA if and only if ((V),1). e2) E GA. We thus conclude that disca ((1, (u, =
disga (Vv (x)))), (v, c)) and disg(u, w) = disc (v, w').
Finally, we can prove the following important corollary:
37

---

Published as a conference paper at ICLR 2023
Corollary C.40. For any c C, lif (u, lfa (v,e)]-
Proof. Pick any w Sā (u, c) and æ E fa (u, c). By Corollary C.39, have disc(w, u) (1, u) == d,
disa v) disc (z, u) d + 1.
The multiset [dissc (u, w') Xa(w") = cß contains |fG (u, c)l elements of value d and lif (u, c) elements of value d + 1. The multiset (diss(v, w') : xe(w") = eß has Ife (u,c)) elements of value d and lifG (u, c)l elements of value d + 1. Since u and v has the same color under SPD-WLL WWL, the two multiset must be equivalent. Therefore, ( c)l = Ife (v,))-
Next, we switch our focus to the graph H. Since we have assumed that the graph representations of G and H are the same, ie. (x)(w) w VB (x=(w)= : w VB. the size of the set {w E V Xu = Xa(u)} must be We may denote the elements as u and v without abuse of notation and thus (u. v) Eτ. Also for any V, have dis (w, u) # disn (w, v). Therefore, we can similarly define the mapping fH : + {u. u) x V and the mapping hu V - (u, v) as in
(12). The auxiliary graph /AA is defined analogous to Definition C.34.
Lemma C.41. For any c C. If (u,c) = 1f (u,c) = Iif (u, e) = =I)''v,,c]
(=(") = clf * {[iss (v, w) xH(w) = c... implying that u and v cannot have the same color under SPD-WL This already concludes the proof by using Corollary C.40 as
Proof. If |5 (u,c)) * I (te, c) we have ( (w,
(w, w)
V cu) 1/ (v. e)l = I5a (M,
c)l (v,
We finally present a technical lemma which will be used in the subsequent proof. Lemma C.42. Given node w V and color E C, define multisets
Da,-(w, c) = (diss(w; x)) x
(xx) ho(w)]: B}
D (w, c) == disss (w, x): : x E X2 (c), (z(() & ha(w)]-
For any two nodes w. w/ E V in graphs G and H satisfying Xc(w) = xu(w"), pick any d e D (w, c) and d' Dw, c). Then d' d.
Proof. Without loss of generality, assume ha(w) = hw(w²) u and let fa(w) = fu(w") = fa'(v, c) and x' E fH (u, c). then ( min(disa u), disc (x,, v)) and dis'(w', u) = minnniss (w, u), disa (w, v)). Thus
(u, Cw). Pick E fo (v.
dis (w', x²) s (ws, u) + disH (iiss(u,30)) x')
min min(diso u), disc v)) + min(disa w), disa (ar, v)) min(diso u) + diso(r, v), diso(w, v) + disa(r, u)) + 1
disa(w, x),
which concludes the proof.
In the following, we will prove that {u, r) is a cut edge in graph H. Consider an edge Il (u, ci), (u, e2) B EY (such an edge exists because Il (u. XH (u)), (v. xx (v))B E EA). We will prove that this is the only case, i.c. it must be = XH(²) = XH (T) o2.
By Definition C.34, (((,, ci), (v, 02) E EHa implies that there exists two nodes x' E F (u, e1) and w' E ff (v, e2). such that {w', x'} E Eg. Pick w E X2 (c2). xe2) By Lemma C.42, (w. n D (w, 01) = 0. Since w/ and have the same color under SPD-WL,
Du.=(w', (1) U UDH
(w', (w' .1) = (G,= c1) U DG. (w),a).
(w', ci) = - (w', cI) = IDc.= (w, ci) = |Da. (w, di)l. Therefore, By Lemma C.41, [DH1,1HH.- (D,,-
De (w, c1) = Dr (w',ii). We claim that all elements in the set Df (w, ci) are the same. This is because for any E X6 (cI), (x)x)) # ha(w), we have
disa(w, x)) diso(w, h M(w)) + 1 disg (h(z))
38

---

Published as a conference paper at ICLR 2023
and by Corollary C.39 disc(w, h(w)) (or disc (h() has equal value for different Since fu', ,''} E Eg, we have 1 E DH,+("' c1) and thus all elements in D (w, 61) equals 1. There- fore, e Xo(u). Analogously, C (u). Therefore,
Xn (u) (n( C2.
Let S, = {w E NV: (u)) = w} and S, = {w E V. hn((w) = v}. Then the above argument implies that if w E Su, S, and {w, x: Eg. then (w,z) {u, v). Therefore {u, v) is edge of graph H.
C.4.3 THE GENERAL CASE
The above proof assumes that the graphs G and H are both connected, and their graph representa- tions euqal, i.e. (xo(w) : VB (x (w: : VB- In the subsequent proof we remove these assumptions and prove the general setting.
Lemma C.43. Either of the following two properties holds:
(xo(w) VB (x) E VB:
Hxa(w): w E VB n (x=(w)) : w VB = 0.
Proof. Consider the GD-WI procedure defined in Algorithm 4 with arbitrary distance function dg- Suppose at iteration 2 T, (w)( E VB + (w) VB. Then at iteration t + 1, we
have for each v E V.
XG (v) hash ((hash(da()) u), xa(u)) : E
Therefore, XG (v) *
++1 XG (1) for all u, V. namely
lx (w) : w E VB n (w) : w VJ =
Finally, by the injective property of the hash function, for any t > T'+ the above equation always holds. Therefore, the stable color mappings XG and XH satisfy Lemma C.43.
The above lemma implies that if there exists edges {wi, E Eg. fa1. Ø2} E Eh satisfying (xa(wi); xa (w2) (xx((1) X# (x2) then (x)(w) w E VB (xx(w)= w VB. Also, SPD-WL ensures that both graphs are either connected or disconnected. If they are both con- nected, the previous proof (Appendices C.4.1 and C.4.2) ensures that [w1, w2] is cut edge of G and only if {.1.22] 222 is cut edge of H. For the disconnected case, let Sg C V be the largest con- nected component containing nodes W1, W2, and similarly denote Sh C V as the largest connected component containing nodes 32, Obviously, |Sal = |S due to the facts that disa(w1, y) oo * disg (w1, 3/) for all & Sg.y y E SG and that the two edges {w1, w2] E Ec. {01, have the same color under SPD-WP WL. Morcover, (xa(w) consider re-execute the SPD-WL algorithm on subgraphs G[Sa] and H[Sh] induced by the vertices in set So and SH, respectively. It follows that for any ug E Sq and us E SH. Xo (uc)) = Xu (uw)
E SG
{x=(w) w SH B. Now
implies that XG]Sa] (uG) (UG) = [H]Ss]] (.)) Therefore, (Wi, w2) } is a cut edge of G[Sa] if and only {21, 222 } is a cut edge of H [S By the dinifition of Sg and SH. {wi, wy } is a cut edge of G if and only if (æ1, 222 } is cut edge of H.
remains to prove that (xx(w): w E VB = [xx(w) : w E BB implics BCETree(G) BCETreo (H). By definition of the block cut-edge tree, each edge of G corresponds to a tree edge in BCETrec(G) and each biconnected component of G corresponds to a node of (C).. We still only focus on the case of connected graphs G, H, and is straightfor- ward to extend the proof to the general (disconnected) case using a similar technique as the previous paragraph.
Given fixed SPD-WL graph representation R, consider any graphs G = (V, Ec) satisfying (xa(w) VB = R. Since we have proved that the SPD-WL node feature Xc(e), V precisely locates all the cut edges, the multiset
C (xxx(())xx(o)) {u,0] Eg is a cut edge]}
is fixed (fully determined by R. not G). Denote cV := U(en o2) as the set that contains the color of endpoints of all cut edges. For each cut edge {u, f) Ec, denote Sa, and Sa be
39

---

Published as a conference paper at ICLR 2023
the vertex partition corresponding to the two connected components after removing the edge {u, v), satisfying u E Sg,u. E SG,u, Sc,u SS = 0. Sç,a U SG. = V. It suffices to prove that given a cut edge {u, u) E &G with color (xa(u), Xa (v)) the multiset (xa(w) : E SG.u. Xc(w) E CV B can be determined purely based on R and the edge color (u), X (c((v)] B. rather than the specific graph G or edge {u, v). This basically concludes the proof, since the BCETree can be uniquely constructed as follows: if (xx(w)
Sc.u. XG(() E C = ffx((u) (L.e. with only one element), then (x)( ( is a leaf edge of the BCETree such that Xa(u) connects to a biconnected component that is leaf of the BCETree. After finding all the leaf edges, we can then find the BCETree edges that connect to leaf edges and determine which leaf edges they connect. The procedure can be recursively executed until the full BCETree is constructed. The whole procedure does not depend on the specific graph G and only depends on R.
We now show how to determine (xx(w) w E Sc,,, (ww)) E CVB given cut edge {u, v} &G with color (xc))) Define the multiset
D(c1, 02) =
= (diso x) xx
(w (c)) can be picked arbitrarily)
Note that Dcc 02) is well-defined (does not depend on w) by definition of the SPD-WL color. For any Cu, Co E C pick arbitrary cut edge {u, v) with color xc(u) = cu, (G) = Co. Define
T(cu, Co) = U McB [( c) D(co,
(13)
CECV
where [[BB x m denotes a multiset with m repeated elements c, and D(c,, c) +1 = fdd
d E D(Cu; B) Intuitively speaking, T(cu, Cy) corresponds to the color of all nodes E V such that disc (t, w) + = di, w) and Xa E CV. Therefore, T(e,, c.) is exactly the multiset (xa(w) w E Xc CV B and we have completed the proof.
C.5 PROOF OF THEOREM 4.2
Theorem C.4.. Let G &V)&)) and 11 (V,EH) be two graphs, and let xa and Xu be the corresponding RD-WE WL color mapping. Then the following holds:
For any two nodes w in G and x E V in H. if xf XH (z), then w a cut vertex of G if and only if x is a cut vertex of H.
If the graph representations of G and H are the same under RD-WL, then their block cut-vertex trees (Definition 2.4) are isomorphic. Mathematically, (xa(w) E VB [xH(w)= : w E VB implies that BCVTroo(G) BCCTrro(H).
Proof Sketch. First observe that Lemma C.43 holds for general distances and thus applies here. Therefore, if Xa(w) (w) = x (x)( the graph representations will be the same, i.e. (xc(w)= w e E VB. By a similar analysis as SPD-WL (Appendix C.4.3), we can only
vB = (xx(w) focus on the case that both graphs are connected. We prove the first bullet of Theorem 4.2 in Appendix C.5.1 and prove the second bullet in Appendix C.5.2, both assuming that G and H are connected and their graph representations are the same.
C.5.1 PROOF OF THE FIRST PART
We first present a key property of the Resistance Distance, which surprisingly relates to the cut vertices in graph.
Lemma C.45. Let G = (V,E) be a connected graph and v V. Then v is a cut vertex of G if R and only if there exists two nodes u, E V, u U. 4 v, such that (u, v) disB( w) dis (u, w).
Proof. We use the key finding that the Resistance Distance is equivalent to the Commute Time Dis- tance multiplied by a constant (Chandra et al., 1996, see also Appendix E.2), i.c. dis w) 2 El R w). Here, the Commute Time Distance is defined as ( (, w) := ho w) + he (w, u) where (u, w) is the average hitting time from in random walk (Appendix E.2).
40

---

Published as a conference paper at ICLR 2023
If is not cut vertex, given any nodes w. # u, all hitting paths Puw from to (not necessarily simple) into two sets Paw and P uw such that all paths p Puw contain and path P E P contains v. Clearly, Puw + and P * 0. Given path P (zg.--. ;nn). define the probability function g(P) T 1/ dega(1;). Then by definitions of the average hitting time h.
can partition the set of
ha(u, w)
Σ PEPaw
E IP)+
Σ
p(P) IPI
PEP
PEP
Σ
((P))(())))()))+)))))))))))))))) (PI)
Σ
(P))
PP
PIEP PEEPo
PEP
Σ ((P))PP
Σ ((Pp)
Σ
(p))
Σ g(Pi)
PEP wv
P.PP
PLEP
REP 0v
+ Σ (P))PI
PEP sw
$ Σ (
E (())p|+
E
(P))
PEP uc
PEP um
PEP
Σ (P)PP|+
Σ
(P))PP+
Σ PP))PP)
PEP us
PEPS.
PEP
= hu(u,,) v) + ho(v, w).
We can similarly prove that ha(w, u) < ha v) ha(u, u).
If is a cut vertex, then there exists different nodes u, w E V, + u, + v, such that any path from u to w goes through v. A similar analysis yields the conclusion that he (u, w) he (u, v) + ha w) and (w u) ho(w, v) ho(v, u).
This completes the proof of Lemma C.45.
In the subsequent proof, assume u E V is cut vertex of G. and let { (m 2) be the partition of the vertex set VV (u), representing each connected component after removing node u. We have the following lemma (which has similar form as Lemma C.27):
Lemma C.46. There is at most one set S satisfying S. n X (xc(w)) # 0. other words, if S, n (xc(u)) # 0 for some [m], then for any E [m]] and j # i, S₁ n (xa((x(()))
Proof. Let u, arg max o'ea (xa(w)) (u, w/). If u, then S; n xa (xa(w) (xa((x(()) = 0 for all i [m] and thus Lemma C.46 clearly holds. Otherwise, u, E S, for some i. We will prove that for any j + S; nx S (xa(u)) 0.
S, If the above conclusion does not holds, then can pick a set S, and a vertex u, &S 1 (xa(u))- Since is cut vertex and S, S₁ are different connected components, by Lemma C.45 we have dish Uz) dist u) + (1, uz) > dis (u,, u). This yields a contradiction because max, (xx() (x)( dis (u, u') o max max (xc(w)) disg w'), which means that and u, not have the same RD-WL color.
The next lemma presents key result which is similar to Corollary C.30.
Lemma C.47. For all u' xa" (xo(u)), ul it is cut vertex of G.
Proof. If Ixa' (xa())) = 1, then Lemma C.47 clearly holds. Otherwise, by Lemma C.46 there exists two sets S, and S, satisfying S, S.nxa (xa(u)) + 0. S, nxxa (xo())) 0. Since S, * 0,
41

---

Published as a conference paper at ICLR 2023
can pick Sj with color xo(w) * Xa(u). Pick u' E S (xo(u)). Since xa(u) = xo(u'), there exists node w' XG (xc(w)) such that disg (u, w) = dis w'). Then we have
( u) d (u, u²) u" x Ex (xa(u))) (14) (dis u²) u" E xa (xa())) (ddis u') + disg ( u²) u" E ex (xc(u)) (15)
where (14) holds because is cut vertex and all u" f u are in the set St but w E Sj (Lemma C.46), and (15) holds because (u) xa(u'). On the other hands,
(diss (ue u²): u" E E (xo(u)) (ddisg (o","""""") u" E xa exa'(x(()))
Therefore, dis (w, x²") dis n') + disg u²) for all u" xa then clearly u" # u' and u" & w. Lemma C.45 shows that u' is a cut vertex, which concludes the proof. See Figure 10 for an illustration of the above proof.
xa" (xo(u)). Pick u" u,
Using a similar proof technique as the one in Lemma C.47, we prove the first bullet of Theorem 4.2. Note that have E VB = (xx(w) w E VB. First consider the case when Ixe Ixa (xo(u)) > 1. Pick wH E XH (xa(w) where is defined in the proof of Lemma C.47. Then, there exists uh E X (xa(u)) satisfying dis R (WH, uH) = (w, u). Pick another node n'n E Xi x (xx(")), dnn * un (this is feasible as Ix (xx(u)) > 1). Following the proce- dure of the above proof, we can obtain that dis (WH, v") = dis (WH, un)+ d (uH, u²) for all u" E ExH (xa())).. There- R fore, dish (wn, u(z) dis (wHr; un) + ( ug)) imply- ing uss is a cut vertex H by Lemma C.45.
sumed (xx(w)=
S
S,
w
Figure 10: Illustration of the proof of Lemma C.47.
denote the node in XH (x)(u)) as without abuse of notation. Choose arbitrary two nodes wi E S and w2 S2, then dis (wi, u) + disg (u, w2) = disg (w1, w2) (Lemma C.45). Pick any w/ E X (xa(wi)) in H. then there exists a node w/ E XH (xz()))) satisfying dis (w1,, w22 = dis (w1, wz²). We also have dis (w1, u) = ( u) and dis (wyy u) disă (w2, u) because is the unique node with color (u) in H. Therefore, dis (w1, u) + dis (u, w²) dis (w), wh) and i cut vertex in H (Lemma C.45).
Now consider the case when (x=(xx(u))
1. Then IxT (xa(w))
and
C.5.2 PROOF OF THE SECOND PART
We first introduce some notations. As before, we assume G and H are connected and (xa(w)) :
w E VB= x (w) w VB- As we will consider multiple cut vertices the following proof, we adopt the notation (5a.(u)))
which represents the set of connected components of graph G after removing node u. Here, mG(u) is the number of connected components after removing node u, which is greater than if u is cut vertex. It follows that (*)(()) Sc.:(u) = -VLu,. We further define the index set (u) == ii [ma(u)] Sa.(u) O Xa (xo(4)) = 0}. By Lemma C.46, either [M((u)l = ma(u)
or [Ma(w)) = ma(u).
Lemma C.48. Let E V be cut vertex of G. Let u' E XH (xa())), then u' is also cut vertex of H. Let i E [m)(u)) and j E (m=(w') be two indices and pick nodes w E SG,(u)) and w E SH,(w'). Assume and w' have the same color, i.e. xa(w) (u')). Then the following holds:
. If E MMlu) and E MMu(u') then dis (w, u) = R (w', ('),
. if E Mo(u) and j & Mu(('', then disk (w,, (w, u) < dis (w', u²).
Proof. Proof of the first bullet: since i e Mc(u), any path from w to node ug E Xo Xo' (xa()) goes through the cut vertex u, implying min (xa(()) dis (w, (w, uc) d u). Similarly,
42

---

Published as a conference paper at ICLR 2023
since MM(uu)) min Ex (xi((()) dish (w', uz) dis (w', u')) Since the color of nodes and w/ are the same under RD-WL, we have
min Myr EXE (xH(
dis (w', un)
min uoExa (xa(1))
R dis (w, ua)
and thus dis R (w', u') disg (w, u).
Proof of the second bullet: first note that dis Hi (w', u') 2 dis (w, u) because di u')= 2
min u (xo((r))
dis (w', ,HH) ua (xa(u))
min disg uc) dis u).
If the lemma does not hold, then dis t (w', u') = disă (w u). Consequentl.
(w, ua) ug E Xa (xa())) = (w: u) + (u, ua) ua E (xo'(x(())) ddis (w', u') + dis (u', un) un E xii (xm((())
On the other hands,
(w, uc) uh (xa( Adiis (w un) un E Xn (xH((
Therefore, dis (w', (w', uH) = disk w') + ( (u', uH) for all uy E Xi (xH(2')). However, we can choose w" E X (xH((()))) n Suy(u') by definition of j. and clearly disH (w', u²) < disH (w', u') + (u', u²) because w' and u" are in the same connected component (Lemma C.45). This yields a contradiction and concludes the proof.
G. Corollary C.49. Let u E V be a cut vertex G. Ler E XH (xa(u)). then u' is also a cut vertex of H. Pick any (u,( and S { with indices i E Ma(u) and j E MH(w'), Then either of the following holds:
* [xc(w) : (a,( = (xu(w) w SH.j(u)B.
(xo(w) : (u) n (xx(w) w (Hn(()))))) = 0.
Proof. Assume (xa(w) nodes w E (G,((() in G and w/ E Su,;(w) in H. satisfying xc(w) = XH (w'). Our goal is to prove that ((xa(w) any color C C, Ix (c) (a,(()) lx (c) (u)
(a)( n (x=(w): E SH,( + A. Then there exists
Sa,(u)) (xx(w)) w Su,((u)B. It thus suffices to prove that for
Define Do(w. c) (dis (w, 2) x E xa [c) and define De(w, c) = {[d + d' d' e Da(w,e) B). We next claim that
(c) Ixa (c) (x)
- () (Da(u,e) + dis (w, u))l
This is simply because for any x (c), either E (u, & Sc, If x & Sa,(u)), then dis (w, æ)) = d u) + dis (u, x) (Lemma C.45); otherwise, (w, + dis R u) +
dis (u, z). Similarly,
n (SSHs(())) (c)
1x (c) IDn(w' (Dmlul,e dis (o'',,'')) w'')ll
Noting that (x) = (c),. Do(w, c) = Dn(w', c). and dis u) dis R (Lemma C.48), we obtain IxG Sc, (c)
(w', u') (u') and conclude the proof. I
Remark C.50. As a special case, Lemma C.48 and Corollary C.49 also hold when G = H. For ex- ample, Corollary C.49 implies that for any Sc, ) and SG.j(u) such that SG., (xx((u))x((xx())) (u.(u) O nxx (x)( = 0, either of the two items in Corollary C.49 holds.
(xc(w))=
Lemma C.48 and Corollary C.49 leads the following key corollary: Corollary C.51. Let u E V be vertex in G and u' E V be veriex in H. If xfx((u) xu (u'), then mG(u)= = mn (u') and
[(xx(w): w E B (Uxn((w) w E Sn.(L') mmng('))
43

---

Published as a conference paper at ICLR 2023
Proof. both u and u' are not cut vertices, Corollary C.51 trivially holds since m mxr(u)
and (c,1(u) = V Mu, (H.( = V( Now assume u and u' are both cut vertices. We first claim that
(xa(w)= : w E Ule.a Sa,i = ((x((w) : w UiEMM(as SH,((u)B-
(16)
To prove the claim, it suffices to prove that for each color c C.C.
U
U
Sua(u')
(17)
(EMo(a)
SEMN(u')
Note that (x)(c)) = (e)- Also note that by Lemma C.48, for any two nodes wi MseMatu) Sa,(uu) n xxx" and w2 E UigMo(a) Sa,((u) n xz" we have (u, wi) <
disg (u, W2). In other words, the following two sets does not intersect:
Dø(u, c) == (dis (w, u) w UlEMa(u) Sx.
Do(u,c) == ddis (w, u) : UieMo(u) (c,( nx)
Since (u(u) = XH()),, we have Du () DD(,,)))) = ( u ()) Then (o(u, c) c)( = (u' c) n Du("', c) = 0 implies that Do(u,c) = Dz('', c) and Da(u,c) = (u',', c). This proves (17) and thus (16) holds.
We next claim that
(lxx(w)) E Sa,(u)) i Mc(u)B = (w) w Sn,(w')B i Mn(u') (18)
This simply follows by using (16) and Corollary C.49. Finally, (18) already yields the desired conclusion because:
If [Ma(u)] = mo(u), then (16) implies that
UiEMm(we (n)( UieMo Sa.((u) =1V111
and thus [MH((u)] mH('').
If [MM[u)) = ma(u) - 1, then analogously [M = (u) - 1. Furthermore, [xx((w): w E (u) : Mc(w)) lxxx((w) w E SH,( : Mu(())
because (xx VM = (xx(w): Wul}..
In both cases, Corollary C.51 holds.
We are now ready prove that (xo(w): E VB = (w) E VB implies (C) BCVTree( H). Recall that a block cut-vertex tree 3CVTTee(GT) ('), there are two types of nodes: all cut vertices of G, and all biconnected components of G. Each edge in BCV G)) is connected between a cut vertex u. E V and a biconnected component B C V such that E 13.
Given fixed RD-WL graph representation R, consider any graph G (V,Ec) satisfying [xc(w)= w E VB = R. First, all cut vertices of G can be determined purely from R using the node colors. We denote the vertex color multiset Next, the number ma(u) for each cut vertex u can be determined only by its color (=(u) (by Corol- lary C.51), which equal to the degree of node in BCVTree(GG), We now give procedure to construct BCV BCVTTeee(C G), which purely depends on R rather than the specific graph G.
CV := x(xa(u) w cut vertex of G...
We examine the multisets T(u) = fl (x)(w):: only depends on R and Xo (u) rather than the specific graph G or node u by Corollary C.51. See Figure 11(b) for an illustration of T, for four types of cut vertices u. In the first step. we find all cut vertices u such that Eser(w) 1[C S # 0] S 1 where 1[-] is the indicator function. In connected component (t) that
Sa, B. ( for all vertices u, which
other words, we find cut vertices u such that there is at most contains cut vertices. These cut vertices u will serve as "leaf (cut vertex) nodes" in BCVTree(GG) in the sense that it connects most one internal node in BCVTree(G)) The number of BCVTree leaf
44

---

Published as a conference paper at ICLR 2023
x
x
x
x
4
x 2
x
x
2
2
x x 1 x
x 2
2
x
(a) The original graph
(b) Illustration of the multisets T(u) for each cut vertex u.
(c) The first step
(d) The second step
(e) The third step
The final step
Figure 11: Illustrations for constructing the BCVTree given the graph representation R.
nodes that connect to u are also determined by Corollary C.51. See Figure 11(c) for an illustration. After finding all the "leaf (cut vertex) nodes". removing all "leaf (cut vertex) nodes" in the BCVTree, will serve as "leaf (cut vertex) node". To do this, compute for each vertex and each biconnected component B, associated with v, whether B, has no cut vertex or all cut vertices in B, correspond to the "leaf (cut vertex) nodes" in BC).ree(G). Then, check whether
then find cut vertex nodes e such that when
v satisfies ESE((N) 1[(CV (S) + 0] s 1, where the set C. contains all colors corresponding to "leaf (cut vertex) nodes". These vertices will serve new "leaf (cut vertex) nodes" when removing all "leaf (cut vertex) nodes" in the BCVTree, and the connection between such vertices and "leaf (cut vertex) nodes" can also be determined (see Figure (d) for an illustration). The procedure can recursively executed until the full BCVTree constructed (see Figure (f)),, and the whole procedure does not depend on the specific graph G and only depends on R, which completes the proof.
C.6 PROOF OF THEOREM 4.5
Given graph G (V,E), let xaa be the 2-FWL color mapping after the t-th iteration (see Algo- rithm 2 for details), and let XG be the stable 2-FWL color mapping. The following result useful for the subsequent proof:
Lemma C.52, Lef u1, u2, U1, E V be nodes in graph G and be an integer. The following holds:
Ifxc(u1 v1) = xuluu, 02), then in = Un if and only if uz = U2!
If v1) = (u2, 02), then {uz, 21 E if and only if (uz, v2) E E;
If (xn.())))) = (22 22) and t 2 1, then (ug = (ugg(u2) and dega(v1)
(vg)
45

---

Published as a conference paper at ICLR 2023
Proof. By the initial coloring (6) of 2-FW,, x2 2) can have the following three types of values:
Csame
if
(u1 01)
Cedge
if u + and {u, f E if u & and [u, v) $ 3
Cother
where Caame, Cedgo, Cother are three different colors. Therefore, if XG [1, un) = xā (gg 22), then 21 = 21 if and only ui = 2/2 and {u,, v1} E if and only {uz, 22 E For the update step,
Xal (u, v) hash (XG (u, v), Aixx (u, XG (w, u)) EV).
(19)
(x1 = Xu2u v2), then (19) implies that Hxgg (uI.w) w E VB = Ux (w2, w) : w VB and thus K E V {u1: w) E E = u E V. {uz, w) E E namely (uga((1) dego(U2). We can similarly prove that dega (1) = (02)
x Finally, note that x& (c(4),2)) = (u2, 02) implies (w,, Xa (u2. U2) using (19). This concludes the proof of the case t by simple induction.
O
For path P = (zy, ... , xd) (not necessarily simple) in graph G of length 2 1, define w(P) := (dega(x1),- ( which is tuple of length d 1. We have the following key lemma:
Lemma C.53. Lert E N be non-negative integer. Given nodes u1, U2 U1, 02 V. if ('
(u2, v2), then the following holds:
Denote P)(u,v) be the set of all paths (not necessarily simple) from node node e of length d. Then
(#1, v1)l = (Pt+i(us) 02)l-
Denote Qa(u, v) be the set of all hitting paths (not necessarily simple) from node to node v of length d. Then, (w(Q)= Q E 21+1 (b)) = (((Q)) Q (121 02) Rr and (w(Q)= : Q E (
(w((): Q u2)
Proof.
We prove the lemma by induction over iteration t. We first prove the base case = 0.
If uj U1 then by Lemma C.52 U2 U2. Note that obviously [Pi u)l and [1, u)] 0 for any node namely (21, = [Pi (w2, uz)l and Q1 u1) = (u2, (22 = D.
Similarly, if u1 * 01 and [ui, 21} & E, then by Lemma C.52 u2 + U2 and (uz, 22) & E. We also have [Pi (u,, v1)1 = [P) (u2, 02) = and Qu v1) = (u v2) = 0.
If uj # and {ur E E, then by Lemma C.52 # U2 and {uz, U2 E E. Then IPi (1), = IP (w2, r2) = and (u v1) = (w2, 02) where both sets have single element that is an empty tuple (O-dimension).
Now suppose that the conclusion of Lemma C.53 holds in iteration we will prove that it also holds in iteration t + 1. First note that for any two nodes u, [Pt+i u) = EweNo()) (Pe+ (u,w)) If [+ (un, v1) = x 2+1 (uz, U2),
then by definition of 2-FWL update formula (19)
(C'c w), Xo(w; u1)) E VD = (x'x (uz, w), Xolw, v2)) : :EEB
which implies that (x'o(11, w) w No(wi)D (x6((22 Lemma C.52. Therefore.
No( due to
By induction, ( w) w e No(v1)) (l (1) w E Nc((2)) It follows that (weNo(u,) (Pe+iuu, w)l = LweNo(ra) (P+il w)l and thus we have
[P142 v1)l = IP1+2(u2 (u2, 22)1.
By induction, ((xx(uu, w), Xa( v1), [w(() : QE (,n((,v1)B) w e (N Xaa
((x' (u2, w).xal (w,, 02), (()(Q) Q E @uti(w, 2))
No(ua) Since
Lemma C.52 says that (a( v) + (o(e, if if
we have
((x6(11 w)) (w(() : Q ( No(w))oo =l((x((u2, w)) (((())
v2) No(2
46

---

Published as a conference paper at ICLR 2023
Further using the third bullet of Lemma C.52 and rearranging the two multisets yields
Hl ((dega(w), (()))) : E No(ur))(( Q (41((w,
w = =[((deg((w) : NN((s))) Q e (41((w)
Equivalently, (w(Q)) Q E Q Q42 = (w(Q) Q Q4+2(u2, U2) We can similarly prove that (Q) : Q E 2--2(1,, un) (Q) Q E 2++2(12, U2)
This concludes the proof of the induction step.
The above lemma directly yields the following corollary: Corollary C.54. Given nodes u1, U2 E V, if xo((i, v1) = Xo(u2, 02). then disc(u1, 01) disc(u2, v2) and disg R (u1, v1) = disg (u2, v2).
Proof. If (c( 21) = Xa(u2, 02), then Xe("1, 01) X6 02) holds for all & 2 0. By Lemma C.53 (1 = [Pr 02)l holds for all 2 0 (the case = 0 trivially holds). Since disc (u, min(t: [P, ut)l > O}. we conclude that (us v1) = disa (12, v2). As for the Resistance Distance dis it is equivalent to the Commute Time Distance multiplied by constant (Chandra et al., 1996, see also Appendix E.2), i.e. disg(u, w) 2| disă(u, w). Since disg (u, r) Ei i. (EPER((u.) (P)) + (vee,()..) ((P)) where 2, v) the set contain- ing all hitting paths of length from u to v, and (PP) = 1/ (dggo()) (1) I dog(r:)) for path P = (zo. ... ,r)). By Lemma C,53, we have Eree v1) (P) = Eree. 7( (P)) and Erer(() (P)) (ve ()) for all i 2 0 (the case i = 0 trivially holds) and thus (u2, 02), namely di 01) = dis (u2, (2).
disg (1), = (
We are now ready to prove Theorem 4.5.
Theorem C.55. The 2-FWI algorithm is more powerful than both SPD-WL and RD-WL. Formally, 2FWL,
given a graph G. let XG XG SPDWLL and XG RDWWL be the vertex color mappings for these algo- rithms, respectively. Then the partition induced by XG
2FWL is finer than both XG
SPDWL and RDWL XG
Proof. Note that by definition (see Appendix B.2), we have (G(v) == Xo(2, u) for any node V. If xa((v) = xx()2), then by definition of 2-FWL aggregation formula,
(xx((11 w), (w, u1)) w VB- = If (V2, w), xa(w, 02)) w E VH.
Using Lemma C.6, if (o( (u W2) for some nodes w1 and w2, then xa(w1) Xa (W2). Therefore, by using Corollary C.54 we obtain that if (a( = Xa (12), then
[(xx(w)) diso(u, w E V = ((x((w)) disa (w, o2)) w E VB. ((x((w), dis (w,v))
VB ((xx(w), dis R (w, 02)) E VB.
SPDWL and 2PWL is finer than both XG The above equantions show that the partition induced by XG RDWL and conclude the proof. XG
Finally, the following proposition trivially holds and will be used to prove Corollary 4.6.
Proposition C.56. Given a graph G = (V, Eg), let xa and āa be two color mappings induced by two different (general) color refinement algorithms, respectively. If the vertex partition induced by the mapping XG is finer than that of Xc. then:
The mapping XG can distinguish cut vertices/edges if Xa can distinguish cut vertices/edges;
The mapping Xa can distinguish the isomorphism type of (CC.TrreeG)BBCCETeee ia can distinguish the isomorphism type of (BCVTreeeGG/BCCCC
Corollary 4.6 is simple consequence of Theorem 4.5 and Proposition C.56.
47

---

Published as conference paper at ICLR 2023
Desargues graph (a) SPD-WL fails while RD-WL succeeds.
Dodecahedron
4x4 rook's 's graph Shrikhande graph (b) Both SPD-WL and RD-WL fail.
Figure 12: Illustration of non-isomorphic distance-regular graphs.
C.7 REGARDING DISTANCE-REGUI GRAPHS
In this subsection, we give more fine- fine-grained theoretical results on the expressiveness upper bound of GD-WL WL by considering the special problem of distinguishing distance-regular graphs, a class of hard graphs that are highly relevant to the GD-WL. framework. We provide full characterization of what types of distance-regular graphs different GD-WL algorithms can or cannot distinguish, with both proofs and counterexamples.
Given a graph G EV, let (u(u)) {w E V disg(u, w) -i} be the i-hop neighbors of u G and let DGG) == maXa,veV disc(u, v) be the diameter of G. We say G distance- with disa(u, v) disc (w, æ), have (w) (2) From the definition, is straightforward to that for all
regular if for all i E [D(G) and all nodes v, w,
(Ag (v) u, and [WG (w)l (w)) (N)),, i.e., the number of i-hop neighbors is the same for all nodes. We thus denote x(G) = (k1,-.. .kD))) as the k-hop-neighbor array where k; := [ (w)l with u E V chosen arbitrarily. We next define another important array:
Definition C.57. (Intersection array) The intersection array of distance-regular graph is denoted (G) {bo. bp(cn ( .DD(G)) where [Wo(u) n N (v) and = (u) n.G
Ai-11pp (v)) with disa v) =
We now present our main results.
Theorem C.58. Let and two connected distance-regular graphs. Then the following holds:
SPD-WL can distinguish the two graphs if and only if their k-hop-neighhor arruys differ, i.e.
x(G) & k(H).
RD-WL distinguish the two graphs if and only if their intersection arrays differ, i.e.
(G') + r(H).
2-FWL can distinguish the two graphs if and only if their intersection arrays differ, i.e. (G) # ((H).
Theorem C.58 precisely characterizes the equivalence class of all distance-regular graphs for differ- ent types of algorithms. Combined the fact that ((G) ((H) implies s(G) x(H) (see e.g. van Dam et al. (2014, page 8)), we immediately arrive at the following corollary:
Corollary C.59. RD-WI BD-WL. is strictly more powerful than SPD-WL. distinguishing non-isomorphic distance-regulad graphs. Moreover, RD-WL is powerful as 2-FWL in distinguishing non- isomorphic distance-regular graphs.
Counterexamples. We provide representitive counterexamples in Figure for both SPD-WL. and RD-WL. In Figure 12(a), both the Dodecahedron and the Desargues graph have 20 vertices and the same k-hop-neighbor array (3, 6, 6, 3, 1), and thus SPD-WL cannot distinguish them. How- ever, they have the different intersection array (i.e., {3, 2, 1, 1, 2,33 for Dodecahedron and {3. 2, 2, 1, 1,1,, 1, 2, 2, 3} for the Desargues graph), and thus RD-WL can distinguish them. In Fig- 12(b),
of the well-known 4x4 rook's graph and the Shrikhande graph, both of which are strongly regular and thus distance-redt resgulce-regular. They have the same intersection array {6. 3; 1, 2} and thus both RD-WL. and 2-FWI. cannot distinguish them although they are non-isomorphic.
make
48

---

Published as a conference paper at ICLR 2023
C.7.1 PROOF THEOREM C.58
We first present lemma that links the definition of distance-regular graph its intersection array. The proof is based on the Bose-Mesnet algebra and its association scheme, and please refer to van Dam al. (2014, Sections 2.5 and 2.6) for details.
Lemma C.60. Let G and H be two graphs with the same intersection array, and suppose nodes U, w, satisfy disg v) disc(w,I). Then (u) (gg(v) [W)(w) (x)) for all 2,j N.
Proof of the first item of Theorem C.58. This part straightforward. Consider the SPD-WL color mapping Xa of graph G after the first iteration. Then for two graphs G, H with nodes, XG (u) (r) if and only if (w) = (w)l for all E [n - 1]. Therefore, if ((G) * k( k(H), then for any node in G and in H, (w)
(max(D(G)) D(H)) and thus (u) # (v). Namely, (u( # (=(v) for all nodes u in G and in H, implying that SPD-WL, can distinguish the two graphs. On the other hand, if (G)) se( H), then for any node in G and in H we have (u) X (v). Similarly, x²(u) XB (1) for any iteration i E N, and thus SPD-WL cannot distinguish the two graphs.
(T)( holds for some
Proof of the second ilem of Theorem C.58. The key insight that given distance-regular graph, the resistance distance between a pair of nodes (u, v) only depends on its SPD. Formally, for any nodes u, w, x in a distance-regular graph G, disa v) = disa (w, x) implies that dis (u, v) dis (w, 2.). Actually, we have the following stronger result:
Theorem C.61. For any two nodes u, in connected distance-regula graph G, dis (dlsc(u.)) where the sequence (ra)deo D(G) is recursively defined as follows:
ifd=0, 0,
D(G)
rd
rd-1 +
Σ ka
if (D(G).
(20)
nka-1ba-
i=d
where (G) = (bo.... 1i .D(C)} is the intersection array of G and x(G)
=
(Ki,"",,,oo ) is its k-hop-neighhor array.
Proof. Let R E R be the RD matrix. Based on Theorem E.1, R can be expressed as R dMag(M))11 + 11 diag(M) 2M, where M (L = and L is the graph Laplacian matrix. Now let R = (w,,) be the matrix with elements defined in (20). The key step is to prove that 2M c11 R for some R. This will yield
2 (iag((cI) - RR111 + 111 diag(c11 - -R)) -c11 + R R
R
(since diag R) O) and finish the proof.
We now prove 2M cll R for some E R, namely (L + 11 c1l - - 21. Note
that symmetric matrix and satisfy R.I = e for some C₁ E R because G is distance-regular: Combined the fact that L1 O, we have
L (1+111) (c11-- - = ) 11 -LR.
9 n
It thus suffices to prove that LR c11 21 for some E R. Let us calculate each element [R]uu (u, E V). We have
D(G)
LR we (iTdis((u.))
Σ
Na (dd()))
(21)
d=
Now consider the following three cases:
49

---

Published as a conference paper at ICLR 2023
u In this case, (u.") 0 and we have
D(G)
Σ ralWa(u) (o ri 2(n 1) n
by using bo - ki and kig O. Thus [LR] Ju 2(n-1)
a
u o v and disa(u, v) < D(G). Denote j = disca (u, v). In this case, in (21) the term (VV( # only when d E 1, + 1}, and by definition of intersection array
we have [Na(u) nnNg-1ll [v)] (v)] = cj. (N) nog [w) = by. and (Wo(u) (Vvo -
[a((u)] - bj = kj Cj- bn. Therefore,
LRJ uv = =kirg - 1-- - (k1 bb- - -g) - rg+1
=g((r- - -j--1) + by(r; - -rj+1)
D(G)
D(G)
20j
2bg
Σ h
Σ k;
nkg-1b9-- -1 i=j
nkzbj i=++1
D(G)
D(G)
2
Kj
Σ k2
nkj
n
i=j
where in the second last step we use the recursive relation of ry, and in the last step use the fact that K2 R for any j E [D(G]] (see c.g. van Dam et al. (2014, page 8)).
u * and disc(u. u) = D(G). This case is similar as the previous one. Denote = disc(u, v), and Nu((u) n (V(()) * only when d E {j- - 1,5}. We have
[LR] kirg -3-1C3 - T3 (Ki cÿ) = cr(rg - r)-1)
2cg
2
kj-
nkj likj-1bj-1 -う
n
where we again use ky 11-16 C2
Combining the above three cases, we conclude that LR
2 11 -2I, which finishes the proof. Li n
We are now ready to prove the main result. Let G (Vo. EG) and H = (VH, Ex) be two distance- regular graphs. We first prove that if (G) = (H). then RD-WL cannot distinguish the two graphs. This is simple consequence of Theorem C.61. Combined with the fact that k(G) x(H). we have &dis w) w E Va} {dis R f (v, w) w E VH) for any nodes u E VG and E VH. Therefore, after the first iteration, the RD-WL color mappings Xa and Xi satisfy (d) = xh (v) for all u E VG and v E Vμ. Similarly, after the f-th iteration we still have xa(u) = Xir (v) for all E VG and E VH and thus RD-WL cannot distinguish the two graphs
It remains to prove that if (G) A r(H)), then RD-WL can distinguish the two graphs. First observe that in Theorem C.61, r; < <ry holds for any i < j. Therefore, for any nodes u E Vo and v E Vn, (dis w): w Vo} {dis (v, w)
Vn if and only if
(rr(C)) x xk(G): i [D(G)] ((r:(H) x (HHH) : [D(H)),
(22)
where Br x k is multiset containing & repeated elements of value r. If (G) 4 (HH), then there exists a minimal index d such that (G) = (HH) and (G+ = (H) for all < d but b. #
b.H)) or (G- # (H). It follows by Theorem C.61 that (G) ry (H) and (, = (H) for all < but either rd41 (G) # Ta+1 (H) (if ba(G) + ba( or (G) + kat1HH) (if
ba(G)= = ba( (F) and (G) F Ca+1 (H)). Therefore, (22) does not hold and (u) * X (v) for
any u E VG and u E VH. namely, RD-WL can distinguish the two graphs.
Proof of the third item of Theorem C.58. First, if (G) # (H), then 2-FWL can distinguish graphs G and H. This is simply due to the fact that 2-FWL is more powerful than RD-WL (Theorem 4.5). It remains prove that if (G) ((H), then 2-FWI. cannot distinguish graphs G and H.
50

---

Published as a conference paper at ICLR 2023
Let XG VV x Va C be the 2-FWL color mapping of graph G after iterations. We aim to prove that for any nodes u, v E VG and w, a E VH, if disg (u, v) = disc(w, (w, æ), then (u u) XH (w,) for any t E N. We prove it by induction. The base case of 0 trivially holds. Now suppose the case of f. holds and let us consider the color mapping after t + 1 iterations. By the 2-FWL update rule (2),
(u, v) hash (xc(u,e), ((xx(l xa((, vvlc))
(23)
It thus suffices to prove that (x, z), x6 2 Vc - (1x (1, x), : Vn
(24)
By Lemma C.60, we have
{(diso (u, 2), disc (2, r)) = V& Bt- =I ([dis:(w, 2), dis (2, x)) ) VH B-
This already yields (24) by the induction result of iteration f. We thus complete the proof.
D FURTHER DISCUSSIONS WITH PRIOR WORKS
D.I KNOWN METRICS FOR MEASURING THE EXPRESSIVE POWER OF GNNS
In this subsection, we review existing metrics used in prior works to measure the expressiveness of GNNs. We will discuss the limitations of these metrics and argue why biconnectivity may serve as more reasonable and compelling criterion in designing powerful GNN architectures.
WL hierarchy. Since the discovery of the relationship between MPNNs and 1-WL test (Xu et al., 2019; Morris et al., 2019), the WL hierarchy has been considered as the most standard metric to guide designing expressive GNNs. However, achieving an expressive power that matches the 2- FWL test is already highly difficult. Indeed, each iteration of the 2-FWL algorithm already requires a complexity of (2n2) time and (n2)) space for graph with n vertices (Immerman & Lander, design expressive GNNs using this metric while maintain-
1990). Therefore, it is impossible ing its computational efficiency. Moreover, whether achieving higher-order WL expressiveness is necessary and helpful for real-world tasks has been questioned by recent works (Veličković, 2022).
Structural metries. Another line of works thus sought different metrics to measure the expressive power of GNNs. Several popular choices the ability of counting substructures (Arvind et al., 2020: Chen et al., 2020; Bouritsas et al., 2022), detecting cycles (Loukas, 2020: Vignac et al., 2020; Huang et al., 2023), calculating the graph diameter (Garg al., 2020: Loukas. 2020) other graph- related (combinatorial) problems problees (Sato et al., 2019). Yet, all these metrics have a common drawback: the corresponding problems may be too hard for GNNs to solve. Indeed, we show in Table that solving any above task requires computation complexity that grows super-linear w.r.t. the graph size even using advanced algorithms. Therefore,
quite natural that standard MPNNs not expressive for these metries, since GNNs can solve these tasks while being efficient. Consequently, instead of using GNNs to directly learn these metrics, these works had to use a precomputation step which can be costly in the worst case.
Table 4: The best computational complexity of known algorithms for solving different graph prob- lems. Here and m are the number of nodes and edges of a given graph, respectively.
Metric
Complexity
Reference
k-FWL
2(x
(Immerman & Lander, 1990)
Counting/detecting triangles
O(min m/2))
(Alon et al., 1997)
Detecting cycles an odd length 3
O(min(n 2.370 m²))
(Alon et al., 1997)
Detecting cycles of an even length & 2 4
O(n²)
(Yuster & Zwick, 1997)
Calculating the graph diameter
O(nm)
Detecting cut vertices Detecting cut edges
O(n + m) O(n + m)
(Tarjan, 1972)
(Tarjan. 1972)
Due to the lack of proper metrics, most subsequent works mainly justify the expressive power of their proposed GNNs by focusing on regular graphs (Li et al., 2020; Bevilacqua al., 2022; Bodnar
51

---

Published as a conference paper at ICLR 2023
al., 2021b; Feng et al., 2022; Velingker et al., 2022, to list few). which hardly appear in practice. In contrast, the biconnectivity metrics proposed in this paper are different from all prior metrics, in that (i) it is a basic graph property and has significant values in both theory and applications; (i) it can be efficiently calculated with a complexity linear in the graph size, and thus is reasonable to expect that these metrics should be learned by expressive GNNs.
D.2 GNNs WITH DISTANCE ENCODING
In this subsection, we review prior works that are related to our proposed GD-WLL, the research field of expressive GNNs, the idea of incorporating distance first appeared in Li et al. (2020), where the authors mainly considered using distance encoding as node features and showed that distance can help distinguish regular graphs. They also considered approach similar to k-hop aggrega- tion by incorporating distance into the message-passingg procedure (but without a systematic study). Zhang& & Li (2021) designed subgraph GNN that also uses (generalized) distance encoding as node features in each subgraph. Ying et al. (2021a) designed a Transformer architecture that incor- porates distance information and empirically showed excellent performance. Very recently, Feng et al. (2022) formally studied the expressive power of k-hop GNNs. Yet, they still restricted the analysis to regular graphs. The concurrent work of Abboud al. (2022) designed the shortest path network which is highly similar to our proposed SPD-WL. They showed the resulting model can alleviate the bottlenecks and over-squashing problems for MPNNS (Alon & Yahav, 2021; Topping et al., 2022) due to the increased receptive field.
Compared with prior works, our contribution lies in the following three aspects:
We formalize the principled and more expressive GD-WL framework, which comprises SPD-WL special case. Our framework theoretically clean and generalizes all prior works in unified manner.
We systematically and theoretically analyze the expressive power of SPD-WL for general graphs and highlight a fundamental advantage distinguishing biggebbionnnttiiitty.
We design Transformer-base GNN that is provably as expressive as GD-WL. Thus, our framework is not only for theoretical analysis, but can also be easily implemented with good empirical performance on real-world tasks.
Discussions with the concurrent work of Velingker et al. (2022). After the initial submission, we became aware of concurrent work (Velingker al., 2022) which also explored the use of Resistance Distance to enhance the expressiveness of standard MPNNs. Here, we provide a comprehensive comparison of these two works. Overall, the main difference is that their approach incorporates RD (and several related affinity measures) into node/edge features (like Zhang & Li (2021)). while we combine RD to design new WL aggregation procedure. As for the theoretical analysis, they only give few toy examples of regular graphs to justify the expressive power beyond the 1-WL test, while we give systematic analysis of the power of RD-WL for general graphs and point out that it is fully expressive for certex-biconneetii comparisons to SPD and conjectured that RD may have additional advantages than SPD in terms of expressiveness. In fact, this question is formally answered in our work, by proving that RD-WL is expressive for vertex-biconneetivii work is that we provide an upper bound of the expressive power of RD-WL be 2-FWL (3-WL), which reveals the limit of incorporating RD information. We also provide a precise and complete characterization for the expressiveness of RD-WL in distinguishing distance-regulat graphs, which reveals that RD-WI. can match the power of 2-FWI. in distinguishing these hard graphs.
In Velingker et al. (2022), the authors also made
while SPD-WL is not. Another important contribution of our
E IMPLEMENTATION OF GENERALIZED DISTANCE WEISFELLER-EEMMNN
In this section, we give implementation details of GD-WL and our proposed GNN architecture. We also give detailed analysis of its computation complexity. Below, assume the input graph G = (V,E) has vertices and m edges.
52

---

Published as a conference paper at ICLR 2023
E. PREPROCESSING SHORTEST PATH DISTANCE
Shortest Path Distance can be easily calculated using the Floyd- warddall algorithm (Floyd, 1962), which has complexity of ( For sparse graphs typically encountered practice (i.e. m )(n")), more clever way is to use breadth-first search that computes the distance from a given node to all other nodes in the graph. The time complexity can be improved to (nm)).
E.2 PREPROCESSING RESISTANCE DISTANCE
In this subsection, we first describe several important properties of Resistance Distance. Based on these properties, we give a simple yet efficient algorithm calculate Resistance Distance.
Equivalence between Resistance Distance (RD) and Commute Time Distance (CTD). Chan- dra et al. (1996) established an important relationship between RD and CTD, by proving that disg(u, r) 2m ( e) holds for any graph and any nodes u, E V. Here, the Commute Time Distance is defined as disg(u. v) = hu tr)+ u) where he v) is the average hitting time from to in random walk. Concretely, ha v) is equal to the average number of edges passed in a random walk when starting from and reaching v for the first time. Mathmatically, satisfies the following recursive relation:
if V;
hG(u, u)
00
if u and are in different connected components, otherwise.
EweNo(u) (u, v)
dega(u)
(25)
The above equation can be used to calculate CTD and thus RD, as we will show later.
Resistance Distance is graph metric. We say function de V V - R is graph metric if it is non-negative, positive semidefinite, symmetric, and satisfies triangular inequality. Let be connected graph. Then Resistance Distance disg a valid graph metric because:
(Positive semidefiniteness) dis (u, e) 2 holds for any u, v E V. Morcover, d v) =
0 iff u
(Symmetry) dis (u, v) = du, u) holds for any u, V.
(Triangular Inequality) For any u, u, w E V. dis v) + (1, w) 2 d w). This can be seen from the definition of CTD, since disg (u, v) + dis (u, w) is equal to the average hitting time from to under the condition of passing node v, which is obviously larger than dis (u, w).
(1,
Comparing RD with SPD. It is easy to that RD is always no larger than SPD, i.e. dis v) s diso v). This because for any subgraph G' of G, have dis (u, v) I dis (u, v), and when G' is chosen to contain only the edges that belong to the shortest path between and v. we have dist (u, v) = disg (u, v). Therefore, the range of RD is the same as SPD, i.c. 0 < dus (u, v) < 1. However, unlike SPD which is an integer, RD can be general rational number. RD can thus be seen as a more fine- fine-graine grained distance metric than SPD. Nevertheless, RD is still discrete and there are only finitely many possible values of dis (u, v) when is fixed.
Relationship to graph Laplacian. We have the following theorem:
Theorem E.1. Let G = EV,E) be a connected graph, V [n], and let L E S" be the graph Laplacian. Then
dis Ma,s + Mís 2M
where M E S" is symmetric matrix defined as
1
M =
L LL+ n
Proof. Denote d (dega(1),...
... .deg Define the probability matrix P such that P.y =
if {i,j} & and P.₃ //deg (i) if {i,}} E E. Then for any * j. (25) can be equivalently
53

---

Published as a conference paper at ICLR 2023
written
h(i,j) = =1+ Σ Pa - Pishh(i.))
(26)
Now define a matrix such that Hig = -1 Ex= Pu. Hkj - Pij then H. = h(i, for all i o (although Hi * 0 = h(i, i)). H can be equivalently written as
H = 11 PH ddiag(H),
(27)
where (H) is the diagnal matrix with elements H₃ for E [n]. We first calculate diag(H) (H). Noting that d = d, we have
d d 11t d (H diag(H)),
and thus d' diag(H) 11 namely
2m
ia -d d;
d di
(28)
Now define H H diag(H), then Hij h(i,j) for all i,j [n]] We will calculate H in the following proof. We first write (27) equivalently as + diag(H) = 11 + PH. Then by multiplying D, we have
D(I PJH D11 T HH) Using the fact that D(I - PT- L and (28), we obtain
(29)
LH D11 2ml.
(30)
Next, noting that L1 0, have
(1- 1 11)
L
L
(31)
One important property that the matrix (L + 111T) is invertible (see Gutman Xiao (2004,
Theorem 4) for proof). Combining (30) and (31) we have
I - H L 1 111
(D11 2ml) M (D11 - 2ml).
(32)
n
By taking diagonal elements and noting that diag (H) = -O, we otain
diag (11 (11TH) H) diag (MD11 ) 2m diag (M)
(33)
Namely,
H H MD1 + 2m diag (M) 1.
(34)
n
Substituting (34) into (32) yields
H M (D11 2m1) - 11 11 DM + 2m11" diag (M).
(35)
Therefore,
H H 2m1111 diag (M) + diag (M) 11 -2M).
(36)
This finally yields (i, the proof.
I Zm dis Ci, Im (H+H)) Mr,++ - - and concludes
Computational Complexity. The graph Laplacian can be calculated in O(n²) time, and M can be calculated by matrix inversion which requires (nn²) time. Therefore, the overall computational complexity is Onn²) (or 2-3376 using advanced matrix multiplication algorithms).
For sparse graphs typically encountered in practice (i.e. m = o(n²)) one may similarly ask whether complexity that depends
be achieved. We conjecture that it should be possible. Below,
54

---

Published as a conference paper at ICLR 2023
give another algorithm calculate (L + 11 _ Note that the graph Laplacian can be equivalently written as EE where E Rexm is defined as
2
if ; = {i,k) and lo > i = (i, and <
Egj
(37)
0
if ff
where we denote 3 {er, Em Let E = [e Em] where e, E R", then M n
(111 + - ) Noting that each e, is highly sparse with only two non-zero elements.
We suspect that Morrison- MorrisonWWoodbury update. We leave as an open problem.
obtain (nm) complexity using techniques similar the Sherman-
E.3 TRANSFORMER-BASE IMPLEMENTATION
Graphormer-GD. The model built on the Graphormer (Ying al., 2021a) model, which use the Transformer (Vaswani et al., 2017) as the backbone network. A Transformer block consists of two layers: self-attention layer followed by -eed-rd layer, with both layers having normalization (e.g., LayerNorm (Ba al., 2016)) and skip connections (He al., 2016). Denote x R=xd as the input to the (1 + 1- block and define ( X, where is the number of nodes and d is the feature dimension. For input ( the (I 1)-th block works follows:
A) =sotmmxx (x with w
(38)
X A (X X w'
(39)
((+1) = X + GELU W
(40)
where W Rdnxd, w K w h Raxdn, w E Rdxx, w E Rrxd, H is the number of attention heads, dæ is the dimension of each head, and is the dimension of the hidden layer. A A"(X) is usually referred to as the attention matrix.
Note that the self-attention layer and the feed-forward layer introduced in (39) and (40) do not encode any structural information of the input graph. As stated in Section 4, we incorporate the distance information into the attention layers of our Graphormer-Gr model. The calculation of the attention matrix in (38) is modified as:
A (x 2/ (D) O softmax (x (x (WW)) + (D)
(41)
where D Raxn the distance matrix such that Du: do v). of and @ are element-wise functions applied to D, and @ denotes the element-wise multiplication. In this way, the graph structural information can be captured by our Graphormer- model.
As stated in Section 4, we mainly consider two distance metrics: Shortest Path Distance disg and Resistance Distance d- For SPD, we follow Ying et al. (2021a) to use their shortest path distance encoding. Formally, let SPD be the SPD matrix such that DSPD = disg(u, v). The function di and Φ2 can simply be parameterized by two learnable vectors v and v². so that Φ (DSPD) is learnable scalar corresponding to "DeP (and similarly for Φτ2). two nodes u and v are not in su the same connected component, i.e., DSPD co, a special learnable scalar is assigned. For RD, we use the Gaussian Basis kernels (Scholkopf et al., 1997) to encode the value since it may not be an integer. The encoded values from different Gaussian Basis kernels are concatenated and further transformed by two-layer MLP. We integrate both the SPD encoding and the RD encoding to obtain I.h (D) and d.h (D). Note that these two matrices are parameterized by different sets of parameters. Following Ying et al. (2021a), we also incorporate the degree of each node in the input layer using degree embedding.
Relationship between Graphormer-GD and GD-WL. As stated Section 4, the expressive power of Graphormer-GD is at most as powerful WL. We will prove that it is actually powerful as GD-WL under mild assumptions. We first restate the Lemma 5 from Xu et al. (2019), which shows that sum aggregators represent injective functions over multisets.
55

---

Published as a conference paper at ICLR 2023
Lemma E.2. (Xu et al., 2019, Lemma 5) Assume the set X is countable. Then there exists function X f:
R that the function h(²) := ExE f(z) is unique for each multiset X C. X of bounded size. Moreover, any multisel function g can be decomposed as g(X) = 2Z ( ((x)) for some function
We are now ready to present the detailed proof of the Theorem 4.4, which restated as follows:
Theorem E.3. Graphormer-GD is at most as powerful as GD-WL. Moreover, when choosing proper functions of and ái and using a sufficiently large number of heads and layers, Graphormer-GD as powerful as GD-WL.
Proof. Consider all graphs with no more than n nodes. The total number of possible values of both SPD and RD are thus finite and depends n (see Appendix E.2). Let
Dr [(diso v), dis (u, u)) G = (), | S U,,
denote the set of all possible pairs (disa(u, v), dis (u,, v)). Since Dn is finite, we can list its elements as Dn = {dg.1....
Without abuse of notation, denote da(u, = (u,sa v), dis (u, v)). Then the GD-WI. aggregation in (3) can be reformulated as follows:
dG.pp..). ,......,..p.....
Xo(v) == hash (xx2 (V), Xa (v), X6
1. (u)))
(42)
6 (u) (xxx a V, do((,,)) d. where X
Intuitively, this reformulation indicates that in each iteration, GD-WL updates the color of node by hashing tuple of color multisets, where each multisct is obtained by injectively aggregating the colors of all nodes E V with certain distance configuration to node v. Therefore, express GD-WL, the model suffices update the representation each node following the above procedure.
We show Graphormer-Gr can achieve this goal. Recall that for the h-th head, the attention ma- trix defined as of (D) O softmax (X (XW)) + oli (D)). For the function of, we de- fine it to be the indicator function <f = 1[d = da.:). For the function oi, we set it to be constant irrespective to the matrix D. Let W
Q' W be zero matrices. It can be seen that
the term softmax (XW) Q (XWk) + ob (D)) reduces 1 11 and thus for each node v, the output in the h-th attention head is the sum aggregation of representations of node u satisfying da(u, v) = da Formally,
A' x
Σ
X
da(u,))=der det.
Note that the constant [V] can be extracted with an additional head and be concatenated the node representations. Moreover, the node representation X is processed via the feed-forward network in the previous layer (see (40). Thus, tion head Graphormer-Gi can implement an injective aggregating function for ([x= u E V. d,, v) de D. Therefore, by using sufficiently large number of attention heads, the multi- set representations XG E [[P,,]] can be injectively obtained.
invoke Lemma E.2 and prove that the h-th atten-
Finally, the multi-head attention defined in (39) is equivalent to first concatenating the output of each attention head and then using a linear mapping to transform the results. Thus, the concatenation clearly an injective mapping of the tuple of multisets (xx XG ..... XG (.I.a)).
When the linear mapping has irrelational weights, the projection will also be injective. Therefore, one attention layer followed by the feed-forward network can implement the aggregation formula (42). Thus, our Graphormer-Gi is able to simulate the GD-WL when using sufficiant number of layers, which concludes the proof.
t.l f.2
F EXPERIMENTAL DETAILS
F.1 SYNTHETIC TASKS
Data Generation and Evaluation Metrics. We carefully design several graph generators to exam- ine the expressive power of compared models graph biconnectivity tasks. First, include the
56

---

Published as a conference paper at ICLR 2023
two families of graphs presented in Examples C.9 and C.10 (Appendix C.2). We further introduce a rich family of regular graphs with both cut vertices and cut edges. Each graph in this family is constructed by first randomly generating several connected components and then linking them via cut edges while simultaneously ensuring that each node has the same degree. Combining the above three families of hard graphs, online generate data instances to train the compared models. For each data instance, the total number of nodes is upper bounded by 120. We use graph-level accu- racy as the metric. That is, for each graph, the prediction of the model is considered correct only when all and only the cut vertices/edges are correctly identified. We use different seeds to repeat the experiments 5 times and report the average accuracy.
Baselines. We choose several baselines with their expressive power being at different levels. First, we consider classic MPNNs including GCN (Kipf & Welling, 2017), GAT (Veličković al., 2018), and GIN (Bouritsas et al., 2022). The expressive power of these GNNs is proven to be at most as powerful as the 1- test (Xu et al., 2019). We also compare the Graph Substructure Net- work (Bouritsas et al., 2022), which extracts graph substructures to improve the expressive power of MPNNs. The substructure counts are incorporated into node features or the aggregation procedure. Lastly, we also compare the Graphormer model (Ying et al., 2021a), which achieved impressive performance in several world competitions (Ying et al., 202 1b; Shi et al., 2022; Luo et al., 2022a).
Settings. We employ a 6-layer Graphormer-GD model. The dimension of hidden layers and feed- forward layers is set to 768. The number of Gaussian Basis kernels is set to 128. The number of attention heads is set to 64. The batch size is set to 32. We use AdamW (Kingma & Ba, 2014) the optimizer and set its hyperparameter e to 1e-8 and (31, 32) to (0.9, 0.999). The peak learning rate is set to 9c-5. The model is trained for 100k steps with 6K-step warm-up stage, After the warm-up stage, the learning rate decays linearly to O. All models are trained on NVIDIA Tesla V V100 GPU.
F.2 REAL-WORLD TASKS
We conduct experiments on the popular benchmark dataset: ZINC from Benchmarking-GiNN (Dwivedi et al., 2020). It is a real-world dataset that consists of 250K molecular graphs. The task is to predict the constrained solubility of molecule, which is an important chemical property for drug discovery. We train our models on both the ZINC-Full and ZINC-Subset (12K selected graphs following Dwivedi et al. (2020)).
Baselines. For a fair comparison, we set the parameter budget of the model to be around 500K fol- lowing Dwivedi et al. (2020). We compare Graphormer-Gh with several competitive baselines, which mainly fall into five categories: Message Passing Neural Networks (MPNNs), High-order GNNs, Suustructuue-baaseeee GNNs, Subgraph GNNs, and Graph Transformers.
First, we compare several classic MPNNs including Graph Convolution Network (GCN) (Kipf & Welling, 2017), Graph Isomorphism Network (GIN) (Xu et al., 2019), Graph Attention Network (GAT) (Veličković et al., 2018), GraphSAGE (Hamilton et al., 2017) and MPNN(sum) (Gilmer al., 2017). Besides, also include several popularly used models. Mixture Model Network (MoNet) (Monti et al., 2017) introduces general architecture to learn on graphs and manifolds us- ing the Bayesian Gaussian Mixture Model. Gated Graph ConvNet (GatedGCNN considers residual connections, batch normalization, and edge gates to design an anisotropic variant of GCN. We com- pare the GatedGCN with positional encodings. Principal Neighborhood Aggregation (PNA) (Corso et al., 2020) combines multiple aggregators with degree-scalers.
Second, we compare two higher-order Graph Neural Networks: RingGNN (Chen et al., 2019) and 3WI.GNN (Maron et al., 2019a) following Dwivedi et al. (2020). RingGNN extends the family of order-2 Graph G-invariant Networks without going into higher order tensors and is able to dis- tinguish between non-isomorphic regular graphs where order-2 G-invariant networks provably fail. 3WLGNN uses rank-2 tensors to build the neural network and is proved to be equivalent to the 3-WL test on graph isomorphism problems.
Third, we compare two representative types of substructure-bart GNNs. The Graph Substructure Network (Bouritsas al., 2022) extracts graph substructures to improve the expressive power of MPNNs. The substructure counts are incorporated into node features or the aggregation procedure. We also compare the Cellular Isomorphism Network (Bodnar et al., 2021a), which extends theo-
57

---

Published as a conference paper at ICLR 2023
retical results on Simplicial Complexes regular Cell Complexes. Such generalization provides powerful set of graph "lifting" transformations with a hierarchical message passing procedure.
Moreover, we compare several Subgraph GNNs. Nested Graph Neural Network (NGNN) (Zhang & Li, 2021) represents a graph with rooted subgraphs instead of rooted subtrees. It extracts a local subgraph around each node and applies base GNN to each subgraph to learn subgraph represen- tation. The whole-graph representation is then obtained by pooling these subgraph representations. GNN-AK (Zhao et al., 2022) follows a similar manner develop Subgraph GNNs with different generation policies. Equivariant Subgraph Aggregation Networks (ESAN) (Bevilacqua et al.. 2022) develops unified framework that includes per-layer aggregation across subgraphs, which are gen- erated using pre-defined policies like edge deletion and ggo-networks. Subgraph Union Network (SUN) (Frasca et al., 2022) is developed based on the symmetry analysis of a series of existing Subgraph GNNs and an upper bound on their expressive power, which theoretically unifies previous architectures and performs well across several graph representation learning benchmarks.
Last, we compare several Graph Transformer models. Tranfoorrrrr (GT) (Dwivedi & Bres- son, 2021) uses the Transformer model on graph tasks, which only aggregates the information from neighbor nodes to ensure graph sparsity, and proposes to use Laplacian eigenvector as positional encoding. Spectral Attention Network (SAN) (Kreuzer et al., 2021) uses a learned positional en- coding (LPE) that can take advantage of the full Laplacian spectrum to learn the position of each node in a given graph. Graphormer (Ying et al., 2021a) develops the centrality encoding, spatial encoding, and edge encoding to incorporate the graph structure information into the Transformer model. Universal RPE (URPE) (Luo et al., 2022b) first shows that there exist continuous sequence- to-sequence functions which RPE-based Transformers cannot approximate, and develops novel and universal attention module called Universal RPE-based Attention. The effectiveness of URPE has been verified across language and graph benchmarks (e.g.. the ZINC dataset).
Settings. Our Graphormer-GD consists of 12 layers. The dimension of hidden layers and feed- forward layers are set to 80. The number of Gaussian Basis kernels set 128. The number of attention heads is set to 8. The batch size is selected from [128, 256, 512]. We use Adam W (Kingma & Ba, 2014) as the optimizer, and set its hyperparameter c to 1e-8 and (81, (22 to (0.9, 0.999). The peak learning rate is selected from [4e-4, 5e-4). The model is trained for 600k and 800k steps with a 60K-step warm-up stage for ZINC-Subset and ZINC-Full respectively. After the warm-up stage, the learning rate decays linearly to zero. The dropout ratio is selected from [0.0, 0.1]. The weight decay is selected from [0.0, 0.01]. All models are trained on NVIDIA Tesla V100 GPUs.
F.3 MORE TASKS
Node-level Tasks. We further conduct experiments on real-world node-level tasks. Following Li et al. (2020), we benchmark our model on two real-world graphs: Brazil-Airports and Europe- Airports, both of which are air traffic networks and are collected by Ackland et al. (2005) from the government websites. The nodes in each graph represent airports and each edge represents that there are commercial flights between the connected nodes. The Brazil-Airpore graph has 131 nodes, 1038 edges in total and its diameter is 5. The Furope-Airports graph has 399 nodes, 5995 edges in total and its diameter is 5. The airport nodes are divided into 4 different levels according to the annual passenger flow distribution by 3 quantiles: 25% 50,, and 75%. The task is predict the level of each airport node. We follow Li et al. (2020) to split the nodes of each graph into train/validation/test subsets with the ratio being 0.8/0. 1/0. respectively. The test accuracy of the best checkpoint on the validation set is reported. We use different seeds to repeat the experiments 20 times and report the average accuracy.
Following Li et al. (2020), we choose several competitive baselines including classical MPNNs (GCN, GraphSAGE, GIN), Struc2vec and Distance-encoding based GNNs (DE-GNN-SPD, DE- GNN-LP, DEA-GNN-SPD). We refer interested readers to Li et al. (2020) for detailed descriptions of baselines. For our Graphormer-GD, the dimension of hidden layers and feed-forward layers are set to 80. The number of layers is selected from [3, 6]. The number of Gaussian Basis kernels is set to 128. The number of attention heads is set to 8. The batch size is selected from [4, 8, 16, 32]. We use AdamW (Kingma& & Ba, 2014) as the optimizer, and set its hyperparameter to 1e-8 and (3,, 33) to (0.9. 0.999). The peak learning rate is selected from [2e-4, 7c-5, 4c-5). The total number of training steps is selected from [500, 1000, 2000]. The ratio of the warm-up stage is set 10%.
58

---

Published as a conference paper at ICLR 2023
After the warm-up stage, the learning rate decays linearly to zero. The dropout ratio is selected from [0.0, 0.1, 0.5]. All models are trained on NVIDIA Tesla V100 GPUs.
The results presented in Table 5. We can that model outperforms these basclines on both datasets with a slightly larger variance value due to the small scale of the datasets.
Table 5: Average Accuracy on Brazil-Airports and Europe-Airports datasets. Experiments are re- peated for 20 times with different seeds. We use * to indicate the best performance.
Model
Brazil-Aine Airrootss
Europe- Airports
GCN (Kipf Welling, 2017)
64.55-14.18
54.83+2.69
GraphSAGE (Hamilton et al., 2017)
70.65++5.33
56.29-
GIN (Xu et al., 2019)
71.89=3.60
57.05=4.008
Strue2vec (Ribeiro et al., 2017)
70.881:.226
57.94=4.01
DE-GNN-SPP (Li al., 2020)
73.28:12.47
56.98-2.79
DE-GNN-LP (Li et al., 2020)
75.10:33.80
58.41+3.20
DEA-GNN-SPD (Li et al., 2020)
75.37+33.25
57.99=2.39
Graphormer-GD (ours)
77.6916.39
59.23
F.4 EFFICIENCY EVALUATION
We further conduct experiments measure the efficiency of our approach by profiling the time cost per training epoch. We compare the efficiency of Graphormer-GD with other baselines along with the number of model parameters on the ZINC-subset from Dwivedi al. (2020). The number of layers and the hidden dimension of our Graphormer-Gh GD are set to 12 and 80 respectively. The number attention heads set to 8. The batch size is set 128, which the same as the settings of all baselines. We run profiling of all models we evaluate the time costs based on the publicly available codes of Dwivedi et al. (2020) and Ying et al. (2021a). The results presented in Table 6.
16GB NVIDIA Tesla V100 GPU. For all baselines,
From Table 6, we can draw the following conclusions. Firstly, the efficiency of Graphormer-Gi is in the same order of magnitude as classic MPNNs despite the fact that the computation complexity of Graphormer-Gi GD is higher than MPNNs (i.e., O(n²) v.s. O(n + m) for a graph with n nodes and edges). This may be due to the high parallelizability of the Transformer layers. Secondly, Graphormer-GD is much more efficient than higher-order GNNs as reflected by the computation complexity in Table 1. Finally, Graphormer-GD is almost efficient the original Graphormer, since the newly introduced module to encode the Resistance Distance takes negligible additional time compared that of the whole architecture.
Table 6: Efficiency Evaluation of different GNN models. We report the time per training epoch (seconds) as well the number of model parameters.
Model
Params
Time (s)
GCN (Kipf & Welling, 2017)
505,079
5.85
GraphSAGE (Hamilton et al., 2017)
505.341
6.02
MoNet (Monti et al., 2017)
504,013
7.19
GIN (Xu et al., 2019)
509.549
8.05
GAT (Veličković et al., 2018)
531,345
8.28
GatedGCN-PE (Bresson & Laurent, 2017)
505,011
10.74
RingGNN (Chen at al., 2019)
527,283
178.03
3WL.GNN (Maron et al., 2019a)
507, 507.603
179.35
Graphormer (Ying et al., 2021a)
489,321
12.26
Graphommer (ours)
502,793
12.52
59


Reviews:
[{"review_id": "UtDyYFvu3V5", "reviewer": "Reviewer_yHMN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper discusses the graph biconnectivity and the potential of existing GNNs on recognizing it. It first proves most of the existing GNNs and 1-WL cannot distinguish biconnectivity. The author proves ESAN are powerful enough for this problem due to the subgraph aggregation policies. Furthermore, author discusses the ", "summary_of_the_review": "I think this is a great paper discussing the capacity of graph neural network on one of the fundamental problem for graph. Despite I found the structure of the paper can be improved, I still think it's an excellent paper to the community. ", "strength_and_weaknesses": "Strength:\n1. Very interesting and innovative study on biconnectivity problem.\n2. The theoretical discussion on ESAN and proposed Graphomer-GD are comprehensive and clear.\n\nWeakness:\n1. The organization of the paper is a bit hard to follow. I am not fully understand of explaining ESAN in the main paper since eventually author proposes a more efficient variant of graphomer. I suggest focus on Section 4 since section 3 and 4 seems quite parallel to me...\n2. The synthetic experiment is missing some details such as number of graphs and size of the graphs. The numbers reported in Table 1 lack of number of repetitions and variations.\n3. The efficiency of the proposed method. Can you share with us the amount of parameters of Graphormer-GD and other baselines ? What's the empirical running time on ZINC?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JAj2S82TEb", "reviewer": "Reviewer_kMJa", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposes using the computation of node- and edge-level biconnectivity properties as expressivity metrics for GNNs. It analyzes four families of GNNs and finds that they fail to decide these biconnectivity metrics, except for ESAN. The paper provides insights into the power of ESAN. Based on these insights, the paper proposes a new color refinement algorithm that leverages distance between nodes to achieve expressivity in terms of the biconnectivity metrics. Experiments on the ZINC dataset show the efficacy of the proposed method in a real-world graph-level task.\n", "summary_of_the_review": "The paper is well-written and consists of a solid contribution to the graph ML community. The results and insights from this paper should definitely be used in further developments in the field. My main concerns revolve around empirical evaluation. Therefore, I am recommending acceptance.\n", "strength_and_weaknesses": "**Strengths**\n- The paper is well-written, and the authors did a good job reviewing the related literature.\n- The introduced biconnectivity metric relates to important concepts in network science and is well-motivated.\n- The paper provides theoretical insights into existing methods and represents an excellent contribution to the graph ML community. \n- The proposed Transformer-based architecture is simple, relatively novel, and naturally derives from the paper's findings.\n\n**Weaknesses**\n- Very limited empirical evaluation setup.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EaCPXfYmBu", "reviewer": "Reviewer_FHtc", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work is proposing a metric to measure and compare the expressivity of GNNs - the capacity of solving vertex/edge biconnectivity. It carefully revisits several popular frameworks of designing powerful GNNs with comprehensive and rigorous analysis of their capacity on biconnectivity. Then, beyond the expressive but expensive previous works, it proposes a cheaper and powerful framework - GD-WL - with its Graphormer implementation. The proposed method is evaluated with synthetic experiments of biconnectivity and real-world benchmarks.", "summary_of_the_review": "I would like to recommend a strong acceptance since this work carefully presents everything necessary in this framework of biconnectivity. On one hand, it is making a significant contribution regarding theoretically understanding expressivity to the GNN community. On the other hand, instead of simply presenting counter-examples on a limited range of models like some common papers these days, it presents theoretical results of the most general frameworks with proof, which would stand a role model for future works.\n\n=== Acknowledgement ===\n\nDue to time limit, I only read the theorems in the main text but did not check the proof in the appendix.", "strength_and_weaknesses": "Pros:\n1. The motivation of proposing such a metric is natural and fundamental, since graph isomorphism testing is too abstract to guide practical design of GNNs. And I agree that biconnectivity plays a key role in justifying any meaningful high-order substructures, such as those in bio-chemistry.\n2. The theoretical of recent popular frameworks is pretty comprehensive. It includes almost all popular works with detailed discussion of counter-examples and proof.\n3. The proposed GD-WL is efficient but still powerful enough to solve biconnectivity. It Graphormer implementation enjoys splendid performance on synthetic experiments and real-world benchmarks against strong baselines.\n\nCon:\n1. Since there are so many results in the main text, it would be great to present all these results in a comprehensive table near the introduction, to make it easier for any audience to get the message precisely.\n\nTypo:\n1. In appendix B.4, bolded ``Note`` -> ``Node``\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%