Counting Graph Substructures with Graph Neural Networks
Authors: Charilaos Kanatsoulis
Alejandro Ribeiro
Venue: ICLR 2024 poster (2024)
Keywords: graph neural networks
expressive power
representation learning
subgraph isomorphism
cliques
cycles
motifs
substructures
count
message-passing
Primary area: learning on graphs and other geometries & topologies
TL;DR: This paper studies the ability of message-passing graph neural networks to count graph substructures.

Abstract: Graph Neural Networks (GNNs) are powerful representation learning tools that have achieved remarkable performance in various downstream tasks. However, there are still open questions regarding their ability to count and list substructures, which play a crucial role in biological and social networks. In this work, we fill this gap and characterize the representation {and generalization} power of GNNs in terms of their ability to produce powerful representations that count substructures. In particular, we study the message-passing operations of GNNs with random node input in a novel fashion, and show how they can produce equivariant representations that are associated with high-order statistical moments. Using these representations, we prove that GNNs can learn how to count cycles, {cliques}, quasi-cliques, and the number of connected components in a graph. We also provide new insights into the generalization capacity of GNNs. Our analysis is constructive and enables the design of a generic GNN architecture that shows remarkable performance in four distinct tasks: cycle detection, cycle counting, graph classification, and molecular property prediction.

Published as a conference paper at ICLR 2024
COUNTING GRAPH SUBSTRUCTURES WITH GRAPH NEURAL NETWORKS
Charilaos I. Kanatsoulis
Alejandro Ribeiro
Electrical and Systems Engineering University of Pennsylvania
Electrical and Systems Engineering University of Pennsylvania Philadelphia, PA 19104 ar rribeirodee weeerroeseas.co upenn, edu
Philadelphia, PA 19104
kanacêseas upenn,
ueeeeessssuuuuneeeeeee edu
ABSTRACT
Graph Neural Networks (GNNs) are powerful representation learning tools that have achieved remarkable performance in various downstream tasks. However, there are still open questions regarding their ability count and list substructures, which play a crucial role in biological and social networks. In this work, we fill this gap and characterize the representation and generalization power of GNNs in terms of their ability to produce powerful representations that count substructures. In particular, we study the message- paassing operations of GNNs with random node input in a novel fashion, and show how they can produce equivariant representations that are associated with high-order statistical moments. Using these representations, we prove that GNNs can learn how to count cycles, cliques, quasi-cliques, and the number of connected components the generalization capacity of GNNs. Our analysis is constructive and enables the design of generic GNN architecture that shows remarkable performance in four distinct tasks: cycle detection, cycle counting, graph classification, and molecular property prediction.
graph. We also provide new insights into
INTRODUCTION
Graph Neural Networks (GNNs) are deep learning architectures that learn powerful representations of graphs and graph signals. GNNs have shown remarkable performance across various domains, such as biology and drug discovery Gainza et al. (2020); Strokaach et al. (2020)00))))) Jiang et al. (202T), quantum chemistry Gilmer al. (0017). roboties Li et al. (2020): Hadou et al. (2022). social networks and recommender systems Ying et al. (2018). Their success can be attributed to their fundamental and favorable properties, including permutation invariance-equivariaan Maron et al. (2018), stability
to deformations Gama et al. (2020), and transferability Ruiz et al. (2020); Levie et al. (2021).
Since GNNs perform representation learning on graph structures and graph data, a lot of research has been conducted to answer how expressive GNN representations are. A major line of research studies the ability of GNNs to perform graph isomorphism. In particular, Morris et al. (2019): Xu et al. (2019) compare the representation power of GNNs to that of the Weisfeiler- Lehman (WL) test Weisfeiler & Leman 1968). where Kanatsoulis & Ribeiro (2022) study the expressivity of GNNs from a spectral perspective. Although graph isomorphism an important and necessary expressivity test, it is not sufficient to fully characterize the representation power of these architectures. Consequently, there has been increased interest in approaching GNN expressivity via counting substructures Arvind et al.) (2000): Chen et al. (2020) or solving graph bi-connectivity Zhang et al. (2023). In this paper, we revisit the representation power of GNNs terms of counting important substructures of the graph. Additionally, we investigate their ability to generalize and transfer structural properties to arbitrary graph families. Our work is motivated by the following research question:
Problem Definition 1.1 Given a graph G without additional features; can a message-passing GNN learn to generate permutation equivariant representations that count and list graph substructures?
Problem I.I studies the ability of a pessaae--pasiing GNN to produce substructure informative representations when the input X is completely uninformative. This is interesting for two reasons.

---

Published as a conference paper at ICLR 2024
First, it provides a theoretical measure of the representation power of GNNs. Second, it has strong practical component, as counting and listing graph substructures, also known as subgraphs, motifs, and graphlets, is pivotal in a plethora of real-world tasks. In molecular chemistry for instance the bonds between atoms or functional groups, form cycles (rings) that are indicative of a molecule's properties and can be utilized generate molecular fingerprints Morgan Morgaan (T965); [Alon al. (2008); Rahman et al.] (2009); O O'Boyle& & Sayle| (2016). Cliques and quasi-cliques, on the other hand, characterize protein complexes in Protein-Protein Interaction networks and community structure in social networks Girvan& & Newman (2002); Jiang et al. (2010): Fox et al. (2020).
In this work, we give an affirmative answer to the Problem I.] and analyze the representation power of GNNs in terms of their ability to count and list cycles, cliques, quasi-cliques, and connected components. To this end, we consider a standard GNN architecture, that performs local message- passing operations, combined with normalization layers. Our analysis employs tools from tensor algebra and stochastic processes to characterize the output of the GNN, when the input a random vector. We show that a suitable choice of activation and normalization functions can generate equivariant node representations, which capture the statistical moments of the GNN output distribution. Additionally, we derive deterministic, closed-form expression for the GNN output and provide rigorous proof that accurately lists all the triangles, and counts cycles ranging from size 3 to 8, n-nde cliques, quasi-cliques, as well as connected components within the graph.
Our results also offer novel insights into the generalization properties of message-passing GNNs. Specifically, we demonstrate that GNN can learn to count important substructures, not only within the family of graphs observed during training but also for any arbitrary graph. This analysis is constructive and enables the development of generic architecture that exhibits success across various tasks. Extensive numerical tests validate the effectiveness of the proposed approach across four distinct tasks: cycle detection, cycle counting, graph classification, and molecular property prediction. Our contribution is summarized as follows:
(C1) We characterize the representation and generalization power of message-passing GNNs by assessing their ability to count and list important graph substructures.
(C2) We propose a novel analysis of GNNs with random node inputs that unlocks the true potential of message-passing and enables them generate powerful equivariant representations that count or list cycles, quasi-cliques, and connected components within a graph.
(C3) We prove that the substructure counting ability of GNNs is generalizable and can transfer to arbitrary graphs that were not observed during training.
(C4) Our constructive analysis enables a generic architecture that is effective across different tasks.
Related work: There are three main lines of work that are closely related to our paper. The first by Xu et al. (2019): Morris et al. (2019); Arvind et al. (2020); Chen et al. (2020) establishes that message-passing GNNs with degree-related inputs are, at most, as powerful as the WL test, thus limiting their ability to count simple subgraphs as triangles. The second line of work (bbbud et al. (2021): Sato et al. 2022 addresses these limitations by employing random features as input to the GNN. This results in enhanced function approximation properties, but at the expense of permutation equivariance, which is fundamental in graph learning. Finally. Tahmasebi et al. (2020)
h You et al. | et al. (2022); Barceló et al. (2021); /eeilaaquu al. (2021): Zhang & Li (202));
Bouritsas
Zhao et al. (202)) directly augment GNNs with structural information to enhance their representation
power. A detailed discussion of prior work with additional references can be found in Appendix A
2 MESSAGE-PASSING GNNs
To begin our discussion consider graph G == (V,E), with a set of vertices V= (1...., "NI...,,,, N}. a set of edges & = {(v, ) and an adjacency matrix S (0. 1J The vertices (nodes) of the graph are often associated with graph signals &, E RD with D features, also known as node attributes.
In this paper, we study standard GNNs that perform local, sassage-passing operations. A message- passing GNN is cascade of layers and is usually defined by the following recursive formula:
x!! -1-1)) 20( (t-1) f(1-1) 1) (f af (I-1))) :
(1)
2

---

Published as a conference paper at ICLR 2024
where N (t) is the neighborhood of vertex v, i.e., E N (v) if and only if (u, v) E E. The function f()) aggregates information from the multiset of neighboring signals, whereas g()) combines the signal each vertex with the aggregated one from the neighboring vertices. Common choices for f()), gd) are the multi-layer perceptron (MLP), the linear function, and the summation function. When f(() the summation function, and 9d) is the multivariate linear function for I = I.... K 1
and the MLP followed by normalization for = K, the output of the K <tth layer is equivalent to the following expression (as shown in Appendix
K
)
Y = [x()]
Σ S* X A=
=
(2)
where X = (0) E N represents the signals of all vertices, H₂ E DxF are the trainable parameters, a is a point-wise nonlinear activation function, and p is normalization function, e.g., batch normalization or softmax. Note that the K-th layer is not necessarily the final one, i.e., Y can be used as an input to other layers defined in Unless noted otherwise the term GNN will refer to local, paassigg GNNs.
3 STUDYING GNNS WITH RANDOM INPUT
Throughout the rest of this paper, we will utilize tensor algebra, specifically the tensor mode product, the canonical polyadic decomposition (CPD) model, and the Tucker model. For a brief introduction, please refer to Appendix [C] and for a more comprehensive understanding of tensors, we recommend consulting Sidiropoulos et al. 20 Kolda & Bader (2009).
The goal of our paper is to answer the research question in 1.1 and characterize the expressive power of message-passing GNNs terms of counting important substructures of the graph. To that we study Equation 2 when the node input is random vector E R.V. Our work focuses on the ability of muessage-passinn GNN operations to generate expressive features, therefore the input æ should be completely uninformative, i.e., structure and identity agnostic. To ensure that æ = [x1, I2,... NN=" agnostic with respect the structure of the graph, we assume that
1,... ...... N independent random variables. To ensure that T;, = 1,.... N are identity agnostic, we assume that they are identically distributed and satisfy E [x,] the elements of æ are independent and identically distributed (i.i.d.), with joint characteristic function du (4.....,ty) I (eJt. jtz), and the moments of the joint distribution of æ satisfy:
E [-p]= = for 1..... .N, and p >2> 2 Z. Overall,
E [x]] = 0, E [x:: 1 I, E [ x] I. E E
L.
(3)
where is the outer product and I denotes super-diagonal tensor with all-one values, i.e.,
I [1,, f2,..., ig] = if 1, = i2 = ... in and I 11, i2. ág] = 0 otherwise. Note that E [a:] is an I-dimensional tensor (vector), E [wx" J = E x x] = is a 2-dimensional tensor (matrix),
and E wox x] = I, E [ x ... x = I are 3- and multi- dintiidimmnsonnal tensors respectively.
We process the input vector æ using 2 i.c., Y = = (Ek S shxxh? where h2 R represents set of F graph filters of the form:
K
S H (H)) y y=
where H (S) = >k such that they can instantiate moments of the distribution of z. As we see in the next section, the moments of can count some very important graph substructures.
o Sth To produce equivariant, deterministic node features we choose a
4 COUNTING GRAPH SUBSTRUCTURES WITH GNNS
In this section, show that appropriate choices a, p in generate equivariant node features that are associated with the moments of the distribution of z. We then analyze these moments and prove that they count cycles, quasi-eliques, and connected components in a graph. The proofs can be found in Appendices D to Results for counting cycles at the node level can be found in Appendix K
3

---

Published as a conference paper at ICLR 2024
4.1 SECOND ORDER MOMENT
First, we study 4 when is the elementwise square function and is the expectation operator. This architecture computes deterministic equivariant node features that measure the variance of z, i.e., = plo (z)] = I=2] Note that E [=] O, since E [a] = and æ; are linearly related. To analyze the output y we instantiate the covariance of x that takes the form:
zz
EE
S wxx
Σ
hmm Sm
Σ hm Sth H
where the last equality comes from the fact that H (S) 2k=0 St and E [xx"] I. Then:
y p (z)] = E [2²] diag (R [zz²]) (H 3 H (S))
(5)
where diag(A) (A) E R is the vector with the diagonal of A RNN O denotes the Hadamard (ele- mentwise) product operation, and the last equality comes from the following property, diag (AB)
(A ④ B) 1, for square matrices A, B. Expanding vields the following expression:
K
K
K
K
S
hmm Sm
hghin (st
ST = Σ humm (st
SSSS) 1.
=
7
k=0 m=
k,m
(6)
We leverage the expression o prove the following theorems.
Theorem 4.1 (Number of connected components) Given a set of graphs { there exists GNN defined in 7 or that counts the number of connected components of all {9i)
Theorem 4.2 (Cycles) There exists a GNN defined in 7 1or that counts the number of cycles with 3 to 5 nodes, of any graph.
Note that in Theorem 4.1 we prove that GNN is able to learn how to count the connected components of graphs that were observed during training. Theorem 4.2 one the other hand, proves that a GNN able to learn how to count the 3-,4-,5-node cycles of any graph. As result, Theorem 4.2 is stronger and also provides novel insights into the generalization ability of GNNs.
4.2 THIRD-ORDER MOMENT
Next, study 4 when is the elementwise cubic function and p the expectation operator. This architecture computes deterministic equivariant node features that measure the skewness of 2, i.e., y = p (=)] E [= To analyze the output y we instantiate the third-order moment of which is a super-symmetric third-order tensor and is defined as follows:
oz E x a X1 H (S) X2 ( X3 H (S).
(7)
where "X1, X2, denote the tensor mode products and multiply each column, and fiber of [ x o x with (S) respectively. Since [ x a œ L. takes the form:
E 220200 2] x1 H (S) H (S) X3 H (S) [ (5), H (S), H (S),,
(8)
where [H (S), H (S), ( Σ H (S) [. H (S) n H (S) [i denotes the CPD
model of E [ o o with factor matrices H (S). Then V1 takes the form:
y1 = p (=)) E [ superdiag (E [z z z)) (H (S) H (S) R H (S)) 1,
where superdiag (.) E N the superdiagonal the tensor and the last equality comes from the definition of the CPD model. Interestingly,
9 can be cast as follows:
K he.
K
y1-
him
Sm
hu.mm o STh 1. S
(10)
1=0
k.I.==D
Using the expression
10
prove in the Appendix the following theorems:
4

---

Published as a conference paper at ICLR 2024
Theorem 4.3 (6-node Cycles) There exists GNN defined in or that counts the number of 6-node cycles of any graph.
Theorem 4.4 (Quasi-cliques) There exists GNN defined in 2r that counts the number of 4-node and 5-node quasi-cliques (chordal cycles) of any graph.
Theorems and 4.4 indicate that y1 = [ is crucial in counting 6-node eycles and 4,5-node quasi-cliques. We can also linearly derive additional equivariant features, from the third moment tensor E [ o z|. that produce rich information about the graph. In particular, we can compute the following equivariant feature vector, which is essential in our proofs for 7-node cycles.
1/2 diag [E z] X3 12) diag (E [ o zo 1² =]) E [= (1"z)]
(11)
The expression in can be derived from when a is the elementwise square function, and p (-) (() @ (1"²) In that case, p defines a normalization layer that multiplies each datum in x² by
1s and measures the average of all data, After some algebraic manipulations that can be found in the Appendix the expression in II takes the form:
K
K
K Σ m==
K
1/2 =
Σ
S
Sy
S
Σ k,4.==0
hk...m (S* ④ (5S)) 1 1
(12)
1=0
4.3 FOURTH-ORDER MOMENT
Following the idea of the previous subsections, if a is the elementwise quartic function and p is the expectation, we can compute deterministic equivariant node features that measure the kurtosis of z.
K
y = E
hg.mmm (S
ST) 1.
(13)
Using 6,
12
13
we can derive the following theorem:
Theorem 4.5 (7-node Cycles) There exists a GNN defined in or that counts the number of 7-node cycles any graph.
Remark 4.6 Theorems 4.2
4.3
4.4 and a.3 prove the ability of a GNN to learn how to count the
substructures of any graph. This brings new insights into the generulization ability of GNNs.
HIGHER-ORDER MOMENTS AND MULTIPLE-LAYER ANALYSIS
In this section, generalize our analysis and study multi-layer message-passing GNN that computes higher-order moments. To this end, we present the following proposition.
Proposition 5.1 Consider pressage-passing GNN with layers, where the output of each layer is defined by 2 Let the input the GNN be random vector with moments in 3 and be the elementwise m th power, i.e., ai (-) (.) me for = =1, 1,..., Q. Also let (()) = (.) be the identity function the first
layers, and p (-) E (-) (1Tz)*m) sm only the I--th th layer. Then the
output Y 1y...... yrl E NxF, of this GNN, has a closed-form expression, defined by 14
yf
big
(S
Sth
(S
St
(S 10... 3 Si (14)
times
The number of multiplications L in 14 equal to the number of layers, the term (S 3 St) reflects the effect of the activation af-), and (Sim+11 C .... S 1) is affected by the choice of normalization p in the final layer. A schematic illustration of the considered architecture is presented in Fig. [I The module Ia consists of proper message gessagg-passsing operations, whereas the module [b consists of Hadamard products between adjacency powers and sparse matrix-vector multiplications. The computational complexity of our approach is analyzed in Appendix
5

---

Published as a conference paper at ICLR 2024
Σ 2u
(+
+[.1]
[ate-11 uFA
(a0- E )
(a) Dassage-passingg module with random input
Ni (89 .... Sh))..... 8... 8i+) (8 8 w))
Sondba -9
(b) Equivalent module
Figure 1: Moment- GNN modules
Remark 5.1 Modules Ta and Tb are equivalent and can be used interchangeably. Furthermore, Layer L in Proposition 5. or Fig. 7 need not need to be the final layer of the GNN architecture, can be followed by classical peessagge-asssine layers as defined in
The previous analysis can also be used to characterize the expressive power of the GNNs defined in or with respect to that of the folklore- Weisfeiler--Lhhee (FWL) test Cai et al. (1992,; Morris et al. (2019): Huang & Villar (02T).
Proposition 5.2 (Expressive Power) GNN defined by Proposition 5. followed by layers described in is strictly more powerful than the 1-FWL test, when f, 9 are injective functions.
6 LISTING AND COUNTING STRUCTURES BEYOND 2-FWL
In this section, we show how a message- message-passing GNN can generate equivariant features that list all the triangles of graph, count the number of node cliques. 8 nonode cycles, and therefore break the expressivity limits of the 2-FWL test. In particular, we consider again the GNN described in 2 which study with uninformative input described in Section derive the following theorem.
Theorem 6.1 (Listing Triangles) There exists a message seessage-passing GNN defined in 75
T ReLU (E [2020 2]) E (0, NNN1N
Sh
(15)
k=0 with an uninformative input x E N as described in Section 3 such that T ji.j.k] = if vertices j. form triangle and T [i.
0 otherwise.
we start with i.i.d. random node inputs, as in the previous analysis, and perform linear message-passeeee operations to compute informative node representations pointwise nonlinearity to z, we compute the three-way outer product z z o 2, and process it via the expectation and ReLUU. This enables the computation of tensor T. which encodes relations of node triplets and can list all the triangles the graph. After learning tensor T we can use to generate random vector o; with the following statistical moments:
Theorem 6.
Instead of applying
E [ = O, E [a, o D. v.. T.
(16)
We then perform similar analysis the one in Section and derive the following theorems.
Theorem 6.2 (4-node eliques) There exists a GNN defined 7 or or with random input ot defined in 16 that counts the number of 4-node cliques of any graph.
Theorem 6.3 (8-node Cycles) There exists GNN defined in or with random input æt defined in 16 that counts the number of 8-node cycles of any graph.
The details of the analysis can found Appendix Theorems
6.3 also prove that:
Proposition 6.1 (Expressive Power) There exist substructure fumiiiicturreumille with O (1). such that 2-FWL
no stronger than the GNN described in Theorems 6.2 6.3

---

Published as a conference paper at ICLR 2024
Table 1: Cycle detection accuracy for different GNN models
Cycle length
4
6
Graph size
12
20
28
36
20
31
42
56
28
50
66
72
Neural MP
98.5
93.2
91.8
86.7
98.7
95.5
92.9
88.0
98.0
96.3
92.5
89.1
GTN
98.3
97.1
95.0
93.0
99.5
97.2
95.1
92.7
98.5
98.8
90.8
92.55
GIN degree
99.3
98.2
97.3
96.7
99.2
97.1
97.1
94.5
99.3
98.7
95.4
GIN rand id
99.0
96.2
94.9
88.3
99.0
97.8
95.1
96.1
98.6
98.0
97.2
95.3
RP
100
99.9
99.7
97.7
99.0
97.4
92.1
84.1
99.2
97.1
92.8
80
PPGN
100
100
100
99.8
98.3
99.4
93.8
87.1
99.9
98.7
84,4
76.5
Ring-GNN
100
99.9
99.9
99.9
100
100
100
100
99.1
99.8
74.4
71.4
SMP
100
100
100
100
100
100
100
100
100
100
100
99.9
Moment-GMM GNN
100
99.9
100
99.9
100
100
100
100
100
100
100
100
Table 2: Cycle detection for in- and out-of-distribution graphs
Setting
In-distribution
Out-of-distribune
Cycle length Graph size
4
6
8
4
8
20
31
50
36
56
72
GIN
93.9
99.7
98.8
81.1
85,8
88.8
PPGN
99.9
99.5
98.7
50.0
50.0
50.0
Ri Rin--GN
100
100
99.9
50.0
50.0
o.o.m.
SMP
100
99.8
99.5
99.8
87.8
79.5
Moment
100
100
99.1
100
100
100
EXPERIMENTS
7.1 ARCHITECTURE
To implement the proposed approach, which we denote Moment we use the equivalent model, shown in Fig. Tb and Equation 14] The architecture consists of single Moment-GMD layer followed by 2 message-passing GIN layers Xu et al. (2019), defined by where f the summation function and g is an MLP. The Moment GNN uses the closed-form expression in 14 (or
more specifically i5 to compute the individual moments E' [z''], for m 2, 3, 4, 5. We use a set of Fm filters for the m-th moment, which outputs a feature representation Y T (P F.+F.+Fs) the is used as input to the GIN layers. The maximum and the number of layers hyperparameters.
7.2 CYCLE DETECTION
In the first set of experiments, we test the ability of the proposed approach to detect cycles of lengths 4, 6, and 8 in graphs of different sizes, which is binary graph classification task. The baselines used for comparison are: Neural message- message-passing network (Neural-Bn 1MM Gilmer et al. (2017), GIN Xu et al.) (2019), relational pooling GNN (RP) Murphy et al. (2019), provably powerful GNN (PPGN) Maron et al. 2019 Ring-GGi Chen et al. (2019), and structural pressage-passing GNN (SMP) Vignac al.
20200 Note that RP, PPCN, Ring-GNN, and SMP have significantly higher computational and memory complexity compared to Neural-MP, GIN, and Moment-GNt We also consider two variants of GIN, namely GIN + degree and GIN rand id. The input of GIN + degree is the one-hot encoding of the degree of each node, and the input of GIN rand id is a random vector that works as a unique identifier cach node Abboud et al. (202T): Sato et al. (021). The latter increases the expressiveness of GIN at the expense of permutation equivariance.
We use the dataset and procedure described Vignac et al. 2020 Each model is trained with 10,000 graphs for each cycle length. Testing is performed classification accuracy of the competing GNNs for different cycle lengths and graph sizes is presented in Table The results for the baselines are taken from Vignac al. (2020).
separate set of 10,000 graphs. The
hhttss//gihuuccom/MMmeetttCC bhaps://ggtuub.com//eiiggga////
7

---

Published as a conference paper at ICLR 2024
Table 3: Moment-GNN Performance in ZINC
(a) Regression MAE for counting cycles in ZINC
(b) Classification accuracy cycle detection in ZINC
Pentagon
Hexagon
Nonagon
Decagon
Training
Testing
Training
Testing
Training
Testing
Training
Testing
0.0012
0.0021
0.0057
0.0059
100
99.8
99.9
99.4
We observe that MoMent-GNN and SMP manage to perfectly detect the cycles of the graphs, whereas Neural-MP, RP, PPGN, Ring-GNN show weaker performance in larger graphs. It is no- table that Moment-Gai is message-passing GNN with lower complexity than RP, PPGN, RING-GNN, yet it yields enhanced performance. Furthermore, Moment markedly outper- forms GIN rand id, despite the initial resemblance in their utilizationn of random input for feeding a mressage-assingg GNN. This can be attributed to the fact that GIN + rand id gener- ates random realizations that serve as distinct identifiers, thus negating permutation equivariance. On the contrary, Moment.GNN employs stochastic approach of the random input and maintains permutation equivariance, which is a crucial property for this task.
In the second set of experiments, we examine the generalization and transferability of the different GNN models. In particular, we train the GNN architectures to detect the cycles small graphs and test detection performance with larger graphs. The classification accuracy for in in-distribution and distriibiiii graphs are presented in Table (o.o.m stands for out of memory). We observe that Moment GNNN is able perfectly detect the cycles in all settings. In particular, it achieves 20% improved accuracy compared to SMP in detecting out-of-distribution cycles of length 8 and 12% improvement in detecting outoof-distribution cycles of length 6. It also 50% better than PPGN and Ring- GNN. The result becomes even more impressive if we consider that SMP, PPGN and Riin-GGie GNN have higher computational and memory complexity compared to Moment GNNN
7.3 CYCLE COUNTING
We further test the ability of Moment GNN to count and detect cycles. To this end, we consider the ZINC dataset, which consists of 12, 000 molecular graphs of different chemical compounds] Irwin et al.
(2012); (Dwivedii et (2033). The cycle statistics of ZINC graphs are presented in Fig. [ We observe that the prevailing substructure is the hexagon (cyclohexane), which is expected since cyclohexanes the most common rings in molecular conformations. There also several pentagons and some single nonagons and decagons. The number of the remaining cycles is insignificant and it unlikely that a learning method will be able to count them. Following these observations we train Moment- - -GNN for 4 different tasks: i) count the number of pentagons, ii) count the number of hexagons, iii) detect nonagon, iv) detect a decagon. The first two are formulated as regression tasks with L, loss, and the last two as binary classification with logistic loss. The ground-truth number of cycles was computed using the subgraph isomorphism algorithm VF2 et al. (2004). For the detection tasks, we train and test with subset of the available graphs to ensure balanced classes.
The training and testing results for counting pentagons and hexagons are presented in Table 3a We observe that Moment-GNN is able to count these cycles with very high accuracy, the mean absolute error (MAE) for both tasks is in the order of 10 10-3 The results for nonagon and decagon detection presented in Table 3b KooenttGNN is able to achieve almost perfect training and testing classification accuracy for both cycle types, even though our theory does not guarantee that the proposed framework will be able to do so. Baseline comparisons can be found in Appendix MM]
7.4 LOGP PREDICTION
Next, we consider the task of predicting the penalized water-octanol partition coefficient-log! for molecules in the ZINC dataset. We use 10,000 of them for training. 1,000 for validation and 1,000 for testing. We use 5-layer message-passing GNN, where the first layer is Moment-GNN and the remaining are traditional normalization layers. We use 2 different implementations: one that does not process edge features and one that does. The feature dimension is set to 128. To assess the performance of our approach use the MAE between the estimated and the ground-truth logP of the testing set. We perform 10
pesssage-passing layers with skip connections followed by batch-
8

---

Published as a conference paper at ICLR 2024
Table 4: logP Prediction in ZINC
Table 5: Graph classification on REDDIT
GNN Model
MAE
MAE (EF)
Method
REDDIT-B
REDDIT-M
GraphSace
0.410 0.005
Wikernel
81.0
525
GXT
0.463 0.002
MoNet
0.407 = 0.007
GatedGON
0.422 0.006
0.363
0.009
PNA
0.320 0.032
0.188
0.004
WEGT.
92.9 1.9
55.4
DGN
0.219 + 0.0102
0.108
0.003
AW_
87.9 1
50.5
1.9
GNNML
41.3
HIMP
0,151 0.006
PATCHYSAN
8
49.1 0.7
SMP
0.219
0.138
RetGK
90.8 0.2
54.2 0.3
rand i
0.822
0.023
rand
57.0
GCN
0.469 = 0.002
GCN
5..0
20.0 0.0
GIN
0.251 = 0.011
0.209 0.018
GIN
91.8
56.9 2.1
GSM
eycles
0.115
with eliques
91.1
56.2
Moment-GNN
0.140 0.004
0.110 0.005
Moment-GNN
92.0 1.8
58.1 = 1.6
different runs and report the mean and standard deviation of the MAE the model that showed the best validation accuracy. We compare against various state-of-art baselines and report the results in Table 4 We observe that Moment GGNN achieves state-of-the- for molecular graphs, whereas GSN with cycle features is the second best. The performance of Noment-CND is achieved by pesssae--pasiigg operations without additional knowledge. This is contrary to GSN which precomputes substructure counts and fine tunes according them.
performance in predicting logP
7.5 GRAPII CLASSIFICATION
We also the performance of Moment GNN in classifying the graphs of REDDIT-B (2000 graphs. 2 classes, 429.6 Avgø nodes) and REDDIT-M (5000 graphs.5 classes, 508.5 Avgll nodes) datasets. Note that the majority of powerful GNNs cannot operate on these datasets due their large size. For example, GSN is only able to compute small number of structural features. To train the GNN models, the graphs are divided into 50-50 training testing splits and 10 different folds. Once again, we 5-layer GNN before but without skip-connections. The feature dimension is set to 64. Table 5 presents the mean and standard deviation of the classification accuracy over 10 folds. We report epoch that provided the best results among 350 epochs, which is the standard for this dataset.
From Table
we see that Moment-GN achieves state-of- the-art art performance for one more task. Note that Moment- GNN is generic architecture and there is need to predefine the structure type (e.g., cycle vs clique, induced vs non-induced) required for a specific task. Moment.GNN will decide the appropriate substructure type according the data and the task.
In summary, our findings highlight the remarkable performance of Woment-CNV across 4 different tasks. Tables [ 3a show that Moment GGNN can count and detect important substructures. Table that it can transfer to out-of-distribution and larger datasets, and Tables 4 that it is effective in down- stream tasks. Overall, the results provide concrete evidence of the generic nature of Moment -GNN, which overcomes the need for fine-tuning based on the most pivotal subgraph type for each specific task. Further experiments on the full ZINC dataset, along with additional baseline comparisons and discussions can be found in Appendix M
8 CONCLUSION
In this paper. we analyzed the representation power of local, message-passing GNNs with respect to their ability to generate representations that count certain important graph substructures. To do so we studied GNNs with random node inputs and showed that proper choices of activation and normalization functions enable the generation of powerful equivariant representations in the output. These representations are provably capable of counting cycles with 3 to 8 nodes, cliques with 3 to nodes, several quasi-cliques, and connected components within a graph. They can also generalize to arbitrary nnt-of-distributee graphs. Our analysis is constructive and designed generic architecture that demonstrated remarkable performance in the tasks of subgraph detection, subgraph counting, graph classification and logP prediction.

---

Published as a conference paper at ICLR 2024
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. IJCAI, 2021.
Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. Bioinformatics, 24(13): 1241-i249, 2008.
Vikraman Arvind, Frank Fuhlbrücck, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. Journal of Computer and System Sciences, 113:42-59, 2020.
Waiss Azizian et al. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2020.
Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning, pp. 599-608. PMLR, 2021.
Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. Advances in Neural Information Processing Systems, 34:25280-25293, 2021.
Sasmita Barik and Sane Umesh Reddy. Number cycles of small length in a graph. AKCE International Journal of Graphs and Combinatorics, pp. 1-14, 2023.
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference Machine Learning, pp. 748-758 PMLR, 2021.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2021.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34:2625-2640, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafciriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(1))657-66) 2022.
Xavier Bresson and Thomas Laurent. 1rXiv: 2017.
Residual gated graph convnets.
arXiv preprint
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound the number of variables for graph identifications. Combinatorica, 12(4):389-410, 1992.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 13:10383-10395, 2020.
Alan Chung, Amin Saberi, and Morgane Austern. Statistical guarantees for link prediction using graph neural networks. arXiv preprint arXiv:2402.02692, 2024.
Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub) graph isomorphism algo- rithm for matching large graphs. IEEE transactions on pattern analysis and machine intelligence, 167-137737 2004.
10

---

Published as a conference paper at ICLR 2024
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260-1322 2020.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
Matthias Fey, Jan- Man-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. arXiv preprint arXiv:2006. /2179, 2020.
Jacob Fox, Tim Roughgarden, C Seshadhri, Fan Wei, and Nicole Wein. Finding cliques in social networks: new distribution-fiee model. SIAM journal on computing, 49(2):4484464 2020.
Pablo Gainza, Freyr Sverrisson, Frederico Monti, Emanuele Rodola, D Boscaini, MM Bronstein, and BE Correia. Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning. Nature Methods, 17(2):184-19) 2020.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions on Signal Processing. 68:5680-5695, 2020.
Floris Geerts and Juan Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representutions, 2021.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1273-1272. PMLR, 2017.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99((2):8811-7826, 2002.
Lorenzo Giusti, Claudio Battiloro, Paolo Di Lorenzo, Stefania Sardellitti, and Sergio Barbarossa. Simplicial attention neural networks. CoRR, 2022.
Samar Hadou, Charilaos Kanatsoulis, and Alejandro Ribeiro. Space-time graph neural networks. In International Conference Learning Representutions, 2022.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Richard A Harshman and Margaret E Lundy. Parafac: Parallel factor analysis. Computational Statistics & Data Analysis, 18(1):39-72, 1994.
Ningyuan Teresa Huang and Soledad Villar. A short tutorial on the weisfeiler-lehman test and its variants. In ICASSP 202/-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5533-8537. IEEE, 2021.
John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: free tool to discover chemistry for biology. Journal of chemical information and modeling, 52(7): 1757-1768, 2012.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International conference on machine learning, pp. 2186-2195. PMLR, 2018
Chuntao Jiang, Frans Coenen, and Michele Zito. Finding frequent subgraphs in longitudinal social network data using a weighted graph mining approach. In Advanced Data Mining and Applica- lions: 6th International Conference, ADMA 2010, Chongging, China, November 19-21, 2010, Proceedings, Part pp. 405-416. Springer, 2010.
Dejun Jiang, Zhenxing Wu, Chang Yu Hsieh, Guangyong Chen, Ben Liao, Zhe Wang, Chao Shen, Dongsheng Cao, Jian Wu, and Tingjun Hou. Could graph neural networks learn better molecular representation for drug discovery? comparison study of descriptor-basee based and graph- based models. Journal of Cheminformatics, 13(1):12, dec 2021.

---

Published as a conference paper at ICLR 2024
Charilaos Kanatsoulis and Alejandro Ribeiro. Representation power of graph neural networks: Improved expressivity via algebraic analysis. arXiv preprint arXiv:2205.08801, 2022.
Thomas N Kipf and Max Welling. Semi- semi-suuereieed classification with graph convolutional networks.
arXiv preprint 1009.2660.022000 2016.
Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3): 455-500, 2009.
Soheil Kolouri, Navid Naderializadeh, Gustavo K Rohde, and Heiko Hoffmann. Wasserstein embed- ding for graph learning. In International Conference on Learning Representations, 2020.
Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research, 22(272): 1-59, 2021.
Qingbiao Li, Fernando Gama, Alejandro Ribeiro, and Amanda Prorok. Graph neural networks for decentralized multi-robot path planning. 2020 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1785-11792. IEEE, 2020.
Derek Lim, Joshua David Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. 2022.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2019.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Harry L Morgan. The generation of a unique machine description for chemical structures-a technique developed at chemical abstracts service. Journal of chemical documentation, 5(2):107-113, 1965.
Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: higher-order graph neural networks. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances Artificial Intelligence, pp. 4602-4609, 2019.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33: 21824-218 21840, 2020.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673, PMLR, 2019.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In International conference on machine learning, pp. 2014-2023. PMLR, 2016.
Noel M O' O'Boyle and Roger A Sayle. Comparing structural fingerprints using literature-based similarity benchmark. Journal of cheminformatics, 8(1):1-14, 2016.
SN Perepechko and AN Voropaev. The number of fixed length cycles in undirected graph. explicit formulae in case of small lengths. Mathematical Modeling and Computational Physics (MMCP2009), 148, 2009.
Syed Asad Rahman, Matthew Bashton, Gemma L Holliday, Rainer Schrader, and Janet M Thornton. Small molecule subgraph detector (smsd) toolkit. Journal of cheminformatics, 1:1-13, 2009.
12

---

Published as a conference paper at ICLR 2024
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-14515 2022.
Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferabilityy of graph neural networks, In Advances in Neural Information Processing Systems, volume 33, pp. 1702-1712, 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341. SIAM, 2021.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Nicholas D Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos E Papalexakis, and Christos Faloutsos. Tensor decomposition for signal processing and machine learning. IEEE Transactions Signal Processing, 65(13):3551-3582 2017.
Alexey Strokach, David Becerra, Carles Corbi-Verge Albert Perez-Riba, and Philip M. Kim. Fast and flexible protein design using deep graph neural networks. Cell Systems, 11(4):422441..ck October 2020.
Behrooz Tahmasebi, Derek Lim, and Stefanie Jegelka. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv preprint arXiv:2012.03/74, 2020.
Petar Veličković, Arantxa Casanova, Pietro Liò, Guillem Cucurull, Adriana Romero, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018- Conference Track Proceedings. International Conference Learning Representations, ICLR, 2018.
Clement Vignac. Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-pasaee paasggg.... Advances in neural information processing systems, 33:14143-11415, 2020.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https: //ppeneeiiew. net/ wtte://ooommmddysa..a..
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedingy of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 10:974-983. June 2018.
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity. arXiv preprint arXiv:2301.09500 2023.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Processing Systems, 14:15734-15744 2021.
Zhen Zhang, Mianzii Wang, Yijian Xiang, Yan Huang, and Arye Nehorai. Retgk: Graph kernels based on return probabilities of random walks. Advances Neural Information Processing Systems,
31, 2018.
13

---

Published as a conference paper at ICLR 2024
Lingxia Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations, 2021.
A RELATED WORK
The expressive power of Graph Neural Networks (GNNs) initially explored by Xu al. (2019) ;
Morris et al. (2019). These studied the expressive power of GNNs terms of performing the graph isomorphism test, i.c., distinguishing different graphs. They identified connection between the Weisfeiler-Lehmal (WL) test Weisfeiler & Leman (1968) and the message-passian operations in GNNs. Using this connection they proved that GNNs with degree-related inputs are, at most, as powerful as the WL test. Arvind et al. (2020); Chen et al. (2020) extended these results to the task of substructure counting, and showed that GNNs with degree-related inputs cannot count important substructures such as triangles.
Expanding on these findings, several works Maron et al. (2018) ) Murphy et al. (2019); Azizian et al. (020)][Morris et al. (2020): [Geerts & Reutter [2021); Giusti et al. (2022) introduced high-order GNN models that utilize tensor representations and capture k-tuple and k-subgraph information. These high-order GNNs offer improved counting capabilities but come with increased computational and memory complexity. Maron et al. (2019): Chen et al. (2019) reduce the computational complexity of high-order GNNs by working directly with matrix tensor multiplications while maintaining high levels of representation power.
Another research direction, addressing the limitations identified by Xu et al. (2019) Morris al. (2019), focuses on accurately counting substructures by providing GNNs with unique node identi- fier Loukas 2019);; Abboou al. (202T); [Sato et al. (202T). Notably, Abboud et al. (202 Sato ct al. [202]] employ random features as input to GNNs, resulting in enhanced function approxima- Tion. However, this approach sacrifices the essential property of permutation equivariance, which is
fundamental in graph learning. Alternatively, Vignac et al. (2020) incorporate global graph infor-
mation the node level, leading to improved substructure counting capabilities but with increased computational and memory requirements.
Tahmasebi et (2020); You al. (2021); Bouritsas al. (002); Barceló et al. (2021 Bevilacqua et al. (2021 Zhang & Li (2021) Zhao et al. (2021); Bodnar et al. (2021) directly augment GNNs with structural information to enhance their representation power. Some of them, as Tahmasebi et al. (2020); You et al. (2021) Bouritsas et al. (2022) directly augment GNNs with structural or spectral Lim et al. (2022) information, that learn from non-message-passing mechanisms, to enhance their representation power and empirical performance. Others Zhang & Li (2021); Zhao ctt al.] (202T); Bodnar et al. (202I) first identify important subgraphs and then they design message- passing mechanisms that operate according these subgraphs. This way, they learn local subgraph representations that are used to extract global graph embeddings. Transformer GNN architectures have been proposed Veličković al. (2018); Rampášek al. (2022) with increased expressive power. Finally, the statistical guarantees GNNs in link prediction are studied in Chung et al. (2024).
B MESSAGE-PASSING GRAPH NEURAL NETWORKS
The most typical Graph Neural Network (GNN) architecture is the message-passing GNN (MPGNN) (Kipf & Welling 2016 Gilmer al. 2017 Xu et al. 2019), which is usually defined follows:
2 (1-1 (1)
:
(17)
where / (v) is the neighborhood of vertex v i.e., u E A (v) if and only if (u, v) E E. The function f(() aggregates information from the multiset of neighboring signals, whereas g( combines the signal of each vertex with the aggregated one from the neighhoring vertices.
14

---

Published as a conference paper at ICLR 2024
B.1
FROM PEESSAG-PPASSING TO GRAPH CONVOLUTION
When f is the summation function and is concatenation followed by multivariate linear function,
17 becomes:
x = A 21
(1-1) + B(I-1)
Σ
zu !1-1)
(18)
(EA(()
which we write in matrix form
x = x(11) A (111)* + B(-1)),
(19)
where S E {0, NNN is the graph adjacency and the v-th row of X (1-1) is x (u,)) = xb
(t-1)²
For MPNN the recursive formula gives:
(1) -XA 10) + S (0)
(20)
( (1) +SX (())
(21)
=XA00 (1)" SX B(O) A A00 Bay)
52 x B
(22)
= - SXH + S² XH2,
(23)
where X = X (0), Following the previous analysis K MPNN layers yield:
k
Z x
SXH,
(24)
K=
After the K-th layer we can also add a pointwise activation function a (.) and a normalization layer [ which are the norm in deep learning. Then
Σ SX H ]
Y == = (Z)
(25)
Overall, the above expression is an MPNN defined 17
where f()) is the summation function, and (1) is the linear function for 1.... K and the MI. followed by normalization layer for
7 = K.
B.2 THE LOCAL GNN ARCHITECTURE
In this paper, we study a cascade of MPNN layers defined in 25 i.c.,
K 5x
(1+1) = pla (Z)] = [2)]=
Hy
(26)
The type of pointwise nonlinearities that study the Rectified Linear Unit (ReLU), and elementwise powers a (-) = (-)".. We also consider the following types of normalization layers:
| E () (1
(27)
P 1 = E ( [1
(28)
(
(29)
where E is the expectation operator, the Hadamard (elementwise) product, and all the powers are also elementwise.
C TENSOR ALGEBRA PRELIMINARIES
To facilitate our analysis, we briefly present some tensor algebra preliminaries and refer the reader to Sidiropoulos et al. (217): Kolda & Bader (209) for further details.
15

---

Published as a conference paper at ICLR 2024
A N-order tensor X E R is N-way array indexed by di ,g,..., in with elements X (11, 12...., in). consists of N types of modes: (1.22...., X (11, ....,INN........................ X(1,, 12, .2..........
rank-one tensor Z E 1 is the outer product of N vectors defined as:
Z di 02 CN,
(30)
where a1 E R' a2 R2b ,..., aN IR and denotes the outer product. The elementwise formula of the above expression is:
Z(i,, ...,,,, ix) a. (81 (())))((()) ax(i)), Vi,, i2. .2...., iN; Any tensor can be realized as sum of N-way outer products (rank one tensors), i.e.
(31)
x x=
at a o...ooa.
(32)
f=1
The above expression represents the canonical polyadic decomposition (CPD) parallel factor analysis (PARAFAC) Harshman & Lundy (1994) of a tensor. The CPD elementwise representation is:
F
k(,,,
Σ
A (11, A2 5) (N,,
(33)
f=1
where An = [a a a E RRI.P, n :,...:N. N are called the low rank factors of the tensor. A tensor can be fully characterized by its latent factors, model as:
can represent a tensor by its CPD
X [A1, A2,..., AN]
(34)
A tensor be also represented as of matrices, by fixing all the modes but two
X i i3............................ iN] = A₁ (Diag (Aa (iz, :)) o ..... O Diag (An (ix,:))) AT where Diag (A,, (in,) :)) is the diagonal matrix with diagonal equal to AN (fn.:).
(35)
An important operation in tensor analytics is the mode product which multiplics a matrix or a vector to tensor in single mode. A joint mode-1, mode-2...., mode-N product of tensor is represented as follows:
(36) where "x," " denotes the operation that multiplies each column of X with P1, "x2" denotes multi- plying each row of X with P2, and "xx" denotes multiplying each modode of X with Pv- The mode product is reflected in the CPD model of the tensor, i.c., the outcome of results in a tensor X with CPD:
X X x Pi X2 P2 XN Pv
X = [PA P2A2, ... ANAN
D STUDYING GNNS WITH RANDOM INPUT
To analyze the representation power of GNNs we study them with a random input x
[11, I2,
IN] inIR that is characterized by the following moments:
[ 0, E [x="] = I. E [ o wooo x II
E x 0o
x I.
(37)
The characteristic function of takes the form:
jr E (arl))
(jxat)
00
j (t')
Oo, (t) = E [2
E
-1+
(38)
1!
1!
1=
1=2
8 (jt) 1! jt Se - jtt) e tt_ jt
Σ
(39)
As result the joint characteristic function of æ is dz (t.....,tty) I (ctt-jth
As mentioned in the main body of the paper, the first layer of GNN with random input consists of an F set of graph filters that are followed by wise activation functions and normalization layers.
K
Σ S H (S) x, y = p (z)],
(40)
0=0
16

---

Published as a conference paper at ICLR 2024
D.1
SECOND ORDER MOMENT
Since æ is a random vector, so is Z with covariance matrix:
K
E
22
E
hg
S
Fx
Σ hmm S.
h4g
S
xx
hmm S
(41)
k=0
m
K
K
K
S
hmm Sth
H (S)
Σ
Σ
hali S gm
(42)
k=0
m=0
k= m=0
2K
h
S
sk+m
= =
(43)
k.m=0
k=0
So the covariance of is graph filter with 2K + 1 parameters that have K degrees of freedom. The parameters of this graph filter derived from h h h, where is the convolution operation.
From the covariance of we can linearly derive two permutation equivariant features for each vertex. In fact, we sum up all the rows of EE [2z") we get:
2K
E 1222" 1= (S)
Σ k.m=0
ha Sht m
S
S*1,
(44)
k=0
which is linear combination of the h-hop degrees of S. To derive this feature according choose a to be the identity function and (-) = [(-) @ (1" [1==)]. For these choices, we get:
40
y
= (2 E xx
1 H (S)1
hkmm Sk+m1 1.
(45)
k
The second equivariant feature is the diagonal of the covariance matrix, i.e., the variance of z. If we choose a to be the elementwise square function and to be the expectation operator we compute:
y = pla (z)] = 22 diag E 1zz" (2=" = diag [H (S) H (S) = (H) O H (S)) 1, (46)
where (A) E RV is the vector with the diagonal of A E NNN, C denotes the Hadamard (elementwise) product operation, and the last equality comes from the following property:
diag (AB) = (A 3 B,
(47)
for square matrices A, B. Expanding 46 yields the following expression:
y
Σ hakmmiag (5++m)= = -Eno hu.m (s C S 1.
(48)
k,m
k.m
that computes the number of k + m closed paths in the graph with adjacency matrix S.
D.2 THIRD-ORDER MOMENT
we choose a to be the elementwise cubic function and to be the expectation operator we can compute deterministic equivariant node features that measure the skewness of
y1 =ll
E [ superdiag (E [[ (H (S) H (49)
where superdiag (-) R.M is the superdiagonal of the tensor. particular,
Z (
(L)) (S) (j. (S) (ke, n)
(50)
17

---

Published as a conference paper at ICLR 2024
and
superdiag [E o (zozz2)) = -
(1,))
(51)
As result, 1aalt,99e can be cast as follows:
K
K
K
K
hgg
S
S
Nim
St
hmd.m (st S о 5T)) 1.
(52)
1=0
W1=0
k.l.m=0
The expression in can be derived from when a is the elementwise square function, and p
[() @ (1=
X3 1 (H()) (S), (S), 1" H (S)] = H (S) Diag (1' (()H(S)) (S)) ( (53) 2
E
diag E [200z22]] X3 1²) = diag H (S) Diag (1" (S)) H (S)) = (H (S) O H (S) H (S) 1,
(54)
where diag (A) E R. is the vector that contains the diagonal of A E NNN and is different than Diag(-). The last equality comes from the following property that being used a lot in this paper:
diag (ADiag (C)B²) = (A o B) diag (C),
(55)
Overall, 11 takes the form:
K
K
K
K Σ
y/2
S
Sy
Σ
hmm STh
ha (St S S
(56)
1=0
v7 m0
k.
D.3 FOURTH-ORDER MOMENT
The fourth-order moment is defined as follows:
E|zoz0z02] H (S), H (S), (S), H (S))
Σ
hylma
s S"
"" S (57)
k.
We can compute the superdiagonal as: = E [=]] = superdiag (E = = (H (S) @ H H
(S))
(58)
However, E xx4 is not the only equivariant feature derive from the fourth moment tensor E In particular, we can compute:
E 2 (1Tz)
diag [E X3 1 X4 17)
diag ((H H (S), (S), H (S) X3 1 X4
diag (H) (Diag (1 (S)) Diag (1TH H (S))) H (S))
diag [H H (S), 1" H (8), (S)])
diag
H (5) (Diag (1" (5)) Diag (1" H (5)) H (S))
(H (S) H (S)) (H (S) H 1S)
halmm (S* O (S o 1*))
(59)
k
18

---

Published as a conference paper at ICLR 2024
which can implemented when is the elementwise square function and p E () (1²z)²
We can also compute:
a [1²²]]
superdiag
[= x4
superdiag
(S), (8), [S)] ({) x4
superdiag
H (S)
(S) @ (S) @ H (S)
(H (S) O H (S) H (5)10 H (5)1)
Σ
h
(st S Sm 1
(60)
which can be implemented when a is the elementwise cubic function and p [() @ (1" =)]
Finally, we can compute E 22 (1" =]²= = E 1²" 22 1. To derive the exact expression we analyze the following
2 02
[6,1]
K
| STT (1,
R.l.m,m=00
K
lg..mm
S [i,] [1 ml 5T [j.n] S" [i.]]
R.l.mmn=0
Jo..mmm
(S* o S*) [.n] (S e (5) [i.
(61)
k.l.m,n=U
As a result:
E
x
21
hadmm (st о 5') (S S*)
(62)
k.l.m.nDD
and we compute:
(1=2
22
Σ
hg.tmm (S* 5t) (STh ④ 55) 1,
(63)
k.l.m,n=0
which can be implemented when the elementwise square function and p (+) E (-) (1" 1²
D.4 HIGHER-ORDER MOMENTS
When is the m-th moment of z is an m-th-order tensor and takes the form:
E 2] H (S), (S) =
hi
Sim]
(64)
$1
from which we can extract the equivariant individual moment:
K Σ
E " H (S) - ... O (S))
hi
(S" ... ......0
(65)
$1.....
which can be derived by when is the elementwise m-th power and p is the expectation operator. We can also extract other equivariant node features by considering multiple GNN layers type, summing up certain modes of the tensor and applying diagonal super-diagonal operators.
19

---

Published as a conference paper at ICLR 2024
Overall single layer GNN (which corresponds to K MPNN layers, as defined in 26 can compute the following outputs:
K (St 0 (S ......'' 5tm)
his
(66)
$ Am
K
y
...
.... 10.. 5mmm)
(67)
which are derived by the m m-th moment z. The expression in using a (+) = z we can compute the
Proposition D.1 Consider the GNN module in Fig. la
with input a being a random vector with
moments as in 3 The oupput thes] GNN block in Fig. la defined by 23 has closed-form solution
and is equivalent to 66 when a (.) = x and
④ z >mm])] and equivalent to 67
when a (z) = x and (.) = E (-) 0 1
We study the normalization function o = (.) ④ E [2"]] in the following section.
E MULTIPLE LAYER ANALYSIS
In the previous sections, we analyzed a single layer 26 The type of outputs we get from this analysis are presented in 66 and 67] which are deterministic and can be given input other layers defined by either] or 26 In our analysis, the expectation operator enables a deterministic output that maintains permutation equivariance and is applied in the normalization layer following the first layer.
corresponding to multiple layers of [
However, it can also be the case that E [-] is applied after multiple layers. To understand the effect of multiple layers we study the following cases:
E. TWO-LAYER GNN WITH (-) = (.)2
We consider two GNN layers defined by [66] where (-) (-) p is equal identity after the first layer and p []] = EE] [-] after the second layer. Then the output of the first layer is:
2
(1) = 2
Σ km=0
(1)
S x
(68)
and the output of the second layer is:
K Σ
E
12
(2)
Sh 22
(69)
To derive expression for x. (2) we study:
K h
K
E
www
T
E
só
S
2
g
(70)
==0
1=0
==0
1=0
To compute E
2 2T
use the expression in 62
K
K
K (St 3 S
E
wwww]
T
S
hadma
g
1=0
k.L.m.
1=0
Σ
hel.maaas
O (ST G S*
(71)
20

---

Published as a conference paper at ICLR 2024
and therefore:
a
I.t. (S* (5% ( o*) (S . ( o5*)
(72)
E.2 TWO-LAYER GNN WITH 1| = ()) O 2²
IN THE FIRST LAYER
Finally, we study two-layer GNN defined by 26 where a is the identity in the first layer, a (.) (-)²
in the second layer, p = (.) o EE xx² after the first layer and p [ E [-] after the second layer.
Then the output of the first layer is:
K
K
=
k
O
E
S
x
k
S a
Σ k=0
h
diag (5*)
R==0
1==0 0
k=
2K
2K
Σ "
S
S
(1) (1)
(S 3 &1
(73)
k=0m=
k=0 m=0
The covariance of (1)
takes the form:
K 2
K 2K
E x (1)
(1)
1 (St + OOS
b 1i x
( (1)
sh (S 2
1==0 m==0
k= m=
( (1)
S ② S)
(2) (1)
S (5
k=0
A= m=
-EME Wka. (st о 1) S (S 1
(74)
k.7.m
and the output of the second layer is:
K
a
(2) E [w="]
k
(2)
(1)
(75)
k=
To derive an expression for x: (2) we study:
K
K
E
"ww""
T
E
h
S
(1)
1 S
(2)
h
S
(1)) (1)
Σ
h S'
(2)
i=0
Σ
St (st ② 1) S (S S)
(76)
k.I.ma..=00
As a result:
x (2)
A.l.m..,diaa (Sa (s* ② 1) S (5th )n))
(77)
We also study two-layer GNN defined by 26 where is the identity in the first layer and the second
layer, p| = (.) @ E = after the first layer and (-)) = [(-) @ (1" 2)] after the second layer.
Then the output of the second layer is:
z
E ww (12 w) E wwww
(78)
As result:
x
Σ
heLmin St (S ② S) (5 о I)S
(79)
k.J.m....0
21

---

Published as a conference paper at ICLR 2024
F COUNTING CONNECTED COMPONENTS: PROOF OF THEOREM 4.1
To prove Theorem 4.1 consider the GNN definition in 4 where we use the Laplacian of a graph as the graph operator 5. Then the spectral decomposition of is:
S = UAUT Σ unnn
(80)
where A is an eigenvalue of S with corresponding eigenvector un The graph convolution in 4 can be cast as:
K
K Σ k=
K
2
hi
Sh x
UUA
Σ K=U
hk
Σ
An
h
un uT
k=U
K
n u U
T x
Σ
h (An) 24n un
(81)
k=0
where
K Σ k=0
h (An)
h4
hg
(82)
the frequency representation the graph filter. Now let (f1,.... ,.g) } be the set the distinet eigenvalues of set of Laplacians (S.) corresponding set of graphs {Gi) Then we can write the following linear system of equations:
h (mI)
M1 p K-1
ho
h (122
1 H2 22
11
k K-1
h1
Wh
(83)
h (pq)
Mi u 1g
[K
W is Vandermonde matrix and when K 0 the determinant of W takes the form:
det (W) II iisijo (14 14))
(84)
Since the values 14 distinct, W has full column rank and there exists graph filter with unique parameters h that passes only one eigenvalue (the k-th eigenvalue), i.c.
1, if i=k h (p:) = 0. if i
(85)
The number of connected components in graph is equal to the multiplicity of the zero eigenvalue of the Laplacian matrix. We can design a graph filter to isolate the eigenvalue i.e.,
1, A=
h (A)
(86)
0, 0
we use the graph filter in 86 in the definition graph convolution in 81 we get:
==U,U x.
(87)
where Un is the eigenspace corresponding to the zero eigenvalue of the Laplacian. Then we feed 87 with random input R with characteristie function dw (f1,.... tx) II (elt: jt,) and
moments defined in 3 If a is the elementwise square function and is the expectation operator, the output 87 takes the yields:
Ø-1
K-1
= E [2-] diag EE [xz²]) diag Σ
h S
[xx
Σ m=0
S
K
diag
Σ k=
S
Σ
Sm
diag (UOU"UGU??) diag (U)U?") (88)
m=0
22

---

Published as a conference paper at ICLR 2024
Therefore the output is the diagonal of matrix with rank equal to the number of connected components r. The eigenvalues of U are 1 with multiplicity equal to the number of connected components and À with multiplicity N Then 1 y takes the form:
1 F y trace (UDU)) = Σ =r
(89)
R
and a single layer GNN, defined 87 can count the number of connected components of graphs {G.)
G COUNTING CYCLES
To prove that the considered message-passeen GNNs can count cycles, we use the formulas in Perepechko & Voropaev (2009) that associate the number of cycles in graph with the graph adjacency.
G.1 PROOF OF THEOREM 4.2
The number of triangles within graph is defined as follows:
(S 5)
(90)
This can be computed by the expression in 6 The number of tetragons and pentagons within graph defined as follows:
T ((S の 52) 1+ ( 1)
(91)
3 1 o @ 55 + 1) 1 1T = 10 -
((s
(92)
All terms in ca, cs can be computed by 6 apart from S (S² 3 1) and S (S² @ S). To compute these terms we just need to pass 6 through one more MPNN layer.
G.2 PROOF OF THROREM
1
6
(S o -
0 1 000-00$00$00000-00000 s
12
(5 1 ( 1)
+ -
125 (S 6 4
(93)
We observe 5 types of terms in cg!
(S* St)
(94)
S (S* S
(95)
S2 (S* S 1
(96)
Ss S
(97)
(S*
5
(98)
The term in 94 can be computed by whereas 95 and 96 computed by passing 6 through
two more MPNN layers respectivelly. Similarly the term in 97 can be computed by 10 whereas 98 by passing 10 through one more MPNN layer.
23

---

Published as a conference paper at ICLR 2024
G.3 PROOF OF THEOREM 4.5
c² 1T 9 (
+ +4(5088880117770011111111111
+ 77 +
(99)
We observe 5 types terms in o7!
@ 2 (S (s
(100)
(101)
S1
(102)
SS*
(103)
S
(104)
The terms in 100 103 and 104 can be computed by 10 and 13 respectively. The term in 101 can
be computed by passing 6 through MPNN layers, whereas the term in 102 can be computed by passing 12 through MPNN layer.
H COUNTING QUASI-CLIQUES
To prove that the considered message-passing GNNs can count quasi-cliques, use the formulas in Barik & Reddy 2023) that associate the number of certain substructures in a graph with the graph adjacency.
H.1 PROOF OF THROREM 4.4
The authors in Barik & Reddy 2023 derive the following equations:
1 1" (s O S 1" (s o 10) 1²
Q+ 1" SS S2
(105)
= IT (S S
S)1+ 1 1s ( 8) 101-11'S SS S) 4Q4,
(106)
which can be computed by and 10 followed by classical message-passing layer.
I PROOF OF PROPOSITION 5.2
The proposed architecture more powerful, for certain problem classes, than the I-FWL test (1-WL and 2-WL) since it can count graph structures that I-FWL cannot. It is strictly more powerful since produce exactly the same outputs I-FWL when f, I are injective.
PROOF OF THEOREMS 6. 6.2 6.3
J.1 LISTING ALL THE TRIANGLES WITHIN GRAPH
Now let T denote the triangle tensor, i.e.,
A S [ S [j k] ki,
(107)
T k] = 1 nodes i, l form a triangle and T j. k]] = 0 otherwise. Unfortunately. does not admit obvious tensor model with factor matrices the adjacency powers.
24

---

Published as a conference paper at ICLR 2024
Instead, we will consider different type of tensor G such that:
ji S [ k] S يا A:] + [i,j]] S S [i.)),
(108)
which is simplician complex tensor that measures relationships between node triplets. In particular G j, k| 3 when ji k). is triangle, G j, k] = 1 when there are two edges between i. or when and (i, k) E. G 1 also when
and (i,j) E & when k and ki, E E. j. 0 in any other case. It is therefore clear that:
T = mod3
G = ReLU [G - 2]
(109)
Interestingly G can be written using the following CPD models:
G = |, + |5, S1 + [1,
(110)
From equation X get that:
K Σ
B [H (S)]
hins
(111)
which concludes our proof.
J.2
COUNTING CLIQUES
The tensor of 4-th order cliques is:
1,i.j, = S(r S k. | [2,4] S G.. S (k,
(112)
1, = 1 if nodes i, k. form elique and Q, = 0 otherwise. Unfortunately Q does not admit an obvious tensor model with factor matrices the adjacency powers. The number of 4-node cliques in a graph is given by:
41
Σ S S S [.. S K.K.K.
S $6.4 [1.4
S [k,
(113)
which is equal
44 = Σ Tis.i, $ (.. S [k.
(114)
By rearranging the summations we get:
91 91 E A S S(.
(115)
fJ..
The inner summation corresponds to the diagonal element a third-order tensor with Tucker model:
ST
(116)
where T the core tensor and S are the factor matrices. To compute the number of 4-node cliques sum the superdiagonal of the tensor above, i.e.,
q4 1 superdiag (IT (T
(117)
When the input to the GNN is æ as described in Section then
E
3 superdiag ([T. H (S), H (S), ()),H(S)))
h superdiag 1",
(118)
fg
which concludes our proof.
25

---

Published as a conference paper at ICLR 2024
J.3 COUNTING 8- 8-NODE CYCLES
To count the number of 8-node cycles in graph using message-passing operations we use Lemma 7 in Barik & Reddy (2023). All the terms in this formula be computed using Hadamard product operations, as discussed in other sections. The only terms that cannot be computed with Hadamard products are those of the following form:
e, - S S(i,j] S 5 S(i,A] [2,1] S
[i,0]
St [k. 4].
(119)
This term can be computed by the procedure discussed in Section 6 and J.2 i.c., by equation [[8 This concludes our proof.
K COUNTING CYCLES AT THE NODE LEVEL
In this section, we study the ability of GNNs defined in or 26 to produce permutation equivariant node representations that count the number of cycles each node is involved in. To this end, derive the following theorem.
Theorem K.1 (Node-level Cycles) There exists GNN defined in or that generates permutation equivariant node representations that count the number of siszze cycles each node participates, for any graph and & < 7.
K. PROOF OF THEOREM K.
To prove Theorem K.I we use the expressions in Perepechko & Voropaev (2009) that instantiate the matrices k- k-paths Pk. To be more precise Ps (i.j) counts the number of paths k-paths between nodes i and j.
K.2 MATRICES OF k PATHS FOR UNDIRECTED GRAPHS
Starting from the definition of k --tptth matrices, as presented in Pereppechko & Voropaey (2009), we can compute k-path matrices Ps for undirected graphs. After some algebraic manipulations Ps for 3 < le < 6 can be cast as:
P3 = -
(120)
Pi = 2 - (S e1
-
25
(121)
P3 -5 9
+ ($$$9f.011000)3355(($$88)801
+ 353 4S
(122)
The number of terms in Pg is large enough and therefore we split them in terms, i... Po =
P! Pe + P3 + P..
26

---

Published as a conference paper at ICLR 2024
(0000000000000000000000000011100 Pg =5
[
=58-0|55565510114444000004444333 +2($"09)5422((099))
(123)
(8
(1
-
(124)
P 3S - (8
+86663999(((553))0000554((000060 (88
(125)
Pd
(5501)98666600001113333333313333 o s)
- o 25 cl
-
+ 4 S 125
(126)
K.3 NODE LEVEL CYCLES FOR
For k: < the number of node level cycles can be computed as (P& 1) The following
expressions are derived after some algebraic manipulations.
1110111 (S3 1
(127)
27

---

Published as a conference paper at ICLR 2024
(POO)1= (S o 5 1- o1) - 1) 1
(128)
S1
(
(129)
The terms involved in the expressions for (P& 3 1, (P) 0 1)1, (Ps C I) can all be computed
by GNN defined by or 26 shown in Appendix D
P ④ 1 01)
- -2 -1
0 o S1
+4(5
- (S S1+ 2 0111
(130)
(P o 051
2 6$$ o
- 3
(131)
where used the following expression.
diag( ())))))))))))))))))))))))))))))) = (5
o Sa1
(132)
The terms involved in the P ④ 1)1, (P) & I) can be computed by GNN defined by or 26 as shown in Appendix D
(Pd ④ 1ori=s' 6 (S 1 6 o (2) 1 0 S S
SS S)
(133)
The last term can be computed by two-layer GNN defined by 26 where o (.) = (-)*, is equal to identity after the first layer and p E [-] after the second layer. Thorough analysis is presented in Appendix E
④ 1) S1 1 2 S) 1251
(134)
The terms involved in the (Pg e 1, (P) о I) can be computed by GNN defined by or 26
as shown in Appendix D and Appendix
K.4 NODE LEVEL CYCLES FOR l: 7
For = the number of node level cycles can be computed as 1 (Pa @ S) or diiag (SP)). The following expressions derived after some algebraic manipulations.
28

---

Published as a conference paper at ICLR 2024
- P @ 1- (5* о (
-(905)
+ = o
+ diag
($)
2 diag (
5 (s ( 0
+2 (
(
S) diag (S 01) (5 (8))),,
(135)
where we have used the following identities:
(S + s) 1)
(S ss o 1) = s (s o vee (5 2 I) vec (5² (5² )
diag (s ② S
0 1)) = (s o vec (S o vec (5a о 1)))
= =(s² o (s 1- (S о 1)
The terms involved in the [P] S) can be computed by GNN defined by o 26 shown in Appendix D and Appendix
(P) 6) 1 2 diag
o o S)
+ (S (
+ + (S ($ diag ( (8 ($ o1)
-
-3 - o
-6 6 d ($ (
- 2 S1
(136)
(P o S)1 (S² (
diag (1 0
+ diag (1( o
+ diag (8(
(137)
29

---

Published as a conference paper at ICLR 2024
triangles
letragons
10,000
pentagoos
hexagons
heptagons
octagons
nonagons
5,000
decagons
0
Figure 2: Histogram of cycles that appear in the ZINC dataset. The x axis indicated the number of cycles in each graph and the axis shows the number of times each of the cycle counts appears.
(P o S) = 18 (8 o
0 S)
5$
(S 56 ( 2 05
(138)
All the terms involved P& @ S) can computed by a GNN defined by 26 as shown in Appendix D and Appendix E
L COMPUTATIONAL AND MEMORY COMPLEXITY
There are two different ways to implement the proposed Moment GGNN. The first is feed it with random vectors and compute the empirical moments, and the second is to work directly with the equivalent model. In the first scenario, the complexity of Moment-CNN complexity of message-passing GNN. For instance, the memory complexity of the forward pass of number of graph filters (hidden dimension, or width) in each layer,
exactly the same as the
GIN is θ (IV[F), where and the computational complexity θ [[V]F2 + (E]F). . we use the equivalent model. We need perform the following type of operations, before training or testing.
S
5th) (Si++1 10-+00000 5t
As result, the forward pass memory, and computational complexity of Koment-GMY GNN is ((V)F) and e [[V] F)) respectively. However, there is an additional preprocessing memory com- plexity θ (nnz (Sm)n((aa) and computational complexity of θ (|V)]E)). nnz counts the number of nonzeros in matrix. Note that, if the sparsity of the matrices is very high specialized sparse matrix multiplication algorithms can be employed to further reduce the computational complexity. Additionally, since max (ix) is usually small (in proofs is less than equal 5) the memory complexity is in the order of [g].
M EXPERIMENTS
In this section, discuss the implementation details of the experiments presented in Section 7 We also present baseline comparisons in detecting the presence of gonode and 10-node cycles in the ZINC dataset. The statistics of ZINC are illustrated in Fig.
30

---

Published as a conference paper at ICLR 2024
Table 6: Classification accuracy for cycle detection ZINC
Algorithm
Nonagon
Decagon
Training
Testing
Training
Testing
Moment-GNN
100
99.8
99.9
99.4
SMP
100
99.6
99.8
98.2
GIN rand id
92.4
89.8
88.5
77.0
Ring-Gu GNN
98.3
98.3
88.5
87.9
PPGN
93.9
91.1
88.0
87.1
M.1 IMPLEMENTATION DETAILS
The experiments are conducted on a Linux server with NVIDIA RTX 3080 GPU. The code of the proposed architecture with all the experiments can be found in this repository
To perform cycle detection (graph classification) we use the specifications in htllttps://iittee /gthhb com/ cvi htvgggna/////ooooo SMP In particular, the Moment-GN layer is followed by a 6-layer GIN with, which we train with stochastic gradient descent optimizer, initial learning rate equal to 10-3 batch size equal to 16 and dropout ratio equal to 0.5. For the synthetic data experiment, epochs to train whereas for the ZINC data experiment, we use 1000 epochs. The hidden dimension for the GNN layers is 32 and for the output (classification layer) 128.
300
To perform cycle counting (graph regression) we use the specifications in https:://ittuut
ccmm//pouritsas/// GSN The Moment-GN. layer is followed by 2 MPNN layers, which are trained with Adam for 1000 epochs. initial learning rate equal to 10 and batch size equal to 16. Each layer is followed by a 3-layer MI. with ReI.U activation function and a batch normalization layer. The hidden dimension for the GNN layers is 128. In this set of experiments, we use CPU implementation.
M.2 BASELINE COMPARISONS
Following the discussion in Section 7.3 we compare the performance of the proposed Moment in the last two tasks, i.e., detect a nonagon or decagon in the ZINC dataset. As mentioned in Section 7.3, we train and test with subset of the available graphs to ensure balanced classes. We use 70% of the graphs for training 20% for testing and 10% for validation. The baselines used for comparison are GIN with random input GIN + rand id Xu al. (2019): Abboud et al. (2021); Sato et al. Ghhn (2021) PPGN (Maron et al. 2019), Ring-GNI Chen et al. (0019) and SMP (Vignac et al. 2020).
The training and testing results for detecting nonagons and decagons presented in Table 6 We observe that detecting a decagon is a more challenging task in this dataset. Moment-Gii achieves the best testing performance, whereas SMP demonstrates similar performance. Compared at least 11.5% percent better in detecting decagons,
to the remaining baselines, Moment-GNB 1.5% better than Ring- GNN and least 8% better than GIN + rand id and PPGN detecting nonagons, It is notable that although both Woment-GNN and GIN + rand id use random input, Moment-G GNNN markedly better in both tasks. This is due the fact that our proposed framework is able to maintain the pivotal property of permutation equivariance, contrary to GIN + rand id.
Ring-GNN
In logP prediction and graph classification we use the following baselines;
logP prediction Baselines: GCN Kipf & Welling (2016), GIN Xu et al. (0019) GraphSage
Hamilton et al. (2017), GAT Velickvié
(2018), MoNet Gilmer al. (2017). GatedGCN
Bresson & Laurent (2017), GIN + rand id PNA Corso et al. (2020). DCN Beaini et al. (201))
GNNLL Balcilar al. (202T). HIMP Fey et al. (2020). SMP Vignac al. (2020). and GSN with
cycles Bouritsas et al. (2022), CTN Bodnar et al. (202)) CTN- sma
Bodnar et al.
202
GraphSage+sud Barceló et al. (2021), ), CAT+sul Barceló et al. (022)) MoNet Barceló
ct al. (2021). CaatedGC++sul Barceló et al. 2221). GCN+sub Barceló et al. 2021
31

---

Published as a conference paper at ICLR 2024
Table 7: logP Prediction in ZINC
GNN Model
MAE
MAE (EF)
GraphSage
0.410 + 0.005
GraphSage+sub
0.24 = 0.01
GAT
0.463 = 0.002
GAT+sub
0.22 + 0.010
Table 8: logP Prediction in ZINC-full
MoNet
0.407 = 0.007
MoNet+sub
0.16 = 0.01
GatedGCN
0.422 + 0.006
0.363 + 0.009
Method
MAE
GatedGCN+sub
0.135 0.01
HIMP
0.036 0.002
PNA
0.320 + 0.032
0.188 + 0.004
CIN-small
0.044 + 0.003
DGN
0.219 = 0.0102
0.168 + 0.003
GIN
0.088 1 0.002
GNNML
0.161 = 0.006
Moment-GNN
0.041 1: 0.001
HIMP
0.151 + 0.006
SMP
0.219 0.322 = 0.026
0.138
GIN + rand id
0.279 = 0.023
GCN
0.469 + 0.002
sCb+
0.20 + 0.01
GIN
0,254 + 0.014
0.209 + 0.018
GSN with cycles
0.140 = 0.006
0.115 + 0.012
Moment-GNN
0.140 + 0.004
0.110 + 0.005
Graph Classification Baselines: GCN Kipf & Welling (2116). GIN Xu al.
(2019).
Bresson
& Laurent (2017). GIN + rand id, GSN with cliques Bouritsas et al. (2022)
AWL
Ivanov &
Burnaev (0188) DGK Yanardag & Vishwanathan| (2015), PATCHYSAN Niepert al.
(0166)
RetGK
Zhang et al. (2088), 8), Wikernel [Shervashidze et al. (001 and WEGT. Kolouri et al.
2020)
We also compare against some extra baselines in Barceló al. (2021). The new comparisons can be found in Table
M.3 ZINC-FULL
We also test the performance the proposed Moment-GNh in the task of logP prediction using the full version of the ZINC dataset. ZINC-full contains about 250,000 molecular graphs with up to 38 heavy atoms. Without adjusting any hyperparameter of the architecture used for the small ZINC dataset that contains 12,000 graphs, are able achieve MAE between the and predicted logP value in the order of 10 2 We compare against GIN and HIMP which are generic architectures as Moment-GNN, and CIN which is specific architecture for molecular graph processing. The results are reported in Table g Note that in the table we report the small version of C CTN that uses a similar number of parameters as our architecture for fair comparisons. The full version of CTN achieves MAE 0.022 + 0.002.
32


Reviews:
[{"review_id": "5Bi1MUxjOG", "reviewer": "Reviewer_jgwt", "summary": "This paper studied the problem of detecting/counting graph structures such as cycles, cliques, and connected components, using MPNNs with random initial node features. They considered taking the high-order moment of the neural network output to obtain deterministic node representations. In this case, the authors proved that with the increase of the order, the resulting GNN can express more and more graph structures, resulting in higher expressivity. Experiments demonstrate the expressive power of the proposed method.", "questions": "See the box above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "1. The theoretical results of this paper are rigorous and correct (although proving it is straightforward given prior work).\n2. The proposed method is quite interesting. Prior to this work, researchers mainly improved the expressive power of GNNs by sacrificing the computational costs, e.g., using higher-order GNNs. While in this paper, the proposed GNNs only have linear complexity. On the other hand, using random node initialization has been proposed in prior work. However, unlike prior work, this paper achieves equivariance by using an expectation in the final layer (although there may be other weaknesses, see below). The authors showed promising theoretical results for this architectural design.", "weaknesses": "1. This paper is poorly written. Please carefully polish the paper in the rebuttal period. Several problems include: (1) the word \"equation\" is redundant in many places; (2) many definitions are unclear. For example, what do you mean by \"x is anonymous\" in page 4, and what do you mean by \"stationary random vector\"? (3) the paper even exposes the author name \"Charilaos\" in page 6. Please fix it. (4) What is role of the characteristic function in page 3? Why is it unrelated to x?\n\n2. Regarding the theoretical results:\n   - The authors only proved positive results for the expressive power of GNNs using high-order moments, which are incomplete. Does the GNNs fail without high-order moments? In other words, are the theoretical results tight? For example, can the GNNs count 6-cycle using only 2-order moment, and can the GNNs count 7-cycle using only 3-order moment?\n   - I do not think Theorem 4.1 is meaningful. The theorem uses a GNN to fit the number of connected components of a *single* graph, which is just equivalent to fit a constant if I understand correctly.\n\n3. Regarding the experiments:\n   - The proposed method relies crucially on taking the expectation in the final layer. How do you implement this in your experiments? Will a large number of samples be needed?\n   - I found from the results that the GNNs can even count 8-cycles perfectly but the current theory did not prove it. What is the number of moment order required in your experiments?\n\n   Please give more details in your paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DNpenbwHOq", "reviewer": "Reviewer_4Tmr", "summary": "This paper studies the representation power of GNNs in terms of counting graph substructures, including cycles, quasi-cliques, and connected components. The authors employ tools from tensor algebra and stochastic processes, and they demonstrate that with appropriate activation and normalization functions, GNNs can generate permutation equivariant node representations that capture statistical moments of the GNN output distribution.", "questions": "1. When performing graph regression task on dataset ZINC, does the 10000 training graphs, 1000 validation graphs and 1000 test graphs are randomly sampled or they are from the ZINC-100K? For a more fair comparison, can this experiment implemented on whole ZINC dataset?\n\n2. Proposition 5.2 show that Moment-GNN can improve expressivity over 1-FWL. What about the upper-bound on its' expressive power?  Is it bounded by 3-WL like subgraph GNNs [1]?\n\n[1] Frasca, F., Bevilacqua, B., Bronstein, M., & Maron, H. (2022). Understanding and extending subgraph gnns by rethinking their symmetries. Advances in Neural Information Processing Systems, 35, 31376-31390.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The exploration of the graph substructure counting ability in the context of GNNs constitutes a novel contribution to this field. This particular property is closely tied to the representational power of GNNs and is critical for numerous real world graph modalities like social networks, making it a pertinent and valuable topic for discussion.\n\n2. The theoretical analysis presented in the paper is extensive and commendable, shedding light on various aspects of the subject matter.\n\n3. The empirical experiments conducted in the paper aligns well with theoretical findings and demonstrates the effectiveness of proposed method.", "weaknesses": "1. Many powerful, expressive, and well-adopted  GNN baselines are missed. For instance, GNN-AK[1], GrphGPS[2], CIN [3], ....\n\n2. The technique of encoding substructures in graphs is widely used in GNNs to improve the expressiveness, such as EGO [1], GNN-AK [1] and NGNN [4].  I think the comparison with these substructure-based GNNs should be discussed.\n\n[1] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with local structure awareness. In International Conference on Learning Representations,2022.\n\n[2] Rampášek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., & Beaini, D. (2022). Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35, 14501-14515.\n\n[3] Bodnar, C., Frasca, F., Otter, N., Wang, Y., Lio, P., Montufar, G. F., & Bronstein, M. (2021). Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34, 2625-2640.\n\n[4] Zhang, M., & Li, P. (2021). Nested graph neural networks. Advances in Neural Information Processing Systems, 34, 15734-15747.\n\n[5]  Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WcaJ9pFjdZ", "reviewer": "Reviewer_K7V4", "summary": "This work studies the substructure counting power of a message-passing neural networks (MPNN) with random input. Concretely, the function class of interest is the expectation of outputs of standard MPNNs with random node features. They prove that this model can count up to 7 cycles, which is more powerful than regular MPNN with constant input. Moreover, the model is shown be equivalent to a deterministic graph filtering with constant input, where the filter is a hadamard product of polynomial filters. The equivalent filtering model has a better empirical performance over tasks such as substructure counting and molecular property prediction.", "questions": "- I was wondering if large cycles (such as 8 cycles) can also be written as hadamard product of $S^k$ and thus can be expressed by the model? I know the construction of such function is pretty combinatorial, so probably the question is open. But it is interesting as 7 cycle is also the counting limitation of 2-FWL.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Though it is known that random node feature injection can improve expressive power, it is interesting to see such analysis in an average meaning (thus perserving equivariance), and the connection to the corresponding graph filtering.", "weaknesses": "- The comparison to other baselines on cycle counting and ZINC is insufficient.\n- I feel like the sentence in the abstract \"However, their ability to count substructures, which play a crucial role in biological and social networks, remains uncertain\" may be confusing in the sense that, the counting ability of regular MPNN is pretty clear as shown in [1].\n\n\n[1] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383–10395, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PcTIOT9Jl8", "reviewer": "Reviewer_QJcy", "summary": "This paper focuses on the representation power of GNNs and their ability to count graph substructures. The analysis enables the design of a generic GNN architecture that achieves good performance in various tasks, including subgraph detection, subgraph counting, graph classification, and logP prediction. The paper also provides both theoretical and experimental evidence of the ability of GNN to count graph substructures in graph-level representation learning tasks.", "questions": "See the weaknesses above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The paper studies an important problem: the ability to recognize subgraphs is crucial in graph applications.\n\n2. The authors provide detailed deductions of how to design the proposed GNN to identify different numbers of graph substructures.", "weaknesses": "1. Writing quality: The presentation and the layout of the paper need to be improved substantially. Equation spacing/referencing is not correct with editing hints unremoved. \nThe paper is hard to follow. A clear introduction/navigation at the beginning of each section is lacking. This is particularly the case in the methodology part, which confuses the reader.\n \n2. Experiments: The experiments show that the proposed GNN has good capability of substructure counting. However, this may not lead to better performance on downstream tasks. There are many benchmark datasets commonly used for node-level and graph-level tasks. Testing on more datasets will better demonstrate how counting substructures can help improve the performance of other tasks.\n \n3. For the regression task on ZINC, the method proposed in ‘Graph Neural Networks with Local Graph Parameters’ accepted by NeurIPS 2021 seems to have a better result, which is not included in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)