Cycle to Clique (Cy2C) Graph Neural Network: A Sight to See beyond Neighborhood Aggregation
Authors: Yun Young Choi
Sun Woo Park
Youngho Woo
U Jin Choi
Venue: ICLR 2023 poster (2023)

Abstract: Graph neural networks have been successfully adapted for learning vector representations of graphs through various neighborhood aggregation schemes. Previous researches suggest, however, that they possess limitations in incorporating key non-Euclidean topological properties of graphs. This paper mathematically identifies the caliber of graph neural networks in classifying isomorphism classes of graphs with continuous node attributes up to their local topological properties. In light of these observations, we construct the Cycle to Clique graph neural network, a novel yet simple algorithm which topologically enriches the input data of conventional graph neural networks while preserving their architectural components. This method theoretically outperforms conventional graph neural networks in classifying isomorphism classes of graphs while ensuring comparable time complexity in representing random graphs. Empirical results further support that the novel algorithm produces comparable or enhanced results in classifying benchmark graph data sets compared to contemporary variants of graph neural networks.

Published as a conference paper at ICLR 2023
CYCLE TO CLIQUE (CY2C) GRAPH NEURAL NET- WORK: A SIGHT TO SEE BEYOND NEIGHBORHOOD
AGGREGATION
Yun Young Choi Sun Woo Park & Youngho Woo
U Jin Choi
Division of Industrial Mathematies National Institute for Mathematical Sciences Dacjeon, South Korea
Department of Mathematical Sciences KAIST Daejeon, South Korea
ABSTRACT
Graph neural networks have been successfully adapted for learning vector repre- sentations of graphs through various neighborhood aggregation schemes. Previous researches suggest, however, that they possess limitations incorporating key non- Euclidean topological properties of graphs. This paper mathematically identifies the caliber of graph neural networks classifying isomorphism classes of graphs with continuous node attributes up to their local topological properties. In light of these observations, we construct the Cycle to Clique graph neural network, a novel yet simple algorithm which topologically enriches the input data of conven- tional graph neural networks while preserving their architectural components. This method theoretically outperforms conventional graph neural networks in classify- ing isomorphism classes of graphs while ensuring comparable time complexity in representing random graphs. Empirical results further support that the novel algorithm produces comparable or enhanced results in classifying benchmark graph data sets compared contemporary variants of graph neural networks.
INTRODUCTION
Graph neural networks (GNN) are prominent deep learning methods for learning vector representation of graphs. Research in GNNs explores their empirical capabilities and effectiveness in classifying node labels, classifying graphs, and predicting links by modifying the message passing layers or pooling methods. These experiments support that GNNs can achieve state-of-the-art performances in executing these tasks and ensure equivalent performance to that of the Weisfeiler-Lehman (WL) isomorphism test in representing graphs with discrete node labels Xu et al. (2018). However, they have limited capabilities in incorporating global topological properties of graphs, thereby exhibiting restricted discriminative power in distinguishing isomorphism classes of graphs Bouritsas al. (2022): Rieck et al.) (2019).
To overcome these limitations, this paper presents mathematical framework that examines which topological properties of graphs with continuous node attribute that conventional GNNs can encap- sulate. Inspired by the works of Krebs and Verbitsky Krebs & Verbitsky (015) and Xu et al Xu ct al. (2018), we use the theory of covering spaces to prove that under some constraints, a pair of graphs with continuous node attributes is distinguishable by GNNs and only if there exist isomor- phisms among the collection of their finite depth unfolding trees that induce equality of induced node attributes. This gives a universal formulation which pinpoints the discriminative power of wide range of variants of GNNs and the topological enrichments these models endow over the graph data set. Such approaches include enriching node attributes, using persistent homological techniques, gluing high dimensional complexes, and keeping track of recurring subgraph structures. Among these candidates, we focus on the procedure of transforming the cycle bases of graphs to complete subgraphs cliques. This operation can be casily implemented by adding suitable edges to transform a cyclic subgraph into a clique and masking any other edges not included in the subgraph. The
"quual Contribution
Coorespondence to: youngw @ nims.re.kr

---

Published as a conference paper at ICLR 2023
adjacency matrices obtained from the induced cliques, denoted as clique adjacency matrices, allow GNNs to effectively process the bases of cycles, which are topological properties equivalent to the first homological invariants of graphs Paton (1669). In particular, the operation can be thought as straightforward pre-processing procedure independent from training dynamical filtration functions or attaching higher dimensional cells HHom et al. 2221): [Boritssas et al. (2022); [ et al. (2021b a).
which are previously carefully studied methods for encapsulating the cyclic structures of graphs.
We thus propose the Cycle-to-Clique Graph Neural Network (Cy2C-GNN), graph neural network whose message passing layers compute two types of hidden node attributes, each obtained from the adjacency matrix and the induced clique adjacency matrix of graph. We confirm that Cy2C-Gh effectively processes cycle bases of graphs, thus surpassing the strengths of conventional GNNs. Experimental results support that Cy2C-GNN ensures comparable performance to GNNs that utilize persistent homological techniques with both fixed and arbitrary filtration functions. Furthermore, the simplicity of the architecture guarantees equivalent computational complexity to conventional GNNs in representing random graphs and the effective utilization of trainable parameters.
Our main contributions can therefore summarized as follows:
1. Theoretical Foundation: We use the theory of covering spaces to prove that conventional GNNs fail to effectively represent cyclic structures of graphs with continuous node attributes.
(Theorem 3.3 Section 3)
2. A Simple yet Novel Network:
We propose a novel algorithm called "Cy2C-GNN" which overcomes the theoretical limitations by enriching the topological properties of the input data admitted by GNNs with clique adjacency matrices, which does not require training filtration functions or attaching high-dimensional complexes. (Theorem 4.3 Section 4)
3. Efficient Enhancements: The proposed algorithm effectively incorporates cyclic structures of graph data sets while ensuring equivalent computational complexity to conventional GNNs for representing random graphs and adaptability to variants of GNNs. (Section 5)
2 RELATED WORKS
Graph Neural Networks (GNNs) We recall the construction of GNNs as suggested in Xu et al Xu et al. (011 Denote by GNN the conventional GNN (GNN) comprised of composition of I neighborhood aggregating layers. Each m-thh layer (m)) of the network constructs hidden node attributes of dimension him denoted as hl(m), .using the following composition of functions:
hi = COMBINE
(1(m-1) AGGREGATE (m))
(ff (m-1)
ht
|ue N(O)
(1)
11 X
Here, X2 is the initial node attribute at v, N(u) is the set of nodes adjacent to E V(G), AGGREGATE!"") is a function which aggregates features of nodes adjacency to and COMBINE a function which combines features of the node u with those of nodes adjacent e.
Denote by H the final layer of the network. The K-dimensional vector representation of G. denoted as lGg is given by
hG == READOUT (0A I (
where (EADOUT()) is the graph readout function of node features updated from hidden layers. We refer readers to Appendix for a rigorous definition of graph neural networks.
A wide range of GNNs and graph representation techniques can be formulated in terms of the construction outlined above. For example, the WL. test is a classical technique which consists of com- bining adjacent discrete node labels, substituting newly obtained labels, and constructing complete histogram of updated labels. The test equivalent to conventional GNNs whose aggregation and combination functions correspond to sums of multisets, and the graph readout function corresponds to hashing function of discrete node labels. Other well-known networks whose architecture can be formulated using conventional GNNs from Section 2 include graph convolutional networks (GCN),
graph attention networks (GAT), and graph isomorphism networks (GIN) Kipf & Welling (0016);
Veličković et al. (201)): Xu et al. 2018).
2

---

Published as a conference paper at ICLR 2023
Covering spaces A number of studies carefully analyzed the strength of graph neural networks in distinguishing isomorphism classes of graphs with discrete node labels. The work by Krebs and Verbitsky Krebs& & Verbitsky (2013) shows that Weisfeiler-Lehman test can distinguish pair of graphs with constant node labels up to isomorphism of their universal covers, i.e. isomorphism of collections of finite depth unfolding trees. We refer to Appendix A.1. for rigorous treatment of the definition of covering spaces of graphs Hatcher (2002); Krebs & Verbitsky (2015).
Definition 2.1. Let G == (V, F) be a directed graph. For each node v E VGG), the depth-1 unfolding tree rooted at v, denoted as T. is subtree of G whose set of nodes consists of the distinguished node v itself and the nodes w such that there exists a directed edge from v to w. The set of edges of Ty are comprised of directed edges from v. (See Definition A. for a rigorous definition.)
For any positive number k, the depth-k unfolding tree rooted at v, denoted as uu is subtree of G whose set of nodes consists of the distinguished node v itself and the nodes wo such that there exists at most k consecutive directed edges from v to w. The set of edges of Thk are comprised of unions of all k consecutive directed edges from v. (For any undirected graph, the finite depth unfolding tree rooted at is defined in an analogous manner, though the set of edges consists of undirected edges instead of directed edges). The collections of all unfolding trees of G of arbitrary depth can be represented as single graph, called the universal cover of G.
Definition 2.2. Let G == (V, F)) be a connected graph. The universal cover of G is a connected tree G (possibly infinite) with the projection map ιa : G + G that maps any depth-1 1 unfolding trees in G isomorphically to some depth-1 unfolding tree in G. (See Definitions 12 for more details.)
For graphs with several connected components, their universal covers are disjoint unions of connected trees, each component of which satisfies the local isomorphism condition from Definition 2.2 We recall that Xu et al. proved that GNNs with injective aggregation, combination, and graph readout functions share equivalent strengths with Weisfeiler-Lehmar test in distinguishing non-isomorphism classes of graphs with discrete node labels Xu et al. (2018). Combined with Krebs and Verbitsky's result, obtain that such GNNs can distinguish pairs of graphs with constant node labels up to isomorphism classes of their universal covers, or finite depth unfolding trees.
Improvements Recent studies focused on excavating novel techniques which may outperform or optimize GNNs in analyzing graph data sets, such as classifying node attributes, classifying graph datasets, and predicting links among the set of nodes. Graph kernels measure similarities among graphs by utilizing inner products between their representations, a form of an embedding to reproducing kernel Hilbert space. Borgwardt et al. (2020); Kashima et al. (2003); Shervashidze itt al. (201T); Vishwanathan et al. (2110) Persistent homological techniques and topological data analytic tools have garnered attention as key sources of encapsulating global topological invariants of graphs, such as counting the number of connected components or cycles present in given graph datasets. Several studies focused on incorporating these topological tools with graph kernels by using pre-defined filtration functions Rieck et al. (2019). with GNNs by constructing task-specific filtration functions Hofer et al. (2020); Horn et al, (222I). Keeping track of topological substructures of graphs is also shown to be effective in enriching the quality of vector representations obtained from GNNs Rieck et al. (2017): Sizemore et al.] (217). Other approaches focus on proposing novel message passing schemes measures to address the limited performance of conventional GNNs Bodnar et af. (20215); Bouritsas et al. (2022).
3 GNNS AND UNIVERSAL COVERS
In this section, we utilize the theory of covering spaces to assess the quality of representations conventional GNNs construct from collections of graphs with continuous node attributes.
Definition 3.1. Let G
= (V. has self-loop. Denote by G" := EV. the directed graph with a projection map p : G" - G' such that each undirected edge of G' from i1 to D2 is constructed as follows: If 01 * U2, the undirected edge corresponds to two directed edges, one edge from en to 22, and the other from 12 to V1: Otherwise, the edge corresponds to single directed self-loop from e1 to itself.
E) be graph. Denote by G' = (V, E') the graph where every node
Figure Iillstrates the construction of G' and G Recall that the graph G is endowed with continuous attributes fc V(G) + R Respecting the configuration of these attributes, we can endow new
3

---

Published as a conference paper at ICLR 2023
node attributes G" and the universal cover G". We call these new assignments of node attributes to the universal cover G" the pullback of node attributes.
Definition 3.2. Let Sa V(G) - R* be the function of node attributes over the graph G. The pullback of the node attributes to the associated universal cover G" is the composition of functions Jc" TT" V(C")= + R*, where Ja" V(G") + R& is the node attributes on G" obtained from using the identical node attributes on G. (See Definitions A.10 for a rigorous formulation.)
Inspired from the effectiveness of Weisfeiler-Lehman isomorphism tests Krebs & Verbitsky 2015) and GNNs Xu et al. (2018), we prove that GNNs with injective message passing layers represent a pair of graphs with continuous node attributes as distinct vectors if and only if there exists an isomorphism between their associated universal covers whose node attributes endowed in manner that respects the node attributes of the original graphs are identical, i.e. there exist isomorphisms among the collection of their finite depth unfolding trees that induce equality of the pullback of node attributes. We refer the proof of the theorem to Appendices A.3. and A.4.
Theorem 3.3. Let G be a collection of finite undirected connected graphs with continuous node attributes. Let G. H E G be any two connected graphs with the same number of nodes. Denote by fc : V(G) + R and fH (HH - R an arbitrary choice of continuous node attributes. Let da,d) du be the diameters of graphs G and H, i.e. the maximum of the shortest length of paths between any two nodes (see Appendix A.4 for the rigorous definition.)
Suppose graph neural network GNN with I layers satisfies the following three constraints:
(I) For every m such that 1 S m and for each v V(G), the functions AGGREGATE, and COMBINE are injective: (2) The graph read-out function READOUT is injective: And (3) l Z 2 max(da, d Then GNN maps the pair of graphs G. E 9 to identical vector representations if and only if there exists isomorphism of universal covers yp G H" whose node attributes respecting the node attributes over G and are identical, i.e.
hG = hn = 3 isomorphism yp 6 - H s.l. Sa "G" s'n" TH" o p
(3)
Remark 3.4. The above theorem outlines the maximal extent of GNNs in detecting non-isomorphism classes of graphs, a generalization of results proved in Krebs & Verbitsky (2015). Xu et al. (2018). and contemporary result from Bamberger (2022). It also pinpoints that conventional GNNs whose number of layers are at least twice the maximum diameter of a graph data set are sufficient to fully distinguish isomorphism classes of graphs up their universal covers, which to the best of our knowledge enhances the results from previous researches that focused on analyzing the performance of GNNs with sufficiently large numbers of layers. Meanwhile, universal covers of graphs are infinite trees that do not contain any cycles, see Chapter 1.3 Hatcher (2002) for example. Thus, conventional GNNs, regardless of the injectivities of the three functions, have limited capability in incorporating homological invariants of graphs, such as cyclic subgraph structures of a finite graph.
4 CYCLE-TO-CLICE GRAPH NEURAL NETWORKS (CY2C-GNN)
Motivation As shown in Theorem 3.3 GNNs can distinguish a collection of finite graphs up to isomorphism classes of their universal covers and equivalences of pullbacks of node attributes, but may fail to distinguish a collection of graphs with isomorphic universal covers whose subgraphs are comprised of cyclic graphs with different number of nodes, see Figure T for instance. We note that Theorem 3.3 proves a rigorous mathematical equivalence relation between the conditions conventional
GNNs satisfy and the nature of isomorphism classes of graphs conventional GNNs can distinguish.
Thus, any novel GNN model which twists one of the conditions from Theorem 3.3 can be considered as a candidate model for outperforming conventional GNNs.
Using Theorem 3.3 we deduce four possible approaches which may enrich the input data structure of graphs the GNN may process to distinguish non-isomorphic classes of graphs. (1) Assignment of unique node attributes: One can assign new attributes to each node. Practical implementations include assigning node degrees as labels, imposing positional encoding, implementing labeling tricks, inductive identity coloring, and random assignment of node features. Dwivedi et al. (2022); Geerts jet al.] (202T): You et al.] (2019); Zhang et al.) (202T); You et al. (202 Abboud et al. (2021). (2) Persistent homological methods: We may incorporate homological invariants of graphs to GNNs
4

---

universal covers of cyclic graphs Cm,," " and Cmg " are isomorphic, whereas the universal covers of Published as a conference paper at ICLR 2023
CyC-ORN
Coneestonal
(4.21
UnberallCoes
Univrnal
= (V,E)
G² (VE)))
6"-IV.E")
Figure 1: (Upper Left) An exemplary graph G with the induced graphs G' and G" (Lower Left) An illustration of pullback of node attributes (Definition 3.2 defined over the base graph G" to its universal cover G The corresponding node attributes and edges over the two graphs are marked in identical colors. (Right) An illustration of Theorem [3.3 and Theorem 4.3 The two graphs G and H have identical associated universal covers G" and H" and equality of pullback of node attributes.
by utilizing or constructing height functions over nodes and edges and constructing the associated persistence diagrams Carrière al. (2020); Hofer et al. (2020); Horn et al. (2021); Rieck et al. (2019). These diagrams allow one to keep track of variations in the number of components and cycles throughout the filtration of graph dataset induced from the choice of the height functions. (3) Topological Enrichments: One can also enrich topological structures of graphs by attaching simplicial and cellular complexes,
incorporating subgraph structures [Bdnnar al. (2021bla) a): Bouritsas et al. (2022). This allows GNNs to capture topological substructures of graphs, such as cliques or cyclic subgraphs. (4) Non-isomorphic universal covers: We may construct a collection of new graphs with non-isomorphic universal covers induced from cyclic subgraphs. We can thus allow conventional GNNs represent collection of cyclic subgraphs as distinct vectors without significantly altering their architectural designs.
The last approach hints a natural procedure orthogonal to the first three previously studied approaches: Substitute cyclic graphs with complete graphs of the same number of nodes. This can be rigorously formulated as in the following lemma, whose proof Lemma A.30
Lemma 4.1. Denote by Cn the eyclic undirected graph without self-loops consisting of n nodes, and Kn, the undirected complete graph with n nodes without self-loops. Then for any ma + m2, the
complete graphs Km," and Km, are not.
We thus devise GNN which admits both the adjacency matrix of graph G' and the adjacency matrix of unions of cliques induced from substituting cyclic subgraphs with complete subgraphs.
Definition 4.2 (Clique Adjacency Matrix). Let G == (V. E) be an undirected graph. Fix the cycle basis BG of G. the set of cyclic subgraphs G which forms the basis of the cycle space (or the first homology group) of G. The clique adjacency matrix of G, denoted Ac, is the adjacency matrix of the union of #Bc complete subgraphs, each obtained from adding all possible edges among the set of nodes of each basis element B BG. Note that such B is cyclic subgraph of G. Explicitly, the matrix Ac := (u.eVv) is given by
3 E BG cyclic s.t. u, E V(B)
(4)
otherwise
Given 3 < S oc, may also define the bounded clique adjacency matrix Aclicnoal le which only substitutes cycles size between e₁ and 02 to cliques:
G == {
if 3 B Ba cyclic s.t. u, v E V(B), ei S [V(B] <
(5)
otherwise
5

---

Published as a conference paper at ICLR 2023
For each node E V(G), we denote by C(v) the set of nodes E V(G) such that there exists cyclic subgraph C' E Bg such that both v and w lie in C:
C(v) : E (V)) B Bg s.t. U, W. E
(6)
Required for computing the set C(v) for each node E V(G), is the basis of cycles of the graph G. Here, the cycle basis, denoted as Be, refers to the minimal set of cyclic subgraphs of G whose combinations generate all possible cyclic subgraphs. To construct the basis, we use the algorithm proposed by Paton, whose time complexity for computing the basis for graph with nodes and m edges is of order O(n²) for 7
y S 3, and that for a random graph with n nodes is of order O(n²) Paton 1969). Given predetermined ordering on E(G), we can use persistent homological techniques to further reduce the time complexity required for obtaining BG to O (mmor(m)). where a(m) is the inverse Ackermann function which be regarded
constant for any practical values of m Hoon et al. (202T). In other words, the best time complexity required for preprocessing the given graph data set of order practically equivalent (m) where m the number of edges of G.
Cycle-to-Clique Graph Neural Network Using the clique adjacency matrices, we now propose the Cycle-to-Clique Graph Neural Network (Cy2C-GNN), a novel and simple modification of GNNs ensuring low computational complexity and efficient usage of trainable weights. The topological features of graph G (V. E) with continuous node attributes fc V(G) - I can be represented by three types of matrices: The adjacency matrix A E Raxn, The node feature matrix X E R obtained from the function fG: And the clique adjacency matrix Ac E TRax (possibly bounded) from Definition 4.2 The Cy2C-GNN admits the three types of matrices Ac, X) inputs, whereas conventional GNNs only utilize two types of matrices XX.
The Cy2C-GNN consists of two sets of neighborhood aggregating layers: A single layer utilizing the clique adjacency matrix Ac: And I neighborhood aggregating layers identical to conventional GNN layers, as defined in Section 2] which utilize the usual adjacency matrix A. The model thus preserves various executive merits of GNNs, such as incorporation of edge attributes and efficient applicability to large graph datasets. The trainable weights are not shared among the hidden layers.
The first layer of Cy2C-GNN is a single neighborhood aggregating layer utilizing the clique adjacency matrix Ac E R The output of the first hidden layer is the hidden attribute cb obtained from the usual aggregation and combination functions used to obtain hidden vectors of conventional GNNs:
COMBINE AGGREGATEE ( (H u C(v)))
Recall that C(v) is a set of nodes which are adjacent to in the clique adjacency matrix. Here, the functions AGGREGATE (.) and COMBINE() are functions as defined in Section 2
To entwine the local topological properties with cyclic structures of a graph, we implement a conventional GNN comprised of neighborhood aggregating layers, disjoint from the single layer utilizing clique adjacency matrices. Each m-th layer outputs the hidden attribute (!")) which is inductively defined as follows.
(m) COMBINE (m)) (n( (m-1) AGGREGATE!!" (mM) hr (m-1)) | ((O)))
(8)
11 = X, for 1 S m ml
The hidden node attributes obtained from pairs of layers o and h are concatenated, followed by multi-layer perceptronos (MLPs) to obtain the final hidden node attribute H,:
H. MLP(CONCAT(()) (c(), A)))).
(9)
As for obtaining the vector representation of a graph G, the Cy2C-GNN separately aggregates the hidden attributes (1) and !!))) for each node v. followed by a composition with MLPs.
Hho.ec MLP(COONCAT (Heo Hea))
Hhg = READOUT (VEV())))
(10)
H cgg (HADOUT"((cC) ([CC))V)))))

---

Published as a conference paper at ICLR 2023
Discriminative Power of Cy2C-GNN Cy2C-GNN can distinguish collection of unions of cyclic graphs, each comprised of possibly different number of nodes, the non -oommooooppic classes of graphs of which GNNs may not distinguish. We refer to Theorem 43 and Figure T for some pairs of graphs with node attributes that Cy2C-GNN can distinguish, whereas conventional GNNs cannot.
Theorem 4.3, Let G and H be graphs which have isomorphic universal covers, endowed with node features fG : V(G) - B and fH ((G) - Rt. Fix cycle basis BG of G. Suppose that there exists a chordless cyclic subgraph C E BG such that any cycle basis Bu does not have any chordless eyclic subgraph of size equal to [V(C).. Then Cy2C-GNN which utilizes bounded clique adjacency matrices can distinguish G and H, whereas conventional GNNs cannot.
Here, a subgraph H C G is chordless if no other cyclic subgraphs C' E satisfy V(C) & (HH). Hence, Cy2C-GNN can distinguish classes of graphs that 1,2, and 3-dimensional WL tests cannot distinguish, in particular certain classes of strongly regular graphs. (See for example Remark A.37 for further details). Theorem 3.3 and Lemma 4.1 further suggest that the first layer of CyNC-GNN utilizing clique adjacency matrix is enough to distinguish such pairs of graphs, a marked improvement from other contemporary GNNs which assume have sufficiently large numbers of hidden layers. We leave the proof of Theorem 4.3 to Theorem (h.35 as well as comparison in discriminative power of Cy2C-GNN other contemporary state-of-the-ar GNNs to Example A.36 and Remark Remark|A.37
Computational Complexity Because the Cy2C-GNN algorithm preserves the conventional neighborhood aggregating layers of GNNs, the time complexity of representing a connected graph G with n nodes and m edges using the Cy2C-GNN algorithm with [+ 1 layers is equal to O + Im). where mc the number of edges of the graph associated the clique adjacency matrix A of G. By the Fuler characteristic formula, the number of elements in the cycle bases BG of a connected graph G is equal to m n + 1. Hence, for connected graphs with bounded number of nodes constituting the subgraphs of their cycle bases, Cy2C-GNN is comparable to time complexity of conventional GNNs, and more efficient than spectral decomposition of adjacency matrices of finite graphs and constructing persistence diagrams using trainable or dynamic filtration functions Milosavljevic et al. (2011): Rieck et al. (2019). In addition, the time complexity for preprocessing the graph G to obtain clique adjacency matrices is practically equivalent O(m), without requiring any training of filtration functions for each graph G. We refer to Appendix A.6 for a detailed discussion on the computational complexity of these algorithms.
EXPERIMENTS
To analyze the effectiveness of Cy2C-GNN in distinguishing graphs with varying cyclic subgraphs, we perform an ablation study by utilizing the "CYCLES" and "NECKLACES" synthetic datasets constructed from Horn et al. (202T). These datasets are comprised of graphs containing cyclic subgraphs, which are designed to assess whether the given GNN can identify differences among such cyclic substructures. As for evaluating the effectiveness of the proposed models in classifying graph datasets, we use the 3 bioinformaticx(DD. PROTEINS(FULL), ENZYMES), social network datasets (COLLAB, IMDB-B, REDDIT-B ), and small molecular datasets (MUTAG, NCI1, NC1109). To further verify the extendability of Cy2C-GNN models to graph datasets with additional attributes, we utilized 3 datasets with edge features (BZR-MD, COX2-MD, PTC-MR) as well. Lastly, we tested Cy2C-GNN models on 4 large datasets (REDDIT-M-5K, MOLHIV, MOLTOX21, MOLTOXCAST) from TU datasets Morris et al. 2020) and Open Graph Benchmark datasets Hu al. (202T) to test their efficiency in processing large graph data sets in comparison to GNNs based on persistent homological techniques. The details of all the aforementioned datasets, obtained from the eetorch-geometee library, are summarized in Appendix B.
Dataset
To assess whether improvements in the discriminative power of Cy2C-GNN lead to enhancements in classifying benchmark graph datasets, we additionally implemented three baseline models comprised of Graph Convolutional (GCN),,(GCN)) Graph Attention Networks(GAT) and Graph Isomorphism (eIN... All baseline models share the same structure with Cy2C-GNNs except for additional structures required for implementing clique adjacency matrices. We also compare the best classification results obtained from Cy2C-GNN with baseline GNNs, those of the kernel methods(WL (Borgwardt et al. 2020, Table 4.5), WL-OA (Borgwardt al. 2020 Table 4.5), RetGK (Ye et al., 2020) Table 3), HGK (Togninalli et al. 2019 Table 2), GH (Toginall) et al. 2019 Table 2)), kernel method with persistent (PW..) (Rieck et al. 2019 Table
Models
7

---

Published as a conference paper at ICLR 2023
1.
Parto mranoc Zoolutrro Number Leyers Qycl detare
Neformares Endiateto Namber Layar- Nediaacs detase
04
04
1301
042-22
04-
00000
Haster Lavins
Figure 2: Comparisons of classification results obtained from baseline models and Cy2C-GNN from synthetic CYCLE (left) and NECKLACE (right) datasets Horn et al. (202T). All other four baseline models are obtained from (Hom et al. 2021 Figure 1).
1), GNN GodeesGGa (Dwivedi et al. 2020, (, GMT (Baek et al., 2021
Table 1). DGCNN (Wijesinghe & Wang 2022, Table 14). PNA (Corso et al. 2020 Figure 6).
ID-GNN (You et al., [021 Table 3), GraphSNN (Wijesinghe & Wang. 2022 Table 3,4,14)) and
GNN models with persistent homology(PersLLay (Carrière et al.) 2020, Table 2), TOGL (Horn et al.
2021 Table 2,3)), which aligned to the experimental protocols tested for Cy2C-GNNs. For OGB datasets(MOLHIV, MOLTOX21, MOLTOXCAST), we also consider GNNs with virtual node(VN) methods Hu et al. 20221) We omitted classification results obtained from other contemporary GNNs whose experimental procedures are different from those suggested in this paper to avoid biased comparisons of proposed GNNs, as carefully suggested in EErrica et al. (2020). Further elaborations on the aforementioned models are outlined in Appendix B.I.
Cy2C-GNN Setup In accordance with the experimental setup proposed by Dwivedì et al. Dwivedi et al. 2020) and Horn et al. Horr et al. (202T), we imposed that the architectural components of the baseline GCN, GAT, and GIN models, such as the number of layers, hidden attribute dimensions, and the classes of aggregation and combination functions, be identical to those of Cy2C-GNN. Differences in the number of trainable parameters among these models mostly occur at the final layer, where Cy2C-GNN harbors additional MLPs utilized for representing graphs as real vectors. For additional test on dataset with edge features and large dataset, we only consider Cy2C-GCN, We performed additional hyperparameter optimizations for implementing Cy2C-GNNs. Further details on the differences among the implemented networks are explicated in Appendix B.
Ablation Studies Figure 2 illlssrates the classification results obtained from baseline models and Cy2C-GCN from synthetic CYCLE (a) and NECKLACE (b) datasets Horn et al.) (202T). We denote by "GCN" graph convolutional networks, "TOGL" topological graph neural networks which model dynamic persistent homological techniques, "PH" static persistent homological techniques, and "WL" the 1-dimensional WL test, all results of which were obtained from (Horn al., [021 Figure 1). The Cy2C-GCN model detects cyclic structures of graphs as effectively as persistent homological techniques, which utilize dynamic choices of graph features. We note that Cy2C-GCN can effectively distinguish cyclic graphs with number of nodes at least 4, because Lemma 4. implies that cyclic graphs and complete graphs of sizes are isomorphic. Placing a single neighborhood aggregating layer utilizing clique adjacency matrices ahead of other conventional layers proves to be effective in detecting desired cyclic structures, as implied from Lemma 4.1
Results Comparisons among the proposed Cy2C-GNN and contemporary graph representation
techniques on benchmark dataset are listed in Table [ The Cy2C-GNN produces outperforming classification results than baseline GNNs on all of the benchmark datasets. With the exception of NCI dataset, we confirm that the Cy2C-GNNs exhibit better or similar performance to variants of WI. tests and conventional GNNs among bioinformatics, social network, and small molecules datasets. Furthermore, we compare Cy2C-GNN model on dataset with edge features and large dataset to verify the robustness of Cy2C-GNN models in representing graph data sets with additional features. Cy2C- GNN shows equivalent or outperforming performance to other GNNs and persistent homological techniques in classifying most graph datasets except PTC-MR and MOLHIV datasets. These results demonstrate that Cy2C-GNN has the potential to efficiently incorporate cyclic structures of large graph datasets to message passing layers, even for datasets with edge features. We also verify that
8

---

Published as a conference paper at ICLR 2023
Table 1: Classification results obtained from bioinformatics, social network and small molecules dataset. Note that N/A indicate graph classification methods which do not report classification results on the given graph data set. Classification methods with grey color text are cited from available results obtained from pre-existing publications.
Broskomaiks PROTEINS/ULLI
Social catoockk IMDB-B
Small melccalo
ENZYMES
COLLAB
REDONT
MUTAG
NCH
WL
(K32213
712200
35551156
WI-DA
7281112
735.09
589.109
9018:022
340-60
87810.3
86 161011995
12
NIA
NOA
GMI
TN 74:40059
15.0420.59
NA
73 73
NM
NA
NOA
DOCNN
16 168143
72.9335
289257
112219
612210
4 22212
764217
NGA
GRanSNN
77.1:33
77.0-31
723-33
818528
TOGI
253344
760-19
530/92
NIA
NA
94-14
NA
758-18
NOA
(ICEN-1)
(DEN-)
(CEN--)
(GEN-)
(GEN4)
(CEN-)
(0EN-5)
(GEN-4)
Beselie GAT
TV 101:3.49
36
68 36.354373
13.50-499
92 12.581100 14
75
77.0722.42
(GAT)
(5
(GAT3)
(GAT4:
(GAF22)
(GAT4)
(GAT.))
(GAT-4
(GAT.S)
Becinee
99139.388
50
58.1236977
$1.751000
538012722
N.31:112
(C20--0CN3)
(CYC-GEN-1)
(CYC-GEN-)
(CyD-OON-5)
(EDC-GIN-7 GIN-7
(C)IC-GEN-3)
KYOC-GIN-D
Table 2: Classification results obtained from datasets with edge features and large datasets. Note that N/A indicate graph classification methods which do not report classification results on the given graph data set. Classification methods with grey color text are cited from available results obtained from pre-existing publications.
datisets with cdgs faineres
Targo dinands MOLIII
BZR MD
COX2 MD
PTC
REDDIT 5K
MOLTOX21
MOLTOXCAST
WWT
04.66:0.84
76.33:1022
6631-1.21
GIN
161117
18.5
7491=055
63.122074
RETGK 12
62.77.1.09
59.4711.66
62.5116
GIN+VN
N/A
75.21133
76,21-0.82
66.18110.88
BGK WL
68.911063
71.611174
NA
PNA
N/A
79.05
NA
N/A
HGK-SP
66.17:11005
7183+1611
N/A
IDGNN
M/
78.30-2.0
N/A
N/A
GH
69. 14::200
66 66221106
N/A
DGONN
49:21:22
N/A
N/A
N/A
GnpbSNN
NIA
N/A
61 61.63-288
GrsphSNN
57,14311
79.72-188
188
76 76.78-1.27
67.68-0.0
CyCOOCN
Cy2C-GNN
(Bex)
(C)20-0ON-5)
(C22C-0N-3)
(Cy2C-00N-5)
(CY2C-0CN-5)
(Cy2C-0CN-5)
(Cy2C-GCN-7)
(Cy1C-GON-3)
Cy2C-GNNs are sufficient enough to incorporate topological structures while managing to reduce computational costs compared to dynamic persistent homological techniques, which require users to find suitable filtration functions for each given graph dataset.
CONCLUSION
In this paper, we utilized the theory of covering spaces to formulate a mathematical framework entailing the strengths of conventional GNNs in detecting isomorphism classes of graphs with continuous node attributes. These mathematical observations lead us to propose Cy2C-GNN, which enriches the topological characteristic of input data by utilizing clique adjacency matrices. We demonstrated both theoretically and experimentally that the proposed network can efficiently and reliably represent cyclic (or homological) structures of graph data sets without undergoing major alterations in the architectural structure of conventional message passing layers, such as training dynamic filtration functions or gluing high-dimensional cells or complexes.
Nevertheless, Cy2C-GNN is not a panacea for resolving the problem of distinguishing all non- isomorphic classes of graphs. For instance, Cy2C-GNN does not guarantee to distinguish collections of graphs whose number of nodes of all cyclic subgraphs are equal to each other. Precautionary measures are also required in stacking large number of neighborhood aggregating layers utilizing clique adjacency matrices, as it may increase the risk of oversmoothing the node features from significantly decreasing the graph diameters. These risks must be taken into account when applying Cy2C-GNN layers for classifying node labels or performing graph regression tasks. We hence advise to use single layer of Cy2C-GNN preceding conventional GNNs, which is enough to discern graphs with markedly different cyclic subgraph structures. Future research may focus identifying the extent of how much homological structures Cy2C-GNN can incorporate, identifying It would be of great interest to analyze the inherent relations among Cy2C-GNN and other variants of GNNs, and experiment whether combining Cy2C-GNNs with other state-of ofte--of-the-rr techniques may further enhance their performances.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENT
This research was supported by the National Institute for Mathematical Sciences (NIMS) grant funded by the Korean Government (MSIT)(NO.B239100000)
REFERENCES
R. Abboud, I. Ceylan, M. Grohe, and T. Lukasiewicz. The surprising power of graph neural networks with random node initialization. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. pp. 2112-2118, 2118, 2021.
Josh Alman and Virginia Vassilevska Williams. refined laser method and faster matrix multiplica- tion. In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), pp. 522-539, 2021.
Jinheon Back, Minki Kang, and Sung Ju Hwang, Accurate learning of graph representations with graph multiset pooling. In International Conference on Learning Representations, 2021. URL
httpss://ppenrevier net. http://ww..ee/oooooooooooooooaaa
Jacob Bamberger. A topological characterization of weisfeiler-leman equivalence classes.
2022. / http:///ss...to..oo.....oo/o///a EV81IwlB/vien
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Liò, Guido F Mont- ufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J, Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp. 2625-2640. Curran Asso- ciates, Inc., 2021a. URL https: /ttp:///ccoccccccs////ccsscc nww.iie.rsppp.... wwtpuurisscccapeeeee /ctpsccc/ca/a/22///1111/ 157792e4abb4 4000044900000 1100099daae 99bbd7 1ttp000177533331dd-------eee--
pdf
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.
Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-Lppzz. Leslie O' O'Bray, and Bastian Rieck. Graph Kernels: State-of-the-Art and Future Challenges. Now Foundations and Trends, 2020.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P 7afeirio, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2022.
Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signatures. In International Conference Artificial Intelligence and Statistics, pp. 2786-279299 PMLR, 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Lin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 13260-13271. Curran Associates, Inc., 2020. Pape: papp://220//E1ee99aaa2222 htt.aaaaaaaaaaaeeeeee22000000000
neur.eeurie ips. cc/
Vijay Prakash Dwivedi, Chaitanya Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982. 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In 10th International Conference on Learning Representations, ICLR 2022, 2022. URL httpps://operre///
net. net. Forum 2iapmiid==wTTi d=wITT hww.:TTnnwGGhh..
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In International Conference on Learning Representations, 2020. htt.hhtttss:/opereer////
10

---

Published as a conference paper at ICLR 2023
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint 1903:0:9,,302228,, 2019.
Floris Geerts, Filip Mazowiecki, and Guillermo Perez. Let's agree to degree: Comparing graph
convolutional networks in the message message-passing framework. In Proceedings of the 38th International
Conference Machine Learning. volume 139, pp. 1640-3649. PMLR, 2021. URLhttps
//proceedinge ngg. ml press v139/ gwe.tsereeee.. html
Aric Hagberg, Pieter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab,(LANI.) Los Alamos, NM (United States), 2008.
Allen Hatcher. Algebraic Topology- Cambridge University Press, 2002.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Christoph Hofer, Florian Graf, Bastian Rieck, Marc Niethammer, and Roland Kwitt. Graph filtration learning. International Conference on Machine Learning, pp. 4314-4323, PMLR, 2020.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. arXiv preprint arXiv:2102.07833, 2021.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 18-22133, 2020.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. OGB- LSC: A large-scale challenge for machine learning on graphs. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. URL
https://cpenrew//
net. forum /tt.:/ooooooogooooCo..
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML '03 pp. 321-328. AAAI Press, 2003.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1rXiv:1412.6900 2014.
Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609::6600002000 2016.
Andreas Krebs and Oleg Verbitsky. Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth. In 2015 30th Annual ACM/IEEE Symposium Logic in Computer Science, number 15345831, 2015.
Nikola Milosavljevič, Dmitriy Morozov, and Primoz Skraba. Zigzag persistent homology in matrix multiplication time. SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry, pp. 215..22.22 SoCG, 2011.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663, 2020.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. International Conference on Machine Learning, pp. 4663-4673, PMLR, 2019.
11

---

Published as a conference paper at ICLR 2023
Keith Paton. An algorithm for finding fundamental set of cycles of graph. Communications of the ACM, 12(9):514-518, 1969.
Bastian Rieck, Ulderico Fugacci, Jonas Lukasezyk, and Heike Leitte. Clique community persistence: A topological visual analysis approach for complex networks. IEEE transactions on visualization and computer gruphics, 24(1):822-831, 2017.
Bastian Rieck, Christian Bock, and Karsten Borgwardt. A persistent weisfeiler-lehman procedure for graph classification. In International Conference on Machine Learning, pp. 5448-5458, PMLR, 2019.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12:2539- 2561,2011.
Ann Sizemore, Chad Giusti, and Danielle S Bassett. Classification of weighted networks through mesoscale homological features. Journal of Complex Networks, 5(2):245-2733 2017.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-lemman graph kernels. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, Buc, Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL htt httttppss//prrccediinnn/ neur Seprrpps ps. CC/ Papeeeddddaapppp.ppp
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10900 2017.
Vishwanathan, N. N. Schraudolph, R. Kondor, and K. M. Borgwardt. Graph kernels. Journal of Machine Learning Research, 11:1201-1242, 2010.
Asiri Wijesinghe and Qing Wang. A new perspective on "how graph neural networks go beyond weisfeiler-lehman?. International Conference on Learning Representutions, 2022. URL
https://openrevit net teee//forrumllduuug000000
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00820 2018.
Wei Ye, Omid Askarisichani, Alex Jones, and Ambuj Singh. Learning deep graph representations via convolutional neural networks. IEEE Transactions on Knowledge and Data Engineering, pp. 1-1, 2020. doi: 10. 10.1109/TKDDE.20003014444
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 7134-7143. PMLR, 2019. URL
mlr. wtt..prres//v9/yyulll htmml
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovee. Identity-aware graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 35712)177711 2021. Utttt:s:: www.oisssaaaa...mmmmmm.m........ org / index. wwtpdexx.pp//AA.ee http:p//p.aaaaatttee////////////
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A the- ory of using graph neural networks for multi-node representation learning. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang. and Wortman Vaughan (eds.), Ad- vances in Neural Information Processing Systems, volume 34, pp. 9061-9073. Curran Asso- ciates, Inc., 2021. URL URLRRtpss//poocccnnnn.. http:////p.ccceeen.neeeeeee////p fber4/e2992220010000092222222333
12

---

Published as a conference paper at ICLR 2023
A PROOFS
A.1 CELL COMPLEXES AND COVERING SPACES
In this section, utilize the theory of covering spaces provide rigorous formulation that Weisfeiler-Lchman test encapsulates local topological properties of graphs by representing finite depth unfolding trees using node attributes. Readers who are interested in a rigorous treatment of the theory of covering spaces may refer to Hatcher (002) or Krebs & Verbitsky (2013). Krebs and Verbitsky Krebs Verbitsky (2015) proved that the Weisfeiler-Lehman test represents a pair of graphs with fixed constant node labels as identical vectors if and only if their universal covers are isomorphic. Combined with the results on the equivalence between graph neural networks and Seesfeiler--ehmmae tests Xu et al. (2018), we prove that graph neural networks represents pair of graphs with arbitrary node labels as identical vectors if and only if there exists a graph isomorphism between their universal covers that induces an equality of node labels on the universal covers.
Throughout this paper, we consider a graph := (V, E) as a cell complex, which is constructed as follows.
Definition A.1 (Graph as a cell complex). A graph G = EV may be constructed the following procedure.
1. The set of nodes V := (G) corresponds to a discrete set of points {e)eEv(G) (0-cells).
2. The set of edges E (G))) corresponds to discrete set of intervals {00, EEEG))))))
(1 (1-cells).
3. The graph G is inductively constructed by attaching the endpoints of the edges to their corresponding nodes. That is, given interval [o, 1] corresponding to edge (21, one glues the endpoint {0} to the node 81, and the endpoint {1} to the node U2.
4. One may iterate the inductive process finitely or indefinitely many times, depending on the cardinality of the set of edges.
We call the spaces constructed in this manner as a 1-dimensional cell complex.
Cell complexes allow one to endow graphs with topological structures induced from that over the set of discrete points and the unit interval [0, 1]. Let us recall that the subset of points characterizes the topological structure defined over the discrete set of points, whereas the open intervals (a, b) with 0 S a < b < 1 characterizes the topological structure defined over [0, 1]. In an analogous manner, the open subsets characterizing the topological structure over graphs are the subset of nodes, the open intervals defined over an edge, and the open subset centered at node obtained from gluing set of open sub-intervals with common endpoints v. Taking countable unions and finite intersections of these three types of open subsets, one shall construct any subsets which represent local topological properties of G.
Definition A.2 (Covering Space). Let G be graph. Let x E G be a point, which could be node E VGG) or any point an edge E E(G). A covering space of G is graph & with projection map pa: â - G such that for any point G. there exists an open subset U G whose pre-image PG (U) is a disjoint union of open subsets (U:), each of which are homeomorphic to U.
In other words, a covering space & of G is graph whose local topological properties are equivalent to those of G. In this paper, we will consider the universal cover of G. which a canonical graph whose subgraphs correspond to paths in G starting at a node E V(G)) up to homotopy, equivalence relation which rigorously defines continuous transformation from one path to another path with same end points.
Definition A.3 (Homotopy). Let f and be two paths in the graph G which starts from a node vo and ends at a node V1. Note that these paths can be considered as functions from the unit interval
[o, to G, i.e. f.g [0, 1] + G are paths such that ʃ(0) = (() = up and f(1) = g(1) = vi- We
say that two paths f and g are homotopic if there exists continuous function H [0, 1] [0, 1] G such that
1. (1, f())
13

---

Published as a conference paper at ICLR 2023
2. H(t, 1) g(t)
3. H(,, x) Ug and (1, 22 U1 for every [0, 1].
The homotopic relation on paths with the same end points in any space an equivalence relation. see Chapter 1.1 of |Hatcher (2002) for the proof of this nontrivial fact. Given a path f [0, 1] + G over graph G, we denote by [J] the equivalence class of f under the homotopy equivalence relation. Using this equívalence relation, we now construct the universal cover of graph G.
Definition A.4 (Universal Covering Space). Let G be graph. Fix point V(G). The universal cover of G, denoted as G, is the space of homotopic classes of paths in G starting
G = : f [0, + such that f(0) o}
(11)
We end this subsection with the theorem that universal covers of connected graphs G' is a graph without any cycles, whose proof can found Chapter 1.3 of Hatcher (2002).
Theorem A.S. Let G be connected graph. Then its universal cover G is simply connected. In particular, a connected graph without any cycles.
A.2 GRAPH NEURAL NETWORKS
Given graph G == (V, F.) with nodes, denote by A E TR the adjacency matrix of G, D E R the diagonal matrix of node degrees of G, and X E R the matrix of concatenated k-dimensional node attributes of G. Denote by Á Rexa the normalized adjacency matrix of G. (One may take, for instance, À D- AD-
Definition A.6. Throughout the appendix, we use the notation {{+}} to denote a multiset of real vectors, i.c we allow multiple instances of its elements.
Remark A.7. Let M be the collection of all multisets of k-dimensional vectors with elements, counting multiplicities. Suppose F Rkxm > RR is a function which is invariant under the permutation action of the symmetric group with elements Sn- (The action corresponds to the permutation of rows of the x m real matrix). Then the function F induces the function over M defined as
F: M + R¹
(12)
{ir U2 1m F(e1, U2, ... Um)
We recall the definition of graph neural networks proposed from Xu et al. (2018).
Definition A.8. We denote by GNNi the graph neural network comprised of composition of /
neighborhood aggregating layers.
1. Each m-th layer ((m) of the network constructs hidden node attributes of dimension km denoted (m)) using the following composition of functions:
(m) = COMBINE (m) (N/ (m-1) AGGREGATE("") A
({( N (m-1)
}b))
(u,))EF(()
X
(13) In the equation above, X, is the initial node attribute at v, M((m) is the collection of all multisets of kn - real vectors with dog u elements counting multiplicities, the aggregation function
AGGREGATE MM() R
(14)
is a set theoretic function of ky, -dimensionnl real vectors defined over My, and the combi- nation function
COMBINE :B 1 km
(15)
is set theoretic function combining the attribute 1m--1 and the image of AGGREGATE (m)
14

---

Published as a conference paper at ICLR 2023
2. Denote by HQ the final layer of the network. Let M0 be the collection of all multisets of ky diddemnniional vectors with # V (G) elements. Let
READOUT: MM + TR.K
(16)
be the graph readout function of K-dimensional real vectors defined over the multiset M() Then the K-dimensional vector representation of G, denoted as hGg is given by
hg == READOUT (Hth!) e [(()))))
(17)
Observant readers may notice that graph neural network is a generalization of the color refinement algorithm, which is designed for distinguishing non -onioooooppiic pairs of graphs with identical discrete node labels Krebs & Verbitsky (2015).
A.3 HIDDEN NODE ATTRIBUTES AND UNIVERSAL COVERS
We now provide rigorous formulation that graph neural networks compute vector representations of finite depth unfolding trees of graph.
Definition A.9. Let := (V,E) E) be a graph. Denote by := (V, E") the graph where every node has self-loop. Denote by G" := (V, EE) the directed graph with a projection map p G" G" such that each undirected edge of G' from U1 to 822 corresponds to the following edges:
1. If A U2, the undirected edge corresponds to two directed edges, one edge from ii to U2. and the other from U2 to U1.
2. If 11 = U2, the edge corresponds to a single directed self-loop from 01 to itself.
By construction, k-dimensional continuous node attributes over G, denoted the function fc VG) + R clearly extends to continuous node attributes over G", denoted as fa" VVG") + IR One can also induce attributes over the set of nodes of the universal cover of G. We achieve this by pre-composing the function fo with the covering map TG G + G.
Definition A.10. Let fc (G²) + A be the function k-dimensional node labels over the graph G. Let ग.. : G + G be the universal covering map. Note that the covering map restricts to function between set of nodes ae : V(ā) + VG)). The pullback of the node labels to the universal cover G is the composition of functions fa अद VV)) - RR (See Figure 6 for an illustration of how pullback of node features are defined over the universal cover).
Definition A.11. Let G == (V, E') be a directed graph. For each node E (G) and any positive number k. the depth-k neighborhood rooted at v, denoted as Ub. is subgraph of G whose set of nodes consists of the distinguished node itself and the nodes w such that there exists at most k consecutive directed edges from v to w. The of edges of U are comprised of unions of all consecutive directed edges from e.
(For any undirected graph, the finite depth neighborhoods rooted at v is defined in an analogous manner, where the set of edges is comprised of undirected edges among a pair of nodes of G, instead of directed edges).
Given graph G, there exists an injective lift of set of nodes from G to G". defined as
ig V(G) - V(G') - V(G") + V(²")
(18)
Likewise, there also exists an injective lift of nodes from G its universal cover G:
&G V(G) + VG)..
(19)
Using predetermined injective lift of nodes of G Ô and Õ", we may define finite depth unfolding trees at a node E V(G) as follows.
Definition A.12. Let G := (V, E) be a graph. Fix an injective lift ig V(G) + V(G"). The directed depth i unfolding tree node v E VG),, denoted as T is the depth-k neighborhood rooted at (v) as a subtree of the associated universal cover Ō" of G. The undirected depth unfolding tree at node v E (G),, denoted as Tk.an is the depth-k neighborhood rooted at ia (v)
subtree of the universal cover & of G.
15

---

Published as a conference paper at ICLR 2023
Throughout this manuscript, will abbreviate the choice of injective lift from the base space G to its covering space G". This is thankfully because if G" is an infinite graph, then the construction of universal covers imply that the directed depth k unfolding trees rooted at a fixed node v E V(G) obtained from any given injective lift &g V(G) + V(G") are all isomorphic to each other. With abuse of notation, will not specify the choice of injective lifts when defining depth k unfolding trees.
We note that the initial node attributes X used for graph neural networks (Definition A.8 is given by
X = fa( (far TT" (ia(v))
(20)
Example A.13. Let G be undirected graph without self-loops given in Figure 3 The associated graphs G" and G" are given as in Figure 3 Let fc V(G) + I2 be function of 3 3-dmennsional node attributes over G. In the exemplary figure, the given node attributes are coordinate-wiss real vectors. each represented as discrete node labels, i.e. (1,0,0) 0) + A, (0, 1,0) + B, and (0, 0, + C. the directed depth 3 unfolding tree node, considered subspace of the universal cover G" of G"
Figures and (anddnddetsstrati
Remark A.14. Given a node e E (() of an undirected graph G == EV, the following three relations hold among directed depth m unfolding subtrees of 1?
1. For any two nodes W1, adjacent to e E V(G) excluding itself, there exists a pair of disjoint subtrees T1, T2 of T C G" which are isomorphic to directed depth m unfolding trees rooted at w1 and W22 i.c.
Tw
=
(21)
2. The tree T contains disjoint unions of directed depth unfolding trees rooted at all nodes adjacent to v (including itself), i.c.
THD
(22)
(EV(
(w.))EE(G)
3. The set of nodes of the tree T is the disjoint union of the singleton set {v} and the set of nodes of depth m unfolding trees at all nodes adjacent to a (including itself), i.e.
V ((Tm+1))
{n} U
L WEV(() (w())
V(T.))
(23)
Figure 5 illustrates how directed depth unfolding subtrees of T constructed from Figure satisfy the three aforementioned relations. Note the depth 2 unfolding subtrees rooted at each node are marked in different colors.
The goal of this section is to identify hidden node attributes obtained from graph neural networks function from a multiset real vector spaces. To do so, define what is called the multiset of nested multisets associated to finite depth unfolding trees. Before doing so, we introduce some notational abbreviations.
Definition A.15. Given multiset S and number d, we use the abbreviation {{S) Ja to denote the multiset whose elements are multisets of d elements in S. Given function of multisets f A + B, we denote by {{f}} A + {{B}} } the function obtained from representing each image of as singleton multiset, i.e.
(a)))a) = {{f(a))) for any A
(24)
Given two multisets A, B, the sum of two multisets, denoted as A + B, is a concatenation of A and B, i.e. it is a multiset whose elements are in either A or B, and whose element- wise multiplicity is the sum of multiplicities of elements of A and B. One may use the usual summation notation Σ to denote sum of several multisets.
For example, element of {{I*>) Hes is multiset of 3 real vectors of dimension k. Given real valued function f(x) = 2z. the function {(f)} sends x to the singleton multiset {[2x]}. The sum of two multisets ([2,3, 3, 5)) and ((3, () is equal to {(2, 3,3,,, 6,
16

---

Published as a conference paper at ICLR 2023
G= (V.E)
G' (V,E")
G" (V,E")
Figure 3: An exemplary graph G with the induced graphs G' and G".
Graph
C"
Layer 1
ABC
ABC
APDC²
AT A
Figure 4: An illustration of Theorem A.19 Each respective node labels obtained from summing the attributes of the node v itself and those of nodes adjacent to correspond to the sum of attributes of nodes of G in the respective colored regions.
Esos:
Graph d
Greph
AE
Layer
Uayer
Figure 5: An illustration of three relations among depth unfolding subtrees of T from Remark A.14 Each respective node labels obtained from summing the attributes of the node itself and those of nodes adjacent to v correspond to the sum of node labels TTe the respective colored regions.
17

---

Published as a conference paper at ICLR 2023
G
= (V,E""
Figure 6: A visual demonstration of pullback of node labels from given graph G" to its universal cover G", as defined from and identical colors.
The corresponding node attributes and edges are marked in
Definition A.16. Let G = (V, be finite undirected graph without self-loops, fa V(G) - R the function of --dimensional node attributes over G, and T the depth unfolding tree at v (()) We inductively define the multiset of nested multisets Ti' associated to the depth unfolding tree T as follows.
R (vy
if = otherwise
(25)
where Σ is the multiset summation operator.
Remark A.17. We note that the multiset of nested multisets Ty is not identical to the multiset of of k-dimensional real vectors with # (V \ V(T!-)) elements. Nevertheless, recall from Remark
A. that
V(T) \ V(T
U
V(T--)).
(26)
w (TT)AV(
The above relation, along with the inductive construction of T. induces an inductive construction of morphism
PTg (===VVV
II weV (T)AV(T))
R + T
(27)
which sends a tuple of node attributes ((far (T))())) uev 1 supported over the set of nodes V (T!) \ VIT--1) to the corresponding multiset respecting the subgraph structure specified by depth 1 unfolding subtrees. Here, for each E VTT!) V)T"), the vectors L!-1 are elements of R i.e. the concatenation of all k-dimensional node attributes supported over the depth - unfolding tree rooted u.
(a(()) EvEVerANveR (1PPH-1))(II.))
if 0
Prg "uevorevee))))
(28)
otherwise
Note that Pro is the identity function from R to itself. As will be demonstrated in the upcoming example, the functions Pry are generalizations the Prisfeiler-Lehmae iteration scheme for updating node attributes.
18

---

Published as a conference paper at ICLR 2023
Example A.18. Let G' be undirected graph without self-loops given in Figure 3 Let fa: V(G) + R be a function of 3-dimensional node attributes over G. Recall that the given node attributes coordinate- real vectors, each represented discrete node labels, i.. (1, + A. (0, 1,0) > B, and (0, 0, + C.
Let E V(G) be node whose attribute is represented A. Denote by di E V(G) the node whose attribute is represented as B, U2 E (G) the degree 3 node whose attribute is represented at C, and ug the remaining node. Figure illustrates the directed depth unfolding tree T rooted the node v. We explain how the maps Pro.Pr3 and P1z are defined. The map Pre : RR IR' by definition, an identity function.
Pro (A) =
(29)
The map Pri [ + To sends a tuple of 3-dimensional real vectors of length deg 0 4 to the following multiset:
Pry : ==x*(((
- T
Σ
{[R")) 1112)
(30)
Pry ((A,) = ((Pry ((Pr (B))) + HPPY, (C)) + HPrgg (C)H)
[[AA) + + [[C))
([A,B,C,C]
The map Pry [=xx*((())) + T sends tuple of 3-dimensional real vectors of length
(V(T)) v(T))) 12 to the following multiset of multisets:
PT3 (** +
Σ
(T.
PP((AAB.CCCCABB.CBBB..C.CC VEV(TRNVV
(31)
=(Ip:))(.BBBC.C) (fPr, (I(A, BAAB BHA,C) (I + ([(AAC))
B,, (HABB)))
Using these definitions, are able rigorously formulate that graph neural networks capture local topological properties of G by representing subtrees of the associated universal cover G" as real vectors.
Theorem A.19. Let G = (V,E) be a graph. Denote by fc V(G) B the function of k- dimensional node labels over G. The node labels over G can be extended to those over the graph G", denoted as fc.. Denote by TG G" + G" the universal covering map of G". Let T be the directed depth unfolding tree of the graph G" at the node (G")..
Let G be a graph neural network comprised of layers. For each node E (G), let T' be the multiset of nested multisets associated to the depth unfolding tree T,, as constructed Definition 1.16 Let PT: : .Rkxx #(V(T)) ((T-->)) - T be the morphism defined as Remark 17 Then there
exists set theoretic function Ft ? R such that the node label obtained from graph neural networks with layers given by
h = F.. (pT: ((Jorr TT (ui) (e
(32)
In other words, the updated node attributes are obtained from set theoretic function supported over the set of nodes in (IT) 11.
Proof. We prove the theorem by induction. For any graph == E) with predetermined normalized adjacency matrix A, denote by a,, the entry of the normalized adjacency matrix À at a pair of nodes (u,
Suppose 1 = 1. The node label at u E V(G) updated from a graph neural network with a single layer is obtained from taking weighted sum of labels of nodes adjacent to and the node itself, followed by evaluating the newly obtained attributes using the activation function o By construction, the depth 0 unfolding tree of the graph G" at is the node itself. The parent node of the depth
19

---

Published as a conference paper at ICLR 2023
Graph
A
B
Graph 6
14
P2
B
B
B P1P2
Figure 7: A visual representation of the set of nodes AT and B from the exemplary graph G from Figure 3 Observe that the lift of nodes V1 V(G) are notated Vayy and the corresponding set of nodes A, and " for m are shaded in distinct colors.
unfolding tree T is the node v. The child nodes of T! are the nodes of G adjacent to v, including itself. Hence there exists bijection
p. ((v) U (u E V(G) u u, (u, v) E F(G))) (V(T)) (V(T))
(33)
which induces an equality of respective restrictions of node attributes fc and for ogg.. By definition and the existence of the bijection (p1, there exists function F! To - R such that
A F. ([((fo" (T) | wE V(T.) (
(34)
= =F Pr: ((Ifom To (w)) (w)a
Suppose the theorem holds for 1 m. For any node adjacent to v (i.e. u (V(T.) (o))), the three relations from Remark among directed finite depth unfolding trees establish bijection of set of nodes T Am + B where the sets Am and B are given as
A V V(TTT-))
(35)
Bm (ITm+I))
U
A
wE(A)M))
The bijection Po induces an equality between respective restrictions of pullback of node attributes fo" Tgr. The collection of bijections {xpt! TueAs extends to bijections
m+
L
B
m
WE Ag
(36)
gm++
B
+ A mm+1l \ AT
uEAdMu)
both of which induce equalities between respective restrictions of fa" gg.. We refer to Figure 7 for an illustration of the set of nodes A and B obtained from the exemplary graph drawn in Figure
Denote by 7 the following multiset of nested multisets:
7m+1
Σ (
(37)
WEV(T!) Te (u)
20

---

Published as a conference paper at ICLR 2023
In other words, Tem+! is multiset summation of nested multisets associated to depth unfolding trees Tu rooted at all nodes u which do not map to the given node under the universal covering +
map xg" G G". Denote by Pro+t 1 IR R (AT)
T the function given by:
Prm+ (w
Σ
(38)
DEAD AA
Here, for each node u, the vectors D elements of RkxT.", i.e the concatenation of all k- dimensional node attributes supported over the depth m unfolding tree rooted at u. Note that as multi-set function,
Pron+i ((I ((=VeCCCC))v))))) = Pry (I ) + PTo+ (1 weww)attiiA (AT)
(39)
For some positive number Km there exists function Fm++l Tmutl - BR such that
AGGREGATE(<*)) (((1)m)) (u.))EB(G) {1]
(
NEV(G),uzt
}
(40)
Fm++1 (Drget ((Ifor (To
To see this, we observe that
AGGREGATE, (m++)
(1) (m))
(11 h (mm)e
AGGREGATE (m+1)
}}) ({{ F. (Pr. ((Jo (wT u A, 10 (o0)]))
({{ PT (pt." ((Jor oW (T) ))
vevic)ute)) (u.))
(41)
AGGREGATE(
= Em++1 (prm ((Ifo o(
The last equation follows from the following observation. The domain of the aggregation function is supported over the set of nodes Lue B Applying the bijection Gm* implies that the aggregation function is defined over the real vector space supported over the of nodes Am+1 \ A
By 39 we hence obtain that there exists function Fm++1 : :Tm++ - Bd+++ such that
h (m++) COMBINE (1) (N(T)) AGGREGATE("" ((l
((())) "EV(G), wse ((,o)EE(G) ((Ifo (w))(())
11))
COMBINE (m++)) (H(m), (mmt (prm--
Fm++1
(m) (FTh pr. ((Jeor (T)" pm++l (prm+) o
fmm+
(
(prmet) ((1frv ((r
(42)
Example A.20. We revisit the graph G as shown in Figure Consider graph neural network with m layers such that for all layers the aggregation function AGGREGATE, and the combination function
COMBINE correspond summation of respective node attributes. One may consider the resulting GNN simplified generalization of the Weisfeiler-Lehmee attributes. Concatenations of adjacent discrete node labels correspond to summations of adjacent node attributes, whereas substitutions of newly obtained node labels are skipped. Then there exists correspondence between the node attributes updated from the graph neural network with m layers and the attributes the set of nodes in V(TT)) ((I:n=I) )). For example, indicated in Figure 4 and [5] the updated node attributes can be obtained by counting the number of occurrences of attributes in the respective colored region.
isomorphism test for continuous node
21

---

Published as a conference paper at ICLR 2023
A.4 PROOF OF THEOREM 3.3
Xu et al. shows that graph neural networks with injective node feature aggregating functions and injective graph-level readout functions are as powerful Weisfeiler-Lehman isomorphism tests in distinguishing non-isomorphic classes of graphs Xu et al. (2018). Using the theory of covering properties of Weisfeiler-Lehmen tests
spaces, we prove a refinement of the moomorphimm-nnvarii over graphs with identical node labels Krebs & Verbitsky (2015) for graph neural networks.
Under certain conditions, the vector representations of graphs obtained from graph neural network can distinguish isomorphism classes of universal covers of graphs as well as non-equivalent pullback of node labels.
Theorem A.21 (Theorem 3.3). Let G be a collection of finite connected graphs such that the least upper bound of their diameters is equal to d. Suppose a graph neural network GNN with layers satisfies the following three constraints:
For every such that 1 S S l and for each u E VVG), the the functions AGGREGATE and COMBINE( are injective.
TTee graph read-out function READOUT is injective.
2 2d.
Then GNN maps any two connected graphs G, H G with the same number of nodes to identical vector representations if and only if there exists isomorphism of universal covers y G" H" that induces an equality of the pullback of node labels, i.e.
hg hu
3 issoorphismm &p G - s.t. fo" TG" f o TH" o pp
(43)
The theorem generalizes the result of Krebs and Verbitsky Krebs & Verbitsky 2015) for pairs of graphs with fixed constant node labels. Before we prove Theorem 3.3 recall the definition of graph diameters and note the following lemma.
Definition A.22 (Graph Diameter). Let G == (V, F)) be finite undirected graph. Given a pair of nodes v, w VG),, let Pe. be the set of sequences of edges (e4) such that one can move from node v to node w by traveling along the sequence of edges (es) The length of the path p is the size of the sequence, i.c. I(p) (((e)){))) p. Then the graph diameter de of G is the
maximum of the shortest length of paths required to move between any two nodes. In other words,
max min ((p) dG (e,))E((G) APEP...
(44)
Lemma A.23. Let G1 and G2 be two undirected graphs with funie number of nodes. Let fcr V(G.) + R² and fa, : V(G22 - R be node attribute functions over G1 and G2. Denote by TG. G, + G; and σेद : G, - G. the universal covering maps for i == =1==1, 1,2. Then the isomorphism G2 + G2 induces an isomorphism h² -G," - G2 and vice versa. If such isomorphisms exist, then fc, TTC fc, o TG2 h if and only if fay कeद = fag Tez h".
Proof. Let v E V(G) be a node of an undirected graph G. We observe that collection of finite depth unfolding trees rooted at nodes of a universal cover & (or Ō") defines an open cover. hence suffices to show that for any I, two undirected depth / unfolding trees Ty.an are isomorphic if and only two directed depth unfolding trees T are isomorphic. Note that by the construction of finite depth unfolding trees, the result on equality of node attributes follows immediately.
As constructed from Definition A.12 we denote by T7.an C Ô the undirected depth 1 unfolding tree rooted at and T) C. G" the directed depth unfolding tree rooted at Note that the directed tree T! can be constructed from the undirected tree Tl.un by substituting all undirected edges with directed edges from its neighboring nodes, adding new copy of the node itself, and adding new directed edge from to its copy. This demonstrates that the statement holds for I -
Suppose the isomorphism invariance of unfolding trees holds for k. As before, denote by Tk+11um C & the undirected depth A: + unfolding rooted v, and T C Õ" the directed
22

---

Published as a conference paper at ICLR 2023
Graph
Graph G"
Graph
Graph G"
Figure 8: A comparison between the universal cover & and the induced universal cover &" of graph G constructed Figure
depth k ++1 unfolding tree rooted at c. The directed tree Th++1 can be constructed from the undirected tree T using the following procedure. For every node E (T?..u)) {v). substitute the undirected tree Tk.un rooted at t with the directed tree u- We then add disjoint copy of the directed tree T and add a new directed edge from the root the tree T*+ to the root of the newly added tree T (This corresponds to adding new directed edge from to its copy). The procedure guarantees to map isomorphic undirected unfolding trees to isomorphic directed unfolding trees, and vice versa. A visual illustration which compares the undirected and the directed rooted unfolding trees can be found in Figure g
We recall the following two lemmas isomorphism classes of finite depth unfolding trees. Both lemmas are reformulations of Lemma 2.5 and Lemma 2.7 of Krebs & Verbitsky (2015), which proves the statements for undirected finite depth unfolding rooted trees.
Lemma A.24. Let u, w E V(G) be any pair of nodes such that for any ' 1, the following conditions hold.
1. The two directed unfolding trees T and Ti-1 are isomorphic.
2. There exists bijection of nodes gt (T?) + ((TL) such that for all u. E (T?), the two directed unfolding trees T and T gi()) are isomorphic.
Then the directed unfolding trees T1+1 and T(+1 are isomorphic.
Lemma A.25. Let G, H be two connected graphs with at most n nodes. Let d be the maximum of the diameters of two graphs G and H, i.e. := max(do, d Then for any pair nodes E V VGG and w E V(H), the directed unfolding trees T and T w are isomorphic for any I 2 2d if and only if
T2d-1 and 2 are isomorphic.
Proof. Note that any depth-d unfolding tree rooted at node VG) or u E V(H), as subspace of the universal covers G and H" contains all pre-images of the set of nodes V(G) and VHH). This V(G)
implies that any depth-2d unfolding trees rooted any node all possible rooted depth-d unfolding trees. remains to invoke the ideas of the proof of Lemma 2.7 of Krebs & Verbitsky (2155) further reduce the lower bound of / from 2n to 2d.
V(H) contains
23

---

Published as a conference paper at ICLR 2023
Using the aforementioned lemmas, able prove that the hidden node attributes obtained from GNNs with layers whose combination and neighborhood aggregation functions are injective indicate the isomorphism classes of depth unfolding rooted trees.
Lemma A.26. Let G and be connected graphs with n nodes. Denote by fa V(G) - R and fH : ( + RK the d-ddimensooal node attributes of G and H. Denote by TG : G - G" and TH H" - H" the universal covering maps of the induced directed graphs G" and H
Suppose a graph neural network GNN with I layers satisfies the condition that for every m such that I m S and for each node of any finite graph G, the functions AGGREGATE, (m) and
COMBINE m)) are injective.
For each E V(G), pick a bijection of set of nodes o. : V(G) V(H) which induces an equality (not an isomorphism) of depth-1 unfolding tree at u and (v( ie. 6,(T.) = 6. or.0)) Then for every 1 S m S I, the bijection 6o induces an equality of hidden node attributes h(m)) and h (m) obtained from GN No for every node u E (GG if and only if the bijection oy induces isomorphisms Pu.m T
(v)
Tm that imply equality of node attributes over the trees T and T In other Do (v)
bu(n)
words:
3 Po.m T.t - TT to
(6) such that yfr Mrm o.pmm
h
(m) (e)
41 m SL
(45)
(e(e)
Note that the bijections for f (VE(()) may not necessarily be singleton set. We refer to Figure for an example pair of graphs G and where one needs to choose distinct bijections d, for each node v.
Proof. This lemma is a generalization of Lemma 2.6 of Krebs & Verbitsky (2013). We prove the statement of the lemma by induction 1. The base case for 1 is trivial, the statement of the lemma simplifies to comparing the attributes of a given pair of nodes.
Suppose the equivalence relation holds up to I 4-- For each v E V(G), let d. V(G) - V(H) be a bijection of set of nodes which induces an isomorphism of depth-1 unfolding trees rooted at o and @i (v). Suppose the hidden node attributes obtained from GN with at most lo 1 layers
identical for every node, i.e. A, (m) = de(e) for S m < l0 + 1. By the induction hypothesis, for any
(m)
1 S S lo, the following equivalence relation holds for each pair of nodes (())
3 2.u.m:: 4 (w) such that ((groogar))ly = =(furor aope pppu.m
(m)
(v)
(m)
(46)
Observe that for each S i lo. the isomorphism so,s T3 To (v) induces the following equivalence relations for all pairs of nodes {u, (e.(())))))ee
and for any 1 S m S lo:
PT T + Tm TT (fonota" =lg (f ue 3 1z
Fu,s(w) (w) such that
A (u)
(m)
(m) mnr (w).
(47)
Pe, offu.m
Note that (u) = (u) because o induces an isomorphism of depth-1 unfolding trees at v and (v))).
Consider the open cover of T by the directed trees (The huEV(Ty). The intersection of any two trees satisfy
(T if u E V(T.) and w/ E VV(T)
To
(48)
otherwise
By Lemma A.24 the collection of isomorphisms
{4au, huev(r))) U -/
(49)
induces the isomorphism PP.lo+1 T
+
b.(o)-
Recall that the hidden node attributes h (l++1) and h (l+t1) are identical. Then the following collections of multisct of node attributes are identical.
(v)
((Ifar (() wer
Prio+1 ((forr o = = butn)
(50)
24

---

Published as a conference paper at ICLR 2023
Universal Cover 6"
Universal Cover H
T Oog
(11)
Pu.1
T (v)
Graph
Graph
pn (12)
Dy (v))
12
Φv
1/4
Do (Pa)
Poy (v))
F3
1/. A
Φor (v5)
Du, (16)
Figure 9: A visual demonstration of the gluing procedure from the proof of Theorem A.26 One can construct an isomorphism between a pair of depth / + unfolding trees rooted at v and ou (v) by identifying the isomorphism classes of depth unfolding trees rooted at and (v) for all E ( and gluing the trees in accordance to their intersections, which are depth / - unfolding trees (48) Observe that the bijection of the set of nodes Ov, does not induce an equality (not an isomorphism) of depth-1 trees at and &u, (v:) for i 2, 5, 6. For example, the set of nodes of the undirected depth-1 unfolding tree at 02 is given by {ui, 12, U5}, whereas the of nodes of the undirected depth-1 unfolding tree at dn, (v2) is the set { (v1), dv,, (12), &o (v3)}. For such nodes, different choices of the bijections of the set of nodes @u; are required.
The above equation follows from the condition that the functions AGGREGATE("" and COMBINE(")) are injective for all E V(G) and S S to + 1, which implies that the function over the multiset of labels Fla+1 as constructed from Theorem A.19 is an injective function.
The collection of isomorphisms from (49) further indicates that for any VTT.) \ VTT),, the following equality of node attributes over T Tie and their intersection T
(Jer o TG" )lpo (SH" o TH T
o O
Bo(o)
(fa" o TT") )l (fH" o TH" Mgyoo o foplo
(u(()
(51)
(Jar To" )1 ) nT: (So" o ='G))Td0-
= =ffr o TH") )1oo o Puulo1 = (fH" o TH THH))lp bal no
o Pado-1
(o(1))
extends the equality of node attributes over Tio UT:o:
(fa" o TT" ( (fH" o TH" )roo b. ,n unh o Po
(52)
Iterating the gluing procedure for all depth trees (T (NEV(T))V(T)) results in the desired equality of node attributes over T
Now suppose that there exists an equality of node attributes between Tio+1 and Tlo+1 induced from (e(e)
the unfolding tree isomorphism F Tho+1 - Tol++11 (e))) Theorem A. implies that there exists
a theoretic function Flo+1, Tooo+1 R such that the node label at v obtained from graph neural networks with / layers is given by
1 (1) = plo+1 (Prgot1 ((Jor o
)
(53)
25

---

Published as a conference paper at ICLR 2023
The conditions that AGGREGATE,,++/ and COMBINE (lo+1)) injective imply that F is an
injective function. Therefore, the equality of hidden node attributes Ite (1 h (a++1
(w) follows
immediately from the fact that the equality of node attributes between depth to + unfolding trees ensures the equality of collection of multiset of node attributes over V(T (TT)).
Using Lemma A.25 and
A.26
we now prove Theorem 3.3
For each v E ((G), let é. V(G) - (H) be a bijection of set of nodes of G and H which induces an equality of depth-1 unfolding trees and (o(v). Lemma A.26 implies that the following equivalence relation holds for every v E V(G):
Theorem A.27
Theorem 3.3
PPe. Touces such
h(())
h(mm) (v) Vu V(G) and 1 1 m S 2d. (54)
(San on llzg =1 yo I1 o.Pu.m
(e)
(e)
Lemma A.25 implies that for any positive number 2 2d, the following equivalence relation holds:
R A.pa T such that
(m) h!mm) (o(()) Vo E V(G) and m S 2d. (55)
(fanorgu)
=/ (ffp((ffor Au(w)
open
Consider the open cover {T wev((d") consisting of directed depth / unfolding trees rooted every node of &" Note that for any E V(G"), there exists node E V(G) such that T = TV For any two nodes w1, w2 E V(C),, there exist injective lifts ic (w1) and (w2) whose corresponding depth / unfolding trees rooted at w,' 's satisfy the following equation:
if m consecutive directed edges from (w(w)) to (w2)
nTI wg
=
Tun 0
if 3 m consecutive directed edges from (w2) to (w()) (56)
otherwise
if and only if for some 2 2d, there exists a bijection @ V(G) (H)) which induces an isomorphism of directed depth I unfolding trees Pud T ~ d(v) for every E VGG). Furthermore, the induced node attributes fa" TG and fH" TH identical if and only if for some > 2d, there exists bijection &u V(G) V(H) which induces an equality of node attributes
Hence there exists an isomorphism &
(fo T (fH" TTT ov(0)
o Poel
(57)
imposed on directed depth unfolding trees Ty TV (o( for each e E V(G). Therefore, we obtain that
3 v: -- H" such that farongu= -fn on oup
h(m) h (m) (v(e)
Yu V(G) and 1 I S 2d.
(58)
Because the graph readout function READOUT is injective, we obtain
h (m)
(m)) (v)
Vo E VG)) and m S + hG hg
(59)
Combining the two equations above proves the theorem.
Remark A.27. One can in fact use Theorem 3.3 to establish notion of weak isomorphism between pair of graphs G1 and G2. Let & be the collection of finite connected undirected graphs. One may define a weak equivalence relation among the elements of G by constructing function F F - X from & to the space of regular cell complexes weakly isomorphic if and only if their images F F(G1) and F(G2) are isomorphic as cell complexes. We refer to Definition of Bodnar et al. (2021a) for a related concept named "cellular lifting map". Theorem 3.3 proves that conventional GNNs establishes weak isomorphism among graphs in G using the lifting function F : G Xaniv from 9 the collection of universal covers I-dimensional cell complexes Xyniv-
with the property that two graphs G₁ and G2 are
26

---

Published as a conference paper at ICLR 2023
A.5 PROOF OF THEOREM 4.3
We now prove that the Cycle-to-Clique graph networks are more powerful than graph neural networks in distinguishing non-isomorphism classes of graphs.
Remark A.28. As stated in the main manuscript, there are four approaches that enrich the input data structure of graphs the graph neural network may process to distinguish non-isomorphic classes of graphs.
1. Unique assignment of node labels: We may distinguish distinct classes of graphs by assigning unique (or randomized) choices of node labels. Practical implementations include assigning node degrees as labels, imposing positional encoding, and implementing labeling tricks.
2. Persistent homological methods: We may incorporate homological invariants of graphs to GNNs by utilizing or constructing height functions over nodes and edges and constructing the associated persistence diagrams. These diagrams allow one to keep track of variations in the number of components and cycles throughout the filtration of graph dataset induced from the choice of the height functions.
3. Topological Enrichment:
We may enrich topological structures of graphs by attaching simplicial and cellular complexes, or incorporating subgraph structures. Such actions allows conventional GNNs to encapsulate particular topological substructures of graphs suitable for classifying graph datasets of our interest, such as cliques within social media datasets or cyclic subgraphs within molecular datasets.
4. Construction of non-isomorphic universal covers: We may incorporate homological
invariants of graphs, in particular eyclic subgraphs of graphs, GNNs by constructing new graph structure induced from subgraphs isomorphic to cyclic graphs. It is advised that the universal covers of newly induced subgraphs not isomorphic to each other, thereby allowing the graph neural network to represent a collection of cyclic subgraphs as distinct vector representations.
Definition A.29, Denote by Cn the cyclic undirected graph without self-loops consisting of n nodes, and K2 the undirected complete graph with n nodes without self-loops.
We state a simple result that the induced universal covers of C, 's are isomorphic, whereas those of K, 's are not.
Lemma A.30 (Lemma 4.2). For any n # m, C₂"" Cm" whereas Kn," " z Kmm".
Proof. The proof follows from the observation that any induced universal cover Ō" of a k-regular graph G is isomorphic to directed infinite 2k + 2 regular tree, where each node is connected by + directed edges from source nodes to v, and by l: + directed edges from v to target nodes. D
Hence, the lemma suggests a natural procedure to allow graph neural networks to distinguish cyclic graphs with distinct number of nodes: Substitute the cyclic graphs Cn with complete graphs Kn, Using this observation, we may construct the Cy2C-GNN, as indicated in the main manuscript.
Before we recall the definitions of clique adjacency matrix and the architecture of the Cy2C-GNN, we first state the definition of cycle basis BG of a graph G.
Definition A.31. Let G EV be a finite graph. A cycle basis BG is set of cyclic subgraphs of G such that every cyclic subgraph of G can be represented by unions and complements of elements in Be.
Given that G is connected, a canonical method to construct a cycle basis of a graph G is to find spanning tree T C G. It is a non-trivial result from algebraic topology that if G has n nodes and edges, then the cardinality of any cycle basis of G is equal to m + 1, see Theorem 2.44 of Hatcher (2002) for instance. Because T is a subgraph of G consisting of n nodes and n - 1 edges, immediately obtain that the remaining m
edges of G not lying in T generates the elements of a cycle basis. Indeed, one can construct a cyclic subgraph by adding one of the m + edges the spanning tree T. Figure 10 illustrates example how can obtain cycle
27

---

Published as a conference paper at ICLR 2023
BG =
B'd G
Figure 10: An illustration which shows how choice of a spanning tree of a graph gives rise to a cycle basis BG of a graph (Definition AA.TT). We note that the first, second, and the fifth cyclic subgraphs are chordless, whereas the third and the fourth cyclic subgraphs not (Definition (A.44). The non-chordless cyclic subgraphs can further decomposed into chordless cyclic subgraphs, as shown in the new cycle basis Byg- (Theorem 4.3)
basis associated to choice of spanning tree T. There are systematic protocols to obtain cycle bases of graphs by conducting a standardized procedure in constructing spanning trees of given graph G. such as Paton's 's algorithm which constructs spanning trees using the first or the last element methods Paton (1969), and persistent homological techniques applied over the of edges E(G) with predetermined total order[Hofee et al. (2020).
Let G == (V, E) be an undirected graph. Fix the cycle basis BG of G, the of cyclic subgraphs of G which forms the basis of the cycle space (or the first homology group) of G. The clique adjacency matrix of G, denoted as Ac, is the adjacency matrix of the union of #B complete subgraphs, each obtained from adding all possible edges among the set of nodes of each basis element B Bg. Explicitly, the matrix Ac = (a is given by
Definition A.32 (Clique Adjacency Matrix (Definition 4.2
= -(
B BG cyclic s.t. u, V(B) otherwise
(60)
Given 3 < S C2 < co, one may also define the bounded clique adjacency matrix Acl(e ( (G) which only substitutes cycles of size between e₁ and 02 to cliques:
a (Cullerea == {
3 B E Ba cyclic s.t. E ((B), S [VB)) S 02
(61)
otherwise
For each node v E V(G), we denote by C(v) the set of nodes w V(G) such that there exists eyclic subgraph C' E Bg such that both and w lie in C:
C(v) = fw E V(G) 3 C BG s.t. U,W V(C)}
(62)
Definition A.33 (Cy2C-GNN). Let = (V, be a graph with n nodes and continuous node attributes fa V(G) - R We denote by Cy2C-GNN' the cycle-to-clique graph neural network comprised of disjoint pair of two types of layers: A single neighborhood aggregating layer 11(") utilizing the clique adjacency matrix Ac: And layers of conventional neighborhood aggregating layers (m) for 1 S m < utilizing the adjacnecy matrix A. The Cy2C-GNN model admits the following three matrices inputs:
28

---

Published as a conference paper at ICLR 2023
The adjacency matrix of graph A E R
The node feature matrix X ma*k obtained from the function fc
The clique adjacency matrix Ac E R (possibly bounded) from Definition 4.2
Each types of message passing layer is constructed in the following manner:
The first layer H of the network constructs the hidden node attribute " using the clique adjacency matrix Aç and the following composition of functions:
1.
= COMBINE
(Xe; AGGREGATEE (((X, u (
(63)
As for the other type of the message passing layer, the m-th layer H(m) of the network for each S m constructs the hidden node attribute of dimension km denoted as ((m)) using the following composition of functions:
[m] he (0) X.
COMBINE (m) (hm
(m-1) AGGREGATE("" (m) ((AAT-)))
(m=-1) vEViG)
}}))
(u,r)E
(64) For the two equations above, Xy is the initial node attribute at u, M!!) the collection of all multisets of -dmme-nimnn real vectors with deg elements counting multiplicities, the aggregation function
AGGREGATEE[") MM R
(65)
is set theoretic function of ky dimensioonl real vectors defined over My, and the combi- nation function
COMBINE IR ++
(66)
is a set theoretic function combining the attribute hm-1 and the image of AGGREGATEE For obtaining the hidden attributes, identical aggregation and combination functions are employed.
2. Denote by (9) be the final conventional neighborhood aggregating layer of the network.
The final hidden attribute H, at node u E VVGG) obtained from Cy2C-GNN' is obtained
by concatenating the hidden attributes (1) and h.!) at each v V(G) and composing with multi-layer perceptrons (MLPs):
H. MLP(CONCAT((C)) h(")).
(67)
For S. m < I, let (m) be the collection of all multisets of dimeennnsio vectors with #V(G) elements. Let
READOUT( (m) - R
(68)
be the graph readout function of K -ddimensional real vectors defined over the multiset Mlm), Then the vector representation of G, denoted as Hho.ca is given by
H cco MLP(CONCAT Hea))
Hng READOUT v V(G)
(69)
Hog READOUT (fEC)) (UE
We end this section with the statement that Cy2C-GNN is more powerful than graph neural networks satisfying the conditions of Theorem 3.3 in distinguishing non-isomorphic classes of graphs.
Definition A.34 (Chordless Subgraphs). Let H C G be subgraph. We say that H is chordless if there does not exist a cyclic subgraph C of G such that V(C) C V(H) (See Figure 10 for examples of cyclic subgraphs which are chordless and not).
29

---

Published as a conference paper at ICLR 2023
Let G and H be graphs which have isomorphic universal covers, endowed with node features fG : V(G) + R² and fu : V(G) + R². Fix a cycle basis BG of G. Suppose that there exists chordless cyclic subgraph C. E BG such that any cycle basis Bí does not have any chordless cyclic subgraph of size equal to (CC).. Then Cy2C-GNN which utilizes bounded clique adjacency matrices can distinguish G and H, whereas conventional GNNs cannot.
Theorem A.35 (Theorem 4.3
Proof. Let G and H be graphs satisfying the conditions of the theorem. Let C E BG be the chordless cyclic subgraph of our interest. If a cyclic subgraph Cи E Bн has size equal to [VC)). then Ch is not chordless, i.c. there exist a set of chordless subgraphs CH, C H such that CH = U,CH. Because CH E Bh. we may substitute the element Cи with one of the CH.s's such that (V(C..) [V(CH)] = [VC)]. Therefore, we can assume that the cycle basis Bi does not contain any elements whose size is equal to [V(C). A visual illustration of the aforementioned argumentation can be found in Figure 10, where one can obtain a new cycle basis comprised of chordless cyclic subgraphs of strietly smaller sizes using the elements from given cycle basis. We can hence apply single layer
of Cy2C-GNN equipped with the bounded clique adjacency matrix A |areaal where 01 = C2 = [V(C))- This results in transforming G to be a non-trivial graph including the graph C, and transforming H to be an empty graph. It is easy to see that the universal covers of such two graphs are not isomorphic to each other.
We note that one may still use the usual clique adjacency matrix to distinguish some of the pairs of graphs G and H satisfying the conditions of Theorem 4.3 One needs to verify, however, that the resulting induced graphs associated to clique adjacency matrices of G and H have non-isomorphic universal covers. The upcoming example gives exemplary pairs of graphs for every node [V(G) 2 6 which are discernible by using Cy2C-GNN equipped with the usual clique adjacency matrix.
Example A.36. In this example, we explicitly construct a collection of isomorphism classes of graphs with n nodes such that CyNC-GNN can distinguish, whereas conventional GNNs cannot.
Consider the two connected graphs G and И with 6 nodes as shown in Figure II Theorem 3.3 implies that any GNN (including the Weisfeiler-Lehmee test) cannot distinguish the two graphs because the induced initial node attributes over the universal covers G" and H" are equal.
In fact, for any even number of nodes 2n 2 6, there exists pair of two labelled connected graphs with 2n nodes that any GNNs cannot distinguish. Consider a graph G, constructed from gluing two Cu+1 cyelic graphs along distinguished edge. Consider another graph H,, constructed from connecting pair of distinguished nodes from two disjoint C, cyelic graphs by an edge. Impose identical attributes to nodes based on their degrees. Note that there are 2 nodes of degree 3 and 2n nodes of degree 2. Then the two universal covers Gn and H " are isomorphic. Furthermore, the node attributes over the universal covers induced from G, and H, are identical. Theorem 33. hence implies that any GNNs cannot distinguish G and Hn. However, the two graphs are clearly not isomorphic.
Let Gn be the graph obtained by substituting the two cyclic subgraphs Cx+1 with two complete graphs Kn+1- Likewise, let Hn,1 be the graph obtained by substituting the two disjoint cyclic graphs Cn with two complete graphs Kn, Among the nodes of Gn.1, there are 2n 2 nodes of degree n and 2 nodes of degree n + 2. As for the nodes of H,,1, there are 2n 2 nodes of degree 1 and 2 consists of two disjoint isomorphic copies of infinite trees, each of which is not isomorphic to Gr,,') "), Therefore, any GNNs satsifying the conditions of Theorem 3.3 may distinguish the graphs GR,1 and Hn,,, The Cy2C-GNN captures the non-isomorphism of universal covers by admitting the clique adjacency matrices of G and H as inputs. Note that the clique adjacency matrix of G (and H) is equal to the sum of the adjacency matrix of G.,1 (and Hn,1, respectively) and the identity matrix.
nodes of degree n. Thus, G * H " (In fact, H "
Likewise, there collection of finite graphs with many connected components that any graph neural network cannot distinguish. Consider a collection of graphs G with n nodes consisting of isomorphism classes of disjoint union of cyclic graphs iEl Cmy- See Figure 12 for instance.
Σm;=n
The directed unfolding tree T. of depth at each node of the graph is isomorphic to directed 3 3-regular rooted tree of depth l. If the node attributes are constant, then Thcorem (3.3 implies that any graph neural networks cannot distinguish all such disjoint union of cyclic graphs.
im3
30

---

Published as a conference paper at ICLR 2023
Universal Cover
6 R"
Graph
O
Graph H
Graphs
Cycle Bases
Clique Adjacency Matrices
Identryy cycle bases
Add edges
(4
B
A
Figure 11: An illustration of Definition 4.2 and Theorem 4.3 The two connected graphs have identical associated universal covers, which implies that graph neural networks cannot distinguish the two graphs. Nevertheless, Cy2CGN is able to distinguish them by adding complete graphs from cycles these graphs, whose universal covers are not isomorphic. The incorporation of cycle bases of graphs to graph representations become feasible via admitting the clique adjacency matrices as inputs.
31

---

Published as a conference paper at ICLR 2023
Graphs (6)
Clique Adjacency Matrices (A₂)
New Universal Covers
Cy2c-GNN
Clique Adjacency Matrices (A,)
Graphs (G)
Cy2C-GNN
Figure 12: An illustration of Theorem 4.3 Each of the following pair graphs with non-isomorphic cyclic subgraphs have identical associated universal covers, which implies that graph neural networks cannot distinguish the two graphs. Nevertheless, Cy2C-GNN is able to distinguish them by adding complete graphs from eycles of these graphs, whose universal covers not isomorphic.
32

---

Published as a conference paper at ICLR 2023
By substituting every disjoint cyclic graphs with complete graphs, however, obtain non-isomorphic classes of disjoint unions of universal covers. Therefore, even if the node attributes are constant, Theorem 3.3 implies that Cy2C-GNN can distniguish all such disjoint union of cyclic graphs.
Remark A.37. One immediate result from Theorem 4.3 is that Cy2C-GNN can distinguish non- isomorphism classes of graphs that 1,2,and 3-WL tests cannot distinguish. The proof of this claim originates from the adaptation of the well-known arguments presented in Bodnar et al. 2021b a). The Rook's 4 4 graph and the Shrikhande graph, which constitutes the only two elements of the strongly regular graphs in family (,,,,,,,,, are not isomorphic because the Shrikhande graph contains a chordless cyclic subgraph of size 5, whereas Rook's 4 X graph does not, see for instance Table 4 of Bodnar et al. (2021a). Theorem 4.3 hence implies that Cy2C-GNN can distinguish these two graphs by incorporating the cycle basis of the Shrikhande graph which contains a chordless cyclic subgraph of size 5, and that of the Rook's s 4 x 4 graph which does not contain such subgraphs.
We note that contemporary techniques which are known to be able to classify classes of graphs that 1,2 and 3-WL tests cannot possess capability in counting the number of nodes of given cyclic or clique subgraphs of G. Such results include Proposition 25 Bodnar et al. (202Ta), Proposition 2 of You et al. 202T). Theorem 8 of Bodnar et al. (2021b), and Proposition 3.4 of Bouritsas et al. (2022).
While these previously studied GNNs and Cy2C-GNN share common objective in distinguishing cyclic substructures of graphs, the inherent algorithm which manifests such objectives are different. To elaborate, Boodnar et al. (2021a) and Bouritsas et al. (0022) propose gluing higher dimensional cells or complexes while preserving the 1-skeleton structure of a given graph. You et al. (2021) proposes perturbing the feature of a designated node, which allows GNNs with sufficiently large number of layers distinguish cyclic substructures of graphs. Cy2C-GNN, on the other hand, circumvents utilizing higher dimensional cells or perturbing the given node attributes by adding suitable edges, or transforming the 1-skeleton structure of a graph. This procedure allows wide range of classes of graphs, in particular those with varying cyclic structures, with isomorphic universal covers to attain additional non-isomorphic universal covers. Because neighborhood aggregating layers are effective in distinguishing isomorphism classes of graphs up to their universal covers, Cy2C-GNN allows conventional GNNs detect such cyclic structures with a single neighborhood aggregating layer utilizing clique adjacency matrices.
A.6 COMPUTATIONAL COMPLEXITY
The computation complexity of Cy2C-GNN method consists of two parts: An extraction algorithm for extracting clique adjacency matrix from general description of graph: And the GNN model with clique adjacency matrix. The extraction algorithm is equivalent to constructing basis of cycles of the first homology group of a given graph G. The classical algorithm proposed by Paton proves that the time complexity of finding cycle basis of finite graph with n nodes is given by O(n)) for 2 < S 3 3[aaton| (169)). For random graphs with n nodes and density 0.5, the time complexity of Paton's 's algorithm is equal (nn)). Indeed, as shown in Table 3 in Appendix B, the average sizes of cycle bases BG for benchmark graph datasets are bounded above by their average numbers of edges. There are other more efficient algorithms than Paton's 's algorithm in obtaining cycle basis of a finite graph with n nodes. One may resort to using persistent homological techniques to construet persistent diagrams associated to filtrations of a finite graph G with m edges, whose time complexity is of order O (m))(m) (m Horn et al. (202T). The function (m) is the inverse Ackermann function, which grows at an extremely slow rate in terms of m. In fact, it grows at such slow rate that we may even assume without loss of generality that ((m) is constant in terms of m for any practical choice of the number of edges m.
The latter architectural component of the Cy2C-GNN algorithm shares equivalent time complexities to conventional GNNs, corresponding to 0(mc + Im1), where is the number of layers, mc is the number of edges of graph associated to the clique adjacency matrix Ac, and m is the number of edges of G. We recall that the Euler characteristic formula implies
#Bg = #E(G) #V(G)* +1
for any connected graph G. Hence, the time complexity of the Cy2C-GNN method is practically equivalent to O(m), given that the number of layers is fixed and the number of nodes consisting each cycle bases is bounded.
33

---

Published as a conference paper at ICLR 2023
We established that as long one chooses sufficiently efficient algorithm for computing cycle bases of graphs, the time complexity to represent graphs with n nodes and m edges using Cy2C-GNN is equivalent to (m)). Such complexity is equivalent to that of conventional GNNs, and more efficient than persistent homological techniques, while managing to capture cyclic substructures of graph data sets. The time complexity of constructing persistence diagrams given an arbitrary height function over the set of nodes and edges of a graph G is equal to (n22",, where w is positive number such that (n))) is the time complexity required for multiplying tWO n n matrix Milosavljevié al. 1211 We note that the time complexity of conventional matrix multiplication algorithm is given by O(n" with the best asymptotic complexity running in O(n") with w 2.37 Alman Williams (202 As for persistent homological techniques obtained from predetermined height function over G, there are classes of height functions whose time complexity to construct persistence diagrams is equal to O(n" logn), see for instance the work by Rieck et al Rieck et al. (2019). Nevertheless, such persistent homological techniques may not necessarily distinguish all isomorphism classes of graphs, as carefully studied in the work by Horn et al Horn et al. (202I). For example, consider the height function h G > IR over a graph G with continuous node attributes fa V(G) - R& defined as
{ (h(v) for E V(G) (n(e) = (Va(v) - Sa(w)ll + T for e (v, E E(G)
(70)
where || ||p is the dip-distance defined over R* and r 0 is a positive bias term. Let G and H be two graphs as shown in Figure 4 Then one may observe that there exists a bijection between the zeroth dimensional persistence diagrams (and first dimensional persistence diagrams, respectively) obtained from filtrations of G and H with respect to the height function h.
B IMPLEMENTATION
The experiments were run on cloud provider, comprising of 16 physical cores (Intel Xeon Processor (Skylake, IBRS) CPU processor @ 20GGz) with 2 NVIDIA Quadro RTX 6000 GPUs.
B. EXPERIMENTAL SETUP
Dataset We perform graph classification on the 3 bioinformatics(DD, PROTEINS(FULL), EN-
ZYMES), social network datasets (COLLAB, IMDB-B, REDDIT-B ). small molecules datasets (
MUTAG, NCII, NC1109) ), 3 datasets with edge features (BZR-MD, COX2-MD, PTC-MR) and 4
large datasets (REDDIT-M-SK. MOLHIV, MOLTOX21, MOLTOXCAST) from TU datasets Morris
et al. 2020) which are available in
library FFy & Lenssen (2019) and Open
Graph Benchmark datasets Hu et al. (022I). We use one-hot encoding for discrete node features and normalize the continuous node features before using GNNs. We make initial node features for the social dataset by utilizing one-hot encoding of node degrees. The details of statistical properties of benchmark data sets summarized in Table 3 and 4 For ablataion study, we perform ablation study by utilizing the "CYCLES" and "NECKLACES" synthetic datasets from Horn et al. (021).
Models We use three baseline models to compare the proposed methods comprised of GCN, GAT, and GIN. The hidden dimension of each message passing layer is uniformly given by 136. The number of heads in GAT is equal 8, and each hidden size equal to 17 for every benchmark dataset. For implementing GCN and GAT, the alement-wise mean pooling layer is used for constructing the outputs of the final message passing layer. We use classifier that consists of three MLPs for classifying graph data sets. In the case of GIN, each layer passes the hidden attributes through the element-wise sum pooling. Furthermore, summed graph representations of each layer are also summed after passing MLPs to obtain the entire graph representation.
Cy2C-GNNs share identical architectural structures to GCN, GAT, and GIN, except for the additional layer for clique adjacency matrix and the dimensions of the hidden state at the first MLP in the classifier. All baseline models and Cy2C-GNNs include batch normalization Toffe & Szegedy (2015) and residual connection He et al. (2016). The hyperparameters of Cy2C-GNNs are optimized with hidden dimensions from 32 to 256, weight decay from 0.0 to 0.01, the number of message passing layer from 1 to 5, initial dropout rate from 0 to 0.8, dropout rate of message passing layer from 0 to 0.8 and the number of layer in classifier from 1 to 3. In case of large data sets, we implement Cy2C-GNI GNN models whose number of layers are between 1 and 7. We also consider both methods for classifier
34

---

Published as a conference paper at ICLR 2023
Table 3: summary of statistics of bioinformaties, social network graph and small molecules datasets. Cells notated as "-" indicate graph data set which do not have or use features in this paper. Numbers in parentheses are dimension features. The term "Average # HI Cycles" indicates the average size of the cycle bases of graphs. The term "Average Magnitude # Cycles" denotes the average number of nodes present in a cyclic subgraph of graph.
BIDINOOMENTICS PROTEINS(FULLD
SOCIAL NETWORK IMDR-8
SMALL MOLBEULES NCTI
DATA SETS
D&D
ENZYMES
COLLAR AB
REDDIT-R
MUTAG
NCT100
2000
CLASS
AVERAGE NODES
284.32
39.06
32.63
74.49
19.77
429.63
17.93
29.57
29.58
AVERAGE EDOOS
715.06
72.82
62.14
2457.78
96.53
497.75
19.99
32.30
32.13
AVEILAGI CYCLES
432.36
34.84
30.75
2563.72
77.76
70.61
2.86
3.62
3.64
AVER AGE MAGNITUDE CYCLES
7.21
3.72
3.69
3.04
3.00
5.412
6.24
5.94
5.92
GRAPE
0
3
67
Table 4: A summary of statistics for graph classification datasets with edge features and large datasets including OGB. Numbers in parentheses are dimension of features. The term "Average HI Cycles" indicates the average size of the cycle bases of graphs. The term "Average Magnitude # Cycles denotes the average number of nodes present in a cyclic subgraph of graph.
DATASETS WITH EDGE FEATURES
LARGE DATASETS
DATA GRRAPIS
BZR-MD
COX2-MD
PTC-MR
REDDIT-M-SK
MOLHIV
MOLTOX21
MOLTOXCAST
306
303
344
4999
41,127
7,831
8,576
AVERAGE NODES
21.30
26.28
14.29
508.52
25.5
18.6
18.8
AVERAGE # FIDGRS
225.06
335.
14.69
594.87
27.5
19.3
19.3
AVERAGE CYCLES
204.75
309.84
1.40
90.08
3.03
1.75
1.75
AVERAGE MAGNITUDE CYCLES
3.0
4.30
7.73
5.65
GRAPH WITHOUT CYCLES
0
0
90
51
1582
1781
1956
NODE PEATURES (DIM)
with last layers outputs and with concatenated outputs of all layers. For classifying BZR-MD and COX2-MD datasets, we require that Cy2C-GNNs incorporate edge attributes respective data sets. For classifying OGB and PTC-MR data sets, however, we implement both cases where Cy2C-GNNs incorporate the given edge features or not.
Graph classification For classifying graph data sets, we adapted stratified 10-fold cross-validations to evaluate the performance of baseline models and Cy2C-GNNs, while preserving the percentage of the train, validation, and test samples for each class. Theses models are optimized by Adam optimizer Kingma& & Ba (2014) with initial learning rate from 10-4 4 to 10-3, We use for learning rate scheduler Pytorch library, which multiplies the learning rate by 0.8 when validation loss does not decrease with the patience of 25. Additionally. we use the early stopping criterion when validation loss does not decrease during the 100 epochs. Training sequences are stopped when the learning rate becomes below the minimum learning rate of 1 10 In case of OGB datasets, we perform overall experiments 10 times with original training/validationnnes dataset splits Hu al. (2020) and batch size is set to 128. Cy2C-GNN optimizer Kingma & Ba (2014). ReduceLLROnPatear are used, which multiplies the learning rate by 0.8 whenever the validation accuracy does not increase during the 25 epochs, along with the stopping criterion of patience of 100.
also optimized by Adam
B.2 DETAILS OF DATASET
Tables and 2 summarizes the statistical properties of benchmark data sets utilized in demonstrating the effectiveness of the proposed model.
The synthetic datasets "CYCLE" and "NECKLACE" are generated using the github repository provided from Homm et al. (2021). Each dataset consists of 1000 synthetically generated graphs with two distinct cyclic substructures, each class of which contains exactly half (for instance 500 graphs out of 1000 graphs) out of all generated graphs. The objective is verify whether the proposed GNN can
35

---

Published as a conference paper at ICLR 2023
Figure 13: An example of CSL data Murphy et al. (2019) with skip length 2 and WL test and Conventional GNNs cannot distinguish these graphs.
accurately implement binary classification by detecting differences in the proposed cyclic structures. The "CYCLE" dataset consists of either a connected cyclic graph with large number of nodes or a disconnected cyclic graphs with smaller number of nodes. The "NECKLACE" dataset consists of two classes of graphs BG satisfying |Bal = 2 such that either the two elements C2, C2 E Be have a non-trivial intersection are disjoint. graphical description of the datasets be found in Figure of Horn et al. 2021).
B.3 DETAILS IMPLEMENTATION
Extraction algorithm We used the following extraction algorithm to construct the clique adjacency matrix. First, we use the function cycle_ _aaiss Paton (1969) from NetworkX library [Hagberg et al. (2008) which returns a list of cycle basis elements of graph. The node sets of cycle basis used for making new edges that transform each cycle to a clique. Then, the clique adjacency matrix is obtained by masking edges that do not include any cycle and adding new edges from the adjacency matrix. We refer to Figure to to recall how the clique adjacency matrix is constructed.
Running time analysis We performed additional experiments measuring the running time of the baseline GNNs and Cy2C-GNNs, including the pre- precpeocessing steps required for Cy2C-GNNs. such as constructing clique adjacency matrices and detecting cycle bases. Since the REDDIT-M-5K dataset has the highest average number of nodes and edges in our benchmark datasets, we selected the dataset to compare additional experiments. First, the CPU's running time for preprocessing steps takes an average of 0)49 seconds for each graph and 2461 ,44 seconds for all graphs in the dataset. For a fair comparison, we evaluate the GPU's running time of baseline GCNs and Cy2C-GCNs with 128 hidden dimensions in the train sequence. We perform five iterations of implementing GCNs and Cy2C-GCNs with identical hyperparameters, and measure the average time spent for reaching the same number of epochs analyze additional computational costs derived from the clique adjacency matrix. Sssows the running time of baseline GCNs and Cy2C- with different numbers of layers. Cy2C-GNNs with single message passing layer takes approximately 1.5 times more time to represent graphs compared to baseline GCNs with the same number of layers. Nevertheless, observe that inereasing the number of layers can significantly decrease the relative computational costs of Cy2C-GNNs to baseline GCNs. This observation is suggested from the fact that Cy2C-GNNs with five message passing layers takes approximately 1.2 times more time to represent graphs compared to baseline GCNs with identical architectural structures, a marked improvement in relative running time compared to the case where Cy2C-GNNs had a single message passing layer.
The running time of Cy2C-GNNs, including preprocessing steps, significantly longer than that of the bascline GNNs. However, since preprocessing steps need to be performed only once for the first time and can parallelized, we can claim that Cy2C-GNNs have comparable computational complexity to baseline GCNs.
Additional ablation studies We performed an additional ablation study to empirically shows the expressive power of Cy2C-GNNs by comparing results of conventional GNNs, Relational Pool- ing GIN(RP-GIN) Murphy et al, (2019) and our method obtained from Circular Skip Link(CSL) dataset Murphy et al. (2019) Figure 13 shows the example of CSL. data that have different skip length
36

---

Published as a conference paper at ICLR 2023
Table Comparison of running time (in seconds) at 50, 100 and 150 epoch obtained from REDDIT- M-5K.
BASELINE
GCN-N
EPOCH
N=1
N=2
N=3
N=4
N=5
50
30.6
37.4
44.7
52.1
59.4
100
60.0
74.8
89.4
103.8
119.5
150
89.0
112.7
133.7
156.2
179.1
CY2C-GCN-L
EPOCH
N=1
N=2
N=3
N=4
N=5
50
43.2
50.1
58.4
65.4
72.5
100
85.7
100.6
115.8
131.3
145.4
150
129.2
150.7
173.3
196.7
217.8
Table 6: Classification resutls obtained from CSL dataset. Classification methods with grey color text are cited from results obtained from pre-existing publication MMrrpyy et al. (2019). The term "Baseline GCN-N" denotes conventional GCNs with N layers, where N takes any value in {1,2,3, 4,
CSL DATASET
MODEL
ACCURACY
MAX
MIN
GIN
10=0.0
10
10
RP-GIN
37.6+12.9
53.3
10
BASELINE GCN-N
10=0.0
10
CY2C-GCN-1
91.3+1.6
93.3
90
R. CSL dataset consists of graphs where R E (2,3,4,5, 6,9, 11. 12, 13, 16) with 41 nodes that have same node features. evaluate baseline GCNs and Cy2C-GCN-1 with 5-fold cross-vale validations while preserving the percentage of the train and validation in reference Murphy et al. (209)). The hidden dimension of each message passing layer is fixed by 16, and the batch size is set to 16. Bascline GCNs and Cy2C-GCN-
optimized by Adam optimizer Kingma & Ba (0044) with learning rate from 1 x 10 Since only the train dataset and validation dataset exist, we choose the best validation accuracy in terms of the accuracy of the train dataset. The results are listed in T The results of baseline GCNs is consistent with the fact that the conventional GNNs cannot distinguish graphs in CSL dataset
al. (2019). Cy2C-GCN-1 not only distinguishes graphs in CSL dataset, but also shows much higher performance than the RP-GIN.
Murphy Murphy
37


Reviews:
[{"review_id": "i82whR14Nc6", "reviewer": "Reviewer_L1b5", "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 proposes a new graph neural network architecture termed Cycle to Clique Graph Neural Network (Cy2C-GNN). The new architecture is simple in that it just adds a separate layer in standard graph neural networks, and thus it maintains the efficiency of simple GNNs such as GCN; at the same time, the new architecture is based on graph theoretic considerations and is provably more powerful than standard GNNs at distinguishing certain isomorphism classes of graphs. The authors also empirically demonstrate that Cy2C-GNN can efficiently and reliably represent cyclic structures of graph datasets. Over a range of benchmark datasets Cy2C-GNN achieves superior or comparable graph classification performance than the current state-of-the-art methods.", "summary_of_the_review": "The paper proposes a simple and novel graph neural network architecture based on universal covering graphs. The new architecture is backed by theoretical insights and also it is shown empirically to achieve state-of-the-art graph classification performance. Even though I think the empirical evaluations are not good enough, overall the strengths of this paper oversights its weaknesses.", "strength_and_weaknesses": "The paper is well motivated and nicely written. The authors provide solid theoretical justifications for the proposed Cy2C-GNN architecture. I liked the fact that this architecture is provably more powerful and simple at the same time, which makes it very accessible to practitioners. I also liked that the authors discuss the limitations of the architecture in the conclusion.\n\nThe weak part of this paper is the empirical evaluations. It seems that the authors are comparing the best performance between baseline models and Cy2C-GNN models. Based on the results reported in Table 1 and Table 2, it is difficult to understand the effect of the additional neighborhood aggregation layer that uses the clique adjacency matrix. For example, for PROTEINS(FULL) in Table 1, the reported baseline GNN is GAT-3 whereas the reported Cy2C-GNN is Cy2C-GCN-4. Both methods use different GNN architecture and also different number of layers (please correct me if I am wrong), therefore it is difficult the understand what exactly had led to the performance gain. The results would be more informative if the authors report results in the setting where the only architectural difference is the additional clique averaging layer (and the final layer of course).", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "aYGfY8crok", "reviewer": "Reviewer_Qt5k", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "In this article, the authors propose to improve graph neural networks by characterizing and processing the graph cycles using universal covers, which is motivated by a characterization of the classes of graphs that usual graph neural nets can distinguish. More precisely, they provide a simple yet efficient procedure for turning cycles into cliques and for processing clique adjacency matrices with new graph neural network layer combined with standard aggregation schemes. They finally show improvements over competitors over several real-world data sets. ", "summary_of_the_review": "Overall, the paper looks good to me, even though I am no expert in graph neural networks.\n", "strength_and_weaknesses": "Strengths:\n---The paper is well written and easy to follow\n---The experiments are quite exhaustive\n---To my knowledge, Theorem 3.3 is new and interesting \n\nWeaknesses:\n---The method sounds a bit complicated. It would be nice to better motivate the use of universal covers: as far as I understand, extended persistent homology would be enough to detect and process such cycles in separate layers. Thus, it would be nice to either discuss or compare more to this alternative.\n---In terms of architecture design, the proposed neural net seems a bit incremental", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Gnoop5njfx", "reviewer": "Reviewer_KiJD", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The main contribution of this paper is Cy2C-GNN, a model that can distinguish pairs of isomorphic graphs that 1-, 2- and 3-WL tests cannot. The proposed approach identifies the cycle basis of the graph and then constructs complete subgraphs consisting of the nodes of each basis element. The clique adjacency matrix is created from these subgraphs. Then, the model produces some features by performing a neighborhood aggregation step using the clique adjacency matrix and these features are concatenated with features emerging from multiple standard neighborhood aggregation steps. The proposed model is evaluated on standard graph classification datasets where it achieves competitive performance with state-of-the-art methods.", "summary_of_the_review": "In my view, the paper seems to be proposing an interesting contribution for the graph representation learning community. The quality of the paper is good, and a novel theoretical results is presented. The proposed method is simple and it seems to perform well on standard datasets. However, I have some concerns mainly with the clarity of the paper, the motivation behind some parts of the method, the significance of the theoretical result, and the empirical evaluation.", "strength_and_weaknesses": "Strengths:\n\n- The proposed method is relatively simple, but still it is more powerful than several standard GNNs since it can distinguish graphs that WL and its variants cannot.\n\n- The proposed approach seems to perform relatively well on the considered graph classification datasets. It outperforms all the baselines on 8 out of the 16 datasets.\n\nWeaknesses:\n\n- Since the authors claim that the Cy2C-GNN model can distinguish graphs that standard or even more powerful GNNs cannot distinguish, one would expect the authors to empirically verify that. There exist datasets that are created to measure the expressiveness of GNNs such as the Circular Skip Link dataset [1], and the EXP and CEXP datasets [2]. I would suggest the authors also evaluate the proposed model on these or other similar datasets. \n\n- Even though the underlying idea is relatively simple, the paper is difficult to follow and contains mathematical notation that takes quite a bit of time to parse. I would thus recommend the authors to try and simplify the presentation. \n\n- The main theoretical result (Theorem 4.3) shows that if one graph has a chordless cyclic element in its basis of different length than all the chordless cyclic elements of the basis of another graph, then the proposed method can distinguish the two graphs. Can all those graphs also be distinguished by some higher-order variant of WL (i.e., the $k$-WL algorithm for some $k>1$)? Are there any real-world problems which require such graphs to be mapped to different embeddings? What is also the intuition behind constructing a complete subgraph consisting of the nodes of a cyclic element?\n \n- The authors discuss in details the computational complexity of the proposed method. However, they do not provide any empirical results. I would suggest the authors also measure the running time of the method (including preprocessing steps such as computing the set of cycles that form a basis for cycles of each input graph). Since the authors have evaluated Cy2C-GNN on REDDIT-M-5K, which contains large graphs, I would guess that the running time is not prohibitive.\n\n- The writing is not very clear. There are several grammatical and syntactic mistakes, while notation is not always clearly defined (for instance, in Lemma 4.1, what do symbols $\\cong$ and $\\not \\cong$ denote?). Therefore, the considered manuscript lacks clarity and I suggest the authors work on improving that.\\\npage 1: \"The graph data set The adjacency matrix\" --> The sentence does not make sense\\\npage 5: \"to each nodes\" --> \"to each node\"\\\npage 7: \"3 social network dataset\" --> \"3 social network datasets\"\\\npage 7: \"3 small molecules\" --> \"3 small molecular datasets\"\n\n- Are there any results that link universal covers with stable colorings that emerge from the WL algorithm?\n\n- Tables 1 and 2 have too small font size, and are not readable when printed. Please increase the font size.\n\n[1] Murphy, R., Srinivasan, B., Rao, V., & Ribeiro, B., \"Relational pooling for graph representations\", In International Conference on Machine Learning, pp. 4663-4673, 2019.\\\n[2] Abboud, R., Ceylan, I. I., Grohe, M., & Lukasiewicz, T., \"The Surprising Power of Graph Neural Networks with Random Node Initialization\", In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pp. 2112-2118, 2021.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster